CPSC 542D, Term 2, Winter 2006-2007 Class Home Page

Level Set Methods

Dynamic Implicit Surfaces and the Hamilton-Jacobi Equation


Contents of this page


Growing Set: avi mpg
Final Set: avi mpg


Late Breaking News:


Handouts

Date Topic
January 8 Course Information and Tentative Outline..


Homeworks

Homework Submission Policy:

# Topic Assigned Due Date Assignment Other Assignment Files & Links Solution Other Solution Files
1 Implicit Surface Functions & Matlab Practice January 15 January 22 Problem Set Example Matlab function example.m, demonstrating coding style and useful plotting commands. If the formatting looks bogus, you might find it easier to get it from the ugrad server example.m. TBA
2 Dynamic Implicit Surfaces January 29 March 2 Problem Set none TBA

Course Overview

Level set methods are a class of numerical algorithms for simulation of dynamic implicit surfaces and approximation of solutions to the Hamilton-Jacobi (HJ) partial differential equation (PDE).

Dynamic implicit surfaces prove useful in such fields as:

  • Computational Geometry and Mesh Generation.
  • Fluid and Combustion Simulation.
  • Graphics and Animation.
  • Image Processing and Computer Vision.

The benefits of an implicit representation of surfaces include hassle free merging and separation of surfaces, easy computation of geometric properties like normals and curvature, and the fact that both curves in two dimensions and surfaces in three dimensions can be treated with the same theory and computational algorithms.

The course will begin with an examination of numerical methods for computing dynamically evolving implicit surfaces. Students will experiment in Matlab with state-of-the-art high order accuracy methods using a Toolbox of Level Set Methods developed by the instructor, and will therefore be able to progress rapidly to application specific details from the fields mentioned above.

Although it was not covered this year, the second part of the class would have turned to the HJ PDE, which arises in such fields as:

  • Dynamic Programming.
  • Financial Mathematics and Mathematical Ecology (through Stochastic Differential Equations).
  • Robotics and Optimal Control.
  • Verification and Reachable Sets.
  • Zero-Sum Differential Games.

This component would have examined generalizations of the level set methods mentioned above, as well as other classes of algorithms (including fast marching, ordered upwind, and sweeping) and some of the viscosity solution theory underlying this ubiquitous equation.

Applications will be explored depending on students' interests.




Course Details

Intended Audience: Graduate students in

Prerequisites: None officially.

Computer Science Breadth: This course does not count toward the computer science graduate breadth requirement, because it concentrates on solving one particular class of PDEs, and hence does not cover the bigger picture of numerical differential equations. However, it is an introductory class in the sense that previous experience with PDEs is not necessary.

Instructor: Ian Mitchell

Lectures: 2:00 - 3:30, Mondays and Wednesdays, ICICS/CS 238

References:

Grades: Your final grade will be based on a combination of

The relative weighting will depend on the precise number of homework assignments, exams and presentations.

Other References:


The Schedule:

