Geometry Processing
Fall Term 2022
CSC419H1 Geometry Processing
CSC2520H Geometry Processing
Prof. Alec Jacobson
TAs, Frank Liu, Otman Benchekroun, Samarendra Dash
Lecutures: Tuesdays 3-5 LM 158
Office Hours: Tuesdays 5-5:30, Wednesdays 5-5:30
Tutorials: Thursdays 4-5 UC 179
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. Students will read academic papers and complete a small weekly programming assignment to implement a corresponding algorithm.
Through attendence of invited Toronto Geometry talks, students will be exposed to a wide variety of cutting-edge research in geometry processing.
Students sharpen crystalize their knowledge and sharpen their presentation skills by creating short explainer videos for geometry processing concepts.
Finally, students will implement a recent paper in the style of a libigl tutorial.
Objectives
- Students should understand, derive, and implement solutions to the prominent challenges that arise in geometry processing applications.
- Students should create a final creative project showcasing their implementation of the different processing algorithms.
- Students should develop an understanding of the mathematical underpinnings of geometry processing including useful discretized operators and energies.
- 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, 13/09/2022 | Geometry Processing Pipeline, "life of a shape", shapes, surface representations, Polygon Mesh Processing [Botsch et al. 2008] Intro Survey, due 12:00 noon ET 20/09/2022 HW 01 assigned, due 12:00 noon ET 20/09/2022 |
| Tuesday, 20/09/2022 | Representations, Topology vs Geometry tangents and normals, geometry vs. topology, orientability, discrete topology, graphs HW 02 assigned, due 12:00 noon ET 28/09/2022 (extended by one day) |
| Tuesday, 27/09/2022 | Acquisition & reconstruction, characteristic function, spatial gradient HW 03 assigned, due 12:00 noon 05/10/2022 |
| Tuesday, 04/10/2022 | 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] point-to-plane distance, iterative closest point, orthogonal Procrustes problem HW 04 assigned, due 12:00 noon 14/10/2022 |
| Tuesday, 11/10/2022 | Surface fairing & denoising, 1D smoothing flow, 1D energy-based smoothing, PDE, Implicit Time integration HW 05 assigned, due 12:00 noon 21/10/2022 |
| Tuesday, 18/10/2022 | 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 HW 06 assigned, due 12:00 noon 28/10/2022 Final Paper Implementation Paper Selection Form, due 12:00 noon 28/10/2022 |
| Tuesday, 25/10/2022 | Surface parameterization, texture mapping, mass-spring methods, graph drawing, harmonic maps, least squares conformal mapping, local parameterization, discrete exponential map, stroke parameterization HW 07 assigned, due 04/11/2022 |
| Tuesday, 01/11/2022 | 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 |
| Tuesday, 08/11/2022 | No Lecture: FAS Reading week. |
| Tuesday, 15/11/2022 | 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] Videos and Final papers due 05/12/2022 noon |
| Wednesday, 16/11/2022 | Last day to drop course |
| Tuesday, 22/11/2022 | TBD |
| Tuesday, 29/12/2022 | Signed distances continued. Outlook into geometry processing research. |
| Tuesday, 06/12/2022 | Video party libigl-style paper implementation due 5/12/2022 |
Cutting room floor: Quad meshing, Subdivision surfaces, Constructive solid geometry, Voxelization, Mesh decimation, simplification, remeshing
Discord
Lateness Policy
0.007% off for every minute late.
Academic Integrity
Any code must belong to the student submitting it. Submitted assignments may be automatically analyzed to identify suspicious levels of code similarity. Consequences of committing an academic offence can be severe.
By staying enrolled in this course, students acknowledge that they have read and understand the University of Toronto's definitions and policy on Academic Integrity.
Supplemental Textbook
Polygon Mesh Processing. Mario Botsch, Leif Kobbelt, Mark Pauly, Pierre Alliez, and Bruno Levy, 2008.
Grading
- 73% small assignments (equal weighting per-assignment)
- 18% libigl-style paper implementation
- 9% explainer videos, seminar attendance
Explainer Videos
An explainer is a short (< 4m minutes) video provides an introduction to or a summary of a topic. Using motion graphics, animation and/or narration, create a compelling video.
Upload the video on youtube. Be sure to include links to an videos or source material that you took inspiration from in your video description. Post a link on the discord channel.
Over the course of the semester you must create two unique videos for any of the topics introduced in the lecture, homeworks or linked readings. It's recommended that you make one 30-sec TikTok style video that's over the top exciting and for a general audience. And one 4-min youtube-style video where you explain a bit more than just hype.
Examples
- Dirac Belt Trick
- Sphere Eversion
- Punctured Torus Eversion
- Mathematical Magic: Undoing Handcuffs
- Euler's Formula V - E + F = 2 | Proof
- Delaunay Triangulation
- Voronoi diagrams
Got other great examples? Submit a PR on this README.md with a link!
Final Paper Implementation
Curated list of papers:
- A Laplacian for Nonmanifold Triangle Meshes
- A concise and provably informative multiβscale signature based on heat diffusion
- Anisotropic geometric diffusion in surface processing
- Appearance Mimicking Surfaces
- Can Mean-Curvature Flow be Modified to be Non-singular?
- Complementary Dynamics
- Compressed manifold harmonics
- Compressed vibration modes of elastic bodies
- Deep Geometric Texture Synthesis
- Developability of Heightfields via Rank Minimization
- Dynamic Kelvinlets: Secondary Motions based on Fundamental Solutions of Elastodynamics
- Fast Approximation of Laplace-Beltrami Eigenproblems
- Fast Quasi-Harmonic Weights for Geometric Data Interpolation
- Fast and Robust QEF Minimization using Probabilistic Quadrics
- Gaussian-Product Subdivision Surfaces
- Harmonic Triangulations
- Instant Neural Graphics Primitives with a Multiresolution Hash Encoding
- Interpolated Corrected Curvature Measures for Polygonal Surfaces
- LSMAT Least Squares Medial Axis Transform
- Laplace Operators for Tetrahedral Meshes
- Learning Smooth Neural Functions via Lipschitz Regularization
- Make it stand: balancing shapes for 3D fabrication
- Neural Jacobian Fields: Learning Intrinsic Mappings of Arbitrary Meshes
- Parallel Globally Consistent Normal Orientation of Raw Unorganized Point Clouds
- Phong Deformation: A Better CO Interpolant for Embedded Deformation
- Repulsive Curves
- SAL: Sign Agnostic Learning of Shapes from Raw Data
- Signing the Unsigned: Robust Surface Reconstruction from Raw Pointsets
- Stable Neo-Hookean Flesh Simulation
- Surface Reconstruction Based on Modified Gauss Formula
- Variational Surface Cutting
- Vector Heat Method
- You Can Find Geodesic Paths in Triangle Meshes by Just Flipping Edges ](https://arxiv.org/pdf/2205.02904.pdf)