Computing Teichmuller Shape Space

M. Jin, W. Zeng, F. Luo and X. Gu
IEEE Transaction on Visualization and Computer Graphics (TVCG), Vol. 15, No. 3, 2009 [BiB]

Shape indexing, classification, and retrieval are fundamental problems in computer graphics. This work introduces a novel method for surface indexing and classification based on Teichm¨ uller theory. Two surfaces are conformal equivalent, if there exists a bijective angle-preserving map between them. The Teichm¨ uller space for surfaces with the same topology is a finite dimensional manifold, where each point represents a conformal equivalence class, and a curve in the Teichm¨ uller space represents a deformation process from one class to the other. In this work, we apply Teichm¨ uller space coordinates as shape descriptors, which are succinct, discriminating and intrinsic, invariant under the rigid motions and scalings, insensitive to resolutions.

Metric-Driven RoSy Fields Design

Y. Lai, M. Jin, X. Xie, Y. He, J. Palacios, E. Zhang, S. Hu, X. Gu
to appear IEEE Transaction on Visualization and Computer Graphics (TVCG), 2009. [BiB]

We formulate automatic N-RoSy design on arbitrary surfaces with user defined field topologies as designing a Riemannian metric, such that the global symmetry of the metric is compatible with the local symmetry of N-RoSy. We prove the compatibility condition using discrete parallel transportation. The user has full control of the number, positions and indices of the singularities, the turning numbers of the loops, and is able to edit the field interactively. To demonstrate the effectiveness of our approach, we apply our design system to pen-and-ink sktetching and geometry remeshing. Furthermore, based on our remeshing results with high global symmetry, we generate Celtic knots on surfaces directly.

Computing Fenchel-Nielsen Coordinates in Teichm¨uller Shape Space

M. Jin, W. Zeng, N. Ding, X. Gu
IEEE International Conference on Shape Modeling and Applications (SMI) 2009. [BiB]

M. Jin, N. Ding, X. Gu, S.-T. Yau
Communications in Information and Systems (CIS), Vol. 9, No. 2, 2009 [BiB]

This work focuses on the computation of the coordinates of high genus surfaces in the Teichm¨ uller space. The coordinates are called as Fenchel-Nielsen coordinates. The main idea is to decompose the surface to pairs of hyperbolic pants. Each pair of pants is a genus zero surface with three boundaries, equipped with hyperbolic metric. Furthermore, all the boundaries are geodesics. Each pair of hyperbolic pants can be uniquely described by the lengths of its boundaries. The way of gluing different pairs of pants can be represented by the twisting angles between two adjacent pairs of pants which share a common boundary.

Discrete Curvature Flows for Surfaces and 3-Manifolds

X. Yin, M. Jin, F. Luo, X. Gu
invited to "Emerging Trends in Visual Computing", Series: Abel Symposia, Publisher: Springer-Verlag, 2009.[BiB]

Intrinsic curvature flows can be used to design Riemannian metrics by prescribed curvatures. This chapter presents three discrete curvature flow methods that are recently introduced into the engineering fields: the discrete Ricci flow and discrete Yamabe flow for surfaces with various topology, and the discrete curvature flow for hyperbolic 3-manifolds with boundaries. For each flow, we introduce its theories in both the smooth setting and the discrete setting, plus the numerical algorithms to compute it. We also provide a brief survey on their history and their link to some of the engineering applications in computer graphics, computer vision, medical imaging, computer aided design and others.

Canonical Homotopy Class Representative Using Hyperbolic Structure

W. Zeng, M. Jin, F. Luo, X. Gu
IEEE International Conference on Shape Modeling and Applications (SMI) 2009. [BiB]

Homotopy group plays a role in computational topology with a fundamental importance. Each homotopy equivalence class contains an infinite number of loops. This work introduces a rigorous and practical method to compute a unique representative for each homotopy class based on hyperbolic structure. we apply hyperbolic Yamabe curvature flow to compute the unique Riemannian metric, which has constant negative one curvature everywhere and is conformal to the original metric. Then we compute the Fuchsian group generators of the surface on the hyperbolic space. For a given loop on the surface, we lift it to the universal covering space, to obtain the Fuchsian transformation corresponding to the homotopy class of the loop. The unique closed geodesic inside the homotopy class is the axis of the Fuchsian transformation, which is the canonical representative.

