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 条

[1]

Amenta N., 2003, PROC 19 ANN ACM SYMP, P211, DOI DOI 10.1145/777792.777824

[2]

[Anonymous], P ACM SIAM S DISCR A

[3]

ANTAKI JF, 2002, SANGRIA PROJECT

[4]

ARGE L, 2001, P EUR S ALG, P1

[5]

Baumgart B. G., 1975, AFIPS P, V44, P589, DOI [DOI 10.1145/1499949.1500071, DOI 10.1145/1499949.1500071)]

[6]

BLANDFORD D, 2003, P ALENEX 03 WORKSH

[7]

BLANDFORD D, 2004, P WORKSH ALG ENG EXP

[8]

BLELLOCH G, 2001, J FUNCTIONAL PROGRAM, V11

[9] Design and implementation of a practical parallel Delaunay algorithm [J].

Blelloch, GE ;

Hardwick, JC ;

Miller, GL ;

Talmor, D .

ALGORITHMICA, 1999, 24 (3-4) :243-269

[10] Triangulations in CGAL [J].

Boissonnat, JD ;

Devillers, O ;

Pion, S ;

Teillaud, M ;

Yvinec, M .

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 2002, 22 (1-3) :5-19

← 1 2 3 4 5 →