新建網(wǎng)頁(yè) 1
兩個(gè)AABB的相交性檢測(cè)
檢測(cè)兩個(gè)靜止AABB的相交性是很簡(jiǎn)單的，只需要在每一維上單獨(dú)檢查它們的重合程度即可。如果在所有維上都沒(méi)有重合，那么這兩個(gè)AABB就不會(huì)相交。intersectAABBs()就是用這項(xiàng)技術(shù)來(lái)實(shí)現(xiàn)的。
//---------------------------------------------------------------------------
// 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間的動(dòng)態(tài)測(cè)試稍微復(fù)雜一些。考慮一個(gè)由極值點(diǎn)
smin和smax定義的靜止AABB和一個(gè)由mmin和mmax定義的運(yùn)動(dòng)AABB。運(yùn)動(dòng)AABB的運(yùn)動(dòng)由向量d給出，t從0變換到1。
目標(biāo)是計(jì)算運(yùn)動(dòng)邊界框碰撞到靜止邊界框的時(shí)刻t（假設(shè)兩個(gè)邊界框剛開(kāi)始時(shí)不相交）。要計(jì)算出t，我們需要計(jì)算出兩個(gè)邊界框在所有維上同時(shí)重合的第一個(gè)點(diǎn)。因?yàn)樗膽?yīng)用范圍在2D或3D中，我們先在2D中解決它（擴(kuò)展到3D也是非常容易的）。先單獨(dú)分析每個(gè)坐標(biāo)，解決兩個(gè)(在3D中就是三個(gè))獨(dú)立的一維問(wèn)題，再把它們組合到一起就得到最終答案。
現(xiàn)在要解決的問(wèn)題變成一維問(wèn)題了。我們需要知道兩個(gè)矩形邊界框在特定維上重合的時(shí)間區(qū)間，假設(shè)把問(wèn)題投影到x軸上，如圖13.15所示：
黑色矩形代表沿?cái)?shù)軸滑動(dòng)的運(yùn)動(dòng)AABB。當(dāng)圖13.15中的t=0時(shí)，運(yùn)動(dòng)的AABB完全位于靜止AABB的左邊，當(dāng)t=1時(shí)運(yùn)動(dòng)AABB完全位于靜止AABB右邊。tenter是兩個(gè)AABB開(kāi)始相交時(shí)的時(shí)刻，tleave是兩個(gè)AABB脫離接觸的時(shí)刻。對(duì)于正在討論的維，設(shè)mmin(t)和mmax(t)代表運(yùn)動(dòng)AABB在時(shí)刻t的最小值和最大值：
mmin(t) = mmin(0) + td
mmax(t) = mmax(0) + td
mmin(0)和mmax(0)是運(yùn)動(dòng)AABB的起始位置，d是位移向量d在這個(gè)維上的分量。類似地用smin和smax來(lái)定義靜止AABB（當(dāng)然，它們和t是不相關(guān)的，因?yàn)檫@個(gè)AABB是靜止的）。tenter就是當(dāng)mmax(t)等于smin時(shí)的t值：
這里有三個(gè)要點(diǎn)：
（1）如果分母d為0，那么兩個(gè)矩形邊界框總是相交，或永不相交。
（2）如果運(yùn)動(dòng)AABB開(kāi)始位于靜止AABB的右邊并向左移動(dòng)，那么tenter將大于tleave。此時(shí)我們交換兩個(gè)值以確保tenter < tleave。
（3）tenter 和 tleave的值可能會(huì)超出[0, 1]這個(gè)區(qū)間，為了應(yīng)付t值超出區(qū)間的情況，可以認(rèn)為運(yùn)動(dòng)AABB是沿著平行于d的無(wú)限軌道移動(dòng)。當(dāng)tenter> 1或tleave < 0時(shí)，在所討論的時(shí)間內(nèi)它們是不相交的，
現(xiàn)在我們已經(jīng)能夠求出兩個(gè)邊界框重合的時(shí)間范圍了，其邊界為tenter和tleave。在這段時(shí)間內(nèi)兩個(gè)邊界框會(huì)在某一維上相交，而所有維上的時(shí)間區(qū)間的交集就是兩個(gè)邊界框相交的時(shí)間段。圖13.16展示了在2D中的兩個(gè)時(shí)間區(qū)間（不要和圖13.15混淆，圖 13.16中的數(shù)軸是時(shí)間軸，而圖13.15中的數(shù)軸是x軸）。
如果區(qū)間為空，那么兩個(gè)邊界框永遠(yuǎn)不會(huì)相交；如果區(qū)間范圍在[0, 1]之外，那么在所討論的時(shí)間段內(nèi)它們不相交。實(shí)際上，這個(gè)時(shí)間區(qū)間給出的信息比我們想要的多，因?yàn)槲覀冎恍枰浪鼈冮_(kāi)始相交的時(shí)間點(diǎn)，而不需要知道結(jié)束相交的點(diǎn)。然而，我們?nèi)匀灰S持這個(gè)區(qū)間來(lái)檢測(cè)時(shí)間區(qū)間是否為空。
intersectMovingAABB()有上述過(guò)程的完整實(shí)現(xiàn)：
//---------------------------------------------------------------------------
// 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;
}
不幸的是，在實(shí)際情況中，物體的邊界框很少是軸對(duì)齊于同一個(gè)坐標(biāo)空間的。然而，因?yàn)檫@個(gè)檢測(cè)相對(duì)較快，所以可以把它當(dāng)作一個(gè)預(yù)備測(cè)試，可以先排除一些物體，然后再做一個(gè)特殊（通常計(jì)算量更大的）檢測(cè)。