Discrete Surface Ricci Flow

M. Jin, J. Kim, F. Luo, X. Gu
IEEE Transactions on Visualization and Computer Graphics (TVCG), Vol. 14, No. 5, 2008. [BiB]

This work introduces a unified framework for discrete surface Ricci flow algorithms, including spherical, Euclidean, and hyperbolic Ricci flows, which can design Riemannian metrics on surfaces with arbitrary topologies by user-defined Gaussian curvatures. Furthermore, the target metrics are conformal (angle-preserving) to the original metrics. Ricci flow conformally deforms the Riemannian metric on a surface according to its induced curvature, such that the curvature evolves like a heat diffusion process. Eventually, the curvature becomes the user defined curvature. Discrete Ricci flow algorithms are based on a variational framework. Given a mesh, all possible metrics form a linear space, and all possible curvatures form a convex polytope. The Ricci energy is defined on the metric space, which reaches its minimum at the desired metric. The Ricci flow is the negative gradient flow of the Ricci energy. Furthermore, the Ricci energy can be optimized using Newton’s method more efficiently.

Manifold Splines with Single Extraordinary Point

X. Gu, Y. He, M. Jin, F. Luo, H. Qin
invited to Computer-Aided Design (CAD), Vol. 40, pp. 676-690, 2008.[BiB]

This paper develops a novel computational technique to define and construct manifold splines with only one singular point by employing the rigorous mathematical theory of Ricci flow. The central idea and new computational paradigm of manifold splines are to systematically extend the algorithmic pipeline of spline surface construction from any planar domain to arbitrary topology. As a result, manifold splines can unify planar spline representations as their special cases. Despite its earlier success, the existing manifold spline framework is plagued by the topology-dependent, large number of singular points (i.e., |2g−2| for any genus-g surface), where the analysis of surface behaviors such as continuity remains extremely difficult. The unique theoretical contribution of this paper is that we devise new mathematical tools so that manifold splines can now be constructed with only one singular point, reaching their theoretic lower bound of singularity for real-world applications.

Globally Optimal Surface Mapping for Surfaces with Arbitrary Topology

X. Li, Y. Bao, X. Guo, M. Jin, X. Gu, and H. Qin
IEEE Transaction on Visualization and Computer Graphics (TVCG), Vol. 14, No. 4, pp. 805-819, 2008.[BiB]

This paper proposes and develops a novel quasi-conformal surface mapping framework to globally minimize the stretching energy inevitably introduced between two different shapes. The existing state-of-the-art intersurface mapping techniques only afford local optimization either on surface patches via boundary cutting or on the simplified base domain, lacking rigorous mathematical foundation and analysis. We design and articulate an automatic variational algorithm that can reach the global distortion minimum for surface mapping between shapes of arbitrary topology, and our algorithm is solely founded upon the intrinsic geometry structure of surfaces. To our best knowledge, this is the first attempt towards rigorously and numerically computing globally optimal maps.

Computing Fundamental Group of General 3-manifold

J. Kim, M. Jin, Q. Zhou, F. Luo, X. Gu
International Symposium on Visual Computing (ISVC2008) (Oral).[BiB]

Fundamental group is one of the most important topological invariants for general manifolds, which can be directly used as manifolds classification. In this work, we provide a series of practical and efficient algorithms to compute fundamental groups for general 3-manifolds based on CW cell decomposition. The input is a tetrahedral mesh, while the output is symbolic representation of its first fundamental group. We further simplify the fundamental group representation using computational algebraic method.We present the theoretical arguments of our algorithms, elaborate the algorithms with a number of examples, and give the analysis of their computational complexity.

Discrete Curvature Flow for Hyperbolic 3-Manifold with Complete Geodesic Boundaries

X. Yin, M. Jin, F. Luo, X. Gu
International Symposium on Visual Computing (ISVC2008) (Oral). [BiB]

Three dimensional manifolds admit canonical metrics, which induce constant sectional curvature. Canonical metrics on 3- manifolds are valuable for the study of 3D topology and have the potential for volumetric parameterization and shape matching. This paper generalizes discrete curvature flow from surfaces to hyperbolic 3-manifolds with complete geodesic boundaries. The metric deforms according to the curvature, until the curvature is constant everywhere. The theoretical results are introduced, the algorithm is explained in details, and thorough experiments are carried out to demonstrate the effectiveness and efficiency of discrete 3-manifold curvature flow.