# Date Topic Links Required Readings Optional Readings
1 Jan 8 Introduction. Set & surface representations. Introductory slides. none. Representations: Farin; Hoffmann.
ODEs: Boyce & DiPrima 8; Heath 9.
2 Jan 10 Set & surface tasks. Implicit surface function implementation of tasks, including constructive solid geometry and surface geometry none. OF 1 T section 3.3
3 Jan 15 Signed Distance Functions. Toolbox Introduction. Toolbox of Level Set Methods OF 2 none.
4 Jan 17 Computer representation of continuous functions: Finite difference and alternatives. Stability digression. none none Heath 8.6, 9.3.1, 10.4; Strikwerda 1
5 Jan 22 Types of differential equations: ODEs vs PDEs and IVPs vs BVPs vs IBVPs. Matlab function representation. Motion by convective flow. none. OF 3.1; T 3.1-3.3, 2.1 Heath 9, 10.1-10.2, 10.4, 11.1-11.3
6 Jan 24 Lax-Richtmayer equivalence and Barles-Souganidis extension. Upwind spatial derivative approximation. Temporal derivative approximation. CFL timestep restriction. none OF 3.2 Heath 11.2; G. Barles & P.E. Souganidis, "Convergence of Approximation Schemes for Fully Nonlinear Second Order Equations," Asymptotic Analysis volume 4, pp.271-283 (1991). [not online]
7 Jan 29 CFL timestep restriction. Multiple dimensional motion. Ollivier-Gooch IAM talk. none OF 3.2 none
8 Jan 31 High order methods (TVD RK, ENO, WENO). none OF 3.3-3.5 T 2.10.2
9 Feb 5 Motion in the Normal direction. Combinations of Motion. none OF 6.1, 6.2, 6.4; T 2.3.2-2.3.3 none
10 Feb 7 Reinitialization. Motion by Mean Curvature. none OF 7.1-7.4, 4.1-4.3, 6.3; T 2.2.1, 2.3.1, 2.4 S 2.3-2.4, 12.1-12.3; Adam M. Oberman, "A Convergent Monotone Difference Scheme for Motion of Level Sets by Mean Curvature," Numerische Mathematik, v.99, pp. 365-379 (2004).
11 Feb 12 General first order HJ terms. Other term: discounting, forcing. none OF 5.1, 5.3; T 2.2.2, 2.5, 2.8.2, 2.8.3 none
12 Feb 14 Constraints and Masking. Applications: Reach Sets. Reach Set Lecture Slides T 2.2.3, 2.6 S 12.4.3; Adam M. Oberman, "Convergent Difference Schemes for Nonlinear Elliptic and Parabolic Equations: Hamilton-Jacobi Equations and Free Boundary Problems," SIAM J. Numerical Analysis, volume 44, number 2, pp. 879-895 (2006); Claire J. Tomlin, Ian M. Mitchell, Alexandre M. Bayen & Meeko Oishi, "Computational Techniques for the Verification of Hybrid Systems," Proceedings of the IEEE, volume 91, number 7, pp. 986-1001 (July 2003).
13 Feb 14 Particle Level Set Method. PLS lecture slides. OF 5.2, 9; Doug Enright, Ronald Fedkiw, Joel Ferziger & Ian Mitchell, "A Hybrid Particle Level Set Method for Improved Interface Capturing," J. Computational Physics, volume 183, pp.83-116 (2002). OF 14-21. Doug Enright, Steven Marschner & Ronald Fedkiw, "Animation and Rendering of Complex Water Surfaces," ACM Trans. Graphics (SIGGRAPH), volume 21, number 3, pp.736-744 (2002); Frank Losasso, Ronald Fedkiw & Stanley Osher, "Spatially Adaptive Techniques for Level Set Methods and Incompressible Flow," Computers and Fluids, volume 35, pp. 995-1010 (2006).
Feb 19-23 Midterm Break (no class)
Feb 26 - April 12 Lectures Cancelled. Project Meetings with Instructor.
April 16-30 Final Exam Period. Project Reports Due.

Course Project Examples:

Students who took this course in 2004 prepared the following projects:

Student Topic Title
Eric Brochu 3D Visualization Implicit Surface Ray Tracer
Tyson Brochu Faster Time Integration Algorithm Semi-Lagrangian Time Integration
Wan Chen Image Segmentation Application Active Contour Without Edges in Level Set Formulation
Sarah Cormier Algorithm to Reduce Computational Complexity A Toolbox Implementation of the Local Level Set Method
Kevin Loken Algorithm to Reduce Numerical Dissipation Particle Level Set Method
Zhenguo Pan New Type of Surface Motion Level Set Method for Motion by Surface Diffusion
Scott Olsen Path Planning Application Level Set Methods Approach to Optimal Path Planning
Tiberiu Popa Generation of Explicit Surface Representation in 3D Survey of Triangulation Algorithms of Implicit Function Represented on Regular Grids
Tim Rees Financial Mathematics Application A Level Set Approach to a Stochastic Differential Equation in Mathematical Finance
Dana Sharon Algorithm for Solving the Stationary HJB Implementation of the Fast Marching Method
Ian Stavness Surface Reconstruction Application Reconstruction of Surfaces from Unorganized Data Points
David White Additional Toolbox Features Spatial and Time-Dependent Boundary Conditions
Alan Woo Physically Based Modelling Application Low-Speed Flame
Yongning Zhu Adaptive Mesh Refinement Adaptively Refined Meshes for Level Set Functions

Links:


CPSC 542D Term 1 Winter 2006-2007 Class Page
maintained by Ian Mitchell