research-article

Bijective parameterization with free boundaries

Authors:

Scott SchaeferAuthors Info & Claims

ACM Transactions on Graphics (TOG), Volume 34, Issue 4

Article No.: 70, Pages 1 - 9

https://doi.org/10.1145/2766947

Published: 27 July 2015 Publication History

Abstract

We present a fully automatic method for generating guaranteed bijective surface parameterizations from triangulated 3D surfaces partitioned into charts. We do so by using a distortion metric that prevents local folds of triangles in the parameterization and a barrier function that prevents intersection of the chart boundaries. In addition, we show how to modify the line search of an interior point method to directly compute the singularities of the distortion metric and barrier functions to maintain a bijective map. By using an isometric metric that is efficient to compute and a spatial hash to accelerate the evaluation and gradient of the barrier function for the boundary, we achieve fast optimization times. Unlike previous methods, we do not require the boundary be constrained by the user to a non-intersecting shape to guarantee a bijection, and the boundary of the parameterization is free to change shape during the optimization to minimize distortion.

Supplementary Material

MP4 File (a70.mp4)

Download
22.30 MB

References

[1]

Aigerman, N., Poranne, R., and Lipman, Y. 2014. Lifted bijections for low distortion surface mappings. ACM Trans. Graph. 33, 4, 69:1--69:12.

Digital Library

[2]

Bommes, D., Zimmer, H., and Kobbelt, L. 2009. Mixed-integer quadrangulation. ACM Trans. Graph. 28, 3, 77:1--77:10.

Digital Library

[3]

Burley, B., and Lacewell, D. 2008. Ptex: Per-face texture mapping for production rendering. In Eurographics Symposium on Rendering, 1155--1164.

Digital Library

[4]

Degener, P., Meseth, J., and Klein, R. 2003. An adaptable surface parameterization method. In Proceedings of the 12th International Meshing Roundtable, 201--213.

[5]

Floater, M. S., and Hormann, K. 2005. Surface parameterization: a tutorial and survey. In In Advances in Multiresolution for Geometric Modelling, Mathematics and Visualization, 157--186.

[6]

Floater, M. S. 1997. Parametrization and smooth approximation of surface triangulations. Computer Aided Geometric Design 14, 231--250.

Digital Library

[7]

Forsgren, A., Gill, P. E., and Wright, M. H. 2002. Interior methods for nonlinear optimization. SIAM Review 44, 4, 525--597.

Digital Library

[8]

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

[9]

Hormann, K., Lévy, B., and Sheffer, A. 2007. Mesh parameterization: Theory and practice. In ACM SIGGRAPH Courses.

Digital Library

[10]

Lévy, B., Petitjean, S., Ray, N., and Maillot, J. 2002. Least squares conformal maps for automatic texture atlas generation. ACM Trans. Graph. 21, 3, 362--371.

Digital Library

[11]

Lipman, Y. 2012. Bounded distortion mapping spaces for triangular meshes. ACM Trans. Graph. 31, 4, 108:1--108:13.

Digital Library

[12]

Liu, L., Zhang, L., Xu, Y., Gotsman, C., and Gortler, S. J. 2008. A local/global approach to mesh parameterization. In Symposium on Geometry Processing, 1495--1504.

Digital Library

[13]

Mullen, P., Tong, Y., Alliez, P., and Desbrun, M. 2008. Spectral conformal parameterization. In Symposium on Geometry Processing, 1487--1494.

Digital Library

[14]

Nocedal, J. 1980. Updating quasi-newton matrices with limited storage. Mathematics of Computation 35, 151, pp. 773--782.

[15]

Pinkall, U., and Polthier, K. 1993. Computing discrete minimal surfaces and their conjugates. Experimental Mathematics 2, 15--36.

[16]

Poranne, R., and Lipman, Y. 2014. Provably good planar mappings. ACM Trans. Graph. 33, 4, 76:1--76:11.

Digital Library

[17]

Purnomo, B., Cohen, J. D., and Kumar, S. 2004. Seamless texture atlases. In Symposium on Geometry Processing, 65--74.

Digital Library

[18]

Sanan, P. D. 2014. Geometric elasticity for graphics, simulation, and computation. PhD thesis, Caltech.

