ETREE - A Database-Oriented Method for Generating Large Octree Meshes

Proceedings, 11th International Meshing Roundtable, Sandia National Laboratories, pp.127-140, September 15-18 2002

MESHING
RESEARCH
CORNER

11th International Meshing Roundtable
Ithaca, New York, USA
September 15-18, 2002

Tiankai Tu
Computer Science Department,
Carnegie Mellon University, Pittsburgh, PA, U.S.A.
tutk@cs.cmu.edu

David R. O’Hallaron
Computer Science Department and Electrical and Computer Engineering Department,
Carnegie Mellon University, Pittsburgh, PA, U.S.A.
droh@cs.cmu.edu

Julio C. Lopez
Electrical and Computer Engineering Department,
Carnegie Mellon University, Pittsburgh, PA, U.S.A.
jclopez@cs.cmu.edu

Abstract
This paper presents the design, implementation and evaluation of the etree, a database-oriented method for large out-of-core octree mesh generation. Our main idea is to map an octree to a database structure and perform all octree operations by querying the database. We use two database techniques - the linear quadtree and the B-tree to index and store the octants on disk. We introduce two two new techniques - auto navigation and local balancing to address the special need of mesh generation. Preliminary evaluation suggests that the etree method is an eective way of generating very large octree meshes (4:3 GB with 13:6 million elements) on a memory-limited machine (128 MB).

Download Full Paper (Postscript Format)