Chapter 3 Surface Classification Methods

Among the goals of this thesis is to devise an algorithm that automatically detects parts of a discretized surface, originating from a simulation workflow, that benefits from a higher resolution of the simulation domain. This requires mathematically analyzing the surfaces so that the regions of interest can be efficiently detected.

In chapter 2 three different surface representations and how to obtain one of their basic geometric properties (i.e., the surface normal) have been discussed. Surfaces have more geometric properties than just the surface normal vector (e.g., the tangent plane). Another property of orientable surfaces, which will be discussed later, is the surface curvature. The surface curvature describes how the direction of the normal vector changes when it is moved from one point on the surface to a neighboring point in an infinitesimal area around the point. Thus, the surface curvature can be used to classify parts of a surface.

In this chapter the mathematical concept of surface curvature on continuous surfaces is introduced. This is followed by a discussion on how these concepts can be discretized for the previously discussed surface representations. For implicit surfaces several methods for calculating surface curvatures are reviewed. The last section in this chapter discusses how discrete surfaces can be analyzed without prior knowledge of surface curvatures.

3.1 Curvature of Continuous Surfaces

The constructions and definitions presented within this section are extracted and simplified from [25]. Only the results needed for further investigations in this work are discussed and proofs are omitted. The goal of this section is to give a rigorous understanding of how the curvatures of a continuous surface are constructed and which properties of the surface they express.

3.1.1 2D Surface (Curves)

First 2D surfaces are discussed. In differential geometry 2D surfaces are referred to as parametrized curves and are defined as follows [25]:

For example consider the map $\gamma (t)=(t^3,t^2)$, the parametrized curve created by this expression is shown in Figure 3.1.

This curve has a point $\mathbf{p}=(0,0)$ for which ${\gamma }^{\prime }(\mathbf{p})=0$, these points are called singular points.

For the further investigations in this section it is important that a parametrized curve $\gamma (t)$ does not have any singular points. Thus, the definition of a parametrized curve is extended to a regular parametrized curve.

Excluding curves with singular points allows for the definition of the length of a curve. The arc length of a regular parametrized curve is defined as follows:

A regular curve that fulfills $\Vert {\gamma }^{\prime }(t)\Vert =1$ for all $t\in I$ is called a curve parametrized by arc length. For such curves the arc length is given by $s(t)=t-t_0$.

The Tangent Line and Curvature of a Curve Parametrized by Arc Length

In each point $\gamma (t)$ on a curve parametrized by arc length there exists a straight line, defined by ${\gamma }^{\prime }(t)$ which has a length of $\Vert {\gamma }^{\prime }(t)\Vert =1$. This vector passes through the point $\gamma (t)$ and is called the tangent line (${\gamma }^{\prime }(t)$). In singular points it is not possible to define the tangent line and so, it is not possible to discuss geometric properties of such curves.

Consider a curve parametrized by arc length $\gamma$ which in a point $\gamma (t)$ fulfills ${\gamma }^{″}(t)\ne 0$, in this case a unit vector $\overrightarrow{n}(t)$ is well-defined by ${\gamma }^{″}(t)=\Vert {\gamma }^{″}(t)\Vert \overrightarrow{n}(t)$. Furthermore, differentiating ${\gamma }^{\prime }(t)\cdot {\gamma }^{\prime }(t)=1$ yields ${\gamma }^{″}(t)\cdot {\gamma }^{\prime }(t)=0$, which proves that ${\gamma }^{″}(t)$ and ${\gamma }^{\prime }(t)$ are orthogonal. Therefore, the vector $\overrightarrow{n}(t)$ is normal to ${\gamma }^{\prime }(t)$ and is called the normal vector in $\gamma (t)$.

Since ${\gamma }^{\prime }(t)$ has length $1$, the norm of the second derivative $|{\gamma }^{″}(t)|$ measures the rate of change of the angles of the neighboring tangent planes at the tangent plane in $\gamma (t)$. In other words the curve parametrized by arc length $\gamma (t)$ pulls away from the tangent line in $\gamma (t)$ at a rate determined by $\Vert {\gamma }^{″}(t)\Vert$.

A straight line $\gamma (t)=\overrightarrow{u}t+\overrightarrow{v}$ with constant vectors $\overrightarrow{u},\overrightarrow{v}$ has a curvature of $0$. Inversely if $\Vert {\gamma }^{″}(t)\Vert =0$ is integrated the curve $\gamma (t)$ has to be a straight line. Thus, the curvature of a curve can be used as a metric to distinguish between parts of a curve that are flat and parts that are not, e.g., curved.

Furthermore, it can be shown that each regular parametrized curve can be expressed as a curve parametrized by arc length  [25]. Thus, the concept of the curvature can be expanded to any regular parametrized curve. The curvature of the regular parametrized curve $\gamma (t)$ is given by the curvature of the reparametrized (i.e., parametrized by arc length) curve ${\gamma }^{\ast }(t)$.

3.1.2 3D Surface

In this section a similar construction to the one presented in the previous section is given for 3D surfaces. However, defining geometric properties like the tangent plane or the curvature for 3D surfaces (which are also referred to as regular surfaces) requires additional considerations. The first major difference is that a regular surface is not defined as a function but as a set [25].

To further elaborate the meaning of Definition 3.1.5 consider Figure 3.2.

