Subdivision connectivity remeshing via Teichmüller extremal map

Chi Po Choi; Xianfeng Gu; Lok Ming Lui

doi:10.3934/ipi.2017039

Article Contents

2017, Volume 11, Issue 5: 825-855. Doi: 10.3934/ipi.2017039

This issue Previous Article Data driven recovery of local volatility surfaces Next Article Well-posed Bayesian inverse problems and heavy-tailed stable quasi-Banach space priors

Subdivision connectivity remeshing via Teichmüller extremal map

1.
Department of Statistics, University of California, Davis, USA
2.
Department of Computer Science, State University of New York at Stony Brook, USA
3.
Department of Mathematics, The Chinese University of Hong Kong, China

Received: February 29, 2016

Revised: May 31, 2017

Published: September 2017

Abstract Full Text(HTML) Figure(19) / Table(2) Related Papers Cited by

Abstract

Curvilinear surfaces in 3D Euclidean spaces are commonly represented by triangular meshes. The structure of the triangulation is important, since it affects the accuracy and efficiency of the numerical computation on the mesh. Remeshing refers to the process of transforming an unstructured mesh to one with desirable structures, such as the subdivision connectivity. This is commonly achieved by parameterizing the surface onto a simple parameter domain, on which a structured mesh is built. The 2D structured mesh is then projected onto the surface via the parameterization. Two major tasks are involved. Firstly, an effective algorithm for parameterizing, usually conformally, surface meshes is necessary. However, for a highly irregular mesh with skinny triangles, computing a folding-free conformal parameterization is difficult. The second task is to build a structured mesh on the parameter domain that is adaptive to the area distortion of the parameterization while maintaining good shapes of triangles. This paper presents an algorithm to remesh a highly irregular mesh to a structured one with subdivision connectivity and good triangle quality. We propose an effective algorithm to obtain a conformal parameterization of a highly irregular mesh, using quasi-conformal Teichmüller theories. Conformality distortion of an initial parameterization is adjusted by a quasi-conformal map, resulting in a folding-free conformal parameterization. Next, we propose an algorithm to obtain a regular mesh with subdivision connectivity and good triangle quality on the conformal parameter domain, which is adaptive to the area distortion, through the landmark-matching Teichmüller map. A remeshed surface can then be obtained through the parameterization. Experiments have been carried out to remesh surface meshes representing real 3D geometric objects using the proposed algorithm. Results show the efficacy of the algorithm to optimize the regularity of an irregular triangulation.

Keywords:

Mathematics Subject Classification: Primary: 94A08, 49Q10, 65E05; Secondary: 65S05, 49M30.

Citation:

Full Text(HTML)

Figure 1. Examples of irregular meshes. Conventional conformal parameterization methods fail on these examples

Download: Full-size image PowerPoint slide

Figure 2. Original surface meshes: Foot, hand, human face and venus

Download: Full-size image PowerPoint slide

Figure 3. Parameterization of Foot: (A) Tutte's embedding and (B) conformal parameterization

Download: Full-size image PowerPoint slide

Figure 4. Parameterization of Venus: (A) Tutte's embedding and (B) conformal parameterization

Download: Full-size image PowerPoint slide

Figure 5. Histogram for $\| \mu (\phi) \|_\infty$c

Download: Full-size image PowerPoint slide

Figure 6. Remeshed surface with a uniform mesh on the parameter domain

Download: Full-size image PowerPoint slide

Figure 7. Remeshing on the parameterization domain of the hand surface: (A) Parameterization mesh; (B) base mesh; (C) subdivision mesh; (D) Teichm¨uller adaptive mesh

Download: Full-size image PowerPoint slide

Figure 8. Remeshing results for the foot surface with different meshes on the parameter domain

Download: Full-size image PowerPoint slide

Figure 9. Surface remeshing results of the foot surface

Download: Full-size image PowerPoint slide

Figure 10. More surface remeshing results of the foot surface at different viewpoint angles

Download: Full-size image PowerPoint slide

Figure 11. Surface remeshing results of the hand surface at different viewpoint angles

Download: Full-size image PowerPoint slide

Figure 12. Surface remeshing results of the human face

Download: Full-size image PowerPoint slide

Figure 13. Surface remeshing of the venus surface

Download: Full-size image PowerPoint slide

Figure 14. Surface remeshing of the lion vase surface

Download: Full-size image PowerPoint slide

