“HOT: Hodge-optimized triangulations” by Mullen, Memari, Goes and Desbrun

We introduce Hodge-optimized triangulations (HOT), a family of well-shaped primal-dual pairs of complexes designed for fast and accurate computations in computer graphics. Previous work most commonly employs barycentric or circumcentric duals; while barycentric duals guarantee that the dual of each simplex lies within the simplex, circumcentric duals are often preferred due to the induced orthogonality between primal and dual complexes. We instead promote the use of weighted duals (“power diagrams”). They allow greater flexibility in the location of dual vertices while keeping primal-dual orthogonality, thus providing a valuable extension to the usual choices of dual by only adding one additional scalar per primal vertex. Furthermore, we introduce a family of functionals on pairs of complexes that we derive from bounds on the errors induced by diagonal Hodge stars, commonly used in discrete computations. The minimizers of these functionals, called HOT meshes, are shown to be generalizations of Centroidal Voronoi Tesselations and Optimal Delaunay Triangulations, and to provide increased accuracy and flexibility for a variety of computational purposes.

1. Alliez, P., Cohen-Steiner, D., Yvinec, M., and Desbrun, M. 2005. Variational tetrahedral meshing. ACM Trans. on Graphics (SIGGRAPH) 24, 3 (July), 617–625. Google ScholarDigital Library
2. Auchmann, B., and Kurz, S. 2006. A geometrically defined discrete Hodge operator on simplicial cells. IEEE Trans. Magn. 42, 4, 643–646.Google ScholarCross Ref
3. Batty, C., Xenos, S., and Houston, B. 2010. Tetrahedral embedded boundary methods for accurate and flexible adaptive fluids. Computer Graphics Forum (Eurographics) 29 (May), 695–704(10).Google ScholarCross Ref
4. Bossavit, A. 1998. Computational Electromagnetism. Academic Press, Boston.Google Scholar
5. CGAL, 2010. Computational Geometry Algorithms Library (release 3.8). http://www.cgal.org.Google Scholar
6. Cheng, S.-W., Dey, T. K., and Levine, J. 2008. Theory of a practical Delaunay meshing algorithm for a large class of domains. In Algorithms, Architecture and Information Systems Security, B. Bhattacharya, S. Sur-Kolay, S. Nandy, and A. Bagchi, Eds., vol. 3 of World Scientific Review, 17–41.Google Scholar
7. Desbrun, M., Kanso, E., and Tong, Y. 2007. Discrete differential forms for computational modeling. In Discrete Differential Geometry, A. Bobenko and P. Schröder, Eds. Springer.Google Scholar
8. Du, Q., Faber, V., and Gunzburger, M. 1999. Centroidal voronoi tessellations: Applications and algorithms. SIAM Rev. 41 (December), 637–676. Google ScholarDigital Library
9. Edelsbrunner, H. 1987. Algorithms in Combinatorial Geometry. Springer-Verlag. Google Scholar
10. Elcott, S., Tong, Y., Kanso, E., Schröder, P., and Desbrun, M. 2007. Stable, circulation-preserving, simplicial fluids. ACM Trans. on Graphics 26, 1 (jan), 4. Google ScholarDigital Library
11. Fisher, M., Springborn, B., Bobenko, A. I., and Schröder, P. 2006. An algorithm for the construction of intrinsic delaunay triangulations with applications to digital geometry processing. In ACM SIGGRAPH Courses, 69–74. Google Scholar
12. Glickenstein, D. 2005. Geometric triangulations and discrete Laplacians on manifolds. Arxiv preprint math/0508188.Google Scholar
13. Grady, L. J., and Polimeni, J. R. 2010. Discrete Calculus: Applied Analysis on Graphs for Computational Science. Springer. Google ScholarCross Ref
14. Hauret, P., Kuhl, E., and Ortiz, M. 2007. Diamond Elements: a finite element/discrete-mechanics approximation scheme with guaranteed optimal convergence in incompressible elasticity. Int. J. Numer. Meth. Engng. 72, 3, 253–294.Google ScholarCross Ref
15. Hirani, A. N. 2003. Discrete Exterior Calculus. PhD thesis, Caltech. Google Scholar
16. Lévy, B., and Liu, Y. 2010. L
p Centroidal Voronoi Tesselation and its Applications. ACM Trans. on Graph. 29, 4. Google ScholarDigital Library
17. Lipman, Y., and Daubechies, I. 2010. Surface Comparison With Mass Transportation. In ArXiv preprint 0912.3488.Google Scholar
18. Liu, Y., Wang, W., Lévy, B., Sun, F., Yan, D., Lu, L., and Yang, C. 2009. On Centroidal Voronoi Tessellation – energy smoothness and fast computation. ACM Trans. on Graph. 28, 4. Google ScholarDigital Library
19. Mémoli, F. 2011. A spectral notion of Gromov-Wasserstein distances and related methods. Journal of Applied and Computational Harmonic Analysis 30, 3, 363–401.Google ScholarCross Ref
20. Meyer, M., Desbrun, M., Schröder, P., and Barr, A. H. 2003. Discrete differential-geometry operators for triangulated 2-manifolds. In Visualization and Mathematics III, Springer-Verlag, H.-C. Hege and K. Polthier, Eds., 35–57.Google Scholar
21. Munkres, J. R. 1984. Elements of Algebraic Topology. Addison-Wesley.Google Scholar
22. Nocedal, J., and Wright, S. J. 1999. Numerical optimization. Springer Verlag.Google Scholar
23. Okabe, A., Boots, B., Sugihara, K., and Chiu, S. N. 2000. Spatial tessellations: Concepts and applications of Voronoi diagrams, 2nd ed. Probability and Statistics. Wiley. Google Scholar
24. Pedoe, D. 1988. Geometry, a comprehensive course, 2nd ed. Dover Publications.Google Scholar
25. Perot, J. B., and Subramanian, V. 2007. Discrete calculus methods for diffusion. Journal of Computational Physics 224, 59–81. Google ScholarDigital Library
26. Pinkall, U., and Polthier, K. 1993. Computing discrete minimal surfaces and their conjugates. Experimental Mathematics 2(1), 15–36.Google ScholarCross Ref
27. Rajan, V. 1994. Optimality of the Delaunay triangulation in Rd. Discrete and Computational Geometry 12, 1, 189–202.Google ScholarDigital Library
28. Shewchuk, J. 2002. What is a Good Linear Element? Interpolation, Conditioning, and Quality Measures. In Proc. of the 11th Int. Meshing Roundtable, 115–126.Google Scholar
29. Sieger, D., Alliez, P., and Botsch, M. 2010. Optimizing voronoi diagrams for polygonal finite element computations. In Proceedings of the 19th International Meshing Roundtable. 335–350.Google Scholar
30. Tournois, J., Wormser, C., Alliez, P., and Desbrun, M. 2009. Interleaving delaunay refinement and optimization for practical isotropic tetrahedron mesh generation. ACM Trans. Graph. 28 (July), 75:1–75:9. Google ScholarDigital Library
31. VanderZee, E., Hirani, A. N., Guoy, D., and Ramos, E. 2010. Well-centered triangulation. SIAM Journal on Scientific Computing 31, 6, 4497–4523. Google ScholarDigital Library
32. Villani, C. 2009. Optimal Transport: Old and New. Fundamental Principles of Mathematical Sciences, 338. Springer-Verlag.Google ScholarCross Ref
33. Wardetzky, M., Mathur, S., Kälberer, F., and Grinspun, E. 2007. Discrete laplace operators: no free lunch. In Symposium on Geometry processing, 33–37. Google ScholarDigital Library
34. Warren, J., Schaefer, S., Hirani, A., and Desbrun, M. 2007. Barycentric coordinates for convex sets. Advances in Computational Mathematics 27, 3, 319–338.Google ScholarCross Ref
35. Wilson, S. O. 2007. Cochain algebra on manifolds and convergence under refinement. Topology and its Applications 154, 9, 1898–1920.Google Scholar