More Web Proxy on the site http://driver.im/

research-article

Public Access

Seamless Parametrization with Arbitrary Cones for Arbitrary Genus

Authors:

Denis ZorinAuthors Info & Claims

ACM Transactions on Graphics (TOG), Volume 39, Issue 1

Article No.: 2, Pages 1 - 19

https://doi.org/10.1145/3360511

Published: 20 December 2019 Publication History

All formats PDF

Abstract

Seamless global parametrization of surfaces is a key operation in geometry processing, e.g., for high-quality quad mesh generation. A common approach is to prescribe the parametric domain structure, in particular, the locations of parametrization singularities (cones), and solve a non-convex optimization problem minimizing a distortion measure, with local injectivity imposed through either constraints or barrier terms. In both cases, an initial valid parametrization is essential to serve as a feasible starting point for obtaining an optimized solution. While convexified versions of the constraints eliminate this initialization requirement, they narrow the range of solutions, causing some problem instances that actually do have a solution to become infeasible.

We demonstrate that for arbitrary given sets of topologically admissible parametric cones with prescribed curvature, a global seamless parametrization always exists (with the exception of one well-known case). Importantly, our proof is constructive and directly leads to a general algorithm for computing such parametrizations. Most distinctively, this algorithm is bootstrapped with a convex optimization problem (solving for a conformal map), in tandem with a simple linear equation system (determining a seamless modification of this map). This initial map can then serve as a valid starting point and be optimized for low distortion using existing injectivity preserving methods.

References

[1]

Noam Aigerman and Yaron Lipman. 2015. Orbifold tutte embeddings. ACM Trans. Graph. 34, 6 (2015), 190:1--190:12.

Digital Library

[2]

Noam Aigerman and Yaron Lipman. 2016. Hyperbolic orbifold tutte embeddings. ACM Trans. Graph. 35, 6 (2016), 217:1--217:14.

Digital Library

[3]

Mirela Ben-Chen, Craig Gotsman, and Guy Bunin. 2008. Conformal flattening by curvature prescription and metric scaling. Comput. Graph. Forum 27, 2 (2008), 449--458.

[4]

David Bommes, Marcel Campen, Hans-Christian Ebke, Pierre Alliez, and Leif Kobbelt. 2013a. Integer-grid maps for reliable quad meshing. ACM Trans. Graph. 32, 4 (2013).

Digital Library

[5]

David Bommes, Bruno Lévy, Nico Pietroni, Enrico Puppo, Claudio Silva, Marco Tarini, and Denis Zorin. 2013b. Quad-mesh generation and processing: A survey. In Computer Graphics Forum. Wiley.

[6]

David Bommes, Henrik Zimmer, and Leif Kobbelt. 2009. Mixed-integer quadrangulation. ACM Trans. Graph. 28, 3 (2009), 77.

Digital Library

[7]

Alon Bright, Edward Chien, and Ofir Weber. 2017. Harmonic global parametrization with rational holonomy. ACM Trans. Graph. 36, 4 (2017), 89:1--89:15.

Digital Library

[8]

Guy Bunin. 2008. A continuum theory for unstructured mesh generation in two dimensions. Comput. Aid. Geom. Design 25, 1 (2008), 14--40.

Digital Library

[9]

Marcel Campen, David Bommes, and Leif Kobbelt. 2015. Quantized global parametrization. ACM Trans. Graph. 34, 6 (2015), 192.

Digital Library

[10]

Marcel Campen and Leif Kobbelt. 2014. Dual strip weaving: Interactive design of quad layouts using elastica strips. ACM Trans. Graph. 33, 6 (2014), 183:1--183:10.

Digital Library

[11]

Marcel Campen and Denis Zorin. 2017. Similarity maps and field-guided t-splines: A perfect couple. ACM Trans. Graph. 36, 4 (2017).

Digital Library

[12]

Pascal Cherrier. 1984. Problèmes de neumann non linéaires sur les variétés riemanniennes. J. Function. Anal. 57, 2 (1984), 154--206.

[13]

Edward Chien, Zohar Levi, and Ofir Weber. 2016. Bounded distortion parametrization in the space of metrics. ACM Trans. Graph. 35, 6 (2016), 215:1--215:16.

Digital Library

[14]

Keenan Crane, Mathieu Desbrun, and Peter Schröder. 2010. Trivial connections on discrete surfaces. Comput. Graph. Forum 29, 5 (2010), 1525--1533.

[15]

Philip J Davis. 2012. Circulant Matrices. American Mathematical Society.

[16]

