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,
Search Nedrilad ::




Custom Search