Keenan Crane
Digital Geometry Processing with Discrete Exterior Calculus
Keenan Crane
Last updated: March 18, 2015
SIGGRAPH 2013 Lecturers:Fernando de Goes, Keenan Crane,
Mathieu Desbrun, Peter Schröder
SGP 2013 Lecturers:Etienne Vouga, Keenan Crane
This course provides an introduction to geometry processing using discrete exterior calculus (DEC). DEC provides a simple, flexible, and efficient framework within which one can build a unified platform for geometry processing. The course provides essential mathematical background as well as a large array of real-world examples. It also provides a short survey of the most relevant recent developments in digital geometry processing and discrete differential geometry.

Course material has been used for semester-long courses at Caltech (2011, 2012, 2013, 2014), Columbia University (2013), and RWTH Aachen University (2014), as well as special sessions at SIGGRAPH (2013) and SGP (2012, 2013, 2014).

These notes grew out of a Caltech course on discrete differential geometry (DDG) over the past few years. Some of this material has also appeared at SGP Graduate schools and a course at SIGGRAPH 2013. Peter Schröder, Max Wardetzky, and Clarisse Weischedel provided invaluable feedback for the first draft of many of these notes; Mathieu Desbrun, Fernando de Goes, Peter Schröder, and Corentin Wallez provided extensive feedback on the SIGGRAPH 2013 revision. Thanks to Mark Pauly's group at EPFL for suffering through (very) early versions of these lectures, to Katherine Breeden for musing with me about eigenvalue problems, and to Eitan Grinspun for detailed feedback and for helping develop exercises about convergence. Thanks also to those who have pointed out errors over the years: Mirela Ben-Chen, Nina Amenta, Chris Wojtan, Yuliy Schwarzburg, Robert Luo, Andrew Butts, Scott Livingston, Christopher Batty, Howard Cheng, Gilles-Philippe Paillé, Jean-François Gagnon, Nicolas Gallego-Ortiz, Henrique Teles Maia, Joaquín Ruales, Papoj Thamjaroenporn, and all the students in CS177 at Caltech, as well as others who I am currently forgetting!
@inproceedings{Crane:2013:DGP, author = {Keenan Crane, Fernando de Goes, Mathieu Desbrun, Peter Schröder}, title = {Digital Geometry Processing with Discrete Exterior Calculus}, booktitle = {ACM SIGGRAPH 2013 courses}, series = {SIGGRAPH '13}, year = {2013}, location = {Anaheim, California}, numpages = {126}, publisher = {ACM}, address = {New York, NY, USA}, }
C++several fundamental geometry processing algorithms (parameterization, smoothing, geodesic distance, ) implemented in a single unified DEC framework.
A surprisingly wide variety of geometry processing tasks can be easily implemented within the single unified framework of discrete exterior calculus (DEC). Above: a conformal parameterization preserves angles between tangent vectors on the initial surface.
Curvature flow can be used to smooth out noisy data or optimize the shape of a surface.
The shortest distance along the surface can be rapidly computed by solving two standard sparse linear equations.
Flows on surfaces can be designed by specifying a few singularities and looking for the smoothest vector field everywhere else.
We also show how to improve mesh quality, which generally improves the accuracy of geometry processing tasks.
Most of these applications boil down to solving a sparse Poisson equation. Above: a prototypical example of a Poisson (or Laplace) equation is the interpolation of boundary data by a harmonic function.
For surfaces of nontrivial topology, one also needs to compute fundamental cycles, which can be achieved using simple graph algorithms.
The decomposition of a vector field into its constituent parts also plays an important role in geometry processing—we describe a simple algorithm for Helmholtz-Hodge decomposition based on the discrete Poisson equation.