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

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

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

1. manugopa says:

When I run console.log(rho.sum()); in the test for poisson-problem, I get that the rho’s sum to zero. Additionally, when I checked random values in rho, the value I got was always 0. Is the entire rho vector supposed to be zero?

1. manugopa says:

Also, is the rho_bar referenced in the comments in the scalar-poisson-problem.js the mean of this rho vector?

1. manugopa says:

I found the information that I was looking for in the written assignment document.

1. Zhang Zetian says:

Hi I met the same problem as you did. I’m not sure what rho_bar is, and I found the sum of rho to be zero. Can you talk about where on the document did you find to be useful?

1. Alex says:

Pages 100-101 of the notes are helpful here.

2. ceviri says:

“You could verify that this matrix is correct, or you could go outside and play in the sunshine.Your choice.”
Gee thanks, COVID-19, now I have no choice and I’m STUCK HERE VERIFYING THIS STUPID MATRIX

1. Keenan says:

🙂

Please check with your local government, but in many locations you can still go and verify matrices outdoors (and it is strongly encouraged!)

3. ceviri says:

For the mean curvature flow implementation, I seem to have semi-working code (the bunny gets visually smoothed) but the numbers appear to be off the test cases by ~1%, which is out of the tolerances. Does anyone else have a similar issue?

1. ceviri says:

I figured it out – I was normalizing the positions *before* doing the stuff, when I should’ve been normalizing the positions *after* doing the stuff.

1. ceviri says:

Also there’s a typo on the submission instructions – it says “…subject line DDG19A03” instead of DDG20A03

4. hawner says:

It seems that core/geometry.js has disappeared from my testing suite somehow. If I try to run any tests that use it (geometry, poisson-problem, discrete-exterior-calclus, etc) I get a blank page, in the upper right corner it says “passes: 0 failures: 0 duration: 0s”

I opened Firefox debugger to look at what’s getting loaded and core/geometry.js is just gone. Anyone else face this problem?