Ray casting

• Pinhole camera model

  

  

• Algorithm

  for each pixel (i, j)
    generate ray r from eye through pixel (i, j)
    if r intersects an object then
      color = ambient
      for each light
        color += shading from this light
        (depends on light and material properties)
        (if needs to add shadows, check if the intersection point is in shadow area of the light)
      return color
    else
      return background color

Whitted-Style ray tracing

• Recursive ray tracing

  

  

• Algorithm

  IntersectColor(vBeginPoint, vDirection)
  {
    Determine IntersectPoint;
    Color = ambient color;
    for each light
      Color += local shading term;
    if (surface is reflective)
      color += reflect Coefficient *
               IntersectColor(IntersectPoint, Reflect Ray);
    else if (surface is refractive)
      color += refract Coefficient *
               IntersectColor(IntersectPoint, Refract Ray);
  
    return color;
  }

Ray-object intersections

• Ray equation: ray is defined by its origin and a direction vector.

  $$\vec{r}(t) = \vec{o} + t\vec{d}, \quad 0 \leq t < \infty$$

• Intersection with sphere

  • Sphere

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

  • Solve for intersection:

    $$(\vec{o} + t\vec{d} - \vec{c})^2 - R^2 = 0$$

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

    where

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

• General implicit surfaces

  $$f(\vec{o}+t\vec{d}) = 0$$

  solve for real, positive roots of $t$.

