Game Development Reference
InDepth Information
2. A set of particles
EP
t
+Δ
t
0
→
1
that is in
C
0
at time
t
and will be in
G
1
→
0
at
time
t
+Δ
t
will not be included in
SP
t
+Δ
t
1
→
0
.
For the first proposition,because
SP
t
+Δ
t
1
→
0
is created by reading the grid at
time
t
,
SP
t
+Δ
t
1
m<x
i
≤
0
=
{
i

m
+
d
+
l
0
}
,
→
GP
1
→
0
=
m<x
i
≤
m
+
d, x
t−
Δ
t
>m
{
i

}
.
SP
t
+Δ
t
1
These equations lead to
GP
1
→
0
⊂
0
, which proves that ghost particles
at time
t
will be sent from the neighbor at time
t
+Δ
t
. Therefore, ghost particles
at time
t
have to be deleted before the processor receives the particles coming
from adjacent subdomains.
For the second proposition,
→
EP
t
+Δ
t
0
→
1
d<x
i
≤
m, m < x
t
+Δ
t
=
{
i

m
−
}
,
and
SP
t
+Δ
t
1
m<x
i
≤
0
=
{
i

m
+
d
+
l
0
}
.
→
These equations lead to
EP
t
+Δ
t
0
→
1
SP
t
+Δ
t
1
→
0
. Thus, particles in a ghost region at
time
t
+Δ
t
should not be deleted. We can also see that the particles coming from
a neighbor have no duplication of particles in its subdomain. So the received data
can just be added at the end of the particles of the processor.
If a grid is used to select the particles to be sent, there are several voxels that
are not fully saturated to the maximum capacity of a voxel. If sent data kept being
added, invalid entries would accumulate. To prevent this, the array is compacted
by using a prefix sum after receiving neighbors.
∈
/
7.4 Choosing an Acceleration Structure
So far, we have discussed how to manage the data on multiple processors. As
neighboringparticle search is expensive, acceleration data structures have to be
introduced. In this section, we first discuss the requirements for a particlebased
simulation and then present the sliced grid, which we used for our simulation. It
not only has several advantages as an acceleration structure, but is also well suited
for parallelized particlebased simulation using domain decomposition.