Prerequisites: linear algebra, vector calculus, some programming experience.
This course focuses on three-dimensional geometry processing, while simultaneously providing a first course in traditional differential geometry. Our main goal is to show how fundamental geometric concepts (like curvature) can be understood from complementary computational and mathematical points of view. This dual perspective enriches understanding on both sides, and leads to the development of practical algorithms for working with real-world geometric data. Along the way we will revisit important ideas from calculus and linear algebra, putting a strong emphasis on intuitive, visual understanding that complements the more traditional formal, symbolic treatment. The course provides essential mathematical background as well as a large array of real-world examples and applications. It also provides a look at recent developments in digital geometry processing and discrete differential geometry. Topics include: curves and surfaces, curvature, connections and parallel transport, exterior algebra, exterior calculus, Stokes’ theorem, simplicial homology, de Rham cohomology, Helmholtz-Hodge decomposition, conformal mapping, geodesics, finite element methods, and numerical linear algebra. Applications include: approximation of curvature, curve and surface smoothing, surface parameterization, vector field design, and computation of geodesic distance.
14 Jan (Tue)Overview(slides,
video)Our first lecture provides motivation for the topics we’ll cover in the course, and takes a deep dive into one specific example (curvature of curves in the plane) to highlight some of the basic principles of discrete differential geometry. This example moves pretty fast and uses some ideas that we’ll study at a slower, more careful pace later on. For now, don’t worry too much about the details—the goal here is to just get a sense of what the course is all about!
16 Jan (Thu)Meshes(slides,
video)In this lecture we'll really start from the beginning, and define some of the basic objects we'll use throughout the class. In particular, we'll look at the idea of a “mesh,” and study one very specific kind of mesh called an oriented simplicial complex.
21 Jan (Tue)Manifolds(slides,
video)This lecture gives a first glimpse of the idea of manifolds, which are central to differential geometry. Rather than giving a formal definition in the smooth case, we’ll start with a notion of discrete manifolds that capture the most important ideas. These discrete manifolds build on the idea of a simplicial complex, introduced in the previous lecture.
23 Jan (Thu)Exterior Algebra(slides,
video)We next cover one of the basic tools used throughout the rest of the course: exterior algebra. The basic idea is to add a couple new operations to our usual list of vector operations (dot product, cross product, etc.) that make it easy to talk about volumes rather than just vectors. If you felt ok working with things like the cross product and the determinant in your linear algebra/vector calculus courses, this shouldn't be too big of a leap.
28 Jan (Tue)k-forms(slides,
video)Today we continue our journey toward building up (discrete) exterior calculus by talking about how to measure little k-dimensional volumes. Just like rulers measure length, and cups measure volume, k-forms will be used to take measurements of the little k-dimensional volumes or k-vectors that we built up using exterior algebra in our previous lecture. Such measurements will ultimately allow us to talk about integration over curved spaces; in the discrete setting, these measurements will be the basic data we associate with the elements of mesh.
30 Jan (Thu)Differential Forms(slides,
video)A differential k-form describes a k-dimensional measurement at each point of space. For instance, the area 2-form on a sphere tells us how much each little piece of the sphere should contribute to an integral over the sphere. In this lecture we give some basic facts and definitions about differential k-forms, and how to work with them in coordinates. Ultimately differential k-forms will pave the way to a general notion of integration, which in turn will be our basic mechanism for turning smooth equations into discrete ones (by integrating over elements of a mesh).
04 Feb (Tue)Exterior Derivative(slides,
video)Ordinary calculus provides tools for understanding rates of change (via derivatives), total quantities (via integration), and the total change (via the fundamental theorem of calculus). Exterior calculus generalizes these ideas to n-dimensional quantities that arise throughout geometry and physics. Our first lecture on exterior calculus studies the exterior derivative, which describes the rate of change of a differential form, and (together with the Hodge star) generalizes the gradient, divergence, and curl operators from standard vector calculus.
06 Feb (Thu)Integration(slides,
video)Our first lecture on exterior calculus covered differentiation; our second lecture completes the picture by discussing integration of differential forms. The relationship between integration and differentiation is encapsulated by Stokes' theorem, which generalizes the fundamental theorem of calculus, as well as many other important theorems from vector calculus and complex analysis (divergence theorem, Green's theorem, Cauchy's integral formula, etc.). Stokes' theorem also plays a key role in numerical discretization of geometric problems, appearing for instance in finite volume methods and boundary element methods; for us it will be the essential tool for developing a discrete version of differential forms that we can actually compute with.
11 Feb (Tue)Discrete Differential Forms(slides,
video)In this lecture, we turn smooth differential k-forms into discrete objects that we can actually compute with. The basic idea is actually quite simple: to capture some information about a differential k-form, we integrate it over each oriented k-simplex of a mesh. The resulting values are just ordinary numbers that give us some sense of what the original k-form must have looked like.
13 Feb (Thu)Discrete Exterior Calculus(slides,
video)This lecture wraps up our discussion of discrete exterior calculus, which will provide the basis for many of the algorithms we'll develop in this class. Here we'll encounter the same operations as in the smooth setting (Hodge star, wedge product, exterior derivative, etc.), which in the discrete setting are encoded by simple matrices that translate problems involving differential forms into ordinary linear algebra problems.
18 Feb (Tue)Vector Valued Forms(slides,
video)The reason we spent so much time developing (discrete) exterior calculus is that it will provide a natural language for talking about—and computing with—curves and surfaces. To make the transition to curves and surfaces complete, we will need to talk briefly about vector-valued forms, i.e., differential forms which produce vector rather than scalar values when used to measure tangent vectors. Really this is not so different: for most operations we just apply the usual scalar operations to each component. However, there are some small differences for things like the wedge product that will make this language very expressive for curve and surface calculations. (This lecture is short, so we may also get started on curves.)
20 Feb (Thu)Smooth Curves(slides,
video)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!
25 Feb (Tue)Discrete Curves(slides,
video)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). This theorem is then extended to a fundamental theorem for discrete space curves, in terms of length, discrete curvature, and discrete torsion.
27 Feb (Thu)Smooth Surfaces I(slides,
video)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 as a parameterization, the difference between an immersion and an embedding, and the key concepts of a Riemannian metric which is central to much of differential geometry.
11 Mar (Tue)Smooth Surfaces II(slides,
video)In this lecture we continue our discussion of smooth surfaces, introducing the Gauss map which will later help us make sense of curvature. We also connect surface theory to the language of exterior calculus, which help us transition to the discrete case.
13 Mar (Thu)Discrete Surfaces(slides,
video)We 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.
18 Mar (Tue)Smooth Curvature(slides,
video)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.
20 Mar (Thu)Discrete Curvature I(slides,
video)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.
25 Mar (Tue)Discrete Curvature II(slides,
video)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.
27 Mar (Thu)Laplacian(slides,
video)In this lecture we 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. We'll motivate Laplace-Beltrami from several points of view, which will in the next lecture lead to different approaches to discretization.
01 Apr (Tue)Discrete Laplacian(slides,
video)This lecture explores how we can discretize the Laplace-Beltrami operator, and show how from a computational point of view it is a sort of “Swiss army knife” of geometry processing algorithms, essentially replacing the discrete Fourier transform from classical signal processing.
03 Apr (Thu)Spring Carnival
08 Apr (Tue)Conformal Geometry(slides,
video)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.
10 Apr (Thu)Discrete Conformal Geometry(slides,
video)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.
15 Apr (Tue)Geodesics I(slides,
video)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. This first lecture covers the locally shortest perspective. We'll also see a glimpse of where (some) meshes come from, in connection with the so-called medial axis.
17 Apr (Thu)Geodesics II(slides,
video)This second lecture covers the “straightest” notion of geodesics, leading to a different discretization than what we saw with the “locally shortest” definition. This exploration also leads us into a discussion of some key ideas from Riemannian geometry, the exponential map and logarithmic map, that help us understand what it means to take an “average” of points on a curved surface. We'll also get a glimpse at traditional calculations in Riemannian geometry, by working out the geodesic equation in Christoffel symbols (and comparing/contrasting to the discrete approach!).
22 Apr (Tue)Intrinsic Triangulations I(slides,
video)The next two lectures explore how the intrinsic perspective of Riemannian geometry can be used to de-couple the mesh used to encode geometry from the one used for computation. The basic shift in perspective is to encode the geometry of a mesh not in terms of ordinary vertex positions, but instead only in terms of edge lengths. Intrinsic triangulations have a long history in mathematics, but only in recent years have been applied to practical geometric computing. We begin by giving motivation for intrinsic triangulations in terms of recent problems in computer graphics, review some key mathematical background, and describe basic data structures for intrinsic triangulations (overlay, signpost, normal coordinates).
24 Apr (Thu)Intrinsic Triangulations II(slides,
video)Using the machinery from our previous lecture, we next translate algorithms from computational geometry and scientific computing into algorithms for curved surfaces. In particular, we look at mesh parameterization, vector field processing, finding geodesics, and solving partial differential equations (PDEs). We also discuss how intrinsic triangulations can help with processing of nonmanifold meshes and point clouds, and conclude with a discussion of open questions.
Roughly every two weeks you will implement some kind of numerical algorithm for working with geometry. An important part of this exercise will be deriving the algorithms, starting from the smooth geometric point of view that we will discuss in class. Each assignment is split roughly between derivations/proofs, and coding exercises. However, you will not have to write this code “from scratch”—for each assignment we will provide a code skeleton and ask you to implement critical routines that have been removed. Since this class tends to be a fairly diverse mix, we suggest that folks with a strong coding background seek out those with a strong math background and vice versa. However, your final work must be your own!
Homework Submission
Assignments are due by 5:59:59 PM Eastern time on the due date (not midnight!)
All homework must be submitted digitally using GradeScope
Put all source files in a single zip file called solution.zip.
All written exercises must be digitized for submission, and uploaded to Gradescope. We won’t accept physical paper submissions.
You can either typeset your answers (using, e.g., LaTeX) or include scans/photos of your written work.
Feedback on your written assignment will be sent back to you via GradeScope
Late policy: You may take up to 5 total late days over the course of the semester, no questions asked. All subsequent late assignments will receive a zero. Late days are for assignments only (not readings). To receive credit, you must indicate which late day you’re using (1–5) on your assignment by including the corresponding “Latonic solid”:
You can either draw these solids by hand, or use one of the provided image files.
Periodically we will ask you to read from the course notes or from other sources online. To encourage you to think more deeply about this material, we will ask you to write a response to each reading consisting of
a short (2-3 sentence) summary of what you read, and
at least one question or comment about something you found interesting and/or confusing.
Writing this summary will also help you prepare for our in-class discussion. Summaries should be uploaded to Gradescope. To receive credit, you must upload your summary by 10:00 AM Eastern time on the day of lecture. Reading summaries must be turned in on time to receive credit (no late days can be used here).
Grading
Grades will be determined by performance on written and coding assignments, as well as participation in discussions in-class and on the course webpage. You will also be periodically asked to do readings from our course notes or from relevant papers, and provide short (2-3 sentence) written summaries. There will be seven assignments (with deadlines outlined on the course calendar) comprised of both a written and coding portion. The first two assignments are mandatory, because they establish a framework that will be used for all remaining assignments. To give you a bit of flexibility during the semester, you can skip one out of the remaining five assignments with no penalty. A 7th assignment can be completed for up to 15% extra credit. The last assignment (A6) will be given in lieu of a final. The grade breakdown is as follows:
Assignments – 90% (pick 6 out of 7)
(15%) A0: Combinatorial Surfaces (can’t skip this one!)
(15%) A1: Exterior Calculus (can’t skip this one!)
(15%) A2: Curvature
(15%) A3: The Laplacian
(15%) A4: Conformal Parameterization
(15%) A5: Geodesic Distance
(15%) A6: Tangent Vector Fields
Readings – 10%
(10%) – reading summaries/questions (1.1̅% each)
Collaboration policy: You are arestrongly encouraged to discuss all course material with your peers, including the written and coding assignments. You are especially encouraged to seek out new friends from other disciplines (CS, math, engineering, etc.) whose experience might complement your own. However, your final work must be your own, written up in your own words and/or implemented by yourself. For instance, if you work collaboratively (e.g., on a whiteboard) you should erase it and go write up your own solution by yourself somewhere. You should not show other students your final writeup, or your final code, nor they should not look at it.
Cheating policy: Don’t cheat. If you get caught, you will get a zero in the course. This has happened before, and it was (truly) very sad for everyone. Duplicate work turned in by two different students will be considered cheating by both students (e.g., even if student A simply found student B’s printout on the printer and maliciously copied it) so be diligent about keeping your final work private!
