Assignment 5 (Coding): Geodesic Distance

For the coding portion of this assignment, you will implement the heat method, which is an algorithm for computing geodesic distance on curved surfaces. All of the details you need for implementation are described in Section 3 of the paper, up through and including Section 3.2. Note that you need only be concerned with the case of triangle meshes (not polygon meshes or point clouds); pay close attention to the paragraph labeled “Choice of Timestep.”

Please implement the following routines in:

  1. projects/geodesic-distances/heat-method.js:
    1. constructor
    2. computeVectorField
    3. computeDivergence
    4. compute

Notes

  • Refer to sections 3.2 of the paper for discretizations of Algorithm 1 (page 3).
  • Your solution should implement zero neumann boundary conditions but feel free to tryout other Dirichlet and Neumann boundary conditions on your own.

Submission Instructions

Please rename your heat-method.js file to heat-method.txt and put it in a single zip file called solution.zip. This file and your solution to the written exercises should be submitted together in a single email to Geometry.Collective@gmail.com with the subject line DDG17A5.

Assignment 4 (Coding): Conformal Parameterization

For the coding portion of your assignment on conformal parameterization, you will implement the Spectral Conformal Parameterization (SCP) algorithm as described in the course notes.

Please implement the following routines in

  1. core/geometry.js:
    1. complexLaplaceMatrix
  2. projects/parameterization/spectral-conformal-parameterization.js:
    1. buildConformalEnergy
    2. flatten
  3. utils/solvers.js:
    1. solveInversePowerMethod
    2. residual

Notes

  • The complex version of the cotan-Laplace matrix can be built in exactly the same manner as its real counterpart. The only difference now is that the cotan values of our matrix will be complex numbers with a zero imaginary component.
  • The buildConformalEnergy function builds a $|V| \times |V|$ complex matrix corresponding to the conformal energy $E_C(z) = E_D(z) – A(z)$, where $E_D$ is the Dirichlet energy (given by our complex cotan-Laplace matrix) and $A$ is the total signed area of the region $z(M)$ in the complex plane (Please refer to Section 7.4 of the notes for more details). You may find it easiest to iterate over the halfedges of the mesh boundaries to construct the area matrix.
  • The flatten function returns a dictionary mapping each vertex to a vector (linear-algebra/vector.js) of planar coordinates by finding the eigenvector corresponding to the smallest eigenvalue of the conformal energy matrix. You can compute this eigenvector by using solveInversePowerMethod (described below).
  • Your solveInversePowerMethod function should implement Algorithm 1 in Section 7.5 of the course notes with one modification – after computing $Ay_i = y_{i-1}$, center $y_i$ around the origin by subtracting its mean. Important: Terminate your iterations when your residual is smaller that 10^-10.
  • The parameterization project directory also contains a basic implementation of the Boundary First Flattening (BFF) algorithm. Feel free to play around with it in the viewer and compare the results to your SCP implementation.

Submission Instructions

Please rename your geometry.js, spectral-conformal-parameterization.js and solvers.js files to geometry.txt, spectral-conformal-parameterization.txt and solvers.txt(respectively) and put them in a single zip file called solution.zip. These files and your solution to the written exercises should be submitted together in a single email to Geometry.Collective@gmail.com with the subject line DDG17A4.

Assignment 3 (Coding): The Laplacian and Curvature Flow

For the coding portion of this assignment, you will build the so-called “cotan-Laplace” matrix and start to see how it can be used for a broad range of surface processing tasks, including the Poisson equation and two kinds of curvature flow.

Getting Started

Please implement the following routines in

  1. core/geometry.js:
    • laplaceMatrix
    • massMatrix
  2. projects/poisson-problem/scalar-poisson-problem.js:
    • constructor
    • solve
  3. projects/geometric-flow/mean-curvature-flow.js:
    • buildFlowOperator
    • integrate
  4. projects/geometric-flow/modified-mean-curvature-flow.js:
    • constructor
    • buildFlowOperator

Notes 

  • Sections 6.4-6 of the course notes describe how to build the cotan-Laplace matrix and mass matrices, and outline how they can be used to solve equations on a mesh. In these applications you will be required to setup and solve a linear system of equations $Ax = b$ where $A$ is the Laplace matrix, or some slight modification thereof. Highly efficient numerical methods such as Cholesky Factorization can be used to solve such systems, but require $A$ to be symmetric positive definite. Notice that the cotan-Laplace matrix described in the notes is negative semi-definite. To make it compatible for use with numerical methods like the Cholesky Factorization, your implementation of laplaceMatrix should instead produce a positive definite matrix, i.e., it should represent the expression\[ (\Delta u)_i = \tfrac{1}{2}\sum_{ij} (\cot\alpha_{ij} + \cot\beta_{ij})(u_i – u_j). \]

    (Note that $u_i-u_j$ is reversed relative to the course notes.) To make this matrix strictly positive definite (rather than semidefinite), you should also add a small offset such as $10^{-8}$ to the diagonal of the matrix (which can be expressed in code as a floating point value 1e-8). This technique is known as Tikhonov regularization.

  • The mass matrix is a diagonal matrix containing the barycentric dual area of each vertex.
  • In the scalar Poisson problem, your goal is to discretize and solve the equation $\Delta \phi = \rho$ where $\rho$ is a scalar density on vertices and $\Delta$ is the Laplace operator. Be careful about appropriately incorporating dual areas into the discretization of this equation (i.e., think about where and how the mass matrix should appear); also remember that the right-hand side cannot have a constant component (since then there is no solution).
  • In your implementation of the implicit mean curvature flow algorithm, you can encode the surface $f : M \rightarrow \mathbb{R}^3$ as a single DenseMatrix of size $|V| x 3$, and solve with the same (scalar) cotan-Laplace matrix used for the previous part.
  • The modified mean curvature flow is nearly identical to standard mean curvature flow. The one and only difference is that you should not update the cotan-Laplace matrix each time step, i.e., you should always be using the cotans from the original input mesh. The mass matrix, however, must change on each iteration.

