Journal Home > Volume 7 , Issue 3
Computational Visual Media 2021, 7(3): 289-318 https://doi.org/10.1007/s41095-021-0233-9
Review Article | Open Access | Issue | Published: 27 July 2021

Inversion-free geometric mapping construction: A survey

Show Author's Information Xiao-Ming Fu1( ),  Jian-Ping Su1,  Zheng-Yu Zhao1,  Qing Fang1,  Chunyang Ye1,  Ligang Liu1
School of Mathematical Sciences, University of Science and Technology of China, Hefei, China
Keywords:
distortion, inversion-free mapping, Jacobian matrix, first-order methods, second-order methods
Cite this article:
Fu X-M, Su J-P, Zhao Z-Y, et al. Inversion-free geometric mapping construction: A survey. Computational Visual Media, 2021, 7(3): 289-318. https://doi.org/10.1007/s41095-021-0233-9
Download citation
EndNote(RIS)
BibTeX

646

Views

24

Downloads

Citations

17

Crossref

16

WoS

17

Scopus

1

CSCD

Abstract Full text About this article

A geometric mapping establishes a correspondence between two domains. Since no real object has zero or negative volume, such a mapping is required to be inversion-free. Computing inversion-free mappings is a fundamental task in numerous computer graphics and geometric processing applications, such as deformation, texture mapping, mesh generation, and others. This task is usually formulated as a non-convex, nonlinear, constrained optimization problem. Various methods have been developed to solve this optimization problem. As well as being inversion-free, different applications have various further requirements. We expand the discussion in two directions to (i) problems imposing specific constraints and (ii) combinatorial problems. This report provides a systematic overview of inversion-free mapping construction, a detailed discussion of the construction methods, including their strengths and weaknesses, and a description of open problems in this research field.


menu
Abstract
Full text
Outline
About this article

Inversion-free geometric mapping construction: A survey

Show Author's information Xiao-Ming Fu1( ), Jian-Ping Su1, Zheng-Yu Zhao1, Qing Fang1, Chunyang Ye1, Ligang Liu1
School of Mathematical Sciences, University of Science and Technology of China, Hefei, China

Abstract

A geometric mapping establishes a correspondence between two domains. Since no real object has zero or negative volume, such a mapping is required to be inversion-free. Computing inversion-free mappings is a fundamental task in numerous computer graphics and geometric processing applications, such as deformation, texture mapping, mesh generation, and others. This task is usually formulated as a non-convex, nonlinear, constrained optimization problem. Various methods have been developed to solve this optimization problem. As well as being inversion-free, different applications have various further requirements. We expand the discussion in two directions to (i) problems imposing specific constraints and (ii) combinatorial problems. This report provides a systematic overview of inversion-free mapping construction, a detailed discussion of the construction methods, including their strengths and weaknesses, and a description of open problems in this research field.

Keywords: distortion, inversion-free mapping, Jacobian matrix, first-order methods, second-order methods

References(163)

