Assignment 3 [Coding]: The Laplacian (Due 4/2)

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=\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.

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 DDG19A3.

9 thoughts on “Assignment 3 [Coding]: The Laplacian (Due 4/2)”

1. karen says:

Can we post the slides for Laplacian on the website? Thanks!

1. Mark says:

Keenan should post the slides soon. In the meantime, you can find a copy on his website here.

2. acpatel says:

For anyone else getting a “Binding Error” when attempting to reuse the same cotan-Laplace matrix between integrations for “modified-mean-curvature-flow.js”, the EmscriptenMemoryManager module is deleting the matrix thinking it will not be used again.

To fix this, you need to remove the object from the list of objects the memory manager handles. Add the following line to your constructor (or similar):

memoryManager.objectList.splice(memoryManager.objectList.indexOf(obj), 1);

3. riceroll says:

What is the rowBar in the solve() function of ScalarPoissonProblem?

1. Mark says:

rhoBar should be the (area-weighted) average of rho. Remember that we can only solve a Poisson equation if the right hand side has mean 0, so before we solve the system we subtract off the mean to ensure that the system has a solution.

1. Adilet Segizekov says:

Do we also have to subtract the average for mean curvature flow? Or does the normalize() call take care of that?

1. Mark says:

You don’t have to subtract off the average for the mean curvature flow