Assignment 4

For your next assignment, due on Friday, March 4th, you will simply complete the exercises you previously skipped over that required use of exterior calculus. These exercises can all be found in the class notes, and include:

  • Chapter 5, Exercise 13 (Hint: read very carefully the end of Section 3.2)
  • Chapter 5, Exercise 16
  • Chapter 6, Exercise 20
  • Chapter 6, Exercise 26

You should also carefully read Section 6.3 (which leads up to Exercise 26), which provides an alternative perspective on the Laplacian to the finite element approach you derived in your last homework, and will be very useful to understand for upcoming assignments.  For the exercises in Chapter 5, it may also be helpful to review your reading of Chapter 2 (on the geometry of surfaces), re-thinking these concepts in terms of differential forms.  (For example, the Weingarten map \(dN\) and differential \(df\) of the immersion can both be viewed as vector-valued 1-forms.)  These exercises are a bit more challenging than the “warm up” exercises from your readings, so please post comments if you have any trouble.

Reading 9 — Exterior Calculus, Part Deux

A1

Continuing with the last reading, your next reading will again be from our course notes, Sections 3.4–3.6. (If it’s been a while since you’ve looked at vector calculus, now may also be a good time to brush up on things like div, grad, and curl.) We’ve again included some simple calculations below, to test your own understanding of these ideas—as usual, please post in the comments if you have any trouble! This reading will be due before class next Tuesday. Note that it is important to do these warm-up exercises, because your next homework will be all about exterior calculus!

  1. Consider the scalar function \(\psi: \mathbb{R}^2 \to \mathbb{R}; (x,y) \mapsto \tfrac{1}{2}x^2 – 3y\), and compute the quantities \(d\psi\), \(\star d\psi\), \(d\star d\psi\), and finally \(\star d \star d \psi\). Express the results in terms of the basis 1-forms \(dx,dy\).
  2. Consider the scalar function \(\phi: \mathbb{R}^2 \to \mathbb{R}; (x,y) \mapsto e^{-(x^2+y^2)}\). Calculate the exterior derivative \(d\phi\), expressing the result in terms of the basis 1-forms \(dx,dy\).
  3. Using the same function \(\phi\) as above, evaluate the directional derivative \(\phi(X)\), where \(X := -(\tfrac{1}{4xe^{-(x^2+y^2)}}\tfrac{\partial}{\partial x} + \tfrac{1}{4ye^{-(x^2+y^2)}}\tfrac{\partial}{\partial y})\). Note that unlike the previous reading, here you are working with a “1-form field“, i.e., you are effectively taking a different inner product at each point. Alternatively, you can imagine that you’re computing a different directional derivative at each point, where the direction is given by \(X\).
  4. Integrate the 1-form \(\omega := \sin\theta\ d\theta\) over the unit circle.

To give a couple concrete examples of what these calculations look like: if \(f(x,y) := y/x – y^2\) and \(Z := \tfrac{\partial}{\partial x} – \tfrac{\partial}{\partial y}\), then
\[
df = \frac{\partial f}{\partial x} dx + \frac{\partial f}{\partial y} dy = -\frac{y}{x^2} dx + (\frac{1}{x}-2y) dy
\]
and
\[
df(Z) = -\frac{y}{x^2} \underbrace{dx(Z)}_{=1} + (\frac{1}{x}-2y) \underbrace{dy(Z)}_{=-1} = -\frac{y}{x^2} – \frac{1}{x}-2y = \frac{2x^2 y – x – y}{x^2}.
\]

Submission: As usual, please send an email to kmcrane@cs.cmu.edu and nsharp@cs.cmu.edu no later than 10:00 AM on Tuesday, March 1st including the string DDGSpring2016 in your subject line.  Your email for readings should always include:

  1. a short (2-3 sentence) summary of what you read, and
  2. at least one question about something you found confusing / interesting / incomplete / not addressed.

Reading 8 — Exterior Calculus Part I

A1

