carrier image

Compact Array-Based Mesh Data Structures

Alumbaugh, Tyler J and Xiangmin Jiao

Proceedings, 14th International Meshing Roundtable, Springer-Verlag, pp.485-504, September 11-14 2005


14th International Meshing Roundtable
San Diego, CA, USA
September 11-14, 2005

Center for Simulation of Advanced Rockets
Computational Science and Engineering
University of Illinois at Urbana-Champaign

In this paper, we present simple and efficient array-based mesh data structures, including a compact representation of the half-edge data structure for surface meshes, and its generalization --a half-face data structure-- for volume meshes. These array-based structures provide comprehensive and efficient support for querying incidence, adjacency, and boundary classification, but require substantially less memory than pointer-based mesh representations. In addition, they are easy to implement in traditional programming languages (such as in C or Fortran 90) and convenient to exchange across different software packages or different storage media. In a parallel setting, they also support partitioned meshes and hence are particularly appealing for large-scale scientific and engineering applications. We demonstrate the construction and usage of these data structures for various operations, and compare their space and time complexities with alternative structures.

Download Full Paper (PDF Format)

Contact author(s) or publisher for availability and copyright information on above referenced article