Journal Home > Volume 9 , Issue 2
Computational Visual Media 2023, 9(2): 265-277 https://doi.org/10.1007/s41095-022-0269-5
Research Article | Open Access | Issue | Published: 03 January 2023

Practical construction of globally injective parameterizations with positional constraints

Show Author's Information Qi Wang1,  Wen-Xiang Zhang1,  Yuan-Yuan Cheng1,  Ligang Liu1,  Xiao-Ming Fu1( )
School of Mathematical Sciences, University ofScience and Technology of China, Hefei 230026,China
Keywords:
globally injective parameterization, constrained parameterization, bijection, flip-free, scaffold mesh
Cite this article:
Wang Q, Zhang W-X, Cheng Y-Y, et al. Practical construction of globally injective parameterizations with positional constraints. Computational Visual Media, 2023, 9(2): 265-277. https://doi.org/10.1007/s41095-022-0269-5
Download citation
EndNote(RIS)
BibTeX

6518

Views

69

Downloads

Citations

0

Crossref

1

WoS

0

Scopus

0

CSCD

Abstract Full text About this article

We propose a novel method to compute globally injective parameterizations with arbitrary positional constraints on disk topology meshes. Central to this method is the use of a scaffold mesh that reduces the globally injective constraint to a locally flip-free condition. Hence, given an initial parameterized mesh containing flipped triangles and satisfying the positional constraints, we only need to remove the flips of a overall mesh consisting of the parameterized mesh and the scaffold mesh while always meeting positional constraints. To successfully apply this idea, we develop two key techniques. Firstly, an initialization method is used to generate a valid scaffold mesh and mitigate difficulties in eliminating flips. Secondly, edge-based remeshing is used to optimize the regularity of the scaffold mesh containing flips, thereby improving practical robustness. Compared to state-of-the-art methods,our method is much more robust. We demonstratethe capability and feasibility of our method on a large number of complex meshes.


menu
Abstract
Full text
Outline
About this article

Practical construction of globally injective parameterizations with positional constraints

Show Author's information Qi Wang1, Wen-Xiang Zhang1, Yuan-Yuan Cheng1, Ligang Liu1, Xiao-Ming Fu1( )
School of Mathematical Sciences, University ofScience and Technology of China, Hefei 230026,China

Abstract

We propose a novel method to compute globally injective parameterizations with arbitrary positional constraints on disk topology meshes. Central to this method is the use of a scaffold mesh that reduces the globally injective constraint to a locally flip-free condition. Hence, given an initial parameterized mesh containing flipped triangles and satisfying the positional constraints, we only need to remove the flips of a overall mesh consisting of the parameterized mesh and the scaffold mesh while always meeting positional constraints. To successfully apply this idea, we develop two key techniques. Firstly, an initialization method is used to generate a valid scaffold mesh and mitigate difficulties in eliminating flips. Secondly, edge-based remeshing is used to optimize the regularity of the scaffold mesh containing flips, thereby improving practical robustness. Compared to state-of-the-art methods,our method is much more robust. We demonstratethe capability and feasibility of our method on a large number of complex meshes.

Keywords: globally injective parameterization, constrained parameterization, bijection, flip-free, scaffold mesh

References(46)

