The Closest Point Method

Unit normal flow on a hand

The Closest Point Method is a new technique for computing on surfaces. For example, the Closest Point Method could be used to compute a numerical solution of a partial differential equation on the surface of a sphere, torus, Möbius strip, or human hand. The animation on the right shows the motion of an interface (shown as the transition from between black and white) on the surface of Laurent's Hand. The interface is moving normal to itself (so-called unit normal flow) and is an example of the level set method applied on a surface.

Level set equations on surfaces via the Closest Point Method

Unit
normal flow on a torus

Torus

Unit normal flow on the surface of a torus (left). The interface (shown here as the black contour on the transition from blue to red) starts at the left and moves rightward by unit normal flow, separates into two interfaces in the middle, and finally rejoins into a single interface at the right.

See the animated torus (also in mpeg format)

Triangulated surfaces

The Closest Point Method can also be used on triangulated surfaces such as those available from AIM@SHAPE.

See the full-size version of the Laurent's Hand movie (mpeg) and from a different angle (mpeg).

Klein bottle

Klein bottle

Redistancing (computing a signed distance function) on the surface of the Klein bottle (right). Each transition from dark-to-light or light-to-dark represents contours of equal distance from the closer of the two initial interfaces indicated with dashed blue lines.

See the animated Klein bottle (mpeg).

The Klein bottle is a codimension-two surface in 4D with no inside/outside; the Closest Point Method is extremely flexible with respect to surface geometry.

Computations using the Closest Point Method are performed using standard finite difference schemes on a regular Cartesian grid enveloping the surface in a tight band of grid points. For more details, download the paper:


Forest Fires: level sets on surfaces

Forest fire

Simulated forest fire on a hill: mountain_slope3.mpg. The flame front is represented by the zero contour of a level set function. The model (which is not necessarily physically realistic) specifies that the flame front wants to spread outwards in the in-surface normal direction and also spreads faster in the uphill direction. The numerical computation is performed in Matlab using Ian Mitchell’s Toolbox of Level Set Methods.

This computation was motivated by work during the 2007 MITACS Industrial Math Summer School with Helen Alexander, Anna Belkine, Chris Poss, and Weining Wang.


The Implicit Closest Point Method

Hands

Blurring with the heat equation

Solving the heat equation blurs the phone number written on Laurent's hand. The images on the right show the initial conditions and the progressively blurrier results after 1, 2 and 6 time steps. For this problem, implicit time stepping allows relatively large time steps compared to explicit methods.

Flexible computational domains

Pig, wire and sphere Temperature on pig

The tail of Annie Hui’s pig is connected to a sphere by a long filament (infinitesimally thin wire). A heat source is then applied under the sphere. The temperature over the entire surface of the domain is modelled according to the heat equation with a localized source term (using Newton’s law of heating and cooling) to account for the candle.

The temperature is initially zero, the candle has temperature 10, and this animation (mpeg) shows the change in heat until t=25. The figure on the right shows the temperature on the surface of the pig at this final time.

This surface is comprised of components of various codimension (the pig and sphere are codimension 1 whereas the filament is codimension 2). This poses no difficulty for the Closest Point Method and the computation proceeds exactly as it would for a simpler surface.

The “Bunnyator” or the “Brusselhare”

Patterns on bunnies

Solutions of the Brusselator reaction-diffusion system on the surface of Stanford Bunny can exhibit various pattern formation behavior. For different values of the parameters, the image on the right shows honeycomb, stripes and spots on the bunny surface. An animation (mpeg) shows the solution evolving in time.

Biharmonic problems

Solving in-surface biharmonic (fourth-order) problems is a one-line change in the code: we simply square the matrix used for the Laplace--Beltrami operator.

The image on the left shows the evolution of a fourth-order interface motion problem on a bumpy sphere. This example uses an innovative semi-implicit splitting by Peter Smereka.


Image segmentation

Segmentation on pig Segmentation on a cube

Luke Tian's MSc thesis applied the Closest Point Method to the problem of image segmentation. Luke used the Chan-Vese segmentation algorithm—adapted to surfaces using the Closest Point Method—to detect objects in the textures of surfaces.

The figures on the left and right (both made by Luke) demonstrate the results: in each case a contour evolves, eventually separating the surface into two distinct regions. In the case of the pig, into red and blue.

The article Segmentation on surfaces with the Closest Point Method (Luke Tian, Colin Macdonald and Steve Ruuth) has been submitted for publication.


Eigenafrica

Eigenvalue problems

Eigenafrica

The Closest Point Method can be used to solve surface eigenvalue problems. The images on the left show some Laplace--Beltrami eigenmodes of a Mobius strip. These can be thought of as vibration patterns of a stylized Mobius-shaped drum.

The figure on the right shows the first nine eigenmodes of continental Africa. The computation is performed using an Africa-shaped piece of a sphere using the Closest Point Method. Dirichlet boundary conditions are applied along the coast line.

The results modes can be compared to the well-known problem of eigenmodes of a L-shaped domain. Interesting to note that they are fairly similar.


Underlying Mathematics

A pringle-shaped curve

Tom März has looked at the underlying mathematics of the method and presented proofs of the principles needed for the Closest Point Method.

Boundary conditions

For open surfaces, boundary conditions can be dealt with in a intuitive way. This also allows coupling between surface and bulk equations.


Literature on the Closest Point Method

(BibTeX entries can be found in my bibliography.)

Other Closest Point Method resources

bunny icon mobius icon

Steve Ruuth’s website has other Closest Point Method pictures and animations.


Part of Colin Macdonald’s website.