“Harmonic triangulations” by Alexa

  • ©Marc Alexa




    Harmonic triangulations

Session/Category Title:   Meshing



    We introduce the notion of harmonic triangulations: a harmonic triangulation simultaneously minimizes the Dirichlet energy of all piecewise linear functions. By a famous result of Rippa, Delaunay triangulations are the harmonic triangulations of planar point sets. We prove by explicit counterexample that in 3D a harmonic triangulation does not exist in general. However, we show that bistellar flips are harmonic: if they decrease Dirichlet energy for one set of function values, they do so for all. This observation gives rise to the notion of locally harmonic triangulations. We demonstrate that locally harmonic triangulations can be efficiently computed, and efficiently reduce sliver tetrahedra. The notion of harmonic triangulation also gives rise to a scalar measure of the quality of a triangulation, which can be used to prioritize flips and optimize the position of vertices. Tetrahedral meshes generated by optimizing this function generally show better quality than Delaunay-based optimization techniques.


    1. Marc Alexa and Max Wardetzky. 2011. Discrete Laplacians on General Polygonal Meshes. ACM Trans. Graph. 30, 4, Article 102 (July 2011), 10 pages. Google ScholarDigital Library
    2. Aleksandr D Alexandrov. 2005. Convex polyhedra. Springer, Berlin, Heidelberg.Google Scholar
    3. Pierre Alliez, David Cohen-Steiner, Mariette Yvinec, and Mathieu Desbrun. 2005. Variational Tetrahedral Meshing. ACM Trans. Graph. 24, 3 (July 2005), 617–625. Google ScholarDigital Library
    4. Franz Aurenhammer. 1987. Power diagrams: properties, algorithms and applications. SIAM J. Comput. 16, 1 (1987), 78–96. Google ScholarDigital Library
    5. Ivo M. Babuška 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
    6. Randolph E. Bank and R. Kent Smith. 1997. Mesh Smoothing Using A Posteriori Error Estimates. SIAM J. Numer. Anal. 34, 3 (June 1997), 979–997. Google ScholarDigital Library
    7. Marshall Bern, Paul Chew, David Eppstein, and Jim Ruppert. 1995. Dihedral Bounds for Mesh Generation in High Dimensions. In Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA ’95). Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 189–196. Google ScholarDigital Library
    8. Alexander I. Bobenko and Boris A. Springborn. 2007. A discrete Laplace-Beltrami operator for simplicial surfaces. Discrete Comput. Geom. 38, 4 (2007), 740–756. Google ScholarDigital Library
    9. Arthur Cayley. 1869. A Memoir on Cubic Surfaces. Philosophical Transactions of the Royal Society of London 159 (1869), 231–326.Google ScholarCross Ref
    10. Long Chen. 2004. Mesh Smoothing Schemes Based on Optimal Delaunay Triangulations.. In Proceedings, 13th International Meshing Roundtable. Sandia National Laboratories, Williamburg, VA, USA, 109–120.Google Scholar
    11. Long Chen and Jinchao Xu. 2004. Optimal Delaunay Triangulations. Journal of Computational Mathematics 22, 2 (2004), 299–308.Google Scholar
    12. Renjie Chen, Yin Xu, Craig Gotsman, and Ligang Liu. 2010. A spectral characterization of the Delaunay triangulation. Computer Aided Geometric Design 27, 4 (2010), 295 — 300. Google ScholarDigital Library
    13. Zhonggui Chen, Wenping Wang, Bruno Lèvy, L.igang Liu, and Feng Sun. 2014. Revisiting Optimal Delaunay Triangulation for 3D Graded Mesh Generation. SIAM Journal on Scientific Computing 36, 3 (2014), A930–A954.Google ScholarCross Ref
    14. Siu-Wing Cheng, Tamal K. Dey, Herbert Edelsbrunner, Michael A. Facello, and Shang-Hua Teng. 2000. Sliver Exudation. J. ACM 47, 5 (Sept. 2000), 883–904. Google ScholarDigital Library
    15. Fernando de Goes, Pooran Memari, Patrick Mullen, and Mathieu Desbrun. 2014. Weighted Triangulations for Geometry Processing. ACM Trans. Graph. 33, 3 (2014), 28:1–28:13. Google ScholarDigital Library
    16. Jesus A. De Loera, Jorg Rambau, and Francisco Santos. 2010. Triangulations: Structures for Algorithms and Applications (1st ed.). Springer, Berlin, Heidelberg. Google ScholarCross Ref
    17. Richard J Duffin. 1959. Distributed and lumped networks. Journal of Mathematics and Mechanics 8, 5 (1959), 793–826.Google Scholar
    18. Gerhard Dziuk. 1988. Finite Elements for the Beltrami operator on arbitrary surfaces. In Partial Differential Equations and Calculus of Variations, Stefan Hildebrandt and Rolf Leis (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 142–155.Google Scholar
    19. Herbert Edelsbrunner and Nimish R. Shah. 1992. Incremental Topological Flipping Works for Regular Triangulations. In Proceedings of the Eighth Annual Symposium on Computational Geometry (SCG ’92). ACM, New York, NY, USA, 43–52. Google ScholarDigital Library
    20. Leman Feng, Pierre Alliez, Laurent Busé, Hervé Delingette, and Mathieu Desbrun. 2018. Curved Optimal Delaunay Triangulation. ACM Trans. Graph. 37, 4, Article 61 (July 2018), 16 pages. Google ScholarDigital Library
    21. Jean Gallier and Jocelyn Quaintance. 2017. Aspects of Convex Geometry Polyhedra, Linear Programming, Shellings, Voronoi Diagrams, Delaunay Triangulations. Book in progress, earlier version available as arXiv:0805.0292.Google Scholar
    22. Gaël Guennebaud, Benoît Jacob, et al. 2010. Eigen v3. http://eigen.tuxfamily.org.Google Scholar
    23. Yixin Hu, Qingnan Zhou, Xifeng Gao, Alec Jacobson, Denis Zorin, and Daniele Panozzo. 2018. Tetrahedral Meshing in the Wild. ACM Trans. Graph. 37, 4, Article 60 (July 2018), 14 pages. Google ScholarDigital Library
    24. Clément Jamin, Sylvain Pion, and Monique Teillaud. 2018. 3D Triangulations. In CGAL User and Reference Manual (4.13 ed.). CGAL Editorial Board. https://doc.cgal.org/4.13/Manual/packages.html#PkgTriangulation3SummaryGoogle Scholar
    25. Barry Joe. 1989. Three-Dimensional Triangulations from Local Transformations. SIAM J. Sci. Stat. Comput. 10, 4 (July 1989), 718–741.Google ScholarCross Ref
    26. Michal Křížek. 1992. On the Maximum Angle Condition for Linear Tetrahedral Elements. SIAM J. Numer. Anal. 29, 2 (April 1992), 513–520. Google ScholarDigital Library
    27. François Labelle and Jonathan Richard Shewchuk. 2007. Isosurface Stuffing: Fast Tetrahedral Meshes with Good Dihedral Angles. ACM Trans. Graph. 26, 3, Article 57 (July 2007), 10 pages. Google ScholarDigital Library
    28. Charles L. Lawson. 1972. Transforming triangulations. Discrete Mathematics 3, 4 (1972), 365 — 372. Google ScholarDigital Library
    29. Mark Meyer, Mathieu Desbrun, Peter Schröder, and Alan H. Barr. 2003. Discrete Differential-Geometry Operators for Triangulated 2-Manifolds. In Visualization and Mathematics III, Hans-Christian Hege and Konrad Polthier (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 35–57.Google Scholar
    30. Neil Molino, Robert Bridson, Joseph Teran, and Ronald Fedkiw. 2003. A crystalline, red green strategy for meshing highly deformable objects with tetrahedra. In Proceedings, 12th International Meshing Roundtable. Sandia National Laboratories, Santa Fe, NM, USA, 103–114.Google Scholar
    31. Oleg R. Musin. 1997. Properties of the Delaunay Triangulation. In Proceedings of the Thirteenth Annual Symposium on Computational Geometry (SCG ’97). ACM, New York, NY, USA, 424–426. Google ScholarDigital Library
    32. Ulrich Pinkall and Konrad Polthier. 1993. Computing discrete minimal surfaces and their conjugates. Experim. Math. 2 (1993), 15–36.Google ScholarCross Ref
    33. William H. Press, Saul A. Teukolsky, William T. Vetterling, and Brian P. Flannery. 1992. Numerical Recipes in C: The Art of Scientific Computing (second ed.). Cambridge University Press. Google ScholarDigital Library
    34. Samuel Rippa. 1990. Minimal Roughness Property of the Delaunay Triangulation. Comput. Aided Geom. Des. 7, 6 (Oct. 1990), 489–497. Google ScholarDigital Library
    35. Jonathan Shewchuk. 2002a. What is a good linear finite element? interpolation, conditioning, anisotropy, and quality measures (preprint). https://people.eecs.berkeley.edu/~jrs/papers/elemj.pdfGoogle Scholar
    36. Jonathan Richard Shewchuk. 2002b. Delaunay Refinement Algorithms for Triangular Mesh Generation. Comput. Geom. Theory Appl. 22, 1-3 (May 2002), 21–74. Google ScholarDigital Library
    37. R. Sibson. 1978. Locally equiangular triangulations. Comput. J. 21, 3 (1978), 243–245.Google ScholarCross Ref
    38. Jane Tournois, Camille Wormser, Pierre Alliez, and Mathieu Desbrun. 2009. Interleaving Delaunay Refinement and Optimization for Practical Isotropic Tetrahedron Mesh Generation. ACM Trans. Graph. 28, 3, Article 75 (July 2009), 9 pages. Google ScholarDigital Library
    39. Max Wardetzky, Saurabh Mathur, Felix Kälberer, and Eitan Grinspun. 2007. Discrete Laplace Operators: No Free Lunch. In Proceedings of the Fifth Eurographics Symposium on Geometry Processing (SGP ’07). Eurographics Association, Aire-la-Ville, Switzerland, Switzerland, 33–37. Google ScholarDigital Library
    40. Jinchao Xu and Ludmil Zikatanov. 1999. A Monotone Finite Element Scheme for Convection-diffusion Equations. Math. Comput. 68, 228 (Oct. 1999), 1429–1446. Google ScholarDigital Library

ACM Digital Library Publication:

Overview Page: