“Weighted Triangulations for Geometry Processing” by Goes, Memari, Mullen and Desbrun

  • ©Fernando de Goes, Pooran Memari, Patrick Mullen, and Mathieu Desbrun

Conference:


Type:


Title:

    Weighted Triangulations for Geometry Processing

Session/Category Title: Fields on Surfaces

Presenter(s)/Author(s):


Moderator(s):


Abstract:


    In this article we investigate the use of weighted triangulations as discrete, augmented approximations of surfaces for digital geometry processing. By incorporating a scalar weight per mesh vertex, we introduce a new notion of discrete metric that defines an orthogonal dual structure for arbitrary triangle meshes and thus extends weighted Delaunay triangulations to surface meshes. We also present alternative characterizations of this primal-dual structure (through combinations of angles, areas, and lengths) and, in the process, uncover closed-form expressions of mesh energies that were previously known in implicit form only. Finally, we demonstrate how weighted triangulations provide a faster and more robust approach to a series of geometry processing applications, including the generation of well-centered meshes, self-supporting surfaces, and sphere packing.

References:


    1. R. Abraham, J. E. Marsden, and T. Ratiu. 1988. Manifolds, Tensor Analysis, and Applications 2nd Ed. Applied Mathematical Sciences, vol. 75. Springer.
    2. P. Alliez, D. Cohen-Steiner, M. Yvinec, and M. Desbrun. 2005. Variational tetrahedral meshing. ACM Trans. Graph. 24, 3, 617–625.
    3. D. N. Arnold. 2013. Spaces of finite element differential forms. In Analysis and Numerics of Partial Differential Equations, U. Gianazza, F. Brezzi, P. Colli Franzone, and G. Gilardi, Eds., Springer, 117–140.
    4. F. Aurenhammer. 1987. Power diagrams: Properties, algorithms and applications. SIAM J. Comput. 16, 1, 78–96.
    5. F. Aurenhammer, F. Hoffmann, and B. Aronov. 1998. Minkowski-type theorems and least-squares clustering. Algorithmica 20, 1, 61–76.
    6. C. Batty, S. Xenos, and B. Houston. 2010. Tetrahedral embedded boundary methods for accurate and flexible adaptive fluids. Comput. Graph. Forum 29, 695–704.
    7. A. Bobenko, U. Pinkall, and B. Springborn. 2010. Discrete conformal maps and ideal hyperbolic polyhedral. arXiv:1005.2698.
    8. A. I. Bobenko and B. A. Springborn. 2003. Variational principles for circle patterns and koebe’s theorem. Trans. Amer. Math. Soc. 356, 659–689.
    9. A. Bossavit. 1998. Computational Electromagnetism. Academic Press, Boston.
    10. A. Buffa, G. Sangalli, and R. Vazquez. 2010. Isogeometric analysis in electromagnetics: B-splines approximation. Comput. Methods Appl. Mech. Engin. 199, 1720, 1143–1152.
    11. B. Chow and F. Luo. 2003. Combinatorial ricci flows on surfaces. J. Diff. Geom. 63, 1, 97–129.
    12. Y. Colin de Verdiere. 1991. Un principe variationnel pour les empilements de cercles. Inventiones Mathematicae 104, 655–669.
    13. K. Crane, U. Pinkall, and P. Schroder. 2011. Spin transformations of discrete surfaces. ACM Trans. Graph. 30, 104:1–104:10.
    14. T. A. Davis. 2011. Algorithm 915, suitesparseqr: Multifrontal multithreaded rank-revealing sparse qr factorization. ACM Trans. Math. Softw. 38, 8:1–8:22.
    15. F. de Goes, P. Alliez, H. Owhadi, and M. Desbrun. 2013. On the equilibrium of simplicial masonry structures. ACM Trans. Graph. 32, 4.
    16. F. de Goes, K. Breeden, V. Ostromoukhov, and M. Desbrun. 2012. Blue noise through optimal transport. ACM Trans. Graph. 31, 171:1–171:11.
    17. M. Desbrun, R. Donaldson, and H. Owhadi. 2013. Modeling across scales: Discrete geometric structures in homogenization and inverse homogenization. In Multiscale Analysis and Nonlinear Dynamics: From Genes to the Brain, M. Z. Pesenson, Ed. Reviews of Nonlinear Dynamics and Complexity, vol. 8, Wiley.
    18. M. Desbrun, E. Kanso, and Y. Tong. 2007. Discrete differential forms for computational modeling. In Discrete Differential Geometry, A. Bobenko and P. Schroder, Eds., Springer.
    19. M. Desbrun, M. Meyer, and P. Alliez. 2002. Intrinsic parameterizations of surface meshes. Comput. Graph. Forum 21, 2.
    20. N. Dimitrov. 2012. Positively weighted delaunay triangulations and their circle patterns as critical points of the hyperbolic volume differential. http://www.math.mcgill.ca/dimitrov/Circle_Patterns_as_Critical_Points.pdf.
    21. Q. Du, V. Faber, and M. Gunzburger. 1999. Centroidal voronoi tessellations: Applications and algorithms. SIAM Rev. 41, 637–676.
    22. R. Dyer and S. Schaefer. 2009. Circumcentric dual cells with negative area. Tech. rep., Simon Fraser University.
    23. S. Elcott, Y. Tong, E. Kanso, P. Schroder, and M. Desbrun. 2007. Stable, circulation-preserving, simplicial fluids. ACM Trans. Graph. 26, 1.
    24. M. Fisher, B. Springborn, P. Schroder, and A. I. Bobenko. 2007. An algorithm for the construction of intrinsic delaunay triangulations with applications to digital geometry processing. Comput. 81, 2–3, 199–213.
    25. D. Glickenstein. 2005. Geometric triangulations and discrete laplacians on manifolds. arXiv.org:math/0508188.
    26. D. Glickenstein. 2011. Discrete conformal variations and scalar curvature on piecewise flat two- and three-dimensional manifolds. J. Diff. Geom. 87, 201–238.
    27. L. J. Grady and J. R. Polimeni. 2010. Discrete Calculus: Applied Analysis on Graphs. Springer.
    28. R. Guo. 2009. Local rigidity of inversive distance circle packing. arXiv:0903.1401v2.
    29. K. Hildebrandt, K. Polthier, and M. Wardetzky. 2006. On the convergence of metric and geometric properties of polyhedral surfaces. Geometria Dedicata 123, 89–112.
    30. A. N. Hirani, K. Kalyanaraman, and E. B. Vanderzee. 2013. Delaunay hodge star. Comput.-Aid. Des. 45, 2, 540–544.
    31. M. Jin, J. Kim, F. Luo, and X. Gu. 2008. Discrete surface ricci flow. IEEE Trans. Vis. Comput. Graph. 14, 5, 1030–1043.
    32. L. Kharevych, B. Springborn, and P. Schroder. 2006. Discrete conformal mappings via circle patterns. ACM Trans. Graph. 25, 2, 412–438.
    33. B. Levy, S. Petitjean, N. Ray, and J. Maillot. 2002. Least squares conformal maps for automatic texture atlas generation. ACM Trans. Graph. 21, 3, 362–371.
    34. Y. Lipman, O. Sorkine, D. Levin, and D. Cohen-Or. 2005. Linear rotation-invariant coordinates for meshes. ACM Trans. Graph. 24, 3, 479–487.
    35. Y. Liu, P. Hao, J. Snyder, W. Wang, and B. Guo. 2013. Computing self-supporting surfaces by regular triangulation. ACM Trans. Graph. 32, 4.
    36. F. Luo. 2010. Rigidity of polyhedral surfaces iii. arXiv:1010.3284v1.
    37. R. Macneal. 1949. The solution of partial differential equations by means of electrical networks. Ph.D. thesis, Caltech.
    38. C. Mercat. 2001. Discrete riemann surfaces and the ising model. Comm. Math. Phys. 218, 177–216.
    39. Q. Merigot. 2011. A multiscale approach to optimal transport. Comput. Graph. Forum 30, 5, 1583-1592.
    40. M. Meyer, M. Desbrun, P. Schroder, and A. H. Barr. 2002. Discrete differential geometry operators for triangulated 2-manifolds. In Proceedings of the VisMath Conference. 35–57.
    41. J. Milnor. 1982. Hyperbolic geometry: The first 150 years. Bull. Amer. Math. Soc. 6, 1, 9–24.
    42. P. Mullen, P. Memari, F. de Goes, and M. Desbrun. 2011. HOT: Hodge-optimized triangulations. ACM Trans. Graph. 30, 103:1–103:12.
    43. J. R. Munkres. 1984. Elements of Algebraic Topology. Addison-Wesley.
    44. J. Nocedal and S. J. Wright. 1999. Numerical Optimization. Springer.
    45. D. Panozzo, P. Block, and O. Sorkine-Hornung. 2013. Designing unreinforced masonry models. ACM Trans. Graph. 32, 4, 91:1–91:12.
    46. D. Pedoe. 1988. Geometry: A Comprehensive Course 2nd Ed. Dover Publications.
    47. U. Pinkall and K. Polthier. 1993. Computing discrete minimal surfaces and their conjugates. Exper. Math. 2, 15–36.
    48. K. Polthier and E. Preuss. 2003. Identifying vector field singularities using a discrete hodge decomposition. In Visualization and Mathematics III, Springer, 113–134.
    49. H. Pottmann, P. Grohs, and N. Mitra. 2009. Laguerre minimal surfaces, isotropic geometry and linear elasticity. Adv. Comput. Math. 31, 4, 391–419.
    50. T. Regge. 1961. General relativity without coordinates. Nuovo Cim. 19, 3, 558–571.
    51. I. Rivin. 1994. Euclidean structures on simplicial surfaces and hyperbolic volume. Ann. Math. 139, 3.
    52. A. Schiftner, M. Hobinger, J. Wallner, and H. Pottmann. 2009. Packing circles and spheres on surfaces. ACM Trans. Graph. 28, 5, 139:1–139:8.
    53. B. Springborn. 2008. A variational principle for weighted delaunay triangulations and hyperideal polyhedra. J. Diff. Geom. 78, 2.
    54. B. Springborn, P. Schroder, and U. Pinkall. 2008. Conformal equivalence of triangle meshes. ACM Trans. Graph. 27, 77:1–77:11.
    55. K. Stephenson. 2003. Circle packing: A mathematical tale. Not. Amer. Math. Soc. 50, 11, 1376–1388.
    56. W. Thurston. 1976. Geometry and Topology of 3-Manifolds. Princeton University Press.
    57. Y. Tong, S. Lombeyda, A. N. Hirani, and M. Desbrun. 2003. Discrete multiscale vector field decomposition. ACM Trans. Graph. 22, 3, 445–452.
    58. E. Vanderzee, A. N. Hirani, D. Guoy, and E. Ramos. 2010. Well-centered triangulation. SIAM J. Sci. Comput. 31, 6, 4497–4523.
    59. E. Vouga, M. Hobinger, J. Wallner, and H. Pottmann. 2012. Design of self-supporting surfaces. ACM Trans. Graph. 31, 4, 87:1–87:11.
    60. A. Wachter and L. T. Biegler. 2006. On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming. Math. Program. 106, 1, 25–57.
    61. Y. Wang, B. Liu, and Y. Tong. 2012. Linear surface reconstruction from discrete fundamental forms on triangle meshes. Comput. Graph. Forum 31, 8, 2277–2287.
    62. M. Wardetzky, S. Mathur, F. Kalberer, and E. Grinspun. 2007. Discrete laplace operators: No free lunch. In Proceedings of the Symposium on Geometry Processesing. 33–37.
    63. Y.-L. Yang, R. Guo, F. Luo, S.-M. Hu, and X. Gu. 2009. Generalized discrete ricci flow. Comput. Graph. Forum 28, 7, 2005–2014.
    64. W. Zeng, R. Guo, F. Luo, and X. Gu. 2012. Discrete heat kernel determines discrete riemannian metric. Graph. Models 74, 4, 121–129.

ACM Digital Library Publication:


Overview Page: