Light Rays:

• Light travels in straight lines.
• Light rays do not "collide" with each other if they cross.
• Light rays travel from the light sources to the eye (but the physics is invariant under path reversal - reciprocity).

Ray Casting:

1. Generate an image by casting one ray per pixel

2. Check for shadows by sending a ray to the light

   Pinhole Camera Model:

Recursive (Whitted-Style) Ray Tracing

Ray-Surface Intersection

Ray Equation: Ray is defined by its origin and a direction vector. Ray equation is $\Large \vec{r}(t)=\vec{o}+t\vec{d}$ $(0\le t<\infty)$.

$\vec{r}$ : point along ray; t: time; $\vec{o}$: origin; $\vec{d}$: (normalized) direction

Ray Intersection With Sphere:

• Ray: $\Large \vec{r}(t)=\vec{o}+t\vec{d}$ $(0\le t<\infty)$

• Sphere: $\vec{p}$ : $\Large (\vec{p}-\vec{c})^2-R^2=0$

• Solve for intersection: $\Large (\vec{o}+t\vec{d}-\vec{c})^2-R^2=0$

• Expand into a quadratic polynomial: $at^2+bt+c=0$, where

  • $a=\vec{d}\cdot\vec{d}$
  • $b=2(\vec{o}-\vec{c})\cdot\vec{d}$
  • $c=(\vec{o}-\vec{c})\cdot(\vec{o}-\vec{c})-R^2$

  $\Large t=\frac{-b\pm\sqrt{b^2-4ac}}{2a}$

Ray Intersection With Implicit Surface:

• Ray: $\Large \vec{r}(t)=\vec{o}+t\vec{d}$ $(0\le t<\infty)$
• General implicit surface: $\vec{p}$ : $\Large f(\vec{p})=0$
• Substitute ray equation: $\Large f(\vec{o}+t\vec{d})=0$
• Solve for real, positive roots

Plane Equation: Plane is defined by normal vector and a point on plane. Plane Equation (if $\vec{p}$ satisfies it, then $\vec{p}$ is on the plane): $\vec{p}$ : $(\vec{p}-\vec{p}^\prime)\cdot \vec{N}=0$, $ax+by+cz+d=0$.

$\vec{p}$: points on plane; $\vec{p}^\prime$: one point on plane; $\vec{N}$: normal vector

Triangle is in a plane:

• Ray-plane intersection
• Test if hit point is inside triangle

Ray Intersection With Triangle Mesh:

• Ray equation: $\Large \vec{r}(t)=\vec{o}+t\vec{d}$ $(0\le t<\infty)$

• Plane equation: $\vec{p}$ : $\Large (\vec{p}-\vec{p}^\prime)\cdot \vec{N}=0$

• Solve for intersection: Set $\vec{p}=\vec{r}(t)$ and solve for t

  $\Large (\vec{p}-\vec{p}^\prime)\cdot \vec{N}=(\vec{o}+t\vec{d}-\vec{p}^\prime)\cdot \vec{N}=0$

  $\Large t=\frac{(\vec{p}^\prime-\vec{o})\cdot\vec{N}}{\vec{d}\cdot\vec{N}}$ Check: $0\le t<\infty$

Moller Trumbore Algorithm: A faster approach, giving barycentric coordinate directly.

Accelerating Ray-Surface Intersection

Bounding Volumes: Quick way to avoid intersections: bound complex object with a simple volume

• Object is fully contained in the volume
• If it doesn't hit the volume, it doesn't hit the object
• So test BVol first, then test object if it hits

Ray Intersection With Box: box is the intersection of 3 pairs of slabs. Specifically, we often use an Axis-Aligned Bounding Box (AABB, 轴对齐包围盒).

Ray Intersection With Axis-Aligned Box: Compute intersections with slabs and take intersection of $t_{min}/t_{max}$ intervals.

2D example; 3D is the same!

• The ray enters the box only when it enters all pairs of slabs

• The ray exits the box as long as it exits any pair of slabs

• For each pair, calculate the $t_{min}$ and $t_{max}$ (negative is fine)

• For the 3D box, $t_{enter}=\max\{t_{min}\}$, $t_{exit}=\min\{t_{max}\}$

• If $t_{enter}<t_{exit}$, we know the ray stays a while in the box (so they must intersect)

• Ray is not a line. Should check whether t is negative for physical correctness.

  • If $t_{exit}<0$: The box is "behind" the ray —— no intersection
  • If $t_{exit}\geq0$ and $t_{enter}<0$: The ray's origin is inside the box —— have intersection

  In summary, ray and AABB intersect if and only if: $\Large t_{enter}<t_{exit}\&\&t_{exit}\geq0$

Uniform Spatial Partitions (Grids)

Grids

Preprocess —— Build Acceleration Gird:

1. Find bounding box

2. Create grid

3. Store each object in overlapping cells

4. Step through grid in ray traversal order

   For each grid cell, test intersection with all objects stored at that cell

Grid Resolution:

• One cell: No speedup
• Too many cells: Inefficiency due to extraneous grid traversal
• Heuristic: #cells = C * #objs, C $\approx$ 27 in 3D

When They Work Well: Grids work well on large collections of objects that are distributed evenly in size and space

When They Fail: "Teapot in a stadium" problem

Spatial Partitions

KD-Tree Pre-Processing

Data Structure for KD-Trees:

• Internal nodes store

  • split axis: x-, y-, or z-axis
  • split position: coordinate of split plane along axis
  • children: pointers to child nodes
  • No objects are stored in internal nodes

• Leaf nodes store

  • list of objects

Traversing a KD-Tree:

1. split A:
2. assume 1 is leaf node:
3. split B and assume 2 is leaf node:
4. split C and assume 3 is leaf node:
5. Intersection found:

KD-Tree's problem:

• Objects may exist in multiple boxes
• The establishment of KD-Tree is not simple, need to consider the intersection of triangles and boxes

Object Partitions & Bounding Volume Hierarchy (BVH)

Bounding Volume Hierarchy (BVH)

• 
• Continue to divide:

Building BVHs:

1. Find bounding box
2. Recursively split set of objects in two subsets
3. Recompute the bounding box of the subsets
4. Stop when necessary
5. Store objects in each leaf node

How to subdivide a node:

• Choose a dimension to split
• Heuristic #1: Always choose the longest axis in node
• Heuristic #2: Split node at location of median object

Termination criteria: stop when node contains few elements (e.g. 5)

Data Structure for BVHs:

• Internal nodes store:

  • Bounding box
  • Children: pointers to child nodes

• Leaf nodes store

  • Bounding box
  • List of objects

• Nodes represent subset of primitives in scene: All objects in subtree

BVH Traversal:

Intersect(Ray ray, BVH node){
    if (ray misses node.bbox) return;
    if (node is a leaf node){
        test intersection with all objs;
        return closest intersection;
    }
    hit1 = Intersect(ray, node.child1);
    hit2 = Intersect(ray, node.child2);
    return the closer of hit1, hit2;
}

Spatial vs Object Partitions

• Spatial partition (e.g. KD-tree)

  • Partition space into non-overlapping regions
  • An object can be contained in multiple regions

• Object partition (e.g. BVH)

  • Partition set of objects into disjoint subsets
  • Bounding boxes for each set may overlap in space