Advanced 3D Hidden Surface Removal Using Octrees

Student: Cameron John Mcallister

Supervisor: Dr. Kevin Gates

Category: Software Engineering Thesis Project

Modern day three dimensional graphics display programs are nearly all based upon the same model of a general main processor, and a dedicated 3D graphics processor which is specially designed to perform calculations on and display 3D scenes. Both of these components have advanced significantly recently and will continue to do so. Since both components perform different (yet partially overlapping) tasks, balancing the workload between the two can be difficult. One way to alleviate the workload from one to the other is by intelligent hidden surface removal before the scene is sent to the graphics processor.

One form of hidden surface removal which is used in most current applications is frustrum culling, removing all of the scene except what is in the possible field of vision. This is very dependent on how the 3D scene is stored, and this thesis is a look at the implementation and optimisation of an Octree data structure, which are only used in a handful of systems and in no current major commercial 3D programs.

Taken into consideration is not only how the octree structure performs in its primary task, storing the scene and frustum culling, but also how it interacts with occlusion culling techniques, including what extra data can be stored or processed in the spatial database and frustrum culling stages to assist the performance of occlusion cullers, such as those investigated by David Pershouse.

A demonstration of recursive traversal frustum culling using a quadtree (2D octree). The dotted shape represents the viewing area, and each child octant contains one object (green circle). As the tree is traversed, each octant's visibility is determined, and if it is visible, then it subdivides further until each octant contains at most one object.

Poster Presentation (PDF)

Thesis Document (PDF)