新建网页 1
两个AABB的相交性检测
检测两个静止AABB的相交性是很简单的，只需要在每一维上单独检查它们的重合程度即可。如果在所有维上都没有重合，那么这两个AABB就不会相交。intersectAABBs()就是用这项技术来实现的。
//---------------------------------------------------------------------------
// Check if two AABBs intersect, and return true if so. Optionally return
// the AABB of their intersection if an intersection is detected.
//---------------------------------------------------------------------------
bool intersectAABBs(const AABB3& box1, const AABB3& box2, AABB3* boxIntersect)
{
// Check for no overlap
if (box1.min.x > box2.max.x) return false;
if (box1.max.x < box2.min.x) return false;
if (box1.min.y > box2.max.y) return false;
if (box1.max.y < box2.min.y) return false;
if (box1.min.z > box2.max.z) return false;
if (box1.max.z < box2.min.z) return false;
// We have overlap. Compute AABB of intersection, if they want it.
if (boxIntersect != NULL)
{
boxIntersect->min.x = max(box1.min.x, box2.min.x);
boxIntersect->max.x = min(box1.max.x, box2.max.x);
boxIntersect->min.y = max(box1.min.y, box2.min.y);
boxIntersect->max.y = min(box1.max.y, box2.max.y);
boxIntersect->min.z = max(box1.min.z, box2.min.z);
boxIntersect->max.z = min(box1.max.z, box2.max.z);
}
return true;
}
AABB间的动态测试稍微复杂一些。考虑一个由极值点
smin和smax定义的静止AABB和一个由mmin和mmax定义的运动AABB。运动AABB的运动由向量d给出，t从0变换到1。
目标是计算运动边界框碰撞到静止边界框的时刻t（假设两个边界框刚开始时不相交）。要计算出t，我们需要计算出两个边界框在所有维上同时重合的第一个点。因为它的应用范围在2D或3D中，我们先在2D中解决它（扩展到3D也是非常容易的）。先单独分析每个坐标，解决两个(在3D中就是三个)独立的一维问题，再把它们组合到一起就得到最终答案。
现在要解决的问题变成一维问题了。我们需要知道两个矩形边界框在特定维上重合的时间区间，假设把问题投影到x轴上，如图13.15所示：
黑色矩形代表沿数轴滑动的运动AABB。当图13.15中的t=0时，运动的AABB完全位于静止AABB的左边，当t=1时运动AABB完全位于静止AABB右边。tenter是两个AABB开始相交时的时刻，tleave是两个AABB脱离接触的时刻。对于正在讨论的维，设mmin(t)和mmax(t)代表运动AABB在时刻t的最小值和最大值：
mmin(t) = mmin(0) + td
mmax(t) = mmax(0) + td
mmin(0)和mmax(0)是运动AABB的起始位置，d是位移向量d在这个维上的分量。类似地用smin和smax来定义静止AABB（当然，它们和t是不相关的，因为这个AABB是静止的）。tenter就是当mmax(t)等于smin时的t值：
这里有三个要点：
（1）如果分母d为0，那么两个矩形边界框总是相交，或永不相交。
（2）如果运动AABB开始位于静止AABB的右边并向左移动，那么tenter将大于tleave。此时我们交换两个值以确保tenter < tleave。
（3）tenter 和 tleave的值可能会超出[0, 1]这个区间，为了应付t值超出区间的情况，可以认为运动AABB是沿着平行于d的无限轨道移动。当tenter> 1或tleave < 0时，在所讨论的时间内它们是不相交的，
现在我们已经能够求出两个边界框重合的时间范围了，其边界为tenter和tleave。在这段时间内两个边界框会在某一维上相交，而所有维上的时间区间的交集就是两个边界框相交的时间段。图13.16展示了在2D中的两个时间区间（不要和图13.15混淆，图 13.16中的数轴是时间轴，而图13.15中的数轴是x轴）。
如果区间为空，那么两个边界框永远不会相交；如果区间范围在[0, 1]之外，那么在所讨论的时间段内它们不相交。实际上，这个时间区间给出的信息比我们想要的多，因为我们只需要知道它们开始相交的时间点，而不需要知道结束相交的点。然而，我们仍然要维持这个区间来检测时间区间是否为空。
intersectMovingAABB()有上述过程的完整实现：
//---------------------------------------------------------------------------
// Return parametric point in time when a moving AABB collides
// with a stationary AABB. Returns > 1 if no intersection.
//---------------------------------------------------------------------------
float intersectMovingAABB(const AABB3& stationaryBox, const AABB3& movingBox, const Vector3& d)
{
// We'll return this huge number if no intersection
const float kNoIntersection = 1e30f;
// Initialize interval to contain all the time under consideration
float tEnter = 0.0f;
float tLeave = 1.0f;
// Compute interval of overlap on each dimension, and intersect this interval with the interval
// accumulated so far. As soon as an empty interval is detected, return a negative result
// (no intersection.) In each case, we have to be careful for an infinite of empty interval on
// each dimension.
// Check x-axis
if (d.x == 0.0f)
{
// Empty or infinite inverval on x
if ((stationaryBox.min.x >= movingBox.max.x) || (stationaryBox.max.x <= movingBox.min.x))
{
// Empty time interval, so no intersection.
return kNoIntersection;
}
// Inifinite time interval - no update necessary
}
else
{
float oneOverD = 1.0f / d.x; // Divide once
// Compute time value when they begin and end overlapping
float xEnter = (stationaryBox.min.x - movingBox.max.x) * oneOverD;
float xLeave = (stationaryBox.max.x - movingBox.min.x) * oneOverD;
// Check for interval out of order
if (xEnter > xLeave)
swap(xEnter, xLeave);
// Update interval
if (xEnter > tEnter) tEnter = xEnter;
if (xLeave < tLeave) tLeave = xLeave;
// Check if this resulted in empty interval
if (tEnter > tLeave)
return kNoIntersection;
}
// Check y-axis
if (d.y == 0.0f)
{
// Empty or infinite inverval on y
if ((stationaryBox.min.y >= movingBox.max.y) || (stationaryBox.max.y <= movingBox.min.y))
{
// Empty time interval, so no intersection
return kNoIntersection;
}
// Inifinite time interval - no update necessary
}
else
{
// Divide once
float oneOverD = 1.0f / d.y;
// Compute time value when they begin and end overlapping
float yEnter = (stationaryBox.min.y - movingBox.max.y) * oneOverD;
float yLeave = (stationaryBox.max.y - movingBox.min.y) * oneOverD;
// Check for interval out of order
if (yEnter > yLeave)
swap(yEnter, yLeave);
// Update interval
if (yEnter > tEnter) tEnter = yEnter;
if (yLeave < tLeave) tLeave = yLeave;
// Check if this resulted in empty interval
if (tEnter > tLeave)
return kNoIntersection;
}
// Check z-axis
if (d.z == 0.0f)
{
// Empty or infinite inverval on z
if ((stationaryBox.min.z >= movingBox.max.z) || (stationaryBox.max.z <= movingBox.min.z))
{
// Empty time interval, so no intersection
return kNoIntersection;
}
// Inifinite time interval - no update necessary
}
else
{
// Divide once
float oneOverD = 1.0f / d.z;
// Compute time value when they begin and end overlapping
float zEnter = (stationaryBox.min.z - movingBox.max.z) * oneOverD;
float zLeave = (stationaryBox.max.z - movingBox.min.z) * oneOverD;
// Check for interval out of order
if (zEnter > zLeave)
swap(zEnter, zLeave);
// Update interval
if (zEnter > tEnter) tEnter = zEnter;
if (zLeave < tLeave) tLeave = zLeave;
// Check if this resulted in empty interval
if (tEnter > tLeave)
return kNoIntersection;
}
// OK, we have an intersection.
// Return the parametric point in time where the intersection occurs.
return tEnter;
}
不幸的是，在实际情况中，物体的边界框很少是轴对齐于同一个坐标空间的。然而，因为这个检测相对较快，所以可以把它当作一个预备测试，可以先排除一些物体，然后再做一个特殊（通常计算量更大的）检测。