# Implicit Closest Point Transform

The Characteristic / Oct Tree Method

## The Problem

My group's research goal is to solve external flow problems over complicated
surfaces with vortex particle methods. One problem we face in trying to
solve such problems is that we have lots of vortex particles flying all
around (millions, literally), and at every point in time we need to know
where each particle is relative to the boundary. Is it inside? Outside?
How far away? And what is the closest point on the surface to it? In our
case, the boundary is usually the surface of a truck--not a simple shape!

Unfortunately, the usual ways to determine where a point is relative to a
surface aren't satisfactory here. The easy approach--loop over every
surface element for every particle--scales with the square of the problem
size, which is far too slow. Fast approaches generally need the particles
to be on a regular grid (they're not) or at least have all positions known
ahead of time (again, no such luck).

What I did here was to modify a very clever strategy by Sean Mauch so that
it is not constrained to problems on a regular grid. Mauch's strategy was
based on the observation that characteristic lines of a certain Eikonal
problem measure distance away from a surface quite naturally. For each
surface element, he finds a volume containing the family of characteristics
emanating from that element, and then uses scan conversion to select a small
set of grid points which lie inside that volume.

Our particles are not on a grid, so I replaced the scan conversion step with
an octree. Details are in the submitted paper.

## Paper: Octree Algorithms for the Implicit Closest Point Transform

M. Rubel. Submitted 6/2003.

### Abstract

Two new algorithms which find the Implicit Closest Point Transform are
presented. Given a 2-D polygonal surface in 3-D space and a test point,
both algorithms identify the location on the surface which is closest to the
test point. Both algorithms give results which are exact to machine
precision, and can operate efficiently without requiring that the points lie
on a regular lattice or belong to a set whose positions are known in advance.
Operating time per test point is constant in both cases; the algorithms
differ in their initial setup times and memory consumptions.

### Preprints

Please contact me by email for preprint.