Area-preserving mesh parameterization for poly-annulus surfaces based on optimal mass transportation☆
Introduction
Surface parameterization (Hormann et al., 2008, Sheffer et al., 2007) refers to the process of mapping a surface embedded in to a canonical planar domain with minimal distortions, which has been utilized for a wide variety of applications (Sheffer et al., 2006) like remeshing (Floater and Reimers, 2001, Floater et al., 2002, Zhang et al., 2010), texture mapping (Dominitz and Tannenbaum, 2010, Lévy and Mallet, 1998, Lévy et al., 2002), morphing (Liu et al., 2008), and shape modeling (Sheffer et al., 2005, Floater, 1997, Floater and Hormann, 2005, Sheffer and Sturler, 2000).
In general, distortions can be classified to angle distortion and area distortion. If a parameterization has neither angle distortion nor area distortion, then it must be an isometric mapping, hence preserves Gaussian curvatures. In general, isometric mapping between a 3D surface and a planar domain doesn't exist. Therefore, in practice, research efforts focus on pursuing either angle-preserving parameterizations or area-preserving parameterizations.
Angle-preserving parameterizations preserve local shapes, therefore they are highly desirable for practical applications, such as texture mapping, visualization. Therefore, most existing algorithms emphasize on angle-preserving parameterizations. Many prominent approaches, such as conformal mapping, harmonic mapping and Ricci Flow that attempt to rigorously minimize the angular distortion have been introduced into the computer graphics community.
The angle-preserving mapping may bring huge area distortions in certain surfaces, for example, Fig. 2(b) shows large shrinkage of the lid of the world cup model. In fact, if one wants to conformally map a cylinder onto a planar annulus, the area distortion on the top is exponential with respect to the height of the cylinder. In turn, such distortions usually introduce much difficulty for the down streaming texture mapping and model processing. The exponential shrinkage makes the surface registration highly inaccurate, the geometric computation numerically unstable. In order to enlarge the insufficient texture area caused by the parameterization, topological surgeries need to be introduced, which makes the algorithm more complicated and less automatic.
Another surface parameterization approach is to minimize the area distortion. The most popular methods include quasi-area parameterization, Lie advection method and optimal mass transportation map method.
Quasi-area parameterization A simple and fast method for generating low-stretch mesh parameterizations is shown in Yoshizawa et al. (2004).
Given a parameterized triangle mesh , consider a mesh triangle and its corresponding triangle U in the parametric plane . The correspondence between the vertices of T and U uniquely defines an affine mapping .
Define, quantity characterizes the stretch of mapping P, where Γ and γ are the maximal and minimal eigenvalues of the metric tensor induced by the mapping P. For each vertex in the parameter domain, its stretch is defined by where denotes the area of triangle T and the sums are taken over all triangles surrounding mesh vertex corresponding to .
For each inner vertex its corresponding vertex , minimizes the local quadratic energy where are vertices corresponding to the mesh one-link neighbors of and are positive weights. The optimal positions for are found by solving a sparse system of linear equations Use the local stretch for each inner vertex in the parametric plane to estimate the weight by assigning
The optimization is achieved by minimizing a weighted quadratic energy with positive weights chosen to minimize the parameterization stretch. The quasi-area parameter is fast since it is based on solving a sparse system of linear equations. In contrast, our method has solid mathematical foundation. Our experimental results demonstrate that our method outperforms this method.
Lie advection The method in Zou et al. (2011) is based on Lie derivative and Cartan's formula. Given a surface S, the Lie advection method designs a time-variant tangent vector field on the surface , each point moves on the surface, at the time t the velocity vector of p is . Therefore, we obtain a single-parameter family of diffeomorphisms , such that Suppose the area element on the surface is ω, the mapping induces the pull-back area element, denoted as , then by Cartan's formula, the Lie derivative of ω where the inner product of v and the 2-form ω is a 1-form, . One can design the Lie derivative of ω to deform the current area element to the desired one, which is controlled by the vector field . Therefore, by designing the vector field, one can manipulate the evolution of the area element. This method can handle surfaces with complicated topologies, incorporating landmark constraints. The method has some disadvantages: the solution is not unique, and the iterative procedure of designing time variant vector field is indirect and less efficient.
Optimal mass transportation (OMT) Another approach to area-preserving parameterization is based on optimal mass transportation, which is also known as the “earth mover's problem” (Gu et al., 2016, Dominitz and Tannenbaum, 2010). Suppose and are two domains in the Euclidean space with measures μ and ν respectively, is a diffeomorphism. We say φ is measure preserving, if for any Borel set , we have equivalently, the PDE is given by where is the Jacobian of the mapping φ. The Optimal Mass Transportation map is a measure-preserving mapping, that minimizes the total transportation cost, namely, where is the transportation cost for moving one unit mass from p to q. There are mainly two approaches to solve OMT problem: one is Kantorovich's approach (Kantorovich, 1948), and the other is Brenier's approach (Brenier, 1991).
Kantorovich's approach discretizes both the source and the target as point sets with Dirac measures, and respectively, such that , a transportation plan can be represented as , which means the mass is moved from to , then the optimal mass transportation plan is a linear programming problem: This method has unknowns, and the solution mapping is not as smooth as those obtained by the alternative methods.
Brenier (1991) observes that if the cost function is the quadratic Euclidean distance , then there exists a convex function , such that the optimal mass transportation map is given by the gradient map of u, . In this case, the measure-preserving condition in Eqn. (1) becomes Monge–Ampère equation, The discrete OMT method discretizes the target as a point set with Dirac measures with only unknowns. This method is equivalent to a convex optimization process, which can be achieved using more efficient Newton's method, and the solution is unique.
Our approach Most existing optimal mass transportation method can only handle simply connected surfaces. An efficient method to compute area-preserving parameterizations for surfaces with complex topologies is highly advantageous for texture mapping and visualization in research area. In our current work, we propose a novel area-preserving parameterization algorithm, which is based on discrete optimal mass transportation (Gu et al., 2016) theory, and therefore it is equivalent to a convex optimization, with a unique solution. Furthermore, it is capable of handling genus zero surfaces with multiple boundaries (topological annuli).
Our method is as follows: first, the input topological annulus is conformally mapped onto a circle domain using discrete Ricci flow method (Chow and Luo, 2003), where and is the disk centered at with radius . Because φ is conformal, the original Riemannian metric on the surface . On the unit disk, we define a measure , where are two adjustable constants, such that . Then we compute the unique optimal mass transportation map . The composition is the desired area-preserving parameterization. Fig. 1 illustrates the pipeline of our approach.
Conformal parameterization The literature for conformal mesh parameterization is vast, and a complete review is beyond the scope of the current work. We refer readers to the thorough surveys Floater and Hormann (2005), Sheffer et al. (2006) and Sheffer et al. (2007). Many existing parameterizations focus on minimizing angle distortion, such as the method based on Riemann–Cauchy equation (Lévy et al., 2002), harmonic energy minimization (Desbrun et al., 2002), holomorphic differentials (Gu and Yau, 2003), most isometric parameterizations (MIPS) (Hormann et al., 1999), angle-based flattening (Sheffer and de Sturler, 2001), conformal equivalence meshes (Springborn et al., 2008), curvature flows (Jin et al., 2008), conformal equivalence (Springborn et al., 2008), spin transformation (Crane et al., 2011) and so on.
Locally injective and bounded distortion mappings Schüller et al. (2013) modify any deformation energy to guarantee a locally injective mapping. Levi and Zorin prioritize higher distortion for minimization and provide a minimal -norm solution for distortion control (Levi and Zorin, 2014). Fu et al. introduce an advanced MIPS method that inherits the local injectivity of MIPS, achieves as low as possible distortions with high efficiency. Their method depends on an enhanced MIPS energy function that penalizes the maximal distortion and distributes the distortion evenly, and the inexact block coordinate descent method that avoids local optima.
Lipman (2012), Aigerman and Lipman (2013), Kovalsky et al., 2014, Kovalsky et al., 2015 propose to construct a maximal convex subspace, which is the continuous piecewise linear mapping space for bounding the maximal distortion and ensuring no inverted mesh elements. Locally injective mapping with bounded distortion is guaranteed when the algorithms converge. The algorithm is iterative, a quadratic programming or semidefinite programming problem needs to solve at each step. A feasible solution space may not exist if the convex subspace is empty or the upper bound of distortion is too small. In contrast, our method has theoretical advantages that the solution exists and is unique, the algorithm converges to the unique global optimum.
Optimal mass transport
(a) Monge–Kantorovich For optimal mass transport, some approaches based on Monge–Kantorovich theory have been proposed. Zhu et al. (2003) applied optimal mass transport for flattening blood vessel in an area preserving mapping for medical visualization. Haker et al. (2004) proposed to use optimal mass transport for image registration and warping, the method is parameter free and has the unique global optimum. Dominitz and Tannenbaum (2010) proposed to use optimal mass transport for texture mapping. The method first starts with an angle-preserving mapping and then refines the mapping using the mass transport procedure derived via gradient flow. Rehman et al. (2009) presented a method for 3D image registration based on optimal mass transport problem. Meanwhile, they stress the fact that the optimization of OMT is computationally expensive and emphasize that it is important to find efficient numerical methods to solve this issue, and it is crucial to extend the results to 3D surfaces.
(b) Monge–Brenier There are also some works based on Monge–Brenier theory. Su et al. proposed an area-preserving mapping method for brain morphological study. Zhao et al. proposed an OMT based method for visualization in Zhao et al. (2013). But these methods can only compute the maps from the unit disk domain with Euclidean measure to another disk with general measure.
Mérigot (2011) has proposed a multi-scale approach to solve optimal transport problem. De Goes et al. (2011) have provided an optimal-transport driven approach for 2D shape reconstruction and simplification. Recently they have presented a formulation of capacity-constrained Voronoi tessellation as an optimal transport problem for image processing (de Goes et al., 2012). This method produces high-quality blue noise point sets with improved spectral and spatial properties.
In summary, the current work has the following contributions:
- •
This work offers an area-preserving surface parameterization method that is able to handle complicated topologies, such as genus zero surfaces with multiple boundaries.
- •
The mapping is diffeomorphic and unique under normalization. Moreover, the mapping is invariant under conformal transformations.
- •
Comparing to existing approaches based on Monge–Kantorovich theory, our method reduces the number of unknown variables from to .
The outline of the remainder of this paper is as follows: In Section 2, we demonstrate the theoretical foundation of Ricci Flow and optimal mass transportation. In Section 3, we discuss some relevant implementation issues. In Section 4, we give some illustrative examples of our scheme, and present an evaluation of the running time and distortion measures of our method, compare with stretch minimization method (Yoshizawa et al., 2004). Finally, in Section 5, we summarize our work and give some possible future research directions.
Section snippets
Theoretical foundation
In this section, we briefly introduce the theoretic foundations of the current work. We refer readers to more thorough treatments on Ricci flow (Zeng and Gu, 2013) and Optimal mass transportation theory (Gu et al., 2016).
Algorithm
This section explains the details of the computational algorithms.
Experimental results
In this section, we demonstrate the efficiency and efficacy of our method using examples from the real world.
All the experiments were conducted on a laptop computer of Intel Core i5-4200U CPU, 2.29 GHz with 8 GB memory. All the algorithms are implemented using generic C++ with visual studio 2013 on Windows 10 platform.
Conclusion
This work proposes a novel parameterization method, based on discrete surface Ricci flow and optimal mass transportation theories. The algorithm is capable of finding area-preserving parameterizations for genus zero surfaces with multiple boundaries. The achieved mapping is diffeomorphic and invariant under conformal transformations. Conventional Kantorovich's approach has unknown variables, whereas the proposed method has only variables, where n is the number of vertices on the
Acknowledgements
This work was supported by National Natural Science Foundation (Grant Nos. DMS-1418255, DMS-1221339), AFOSR FA9550-10-1-0294, AFOSR FA955014-1-0193, National Natural Science Foundation of China (Grant No. 61328206, No. 11271156, No. 11001017) and Ph.D. Programs Foundation of Ministry of Education of China (No. 20120141120006). The authors are also grateful to anonymous referees for their helpful comments and suggestions.
References (47)
Parametrization and smooth approximation of surface triangulations
Comput. Aided Geom. Des.
(1997)- et al.
Meshless parameterization and surface reconstruction
Comput. Aided Geom. Des.
(2001) - et al.
Mesh reconstruction by meshless denoising and parameterization
Comput. Graph.
(2010) - et al.
Injective and bounded distortion mappings in 3d
ACM Trans. Graph.
(2013) Convex Polyhedra
(2005)- et al.
Minkowski-type theorems and least-squares clustering
Algorithmica
(1998) Polar factorization and monotone rearrangement of vector-valued functions
Commun. Pure Appl. Math.
(1991)- et al.
Combinatorial Ricci flow on surfaces
J. Differ. Geom.
(2003) - et al.
Spin transformations of discrete surfaces
ACM Trans. Graph.
(2011) - et al.
An optimal transport approach to robust reconstruction and simplification of 2d shapes
Blue noise through optimal transport
ACM Trans. Graph.
Intrinsic parameterizations of surface meshes
Comput. Graph. Forum
Texture mapping via optimal mass transport
IEEE Trans. Vis. Comput. Graph.
Surface parameterization: a tutorial and survey
Parameterization of manifold triangulations
Global conformal surface parameterization
A discrete uniformization theorem for polyhedral surfaces
Variational principles for Minkowski type problems, discrete optimal transport, and discrete Monge–Ampère equations
Asian J. Math.
Optimal mass transport for registration and warping
Int. J. Comput. Vis.
Hierarchical parametrization of triangulated surfaces
Mesh parameterization: theory and practice
Discrete surface Ricci flow
IEEE Trans. Vis. Comput. Graph.
On a problem of Monge
Usp. Mat. Nauk
Cited by (56)
A novel explicit design method for complex thin-walled structures based on embedded solid moving morphable components
2023, Computer Methods in Applied Mechanics and EngineeringArea-Preserving Hierarchical NURBS Surfaces Computed by the Optimal Freeform Transformation
2022, CAD Computer Aided DesignCitation Excerpt :Area-preserving parameterizations preserve the area element when an elementary area of the parametric domain is mapped to an elementary area of the surface [10–12].
Fundamental theory and R-linear convergence of stretch energy minimization for spherical equiareal parameterization
2024, Journal of Numerical MathematicsArea-Preserving Parameterization with Tutte Regularization
2023, Communications in Mathematics and Statistics
- ☆
This paper has been recommended for acceptance by Rida Farouki.