Closest Point Transform

Introduction

This code implements an algorithm for computing the closest point transform to a triangle mesh surface on a regular 3-D grid. The closest point transform finds the Euclidean distance to the triangle mesh. In addition, it can compute the closest point on the surface, the closest triangle face in the mesh and the gradient of the distance. The distance, etc., are computed to within a specified distance of the surface. The closest point, closest face, distance and gradient of the distance to the mesh surface are calculated by solving the Eikonal equation with the method of characteristics. The method of characteristics is implemented efficiently with the aid of computational geometry and polyhedron scan conversion. The computed distance is accurate to within machine precision. The computational complexity of the algorithm is linear in both the number of grid points for which the distance is computed and the size of the mesh. Thus for many problems, it has the optimal computational complexity. Visit http://www.its.caltech.edu/~sean/ for publications on solving static Hamilton-Jacobi equations and in particular for computing the CPT.

The Standard Interface

The classes State<3,T> and State<2,T> contain the standard interface (C++ interface) to the CPT package. If you use the standard interface, there is no library to build. Just include cpt.h to get the templated class library.

To use the standard interface, instantiate a State<3,T> or State<2,T> class. Its member functions provide the interface. Consult the class for this documentation.

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

The C and Fortran Interfaces

There is a C interface and a fortran interface contained in the headers: cpt_c.h and cpt_f.h, respectively. These interfaces are free functions that are analogous to the member functions of the C++ interface.

The C interface is not in the cpt namespace. Instead the functions have a cpt_ prefix. For example: cpt_closest_point_transform_3(). The C interface wraps the standard interface. Functions in the fortran interface have a cpt_ prefix and a _f suffix. For example: cpt_closest_point_transform_3_f(). The fortran interface wraps the C interface.

Both the C and fortran interfaces instantiate a static instance of State<3,T> and State<2,T>. Thus you must make and link with the library. Use gnu "make" to build the cpt.a archive.

The Drivers

cpt_driver2 and cpt_driver3 are example applications that use the CPT package. They read a b-rep from a file and write the distance, the gradient of the distance, the closest point and the closest face transforms to files.