A regular surface is a subset of the plane that gets deformed in ${\mathbb{R}}^3$. The deformation is handled in such a way that the resulting surface has no sharp points, edges or self-intersections. This definition allows for the definition of a tangent plane in each point on the surface and ensures that the surface is smooth enough to apply methods from calculus. The map $\mathbf{x}$ is called a parametrization of the surface $S$. A surface $S$ may have several parametrizations, however, certain properties of the surface do not depend on the parametrization but only on the set $S$.

Definition 3.1.5 is a technical definition of a regular surface, which is useful for the theoretical investigation of surfaces and their properties. In this work, the geometric properties of discretized surfaces are investigated, thus, two less technical descriptions of regular surfaces are given which result from Definition 3.1.5.

Proposition 3.1.6 can be interpreted in a more descriptive way. The set of points in ${\mathbb{R}}^3$ that fulfill an implicitly defined function $f(x,y,z)=a$, which has a non-vanishing gradient in each point of the image, describes a regular surface. Consider, for example, the following function $f(x,y,z)=x^2+y^2+z^2-1$, all points except for $\mathbf{p}=(0,0,0)$ have a non-vanishing gradient, however, $f^{-1}(0)$ is not in the preimage of $f$, thus it is a regular surface (i.e., a sphere with radius $1$).

Proposition 3.1.7 guarantees that in a neighborhood around each point on a regular surface $S$ the surface can be expressed as the graph of a differentiable function.

The Tangent Plane and Curvatures of a Regular Surface

Consider a regular surface $S$ and a point on the surface $\mathbf{p}\in S$, and a regular parametrized curve $\gamma :(-ϵ,ϵ)\to S$ with $\gamma (0)=\mathbf{p}$. Since $\gamma$ is a regular parametrized curve the tangent line ${\gamma }^{\prime }(0)$ exists. Let $\mathbf{x}:U\subset {\mathbb{R}}^2\to S$ be a parametrization of $S$ and let $\mathbf{q}\in U$. Then the set of all tangent lines of regular parametrized curves on the surface $S$ passing through $\mathbf{p}$ span a 2D subspace. The plane $d{\mathbf{x}}_q$, that passes through $\mathbf{x}(\mathbf{q})=\mathbf{p}$, does not depend on the parametrization and is called the tangent plane to $S$ denoted by ($T_{\mathbf{p}}(S)$) at the point $\mathbf{p}$. The basis vectors that span $T_{\mathbf{p}}(S)$ are written as ${\mathbf{x}}_u$ and ${\mathbf{x}}_v$ and are determined by the parametrization. By choosing a parametrization $\mathbf{x}$, a unit normal vector in the point $\mathbf{p}\in \mathbf{x}(U)$ can be defined as follows

$$\begin{array}{}\text{(3.1)}& \overrightarrow{n}(\mathbf{p})=\frac{{\mathbf{x}}_u\times {\mathbf{x}}_v}{\Vert {\mathbf{x}}_u\times {\mathbf{x}}_v\Vert }(\mathbf{p}),\end{array}$$ which is called the normal vector of the surface $S$ in $\mathbf{p}$ (see Figure 3.3).

It is not always possible to continuously define a unique normal vector $\overrightarrow{n}(\mathbf{p})$ on every point of a regular surface, see, for example, the Möbius strip (see Figure 3.4).

When a normal vector and a closed curve that traces over the Möbius strip is chosen, and the normal is moved along this curve it ends up in the same point, however, the normal now points in the opposite direction. This observation can also be described with the help of parametrizations. On each point of the Möbius strip there exist different parametrizations of the surface, these parametrizations describe the same tangent plane. However, the normal vectors defined by the parametrizations point in opposite directions (see Figure 3.4) and it is not possible to continuously change from one parametrization to the other.

For the following discussions it is essential that the discussed surfaces allow to continuously define a unique normal vector in each surface point. To that end a parametrization of a neighborhood of each point on a regular surface is fixed, the set of all these parametrizations is called a family of coordinate neighborhood. If this family of coordinate neighborhood describes a positive movement around each point of the surface it is called an orientation of the surface which is formally defined as follows:

Intuitively, Definition 3.1.8 expresses that on an orientable surface the change in the direction of the normal vector is continuous when switching between two neighboring parametrizations.

If a regular surface $S$ is defined by a differentiable function $f:U\subset {\mathbb{R}}^3\to \mathbb{R}$ as follows $S=\{(x,y,z)\in {\mathbb{R}}^3:f(x,y,z)=a\}$ and $f^{-1}(a)\ne 0$ then $S$ is orientable.

It should be mentioned that an orientation can locally be defined on every regular surface, however, orientability is a global property that concerns the entire surface.

To gain further insights into the geometry of a surface the orientation (i.e., $\mathcal{N}$) defined on the entire surface is further investigated.

Figure 3.5 visualizes how the Gauss map operates on the hyperbolic paraboloid. Another easily visualized example of the Gauss map is the image of the torus which simply is the entire surface of the unit sphere.

