Graphics Reference
In-Depth Information
The preceding code should be a sufficient framework for implementing the addi-
tional code required to complete the linked-list implementation of sort and sweep.
7.5.2
Array-based Sorting
The strength of the linked-list approach is twofold. First, it can handle a large number
of objects, memory permitting. Second, when none or just a few objects move, little
or no work is required to maintain the data structures from frame to frame. Unfor-
tunately, the rather hefty memory overhead for each object AABB is a drawback. The
worst-case
O
(
n
2
) clustering behavior is equally serious.
An alternative is to implement axial extent sorting using arrays. Arrays are more
inflexible when it comes to dynamically allowing more objects, but they use less
memory. Using arrays, even if a single object moves the whole array might need
updating, and thus a full sorting pass is required regardless. At the same time, the
clustering problem is virtually removed and worst-case performance is determined
by the sorting algorithm used [for example,
O
(
n
log
n
) for Quicksort or
O
(
kn
) for
radix sort]. Unlike lists, this remains constant even if all objects move, or if they move
over large distances. Using arrays simplifies the code and provides cache-friendly
accessing of memory. The following implementation operates on a single array of
pointers, pointing to the object AABBs.
struct AABB {
Point min;
Point max;
...
};
AABB *gAABBArray[MAX_OBJECTS];
For each pass of the sort-and-sweep algorithm one of the coordinate axes is
selected as the axis to sort along. (The selection is described later.) The selected
axis is specified through a global variable.
int gSortAxis = 0;
// Specifies axis (0/1/2) to sort on (here arbitrarily initialized)
Given a sorting axis, the pointers are sorted in ascending order based on the
minimum value of the referenced AABB. To simplify the presentation, the following
code uses
stdlib
's
qsort()
. The required comparison function needed for
qsort()
to
sort the AABBs is:
// Comparison function for qsort. Given two arguments A and B must return a
// value of less than zero ifA<B,zero ifA=B,andgreater than zero ifA>B