PDL Abstract

A Computational Database System for Generating Unstructured Hexahedral Meshes with Billions of Elements

SC2004, November 6-12, 2004, Pittsburgh, PA USA.

Tiankai Tu, David R. O’Hallaron

School of Computer Science
Dept. Electrical and Computer Engineering
Carnegie Mellon University
Pittsburgh, PA 15213


For a large class of physical simulations with relatively simple geometries, unstructured octree-based hexahedral meshes provide a good compromise between adaptivity and simplicity. However, generating unstructured hexahedral meshes with over 1 billion elements remains a challenging task. We propose a database approach to solve this problem. Instead of merely storing generated meshes into conventional databases, we have developed a new kind of software system called Computational Database System (CDS) to generate meshes directly on databases. Our basic idea is to extend existing database techniques to organize and index mesh data, and use database-aware algorithms to manipulate database structures and generate meshes. This paper presents the design, implementation, and evaluation of a prototype CDS named Weaver, which has been used successfully by the CMU Quake project to generate queryable high-resolution finite element meshes for earthquake simulations with up to 1.22B elements and 1.37B nodes.