SpringerLink
Log in

The Flexible, Extensible and Efficient Toolbox of Level Set Methods

  • Published:
Journal of Scientific Computing Aims and scope Submit manuscript

Abstract

Level set methods are a popular and powerful class of numerical algorithms for dynamic implicit surfaces and solution of Hamilton-Jacobi PDEs. While the advanced level set schemes combine both efficiency and accuracy, their implementation complexity makes it difficult for the community to reproduce new results and make quantitative comparisons between methods. This paper describes the Toolbox of Level Set Methods, a collection of Matlab routines implementing the basic level set algorithms on fixed Cartesian grids for rectangular domains in arbitrary dimension. The Toolbox’s code and interface are designed to permit flexible combinations of different schemes and PDE forms, allow easy extension through the addition of new algorithms, and achieve efficient execution despite the fact that the code is entirely written as m-files. The current contents of the Toolbox and some coding patterns important to achieving its flexibility, extensibility and efficiency are briefly explained, as is the process of adding two new algorithms. Code for both the Toolbox and the new algorithms is available from the Web.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
EUR 32.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or Ebook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Germany)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Adalsteinsson, D., Sethian, J.A.: The fast construction of extension velocities in level set methods. J. Comput. Phys. 148, 2–22 (1999)

    Article  MATH  MathSciNet  Google Scholar 

  2. Barles, G., Souganidis, P.E.: Convergence of approximation schemes for fully nonlinear second order equations. Asymptot. Anal. 4(3), 271–283 (1991)

    MATH  MathSciNet  Google Scholar 

  3. Cardaliaguet, P., Quincampoix, M., Saint-Pierre, P.: Set-valued numerical analysis for optimal control and differential games. In: Bardi, M., Raghavan, T.E.S., Parthasarathy, T. (eds.) Stochastic and Differential Games: Theory and Numerical Methods. Annals of International Society of Dynamic Games, vol. 4, pp. 177–247. Birkhäuser, Basel (1999)

    Google Scholar 

  4. Chopp, D.: Computing minimal surfaces via level set curvature flow. J. Comput. Phys. 106, 77–91 (1993)

    Article  MATH  MathSciNet  Google Scholar 

  5. Chu, K.T., Prodanovic, M.: Level set method library (LSMLIB). [Online]. Available: http://www.princeton.edu/~ktchu/software/lsmlib/

  6. Crandall, M.G., Lions, P.-L.: Viscosity solutions of Hamilton-Jacobi equations. Trans. Am. Math. Soc. 277(1), 1–42 (1983)

    Article  MATH  MathSciNet  Google Scholar 

  7. Crandall, M.G., Lions, P.-L.: Two approximations of solutions of Hamilton-Jacobi equations. Math. Comput. 43(167), 1–19 (1984)

    Article  MATH  MathSciNet  Google Scholar 

  8. Crandall, M.G., Ishii, H., Lions, P.-L.: User’s guide to viscosity solutions of second order partial differential equations. Bull. Am. Math. Soc. 27(1), 1–67 (1992)

    Article  MATH  MathSciNet  Google Scholar 

  9. [Online]. Available: http://creativecommons.org

  10. Fedkiw, R., Aslam, T., Merriman, B., Osher, S.: A non-oscillatory Eulerian approach to interfaces in multimaterial flows (the ghost fluid method). J. Comput. Phys. 152, 457–492 (1999)

    Article  MATH  MathSciNet  Google Scholar 

  11. Jiang, G.-S., Peng, D.: Weighted ENO schemes for Hamilton-Jacobi equations. SIAM J. Sci. Comput. 21, 2126–2143 (2000)

    Article  MATH  MathSciNet  Google Scholar 

  12. J. Sci. Comput. 19 (1–3) (2003)

  13. Kao, C.-Y., Osher, S., Qian, J.: Lax-Friedrichs swee** schemes for static Hamilton-Jacobi equations. J. Comput. Phys. 196, 367–391 (2004)

    Article  MATH  MathSciNet  Google Scholar 

  14. Kloeden, P.E., Platen, E.: Numerical Solution of Stochastic Differential Equations, 3rd edn. Applications of Mathematics. Springer, New York (1999)

    Google Scholar 

  15. Kurzhanski, A.B., Mitchell, I.M., Varaiya, P.: Control synthesis for state constrained systems and obstacle problems. In: Proceedings of the IFAC Workshop on Nonlinear Control (NOLCOS). Vienna, Austria (2004)

    Google Scholar 

  16. Mallet, V.: Multivac C++ library. [Online]. Available: http://vivienmallet.net/fronts/index.php

  17. [Online]. Available: http://www.cs.ubc.ca/~mitchell/ToolboxLS

  18. Mitchell, I.M.: A toolbox of level set methods (version 1.1). Department of Computer Science, University of British Columbia, Vancouver, BC, Canada, Tech. Rep. TR-2007-11, June 2007. [Online]. Available: http://www.cs.ubc.ca/~mitchell/ToolboxLS/toolboxLS.pdf

  19. Mitchell, I.M., Templeton, J.A.: A toolbox of Hamilton-Jacobi solvers for analysis of nondeterministic continuous and hybrid systems. In: Morari, M., Thiele, L. (eds.) Hybrid Systems: Computation and Control. Lecture Notes in Computer Science, vol. 3414, pp. 480–494. Springer, New York (2005)

    Google Scholar 

  20. Mitchell, I., Tomlin, C.: Level set methods for computation in hybrid systems. In: Krogh, B., Lynch, N. (eds.) Hybrid Systems: Computation and Control. Lecture Notes in Computer Science, vol. 1790, pp. 310–323. Springer, New York (2000)

    Chapter  Google Scholar 

  21. Mitchell, I.M., Bayen, A.M., Tomlin, C.J.: A time-dependent Hamilton-Jacobi formulation of reachable sets for continuous dynamic games. IEEE Trans. Autom. Control 50(7), 947–957 (2005)

    Article  MathSciNet  Google Scholar 

  22. Oberman, A.: A convergent upwind difference scheme for motion of level sets by mean curvature. Numer. Math. 99(2), 365–379 (2004)

    Article  MATH  MathSciNet  Google Scholar 

  23. Oberman, A.: Convergent difference schemes for degenerate elliptic and parabolic equations: Hamilton-Jacobi equations and free boundary problems. SIAM J. Numer. Anal. 44(2), 879–895 (2006)

    Article  MATH  MathSciNet  Google Scholar 

  24. Øksendal, B.: Stochastic Differential Equations: An Introduction with Applications, 6th edn. Springer, New York (2003)

    Google Scholar 

  25. Osher, S.: A level set formulation for the solution of the Dirichlet problem for Hamilton-Jacobi equations. SIAM J. Math. Anal. 24(5), 1145–1152 (1993)

    Article  MATH  MathSciNet  Google Scholar 

  26. Osher, S., Fedkiw, R.: Level set methods: an overview and some recent results. J. Comput. Phys. 169, 463–502 (2001)

    Article  MATH  MathSciNet  Google Scholar 

  27. Osher, S., Fedkiw, R.: Level Set Methods and Dynamic Implicit Surfaces. Springer, New York (2002)

    Google Scholar 

  28. Osher, S., Paragios, N. (eds.): Geometric Level Set Methods in Imaging, Vision and Graphics. Springer, New York (2003)

    MATH  Google Scholar 

  29. Osher, S., Sethian, J.A.: Fronts propagating with curvature-dependent speed: algorithms based on Hamilton-Jacobi formulations. J. Comput. Phys. 79(1), 12–49 (1988)

    Article  MATH  MathSciNet  Google Scholar 

  30. Osher, S., Shu, C.-W.: High-order essentially nonoscillatory schemes for Hamilton-Jacobi equations. SIAM J. Numer. Anal. 28(4), 907–922 (1991)

    Article  MATH  MathSciNet  Google Scholar 

  31. Peng, D., Merriman, B., Osher, S., Zhao, H., Kang, M.: A PDE based fast local level set method. J. Comput. Phys. 165, 410–438 (1999)

    Article  MathSciNet  Google Scholar 

  32. Peyré, G.: Toolbox fast marching. [Online]. Available: http://www.mathworks.com/matlabcentral/fileexchange/loadFile.do?objectId=6110

  33. Russo, G., Smereka, P.: A remark on computing distance functions. J. Comput. Phys. 163, 51–67 (2000)

    Article  MATH  MathSciNet  Google Scholar 

  34. Sethian, J.A.: Level Set Methods and Fast Marching Methods. Cambridge University Press, New York (1999)

    MATH  Google Scholar 

  35. Sethian, J.A.: Evolution, implementation, and application of level set and fast marching methods for advancing fronts. J. Comput. Phys. 169, 503–555 (2001)

    Article  MATH  MathSciNet  Google Scholar 

  36. Shu, C.-W., Osher, S.: Efficient implementation of essentially non-oscillatory shock-capturing schemes. J. Comput. Phys. 77, 439–471 (1988)

    Article  MATH  MathSciNet  Google Scholar 

  37. Smereka, P.: Spiral crystal growth. Physica D 138, 282–301 (2000)

    Article  MATH  MathSciNet  Google Scholar 

  38. Spiteri, R.J., Ruuth, S.J.: A new class of optimal high-order strong-stability-preserving time discretization methods. SIAM J. Numer. Anal. 40(2), 469–491 (2002)

    Article  MATH  MathSciNet  Google Scholar 

  39. Sumengen, B.: A Matlab toolbox implementing level set methods. [Online]. Available: http://barissumengen.com/level_set_methods/index.html

  40. Sussman, M., Smereka, P., Osher, S.: An improved level set method for incompressible two-phase flow. J. Comput. Phys. 114, 145–159 (1994)

    Article  Google Scholar 

  41. Takei, R.: Modern theory of numerical methods for motion by mean curvature. Master’s thesis, Department of Mathematics, Simon Fraser University (August 2007)

  42. Zalesak, S.T.: Fully multidimensional flux-corrected transport algorithms for fluids. J. Comput. Phys. 31(3), 335–362 (1979)

    Article  MATH  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, University of British Columbia, 2366 Main Mall, Vancouver, BC, Canada, V6T 1Z4

    Ian M. Mitchell

Authors
  1. Ian M. Mitchell
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Ian M. Mitchell.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Mitchell, I.M. The Flexible, Extensible and Efficient Toolbox of Level Set Methods. J Sci Comput 35, 300–329 (2008). https://doi.org/10.1007/s10915-007-9174-4

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10915-007-9174-4

Keywords

Search

Navigation