Assignment 3: The Laplacian
These exercises will lead you through two different derivations for the cotan-Laplace operator. As we’ll discuss in class, this operator is basically the “Swiss army knife” of discrete differential geometry and digital geometry processing, opening the door to a huge number of interesting algorithms and applications. Note that this time the exercises all come from the course notes—you will need to read the accompanying notes in order to familiarize yourself with the necessary material (though actually we’ve covered much of this stuff in class already!)
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
- core/geometry.js:
- laplaceMatrix
- massMatrix
- projects/poisson-problem/scalar-poisson-problem.js:
- constructor
- solve
- projects/geometric-flow/mean-curvature-flow.js:
- buildFlowOperator
- integrate
- projects/geometric-flow/modified-mean-curvature-flow.js:
- constructor
- buildFlowOperator
- 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=\frac12 \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 \to \mathbb R^3\) as a single DenseMatrix of size \(|V| \times 3\), and solve with the same (scalar) cotan-Laplace matrix used for the previous part. When constructing the flow operator, you should follow section 6.6 of the notes. But be careful - when we discretize equations of the form \(\Delta f = \rho\), we create systems of the form \(A f = M \rho\). So you'll need to add in the mass matrix somewhere. Also, recall that our discrete Laplace matrix is the negative of the actual Laplacian.
- 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.