Fernando de Goes
Skip Abstract Section
Skip Supplemental Material SectionAbstract
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.
Supplemental Material
- R. Abraham, J. E. Marsden, and T. Ratiu. 1988. Manifolds, Tensor Analysis, and Applications 2nd Ed. Applied Mathematical Sciences, vol. 75. Springer. Google Scholar
Digital Library
- P. Alliez, D. Cohen-Steiner, M. Yvinec, and M. Desbrun. 2005. Variational tetrahedral meshing. ACM Trans. Graph. 24, 3, 617--625. Google ScholarDigital Library
- 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.Google Scholar
- F. Aurenhammer. 1987. Power diagrams: Properties, algorithms and applications. SIAM J. Comput. 16, 1, 78--96. Google ScholarDigital Library
- F. Aurenhammer, F. Hoffmann, and B. Aronov. 1998. Minkowski-type theorems and least-squares clustering. Algorithmica 20, 1, 61--76.Google ScholarCross Ref
- C. Batty, S. Xenos, and B. Houston. 2010. Tetrahedral embedded boundary methods for accurate and flexible adaptive fluids. Comput. Graph. Forum 29, 695--704.Google ScholarCross Ref
- A. Bobenko, U. Pinkall, and B. Springborn. 2010. Discrete conformal maps and ideal hyperbolic polyhedral. arXiv:1005.2698.Google Scholar
- A. I. Bobenko and B. A. Springborn. 2003. Variational principles for circle patterns and koebe's theorem. Trans. Amer. Math. Soc. 356, 659--689.Google ScholarCross Ref
- A. Bossavit. 1998. Computational Electromagnetism. Academic Press, Boston.Google Scholar
- A. Buffa, G. Sangalli, and R. Vazquez. 2010. Isogeometric analysis in electromagnetics: B-splines approximation. Comput. Methods Appl. Mech. Engin. 199, 1720, 1143--1152.Google Scholar
- B. Chow and F. Luo. 2003. Combinatorial ricci flows on surfaces. J. Diff. Geom. 63, 1, 97--129.Google ScholarCross Ref
- Y. Colin de Verdiere. 1991. Un principe variationnel pour les empilements de cercles. Inventiones Mathematicae 104, 655--669.Google ScholarCross Ref
- K. Crane, U. Pinkall, and P. Schroder. 2011. Spin transformations of discrete surfaces. ACM Trans. Graph. 30, 104:1--104:10. Google ScholarDigital Library
- T. A. Davis. 2011. Algorithm 915, suitesparseqr: Multifrontal multithreaded rank-revealing sparse qr factorization. ACM Trans. Math. Softw. 38, 8:1--8:22. Google ScholarDigital Library
- F. de Goes, P. Alliez, H. Owhadi, and M. Desbrun. 2013. On the equilibrium of simplicial masonry structures. ACM Trans. Graph. 32, 4. Google ScholarDigital Library
- F. de Goes, K. Breeden, V. Ostromoukhov, and M. Desbrun. 2012. Blue noise through optimal transport. ACM Trans. Graph. 31, 171:1--171:11. Google ScholarDigital Library
- 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.Google Scholar
- 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.Google Scholar
- M. Desbrun, M. Meyer, and P. Alliez. 2002. Intrinsic parameterizations of surface meshes. Comput. Graph. Forum 21, 2.Google ScholarCross Ref
- 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.Google Scholar
- Q. Du, V. Faber, and M. Gunzburger. 1999. Centroidal voronoi tessellations: Applications and algorithms. SIAM Rev. 41, 637--676. Google ScholarDigital Library
- R. Dyer and S. Schaefer. 2009. Circumcentric dual cells with negative area. Tech. rep., Simon Fraser University.Google Scholar
- S. Elcott, Y. Tong, E. Kanso, P. Schroder, and M. Desbrun. 2007. Stable, circulation-preserving, simplicial fluids. ACM Trans. Graph. 26, 1. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- D. Glickenstein. 2005. Geometric triangulations and discrete laplacians on manifolds. arXiv.org:math/0508188.Google Scholar
- D. Glickenstein. 2011. Discrete conformal variations and scalar curvature on piecewise flat two- and three-dimensional manifolds. J. Diff. Geom. 87, 201--238.Google ScholarCross Ref
- L. J. Grady and J. R. Polimeni. 2010. Discrete Calculus: Applied Analysis on Graphs. Springer. Google ScholarDigital Library
- R. Guo. 2009. Local rigidity of inversive distance circle packing. arXiv:0903.1401v2.Google Scholar
- K. Hildebrandt, K. Polthier, and M. Wardetzky. 2006. On the convergence of metric and geometric properties of polyhedral surfaces. Geometria Dedicata 123, 89--112.Google ScholarCross Ref
- A. N. Hirani, K. Kalyanaraman, and E. B. Vanderzee. 2013. Delaunay hodge star. Comput.-Aid. Des. 45, 2, 540--544. Google ScholarDigital Library
- M. Jin, J. Kim, F. Luo, and X. Gu. 2008. Discrete surface ricci flow. IEEE Trans. Vis. Comput. Graph. 14, 5, 1030--1043. Google ScholarDigital Library
- L. Kharevych, B. Springborn, and P. Schroder. 2006. Discrete conformal mappings via circle patterns. ACM Trans. Graph. 25, 2, 412--438. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- Y. Lipman, O. Sorkine, D. Levin, and D. Cohen-Or. 2005. Linear rotation-invariant coordinates for meshes. ACM Trans. Graph. 24, 3, 479--487. Google ScholarDigital Library
- Y. Liu, P. Hao, J. Snyder, W. Wang, and B. Guo. 2013. Computing self-supporting surfaces by regular triangulation. ACM Trans. Graph. 32, 4. Google ScholarDigital Library
- F. Luo. 2010. Rigidity of polyhedral surfaces iii. arXiv:1010.3284v1.Google Scholar
- R. Macneal. 1949. The solution of partial differential equations by means of electrical networks. Ph.D. thesis, Caltech.Google Scholar
- C. Mercat. 2001. Discrete riemann surfaces and the ising model. Comm. Math. Phys. 218, 177--216.Google ScholarCross Ref
- Q. Merigot. 2011. A multiscale approach to optimal transport. Comput. Graph. Forum 30, 5, 1583-1592.Google ScholarCross Ref
- 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.Google Scholar
- J. Milnor. 1982. Hyperbolic geometry: The first 150 years. Bull. Amer. Math. Soc. 6, 1, 9--24.Google ScholarCross Ref
- P. Mullen, P. Memari, F. de Goes, and M. Desbrun. 2011. HOT: Hodge-optimized triangulations. ACM Trans. Graph. 30, 103:1--103:12. Google ScholarDigital Library
- J. R. Munkres. 1984. Elements of Algebraic Topology. Addison-Wesley.Google Scholar
- J. Nocedal and S. J. Wright. 1999. Numerical Optimization. Springer.Google Scholar
- D. Panozzo, P. Block, and O. Sorkine-Hornung. 2013. Designing unreinforced masonry models. ACM Trans. Graph. 32, 4, 91:1--91:12. Google ScholarDigital Library
- D. Pedoe. 1988. Geometry: A Comprehensive Course 2nd Ed. Dover Publications.Google Scholar
- U. Pinkall and K. Polthier. 1993. Computing discrete minimal surfaces and their conjugates. Exper. Math. 2, 15--36.Google ScholarCross Ref
- K. Polthier and E. Preuss. 2003. Identifying vector field singularities using a discrete hodge decomposition. In Visualization and Mathematics III, Springer, 113--134.Google Scholar
- H. Pottmann, P. Grohs, and N. Mitra. 2009. Laguerre minimal surfaces, isotropic geometry and linear elasticity. Adv. Comput. Math. 31, 4, 391--419.Google ScholarCross Ref
- T. Regge. 1961. General relativity without coordinates. Nuovo Cim. 19, 3, 558--571.Google ScholarCross Ref
- I. Rivin. 1994. Euclidean structures on simplicial surfaces and hyperbolic volume. Ann. Math. 139, 3.Google ScholarCross Ref
- 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. Google ScholarDigital Library
- B. Springborn. 2008. A variational principle for weighted delaunay triangulations and hyperideal polyhedra. J. Diff. Geom. 78, 2.Google Scholar
- B. Springborn, P. Schroder, and U. Pinkall. 2008. Conformal equivalence of triangle meshes. ACM Trans. Graph. 27, 77:1--77:11. Google ScholarDigital Library
- K. Stephenson. 2003. Circle packing: A mathematical tale. Not. Amer. Math. Soc. 50, 11, 1376--1388.Google Scholar
- W. Thurston. 1976. Geometry and Topology of 3-Manifolds. Princeton University Press.Google Scholar
- Y. Tong, S. Lombeyda, A. N. Hirani, and M. Desbrun. 2003. Discrete multiscale vector field decomposition. ACM Trans. Graph. 22, 3, 445--452. Google ScholarDigital Library
- E. Vanderzee, A. N. Hirani, D. Guoy, and E. Ramos. 2010. Well-centered triangulation. SIAM J. Sci. Comput. 31, 6, 4497--4523. Google ScholarDigital Library
- E. Vouga, M. Hobinger, J. Wallner, and H. Pottmann. 2012. Design of self-supporting surfaces. ACM Trans. Graph. 31, 4, 87:1--87:11. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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.Google ScholarCross Ref
- W. Zeng, R. Guo, F. Luo, and X. Gu. 2012. Discrete heat kernel determines discrete riemannian metric. Graph. Models 74, 4, 121--129. Google ScholarDigital Library
Index Terms
- Weighted Triangulations for Geometry Processing
Recommendations
Conforming weighted delaunay triangulations
Given a set of points together with a set of simplices we show how to compute weights associated with the points such that the weighted Delaunay triangulation of the point set contains the simplices, if possible. For a given triangulated surface, this ...
Navigating intrinsic triangulations
We present a data structure that makes it easy to run a large class of algorithms from computational geometry and scientific computing on extremely poor-quality surface meshes. Rather than changing the geometry, as in traditional remeshing, we consider ...
Delaunay triangulations of polyhedral surfaces, a discrete Laplace-Beltrami operator and applications
SCG '08: Proceedings of the twenty-fourth annual symposium on Computational geometryA simplicial surface provides its carrier with a natural triangulation whose vertex set includes the cone points and the corners of the boundary. However, this triangulation is not intrinsically distinguished from other triangulations with the same ...
Comments