Min ZhangStony Brook UniversityRen GuoOregon State UniveristyWei ZengSchool of Computing and Information Sciences, Florida International UniversityFeng LuoRutgers UniversityShing Tung YauHarvard UniversityXianfeng GuStony Brook Univerisity
Computational GeometryDifferential GeometryGeometric Modeling and ProcessingConvex and Discrete Geometry mathscidoc:1612.01001
Graphical Models/Geometric Modeling and Processing 2014, 76, (5), 321-339, 2014.9
Ricci ﬂow deformsthe Riemannian metric proportionallyto the curvature, such that the curvatureevolves accordingto a heat diffusion process and eventually becomes constant everywhere. Ricci ﬂow has demonstrated its great potential by solving various problems in many ﬁelds, which can be hardly handled by alternative methods so far. This work introduces the uniﬁed theoretic framework for discrete Surface Ricci Flow, including all the common schemes: Tangential Circle Packing, Thurston’s Circle Packing, Inversive Distance Circle Packing and Discrete Yamabe Flow. Furthermore, this work also introduces a novel schemes, Virtual Radius Circle Packing and the Mixed Type schemes, under the uniﬁed framework. This work gives explicit geometric interpretation to the discrete Ricci energies for all the schemes with all back ground geometries, and the corresponding Hessian matrices. The uniﬁed frame work deepens our understanding to the the discrete surface Ricci ﬂow theory, and has inspired us to discover the new schemes, improved the ﬂexibility and robustness of the algorithms, greatly simpliﬁed the implementation and improved the efﬁciency. Experimental results show the uniﬁed surface Ricci ﬂow algorithms can handle general surfaces with different topologies, and is robust to meshes with different qualities, and is effective for solving real problems.
Surface parameterizations and registrations are important in computer graphics and imaging, where 1-1 correspondences between meshes are computed. In practice, surface maps are usually represented and stored as three-dimensional coordinates each vertex is mapped to, which often requires lots of memory. This causes inconvenience in data transmission and data storage. To tackle this problem, we propose an effective algorithm for compressing surface homeomorphisms using Fourier approximation of the Beltrami representation. The Beltrami representation is a complex-valued function defined on triangular faces of the surface mesh with supreme norm strictly less than 1. Under suitable normalization, there is a 1-1 correspondence between the set of surface homeomorphisms and the set of Beltrami representations. Hence, every bijective surface map is associated with a unique Beltrami representation. Conversely, given a Beltrami representation, the corresponding bijective surface map can be exactly reconstructed using the linear Beltrami solver introduced in this paper. Using the Beltrami representation, the surface homeomorphism can be easily compressed by Fourier approximation, without distorting the bijectivity of the map. The storage requirement can be effectively reduced, which is useful for many practical problems in computer graphics and imaging. In this paper, we propose applying the algorithm to texture map compression and video compression. With our proposed algorithm, the storage requirement for the texture properties of a textured surface can be significantly reduced. Our algorithm can further be applied to compressing motion vector fields for video compression, which effectively improves the compression ratio.
Morphing is the process of changing a geometric model or an image into another. The process generally involves rigid body motions and non-rigid deformations. It is well known that there exists a unique conformal mapping from a simply connected surface into a unit disk by the Riemann mapping theorem. On the other hand, a 3D surface deformable model can be built via various approaches such as mutual parameterization from direct interpolation or surface matching using landmarks. In this paper, a numerical methods of 3D surface morphing based on deformable model and conformal mapping is demonstrated.
We take the advantage of the unique representation of 3D surfaces by the mean curvatures $H$ and the conformal factors $\lambda$ associated with the Riemann mapping and build up the deformation model by consistently registering the landmarks on the conformal parametric domains. As a result, the correspondence of the $(H, \lambda)$ between two surfaces can be defined and a 3D deformation field can be reconstructed. Furthermore, by composition of the M\"obius transformation and the 3D deformation field, a smooth morphing sequence can be generated over a consistent mesh structure via the cubic spline homotopy. Several numerical experiments on the face morphing are presented to demonstrate the robustness of our approach.
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.
Automatic hexahedral mesh generation plays a fundamental role in CAD/CAE fields, especially for IGA (isogeometric
analysis). Recently, an automatic hex-mesh generation method has been proposed, which is based on the equivalence among
three key concepts: colorable quadrilateral meshes, finite measured foliations and Strebel differentials.
This work focuses on the computational aspect of Strebel differentials on high genus surfaces, which is based on graph-valued
harmonic mapping. The algorithmic pipeline is as follows: first, the user inputs an admissible curve system, which induces a
cylindric-decomposition graph; then the user specifies the lengths of the edges of the graph; third, the algorithm finds the unique
harmonic map from the surface to the metric graph by a non-linear heat flow; finally, the harmonic map induces a Strebel
differential, which can be further utilized to generate the hex-mesh.
The method has solid theoretic foundation, which guarantees the existence and the uniqueness of the graph-valued harmonic
map. The algorithm is capable of handling surfaces with complicated topologies, and producing all possible Strebel differentials
on the surface. The user has full control of the combinatorial type and the geometry of the Strebel differential. The computational
pipeline is automatic.
The experimental results show the efficiency and efficacy of the algorithm, and demonstrate the great potential for automating
the structured hexahedral mesh generation.