# Geometry Processing

Fall Term 2018
CSC2520H Geometry Processing
CSC490H1 Capstone Design: Geometry Processing
Prof. Alec Jacobson
T 3–5 MP 137

The class is aimed at preparing students for working with geometric data via understanding fundamental theoretical concepts. Students should have a background in Linear Algebra and Computer Programming. Previous experience with Numerical Methods, Differential Equations, and Differential Geometry is appreciated but not required.

Extending traditional signal processing, geometry processing interprets three-dimensional curves and surfaces as signals. Just as audio and image signal data can be filtered, denoised and decomposed spectrally, so can the geometry of a three-dimensional curve or surface.

In this course, we study the algorithms and mathematics behind fundamental operations for interpreting and manipulating geometric data. These essential tools enable: geometric modeling for computer aided design, life-like animations for computer graphics, reliable physical simulations, and robust scene representations for computer vision.

Topics include: discrete curves and surfaces, curvature computation, surface reconstruction from point clouds, surface smoothing and denoising, mesh simplification, parameterization, symmetry detection, shape deformation and animation.

## Organization

In lecture we will cover the mathematical background and visual intuition of the week’s topic. At home, students will read academic papers and complete a small weekly programming assignment to implement a corresponding algorithm. By the end of the semester, these algorithms compose a toolbox that students can use to create a unique artifact: the final project is to use these tools to create a unique piece of geometry to visualize (as an image or interactive experience) or 3D print.

## Objectives

1. Students should understand, derive, and implement solutions to the prominent challenges that arise in geometry processing applications.
2. Students should create a final creative project showcasing their implementation of the different processing algorithms.
3. Students should develop an understanding of the mathematical underpinnings of geometry processing including useful discretized operators and energies.
4. Students should develop a working knowledge of libigl to develop these algorithms without worrying about the grunt-work of OpenGL viewers, quadrature, etc.

## Prerequisites

Students should have already taken Linear Algebra and Calculus.

Students should have already taken Introduction to Computer Science and should be proficient in computer programming (in any language) and should feel comfortable programming in C++.

While knowledge of Partial Differential Equations is not required, it will certainly be very handy for derivations. A quick survey will be posted to help students evaluate their readiness on these topics.

On the programming side, we will be coding mainly in C++ and using a libigl, an open-source geometry processing library. We will be using Eigen for computational linear algebra, and Cmake for building the coding assignments.

## A Mathematical Foundation

Much of the framing for our techniques will be looking at the continuous analogue of our problem and discretizing it in an intrinsic way, preserving continuous theorems as much as possible. We will discretize continuous operators like the Laplacian and the Gradient, and we will find adequate representations of concepts like normal vectors and curvature. Perhaps surprisingly we will see that there are many choices of discretization, each with their own benefits and downsides, prompting us to choose appropriately for the particular application.

## Schedule

