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 processing 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.
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's head, 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 kd-tree nodes can be expensive. One solution is to avoid building the entire structure as a preprocess, and instead 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 many computer science algorithms. The point of this assignment is to implement a lazy kd-tree to improve pbrt's performance when rendering complex scenes whose geometry extends well beyond the space traversed by the rays generated to render an image, such as in the examples above. Your implementation should be lazy in two key ways: (1) kd-tree nodes will be constructed dynamically as needed, and (2) Scene objects will be refined into their primitive components only when required.
Step 1: Understanding pbrt's kd-tree
It is critical that you first obtain a detailed understanding of the current kd-tree implementation in pbrt. Read Section 4.4 of the textbook and make sure you can follow the code in kd-tree.cpp, located in the accelerator directory of the code base. You should be able to answer the following questions about the current implementation (we do not expect you to hand in answers to these questions).
Describe the memory layout of the kd-tree representation. pbrt takes takes great care to minimize the sotrage required by a single kd-tree node. Since kd-trees may have millions of nodes, optimizing the memory footprint of a single node is important for both performance and memory utilization. In particular, notice how pbrt saves space by cleverly positioning child nodes in relation to parent nodes. This may need to change in your lazy implementation.
- Describe the heuristics of choosing the splitting plane and implementation of the cost function. You may choose to alter the cost function in this assignment.
What input data is required to build a new kd-tree node? Your implementation will need to be able to access this data dynamically as your lazy kd-tree is generated during the rendering process.
Understand the use of the "badrefines" variable in kdtree.cpp.
Understand how ray traversal through the kd-tree structure works (in the method KdTreeAccel::Intersect). Your lazy imeplementation will need to modify this algorithm to generate new kd-tree nodes while traversing.