Rendering Project 1: Accelerator

[Part 1: Geometric Ray-Sphere Intersection]  [Part 2: Accelerator]  [Downloads]  [References]

Part 1: Geometric Ray-Sphere Intersection


The implementation is straightfoward and can be done by simply follow the process taught in class[3]. However, I spent a lot of time dealing with the NaN problem due to the normalization of ray direction vector.


My geometric implementation performs slightly better than the original one. The result images of the two method looks nearly identical, but with only a few pixels have different colors. I think it is due to some inevitable error during the computaion and thus can be ignored.

Part 2: Accelerator

My first attempt is to implement the octree algorithm. But later I found that the octree-R can perform much better than the octree and differ with the octree only in spliting the child voxels, which sounds appealing. Therefore I decided to implement both of the algorithms and compare their performance against each other and the kd-tree. The codes are modified from the kd-tree's, but differs in the tree construction and ray intersection checking.

Tree construction

I refer to [1] and [2] for the tree construction, and I mainly follow the algorithm describe in these papers. But the problem lies in the termination condition of the tree construction recursion: The procedure describe in [1] and [2] state that the construction ends when the number of primitives is less than maxiNumberPrims. However, the spliting plane cannot always cut on the bounding plane of each plane, which can be achieved in kd-tree's implementation.

Therefore, I have come up with an approach to deal with the problem. I count the primitives that will be counted only once by all the 8 children. In addition, I will check if the total number of primitives counted in each child, which may share the same primitive with other children, are two times larger than the true number of primitives in this node. If the answer is yes and the number of primitives counted once is less than a number(I choose 6 in my implementation), than make it a leaf node instead of spliting it into 8 children.

Ray intersection

For both octree and octree-R, the two functions, Intersect() and IntersectP(), are the same.

The idea is similar to the kd-tree's. The difference is that an internal node has only two children in kd-tree, while a octree/octree-R internal node has 8 children. For each internal node, I first check the intersection of the ray and each of its 8 children. After finding all children that will intersect with the ray, I sort them according to the t's of the intersection. Finally, push them into the todo stack in the reverse order.

To calculate the intersection, we have to check the 3 axis for tNear and tFar for each of the 8 children, which result total of 48 computations for a node. But we can observe that every node has to check the 6 bounding plane and 3 spliting plane for intersection, so I precalculate those 9 intersection t's, and use a look-up table for each children to get the right tNear and tFar. This method thus reduce the computation from 48 to 9.


Both of my implementations perform worse than the kd-tree algorithm. The speed ratio of kd-tree and octree ranges from 1.17 to 7.12, and for the kd-tree and octree-R the speed ratio ranges from 1.06 to 3.41. The octree and the octree-R performs better in buddha.pbrt and plants-directsun.pbrt, from which they get speed ratio close to 1. In general, the octree-R algorithm performs better, but it costs more construction time than the octree.

I think that the reason why the octree and octree-R are slower than the kd-tree is because a primitive is much more likely to be included in different leaf nodes in the octree and the octree-R than the kd-tree, which will costs more time to in both construction and intersection.

The result image of my octree and octree-R has some differences between the kd-tree's. My results seems to have a slightly better image! But the speed performances are bad :(

Kd-tree   Octree/Octree-R, better shadows?


Part 1

To switch between the original implementation and the geometric one, you have to change the #define's: "#define ALGEBRAIC_SOL" and "#define GEOMETRIC_SOL". Note that only one of them can be defined.

Source code: sphere.cpp (Put it into $PBRT_ROOT/shapes)

Part 2

Source code: octree.cpp, octreer.cpp (Put them into $PBRT_ROOT/accelerators)

Execution Time

Compiled and run on NTUCSIE workstation(linux9)


  1. A. Glassner, Space Subdivision for Fast Ray Tracing, IEEE CG&A 1984.
  2. K.-Y. Whang et. al., Octree-R: An Adaptive Octree for Efficient Ray Tracing, IEEE TVCG 1995
  3. Course slides(Shapes, Accelerators)