Geometry processing is an area of research that uses concepts fromapplied mathematics,computer science andengineering to design efficientalgorithms 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 tosignal processing andimage processing. For example, whereimage smoothing might convolve an intensity signal with a blur kernel formed using theLaplace operator,geometric smoothing might be achieved by convolving asurface geometry with a blur kernel formed using theLaplace-Beltrami operator.

Applications of geometry processing algorithms already cover a wide range of areas frommultimedia,entertainment and classicalcomputer-aided design, to biomedical computing,reverse engineering, andscientific computing.^[1]

Geometry processing is a common research topic atSIGGRAPH, the premiercomputer graphics academic conference, and the main topic of the annualSymposium on Geometry Processing.

Geometry processing involves working with ashape, 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: amodel, amathematical representation, or ascan. 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 itsEuler characteristic. Editing may involve denoising, deforming, or performingrigid 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 befabricated in the real world, through a method such as 3D printing or laser cutting.

Like any other shape, the shapes used in geometry processing have properties pertaining to theirgeometry andtopology. The geometry of a shape concerns the position of the shape'spoints in space,tangents,normals, andcurvature. It also includes the dimension in which the shape lives (ex.${\displaystyle R^2}$ or${\displaystyle R^3}$). Thetopology 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 ofholes andboundaries, as well as theorientability of the shape. One example of a non-orientable shape is theMobius strip.

In computers, everything must be discretized. Shapes in geometry processing are usually represented astriangle meshes, which can be seen as agraph. Each node in the graph is a vertex (usually in${\displaystyle R^3}$), 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 ofpolygon meshes can also be used to represent a shape. More advanced representations likeprogressive 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.^[2]

One particularly important property of a 3D shape is itsEuler characteristic, which can alternatively be defined in terms of itsgenus. The formula for this in the continuous sense is${\displaystyle \chi =2c-2h-b}$, where${\displaystyle c}$ is the number of connected components,${\displaystyle h}$ is number of holes (as in donut holes, seetorus), and${\displaystyle b}$ is the number of connected components of the boundary of the surface. A concrete example of this is a mesh of apair 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.${\displaystyle \chi =|V|-|E|+|F|}$.

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^[3] strategy can be employed. This method states that theindicator 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 is0 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:

The task of reconstruction then becomes avariational problem. To find the indicator function of the surface, we must find a function${\displaystyle \chi }$ such that${\displaystyle \Vert ▽\chi -\mathbf{\text{V}}\Vert }$ is minimized, where${\displaystyle \mathbf{\text{V}}}$ is the vector field defined by the samples. As a variational problem, one can view the minimizer${\displaystyle \chi }$as a solution ofPoisson's equation.^[3] After obtaining a good approximation for${\displaystyle \chi }$ and a value${\displaystyle \sigma }$ for which the points${\displaystyle (x,y,z)}$ with${\displaystyle \chi (x,y,z)=\sigma }$ lie on the surface to be reconstructed, themarching cubes algorithm can be used to construct atriangle mesh from the function${\displaystyle \chi }$ , which can then be applied in subsequent computer graphics applications.

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 asregistration. In registration, we wish to find an optimalrigid transformation that will align surface${\displaystyle X}$ with surface${\displaystyle Y}$. More formally, if${\displaystyle P_Y(x)}$ is the projection of a pointx 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)|{|}^{2}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 asIterative 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}$. 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.^[4] Thereafter, 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.

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 asdata denoising, while noise reduction on the latter is known assurface 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 \overline{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 }_{\mathrm{\Omega }}\Vert f-\overline{f}{\Vert }^2+\lambda \Vert \mathrm{\nabla }f{\Vert }^{2}dx}$.

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

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

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

