= Assignment 2: Lazy KD Tree =

== Due: Tuesday April 25th, 11:59PM ==

Questions? Need help? Post them on the Assignment2Discussion page so everyone else can see!

Please link to your final Assignment 2 writeup wiki page from Assignment2Writeups.

=== Description ===

In this assignment, you will improve pbrt's implementation of the kd-tree accelerator.  As described in Chapter 4 of the textbook, before rendering, pbrt constructs a kd-tree containing all geometric primitives in the scene.  This approach can be inefficient for several reasons.  First, as you will observe in this assignment, building a complete kd-tree for a scene containing many geometric elements can be very costly.  Depending on the camera's location, or on how large objects in the scene hide others from view, it is possible that many kd-tree nodes created in the initial build process may never be hit by any rays.  In this case, both the time spent building these nodes and the memory used to store them is wasted.
As an example, the following images show the same scene from three different camera positions.

http://graphics.stanford.edu/courses/cs348b-06/Homework2/images/killeroos-view1.jpg http://graphics.stanford.edu/courses/cs348b-06/Homework2/images/killeroos-view2.jpg
http://graphics.stanford.edu/courses/cs348b-06/Homework2/images/killeroos-view3.jpg

In all images, the rendered scene contains 4 killeroos, a ground plane, and two walls.  In the left image, the camera faces the killeroos and all the objects in the scene are visible. In the center image, the camera is placed such that the killeroos are hidden behind the walls.  In the image at right, the camera is zoomed in on one of the killeroo heads, occluding large regions of the scene.

For this scene, pbrt builds the kd-tree consisting of 273.1k tree nodes irregardless of camera position.  However, it is clear there is no need to create nodes in the space surrounding the killeroos in the second image, since they are occluded from view and no rays will traverse through that part of the scene.  The following segment shows statistics from rendering the left and center scenes in pbrt.

{{{
Geometry
    Total shapes created                                    133.1k
    Triangle Ray Intersections                              1.475M:9.220M (16.00%)
    Triangles created                                       133.1k
Kd-Tree Accelerator
    Avg. number of primitives in leaf nodes                 865.8k:273.1k (3.17x)
    Interior kd-tree nodes made                             273.1k
    Leaf kd-tree nodes made                                 273.1k
    Maximum number of primitives in leaf node               155
}}}

Constructing these extra tree nodes can be expensive.  One solution is to skip building the entire tree as a preprocess, and dynamically build the necessary parts of the kd-tree while tracing rays.  This attempt of delayed computation or ''lazy evaluation'' is a common technique used in computer science.