Three-dimensional boundary detection for particle methods

The three-dimensional exposure method for the detection of the boundary of a set of overlapping spheres is presented. Like the two-dimensional version described in a previous paper, the three-dimensional algorithm precisely detects void opening or closure, and is optimally suited to the kernel-mediated interactions of smoothed-particle hydrodynamics, although it may be used in any application involving sets of overlapping spheres. The principle idea is to apply the two-dimensional method, on the surface of each candidate boundary sphere, to the circles of intersection with neighboring spheres. As the algorithm finds the exact solution, the quality of detection is independent of particle configuration, in contrast to gradient-based techniques. The observed CPU execution times scale as O(MNϵ), where M is the number of particles, N is the average number of neighbors of a particle, and ϵ is a problem-dependent constant between 1.6 and 1.7. The time required per particle is comparable to the amount of time required to evaluate a three-dimensional linear moving-least-squares interpolant at a single point.