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.

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.

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.

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:
df \wedge df &=& 2NdA \\
df \wedge dN &=& 2HNdA \\
dN \wedge dN &=& 2KNdA \\
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
df_t \wedge df_t
&=& (df + t dN) \wedge (df + t dN) \\
&=& df \wedge df + 2t df \wedge dN + t^2 dN \wedge dN,
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.