Geometry Processing Project

Posted on 2024-09-22 Edited on 2024-11-15 In GameGraphics Views: Word count in article: 3.5k Reading time ≈ 3 mins.

Implicit Surface Reconstruction
Mesh Parameterization
Shape Deformation
Skinning and Skeletal Animation

Implicit Surface Reconstruction

Compute an implicit MLS function approximating a 3D point cloud with given normals.
Sample the implicit function on a 3D volumetric grid.
Apply the marching cubes algorithm to extract a triangle mesh from the zero level set.

Mesh Parameterization

Parameterize a mesh by minimizing four different distortion measures with fixed or free boundaries.
- Spring energy (uniform Laplacian)
- Dirichlet/harmonic energy (cotangent Laplacian)
- Least Squares Conformal Maps (LSCM)
- As-Rigid-As-Possible (ARAP)
Visualize the distortion by color coding.

Uniform and cotangent Laplacian

Spring energy is defined as \[ \frac{1}{2}k_{i,j}\Vert \mathbf{u}_{i}-\mathbf{u}_{j} \Vert^{2} \] Minimizing the spring enegy \[ \begin{align*} E(\mathbf{u}_{1}, \cdots, \mathbf{u}_{n})&=\sum\limits \frac{1}{2}k_{i,j}\Vert \mathbf{u}_{i}-\mathbf{u}_{j} \Vert^{2}\\ \frac{\partial{E(\mathbf{u}_{1},\cdots,\mathbf{u}_{n})}}{\partial \mathbf{u}_{i}}&=\sum\limits k_{i,j}(\mathbf{u}_{i}-\mathbf{u}_{j})=0 \\ \sum\limits_{j \in \mathcal{N}(i)\cap \mathcal{B}} k_{ij}\mathbf{u}_{i}+\sum\limits_{j \in \mathcal{N}(i) \backslash \mathcal{B}} k_{i,j}(\mathbf{u}_{i}-\mathbf{u}_{j})&= \sum\limits_{j \in \mathcal{N}(i)\cap \mathcal{B}} k_{i,j}\mathbf{u}_{j} \end{align*} \]

Two choices of spring constants
- Uniform \(k_{i,j}=1\)
- Cotan \(k_{i,j}=\cot{\phi_{i,j}}+\cot{\phi_{j,i}}\)

LSCM

The LSCM distortion measure can be defined as \[ D(J) = \| J + J^T - (\text{tr}\, J) I \|_F^2 \]

ARAP

The ARAP distortion is defined as \[ D(J) = \| J - R\|_F^2 \] where \(R\) is the cloest rotation matrix to \(J\). The ARAP procedure follows the steps below: - Local step: The Jacobians for each face of the current iterate are computed. Then for each Jacobian the closest rotation matrix is found. This can be done using the SVD of \(J\). - Global step: Then for each Jacobian the closest rotation matrix is found, they are all assumed to be fixed, and then minimize the ARAP distortion measure by solving a linear system.

Shape Deformation

Implement multiresolution mesh editing algorithm to interactively deform 3D models. Construct a two-level multi-resolution surface representation and use naive Laplacian editing to deform it.

Multiresolution mesh editing algorithm: 1. Remove high-frequency details by surface smoothing 2. Deform the smooth mesh 3. Transfer high-frequency details back to the deformed surface

Skinning and Skeletal Animation

Rotation Representation

Representions	Short Description	pros	cons
rotation matrix	3x3 Matrix to represent rotation in 3D	Simple to use directly.	Requires 9 elements to compute. Hard to interpolation. Direct interpolation leads to artifact.
euler angles	Use three angles (yaw, pitch, roll) to represent 3D representation	Only three parameters needed to represent rotations. Intuitive. Easy to transformed to rotation matrix	The gimbal lock problem. Can result in interpolation problems
axis angle	Rotation defined by an rotation axis and an angle	straightforward and intuitive, easily be converted to and from a matrix	Angle choices is not unique. Cannot perform interpolation directly
quaternions	Use a four-tuple of real number (x,y,z,w)	very efficient for interpolation. Without gimbal lock. Only 4 parameters required.	Less intuitive. more complex to transformed to rotation matrix. Double cover problem