A Toolbox of Level Set Methods

version 1.1.1

Ian Mitchell

Department of Computer Science

University of British Columbia


Version 1.1.1

Primarily a bug fix version.

A few new functions were added to the kernel: deleteDimension, downsampleGrid, dividedDifferenceTable and getCellIndexes. For more details on these functions, see their help entries.

The user manual has not been updated for version 1.1.1.


Download the toolbox

Documentation: Download the user manual (pdf, 1.8 MB).

Source code: We recommend retrieving a version from the ToolboxLS public repository at BitBucket.org. The current stable release is tagged "ToolboxLS-1.1.1".

If you are very uncomfortable with version control systems, you can download an archived copy of Toolbox-1.1.1 (zip, 288 KB). By clicking on this link, you agree to the license terms, which are also available in the file LICENSE in the top directory of this archive.

Once you have retrieved a copy, follow the instructions in the README file.


Minimum Time to Reach the Origin for a Double Integrator.

For those who prefer pictures:

Important Notes

  • The Toolbox requires basic Matlab. No additional toolboxes are needed.
    • Version 1.1.1 of ToolboxLS definitely works with Matlab Versions 7.14 (R2012a) and 7.11 (R2012b).
    • Version 1.1 of ToolboxLS definitely works with Matlab Versions 6.5, 7.2 (R2006a) and 7.5 (R2007b).
    • Other versions of Matlab have not been directly tested.
  • The Toolbox is not a tutorial on level set methods. For that purpose I recommend [1] and/or [2]. Because the Toolbox focuses on regular grids and time-dependent PDEs, it follows [1] more closely.
  • If you find the Toolbox useful, please send me an email (mitchell (at) cs.ubc.ca). The more people who use the toolbox, the more justification I have for continuing its development.

Growing Set: avi mpg
Final Set: avi mpg

More Details

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

These algorithms have application in such fields as:

  • Computational Geometry and Mesh Generation.
  • Differential Games.
  • Dynamic Programming.
  • Financial Mathematics.
  • Fluid and Combustion Simulation.
  • Graphics.
  • Image Processing and Computer Vision.
  • Robotics and Control.
  • Verification and Reachable Sets.

Compared to their competitors, level set methods can be relatively easy to implement. However, picking through the literature to find all the gory details of high accuracy methods, and then debugging the code in three dimensions (or more) is a slow process at best.

This Toolbox is designed to minimize the sum of coding, execution and analysis time for those who want to explore level set methods. Computationally, Matlab is not the fastest environment in which to solve PDEs, but as a researcher I have found that the enviroment has several important advantages over faster compiled implementations:

  • Built in visualization, including three dimensional isosurfaces.
  • Fully functional debugger, including the ability to visualize two and three dimensional surfaces while debugging.
  • No compilation is required, so it is easy to write scripts, construct initial conditions and examine results interactively.
  • All the source code for the Toolbox is provided (as m-files).
  • Kernel code can be written in a dimensionally independent manner.
  • Execution time is quite reasonable (even for three dimensional problems), through the use of Matlab's "vectorization" and restriction of the computational domain to regular Euclidean grids.

The Toolbox is not a tutorial on level set methods. Users unfamiliar with these algorithms should consult one or both of the textbooks [1],[2] (or the academic literature cited therein). Because of the focus of the current version of the toolbox, it follows [1] more closely.

In addition to examples which demonstrate the basic features of the toolbox, recreations of examples from [1] and [2] are included, as well as solutions of general time-dependent HJ PDEs and calculations of reachable sets.

References


Growing Set: avi mpg


Growing Set: avi mpg


Email Me If You

  • Find the Toolbox useful for something. When it comes time to justify my research agenda to granting agencies and the university, the popularity of my software package(s) will definitely help. If you can tell me how you use the Toolbox and how to improve it, all the better.
  • Would like to be informed of future releases.
  • Find a bug in the toolbox. I will need a (small sized) example of the code which recreates the bug. Note that numerical instability (the level set function blows up) is usually caused by incorrect driver code (initialization, boundary conditions, dynamics or CFL choice), not by kernel code.
  • Implement a useful feature. External contributions to the toolbox are welcome, although documentation will be needed.
  • Would like a feature implemented. I cannot implement all requests, but I will try to implement popular ones.

My email address is: mitchell (at) cs.ubc.ca


Additional Code

Some additional code selections from publications. By clicking on any of these links, you agree that the
license terms applicable to the Toolbox of Level Set Methods also applies to this additional code that you download.

Related Publications and Citing the Toolbox

Here are some papers related to the Toolbox which may contain material that does not appear in the Toolbox documentation.

Also, citations matter to my academic career, so if you have used the Toolbox in research that will be published, please choose a citation appropriate to the field of publication from the list below. While citations and links to the web site are greatly appreciated, please do not use a URL as the only citation in published work.


Previous Versions

Version 1.1 (June 2007) Version 1.0 (July 2004)

The php script in the links is just a free click counter (to help me justify future releases) and leads immediately to the download files.


Created 25 June 2004.
Last updated 24 August 2012.
Created and maintained by Ian Mitchell.

Here is a dummy link. Don't click on it.