Game Development Reference

In-Depth Information

Algorithm 1
SPH algorithm in pseudocode.

[
x
i
]
0
:1

[
v
i
]
0
:1

{{

{

≤

i

≤

n

}

and

{

≤

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
;

end
;

end
;

for al l
particles
i

begin

query spatial hash at
[
x
i
]
0
;

for al l
nearby particles
j
from query

begin

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

end
;

end
;

for al l
particles
i

begin

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
;

parallel environment, we would need to run three parallel passes: one for the den-

sity update, one for the force update, and one for position integration. Usually

this requires sending data like the particle positions, densities and forces to the

parallel execution units multiple times, decreasing the effective bandwidth of the

system.

Also, the density and force update passes require iterating over all nearby

particles—potential neighbors—of the particle that is updated. So, the search for

actual neighbors is performed twice. A neighbor list can be used for every particle

to alleviate the loss of efficiency caused by performing all distance comparisons

twice. The neighbor list keeps the actual neighbor particles determined during

the first neighbor search in step 1, where the particle densities are determined.