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 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. 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 \chi= 2c - 2h - b , where c is the number of connected components, h is number of holes (as in donut holes, see torus), and b 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. \chi = |V| - |E| + |F| . \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 \chi such that \lVert \triangledown \chi - \textbf{V} \rVert is minimized, where \textbf{V} is the vector field defined by the samples. As a variational problem, one can view the minimizer \chi as a solution of Poisson's equation. After obtaining a good approximation for \chi and a value \sigma for which the points (x,y,z) with \chi(x,y,z)= \sigma lie on the surface to be reconstructed, the marching cubes algorithm can be used to construct a triangle mesh from the function \chi , which can then be applied in subsequent computer graphics applications. \mathcal{L}(f) = \int_{\Omega}\|f - \bar f\|^2 + \lambda \|\nabla f\|^2 dx . Taking a variation \delta f on \mathcal{L} emits the necessary condition 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 \begin{align} \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{align} where our choice of \nabla^2 is chosen to be M^{-1}\mathbf{L} for the cotangent Laplacian \mathbf{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 \lambda : \bar f =(M + \lambda \mathbf{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_{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 \alpha_{ij} and \beta_{ij} are the angles opposite the edge (i,j) 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: M_{ij} = \begin{cases} \frac{1}{3}\sum\limits_{t=1}^m\begin{cases} Area(t) & \text{if triangle t contains vertex i} \\ 0 & \text{otherwise} \end{cases} & \text{if i=j} \\ 0 & \text{otherwise} \end{cases} There are a few other things to consider. We would like to minimize the angle distortion to preserve orthogonality. That means we would like \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. \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: \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. A rest surface \hat{S} immersed in \R^3 can be described with a mapping \hat{x} : \Omega \rightarrow \R^3 , where \Omega is a 2D parametric domain. The same can be done with another mapping x for the transformed surface 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 d = x - \hat{x} 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: \min_{\textbf{d}} \int_{\Omega} || \Delta \textbf{d} ||^2 dA . While this method is translation invariant, it is unable to account for rotations. The As-Rigid-As-Possible deformation scheme applies a rigid transformation x_i = R\hat{x_i} + t to each handle i, where R \in SO(3) \subset \R^3 is a rotation matrix and t \in \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 \textbf{R} : \Omega \rightarrow SO(3) which outputs the best rotation for every point on the surface. The resulting energy, then, must optimize over both \textbf{x} and \textbf{R} : \min_{\textbf{x,R} \in SO(3)} \int_{\Omega} || \nabla \textbf{x} - \textbf{R} \nabla \hat{\textbf{x}} ||^2 dA Note that the translation vector is not present in the final objective function because translations have constant gradient. In the simplest case, the shape is closed. In this case, to determine if a point q is inside or outside the surface, we can cast a ray r in any direction from a query point, and count the number of times count_r it passes through the surface. If q was outside S then the ray must either not pass through S (in which case count_r = 0 ) or, each time it enters S it must pass through twice, because S is bounded, so any ray entering it must exit. So if q is outside, count_r is even. Likewise if q is inside, the same logic applies to the previous case, but the ray must intersect S one extra time for the first time it leaves S . So: isInside_r(q) = \left\{ \begin{array}{ll} 1 & count_r \ is \ odd \\ 0 & count_r \ is \ even\\ \end{array} \right. Now, oftentimes we cannot guarantee that the 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 q as being inside if and only if most of the rays intersected S an odd number of times. To quantify this, let us say we cast k rays, r_1,r_2,\dots,r_k . We associate a number rayTest(q) = \frac{1}{k}\sum_{i=1}^{k} isInside_{r_i}(q) which is the average value of isInside_r from each ray. Therefore: isInside(q) = \left\{ \begin{array}{ll} 1 & rayTest(q) \geq 0.5 \\ 0 & rayTest(q) 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 q of each triangle in the mesh to determine if q is inside or outside. The value of the Generalized Winding Number at q , wn(q) is proportional to the sum of the solid angle contribution from each triangle in the mesh: wn(q) = \frac{1}{4\pi}\sum_{t \in F} solidAngle(t) For a closed mesh, wn(q) is equivalent to the characteristic function for the volume represented by S . Therefore, we say: isInside(q) = \left\{ \begin{array}{ll} 1 & wn(q) \geq 0.5 \\ 0 & wn(q) Because wn(q) 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. ==References== REFERENCES ---------- BIBLIOGRAPHY (BibTeX) -------------------- @article{ref0, title = {Geometry processing}, url = {https://encyclopegia.org/a/geometry-processing} } BIBLIOGRAPHY (RIS) ------------------- TY - JOUR TI - Geometry processing UR - https://encyclopegia.org/a/geometry-processing ER - CITE THIS ARTICLE ---------------- Cite this article: Geometry processing Derived from: https://en.wikipedia.org/w/index.php?oldid=1365620838 Licence: CC BY-SA 4.0 Snapshot: enwiki-001365620838 Permalink: /a/geometry-processing