The derivative of the Gauss map $d{\mathcal{N}}_{\mathbf{p}}$ in a point $\mathbf{p}$ maps the tangent plane $T_{\mathbf{p}}(S)$ into itself. Now consider a curve $\gamma (t)$ in $S$ with $\gamma (0)=\mathbf{p}$, when the normal vector of the surface ${\overrightarrow{n}}_S(\mathbf{p})$ is restricted to the curve $\gamma (t)$ the map $d{\mathcal{N}}_{\mathbf{p}}(\gamma (0))={\overrightarrow{n}}_S^{\prime }(\mathbf{p})$ results in a tangent vector in $T_{\mathbf{p}}(S)$. So $d{\mathcal{N}}_{\mathbf{p}}$ measures how fast ${\overrightarrow{n}}_S(\mathbf{p})$ pulls away from the surface in the curve $\gamma (0)$. This is a similar construction to the one discussed for regular parametrized curves with the difference that the curvature is measured by a linear map and not by the norm of a vector. The construction is independent of the chosen regular parametrized curve, so the following definition can be given:

This definition results in a curvature value dependent on the chosen curve on the surface, which leads to the question if these curves can be classified in some way. To get further insights into this question the Gauss map $\mathcal{N}$ of a surface $S$ is further investigated. The negative differential $-d\mathcal{N}$ of the Gauss map (sometimes referred to as the Weingarten map or shape operator) is a self-adjoint linear operator ($II$). Thus, its Eigenvectors are orthogonal, and the Eigenvalues are real [25]. The matrix $II$ is also known as the second fundamental form of the surface $S$. Recall, that $-d{\mathcal{N}}_{\mathbf{p}}$ measures the normal curvature for each regular parametrized curve passing through $\mathbf{p}$. Since the map $-d{\mathcal{N}}_{\mathbf{p}}$ is a self-adjoint linear operator the maximum and minimum normal curvatures in each point can be calculated, which leads to the following definition:

The corresponding Eigenvectors to the principal curvatures are called the principal directions of $S$ in $\mathbf{p}$. Since the map $-d\mathcal{N}$ is a linear map the trace and the determinant of the map can be calculated.

The mean and Gaussian curvature are used to define two special classes of surfaces. Surfaces with a constant Gaussian curvature of $0$ are called developable surfaces, these surfaces can be "rolled" into the plane, or in other words folded out of paper. A cylinder is an example of a developable surface and the sphere is an example of a non-developable surface.

Surfaces with a constant mean curvature of $0$ are called minimal surfaces, if these surfaces are bounded they minimize the Dirichlet energy in each point [65]. The plane is a trivial example of a minimal surface, where an example for a non-trivial minimal surface is the helicoid. Minimal surfaces play an important role in the remainder of this work.

Until this point the curvatures of a surface have been derived from the definition of the Gauss map without any explicit reference to a local coordinate system (i.e., a parametrization). For the calculation of the surface curvatures of discrete surfaces a description of the Gauss map in a local coordinate system $\{{\mathbf{x}}_u,{\mathbf{x}}_v\}$ is required and is given by [25]

$$\begin{array}{}\text{(3.2)}& d\mathcal{N}=\left(\begin{array}{cc}{a}_{11}& a_{12}\\ a_{21}& a_{22}\end{array}\right):=-\underset{II}{\underbrace{\left(\begin{array}{cc}e& f\\ f& g\end{array}\right)}}\underset{I}{\underbrace{{\left(\begin{array}{cc}E& F\\ F& G\end{array}\right)}^{-1}}},\end{array}$$ with

$$\begin{array}{}\text{(3.3)}& \begin{array}{ccl}E={\mathbf{x}}_u\cdot {\mathbf{x}}_u& & -f={\overrightarrow{n}}_v\cdot {\mathbf{x}}_u={\overrightarrow{n}}_u\cdot {\mathbf{x}}_v\\ F={\mathbf{x}}_u\cdot {\mathbf{x}}_v& & -e={\overrightarrow{n}}_u\cdot {\mathbf{x}}_u\\ G={\mathbf{x}}_v\cdot {\mathbf{x}}_v& & -g={\overrightarrow{n}}_v\cdot {\mathbf{x}}_v\end{array},\end{array}$$ $I$ (see Equation 3.2) is also referred to as the first fundamental form. The mean and Gaussian curvature can thus be expressed in any basis as

$$\begin{array}{}\text{(3.4)}& K& =\frac{det(II)}{det(I)},\text{(3.5)}& H& =\frac{\mathrm{trace}(I\mathrm{adj}(II))}{2det(I)}\end{array}$$ where $\text{adj}(M)$ stands for the adjugate matrix.

Some methods of calculating the curvatures of discretized surfaces further down in this chapter only calculate the mean and the Gaussian curvature. The principal curvatures can be calculated from the mean and Gaussian curvature by solving the following equation

$$\begin{array}{}\text{(3.6)}& {\kappa }_{1,2}=H\mathrm{p}\mathrm{m}\sqrt{H^2-K}.\end{array}$$

3.2 Curvature Calculation for Point Clouds

When estimating the surface curvatures of a point cloud similar obstacles, such as the approximation of the surface normal discussed in Section 2.1.1, have to be overcome. Since there is no information about the spatial coherence of the points in a point cloud, a suitable neighborhood has to be estimated first. After a suitable neighborhood has been identified, recall Proposition 3.1.7, which states that in a local neighborhood a surface can be expressed by a differentiable function $f(x,y)$, which is also called the height function [66]. The goal now is to estimate $f(x,y)$ with the points in the previously estimated neighborhood. $f(x,y)$ can be expressed by a Taylor series of order $n$

