Game Development Reference
In-Depth Information
Figure 3.11. AABB array on the selected axis.
Parallelize finding overlapped pairs algorithm. To find the intersection of
AABBs, continue to traverse the AABB array until a maximum value of the cur-
rent AABB becomes smaller than a minimum value of the next AABB. This pro-
cess is implemented as a simple double loop, shown in Listing 3.2. Figure 3.12
illustrates this algorithm using an extreme case. Actually, pairs with a dotted line
aren't processed because any unnecessary processing is removed by checking the
end condition.
for( int i=0;i
{
for( int j=i+1;j < total ;j++) {
// axis : 0,1,2 = X,Y,Z
i f ( AABBs [ i ] . max [ a x i s ] < AABBs [ j ] . min [ a x i s ] )
<
total ;i++)
{
break ;
i f ( c h e c kO v e r l a p ( AABBs [ i ] , AABBs [ j ] ) )
{
submitOverlappedPair (i , j );
}
}
}
Listing 3.2. The example code of finding overlapped pairs.
The next step is to parallelize this process. Because there is more efficient
parallelization if we can divide by a large processing element, we divide by the
outside loop instead of the inner loop. Since there are no data dependencies be-
tween AABBs, we can divide the total number of AABBs by the number of the
possible parallel batches as in Figure 3.12. As soon as each SPU finds a batch
that hasn't been processed, it starts finding overlapping pairs within this batch.
We can't know the execution time of each batch beforehand, as the amount of
data included in each batch isn't uniform. It is necessary to choose the number of
batches carefully so that an SPU does not become free.