More Web Proxy on the site http://driver.im/

research-article

POLYLLA: polygonal meshing algorithm based on terminal-edge regions

Authors:

Sergio Salinas-Fernández,

Nancy Hitschfeld-Kahler,

Alejandro Ortiz-Bernardin,

Hang SiAuthors Info & Claims

Engineering with Computers, Volume 38, Issue 5

Pages 4545 - 4567

https://doi.org/10.1007/s00366-022-01643-4

Published: 01 October 2022 Publication History

Abstract

This paper presents an algorithm to generate a new kind of polygonal mesh obtained from triangulations. Each polygon is built from a terminal-edge region surrounded by edges that are not the longest-edge of any of the two triangles that share them. The algorithm is termed Polylla and is divided into three phases. The first phase consists of labeling each edge of the input triangulation according to its size; the second phase builds polygons (simple or not) from terminal-edges regions using the label system; and the third phase transforms each non simple polygon into simple ones. The final mesh contains polygons with convex and non convex shape. Since Voronoi-based meshes are currently the most used polygonal meshes, we compare some geometric properties of our meshes against constrained Voronoi meshes. Several experiments were run to compare the shape and size of polygons, the number of final mesh points and polygons. For the same input, Polylla meshes contain less polygons than Voronoi meshes and the algorithm is simpler and faster than the algorithm to generate constrained Voronoi meshes. Finally, we have validated Polylla meshes by solving the Laplace equation on an L-shaped domain using the virtual element method (VEM). We show that the numerical performance of the VEM using Polylla meshes and Voronoi meshes is similar.

References

[1]

Beirão da Veiga L, Brezzi F, Cangiani A, Manzini G, Marini L, and Russo A Basic principles of virtual element methods Math Models Methods Appl Sci 2013 23 01 199-214

[2]

Beirão da Veiga L, Brezzi F, and Marini LD Virtual elements for linear elasticity problems SIAM J Numer Anal 2013 51 2 794-812

[3]

Wriggers P, Aldakheel F, Hudobivnik B (2019) Application of the virtual element method in mechanics. Technical report, report number: ISSN 2196-3789. Leibniz Universität Hannover (January)

[4]

Rivara MC New longest-edge algorithms for the refinement and/or improvement of unstructured triangulations Int J Numer Methods Eng 1997 40 3313-3324

[5]

Schlömer N (2021) pygalmesh: Python interface for CGAL’s meshing tools. https://github.com/nschloe/pygalmesh. Accessed 30 Jan 2022

[6]

Huisman O, de By R (2009) Principles of geographic information systems: an introductory textbook, p 258

[7]

Johnson AE and Hebert M Control of polygonal mesh resolution for 3-D computer vision Graph Models Image Process 1998 60 4 261-285

[8]

Ho-Le K Finite element mesh generation methods: a review and classification Comput Aided Des 1988 20 1 27-38

[9]

Zhang YJ, Hughes TJR, Bajaj CL (2007) Automatic 3D mesh generation for a domain with multiple materials. In: IMR

[10]

Cheng S-W, Dey TK, Shewchuk J, Sahni S (2013) Delaunay mesh generation. CRC Press Boca Raton

[11]

Yan D-M, Wang W, Lévy B, and Liu Y Efficient computation of clipped Voronoi diagram for mesh generation Comput Aided Des 2011

[12]

Yan D-M, Wang K, Levy B, Alonso L (2011) Computing 2D periodic centroidal Voronoi tessellation. In: 2011 eighth international symposium on Voronoi diagrams in science and engineering, pp 177–184.

[13]

Talischi C, Paulino G, Pereira A, and Menezes I Polymesher: a general-purpose mesh generator for polygonal elements written in matlab Struct Multidiscip Optim 2012 45 3 309-328

[14]

Löhner R Progress in grid generation via the advancing front technique Eng Comput 1996 12 3–4 186-210

[15]

