used in Octree Ray Tracing Algorithms
Scott D. Brown · 1998
Key words: ray tracing optimization, non-uniform spatial subdivision, octree, octtree, octree subdivision methods. The non-uniform spatial subdivision technique refined by Andrew Glassner [Glassner 1984] minimizes facet intersection tests (i) by automatically generating a density dependent spatial hierarchy of facet regions (called an octree)and(ii) by only testing facets in regions along the path of the ray. Past research has addressed optimization of the octree ray tracing process by separately improving both the octree traversal method and facet intersection algorithms. This author attempted to further improve the overall approach by attempting to identify new octree construction methods that would decrease the number of traversals required to render the scene. This research focused on the subdivision technique used in constructing the octree. The conventional Glassner algorithm utilizes cubic octants that can result in a large population of empty octants when rendering scenes containing localized regions with high facet density. Sparse octrees (containing significant numbers of empty octants) were believed to hinder performance of the facet traversal algorithm. As an alternative to the conventional cubic algorithm, the performance benefits of non-cubic octants were