Graphics Reference
In-Depth Information
Figure 7.20
Objects clustered on the
y
axis (caused, for example, by falling objects settling
on the ground). Even small object movements can now cause large positional changes in the
list for the clustered axis.
In general, updating lists for
n
objects is expected time
O
(
n
). However, coherence
can break down due to clustering of objects. Specifically, sorting can deteriorate to
O
(
n
2
) on the clustered axis because of small world movements causing large positional
movements in the list. Unfortunately, such clustering is common. For instance, having
all objects on a surface, such as a floor, will cause tight clustering on the vertical axis
(Figure 7.20).
One solution to the global situation in which objects tend to cluster on, say, the
y
axis is to track only the
x
and
z
lists. In most situations, sorting on just two axes is
likely to be sufficient, which also has the benefit of reducing the memory overhead of
this scheme. In some cases, it might even be worthwhile to pick axes other than the
normal
x
,
y
, and
z
ones to sort on. For instance, the
x
y
axis could be considered
in situations in which objects tend to cluster on
x
or
y
. Although this may lessen the
clustering problem for specific applications, the problem still remains. Section 7.5.2
suggests an alternative implementation avoiding the worst-case
O
(
n
2
) behavior.
=
7.5.1
Sorted Linked-list Implementation
To maintain the axis-sorted lists of projection interval extents, two types of struc-
tures are required: one that is the linked-list element corresponding to the minimum
or maximum interval values and another one to link the two entries. A naive
implementation would look as follows.
struct AABB {
Elem *pMin[3];
// Pointers to the three minimum interval values (one for each axis)
Elem *pMax[3];
// Pointers to the three maximum interval values (one for each axis)
Object *pObj;
// Pointer to the actual object contained in the AABB
};
struct Elem {
AABB *pAABB;
// Back pointer to AABB object (to find matching max/min element)
Elem *pLeft;
// Pointer to the previous linked list element
