# Geometry processing

Polygon Mesh Processing by Mario Botsch et al. is a textbook on the topic of Geometry Processing[1].

Geometry processing, or mesh processing, is an area of research that uses concepts from applied mathematics, computer science and engineering to design efficient algorithms for the acquisition, reconstruction, analysis, manipulation, simulation and transmission of complex 3D models. As the name implies, geometry processing is meant to be analogous to signal processing and image processing. Many concepts, data structures and algorithms are directly analogous. For example, where image smoothing might convolve an intensity signal with a blur kernel formed using the Laplace operator, geometric smoothing might be achieved by convolving a surface geometry with a blur kernel formed using the Laplace-Beltrami operator.

Applications of geometry processing algorithms already cover a wide range of areas from multimedia, entertainment and classical computer-aided design, to biomedical computing, reverse engineering and scientific computing.[1]

Geometry processing is a common research topic at SIGGRAPH, the premier computer graphics academic conference, and the main topic of the annual Symposium on Geometry Processing.

## Properties of a shape

A mesh of the famous Stanford bunny. Shapes are usually represented as a mesh, a collection of polygons that delineate the contours of the shape.

Geometry processing involves working with a shape, usually in 2D or 3D, although the shape can live in a space of arbitrary dimensions. The processing of a shape involves three stages, which is known as its life cycle. At its "birth," a shape can be instantiated through one of three methods: a model, a mathematical representation, or a scan. After a shape is born, it can be analyzed and edited repeatedly in a cycle. This usually involves acquiring different measurements, such as the distances between the points of the shape, the smoothness of the shape, or its Euler characteristic. Editing may involve denoising, deforming, or performing rigid transformations. Finally, at the final stage of the shape's "life," it is consumed as a product. For example, it can be sent to a 3D printer to be used as a physical model.

A mesh of a cactus showing the Gaussian Curvature at each vertex, using the angle defect method.

Like any other shape, the shapes used in geometry processing have properties pertaining to their geometry and topology. The geometry of a shape concerns the position of the shape's points in space, tangents, normals, and curvature. It also includes the dimension in which the shape lives (ex. ${\displaystyle R^{2}}$ or ${\displaystyle R^{3}}$). The topology of a shape is a collection of properties that do not change even after smooth transformations have been applied to the shape. It concerns dimensions such as the number of holes and boundaries, as well as the orientability of the shape. One example of a non-orientable shape is the Mobius strip.

## Surface reconstruction

### Poisson reconstruction from surface points to mesh

A triangle mesh is constructed out of a point cloud. Sometimes shapes are initialized only as "point clouds," a collection of sampled points from the shape's surface. Often, these point clouds need to be converted to meshes.

Depending on how a shape is initialized or "birthed," the shape might exist only as a nebula of sampled points that represent its surface in space. To transform the surface points into a mesh, the Poisson reconstruction[2] strategy can be employed. This method states that the indicator function, a function that determines which points in space belong to the surface of the shape, can actually be computed from the sampled points. The key concept is that gradient of the indicator function is 0 everywhere, except at the sampled points, where it is equal to the inward surface normal. More formally, suppose the collection of sampled points from the surface is denoted by ${\displaystyle S}$, each point in the space by ${\displaystyle p_{i}}$, and the corresponding normal at that point by ${\displaystyle n_{i}}$. Then the gradient of the indicator function is defined as:

${\displaystyle \triangledown g={\begin{cases}{\textbf {n}}_{i},&\forall p_{i}\in S\\0,&{\text{otherwise}}\end{cases}}}$

The task of reconstruction then becomes a variational problem. To find the indicator function of the surface, we must find a function ${\displaystyle \chi }$ such that ${\displaystyle \lVert \triangledown \chi -{\textbf {V}}\rVert }$ is minimized, where ${\displaystyle {\textbf {V}}}$ is the vector field defined by the samples.

## Registration

An animation depicting registration of a partial mesh onto a complete mesh, with piecewise constant approximation of the projection function.
An animation depicting the same registration procedure as above, but with piecewise linear approximation of the projection function. Note that it converges much faster.

One common problem encountered in geometry processing is how to merge multiple views of a single object captured from different angles or positions. This problem is known as registration. In registration, we wish to find an optimal rigid transformation that will align surface ${\displaystyle X}$ with surface ${\displaystyle Y}$. More formally, if ${\displaystyle P_{Y}(x)}$ is the projection of a point x from surface ${\displaystyle X}$ onto surface ${\displaystyle Y}$, we want to find the optimal rotation matrix ${\displaystyle R}$ and translation vector ${\displaystyle t}$ that minimize the following objective function:

${\displaystyle \int _{x\in X}||Rx+t-P_{Y}(x)||dx}$

While rotations are non-linear in general, small rotations can be linearized as skew-symmetric matrices. Moreover, the distance function ${\displaystyle x-P_{Y}(x)}$ is non-linear, but is amenable to linear approximations if the change in ${\displaystyle X}$ is small. An iterative solution such as Iterative Closest Point (ICP) is therefore employed to solve for small transformations iteratively, instead of solving for the potentially large transformation in one go. In ICP, n random sample points from ${\displaystyle X}$ are chosen and projected onto ${\displaystyle Y}$. Then the optimal transformation is calculated based on the difference between each ${\displaystyle x}$ and its projection. In the following iteration, the projections are calculated based on the result of applying the previous transformation on the samples. The process is repeated until convergence.

## Smoothing

When shapes are defined or scanned, there may be accompanying noise, either to a signal acting upon the surface or to the actual surface geometry. Reducing noise on the former is known as data denoising, while noise reduction on the latter is known as surface fairing. The task of geometric smoothing is analogous to signal noise reduction, and consequently employs similar approaches.

