“Guaranteed-quality higher-order triangular meshing of 2D domains” by Mandad and Campen

We present a guaranteed quality mesh generation algorithm for the curvilinear triangulation of planar domains with piecewise polynomial boundary. The resulting mesh consists of higher-order triangular elements which are not only regular (i.e., with injective geometric map) but respect strict bounds on quality measures like scaled Jacobian and MIPS distortion. This also implies that the curved triangles’ inner angles are bounded from above and below. These are key quality criteria, for instance, in the field of finite element analysis. The domain boundary is reproduced exactly, without geometric approximation error. The central idea is to transform the curvilinear meshing problem into a linear meshing problem via a carefully constructed transformation of bounded distortion, enabling us to leverage key results on guaranteed-quality straight-edge triangulation. The transformation is based on a simple yet general construction and observations about convergence properties of curves under subdivision. Our algorithm can handle arbitrary polynomial order, arbitrarily sharp corners, feature and interface curves, and can be executed using rational arithmetic for strict reliability.

1. Remi Abgrall, Cécile Dobrzynski, and Algiane Froehly. 2014. A method for computing curved meshes via the linear elasticity analogy, application to fluid dynamics problems. International Journal for Numerical Methods in Fluids 76, 4 (2014), 246–266.Google ScholarCross Ref
2. I. Babuska and A. K. Aziz. 1976. On the Angle Condition in the Finite Element Method. SIAM J. Numer. Anal. 13, 2 (1976), 214–226.Google ScholarDigital Library
3. Marshall Bern, David Eppstein, and John Gilbert. 1994. Provably good mesh generation. J. Comput. System Sci. 48, 3 (1994), 384–409.Google ScholarDigital Library
4. Jean-Daniel Boissonnat, Olivier Devillers, Monique Teillaud, and Mariette Yvinec. 2000. Triangulations in CGAL. In Proc. 16th Symp. on Computational Geometry. 11–18.Google Scholar
5. Charles Boivin and Carl Ollivier-Gooch. 2002. Guaranteed-quality triangular mesh generation for domains with curved boundaries. Int. J. Numer. Methods Eng. 55, 10 (2002), 1185–1213.Google ScholarCross Ref
6. Jan Brandts, Antti Hannukainen, Sergey Korotov, and Michal Křîžek. 2011. On angle conditions in the finite element nethod. SeMA Journal 56 (09 2011), 81–95.Google Scholar
7. Siu-Wing Cheng, Tamal K Dey, and Jonathan Shewchuk. 2012. Delaunay mesh generation. CRC Press.Google ScholarDigital Library
8. L. Paul Chew. 1989. Guaranteed-Quality Triangular Meshes. Tech. Rep. Department of Computer Science, Cornell University.Google Scholar
9. L. Paul Chew. 1993. Guaranteed-Quality Mesh Generation for Curved Surfaces. In Proc. 9th Symp. on Computational Geometry. 274–280.Google ScholarDigital Library
10. P.G. Ciarlet and P.-A. Raviart. 1972a. The Combined Effect of Curved Boundaries and Numerical Integration in Isoparametric Finite Element Methods. In The Mathematical Foundations of the Finite Element Method with Applications to Partial Differential Equations, A.K. Aziz (Ed.). Academic Press, 409 — 474.Google Scholar
11. P.G. Ciarlet and P.-A. Raviart. 1972b. Interpolation theory over curved elements, with applications to finite element methods. Comput. Methods Appl. Mech. Eng. 1, 2 (1972).Google Scholar
12. Y. Colin de Verdière and A. Marin. 1990. Triangulations presque équilatérales des surfaces. J. Differential Geom. 32, 1 (1990), 199–207.Google Scholar
13. Mark de Berg, Marc van Kreveld, Mark Overmars, and Otfried Cheong Schwarzkopf. 2000. Polygon Triangulation. Springer Berlin Heidelberg, Berlin, Heidelberg, 45–61.Google Scholar
14. Saikat Dey, Robert M. O’Bara, and Mark S. Shephard. 1999. Curvilinear Mesh Generation In 3D. In Proc. International Meshing Roundtable. John Wiley & Sons, 407–417.Google Scholar
15. Luke Engvall and John A. Evans. 2020. Mesh quality metrics for isogeometric Bernstein-Bézier discretizations. Comput. Methods Appl. Mech. Eng. 371 (2020).Google Scholar
16. Hale Erten and Alper Üngör. 2009. Quality Triangulations with Locally Optimal Steiner Points. SIAM Journal on Scientific Computing 31, 3 (2009), 2103–2130.Google ScholarDigital Library
17. Gerald Farin. 1986. Triangular Bernstein-Bézier patches. Computer Aided Geometric Design 3, 2 (1986), 83–127.Google ScholarDigital Library
18. Leman Feng, Pierre Alliez, Laurent Busé, Hervé Delingette, and Mathieu Desbrun. 2018. Curved Optimal Delaunay Triangulation. ACM Trans. Graph. 37, 4 (2018).Google ScholarDigital Library
19. A. Fournier and D. Y. Montuno. 1984. Triangulating Simple Polygons and Equivalent Problems. ACM Trans. Graph. 3, 2 (April 1984), 153–174.Google ScholarDigital Library
20. Isaac Fried. 1972. Condition of finite element matrices generated from nonuniform meshes. Aiaa Journal 10, 2 (1972), 219–221.Google ScholarCross Ref
21. P.L. George and H. Borouchaki. 2012. Construction of tetrahedral meshes of degree two. Int. J. Numer. Methods Eng. 90, 9 (2012), 1156–1182.Google ScholarCross Ref
22. William J. Gordon and Charles A. Hall. 1973. Transfinite element methods: Blending-function interpolation over arbitrary curved element domains. Numer. Math. 21, 2 (1973), 109–129.Google ScholarDigital Library
23. Serge Gosselin and Carl Ollivier-Gooch. 2007. Revisiting Delaunay Refinement Triangular Mesh Generation on Curve-bounded Domains. Technical Report. U British Columbia.Google Scholar
24. Jens Gravesen, Anton Evgrafov, Dang-Manh Nguyen, and Peter Nørtoft. 2014. Planar Parametrization in Isogeometric Analysis. In Mathematical Methods for Curves and Surfaces. Springer Berlin Heidelberg, 189–212.Google Scholar
25. Robert Haber, Mark S. Shephard, John F. Abel, Richard H. Gallagher, and Donald P. Greenberg. 1981. A general two-dimensional, graphical finite element preprocessor utilizing discrete transfinite mappings. Int. J. Numer. Methods Eng. 17, 7 (1981).Google ScholarCross Ref
26. Victoria Hernandez-Mederos, Jorge Estrada-Sarlabous, and Dionne León Madrigal. 2006. On local injectivity of 2D triangular cubic Bezier functions. Investigación Operacional 27, 3 (2006), 261–275.Google Scholar
27. Kai Hormann and Günther Greiner. 2000. MIPS: An efficient global parametrization method. Curve and Surface Design ’99 (2000), 153–162.Google Scholar
28. Yixin Hu, Teseo Schneider, Xifeng Gao, Qingnan Zhou, Alec Jacobson, Denis Zorin, and Daniele Panozzo. 2019. TriWild: Robust Triangulation with Curve Constraints. ACM Trans. Graph. 38, 4 (2019).Google ScholarDigital Library
29. A. Johnen, C. Geuzaine, T. Toulorge, and J.-F. Remacle. 2016. Efficient Computation of the Minimum of Shape Quality Measures on Curvilinear Finite Elements. Procedia Engineering 163 (2016), 328 — 339.Google ScholarCross Ref
30. Patrick M. Knupp. 2000. Achieving finite element mesh quality via optimization of the Jacobian matrix norm and associated quantities. Part I—a framework for surface mesh optimization. Internat. J. Numer. Methods Engrg. 48, 3 (2000), 401–420.Google ScholarCross Ref
31. Richard Leroy. 2008. Certificates of positivity and polynomial minimization in the multivariate Bernstein basis. Ph.D. Dissertation. University of Rennes 1.Google Scholar
32. J. Li, T. J. Peters, and J. A. Roulier. 2012. Angular Convergence during Bézier Curve Approximation. arXiv:1210.2686 [math.GT]Google Scholar
33. Manish Mandad and Marcel Campen. 2020a. Bézier Guarding: Precise Higher-Order Meshing of Curved 2D Domains. ACM Trans. Graph. 39, 4, Article 103 (2020).Google ScholarDigital Library
34. Manish Mandad and Marcel Campen. 2020b. Efficient piecewise higher-order parametrization of discrete surfaces with local and global injectivity. Computer-Aided Design 127 (2020).Google Scholar
35. Gary L. Miller, Steven E. Pav, and Noel J. Walkington. 2003. When and Why Ruppert’s Algorithm Works. In Proc. 12th International Meshing Roundtable. 91–102.Google Scholar
36. Géraldine Morin and Ron Goldman. 2001. On the smooth convergence of subdivision and degree elevation for Bézier curves. Comput. Aided Geom. Des. 18, 7 (2001).Google Scholar
37. D. Moxey, D. Ekelschot, Ü. Keskin, S.J. Sherwin, and J. Peiró. 2016. High-order Curvilinear Meshing Using a Thermo-elastic Analogy. Comput. Aided Des. 72, C (2016).Google Scholar
38. Peter Oswald. 2015. Divergence of FEM: Babuška-Aziz triangulations revisited. Applications of Mathematics 60, 5 (2015), 473–484. http://eudml.org/doc/271633Google ScholarCross Ref
39. Steven J Owen. 1998. A survey of unstructured mesh generation technology. IMR 239 (1998), 267.Google Scholar
40. Steven Elliot Pav. 2003. Delaunay Refinement Algorithms. Ph.D. Dissertation. Carnegie Mellon University.Google Scholar
41. Steven E. Pav and Noel J. Walkington. 2005. Delaunay Refinement by Corner Lopping. In Proceedings of the 14th International Meshing Roundtable, Byron W. Hanks (Ed.). Springer Berlin Heidelberg, Berlin, Heidelberg, 165–181.Google Scholar
42. Ulrich Pinkall and Konrad Polthier. 1993. Computing discrete minimal surfaces and their conjugates. Experimental mathematics 2, 1 (1993), 15–36.Google Scholar
43. Hartmut Prautzsch, Wolfgang Boehm, and Marco Paluszny. 2013. Bézier and B-spline techniques. Springer Science & Business Media.Google Scholar
44. Alexander Rand. 2011a. Improved Examples of Non-Termination for Ruppert’s Algorithm. arXiv:1103.3903 [cs.CG]Google Scholar
45. Alexander Rand. 2011b. Where and How Chew’s Second Delaunay Refinement Algorithm Works. In Proc. 23rd Canadian Conference on Computational Geometry.Google Scholar
46. Ramsharan Rangarajan and Adrián J. Lew. 2014. Universal meshes: A method for triangulating planar curved domains immersed in nonconforming meshes. Int. J. Numer. Methods Eng. 98, 4 (2014), 236–264.Google ScholarCross Ref
47. J. Ruppert. 1995. A Delaunay Refinement Algorithm for Quality 2-Dimensional Mesh Generation. Journal of Algorithms 18, 3 (1995), 548 — 585.Google ScholarDigital Library
48. Teseo Schneider, Yixin Hu, Jérémie Dumas, Xifeng Gao, Daniele Panozzo, and Denis Zorin. 2018. Decoupling Simulation Accuracy from Mesh Quality. ACM Trans. Graph. 37, 6 (2018).Google ScholarDigital Library
49. Jonathan R. Shewchuk. 2002a. Delaunay refinement algorithms for triangular mesh generation. Computational Geometry 22, 1 (2002), 21 — 74. 16th ACM Symp. Comput. Geom.Google ScholarDigital Library
50. Jonathan Richard Shewchuk. 2002b. What is a good linear element? Interpolation, Conditioning, and Quality Measures. In Proc. 11th Int. Meshing Roundtable. 115–126.Google Scholar
51. Thomas Toulorge, Christophe Geuzaine, Jean-François Remacle, and Jonathan Lambrechts. 2013. Robust untangling of curvilinear meshes. J. Comput. Phys. 254 (2013).Google Scholar
52. Godfried T Toussaint. 1984. A new linear algorithm for triangulating monotone polygons. Pattern Recognition Letters 2, 3 (1984), 155–158.Google ScholarDigital Library
53. Michael Turner, Joaquim Peiró, and David Moxey. 2018. Curvilinear mesh generation using a variational framework. Computer-Aided Design 103 (2018), 73–91.Google ScholarDigital Library
54. S.A. Vavasis. 1996. Stable finite elements for problems with wild coefficients. SIAM J. Numer. Anal. 33 (1996), 890–916.Google ScholarDigital Library
55. Z.J. Wang, Krzysztof Fidkowski, Rémi Abgrall, Francesco Bassi, Doru Caraeni, Andrew Cary, Herman Deconinck, Ralf Hartmann, Koen Hillewaert, H.T. Huynh, Norbert Kroll, Georg May, Per-Olof Persson, Bram van Leer, and Miguel Visbal. 2013. High-order CFD methods: current status and perspective. International Journal for Numerical Methods in Fluids 72, 8 (2013), 811–845.Google Scholar