Lab 2

Accelerating Data Structures and Space Partition Techniques

Due: Thu, November 16, 2017 at 23:55

Start Early!!!

This lab was modeled after the exercise 4.1 and 4.2 of the pbrt book.
Individual Effort:
No team participation is really encouraged in the case of the homework or the labs.
Academic Misconduct
Late Submission Policy

Objectives

The goal of this assignment is two-fold. At first, you are to reason about the pros and cons of the ray-tracing acceleration structures that pbrt has implemented. In that part of the lab, you will get to know the scene description files of pbrt and do not have much code modification to do. In the second part, however, you are to improve the provided grid acceleration structure and evaluate how much performance improvements you get.

Step 1: Adding Grid Accelerator to pbrt-v3

Please read section 4.2 of the pbrt book before starting this section. Download gridaccel.h and gridaccel.cpp and copy them to the pbrt-v3/src/accelerators folder. The code provides a grid-based acceleration data structure. To add the new files to the Makefiles and project files, you need to run CMake again.

To be able to use the new grid accelerator in rendering the scene file, you need to call CreateGridAccelerator function in core/api.cpp. To do so, first include the gridaccel.h header file at the top, as: 

#include "accelerators/gridaccel.h"
Then add the grid accelerator in the MakeAccelerator function, by adding an extra if statement: 
if (name == "bvh")
    accel = CreateBVHAccelerator(prims, paramSet);
else if (name == "kdtree")
    accel = CreateKdTreeAccelerator(prims, paramSet);
else if (name == "grid")
    accel = CreateGridAccelerator(prims, paramSet);
else
    Warning("Accelerator \"%s\" unknown.", name.c_str());
Now it is time to test the new accelerator in action. Download the cornell-box or coffee-maker scenes from Benedikt Bitterli's page. Open the scene.pbrt file and add the following line at the top of the file to override the default bvh accelerator: 
Accelerator "grid"
Render the scene with the new accelerator. Read the code and try to understand its behavior. Include the answer to the following questions about the grid accelerator in your writeup:

Step 2: Understand pbrt's implementations of the BVH accelerator

It is critical that you first obtain a detailed understanding of pbrt's BVH accelerator. Read Section 4.3 of the textbook and make sure you can follow the code in bvh.cpp, located in the accelerators directory of the code base. Include the answers to the following questions about the current implementation in your writeup. It is highly recommended that you also read section 4.4 of the textbook about the kd-tree accelerator to have a deeper understanding of the topic before submitting your report.

Step 3: Background reading

Read the paper "Grid Creation Strategies for Efficient Ray Tracing" by Thiago Ize, Peter Shirley, and Steven Parker. Include the answers to the following questions in your writeup.

Step 4: Implement a two-level grid accelerator

Modify gridaccel.cpp so that the grid accelerator uses a two-level grid using the heuristics as explained in the paper by Ize et al. Be sure to keep a copy of the original grid accelerator implementation around for use in later assignments and for debugging and test in this assignment. (Alternatively, you may want to implement your two-level grid accelerator as a new class in pbrt. This will require running CMake again to add the new files to the Makefiles and project files, but would allow you to select between your and the original grid implementation by only changing the scene file, not recompiling the grid accelerator module. The procedure is similar to what you did in Step 1.).

Debugging suggestions

Step 5: Evaluation

Understand the performance gains of your implementation.

building time

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 grid (see the CreateGridAccelerator function in gridaccel.cpp. Modify the code to time the creation of the GridAccel like this: 

std::shared_ptr CreateGridAccelerator(const std::vector > &prims,
        const ParamSet &ps) {
    ProgressReporter progress(1, "Building twoLevelGrid");
    std::shared_ptr accel = std::make_shared(prims);

    progress.Update();
    progress.Done();
    return accel;
}

Step 6: Submission

Be sure to double check your final submission by unzipping it in another directory on a computer in the PC LAB and testing it. (Especially for last minute submissions.) A project that doesn't run will lose more points than one that is one day late. Be sure to submit any comments or remarks in a 'readme.txt' file. Submit your files at Moodle here. Your submission should contain:

We expect a good student to have to work approximately 15 hours on this assignment.

Grading

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.

This assignment will be graded based on the following criteria:

Academic Honesty