Game Development Reference

In-Depth Information

preallocated based on a maximum number of particles per hash bucket. The dis-

advantage is that the size of a hash bucket can never exceed the maximum num-

ber of particles estimated during preallocation. For architectures without a cache,

contiguity of hash buckets is not necessary, so a hash bucket can alternatively be

represented in a linked-list fashion, where each particle references the previous

and next particle of the hash bucket it belongs to. Each particle then updates only

these references as it moves around within the fluid simulation, but it does not

change its location within the list of particles constituting the spatial hash. This

way, restrictions on hash bucket size are avoided. In either case, the incremental

solution modifies an existing spatial hash, which makes it less suitable for parallel

implementations.

Regardless of the method of construction, the spatial hash structure can be

utilized in two different ways. One way is to insert a fluid particle during the con-

struction phase in all the hash buckets that its area of influence maps to and—to

find all neighbors of a particle during the query phase—query just the hash bucket

that a fluid particle position maps to. The second way is to insert the fluid particle

into one hash bucket and query all hash buckets of grid cells intersecting the area

of influence of a particle during the neighbor search. The two methods do not

differ much in terms of complexity: the first method has
c
insert operations and

one query operation per particle, where
c
is the number of grid cells intersecting

an area of influence defined by the smoothing radius
h
, and the second method

has one insert operation and
c
query operations per particle.

Still, there are at least three reasons why the latter method is more popular.

Firstly, constructing the hash structure is more complex than is querying the hash

structure. For every new insertion, data have to be copied around or modified, and

some solutions require reservation of space to hold the data. A query operation

just reads the data, without modifications to the data structure itself. Secondly,

constructing the hash structure is, in essence, a scattering operation, while query-

ing it resembles a gathering operation, which is much better suited to many of

today's parallel architectures. Thirdly, using the method with a single insertion

operation makes it easier to update the hash structure incrementally as the parti-

cles move around within the fluid, instead of reconstructing the hash from scratch

at every new iteration of the SPH algorithm.

For querying, a spatial hash structure has to minimize the number of fluid

particles mapping to a single hash bucket
q
, as querying is of time complexity

O
(
q
). This is achieved by choosing parameters for the spatial hash structure

and the fluid simulation itself. We will highlight three possible choices.

The first choice is to use a larger spatial hash with more buckets. This de-

creases the chance that two grid cells map to the same hash bucket and, as such,