“Efficient and robust discrete conformal equivalence with boundary” by Campen, Capouellez, Shen, Zhu, Panozzo, et al. …
Conference:
Type(s):
Title:
- Efficient and robust discrete conformal equivalence with boundary
Session/Category Title: Surface Parameterization and Texturing
Presenter(s)/Author(s):
Abstract:
We describe an efficient algorithm to compute a discrete metric with prescribed Gaussian curvature at all interior vertices and prescribed geodesic curvature along the boundary of a mesh. The metric is (discretely) conformally equivalent to the input metric. Its construction is based on theory developed in [Gu et al. 2018b] and [Springborn 2020], relying on results on hyperbolic ideal Delaunay triangulations. Generality is achieved by considering the surface’s intrinsic triangulation as a degree of freedom, and particular attention is paid to the proper treatment of surface boundaries. While via a double cover approach the case with boundary can be reduced to the case without boundary quite naturally, the implied symmetry of the setting causes additional challenges related to stable Delaunay-critical configurations that we address explicitly. We furthermore explore the numerical limits of the approach and derive continuous maps from the discrete metrics.
References:
1. Julien Basch, Leonidas J Guibas, and John Hershberger. 1999. Data structures for mobile data. Journal of Algorithms 31, 1 (1999), 1–28.
2. Mirela Ben-Chen, Craig Gotsman, and Guy Bunin. 2008. Conformal Flattening by Curvature Prescription and Metric Scaling. Computer Graphics Forum 27, 2 (2008).
3. Alexander I Bobenko and Boris A Springborn. 2007. A discrete Laplace-Beltrami operator for simplicial surfaces. Discrete & Computational Geometry 38, 4 (2007), 740–756.
4. Marcel Campen, Hanxiao Shen, Jiaran Zhou, and Denis Zorin. 2019. Seamless Parametrization with Arbitrary Cones for Arbitrary Genus. ACM Trans. Graph. 39, 1 (2019).
5. Marcel Campen and Denis Zorin. 2017a. On Discrete Conformal Seamless Similarity Maps. arXiv:1705.02422 [cs.GR]
6. Marcel Campen and Denis Zorin. 2017b. Similarity Maps and Field-Guided T-Splines: a Perfect Couple. ACM Trans. Graph. 36, 4 (2017).
7. Keenan Crane. 2020. Discrete Conformal Geometry. In Proceedings of Symposia in Applied Mathematics. American Mathematical Society.
8. Mathieu Desbrun, Mark Meyer, and Pierre Alliez. 2002. Intrinsic parameterizations of surface meshes. Computer Graphics Forum 21, 3 (2002), 209–218.
9. Pablo Diaz-Gutierrez, David Eppstein, and Meenakshisundaram Gopi. 2009. Curvature aware fundamental cycles. Computer Graphics Forum 28, 7 (2009), 2015–2024.
10. Matthew Fisher, Boris Springborn, Peter Schröder, and Alexander I Bobenko. 2007. An algorithm for the construction of intrinsic Delaunay triangulations with applications to digital geometry processing. Computing 81, 2-3 (2007), 199–213.
11. Michael S. Floater. 1997. Parametrization and smooth approximation of surface triangulations. Computer Aided Geometric Design 14, 3 (1997), 231 — 250.
12. Mark Gillespie, Boris Springborn, and Keenan Crane. 2021. Discrete Conformal Equivalence of Polyhedral Surfaces. ACM Trans. Graph. 40, 4 (2021).
13. Xianfeng Gu, Ren Guo, Feng Luo, Jian Sun, and Tianqi Wu. 2018a. A discrete uni-formization theorem for polyhedral surfaces II. Journal of Differential Geometry 109, 3 (2018), 431–466.
14. Xianfeng Gu, Feng Luo, Jian Sun, and Tianqi Wu. 2018b. A discrete uniformization theorem for polyhedral surfaces. Journal of Differential Geometry 109, 2 (2018), 223–256.
15. Xianfeng Gu and Shing-Tung Yau. 2003. Global conformal surface parameterization. In Proc. Symp. Geometry Processing 2003. 127–137.
16. Miao Jin, Junho Kim, and Xianfeng David Gu. 2007. Discrete surface Ricci flow: Theory and applications. In IMA International Conference on Mathematics of Surfaces. Springer, 209–232.
17. Liliya Kharevych, Boris Springborn, and Peter Schröder. 2006. Discrete conformal mappings via circle patterns. ACM Trans. Graph. 25, 2 (2006), 412–438.
18. Bruno Lévy, Sylvain Petitjean, Nicolas Ray, and Jérome Maillot. 2002. Least squares conformal maps for automatic texture atlas generation. ACM Transactions on Graphics 21, 3 (2002), 362–371.
19. Feng Luo. 2004. Combinatorial Yamabe flow on surfaces. Communications in Contemporary Mathematics 6, 05 (2004), 765–780.
20. Ashish Myles, Nico Pietroni, and Denis Zorin. 2014. Robust Field-aligned Global Parametrization. ACM Trans. Graph. 33, 4 (2014), 135:1–135:14.
21. Ashish Myles and Denis Zorin. 2012. Global parametrization by incremental flattening. ACM Trans. Graph. 31, 4 (2012), 109.
22. Daniele Panozzo, Yaron Lipman, Enrico Puppo, and Denis Zorin. 2012. Fields on Symmetric Surfaces. ACM Trans. Graph. 31, 4 (2012).
23. Igor Rivin. 1994. Euclidean structures on simplicial surfaces and hyperbolic volume. Annals of mathematics 139, 3 (1994), 553–580.
24. Rohan Sawhney and Keenan Crane. 2017. Boundary First Flattening. ACM Trans. Graph. 37, 1 (2017).
25. Patrick Schmidt, Marcel Campen, Janis Born, and Leif Kobbelt. 2020. Inter-Surface Maps via Constant-Curvature Metrics. ACM Transactions on Graphics 39, 4 (2020).
26. Nicholas Sharp and Keenan Crane. 2020. A Laplacian for nonmanifold Triangle Meshes. Computer Graphics Forum 39, 5 (2020), 69–80.
27. Nicholas Sharp, Yousuf Soliman, and Keenan Crane. 2019. Navigating intrinsic triangulations. ACM Transactions on Graphics 38, 4 (2019), 1–16.
28. Yousuf Soliman, Dejan Slepčev, and Keenan Crane. 2018. Optimal cone singularities for conformal flattening. ACM Transactions on Graphics 37, 4 (2018), 1–17.
29. Boris Springborn. 2020. Ideal Hyperbolic Polyhedra and Discrete Uniformization. Discrete & Computational Geometry 64, 1 (2020), 63–108.
30. Boris Springborn, Peter Schröder, and Ulrich Pinkall. 2008. Conformal Equivalence of Triangle Meshes. ACM Transactions on Graphics 27, 3 (2008), 1–11.
31. Jian Sun, Tianqi Wu, Xianfeng Gu, and Feng Luo. 2015. Discrete conformal deformation: algorithm and experiments. SIAM Journal on Imaging Sciences 8, 3 (2015), 1421–1456.
32. Jeffrey R Weeks. 1993. Convex hulls and isometries of cusped hyperbolic 3-manifolds. Topology and its Applications 52, 2 (1993), 127–149.
33. Tianqi Wu. 2014. Finiteness of Switches in discrete Yamabe flow. Master’s thesis. Tsinghua University.
34. Denis Zorin. 2021. Convergence Analysis of the Algorithm in “Efficient and Robust Discrete Conformal Equivalence with Boundary”. arXiv:2109.03436 [math.NA]
