Assignment 2: Memory-Efficient Bounding Volume Hierarchies
By mmp and zdevito

Memory-Efficient Bounding Volume Hierarchies

Due Date: Tuesday, May 7, 11:59 PM

Description

In this assignment, you'll modify PBRT's bounding volume hierarchy implementation to be more memory efficient by reducing the storage requirements for the of bounding boxes stored at each node in the BVH. You will measure the performance impact of this change and prepare a writeup that discusses your observations.

Step 1: Review the relevant reading

To prepare for this assignment, first review Chapter 4 of Physically Based Rendering (especially Section 4.4 on the implementation of bounding volume hierarchies in PBRT.)

Next, read the paper Memory Efficient Ray Tracing with Hierarchical Mesh Quantization, by Segovia and Ernst. For this assignment you'll only be implementing a basic quantized BVH, but there are many interesting ideas about memory-efficient ray tracing in this paper.

Step 2: Download and build pbrt

For instructions on how to build pbrt, see our installation guide. Make sure that PBRT builds and can render a simple image before moving on.

Step 3: Build and run the project code

Download the skeleton code for this assignment. We need to add a new accelerator ebvh (our "Efficient" BVH) to pbrt. To do this, first copy the provided ebvh.h and ebvh.cpp files to pbrt's src/accelerators directory. Next, modify src/core/api.cpp with these changes:

diff --git a/src/core/api.cpp b/src/core/api.cpp
index 957290a..2598c85 100644
--- a/src/core/api.cpp
+++ b/src/core/api.cpp
@@ -44,6 +44,7 @@

 // API Additional Headers
 #include "accelerators/bvh.h"
+#include "accelerators/ebvh.h"
 #include "accelerators/grid.h"
 #include "accelerators/kdtreeaccel.h"
 #include "cameras/environment.h"
