Game Development Reference
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