A numerical method for computing the extremal Teichmüller map between multiply-connected domains is presented. Given two multiply-connected domains, there exists a unique Teichmüller map (T-Map) between them minimizing the conformality distortion. The extremal T-Map can be considered as the ‘most conformal’ map between multiply-connected domains. In this paper, we propose an iterative algorithm to compute the extremal T-Map using the Beltrami holomorphic flow (BHF). The BHF procedure iteratively adjusts the initial map based on a sequence of Beltrami coefficients, which are complex-valued functions defined on the source domain. It produces a sequence of quasi-conformal maps, which converges to the T-Map minimizing the conformality distortion. We test our method on synthetic data together with real human face data. Results show that our algorithm computes the extremal T-Map between two multiply-connected domains of the same topology accurately and efficiently.

Surface mapping plays an important role in geometric processing. They induce both area and angular distortions. If the angular distortion is bounded, the mapping is called a quasi-conformal map. Many surface maps in our physical world are quasi-conformal. The angular distortion of a quasi-conformal map can be represented by Beltrami differentials. According to quasi-conformal Teichmüller theory, there is an 1-1 correspondence between the set of Beltrami differentials and the set of quasi-conformal surface maps. Therefore, every quasi-conformal surface map can be fully determined by the Beltrami differential and can be reconstructed by solving the so-called Beltrami equation. In this work, we propose an effective method to solve the Beltrami equation on general Riemann surfaces. The solution is a quasi-conformal map associated with the prescribed Beltrami differential. We firstly formulate a discrete analog of quasi-conformal maps on triangular meshes. Then, we propose an algorithm to compute discrete quasi-conformal maps. The main strategy is to define a discrete auxiliary metric of the source surface, such that the original quasi-conformal map becomes conformal under the newly defined discrete metric. The associated map can then be obtained by using the discrete Yamabe flow method. Numerically, the discrete quasi-conformal map converges to the continuous real solution as the mesh size approaches to 0. We tested our algorithm on surfaces scanned from real life with different topologies. Experimental results demonstrate the generality and accuracy of our auxiliary metric method.

This paper is motivated by the problem of subdividing a prismatic mesh to a tetrahedral mesh (without inserting Steiner points) so as to not only match arbitrarily prescribed boundary conditions but also allow arbitrary topologies in the base mesh. We explore all possible combinations of these two factors, and propose a complete solution to this 3D problem by converting it to an equivalent 2D graph problem, called cutting flow problem. For each case, we not only prove the sufficient and necessary condition for the existence of solutions, but also provide linear and provable algorithms to compute a solution whenever there is one.

Surface conformal parameterizations have been widely applied to various tasks in computer graphics. In this paper, we develop a convergent conformal energy minimization (CCEM) iterative algorithm via the line-search gradient descent method with a quadratic approximation for the computation of disk-shaped conformal parameterizations of simply connected open triangular meshes. In addition, we prove the global convergence of the proposed CCEM iterative algorithm. Moreover, under some mild assumptions, we prove the existence of the nontrivial solution, which is a local minimum of the conformal energy with a bijective boundary map. Numerical experiments indicate that the efficiency of the proposed CCEM algorithm is highly improved and the accuracy is competitive with that of state-of-the-art algorithms.

In the past decades, many methods for computing conformal mesh parameterizations have been developed in response to demand of numerous applications in the field of geometry processing. Spectral conformal parameterization (SCP) (Mullen et al. in Proceedings of the symposium on geometry processing, SGP ’08. Eurographics Association, Aire-la-Ville, Switzerland, pp 1487–1494, 2008) is one of these methods used to compute a quality conformal parameterization based on the spectral techniques. SCP focuses on a generalized eigenvalue problem (GEP) $L_{C} \bf{f} = \lambda B \bf{f}$ whose eigenvector(s) associated with the smallest positive eigenvalue(s) provide the conformal parameterization result. This paper is devoted to studying a novel eigensolver for this GEP. Based on structures of the matrix pair $(L_{C}, B)$, we show that this GEP can be transformed into a small-scale compressed and deflated standard eigenvalue problem with a symmetric positive definite skew-Hamiltonian operator. We then propose a symmetric skew-Hamiltonian isotropic Lanczos algorithm (SHILA) to solve the reduced problem. Numerical experiments show that our compressed deflating technique can exclude the impact of convergence from the kernel of $L_{C}$ and transform the original problem to a more robust system. The novel SHILA method can effectively avoid the disturbance of duplicate eigenvalues. As a result, based on the spectral model of SCP, our numerical eigensolver can compute the conformal parameterization accurately and efficiently.