06/01/1990 09:00 AM
Computer Science
The large size of many volume data sets often prevents visualization algorithms from providing interactive rendering. The use of hierarchical data structures can ameliorate this problem by storing summary information to prevent useless exploration of regions of little or no interest within the volume. This paper discusses research into the use of the *octree* hierarchical data structure for this purpose. Octrees are well suited to the six-sided cell structure of many volumes. We introduce a new space-efficient design for octree representations of volumes whose dimensions are not conveniently a power of two; octrees following this design are called *branch- on-need octrees* (BONOs). We also describe a caching method that essentially passes information between octree neighbors whose visitation times may be quite different, then discards it when its useful life is over. Using the application of octrees is isosurface generation as a focus, we present space and time comparisons for octree-based versus more traditional ``marching\'\' methods.