$$\begin{array}{r}f(x,y)=J_{\overrightarrow{B},n}(x,y)+\mathcal{O}(\Vert (x,y){\Vert }^{n+1}),\end{array}$$ $J_{\overrightarrow{B},n}(x,y)$ is called a jet of order $n$ or an $n$-jet. To obtain an $n$-jet of the height function defined by the points in a neighborhood around a point $\mathbf{p}$ it has to be approximated. The $n$-jet is approximated in the least square sense which leads to the following optimization problem

$$\begin{array}{r}min(\sum _{i=1}^N(J_{\overrightarrow{B},n}(x_i,y_i)-f(x_i,y_i){)}^2).\end{array}$$ This optimization problem results in a vector $\overrightarrow{B}$ that holds the first $n$ coefficients of the Taylor polynomial associated with the $n$-jet.

$$\begin{array}{}\text{(3.7)}& J_{\overrightarrow{B},n}=B_{0,0}+B_{1,0}x+B_{0,1}y+\frac{1}{2}(B_{2,0}{x}^2+2B_{1,1}xy+B_{0,2}{y}^2)+\dots .\end{array}$$ To calculate the curvatures of a surface requires at least a $2$-jet. The coefficients of the Taylor polynomial can then be used to calculate the Weingarten map (see Equation 3.2) with [66]

$$\begin{array}{}\text{(3.8)}& \begin{array}{ccl}E=1+B_{1,0}^2& & -f=\frac{2B_{0,2}}{\sqrt{1+B_{1,0}^2+B_{0,1}^2}}\\ F=B_{1,0}{B}_{0,1}& & -e=\frac{2B_{1,1}}{\sqrt{1+B_{1,0}^2+B_{0,1}^2}}\\ G=1+B_{0,1}^2& & -g=\frac{2B_{0,2}}{\sqrt{1+B_{1,0}^2+B_{0,1}^2}}\end{array}.\end{array}$$ The here presented discussion on 3D surfaces can be similarly adapted for 2D surfaces [66].

3.3 Curvature Calculation for Surface Meshes

Estimating the curvatures of a 3D surface mesh requires less computational effort than for point clouds, since the neighborhood of a vertex and information about the geometry is already present in the discretization. The general idea for calculating the curvatures of a surface mesh is to associate an infinitesimal area around a vertex with the value of an operator, further referred to as spatial averaging. Two different operators are required to calculate the Gaussian and mean curvatures. When the area around a vertex converges towards zero the value of the quotient between these operators and the area converges towards the desired curvature value [67]. Thus, first an appropriate area around each vertex on a surface mesh has to be determined. An appropriate area around a given vertex is given by the so-called Voronoi region [67]. Furthermore, each Voronoi cell (i.e., the Voronoi area each triangle contributes to the Voronoi region) minimizes the error introduced by the spatial averaging and the discretization [68].

Before the calculation of the Voronoi region is presented another concept has to be introduced. The set of all vertices incident to a vertex ${\mathbf{x}}_i$ is referred to as the 1-ring neighborhood of ${\mathbf{x}}_i$ ($N_1({\mathbf{x}}_i)$) (see Figure 3.6a).

Thus, the Voronoi region of a vertex ${\mathbf{x}}_i$ in a triangle mesh is calculated as follows

$$\begin{array}{}\text{(3.9)}& A_{\text{Voronoi}}=\frac{1}{8}\sum _{j\in N_1({\mathbf{x}}_i)}(\cot {\alpha }_{ij}+\cot {\beta }_{ij})\Vert {\mathbf{x}}_i-{\mathbf{x}}_j{\Vert }^2,\end{array}$$ see Figure 3.6b. This definition only holds for triangle meshes with non-obtuse triangles, which can in general not be guaranteed. The operators discussed further down in this section also result in valid curvature values for 1-ring neighborhoods which consist only of obtuse triangles. Therefore, the calculation of the area has to be adapted (see Algorithm 1) [67]. The algorithm checks each triangle in the 1-ring neighborhood, if a triangle is obtuse a fraction of its area is added to $A_{\text{mixed}}$, otherwise the area of the Voronoi cell is added. $A_{\text{mixed}}$ denotes the surface area of the mixed region around a vertex, the set of points making up the mixed region is referred to as $A_M$.

Mean Curvature

As previously hinted, surfaces with a constant mean curvature of $0$ describe a special class of surfaces: minimal surfaces. Minimal surfaces minimize the surface area of a surface, which lead to an ample body of literature [69, 70]. One of the investigated operators is the mean curvature normal operator which establishes a direct relation between the mean curvature flow and the minimization of the surface area [71]

$$\begin{array}{}\text{(3.10)}& \underset{\text{diam}(A_{\mathbf{p}})\to 0}{lim}\frac{\mathrm{\nabla }{A}_{\mathbf{p}}}{A_{\mathbf{p}}}=2H_{\mathbf{p}}{\overrightarrow{n}}_{\mathbf{p}},\end{array}$$ where $\mathrm{\nabla }{A}_{\mathbf{p}}$ stands for the gradient, and $A_{\mathbf{p}}$ for the area around the point $\mathbf{p}$. The mean curvature normal operator, also known as the Laplace-Beltrami operator, is defined as follows:

The integral of the Laplace-Beltrami operator over the area $A_{\text{mixed}}$ in a vertex ${\mathbf{x}}_i$ on a surface mesh can be discretized as follows [67]