Tamal K. Dey, Fengtao Fan, and Yusu Wang. 2013. An efficient computation of handle and tunnel loops via Reeb graphs. ACM Trans. Graph. 32, 4 (2013), 32:1--32:10.

Digital Library

[17]

Hans-Christian Ebke, Patrick Schmidt, Marcel Campen, and Leif Kobbelt. 2016. Interactively controlled quad remeshing of high resolution 3D models. ACM Trans. Graph. 35, 6 (2016), 218:1--218:13.

Digital Library

[18]

Jeff Erickson and Kim Whittlesey. 2005. Greedy optimal homotopy and homology generators. In Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms. 1038--1046.

[19]

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.

Digital Library

[20]

M. S. Floater and K. Hormann. 2005. Surface parameterization: A tutorial and survey. In Advances in Multiresolution for Geometric Modelling, Neil A. Dodgson, Michael S. Floater, and Malcolm A. Sabin (Eds.).

[21]

Michael S. Floater. 1997. Parametrization and smooth approximation of surface triangulations. Comput. Aid. Geom. Design 14, 3 (1997), 231--250.

Digital Library

[22]

Xiao-Ming Fu, Yang Liu, and Baining Guo. 2015. Computing locally injective mappings by advanced MIPS. ACM Trans. Graph. 34, 4 (2015), 71:1--71:12.

Digital Library

[23]

Steven J. Gortler, Craig Gotsman, and Dylan Thurston. 2006. Discrete one-forms on meshes and applications to 3D mesh parameterization. Comput. Aid. Geom. Design 23, 2 (2006), 83--112.

Digital Library

[24]

Pierre Grisvard. 1985. Elliptic problems in nonsmooth domains, vol. 24 of Monographs and Studies in Mathematics. Pitman.

[25]

Xianfeng Gu, Ren Guo, Feng Luo, Jian Sun, and Tianqi Wu. 2018a. A discrete uniformization theorem for polyhedral surfaces II. J. Diff. Geom. 109, 3 (2018), 431--466.

[26]

Xianfeng Gu, Feng Luo, Jian Sun, and Tianqi Wu. 2018b. A discrete uniformization theorem for polyhedral surfaces. J. Diff. Geom. 109, 2 (2018).

[27]

Xianfeng Gu and Shing-Tung Yau. 2003. Global conformal surface parameterization. In Proceedings of the Symposium on Geometry Processing. 127--137.

Digital Library

[28]

Eden Fedida Hefetz, Edward Chien, and Ofir Weber. 2019. A subspace method for fast locally injective harmonic mapping. In Computer Graphics Forum, Vol. 38. Wiley, 105--119.

[29]

K. Hormann and G. Greiner. 2000. MIPS: An efficient global parametrization method. In Curve and Surface Design: Saint-Malo 1999. Vanderbilt University Press, 153--162.

[30]

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.

[31]

Felix Kälberer, Matthias Nieser, and Konrad Polthier. 2007. QuadCover: Surface parameterization using branched coverings. Comput. Graph. Forum 26, 3 (2007), 375--384.

[32]

Liliya Kharevych, Boris Springborn, and Peter Schröder. 2006. Discrete conformal mappings via circle patterns. ACM Trans. Graph. 25, 2 (2006), 412--438.

Digital Library

[33]

Shahar Z. Kovalsky, Meirav Galun, and Yaron Lipman. 2016. Accelerated quadratic proxy for geometric optimization. ACM Trans. Graph. 35, 4 (2016), 134:1--134:11.

Digital Library

[34]

Feng Luo. 2004. Combinatorial yamabe flow on surfaces. Commun. Contemp. Math. 6, 05 (2004), 765--780.

[35]

Max Lyon, Marcel Campen, David Bommes, and Leif Kobbelt. 2019. Parametrization quantization with free boundaries for trimmed quad meshing. ACM Trans. Graph. 38, 4 (2019), 51:1--51:14.

Digital Library

[36]

Manish Mandad and Marcel Campen. 2019. Exact constraint satisfaction for truly seamless parametrization. In Computer Graphics Forum, Vol. 38. Wiley, 135--145.

[37]

Giorgio Marcias, Nico Pietroni, Daniele Panozzo, Enrico Puppo, and Olga Sorkine-Hornung. 2013. Animation-aware quadrangulation. In Proceedings of the Symposium on Geometry Processing. 167--175.

Digital Library

[38]

Ashish Myles, Nico Pietroni, and Denis Zorin. 2014. Robust field-aligned global parametrization. ACM Trans. Graph. 33, 4 (2014).

Digital Library

[39]

