Octree Data Structures and Creation by Stacking

摘要

Efficient, compact data structures are necessary for the representation of octrees. First, several concrete data structures for the octree abstract data type are compared in terms of storage space required and execution time needed to perform operations such as to find a certain node or obel. Compared are information theoretic minimal representations, digital search trees sometimes storing some information in an immediate mode without pointers, and storing the set of rays, which is often the most compact. It is also necessary to convert from other formats into octrees. Therefore, a fast method to convert a quadric surface into rays is described next. Finally, a new algorithm to stack these rays into an octree is given. It is very fast, has no intermediate swell in the storage, and does not thrash virtual memory. These algorithms have been implemented and tested on large examples.