Digital Library

[19]

Sander, P. V., Snyder, J., Gortler, S. J., and Hoppe, H. 2001. Texture mapping progressive meshes. In ACM SIGGRAPH, 409--416.

Digital Library

[20]

Schneider, T., Hormann, K., and Floater, M. S. 2013. Bijective composite mean value mappings. In Symposium on Geometry Processing, 137--146.

Digital Library

[21]

Schreiner, J., Asirvatham, A., Praun, E., and Hoppe, H. 2004. Inter-surface mapping. In ACM SIGGRAPH, 870--877.

Digital Library

[22]

Schüller, C., Kavan, L., Panozzo, D., and Sorkinehornung, O. 2013. Locally injective mappings. In Symposium on Geometry Processing, 125--135.

Digital Library

[23]

Sheffer, A., and de Sturler, E. 2001. Parameterization of faceted surfaces for meshing using angle-based flattening. Engineering with Computers 17, 3, 326--337.

[24]

Sheffer, A., Lévy, B., Mogilnitsky, M., and Bogomyakov, A. 2005. Abf++: Fast and robust angle based flattening. ACM Trans. Graph. 24, 2, 311--330.

Digital Library

[25]

Sheffer, A., Praun, E., and Rose, K. 2006. Mesh parameterization methods and their applications. Found. Trends. Comput. Graph. Vis. 2, 2, 105--171.

Digital Library

[26]

Sorkine, O., Cohen-Or, D., Goldenthal, R., and Lischinski, D. 2002. Bounded-distortion piecewise mesh parameterization. In Proceedings of the Conference on Visualization, 355--362.

Digital Library

[27]

Springborn, B., Schröder, P., and Pinkall, U. 2008. Conformal equivalence of triangle meshes. ACM Trans. Graph. 27, 3, 77:1--77:11.

Digital Library

[28]

Tutte, W. T. 1963. How to draw a graph. Proceedings of the London Mathematical Society 13, 3, 743--768.

[29]

Weber, O., and Zorin, D. 2014. Locally injective parametrization with arbitrary fixed boundaries. ACM Trans. Graph. 33, 4, 75:1--75:12.

Digital Library

[30]

Wolfe, P. 1969. Convergence conditions for ascent methods. SIAM Review 11, 2, 226--235.

Digital Library

[31]

Yuksel, C., Keyser, J., and House, D. H. 2010. Mesh colors. ACM Transactions on Graphics 29, 2, 15:1--15:11.

Digital Library

[32]

Zhang, E., Mischaikow, K., and Turk, G. 2005. Featurebased surface parameterization and texture mapping. ACM Trans. Graph. 24, 1 (Jan.), 1--27.

Digital Library

[33]

Zhou, K., Synder, J., Guo, B., and Shum, H.-Y. 2004. Iso-charts: Stretch-driven mesh parameterization using spectral analysis. In Symposium on Geometry Processing, 45--54.

Digital Library

Cited By

Knodt JGao X(2025)Texture Size Reduction Through Symmetric Overlap and Texture CarvingACM Transactions on Graphics10.1145/371440844:1(1-20)Online publication date: 25-Jan-2025
https://dl.acm.org/doi/10.1145/3714408
Ye HLiu TNi HChen J(2025)Robust full-layer prismatic mesh generation based on bijective mappingJournal of Computational Physics10.1016/j.jcp.2025.113744524(113744)Online publication date: Mar-2025
https://doi.org/10.1016/j.jcp.2025.113744
Poya ROrtigosa RGil AKim TBonet J(2025)Generalised tangent stabilised nonlinear elasticity: An automated framework for controlling material and geometric instabilitiesComputer Methods in Applied Mechanics and Engineering10.1016/j.cma.2024.117701436(117701)Online publication date: Mar-2025
https://doi.org/10.1016/j.cma.2024.117701
Show More Cited By

Index Terms

Bijective parameterization with free boundaries
1. Computing methodologies
  1. Computer graphics
    1. Shape modeling
2. Theory of computation
  1. Randomness, geometry and discrete structures
    1. Computational geometry

Recommendations

Robust spherical parameterization of triangular meshes
Geometric modelling dagstuhl 2002