The pertinent Lagrangian to be minimized is derived by recording the conformity to the initial signal ${\displaystyle {\bar {f}}}$ and the smoothness of the resulting signal, which approximated by the magnitude of the gradient with a weight ${\displaystyle \lambda }$:

${\displaystyle {\mathcal {L}}(f)=\int _{\Omega }\|f-{\bar {f}}\|^{2}+\lambda \|\nabla f\|^{2}dx}$.

Taking a variation ${\displaystyle \delta f}$ on ${\displaystyle {\mathcal {L}}}$ emits the necessary condition

${\displaystyle 0=\delta {\mathcal {L}}(f)=\int _{\Omega }\delta f(\mathbf {I} +\lambda \nabla ^{2})f-\delta f{\bar {f}}dx}$.

By discretizing this onto piecewise-constant elements with our signal on the vertices we obtain

{\displaystyle {\begin{aligned}\sum _{i}M_{i}\delta f_{i}{\bar {f}}_{i}&=\sum _{i}M_{i}\delta f_{i}\sum _{j}(\mathbf {I} +\lambda \nabla ^{2})f_{j}=\sum _{i}\delta f_{i}\sum _{j}(M+\lambda M\nabla ^{2})f_{j},\end{aligned}}}

A noisy sphere being iteratively smoothed.

where our choice of ${\displaystyle \nabla ^{2}}$ is chosen to be ${\displaystyle M^{-1}\mathbf {L} }$ for the cotangent Laplacian ${\displaystyle \mathbf {L} }$ and the ${\displaystyle M^{-1}}$ term is to map the image of the Laplacian from areas to points. Because the variation is free, this results in a self-adjoint linear problem to solve with a parameter ${\displaystyle \lambda }$: ${\displaystyle {\bar {f}}=(M+\lambda \mathbf {L} )f.}$ When working with triangle meshes one way to determine the values of the Laplacian matrix ${\displaystyle L}$ is through analyzing the geometry of connected triangles on the mesh.

${\displaystyle L_{ij}={\begin{cases}{\frac {1}{2}}(cot(\alpha _{ij})+cot(\beta _{ij}))&{\text{edge ij exists}}\\-\sum \limits _{i\neq j}L_{ij}&i=j\\0&{\text{otherwise}}\end{cases}}}$

Where ${\displaystyle \alpha _{ij}}$ and ${\displaystyle \beta _{ij}}$ are the angles opposite the edge ${\displaystyle (i,j)}$[3]

## Parameterization

Occasionally, we need to flatten a 3D surface onto a flat plane. This process is known as parameterization. The goal is to find coordinates u and v onto which we can map the surface so that distortions are minimized. In this manner, parameterization can be seen as an optimization problem. One of the major applications of mesh parameterization is texture mapping.

### Mass springs method

The Tutte Embedding shows non-smooth parameterizations on the side of the beetle.

One way to measure the distortion accrued in the mapping process is to measure how much the length of the edges on the 2D mapping differs from their lengths in the original 3D surface. In more formal terms, the objective function can be written as:

${\displaystyle {\underset {U}{\text{min}}}\sum _{ij\in E}||u_{i}-u_{j}||^{2}}$

Where ${\displaystyle E}$ is the set of mesh edges and ${\displaystyle U}$ is the set of vertices. However, optimizing this objective function would result in a solution that maps all of the vertices to a single vertex in the uv-coordinates. Borrowing an idea from graph theory, we apply the Tutte Mapping and restrict the boundary vertices of the mesh onto a unit circle or other convex polygon. Doing so prevents the vertices from collapsing into a single vertex when the mapping is applied. The non-boundary vertices are then positioned at the barycentric interpolation of their neighbours. The Tutte Mapping, however, still suffers from severe distortions as it attempts to make the edge lengths equal, and hence does not correctly account for the triangle sizes on the actual surface mesh.

### Least-squares conformal mappings

A comparison of the Tutte Embedding and Least-Squares-Conformal-Mapping parameterization. Notice how the LSCM parameterization is smooth on the side of the beetle.

Another way to measure the distortion is to consider the variations on the u and v coordinate functions. The wobbliness and distortion apparent in the mass springs methods are due to high variations in the u and v coordinate functions. With this approach, the objective function becomes the Dirichlet energy on u and v:

${\displaystyle {\underset {u,v}{\text{min}}}\int _{S}||\nabla u||^{2}+||\nabla v||^{2}dA}$

There are a few other things to consider. We would like to minimize the angle distortion to preserve orthogonality. That means we would like ${\displaystyle \nabla u=\nabla v^{\perp }}$. In addition, we would also like the mapping to have proportionally similar sized regions as the original. This results to setting the Jacobian of the u and v coordinate functions to 1.

${\displaystyle {\begin{bmatrix}{\dfrac {\partial u}{\partial x}}&{\dfrac {\partial u}{\partial y}}\\[1em]{\dfrac {\partial v}{\partial x}}&{\dfrac {\partial v}{\partial y}}\end{bmatrix}}=1}$

Putting these requirements together, we can augment the Dirichlet energy so that our objective function becomes:[4][5]

${\displaystyle {\underset {u,v}{\text{min}}}\int _{S}{\frac {1}{2}}||\nabla u||^{2}+{\frac {1}{2}}||\nabla v||^{2}-\nabla u\cdot \nabla v^{\perp }}$

To avoid the problem of having all the vertices mapped to a single point, we also require that the solution to the optimization problem must have a non-zero norm and that it is orthogonal to the trivial solution.