Submission Instructions

Please rename your geometry.js, scalar-poisson-problem.js, mean-curvature-flow.js and modified-mean-curvature-flow.js files to geometry.txt, scalar-poisson-problem.txt, mean-curvature-flow.txt and modified-mean-curvature-flow.txt (respectively) and put them in a single zip file called solution.zip. These files and your solution to the written exercises should be submitted together in a single email to Geometry.Collective@gmail.com with the subject line DDG17A3.

Assignment 2 (Coding): Investigating Curvature

For the coding portion of this assignment, you will implement various expressions for discrete curvatures and surfaces normals that you will derive in the written assignment. (However, the final expressions are given below in case you want to do the coding first.) Once implemented, you will be able to visualize these geometric quantities on a mesh. For simplicity, you may assume that the mesh has no boundary.

Getting Started

Please implement the following routines in core/geometry.js:

  1. angle
  2. dihedralAngle
  3. vertexNormalAngleWeighted
  4. vertexNormalSphereInscribed
  5. vertexNormalAreaWeighted
  6. vertexNormalGaussianCurvature
  7. vertexNormalMeanCurvature
  8. angleDefect
  9. totalAngleDefect
  10. scalarMeanCurvature
  11. circumcentricDualArea
  12. principalCurvatures

Notes 

1. The dihedral angle between the normals $N_{ijk}$ and $N_{ijl}$ of two adjacent faces $ijk$ and $jil$ (respectively) is given by

$\theta_{ij} := \mathrm{atan2}( \frac{e_{ij}}{|e_{ij}|} \cdot (N_{ijk} \times N_{jil}), N_{ijk} \cdot N_{jil} )$

where $e_{ij}$ is the vector from vertex $i$ to vertex $j$.

2. The formulas for the angle weighted normal, sphere inscribed normal, area weighted normal, discrete Gaussian curvature normal and discrete mean curvature normal at vertex $i$ are

$N_i^{\phi} := \sum_{ijk \in F} \phi_i^{jk} N_{ijk}$

$N_i^S := \sum_{ijk \in F} \frac{e_{ij} \times e_{ik}}{|e_{ij}|^2 |e_{ik}|^2}$

$N_i^A := \sum_{ijk \in F} A_{ijk} N_{ijk}$

$KN_i = \frac{1}{2}\sum_{ij \in E} \frac{\theta_{ij}}{|e_{ij}|}e_{ij}$

$HN_i = \frac{1}{2}\sum_{ij \in E} (cot(\alpha_k^{ij}) + cot(\beta_l^{ij}))e_{ij}$

where $\phi_i^{jk}$ is the interior angle between edges $e_{ij}$  and $e_{ik}$, and $A_{ijk}$ is the area of face $ijk$. Note that sums are taken only over elements (edges or faces) containing vertex \(i\). Normalize the final value of all your normal vectors before returning them.

3. The circumcentric dual area at vertex $i$ is given by

$A_i := \frac{1}{8}\sum_{ijk \in F} |e_{ik}|^2 cot(\alpha_j^{ki}) + |e_{ij}|^2 cot(\beta_k^{ij})$

4. The discrete scalar Gaussian curvature (also known as angle defect) and discrete scalar mean curvature at vertex $i$ are given by

$K_i := 2\pi – \sum_{ijk \in F} \phi_i^{jk}$

$H_i := \frac{1}{2}\sum_{ij \in E} \theta_{ij} |e_{ij}|$

Note that these quantities are discrete 2-forms, i.e., they represent the total Gaussian and mean curvature integrated over a neighborhood of a vertex. They can be converted to pointwise quantities (i.e., discrete 0-forms at vertices) by dividing them by the  circumcentric dual area of the vertex (i.e., by applying the discrete Hodge star).

5. You are required to derive expressions for the principal curvatures $\kappa_1$ and $\kappa_2$ in exercise 4 of the written assignment. Your implementation of principalCurvatures should return the (pointwise) minimum and maximum principal curvature values at a vertex (in that order).

Submission Instructions

Please rename your geometry.js file to geometry.txt and put it in a single zip file called solution.zip. This file and your solution to the written exercises should be submitted together in a single email to Geometry.Collective@gmail.com with the subject line DDG17A2.