Game Development Reference

In-Depth Information

cells different from the one that is queried. The disadvantage of the indirection is

obvious: per query, there may be one more cache miss. However, a hash query

visits only the particles of a single grid cell instead of a whole hash bucket. So,

the number of cache misses during traversal of the particle list—the last step in

the query algorithm—may be greatly reduced.

A more subtle disadvantage of the original spatial hash is that it requires extra

bookkeeping for finding all neighbors of a fluid particle. Multiple neighboring

grid cells are queried—27 for a grid cell size of
h
—and all of these neighboring

grid cells may map to the same hash bucket. For the original spatial hash structure,

it would be incorrect to traverse the same hash bucket more than once for multiple

neighboring grid cells; the fluid particles belonging to this hash bucket would be

included as neighbors multiple times. A guard has to be constructed to prevent

these superfluous hash bucket traversals. For the grid-cell-based hash, such a

guard is not required because a query only visits a single grid cell belonging to a

hash bucket. All neighboring grid cells of a fluid particle are distinct, so a single

grid cell is never visited twice, even if the same hash bucket is visited twice.

The performance of querying the grid-cell-based hash structure is of time

complexity
O
(
c
)+
O
(
g
),where
c
is the number of hash collisions in a hash bucket

and
g
is the number of fluid particles in a grid cell. The original hash structure

query complexity was of
O
(
q
), with
q
being the number of fluid particles in a hash

bucket. As
q
=
c

g
, the time complexity of a hash query has been improved in

the grid-cell-based spatial hash.

For testing performance of the grid-cell-based spatial hash in Section 6.7 on

an Intel Xeon W3520, we used an implementation with incremental construction,

using preallocated hash buckets and grid cells. Furthermore, this implementation

uses a grid cell size equal to
h
, with a fluid particle inserted into the hash just

once, as described in Section 6.4.1.

∗

6.5 Collapsing the SPH Algorithm

In Section 6.3, the basic algorithm for evaluation of the SPH equations was de-

scribed. The algorithm in its original form is inefficient in a number of ways.

These inefficiencies will be described in this section, along with a modified SPH

algorithm which eliminates the inefficiencies.

Looking back at the algorithm from Figure 6.1, we can see three dependencies

in the form of Step 1 to Step 3. This algorithm can be described by the pseudocode

in Algorithm 1.

It is clear that we iterate over all fluid particles thrice. If this algorithm

runs sequentially on a CPU, there is an increased chance of cache misses. In a