Gamasutra is part of the Informa Tech Division of Informa PLC

This site is operated by a business or businesses owned by Informa PLC and all copyright resides with them. Informa PLC's registered office is 5 Howick Place, London SW1P 1WG. Registered in England and Wales. Number 8860726.

Gamasutra: The Art & Business of Making Gamesspacer
Sponsored Feature: Fluid Simulation for Video Games (Part 2)
arrowPress Releases
July 28, 2021
Games Press
View All     RSS

If you enjoy reading this site, you might also want to check out these UBM Tech sites:


Sponsored Feature: Fluid Simulation for Video Games (Part 2)

October 28, 2009 Article Start Previous Page 2 of 5 Next

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(N2) 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.

Article Start Previous Page 2 of 5 Next

Related Jobs

Sucker Punch Productions
Sucker Punch Productions — Bellevue, Washington, United States

AI Systems Designer
Xbox Graphics
Xbox Graphics — Redmond, Washington, United States

Senior Software Engineer: Performance Tooling
Xbox Graphics
Xbox Graphics — Redmond, Washington, United States

Senior Software Engineer: GPU Compilers
Insomniac Games
Insomniac Games — Burbank, California, United States

Senior Hard Surface Outsource Artist

Loading Comments

loader image