Assignment 2: Lazy K-D Tree

Due: Thursday April 26th, 11:59PM

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

Answers to common questions are posted on Assignment2Discussion.


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.

topview mediumrange closeup

The images above show 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:

    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). Imagine the amount of memory required if we were rendering a battle scene from Lord of the Rings!

One solution to this problem is to build the tree only when needed. In the case of ray tracing, we only build a tree if a ray enters the region of space occupied by the model, this case one of the killaroos. 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.

Step 1: Understanding pbrt's k-d tree

It is critical that you first obtain a detailed understanding of pbrt's current k-d tree implementation. 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).

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

The rendering time reported by pbrt does not include the time spent building the acceleration structure. 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. Modify the code to time the creation of the KDtreeAccel like this:

  ProgressReporter progress(1, "Building KDTree");

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


Step 3: Implement a Lazy K-D Tree

Begin by downloading the Assignment 2 pbrt scene files located at http://graphics.stanford.edu/courses/cs348b-07/assignment2/assignment2.zip.

manykilleroos.pbrt is the scene you will render in this assignment. This main scene file includes the files killeroo_subdiv0.pbrt, killeroo_subdiv1.pbrt, and killeroo_row.pbrt. At the top of manykilleroos.pbrt you will notice 3 different camera positions specified by different LookAt transforms which correspond to the 3 camera position in the images shown above.

Modify kdtree.cpp so that the k-d tree accelerator uses lazy evaluation to gain efficiency for complex scenes. Be sure to keep a copy of the original k-d tree accelerator implementation around for use in later assignments and for debugging and test in this assignment. (Alternatively, you may want to implement your lazy k-d tree accelerator as a new class in pbrt. This is more work, as it requires modification of the pbrt project/Makefiles, and some of the surrounding pbrt code, but would allow you to select between your and the original k-d tree implementation by only changing the scene file, not recompiling the k-d tree accelerator module. Ask for help if you wish to do this, and cannot figure out how to do so on your own).

This assignment is extremely open ended, and there are many ways to correctly implement the assignment. In addition to the correctness of your code, your grade will depend largely on your ability to describe the strategies you tried and your evaluation of them on the test scene. Here are some suggestions to get you started:

Advanced Suggestions

Debugging suggestions

Step 4: Evaluation Part 1

The evaluation of the quality of your implementation is an important part of this assignment. Test your lazy k-d tree implementation by rendering all 3 views of the killeroo scene and compare your results with the regular pbrt k-d tree implementation. Write up a report that addresses the following:

pbrt K-D Tree

my Lazy K-D Tree

Ratio (lazy/non-lazy reference)

build time (secs)




total time (secs)




nodes made




Triangle ray intersections




Step: 5 Render on a BIG scene

Lastly, we'd like you increase subdivision on all 76 killeroos in the scene to be at least level 1 (the 6 baby killeroos are already subdivided to this level). To do this, modify killeroo_row.pbrt so that the file includes copies of killeroo_subdiv1.pbrt instead of killeroo_subdiv0.pbrt. Now the scene, fully refined, contains 2.5 million triangles. Render the scene from the close up viewpoint using your lazy k-d tree implementation, and compare statistics with the original pbrt implementation if possible. Note that on systems with only a gig of RAM, using the original non-lazy k-d tree implementation many cause pbrt to swap. We hope your system can complete a rendering using pbrt's original k-d tree implementation. Note that if you lazily built a tree, but did not implement lazy refinement, your memory footprint may still be very large (why is this the case?). This test highlights the importance of lazy refinement and building. It makes rendering very large scenes possible when the entire scene is not in view. Include the results of this test in your writeup.

Step 6: Submission


This assignment (as well as all future assignments in the class) will be graded on a 4 point scale:

Extra credit will be given for exceptional experimentation with heuristics or techniques to improve the performance or quality (for example: the number of nodes created) of your lazy k-d tree implementation.

last edited 2007-05-06 23:02:39 by KayvonFatahalian