Schöberl J Netgen an advancing front 2D/3D-mesh generator based on abstract rules Comput Vis Sci 1997 1 41-52

[16]

Bern M, Eppstein D, and Gilbert J Provably good mesh generation J Comput Syst Sci 1994 48 3 384-409

[17]

Bommes D, Lévy B, Pietroni N, Puppo E, Silva C, Tarini M, Zorin D (2013) Quad-mesh generation and processing: a survey. In: Computer graphics forum. Wiley Online Library, vol 32, pp 51–76

[18]

Liang X and Zhang YJ An octree-based dual contouring method for triangular and tetrahedral mesh generation with guaranteed angle range Eng Comput 2013 30 211-222

[19]

Owen SJ, Staten ML, Canann SA, and Saigal S Q-morph: an indirect approach to advancing front quad meshing Int J Numer Methods Eng 1999 44 9 1317-1340

[20]

Ito Y and Nakahashi K Unstructured mesh generation for viscous flow computations IMR 2002 2002 367-377

[21]

Owen SJ A survey of unstructured mesh generation technology IMR 1998 239 267

[22]

Johnen A (2016) Indirect quadrangular mesh generation and validation of curved finite elements. Ph.D. thesis, Université de Liège, Liège, Belgique

[23]

Lee CK and Lo SH A new scheme for the generation of a graded quadrilateral mesh Comput Struct 1994 52 5 847-857

[24]

Remacle J-F, Lambrechts J, Seny B, Marchandise E, Johnen A, and Geuzainet C Blossom-quad: a non-uniform quadrilateral mesh generator using a minimum-cost perfect-matching algorithm Int J Numer Methods Eng 2012 89 9 1102-1119

[25]

Merhof D, Grosso R, Tremel U, and Greiner G Anisotropic quadrilateral mesh generation: an indirect approach Adv Eng Softw 2007 38 11/12 860-867

[26]

Shewchuk JR Lin MC and Manocha D Triangle: engineering a 2D quality mesh generator and Delaunay triangulator Applied computational geometry towards geometric engineering 1996 Berlin Springer 203-222

[27]

Si H (2019) An introduction to unstructured mesh generation methods and softwares for scientific computing. Course. 2019 International Summer School in Beihang University

[28]

Barber CB, Dobkin DP, and Huhdanpaa H The Quickhull algorithm for convex hulls ACM Trans Math Softw 1996 22 4 469-483

[29]

Yvinec M (2021) 2D triangulations. In: CGAL user and reference manual, 5.3.1 edn. CGAL Editorial Board, CGAL project. https://doc.cgal.org/5.3.1/Manual/packages.html#PkgTriangulation2. Accessed 23 Jan 2022

[30]

Chew LP Constrained delaunay triangulation Algorithmica 1994 4 97-108

[31]

Canann SA, Tristano JR, Staten ML (1998) An approach to combined Laplacian and optimization-based smoothing for triangular, quadrilateral and quad-dominant meshes. In: 7th international meshing roundtable, pp 479–494

[32]

Lee K-Y, Kim I-I, Cho D-Y, and Kim T-w An algorithm for automatic 2D quadrilateral mesh generation with line constraints Comput Aided Des 2003 35 12 1055-1068

[33]

Owen SJ, Staten ML, Canann SA, Saigal S (1998) Advancing front quadrilateral meshing using triangle transformations. In: Proceedings, 7th international meshing roundtable, vol 98, pp 409–428

[34]

Jaillet F, Lobos C (2021) Fast Quadtree/Octree adaptive meshing and re-meshing with linear mixed elements. Eng Comput 1435–5663

[35]

Perumal L A brief review on polygonal/polyhedral finite element methods Math Probl Eng 2018 2018 1-22

[36]

Chi H, Talischi C, Lopez-Pamies O, and Paulino G Polygonal finite elements for finite elasticity Int J Numer Methods Eng 2015 101 305-328

