# American Institute of Mathematical Sciences

October  2017, 11(5): 825-855. doi: 10.3934/ipi.2017039

## 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  March 2016 Revised  June 2017 Published  July 2017

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.

Citation: Chi Po Choi, Xianfeng Gu, Lok Ming Lui. Subdivision connectivity remeshing via Teichmüller extremal map. Inverse Problems & Imaging, 2017, 11 (5) : 825-855. doi: 10.3934/ipi.2017039
##### References:

show all references

##### References:
Examples of irregular meshes. Conventional conformal parameterization methods fail on these examples
Original surface meshes: Foot, hand, human face and venus
Parameterization of Foot: (A) Tutte's embedding and (B) conformal parameterization
Parameterization of Venus: (A) Tutte's embedding and (B) conformal parameterization
Histogram for $\| \mu (\phi) \|_\infty$c
Remeshed surface with a uniform mesh on the parameter domain
Remeshing on the parameterization domain of the hand surface: (A) Parameterization mesh; (B) base mesh; (C) subdivision mesh; (D) Teichm¨uller adaptive mesh
Remeshing results for the foot surface with different meshes on the parameter domain
Surface remeshing results of the foot surface
More surface remeshing results of the foot surface at different viewpoint angles
Surface remeshing results of the hand surface at different viewpoint angles
Surface remeshing results of the human face
Surface remeshing of the venus surface
Surface remeshing of the lion vase surface
Surface remeshing of the mask surface
Triangle quality of Foot
Triangle quality of Venus
Surface remeshing of the foot surface with subdivision connectivity at various levels
Surface remeshing of the mask surface with subdivision connectivity at various levels
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
 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
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
 # = 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
 [1] Ursula Hamenstädt. Bowen's construction for the Teichmüller flow. Journal of Modern Dynamics, 2013, 7 (4) : 489-526. doi: 10.3934/jmd.2013.7.489 [2] Martí Prats. Beltrami equations in the plane and Sobolev regularity. Communications on Pure & Applied Analysis, 2018, 17 (2) : 319-332. doi: 10.3934/cpaa.2018018 [3] Matteo Costantini, André Kappes. The equation of the Kenyon-Smillie (2, 3, 4)-Teichmüller curve. Journal of Modern Dynamics, 2017, 11: 17-41. doi: 10.3934/jmd.2017002 [4] Martin Möller. Shimura and Teichmüller curves. Journal of Modern Dynamics, 2011, 5 (1) : 1-32. doi: 10.3934/jmd.2011.5.1 [5] A. M. Micheletti, Angela Pistoia. Multiple eigenvalues of the Laplace-Beltrami operator and deformation of the Riemannian metric. Discrete & Continuous Dynamical Systems - A, 1998, 4 (4) : 709-720. doi: 10.3934/dcds.1998.4.709 [6] Micol Amar, Roberto Gianni. Laplace-Beltrami operator for the heat conduction in polymer coating of electronic devices. Discrete & Continuous Dynamical Systems - B, 2018, 23 (4) : 1739-1756. doi: 10.3934/dcdsb.2018078 [7] Lok Ming Lui, Tsz Wai Wong, Wei Zeng, Xianfeng Gu, Paul M. Thompson, Tony F. Chan, Shing Tung Yau. Detection of shape deformities using Yamabe flow and Beltrami coefficients. Inverse Problems & Imaging, 2010, 4 (2) : 311-333. doi: 10.3934/ipi.2010.4.311 [8] Lok Ming Lui, Chengfeng Wen, Xianfeng Gu. A conformal approach for surface inpainting. Inverse Problems & Imaging, 2013, 7 (3) : 863-884. doi: 10.3934/ipi.2013.7.863 [9] Dawei Chen. Strata of abelian differentials and the Teichmüller dynamics. Journal of Modern Dynamics, 2013, 7 (1) : 135-152. doi: 10.3934/jmd.2013.7.135 [10] Ursula Hamenstädt. Dynamics of the Teichmüller flow on compact invariant sets. Journal of Modern Dynamics, 2010, 4 (2) : 393-418. doi: 10.3934/jmd.2010.4.393 [11] Fei Yu, Kang Zuo. Weierstrass filtration on Teichmüller curves and Lyapunov exponents. Journal of Modern Dynamics, 2013, 7 (2) : 209-237. doi: 10.3934/jmd.2013.7.209 [12] Karol Mikula, Mariana Remešíková, Peter Novysedlák. Truss structure design using a length-oriented surface remeshing technique. Discrete & Continuous Dynamical Systems - S, 2015, 8 (5) : 933-951. doi: 10.3934/dcdss.2015.8.933 [13] Guizhen Cui, Yunping Jiang, Anthony Quas. Scaling functions and Gibbs measures and Teichmüller spaces of circle endomorphisms. Discrete & Continuous Dynamical Systems - A, 1999, 5 (3) : 535-552. doi: 10.3934/dcds.1999.5.535 [14] Andrea Bonito, Roland Glowinski. On the nodal set of the eigenfunctions of the Laplace-Beltrami operator for bounded surfaces in $R^3$: A computational approach. Communications on Pure & Applied Analysis, 2014, 13 (5) : 2115-2126. doi: 10.3934/cpaa.2014.13.2115 [15] Giovanni Forni, Carlos Matheus. Introduction to Teichmüller theory and its applications to dynamics of interval exchange transformations, flows on surfaces and billiards. Journal of Modern Dynamics, 2014, 8 (3&4) : 271-436. doi: 10.3934/jmd.2014.8.271 [16] Giovanni Forni. On the Brin Prize work of Artur Avila in Teichmüller dynamics and interval-exchange transformations. Journal of Modern Dynamics, 2012, 6 (2) : 139-182. doi: 10.3934/jmd.2012.6.139 [17] Alex Wright. Schwarz triangle mappings and Teichmüller curves: Abelian square-tiled surfaces. Journal of Modern Dynamics, 2012, 6 (3) : 405-426. doi: 10.3934/jmd.2012.6.405 [18] Anna Lenzhen, Babak Modami, Kasra Rafi. Teichmüller geodesics with $d$-dimensional limit sets. Journal of Modern Dynamics, 2018, 12: 261-283. doi: 10.3934/jmd.2018010 [19] Hsuan-Wen Su. Finding invariant tori with Poincare's map. Communications on Pure & Applied Analysis, 2008, 7 (2) : 433-443. doi: 10.3934/cpaa.2008.7.433 [20] Amadeu Delshams, Josep J. Masdemont, Pablo Roldán. Computing the scattering map in the spatial Hill's problem. Discrete & Continuous Dynamical Systems - B, 2008, 10 (2&3, September) : 455-483. doi: 10.3934/dcdsb.2008.10.455

2018 Impact Factor: 1.469