COMPACT REPRESENTATIONS OF SIMPLICIAL MESHES IN TWO AND THREE DIMENSIONS
- 1 February 2005
- journal article
- Published by World Scientific Pub Co Pte Ltd in International Journal of Computational Geometry & Applications
- Vol. 15 (1), 3-24
- https://doi.org/10.1142/s0218195905001580
Abstract
We describe data structures for representing simplicial meshes compactly while supporting online queries and updates efficiently. Our data structure requires about a factor of five less memory than the most efficient standard data structures for triangular or tetrahedral meshes, while efficiently supporting traversal among simplices, storing data on simplices, and insertion and deletion of simplices. Our implementation of the data structures uses about 5 bytes/triangle in two dimensions (2D) and 7.5 bytes/tetrahedron in three dimensions (3D). We use the data structures to implement 2D and 3D incremental algorithms for generating a Delaunay mesh. The 3D algorithm can generate 100 Million tetrahedra with 1 Gbyte of memory, including the space for the coordinates and all data used by the algorithm. The runtime of the algorithm is as fast as Shewchuk's Pyramid code, the most efficient we know of, and uses a factor of 3.5 less memory overall.Keywords
This publication has 21 references indexed in Scilit:
- Triangulations in CGALComputational Geometry, 2002
- External memory algorithms and data structuresACM Computing Surveys, 2001
- Using generic programming for designing a data structure for polyhedral surfacesComputational Geometry, 1999
- Edgebreaker: connectivity compression for triangle meshesIEEE Transactions on Visualization and Computer Graphics, 1999
- Geometric compression through topological surgeryACM Transactions on Graphics, 1998
- Separators for sphere-packings and nearest neighbor graphsJournal of the ACM, 1997
- A Delaunay Refinement Algorithm for Quality 2-Dimensional Mesh GenerationJournal of Algorithms, 1995
- Randomized incremental construction of Delaunay and Voronoi diagramsAlgorithmica, 1992
- Computing the n-dimensional Delaunay tessellation with application to Voronoi polytopesThe Computer Journal, 1981
- Universal codeword sets and representations of the integersIEEE Transactions on Information Theory, 1975