# Level Set Methods

## Dynamic Implicit Surfaces and the Hamilton-Jacobi Equation

Growing Set: avi mpg
Final Set: avi mpg

## Late Breaking News:

• 2007/01/29: Homework 2 is available below.
• 2007/01/26: Approximate schedule for the remaining lectures is posted below.
• 2007/01/15: Homework 1 is available below.
• 2007/01/10: Matlab tutorial for new Matlab users, 5 - 7pm, DMP 110.
• 2007/01/08: First Lecture.

## Handouts

Date Topic
January 8 Course Information and Tentative Outline..

## Homeworks

Homework Submission Policy:

• Get it in soon or I can't release solutions.
• Get it in by the end of the semester, or you won't get a grade.

# 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

• Computer Science,
• Applied Mathematics,
• Engineering and other application fields.

Prerequisites: None officially.

• Students should have seen elementary differential equations, multivariable calculus and introductory numerical methods.
• Be ready to program. Homework assignments will most easily be solved with Matlab. Programming in Matlab is essentially the same as Java or C but with lots of useful visualization tools. See the Links section for more discussion of Matlab, or Ian Mitchell's Matlab Resources web page for tutorials and demos.
• Course project proposals may be programmed in the language of the student's choosing, although programming is unlikely to be required for the proposal.
• Familiarity with numerical methods for partial differential equations is not necessary.
• If you are in doubt, come to the first class or see me.

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

• Email: mitchell (at) cs (dot) ubc (dot) ca
• Office Location: ICICS/CS 217
• Office Phone: (604) 822-2317
• Office Hours: TBA (and by appointment)

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

• Location is subject to change; check here or the CS Graduate Course web page or UBC Course Web Site for updates.
• There are no lectures Monday February 19 to Friday February 23 (Midterm break).
• There are no lectures Friday April 6 (Good Friday) or Monday April 9 (Easter Monday).
• There are no scheduled labs or tutorials for this course.

References:

• Level Set Methods and Dynamic Implicit Surface by Stanley Osher and Ronald Fedkiw. The official (required) textbook for the class, available at the bookstore. Excellent coverage of high order accuracy methods on structured grids, image processing and computational physics.
• Level Set Methods and Fast Marching Methods by James Sethian. The other level set book. Excellent coverage of fast marching methods, unstructured grids, and many other applications. Inexpensive.
• The manual for the Matlab Toolbox used in the course. Get the software and manual for version 1.1 beta.
• Research papers listed (and linked) in the Schedule below.

• 2-3 homework assignments
• 1-2 in class presentations
• 1 project
The relative weighting will depend on the precise number of homework assignments, exams and presentations.

Other References:

• Scientific Computing: An Introductory Survey by Heath.
• Numerical Analysis by Burden and Faires.
• Elementary Differential Equations and Boundary Value Problems by Boyce and DiPrima.
• Single Variable Calculus and Calculus of Several Variables by Adams.
• Partial Differential Equations by L. C. Evans.
• Finite Difference Schemes and Partial Differential Equations by Strikwerda.
• Finite Volume Methods for Hyperbolic Problems by LeVeque.
• Curves and Surfaces for Computer Aided Geometric Design by Farin.
• Geometric and Solid Modeling: An Introduction by Hoffmann.

## The Schedule:

• Topics of future lectures are subject to change.
• Readings marked "OF" are from the Osher and Fedkiw text, "S" are from the Sethian text, and "T" are from the Toolbox Manual.
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

• CPSC 542D Term 1 Winter 2006-2007 Course Web Page (this page): http://www.cs.ubc.ca/~mitchell/Class/CS542D.2006W2/index.html
• CPSC 542D is offered by
• A few of the many researchers active in level set methods (and their favorite applications, if applicable):
• We will use Mathworks' Matlab package for the programming components of this course.
• It includes powerful visualization, a standard imperative programming language, a full featured debugger, and many standard numerical algorithms for linear algebra and the approximation and discretization tasks we will encounter in this course.
• If you are unfamiliar with Matlab, take a look at Ian Mitchell's Matlab Resources web page or Mathworks' Introduction to Matlab.
• There are also many other tutorials available on the web, although many are quite old. The current version is 7.2 and should be available on the undergraduate machines.
• If you prefer to work from home, a student version of Matlab should be available for purchase from the UBC Bookstore. While the student version does not include all the toolboxes available on the undergraduate machines, it should be sufficient for the homework in this course.

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