Game Development Reference
needed to access the next node. We can't use the method of double buffering due
to this dependency.
However, with a sorted array we can calculate the address of each node by
adding an offset address and an index of a node. Thus, we can calculate an address
of a node used in the future. We prepare two buffers and assign one for DMA
transfer of data and the other for computation and then execute computation and
DMA transfer in parallel to hide the latency of DMA transfer.
The following two operations are needed to replace the operations of a linked
Insert. Add new nodes to the last of an array, then sort the whole array.
Remove. Set sort keys of removed nodes to the maximum number as a
sentinel value, then sort the whole array.
Parallelize the sort algorithm. For faster operation, a sort algorithm is also
need to load as much data from main memory as we can store into the local stor-
age and then sort the data on each SPU. The straightforward implementation of
this sort is not complicated because sorting is executed on a single SPU, and all
the necessary data is in its local storage. Actually, we use the combination of the
bitonic and the merge sort for sorting on a single SPU.
The next step is to merge two sorted data sets using two SPUs, just putting data
from both sides while comparing the value of data. Then repeat these procedures
a few times and all the data will be sorted correctly, as shown in Figure 3.10.
How to find overlapped pairs using sorted AABB arrays. First, prepare AABB
arrays that are sorted along the x -, y -, and z -axes, taking the minimum value
as a sort key. Then, find the axis along which all rigid bodies are most widely