User-controllable Polycube Map for Manifold Spline Construction

H.Wang, M. Jin, Y. He, X. Gu, H. Qin
ACM Solid and Physical Modeling Symposium, pp. 397-404, 2008. [BiB]

Polycube T-spline has been formulated elegantly that can unify Tsplines and manifold splines to define a new shape representation for surfaces of arbitrary topology by using polycube map as its parametric domain. Naturally, The data fitting quality using polycube T-splines hinges on the construction of underlying polycube
maps. This paper proposes a novel framework of user-controllable polycube maps, which can overcome the disadvantages of the conventional methods and is much more efficient and accurate. The current approach allows users to directly select the corner points of the polycubes on the original 3D surfaces, then construct the polycube maps by using the new computational tool of discrete Euclidean ricci flow.

Computing General Geometric Structures on Surfaces Using Ricci Flow

M. Jin, F. Luo, and X. Gu
invited to Computer-Aided Design (CAD), Vol. 39, No. 8, pp. 663-675, 2007. [BiB]

Surfaces have natural geometric structures, such as spherical structure, affine structure, projective structure, hyperbolic structure and conformal structure. Geometric structures allow different geometries to be defined on various manifolds, such that the algorithms designed for planar domains can be systematically and straightforwardly generalized to the surface domains. In this paper, we thoroughly explain both theoretic and practical aspects of the computational methodology for geometric structures based on Ricci flow, and demonstrate several important applications of Geometric Structures.

Conformal Geometry and Its Applications on 3D Shape Matching, Recognition, and Stitching

S. Wang, Y. Wang, M. Jin, X. Gu, and D. Samaras
IEEE Transactions on Pattern Analysis and Machine Intelligence (PAMI), Vol. 29, No. 7, pp.1209-1220, 2007. [BiB]

In this paper, we analyze a family of quasi-conformal maps including harmonic maps, conformal maps, and least-squares conformal maps with regards to 3D shape matching. As a result, we propose a novel and computationally efficient shape matching framework by using least-squares conformal maps. According to conformal geometry theory, each 3D surface with disk topology can be mapped to a 2D domain through a global optimization and the resulting map is a diffeomorphism, i.e., one-to-one and onto. This allows us to simplify the 3D shape-matching problem to a 2D image-matching problem, by comparing the resulting 2D parametric maps, which are stable, insensitive to resolution changes and robust to occlusion, and noise. Therefore, highly accurate and efficient 3D shape matching algorithms can be achieved by using the above three parametric maps.

Computing shortest cycles using universal covering space

X. Yin, M. Jin, and X. Gu
The Visual Computer (VC), Vol. 23, No. 12, pp. 999-1004, 2007. [PDF] [BiB]

10th International Conference on Computer-Aided Design and Computer Graphics (CAD/Graphics 2007), 2007. (The Best Student Paper Award)[BiB]

This paper proposes and develops a novel quasi-conformal surface mapping framework to globally minimize the stretching energy inevitably introduced between two different shapes. The existing state-of-the-art intersurface mapping techniques only afford local optimization either on surface patches via boundary cutting or on the simplified base domain, lacking rigorous mathematical foundation and analysis. We design and articulate an automatic variational algorithm that can reach the global distortion minimum for surface mapping between shapes of arbitrary topology, and our algorithm is solely founded upon the intrinsic geometry structure of surfaces. To our best knowledge, this is the first attempt towards rigorously and numerically computing globally optimal maps.

Geometric accuracy analysis for discrete surface approximation

J. Dai, W. Luo, M. Jin, W. Zeng, Y. He, S.-T. Yau, and X. Gu
Computer-Aided Geometric Design (CAD), Vol. 24, No. 6, pp.323-338, 2007. [BiB]

