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.

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.

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!