$$\begin{array}{r}\underset{A_M}{\iint }\mathbf{\text{H}}({\mathbf{x}}_i)dA=\frac{1}{2}\sum _{j\in N_1({\mathbf{x}}_i)}(\cot {\alpha }_{ij}+\cot {\beta }_{ij})({\mathbf{x}}_i-{\mathbf{x}}_j).\end{array}$$ After inserting the discretized value of the Laplace-Beltrami operator and $A_{\text{mixed}}$ into Equation 3.10. The mean curvature of a vertex ${\mathbf{x}}_i$ on a surface mesh can be expressed as

$$\begin{array}{}\text{(3.11)}& H_{{\mathbf{x}}_i}=\frac{\Vert \sum _{j\in N_1({\mathbf{x}}_i)}(\cot {\alpha }_{ij}+\cot {\beta }_{ij})({\mathbf{x}}_i-{\mathbf{x}}_j)\Vert }{4A_{\text{mixed}}}.\end{array}$$

Gaussian Curvature

The Gaussian curvature, like the mean curvature, can also be expressed as a fraction of an infinitesimal area around a point as follows [72]

$$\begin{array}{r}\underset{\text{diam}(A_{\mathbf{p}})\to 0}{lim}\frac{A_{\mathbf{p}}^G}{A_{\mathbf{p}}}=K.\end{array}$$ To elaborate the meaning of $A_{\mathbf{p}}^G$, recall the definition of the Gauss map $\mathcal{N}$, it maps all normal vectors from a surface into the unit sphere. Consider a small surface area around a point $\mathbf{p}$ on an orientable surface, then the image of that area under $\mathcal{N}$ describes a small area on the surface of the unit sphere (e.g., $A_{\mathbf{p}}^G$). Instead of directly calculating the integral over the image of the Gauss map the Gauss-Bonnet theorem is used [67]

$$\begin{array}{r}\underset{A_M}{\iint }KdA+\sum _{i=0}^k{\epsilon }_i=2\pi .\end{array}$$ This is a simplified version of the theorem since the surface area of the sphere is investigated which has a geodesic curvature of $0$ [25]. The ${\epsilon }_i$ stand for the external angles of the boundary of the Voronoi region. For Voronoi regions it is easy to see that the angle at the vertex ${\mathbf{x}}_i$ is ${\theta }_i={\epsilon }_i$, because both edges of the Voronoi cell are perpendicular to the edges of the triangle and, therefore, ${\theta }_i+{\alpha }_i=\pi$ (see Figure 3.7). Thus, the Gaussian curvature of a vertex ${\mathbf{x}}_i$ on a surface mesh can be expressed as

$$\begin{array}{}\text{(3.12)}& K_{{\mathbf{x}}_i}=\frac{(2\pi -\sum _{j=1}^f{\theta }_j)}{A_{\text{mixed}}},\end{array}$$ where $f$ stands for the number of all triangles in $N({\mathbf{x}}_i)$.

3.4 Curvature Calculation for Implicit Surfaces

The computationally least expensive way to estimate the surface curvatures of a discrete surface considered in this work is the estimation for implicit surfaces, since, derivatives can be approximated directly from the discretization.

In this section three different approaches of calculating the surface curvatures of an implicitly defined surface are presented: The general formula for implicit surfaces, mean curvature estimation by calculating the variation of the normal vector, and mean curvature estimation through the shape operator. These three approaches are further analyzed in Chapter 5.

3.4.1 General Formula

The goal is to express Equations 3.4 and 3.5 with the derivatives of an implicit function $\varphi$. This is achieved in the following way, the determinants and traces are transformed such that they are expressed with respect to a local parametrized $\mathbf{x}$ and the normal vector $\overrightarrow{n}$ defined by the chosen parametrization [73]

$$\begin{array}{}\text{(3.13)}& K& =\frac{({\mathbf{x}}_u\times {\mathbf{x}}_v)\cdot ({\overrightarrow{n}}_u\times {\overrightarrow{n}}_v)}{\Vert {\mathbf{x}}_u\times {\mathbf{x}}_v{\Vert }^2},\text{(3.14)}& H& =\frac{({\mathbf{x}}_u\times {\mathbf{x}}_v)\cdot (({\mathbf{x}}_v\times {\overrightarrow{n}}_u)-({\mathbf{x}}_u\times {\overrightarrow{n}}_v))}{2\Vert {\mathbf{x}}_u\times {\mathbf{x}}_v{\Vert }^2}.\end{array}$$ Afterwards, the terms of the above equations are transformed such that they are expressed as the derivatives of the implicit function. This is achieved with the help of matrix identities, which transform the above expressions into [73]

$$\begin{array}{}\text{(3.15)}& K& =\frac{\mathrm{\nabla }\varphi \text{adj}(\text{Hess}(\varphi ))\mathrm{\nabla }{\varphi }^T}{\Vert \mathrm{\nabla }\varphi {\Vert }^4},\text{(3.16)}& H& =\frac{\mathrm{\nabla }\varphi \text{Hess}(\varphi )\mathrm{\nabla }{\varphi }^T-\Vert \mathrm{\nabla }\varphi {\Vert }^2\text{trace}(\text{Hess}(\varphi ))}{2\Vert \mathrm{\nabla }\varphi {\Vert }^3},\end{array}$$ where $\text{Hess}(\varphi )$ stands for the Hessian matrix of $\varphi$. Furthermore, the mean curvature of an implicit surface can be expressed as

