Growing Set: avi mpg
Final Set: avi mpg
|January 8||Course Information and Tentative Outline..|
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 OverviewLevel 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:
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:
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.
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
Grades: Your final grade will be based on a combination of
|#||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.|
|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|