Spring Quarter, 1998

Marc Levoy

Handout #22

- Assignment overview
- Project 2 Requirements
- Acceleration Techniques (Overview)
- Major Acceleration Techniques
- Moderate Acceleration Techniques
- Minor Acceleration Techniques
- Questions

- Why spend a whole project on optimization?
Test Polygons Unoptimized Octree Bounding Box test1

(Table & 2 chess pieces)6000 12 hours 50 seconds 21 seconds test2

(Barcelona Olympic Pavilion)5000 1.3 hours 70 seconds 155 seconds test3

(Mesh grid of dog's head)10,000 2.1 hours 41 seconds 88 seconds *Two good raytracers from 1996, rendering a 400x400 image, 5 levels deep, on a 250MHz firebird. These raytracers did no off-line precomputation, since it only took about 1 to 5 seconds.*

- Command-line interface
- Be able to run interactive or no-window mode
- Required: input file, output file, image size
- Suggested: be able to specify all slider / checkbox parameters
with arguments, too. e.g.:
- tree depth (5 for timing runs)
- min weight (0 for timing runs)
- image size (400 for timing runs)
- brightness scaling (or whatever other parameters your raytracer uses)
- print usage (e.g. "raytrace -h")
- ...

- Trace 5 levels ( eye -> hit
_{1}-> hit_{2}-> hit_{3}-> hit_{4}-> hit_{5})- cast shadow rays for hit
_{5}, not reflection rays - Stop only if K
_{s}is 0

- cast shadow rays for hit
- Per-Vertex normals
- Use geometric normal for all intersection tests
- Use interpolated normal for shading, reflection, refraction
- Barycentric coordinates give interpolation

- Per-Vertex materials
- Interpolate every field that changes (diffuse, ambient, specular, shininess, or ktran)
- Barycentric coordinates give interpolation

- No Transparency in test cases
- Your intersect routine will probably return only the closest intersection, not every intersection
- However, you probably will want to keep the refraction code, for project3.
- For shadow rays through transparent surfaces, you can call Intersect multiple times, starting at the new surface.

- Submission
- Measure elapsed time: "time myraytracer args..."
- Measure memory use: "top"
- Measure precomputation time
- This time doesn't count towards project2 grade
- However, be careful of algorithms worse than
O(n
^{2}). For the final project, this can cost you a lot of time in the scene development / test cycle.

- README (see assignment for detailed instructions)

- Faster intersections
- Faster ray-object intersections
- e.g. Object bounding volumes

- Fewer ray-object intersections
- e.g. Bounding volume hierarchies
- Space subdivision
- Directional Techniques

- Faster ray-object intersections
- Fewer rays (not allowed for project2... :-)
- Adaptive tree-depth control
- Statistical optimizations for anti-aliasing

- Generalized rays
- Beam tracing
- Cone tracing
- Pencil raytracing

- Hierarchical Bounding Volumes
- Bottom-Up
- Use scene's native hierarchy
- Easiest to implement
- Can give horrible performance

- Top-Down
- Pool all polygons together, start clustering them
- Critical issue: How (and when) to divide?
- Let: t
_{bound}be the time to test intersection with the bound - Let: t
_{children}be the time to test intersection with the children - Cost: t
_{bound}* (all rays tested against bound) - Benefit: t
_{children}* (number of rays that missed the bound) - Profit = Benefit - Cost

(t_{children}- t_{bound}) * (number of rays that missed the bound) -

t_{bound}* (number of rays that hit bound) - Think Ferengi: Want to maximize profit

- Let: t

- Bottom-Up
- Spatial Subdivision
- Octrees
- Uniform vs. Nonuniform
- Uniform easier to traverse
- Non-uniform can be far faster
- Non-uniform can be more memory efficient

- Generation: Subdivide each voxel into 8 subvoxels
- Top-down
- Each voxel lists objects that are partially or fully within the voxel
- Stop subdividing when few (or no) primitives, or when voxel gets too small

- Traversal: Walk through voxels
- Want to avoid testing objects multiple times (see "mailboxes", Glassner, p.225)
- If voxel points to an object, and ray intersects that object, but the intersection is not in the current voxel, you must keep traversing voxels until you get to the voxel which contains that intersection.

- Uniform vs. Nonuniform
- BSP trees
- Recursively cut the world in half with planes
- When raytracing, break ray into two intervals
- Do "close" interval first
- Don't need to test anything in far half if an intersection is found in the close half
- Often, the interval in one half is empty

- Octrees

- Directional Techniques
- The Direction Cube (Glassner pp. 228-231)
- Given a point in space, surround it with a cube
- Squares on cube face form "windows" through which only some objects are visible
- Given any ray from (to) that point, you can compute which window that ray passes through

- The Light Buffer (Glassner, pp. 231-234)
- Form a direction cube around a pointlight
- For each window, form list of objects
- Sort them from closest to farthest
- Cull backfacing, stop if completely opaque
- When checking ray to the light, go through the list
- Let t
_{0}be distance to our surface - If you find another intersection with t less
than t
_{0}, then it's in shadow - If the closest intersection is t
_{0}, then the light hits our surface - Be careful of intersecting objects, which don't have a single ordering

- Let t

- The Direction Cube (Glassner pp. 228-231)
- Generalized Rays
- Cones (Glassner pp. 242-243)
- Calculate how much of cone blocked by each object
- Secondary rays: surface curvature affects spread of the cone
- Cone enables penumbra, dull reflections
- Intersection tricky, limited to polygons and spheres

- Beams (Glassner pp. 243-246)
- Like cones, but with polygonal cross-section
- For reflection, compute "virtual eyepoint" of new beam
- Partial occlusion -> clip polygon of beam
- Problems: Non-convex, fragmented beam polygons

- Pencils (Glassner p.246)
- Set of beams with some given deviation, assumed close enough together that interaction with each surface is linear
- Edges, discontinuities mean you must trace individual rays.

- Cones (Glassner pp. 242-243)

- Turn compiler optimization flags on, such as -O3.
*(after you've finished debugging! :-)* - Tune the code inside the inner loop of bottlenecks
(such as intersection)
- Whitted: generally over 95% of time spent doing intersection
- Avoid unnecessary expensive operations, such as malloc, inside your inner loop
- Use temporary variables to avoid repeating code (such as taking the square root of something twice in the same function)
- Replace simple functions with macros
- This allows the compiler to optimize the code better
- Be careful about parentheses!!!

- Don't waste time tuning code that isn't a bottleneck.
- If you don't know your bottlecks, try profiling your program. See "man prof".

Text by Lucas Periera

Minor modifications by Tamara Munzner

Friday, 01-May-1998 01:30:57 PDT