• Intersection with triangle mesh

  • Why?

    • Rendering: visibility, shadows, lighting...

    • Geometry: inside / outside tests

  • How to compute?

    • Just intersect with each triangle? (inefficient)

    • Note: can have 0, 1 intersections (ignoring multiple intersections).

  • Triangle is in a plane:

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

    $$t = \frac{(\vec{p'} - \vec{o}) \cdot \vec{N}}{\vec{d} \cdot \vec{N}}$$

  • Then test if hit point is inside triangle.

• Intersection with planar polygon

  

• Moller-Trumbore algorithm

  $$\vec{o} + t\vec{d} = (1-b_1-b_2)\vec{P_0} + b_1\vec{P_1} + b_2\vec{P_2}$$

  Where:

  $$\vec{E_1} = \vec{P_1} - \vec{P_0}, \quad \vec{E_2} = \vec{P_2} - \vec{P_0}, \quad \vec{S} = \vec{o} - \vec{P_0}$$

  $$\vec{S_1} = \vec{d} \times \vec{E_2}, \quad \vec{S_2} = \vec{S} \times \vec{E_1}$$

  $$\begin{bmatrix} t \\ b_1 \\ b_2 \end{bmatrix} = \frac{1}{\vec{S_1} \cdot \vec{E_1}} \begin{bmatrix} \vec{S_2} \cdot \vec{E_2} \\ \vec{S_1} \cdot \vec{S} \\ \vec{S_2} \cdot \vec{d} \end{bmatrix}$$

  Recall: To determine if the intersection is inside the triangle, check if $(1-b_1-b_2)$, $b_1$, and $b_2$ are all within $[0, 1]$. These are barycentric coordinates.

Accelerating ray tracing

• Performance challenges:

  • Simple ray-scene intersection:

    • Exhaustively test ray-intersection with every triangle.
    • Find the closest hit (i.e., minimum $t$).

  • Problem:

    • Naive algorithm complexity: $\text{\#pixels} \times \text{\#triangles} \times (\text{\#bounces})$.
    • Very slow!

  • Generalization:

    • Use the term "objects" instead of "triangles" for flexibility (doesn’t necessarily mean entire objects).

AABB

• Bounding volumes

  • Quick way to avoid intersections: bound complex object with a simple volume.

  

• Axis-aligned bounding box (AABB)

  • Box is the intersection of 3 pairs of slabs.

  • AABB of a triangle

    

  • AABB of a group

    

  • AABB of a transform

    • Bounding box of transformed object is not the transformed bounding box.

• Intersection with AABB

  • 2D example; 3D is the same. Compute intersections with slabs and take intersection of $t_{min}/t_{max}$ intervals.

  

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

  • For each pair, calculate $t_{min}$ and $t_{max}$.

  • For the 3D box:

    $$t_{enter} = \max(t_{xmin}, t_{ymin}, t_{zmin})$$

    $$t_{exit} = \min(t_{xmax}, t_{ymax}, t_{zmax})$$

  • Ray and AABB intersects iff:

    $$t_{enter} < t_{exit} \quad \text{and} \quad t_{exit} \geq 0$$

• Why axis-aligned?

  

Grids

• Accelerate intersection test: uniform grids and spatial partitions.

• Uniform spatial partitions (grids)

  • Build

    

  • Intersection detection

    

  • How to determine the ray traversal order?

    

  • Grid resolution?

    • Too coarse: little speedup.

    • Too fine: too many cells to traverse.

    • In practice: $\#\text{cells} = C\times \#\text{objs}$, where $C\approx 27$ in 3D.

• Grids work well on large collections of objects that are distributed evenly in size and space. But fails on "Teapot in a stadium" scenes.

Spatial partitioning examples

• Oct-Tree

  

• BSP-Tree

  

• KD-Tree

  Binary tree that recursively partitions space with axis-aligned planes.

  

  • Internal nodes store:

    • Split axis: x-, y-, or z-axis.

    • Split position: coordinate of split plane along the axis.

    • Children: pointers to child nodes.

    • No objects are stored in internal nodes.

  • Leaf nodes store:

    • List of objects.

  • Traversing the KD-Tree

    

    

  • A smart way to traverse KD-Tree.

    • Get main bbox intersection from parent - $t_{start}$ and $t_{end}$.

    • $t$: intersect with splitting plane — easy because axis aligned.

    • Decide which child / both to traverse based on $t$, $t_{start}$, $t_{end}$.

    

  • Important details.

    • If there is an intersection in the first node, do not visit the second one. This allows ray casting to be reasonably independent of scene depth complexity.

    • For leaf nodes, do not report intersection if $t$ is not within $[t_{start}, t_{end}]$. This is crucial for primitives that overlap multiple nodes.

    • Handle degeneracies when the ray direction is parallel to one axis.

Object partitioning & BVH

• BVH: Bounding Volume Hierarchy

  

• Build a BVH

  • Find bounding box.

  • Recursively split the set of objects into two subsets.

  • Recompute the bounding box of two subsets.

  • Stop when necessary.

  • Store objects in leaf nodes.

• 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?

  • Heuristic: stop when node contains few elements (e.g. 5).

• Data structure of BVH.

  • Internal nodes store: Bounding box. Children: pointers to child nodes.

  • Leaf nodes store: Bounding box. List of objects.

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

• BVH traversal

  Intersect(Ray ray, BVH node) {
    // If the ray misses the bounding box, return no intersection
    if (!rayIntersectsAABB(ray, node.bbox)) return null;
  
    // If the node is a leaf, test intersection with all objects
    if (node.isLeaf()) {
      Intersection closestHit = null;
      for (Object obj : node.objects) {
        Intersection hit = rayIntersectsObject(ray, obj);
        if (hit != null && (closestHit == null || hit.t < closestHit.t)) {
          closestHit = hit;
        }
      }
      return closestHit;
    }
  
    // Otherwise, traverse child nodes
    Intersection hit1 = Intersect(ray, node.child1);
    Intersection hit2 = Intersect(ray, node.child2);
  
    // Return the closer intersection
    if (hit1 == null) return hit2;
    if (hit2 == null) return hit1;
    return (hit1.t < hit2.t) ? hit1 : hit2;
  }

• Discussion

  • Advantages: easy to connect / traverse, binary tree (simple structure).

  • Disadvantages: may be difficult to choose good split planes.

Basic radiometry

• Measurement system and units for illumination.

• Accurately measure the spatial properties of light.

• Perform lighting calculations in a physically correct manner.

Radiant energy and flux (power)

• Radiant energy: $Q$ (Joules, J)

• Radiant flux (power): $\Phi = \mathrm{d}Q/\mathrm{d}t$ (Watts, W = J/s)

  • # of photons flowing through a sensor in unit time.

Radiant intensity

• Power per unit solid angle:

  $$I(\omega) = \frac{\mathrm{d}\Phi}{\mathrm{d}\omega}$$

  where $\omega$ is the direction, $\mathrm{d}\omega$ is the differential solid angle (steradian, sr).

• Isotropic point light source:

  $$I(\omega) = \frac{\Phi}{4\pi}$$

Irradiance

• Power per unit area:

  $$E(\mathbf{x}) = \frac{\mathrm{d}\Phi(\mathbf{x})}{\mathrm{d}A}$$

• Lambert's cosine law:

  $$E = \frac{\Phi}{A} \cos \theta$$

  where $\theta$ is the angle between the light direction and the surface normal.

  

• Irradiance falloff with distance:

  $$E(r) = \frac{\Phi}{4\pi r^2}$$

Radiance

• The power emitted, reflected, transmitted, or received by a surface, per unit solid angle per unit projected area.

  $$L(p, \omega) = \frac{\mathrm{d}^2 \Phi(p, \omega)}{\mathrm{d}\omega \mathrm{d}A \cos \theta}$$

• Radiance is the quantity associated with a ray.

• Rendering is all about computing radiance.

• Incident radiance is the irradiance per unit solid angle arriving at the surface.

  $$L_i(p, \omega) = \frac{\mathrm{d}E(p, \omega)}{\mathrm{d}\omega \cos \theta}$$

• Exiting radiance is the intensity per unit projected area leaving the surface.

  $$L_o(p, \omega) = \frac{\mathrm{d}I(p, \omega)}{\mathrm{d}A \cos \theta}$$

• Integrate radiance over hemisphere to get irradiance:

  $$E(p) = \int_{H^2} L_i(p, \omega) \cos \theta \mathrm{d}\omega$$

  

Light transport

BRDF

• Bidirectional reflectance distribution function (BRDF)

  $$f_r(p, \omega_i \to \omega_o) = \frac{\mathrm{d}L_r(p, \omega_r)}{\mathrm{d}E(p, \omega_i)} = \frac{\mathrm{d}L_r(p, \omega_r)}{L_i(p, \omega_i) \cos \theta_i \mathrm{d}\omega_i}$$

  • Represents how much light is reflected into each outgoing direction $\omega_r$ from each incoming direction.

  • Describes surface reflectance properties (material).

• All reflected power per unit area, caused by incident power from direction $\omega_i$:

  $$\frac{\mathrm{d}E_r(p)}{\mathrm{d}E_i(p, \omega_i)} = \int_{H^2} f_r(p, \omega_i \to \omega_r) \cos \theta_r \mathrm{d}\omega_r \leq 1$$

  

• Accumulate incident light from all directions to get outgoing radiance in direction $\omega_r$:

  $$L_r(p, \omega_r) = \int_{H^2} f_r(p, \omega_i \to \omega_r) L_i(p, \omega_i) \cos \theta_i \mathrm{d}\omega_i$$

Rendering equation

• Add the emission term to make it general.

  $$L_o(p, \omega_o) = L_e(p, \omega_o) + \int_{\Omega^+} L_i(p, \omega_i) f_r(p, \omega_i \to \omega_o) (n\cdot\omega_i) \mathrm{d}\omega_i$$

• May replace $L_i$ with $L_r$ at other points to get recursive form.

  $$L_i(p, \omega_i) \to L_o(p', -\omega_i)$$