Time to get busy with exterior calculus. Very roughly speaking, exterior calculus is a “souped up” version of vector calculus that will let us do lots of interesting calculations on surfaces, both mathematically and computationally. This material is critical to the assignments we’ll do during the rest of the course; it is well-worth your time to understand it well! Your reading assignment for Thursday (not Tuesday) is to read the first half of Chapter 3 from our course notes, namely Sections 3.1–3.3 (pp. 23-35). We have also given you four mini-exercises below, which you should submit answers to either by email, or in-class if you prefer to do them on paper. These shouldn’t take more than a few minutes, and are mostly to confirm your own understanding; if you’re having trouble, please don’t hesitate to ask questions either here on the website or via email.

  1. Write the column vector \(u = [\ 1\ 2\ 3\ ]^T\) and the row vector \(\alpha = [\ 4\ 5\ 6\ ]\) using the notation described for vectors and 1-forms (respectively) in Section 3.1.
  2. Using the same values of \(u\) and \(\alpha\), what is \(\alpha(u)\)?
  3. Bonus question: suppose that for vectors \(u,v \in \mathbb{R}^n\), we define the metric as \(g(u,v) := 2\langle u, v \rangle\) where \(\langle \cdot, \cdot \rangle\) is the usual Euclidean inner product, i.e., our metric \(g\) is simply a conformal rescaling of the Euclidean metric by a factor 2. Based on the comment immediately preceding Section 3.1.1., what do you think the 1-form \(u^\flat\) and the vector \(\alpha^\sharp\) should be (using the same values for \(u\) and \(\alpha\) as in the previous question)? You can work out the answer using matrices if you like, but try writing the final answer in terms of the basis vectors and 1-forms (as in the previous question).
  4. Letting \(\alpha := 2 dx + 3 dy + 4 dz\) and \(\beta := 5 dx + 6 dy + 7 dz\), calculate \(\alpha \wedge \beta\). (This time, no matrices allowed!)
  5. Letting \(\alpha := 8 dx \wedge 9 dy\), write out \(d\alpha \wedge d\alpha\), showing explicitly why it’s equal to zero.

To give a couple concrete examples of what these calculations look like: if \(u := \tfrac{\partial}{\partial x} – 2 \tfrac{\partial}{\partial y}\), \(\alpha = dx – dy\), and \(\beta = 2 dx + dy\), then
\[
\alpha(u) = dx(u) – dy(u) = dx(\tfrac{\partial}{\partial x} – 2 \tfrac{\partial}{\partial y}) – dy(\tfrac{\partial}{\partial x} – 2 \tfrac{\partial}{\partial y}) = 1 – (-2) = 3,
\]
and
\[
\alpha \wedge \beta = (dx-dy) \wedge (2dx + dy) = 2 dx \wedge dx + dx \wedge dy – 2 dy \wedge dx – dy \wedge dy = 0 + dx \wedge dy + 2 dx \wedge dy – 0 = 3 dx \wedge dy.
\]

Submission: As usual, please send an email to kmcrane@cs.cmu.edu and nsharp@cs.cmu.edu no later than 10:00 AM on Thursday, February 24th including the string DDGSpring2016 in your subject line.  Your email for readings should always include:

  1. a short (2-3 sentence) summary of what you read, and
  2. at least one question about something you found confusing / interesting / incomplete / not addressed.

Reading 7 – Optimal Transport

An emerging tool for processing visual or geometric data (among many other things) is optimal transport / earth mover’s distance / Wasserstein distance.  For this reading, try to give an (extremely!) high-level description of the problem of optimal transport, and identify at least one interesting/cool/useful place where part of this theory has been applied.  In addition to the links above, some good starting points for applications in image and geometry processing include

As usual, you can probably Google for “optimal transport” plus any application and find something interesting.  The goal here is not to get an in-depth understanding of the subject, but rather just get a feel for the kind of problems people are solving with optimal transport.

More technical, in-depth introductions can be found in Ambrosio & Gigli, “A User’s Guide to Optimal Transport” and Villani, “Optimal Transport, Old and New.”

Submission: As usual, please send an email to kmcrane@cs.cmu.edu and nsharp@cs.cmu.edu no later than 10:00 AM on Thursday, February 18th including the string DDGSpring2016 in your subject line.  Your email for readings should always include:

  1. a short (2-3 sentence) summary of what you read, and
  2. at least one question about something you found confusing / interesting / incomplete / not addressed.

Reading 6 – Generalized Winding Numbers

winding

For the next reading assignment, you should take a (brief!) look at the paper

Jacobson et al, “Robust Inside-Outside Segmentation using Generalized Winding Numbers.”

This paper provides a nice example of how simple geometric observations can lead to very practical algorithms for mesh processing.  The goal of this reading is not to understand every detail of the algorithm, but rather to get a sense of

  1. What is the practical problem the authors are trying to solve?
  2. What is a winding number?
  3. How did the authors generalize this notion of winding number, and how does it help them solve the practical problem?

As always, Wikipedia is your friend.

Submission: As usual, please send an email to kmcrane@cs.cmu.edu and nsharp@cs.cmu.edu no later than 10:00 AM on Thursday, February 11th including the string DDGSpring2016 in your subject line.  Your email for readings should always include:

  1. a short (2-3 sentence) summary of what you read, and
  2. at least one question about something you found confusing / interesting / incomplete / not addressed.

Assignment 3