In geometric modeling and processing, computer graphics and computer vision, smooth surfaces are approximated by discrete triangular meshes reconstructed from sample points on the surfaces. A fundamental problem is to design rigorous algorithms to guarantee the geometric approximation accuracy by controlling the sampling density. This paper gives explicit formulae to the bounds of Hausdorff distance, normal distance and Riemannian metric distortion between the smooth surface and the discrete mesh in terms of principle curvature and the radii of geodesic circum-circle of the triangles. These formulae can be directly applied to design sampling density for data acquisitions and surface reconstructions. Furthermore, we prove that the meshes induced from the Delaunay triangulations of the dense samples on a smooth surface are convergent to the smooth surface under both Hausdorff distance and normal fields. The Riemannian metrics and the Laplace-Beltrami operators on the meshes are also convergent to those on the smooth surfaces. These theoretical results lay down the foundation for a broad class of reconstruction and approximation algorithms in geometric modeling and processing.

Computing Geodesic Spectra of Surfaces

M. Jin, F. Luo, S.-T. Yau, X. Gu
ACM Solid and Physical Modeling Symposium, pp. 387-393, 2007. [BiB]

Three dimensional manifolds admit canonical metrics, which induce constant sectional curvature. Canonical metrics on 3- manifolds are valuable for the study of 3D topology and have the potential for volumetric parameterization and shape matching. This paper generalizes discrete curvature flow from surfaces to hyperbolic 3-manifolds with complete geodesic boundaries. The metric deforms according to the curvature, until the curvature is constant everywhere. The theoretical results are introduced, the algorithm is explained in details, and thorough experiments are carried out to demonstrate the effectiveness and efficiency of discrete 3-manifold curvature flow.

Discrete Surface Ricci Flow: Theory and Applications

M. Jin, J. Kim, F. Luo, X. Gu
Mathematics of Surfaces XII, Vol. 4647, pp. 209-232, 2007. [BiB]

Conformal geometry is in the core of pure mathematics. Conformal structure is more flexible than Riemaniann metric but more rigid than topology. Conformal geometric methods have played important roles in engineering fields. This work introduces a theoretically rigorous and practically efficient method for computing Riemannian metrics with prescribed Gaussian curvatures on discrete surfaces - discrete surface Ricci flow, whose continuous counter part has been used in the proof of Poincar´e conjecture.

Computational Conformal Geometry Applied in Engineering Fields

X. Gu, M. Jin, J. Kim, S.-T. Yau
ICCM 2007 (invited talk). [BiB]

Computational conformal geometry offers many powerful tools to handle a broad range of geometric problems in engineering fields. This work summarizes our research results in the past years. We have introduced efficient and robust algorithms for computing conformal structures of surfaces acquired from the real life, which are based on harmonic maps, holomorphic differential forms and surface Ricci flow. We have applied conformal geometric algorithms in computer graphics, computer vision, geometric modeling and medical imaging.

Manifold splines with single extraordinary point

X. Gu, Y. He, M. Jin, F. Luo, H. Qin
ACM Solid and Physical Modeling Symposium, pp. 61-72, 2007. [BiB]

Polycube T-spline has been formulated elegantly that can unify Tsplines and manifold splines to define a new shape representation for surfaces of arbitrary topology by using polycube map as its parametric domain. Naturally, The data fitting quality using polycube T-splines hinges on the construction of underlying polycube
maps. This paper proposes a novel framework of user-controllable polycube maps, which can overcome the disadvantages of the conventional methods and is much more efficient and accurate. The current approach allows users to directly select the corner points of the polycubes on the original 3D surfaces, then construct the polycube maps by using the new computational tool of discrete Euclidean ricci flow.

Computing Surface Hyperbolic Structure and Real Projective Structure

M. Jin, F. Luo, X. Gu
ACM Solid and Physical Modeling Symposium, pp. 105-116, 2006. [BiB]

Surfaces with negative Euler characteristic numbers admit hyperbolic structures and allow hyperbolic geometry. This paper introduces theoretically rigorous and practically simple algorithms to compute hyperbolic structures and real projective structures for general surfaces. The algorithms have been verified on real surfaces scanned from sculptures. The method is efficient and robust in practice. To the best of our knowledge, this is the first work of introducing algorithms based on Ricci flow to compute hyperbolic structure and real projective structure.

Conformal Virtual Colon Flattening

W. Hong, X. Gu, F. Qiu, M. Jin, A. Kaufman
ACM Solid and Physical Modeling Symposium, pp. 85-93, 2006. [BiB]