$$\begin{array}{}\text{(3.17)}& H=\mathrm{\nabla }\cdot \frac{\mathrm{\nabla }\varphi }{\Vert \mathrm{\nabla }\varphi \Vert },\end{array}$$ which can be seen by expanding Equation 3.16 and Equation 3.17 and comparing the resulting terms.

Now that an expression for the curvatures of an implicit surface is available it has to be discussed how these formulas can be used on discretized implicit surfaces. Considering a discretized implicit surface as defined in Section 2.3 (e.g., a level-set function), the derivatives of a level-set function can be approximated by central differences as follows

$$\begin{array}{}\text{(3.18)}& D_x({\varphi }_{i,j,k})& \approx \frac{{\varphi }_{i+1,j,k}-{\varphi }_{i-1,j,k}}{2\mathrm{\Delta }x},\text{(3.19)}& D_{xx}({\varphi }_{i,j,k})& \approx \frac{{\varphi }_{i+1,j,k}-2{\varphi }_{i,j,k}+{\varphi }_{i-1,j,k}}{\mathrm{\Delta }{x}^2},\text{(3.20)}& D_{xy}({\varphi }_{i,j,k})& \approx \frac{{\varphi }_{i+1,j+1,k}-{\varphi }_{i-1,j+1,k}-{\varphi }_{i+1,j-1,k}+{\varphi }_{i-1,j-1,k}}{4\mathrm{\Delta }x\mathrm{\Delta }y},\end{array}$$ where ${\varphi }_{i,j,k}$ stands for the $\varphi$-value of the level-set function at the grid point $(i,j,k)$, if the subscript indices are omitted it is assumed that they are $(i,j,k)$. Using these approximations and an expanded form of Equation 3.16, the discretized mean curvature of a level-set function can be approximated as follows

$$\begin{array}{}\text{(3.21)}& H=\frac{{\displaystyle \genfrac{}{}{0ex}{}{D_x(\varphi {)}^2(D_{yy}(\varphi )+D_{zz}(\varphi ))\hfill }{\hfill \genfrac{}{}{0ex}{}{+D_y(\varphi {)}^2(D_{xx}(\varphi )+D_{zz}(\varphi ))\hfill }{\hfill \genfrac{}{}{0ex}{}{+D_z(\varphi {)}^2(D_{xx}(\varphi )+D_{yy}(\varphi ))\hfill }{\hfill \genfrac{}{}{0ex}{}{-2D_x(\varphi )D_y(\varphi )D_{xy}(\varphi )\hfill }{\hfill \genfrac{}{}{0ex}{}{-2D_y(\varphi )D_z(\varphi )D_{yz}(\varphi )\hfill }{\hfill -2D_z(\varphi )D_x(\varphi )D_{xz}(\varphi )}}}}}}}{2\Vert \mathrm{\nabla }\varphi {\Vert }^3}.\end{array}$$ This method of calculating the mean curvature will be referred to as the General Formula method. The Gaussian curvature can be calculated similarly by using an expanded form of Equation 3.15

$$\begin{array}{}\text{(3.22)}& K=\frac{{\displaystyle \genfrac{}{}{0ex}{}{D_x(\varphi {)}^2(D_{yy}(\varphi )D_{zz}(\varphi )-D_{yz}(\varphi {)}^2)\hfill }{\hfill {\displaystyle \genfrac{}{}{0ex}{}{+D_y(\varphi {)}^2(D_{xx}(\varphi )D_{zz}(\varphi )-D_{xz}(\varphi {)}^2)\hfill }{\hfill {\displaystyle \genfrac{}{}{0ex}{}{+D_z(\varphi {)}^2(D_{xx}(\varphi )D_{yy}(\varphi )-D_{xy}(\varphi {)}^2)\hfill }{\hfill {\displaystyle \genfrac{}{}{0ex}{}{+2D_x(\varphi )D_y(\varphi )(D_{xz}(\varphi )D_{yz}(\varphi )-D_{xy}(\varphi )D_{zz}(\varphi ))\hfill }{\hfill {\displaystyle \genfrac{}{}{0ex}{}{+2D_x(\varphi )D_z(\varphi )(D_{xy}(\varphi )D_{yz}(\varphi )-D_{xz}(\varphi )D_{yy}(\varphi ))\hfill }{\hfill +2D_y(\varphi )D_z(\varphi )(D_{xy}(\varphi )D_{xz}(\varphi )-D_{yz}(\varphi )D_{xx}(\varphi ))}}}}}}}}}}}{(D_x(\varphi {)}^2+D_y(\varphi {)}^2+D_z(\varphi {)}^2{)}^2}.\end{array}$$ Calculating the Gaussian curvature requires the same derivatives as calculating the mean curvature.

The finite difference approximations used for calculating the surface curvatures require a certain amount of grid points to be calculated. The set of all grid points required for the calculation of a set of finite differences is referred to as a finite difference stencil, or just stencil ($\eta (\mathbf{x})$). A finite difference stencil is always considered with respect to the central grid point $\mathbf{x}=(i,j,k)$. Two finite difference stencils are of particular importance for this work, the $7$ point star stencil (${\eta }_S(\mathbf{x})$), and the $19$ point plane stencil (${\eta }_P(\mathbf{x})$). Figure 3.8 shows an illustration of these stencils. Calculating the surface curvature with the General Formula requires a plane stencil.

