Seamless Parametrization in Penner Coordinates
Article No.: 61, Pages 1 - 13
Abstract
We introduce a conceptually simple and efficient algorithm for seamless parametrization, a key element in constructing quad layouts and texture charts on surfaces. More specifically, we consider the construction of parametrizations with prescribed holonomy signatures i.e., a set of angles at singularities, and rotations along homology loops, preserving which is essential for constructing parametrizations following an input field, as well as for user control of the parametrization structure. Our algorithm performs exceptionally well on a large dataset based on Thingi10k [Zhou and Jacobson 2016], (16156 meshes) as well as on a challenging smaller dataset of [Myles et al. 2014], converging, on average, in 9 iterations. Although the algorithm lacks a formal mathematical guarantee, presented empirical evidence and the connections between convex optimization and closely related algorithms, suggest that a similar formulation can be found for this algorithm in the future.
References
[1]
Mirela Ben-Chen, Craig Gotsman, and Guy Bunin. 2008. Conformal Flattening by Curvature Prescription and Metric Scaling. Computer Graphics Forum 27, 2 (2008).
[2]
David Bommes, Marcel Campen, Hans-Christian Ebke, Pierre Alliez, and Leif Kobbelt. 2013. Integer-Grid Maps for Reliable Quad Meshing. ACM Trans. Graph. 32, 4 (2013), 98:1--98:12.
[3]
David Bommes, Henrik Zimmer, and Leif Kobbelt. 2009. Mixed-integer quadrangulation. ACM Trans. Graph. 28, 3 (2009), 77.
[4]
Alon Bright, Edward Chien, and Ofir Weber. 2017. Harmonic Global Parametrization with Rational Holonomy. ACM Trans. Graph. 36, 4 (2017).
[5]
Marcel Campen, David Bommes, and Leif Kobbelt. 2015. Quantized global parametrization. ACM Trans. Graph. 34, 6 (2015), 192.
[6]
Marcel Campen, Ryan Capouellez, Hanxiao Shen, Leyi Zhu, Daniele Panozzo, and Denis Zorin. 2021. Efficient and Robust Discrete Conformal Equivalence with Boundary. ACM Trans. Graph. 40, 6, Article 261 (dec 2021), 16 pages.
[7]
Marcel Campen, Hanxiao Shen, Jiaran Zhou, and Denis Zorin. 2019. Seamless Parametrization with Arbitrary Cones for Arbitrary Genus. ACM Trans. Graph. 39, 1 (2019).
[8]
Marcel Campen and Denis Zorin. 2017a. On Discrete Conformal Seamless Similarity Maps. arXiv:1705.02422 [cs.GR]
[9]
Marcel Campen and Denis Zorin. 2017b. Similarity Maps and Field-Guided T-Splines: a Perfect Couple. ACM Trans. Graph. 36, 4 (2017).
[10]
Ryan Capouellez and Denis Zorin. 2023. Metric Optimization in Penner Coordinates. ACM Trans. Graph. 42, 6, Article 234 (dec 2023), 19 pages.
[11]
Keenan Crane, Mathieu Desbrun, and Peter Schröder. 2010. Trivial Connections on Discrete Surfaces. Computer Graphics Forum 29, 5 (2010), 1525--1533.
[12]
Nahum Farchi and Mirela Ben-Chen. 2018. Integer-only cross field computation. ACM Trans. Graph. 37, 4, Article 91 (jul 2018), 13 pages.
[13]
Xiao-Ming Fu, Jian-Ping Su, Zheng-Yu Zhao, Qing Fang, Chunyang Ye, and Ligang Liu. 2021. Inversion-free geometric mapping construction: A survey. Computational Visual Media 7, 3 (2021), 289--318.
[14]
Mark Gillespie, Boris Springborn, and Keenan Crane. 2021. Discrete Conformal Equivalence of Polyhedral Surfaces. ACM Trans. Graph. 40, 4, Article 103 (jul 2021), 20 pages.
[15]
Xianfeng Gu, Ren Guo, Feng Luo, Jian Sun, and Tianqi Wu. 2018a. A discrete uniformization theorem for polyhedral surfaces II. Journal of Differential Geometry 109, 3 (2018), 431--466.
[16]
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.
[17]
Eden Fedida Hefetz, Edward Chien, and Ofir Weber. 2019. A Subspace Method for Fast Locally Injective Harmonic Mapping. Computer Graphics Forum 38, 2 (2019), 105--119.
[18]
Yixin Hu, Qingnan Zhou, Xifeng Gao, Alec Jacobson, Denis Zorin, and Daniele Panozzo. 2018. Tetrahedral meshing in the wild. ACM Trans. Graph. 37, 4 (2018), 60--1.
[19]
Ivan Izmestiev, Robert B Kusner, Günter Rote, Boris Springborn, and John M Sullivan. 2013. There is no triangulation of the torus with vertex degrees 5, 6,..., 6, 7 and related results: Geometric proofs for combinatorial theorems. Geometriae Dedicata 166 (2013), 15--29.
[20]
Ernest Jucovič and Marián Trenkler. 1973. A theorem on the structure of cell-decompositions of orientable 2--manifolds. Mathematika 20, 01 (1973), 63--82.
[21]
F. Kälberer, M. Nieser, and K. Polthier. 2007. QuadCover: Surface Parameterization using Branched Coverings. Computer Graphics Forum 26, 3 (2007), 375--384.
[22]
Liliya Kharevych, Boris Springborn, and Peter Schröder. 2006. Discrete conformal mappings via circle patterns. ACM Trans. Graph. 25, 2 (2006), 412--438.
[23]
Zohar Levi. 2023. Seamless Parametrization with Cone and Partial Loop Control. ACM Transactions on Graphics (2023).
[24]
W. Li, B. Vallet, N. Ray, and B. Levy. 2006. Representing Higher-Order Singularities in Vector Fields on Piecewise Linear Surfaces. IEEE Transactions on Visualization and Computer Graphics 12, 5 (2006), 1315--1322.
[25]
Yaron Lipman. 2012. Bounded Distortion Mapping Spaces for Triangular Meshes. ACM Trans. Graph. 31, 4 (2012), 108:1--108:13.
[26]
Ligang Liu, Chunyang Ye, Ruiqi Ni, and Xiao-Ming Fu. 2018. Progressive parameterizations. ACM Transactions on Graphics (TOG) 37, 4 (2018), 1--12.
[27]
Max Lyon, Marcel Campen, and Leif Kobbelt. 2021. Quad layouts via constrained t-mesh quantization. In Computer Graphics Forum, Vol. 40. Wiley Online Library, 305--314.
[28]
Ashish Myles, Nico Pietroni, and Denis Zorin. 2014. Robust Field-aligned Global Parametrization. ACM Trans. Graph. 33, 4 (2014), 135:1--135:14.
[29]
Ashish Myles and Denis Zorin. 2013. Controlled-distortion constrained global parametrization. ACM Transactions on Graphics 32, 4 (2013), 105.
[30]
Alexander Naitsat, Gregory Naitzat, and Yehoshua Y Zeevi. 2021. On Inversion-Free Mapping and Distortion Minimization. Journal of Mathematical Imaging and Vision (2021), 1--36.
[31]
Robert C Penner. 1987. The decorated Teichmüller space of punctured surfaces. Communications in Mathematical Physics 113, 2 (1987), 299--339.
[32]
Michael Rabinovich, Roi Poranne, Daniele Panozzo, and Olga Sorkine-Hornung. 2017. Scalable Locally Injective Mappings. ACM Trans. Graph. 36, 2 (2017), 16:1--16:16.
[33]
Nicolas Ray, Bruno Vallet, Laurent Alonso, and Bruno Levy. 2009. Geometry-Aware Direction Field Processing. ACM Trans. Graph. 29, 1 (2009).
[34]
Nicolas Ray, Bruno Vallet, Wan Chiu Li, and Bruno Lévy. 2008. N-Symmetry Direction Field Design. ACM Trans. Graph. 27, 2 (2008).
[35]
Igor Rivin. 1994. Euclidean structures on simplicial surfaces and hyperbolic volume. Annals of mathematics 139, 3 (1994), 553--580.
[36]
Christian Schüller, Ladislav Kavan, Daniele Panozzo, and Olga Sorkine-Hornung. 2013. Locally Injective Mappings. Computer Graphics Forum 32, 5 (2013), 125--135.
[37]
Nicholas Sharp, Keenan Crane, et al. 2019a. GeometryCentral: A modern C++ library of data structures and algorithms for geometry processing. https://geometry-central.net/. (2019).
[38]
Nicholas Sharp, Yousuf Soliman, and Keenan Crane. 2019b. Navigating intrinsic triangulations. ACM Transactions on Graphics 38, 4 (2019), 1--16.
[39]
Alla Sheffer and Eric de Sturler. 2001. Parameterization of faceted surfaces for meshing using angle-based flattening. Engineering with computers 17, 3 (2001), 326--337.
[40]
Hanxiao Shen, Leyi Zhu, Ryan Capouellez, Daniele Panozzo, Marcel Campen, and Denis Zorin. 2022. Which cross fields can be quadrangulated? global parameterization from prescribed holonomy signatures. ACM Transactions on Graphics (TOG) 41, 4 (2022), 1--12.
[41]
Boris Springborn. 2020. Ideal Hyperbolic Polyhedra and Discrete Uniformization. Discrete & Computational Geometry 64, 1 (2020), 63--108.
[42]
Boris Springborn, Peter Schröder, and Ulrich Pinkall. 2008. Conformal Equivalence of Triangle Meshes. ACM Transactions on Graphics 27, 3 (2008), 1--11.
[43]
Y. Tong, P. Alliez, D. Cohen-Steiner, and M. Desbrun. 2006. Designing quadrangulations with discrete harmonic forms. Symposium on Geometry Processing (2006), 201--210.
[44]
Amir Vaxman, Marcel Campen, Olga Diamanti, Daniele Panozzo, David Bommes, Klaus Hildebrandt, and Mirela Ben-Chen. 2016. Directional Field Synthesis, Design, and Processing. Comp. Graph. Forum 35, 2 (2016).
[45]
Jiaran Zhou, Changhe Tu, Denis Zorin, and Marcel Campen. 2020. Combinatorial construction of seamless parameter domains. In Computer Graphics Forum, Vol. 39. Wiley Online Library, 179--190.
[46]
Qingnan Zhou and Alec Jacobson. 2016. Thingi10K: A Dataset of 10,000 3D-Printing Models. arXiv preprint arXiv:1605.04797 (2016).
Index Terms
- Seamless Parametrization in Penner Coordinates
Recommendations
Metric Optimization in Penner Coordinates
Many parametrization and mapping-related problems in geometry processing can be viewed as metric optimization problems, i.e., computing a metric minimizing a functional and satisfying a set of constraints, such as flatness.
Penner coordinates are global ...
Approximate parametrization of plane algebraic curves by linear systems of curves
It is well known that an irreducible algebraic curve is rational (i.e. parametric) if and only if its genus is zero. In this paper, given a tolerance @e>0 and an @e-irreducible algebraic affine plane curve C of proper degree d, we introduce the notion ...
Accurate Parametrization of Conics by NURBS
It is well known that NURBS curves provide an exact representation of conics. Nevertheless, if this representation is exact on the geometric point of view (that is, the shape), the resulting parametrization is usually bad. For instance, the highest ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Copyright © 2024 Copyright is held by the owner/author(s). Publication rights licensed to ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 19 July 2024
Published in TOG Volume 43, Issue 4
Check for updates
Author Tags
Qualifiers
- Research-article
Funding Sources
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 225Total Downloads
- Downloads (Last 12 months)225
- Downloads (Last 6 weeks)52
Reflects downloads up to 14 Nov 2024
Other Metrics
Citations
View Options
Get Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in