Implicit Closest Point Transform

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.