Lecture Date Tentative Topic
Tuesday, 11/09/2018 Geometry Processing Pipeline, “life of a shape”, shapes, surface representations, tangents and normals, geometry vs. topology
Polygon Mesh Processing [Botsch et al. 2008]
HW 00 assigned, due 17/01/2018
Tuesday, 18/09/2018 orientability, discrete topology, meshes, data structures
Acquisition & reconstruction, characteristic function, spatial gradient
“Poisson surface reconstruction” [Kazhdan et al. 2006]
HW 01 assigned due 29/01/2018
Tuesday, 25/09/2018 quadratic energy minimization, marching cubes
Alignment & registration Hausdorff distance, integrated closest point distance
“Object modelling by registration of multiple range images” [Chen & Medioni 1991]
“A method for registration of 3-D shapes” [Besl & McKay 1992]
“Efficient Variants of the ICP Algorithm” [Rusinkiewicz & Levoy 2001]
“Sparse Iterative Closest Point” [Bouaziz et al. 2013]
HW 02 assigned due 05/02/2018
Tuesday, 02/10/2018 point-to-plane distance, iterative closest point, orthogonal Procrustes problem
Surface fairing & denoising, 1D smoothing flow, 1D energy-based smoothing, PDE, Implicit Time integration
Discrete Differential Geometry “Forum”
“Curve and surface smoothing without shrinkage” [Taubin 1995]
“Skeleton extraction by mesh contraction” [Au et al. 2008]
“Can Mean-Curvature Flow Be Made Non-Singular” [Kazhdan et al. 2005]
Tuesday, 09/10/2018 Smoothing continued, Spatial Laplacian, calculus of variations, Green’s Identity, role of trace in quadratic energies, minimizing quadratic energies in libigl
HW 03 assigned due 13/02/2018
Tuesday, 16/10/2018 Surface parameterization, Guest lecture by Ryan Schmidt, texture mapping, mass-spring methods, graph drawing, harmonic maps, least squares conformal mapping, local parameterization, discrete exponential map, stroke parameterization
“Intrinsic parameterizations of surface meshes” [Desbrun et al. 2002]
“Least squares conformal maps for automatic texture atlas generation” [Lévy et al. 2002]
“Spectral conformal parameterization” [Mullen et al. 2008]
“Interactive Decal Compositing with Discrete Exponential Maps” [Schmidt et al. 2006]
HW 04 assigned, due 20/02/2018 24/02/2018
Tuesday, 23/10/2018 Shape deformation, continuous deformation, pointwise mappings, energy-based model, handle-based deformation, local distortion mesure, gradient-based distortion, Laplacian-based distortion, as-rigid-as-possible
“An intuitive framework for real-time freeform modeling” [Botsch & Kobbelt 2004]
“On linear variational surface deformation methods” [Botsch & Sorkine 2008]
“As-rigid-as-possible surface modeling” [Sorkine & Alexa 2007]
“Bounded Biharmonic Weights for Real-Time Deformation” [Jacobson et al. 2010]
HW 05 assigned due 06/03/2018
Tuesday, 30/10/2018 “Reading Week” (warning: not the same as FAS)
Tuesday, 06/11/2018 Curvature & surface analysis Planar curves, tangents, arc-length parameterization, osculating circle, curvature, turning number theorem, discrete curvature, normal curvature, minimum/maximum/mean curvature Principal curvature, Gauss map, Euler’s theorem, shape operator, Gaussian curvature
“Computing Discrete Minimal Surfaces and Their Conjugates” [Pinkall and Polthier 1993]
“Gaussian Curvature and Shell Structures” [Calladine 1986]
“Discrete differential-geometry operators for triangulated 2-manifolds” [Meyer et al. 2002]
Elementary Differential Geometry, [Barret O’Neill 1966
Discrete Differential Geometry: An Applied Introduction, SIGGRAPH Course, [Grinspun et al. 2005]
Tuesday, 13/11/2018 Subdivision surfaces
“Subdivision for Modeling and Animation” [Zorin et al. 2000]
Tuesday, 20/11/2018 Mesh decimation, simplification, remeshing
“Surface Simplification Using Quadric Error Metrics” [Garland and Heckbert 1997]
“A Remeshing Approach to Multiresolution Modeling” [Botsch and Kobbelt 2004]
Tuesday, 27/11/2018 Signed distances, Offset surfaces, inside-outside segmentation, medial axis, isosurface/level sets, signed distances to polyhedra, parity counting, winding number
“Signed Distance Computation using the Angle Weighted Pseudo-normal” [Baerentzen & Aanaes 2005]
“3D distance fields: a survey of techniques and applications” [Jones et al. 2006]
“Robust Inside-Outside Segmentation using Generalized Winding Numbers” [Jacobson et al. 2013]
Tuesday, 04/12/2018 Final project presentations

Cutting room floor: Quad meshing, Subdivision surfaces, Constructive solid geometry, Voxelization

## Slack

dgp-graphics.slack.com, #geometry-processing channel, ask dgp member for invite

## Lateness Policy

0.007% off for every minute late.

## Supplemental Textbook

Polygon Mesh Processing. Mario Botsch, Leif Kobbelt, Mark Pauly, Pierre Alliez, and Bruno Levy, 2008.

## Grading

• 50% small assignments
• 25% final project:
• in-class presentation
• formal two-page technical extended abstract
• (less formal) in depth documentation
• it’s great if you can align with your research, but please discuss this with me early on.
• 20% participation: in class, reading papers, answering “Issues” on assignments
• 5% full-class collaborative project: improve https://en.wikipedia.org/wiki/Geometry_processing and related topics
• Graded based on delta of this page between now and end of term
• Grade is shared by entire class