3D Surface Representation Using Ricci Flow (Computer Vision) Part 2

Smooth Surface Ricci Flow

Suppose S is a smooth surface with a Riemannian metric g. The Ricci flow deforms the metric g(t) according to the Gaussian curvature K(t) (induced by itself), where t is the time parameter:

tmpf103-73_thumb_thumb

There is an analogy between the Ricci flow and the heat diffusion process. Suppose T(t) is a temperature field on the surface. The heat diffusion equation is dT(t)/dt = -AgT(t), where Ag is the Laplace-Beltrami operator induced by the surface metric. The temperature field becomes increasingly uniform with the increase of t, and it will become constant eventually.

In a physical sense, the curvature evolution induced by the Ricci flow is exactly the same as heat diffusion on the surface, as follows:

tmpf103-74_thumb[2]


wheretmpf103-75_thumb[2]is the Laplace-Beltrami operator induced by the metric g(t). If we replace the metric in Equation (4.17) withtmpf103-76_thumb[2]then the Ricci flow can be simplified as

tmpf103-79_thumb[2]

which states that the metric should change according to the curvature. The following theorems postulate that the Ricci flow defined in Equation (4.17) is convergent and leads to a conformal uniformization metric. For surfaces with nonpositive Euler number, Hamilton (1988) proved the convergence of the Ricci flow:

Theorem 4.2 (Hamilton, 1988)

For a closed surface of nonpositive Euler characteristic, if the total area of the surface is preserved during the flow, the Ricci flow will converge to a metric such that the Gaussian curvature is constant everywhere.

It is much more difficult to prove the convergence of the Ricci flow on surfaces with positive Euler number. The following result was proven by Chow (1991).

Theorem 4.3 (Chow, 1991)

For a closed surface of positive Euler characteristic, if the total area of the surface is preserved during the flow, the Ricci flow will converge to a metric such that the Gaussian curvature is constant everywhere.

The corresponding metric g(^) is the uniformization metric. Moreover, at any time t, the metric g(t) is conformal to the original metric g(0).

The Ricci flow can be easily modified to compute a metric with a user-defined curvature K as the following:

tmpf103-80_thumb[2]

With this modification, the solution metric g(<*>) can be computed, which induces the curvature K.

Theories on the Discrete Surface Ricci Flow

In engineering fields, smooth surfaces are often approximated by simplicial complexes (triangle meshes). Major concepts, such as metric, curvature, and conformal deformation, in the continuous setting can be generalized to the discrete setting. We denote a triangle mesh as X, a vertex set as V, an edge set as E, and a face set as F. e. represents the edge connecting vertices vt and v., and fijkdenotes the face formed by vt, v., and vk.

Background Geometry

In graphics, it is always assumed that a mesh X is embedded in the 3D Euclidean space M3, and therefore each face is Euclidean. In this case, we say the mesh is with Euclidean background geometry (see Figure 4.2b). The angles and edge lengths of each face satisfy the Euclidean cosine law.

Similarly, if we assume that a mesh is embedded in the 3D sphere S3, then each face is a spherical triangle. We say the mesh is with spherical background geometry (see Figure 4.2a). The angles and the edge lengths of each face satisfy the spherical cosine law.

Furthermore, if we assume that a mesh is embedded in the 3D hyperbolic space H3, then all faces are hyperbolic triangles. We say the mesh is with hyperbolic background geometry (see Figure 4.2c). The angles and the edge lengths of each face satisfy the hyperbolic cosine law.

In the following discussion, we will explicitly specify the background geometry for a mesh when it is needed. Otherwise, the concept or the algorithm is appropriate for all kinds of background geometries.

Discrete Riemannian Metric

A discrete Riemannian metric on a mesh X is a piecewise constant metric with cone singularities. A metric on a mesh with Euclidean metric is a discrete Euclidean metric with cone singularities. Each vertex is a cone singularity. Similarly, a metric on a mesh with spherical background geometry is a discrete spherical metric with cone singularities; a metric on a mesh with hyperbolic background geometry is a discrete hyperbolic metric with cone singularities.

The edge lengths of a mesh X are sufficient to define a discrete Riemannian metric:

tmpf103-81_thumb[2]

as long as, for each face fijk , the edge lengths satisfy the triangle inequality hj + lk > lki for the three background geometries, and another inequality lj + ljk + lki < 2n for spherical geometry.

Discrete gaussian Curvature

The discrete Gaussian curvature Kt on a vertex vt eX can be computed from the angle deficit:

tmpf103-82_thumb[2]

where djk represents the corner angle attached to vertex vt in the face fjk, and dX represents the boundary of the mesh. The discrete Gaussian curvatures are determined by the discrete metrics.

Discrete Gauss-Bonnet Theorem

The Gauss-Bonnet theorem (Equation [4.2]) states that the total curvature is a topological invariant. It still holds on meshes as follows:

tmpf103-83_thumb[2]

