Game Development Reference

In-Depth Information

implementations, but for parallel implementations, the use of particle states at
t
1

is more problematic. The main culprit is the synchronization of particle states that

are updated, with particle states being read for density and force accumulations.

This sort of dependency has been proven to be inefficient even for much simpler

cases [Green 08].

Instead, we simply use the “old” state at
t
0
for
x
i
and
v
i
and use
t
−
1
for

ρ
j
,as[
ρ
j
]
0
is not yet determined when positions are updated to time step
t
0
.

The algorithm now has an easy and efficient implementation for both sequential-

and parallel-execution environments, at the expense of some accuracy. The full

collapsed SPH algorithm
is presented in Algorithm 3.

Algorithm 3
Full collapsed SPH algorithm.

{
[
x
i
]
0
:1
≤ i ≤ n}
,
{
[
v
i
]
0
:1
≤ i ≤ n}
and
{
[
ρ
i
]
−
1
:1
≤ i ≤ n}
are known

{{

}}

begin

construct spatial hash structure using
{
[
x
i
]
0
:1
≤ i ≤ n}
;

for al l
particles
i

begin

query spatial hash at
[
x
i
]
0
;

for al l
nearby particles
j
from query

begin

accumulate
[
ρ
i
]
0
using
[
x
j
]
0
and
m
j
;

accumulate
[
f
i
]
0
using
[
x
j
]
0
,
[
v
j
]
0
,
[
ρ
j
]
−
1
and
m
j
;

end;

calculate
[
a
i
]
0
using
[
f
i
]
0
and
m
i
;

integrate
[
v
i
]
1
using
[
a
i
]
0
;

integrate
[
x
i
]
1
using
[
v
i
]
1
;

end;

end;

Note that this algorithm is almost the same as the original algorithm, apart

from using the density at
t
−
1
instead of at
t
0
for calculating the force at
t
1
.Using

a sufficiently small time step, [
ρ
j
]
0

[
ρ
j
]
−
1
should be small, so the resulting

difference in fluid behavior should be small as well. As an aside, we might try to

estimate [
ρ
j
]
0
based on [
ρ
j
]
−
1
and a time derivative of
ρ
,asdefinedby

−

n

dρ
i

dt

=

m
j
(
v
i
−

v
j
)

∇

W
(
x
i
−

x
j
,h
)
.

j
=1

We choose not to perform this estimation because it relies on estimating a

change in the smoothing kernel based on a first-order derivative, which can lead