Lastly it should be mentioned that the maximal curvature a level-set function can describe is bound by $\mathrm{p}\mathrm{m}1/\mathrm{\Delta }x$ [15], since the smallest circle radius which can be represented with a given resolution is $\mathrm{\Delta }x$.

3.4.2 Shape Operator

Recalling Equation 3.17, the formula states that the mean curvature of an implicit surface can be expressed as the gradient of the normal vector. This expression can be expanded and leads to the following expression [75]

$$\begin{array}{}\text{(3.23)}& \mathrm{\nabla }\cdot \frac{\mathrm{\nabla }\varphi }{\Vert \mathrm{\nabla }\varphi \Vert }=\mathrm{\nabla }\overrightarrow{n}=-\frac{1}{\Vert \mathrm{\nabla }\varphi \Vert }(I-\overrightarrow{n}{\overrightarrow{n}}^T)\text{Hess}(\varphi ),\end{array}$$ where $I$ stands for the Identity matrix.

Assuming that the level-set function fulfills the Eikonal equation (see Equation 2.8) with $F(\mathbf{x})=1$, then the term $1/\Vert \varphi \Vert$ can be ignored. The matrix $(I-\overrightarrow{n}{\overrightarrow{n}}^T)$ projects onto the tangent plane of the implicit surface. Restricting $\mathrm{\nabla }\overrightarrow{n}$ to the tangent plane shows that it is symmetric [75]. Thus, there exists an orthonormal basis $[\overrightarrow{p_1},\overrightarrow{p_2}]$ in ${\mathbb{R}}^2$ of the tangent plane, this basis can be expanded to an orthonormal basis in ${\mathbb{R}}^3$ as follows $[\overrightarrow{p_1},\overrightarrow{p_2},\overrightarrow{n}]$. When the gradient of the normal vector is expressed in this basis it results in the following matrix

$$\begin{array}{}\text{(3.24)}& \mathrm{\nabla }\overrightarrow{n}=\left(\begin{array}{ccc}{\kappa }_1& 0& {\sigma }_1\\ 0& {\kappa }_2& {\sigma }_2\\ 0& 0& 0\end{array}\right).\end{array}$$ Here, ${\kappa }_1$ and ${\kappa }_2$ stand for the principal curvatures with the principal directions $\overrightarrow{p_1}$ and $\overrightarrow{p_2}$, ${\sigma }_1$ and ${\sigma }_2$ stand for the so-called flow line curvatures [75]. So the mean curvature of the surface can be expressed as $\text{trace}(\mathrm{\nabla }\overrightarrow{n})/2$. Furthermore, the trace of a matrix is independent of the chosen basis, thus the mean curvature of a level-set function $\varphi$ with $\Vert \mathrm{\nabla }\varphi \Vert =1$ can be expressed as

$$\begin{array}{}\text{(3.25)}& H=\frac{\text{trace}(\text{Hess}({\varphi }_{i,j,k}))}{2}=\frac{D_{xx}({\varphi }_{i,j,k})+D_{yy}({\varphi }_{i,j,k})+D_{zz}({\varphi }_{i,j,k})}{2}.\end{array}$$ This method is referred to as the Shape Operator method. In Section 4.1.2 a method is discussed that describes how a level-set function can be constructed that fulfills $\Vert \mathrm{\nabla }\varphi \Vert =1$. Calculating the mean curvature of the zero level-set using the Shape Operator method requires a star stencil ${\eta }_S$. It should be mentioned that the quality of the mean curvature calculated with this method on a discretized surface is highly dependent on the quality of the discretization, which is discussed further in Section 5.1.3.

3.4.3 Variation of Normal

The third method calculates the mean curvature of the level-set function by again using Equation 3.17 which is approximated through the Euler-Lagrange derivative [76, 77]. In addition to the first-order central differences, this approximation requires the first-order forward and backward differences which can be approximated by

$$\begin{array}{}\text{(3.26)}& D_x^{+}({\varphi }_{i,j,k})\approx \frac{{\varphi }_{i+1,j,k}-{\varphi }_{i,j,k}}{\mathrm{\Delta }x},\end{array}$$

$$\begin{array}{}\text{(3.27)}& D_x^{-}({\varphi }_{i,j,k})\approx \frac{{\varphi }_{i,j,k}-{\varphi }_{i-1,j,k}}{\mathrm{\Delta }x}.\end{array}$$ In turn, the mean curvature can be approximated as [77]

$$\begin{array}{c}H=\mathrm{\nabla }\cdot \frac{\mathrm{\nabla }\varphi }{\Vert \mathrm{\nabla }\varphi \Vert }\approx \frac{1}{2\mathrm{\Delta }x}((\frac{D_x^{+}(\varphi )}{\Vert {\overrightarrow{g}}_x^{+}\Vert }-\frac{D_x^{-}(\varphi )}{\Vert {\overrightarrow{g}}_x^{-}\Vert })+\hfill \\ \text{(3.28)}& \hfill (\frac{D_y^{+}(\varphi )}{\Vert {\overrightarrow{g}}_y^{+}\Vert }-\frac{D_y^{-}(\varphi )}{\Vert {\overrightarrow{g}}_y^{-}\Vert })+(\frac{D_z^{+}(\varphi )}{\Vert {\overrightarrow{g}}_z^{+}\Vert }-\frac{D_z^{-}(\varphi )}{\Vert {\overrightarrow{g}}_z^{-}\Vert })),\end{array}$$ where ${\overrightarrow{g}}_x^{\mathrm{p}\mathrm{m}}$ is defined as

