research-article

Fast centroidal Voronoi Delaunay triangulation for unstructured mesh generation

Authors:

Z.J. TanAuthors Info & Claims

Journal of Computational and Applied Mathematics, Volume 280, Issue C

Pages 158 - 173

https://doi.org/10.1016/j.cam.2014.11.035

Published: 15 May 2015 Publication History

Abstract

A fast unstructured mesh generation algorithm based on conforming centroidal Voronoi Delaunay triangulation (CfCVDT) algorithm (Ju, 2007) is proposed in this paper. In the new algorithm, the constrained Delaunay triangulation (CDT) algorithm is used only for the generation of the initial mesh. The mesh quality shall be continuously improved by updating the positions of vertices and flipping edges in a number of iterations. Since the most time consuming procedure in CfCVDT algorithm is the CDT in each iteration which has been successfully avoided in this new algorithm the efficiency has been significantly improved. Furthermore, the meshes generated by this algorithm have similar high quality features as that generated by CfCVDT. When complex interfaces are involved, our algorithm can keep the mesh conforming to the interfaces very efficiently. By using various density functions, this algorithm can produce high quality non-uniform meshes for potentially many applications. A fast high quality triangular mesh generation algorithm (FCfCVDT) is proposed based on the CfCVDT algorithm.The FCfCVDT algorithm significantly improves the efficiency of CfCVDT algorithm at the same time maintains the mesh quality.It is capable of generating high quality body/interface fitted meshes for complicate domains/interfaces.

References

[1]

Nigel P. Weatherill, Delaunay triangulation in computational fluid dynamics, Comput. Math. Appl., 24 (1992) 129-150.

[2]

Yunqing Huang, Hengfeng Qin, Desheng Wang, Qiang Du, Convergent adaptive finite element method based on centroidal Voronoi tessellations and superconvergence, Commun. Comput. Phys., 10 (2011) 339.

[3]

Lili Ju, Max Gunzburger, Weidong Zhao, Adaptive finite element methods for elliptic PDEs based on conforming centroidal Voronoi-Delaunay triangulations, SIAM J. Sci. Comput., 28 (2006) 2023-2053.

Digital Library

[4]

Vittorio Cristini, Jerzy Bławzdziewicz, Michael Loewenberg, An adaptive mesh algorithm for evolving surfaces: simulations of drop breakup and coalescence, J. Comput. Phys., 168 (2001) 445-463.

Digital Library

[5]

H. Borouchaki, S.H. Lo, Fast Delaunay triangulation in three dimensions, Comput. Methods Appl. Mech. Engrg., 128 (1995) 153-167.

[6]

Qiang Du, Max Gunzburger, Grid generation and optimization based on centroidal Voronoi tessellations, Appl. Math. Comput., 133 (2002) 591-607.

Digital Library

[7]

Lili Ju, Conforming centroidal Voronoi Delaunay triangulation for quality mesh generation, Int. J. Numer. Anal. Model., 4 (2007) 531-547.

[8]

Jonathan Richard Shewchuk, Delaunay refinement algorithms for triangular mesh generation, Comput. Geom. Theory Appl., 22 (2002) 21-74.

Digital Library

[9]

Jane Tournois, Pierre Alliez, Olivier Devillers, Interleaving Delaunay refinement and optimization for 2D triangle mesh generation, in: Proceedings of the 16th International Meshing Roundtable, Springer, 2008, pp. 83-101.

[10]

David A. Field, Laplacian smoothing and Delaunay triangulations, Commun. Appl. Numer. Methods, 4 (1988) 709-712.

[11]

Peter Hansbo, Generalized laplacian smoothing of unstructured grids, Comm. Numer. Methods Engrg., 11 (1995) 455-464.

[12]

Long Chen, Jinchao Xu, Optimal Delaunay triangulations, J. Comput. Math., 22 (2004) 299-308.

[13]

Long Chen, Michael Holst, Efficient mesh optimization schemes based on optimal Delaunay triangulations, Comput. Methods Appl. Mech. Engrg., 200 (2011) 967-984.

[14]

Qiang Du, Vance Faber, Max Gunzburger, Centroidal voronoi tessellations: applications and algorithms, SIAM Rev., 41 (1999) 637-676.

