AI Chat Paper
Note: Please note that the following content is generated by AMiner AI. SciOpen does not take any responsibility related to this content.
{{lang === 'zh_CN' ? '文章概述' : 'Summary'}}
{{lang === 'en_US' ? '中' : 'Eng'}}
Chat more with AI
Powered by AMiner. Clicking this button will take you away from SciOpen.
Home Computational Visual Media Article
PDF (10.8 MB)
Cite
EndNote(RIS) BibTeX
Collect
Submit Manuscript AI Chat Paper
Show Outline
Outline
Show full outline
Hide outline
Outline
Show full outline
Hide outline
Research Article | Open Access

Practical construction of globally injective parameterizations with positional constraints

School of Mathematical Sciences, University ofScience and Technology of China, Hefei 230026,China
Show Author Information

Graphical Abstract

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 parameterizationconstrained parameterizationbijectionflip-freescaffold mesh

References

[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.
Crossref
[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.
Crossref 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.
Crossref
[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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref Google Scholar
[9]
Lipman, Y. Bounded distortion mapping spaces for triangular meshes. ACM Transactions on Graphics Vol. 31, No. 4, Article No. 108, 2012.
Crossref Google Scholar
[10]
Smith, J.; Schaefer, S. Bijective parameterization with free boundaries. ACM Transactions on Graphics Vol. 34, No. 4, Article No. 70, 2015.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref
[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.
Crossref 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.
Crossref 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.
Crossref Google Scholar
[23]
Aigerman, N.; Lipman, Y. Orbifold tutte embeddings. ACM Transactions on Graphics Vol. 34, No. 6, Article No. 190, 2015.
Crossref Google Scholar
[24]
Aigerman, N.; Lipman, Y. Hyperbolic orbifold tutte embeddings. ACM Transactions on Graphics Vol. 35, No. 6, Article No. 217, 2016.
Crossref Google Scholar
[25]
Floater, M. One-to-one piecewise linear mappings over triangulations. Mathematics of Computation Vol. 72, No. 242, 685–696, 2003.
Crossref 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.
Crossref Google Scholar
[27]
Tutte, W. T. How to draw a graph. Proceedings of the London Mathematical Society Vol. s3-13, 743–767, 1963.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref 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.
Computational Visual Media
Volume 9 Issue 2,
June 2023
Pages 265-277
DOI: 10.1007/s41095-022-0269-5
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

8119

Views

76

Downloads

0

Crossref

2

Web of Science

2

Scopus

0

CSCD

Altmetrics
Received: 10 November 2021
Accepted: 06 January 2022
Published: 03 January 2023
© The Author(s) 2022.

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