Topological Invariants of Discrete Surfaces

[BKP+10] is a whirlwind tour of the applications that makes use of differential geometry. The lack of exercises makes this is a quick read. Its focus is to provide a mental model of the digital geometry processing pipeline.

[Zha16] is a nice introductory overview to peruse before starting differential geometry. There are a few concepts to be aware of:

At the core of discrete differential geometry lies a hierarchy of structures in geometry: topological structure \(\supset\) differentiable structure \(\supset\) geometric structure. The intuition behind these conceptual primitives are essential to understanding more complex subjects.

After reading the aforementioned materials, complete Chapter 4 in [Cra].

Polyhedral Formula

Recall that a simple polygon encloses a region with no holes where exactly two edges meet at each vertex, and the number of edges \(E\) is equal to the number of vertices \(V\).

Polygonal Disk

A polygonal disk is any topological disk constructed out of simple polygons. The simplest polygonal disk is a simple polygon that has \(F = 1\). By inspection, the base case is satisfied. For the inductive step, suppose \(V - E + F = 1\) holds for a polygonal disk with \(F\) faces, \(V\) vertices, and \(E\) edges.

There are only two valid operations on a polygonal disk. When placing a new vertex on an existing edge, that edge is split into two edges without affecting \(F\). The polyhedral formula still holds because \((V + e) - (E + e) + F = 1\) where \(e = 1\).

When a new face is delimited within the polygonal disk, the resulting simple polygon must introduce \(e + v\) new vertices and \(e + v + 1\) new edges where \(v \in \mathbb{W}\) is the number of new vertices placed on non-edges and \(e \in \mathbb{W}\) is the number of new vertices placed on edges. The simple polygon cannot be formed using an entirely new set of vertices and edges because that decomposition would violate the definition of a polygonal disk. The polyhedral formula still holds because \((V + e + v) - (E + e + v + 1) + (F + 1) = 1\).

Polyhedron

A polyhedron is a sphere made of polygons. The simplest polyhedron is a tetrahedron with \(V = 4\) vertices, \(E = 6\) edges, and \(F = 4\) faces. By inspection, the base case \(V - E + F = 2\) is satisfied. For the inductive step, suppose that relationship holds for a polyhedron with \(F\) faces, \(V\) vertices, and \(E\) edges. Imagine inflating that polyhedron until it is a sphere. Any decomposition of the polyhedron can then be interpreted as operations on the surface of the sphere. These operations are equivalent to the ones for a polygonal disk assuming the polyhedron is simply connected. Thus \(V - E + F = 2\) holds for any simply connected polyhedron.

Platonic Solids

The vertices of a Platonic solid have equal valence \(q\). Let \(p\) be the number of edges (or equivalently vertices) of each face, and let \(q\) be the number of faces (or equivalently edges) that meet at each vertex.

Since any edge joins two vertices and has two adjacent faces,

\[pF = 2E = qV\]

because the edges are double counted. Since the simplest Platonic solid has \(p, q \geq 3\), there are only five Platonic solids that satisfy

