Geometry processing

Properties of a 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.

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. R 2 or 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.

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

▽ g = { n i , ∀ p i ∈ S 0 , otherwise

The task of reconstruction then becomes a variational problem. To find the indicator function of the surface, we must find a function χ such that ∥ ▽ χ − V ∥ is minimized, where V is the vector field defined by the samples.

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

∫ x ∈ X | | R x + t − P Y ( x ) | | d x

An iterative solution, known as Iterative Closest Point, is usually employed. n random sample points from X are chosen and projected onto Y . Then the optimal transformation is calculated based on the difference between each 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 f ¯ and the smoothness of the resulting signal, which approximated by the magnitude of the gradient with a weight λ :

L ( f ) = ∫ Ω ∥ f − f ¯ ∥ 2 + λ ∥ ∇ f ∥ 2 d x .

Taking a variation δ f on L emits the necessary condition

0 = δ L ( f ) = ∫ Ω δ f ( I + λ ∇ 2 ) f − δ f f ¯ d x .

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

∑ i M i δ f i f ¯ i = ∑ i M i δ f i ∑ j ( I + λ ∇ 2 ) f j = ∑ i δ f i ∑ j ( M + λ M ∇ 2 ) f j ,

where our choice of ∇ 2 is chosen to be M − 1 L for the cotangent Laplacian L and the 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 λ :

f ¯ = ( M + λ L ) f . When working with triangle meshes one way to determine the values of the Laplacian matrix L is through analyzing the geometry of connected triangles on the mesh.

L i j = { 1 2 ( c o t ( α i j ) + c o t ( β i j ) ) edge ij exists − ∑ i ≠ j L i j i = j 0 otherwise

Where α i j and β i j are the angles opposite the edge ( i , j )

Parameterization

Paremeterization refers to strategies employed in mapping a 3D mesh onto a 2D surface.