Game Development Reference
InDepth Information
O
(
c
), with
c
being the number of hash collisions in a hash bucket. However,
the number of collisions should always be very small because it is possible to
optimize for a limited number of collisions by increasing the number of hash
buckets.
To find all neighbors of a fluid particle, we calculate its grid cell and neigh
boring grid cells. We can then query the hash structure for every one of these grid
cells. Querying is performed as follows:
•
Calculate the hash bucket the grid cell maps to using its grid cell coordi
nates. The grid cell coordinates are equal to
D
(
x
) for all positions
x
within
the grid cell.
•
Iterate through the hash bucket's list of grid cells.

If a grid cell that matches the queried grid cell coordinates is found,
search its list of fluid particles to find potential neighbors.

If no matching grid cell is found, the query for this grid cell is termi
nated.
It is possible to construct a gridcellbased spatial hash from scratch as well as
incrementally. To construct from scratch, a contiguous block of particles is sorted
based on grid cell coordinates to obtain lists of particles per grid cell, contiguous
in memory. From the sorted list of particles, a list of grid cells is extracted. The
list of grid cells is sorted based on hash index to obtain lists of grid cells per hash
bucket, also contiguous in memory. Based on the sorted list of grid cells, the hash
bucket references are constructed.
For incremental construction, particles are relocated between grid cells as they
change position, while grid cells are added and removed from the lists of grid cells
per hash bucket as particles are added and removed from the grid cells. The lists of
grid cells per hash bucket and the lists of particles per grid cell can be preallocated,
based on the maximum number of grid cell collisions per hash bucket
c
and the
maximum number of particles per grid cell
g
, respectively. This allows lists of
particles per grid cell as well as lists of grid cells per hash bucket to be contiguous
in memory.
Regardless of the method of construction, the gridcellbased spatial hash
structure contains three contiguous lists instead of two: the hash table, a list of
grid cells sorted by hash bucket, and a list of fluid particles sorted by grid cell
coordinates.
Compared to the original spatial hash structure, one more indirection has been
added for querying; instead of immediately iterating through potential neighbors
in a hash bucket, we implicitly filter out the potential neighbors belonging to grid