Game Development Reference

In-Depth Information

Subsequent passes then only have to evaluate particles that are actual neighbors

instead of evaluating all potential neighbors. However, constructing such a neigh-

bor list costs time, and in parallel execution environments it becomes non-trivial

to manage query access patterns of the neighbor list on the different execution

units. While efficiency of a neighbor list for parallel execution is shown to be

good by [Hjelte 06], the effect of using a neighbor list on the overall performance

of the algorithm is difficult to estimate and tune.

Instead, it is an interesting idea to forgo the complexity of multiple passes

and neighbor lists by collapsing the three passes into one, possibly at the cost of

simulation accuracy. Naively collapsing the three passes gives the algorithm in

Algorithm 2.

Algorithm 2
SPH algorithm with the three passes collapsed.

{
[
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
]
?
and
m
j
;

accumulate
[
f
i
]
0
using
[
x
j
]
?
,
[
v
j
]
?
,
[
ρ
j
]
?
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;

This algorithm is not complete. It is not clear what the state of
x
j
is for

every particle
j
during accumulation of [
ρ
i
]
0
, and the same problem presents itself

during accumulation of [
f
i
]
0
. The problem is caused by a partially updated state

of neighbor particles when a certain particle
i
is being updated, as some neighbor

particles may already have updated their state to time step
t
1
—in particular, those

with indices
j
:
j<i
. One solution is to simply use the state at
t
1
for those

particles, but in that case, the state of the particle positions may be inconsistent

with the state of the spatial hash, unless we decide to update the spatial hash in

between particle updates as well. This may not be such a problem for sequential