Bounding Volumes - Real-Time Collision Detection - page 84

A
Figure 4.6 When computing a tight AABB, only the highlighted vertices that lie on the
convex hull of the object must be considered.
When n is large, this O ( n ) procedure can be expensive if performed at runtime.
Preprocessing of the vertex data can serve to speed up the process. One simple
approach that adds no extra data is based on the fact that only the vertices on the
convex hull of the object can contribute to determining the bounding volume shape
(Figure 4.6). In the preprocessing step, all k vertices on the convex hull of the object
would be stored so that they come before all remaining vertices. Then, a tight AABB
could be constructed by examining these k first vertices only. For general concave
volumes this would be a win, but a convex volume, which already has all of its
vertices on its convex hull, would see no improvement.
By use of additional, dedicated, precomputed search structures, locating extremal
vertices can be performed in O (log n ) time. For instance, the Dobkin-Kirkpatrick
hierarchy (described in Chapter 9) can be used for this purpose. However, due to
the extra memory required by these structures, as well as the overhead in traversing
them, they have to be considered overkill in most circumstances. Certainly if tight
bounding volumes are that important, tighter bounding volumes than AABBs should
be considered.
4.2.5 AABB from Hill-climbing Vertices of the Object
Representation
Another way to speed up the AABB realignment process is to use an object rep-
resentation in which neighboring vertices of a vertex can be found quickly. Such a
representation allows the extreme vertices that define the new AABB to be located
through simple hill climbing (Figure 4.7).