Assignment 3 is now available! You can view the document here. This assignment will be due at 11:00 pm on Feb 23rd. The submission guidelines are identical to the previous assignment. Electronic submissions are preferred (cc’ing both kmcrane@cs.cmu.edu and nsharp@cs.cmu.edu), but if you wish to submit a physical document, do so in class or at 215 Smith Hall. Smith Hall locks to the public at 5:00 pm, so plan accordingly.

The document linked above has several questions inline, numbered as Exercises 18-26. You DO NOT need to complete exercises 20 and 26, and you might not understand Section 6.3 — these all depend on exterior calculus, which we will be covering soon.

Once again, there is a coding component at the conclusion of the document, where you will be asked to implement some of the ideas described in the preceding text. A corresponding code skeleton is now present in the course repository, which you should download and modify. Note that the core library has also been updated, so you will need to re-download (or git pull, if you’re using git) the entire repository. The skeleton in Assignment3.py contains empty methods in which you will implement your solution, all of your modifications must be between the lines which say BEGIN YOUR CODE and END YOUR CODE. Some of the function names referenced in the text might not perfectly align with the codebase; don’t worry about this, just fill out the skeleton code. To submit the coding portion, email us your modified copy of the file Assignment3.py along with your written submission.

Again, we will only be considering triangular meshes without boundary for this assignment. There is a collection of such meshes in the Assignment3/Boundaryless_Meshes/ directory on which to test your code. Also, the codebase wiki has some information on matrix computation in Python which you might find useful.

Be warned, this coding portion is a bit more involved than the previous assignment, I suggest you start early so you have time to ask questions as needed.

Reading 5 – The Laplacian

The Laplace-Beltrami operator plays a fundamental role in geometry and physics; it is also a key object in digital geometry processing, take the role (in some sense) of the fast Fourier transform from traditional signal processing. Your next reading assignment will be to gain a better understanding of the Laplacian, both from a formal as well as intuitive geometric viewpoint. (If you haven’t seen vector calculus in a while, this may also be a good moment to brush up on things like the divergence, gradient, and curl.)

Some potential starting points:

  • Laplace operator – the obligatory Wikipedia link
  • Laplace-Beltrami – a generalized version of the Laplacian used in geometry; a discrete version of this operator is what we will effectively use to develop a number of algorithms throughout the remainder of the term.
  • Laplace-Beltrami: The Swiss Army Knife of Geometry Processing – some slides that give a nice visual overview of the Laplacian, its relationship with geometry, its discretization, and its applications in digital geometry processing.
  • Chapter 6 – The Laplacian – from our course notes; you will see a version of this chapter again very soon, since it forms the basis for your next assignment.
  • A discrete Laplace-Beltrami operator for simplicial surfaces – for folks who want to dig a bit deeper, this paper goes into some of the deeper questions about how to define a Laplace operator on a discrete surface, while capturing important features of the smooth operator.
  • Discrete Laplace operators: No free lunch – another “go deeper” paper; this one shows that (under certain assumptions) it’s actually impossible to preserve all the properties you might like to have.

Submission: As usual, please send an email to kmcrane@cs.cmu.edu and nsharp@cs.cmu.edu no later than 10:00 AM on Tuesday, February 9th including the string DDGSpring2016 in your subject line.  Your email for readings should always include:

  1. a short (2-3 sentence) summary of what you read, and
  2. at least one question about something you found confusing / interesting / incomplete / not addressed.

Reading 4 – A Quick and Dirty Introduction to Differential Geometry

A1 Your reading assignment for Thursday is to read Chapter 2 of our course notes on Discrete Differential Geometry, “A Quick and Dirty Introduction to Differential Geometry.” This chapter provides a different perspective from the topological picture we’ve been studying in class: rather than slowly building everything “from the ground up” (sets, topology, smooth structure…) it skips immediately to the juicy stuff: curved surfaces with real geometry sitting in space. We’ll fill in everything “in between” in the next few lectures.

To test your own understanding, try computing (in explicit coordinates) the metric induced by the immersion
\[
f(u,v) := \frac{1}{u^2+v^2+1}(2u,2v,u^2+v^2-1),\qquad\qquad
\]
which maps the plane \(\mathbb{R}^2\) to the unit sphere in \(\mathbb{R}^3\). Do you notice anything special about this metric?

Submission: As usual, please send an email to kmcrane@cs.cmu.edu and nsharp@cs.cmu.edu no later than 10:00 AM on Thursday, February 4th including the string DDGSpring2016 in your subject line.  Your email for readings should always include:

  1. a short (2-3 sentence) summary of what you read, and
  2. at least one question about something you found confusing / interesting / incomplete / not addressed.