Optional Reading: Discrete Conformal Geometry

Those of you interested in taking a “deeper dive” into discrete conformal geometry might want to take a look at the course notes below, written for for an upcoming AMS short course on discrete differential geometry. Be warned that these notes are a (very) rough draft, and there will be errors and omissions! 🙂

[Note: these notes are not a required reading.]

Complex-valued differential forms

In Assignment 4, you get to work with complex-valued differential forms. These work mostly the same as real-valued differential forms, but there are a couple additional features.

  • Recall that the wedge product for real-valued two 1-forms \(\alpha\), \(\beta\) is defined as
    \(\alpha \wedge \beta (u, v) = \alpha(u)\cdot \beta(v) – \alpha(v)\cdot \beta(u),\)
    where “\(\cdot\)” in the usual product for real numbers. The wedge product for complex-valued 1-forms is identical, except that \(\cdot\) is replaced with the complex product
    \((a + bi) \cdot (c + di) = ac – bd + (ad + bc)i.\)
  • A special operator on the complex numbers is the conjugation map \(z \mapsto \bar{z}\), where \(\overline{a + bi} = a – bi\). This operator can be applied to complex-valued forms, too. For a \(k\)-form \(\alpha\) the conjugate will be
    \(
    \overline{\alpha}(X_1, …, X_k) = \overline{\alpha(X_1, …, X_k)}
    \)
    Note that conjugations commutes with the exterior calculus operators \(d\), \(\star\) and \(\wedge\). That is, \(\overline{d\alpha} = d\overline{\alpha}\), \(\overline{\star \alpha} = \star \overline{\alpha}\) and \(\overline{\alpha \wedge \beta} = \overline{\alpha} \wedge \overline{\beta}\).

Please ask in the comments if there is anything else you need to be clarified about complex-valued differential forms.

Assignment 4 (Coding): Conformal Parameterization

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

  • 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.
  • The buildConformalEnergy function builds a $|V| \times |V|$ complex matrix corresponding to the conformal energy $E_C(z) = E_D(z) – A(z)$, where $E_D$ is the Dirichlet energy (given by our complex cotan-Laplace matrix) and $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.
  • 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. 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 DDG17A4.

Slides — Conformal Geometry

Conformal geometry is, in a sense, the study of geometry when you can measure angles, but not lengths. Though this viewpoint may seem a bit abstract, it plays an surprisingly interesting and important role in both smooth and discrete differential geometry. For one thing, it provides a setting for working with surfaces that is both very simple and very regular—recall for instance that we typically like to work with regular curves, because we can be confident that subsequent quantities will be well-defined (tangents, normals, curvatures, etc.); if we assume curves have an arc length parameterization, then life becomes particularly simple because we don’t have to worry about accounting for “stretching” as we go from the domain to the image of the curve. Likewise, with surfaces, we tend to work with immersions, which provide a useful notion of regularity. What’s the analogue of an arc-length parameterization for surfaces? In general it’s impossible to find a parameterization that has no stretching whatsoever, but we can always find one that at least preserves angles—a so-called conformal parameterization. Akin to arc-length parameterized curves, the amount of extra information about “stretching” that we need to carry around is now minimal. Moreover, the condition of angle preservation automatically gives us even more regularity than even a plain immersion: it automatically guarantees that our map is smooth. Note that this whole story applies equally well in both the smooth and discrete case: just as we had notions of discrete regularity for polygonal curves and discrete immersions for simplicial surfaces, we will also have a notion of discrete conformal equivalence for triangle meshes. Beyond these analytical properties, discrete conformal geometry leads to a huge number of fast, useful, and beautiful algorithms, which we will study and implement in the next few weeks.

(Note: these slides will also help you understand the homework, so please take a look!)

Assignment 4 (Written): Conformal Parameterization

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 (to be announced soon).