Octree Optimization

Al Globus, CSC, NASA Ames Research Center, 18 July 1990

NAS report RNR-90-011

Abstract

A number of algorithms search large, typically 3D, computational spaces for features of interest. Marching cubes isosurface generation described by Lorensen and Cline is an example. The speed of these algorithms is dependent on the time necessary to 1. find the features of interest in the data and 2. to compute over them. This paper describes an optimizing search using octrees to divide computation space. Information stored in the branch nodes is used to prune portions of computation space thus avoiding unnecessary memory references and tests for features of interest. This technique is implemented for marching cubes isosurface generation on computational fluid dynamics data. Numerical experiments were run indicating a factor of 3.8 - 9.0 overall performance increase, measured by stopwatch; and a factor of 3.9 - 9.9 speedup in calculation times as measured by the UNIX times() utility. The overhead is a one time cost of 0.2 - 2.8 the time to compute an average isosurface and O(n) space with a small constant factor. Thus, interactive rates may be approached for much larger data sets.

Postscript version