Graphics Reference
In-Depth Information
for(intc=0;c<3;c++)
v[c] = s2[c] - s[c] * s[c] / MAX_OBJECTS;
// Update axis sorted to be the one with greatest AABB variance
gSortAxis = 0;
if (v[1] > v[0]) gSortAxis = 1;
if (v[2] > v[gSortAxis]) gSortAxis = 2;
}
During the sweep pass, the variances of the AABB centers along each of the three
axes are computed. After the pass is completed, the axis corresponding to the largest
variance is selected for use the next time the routine is called. This method does
not entirely avoid pathological cases. When objects are clustering in more than one
dimension, worst-case
O
(
n
2
) behavior could still arise.
Insertions are
O
(1) by adding new AABBs after the position last used in the array.
The sorting pass absorbs the cost of bringing the AABBs to their proper place. When
an AABB is removed, its corresponding pointer also has to be removed from the
array. Given an AABB, a binary search over the array locates the pointer in
O
(log
n
)
time. The last pointer in the array replaces the pointer to be deleted. If removals are
frequent, a back pointer inside the AABB structure to the array pointer could be filled
in during the sweep pass, making deletions
O
(1) as well.
7.6
Cells and Portals
Having an explicit spatial partitioning scheme just for collision detection is not always
necessary. Sometimes it is sufficient to tie into a hierarchical organization already
present for the efficient rendering of world geometry, such as a scene graph. An exam-
ple of an organizational structure that lends itself well to being used with collision
detection is the
cells
-
and
-
portals
method [Teller92], [Luebke95].
This method was developed for rendering architectural walkthrough systems.
These are categorized by heavily occluded environments with high depth complex-
ity. However, the amount of visible geometry in a typical architectural scene is low
in comparison to the total geometry contained in the view frustum. The cells-and-
portals method exploits the occluded nature of these scenes to reduce the amount of
geometry that has to be rendered. The method proceeds by dividing the world into
regions (cells) and the boundaries that connect them (portals). Rooms in the scene
would correspond to cells, and doorways and windows to portals. The portals define
connections between cells and both directly and indirectly determine which cells can
be viewed from a given cell (Figure 7.21).
Rendering a scene partitioned into cells and portals starts with drawing the geom-
etry for the cell containing the camera. After this cell has been rendered, the rendering
