Lec 7. Ray Tracing 1
约 1654 字大约 6 分钟
2025-11-05
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.
r(t)=o+td,0≤t<∞
Intersection with sphere
Sphere
p:(p−c)2−R2=0
Solve for intersection:
(o+td−c)2−R2=0
t=2a−b±b2−4ac
where
a=d⋅d,b=2d⋅(o−c),c=(o−c)⋅(o−c)−R2
General implicit surfaces
f(o+td)=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:
(o+td−p′)⋅N=0
t=d⋅N(p′−o)⋅N
Then test if hit point is inside triangle.
Intersection with planar polygon

Moller-Trumbore algorithm
o+td=(1−b1−b2)P0+b1P1+b2P2
Where:
E1=P1−P0,E2=P2−P0,S=o−P0
S1=d×E2,S2=S×E1
tb1b2=S1⋅E11S2⋅E2S1⋅SS2⋅d
Recall: To determine if the intersection is inside the triangle, check if (1−b1−b2), b1, and b2 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: #pixels×#triangles×(#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 tmin/tmax intervals.

The ray enters the box only when it enters all pairs of slabs.
For each pair, calculate tmin and tmax.
For the 3D box:
tenter=max(txmin,tymin,tzmin)
texit=min(txmax,tymax,tzmax)
Ray and AABB intersects iff:
tenter<texitandtexit≥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: #cells=C×#objs, where C≈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 - tstart and tend.
t: intersect with splitting plane — easy because axis aligned.
Decide which child / both to traverse based on t, tstart, tend.

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 [tstart,tend]. 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): Φ=dQ/dt (Watts, W = J/s)
- # of photons flowing through a sensor in unit time.
Radiant intensity
Power per unit solid angle:
I(ω)=dωdΦ
where ω is the direction, dω is the differential solid angle (steradian, sr).
Isotropic point light source:
I(ω)=4πΦ
Irradiance
Power per unit area:
E(x)=dAdΦ(x)
Lambert's cosine law:
E=AΦcosθ
where θ is the angle between the light direction and the surface normal.

Irradiance falloff with distance:
E(r)=4πr2Φ
Radiance
The power emitted, reflected, transmitted, or received by a surface, per unit solid angle per unit projected area.
L(p,ω)=dωdAcosθd2Φ(p,ω)
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.
Li(p,ω)=dωcosθdE(p,ω)
Exiting radiance is the intensity per unit projected area leaving the surface.
Lo(p,ω)=dAcosθdI(p,ω)
Integrate radiance over hemisphere to get irradiance:
E(p)=∫H2Li(p,ω)cosθdω

Light transport
BRDF
Bidirectional reflectance distribution function (BRDF)
fr(p,ωi→ωo)=dE(p,ωi)dLr(p,ωr)=Li(p,ωi)cosθidωidLr(p,ωr)
Represents how much light is reflected into each outgoing direction ωr from each incoming direction.
Describes surface reflectance properties (material).
All reflected power per unit area, caused by incident power from direction ωi:
dEi(p,ωi)dEr(p)=∫H2fr(p,ωi→ωr)cosθrdωr≤1

Accumulate incident light from all directions to get outgoing radiance in direction ωr:
Lr(p,ωr)=∫H2fr(p,ωi→ωr)Li(p,ωi)cosθidωi
Rendering equation
Add the emission term to make it general.
Lo(p,ωo)=Le(p,ωo)+∫Ω+Li(p,ωi)fr(p,ωi→ωo)(n⋅ωi)dωi
May replace Li with Lr at other points to get recursive form.
Li(p,ωi)→Lo(p′,−ωi)