Reading: Geodesic Distance and the Heat Method

For the final reading, we will take a look at the paper “The Heat Method for Distance Computation”, by Crane, Weischedel, and Wardetzky. Note that all students should do this reading, even if you’ve already completed four written/coding assignments. The hand-in instructions are the same as for all previous reading assignments; the reading is due on Thursday, December 14th.

Assignment 5 (Written): Geodesic Distance

Here’s the writeup for your final assignment, which is due on Thursday, December 14th. 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.

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

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