Ashish Myles and Denis Zorin. 2012. Global parametrization by incremental flattening. ACM Trans. Graph. 31, 4 (2012), 109.

Digital Library

[40]

Ashish Myles and Denis Zorin. 2013. Controlled-distortion constrained global parametrization. ACM Trans. Graph. 32, 4 (2013), 105.

Digital Library

[41]

Budirijanto Purnomo, Jonathan D. Cohen, and Subodh Kumar. 2004. Seamless texture atlases. In Proceedings of the Symposium on Geometry Processing. 65--74.

Digital Library

[42]

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.

Digital Library

[43]

Nicolas Ray, Vincent Nivoliers, Sylvain Lefebvre, and Bruno Lévy. 2010. Invisible seams. In Proceedings of the EG Symposium on Rendering.

Digital Library

[44]

Rohan Sawhney and Keenan Crane. 2017. Boundary first flattening. ACM Trans. Graph. 37, 1 (2017), 5:1--5:14.

Digital Library

[45]

Christian Schüller, Ladislav Kavan, Daniele Panozzo, and Olga Sorkine-Hornung. 2013. Locally injective mappings. Comput. Graph. Forum 32, 5 (2013), 125--135.

Digital Library

[46]

Anna Shtengel, Roi Poranne, Olga Sorkine-Hornung, Shahar Z. Kovalsky, and Yaron Lipman. 2017. Geometric optimization via composite majorization. ACM Trans. Graph. 36, 4 (2017), 38:1--38:11.

Digital Library

[47]

Yousuf Soliman, Dejan Slepčev, and Keenan Crane. 2018. Optimal cone singularities for conformal flattening. ACM Trans. Graph. 37, 4 (2018), 105:1--105:17.

Digital Library

[48]

B. Springborn. 2017. Hyperbolic polyhedra and discrete uniformization. ArXiv E-prints arxiv:1707.06848

[49]

Boris Springborn, Peter Schröder, and Ulrich Pinkall. 2008. Conformal equivalence of triangle meshes. ACM Trans. Graph. 27, 3 (2008).

Digital Library

[50]

Yiying Tong, Pierre Alliez, Daniel Cohen-Steiner, and Mathieu Desbrun. 2006. Designing quadrangulations with discrete harmonic forms. In Proceedings of the Symposium on Geometry Processing. 201--210.

[51]

Marc Troyanov. 1991. Prescribing curvature on compact surfaces with conical singularities. Trans. Amer. Math. Soc. 324 (1991), 793--821.

[52]

W. T. Tutte. 1963. How to draw a graph. Proc. Lond. Math. Soc. 13 (1963), 743--767.

[53]

Amir Vaxman, Marcel Campen, Olga Diamanti, Daniele Panozzo, David Bommes, Klaus Hildebrandt, and Mirela Ben-Chen. 2016. Directional field synthesis, design, and processing. Comput. Graph. Forum 35, 2 (2016).

[54]

Ana-Maria Vintescu, Florent Dupont, Guillaume Lavoué, Pooran Memari, and Julien Tierny. 2017. Conformal factor persistence for fast hierarchical cone extraction. In Proceedings of the Eurographics Conference (EG’17).

[55]

Jiaran Zhou, Marcel Campen, Denis Zorin, Changhe Tu, and Claudio T Silva. 2018. Quadrangulation of non-rigid objects using deformation metrics. Comput. Aid. Geom. Design 62 (2018), 3--15.

[56]

Yufeng Zhu, Robert Bridson, and Danny M. Kaufman. 2018. Blended cured quasi-newton for distortion optimization. ACM Trans. Graph. 37, 4 (2018), 40:1--40:14.

Digital Library

Cited By

Li YKamil SCrane KJacobson AGingold Y(2024)IMESH: A DSL for Mesh ProcessingACM Transactions on Graphics10.1145/366218143:5(1-17)Online publication date: 25-Jun-2024
https://dl.acm.org/doi/10.1145/3662181
Hu ADesai NAbu Alhaija HKim SShugrina M(2024)Diffusion Texture PaintingACM SIGGRAPH 2024 Conference Papers10.1145/3641519.3657458(1-12)Online publication date: 13-Jul-2024
https://dl.acm.org/doi/10.1145/3641519.3657458
Simons LAmenta N(2024)Anisotropy and Cross FieldsComputer Graphics Forum10.1111/cgf.1513243:5Online publication date: 5-Aug-2024
https://doi.org/10.1111/cgf.15132
Show More Cited By

Index Terms

