Abstract
Conformal mapping, a classical topic in complex analysis and differential geometry, has become a subject of great interest in the area of surface parameterization in recent decades with various applications in science and engineering. However, most of the existing conformal parameterization algorithms only focus on simply-connected surfaces and cannot be directly applied to surfaces with holes. In this work, we propose two novel algorithms for computing the conformal parameterization of multiply-connected surfaces. We first develop an efficient method for conformally parameterizing an open surface with one hole to an annulus on the plane. Based on this method, we then develop an efficient method for conformally parameterizing an open surface with k holes onto a unit disk with k circular holes. The conformality and bijectivity of the mappings are ensured by quasi-conformal theory. Numerical experiments and applications are presented to demonstrate the effectiveness of the proposed methods.
Similar content being viewed by others
Avoid common mistakes on your manuscript.
1 Introduction
The goal of surface parameterization is to map a surface in \(\mathbb {R}^3\) onto a simple standardized domain. Over the past few decades, surface parameterization algorithms have been extensively studied [1,2,3]. In general, any parameterization will unavoidably induce angle and/or area distortions. Therefore, it is common to consider conformal parameterizations, which preserve angles and hence the local geometry of the surfaces. Existing conformal parameterization methods include harmonic energy minimization [4, 5] and its linearizations [6,7,8], least-square conformal map (LSCM) [9], discrete natural conformal parameterization (DNCP) [10], holomorphic 1-form [11], Yamabe flow [12], angle-based flattening (ABF) [13, 14], circle patterns [15], discrete conformal equivalence [16], Ricci flow [17,18,19,20], spectral conformal map [21], curvature prescription [22], zipper algorithms [23, 24], boundary first flattening [25], conformal energy minimization [26] etc. In recent years, quasi-conformal theory has emerged as a useful tool for the development of surface parameterization methods [27, 28] with applications to image and video processing [29, 30], geometry processing and graphics [31,32,33,34,35], metamaterial design [36], medical visualization [37, 38] and biological shape analysis [39,40,41]. However, most of the above-mentioned conformal parameterization methods only work for simply-connected surfaces, which do not contain any holes.
For multiply-connected surfaces with annulus or poly-annulus topology, the computation of conformal maps is more complicated. Some earlier works have considered mapping a multiply-connected open surface onto a circular domain with concentric circular slits [42, 43]. Also, by the Koebe’s uniformization theorem, any multiply-connected open surface with k holes can be conformally mapped to a unit disk with k circular holes [44]. Based on this remarkable result, a few parameterization algorithms have been developed for multiply-connected open surfaces using Ricci flow [17], holomorphic 1-form [45], Laurent series [46], Beltrami energy minimization [47], discrete conformal equivalence [48] etc.
In this work, we propose two novel algorithms for computing the conformal parameterization of multiply-connected surfaces using quasi-conformal theory. We first propose an efficient method for conformally mapping an open surface with one hole (i.e. a topological annulus) to an annulus domain with unit outer radius (Fig. 1, left). We then utilize this method to develop another fast algorithm for conformally mapping a multiply-connected open surface with k holes (i.e. a topological poly-annulus) to a unit disk with k circular holes (Fig. 1, right). With the aid of quasi-conformal theory, we can effectively achieve the conformality and bijectivity of the parameterizations.
The rest of the paper is organized as follows. In Sect. 2, we review the concepts of conformal and quasi-conformal maps. In Sect. 3, we describe our proposed methods for the conformal parameterization of multiply-connected surfaces. In Sect. 4, we demonstrate the effectiveness of our parameterization methods using numerical experiments. Applications of the proposed methods are explored in Sect. 5. We conclude the paper and discuss possible future directions in Sect. 6.
2 Mathematical Background
In this section, we review some mathematical concepts related to our work. Readers are referred to [49,50,51] for more details.
2.1 Conformal Map
Let \(f: \mathbb {C}\rightarrow \mathbb {C}\) be a map with \(f(z) = f(x,y) = u(x,y)+iv(x,y)\), where u, v are real-valued functions. f is said to be a conformal map if it satisfies the Cauchy–Riemann equations:
Möbius transformations are a special class of conformal maps on the complex plane. Mathematically, a Möbius transformation \(f:\mathbb {C}\rightarrow \mathbb {C}\) is in the form
with \(a,b,c,d\in \mathbb {C}\) satisfying \(ad-bc\ne 0\).
2.2 Quasi-Conformal Map
Quasi-conformal maps are a generalization of conformal maps. Mathematically, a mapping \(f:\mathbb {C} \rightarrow \mathbb {C}\) is said to be a quasi-conformal map if it satisfies the Beltrami equation
for some complex-valued function \(\mu _f\) with \(\Vert \mu _f\Vert _\infty <1\), where the complex derivatives are given by
Here, \(\mu _f\) is called the Beltrami coefficient of f. Note that if \(\mu _f \equiv 0\), then Eq. (3) becomes the Cauchy–Riemann equations (1) and hence f is conformal.
Intuitively, conformal mappings map infinitesimal circles to infinitesimal circles, while quasi-conformal mappings map infinitesimal circles to infinitesimal ellipses with bounded eccentricity. To see this, consider the first order approximation of f around a point \(z_0 \in \mathbb {C}\):
This indicates that an infinitesimal circle centered at \(z_0\) is mapped to an infinitesimal ellipse centered at \(f(z_0)\), with the maximum magnification \(|f_z(z_0)|(1+|\mu _f(z_0)|)\) and the maximum shrinkage \(|f_z(z_0)|(1-|\mu _f(z_0)|)\) (see Fig. 2 for an illustration). The aspect ratio of the ellipse is then given by \(\frac{1+|\mu _f(z_0)|}{1-|\mu _f(z_0)|}\). Therefore, the Beltrami coefficient effectively captures the conformal distortion of its associated mapping.
The Beltrami coefficient is also closely related to the bijectivity of the mapping. Note that if \(f(x,y) = u(x,y) + i v(x,y)\), then the Jacobian \(J_f\) of f is given by
Therefore, we have the following result:
Theorem 1
If f is a \(C^1\) map satisfying \(\Vert \mu _f\Vert _{\infty } <1\), then f is bijective.
Besides, the Beltrami coefficient of a composition of two quasi-conformal maps can be expressed explicitly. Let \(f: \varOmega _1 \rightarrow \varOmega _2\) and \(g: \varOmega _2 \rightarrow \varOmega _3\) be two quasi-conformal maps. The Beltrami coefficient of the composition map \(g \circ f\) is given by
In particular, if \(\mu _{f^{-1}} \equiv \mu _g\), we have
and hence
which implies that the composition map \(g \circ f\) is conformal. This suggests that one can eliminate the conformal distortion of a quasi-conformal map by composing it with another quasi-conformal map with the same Beltrami coefficient, provided that the boundary constraint is admissible. This idea of quasi-conformal composition [6] will be used in our proposed methods for the computation of conformal parameterizations.
While the above concepts are introduced in terms of mappings on the complex plane, they can be naturally extended for Riemann surfaces with the aid of local charts.
2.3 Linear Beltrami Solver (LBS)
Lui et al. [29] developed a linear method called the Linear Beltrami Solver (LBS) for computing a quasi-conformal map \(f(x,y) = u(x,y) + iv(x,y)\) with a given Beltrami coefficient \(\mu (x,y) = \rho (x,y) + i \eta (x,y)\). The idea is to consider the real and imaginary parts in the Beltrami Eq. (3) separately:
from which we can express \(v_x\) and \(v_y\) as linear combinations of \(u_x\) and \(u_y\):
where
Similarly, we can express \(u_x\) and \(u_y\) as linear combinations of \(v_x\) and \(v_y\):
Since \((v_y)_x + (-v_x)_y = 0\) and \((-u_y)_x + (u_x)_y = 0\), from Eq. (11) and Eq. (13) we have
where \(A = \left( \begin{array}{cc} \alpha _1 &{} \alpha _2\\ \alpha _2 &{} \alpha _3 \end{array}\right) \). In the discrete case, Eq. (14) can be discretized as two sparse symmetric positive definite linear systems. Therefore, one can easily obtain \(u_x, u_y, v_x, v_y\) (and hence the quasi-conformal map f) for any given \(\mu \) by solving two linear systems with certain boundary constraints (see [29] for details). We denote the above procedure by \(f = \mathbf{LBS} (\mu )\).
3 Proposed Methods
Below, we first develop an efficient algorithm for conformally parameterizing an open surface with one hole onto a planar annulus. We then utilize this algorithm to develop another efficient method for conformally parameterizing a multiply-connected open surface with k holes onto a unit disk with k circular holes.
3.1 Annulus Conformal Map for Open Surfaces with One Hole
Let S be an open surface in \(\mathbb {R}^3\) with one hole, i.e. a topological annulus. Denote the surface boundary as \(\partial S = \gamma _0 - \gamma _1\), where \(\gamma _0\) is the outer boundary and \(\gamma _1\) is the inner boundary. Our goal is to find a conformal parameterization \(f:S \rightarrow \mathbb {C}\) that maps S to an annulus on the plane with unit outer radius. The proposed method is outlined in Fig. 3.
To begin, we take an arbitrary vertex at the inner boundary \(\gamma _1\) and find a shortest path from it to the outer boundary \(\gamma _0\). By slicing S along the path, we obtain a simply-connected open surface \(\tilde{S}\) (see the red curve in Fig. 3, second left). Due to the change in the surface topology, it is possible to map \(\tilde{S}\) onto a planar domain without holes. As for the reason of using a shortest path, note that the cut path between the two vertices corresponds to the two boundary edges connecting the left and right corners of the rectangle as illustrated in Fig. 3. Since the two edges are the geodesics between the corners, the shortest path between the two corresponding vertices in the input mesh is a natural choice for the cut path. Also, as the corners of the rectangle are enforced to be with angle \(=\pi /2\), using a shortest path can help reduce the angular distortion there in the discrete case.
Now, we consider mapping \(\tilde{S}\) onto a strip conformally (see Fig. 3, middle). Meng et al. [28] developed an efficient rectangular conformal mapping algorithm based on the LBS method [29]. The algorithm first computes an initial flattening map of the input surface onto the unit disk. It then maps the disk to the unit square using the LBS method. In particular, four boundary vertices are chosen as the four corners of a unit square, and an optimal quasi-conformal map is computed for mapping the remaining vertices onto the square domain. Finally, it keeps the length of the square domain fixed and optimally rescale the width of it so as to achieve a rectangular conformal map. Here, we follow the approach in [28] with some modifications for obtaining the conformal map onto a strip.
We first compute a disk harmonic map \(\phi :\tilde{S} \rightarrow \mathbb {D}\) by solving the following Laplace equation
where the boundary constraint is given by the arc-length parameterization. More explicitly, denote \(\{p_i\}_{i=1}^n\) as the boundary vertices of \(\tilde{S}\) in anti-clockwise order. For every i, we map \(p_i\) to a point \((\cos \theta _i, \sin \theta _i)\) on the unit circle, where \(\theta _1 = 0\), and \(\theta _2, \theta _3, \dots , \theta _n\) are determined using the boundary edge lengths:
Here, \(l_{[p_j, p_{j+1}]}\) is the length of the edge \([p_j, p_{j+1}]\), and \(p_{n+1} = p_0\). The Laplacian \(\varDelta \) is the Laplace–Beltrami operator on \(\tilde{S}\), which can be easily discretized using the cotangent formulation [4]. After flattening the sliced surface onto the unit disk, we compute a quasi-conformal map \(\psi :\mathbb {D} \rightarrow R = [0,L] \times [0,1]\) from the unit disk to a rectangular domain with length L and unit width, where L is to be determined. In particular, we use the LBS method with the target Beltrami coefficient being \(\mu _\psi = \mu _{\phi ^{-1}}\):
where the four vertices on \(\partial \tilde{S}\) that correspond to the endpoints of the cut path are set to be the four corners of the target rectangular domain. More explicitly, denote \(p, p'\) as the two vertices on \(\partial \tilde{S}\) that correspond to the endpoint at the inner boundary \(\gamma _1\), and \(q, q'\) as the two vertices on \(\partial \tilde{S}\) that correspond to the endpoint at the outer boundary \(\gamma _0\). The four corners of R are set as follows (see Fig. 3):
Note that by Eq. (9), the conformal distortion of the quasi-conformal composition \(\psi \circ \phi \) can be significantly reduced given an appropriate boundary constraint. In the original formulation [28], the boundary vertices are allowed to freely slice along the sides of the rectangular domain to achieve conformality. However, in our case, the top and bottom sides of R correspond to the cut path and are with equal number of corresponding vertices (see the two red curves in Fig. 3, middle). To enforce their positional consistency, we impose a periodic boundary constraint on the x-coordinates of the top and bottom boundary vertices. As for the choice of L, we start with an initial guess \(L=1\) and compute the map \(\psi \) using Eq. (17). Then, we search for the optimal L which minimizes the norm of the Beltrami coefficient of \(\psi \circ \phi \) to further reduce the conformal distortion.
Here we remark that one may look for an extra shear transformation \(\begin{pmatrix} x \\ y \end{pmatrix} \mapsto \begin{pmatrix} 1 &{} 0 \\ a &{} 1 \end{pmatrix} \begin{pmatrix} x \\ y \end{pmatrix}\) to transform R into a parallelogram, such that the two bottom corner points do not necessarily have the same y-coordinates. Theoretically, this can help further reduce the conformal distortion of the mapping. However, as the cut path is chosen to be a shortest path, we find that the optimal a is usually very small (with \(|a| \sim 10^{-4}\)) in our experiments and the improvement in the conformality is negligible. Therefore, this step can be skipped in practice.
After getting the rectangular parameterization \(\psi \circ \phi \), we apply the exponential map
which maps the rectangular domain \([0,L] \times [0,1]\) to an annulus with inner radius \(e^{-2\pi L}\) and outer radius 1. Because of the periodicity imposed in the computation of the rectangular parameterization, the top and bottom boundaries (i.e. the cut path vertices) are mapped to consistent locations on the annulus domain. We can then identify every pair of them and obtain a seamless mapping result (see Fig. 3, second right).
Finally, we use the quasi-conformal composition to further improve the conformality of the annulus map. Specifically, we compute an automorphism \(\zeta \) on the annulus \((\eta \circ \psi \circ \phi )(S)\) with
where all boundary vertices are fixed. This results in the final annulus conformal parameterization \(f = \zeta \circ \eta \circ \psi \circ \phi \) (see Fig. 3, rightmost). We remark that by the quasi-conformal composition, the Beltrami coefficient of the resulting map is with supremum norm less than 1 and hence is bijective.
The proposed annulus conformal map (ACM) algorithm is summarized in Algorithm 1.
3.2 Poly-annulus Conformal Parameterization of Multiply-Connected Open Surfaces with k Holes
Let S be a multiply-connected open surface in \(\mathbb {R}^3\) with k holes, i.e. a topological poly-annulus. Denote the surface boundary as \(\partial S = \gamma _0 - \gamma _1 - \gamma _2 - \cdots - \gamma _k\), where \(\gamma _0\) is the outer boundary and \(\gamma _1, \cdots , \gamma _k\) are the inner boundaries. Our goal is to find a conformal parameterization \(f:S \rightarrow \mathbb {D}\) that maps S to the unit disk with k circular holes. The proposed method is outlined in Fig. 4.
Analogous to the Koebe’s iteration method [44, 45], our method handles the k holes of the surface S one by one. We first fill all but the first holes to get a surface \(S_1\) with annulus topology. In practice, one can simply fill a hole by adding a new vertex at the center of the hole and including its one-ring neighborhood of triangular faces. We can then apply the proposed ACM method (Algorithm 1) with the the quasi-conformal composition step (Line 5 in Algorithm 1) skipped to obtain an annulus map \(g_1:S_1 \rightarrow \mathbb {C}\), with \(\gamma _0\) and \(\gamma _1\) mapped to the outer circle and the inner circle respectively. After that, we remove all filled regions to restore the surface topology. Here, we remark that the quasi-conformal composition step is skipped for simplifying the computational procedure. As shown in Fig. 3, the quasi-conformal composition primarily improves the conformality near the cut path, while the conformality of all other regions is largely unaffected. Therefore, we can leave the quasi-conformal composition step to the last part of the poly-annulus parameterization, which allows us to correct the conformal distortion in one solve instead of k solves.
By repeating the above process for handling all the remaining holes, we obtain the composition map \(g_k \circ g_{k-1} \circ \cdots \circ g_1\). Here, note that each time one new hole is enforced to be a perfect circle, and in fact the circularity of the previously handled holes is also largely preserved. The reason is that the hole filling procedure involves adding a new vertex at the center of those holes together with a ring of triangles, and hence each of the subsequent annulus maps (which is highly conformal at most places even without the quasi-conformal composition step) will preserve the angles in the entirely filled shape including those in the filled holes as much as possible, thereby effectively preventing the previously handled holes from being largely distorted in circularity.
More specifically, consider a hole which has been mapped to a small circle and denote its vertices as \(w_1, w_2, \dots , w_n\). Since the hole is circular, the new vertex added to that hole in the next hole filling procedure (denoted as O) is the center of the small circle (see Fig. 5, left), which implies that O is equidistant from all \(w_j\):
It is then straightforward to see that \(\angle Ow_j w_{j+1} = \angle Ow_{j+1} w_{j}\) for all j in the newly added ring of triangles. Now, suppose the vertices are mapped to \(w_1', w_2', \dots , w_n', O'\) under the next annulus map (see Fig. 5, right). As the annulus map is highly conformal, for every j we should have
and hence \(l_{[O', w_j']} \approx l_{[O', w_{j+1}']}\) for all j . It follows that \(O'\) is approximately equidistant from all \(w_j'\), which implies that the hole formed by \(w_1', w_2', \dots , w_n'\) is close to a circle. One can then repeat the above argument at all subsequent steps to show that the hole will continue to be approximately circular. In other words, by the property of the hole filling procedure and the annulus map, every hole will remain approximately circular once it has been enforced to be a circle at a certain step. While the holes may not all be perfectly circular as numerical errors may accumulate throughout the entire process, an extra step of further enforcing the circularity will be added later.
Now, note that the k-th hole of S is mapped to the center of the unit disk. Since this may not follow the distribution of the holes on S well, the area distortion of the map may be large. To alleviate this issue, we use the Möbius area correction scheme [24] to reduce the area distortion of the map while preserving conformality, thereby ensuring that the holes are at appropriate locations on the planar domain. More explicitly, we search for an optimal automorphism \(\tau _{\alpha }\) on the unit disk in the following form:
where \(\alpha \in \mathbb {C}\) with \(|\alpha |<1\), such that the composition \(\tau _{\alpha } \circ g_k \circ g_{k-1} \circ \cdots \circ g_1\) minimizes the area distortion of the parameterization with respect to the input surface.
As discussed above, all the k holes become close to circles under the annulus mapping steps but they may not all be perfectly circular. Also, while Möbius transformations map circles and straight lines to circles and straight lines in theory, in the discrete case they may cause a small distortion in the circularity of the holes. Therefore, we add a step of enforcing the circularity of the holes via projections. More specifically, for each hole \((\tau _{\alpha } \circ g_k \circ g_{k-1} \circ \cdots \circ g_1)(\gamma _i)\), we find the maximum inscribed circle of it and project all boundary vertices onto this circle. After performing this operation for all k holes, we obtain a unit disk with k circular holes. We denote the process by \(\rho : \mathbb {D} \rightarrow \mathbb {D}\).
Finally, we use the quasi-conformal composition to further reduce the conformal distortion caused by the annulus mapping steps and the projection step. We compute an automorphism h on the unit disk with the Beltrami coefficient \(\mu _{(\rho \circ \tau _{\alpha } \circ g_k \circ g_{k-1} \circ \cdots \circ g_1)^{-1}}\) using the LBS method [29]:
where all boundary vertices are fixed. By the composition formula in Eq. (9), the composition \(f = h \circ \rho \circ \tau _{\alpha } \circ g_k \circ g_{k-1} \circ \cdots \circ g_1\) gives a conformal parameterization of S onto the unit disk with exactly k circular holes. Similar to Algorithm 1, the quasi-conformal composition here also ensures that the Beltrami coefficient of the resulting map is with supremum norm less than 1 and hence is bijective.
The proposed conformal parameterization method for poly-annulus surfaces is summarized in Algorithm 2.
4 Experimental Results
The proposed conformal parameterization algorithms are implemented in MATLAB. The linear systems are solved using the backslash operator (\(\backslash \)) in MATLAB. For the step of mesh slicing in Algorithm 1, we use the MATLAB function graphshortestpath to compute a shortest path between the arbitrary vertex at the inner boundary \(\gamma _1\) and the closest vertex at the outer boundary \(\gamma _0\) of the input triangular mesh. For the rectangular conformal map in Algorithm 1, we use the MATLAB function fminbnd to search for the optimal length L of the rectangular domain. For the Möbius transformation in Eq. (23) in Algorithm 2, we write \(\alpha = re^{i\theta }\) and use the MATLAB function fmincon to search for the optimal parameters \((r,\theta ) \in [0,1] \times [0, 2\pi ]\). For the step of finding maximum inscribed circles of the holes, we use the function find_inner_circle available in the MATLAB Central FileExchange [52]. All experiments are performed on a PC with a 4.0 GHz quad core CPU and 16 GB RAM. To assess the conformality of a parameterization \(f:S \rightarrow \mathbb {C}\), we consider the angular distortion of every angle \([v_i,v_j,v_k]\) on the surface mesh under the parameterization:
For an ideal conformal map, we should have \(d = 0\) for all angles.
Figure 6 shows several surfaces with annulus topology and the annulus conformal parameterizations achieved by our proposed ACM method. Note that our method is capable of handling surfaces with a highly non-convex hole (see the top example) as well as surfaces with a highly tubular geometry (see the bottom example). From the histograms of the angular distortion d, it can be observed that the parameterizations are highly conformal. For comparison, we consider the Ricci flow (RF) method [17] with implementation available in the RiemannMapper toolbox [53]. Table 1 records the computation time and the conformal distortion of our proposed ACM method and the RF method, from which it can be observed that our method outperforms the RF method in both the conformality and efficiency. The improvement in the conformality can be explained by that the RF method is based on the circle packing metric, which is highly dependent on the quality of the triangulations. For surface meshes with coarse or irregular triangulations, the approximation of the metric may be inaccurate, thereby yielding a large conformal distortion in the parameterization results. By contrast, our method effectively reduces the conformal distortion using the idea of quasi-conformal composition. As for the improvement in the efficiency, note that the RF method uses a gradient descent approach for minimizing the Ricci energy and hence is time-consuming, while our method only involves solving a few linear systems and a one-dimensional optimization problem.
Figure 7 shows the poly-annulus conformal parameterizations of several multiply-connected open surfaces achieved by our proposed PACM method. It can be observed that our method works well for surfaces with different size, shape, and number of holes. For a more quantitative analysis, we again compare our method with the RF method in terms of the computation time and the angular distortion. As shown in Table 2, our method achieves a significant improvement in both the efficiency and conformality when compared to the RF method. Therefore, our method is more advantageous for the computation of the poly-annulus conformal parameterization.
5 Applications
5.1 Texture Mapping
The proposed conformal parameterization methods can be effectively applied to texture mapping. Using our methods, any multiply-connected open surface in \(\mathbb {R}^3\) can be conformally mapped onto a unit disk with circular holes. Textures can then be designed on the plane and mapped back onto the surface easily. As our methods are angle-preserving, the local geometry of the designed textures will be well-preserved. Also, as our methods produce global parameterizations of the surfaces, the texture mapping results will be seamless. Figure 8 shows two texture mapping results produced using our parameterization methods. The orthogonality of the checkerboard patterns on the surfaces indicates that our parameterizations are highly conformal.
5.2 Surface Remeshing
The proposed conformal parameterization methods can also be applied to surface remeshing. Suppose we would like to improve the mesh quality of a given multiply-connected surface. A simple way is to map it onto the unit disk with circular holes using our parameterization methods, and then perform the remeshing process on the plane.
In particular, DistMesh [54] is a powerful toolbox for generating triangular meshes, which uses signed distance functions to specify the geometry of the domain and control the mesh quality. In our case, the disk domain with circular holes can be easily expressed as a difference between signed distance functions for several circles using the ddiff and dcircle functions in DistMesh. The target mesh quality is set using a scaled edge length function in DistMesh, which can also be easily controlled using the signed distance functions for circles. Therefore, our parameterization methods can be naturally combined with DistMesh for the remeshing task. Once a new planar mesh is generated, we can map it back to the surface via the parameterization. Figure 9 shows two examples of remeshing a multiply-connected human face surface, from which it can be observed that different remeshing effects can be easily achieved. As the parameterization is angle-preserving, the regularity of the triangles in the new planar meshes is well-preserved in the final remeshed surfaces.
5.3 Surface Registration
Another possible application of the proposed conformal parameterization methods is multiply-connected surface registration [55]. As shown in Fig. 10, given two multiply-connected open surfaces (denoted as \(S_1\) and \(S_2\)) with the same topology, we can first compute the poly-annulus conformal parameterizations (denoted as \(f_1\) and \(f_2\)) of them using our proposed methods. Then, we can compute a quasi-conformal map g between the two planar domains \(f_1(S_1)\) and \(f_2(S_2)\) with all corresponding holes exactly matched using the LBS method. The composition \(f_2^{-1} \circ g \circ f_1\) then gives a registration mapping between the surfaces \(S_1\) and \(S_2\). From the final registration result in Fig. 10, it can be observed that the two multiply-connected surfaces are matched very well.
6 Discussion
With the advancement in computer technology, there has been a surge of interest in the development of conformal parameterization algorithms for science and engineering applications in recent decades. However, most of the existing methods only work for simply-connected surfaces. In this work, we have proposed two novel algorithms for the conformal parameterization of multiply-connected surfaces onto either an annulus or a unit disk with circular holes using quasi-conformal theory. As there are a vast number of analytical and numerical conformal mapping methods for multiply-connected planar domains [56,57,58,59,60], the proposed parameterization algorithms pave the way for applying these methods to multiply-connected surfaces. For instance, the prime function has been used for solving various applied and natural science problems on multiply-connected planar domains [61]. With the aid of our proposed parameterization algorithms, it may be possible to extend the method to Riemann surfaces.
Besides the applications discussed in this work, it is natural to explore the use of the proposed conformal parameterization methods for shape analysis [62, 63], greedy routing in sensor networks [64] etc. Also, note that both the proposed poly-annulus conformal parameterization method in this work and the conventional Koebe’s iteration method rely on a series of annulus mappings for producing the final result. Alternatively, as shown in the recent discrete conformal equivalence approach [48], the poly-annulus parameterization can be achieved by gluing faces to all but one boundary component and constructing a discrete conformal map using discrete conformal equivalence of cyclic polyhedral surfaces. A possible future direction would be to adopt a similar strategy to further simplify the computational procedure of our method. Another possible future direction is to combine the proposed methods with the optimal mass transport (OMT) [65,66,67,68] or the density-equaling map (DEM) [69, 70] for efficiently computing area-preserving parameterizations of multiply-connected surfaces.
Data availability
The data are available from the corresponding author on request.
References
Floater, M.S., Hormann, K.: Surface parameterization: a tutorial and survey. In: Advances in Multiresolution for Geometric Modelling, pp. 157–186, Springer (2005)
Sheffer, A., Praun, E., Rose, K.: Mesh parameterization methods and their applications. Found. Trends Comput. Graph. Vis. 2(2), 105–171 (2006)
Hormann, K., Lévy, B., Sheffer, A.: Mesh parameterization: theory and practice. In: ACM SIGGRAPH 2007 Courses. Association for Computing Machinery, New York, NY, USA (2007)
Pinkall, U., Polthier, K.: Computing discrete minimal surfaces and their conjugates. Exp. Math. 2(1), 15–36 (1993)
Gu, X., Wang, Y., Chan, T.F., Thompson, P.M., Yau, S.-T.: Genus zero surface conformal mapping and its application to brain surface mapping. IEEE Trans. Med. Imaging 23(8), 949–958 (2004)
Choi, P.T., Lam, K.C., Lui, L.M.: FLASH: Fast landmark aligned spherical harmonic parameterization for genus-0 closed brain surfaces. SIAM J. Imaging Sci. 8(1), 67–94 (2015)
Choi, G.P.-T., Ho, K.T., Lui, L.M.: Spherical conformal parameterization of genus-0 point clouds for meshing. SIAM J. Imaging Sci. 9(4), 1582–1618 (2016)
Choi, G.P.-T., Lui, L.M.: A linear formulation for disk conformal parameterization of simply-connected open surfaces. Adv. Comput. Math. 44(1), 87–114 (2018)
Lévy, B., Petitjean, S., Ray, N., Maillot, J.: Least squares conformal maps for automatic texture atlas generation. ACM Trans. Graph. 21(3), 362–371 (2002)
Desbrun, M., Meyer, M., Alliez, P.: Intrinsic parameterizations of surface meshes. Comput. Graph. Forum 21(3), 209–218 (2002)
Gu, X., Yau, S.-T.: Global conformal surface parameterization. In: Proceedings of the 2003 Eurographics/ACM SIGGRAPH Symposium on Geometry Processing, pp. 127–137 (2003)
Luo, F.: Combinatorial Yamabe flow on surfaces. Commun. Contemp. Math. 6(05), 765–780 (2004)
Sheffer, A., de Sturler, E.: Parameterization of faceted surfaces for meshing using angle-based flattening. Eng. Comput. 17(3), 326–337 (2001)
Sheffer, A., Lévy, B., Mogilnitsky, M., Bogomyakov, A.: ABF++: fast and robust angle based flattening. ACM Trans. Graph. 24(2), 311–330 (2005)
Kharevych, L., Springborn, B., Schröder, P.: Discrete conformal mappings via circle patterns. ACM Trans. Graph. 25(2), 412–438 (2006)
Springborn, B., Schröder, P., Pinkall, U.: Conformal equivalence of triangle meshes. ACM Trans. Graph. 27(3), 1–11 (2008)
Jin, M., Kim, J., Luo, F., Gu, X.: Discrete surface Ricci flow. IEEE Trans. Vis. Comput. Graph. 14(5), 1030–1043 (2008)
Yang, Y.-L., Guo, R., Luo, F., Hu, S.-M., Gu, X.: Generalized discrete Ricci flow. Comput. Graph. Forum 28(7), 2005–2014 (2009)
Yang, Y.-L., Kim, J., Luo, F., Hu, S.-M., Gu, X.: Optimal surface parameterization using inverse curvature map. IEEE Trans. Vis. Comput. Graph. 14(5), 1054–1066 (2008)
Zhang, M., Zeng, W., Guo, R., Luo, F., Gu, X.D.: Survey on discrete surface Ricci flow. J. Comput. Sci. Technol. 30(3), 598–613 (2015)
Mullen, P., Tong, Y., Alliez, P., Desbrun, M.: Spectral conformal parameterization. Comput. Graph Forum 27(5), 1487–1494 (2008)
Ben-Chen, M., Gotsman, C., Bunin, G.: Conformal flattening by curvature prescription and metric scaling. Comput. Graph. Forum 27(2), 449–458 (2008)
Marshall, D.E., Rohde, S.: Convergence of a variant of the zipper algorithm for conformal mapping. SIAM J. Numer. Anal. 45(6), 2577–2609 (2007)
Choi, G.P.T., Leung-Liu, Y., Gu, X., Lui, L.M.: Parallelizable global conformal parameterization of simply-connected surfaces via partial welding. SIAM J. Imaging Sci. 13(3), 1049–1083 (2020)
Sawhney, R., Crane, K.: Boundary first flattening. ACM Trans. Graph. 37(1), 1–14 (2017)
Yueh, M.-H., Lin, W.-W., Wu, C.-T., Yau, S.-T.: An efficient energy minimization for conformal parameterizations. J. Sci. Comput. 73(1), 203–227 (2017)
Choi, P.T., Lui, L.M.: Fast disk conformal parameterization of simply-connected open surfaces. J. Sci. Comput. 65(3), 1065–1090 (2015)
Meng, T.W., Choi, G.P.-T., Lui, L.M.: TEMPO: Feature-endowed Teich\({\ddot{{\rm m}}}\)uller extremal mappings of point clouds. SIAM J. Imaging Sci. 9(4), 1922–1962 (2016)
Lui, L.M., Lam, K.C., Wong, T.W., Gu, X.: Texture map and video compression using Beltrami representation. SIAM J. Imaging Sci. 6(4), 1880–1902 (2013)
Yung, C.P., Choi, G.P.T., Chen, K., Lui, L.M.: Efficient feature-based image registration by mapping sparsified surfaces. J. Vis. Commun. Image Represent. 55, 561–571 (2018)
Lipman, Y.: Bounded distortion mapping spaces for triangular meshes. ACM Trans. Graph. 31(4), 1–13 (2012)
Weber, O., Myles, A., Zorin, D.: Computing extremal quasiconformal maps. Comput. Graph. Forum 31(5), 1679–1689 (2012)
Wong, T.W., Zhao, H.-K.: Computation of quasi-conformal surface maps using discrete Beltrami flow. SIAM J. Imaging Sci. 7(4), 2675–2699 (2014)
Lui, L.M., Lam, K.C., Yau, S.-T., Gu, X.: Teichmüller mapping (T-map) and its applications to landmark matching registration. SIAM J. Imaging Sci. 7(1), 391–426 (2014)
Choi, G.P.-T., Man, M.H.-Y., Lui, L.M.: Fast spherical quasiconformal parameterization of genus-\(0 \) closed surfaces with application to adaptive remeshing. Geom. Imaging Comput. 3(1), 1–29 (2016)
Choi, G.P.T., Dudte, L.H., Mahadevan, L.: Programming shape using kirigami tessellations. Nat. Mater. 18(9), 999–1004 (2019)
Zeng, W., Marino, J., Gurijala, K.C., Gu, X., Kaufman, A.: Supine and prone colon registration using quasi-conformal mapping. IEEE Trans. Vis. Comput. Graph. 16(6), 1348–1357 (2010)
Choi, G.P.T., Chen, Y., Lui, L.M., Chiu, B.: Conformal mapping of carotid vessel wall and plaque thickness measured from 3D ultrasound images. Med. Biol. Eng. Comput. 55(12), 2183–2195 (2017)
Choi, G.P.T., Mahadevan, L.: Planar morphometrics using Teichmüller maps. Proc. R. Soc. A 474(2217), 20170905 (2018)
Choi, G.P.T., Chan, H.L., Yong, R., Ranjitkar, S., Brook, A., Townsend, G., Chen, K., Lui, L.M.: Tooth morphometry using quasi-conformal theory. Pattern Recognit. 99, 107064 (2020)
Choi, G.P.T., Qiu, D., Lui, L.M.: Shape analysis via inconsistent surface registration. Proc. R. Soc. A 476(2242), 20200147 (2020)
Yin, X., Dai, J., Yau, S.-T., Gu, X.: Slit map: Conformal parameterization for multiply connected surfaces. In: International Conference on Geometric Modeling and Processing, pp. 410–422. Springer (2008)
Wang, Y., Gu, X., Chan, T. F., Thompson, P. M., Yau, S.-T.: Conformal slit mapping and its applications to brain surface parameterization. In: International Conference on Medical Image Computing and Computer-Assisted Intervention, pp. 585–593. Springer (2008)
Koebe, P.: Über die konforme abbildung mehrfach zusammenhängender bereiche. Jahresbericht der Deutschen Mathematiker-Vereinigung 19, 339–348 (1910)
Zeng, W., Yin, X., Zhang, M., Luo, F., Gu, X.: Generalized Koebe’s method for conformal mapping multiply connected domains. In: 2009 SIAM/ACM Joint Conference on Geometric and Physical Modeling. pp. 89–100 (2009)
Kropf, E., Yin, X., Yau, S.-T., Gu, X.D.: Conformal parameterization for multiply connected domains: combining finite elements and complex analysis. Eng. Comput. 30(4), 441–455 (2014)
Ho, K.T., Lui, L.M.: QCMC: quasi-conformal parameterizations for multiply-connected domains. Adv. Comput. Math. 42(2), 279–312 (2016)
Bobenko, A. I., Sechelmann, S., Springborn, B.: Discrete conformal maps: Boundary value problems, circle domains, Fuchsian and Schottky uniformization. In: Advances in Discrete Differential Geometry, pp. 1–56, Springer, Berlin (2016)
Lehto, O.: Quasiconformal Mappings in the Plane, vol. 126. Springer, Berlin, Heidelberg (1973)
Gardiner, F.P., Lakic, N.: Quasiconformal Teichmüller Theory, vol. 76. American Mathematical Society, New York (2000)
Ahlfors, L.V.: Lectures on Quasiconformal Mappings, vol. 38. American Mathematical Society, New York (2006)
Birdal, T.: Maximum inscribed circle using Voronoi diagram. https://www.mathworks.com/matlabcentral/fileexchange/32543-maximum-inscribed-circle-using-voronoi-diagram
Gu, X.: RiemannMapper: a mesh parameterization toolkit. https://www3.cs.stonybrook.edu/ gu/software/RiemannMapper/
Persson, P.-O., Strang, G.: A simple mesh generator in MATLAB. SIAM Rev. 46(2), 329–345 (2004)
Ng, T.C., Gu, X., Lui, L.M.: Teichmüller extremal map of multiply-connected domains using Beltrami holomorphic flow. J. Sci. Comput. 60(2), 249–275 (2014)
Crowdy, D.: The Schwarz–Christoffel mapping to bounded multiply connected polygonal domains. Proc. R. Soc. A 461(2061), 2653–2678 (2005)
Crowdy, D., Marshall, J.: Conformal mappings between canonical multiply connected domains. Comput. Methods Funct. Theory 6(1), 59–76 (2006)
Crowdy, D.: Schwarz–Christoffel mappings to unbounded multiply connected polygonal regions. Math. Proc. Camb. Philos. Soc. 142(2), 319 (2007)
Nasser, M.M.S.: Numerical conformal mapping via a boundary integral equation with the generalized Neumann kernel. SIAM J. Sci. Comput. 31(3), 1695–1715 (2009)
Nasser, M.M.S.: PlgCirMap: A MATLAB toolbox for computing conformal mappings from polygonal multiply connected domains onto circular domains. SoftwareX 11, 100464 (2020)
Crowdy, D.: Solving problems in multiply connected domains. NSF-CBMS Regional Conference Series in Applied Mathematics, Society for Industrial and Applied Mathematics, Philadelphia (2020)
Zeng, W., Lui, L.M., Gu, X., Yau, S.-T.: Shape analysis by conformal modules. Methods Appl. Anal. 15(4), 539–556 (2008)
Zhao, J., Qi, X., Wen, C., Lei, N., Gu, X.: Automatic and robust skull registration based on discrete uniformization. In: Proceedings of the IEEE International Conference on Computer Vision, pp. 431–440, (2019)
Li, S., Zeng, W., Zhou, D., Gu, X., Gao, J.: Compact conformal map for greedy routing in wireless mobile sensor networks. IEEE Trans. Mobile Comput. 15(7), 1632–1646 (2015)
Zhao, X., Su, Z., Gu, X.D., Kaufman, A., Sun, J., Gao, J., Luo, F.: Area-preservation mapping using optimal mass transport. IEEE Trans. Vis. Comput. Graph. 19(12), 2838–2847 (2013)
Su, K., Cui, L., Qian, K., Lei, N., Zhang, J., Zhang, M., Gu, X.D.: Area-preserving mesh parameterization for poly-annulus surfaces based on optimal mass transportation. Comput. Aided Geom. Des. 46, 76–91 (2016)
Pumarola, A., Sanchez-Riera, J., Choi, G. P. T., Sanfeliu, A., Moreno-Noguer, F.: 3DPeople: modeling the geometry of dressed humans. In: Proceedings of the IEEE International Conference on Computer Vision, pp. 2242–2251 (2019)
Giri, A., Choi, G.P.T., Kumar, L.: Open and closed anatomical surface description via hemispherical area-preserving map. Signal Process. 180, 107867 (2021)
Choi, G.P.T., Rycroft, C.H.: Density-equalizing maps for simply connected open surfaces. SIAM J. Imaging Sci. 11(2), 1134–1178 (2018)
Choi, G.P.T., Chiu, B., Rycroft, C.H.: Area-preserving mapping of 3D carotid ultrasound images using density-equalizing reference map. IEEE Trans. Biomed. Eng. 67(9), 1507–1517 (2020)
Acknowledgements
This work was supported in part by the National Science Foundation under Grant No. DMS-2002103.
Author information
Authors and Affiliations
Corresponding author
Ethics declarations
Conflict of interest
The author declares no conflict of interest.
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Choi, G.P.T. Efficient Conformal Parameterization of Multiply-Connected Surfaces Using Quasi-Conformal Theory. J Sci Comput 87, 70 (2021). https://doi.org/10.1007/s10915-021-01479-y
Received:
Revised:
Accepted:
Published:
DOI: https://doi.org/10.1007/s10915-021-01479-y
Keywords
- Surface parameterization
- Conformal mapping
- Quasi-conformal theory
- Multiply-connected surfaces
- Annulus
- Poly-annulus