Journal Home > Volume 9 , Issue 2

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 Wang1Wen-Xiang Zhang1Yuan-Yuan Cheng1Ligang Liu1Xiao-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
Received: 10 November 2021 Accepted: 06 January 2022 Published: 03 January 2023 Issue date: June 2023
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.
[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.
[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.
[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.
[7]
Schüller, C.; Kavan, L.; Panozzo, D.; Sorkine-Hornung, O. Locally injective mappings. Computer Graphics Forum Vol. 32, No. 5, 125–135, 2013.
[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.
[9]
Lipman, Y. Bounded distortion mapping spaces for triangular meshes. ACM Transactions on Graphics Vol. 31, No. 4, Article No. 108, 2012.
[10]
Smith, J.; Schaefer, S. Bijective parameterization with free boundaries. ACM Transactions on Graphics Vol. 34, No. 4, Article No. 70, 2015.
[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.
[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.
[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.
[14]
Jin, Y.; Huang, J.; Tong, R. Remeshing-assisted optimization for locally injective mappings. Computer Graphics Forum Vol. 33, No. 5, 269–279, 2014.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[23]
Aigerman, N.; Lipman, Y. Orbifold tutte embeddings. ACM Transactions on Graphics Vol. 34, No. 6, Article No. 190, 2015.
[24]
Aigerman, N.; Lipman, Y. Hyperbolic orbifold tutte embeddings. ACM Transactions on Graphics Vol. 35, No. 6, Article No. 217, 2016.
[25]
Floater, M. One-to-one piecewise linear mappings over triangulations. Mathematics of Computation Vol. 72, No. 242, 685–696, 2003.
[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.
[27]
Tutte, W. T. How to draw a graph. Proceedings of the London Mathematical Society Vol. s3-13, 743–767, 1963.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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