Game Development Reference

In-Depth Information

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

list (see
Figures 3.7
and
3.8
)
.

•

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

needed to run in parallel when using multiple SPUs (see
Figure 3.9
).
First, we

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

Figure 3.7.

Insert operation.