On the last assignment, please be sure to use exactly the string DDG19A6 as the subject line – I don’t want to miss any of your submissions so soon before the grading deadline.

I missed a few submissions of earlier assignments due to people using a different subject – I think I’ve found all of the submissions, but it’s entirely possible that I’m still missing some. As far as I know, I have finished grading assignments 0-4. If you submitted any of those assignments but haven’t received a grade, please let me know. If you need to get in touch with me, it will probably be easier for you to email me at mgillesp@andrew.cmu.edu. The DDG class email inbox is always full of assignments/readings, so it’s easy for me to miss things.

## Assignment 6 [Written]: Vector Field Decomposition and Design (Due 5/14)

Warning: You cannot use late days on this assignment since it’s the last one.

In this assignment, you will investigate tools for working with tangent vector fields on surfaces. Tangent vector fields are central to classical differential geometry, and have many interesting applications. For this homework, we’ll look at one algorithm for designing vector fields, and along the way we’ll cover a lot of deep facts about surfaces.

There’s no PDF this week since the exercises are all from the notes.

Do any 12 of Exercise 8.1 – Exercise 8.21 in the notes, except for Exercise 8.13.

Submission Instructions. Please submit your solutions to the exercises (whether handwritten, LaTeX, etc.) as a single PDF file by email to Geometry.Collective@gmail.com. This email must also contain the .zip file for your coding solution. Scanned images/photographs can be converted to a PDF using applications like Preview (on Mac) or a variety of free websites (e.g., http://imagetopdf.com). Your submission email must include the string DDG19A6 in the subject line.

Warning: You cannot use late days on this assignment since it’s the last one.

## Assignment 6 [Coding]: Vector Field Decomposition and Design (Due 5/14)

Warning: You cannot use late days on this assignment since it’s the last one.

Please implement the following routines in:

1. projects/vector-field-decomposition/tree-cotree.js:
1. buildPrimalSpanningTree
2. inPrimalSpanningTree
3. buildDualSpanningCotree
4. inDualSpanningCotree
5. buildGenerators
2. projects/vector-field-decomposition/harmonic-bases.js:
1. buildClosedPrimalOneForm
2. compute

In addition, please implement either Hodge Decomposition, or Trivial Connections (on surfaces of genus 0):

Hodge Decomposition: Please implement the following routines in

1. projects/vector-field-decomposition/hodge-decomposition.js:
1. constructor
2. computeExactComponent
3. computeCoExactComponent
4. computeHarmonicComponent

Trivial Connections on Surfaces of Genus 0: Please implement computeConnections in projects/direction-field-design/trivial-connections.js. This file has function signatures for trivial connections on arbitrary surfaces, but for this assignment we are only requiring you to compute the connection form on simply-connected surfaces where you don’t have to worry about the period matrix. You are, of course, welcome to implement the general algorithm if you would like to!

Notes:

• I made some changes to the tests for this assignment, and to the trivial connections viewer. You should update the following files before starting the assignment:
• tests/vector-field-decomposition/test.html
• tests/vector-field-decomposition/test.js
• tests/direction-field-design/sphere.js
• tests/direction-field-design/test.html
• tests/direction-field-design/test.js
• projects/direction-field-design/index.html
• Recall that homology generators are a set of loops which somehow describe all of the interesting loops on a surface. For example, here are the two homology generators for the torus.
• Your buildGenerators function should implement the Tree-Cotree algorithm, which is Algorithm 5 of section 8.2 of the notes.
• In tree-cotree.js the trees are stored using the dictionaries vertexParent and faceParent. You should store the primal spanning tree by storing the parent of vertex v in vertexParent[v]. The root should be its own parent. Similarly, you should store the dual spanning cotree by storing the parent of face f in faceParent[f].
• The Tree Cotree algorithm finds homology generators on the dual mesh. That is to say, you should take each dual edge which is not in either spanning tree, and form a loop by following its endpoint back up the dual cotree until they meet at the root of the dual cotree. Even though we’re thinking of these homology generators as loops on the dual mesh, we still store them as lists of ordinary halfedges, since edges in the dual mesh are in 1-1 correspondence with edges in the primal graph.
• buildClosedPrimalOneForm should use a homology generator to construct a closed primal 1-form as described in section 8.22 of the notes.
• The compute function in HarmonicBases should compute a harmonic basis using Algorithm 6 in section 8.2 of the notes. If you choose to implement Hodge decomposition for the assignment, you are welcome to use your Hodge decomposition code to solve for $d\alpha$. Otherwise, you can just ignore the hodgeDecomposition parameter and directly solve the linear system $\Delta \alpha = \delta \omega$ to find $\alpha$. (Recall that $\delta$ is the codifferential, which we talked a lot about in the Discrete Exterior Calculus assignment).

Notes (Hodge Decomposition):

• The procedure for Hodge Decomposition is given as Algorithm 3 in section 8.1 of the Notes.
• Note that the SparseMatrix class has an invertDiagonal function that you can use to invert diagonal matrices.
• For computeCoExactComponent, you should compute the coexact component $\delta \beta$ of a differential form $\omega$ by solving the equation $d\delta \beta = d\omega$. As stated in the notes, the most convenient way of doing this is to define a dual 0-form $\tilde \beta := *\beta$, and then to solve $d*d \tilde \beta = d \omega$. Then you can compute $\delta \beta$ using the fact that $\delta \beta = *d*\beta = *d\tilde\beta$. When doing these computations, you should keep tract of whether your forms are primal forms or dual forms, recalling that hodge stars take you from primal forms to dual forms, and hodge star inverses take you from dual forms to primal forms. (THis is discussed in detail in section 8.1.3 of the notes.
• Note that the 2-form Laplacian B is not necessarily positive definite, so you should use an LU solver instead of a Cholesky solver when solving systems involving B.

Notes (Trivial Connections):

• The trivial-connection-js file is structured for implementing the full trivial connections algorithm on arbitrary surfaces. Since that’s tricky, we’re only requiring that you compute connections on topological spheres. You should implement this in the computeConnections() function, and it should pass the tests labeled “computeConnections on a sphere”.
• Even though we’re working with spheres, it is still helpful to use the formulation of Trivial connections given in section 8.4.1 of the notes. In particular, you should solve the optimization problem given in Exercise 8.21.
• On a sphere, there are no harmonic 1-forms, so the $\gamma$ part of your Hodge decomposition will always be 0. Furthermore, the sphere has no homology generators, so the problem simplifies to $\min_{\delta \beta} \;\|\delta\beta\|^2\;\text{s.t.}\; d\delta\beta = u$
• Following the notes, we observe that the constraint $d\delta\beta = u$ determines $\beta$ up to a constant, and that constant is annihilated by $\delta$. So you can find the connection 1-form $\delta \beta$ with a single linear solve.

Submission Instructions
Please rename all js files you edited to be txt files and put them 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 DDG19A6.

Warning: You cannot use late days on this assignment since it’s the last one.

## Lecture 21—Geodesics

In this lecture we’ll start taking a look at geodesics, which generalize the concept of a “straight line” to curved manifolds. Here again we encounter The Game of discrete differential geometry: different characterizations of geodesics—namely, straightest vs. (locally) shortest—will lead us down a path toward different discrete analogues, and ultimately, different algorithms.

## Assignment 5 [Written]: Geodesic Distance (Due 5/2)

Here’s the writeup for your second to last assignment. This time, we’re taking off the “training wheels” and having you read a real paper, rather than course notes. Why? Because you’re ready for it! At this point you have all the fundamental knowledge you need to go out into the broader literature and start implementing all sorts of algorithms that are built on top of ideas from differential geometry. In fact, this particular algorithm is not much of a departure from things you’ve done already: solving simple equations involving the Laplacian on triangle meshes. As discussed in our lecture on the Laplacian, you’ll find many algorithms in digital geometry processing that have this flavor: compute some basic data (e.g., using a local formula at each vertex), solve a Laplace-like equation, compute some more basic data, and so on.

Your main references for this assignment will be:

• this video, which gives a brief (18-minute) overview of the algorithm, and
• this paper, which explains the algorithm in detail.

Written exercises for this assignment are found below.

Warning: The original version of this assignment had an unsolvable linear system in Exercise 7. I updated the assignment on Thursday, so hopefully the exercise is possible now.

## Assignment 5 [Coding]: Geodesic Distance (Due 5/2)

For the coding portion of this assignment, you will implement the heat method, which is an algorithm for computing geodesic distance on curved surfaces. All of the details you need for implementation are described in Section 3 of the paper, up through and including Section 3.2. Note that you need only be concerned with the case of triangle meshes (not polygon meshes or point clouds); pay close attention to the paragraph labeled “Choice of Timestep.”

Please implement the following routines in:

1. projects/geodesic-distances/heat-method.js:
1. constructor
2. computeVectorField
3. computeDivergence
4. compute

Notes

• Refer to sections 3.2 of the paper for discretizations of Algorithm 1 (page 3).
• Recall that our Laplace matrix is positive semidefinite, which might differ from the sign convention the authors use.
• The tests for computeVectorField and computeDivergence depend on the A and F matrices you define in your constructor. So if you fail the tests but your functions look correct, check whether you have defined the flow and laplace matrices properly.
• Your solution should implement zero neumann boundary conditions (which are the “default behavior” of the cotan Laplacian) but feel free to tryout other Dirichlet and Neumann boundary conditions on your own.

Submission Instructions

Please rename your heat-method.js file to heat-method.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 DDG19A4.

## Reading 7—Discrete Conformal Geometry (Due Thursday, April 18)

Your next reading will take a deep dive into conformal geometry and the many ways to discretize and compute conformal maps. This subject makes some beautiful and unexpected connections to other areas of mathematics (such as circle packings, and hyperbolic geometry), and is in some sense one of the biggest “success stories” of DDG, since there is now a complete uniformization theorem that mirrors the one on the smooth side. You’ll find out more about what this all means in the reading! The reading comes from the note, “Conformal Geometry of Simplicial Surface”:

For your assignment you will need to read the Overview (1.1) and Preliminaries (1.2); you must also pick one of Part I, Part II, or Part III to read, each of which covers a different perspective on discrete conformal maps. The most interesting subject, perhaps, is the connections to hyperbolic geometry in Part IV, which you can read for your own enjoyment! 🙂

Hand-in instructions are, as usual, found on the assignments page. The reading is due at 10 AM Eastern, before lecture on April 18, 2019.

## Bonus Lecture: Simulation and Geometry

In this lecture, we saw some of the geometry underlying classical mechanics and explored how understanding this geometry can lead us to well-behaved simulation algorithms. Along the way, we explored conservation laws and Noether’s theorem.

You can find a demo of the different Euler integrators applied to a pendulum here, and you can find a demo of how they flow particles on phase space here.

## Assignment 4 [Written]: Conformal Parameterization (Due 4/16)

The written part of your next assignment, on conformal surface flattening, is now available below. Conformal flattening is important for (among other things) making the connection between processing of 3D surfaces, and existing fast algorithms for 2D image processing. You’ll have the opportunity to implement one of these algorithms in the coding part of the assignment.

## Assignment 4 [Coding]: Conformal Parameterization (Due 4/16)

For the coding portion of your assignment on conformal parameterization, you will implement the Spectral Conformal Parameterization (SCP) algorithm as described in the course notes.Please implement the following routines in

1. core/geometry.js:
1. complexLaplaceMatrix
2. projects/parameterization/spectral-conformal-parameterization.js:
1. buildConformalEnergy
2. flatten
3. utils/solvers.js:
1. solveInversePowerMethod
2. residual

Notes

• I added a few tests for utils/solvers.js. They’re available in the git repository. If you’re familiar with git, you can pull the changes. If you’d prefer not to mess around with git, you can also just download the files and put them in tests/utils.
• Warning: I fixed a problem with the residual test. In the notes, the residual is defined as a vector $Ax – \lambda x$. But your function residual should return a float. You should return $\frac{\|Ax – \lambda x\|_2}{\|x\|_2}$. Furthermore, you should compute $\lambda$ as $\frac{x^\dagger A x}{x^\dagger x}$ where $x^\dagger$ is the conjugate transpose of $x$.
• The complex version of the cotan-Laplace matrix can be built in exactly the same manner as its real counterpart. The only difference now is that the cotan values of our matrix will be complex numbers with a zero imaginary component. This time, we will work with meshes with boundary, so your Laplace matrix will have to handle boundaries properly (you just have to make sure your cotan function returns 0 for halfedges which are in the boundary).
• The buildConformalEnergy function builds a $|V| \times |V|$ complex matrix corresponding to the conformal energy $E_C(z) = E_D(z) – \mathcal A(Z)$ where $E_D$ is the Dirichlet energy (given by our complex cotan-Laplace matrix) and $\mathcal A$ is the total signed area of the region $z(M)$ in the complex plane (Please refer to Section 7.4 of the notes for more details). You may find it easiest to iterate over the halfedges of the mesh boundaries to construct the area matrix (Recall that the Mesh object has a boundaries variable which stores all the boundary loops.
• The flatten function returns a dictionary mapping each vertex to a vector (linear-algebra/vector.js) of planar coordinates by finding the eigenvector corresponding to the smallest eigenvalue of the conformal energy matrix. You can compute this eigenvector by using solveInversePowerMethod (described below).
• Your solveInversePowerMethod function should implement Algorithm 1 in Section 7.5 of the course notes with one modification – after computing $Ay_i = y_{i-1}$, center $y_i$ around the origin by subtracting its mean. You don’t have to worry about the $B$ matrix or generalized eigenvalue problem. Important: Terminate your iterations when your residual is smaller that 10^-10.
• The parameterization project directory also contains a basic implementation of the Boundary First Flattening (BFF) algorithm. Feel free to play around with it in the viewer and compare the results to your SCP implementation.

Submission Instructions

Please rename your geometry.js, spectral-conformal-parameterization.js and solvers.js files to geometry.txt, spectral-conformal-parameterization.txt and solvers.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 DDG19A4.

## Lecture 20: Discrete Conformal Geometry

In this lecture we’ll attempt to translate several smooth characterizations of conformal maps into the discrete setting. We’ll also see how each of these attempts leads to a different class of computational algorithms, with different trade offs. Although conformal maps are often associated with angle preservation, we’ll see that preserving angles at the discrete level results in a theory that is far to rigid: i.e., it does not capture any of the interesting structure of smooth conformal geometry. Instead, we’ll see how less-obvious starting points (such as patterns of circles, or preservation of length cross ratios) lead to some deep and beautiful connections between the classic smooth picture, and the discrete, combinatorial picture.

## Lecture 19: Conformal Geometry

A basic task in geometric algorithms is finding mappings between surfaces, which can be used to transfer data from one place to another. A particularly nice class of algorithms (both from a mathematical and computational perspective) are conformal mappings, which preserve angles between vectors, and are generally very well-behaved. In this lecture we’ll take a look at smooth characterizations of conformal maps, which will ultimately inspire the way we talk about conformal maps in the discrete/computational setting.

## Reading 6—The Laplace Operator (due March 28)

Your next reading covers one of the most fundamental objects in differential geometry, and one of the most useful objects in practical geometry processing: the Laplace-Beltrami operator $\Delta$, which we’ll often refer to as just the “Laplacian”. This operator generalizes the familiar Laplace operator $\Delta = \frac{\partial^2}{\partial x_1^2} + \cdots + \frac{\partial^2}{\partial x_n^2}$ from Euclidean $\mathbb{R}^n$ to general curved manifolds. Like the ordinary Laplacian, at a very basic level Laplace-Beltrami provides information about the “curvature” of a function. It also shows up in an enormous number of physical and geometric equations, and for this reason there has been intense study of different ways to discretize the Laplacian (not only for simplicial meshes, but also point clouds and other discrete surface representations).

The reading will expose you to some of the key issues to think about when designing a discrete Laplacian. For this reading, you can choose either of the following two papers:

You should not worry about deeply understanding all of the mathematical details in these papers; the point is just to get a sense of the issues at stake, and how these considerations translate into practical definitions of discrete Laplace matrices. The first paper, by Wardetzky et al, considers a “No Free Lunch” theorem for discrete Laplacians that continues our story of “The Game” played in discrete differential geometry. The second paper, by Bobenko & Springborn considers the important perspective of intrinsic triangulations of polyhedral surfaces, and uses this perspective to develop a Laplace operator that is well-behaved even for very poor quality triangulations. You should simply summarize the high-level ideas in these papers, and any questions you might have.

The reading is due on Thursday, March 28 at 10am Eastern time. Hand-in instructions are as usual described on the assignments page.

## Lectures 17 & 18—Laplace Beltrami

In the next two lectures we’ll take a deep dive into one of the most important objects not only in discrete differential geometry, but in differential geometry at large (not to mention physics!): the Laplace-Beltrami operator. This operator generalizes the familiar Laplacian you may have studied in vector calculus, which just gives the sum of second partial derivatives: $\Delta \phi = \sum_i \partial^2 \phi_i / \partial x_i^2$. We’ll motivate Laplace-Beltrami from several points of view, talk about how to discretize it, and show how from a computational point of view it really is the —Swiss army knife— of geometry processing algorithms, essentially replacing the discrete Fourier transform from classical signal processing.

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

## Steiner Formula for Surfaces in $\mathbb{R}^3$

In the slides we derived a Steiner formula for polyhedral surfaces in $\mathbb{R}^3$, by considering the Minkowski sum with a ball and working out expressions for the areas and curvatures associated with vertices, edges, and faces. But we can also get a Steiner formula for smooth surfaces, using the expressions already derived in class. In particular, recall that for a closed surface $f: M \to \mathbb{R}^3$ with Gauss map $N$, we can obtain the basic curvatures by just wedging together $df$ and $dN$ in all possible ways:
$\begin{array}{rcl} df \wedge df &=& 2NdA \\ df \wedge dN &=& 2HNdA \\ dN \wedge dN &=& 2KNdA \\ \end{array}$
Here $H$ and $K$ denote the mean and Gauss curvature (resp.), and dA is the area form induced by $f$. For sufficiently small $t$, taking a Minkowski sum with a ball is the same as pushing the surface in the normal direction a distance $t$. In other words, the surface
$f_t := f + tN$
will describe the “outer” boundary of the Minkowski sum; this surface has the same Gauss map $N$ as the original one. To get its area element, we can take the wedge product
$\begin{array}{rcl} df_t \wedge df_t &=& (df + t dN) \wedge (df + t dN) \\ &=& df \wedge df + 2t df \wedge dN + t^2 dN \wedge dN, \end{array}$
where we have used the fact that $\alpha \wedge \beta = \beta \wedge \alpha$ when $\alpha,\beta$ are both $\mathbb{R}^3$-valued 1-forms. The list of identities above then yields
$df_t \wedge df_t = (2 + 4tH + 2t^2 K)NdA,$
or equivalently,
$\fbox{$dA_t = (1+2tH+t^2K)dA.$}$
In other words, just as in the polyhedral case, the rate at which the area is growing is a polynomial in the ball radius $t$; the coefficients of this polynomial are given by the basic curvatures of the surface (also known as quermassintegrals!).

## Lecture 16—Discrete Curvature II (Variational Viewpoint)

In this lecture we wrap up our discussion of discrete curvature, and see how it all fits together into a single unified picture that connects the integral viewpoint, the variational viewpoint, and the Steiner formula. Along the way we’ll touch upon several of the major players in discrete differential geometry, including a discrete version of Gauss-Bonnet, Schläfli’s polyhedral formula, and the cotan Laplace operator—which will be the focus of our next set of lectures.

## Lecture 15—Discrete Curvature I (Integral Viewpoint)

Just as curvature provides powerful ways to describe and analyze smooth surfaces, discrete curvatures provide a powerful way to encode and manipulate digital geometry—and is a fundamental component of many modern algorithms for surface processing. This first of two lectures on discrete curvature from the integral viewpoint, i.e., integrating smooth expressions for discrete curvatures in order to obtain curvature formulae suitable for discrete surfaces. In the next lecture, we will see a complementary variational viewpoint, where discrete curvatures arise by instead taking derivatives of discrete geometry. Amazingly enough, these two perspectives will fit together naturally into a unified picture that connects essentially all of the standard discrete curvatures for triangle meshes.

## Lecture 14—Smooth Curvature

Much of the geometry we encounter in everyday life (such as curves and surfaces sitting in space) is well-described by it curvatures. For instance, the fundamental theorem for plane curves says that an arc-length parameterized plane curve is determined by its curvature function, up to rigid motions. Similar statements can be made about surfaces and their curvatures, which we explore in this lecture.

## Lecture 13—Discrete Surfaces

We’ll follow up our lecture on smooth surfaces with a view of surfaces from the discrete point of view. Our goal will be to translate basic concepts (such as the differential, immersions, etc.) into a purely discrete language. Here we’ll also start to see the benefit of developing discrete differential forms: many of the statements we made about surfaces in the smooth setting can be translated into the discrete setting with minimal effort. As we move forward with discrete differential geometry, this “easy translation” will enable us to take advantage of deep insights from differential geometry to develop practical computational algorithms.

## Lecture 12—Smooth Surfaces

This lecture gives a crash course in the differential geometry of surfaces. There’s of course way more to know about surfaces than we can pack into a single lecture (and we’ll see plenty more later on), but this lecture will cover basic concepts like how to describe a surface and its normals. It also starts to connect surface theory to the other tools we’ve been building up, via vector-valued differential forms.

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

## Reading 5—Curves and Surfaces (due 3/7)

Your next reading complements our in-class discussion of the geometry of curves and surfaces. In particular, you should read Chapter 3 of the course notes, pages 28–44. This reading is due next Thursday, March 7.

Handin instructions are described on the Assignments Page.

Since these notes just barely scratch the surface (literally), I am often asked for recommendations on books that provide a deeper discussion of surfaces. The honest answer is, “I don’t know; I mostly didn’t learn it from a book.” But there are a couple fairly standard references (other) people seem to like, both of which should be available digitally from the CMU library:

## Lecture 11—Discrete Curves

This lecture presents the discrete counterpart of the previous lecture on smooth curves. Here we also arrive at a discrete version of the fundamental theorem for plane curves: a discrete curve is completely determined by its discrete parameterization (a.k.a. edge lengths) and its discrete curvature (a.k.a. exterior angles). Can you come up with a discrete version of the fundamental theorem for space curves? If we think of torsion as the rate at which the binormal is changing, then a natural analogue might be to (i) associate a binormal $B_i$ with each vertex, equal to the normal of the plane containing $f_{i-1}$, $f_{i}$, and $f_{i+1}$, and (ii) associate a torsion $\tau_{ij}$ to each edge $ij$, equal to the angle between $B_i$ and $B_{i+1}$. Using this data, can you recover a discrete space curve from edge lengths $\ell_{ij}$, exterior angles $\kappa_i$ at vertices, and torsions $\tau_{ij}$ associated with edges? What’s the actual algorithm? (If you find this problem intriguing, leave a comment in the notes! It’s not required for class credit.)

## Lecture 10—Smooth Curves

After spending a great deal of time understanding some basic algebraic and analytic tools (exterior algebra and exterior calculus), we’ll finally start talking about geometry in earnest, starting with smooth plane and space curves. Even low-dimensional geometry like curves reveal a lot of the phenomena that arise when studying curved manifolds in general. Our main result for this lecture is the fundamental theorem of space curves, which reveals that (loosely speaking) a curve is entirely determined by its curvatures. Descriptions of geometry in terms of “auxiliary” quantities such as curvature play an important role in computation, since different algorithms may be easier or harder to formulate depending on the quantities or variables used to represent the geometry. Next lecture, for instance, we’ll see some examples of algorithms for curvature flow, which naturally play well with representations based on curvature!

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

## Slides—Discrete Exterior Calculus

This lecture wraps up our discussion of discrete exterior calculus, which will provide the basis for many of the algorithms we’ll develop in this class. Here we’ll encounter the same operations as in the smooth setting (Hodge star, wedge product, exterior derivative, etc.), which in the discrete setting are encoded by simple matrices that translate problems involving differential forms into ordinary linear algebra problems.

## 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…

This assignment is due on Tuesday, February 26.

## Slides—Discrete Differential Forms

In this lecture, we turn smooth differential $k$-forms into discrete objects that we can actually compute with. The basic idea is actually quite simple: to capture some information about a differential $k$-form, we integrate it over each oriented $k$-simplex of a mesh. The resulting values are just ordinary numbers that give us some sense of what the original $k$-form must have looked like.

## Slides—Exterior Calculus II: Integration

Our first lecture on exterior calculus covered differentiation; our second lecture completes the picture by discussing integration of differential forms. The relationship between integration and differentiation is encapsulated by Stokes’ theorem, which generalizes the fundamental theorem of calculus, as well as many other important theorems from vector calculus and complex analysis (divergence theorem, Green’s theorem, Cauchy’s integral formula, etc.). Stokes’ theorem also plays a key role in numerical discretization of geometric problems, appearing for instance in finite volume methods and boundary element methods; for us it will be the essential tool for developing a discrete version of differential forms that we can actually compute with.

## Reading 4: Exterior Calculus — due 2/14

The next reading assignment will wrap up our discussion of exterior calculus, both smooth and discrete. In particular, it will explore how to differentiate and integrate $k$-forms, and how an important relationship between differentiation and integration (Stokes’ theorem) enables us to turn derivatives into discrete operations on meshes. In particular, the basic data we will work with in the computational setting are “integrals of derivatives,” which amount to simple scalar quantities we can associate with the vertices, edges, faces, etc. of a simplicial mesh. These tools will provide the basis for the algorithms we’ll explore throughout the rest of the semester.

The reading is the remainder of Chapter 4 from the course notes, “A Quick and Dirty Introduction to Exterior Calculus”, Sections 4.6 through 4.8 (pages 67–83). Note that you just have to read these sections; you do not have to do the written exercises; a different set of written problems will be posted later on. The reading is due Thursday, February 14 at 10am. See the assignments page for handin instructions.

## Slides—Exterior Calculus I: Differentiation

Ordinary calculus provides tools for understanding rates of change (via derivatives), total quantities (via integration), and the total change (via the fundamental theorem of calculus). Exterior calculus generalizes these ideas to $n$-dimensional quantities that arise throughout geometry and physics. Our first lecture on exterior calculus studies the exterior derivative, which describes the rate of change of a differential form, and (together with the Hodge star) generalizes the gradient, divergence, and curl operators from standard vector calculus.

## Slides—Differential Forms in $R^n$

A differential $k$-form describes a $k$-dimensional measurement at each point of space. For instance, the area 2-form on a sphere tells us how much each little piece of the sphere should contribute to an integral over the sphere. In this lecture we give some basic facts and definitions about differential $k$-forms, and how to work with them in coordinates. Ultimately differential $k$-forms will pave the way to a general notion of integration, which in turn will be our basic mechanism for turning smooth equations into discrete ones (by integrating over elements of a mesh).

## Reading 3: Exterior Algebra and k-Forms (due 2/7)

Your next reading assignment will help you review the concepts we’ve been discussing in class: describing “little volumes” or $k$-vectors using the wedge product and the Hodge star, and measuring these volumes using “dual” volumes called $k$-forms. These objects will ultimately let us integrate quantities over curved domains, which will also be our main tool for turning smooth equations from geometry and physics into discrete equations that we can actually solve on a computer.

The reading is Chapter 4, “A Quick and Dirty Introduction to Exterior Calculus”, up through section 4.5.1 (pages 45–65). It will be due Thursday, February 7 at 10am Eastern time. See the assignments page for handin instructions.

Your next homework will give you some hands-on practice with differential forms; just take this time to get familiar with the basic concepts.

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

## Slides—$k$-Forms

Today we continue our journey toward building up (discrete) exterior calculus by talking about how to measure little k-dimensional volumes. Just like rulers measure length, and cups measure volume, k-forms will be used to take measurements of the little k-dimensional volumes or k-vectors that we built up using exterior algebra in our previous lecture. Such measurements will ultimately allow us to talk about integration over curved spaces; in the discrete setting, these measurements will be the basic data we associate with the elements of mesh.

## Recitation

We will have a recitation on Tuesday at 4:30 in Gates 4102 to go over the Javascript framework that we use in this class. I will review the halfedge data structure, and I’ll go over some examples of using our framework. I will also talk about sparse matrices and solving linear systems of equations.

Recitation Slides

## Slides—Exterior Algebra

Today’s lecture will cover one of the basic tools we’ll use throughout the rest of the course: exterior algebra. The basic idea is to add a couple new operations to our usual list of vector operations (dot product, cross product, etc.) that make it easy to talk about volumes rather than just vectors. If you felt ok working with things like the cross product and the determinant in your linear algebra/vector calculus courses, this shouldn’t be too big of a leap. (If not, could be a good moment for a review!)

## Assignment 0 (Written): Combinatorial Surfaces — due 2/7

For the written part of your first homework you will do some exercises that will help familiarize you with basic descriptions and representations of combinatorial surfaces (simplicial surfaces, adjacency matrices, halfedge meshes), which will help prepare you to work with such surfaces as we continue through the course. (If any of this stuff seems abstract right now, don’t worry: we’ll use it over and over again to implement “real” algorithms starting in just a couple weeks!)

You must complete 8 out of 15 exercises in the Written Exercises section of Chapter 2 of the course notes. You may choose any set of 8 exercises you like, but if you do more than 8, please mark clearly on your submission which ones you would like us to grade.

The assignment is due on February 7, 2019 at 5:59:59pm Eastern (not at midnight!). Further hand-in instructions can be found on this page.

## Assignment 0 (Coding): Combinatorial Surfaces — due 2/7

For the coding portion of your first assignment, you will implement some operations on simplicial complexes which were discussed in class and in Chapter 2 of the course notes. Once implemented, you will be able to select simplices and apply these operations to them by clicking the appropriate buttons in the viewer (shown above).

Getting Started

• Please download or clone the files in this repository. It contains a fast and flexible framework for 3D geometry processing implemented in Javascript. Over the course of the semester, you will implement all of your coding assignments here.
• For this assignment, you will need to implement the following routines in projects/simplicial-complex-operators/simplicial-complex-operators.js:
• assignElementIndices
• buildVertexVector
• buildEdgeVector
• buildFaceVector
• star
• closure
• isComplex
• isPureComplex
• boundary

Notes

• This assignment comes with a viewer projects/simplicial-complex-operators/index.html which lets you apply your operators to simplices of meshes and visualize the results.
• Selecting simplices will not work until you fill in the assignElementIndices function.
• The assignment also comes with a test script tests/simplicial-complex-operators/text.html which you can use to verify the correctness of your operators.
• The code framework is implemented in Javascript, which means no compilation or installation is necessary on any platform. You can simply get started by opening the index.html file in projects/discrete-exterior-calculus/ in a web browser. We recommend using Chrome or Firefox. Safari has poor WebGL performance.
• If you do not have prior experience with Javascript, do not worry! You should be able to get a handle on Javascript syntax by reading through some of the code in the framework (a good place to start might be core/geometry.js). The framework also contains extensive documentation (see docs/index.html).
• All browsers come with tools for debugging (for instance the JavaScript Console in Chrome).

Submission Instructions

Please rename your simplicial-complex-operators.js file to simplicial-complex-operators.txt and submit it in a zip file called solution.zip to Geometry.Collective@gmail.com.

## Reading 2: Combinatorial Surfaces (Due 1/29)

Your next reading will take a dive into purely combinatorial descriptions of surfaces, i.e., those that capture connectivity, but not geometry.  These descriptions and data structures will provide the foundation for all the geometry and algorithms we’ll build up in this class.  (The reading also provides the essential background for your first written and coding assignments!)

The reading is Chapter 2, pages 7–20 of our course notes, which can always be accessed from the link above.

Your short 2-3 sentence summary is due by 10am Eastern on January 29, 2019.  Handin instructions can be found on the assignment page.

## Reading 1: Overview of DDG (Due 1/22)

Your first reading assignment will be to read an overview article on Discrete Differential Geometry. Since we know we have a diverse mix of participants in the class, you have several options (pick one):

1. (pages 1–3) Crane & Wardetzky, “A Glimpse into Discrete Differential Geometry”.
This article discusses the “no free lunch” story about curvature we looked at in class, plus a broader overview of the field.
2. (pages 1–5) Pottman et al, “Architectural Geometry”.
This article discusses the beautiful tale of how discrete differential geometry is linked to modern approaches to computational design for architecture, as well as fabrication and “rationalization” of free-form designs.
3. (pages 5–9) Bobenko & Suris, “Discrete Differential Geometry: Consistency As Integrability”.
This article provides another overview of discrete differential geometry, with an emphasis on nets and their connection to the notion of integrability in geometry and physics.

Though written for a broad audience, be warned that all of these articles are somewhat advanced—the goal here is not to understand every little detail, but rather just get a high-level sense of what DDG is all about.

Assignment: Pick one of the readings 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.  For this first assignment, we are also very interested to know a little bit about YOU! E.g., why are you taking this course?  What’s your background?  What do you hope to get out of this course?  What are your biggest fears about the course?  Etc.

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 day of the next lecture (September 7, 2017).

Enjoy!

## Assignment -1: Favorite Formula

Part of your course grade is determined by participation, which can include both in-class participation as well as discussion here on the course webpage.  Therefore, your first assignment is to:

1. create an account, and
2. leave a comment on this post containing your favorite mathematical formula (see below).
To make things interesting, your comment should include a description of your favorite mathematical formula typeset in $\LaTeX$.  If you don’t know how to use $\LaTeX$ this is a great opportunity to learn — a very basic introduction can be found here.  (And if you don’t have a favorite mathematical formula, this is a great time to pick one!)

(P.S. Anyone interested in hearing about some cool “favorite theorems” should check out this podcast.)

## Welcome to Discrete Differential Geometry! (Spring 2019)

Welcome to the website for 15-458/858 (Discrete Differential Geometry).  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!

To participate in the class, you must register using your Andrew (CMU) email address.

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 \int_M K dA = 2\pi\chi gets typeset as $\int_M K dA = 2\pi\chi$.
If you encounter any problems while trying to use the website, please contact the TA (listed under the course description).