## Mesh-free Discretizations

In contrast to grid-based discretizations, mesh-free
discretizations are useful for Lagrangian views -- that is, tracking the behavior
of particles as they move with the flow. These particles can represent fluid
properties such as position, density, velocity, and vorticity. Those properties
never diffuse (unless you tell them to). Furthermore, the simulation can place
more particles only where the flow requires higher resolution, so the
simulation can (in principle) be more efficient.

Fluid particle simulations come in two major varieties: SPH and the
discrete vortex method (DVM). SPH simulations use "fluid particles" to
represent a flow field. Although it is tempting to think of these fluid
particles as particles of fluid material, it is perhaps better to think of them
as mobile clouds that move and carry fluid property information with them. The
distinction is subtle but important. In mesh-free simulations, finding the
value of a fluid property at any given location requires interpolating values
between particles. Each particle represents a "source" in a smoothed, localized
field. Figure 3a shows an example of a smoothing function that "spreads" the
influence of a particle across a small region. The field could be any fluid
property, such as density, temperature, or velocity. In order to find the value
of the field at a given location, you include contributions to that field due
to all particles in the vicinity of that location. Usually, several particles
contribute to the field at each location. So, you would need to interpolate
between particles, as shown in Figure 3b.

**Figure 3: Smoothed
particle discretization. (a) Smoothing function. (b) Several smoothed particles
representing a field. Lines connect particles that would be used to interpolate
the field in that region.
**

DVM simulations use vortex particles called vortons to represent tiny vortex
elements, which represent swirling regions. Each of these particles induces a
velocity field that circulates around the vorton, as shown in Figure 4. This
induced velocity field extends outward to large distances. So, each vorton influences
the motion of all other vortons in the fluid.

**Figure 4: Vortex
particles (vortons) and the velocity fields they induce. (a) Counter-rotating
vortex pairs push each other along a line. (b) Co-rotating vortex pairs orbit
each other. (c) Four or more vortices move each other chaotically.
**

The recipe for evolving a mesh-free fluid simulation has the same
structure as in grid-based simulations, plus one extra step: advection. The
first article in this series explained advection; each particle needs to move
(following the flow) in addition to having its properties updated. The "update"
step resembles the same step as in grid-based simulations; but the advection
step differs substantially.

You might wonder why the grid-based simulations lack this
need for advection. Given that the fluid equations are the same in both views
(Eulerian and Lagrangian), the effects of advection should exist in both. So,
why is there no advection step in a grid-based simulation? The answer is that
grid-based simulations still include the advection term, but its effects
influence the properties of stationary gridpoints. In grid-based simulations,
each grid point feels the effects of advection in much the same way a
stationary thermometer would feel temperature change as water flows past it. In
contrast, in a mesh-free particle simulation, you would imagine such
thermometers as attached to buoys free to move with the fluid. Advection exists
in both cases, but (as mentioned in the first article) the treatment of the
advection term boils down to whether you keep it on the right or left side of
the fluid equations: The right side is Eulerian (grid based), and the left side
is Lagrangian (particle based).

Computing advection in a vortex simulation requires special
treatment, because the vorticity equation does not directly *provide* velocity but via the advection
term directly *requires* velocity. (In
contrast, the momentum equation both provides and requires velocity.) Computing
advection in a vortex-based simulation therefore requires obtaining velocity
from vorticity. The Biot-Savart law relates the vorticity of a vortex element at a displacement to a point with velocity :

DVM simulations use this law to advect each vorton because of the
influence of all other vortons.

Instead of representing vortices as particles, you could
represent them as filaments. In practice, the simulation would still track the
positions of vortex particles but would also remember their connectivity -- namely,
that each particle connects to two adjacent particles. Then, computing the
induced velocity field would involve evaluating the Biot-Savart law along the
curves connecting adjacent particles. This technique provides the benefit that,
to a rough approximation, it automatically takes into account vortex
stretching, therefore alleviating the need to compute that term using spatial
derivatives.

If the simulation has N vortons, a straightforward advection computation would
take O(N^{2})
operations, which is too slow. So instead, you can approximate the influence of
clusters of multiple distance vortices as a single vortex. As long as those
clusters are far enough away, this approximation works well enough for visual
effects. Figure 5 shows ways in which you can represent vortex clusters using
hierarchical data structures (for example, trees). The bottom row of nodes
represents actual vortons. In the layer above that, each node represents
clusters of vortons, and the layer above that represents clusters of clusters, and
so on. To compute the velocity at a query location, traverse the tree from top
down, as Figure 5b shows: Visit each node and ask whether the query location
(heavy oval) is inside the region that node represents. If not, apply the
influence of that cluster (shaded regions) as though it were a single vorton. If
the query location lies within the cluster region, then descend that branch
(following the arrows) and repeat.

**Figure 5: Vorton
cluster tree. (a) Each ancestor node represents its descendents as a single
vorton. (b) Traversal for finding clusters influencing the marked vorton.
**

In principle, vorton simulations can focus computational
resources on areas of flow with the most interesting motion: regions with
vorticity. Because it does not numerically diffuse vorticity, the technique
works for low-viscosity flows -- for example, smoke from a fire -- where you want to
retain fine-scale swirly motion over long durations. But the long-range
advection interaction is either slow or complicated; there are no trivial, fast
solutions.

You can combine elements of grid-based and particle-based
simulations to get the best of both.