Quad-tree Optimization

To help accelerate the rendering of height field objects I have written code to store the mesh in a quad-tree. To compare performance I have ray traced a scene with the quad-tree and without any sort of spacial subdivision.

Here is an image of the test scene.

No quad-tree optimization.

With quad-tree optimization.

The "classic" method was the method I implemented for assignment 4. It is actually a binary tree of bounding boxes.

Comments:

The quad-tree method was 46x faster than rendering without using any spacial subdivision. In fact, the actual performance (in general) is greater than this amount. The reason for this, is that the quad-tree takes a fair bit of pre-computation. In such a small test, the precomputation takes a significant amount of the total time. If the size of the image rendered was increased, I imagine the performance increase would be over 50x faster. I would also expect to see the performance of the quad-tree to improve a slight amount relative to the "classic" method.

Limitations:

When creating the quad-tree, it is necessary to split polygons when they cross a boundary in the quad tree. This splitting also means that I have to calculate new normals for the vertices I create. The new normals I introduce seem to cause some visual artifacts. I think this is because of a problem involving normal interpolation. This is discussed further in my submitted documentation for the project.