Figure 15. Surface remeshing of the mask surface

Download: Full-size image PowerPoint slide

Figure 16. Triangle quality of Foot

Download: Full-size image PowerPoint slide

Figure 17. Triangle quality of Venus

Download: Full-size image PowerPoint slide

Figure 18. Surface remeshing of the foot surface with subdivision connectivity at various levels

Download: Full-size image PowerPoint slide

Figure 19. Surface remeshing of the mask surface with subdivision connectivity at various levels

Download: Full-size image PowerPoint slide

Table 1. The conformality distortion of different parameterization methods for meshes with various triangle quality

Mesh	mean of $\tau_i$	std of $\tau_i$	min of $\tau_i$	Ricci	Yamabe	IDRF	Double	Ours
Foot	0.7769	0.1666	0.0126	0.2653	0.0238	0.0238	0.0304	0.0247
Hand	0.7117	0.1983	0.0079	0.3328	fail	fail	fail	0.0976
Face	0.7847	0.1951	0.0317	0.2420	fail	fail	0.0679	0.0109
Venus	0.8036	0.0712	0.0014	0.2837	fail	fail	fail	0.0064
Mask	0.8328	0.1603	0.0010	0.2379	fail	fail	0.1104	0.0057
Lion	0.6697	0.2220	0.0157	0.2029	fail	fail	0.0959	0.0323

| Show Table

DownLoad: CSV

Table 2. Comparison between the direct CVT method and Teichm¨uller remeshing

	# = 2557		# = 11065
	Direct	Teichmüuller	Direct	Teichmüuller
	CVT	Remeshing	CVT	Remeshing
