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

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^* A x}{x^* x}$ where $x^*$ 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 DDG20A4.

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


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

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.

The video covering both today and Thursday’s lecture (on discrete aspects of conformal maps) can be found here.

Reading 7—Discrete Conformal Geometry (Due Tuesday, April 21)

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.

Lecture 18 (revised): The Laplace-Beltrami Operator

In this lecture we take a close look at the Laplacian, and its generalization to curved spaces via the Laplace-Beltrami operator. The Laplacian is one of the most fundamental objects in geometry and physics, and which plays a major role in algorithms. Here we consider several perspectives to build up some basic intuition about what the Laplacian is, and what it means.

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

You can find a video lecture for these slides, from a talk given by Etienne Vouga, here.

Lecture 17—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.