## 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