\[\begin{split}V - E + F &= 2 & \quad & \text{Euler's polyhedral formula}\\ \frac{2E}{q} - E + \frac{2E}{p} &= 2\\ \frac{1}{q} + \frac{1}{p} &= \frac{1}{E} + \frac{1}{2}\\ \frac{1}{q} + \frac{1}{p} &> \frac{1}{2}.\end{split}\]

Regular Valence

The valence of a vertex in a piecewise linear surface is the number of faces that contain that vertex. A vertex of a simplicial surface is said to be regular when its valence equals \(q = 6\). A simplicial surface is defined to have \(p = 3\) edges per face. Since any edge joins two vertices and has two adjacent faces, the previously derived relationship

\[\newcommand{\Euler}{\textrm{Euler}} \newcommand{\Poincare}{\textrm{Poincaré}} qV = 2E = pF\]

still holds. Applying the \(\Euler-\Poincare\) formula reveals

\[\begin{split} 2 - 2g &= V - E + F\\ &= \frac{2E}{6} - E + \frac{2E}{3}\\ &= 0\\ g &= 1.\end{split}\]

Therefore, the only simplicial surface for which every vertex has a regular valence is a torus that has a genus of one.

Minimally Irregular Valence

Suppose a simplicial surface \(K\) has a genus \(g\) where each vertex \(i\) has valence \(q_i \geq 3\), \(p = 3\), and there are finitely many faces.

The relationship between edges, faces, and vertices is now

\[pF = 2E = 6 (V - n) + \sum_{j = 1}^n q_j\]

where \(n\) is the number of vertices with irregular valence. Applying the \(\Euler-\Poincare\) formula gives

\[\begin{split}2 - 2g &= V - E + F\\ &= V - \frac{1}{2} pF + F\\ &= V + \frac{2 - p}{2} \left( \frac{6 (V - n) + \sum_{j = 1}^n q_j}{p} \right)\\ &= V - (V - n) - \frac{1}{6} \sum_j q_j & \quad & p = 3\\ n &= 2 - 2g + \frac{1}{6} \sum_j q_j\\ n &= 2 - 2g + \frac{1}{6} \sum_j 3 + q'_j & \quad & q'_j = q_j - 3 \geq 0\\ n &= 4 - 4g + \frac{1}{3} \sum_j q'_j\\ &\geq 4 - 4g.\end{split}\]

By inspection, \(m(K)\) is satisfied for \(g = 0\) and \(g = 1\). When \(g \geq 2\), \(n \geq 1\) because

\[\begin{split}n &= 4 - 4g + \frac{1}{3} \sum_j q'_j\\ 0 &= 4 - 4g\end{split}\]

contradicts while

\[\begin{split}n &= 4 - 4g + \frac{1}{3} \sum_j q'_j\\ 1 &= 4 - 4g + \frac{1}{3} q'_j\\ q'_j &= 12g - 9\end{split}\]

is feasible for a connected, orientable simplicial surface.

Mean Valence

The relationship between edges, faces, and vertices in a connected, orientable simplicial surface is now

\[pF = 2E = \sum_{i = 1}^V q_i.\]

Applying the \(\Euler-\Poincare\) formula gives

\[\begin{split}2 - 2g &= V - E + F\\ &= V - \frac{1}{2} \sum_i q_i + \frac{1}{p} \sum_i q_i\\ \frac{1}{6} \sum_i q_i &= V - 2 + 2g & \quad & p = 3\\ \frac{1}{V} \sum_i q_i &= 6 - \frac{12 + 12g}{V},\end{split}\]

which shows that the mean valence \(q_\infty = V^{-1} \sum_i q_i \to 6\) as \(V \to \infty\) and

\[\begin{split}q_\infty = V^{-1} 2E = V^{-1} pF \implies \begin{cases} F = \frac{1}{p} V q_\infty = 2V\\ E = \frac{1}{2} V q_\infty = 3V \end{cases}\end{split}\]

Area of a Spherical Triangle

Recall that any two distinct great circles intersect in two points which are negatives of each other [Cha]. The angle between two great circles at an intersection point is the angle between their respective planes. A region bounded by two great circles is called a diangle. The angle at both the vertices are equal. Both diangles bounded by two great circles are congruent to each other.

Let \(\theta\) be the angle of a diangle. Suppose the area of the diangle is not \(2 \theta\). When the diangles are parallel (\(\theta = \pi\)), each diangle represents a hemisphere whose area is \(2 \pi\) because the surface area of a sphere is \(4 \pi\). However, this implies each diangle has an area of \(2 \theta\), which is a contradiction. Therefore, the area of a diangle is \(2 \theta\).

Given a spherical triangle with interior angles \(\left\{ \alpha_i \right\}_{i = 1}^3\), let \(A\) denote the area of the spherical triangle and \(a_i = 2 \alpha_i\) represent the area of each diangle. Observe that the union of all diangle pairs covers more than the surface area of a sphere because \(A\) gets counted four times over. Thus

\[\begin{split}4 \pi &= \sum_i 2 a_i - 4A\\ A &= \sum_i \alpha_i - \pi & \quad & \text{Girard’s Theorem}.\end{split}\]

Area of a Spherical Polygon

Recall that a polygon with \(n > 3\) vertices can be decomposed into \(n - 2\) triangles.

A spherical polygon is a polygon whose sides are parts of great circles.

Computing the area of each resulting spherical triangle gives

\[A = \sum_i \alpha_i - (n - 2) \pi = (2 - n) \pi + \sum_i \alpha_i.\]

Angle Defect

For a discrete surface, the area on the unit sphere bounded by a spherical polygon whose vertices are the unit normals of the faces around \(v\) is equal to the angle defect

\[d(v) = 2 \pi - \sum_{f \in F_v} \angle_f(v)\]

where \(F_v\) is the set of faces containing \(v\) and \(\angle_f(v)\) is the interior angle of face \(f\) at vertex \(v\).

By the area of a spherical polygon, the following condition must hold:

\[\begin{split}A &= d(v)\\ 2 \pi - n\pi + \sum_{i = 1}^n \beta_i &= 2 \pi - \sum_{f \in F_v} \angle_f(v)\\ \sum_{i = 1}^n \beta_i &= \sum_{f \in F_v} \pi - \angle_f(v)\end{split}\]

where \(\left\{ \beta_i \right\}_{i = 1}^n\) are the consecutive interior angles of the spherical polygon.

Suppose \(a, b, c\) are consecutive faces of the discrete surface sharing the vertex \(v\). Let \(N_a, N_b, N_c\) denote the corresponding unit normals of the faces. The direction of the intersection line (or edge) between each face is defined as \(E_{ba} = N_b \times N_a\) and \(E_{bc} = N_b \times N_c\).

The dihedral angle between two planes, which have normal vectors \(N_a\) and \(N_b\), is given by \(\cos \theta_{ab} = N_a \cdot N_b\).

The great-circle distance is the shortest distance between two points on the surface of a sphere measured along the surface of the sphere. A great circle of a sphere is the intersection of the sphere and a plane that passes through the center of the sphere. The angle between two great circles at an intersection point is the angle between their respective planes.

In order to show \(\beta_i = \pi - \angle_f(v)\) where \(i = f\) (i.e. they share a unit normal), an appropriate origin \(O\) for the sphere is needed. Define \(O + N_b\) as the intersection between the geodesic arc connecting \(N_a\) to \(N_b\) and the geodesic arc connecting \(N_c\) to \(N_b\).

The projection of that intersection onto the plane \((v, N_b)\) is

\[\begin{split}P_b &= (O + N_b) - \left( N_b \cdot (O + N_b - v) \right) N_b\\ &= (O + N_b) - (N_b \cdot O) N_b - N_b + (N_b \cdot v) N_b\\ &= O - (N_b \cdot O) N_b + (N_b \cdot v) N_b\\ &= O + \left( N_b \cdot (v - O) \right) N_b.\end{split}\]

By the spherical law of cosines, the angle \(\beta_b\) is given by

\[\cos \beta_b = t_{ba} t_{bc}\]

where the tangent vectors are defined as

\[t_{b\cdot} = \frac{ N_\cdot - N_b (N_b \cdot N_\cdot) }{ \left\Vert N_\cdot - N_b (N_b \cdot N_\cdot) \right\Vert } = \frac{ N_\cdot - N_b \cos \theta_{b\cdot} }{ \sin \theta_{b\cdot} }\]

and \(\theta_{b\cdot}\) denotes the geodesic arc length on the unit sphere.

The tangent vectors at \(P_b\) are orthogonal to both edges because

\[\begin{split}t_{b\cdot} \cdot E_{b\cdot} &= \frac{ N_\cdot - N_b \cos \theta_{b\cdot} }{ \sin \theta_{b\cdot} } \cdot (N_b \times N_\cdot)\\ &= \frac{1}{\sin \theta_{b\cdot}} \left( N_\cdot \cdot (N_b \times N_\cdot) - N_b \cos \theta_{b\cdot} \cdot (N_b \times N_\cdot) \right) &= 0.\end{split}\]

By inspection of \(v\), \(P_b\), and the projection of \(P_b\) onto both edges, the resulting polygon is regular and has an internal angle sum of \(2 \pi = \angle_b + \beta_b + \pi\). Therefore, \(\beta_b = \pi - \angle_b\). [Glu] has an insightful illustration of this proof.

Discrete Gauss-Bonnet Theorem

The (connected, orientable) simplicial surface \(K\) has no boundary.

The following makes use of the fact that a triangle has an internal angle sum equal to \(\pi\).

\[\begin{split}\sum_{v \in V} d(v) &= \sum_{v \in V} 2 \pi - \sum_{f \in F_v} \angle_f(v)\\ &= 2 \pi V - \sum_{v \in V} \sum_{f \in F_v} \angle_f(v)\\ &= 2 \pi V - \pi F & \quad & p = 3\\ &= 2 \pi V - \pi F + 0\\ &= 2 \pi V - \pi F + \pi (3F - 2E) & \quad & pF = 2E\\ &= 2 \pi \chi.\end{split}\]

Total Curvature

Recall that the median of a triangle is a line segment joining a vertex to the midpoint of the opposing side. The intersection of all medians is at the triangle’s barycenter. The resulting six smaller triangles have equal area. The medians are not necessarily orthogonal to the edge they bisect. The intersection of a triangle’s perpendicular bisectors is called the circumcenter.

[Cra] approximates the discrete Gaussian curvature with barycentric cells because of its simplicity.

[MDSchroderB03] proposes a unified and consistent set of flexible tools to approximate important geometric attributes such as normal vectors and curvatures on arbitrary triangle meshes, specifically 2-manifolds and 3-manifolds in \(nD\). The approximation, based on Voronoi cells, has tight error bounds. The curvature operators (e.g. mean, Gaussian, principal) are motivated through the Laplace-Beltrami operator, a generalization of the Laplacian from flat spaces to manifolds.

Pointwise Curvature Estimates

[MW00] shows that the angle deficit method approximates the curvature to accuracy \(\mathcal{O}(1)\). The method does converge to the correct solution as the mesh becomes more refined [MSR07].

References

Cha

Abhijit Champanerkar. Spherical triangles and girard’s theorem. http://www.math.csi.cuny.edu/abhijit/623/spherical-triangle.pdf. Accessed on 2017-09-07.

Glu

Herman Gluck. The gauss-bonnet theorem. https://www.math.upenn.edu/ shiydong/Math501X-7-GaussBonnet.pdf. Accessed on 2017-09-13.

MSR07

Evgeni Magid, Octavian Soldea, and Ehud Rivlin. A comparison of gaussian and mean curvature estimation methods on triangular meshes of range image data. Computer Vision and Image Understanding, 107(3):139–159, 2007.

MW00

Dereck S Meek and Desmond J Walton. On surface normal and gaussian curvature approximations given data sampled from a smooth surface. Computer Aided Geometric Design, 17(6):521–543, 2000.

MDSchroderB03

Mark Meyer, Mathieu Desbrun, Peter Schröder, and Alan H Barr. Discrete differential-geometry operators for triangulated 2-manifolds. In Visualization and mathematics III, pages 35–57. Springer, 2003.

Zwe

John Zweck. Inverse function theorem and regular mappings. http://www.utdallas.edu/ jwz120030/Teaching/PastCoursesUMBC/M423S10/M423L4.pdf. Accessed on 2017-07-27.