[37]

Yan D-M, Wang W, Lévy B, Liu Y (2010) Efficient computation of 3D clipped Voronoi diagram. In: GMP, pp 269–282

[38]

Ebeida MS, Mitchell SA (2012) Uniform random Voronoi meshes. In: Quadros WR (ed) Proceedings of the 20th international meshing roundtable, pp 273–290. Springer, Berlin

[39]

Sieger D, Alliez P, Botsch M (2010) Optimizing Voronoi diagrams for polygonal finite element computations. In: Proceedings of the 19th international meshing roundtable, IMR 2010, October 3–6, 2010, Chattanooga, Tennessee, USA, pp 335–350

[40]

Wachspress EL A rational finite element basis. Mathematics in science and engineering 1975 New York Academic Press

[41]

Sukumar N and Malsch EA Recent advances in the construction of polygonal finite element interpolants Arch Comput Methods Eng 2006 13 1 129-163

[42]

Tabarraei A and Sukumar N Extended finite element method on polygonal and quadtree meshes Comput Methods Appl Mech Eng 2008 197 5 425-438

[43]

Beirão da Veiga L, Lovadina C, and Mora D A virtual element method for elastic and inelastic problems on polytope meshes Comput Methods Appl Mech Eng 2015 295 327-346

[44]

Cáceres E, Gatica GN, and Sequeira FA A mixed virtual element method for the brinkman problem Math Models Methods Appl Sci 2017 27 04 707-743

[45]

Cáceres E, Gatica GN, and Sequeira FA A mixed virtual element method for quasi-Newtonian stokes flows SIAM J Numer Anal 2018 56 1 317-343

[46]

Benedetto MF, Berrone S, Pieraccini S, and Scialò S The virtual element method for discrete fracture network simulations Comput Methods Appl Mech Eng 2014 280 135-156

[47]

Wriggers P, Reddy BD, Rust WT, and Hudobivnik B Efficient virtual element formulations for compressible and incompressible finite deformations Comput Mech 2017 60 253-268

[48]

Wriggers P and Hudobivnik B A low order virtual element formulation for finite elasto-plastic deformations Comput Methods Appl Mech 2017 327 459-477

[49]

Hussein A, Aldakheel F, Hudobivnik B, Wriggers P, Guidault P-A, and Allix O A computational framework for brittle crack-propagation based on efficient virtual element method Finite Elem Anal Des 2019 159 15-32

[50]

Aldakheel F, Hudobivnik B, and Wriggers P Virtual element formulation for phase-field modeling of ductile fracture Int J Multiscale Comput Eng 2019 17 2 181-200

[51]

Park K, Chi H, and Paulino GH On nonconvex meshes for elastodynamics using virtual element methods with explicit time integration Comput Methods Appl Mech Eng 2019 356 669-684

[52]

Chi H, da Veiga LB, and Paulino GH Some basic formulations of the virtual element method (VEM) for finite deformations Comput Methods Appl Mech Eng 2017 318 148-192

[53]

Torres J, Hitschfeld N, Ruiz RO, and Ortiz-Bernardin A Krzhizhanovskaya VV, Závodszky G, Lees MH, Dongarra JJ, Sloot PMA, Brissos S, and Teixeira J Convex polygon packing based meshing algorithm for modeling of rock and porous media Computational science—ICCS 2020 2020 Cham Springer 257-269

[54]

Alonso R, Ojeda J, Hitschfeld N, Hervías C, and Campusano LE Delaunay based algorithm for finding polygonal voids in planar point sets Astron Comput 2018 22 48-62

[55]

Ojeda J, Alonso R, Hitschfeld-Kahler N (2018) A new algorithm for finding polygonal voids in delaunay triangulations and its parallelization. In: The 34th European workshop on computational geometry, EuroCG, pp 349–354

[56]

