Graphics Reference
In-Depth Information
7.5
Sort and Sweep Methods
A drawback of inserting objects into the fixed spatial subdivisions that grids and
octrees represent is having to deal with the added complications of objects straddling
multiple partitions. An alternative approach is to instead maintain the objects in some
sort of sorted spatial ordering. One way of spatially sorting the objects is the
sort and
sweep
method [Baraff92] (referred to as
sweep and prune
in [Cohen95]).
First consider the case of detecting overlap among 1D bounding boxes. Each such
box corresponds to an interval
on the coordinate axis. Given
n
such intervals,
all
b
and
e
values can be inserted into a sorted list (Figure 7.19). By sweeping the list,
active intervals can be tracked by adding them to a list whenever their
b
values are
encountered and removing them when their
e
values are encountered. Whenever a
new interval is added to the list, it has also been found to overlap the already active
intervals on the list.
By considering their projection intervals onto the
x
,
y
, and
z
axes, AABBs in 3D
can be identified as three independent such intervals. Thus, for each coordinate axis a
sorted linked list is maintained of the start and end values of the corresponding AABB
projection intervals of all objects. The collisions for a single object can on average be
found in near constant time by querying neighboring objects for overlap. Only those
objects within the projection interval of the tested object have to be examined. Linked
lists also allow for dynamic updating whenever an object moves.
After the lists have been sorted, as objects generally do not move very far between
frames the lists will remain almost sorted from one frame to the next. To exploit
temporal coherence effectively, the lists are kept from frame to frame and they are
maintained sorted using a simple insertion sort, which has linear behavior for nearly
ordered lists.
To allow for fast updates during the sorting pass, the lists need to be double linked.
Start and end list sentinels help both to simplify (by removing special case tests such
as testing for empty lists or reaching either end of the list) and speed up the code
[Knuth98].
[
b
,
e
]
b
0
b
1
e
0
b
2
e
1
e
2
b
3
b
4
e
3
e
4
Figure 7.19
Projected AABB intervals on the
x
axis.
