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.