Game Development Reference

In-Depth Information

task depends heavily on the purpose of the simulation and the target platform of

the implementation.

This chapter does not focus on the visualization of the metaballs. We will

solely focus on the SPH simulation—the algorithms forming the basis of SPH

and their implementation. Also, we will not focus on an implementation specific

to a particular target platform, as the current emergence of parallel architectures

in their multitudinous embodiments advances at a pace that swiftly depreciates

any such dedicated implementation effort. Instead, in this chapter we discuss

an efficient representation of the SPH equations, followed by an optimization

suitable for any target platform. As do many real-time applications, our version of

the SPH equations trades in accuracy for performance. Therefore, we also discuss

differences in stability and behavior compared to the standard implementation

from [Muller et al. 03]. Additionally, we discuss an optimization to the data

structure used for evaluation of the SPH equations, along with its performance

compared to the original method.

Section 6.2 gives an overview of the basic SPH equations, followed by a de-

scription of the basic algorithm used to evaluate these equations in Section 6.3.

Section 6.4.1 discusses the choice of data structure used to accelerate the eval-

uation of the SPH equations, followed by an optimization of the chosen data

structure in Section 6.4.2. Section 6.5 introduces an optimization for the SPH

algorithm. We evaluate the stability and behavior of the optimized SPH algorithm

in Section 6.6 and test the performance of the original and optimized algorithm

and data structure in Section 6.7.

6.2 The SPH Equations

In this section, we will briefly describe the SPH model, to establish the definitions

and highlight the choices specific to our implementation. We define a set of fluid

particles

, with positions
x
i
, velocities
v
i
, accelerations
a
i
,and

masses
m
i
constant over time. Also, every particle has a density
ρ
i
, which is the

fluid density at
x
i
. SPH consists of a set of equations that ultimately define a force

f
i
applied to every particle
i
. The positions and velocities of the fluid particles at

any time
t
can be determined by integration of
f
i
using an integration scheme,

such as the semi-implicit Euler method [Vesely 01].

In general, every particle attribute can be seen as a quantity
A
defined at the

particle positions. The SPH model, as mentioned in Monaghan's original pa-

per [Monaghan 88], states a general equation that can be applied to interpolate

any such quantity
A
at an arbitrary location
x
from the values of
A
at all particle

{

i
:1

≤

i

≤

n

}