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!

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.

killeroos-view1 killeroos-view2 killeroos-view3

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 a killeroo head which occludes large regions of the scene behind it.

For this scene, pbrt builds the kd-tree consisting of 273,100 tree nodes irrespective 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 is 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. 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 kdtree.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 storage required by a single kd-tree node. Since kd-trees may have millions of nodes, optimizing the memory footprint of nodes is important for both performance and memory utilization. In particular, notice how pbrt saves space by cleverly positioning child nodes in relation to a parent node. This scheme may need to change in your lazy implementation.
Describe the heuristics of choosing the splitting plane and the 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.
Notice that the current kd-tree implementation refines scene objects into their geometric primitives before building the complete kd-tree. What problems does this approach present for lazy evaluation?

Step 2: Implement a Lazy kd-tree

Given what you have learned from studying the existing pbrt kd-tree implementation, implement your own kd-tree acclerator that uses lazy evaluation to gain efficiency for complex scenes. Create the file pbrt/accelerator/lz-kdtree.cpp in your source tree, and implement your kd-tree in this file. You do not have to write everything from scratch (and we encourage you not to). Feel free to reuse any data structures and functions from kdtree.cpp. You should not need to change any other source files in pbrt. Download this zip file, which contains several scene files (You will need to obtain the models for plants-view1.pbrt and plants-view2.pbrt from the scenes directory on the PBRT CD). Test your implementation using these scenes and compare the results with pbrt's kd-tree implementation. Note that the rendering time recorded by pbrt does not include build time of the acceleration structure. Use ProgressReporter class to record the tree construction time. The evaluation of the quality of your implementation is an important part of this assignment. The number of tree nodes constructed, tree build time (upfront), total rendering time, and number of ray-triangle intersections are all important statistics that you can use to guide your implementation choices.

Suggestions

Here are some suggestions to get you started.

Think about how much of the tree you want to build during the initial build process. You may want to begin with a single node or build the tree out to an certain depth. Note that in the limit, the entire tree is constructed in the preprocess, and you have returned to pbrt's original kd-tree implementation.
You will need to have a mechanism to mark a node as a 'lazy' node, ie. a node that will need to be refined further when intersected by a ray. Lazy nodes will need a means to access all the data necessary to construct the remaining subtree.
It is likely that your implementation will need to manage a number of temporary data structures. The performance of your implementation will depend on our choices related to memory management.
Consider ways to be lazy about the refinement of objects into their geometric primitives. It may be much more efficient to build a tree of conglomerate objects rather than construct the tree for an enormous list of primitives. A kd-tree need not contain only primitives, it could contain a set of kd-trees as well.

Additional Optimizations

We want you to go to town on this assignment, and we will provide extra credit for clever optimizations beyond the lazy optimizations described above. Here are some ideas for further kd-tree optimizations:

Tune your kd-tree layout for optimal efficiency (minimize storage, improve layout for cache performance, etc).
Experiment with different heuristics for making node splitting decisions. The move to a lazily constructed kd-tree makes cost estimation more difficult.
The current cost function is independent of the camera configuration. As briefly discussed in class, compute a more accurate cost estimate, which takes into account the viewing constraints.

Submission

Detailed submission instructions will be posted shortly.

Create a wiki page named 'Assignment2' under your home directory that includes a description of your techniques and your final rendered images. In addition to rendering several views from the test scenes discussed above, you will also test the quality of your implementation on a much more complex outdoor scene. For both of these scenes, you will need to report the following rendering statistics for both your implementation and pbrt's default kd-tree: (1) construction time (2) total rendering time including any pre-build (construction time + rendering time) (3) number of created tree nodes (4) the number of ray-triangle intersections. Please provide the actual numbers, and well as the ratios between the two implementations. In your writeup, please follow the layout of the page template given [Assignment2Template]. Do not include your source file in the wiki page. Send an email to cs348b-spr0506-staff@lists.stanford.edu with title exactly as "cs348b HW2" and your lz-kdtree.cpp as an attachment.