$$\begin{array}{}\text{(3.29)}& \begin{array}{rl}{\overrightarrow{g}}_x^{\mathrm{p}\mathrm{m}}:=(D_x^{\mathrm{p}\mathrm{m}}({\varphi }_{i,j,k}),& \frac{1}{2}(D_y({\varphi }_{ij,k})+D_y({\varphi }_{i\mathrm{p}\mathrm{m}1,j,k})),\\ & \frac{1}{2}(D_z({\varphi }_{i\mathrm{p}\mathrm{m}1,j,k})+D_z({\varphi }_{i,j,k}))),\end{array}\end{array}$$

$$\begin{array}{}\text{(3.30)}& \begin{array}{rl}{\overrightarrow{g}}_y^{\mathrm{p}\mathrm{m}}:=(D_y^{\mathrm{p}\mathrm{m}}({\varphi }_{i,j,k}),& \frac{1}{2}(D_x({\varphi }_{i,j\mathrm{p}\mathrm{m}1,k})+D_x({\varphi }_{i,j,k})),\\ & \frac{1}{2}(D_z({\varphi }_{i,j\mathrm{p}\mathrm{m}1,k})+D_z({\varphi }_{i,j,k}))),\end{array}\end{array}$$

$$\begin{array}{}\text{(3.31)}& \begin{array}{rl}{\overrightarrow{g}}_z^{\mathrm{p}\mathrm{m}}:=(D_z^{\mathrm{p}\mathrm{m}}({\varphi }_{i,j,k})),& \frac{1}{2}(D_x({\varphi }_{i,j,k\mathrm{p}\mathrm{m}1})+D_x({\varphi }_{i,j,k})),\\ & \frac{1}{2}(D_y({\varphi }_{i,j,k\mathrm{p}\mathrm{m}1})+D_y({\varphi }_{i,j,k})).\end{array}\end{array}$$ To calculate all the required finite differences a plane stencil ${\eta }_P$ is required, this method is referred to as the Variation of Normal method. This method only calculates the mean curvature, thus, the Gaussian curvature has to be estimated separately by using Equation 3.22.

3.4.4 Curvature of 2D Implicit Surfaces (Curves)

An analogous construction to the one presented in Section 3.4.1 can be done for regular curves (i.e., 2D surfaces) [73]. Recall that regular curves only have one type of curvature which can be approximated for a 2D level-set function with the formula

$$\begin{array}{}\text{(3.32)}& \kappa =\frac{D_y(\varphi {)}^2{D}_{xx}(\varphi )-2D_x(\varphi )D_y(\varphi )D_{xy}(\varphi )+D_x(\varphi {)}^2{D}_{yy}(\varphi )}{\Vert \mathrm{\nabla }\varphi {\Vert }^3}.\end{array}$$

3.5 Intuitive Approach to Surface Classification

When considering the construction of the normal curvature presented in Section 3.1.2 one can see that the normal curvatures are defined through the curvature of a parametrized curve and the cosine of the angle between the surface normal and the normal of the considered parametrized curve. It is tempting to drop the formal mathematics behind curvature calculation and try to directly use the angle between the normal vectors of surface points in a neighborhood on a discretized surface for surface classification. However, this approach has several drawbacks which are discussed in the remainder of this section. The most striking drawback is, that this approach can only estimate angles with points of the discretization without any knowledge of the underlying parametrization of the surface.

Point Clouds

Consider a point cloud and a neighborhood $M_i({\mathbf{x}}_i)$ of a point ${\mathbf{x}}_i$. The relative spatial position of the points in the neighborhood with respect to the investigated point ${\mathbf{x}}_i$ is not known. So, it is possible that two points in the neighborhood describe the same curve on the surface and that one point is farther away from ${\mathbf{x}}_i$. In this scenario it is not known which of the two points should be chosen for the classification of the surface which can lead to wrong classifications. Therefore, this approach is not suited for point clouds.

Surface Meshes

The triangles of a surface mesh are flat, thus, they have a mean and Gaussian curvature of 0. A similar argument can be used for edges, since the surface can only bend in one direction over an edge. Consequently, using the angle between normal vectors can of course only be used on vertices on a surface mesh, but there is no straightforward way to calculate the surface normal of a vertex. Which again, as with point clouds, makes this approach unsuited for surface meshes.

Level-Set Functions (Implicit Surfaces)

Finally, considering level-set function, some merit can be found in applying the normal vector angle approach. All points on a regular grid have the same distance from each other, so one could check if the points that lie in a box stencil (see Figure 3.9) are surface points (i.e., the level-set function changes sign from the point ${\mathbf{x}}_i$ to this neighboring point). However, depending on the position of the zero level-set more points in the stencil are required, i.e., $21$ in 2D and $81$ in 3D, which is a lot more than calculating the derivatives for curvature calculation. Further drawbacks of this method on level-set functions are discussed in Section 5.1.4.