Seamless Parametrization with Arbitrary Cones for Arbitrary Genus
1. Computing methodologies
  1. Computer graphics
    1. Shape modeling
      1. Mesh geometry models
      2. Parametric curve and surface models

Recommendations

Maximally smooth cubic spline quasi-interpolants on arbitrary triangulations
Abstract
We investigate the construction of C 2 cubic spline quasi-interpolants on a given arbitrary triangulation T to approximate a sufficiently smooth function f. The proposed quasi-interpolants are locally represented in terms of a simplex spline ...
Highlights
- We construct three C 2 cubic spline quasi-interpolants over arbitrary triangulations.
- They are represented via a local simplex spline basis defined on the cubic Wang–Shi split.
- Their coefficients are determined by considering a ...
Seamless Parametrization in Penner Coordinates

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 ...
A generalized curve subdivision scheme of arbitrary order with a tension parameter

This article presents a generalized subdivision scheme of arbitrary order with a tension parameter for curve design. The scheme is built upon refinement of a family of generalized B-splines that unify classic B-splines with algebraic-trigonometric B-...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Graphics

ACM Transactions on Graphics Volume 39, Issue 1

February 2020

112 pages

ISSN:0730-0301

EISSN:1557-7368

DOI:10.1145/3366374

Editor:
Marc Alexa
TU Berlin, Germany

Issue’s Table of Contents

Copyright © 2019 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: 20 December 2019

Accepted: 01 July 2019

Revised: 01 April 2019

Received: 01 November 2018

Published in TOG Volume 39, Issue 1

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

NSF
Adobe

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

30
Total Citations
View Citations
1,499
Total Downloads

Downloads (Last 12 months)336
Downloads (Last 6 weeks)41

Reflects downloads up to 31 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Li YKamil SCrane KJacobson AGingold Y(2024)IMESH: A DSL for Mesh ProcessingACM Transactions on Graphics10.1145/366218143:5(1-17)Online publication date: 25-Jun-2024
https://dl.acm.org/doi/10.1145/3662181
Hu ADesai NAbu Alhaija HKim SShugrina M(2024)Diffusion Texture PaintingACM SIGGRAPH 2024 Conference Papers10.1145/3641519.3657458(1-12)Online publication date: 13-Jul-2024
https://dl.acm.org/doi/10.1145/3641519.3657458
Simons LAmenta N(2024)Anisotropy and Cross FieldsComputer Graphics Forum10.1111/cgf.1513243:5Online publication date: 5-Aug-2024
https://doi.org/10.1111/cgf.15132
Brückler HBommes DCampen M(2024)Integer‐Sheet‐Pump Quantization for Hexahedral MeshingComputer Graphics Forum10.1111/cgf.1513143:5Online publication date: 31-Jul-2024
https://doi.org/10.1111/cgf.15131
Zhang ZLi MZhao ZFang QFu X(2024)Practical Integer-Constrained Cone Construction for Conformal ParameterizationsIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2023.328730330:8(5227-5239)Online publication date: Aug-2024
https://doi.org/10.1109/TVCG.2023.3287303
Soliman YPinkall USchröder P(2024)Conformal surface splinesDifferential Geometry and its Applications10.1016/j.difgeo.2024.10220097(102200)Online publication date: Dec-2024
https://doi.org/10.1016/j.difgeo.2024.102200
Jezdimirović JChemin ARemacle J(2024)Integrable Cross-Field Generation Based on Imposed Singularity Configuration—The 2D Manifold CaseSIAM International Meshing Roundtable 202310.1007/978-3-031-40594-5_16(343-369)Online publication date: 21-Mar-2024
https://doi.org/10.1007/978-3-031-40594-5_16
Coiffier GCorman E(2023)The Method of Moving Frames for Surface Global ParametrizationACM Transactions on Graphics10.1145/360428242:5(1-18)Online publication date: 20-Sep-2023
https://dl.acm.org/doi/10.1145/3604282
Levi Z(2023)Seamless Parametrization with Cone and Partial Loop ControlACM Transactions on Graphics10.1145/360008742:5(1-22)Online publication date: 30-Aug-2023
https://dl.acm.org/doi/10.1145/3600087
Shepherd KHiemstra RHughes T(2023)The quad layout immersion: A mathematically equivalent representation of a surface quadrilateral layoutComputer Methods in Applied Mechanics and Engineering10.1016/j.cma.2023.116445417(116445)Online publication date: Dec-2023
https://doi.org/10.1016/j.cma.2023.116445
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

HTML Format

View this article in HTML Format.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Media

Figures

Other

Tables

View Issue’s Table of Contents