@@ -583,6 +584,8 @@ Primitive *MakeAccelerator(const string &name;,
     Primitive *accel = NULL;
     if (name == "bvh")
         accel = CreateBVHAccelerator(prims, paramSet);
+    else if(name == "ebvh")
+        accel = CreateEBVHAccelerator(prims, paramSet);
     else if (name == "grid")
         accel = CreateGridAccelerator(prims, paramSet);
     else if (name == "kdtree")

Re-build PBRT. If you want to use the ebvh accelerator on other scenes, you need to add the following line the top of the *.pbrt file for the scene.

Accelerator "ebvh"

Otherwise, the scene will use the normal bvh accelerator. When configured to use your ebvh accelerator, you should see a line like the following that indicates that the ebvh accelerator is being used:

EBVH created with 138883 nodes for 69454 primitives at 32 bytes/node (4.24 MB)

Step 4: Scene-Bounds-Relative Quantized Bounding Boxes

You should make the following changes to the file accelerators/ebvh.cpp; leave accelerators/bvh.cpp unchanged so that you can do performance experiments comparing to the original implementation.

In the PBRT BVH code, first a regular pointer-based BVH is built using splits based on the surface area heuristic. This BVH is then converted into a more memory-efficient representation in the flattenEBVHTree() method. Currently, the LinearEBVHNode structures that flattenEBVHTree() initializes are 32 bytes big; 24 of these bytes are due to the BBox bounds member, which stores 6 32-bit float values for the two opposite corners of the box.

In your code, modify the LinearEBVHNode structure definition to use a quantized representation of the bounding box, replacing the bounds member variable with six 10-bit unsigned integer member variables, thus reducing the total size of LinearEBVHNode to 16 bytes. For example, you might do something like:

struct LinearBVHNode {
   unsigned int bounds_x0:10;
   unsigned int bounds_y0:10;
   unsigned int bounds_z0:10;
   unsigned int bounds_x1:10;
   unsigned int bounds_y1:10;
   unsigned int bounds_z1:10;

   // remainder of LinearBVHNode members...
};

The :10 after the field name is a bitfield. It specifies that the field should only occupy 10 bits in the structure.

Originally, the BBox object encoded the bounding box as absolute coordinates in world space. For the compressed representation, you should encode each node's bounding box relative to the overall bounding box of all of the primitives in the BVH in equal steps over its range. For instance, if bounds_x0 were 0 then it specifies the minimum x of overall bounding box. If bounds_x0 were $2^{10}-1$ then it specifies the maximum x of the overall bounding box. The overall scene bounding box can be found in the bounds member of the EBVHBuildNode at the root of the tree after initial BVH construction. (You'll want to save a copy of this bounding box in the EBVHAccel class so that it's available later.)

Make sure that you round down when quantizing the lower extent of the bounds and round up when quantizing the upper extent, so that your quantized bounding boxes are never smaller than the original ones.

Next, modify the Intersect() and IntersectP() methods to convert these quantized bounding boxes back to regular Bounds structure instances before computing ray-bounds intersection tests.

Step 5: Evaluation

Downloads the test scenes and untar the files. Ensure that your implementation computes correct images by rendering the bunny.pbrt and tt.pbrt scenes. First render the scene as provided and save a copy of the image that is written to the files bunny.exr and tt.exr, respectively. Then, change the line:

Accelerator "bvh"

to

Accelerator "ebvh"

to select your BVH implementation. Use the exrdiff program from the pbrt distribution to compare the two images for each of the two renderings. (It's ok if your images have a very small number of differences as long as those differences are not noticeable when compared visually.)

Once you're generating correct images, measure the running time of your implementation and the running time of the original implementation. You may want to do a number of runs to make sure the timings you're seeing are consistent.

Prepare a writeup that reports the performance you're seeing and discusses reasons that your implementation may be faster than the original as well as reasons that your implementation may be slower.

Step 6: Parent-Relative Quantization

You can reduce the error introduced by quantization by quantizing bounding boxes in child nodes relative to the bounding boxes of their parent node, rather than the bounding box of the entire scene. Modify your implementation to quantize bounding boxes in this manner; note that you should quantize relative to the quantized bounding box of the parent node, rather than its original bounding box (as the quantized bounding box is the only one that will be available during BVH traversal and ray intersection calculations.)

Note that you will need to modify the Intersect() and IntersectP() method to track the parent node of each child node on the todo stack as well as the nodes themselves.

Step 7: Evaluation

Measure the performance of parent-relative quantization and compare it to both the original BVH an the initial implementation of quantized bounding boxes for each of the two test scenes.

Submission

To submit your work, create a .zip or .tar.gz file that contains:

  • Your ebvh.cpp file and any other files you modified.
  • Your writeup and evaluation as described above.
  • A description of the extra-credit you attempted, if any.

Use the assignment submission page to upload and submit your work (choose Assignment 2). You can submit multiple times if you wish to make changes after your initial submission. A record of the submission including the date submitted and an md5 checksum of your bundle will appear on the submission page when it is successful.

Tips

When you're debugging your implementation, you may want to leave the original BBox bounds member variable in the LinearEBVHNode (and keep on initializing it in flattenBVHTree()!). Then, you can test your quantized bounding boxes by making sure that any time the original float-based BBox returned true from a ray/bounds intersection test, your quantized bounding box does as well.

Grading

In addition to the correctness of your code, your grade will depend largely on your ability to describe the performance you observed and reasonably hypothesize about why it is what it is. This assignment will be graded on a 3 point scale:

  • 0 points: code doesn't compile or crashes when run
  • 1 point: code compiles but creates incorrect output or creates correct output with no reduction in memory use
  • 2 points: code compiles and creates correct output, but with minimal writup
  • 3 points: code compiles and creates correct output, with clear writup and analysis of the results observed.

Extra Credit

For one point of extra credit, you may implement more aggressive compression schemes (for example, the Segovia and Ernst paper describes a hybrid approach that uses less aggressive compression for bounding boxes at higher levels of the tree but a very aggressive approach for bounding boxes lower in the tree.) If you implement such a scheme, you should include a writeup analyzing its memory use and performance compared to the baseline approach in this assignment.