[1]
Floater, M.; Hormann, K. Parameterization of triangulations and unorganized points. In: Tutorials on Multiresolution in Geometric Modelling. Mathematics and Visualization. Iske, A.; Quak, E.; Floater, M. S. Eds. Springer Berlin Heidelberg, 287–316, 2002.
DOI
[2]
Floater, M. S.; Hormann, K. Surface parameterization: A tutorial and survey. In: Advances in Multiresolution for Geometric Modelling. Mathematics and Visua-lization. Dodgson, N. A.; Floater, M. S.; Sabin, M. A. Eds. Springer Berlin Heidelberg, 157–186, 2005.
[3]
Sheffer, A.; Praun, E.; Rose, K. Mesh parameterization methods and their applications. Foundations and Trends® in Computer Graphics and Vision Vol. 2, No. 2, 105–171, 2006.
DOI Google Scholar
[4]
Hormann, K.; Lévy, B.; Sheffer, A. Mesh parame-terization: Theory and practice. In: Proceedings of the ACM SIGGRAPH 2007 Courses, 1–es, 2007.
DOI
[5]
Fu, X. M.; Su, J. P.; Zhao, Z. Y.; Fang, Q.; Ye, C. Y.; Liu, L. G. Inversion-free geometric mapping construction: A survey. Computational Visual Media Vol. 7, No. 3, 289–318, 2021.
DOI Google Scholar
[6]
Fu, X. M.; Liu, Y.; Guo, B. N. Computing locally injective mappings by advanced MIPS. ACM Transactions on Graphics Vol. 34, No. 4, Article No. 71, 2015.
DOI Google Scholar
[7]
Schüller, C.; Kavan, L.; Panozzo, D.; Sorkine-Hornung, O. Locally injective mappings. Computer Graphics Forum Vol. 32, No. 5, 125–135, 2013.
DOI Google Scholar
[8]
Su, J. P.; Fu, X. M.; Liu, L. G. Practical foldover-free volumetric mapping construction. Computer Graphics Forum Vol. 38, No. 7, 287–297, 2019.
DOI Google Scholar
[9]
Lipman, Y. Bounded distortion mapping spaces for triangular meshes. ACM Transactions on Graphics Vol. 31, No. 4, Article No. 108, 2012.
DOI Google Scholar
[10]
Smith, J.; Schaefer, S. Bijective parameterization with free boundaries. ACM Transactions on Graphics Vol. 34, No. 4, Article No. 70, 2015.
DOI Google Scholar
[11]
Jiang, Z. S.; Schaefer, S.; Panozzo, D. Simplicial complex augmentation framework for bijective maps. ACM Transactions on Graphics Vol. 36, No. 6, Article No. 186, 2017.
DOI Google Scholar
[12]
Su, J.-P.; Ye, C.; Liu, L.; Fu, X.-M. Efficient bijective parameterizations. ACM Transactions on Graphics Vol. 39, No. 4, Article No. 111, 2020.
DOI Google Scholar
[13]
Overby, M.; Kaufman, D.; Narain, R. Globally injective geometry optimization with non-injective steps. Computer Graphics Forum Vol. 40, No. 5, 111–123, 2021.
DOI Google Scholar
[14]
Jin, Y.; Huang, J.; Tong, R. Remeshing-assisted optimization for locally injective mappings. Computer Graphics Forum Vol. 33, No. 5, 269–279, 2014.
DOI Google Scholar
[15]
Fang, Y.; Li, M. C.; Jiang, C.; Kaufman, D. M. Guaranteed globally injective 3D deformation processing. ACM Transactions on Graphics Vol. 40, No. 4, Article No. 75, 2021.
DOI Google Scholar
[16]
Du, X. Y.; Kaufman, D. M.; Zhou, Q. N.; Kovalsky, S. Z.; Yan, Y. J.; Aigerman, N.; Ju, T. Optimizing global injectivity for constrained parameterization. ACM Transactions on Graphics Vol. 40, No. 6, Article No. 260, 2021.
DOI Google Scholar
[17]
Zhang, E.; Mischaikow, K.; Turk, G. Feature-based surface parameterization and texture mapping. ACM Transactions on Graphics Vol. 24, No. 1, 1–27, 2005.
DOI Google Scholar
[18]
Lipman, Y. Bijective mappings of meshes with boundary and the degree in mesh processing. SIAM Journal on Imaging Sciences Vol. 7, No. 2, 1263–1283, 2014.
DOI Google Scholar
[19]
Botsch, M.; Kobbelt, L. A remeshing approach to multiresolution modeling. In: Proceedings of the Eurographics/ACM SIGGRAPH Symposium on Geometry Processing, 185–192, 2004.
DOI
[20]
Claici, S.; Bessmeltsev, M.; Schaefer, S.; Solomon, J. Isometry-aware preconditioning for mesh para-meterization. Computer Graphics Forum Vol. 36, No. 5, 37–47, 2017.
DOI Google Scholar
[21]
Liu, L. G.; Ye, C. Y.; Ni, R. Q.; Fu, X. M. Progressive parameterizations. ACM Transactions on Graphics Vol. 37, No. 4, Article No. 41, 2018.
DOI Google Scholar
[22]
Rabinovich, M.; Poranne, R.; Panozzo, D.; Sorkine-Hornung, O. Scalable locally injective mappings. ACM Transactions on Graphics Vol. 36, No. 4, Article No. 16, 2017.
DOI Google Scholar
[23]
Aigerman, N.; Lipman, Y. Orbifold tutte embeddings. ACM Transactions on Graphics Vol. 34, No. 6, Article No. 190, 2015.
DOI Google Scholar
[24]
Aigerman, N.; Lipman, Y. Hyperbolic orbifold tutte embeddings. ACM Transactions on Graphics Vol. 35, No. 6, Article No. 217, 2016.
DOI Google Scholar
[25]
Floater, M. One-to-one piecewise linear mappings over triangulations. Mathematics of Computation Vol. 72, No. 242, 685–696, 2003.
DOI Google Scholar
[26]
Shen, H. X.; Jiang, Z. S.; Zorin, D.; Panozzo, D. Progressive embedding. ACM Transactions on Graphics Vol. 38, No. 4, Article No. 32, 2019.
DOI Google Scholar
[27]
Tutte, W. T. How to draw a graph. Proceedings of the London Mathematical Society Vol. s3-13, 743–767, 1963.
DOI Google Scholar
[28]
Hormann, K.; Greiner, G. MIPS: An efficient global parametrization method. In: Curve and Surface Design: Saint-Malo 1999. Vanderbilt University Press, 153–162, 2000.
[29]
Schreiner, J.; Asirvatham, A.; Praun, E.; Hoppe, H. Inter-surface mapping. ACM Transactions on Graphics Vol. 23, No. 3, 870–877, 2004.
DOI Google Scholar
[30]
Kovalsky, S. Z.; Galun, M.; Lipman, Y. Accelerated quadratic proxy for geometric optimization. ACM Transactions on Graphics Vol. 35, No. 4, Article No. 134, 2016.
DOI Google Scholar
[31]
Zhu, Y. F.; Bridson, R.; Kaufman, D. M. Blended cured quasi-Newton for distortion optimization. ACM Transactions on Graphics Vol. 37, No. 4, Article No. 40, 2018.
DOI Google Scholar
[32]
Shtengel, A.; Poranne, R.; Sorkine-Hornung, O.; Kovalsky, S. Z.; Lipman, Y. Geometric optimization via composite majorization. ACM Transactions on Graphics Vol. 36, No. 4, Article No. 38, 2017.
DOI Google Scholar
[33]
Smith, B.; De Goes, F.; Kim, T. Analytic eigensystems for isotropic distortion energies. ACM Transactions on Graphics Vol. 38, No. 1, Article No. 3, 2019.
DOI Google Scholar
[34]
Golla, B.; Seidel, H. P.; Chen, R. J. Piecewise linear mapping optimization based on the complex view. Computer Graphics Forum Vol. 37, No. 7, 233–243, 2018.
DOI Google Scholar
[35]
Kovalsky, S. Z.; Aigerman, N.; Basri, R.; Lipman, Y. Large-scale bounded distortion mappings. ACM Transactions on Graphics Vol. 34, No. 6, Article No. 191, 2015.
DOI Google Scholar
[36]
Fu, X. M.; Liu, Y. Computing inversion-free mappings by simplex assembly. ACM Transactions on Graphics Vol. 35, No. 6, Article No. 216, 2016.
DOI Google Scholar
[37]
Escobar, J. M.; Rodríguez, E.; Montenegro, R.; Montero, G.; González-Yuste, J. M. Simultaneous untangling and smoothing of tetrahedral meshes. Computer Methods in Applied Mechanics and Engineering Vol. 192, No. 25, 2775–2787, 2003.
DOI Google Scholar
[38]
Garanzha, V.; Kaporin, I.; Kudryavtseva, L.; Protais, F.; Ray, N.; Sokolov, D. Foldover-free maps in 50 lines of code. ACM Transactions on Graphics Vol. 40, No. 4, Article No. 102, 2021.
DOI Google Scholar
[39]
Xu, Y.; Chen, R. J.; Gotsman, C.; Liu, L. G. Embedding a triangular graph within a given boundary. Computer Aided Geometric Design Vol. 28, No. 6, 349–356, 2011.
DOI Google Scholar
[40]
Du, X. Y.; Aigerman, N.; Zhou, Q. N.; Kovalsky, S. Z.; Yan, Y. J.; Kaufman, D. M.; Ju, T. Lifting simplices to find injectivity. ACM Transactions on Graphics Vol. 39, No. 4, Article No. 120, 2020.
DOI Google Scholar
[41]
Misztal, M. K.; Bærentzen, J. A. Topology-adaptive interface tracking using the deformable simplicial complex. ACM Transactions on Graphics Vol. 31, No. 3, Article No. 24, 2012.
DOI Google Scholar
[42]
Müller, M.; Chentanez, N.; Kim, T. Y.; Macklin, M. Air meshes for robust collision handling. ACM Transactions on Graphics Vol. 34, No. 4, Article No. 133, 2015.
DOI Google Scholar
[43]
Ainsley, S.; Vouga, E.; Grinspun, E.; Tamstorf, R. Speculative parallel asynchronous contact mechanics. ACM Transactions on Graphics Vol. 31, No. 6, Article No. 151, 2012.
DOI Google Scholar
[44]
Horn, B. K. P. Closed-form solution of absolute orientation using unit quaternions. Journal of the Optical Society of America A Vol. 4, No. 4, 629, 1987.
DOI Google Scholar
[45]
Bouaziz, S.; Deuss, M.; Schwartzburg, Y.; Weise, T.; Pauly, M. Shape-up: Shaping discrete geometry with projections. Computer Graphics Forum Vol. 31, No. 5, 1657–1667, 2012.
DOI Google Scholar
[46]
Shewchuk, J. R. Triangle: Engineering a 2D quality mesh generator and Delaunay triangulator. In: Applied Computational Geometry towards Geometric Engineering. Lecture Notes in Computer Science, Vol. 1148. Lin, M. C.; Manocha, D. Eds. Springer Berlin Heidelberg, 203–222, 1996.
Publication history
Copyright
Acknowledgements
Rights and permissions

Publication history

Received: 10 November 2021
Accepted: 06 January 2022
Published: 03 January 2023
Issue date: June 2023

Copyright

© The Author(s) 2022.

Acknowledgements

We would like to thank the anonymous reviewers for their constructive suggestions and comments. This work was supported by the National Natural Science Foundation of China (61802359, 62025207) and USTC Research Funds of the Double First-Class Initiative (YD0010002003).

Rights and permissions

Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduc-tion in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made.

The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder.

To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.

Other papers from this open access journal are available free of charge from http://www.springer.com/journal/41095. To submit a manuscript, please go to https://www.editorialmanager.com/cvmj.

Return