[1]
Botsch, M.; Kobbelt, L.; Pauly, M.; Alliez, P.; Levy, B. Polygon Mesh Processing. New York: A K Peters/CRC Press, 2010.
DOI
[2]
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
[3]
Sheffer, A.; de Sturler, E. Parameterization of faceted surfaces for meshing using angle-based flattening. Engineering With Computers Vol. 17, No. 3, 326–337, 2001.
DOI Google Scholar
[4]
Sheffer, A.; Lévy, B.; Mogilnitsky, M.; Bogomyakov, A. ABF++: Fast and robust angle based flattening. ACM Transactions on Graphics Vol. 24, No. 2, 311–330, 2005.
DOI Google Scholar
[5]
Paillé, G. P.; Ray, N.; Poulin, P.; Sheffer, A.; Lévy, B. Dihedral angle-based maps of tetrahedral meshes. ACM Transactions on Graphics Vol. 34, No. 4, Article No. 54, 2015.
DOI Google Scholar
[6]
Springborn, B.; Schröder, P.; Pinkall, U. Conformal equivalence of triangle meshes. ACM Transactions on Graphics Vol. 27, No. 3, 1–11, 2008.
DOI Google Scholar
[7]
Ben-Chen, M.; Gotsman, C.; Bunin, G. Conformal flattening by curvature prescription and metric scaling. Computer Graphics Forum Vol. 27, No. 2, 449–458, 2008.
DOI Google Scholar
[8]
Fang, Q.; Zhao, Z. Y.; Liu, Z. Y.; Liu, L. G.; Fu, X. M. Metric first reconstruction for interactive curvature-aware modeling. Computer-Aided Design Vol. 126, 102863, 2020.
DOI Google Scholar
[9]
Chien, E.; Levi, Z.; Weber, O. Bounded distortion parametrization in the space of metrics. ACM Transactions on Graphics Vol. 35, No. 6, Article No. 215, 2016.
DOI Google Scholar
[10]
Roček, M.; Williams, R. M. The quantization of Regge calculus.Zeitschrift Für Physik C Particles and Fields Vol. 21, No. 4, 371–381, 1984.
DOI Google Scholar
[11]
Luo, F. Combinatorial yamabe flow on surfaces. Communications in Contemporary Mathematics Vol. 6, No. 5, 765–780, 2004.
DOI Google Scholar
[12]
Su, K.; Li, C.; Zhou, Y.; Xu, X.; Gu, X. Discrete calabi flow: A unified conformal parameterization method. Computer Graphics Forum Vol. 38, No. 7, 707–720, 2019.
DOI Google Scholar
[13]
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
[14]
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
[15]
Poranne, R.; Lipman, Y. Provably good planar mappings. ACM Transactions on Graphics Vol. 33, No. 4, Article No. 76, 2014.
DOI Google Scholar
[16]
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
[17]
Chen, R. J.; Weber, O. GPU-accelerated locally injective shape deformation. ACM Transactions on Graphics Vol. 36, No. 6, Article No. 214, 2017.
DOI Google Scholar
[18]
Chen, R. J.; Weber, O. Bounded distortion harmonic mappings in the plane. ACM Transactions on Graphics Vol. 34, No. 4, Article No. 73, 2015.
DOI Google Scholar
[19]
Levi, Z.; Weber, O. On the convexity and feasibility of the bounded distortion harmonic mapping problem. ACM Transactions on Graphics Vol. 35, No. 4, Article No. 106, 2016.
DOI Google Scholar
[20]
Hughes, T. J. R.; Cottrell, J. A.; Bazilevs, Y. Isogeometric analysis: CAD, finite elements, NURBS, exact geometry and mesh refinement. Computer Methods in Applied Mechanics and Engineering Vol. 194, Nos. 39–41, 4135–4195, 2005.
DOI Google Scholar
[21]
Liu, H.; Yang, Y.; Liu, Y.; Fu, X. M. Simultaneous interior and boundary optimization of volumetric domain parameterizations for IGA.Computer Aided Geometric Design Vol. 79, 101853, 2020.
DOI Google Scholar
[22]
Nian, X. S.; Chen, F. L. Planar domain parame-terization for isogeometric analysis based on Teichmüller mapping. Computer Methods in Applied Mechanics and Engineering Vol. 311, 41–55, 2016.
DOI Google Scholar
[23]
Dong, Z. C.; Fu, X. M.; Yang, Z. S.; Liu, L. G. Redirected smooth mappings for multiuser real walking in virtual reality. ACM Transactions on Graphics Vol. 38, No. 5, Article No. 149, 2019.
DOI Google Scholar
[24]
Dong, Z. C.; Fu, X. M.; Zhang, C.; Wu, K.; Liu, L. G. Smooth assembled mappings for large-scale real walking. ACM Transactions on Graphics Vol. 36, No. 6, Article No. 211, 2017.
DOI Google Scholar
[25]
Sun, Q.; Wei, L.-Y.; Kaufman, A. Mapping virtual and physical reality.ACM Transactions on Graphics Vol. 35, No. 4, Article No. 64, 2016.
DOI Google Scholar
[26]
Aigerman, N.; Lipman, Y. Injective and bounded distortion mappings in 3D. ACM Transactions on Graphics Vol. 32, No. 4, Article No. 106, 2013.
DOI Google Scholar
[27]
Degener, P.; Meseth, J.; Klein, R. An adaptable surface parameterization method. In: Proceedings of the 12th International Meshing Roundtable, 201–213, 2003.
[28]
Hormann, K.; Greiner, G. MIPS: An efficient global parametrization method. In: Curve and Surface Design: Saint-Malo 1999. Laurent, P.-J.; Sablonniere, P.; Schumaker, L. L. Eds. Vanderbilt University Press, 153–162, 2000.
[29]
Lévy, B.; Petitjean, S.; Ray, N.; Maillot, J. Least squares conformal maps for automatic texture atlas generation. ACM Transactions on Graphics Vol. 21, No. 3, 362–371, 2002.
DOI Google Scholar
[30]
Liu, L. G.; Zhang, L.; Xu, Y.; Gotsman, C.; Gortler, S. J. A local/global approach to mesh parameterization. Computer Graphics Forum Vol. 27, No. 5, 1495–1504, 2008.
DOI Google Scholar
[31]
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
[32]
Smith, J.; Schaefer, S. Bijective parameterization with free boundaries. ACM Transactions on Graphics Vol. 34, No. 4, Article No. 70, 2015.
DOI Google Scholar
[33]
Lipman, Y. Bounded distortion mapping spaces for triangular meshes.ACM Transactions on Graphics Vol. 31, No. 4, Article No. 108, 2012.
DOI Google Scholar
[34]
Tutte, W. T. How to draw a graph. Proceedings of the London Mathematical Society Vol. s3-13, No. 1, 743–767, 1963.
DOI
[35]
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
[36]
Claici, S.; Bessmeltsev, M.; Schaefer, S.; Solomon, J. Isometry-aware preconditioning for mesh parame-terization. Computer Graphics Forum Vol. 36, No. 5, 37–47, 2017.
DOI Google Scholar
[37]
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
[38]
Aigerman, N.; Lipman, Y. Orbifold Tutte embeddings. ACM Transactions on Graphics Vol. 34, No. 6, Article No. 190, 2015.
DOI Google Scholar
[39]
Floater, M. S. One-to-one piecewise linear mappings over triangulations. Mathematics of Computation Vol. 72, No. 242, 685–697, 2003.
DOI Google Scholar
[40]
Campen, M.; Silva, C. T.; Zorin, D. Bijective maps from simplicial foliations. ACM Transactions on Graphics Vol. 35, No. 4, Article No. 74, 2016.
DOI Google Scholar
[41]
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
[42]
Liu, T. T.; Gao, M.; Zhu, L. F.; Sifakis, E.; Kavan, L. Fast and robust inversion-free shape manipulation. Computer Graphics Forum Vol. 35, No. 2, 1–11, 2016.
DOI Google Scholar
[43]
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
[44]
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
[45]
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
[46]
Hormann, K. Theory and applications of parame-terizing triangulations. Ph.D. Thesis. Department of Computer Science, University of Erlangen, 2001.
[47]
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
[48]
Nocedal, J.; Wright, S. J. Numerical Optimization, 2nd edn. New York: Springer, 2006.
[49]
Jiang, L. J.; Byrd, R. H.; Eskow, E.; Schnabel, R. B. A preconditioned L-BFGS algorithm with application to molecular energy minimization. Technical Report. CU-CS-982-04. Department of Computer Science, University of Colorado, 2004.
DOI
[50]
Liu, T. T.; Bouaziz, S.; Kavan, L. Quasi-Newton methods for real-time simulation of hyperelastic materials. ACM Transactions on Graphics Vol. 36, No. 3, Article No. 23, 2017.
DOI Google Scholar
[51]
Nocedal, J.; Wright, S. J. Numerical Optimization.New York: Springer, 1999.
DOI
[52]
Teran, J.; Sifakis, E.; Irving, G.; Fedkiw, R. Robust quasistatic finite elements and flesh simulation. In: Proceedings of the ACM SIGGRAPH/Eurographics Symposium on Computer Animation, 181–190, 2005.
DOI
[53]
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
[54]
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
[55]
Ho, K. T.; Lui, L. M. QCMC: Quasi-conformal parameterizations for multiply-connected domains. Advances in Computational Mathematics Vol. 42, No. 2, 279–312, 2016.
DOI Google Scholar
[56]
Zeng, W.; Gu, X. D. Registration for 3D surfaces with large deformations using quasi-conformal curvature flow. In: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, 2457–2464, 2011.
DOI
[57]
Weber, O.; Myles, A.; Zorin, D. Computing extremal quasiconformal maps. Computer Graphics Forum Vol. 31, No. 5, 1679–1689, 2012.
DOI Google Scholar
[58]
Ma, M.; Lei, N.; Chen, W.; Su, K. H.; Gu, X. F. Robust surface registration using optimal mass transport and Teichmüller mapping.Graphical Models Vol. 90, 13–23, 2017.
DOI Google Scholar
[59]
Mastin, C. W.; Thompson, J. F. Discrete quasicon-formal mappings.Zeitschrift Für Angewandte Mathematik Und Physik ZAMP Vol. 29, No. 1, 1–11, 1978.
DOI Google Scholar
[60]
He, Z. X. Solving Beltrami equations by circle packing. Transactions of the American Mathematical Society Vol. 322, No. 2, 657–670, 1990.
DOI Google Scholar
[61]
Daripa, P. A fast algorithm to solve the Beltrami equation with applications to quasiconformal mappings. Journal of Computational Physics Vol. 106, No. 2, 355–365, 1993.
DOI Google Scholar
[62]
Wong, T. W.; Zhao, H. K. Computation of quasi-conformal surface maps using discrete beltrami flow. SIAM Journal on Imaging Sciences Vol. 7, No. 4, 2675–2699, 2014.
DOI Google Scholar
[63]
Lui, L. M.; Wong, T. W.; Zeng, W.; Gu, X. F.; Thompson, P. M.; Chan, T. F.; Yau, S.-T. Optimization of surface registrations using beltrami holomorphic flow. Journal of Scientific Computing Vol. 50, No. 3, 557–585, 2012.
DOI Google Scholar
[64]
Zeng, W.; Lui, L. M.; Luo, F.; Chan, T. F. C.; Yau, S. T.; Gu, D. X. Computing quasiconformal maps using an auxiliary metric and discrete curvature flow. Numerische Mathematik Vol. 121, No. 4, 671–703, 2012.
DOI Google Scholar
[65]
Kovalsky, S. Z.; Aigerman, N.; Basri, R.; Lipman, Y. Controlling singular values with semidefinite programming. ACM Transactions on Graphics Vol. 33, No. 4, Article No. 68, 2014.
DOI Google Scholar
[66]
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
[67]
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
[68]
Peng, Y.; Deng, B. L.; Zhang, J. Y.; Geng, F. Y.; Qin, W. J.; Liu, L. G. Anderson acceleration for geometry optimization and physics simulation.ACM Transactions on Graphics Vol. 37, No. 4, Article No. 42, 2018.
DOI Google Scholar
[69]
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
[70]
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
[71]
Toulorge, T.; Geuzaine, C.; Remacle, J. F.; Lambrechts, J. Robust untangling of curvilinear meshes. Journal of Computational Physics Vol. 254, 8–26, 2013.
DOI Google Scholar
[72]
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
[73]
Yang, Y.; Fu, X. M.; Chai, S. M.; Xiao, S. W.; Liu, L. G. Volume-enhanced compatible remeshing of 3D models. IEEE Transactions on Visualization and Computer Graphics Vol. 25, No. 10, 2999–3010, 2019.
DOI Google Scholar
[74]
Zayer, R.; Lévy, B.; Seidel, H.-P. Linear angle based parameterization. In: Proceedings of the 5th Eurographics Symposium on Geometry Processing, 135–141, 2007.
[75]
Crane, K.; Pinkall, U.; Schröder, P. Robust fairing via conformal curvature flow. ACM Transactions on Graphics Vol. 32, No. 4, Article No. 61, 2013.
DOI Google Scholar
[76]
Jin, M.; Kim, J.; Luo, F.; Gu, X. F. Discrete surface ricci flow. IEEE Transactions on Visualization and Computer Graphics Vol. 14, No. 5, 1030–1043, 2008.
DOI Google Scholar
[77]
Ge, H. B. Combinatorial Calabi flows on surfaces. Transactions of the American Mathematical Society Vol. 370, No. 2, 1377–1391, 2018.
DOI Google Scholar
[78]
Wang, Y. L.; Shi, J.; Yin, X. T.; Gu, X. F.; Chan, T. F.; Yau, S. T.; Toga, A. W.; Thompson, P. M. Brain surface conformal parameterization with the ricci flow. IEEE Transactions on Medical Imaging Vol. 31, No. 2, 251–264, 2012.
DOI Google Scholar
[79]
Zhao, H.; Li, X.; Ge, H. B.; Lei, N.; Zhang, M.; Wang, X. L.; Gu, X. F. Conformal mesh parameterization using discrete Calabi flow. Computer Aided Geometric Design Vol. 63, 96–108, 2018.
DOI Google Scholar
[80]
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
[81]
Zhang, W. J.; Ma, Y. W.; Zheng, J. M.; Allen, W. J. Tetrahedral mesh deformation with positional constraints. Computer Aided Geometric Design Vol. 81, 101909, 2020.
DOI Google Scholar
[82]
Hu, X.; Fu, X. M.; Liu, L. G. Advanced hierarchical spherical parameterizations. IEEE Transactions on Visualization and Computer Graphics Vol. 24, No. 6, 1930–1941, 2018.
DOI Google Scholar
[83]
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
[84]
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
[85]
Li, M. C.; Ferguson, Z.; Schneider, T.; Langlois, T.; Zorin, D.; Panozzo, D.; Jiang, C.; Kaufman, D. M. Incremental potential contact. ACM Transactions on Graphics Vol. 39, No. 4, Article No. 49, 2020.
DOI Google Scholar
[86]
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
[87]
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
[88]
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
[89]
Ye, C. Y.; Su, J. P.; Liu, L. G.; Fu, X. M. Memory-efficient bijective parameterizations of very-large-scale models. Computer Graphics Forum Vol. 39, No. 7, 1–12, 2020.
DOI Google Scholar
[90]
Hormann, K.; Lévy, B.; Sheffer, A. Mesh parame-terization: Theory and practice. In: Proceedings of the SIGGRAPH ’07: ACM SIGGRAPH 2007 Courses, 1–es, 2007.
DOI
[91]
Van Kaick, O.; Zhang, H.; Hamarneh, G.; Cohen-Or, D. A survey on shape correspondence. Computer Graphics Forum Vol. 30, No. 6, 1681–1707, 2011.
DOI Google Scholar
[92]
Li, X.; Iyengar, S. S. On computing mapping of 3D objects. ACM Computing Surveys Vol. 47, No. 2, Article No. 34, 2015.
DOI Google Scholar
[93]
Kraevoy, V.; Sheffer, A. Cross-parameterization and compatible remeshing of 3D models. ACM Transactions on Graphics Vol. 23, No. 3, 861–869, 2004.
DOI Google Scholar
[94]
Yang, Y.; Zhang, W. X.; Liu, Y.; Liu, L. G.; Fu, X. M. Error-bounded compatible remeshing. ACM Transactions on Graphics Vol. 39, No. 4, Article No. 113, 2020.
DOI Google Scholar
[95]
Alexa, M. Merging polyhedral shapes with scattered features. In: Proceedings of the International Conference on Shape Modeling and Applications, 202–210, 1999.
DOI
[96]
Kwok, T. H.; Zhang, Y. B.; Wang, C. C. L. Efficient optimization of common base domains for cross parameterization. IEEE Transactions on Visualization and Computer Graphics Vol. 18, No. 10, 1678–1692, 2012.
DOI Google Scholar
[97]
Aigerman, N.; Poranne, R.; Lipman, Y. Lifted bijections for low distortion surface mappings. ACM Transactions on Graphics Vol. 33, No. 4, Article No. 69, 2014.
DOI Google Scholar
[98]
Aigerman, N.; Poranne, R.; Lipman, Y. Seamless surface mappings. ACM Transactions on Graphics Vol. 34, No. 4, Article No. 72, 2015.
DOI Google Scholar
[99]
Aigerman, N.; Lipman, Y. Hyperbolic orbifold tutte embeddings. ACM Transactions on Graphics Vol. 35, No. 6, Article No. 190, 2016.
DOI Google Scholar
[100]
Praun, E.; Hoppe, H. Spherical parametrization and remeshing. ACM Transactions on Graphics Vol. 22, No. 3, 340–349, 2003.
DOI Google Scholar
[101]
Wang, C. X.; Hu, X.; Fu, X. M.; Liu, L. G. Bijective spherical parametrization with low distortion. Computers & Graphics Vol. 58, 161–171, 2016.
DOI Google Scholar
[102]
Hoppe, H. Progressive meshes. In: Proceedings of the 26th Annual Conference on Computer Graphics and Interactive Techniques, 99–108, 1996.
DOI
[103]
Schmidt, P.; Born, J.; Campen, M.; Kobbelt, L. Distortion-minimizing injective maps between surfaces. ACM Transactions on Graphics Vol. 38, No. 6, Article No. 156, 2019.
DOI Google Scholar
[104]
Schmidt, P.; Campen, M.; Born, J.; Kobbelt, L. Inter-surface maps via constant-curvature metrics. ACM Transactions on Graphics Vol. 39, No. 4, Article No. 119, 2020.
DOI Google Scholar
[105]
Tarini, M.; Hormann, K.; Cignoni, P.; Montani C. PolyCube-Maps. ACM Transactions on Graphics Vol. 23, No. 3, 853–860, 2004.
DOI Google Scholar
[106]
Yao, C. Y.; Lee, T. Y. Adaptive geometry image. IEEE Transactions on Visualization and Computer Graphics Vol. 14, No. 4, 948–960, 2008.
DOI Google Scholar
[107]
Chang, C.-C.; Lin, C.-Y. Texture tiling on 3D models using automatic PolyCube-maps and Wang tiles. Journal of Information Science and Engineering Vol. 26, No. 1, 291–305, 2010.
Google Scholar
[108]
Fu, X. M.; Bai, C. Y.; Liu, Y. Efficient volumetric PolyCube-map construction. Computer Graphics Forum Vol. 35, No. 7, 97–106, 2016.
DOI Google Scholar
[109]
Gregson, J.; Sheffer, A.; Zhang, E. All-hex mesh generation via volumetric PolyCube deformation. Computer Graphics Forum Vol. 30, No. 5, 1407–1416, 2011.
DOI Google Scholar
[110]
Yu, Y. Z.; Zhou, K.; Xu, D.; Shi, X. H.; Bao, H. J.; Guo, B. N.; Shum, H.-Y. Mesh editing with Poisson-based gradient field manipulation. ACM Transactions on Graphics Vol. 23, No. 3, 644–651, 2004.
DOI Google Scholar
[111]
Huang, J.; Jiang, T. F.; Shi, Z. Y.; Tong, Y. Y.; Bao, H. J.; Desbrun, M. ℓ1-based construction of polycube maps from complex shapes. ACM Transactions on Graphics Vol. 33, No. 3, Article No. 25, 2014.
DOI Google Scholar
[112]
Fang, X. Z.; Xu, W. W.; Bao, H. J.; Huang, J. All-hex meshing using closed-form induced polycube. ACM Transactions on Graphics Vol. 35, No. 4, Article No. 124, 2016.
DOI Google Scholar
[113]
Liu, C. L.; Yu, W. Y.; Chen, Z. G.; Li, X. Distributed poly-square mapping for large-scale semi-structured quad mesh generation.Computer-Aided Design Vol. 90, 5–17, 2017.
DOI Google Scholar
[114]
Xiao, S. W.; Kang, H. M.; Fu, X. M.; Chen, F. L. Computing IGA-suitable planar parameterizations by PolySquare-enhanced domain partition. Computer Aided Geometric Design Vol. 62, 29–43, 2018.
DOI Google Scholar
[115]
Livesu, M.; Vining, N.; Sheffer, A.; Gregson, J.; Scateni, R. PolyCut: Monotone graph-cuts for PolyCube base-complex construction. ACM Transactions on Graphics Vol. 32, No. 6, Article No. 171, 2013.
DOI Google Scholar
[116]
Guo, H. X.; Liu, X. H.; Yan, D. M.; Liu, Y. Cut-enhanced PolyCube-maps for feature-aware all-hex meshing. ACM Transactions on Graphics Vol. 39, No. 4, Article No. 106, 2020.
DOI Google Scholar
[117]
Xia, J.; Garcia, I.; He, Y.; Xin, S. Q.; Patow, G. Editable polycube map for GPU-based subdivision surfaces. In: Proceedings of the Symposium on Interactive 3D Graphics and Games, 151–158, 2011.
DOI
[118]
Liu, H. Y.; Fu, X. M.; Ye, C. Y.; Chai, S. M.; Liu, L. G. Atlas refinement with bounded packing efficiency. ACM Transactions on Graphics Vol. 38, No. 4, Article No. 33, 2019.
DOI Google Scholar
[119]
Zhang, C.; Xu, M. F.; Chai, S. M.; Fu, X. M. Robust atlas generation via angle-based segmentation. Computer Aided Geometric Design Vol. 79, 101854, 2020.
DOI Google Scholar
[120]
Eppstein, D.; Mumford, E. Steinitz theorems for orthogonal polyhedra. In: Proceedings of the 26th Annual Symposium on Computational Geometry, 429–438, 2010.
DOI
[121]
Yang, Y.; Fu, X. M.; Liu, L. G. Computing surface PolyCube-maps by constrained voxelization. Computer Graphics Forum Vol. 38, No. 7, 299–309, 2019.
DOI Google Scholar
[122]
Myles, A.; Pietroni, N.; Zorin, D. Robust field-aligned global parametrization. ACM Transactions on Graphics Vol. 33, No. 4, Article No. 135, 2014.
DOI Google Scholar
[123]
Myles, A.; Zorin, D. Global parametrization by incremental flattening.ACM Transactions on Graphics Vol. 31, No. 4, Article No. 109, 2012.
DOI Google Scholar
[124]
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
[125]
Sawhney, R.; Crane, K. Boundary first flattening. ACM Transactions on Graphics Vol. 37, No. 1, Article No. 5, 2018.
DOI Google Scholar
[126]
Campen, M.; Shen, H. X.; Zhou, J. R.; Zorin, D. Seamless parametrization with arbitrary cones for arbitrary genus. ACM Transactions on Graphics Vol. 39, No. 1, Article No. 2, 2020.
DOI Google Scholar
[127]
Zhou, J.; Tu, C.; Zorin, D.; Campen, M. Combinatorial construction of seamless parameter domains. Computer Graphics Forum Vol. 39, No. 2, 179–190, 2020.
DOI Google Scholar
[128]
Levi, Z. Direct seamless parametrization. ACM Transactions on Graphics Vol. 40, No. 1, Article No. 6, 2021.
DOI Google Scholar
[129]
Gu, X.; Yau, S.-T. Global conformal surface parameterization. In: Proceedings of the Eurographics/ACM SIGGRAPH Symposium on Geometry Processing, 127–137, 2003.
[130]
Bommes, D.; Zimmer, H.; Kobbelt, L. Mixed-integer quadrangulation. ACM Transactions on Graphics Vol. 28, No. 3, Article No. 77, 2009.
DOI Google Scholar
[131]
Myles, A.; Zorin, D. Global parametrization by incremental flattening.ACM Transactions on Graphics Vol. 31, No. 4, Article No. 109, 2012.
DOI Google Scholar
[132]
Myles, A.; Zorin, D. Controlled-distortion constrained global parametrization. ACM Transactions on Graphics Vol. 32, No. 4, Article No. 105, 2013.
DOI Google Scholar
[133]
Campen, M.; Bommes, D.; Kobbelt, L. Quantized global parametrization.ACM Transactions on Graphics Vol. 34, No. 6, Article No. 77, 2015.
DOI Google Scholar
[134]
Bright, A.; Chien, E.; Weber, O. Harmonic global parametrization with rational holonomy. ACM Transac-tions on Graphics Vol. 36, No. 4, Article No. 89, 2017.
DOI Google Scholar
[135]
Hefetz, E. F.; Chien, E.; Weber, O. A subspace method for fast locally injective harmonic mapping. Computer Graphics Forum Vol. 38, No. 2, 105–119, 2019.
DOI Google Scholar
[136]
Kharevych, L.; Springborn, B.; Schröder, P. Discrete conformal mappings via circle patterns. ACM Transactions on Graphics Vol. 25, No. 2, 412–438, 2006.
DOI Google Scholar
[137]
Soliman, Y.; Slepčev, D.; Crane, K. Optimal cone singularities for conformal flattening. ACM Transactions on Graphics Vol. 37, No. 4, Article No. 105, 2018.
DOI Google Scholar
[138]
Liu, H.; Zhang, X. T.; Fu, X. M.; Dong, Z. C.; Liu, L. G. Computational peeling art design. ACM Transactions on Graphics Vol. 38, No. 4, Article No. 64, 2019.
DOI Google Scholar
[139]
Julius, D.; Kraevoy, V.; Sheffer, A. D-charts: Quasi-developable mesh segmentation. Computer Graphics Forum Vol. 24, No. 3, 581–590, 2005.
DOI Google Scholar
[140]
Sander, P. V.; Gortler, S. J.; Snyder, J.; Hoppe, H. Signal-specialized parametrization. In: Proceedings of the 13th Eurographics Workshop on Rendering, 87–98, 2002.
[141]
Zhou, K.; Synder, J.; Guo, B. N.; Shum, H. Y. Iso-charts: Stretch-driven mesh parameterization using spectral analysis. In: Proceedings of the Eurographics/ACM SIGGRAPH Symposium on Geometry Processing, 45–54, 2004.
DOI
[142]
Li, M.; Kaufman, D. M.; Kim, V. G.; Solomon, J.; Sheffer, A. OptCuts: Joint optimization of surface cuts and parameterization. ACM Transactions on Graphics Vol. 37, No. 6, Article No. 247, 2018.
DOI Google Scholar
[143]
Poranne, R.; Tarini, M.; Huber, S.; Panozzo, D.; Sorkine-Hornung, O. Autocuts. ACM Transactions on Graphics Vol. 36, No. 6, Article No. 215, 2017.
DOI Google Scholar
[144]
Sheffer, A.; Hart, J. C. Seamster: Inconspicuous low-distortion texture seam layout. In: Proceedings of the IEEE Visualization, 291–298, 2002.
[145]
Sheffer, A. Spanning tree seams for reducing parameterization distortion of triangulated surfaces. In: Proceedings of the Shape Modeling International, 61–272, 2002.
[146]
Chai, S. M.; Fu, X. M.; Hu, X.; Yang, Y.; Liu, L. G. Sphere-based cut construction for planar parameterizations. Computers & Graphics Vol. 74, 66–75, 2018.
DOI Google Scholar
[147]
Zhu, T.; Ye, C. Y.; Chai, S. M.; Fu, X. M. Greedy cut construction for parameterizations. Computer Graphics Forum Vol. 39, No. 2, 191–202, 2020.
DOI Google Scholar
[148]
Chai, S. M.; Fu, X. M.; Liu, L. G. Voting for distortion points in geometric processing. IEEE Transactions on Visualization and Computer Graphics Vol. 27, No. 4, 2469–2480, 2021.
DOI Google Scholar
[149]
Gu, X. F.; Gortler, S. J.; Hoppe, H. Geometry images. ACM Transactions on Graphics Vol. 21, No. 3, 355–361, 2002.
DOI Google Scholar
[150]
Sorkine, O.; Cohen-Or, D.; Goldenthal, R.; Lischinski, D. Bounded-distortion piecewise mesh parameterization. In: Proceedings of the IEEE Visualization, 355–362, 2002.
[151]
Hwang, F. K.; Richards, D. S.; Winter, P. The Steiner Tree Problem.North Holland, 1992.
DOI
[152]
Fomin, F. V.; Grandoni, F.; Kratsch, D. Faster Steiner tree computation in polynomial-space. In: Algorithms - ESA 2008. Lecture Notes in Computer Science, Vol. 5193. Halperin, D.; Mehlhorn, K. Eds. Springer Berlin Heidelberg, 430–441, 2008.
[153]
Beasley, J. E. An SST-based algorithm for the Steiner problem in graphs.Networks Vol. 19, No. 1, 1–16, 1989.
DOI Google Scholar
[154]
Hakimi, S. L. Steiner’s problem in graphs and its implications.Networks Vol. 1, No. 2, 113–133, 1971.
DOI Google Scholar
[155]
Berman, P.; Ramaiyer, V. Improved approximations for the steiner tree problem. Journal of Algorithms Vol. 17, No. 3, 381–408, 1994.
DOI Google Scholar
[156]
Byrka, J.; Grandoni, F.; Rothvoss, T.; Sanità, L. Steiner tree approximation via iterative randomized rounding. Journal of the ACM Vol. 60, No. 1, 1–33, 2013.
DOI Google Scholar
[157]
Robins, G.; Zelikovsky, A. Tighter bounds for graph steiner tree approximation. SIAM Journal on Discrete Mathematics Vol. 19, No. 1, 122–134, 2005.
DOI Google Scholar
[158]
Pajor, T.; Uchoa, E.; Werneck, R. F. A robust and scalable algorithm for the Steiner problem in graphs. Mathematical Programming Computation Vol. 10, No. 1, 69–118, 2018.
DOI Google Scholar
[159]
Kou, L.; Markowsky, G.; Berman, L. A fast algorithm for Steiner trees.Acta Informatica Vol. 15, No. 2, 141–145, 1981.
DOI Google Scholar
[160]
Takahashi, H.; Matsuyama, A. An approximate solution for the Steiner problem in graphs. Mathematica Japonica Vol. 24, No. 6, 573–577, 1980.
Google Scholar
[161]
Alliez, P.; Ucelli, G.; Gotsman, C.; Attene, M. Recent advances in remeshing of surfaces. In: Shape Analysis and Structuring. Mathematics and Visualization. De Floriani, L.; Spagnuolo, M. Eds. Springer Berlin Heidelberg, 53–82, 2008.
DOI
[162]
Gao, X. F.; Panozzo, D.; Wang, W. P.; Deng, Z. G.; Chen, G. N. Robust structure simplification for hex re-meshing. ACM Transactions on Graphics Vol. 36, No. 6, Article No. 185, 2017.
DOI Google Scholar
[163]
Chern, A.; Pinkall, U.; Schröder, P. Close-to-conformal deformations of volumes. ACM Transactions on Graphics Vol. 34, No. 4, Article No. 56, 2015.
DOI Google Scholar
Publication history
Copyright
Acknowledgements
Rights and permissions

Publication history

Received: 29 December 2020
Accepted: 27 March 2021
Published: 27 July 2021
Issue date: September 2021

Copyright

© The Author(s) 2021

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 (Nos. 61802359 and 61672482) and the USTC Research Funds of the Double First-Class Initiative (No. YD0010002003).

Rights and permissions

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