Game Development Reference
In-Depth 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
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
neighboring-particle search is expensive, acceleration data structures have to be
introduced. In this section, we first discuss the requirements for a particle-based
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 particle-based simulation using domain decomposition.