Graphics Reference
In-Depth Information
d
E
E
E
'
(a)
(b)
Figure 4.7
(a) The extreme vertex
E
in direction
d
. (b) After object rotates counterclockwise,
the new extreme vertex
E
in direction
d
can be obtained by hill climbing along the vertex path
highlighted in gray.
Instead of keeping track of the minimum and maximum extent values along each
axis, six vertex pointers are maintained. Corresponding to the same values as before,
these now actually point at the (up to six) extremal vertices of the object along each
axis direction. The hill-climbing step now proceeds by comparing the referenced
vertices against their neighbor vertices to see if they are still extremal in the same
direction as before. Those that are not are replaced with one of their more extreme
neighbors and the test is repeated until the extremal vertex in that direction is found.
So as not to get stuck in local minima, the hill-climbing process requires objects to
be convex. For this reason, hill climbing is performed on precalculated convex hulls
of nonconvex objects. Overall, this recalculation of the tight AABB is an expected
constant-time operation.
Only having to transform vertices when actually examined by the hill-climbing
process greatly reduces computational effort. However, this can be further improved
by the realization that only one of the
x
,
y
,or
z
components is used in finding the
extremal vertex along a given axis. For instance, when finding the extremal point
along the
x
axis only the
x
components of the transformed vertices need to be
computed. Hence, the transformational cost is reduced by two-thirds.
Some care must be taken in order to write a robust implementation of this hill-
climbing method. Consider an extremal vertex along any axis surrounded by coplanar
vertices only. If the object now rotates 180 degrees about any of the remaining two
axes, the vertex becomes extremal along the opposite direction along the same axis.
However, as it is surrounded by co-planar vertices, the hill-climbing step cannot find
a better neighboring vertex and thus terminates with a vertex that is, in fact, the least
extremal in the sought direction! A robust implementation must special-case this
situation. Alternatively, coplanar vertices can be removed in a preprocessing step,
as described in Chapter 12. The problem of finding extremal vertices is revisited in
Section 9.5.4.
+