We present an efficient colon flattening algorithm using conformal structure, which is angle-preserving and minimizes the global distortion. First, the colon wall is segmented and extracted from the CT dataset. The topology noise is located and removed automatically. The holomorphic 1-form, a pair of orthogonal vector fields, is then computed on the 3D colon surface mesh using the conjugate gradient method. The colon surface is cut along a vertical trajectory traced using the holomorphic 1-form. Consequently, the 3D colon surface is conformal mapped to a 2D rectangle. The flattened 2D mesh is then rendered using a direct volume rendering method accelerated with the GPU. Our algorithm is tested with a number of CT datasets of real pathological cases, and gives consistent results. We demonstrated that the shape of the polyps is well preserved on the flattened colon images, which provides an efficient way to enhance the navigation of a virtual colonoscopy system.

3D Surface Matching and Recognition Using Conformal Geometry

S. Wang, Y. Wang, M. Jin, X. Gu, D. Samaras
IEEE Computer Vision Pattern Recognition (CVPR06), pp. 2453-2460, 2006. [BiB]

According to conformal geometry theory, each 3D surface with disk topology can be mapped to a 2D domain through a global optimization and the resulting map is a diffeomorphism, i.e., one-to-one and onto. This allows us to simplify the 3D surface-matching problem to a 2D image-matching problem, by comparing the resulting 2D conformal geometric maps, which are stable, insensitive to resolution changes and robust to occlusion and noise. Therefore, highly accurate and efficient 3D surface matching algorithms can be achieved by using conformal geometric maps.

Topology-driven Surface Mappings with Robust Feature Alignment

C. Carner, M. Jin, X. Gu, H. Qin
IEEE Visualization, pp. 543-550, 2005. [BiB]

Topological concepts and techniques have been broadly applied in computer graphics and geometric modeling. However, the homotopy type of a mapping between two surfaces has not been addressed before. In this paper, we present a novel solution to the problem of computing continuous maps with different homotopy types between two arbitrary triangle meshes with the same topology. Our method allows the user to change the homotopy type or global structure of the mapping with minimal intervention and satisfies hard feature constraints.

Optimal Global Conformal Surface Parameterization for Visualization

M. Jin, Y. Wang, X. Gu, and S.-T. Yau
Communications in Information and Systems (CIS), 4(2), pp. 117-134, 2005. [BiB]

This paper gives an explicit method for finding optimal global conformal parameterizations of arbitrary surfaces. It relies on certain holomorphic differential forms and conformal mappings from differential geometry and Riemann surface theories. Algorithms are developed to modify topology, locate zero points, and determine cohomology types of differential forms. The implementation is based on finite dimensional optimization method. The optimal parameterization is intrinsic to the geometry, preserving angular structure, and can play an important role in various applications including texture mapping, remeshing, morphing and simulation.

A C1 Globally Interpolatory Spline of Arbitrary Topology

Y. He, M. Jin, X. Gu, H. Qin
Lecture Notes in Computer Science, Vol. 3752, pp. 295-306, 2005. [BiB]

Converting point samples and/or triangular meshes to a more compact spline representation for arbitrarily topology is both desirable and necessary for computer vision and computer graphics. This paper presents a C1 manifold interpolatory spline that can exactly pass through all the vertices and interpolate their normals for data input of complicated topological type. Starting from the Powell-Sabin spline as a building block, we integrate the concepts of global parametrization, affine atlas, and splines defined over local, open domains to arrive at an elegant, easy-to-use spline solution for complicated datasets. The proposed global spline scheme enables the rapid surface reconstruction and facilitates the shape editing and analysis functionality.

Optimal Global Conformal Surface Parameterization

M. Jin, Y. Wang, S.-T. Yau, X. Gu
IEEE Visualization, pp. 267-274, 2004. [BiB]

This paper gives an explicit method for finding optimal global conformal parameterizations of arbitrary surfaces. It relies on certain holomorphic differential forms and conformal mappings from differential geometry and Riemann surface theories. Algorithms are developed to modify topology, locate zero points, and determine cohomology types of differential forms. The implementation is based on finite dimensional optimization method. The optimal parameterization is intrinsic to the geometry, preserving angular structure, and can play an important role in various applications including texture mapping, remeshing, morphing and simulation.