Evaluation of subdivision methods used in octree ray tracing algorithms

Show full item record

Title: Evaluation of subdivision methods used in octree ray tracing algorithms
Author: Brown, Scott
Abstract: 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 investigated. Octrees constructed with "rectangular" octants which more closely bound the scene were tested as one alternative to the cubic octants method. As a second alternative, this author proposed and implemented an "ideal-cut" subdivision algorithm that subdivides the parent octant through the mean location of the facets contained in the octant. For the scenes tested, the "conventional" cubic algorithm was shown to perform better than either alternative method, although, it was also shown to suffer from memory and run-time explosions on some scenes. The "rectangular" octant algorithm consistently approached the run-times produced by the "cubic" method. Since, the "rectangular" method defaults to the "cubic" method for scenes with 1:1:1 aspect ratios, the "rectangular" method must be considered as a reasonable alternative in rendering applications. The "idealcut"
Record URI: http://hdl.handle.net/1850/13615
Date: 1998

Files in this item

Files Size Format View
SBrownThesis02-12-1998.pdf 15.75Mb PDF View/Open

The following license files are associated with this item:

This item appears in the following Collection(s)

Show full item record

Search RIT DML


Advanced Search

Browse