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.  As the name implies, many of the concepts, data structures, and algorithms are directly analogous to signal processing and image processing. 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.

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.

Geometry processing as a life cycle 

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. At the final stage of the shape's "life," it is consumed. This can mean it is consumed by a viewer as a rendered asset in a game or movie, for instance. The end of a shape's life can also be defined by a decision about the shape, like whether or not it satisfies some criteria. Or it can even be fabricated in the real world, through a method such as 3D printing or laser cutting.

Discrete Representation of a Shape 
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.  or ). 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.

In computers, everything must be discretized. Shapes in geometry processing are usually represented as triangle meshes, which can be seen as a graph. Each node in the graph is a vertex (usually in ), which has a position. This encodes the geometry of the shape. Directed edges connect these vertices into triangles, which by the right hand rule, then have a direction called the normal. Each triangle forms a face of the mesh. These are combinatoric in nature and encode the topology of the shape. In addition to triangles, a more general class of polygon meshes can also be used to represent a shape. More advanced representations like progressive meshes encode a coarse representation along with a sequence of transformations, which produce a fine or high resolution representation of the shape once applied. These meshes are useful in a variety of applications, including geomorphs, progressive transmission, mesh compression, and selective refinement.

Properties of a shape

Euler Characteristic 
One particularly important property of a 3D shape is its Euler characteristic, which can alternatively be defined in terms of its genus. The formula for this in the continuous sense is , where  is the number of connected components,  is number of holes (as in donut holes, see torus), and  is the number of connected components of the boundary of the surface. A concrete example of this is a mesh of a pair of pants. There is one connected component, 0 holes, and 3 connected components of the boundary (the waist and two leg holes). So in this case, the Euler characteristic is -1. To bring this into the discrete world, the Euler characteristic of a mesh is computed in terms of its vertices, edges, and faces. .

Surface reconstruction

Poisson reconstruction from surface points to mesh 

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 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 , each point in the space by , and the corresponding normal at that point by . Then the gradient of the indicator function is defined as:

The task of reconstruction then becomes a variational problem. To find the indicator function of the surface, we must find a function  such that  is minimized, where  is the vector field defined by the samples. As a variational problem, one can view the minimizer as a solution of Poisson's equation. After obtaining a good approximation for  and a value   for which the points  with  lie on the surface to be reconstructed, the marching cubes algorithm can be used to construct a triangle mesh from the function   , which can then be applied in subsequent computer graphics applications.

Registration 

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  with surface . More formally, if  is the projection of a point x from surface  onto surface , we want to find the optimal rotation matrix  and translation vector  that minimize the following objective function:

While rotations are non-linear in general, small rotations can be linearized as skew-symmetric matrices. Moreover, the distance function  is non-linear, but is amenable to linear approximations if the change in  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  are chosen and projected onto . In order to sample points uniformly at random across the surface of the triangle mesh, the random sampling is broken into two stages: uniformly sampling points within a triangle; and non-uniformly sampling triangles, such that each triangle's associated probability is proportional to its surface area. Thereafter, the optimal transformation is calculated based on the difference between each  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  and the smoothness of the resulting signal, which approximated by the magnitude of the gradient with a weight :

.

Taking a variation  on  emits the necessary condition

.

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

where our choice of  is chosen to be  for the cotangent Laplacian  and the  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 :  When working with triangle meshes one way to determine the values of the Laplacian matrix  is through analyzing the geometry of connected triangles on the mesh.

Where  and  are the angles opposite the edge 
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:

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 

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:

Where  is the set of mesh edges and  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 

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:

There are a few other things to consider. We would like to minimize the angle distortion to preserve orthogonality. That means we would like . 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.

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

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.

Deformation 

Deformation is concerned with transforming some rest shape to a new shape. Typically, these transformations are continuous and do not alter the topology of the shape. Modern mesh-based shape deformation methods satisfy user deformation constraints at handles (selected vertices or regions on the mesh) and propagate these handle deformations to the rest of shape smoothly and without removing or distorting details. Some common forms of interactive deformations are point-based, skeleton-based, and cage-based. 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. Cage-based deformation requires a cage to be drawn around all or part of a shape so that, when the user manipulates points on the cage, the volume it encloses changes accordingly.

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

