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)
View All     RSS
October 19, 2019
arrowPress Releases
October 19, 2019
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 3 of 5 Next
 

Hybrid Schemes

Eulerian approaches can suffer from instability because of the advection term (as explained below). One way to avoid the instability is to ask, for each grid point at each time step, from where did the flow arrive? This "backtracking" is called a semi-Lagrangian technique, because it treats advection similarly to particle-based methods.

Conversely, discrete vortex methods require either expensive or complicated algorithms (described above) to compute velocity. Instead of using the Biot-Savart law, you can transfer vorticity from particles to a grid and solve a vector Poisson equation to recover the velocity field. (Poisson solvers are readily available.) These so-called particle-in-cell (PIC) or vortex-in-cell (VIC) techniques also simplify computing spatial derivatives (discussed below). Meanwhile, the basis of the simulation remains in vortons, which do not diffuse, so VIC methods give you the relative simplicity of a grid-based method and the lack of diffusion of a particle method.

Numerical Methods

Numerical methods used in fluid simulation include interpolating values between nodes, approximating spatial derivatives, solving differential equations to evolve flow through time, and satisfying boundary conditions.

Interpolation

You need to be able to determine values at locations other than nodes where the simulation explicitly represents them. You do so using interpolants, also called basis functions, which pass through nodes.

You can choose among a variety of interpolating functions, from local to global. Piecewise line segments provide linear interpolation between adjacent gridpoints (Figure 6a). Instead of using only the immediately adjacent points, you can also use a broader neighborhood of gridpoints and a higher-order interpolant such as a piecewise cubic spline (Figure 6b). Taking that line of thought to its logical conclusion, you can use a much higher-order function to create a spline that spans the entire domain (Figure 6c).


Figure 6: Interpolation on a grid. (a) Linear. (b) Cubic. (c) Global.

Particle simulations can track nearest-neighbors (as a portion of Figure 3b shows) and use interpolation techniques specialized for irregular data. Spatial partitions such as octrees and kd-trees organize particles that reside in the same physical neighborhood to also reside in the same data neighborhood. You can then search the resulting tree for the nearest neighbors of a given location.

Alternatively, you could use a hybrid PIC approach; use particles to represent fluid properties, transfer values from particles to a grid, and use grid-based techniques to interpolate those properties in the regions between particles.

Spatial Derivatives

The equations governing fluid motion include terms involving spatial derivatives, so you need to compute those. The techniques to approximate spatial derivatives relate directly to the interpolation techniques.

Finite difference (FD) methods use differences of quantities from adjacent locations divided by their separation (as shown in Figure 7). Because they use only local information, FD methods readily handle arbitrary, changing boundaries (for example, moving bodies in the fluid) but have low accuracy compared to other techniques. FD is simple, flexible, and effective and so is a good choice for video games, where accuracy is not paramount.


Figure 7: Finite differences. (a) Forward, (b) backward, and (c) centered.

Spectral methods use interpolating functions spanning multiple values in the domain, and you can compute derivatives of those functions analytically. Spectral methods offer higher accuracy but because they use global (or less local) information, the domain shape and boundary conditions impose constraints that determine which functions work well to represent the flow field.

Spectral methods come in two varieties: collocation and Galerkin. Collocation techniques use values arranged in a spatial domain, as depicted above. Galerkin methods use an abstract domain, analogous to the frequency domain for audio signals. Hybrid collocation-Galerkin methods also exist.

These techniques to approximate spatial derivatives equip you with the ability to compute each term in the governing equations.

By replacing derivatives in the continuous equations with approximation, you convert the continuous equations with a discretized form. When using FDs, this means the continuous PDE's change into a system of linear algebraic equations. For example, replacing the gradient with a centered difference, the continuous equation

becomes the spatially discrete equation

After plugging approximated spatial derivative values into the original fluid dynamics equations we must also discretize those equations in time to create an algorithm to update the simulation for each new step in time.


Article Start Previous Page 3 of 5 Next

Related Jobs

Bit Fry Game Studios, Inc.
Bit Fry Game Studios, Inc. — Portsmouth, New Hampshire, United States
[10.19.19]

Gameplay Engineer
Bit Fry Game Studios, Inc.
Bit Fry Game Studios, Inc. — Portsmouth, New Hampshire, United States
[10.19.19]

Game Network Engineer
Bit Fry Game Studios, Inc.
Bit Fry Game Studios, Inc. — Portsmouth, New Hampshire, United States
[10.19.19]

Backend Engineer
Bit Fry Game Studios, Inc.
Bit Fry Game Studios, Inc. — Portsmouth, New Hampshire, United States
[10.19.19]

Game Client Engineer





Loading Comments

loader image