Compact representations of simplicial meshes in two and three dimensions

被引：24

作者：

Blandford, DK ^{[1
]}

Blelloch, GE ^{[1
]}

Cardoze, DE ^{[1
]}

Kadow, C ^{[1
]}

机构：

[1] Carnegie Mellon Univ, Dept Comp Sci, Pittsburgh, PA 15213 USA

来源：

INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS | 2005年 / 15卷 / 01期

基金：

美国国家科学基金会;

关键词：

mesh representations; computational geometry; compression;

D O I：

10.1142/S0218195905001580

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

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.

引用

页码：3 / 24

页数：22

共 46 条

[21]

Gu X., Harvard graphics archive-mesh library

[22] PRIMITIVES FOR THE MANIPULATION OF GENERAL SUBDIVISIONS AND THE COMPUTATION OF VORONOI DIAGRAMS [J].

GUIBAS, L ;

STOLFI, J .

ACM TRANSACTIONS ON GRAPHICS, 1985, 4 (02) :74-123

[23] RANDOMIZED INCREMENTAL CONSTRUCTION OF DELAUNAY AND VORONOI DIAGRAMS [J].

GUIBAS, LJ ;

KNUTH, DE ;

SHARIR, M .

ALGORITHMICA, 1992, 7 (04) :381-413

[24]

GUMHOLD S, 1998, P SIGGRAPH 98, P133

[25]

Isenburg M, 2000, COMP GRAPH, P263, DOI 10.1145/344779.344919

[26]

Karni Z, 2000, COMP GRAPH, P279, DOI 10.1145/344779.344924

[27] Using generic programming for designing a data structure for polyhedral surfaces [J].

Kettner, L .

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 1999, 13 (01) :65-90

[28] N-DIMENSIONAL GENERALIZED COMBINATORIAL MAPS AND CELLULAR QUASI-MANIFOLDS [J].

Lienhardt, Pascal .

INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS, 1994, 4 (03) :275-324

[29]

MCMAINS S, 2001, P 6 ACM S SOL MOD AP, P171

[30]

Mehlhorn Kurt, 1999, LEDA: A Platform for Combinatorial and Geometric Computing

← 1 2 3 4 5 →