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 Late breaking news Things to print Handouts Homeworks Course Overview Course Details Audience Prerequisites Instructor Lecture Time and Location Textbooks Grades Other Reading Tentative Schedule Course Projects Related Links

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

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.

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

• 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.

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

• 2-3 homework assignments
• 1-2 in class presentations
• 1 project

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.
• Some readings and/or links may not be operational from computers outside the UBC domain. If you have problems, please contact the instructor.
• Readings marked "OF" are from the Osher and Fedkiw text, "S" are from the Sethian text, and "T" are from the Toolbox Manual.

Course Project Examples:

Links:

• 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
• Ian Mitchell
• Department Computer Science
• University of British Columbia
• A few of the many researchers active in level set methods (and their favorite applications, if applicable):
  • Ronald Fedkiw (animation and fluids)
  • Ben Houston (animation)
  • Ron Kimmel (image processing and robotics)
  • Stanley Osher (image processing)
  • Steve Ruuth (at SFU, PDE solvers)
  • James A. Sethian (many different applications)
  • Alexander Vladimirksy (control theory and differential games)
  • Hong-Kai Zhao (image processing and graphics)
• 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.