Geometric Tests - 3D Math Primer for Graphics and Game Development - page 738

This strategy is actually an instance of a more general strategy known
as the separating axis test. If two convex polyhedra do not overlap, then
there exists a separating axis upon which, if we project the two polyhedra,
their projections will not overlap. (In 3D, it's easier to visualize a plane
perpendicular to the separating axis that can be placed between the two
polyhedra.) The key to the separating axis method is that only a finite
number of axes need to be tested: the normals of the faces and certain
cross products; for details, see Ericson [18]. If the projections of the poly-
hedra onto those axes overlap in all cases, then it is safe to assume that no
separating axis can be found. In the case of two AABBs, only the three
cardinal axes need to be tested. Furthermore, these “projections” simply
extract the appropriate coordinate.
The dynamic intersection of AABBs is only slightly more complicated.
Consider a stationary AABB defined by extreme points s min and s max , and
a moving AABB, which has extreme points m min and m max in the initial
position at t = 0. The moving AABB displaces by an amount given by the
vector d , as t varies from 0 to 1.
Our task is to compute t, the parametric point in time where the mov-
ing box first collides with the stationary box. (We assume that the boxes
are not initially intersecting.) To do this, we will attempt to determine the
first point in time when the boxes have overlap on all dimensions simultane-
ously. Since this applies in 2D or 3D, we illustrate the problem here in 2D;
extending the technique into 3D is straightforward. We analyze each co-
ordinate separately, solving two (or three, in 3D) separate one-dimensional
problems, and then combining these results to give the answer.
The problem is now one-dimensional. We need to know the interval of
time when the two boxes overlap on a particular dimension. Imagine pro-
jecting the problem onto the x-axis (for example), as shown in Figure A.15.
Figure A.15
Projecting the
dynamic AABB
intersection
problem onto
one axis
As we advance in time, the line segment representing the moving box
will slide along the number line. In the illustration in Figure A.15, at t = 0