Geometry processing

Geometry 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.

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.

At its "birth," a shape can be instantiated through one of three methods: a model, a mathematical representation, or a scan.

This can mean it is consumed by a viewer as a rendered asset in a game or movie, for instance.

In addition to triangles, a more general class of polygon meshes can also be used to represent a shape.

[2] One particularly important property of a 3D shape is its Euler characteristic, which can alternatively be defined in terms of its genus.

To bring this into the discrete world, the Euler characteristic of a mesh is computed in terms of its vertices, edges, and faces.

To transform the surface points into a mesh, the Poisson reconstruction[3] strategy can be employed.

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.

lie on the surface to be reconstructed, the marching cubes algorithm can be used to construct a triangle mesh from the function

One common problem encountered in geometry processing is how to merge multiple views of a single object captured from different angles or positions.

In the following iteration, the projections are calculated based on the result of applying the previous transformation on the samples.

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

Because the variation is free, this results in a self-adjoint linear problem to solve with a parameter

[5] The mass matrix M as an operator computes the local integral of a function's value and is often set for a mesh with m triangles as follows:

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.

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.

The wobbliness and distortion apparent in the mass springs methods are due to high variations in the u and v coordinate functions.

[8] In point-based deformation, a user can apply transformations to small set of points, called handles, on the shape.

Skeleton-based deformation defines a skeleton for the shape, which allows a user to move the bones and rotate the joints.

Handles provide a sparse set of constraints for the deformation: as the user moves one point, the others must stay in place.

[9] Applying the Laplace operator to these mappings allows us to measure how the position of a point changes relative to its neighborhood, which keeps the handles smooth.

While seemingly trivial, in many cases, determining the inside from the outside of a triangle mesh is not an easy problem.

The naive attempt to solve this problem is to shoot many rays in random directions, and classify

is a harmonic function, it degrades gracefully, meaning the inside-outside segmentation would not change much if we poked holes in a closed mesh.

For this reason, the Generalized Winding Number handles open meshes robustly.

Polygon Mesh Processing by Mario Botsch et al. is a textbook on the topic of Geometry Processing. [ 1 ]
A mesh of a cactus showing the Gaussian Curvature at each vertex, using the angle defect method
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.
This image shows a mesh of a pair of pants, with Euler characteristic -1. This is explained by the equation to compute the characteristic: 2c - 2h - b. The mesh has 1 connected component, 0 topological holes, and 3 boundaries (the waist hole and each leg hole): 2 - 0 - 3 = -1.
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.
A noisy sphere being iteratively smoothed
The Tutte Embedding shows non-smooth parameterizations on the side of the beetle.
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.
An example of as-rigid-as-possible deformation
Approximating inside-outside segmentation by shooting rays from a query point for varying number of rays