Game Development Reference
In-Depth Information
Figure 3.5. Sweep and prune.
Figure 3.6. Structure of AABB node.
3.3.2 An Optimized SAP Algorithm
First, remove the data structure connected with many pointers because that struc-
ture is hard for SPUs to deal with. As in Figure 3.5, linked lists are created
along the x -, y -, and z -axes, and each node in these lists is linked with a previous
node. When traversing all lists, such a structure causes calling too many DMA
operations and ends up with a low performance. Therefore, to reduce traversing
pointers, it is better to use a structure that holds all necessary information without
pointers.
An Optimized Structure of AABB. Figure 3.6 shows the structure of the node
that holds all AABB values in one structure. For efficient use of the local storage,
we take a value of AABB as a 16-bit integer instead of using a 32-bit float, and
this structure is represented as a 128-bit length so that SPUs can handle it at a
peak performance.
Using a sorted array as a list. To parallelize computation and DMA transfer
in double-buffering mode, a sorted array is better than a linked list. As for a
linked list in which all nodes are connected by pointers, the current node is always
Search Nedrilad ::




Custom Search