where A; denotes the area of face f, and X represents the constant curvature for the background geometry: +1 for the spherical geometry, 0 for the Euclidean geometry, and -1 for the hyperbolic geometry.

Discrete Conformal Deformation

Conformal metric deformations preserve infinitesimal circles and the intersection angles among them. The discrete conformal deformation of metrics uses circles with finite radii to approximate the infinitesimal circles.

The concept of the circle packing metric was introduced in 1976 by Thurston (see Thurston, 1980) as shown in Figure 4.4. Let r be a function defined on the vertices, r : V ^ M+, which assigns a radius y to the vertex v. Similarly, let O be a function defined on the edges, O : E ^ [0,^/2], which assigns an acute angle ^>(ei]) to each edge e. and is called a weight function on the edges. Geometrically, O(e. ) is the intersection angle of two circles centered at vt and v.. The pair of vertex radius function and edge weight function on a mesh X, (r ¢), is called a circle packing metric of X.

 Circle packing metric. (a) Flat circle packing metric. (b) Circle packing metric on a triangle.

FIGURE 4.4 Circle packing metric. (a) Flat circle packing metric. (b) Circle packing metric on a triangle.

The hyperbolic Ricci flow. (a) Genus two vase model marked with a set of canonical fundamental group generators, which cut the surface into a topological disk with eight sides: a1,b1,a-1,b1-1, a2,b2, a-1,b-1 (b) The fundamental domain is conformally flattened onto the Poincaré disk with marked sides. (c) A Möbius transformation moves the side b1 ^ b-1. (d) Eight copies of the fundamental domain are glued coherently by eight Möbius transformations. (e) A finite portion of the universal covering space is flattened onto the Poincaré disk. (f) Zoom in on a region on the universal covering space, where eight fundamental domains join together. No seams or overlapping can be found. (g) Conformal parameterization induced by the hyperbolic flattening. The corner angles of checkers are well preserved.

Figure 4.5 The hyperbolic Ricci flow. (a) Genus two vase model marked with a set of canonical fundamental group generators, which cut the surface into a topological disk with eight sides: a1,b1,a-1,b1-1, a2,b2, a-1,b-1 (b) The fundamental domain is conformally flattened onto the Poincaré disk with marked sides. (c) A Möbius transformation moves the side b1 ^ b-1. (d) Eight copies of the fundamental domain are glued coherently by eight Möbius transformations. (e) A finite portion of the universal covering space is flattened onto the Poincaré disk. (f) Zoom in on a region on the universal covering space, where eight fundamental domains join together. No seams or overlapping can be found. (g) Conformal parameterization induced by the hyperbolic flattening. The corner angles of checkers are well preserved.

Figure 4.4 illustrates the circle packing metrics. Each vertex vi has a circle with radius r. For each edge e., the intersection angle is defined by the two circles of vj and v., which either intersect or are tangent.

Two circle packing metrics (r1, 01) and (r2,02) on the same mesh are conformally equivalent if 01 = 02. A conformal deformation of a circle packing metric only modifies the vertex radii and preserves the intersection angles O on the edges.

Admissible Curvature Space

A mesh X with edge weight O is called a weighted mesh, which is denoted as (X, O). In the following, we want to clarify the spaces of all possible circle packing metrics and all possible curvatures of a weighted mesh. Let the vertex set be V = {v1, v2,…, vn}, and the radii be r = {r1,r2,., rn}. Let ui be


tmpf103-86_thumb[2]

where E2, H2, and S2 indicate the background geometry of the mesh. We represent a circle packing metric on (X ,O) by a vector u = (u1,u2,.,un)T. Similarly, we represent the Gaussian curvatures at mesh vertices by the curvature vector k = (K1,K2,…,Kn). All the possible u’s form the admissible metric space, and all the possible k’s form the admissible curvature space.

According to the Gauss-Bonnet theory (Equation [4.23]), the total curvature must be 2nx(X), and therefore the curvature space is n – 1 dimensional. We add one linear constraint to the metric vector u, Xut = 0, for the normalized metric. As a result, the metric space is also n – 1 dimensional. If all the intersection angles are acute, then the edge lengths induced by a circle packing satisfy the triangle inequality. There is no further constraint on u. Therefore, the admissible metric space is simply m”-1.

A curvature vector k is admissible if there exists a metric vector u that induces k. The admissible curvature space of a weighted mesh (X,0) is a convex polytope, specified by the following theorem. The detailed proof can be found in Chow and Luo (2003).

Theorem 4.4

Suppose (X , O) is a weighted mesh with Euclidean background geometry, I is a proper subset of vertices, F1 is the set of faces whose vertices are in I, and the link set Lk(I) is formed by faces (e,v), where e is an edge and v is the third vertex in the face,

tmpf103-87_thumb[2]

then a curvature vector k is admissible if and only if

tmpf103-88_thumb[2]

The admissible curvature space for weighted meshes with hyperbolic or spherical background geometries is more complicated. We refer the readers to Luo, Gu, and Dai (2007) for a detailed discussion.

Next post:

Previous post: