Revision 2 as of 2007-04-12 02:36:54

    Assignment2

Assignment 2: Lazy K-D Tree

Due: Thursday April 26th, 11:59PM

topview mediumrange closeup

In this assignment, you will improve pbrt's implementation of the k-d tree accelerator. As described in Chapter 4 of the textbook, before rendering, pbrt constructs a k-d 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 k-d tree for a scene containing many geometric elements can be very costly. Depending on the camera's location and how objects in the scene occlude others from view, it is possible that many k-d tree nodes created in the initial build process may never be hit by any rays. In this case, both computation spent building these nodes and, more importantly, the memory used to store them is wasted. Your objective in this assignment is to modify pbrt's k-d tree accelerator to lazily build the acceleration structure as rays are shot through the scene.

In the images above the same scene rendered from three different camera positions. The scene contains 76 killeroos and each killeroo is a subdivision surface shape with a base mesh consisting of 8316 triangles. Six of these killeroos (the baby killeroos) undergo one level of subdivision, so the resulting meshes contain 33262 triangles. In total, the killeroos constitute 775,692 triangles.

Regardless of the camera position used, pbrt preprocesses the scene into a k-d tree containing 9.7 million nodes. pbrt's statistics for the scene are given below:

Geometry
    Total shapes created                                    781.9k
    Triangle Ray Intersections                              656.7k:4838.6k (13.57%)
    Triangles created                                       781.7k
Kd-Tree Accelerator
    Avg. number of primitives in leaf nodes                 12.148M:4.886M (2.49x)
    Interior kd-tree nodes made                             4.886M
    Leaf kd-tree nodes made                                 4.886M
    Maximum number of primitives in leaf node               395

This preprocess can expensive. On my laptop the k-d tree build takes about 30 seconds, while rendering the scene using the k-d tree requires approximately 25 seconds. Additionally, it consumes a large amount of memory. Even with pbrt's compact 8 byte representation of a tree node, the 9.7 million nodes consume 77MB of memory (plus an additional 48MB to store the references to primitives from tree leaf nodes). One solution is to build the tree on demand while tracing rays through the scene. 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 images at center and at right. Your implementation must 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.

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

Please add a link to your final writeup on Assignment2Submission.

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 k-d tree

It is critical that you first obtain a detailed understanding of the current k-d 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 k-d tree representation. pbrt takes takes great care to minimize the storage required by a single k-d tree node. Since k-d 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 k-d tree node? Your implementation will need to be able to access this data dynamically as your lazy k-d tree is generated during the rendering process.

  • Understand the use of the "badrefines" variable in kdtree.cpp.

  • Understand how ray traversal through the k-d tree structure works (in the method KdTreeAccel::Intersect). Your lazy imeplementation will need to modify this algorithm to generate new k-d tree nodes while traversing.

  • Notice that the current k-d tree implementation refines scene objects into their geometric primitives before building the complete k-d tree. What problems does this approach present for lazy evaluation? In particular, look at the implementation of Refine in the loop subdivision shape. What are the benefits of delaying the refine of such objects.

Step 2: Time pbrt's original k-d tree build

Use the ProgressReporter class to measure the amount of time it takes pbrt to create a k-d tree (see the CreateAccelerator function in kdtree.cpp. You'll need to wrap the creation of the KDtreeAccel like this:

  ProgressReporter progress(1, "Building KDTree");

  KdTreeAccel* accel = new KdTreeAccel(prims, isectCost, travCost,
                                       emptyBonus, maxPrims, maxDepth);

  progress.Update();
  progress.Done();

Step 3: Implement a Lazy kd-tree

Recent