×

A new efficient algorithm for volume-preserving parameterizations of genus-one 3-manifolds. (English) Zbl 1457.65016

Summary: Parameterizations of manifolds are widely applied to the fields of numerical partial differential equations and computer graphics. To this end, in recent years several efficient and reliable numerical algorithms have been developed by different research groups for the computation of triangular and tetrahedral mesh parameterizations. However, it is still challenging when the topology of manifolds is nontrivial, e.g., the 3-manifold of a topological solid torus. In this paper, we propose a novel volumetric stretch energy minimization algorithm for volume-preserving parameterizations of toroidal polyhedra with a single boundary being mapped to a standard torus. In addition, the algorithm can also be used to compute the equiareal mapping between a genus-one closed surface and the standard torus. Numerical experiments indicate that the developed algorithm is effective and performs well on the bijectivity of the mapping. Applications on manifold registrations and partitions are demonstrated to show the robustness of our algorithms.

MSC:

65D18 Numerical aspects of computer graphics, image analysis, and computational geometry
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
52C26 Circle packings and discrete conformal geometry
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Digital Shape Workbench - Shape Repository, http://visionair.ge.imati.cnr.it/ontologies/shapes/, 2016.
[2] TurboSquid, http://www.turbosquid.com/, 2016.
[3] CGTrader, https://www.cgtrader.com/, 2019.
[4] Sketchfab, https://sketchfab.com/, 2019.
[5] RiemannMapper : A Mesh Parameterization Toolkit, https://www3.cs.stonybrook.edu/ gu/software/RiemannMapper/index.html, 2020.
[6] A. Chern, U. Pinkall, and P. Schröder, Close-to-conformal deformations of volumes, ACM Trans. Graphics, 34 (2015), 56, https://doi.org/10.1145/2766916. · Zbl 1334.68241
[7] G. P.-T. Choi and L. M. Lui, A linear formulation for disk conformal parameterization of simply-connected open surfaces, Adv. Comput. Math., 44 (2018), pp. 87-114, https://doi.org/10.1007/s10444-017-9536-x. · Zbl 1425.68431
[8] G. P. T. Choi and C. H. Rycroft, Density-equalizing maps for simply connected open surfaces, SIAM J. Imaging Sci., 11 (2018), pp. 1134-1178, https://doi.org/10.1137/17M1124796. · Zbl 1401.68347
[9] P. T. Choi, K. C. Lam, and L. M. Lui, FLASH: Fast landmark aligned spherical harmonic parameterization for genus-0 closed brain surfaces, SIAM J. Imaging Sci., 8 (2015), pp. 67-94, https://doi.org/10.1137/130950008. · Zbl 1316.65028
[10] P. T. Choi and L. M. Lui, Fast disk conformal parameterization of simply-connected open surfaces, J. Sci. Comput., 65 (2015), pp. 1065-1090, https://doi.org/10.1007/s10915-015-9998-2. · Zbl 1329.65050
[11] M. Desbrun, M. Meyer, and P. Alliez, Intrinsic parameterizations of surface meshes, Comput. Graph. Forum, 21 (2002), pp. 209-218.
[12] T. K. Dey, F. Fan, and Y. Wang, ReebHanTun Software, http://web.cse.ohio-state.edu/ dey.8/handle/ReebHanTun-download/reebhantun.html, 2013.
[13] T. K. Dey, K. Li, J. Sun, and D. Cohen-Steiner, Computing geometry-aware handle and tunnel loops in 3d models, ACM Trans. Graphics, 27 (2008), 45, https://doi.org/10.1145/1360612.1360644.
[14] D. Engwirda, Locally optimal Delaunay-refinement and optimisation-based mesh generation, Ph.D. thesis, University of Sydney, 2014, http://hdl.handle.net/2123/13148.
[15] D. Engwirda, Voronoi-based point-placement for three-dimensional Delaunay-refinement, Proc. Engrg., 124 (2015), pp. 330-342, https://doi.org/10.1016/j.proeng.2015.10.143.
[16] D. Engwirda, Conforming restricted Delaunay mesh generation for piecewise smooth complexes, Proc. Engrg., 163 (2016), pp. 84-96, https://doi.org/10.1016/j.proeng.2016.11.024.
[17] D. Engwirda and D. Ivers, Face-centred Voronoi refinement for surface mesh generation, Proc. Engrg., 82 (2014), pp. 8-20, https://doi.org/10.1016/j.proeng.2014.10.364.
[18] D. Engwirda and D. Ivers, Off-centre Steiner points for Delaunay-refinement on curved surfaces, Computer-Aided Design, 72 (2016), pp. 157-171, https://doi.org/10.1016/j.cad.2015.10.007.
[19] M. S. Floater and V. Pham-Trong, Convex combination maps over triangulations, tilings, and tetrahedral meshes, Adv. Comput. Math., 25 (2006), pp. 347-356, https://doi.org/10.1007/s10444-004-7620-5. · Zbl 1101.05028
[20] D. X. Gu,David Xianfeng Gu’s Home Page, http://www3.cs.stonybrook.edu/ gu/, 2017.
[21] X. Gu, F. Luo, J. Sun, and S.-T. Yau, Variational principles for Minkowski type problems, discrete optimal transport, and discrete Monge-Ampère equations, Asian J. Math., 20 (2016), pp. 383-398, https://doi.org/10.4310/AJM.2016.v20.n2.a7. · Zbl 1339.49039
[22] X. Gu and S.-T. Yau, Computing conformal structures of surfaces, Commun. Inf. Syst., 2 (2002), pp. 121-146, https://doi.org/10.4310/CIS.2002.v2.n2.a2. · Zbl 1092.14514
[23] X. Gu and S.-T. Yau, Global conformal surface parameterization, in Eurographics Symposium on Geometry Processing, L. Kobbelt, P. Schroeder, and H. Hoppe, eds., SGP ’03, ACM, New York, 2003, pp. 127-137, http://dl.acm.org/citation.cfm?id=882370.882388.
[24] X. Gu and S.-T. Yau, Computational Conformal Geometry, Higher Education Press, Beijing, China, 2008. · Zbl 1144.65008
[25] J. E. Hutchinson, Computing conformal maps and minimal surfaces, in Workshop on Theoretical and Numerical Aspects of Geometric Variational Problems (Canberra, 1990), Proc. Centre Math. Appl. Austral. Nat. Univ. 26, Austral. Nat. Univ., Canberra, Australia, 1991, pp. 140-161. · Zbl 0737.53012
[26] M. Jin, J. Kim, F. Luo, and X. Gu, Discrete surface ricci flow, IEEE Trans. Vis. Comput. Graphics, 14 (2008), pp. 1030-1043, https://doi.org/10.1109/TVCG.2008.57.
[27] M. Jin, Y. Wang, S.-T. Yau, and X. Gu, Optimal global conformal surface parameterization, in IEEE Visualization 2004, IEEE, Washington, DC, 2004, pp. 267-274, https://doi.org/10.1109/VISUAL.2004.75.
[28] Y. Jin, G.-P. Qian, J.-Y. Zhao, J. Chang, R.-F. Tong, and J. Zhang, Stretch-minimizing volumetric parameterization, J. Comput. Sci. Tech., 30 (2015), pp. 553-564, https://doi.org/10.1007/s11390-015-1545-y.
[29] S. Z. Kovalsky, N. Aigerman, R. Basri, and Y. Lipman, Controlling singular values with semidefinite programming, ACM Trans. Graphics, 33 (2014), 68, https://doi.org/10.1145/2601097.2601142. · Zbl 1396.65051
[30] S. Z. Kovalsky, N. Aigerman, R. Basri, and Y. Lipman, Large-scale bounded distortion mappings, ACM Trans. Graphics, 34 (2015), 19, https://doi.org/10.1145/2816795.2818098.
[31] A. Naitsat, E. Saucan, and Y. Y. Zeevi, Volumetric quasi-conformal mappings-quasi-conformal mappings for volume deformation with applications to geometric modeling, in Proceedings of the 10th International Conference on Computer Graphics Theory and Applications - Volume 1: GRAPP (VISIGRAPP 2015), INSTICC, SciTePress, 2015, pp. 46-57, https://doi.org/10.5220/0005298900460057.
[32] G.-P. Paillé and P. Poulin, As-conformal-as-possible discrete volumetric mapping, Computers & Graphics, 36 (2012), pp. 427-433, https://doi.org/10.1016/j.cag.2012.03.014.
[33] G.-P. Paillé, N. Ray, P. Poulin, A. Sheffer, and B. Lévy, Dihedral angle-based maps of tetrahedral meshes, ACM Trans. Graphics, 34 (2015), 54, https://doi.org/10.1145/2766900. · Zbl 1334.68264
[34] M. Rabinovich, R. Poranne, D. Panozzo, and O. Sorkine-Hornung, Scalable locally injective mappings, ACM Trans. Graphics, 36 (2017), 16, https://doi.org/10.1145/2983621.
[35] R. Sawhney and K. Crane, Boundary first flattening, ACM Trans. Graphics, 37 (2017), 5, https://doi.org/10.1145/3132705.
[36] J. Smith and S. Schaefer, Bijective parameterization with free boundaries, ACM Trans. Graphics, 34 (2015), 70, https://doi.org/10.1145/2766947. · Zbl 1334.68266
[37] K. Su, W. Chen, N. Lei, J. Zhang, K. Qian, and X. Gu, Volume preserving mesh parameterization based on optimal mass transportation, Comput. Aided Design, 82 (2017), pp. 42-56, https://doi.org/10.1016/j.cad.2016.05.020.
[38] K. Su, L. Cui, K. Qian, N. Lei, J. Zhang, M. Zhang, and X. D. Gu, Area-preserving mesh parameterization for poly-annulus surfaces based on optimal mass transportation, Comput. Aided Geom. Design, 46 (2016), pp. 76-91, https://doi.org/10.1016/j.cagd.2016.05.005. · Zbl 1418.65036
[39] J. M. Sullivan, Conformal tiling on a torus, in Proceedings of Bridges 2011: Mathematics, Music, Art, Architecture, Culture, Coimbra, Portugal, 2011, pp. 593-596.
[40] Y. Tong, S. Lombeyda, A. N. Hirani, and M. Desbrun, Discrete multiscale vector field decomposition, ACM Trans. Graphics, 22 (2003), pp. 445-452, https://doi.org/10.1145/882262.882290.
[41] Y. Wang, X. Gu, T. F. Chan, P. M. Thompson, and S.-T. Yau, Volumetric harmonic brain mapping, in Proceedings of the 2nd IEEE International Symposium on Biomedical Imaging: Nano to Macro, Vol. 2, IEEE, Washington, DC, 2004, pp. 1275-1278, https://doi.org/10.1109/ISBI.2004.1398778.
[42] Y. Wang, X. Gu, and S.-T. Yau, Volumetric harmonic map, Commun. Inform. Syst., 3 (2004), pp. 191-202, https://projecteuclid.org:443/euclid.cis/1088692283. · Zbl 1112.68488
[43] Z. Wang, Z.-x. Luo, J.-l. Zhang, and E. Saucan, Arap++: an extension of the local/global approach to mesh parameterization, Front. Inform. Tech. Electron. Engrg., 17 (2016), pp. 501-515, https://doi.org/10.1631/FITEE.1500184.
[44] M.-H. Yueh, X. D. Gu, W.-W. Lin, C.-T. Wu, and S.-T. Yau, Conformal surface registration with applications on face morphing, 2016, http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20160520142138341876035, mathscidoc:1605.09001.
[45] M.-H. Yueh, T. Li, W.-W. Lin, and S.-T. Yau, A novel algorithm for volume-preserving parameterizations of 3-manifolds, SIAM J. Imaging Sci., 12 (2019), pp. 1071-1098, https://doi.org/10.1137/18M1201184. · Zbl 07716395
[46] M.-H. Yueh, W.-W. Lin, C.-T. Wu, and S.-T. Yau, An efficient energy minimization for conformal parameterizations, J. Sci. Comput., 73 (2017), pp. 203-227, https://doi.org/10.1007/s10915-017-0414-y. · Zbl 1380.65049
[47] M.-H. Yueh, W.-W. Lin, C.-T. Wu, and S.-T. Yau, A novel stretch energy minimization algorithm for equiareal parameterizations, J. Sci. Comput., 78 (2019), pp. 1353-1386, https://doi.org/10.1007/s10915-018-0822-7. · Zbl 1417.65112
[48] M. Zhang, R. Guo, W. Zeng, F. Luo, S.-T. Yau, and X. Gu, The unified discrete surface Ricci flow, Graphical Models, 76 (2014), pp. 321-339, https://doi.org/10.1016/j.gmod.2014.04.008.
[49] X. Zhao, Z. Su, X. D. Gu, A. Kaufman, J. Sun, J. Gao, and F. Luo, Area-preservation mapping using optimal mass transport, IEEE Trans. Visual Comput. Graphics, 19 (2013), pp. 2838-2847, https://doi.org/10.1109/TVCG.2013.135.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.