Parameterization of 3D mesh data is important for many graphics and mesh processing applications, in particular for texture mapping, remeshing and morphing. Closed, manifold, genus-0 meshes are topologically equivalent to a sphere, hence this is the ...
Differentials-based segmentation and parameterization for point-sampled surfaces

Efficient parameterization of point-sampled surfaces is a fundamental problem in the field of digital geometry processing. In order to parameterize a given point-sampled surface for minimal distance distortion, a differentials-based segmentation and ...
Measure controllable volumetric mesh parameterization
Abstract
Volumetric parameterization is a fundamental problem in solid and physical modeling. In practice, it is highly desirable to control the volumes of the regions of interest in the parameter domain. This work introduces a novel volumetric ...
Highlights
- The proposed method can handle solids with complicated topologies.
- Allows users to prescribe measures on the target and guarantees to reach it exactly.
- Comparing to other algorithms the proposed method reduces the number of ...

Comments

Information & Contributors

Information

Published In

cover image ACM Transactions on Graphics

ACM Transactions on Graphics Volume 34, Issue 4

August 2015

1307 pages

ISSN:0730-0301

EISSN:1557-7368

DOI:10.1145/2809654

Issue’s Table of Contents

Copyright © 2015 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 ACM 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: 27 July 2015

Published in TOG Volume 34, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

184
Total Citations
View Citations
1,303
Total Downloads

Downloads (Last 12 months)119
Downloads (Last 6 weeks)6

Reflects downloads up to 07 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Knodt JGao X(2025)Texture Size Reduction Through Symmetric Overlap and Texture CarvingACM Transactions on Graphics10.1145/371440844:1(1-20)Online publication date: 25-Jan-2025
https://dl.acm.org/doi/10.1145/3714408
Ye HLiu TNi HChen J(2025)Robust full-layer prismatic mesh generation based on bijective mappingJournal of Computational Physics10.1016/j.jcp.2025.113744524(113744)Online publication date: Mar-2025
https://doi.org/10.1016/j.jcp.2025.113744
Poya ROrtigosa RGil AKim TBonet J(2025)Generalised tangent stabilised nonlinear elasticity: An automated framework for controlling material and geometric instabilitiesComputer Methods in Applied Mechanics and Engineering10.1016/j.cma.2024.117701436(117701)Online publication date: Mar-2025
https://doi.org/10.1016/j.cma.2024.117701
Liu BLiu WLei ZZhang FHuang XAwwad T(2024)A Planar Feature-Preserving Texture Defragmentation Method for 3D Urban Building ModelsRemote Sensing10.3390/rs1622415416:22(4154)Online publication date: 7-Nov-2024
https://doi.org/10.3390/rs16224154
Sundararaman RDonati NMelzi SCorman EOvsjanikov M(2024)Deformation Recovery: Localized Learning for Detail-Preserving DeformationsACM Transactions on Graphics10.1145/368796843:6(1-16)Online publication date: 19-Dec-2024
https://dl.acm.org/doi/10.1145/3687968
Brodt KBessmeltsev M(2024)Skeleton-Driven Inbetweening of Bitmap Character DrawingsACM Transactions on Graphics10.1145/368795543:6(1-19)Online publication date: 19-Dec-2024
https://dl.acm.org/doi/10.1145/3687955
Livesu M(2024)Stripe Embedding: Efficient Maps with Exact Numeric ComputationACM Transactions on Graphics10.1145/368791543:6(1-14)Online publication date: 19-Dec-2024
https://dl.acm.org/doi/10.1145/3687915
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
Minarčík JEstep SNi WCrane K(2024)Minkowski Penalties: Robust Differentiable Constraint Enforcement for Vector GraphicsACM SIGGRAPH 2024 Conference Papers10.1145/3641519.3657495(1-12)Online publication date: 13-Jul-2024
https://dl.acm.org/doi/10.1145/3641519.3657495
Aigerman NGroueix T(2024)Generative Escher MeshesACM SIGGRAPH 2024 Conference Papers10.1145/3641519.3657452(1-11)Online publication date: 13-Jul-2024
https://dl.acm.org/doi/10.1145/3641519.3657452
Show More Cited By

View Options

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

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Issue’s Table of Contents