carrier image

Incrementally Constructing and Updating Constrained Delaunay Tetrahedralizations with Finite Precision Coordinates

Si, Hang and Jonathan Richard Shewchuk

21st International Meshing Roundtable, Springer-Verlag, pp.173-190, October 7-10 2012


21st International Meshing Roundtable
San Jose, CA
October 7-10,2012

Weierstrass Institute for Applied Analysis and Stochastics (WIAS), MohrenstraBe 39, 10117, Berlin, Germany

Constrained Delaunay tetrahedralizations (CDTs) are valuable for generating meshes of nonconvex domains and domains with internal boundaries, but they are difficult to maintain robustly when nite-precision coordinates yield vertices on a line that are not perfectly collinear and polygonal facets that are not perfectly at. We experimentally compare two recent algorithms for inserting a polygonal facet into a CDT: a bistellar ip algorithm of Shewchuk (Proc. 19th Annual Symposium on Computational Geometry, June 2003) and a cavity retriangulation algorithm of Si and Gartner (Proc. Fourteenth International Meshing Roundtable, September 2005). We modify these algorithms to succeed in practice for polygons whose vertices deviate from exact coplanarity.

Download Full Paper (PDF Format)

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