Abstract
Solving the N-body problem, i.e.\ the Poisson problem with point sources,
is a common task in graphics and simulation. The naive direct summation
of the kernel function over all particles scales quadratically, rendering
it too slow for large problems, while the optimal Fast Multipole Method has
drastic implementation complexity and can sometimes carry too high an overhead
to be practical. We present a new Particle-Particle Particle-Mesh (PPPM)
algorithm which is fast, accurate, and easy to implement even in parallel on
a GPU. We capture long-range interactions with a fast multigrid solver on a
background grid with a novel boundary condition, while short-range interactions
are calculated directly with a new error compensation to avoid error from the
background grid. We demonstrate the power of PPPM with a new vortex particle
smoke solver, which features a vortex segment-approach to the stretching term,
potential flow to enforce no-stick solid boundaries on arbitrary moving solid
boundaries, and a new mechanism for vortex shedding from boundary layers.
Comparison against a simpler Vortex-in-Cell approach shows PPPM can produce
significantly more detailed results with less computation. In addition, we use
our PPPM solver for a Poisson surface reconstruction problem to show its potential
as a general-purpose Poisson solver.
|