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.

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

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!)


 

Assignment 2 (Written): Investigating Curvature (Due 3/19)

The written portion of Assignment 2 can be found below. It takes a look at the curvature of smooth and discrete surfaces, which we have been talking about in lecture. Note that you are required to complete only two problems from each section!

Warning: We renumbered the Exercises in the course notes to make more sense, so you make sure you refer to the updated notes when doing these exercises.

Assignment 2 (Coding): Investigating Curvature (Due 3/19)


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 $ijl$ (respectively) is given by
$$ \theta_{ij} := \text{atan2}\left(\frac{e_{ij}}{\|e_{ij}\|} \cdot \left(N_{ijk} \times N_{jil}\right), N_{ijk} \cdot N_{jil}\right)$$

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
\[\begin{aligned}
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 12 \sum_{ij \in E} \frac{\theta_{ij}}{\|e_{ij}\|}e_{ij}\\
HN_i &= \frac 12 \sum_{ij \in E}\left(\cot\left(\alpha_k^{ij}\right) + \cot\left(\beta_l^{ij}\right)\right)e_{ij}
\end{aligned}
\]

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 18 \sum_{ijk \in F} \|e_{ik}\|^2\cot\left(\alpha_j^{ki}\right) + \|e_{ij}\|^2\cot\left(\beta_k^{ij}\right)\]

4. The discrete scalar Gaussian curvature (also known as angle defect) and discrete scalar mean curvature at vertex $i$ are given by
\[\begin{aligned}
K_i &:= 2\pi – \sum_{ijk \in F} \phi_i^{jk}\\
H_i &:= \frac 12 \sum_{ij \in E} \theta_{ij}\|e_{ij}\|
\end{aligned}
\]

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

Assorted things about homework

  1. Here’s a piece of advice for assignment 1 which I forgot to put in the original post: You can compute the ratio of dual edge lengths to primal edge lengths using the cotan formula, which can be found on Slide 28 of the Discrete Exterior Calculus lecture, or in exercise 36 of the notes (you don’t have to do the exercise for this homework).
  2. I just emailed out grades for assignment 0. If you have questions or concerns about your graded assignment, or if you did not receive a graded assignment, please feel free to email me or to talk to me during office hours.
  3. Very few people have been attending my office hours on Fridays, so I am moving my office hours to be 2:30pm-4pm on Monday afternoons. They will still be held outside of Smith 232.
  4. If you would like to see solutions for assignment 0, we will bring some printed copies to class on Tuesday. I can also print you solutions if you stop by during office hours.

Assignment 1 (Coding): Exterior Calculus (Due 2/26)

For the coding portion of your first assignment, you will implement the discrete exterior calculus (DEC) operators $\star_0, \star_1, \star_2, d_0$ and $d_1$. Once implemented, you will be able to apply these operators to a scalar function (as depicted above) by pressing the “$\star$” and “$d$” button in the viewer. The diagram shown above will be updated to indicate what kind of differential k-form is currently displayed. These basic operations will be the starting point for many of the algorithms we will implement throughout the rest of the class; the visualization (and implementation!) should help you build further intuition about what these operators mean and how they work

Getting Started

  • For this assignment, you need to implement the following routines:
    1. in core/geometry.js
      1. cotan
      2. barycentricDualArea
    2. in core/discrete-exterior-calculus.js
      1. buildHodgeStar0Form
      2. buildHodgeStar1Form
      3. buildHodgeStar2Form
      4. buildExteriorDerivative0Form
      5. buildExteriorDerivative1Form

In practice, a simple and efficient way to compute the cotangent of the angle $\theta$ between two vectors $u$ and $v$ is to use the cross product and the dot product rather than calling any trigonometric functions directly; we ask that you implement your solution this way. (Hint: how are the dot and cross product of two vectors related to the cosine and sine of the angle between them?)

In case we have not yet covered it in class, the barycentric dual area associated with a vertex $i$ is equal to one-third the area of all triangles $ijk$ touching $i$.

EDIT: You can compute the ratio of dual edge lengths to primal edge lengths using the cotan formula, which can be found on Slide 28 of the Discrete Exterior Calculus lecture, or in exercise 36 of the notes (you don’t have to do the exercise for this homework).

Submission Instructions

Please rename your geometry.js and discrete-exterior-calculus.js files to geometry.txt and discrete-exterior-calculus.txt (respectively) and submit them in a single zip file called solution.zip by email to Geometry.Collective@gmail.com.

Assignment 1 (Written): Exterior Calculus (Due 2/26)

The written portion of assignment 1 is now available (below), which covers some of the fundamental tools we’ll be using in our class. Initially this assignment may look a bit intimidating, but keep a few things in mind:

  • The homework is not as long as it might seem: all the text in the big gray blocks contains supplementary, formal definitions that you do not need to know in order to complete the assignments.
  • Moreover, note that you are required to complete only three problems from each section.

Finally, don’t be shy about asking us questions here in the comments, via email, or during office hours.  We want to help you succeed on this assignment, so that you can enjoy all the adventures yet to come…
A1Written

This assignment is due on Tuesday, February 26.

Office Hours + Homework Typo

I will hold office hours tomorrow (Friday Feb. 1) in the Smith Hall 2nd floor open space from 3pm to 4pm. Next week, since the homework is due on Thursday, I will hold office hours on Tuesday from 3pm to 4pm in the same place. After that, I will go back to having office hours on Fridays.

Sorry for the short notice. If these times don’t work for you, feel free to email me and we can arrange to meet another time.

 

Also, somebody pointed out a typo in the coding assignment during recitation – the vertex-edge and edge-face adjacency matrices should be sparse matrices, not dense like it says in the comments/documentation.