Project 2 Help Notes

Outline

• Assignment overview
• Project 2 Requirements
• Acceleration Techniques (Overview)
• Major Acceleration Techniques
• Moderate Acceleration Techniques
• Minor Acceleration Techniques
• FAQ

Assignment overview

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

Project 2 Requirements

• 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₁ -> hit₂ -> hit₃ -> hit₄ -> hit₅ )
• cast shadow rays for hit₅, not reflection rays
• Stop only if K_s is 0
• 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²). For the final project, this can cost you a lot of time in the scene development / test cycle.
• README (see assignment for detailed instructions)

Acceleration Techniques (Overview)

• Faster intersections
• Faster ray-object intersections
• e.g. Object bounding volumes
• Fewer ray-object intersections
• e.g. Bounding volume hierarchies
• Space subdivision
• Directional Techniques
• Fewer rays (not allowed for project2... :-)
• Adaptive tree-depth control
• Statistical optimizations for anti-aliasing
• Generalized rays
• Beam tracing
• Cone tracing
• Pencil raytracing

Major Acceleration Techniques

• 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)
• Maximize profit
• 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.
• 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

Moderate Acceleration Techniques

• 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₀ be distance to our surface
• If you find another intersection with t less than t₀, then it's in shadow
• If the closest intersection is t₀, then the light hits our surface
• Be careful of intersecting objects, which don't have a single ordering
• 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.

Minor Acceleration Techniques

• 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".