Hervías C, Hitschfeld-Kahler N, Campusano LE, Font G (2013) On finding large polygonal voids using Delaunay triangulation: the case of planar point sets. In: Proceedings of the 22nd international meshing roundtable, pp 275–292

[57]

De Floriani L, Kobbelt L, and Puppo E Dodgson NA, Floater MS, and Sabin MA A survey on data structures for level-of-detail models Advances in multiresolution for geometric modelling 2005 Berlin Springer 49-74

[58]

Boissonnat J-D, Devillers O, Pion S, Teillaud M, Yvinec M (2002) Triangulations in cgal. Comput Geom 22(1):5–19. 16th ACM symposium on computational geometry.

[59]

Turner R (2021) Deldir: Delaunay Triangulation and Dirichlet (Voronoi) Tessellation. R package version 0.2-10. https://CRAN.R-project.org/package=deldir. Accessed 30 Aug 2021

[60]

Austral University of Chile: Patagón Supercomputer (2021). https://patagon.uach.cl. Accessed 30 Sep 2021

[61]

Karavelas M (2021) 2D Voronoi diagram adaptor. In: CGAL user and reference manual, 5.3.1 edn. CGAL Editorial Board, CGAL project. https://doc.cgal.org/5.3.1/Manual/packages.html#PkgVoronoiDiagram2. Accessed 23 Jan 2022

[62]

Ortiz-Bernardin A, Álvarez C, Hitschfeld-Kahler N, Russo A, Silva-Valenzuela R, and Olate-Sanzana E Veamy: an extensible object-oriented C++ library for the virtual element method Numer Algor 2019 82 4 1-32

[63]

Mitchell WF A collection of 2D elliptic problems for testing adaptive grid refinement algorithms Appl Math Comput 2013 220 350-364

Cited By

Balreira Dda Silveira T(2024)Triangular matrix-based lossless compression algorithm for 3D mesh connectivityThe Visual Computer: International Journal of Computer Graphics10.1007/s00371-024-03400-840:6(3961-3970)Online publication date: 1-Jun-2024
https://dl.acm.org/doi/10.1007/s00371-024-03400-8

Recommendations

A new quality preserving polygonal mesh refinement algorithm for Polygonal Element Methods
Abstract
Mesh adaptivity is a useful tool for efficient solution to partial differential equations in very complex geometries. In the present paper we discuss the use of polygonal mesh refinement in order to tackle two common issues: first, ...
Highlights
- A new refinement strategy for general convex polygons.
- Quality measure of a ...
Untangling polygonal and polyhedral meshes via mesh optimization

We propose simple and efficient optimization-based untangling strategies for 2D polygonal and 3D polyhedral meshes. The first approach uses a size-based mesh metric, which eliminates inverted elements by averaging element size over the entire mesh. The ...
A macro BDM H-div mixed finite element on polygonal and polyhedral meshes
Abstract
A BDM type of H ( div ) mixed finite element is constructed on polygonal and polyhedral meshes. The flux space is the H ( div ) subspace of the n-product Π i P k ( T i ) d space such that the divergence is a one-piece P k − 1 polynomial on the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Engineering with Computers

Engineering with Computers Volume 38, Issue 5

Oct 2022

890 pages

ISSN:0177-0667

EISSN:1435-5663

Issue’s Table of Contents

© The Author(s), under exclusive licence to Springer-Verlag London Ltd., part of Springer Nature 2022.

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 01 October 2022

Accepted: 10 February 2022

Received: 11 October 2021

Author Tags

Qualifiers

Research-article

Funding Sources

Fondecyt
Anid doctoral scholarship

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 24 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Balreira Dda Silveira T(2024)Triangular matrix-based lossless compression algorithm for 3D mesh connectivityThe Visual Computer: International Journal of Computer Graphics10.1007/s00371-024-03400-840:6(3961-3970)Online publication date: 1-Jun-2024
https://dl.acm.org/doi/10.1007/s00371-024-03400-8

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents