Abstract
A novel algorithm of conforming Delaunay triangulation for curved geometry is presented in the paper. A progress has been made for the problem puzzled Delaunay refinement where curved constraints cannot be accepted as input directly. The algorithm is based on a new sufficient condition for the existence of constraints in triangulation. It requires computing only the intersection between constraints and Voronoi edges or faces instead of the circum-sphere of curved constraint. For the termination of the algorithm when small input angles exist in constraints, a weighted method is applied to ensure that the algorithm can terminate under any input. Some two-dimensional and three-dimensional results are also presented. It is shown that the algorithm has the capability of dealing with both linear and nonlinear constraints in a consistent way, without the need of maintaining triangular meshes on face constraints.
Similar content being viewed by others
References
Lawson C L. Generation a Triangular Grid with Applications of Contour Plotting. Technical Memo. 299. Jet Propulation Laboratory, 1972
Bowyer A. Computing dirichlet tessellations. The Comput J, 1981, 24: 162–166
Watson D F. Computing the Delaunay tessellation with applications to Voronoi polytopes. The Comput J, 1981, 24: 167–172
Chew L P. Guaranteed-quality Triangular Meshes, Report TR-98-983, Cornell Univ, 1989
Ruppert J. A Delaunay refinement algorithm for quality 2-dimensional mesh generation. J Algorithms, 1995, 18: 548–585
Shewchuk J R. Tetrahedral mesh generation by Delaunay refinement. In: Proc 14th Annu Sympos Comput Geom, 1998. 86–95
Shewchuk J R. Delaunay refinement algorithms for triangular mesh generation. Comput Geom, 2002, 22: 21–74
Murphy M, Mount D M, Gable C W. A point-placement strategy for conforming Delaunay tetrahedralization. Int J Comput Geom Appl, 2001, 11: 669–682
Cohen-Steiner D, Verdiere E C, Yvinec M. Conforming Delaunay triangulations in 3D. In: Proc Annu Sympos Comput Geom, 2002. 199–208
Pav S. Walkington N. Robust three dimensional delaunay refinement. In: Proc 13th Internat Meshing Roundtable, 2004. 145–156
Cheng S W, Poon S H. Graded conforming Delaunay tetrahedralization with bounded radius-edge ratio. In: Proc 14th Annu ACM-SIAM Sympos Discrete Algorithms, Baltimore, Maryland, USA, 2003. 295–304
Cheng S W, Dey T K, Ramos E A, et al. Quality meshing for polyhedral with small angles. In: Proc 20th Annu ACM Sympos Comput Geom, Brooklyn, New York, USA, 2004. 290–299
Yang Q. Constrainted delaunay triangulation (in Chinese). Ph. D Dissertation. Beijing: Beihang University, 2001. 80–87
Cheng S W, Dey T K, Edelsbrunner H, et al. Sliver exudation. J ACM, 2000, 47: 883–904
Shewchuk J R. Theoretically guaranteed Delaunay mesh generation-in practice. In: 13th Internat Meshing Roundtable, Short Course, 2004. 99–105
Boivin C, Ollivier-Gooch C. Guaranteed-quality triangular mesh generation for domains with curved boundaries. Int J Numer Meth Eng, 2002, 55: 1185–1213
Chew L P. Guaranteed-quality mesh generation for curved surfaces. In: Proc 9th Annu Sympos Comput Geom, San Diego, California, USA, 1993. 274–280
Boissonnat J D, Oudot S. Provably good surface sampling and approximation. In: Proc Eurographics Sympos Geom Process, 2003. 9–18
Cheng S W, Dey T K, Ramos E A, et al. Sampling and meshing a surface with guaranteed topology and geometry. In: Proc 20th Annu Sympos Comput Geom, Brooklyn, New York, USA, 2004. 280–289
Pav S E, Walkington N J. Delaunay refinement by corner lopping. In: Proc 14th Internat Meshing Roundtable. Berlin: Springer-Verlag, 2005. 165–182
Edelsbrunner H, Shah N. Triangulating topological spaces. Int J Comput Geom Appl, 1997, 7: 365–378
Wu Z Z, Huai J P, Yang Q. Algorithm for constructing the regular triangulation of a set of weighted points in E d (in Chinese). Chinese J Comput, 2002, 25: 1243–1249
Meng X H, Li J, Yang Q. Conforming Delaunay triangulation optimized by weighted method (in Chinese). J Beijing Univ Aeronaut Astronaut, 2005, 31: 1284–1288
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Meng, X., Li, J., Yang, Q. et al. Complex conforming Delaunay triangulation. Sci. China Inf. Sci. 53, 1130–1140 (2010). https://doi.org/10.1007/s11432-010-0097-6
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11432-010-0097-6