N-D Static Hamilton-Jacobi Solver

Introduction

This package contains classes for solving static Hamilton-Jacobi equations. There is an interface in hj.h that allows you to solve some common problems with simple function calls.

Interface for Common Problems

Functions

The interface in hj.h provides functions for computing signed and unsigned distance. All functions are in the hj namespace.

hj::initialize()
hj::unsignedDistance()
hj::signedDistance()
hj::floodFillUnsignedDistance()
hj::floodFillSignedDistance()
hj::levelSetToSignedDistance()
hj::constantAdvection()

There are also wrapper functions which take a pointer to the array data as an argument.

Compiling

There is no library, just header files. Thus, to compile your application, include the file hj.h in your source.

The H-J package requires my algorithms and data structures (ADS) package. The ADS package is a templated class library. Place the ADS package in a convenient directory and include the relevant directory in your makefile by using the -I compiler flag.

I have compiled the library using g++ (GCC) 3.4.3. If you use a different compiler or version, the code may need modification.

Examples

There are examples of using the interface functions in the test directory.

Classes for Solving Hamilton-Jacobi Equations in N-D

Solution Methods

The package provides two marching methods for solving static Hamilton-Jacobi equations. Sethian's fast marching method is implemented in the hj::GridFM class. The marching with a correctness criterion algorithm is implemented in hj::GridMCC. In addition, there is a method which schedules the labeling operations using a breadth first search. This does not produce the correct solution, but gives a lower bound on the execution time of an ideal method. This is implemented in hj::GridBFS.

Equations

Currently, one can solve either the homogeneous eikonal equation: $| \nabla u | = 1$ or the inhomogeneous eikonal equation: $| \nabla u | f = 1$ . Here $ f $ is the speed function, which is specified on the computational grid. The solution of the former equation, $| \nabla u | = 1$ , with the boundary condition $ u|_S = 0 $ is the unsigned distance from the manifold $ S $ . This equation is implemented in hj::Distance and the classes that derive from it.

For the problem: $| \nabla u | f = 1$ , $ u|_S = 0 $ , the solution is the arrival time of a wave propagating with speed $ f $ and starting at the manifold $ S $ . This equation is implemented in hj::Eikonal and the classes that derive from it.

One can add other equations by providing the functionality in either of the above classes.

Drivers

The performance directory has drivers which show how to use the solvers. Compile the executables with "make". There are programs (for 2-D and 3-D) which measure the execution time of any of the three methods (fast marching, marching with a correctness criterion or placebo) with either the homogeneous or inhomogeneous eikonal equation. There are also programs (for 2-D and 3-D) which measure the error in solving the homogeneous eikonal equation to compute distance.