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

Discrete Surface Ricci Flow

Suppose (X , O) is a weighted mesh with an initial circle packing metric. The discrete Ricci flow is defined as follows:

whereis    the user-defined target curvature. The dis

crete Ricci flow has the same form as the smooth Ricci flow (Equation [4.2]), which deforms the circle packing metric according to the Gaussian curvature, as in Equation (4.27).

The discrete Ricci flow can be formulated in the variational setting—namely, it is a negative gradient flow of a special energy form. Let (X , O) be a weighted mesh with spherical (Euclidean or hyperbolic) background geometry. For two arbitrary vertices vi and v.., the following symmetric relation holds:

Letbe  a differential  one-form (Weitraub,  2007). The symmetric relation guarantees that the one-form is closed (curl free) in the metric space:

By Stokes theorem, the following integration is path independent:

where u0 is an arbitrary initial metric. Therefore, the above integration is well defined and is called the discrete Ricci energy. The discrete Ricci flow is the negative gradient flow of the discrete Ricci energy. The discrete metric, which induces k , is the minimizer of the energy.

Computing the desired metric with user-defined curvature k is equivalent to minimizing the discrete Ricci energy. For Euclidean or hyperbolic cases, the discrete Ricci energy (see Equation [4.30]) was first proved to be strictly convex in the seminal work of Yves Colin de Verdiére (1991) for the ¢ = 0 case, and was generalized to all cases of 0< n/2 in Chow and Luo (2003). The global minimum uniquely exists, corresponding to the metric u, which induces k. The discrete Ricci flow converges to this global minimum.

Theorem 4.5 (Chow and Luo, 2002: Euclidean Ricci Energy)

The Euclidean Ricci energy f(u) on the space of the normalized metric Xui = 0 is strictly convex.

Theorem 4.6 (Chow and Luo, 2002: Hyperbolic Ricci Energy)

The hyperbolic Ricci energy is strictly convex.

Although the spherical Ricci energy is not strictly convex, the desired metric u is still a critical point of the energy. In our experiments, the solution can be reached using Newton’s method.

Figure 4.7 shows the discrete Euclidean Ricci flow for the kitten model with zero Euler number. By translation of the fundamental domain, the universal covering space of the kitten mesh is constructed, which tiles the plane. The conformality can be verified from the fact that all the corner angles in the checker-board texture are preserved. Fgiure 4.5 shows the discrete hyperbolic Ricci flow for the amphora model with negative Euler number. A finite portion of the universal covering space is flattened onto the Poincaré disk, where different periods are denoted in different colors. Similarly, the corner angles of checkers are well preserved through the conformal mapping. Figure 4.6 shows the performance of the discrete Ricci flow for different topological surfaces, such as with positive, zero, and negative Euler numbers, respectively.

Discrete Surface Yamabe Flow

For smooth surfaces, the Ricci flow and Yamabe flow are equivalent. In the discrete case, there is a subtle difference caused by a different notion of discrete conformal classes. The following summarizes the sharp distinctions:

1. The discrete Ricci flow requires circle packing, whereas the discrete Yamabe flow is directly defined on triangulations. Therefore, Yamabe flow is more flexible.

FIGURE 4.6 Performance of the Ricci flow. (a) Euclidean RF for kitten model with zero Euler number; (b) Hyperbolic RF for vase model with negative Euler number: -2; and (c) Spherical RF for human head model with positive Euler number: +2. The horizontal axis represents time; the vertical axis represents the maximal curvature error. The blue curves are for the Newton’s method; the green curves are for the gradient descent method. The meshes have about 30k faces. The tests were carried out on a laptop with 1.7 GHz CPU and 1 G RAM. All the algorithms are written in C++ on a Windows platform without using any other numerical library.

2. Both the Ricci flow and the Yamabe flow are variational. The energy form for the Ricci flow and the Yamabe flow are convex. But the metric space (domain of u) of the Ricci flow is convex, while the metric space of Yamabe flow is nonconvex. Therefore, it is stable to use Newton’s method for optimizing the Ricci energy. For Yamabe energy optimization, the algorithm takes more caution.

FIGURE 4.7 The Euclidean Ricci flow. (a) Genus one kitten model marked with a set of canonical fundamental group generators a and b. (b) A fundamental domain is conformally flattened onto the plane, marked with four sides aba~1b~1. (c) One translation moves the side b ^ b-1. (d) The other translation moves the side a ^ a-1. (e) The layout of the universal covering space of the kitten mesh on the plane, which tiles the plane. (f) The conformal parameterization is used for the texture mapping purpose. A checkerboard texture is placed over the parameterization in (b). The conformality can be verified from the fact that all the corner angles of the checkers are preserved.

3. Yamabe flow can adapt the connectivity to the target curvature automatically, which makes it valuable for practical purposes. During Yamabe flow, if the algorithm detects a degenerate triangle, where one angle becomes n, then the algorithm swaps the edge against the angle and continues the flow. Unfortunately, this important technique of adapting connectivity to the target curvature during the flow cannot be generalized to the Ricci flow directly.

Using the symbols in the previous discussion, let M be a triangle mesh embedded in M3. Let e. be an edge with end vertices vi and v.. d. is the edge length of e. induced by the Euclidean metric of M3. A function defined on the vertices u : V ^ M is the discrete conformal factor. The edge length lij is defined as

Let Ki and Kt denote the current vertex curvature and the target vertex curvature, respectively. The discrete Yamabe flow is defined as

with initial condition ut (0) = 0. The convergence of Yamabe flow is proven in Luo (2004).    i

Furthermore, Yamabe flow is the gradient flow of the following Yamabe energy, letbe    the    total number of vertices:

Similar to the Ricci flow, one can show that

The Yamabe energy is well defined and convex. The Hessian matrix can be easily constructed as follows. Supposing faces fijk and fjil are adjacent to the edge e., define the weight of the edge e. as

where dk is the angle at vk in f.k, and 6t is the angle at vt in face fja. If the edge is on the boundary, and only attaches to ., then

It can be shown by direct computation that the differential relation between the curvature and the conformal factor is

So the Hessian matrix of the Yamabe energy is given by

The Hessian matrix is positive definite on the linear subspace Xjuj = 0. By using the Hessian matrix formula 4.38, the Yamabe energy 4.33 can be optimized effectively. But the major difficulty is that the admissible metric space D.(u) for a mesh with fixed connectivity is not convex:

Therefore, during the optimization process using Newton’s method, we need to ensure that the metric u is in the admissible metric space Q(u) at each step. If a degenerated triangle fijk is detected, then we swap the longest edge of it. For example, if dk exceeds n, then we swap edge e. as shown in Figure 4.8. The major difficulty for the discrete Ricci flow is finding a good initial circle packing with all acute edge intersection angles. This problem does not exist for discrete Yamabe flow. Therefore, Yamabe flow in general produces better conformality in practice. Figure 4.9 shows the conformal parameterizations using Yamabe flow. In frames (a) and (b), the boundary target curvature is 2n/m, where m is the total number of boundary vertices. In frames (c) and (d), the curvatures at the four corners are n/2 and are zeros everywhere else. Figure 4.10 shows the hyperbolic Yamabe flow for a genus zero surface with 3 boundaries. The traget curvatures are -1 for interior vertices and 0 for boundary vertices. The number of edge swaps depends on the initial connectivity, initial curvatures, and target curvatures.

FIGURE 4.8 Edge swap.

FIGURE 4.9 Conformal parameterizations using the Yamabe flow. (a, b) The boundary curvature is constant. (c, d) The curvatures at the four corners are n/2 and are zeros everywhere else.