A rest surface  immersed in  can be described with a mapping , where  is a 2D parametric domain. The same can be done with another mapping  for the transformed surface . Ideally, the transformed shape adds as little distortion as possible to the original. One way to model this distortion is in terms of displacements  with a Laplacian-based energy. 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. Thus, the energy we would like to minimize can be written as:

.

While this method is translation invariant, it is unable to account for rotations. The As-Rigid-As-Possible deformation scheme applies a rigid transformation  to each handle i, where  is a rotation matrix and  is a translation vector. Unfortunately, there's no way to know the rotations in advance, so instead we pick a “best” rotation that minimizes displacements. To achieve local rotation invariance, however, requires a function  which outputs the best rotation for every point on the surface. The resulting energy, then, must optimize over both  and :

Note that the translation vector is not present in the final objective function because translations have constant gradient.

Inside-Outside Segmentation 
While seemingly trivial, in many cases, determining the inside from the outside of a triangle mesh is not an easy problem. In general, given a surface  we pose this problem as determining a function  which will return  if the point  is inside , and  otherwise.

In the simplest case, the shape is closed. In this case, to determine if a point  is inside or outside the surface, we can cast a ray  in any direction from a query point, and count the number of times  it passes through the surface. If  was outside  then the ray must either not pass through  (in which case ) or, each time it enters  it must pass through twice, because S is bounded, so any ray entering it must exit. So if  is outside,  is even. Likewise if  is inside, the same logic applies to the previous case, but the ray must intersect  one extra time for the first time it leaves . So:

Now, oftentimes we cannot guarantee that the  is closed. Take the pair of pants example from the top of this article. This mesh clearly has a semantic inside-and-outside, despite there being holes at the waist and the legs.

The naive attempt to solve this problem is to shoot many rays in random directions, and classify  as being inside if and only if most of the rays intersected  an odd number of times. To quantify this, let us say we cast  rays, . We associate a number  which is the average value of  from each ray. Therefore:

In the limit of shooting many, many rays, this method handles open meshes, however it in order to become accurate, far too many rays are required for this method to be computationally ideal. Instead, a more robust approach is the Generalized Winding Number. Inspired by the 2D winding number, this approach uses the solid angle at  of each triangle in the mesh to determine if  is inside or outside. The value of the Generalized Winding Number at ,  is proportional to the sum of the solid angle contribution from each triangle in the mesh:

For a closed mesh,  is equivalent to the characteristic function for the volume represented by . Therefore, we say:

Because  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. The boundary between inside and outside smoothly passes over holes in the mesh. In fact, in the limit, the Generalized Winding Number is equivalent to the ray-casting method as the number of rays goes to infinity.

Applications 
 Computer-aided design (CAD)
 3D Surface Reconstruction, e.g. range scanners in airport security, autonomous vehicles, medical scanner data reconstruction
 Image-to-world Registration, e.g. Image-guided surgery
 Architecture, e.g. creating, reverse engineering
 Physics simulations
 Computer games e.g. collision detection
 Geologic modelling
 Visualization (graphics) e.g. Information visualizations, mathematical visualizations
 Texture mapping
 Modelling biological systems e.g. muscle and bone modelling, real-time hand tracking

See also 
 Calculus of variations
 Computer graphics
 3D computer graphics
 Graphics processing unit (GPU)
 Computer-aided design (CAD)
 Digital image
 Digital image processing
 Discrete differential geometry
 Glossary of differential geometry and topology
 Industrial CT scanning
 List of interactive geometry software
 MeshLab
 Signal processing
 Digital signal processing
 Digital signal processor (DSP)
 Topology

References

External links 

 Symposium on Geometry Processing
 Multi-Res Modeling Group, Caltech 
 Mathematical Geometry Processing Group, Free University of Berlin
 Computer Graphics Group, RWTH Aachen University
 Polygon Mesh Processing Book
 Polygon Mesh Processing Library
 Discrete Differential Geometry: An Applied Introduction, course notes by Keenan Crane et al.
 Video tutorials from SGP 2017 grad school
 libigl geometry processing library
 CGAL The Computational Geometry Algorithms Library (see section on Polygon Mesh Processing)

 
3D imaging
3D computer graphics
Geometry
Computational geometry
Differential geometry