Digital Library

[15]

Qiang Du, Max Gunzburger, Lili Ju, Advances in studies and applications of centroidal Voronoi tessellations, Numer. Math. Theory Methods Appl., 3 (2010) 119-142.

[16]

James MacQueen, Some methods for classification and analysis of multivariate observations, in: Proceedings of the Fifth Berkeley Symposium on Mathematical Statistics and Probability, California, USA, vol. 1, 1967, pp. 281-297.

[17]

Stuart Lloyd, Least squares quantization in PCM, IEEE Trans. Inform. Theory, 28 (1982) 129-137.

Digital Library

[18]

Jane Tournois, Pierre Alliez, Olivier Devillers, 2D centroidal Voronoi tessellations with constraints, Numer. Math-Theory Me., 3 (2010) 212-222.

[19]

Pedro Machado Manhães de Castro, Jane Tournois, Pierre Alliez, Olivier Devillers, Filtering relocations on a Delaunay triangulation, in: Computer Graphics Forum. Vol. 28, Wiley Online Library, 2009, pp. 1465-1474.

[20]

Yang Liu, Wenping Wang, Bruno Lévy, Feng Sun, Dong-Ming Yan, Lin Lu, Chenglei Yang, On centroidal voronoi tessellation energy smoothness and fast computation, ACM Trans. Graph., 28 (2009) 101.

Digital Library

[21]

Qiang Du, Maria Emelianenko, Lili Ju, Convergence of the Lloyd algorithm for computing centroidal Voronoi tessellations, SIAM J. Numer. Anal., 44 (2006) 102-119.

Digital Library

[22]

Per-Olof Persson, Gilbert Strang, A simple mesh generator in MATLAB, SIAM Rev., 46 (2004) 329-345.

Digital Library

[23]

Marc Vigo Anglada, An improved incremental algorithm for constructing restricted Delaunay triangulations, Comput. Graph., 21 (1997) 215-223.

[24]

David A. Field, Qualitative measures for initial meshes, Internat. J. Numer. Methods Engrg., 47 (2000) 887-906.

Cited By

Haklı HUğuz HÇay T(2016)A new approach for automating land partitioning using binary search and Delaunay triangulationComputers and Electronics in Agriculture10.1016/j.compag.2016.05.006125:C(129-136)Online publication date: 1-Jul-2016
https://dl.acm.org/doi/10.1016/j.compag.2016.05.006

Recommendations

Grid generation and optimization based on centroidal Voronoi tessellations

Centroidal Voronoi tessellations (CVTs) are Voronoi tessellations of a region such that the generating points of the tessellations are also the centroids of the corresponding Voronoi regions. Such tessellations are of use in very diverse applications, ...
Fast spherical centroidal Voronoi mesh generation: A Lloyd-preconditioned LBFGS method in parallel
Abstract
Centroidal Voronoi tessellation (CVT)-based mesh generation is a very effective technique for creating high-quality Voronoi meshes and their dual Delaunay triangulations that often play a crucial role in applications, including ocean ...
Highlights
- The method could reduce computational costs of classical methods one order of magnitude in generating highly variable-resolution meshes.
Efficient computation of clipped Voronoi diagram for mesh generation

The Voronoi diagram is a fundamental geometric structure widely used in various fields, especially in computer graphics and geometry computing. For a set of points in a compact domain (i.e. a bounded and closed 2D region or a 3D volume), some Voronoi ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of Computational and Applied Mathematics

Journal of Computational and Applied Mathematics Volume 280, Issue C

May 2015

412 pages

ISSN:0377-0427

Issue’s Table of Contents

Copyright © Elsevier B.V.

Publisher

Elsevier Science Publishers B. V.

Netherlands

Publication History

Published: 15 May 2015

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 05 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Haklı HUğuz HÇay T(2016)A new approach for automating land partitioning using binary search and Delaunay triangulationComputers and Electronics in Agriculture10.1016/j.compag.2016.05.006125:C(129-136)Online publication date: 1-Jul-2016
https://dl.acm.org/doi/10.1016/j.compag.2016.05.006

View Options

View options

Figures

Tables

Media

View Issue’s Table of Contents