Game Development Reference
In-Depth Information
Subsequent passes then only have to evaluate particles that are actual neighbors
instead of evaluating all potential neighbors. However, constructing such a neigh-
bor list costs time, and in parallel execution environments it becomes non-trivial
to manage query access patterns of the neighbor list on the different execution
units. While efficiency of a neighbor list for parallel execution is shown to be
good by [Hjelte 06], the effect of using a neighbor list on the overall performance
of the algorithm is difficult to estimate and tune.
Instead, it is an interesting idea to forgo the complexity of multiple passes
and neighbor lists by collapsing the three passes into one, possibly at the cost of
simulation accuracy. Naively collapsing the three passes gives the algorithm in
Algorithm 2.
Algorithm 2 SPH algorithm with the three passes collapsed.
{ [ x i ] 0 :1 ≤ i ≤ n} , { [ v i ] 0 :1 ≤ i ≤ n} and { [ ρ i ] 1 :1 ≤ i ≤ n} are known
{{
}}
begin
construct spatial hash structure using { [ x i ] 0 :1 ≤ i ≤ n} ;
for al l particles i
begin
query spatial hash at [ x i ] 0 ;
for al l nearby particles j from query
begin
accumulate [ ρ i ] 0 using [ x j ] ? and m j ;
accumulate [ f i ] 0 using [ x j ] ? , [ v j ] ? , [ ρ j ] ? and m j ;
end;
calculate [ a i ] 0 using [ f i ] 0 and m i ;
integrate [ v i ] 1 using [ a i ] 0 ;
integrate [ x i ] 1 using [ v i ] 1 ;
end;
end;
This algorithm is not complete. It is not clear what the state of x j is for
every particle j during accumulation of [ ρ i ] 0 , and the same problem presents itself
during accumulation of [ f i ] 0 . The problem is caused by a partially updated state
of neighbor particles when a certain particle i is being updated, as some neighbor
particles may already have updated their state to time step t 1 —in particular, those
with indices j : j<i . One solution is to simply use the state at t 1 for those
particles, but in that case, the state of the particle positions may be inconsistent
with the state of the spatial hash, unless we decide to update the spatial hash in
between particle updates as well. This may not be such a problem for sequential
Search Nedrilad ::




Custom Search