where our choice of${\displaystyle {\mathrm{\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 \overline{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.

Where${\displaystyle {\alpha }_{ij}}$ and${\displaystyle {\beta }_{ij}}$ are the angles opposite the edge${\displaystyle (i,j)}$^[5]Themass 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:

Occasionally, we need to flatten a 3D surface onto a flat plane. This process is known asparameterization. The goal is to find coordinatesu andv 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 istexture mapping.

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 theuv-coordinates. Borrowing an idea from graph theory, we apply theTutte Mapping and restrict the boundary vertices of the mesh onto aunit circle or otherconvex 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 thebarycentric 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.

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

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

There are a few other things to consider. We would like to minimize the angle distortion topreserve orthogonality. That means we would like${\displaystyle \mathrm{\nabla }u=\mathrm{\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 theu andv coordinate functions to 1.

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

${\displaystyle \underset{u,v}{\text{min}}{\int }_S\frac{1}{2}||\mathrm{\nabla }u|{|}^2+\frac{1}{2}||\mathrm{\nabla }v|{|}^2-\mathrm{\nabla }u\cdot \mathrm{\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.

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.^[8] In point-based deformation, a user can apply transformations to small set of points, called handles, on the shape. Skeleton-based deformation defines askeleton 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.

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${\displaystyle \hat{S}}$immersed in${\displaystyle {\mathbb{R}}^3}$ can be described with a mapping${\displaystyle \hat{x}:\mathrm{\Omega }\to {\mathbb{R}}^3}$, where${\displaystyle \mathrm{\Omega }}$ is a 2D parametric domain. The same can be done with another mapping${\displaystyle x}$ for the transformed surface${\displaystyle S}$. Ideally, the transformed shape adds as little distortion as possible to the original. One way to model this distortion is in terms of displacements${\displaystyle d=x-\hat{x}}$ with a Laplacian-based energy.^[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. Thus, the energy we would like to minimize can be written as:

${\displaystyle \underset{\mathbf{\text{d}}}{min}{\int }_{\mathrm{\Omega }}||\mathrm{\Delta }\mathbf{\text{d}}|{|}^{2}dA}$.

While this method is translation invariant, it is unable to account for rotations. The As-Rigid-As-Possible deformation scheme^[10] applies a rigid transformation${\displaystyle x_i=R\widehat{x_i}+t}$ to each handle i, where${\displaystyle R\in SO(3)\subset {\mathbb{R}}^3}$ is arotation matrix and${\displaystyle t\in {\mathbb{R}}^3}$ 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${\displaystyle \mathbf{\text{R}}:\mathrm{\Omega }\to SO(3)}$ which outputs the best rotation for every point on the surface. The resulting energy, then, must optimize over both${\displaystyle \mathbf{\text{x}}}$ and${\displaystyle \mathbf{\text{R}}}$:

${\displaystyle \underset{\mathbf{\text{x,R}}\in SO(3)}{min}{\int }_{\mathrm{\Omega }}||\mathrm{\nabla }\mathbf{\text{x}}-\mathbf{\text{R}}\mathrm{\nabla }\widehat{\mathbf{\text{x}}}|{|}^{2}dA}$

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

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${\displaystyle S}$ we pose this problem as determining a function${\displaystyle isInside(q)}$ which will return${\displaystyle 1}$ if the point${\displaystyle q}$ is inside${\displaystyle S}$, and${\displaystyle 0}$ otherwise.

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

Now, oftentimes we cannot guarantee that the${\displaystyle S}$ 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${\displaystyle q}$ as being insideif and only if most of the rays intersected${\displaystyle S}$ an odd number of times. To quantify this, let us say we cast${\displaystyle k}$ rays,${\displaystyle r_1,r_2,\dots ,r_k}$. We associate a number${\displaystyle rayTest(q)=\frac{1}{k}\sum _{i=1}^{k}isInsid{e}_{r_i}(q)}$ which is the average value of${\displaystyle isInsid{e}_r}$ 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.^[11] Inspired by the 2Dwinding number, this approach uses thesolid angle at${\displaystyle q}$ of each triangle in the mesh to determine if${\displaystyle q}$ is inside or outside. The value of the Generalized Winding Number at${\displaystyle q}$,${\displaystyle wn(q)}$ is proportional to the sum of the solid angle contribution from each triangle in the mesh:

${\displaystyle wn(q)=\frac{1}{4\pi }\sum _{t\in F}solidAngle(t)}$

For a closed mesh,${\displaystyle wn(q)}$ is equivalent to the characteristic function for the volume represented by${\displaystyle S}$. Therefore, we say:

Because${\displaystyle wn(q)}$ is aharmonic 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.

• Computer-aided design (CAD)
• 3DSurface 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 gamese.g.collision detection
• Geologic modelling
• Visualization (graphics)e.g.Information visualizations,mathematical visualizations
• Texture mapping
• Modelling biological systemse.g. muscle and bone modelling, real-time hand tracking

• Calculus of variations
• Computer graphics
  • 3D computer graphics
  • Graphics processing unit (GPU)
• CGAL, The Computational Geometry Algorithms Library
• 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
• MeshLib
• Signal processing
  • Digital signal processing
  • Digital signal processor (DSP)
• Topology

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

• Articles with short description
• Short description is different from Wikidata