Project Proposal:
CPU-Based Parallel Ray Tracer
Abhishek Chugh, Chenxi Liu

Project Main Page

Checkpoint Report

Final Report

Summary
We will implement a ray tracer with a bounding volume hierarchy (BVH) and packet tracing. The construction of BVH will be parallelized.
Background
Ray tracing is a technique for rendering 3D scene onto the screen using ray casting and physics law. A ray tracer simulates a real-world camera in a backward way. Instead of accumulating lights from light sources, a ray tracer shoots rays to every pixel on the screen and checks whether the rays eventually return to light sources. When tracking a ray, the ray tracer compute the color of corresponding pixel based on objects encountered along the path.

A main task involved in ray tracing is visibility test, that is, checking if the ray hits an object first. The visibility test is increasingly costly when the number of objects grows. To avoid expensive test on each step, data structures for objects are often introduced to reduce computations. Several examples are BVH, kd-tree, and octree.

A ray tracer with the spatial data structure has two working phases. Phase one is maintaining the data structure, which may require to build a whole data structure from scratch or adjust the structure for changed scene or view point. Phase two is doing the regular ray tracing with the data structure. This phase could be further broken into smaller steps, such as ray casting and color computing.
Challenge
By adding spatial data structure, the cost of visibility test is saved. However, maintaining a fancy data structure, like BVH we chose in this project, could become a new bottleneck. Parallelization could again be a solution. But unlike the regular ray tracing, the construction of spatial data structure could not be intuitively parallelized because of data dependence. Although there are a plenty of research papers with topics related to parallel construction of BVHs, the actual implementation could also be nontrivial.

Another issue rises from CPU. Compared to GPU, the core number of CPU is remarkably limited. This shortage would cause serialization, which is simply because there are not enough cores to run more parallel tasks in parallel. One solution is to use packetized rays as the unit of intersection check. When traversing the data structure, a group of rays are tested against the current element and the traversal would not end until the intersections for all the rays are found. This approach is usually mapped to SIMD implementation. Notice that how to select rays as a group is challenging, since naive selection may cause a traversal of the whole data structure.
Resources
We use the code from "Project 3" of Computer Graphics course as out starting code base. It contains a basic framework for raytracing scenes. We would be running these on our the Gates 3000 machines. If the SSE support on these machines turns out to be insufficient for our needs, we may switch to some other (personal) machines for AVX support.
Goals/Deliverables
Our project can be divided into three broad optimisations. The first of these two we plan to achieve, the others we hope to achieve if the project goes very well.
  1. Creating a Bounding Volume Hierarchy using the surface area heuristic that could be built in parallel.
  2. "Packet Tracing" - Speeding up raytracing by using SIMD instructions.
  3. "On-Demand Tessalation" - Efficiently tessellate surfaces to render scenes that, if fully tessellated, would not fit in the memory.
  4. Optimise BVH construction for animated scenes.
Platform
We have the starter code written in C++. This makes sense too because being a middle level language, C++ allows you highly optimized code in order to get the best performance from the platform. Writing the code in C++ also gives us the flexibility to run this code on multiple platforms. We plan to use OpenMP for creating BVH in parallel and ISPC for packet tracing.
Proposed Schedule

Week What We Plan To Do
4-10, AprilCleaning up the code base; survey of literature.
11-17, AprilAchieve a sequential implementation of BVH with SAH.
18-24, AprilParallelize BVH construction, start packetisation.
25-31, MayFine tune packetisation and Optimize BVH construction for animated scenes.
1-9, MayFixing bugs, collecting data and writing Final Report.