Triangle Quality	mean = 0.9189 std = 0.0704 min = 0.1471	mean 0.9031 = std = 0.0476 min = 0.5252	mean = 0.9096 std = 0.0759 min = 0.0122	mean = 0.8786 std = 0.0368 min = 0.3240
Time	79s	21s	839s	61s

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	P. Alliez, E. C. de Verdiere, O. Devillers and M. Isenburg, Isotropic surface remeshing, Graphical Models, 67 (2005), 204-231. doi: 10.1109/SMI.2003.1199601.
[2]	P. Alliez, D. Cohen-Steiner, O. Devillers, B. Lévy and M. Desbrun, Anisotropic polygonal remeshing, ACM Transactions on Graphics (TOG), 22 (2003), 485-493. doi: 10.1145/1201775.882296.
[3]	Z. Chen, J. Cao and W. Wang, Isotropic surface remeshing using constrained centroidal delaunay mesh, Computer Graphics Forum, 31 (2012), 2077-2085. doi: 10.1111/j.1467-8659.2012.03200.x.
[4]	M. Desbrun, P. Alliez and M. Meyer, Interactive Geometry Remeshing Proceeding of ACM SIGGRAPH, 2002.
[5]	Q. Du, V. Faber and M. Gunzburger, Centroidal Voronoi tessellations: Applications and algorithms, SIAM Review, 41 (1999), 637-676. doi: 10.1137/S0036144599352836.
[6]	M. Eck, T. DeRose, T. Duchamp, H. Hoppe, M. Lounsbery and W. Stuetzle, Multiresolution analysis of arbitrary meshes, ACM Computer Graphics (SIGGRAPH 95 Proceedings), (1995), 173-182. doi: 10.1145/218380.218440.
[7]	P. J. Frey, About surface remeshing, Proceedings of 9th International Meshing Roundtable, (2000), 123-136.
[8]	P. J. Frey and H. Borouchaki, Geometric surface mesh optimization, Computing and Visualization in Science, 1 (1998), 113-121. doi: 10.1007/s007910050011.
[9]	F. Gardiner and N. Lakic, Quasiconformal Teichmuller Theory American Mathematics Society, 2000.
[10]	A. Gersho, Asymptotically optimal block quantization, IEEE Transactions on Information Theory, 25 (1979), 373-380. doi: 10.1109/TIT.1979.1056067.
[11]	X. F. Gu, S. J. Gortler and H. Hoppe, Geometry images, ACM Transactions on Graphics (TOG) -Proceedings of ACM SIGGRAPH, 21 (2002), 355-361. doi: 10.1145/566570.566589.
[12]	X. Gu and S. T. Yau, Computing conformal structures of surfaces, Communication in Information System, 2 (2002), 121-145. doi: 10.4310/CIS.2002.v2.n2.a2.
[13]	X. Gu, Y. Wang, T. F. Chan, P. Thompson and S. T. Yau, Genus zero surface conformal mapping and its application to brain surface mapping, Information Processing in Medical Imaging, (2003), 172-184. doi: 10.1007/978-3-540-45087-0_15.
[14]	S. Haker, S. Angenent, A. Tannenbaum, R. Kikinis, G. Sapiro and M. Halle, Conformal surface parameterization for texture mapping, IEEE Trans. Visualization and Computer Graphics, 6 (2000), 181–189. doi: 10.1109/2945.856998.
[15]	H. Hoppe, Progressive meshes, Computer Graphics. SIGGRAPH 96 Proceedings, 30 (1996), 99-108. doi: 10.1145/237170.237216.
[16]	H. Hoppe, T. DeRose, T. Duchamp, J. McDonald and W. Stuetzle, Mesh optimization, Computer Graphics. SIGGRAPH 93 Proceedings, 27 (1993), 19-26. doi: 10.1145/166117.166119.
[17]	K. Hormann, U. Labsik and G. Greiner, Remeshing triangulated surfaces with optimal parameterizations, Computer-Aided Design, 33 (2001), 779-788. doi: 10.1016/S0010-4485(01)00094-X.
[18]	M. K. Hurdal and K. Stephenson, Cortical cartography using the discrete conformal approach of circle packings, NeuroImage, 23 (2004), S119-S128. doi: 10.1016/j.neuroimage.2004.07.018.
[19]	M. Jin, J. Kim, F. Luo and X. Gu, Discrete surface Ricci flow, IEEE Transaction on Visualization and Computer Graphics, 14 (2008), 1030-1043. doi: 10.1109/TVCG.2008.57.
[20]	M. Jin, J. Kim, F. Luo and X. Gu, Combinatorial Yamabe flow on surfaces, Communication in Contemporary Mathematics, 6 (2004), 765-780. doi: 10.1142/S0219199704001501.
[21]	U. Labsik, L. Kobbelt, R. Schneider and H. P. Seidel, Progressive transmission of subdivision surfaces, Computational Geometry, 15 (2000), 25-39. doi: 10.1016/S0925-7721(99)00045-0.
[22]	R. Lai, Z. Wen, W. Yin, X. Gu and L. M. Lui, Folding-free global conformal mapping for genus-0 surfaces by harmonic energy minimization, Journal of Scientific Computing, 58 (2014), 705-725. doi: 10.1007/s10915-013-9752-6.
[23]	B. Lévy and J. Maillot, Least Squares Conformal Maps for Automatic Texture Atlas Generation ACM SIGGRAPH Proceedings, 2002.
[24]	M. Lounsbery, T. DeRose and J. Warren, Multiresolution analysis for surfaces of arbitrary topological type, ACM Transactions on Graphics (TOG) TOG Homepage Archive, 16 (1997), 34-73. doi: 10.1145/237748.237750.
[25]	L. M. Lui, T. W. Wong, W. Zeng, X. F. Gu, P. M. Thompson, T. F. Chan and S. T. Yau, Optimization of surface registrations using beltrami holomorphic flow, Journal of Scientific Computing, 50 (2012), 557-585. doi: 10.1007/s10915-011-9506-2.
[26]	L. M. Lui, T. W. Wong, X. F. Gu, P. M. Thompson, T. F. Chan and S. T. Yau, Hippocampal Shape Registration using Beltrami Holomorphic flow, Medical Image Computing and Computer Assisted Intervention(MICCAI), Part Ⅱ, LNCS, 6362 (2010), 323-330.
[27]	L. M. Lui, K. C. Lam, S. T. Yau and X. F. Gu, Teichmuller mapping (T-Map) and its applications to landmark matching registrations, SIAM Journal on Imaging Sciences, 7 (2014), 391-426. doi: 10.1137/120900186.
[28]	L. M. Lui, K. C. Lam, T. W. Wong and X. F. Gu, Texture map and video compression using Beltrami representation, SIAM Journal on Imaging Sciences, 6 (2013), 1880-1902. doi: 10.1137/120866129.
[29]	L. M. Lui, X. F. Gu and S. T. Yau, Convergence analysis of an iterative algorithm for Teichmuller maps via harmonic energy optimization, Mathematics of Computation, 84 (2015), 2823-2842. doi: 10.1090/S0025-5718-2015-02962-7.
[30]	T. C. Ng, X. F. Gu and L. M. Lui, Teichmuller extremal map of multiply-connected domains using Beltrami holomorphic flow, Journal of Scientific Computing, 60 (2014), 249-275. doi: 10.1007/s10915-013-9791-z.
[31]	P. Pébay and T. Baker, Analysis of triangle quality measures, Mathematics of Computation, 72 (2003), 1817-1839. doi: 10.1090/S0025-5718-03-01485-6.
[32]	G. Peyré and L. Cohen, Geodesic computations for fast and accurate surface remeshing and parameterization, Progress in Nonlinear equation and applications, 63 (2005), 157-171. doi: 10.1007/3-7643-7384-9_18.
[33]	E. Praun and H. Hoppe, Spherical parametrization and remeshing, ACM Transactions on Graphics (TOG) -Proceedings of ACM SIGGRAPH, 22 (2003), 340-349. doi: 10.1145/1201775.882274.
[34]	A. Rassineux, P. Villon, J.-M. Savignat and O. Stab, Surface remeshing by local Hermite diffuse interpolation, International Journal for Numerical Methods in Engineering, 49 (2000), 31-49.
[35]	G. Rong, M. Jin, L. Shuai and X. Guo, Centroidal Voronoi tessellation in universal covering space of manifold surfaces, Computer Aided Geometric Design (CAGD), 28 (2011), 475-496. doi: 10.1016/j.cagd.2011.06.005.
[36]	P. Schroder and W. Sweldens, Spherical wavelets: Efficiently representing functions on the sphere, ACM Computer Graphics (SIGGRAPH 95 Proceedings), (1995), 161-172.
[37]	V. Surazhsky and C. Gotsman, Explicit surface remeshing, Computer Graphics. SIGGRAPH 92 Proceedings, 26 (1992), 55-64.
[38]	G. Fejes Tóth, A stability criterion to the moment theorem, Studia Scientiarum Mathematicarum Hungarica, 38 (2001), 209-224. doi: 10.1556/SScMath.38.2001.1-4.14.
[39]	G. Turk, Re-tiling polygonal surfaces, Computer Graphics. SIGGRAPH 92 Proceedings, 26 (1992), 55-64. doi: 10.1145/133994.134008.
[40]	O. Weber, A. Myles and D. Zorin, Computing extremal quasiconformal maps, Computer Graphics Forum, 31 (2012), 1679-1689. doi: 10.1111/j.1467-8659.2012.03173.x.
[41]	D. Yan, B. Lévy, Y. Liu, F. Sun and W. Wang, Isotropic remeshing with fast and exact computation of restricted Voronoi diagram, Eurographics Symposium on Geometry Processing, 28 (2009), 1445-1454. doi: 10.1111/j.1467-8659.2009.01521.x.
[42]	Y. L. Yang, R. Guo, F. Luo, S. M. Hu and X. F. Gu, Generalized discrete ricci flow, Computer Graphics Forum, 28 (2009), 2005-2014.
[43]	W. Zeng, L. M. Lui, L. Shi, D. Wang, W. C. Chu, J. C. Cheng, J. Hua, S. T. Yau and X. F. Gu, Shape Analysis of Vestibular Systems in Adolescent Idiopathic Scoliosis Using Geodesic Spectra, Medical Image Computing and Computer Assisted Intervation, 13 (2010), 538-546. doi: 10.1007/978-3-642-15711-0_67.
[44]	W. Zeng, L. M. Lui, F. Luo, T. F. Chan, S. T. Yau and X. F. Gu, Computing quasiconformal maps using an auxiliary metric and discrete curvature flow, Numerische Mathematik, 121 (2012), 671-703. doi: 10.1007/s00211-012-0446-z.
[45]	W. Zeng and X. Gu, Registration for 3D surfaces with large deformations using quasi-conformal curvature flow IEEE Conference on Computer Vision and Pattern Recognition (CVPR11) Colorado Springs, Colorado, USA, Jun 20-25,2011. doi: 10.1109/CVPR.2011.5995410.
[46]	D. Zorin, P. Schroder and W. Sweldens, Interactive multiresolution mesh editing, ACM Computer Graphics (SIGGRAPH 97 Proceedings), (1997), 259-268. doi: 10.1145/258734.258863.