Assignment 3 (Written): 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!)

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.

Implementing Curvature Flow

For anyone interested in learning more about the 1D curvature flows we saw today in class, there’s an assignment (and some notes) from a previous year’s class here:

Curvature Flow

In fact, it wouldn’t be hard to implement in the same code framework we’re using for the class, since you can think of a plane curve as a “mesh” consisting of a single flat polygon with many edges.

The paper I mentioned on discrete curve shortening with no crossings is:

Hass and Scott, “Shortening Curves on Surfaces”, Topology 33, (1994) 25-43.

It would be fun to see an implementation of something like this on a surface (I’ve never done it myself!).

Taking Gradients: Partial Derivatives vs. Geometric Reasoning

In your homework, you are asked to derive an expression for the gradient of the area of a triangle with respect to one of its vertices. In particular, if the triangle has vertices \(a,b,c \in \mathbb{R}^3\), then the gradient of its area \(A\) with respect to the vertex \(a\) can be expressed as
\[
\nabla_a A = \tfrac{1}{2} N \times (b-c).
\]
This formula can be obtained via a simple geometric argument, has a clear geometric meaning, and generally leads to a an efficient and error-free implementation.

In contrast, here’s the expression produced by taking partial derivatives via Mathematica (even after calling FullSimplify[]):

Longer expressions like these will of course produce the same values. But without further simplification (by hand) it will be less efficient, and could potentially exhibit poorer numerical behavior due to the use of a longer sequence of floating-point operations. Moreover, they are far less easy to understand/interpret, especially if this calculation is just one small piece of a much larger equation (as it often is).

In general, taking gradients the “geometric way” often provides greater simplicity and deeper insight than just grinding everything out in components. Your current assignment will give you some opportunity to see how this all works.

Update: As mentioned by Peter in the comments, here’s the expression for the gradient of angle via partial derivatives (as computed by Mathematica). Hopefully by the time you’re done with your homework, you’ll realize there’s a better way!

Reading Assignment: Introduction to Curves & Surfaces (Due 10/24)

For your next reading assignment, you will read a few pages about curves and surfaces from the course notes: Chapter 2, pages 7–23. This material should be enough to get you started on the written/coding exercises NOW, rather than waiting until we are done with the full set of lectures. We will cover these topics in greater depth during lecture (especially the topic of curvature).

Assignment: Read the pages above, and write 2–3 sentences summarizing what you read, plus at least one question about something you didn’t understand, or some thought/idea that occurred to you while reading the article.

Handin instructions can be found in the “Readings” section of the Assignments page.  Note that you must send your summary in no later than 10am Eastern on the date of the next lecture (October 24, 2017).

Enjoy!

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.

Linear Algebra and Vector Calculus Review

The prerequisites for 15-458/858B include courses or other past experience in linear algebra and vector calculus. However, we realize that for many of you it may have been a while since you studied this material. The worksheets below provide optional practice for those who wish to brush up on their skills. To emphasize again: this material is purely for your own review; it is not a required assignment, nor will it be graded. You may also wish to review this material from time to time during the semester (e.g., when we study exterior calculus).

[Linear Algebra Review]
[Vector Calculus Review]

Please email us if you’d like to see the solutions! (We keep these solutions private so they can be re-used for other classes in future years.)

Welcome to 15-458 / 15-858B! (Fall 2017)

Welcome to the website for 15-458/858B.  Here you’ll find course notes, lecture slides, and homework (see links on the right).

If you are a student in the class, register now by clicking here!

We strongly prefer that you register using your CMU email, but in any case you must not register with an address at a free email service like gmail.com, yahoo.com, etc., as email from these domains will be filtered out by the web host.

A few things to note:

  • You will be subscribed to receive email notification about new posts, comments, etc.
  • You can ask questions by leaving a comment on a post.  If you’re apprehensive about asking questions in public, feel free to register under a pseudonym.
  • Otherwise, please associate a picture to your profile by registering your email address at Gravatar.com—doing so will help us better recognize you in class!
  • You can include mathematical notation in your questions using standard $\LaTeX$ syntax.  For instance, when enclosed in a pair of dollar signs, an expression like dollar\int_M K dA = 2\pi\chidollar gets typeset as $\int_M K dA = 2\pi\chi$.
If you encounter any problems while trying to use the website, please contact the TAs (listed under the course description).