Summary
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 finite-precision coordinates yield vertices on a line that are not perfectly collinear and polygonal facets that are not perfectly flat. We experimentally compare two recent algorithms for inserting a polygonal facet into a CDT: a bistellar flip algorithm of Shewchuk (Proc. 19th Annual Symposium on Computational Geometry, June 2003) and a cavity retriangulation algorithm of Si and Gärtner (Proc. Fourteenth International Meshing Roundtable, September 2005). We modify these algorithms to succeed in practice for polygons whose vertices deviate from exact coplanarity.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Boissonnat, J.-D., Devillers, O., Pion, S., Teillaud, M., Yvinec, M.: Triangulations in CGAL. Computational Geometry: Theory and Applications 22(1-3), 5–19 (2002)
Bowyer, A.: Computing Dirichlet tessellations. The Computer Journal 24(2), 162–166 (1981)
Cheng, S.-W., Dey, T.K., Edelsbrunner, H., Facello, M.A., Teng, S.-H.: Sliver exudation. Journal of the Association for Computing Machinery 47(5), 883–904 (2000)
Paul Chew, L.: Building Voronoi diagrams for convex polygons in linear expected time. Technical Report PCS-TR90-147, Department of Mathematics and Computer Science, Dartmouth College (1990)
Clarkson, K.L., Shor, P.W.: Applications of random sampling in computational geometry, II. Discrete & Computational Geometry 4(1), 387–421 (1989)
Devillers, O., Pion, S., Teillaud, M.: Walking in a triangulation. In: Proceedings of the Seventeenth Annual Symposium on Computational Geometry, Medford, Massachusetts, pp. 106–114 (June 2001)
Edelsbrunner, H., Mücke, E.P.: Simulation of simplicity: A technique to cope with degenerate cases in geometric algorithms. ACM Transactions on Graphics 9(1), 66–104 (1990)
Fortune, S., Van Wyk, C.J.: Static analysis yields efficient exact integer arithmetic for computational geometry. ACM Transactions on Graphics 15(3), 223–248 (1996)
Guigue, P., Devillers, O.: Fast and robust triangle-triangle overlap test using orientation predicates. Journal of Graphics Tools 8(1), 25–32 (2003)
Lee, D.-T., Lin, A.K.: Generalized Delaunay triangulations for planar graphs. Discrete & Computational Geometry 1, 201–217 (1986)
Miller, G.L., Talmor, D., Teng, S.-H., Walkington, N.J., Wang, H.: Control volume meshes using sphere packing: Generation, refinement and coarsening. In: Proceedings of the 5th International Meshing Roundtable, Pittsburgh, Pennsylvania, pp. 47–61 (October 1996)
Mücke, E.P.: Shapes and Implementations in Three-Dimensions Geometry. Ph.D. thesis, Department of Computer Science, University of Illinois at Urbana-Champaign, Urbana, Illinois (1993)
Seidel, R.: Voronoi diagrams in higher dimensions. Diplomarbeit, Institut für Informationsverarbeitung, Technische Universität Graz (1982)
Shewchuk, J.R.: Adaptive precision floating-point arithmetic and fast robust geometric predicates. Discrete & Computational Geometry 18(3), 305–363 (1997)
Shewchuk, J.R.: A condition guaranteeing the existence of higher-dimensional constrained Delaunay triangulations. In: Proceedings of the Fourteenth Annual Symposium on Computational Geometry, pp. 76–85 (June 1998)
Shewchuk, J.R.: Tetrahedral mesh generation by Delaunay refinement. In: Proceedings of the Fourteenth Annual Symposium on Computational Geometry, Minneapolis, Minnesota, pp. 86–95 (June 1998)
Shewchuk, J.R.: Sweep algorithms for constructing higher-dimensional constrained Delaunay triangulations. In: Proceedings of the Sixteenth Annual Symposium on Computational Geometry, Hong Kong, pp. 350–359 (June 2000)
Shewchuk, J.R.: Constrained Delaunay tetrahedralizations and provably good boundary recovery. In: Proceedings of the 11th International Meshing Roundtable, Ithaca, New York, pp. 193–204 (September 2002)
Shewchuk, J.R.: Updating and constructing constrained Delaunay and constrained regular triangulations by flips. In: Proceedings of the Nineteenth Annual Symposium on Computational Geometry, pp. 181–190 (June 2003)
Shewchuk, J.R.: General-dimensional constrained Delaunay triangulations and constrained regular triangulations I: Combinatorial properties. Discrete & Computational Geometry 39(1-3), 580–637 (2008)
Si, H., Gärtner, K.: Meshing piecewise linear complexes by constrained Delaunay tetrahedralizations. In: Hanks, B.W. (ed.) Proceedings of the Fourteenth International Meshing Roundtable, pp. 147–163 (September 2005)
Si, H., Gärtner, K.: 3D boundary recovery by constrained Delaunay tetrahedralization. International Journal for Numerical Methods in Engineering 85(11), 1341–1364 (2011)
Watson, D.F.: Computing the n-dimensional Delaunay tessellation with application to Voronoi polytopes. The Computer Journal 24(2), 167–172 (1981)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Si, H., Shewchuk, J.R. (2013). Incrementally Constructing and Updating Constrained Delaunay Tetrahedralizations with Finite Precision Coordinates. In: Jiao, X., Weill, JC. (eds) Proceedings of the 21st International Meshing Roundtable. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-33573-0_11
Download citation
DOI: https://doi.org/10.1007/978-3-642-33573-0_11
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-33572-3
Online ISBN: 978-3-642-33573-0
eBook Packages: EngineeringEngineering (R0)