和立方体相交和前两个相交测试比起来略微有点难度，我们先从标准的AABB开始，了解思路之后再推到OBB的情况。
射线和AABB相交
AABB是轴向对齐包围盒的缩写，因此AABB的边界会和坐标轴平行，相较OBB起来比较简单。依旧是从2D的情况开始分析，这样连z轴都少了，如法炮制，看图说话：
![射线和正方形相交][ray-box]
相交
我们先来看相交的情况。可以这么看，包围盒的左右边界的两条直线，和ray相交，截出一条线段，交点为 tx0, tx1（我们以交点在射线上的 t 值来代替交点）。如果这条被截取的线段发生如下情况：
- 和上下边界的直线有交点，则有交点 tx0 < ty < tx1 如下情况
- tx0 < ty0 < ty1 < tx1; (和两条边界相交)
- tx0 < ty1 < tx1; (和下边界相交，且 ty0 < tx0)，
- tx0 < ty0 < tx1; (和上边界相交，且 tx1 < ty1)
- 在上下边界的直线的区间内，可以交换着看，被上下边界截出来的线段，和左右边界有交点，然后按照情况1分析。
就说明射线和包围盒相交了，那么真正的交点应该是：
t0 = min(tx0, ty0);
t1 = min(tx1, ty1);
不相交
然而射线不会一直和AABB相交，看图中上下两条射线，tx1' < ty0' 或者 ty1' < tx0' 的时候，射线就不会相交，注意，同时成立的还有 tx0' < tx1', ty0' <ty1。那么结合相交的最后情况，就能判断相交情况。
- 求出交点 tx0, tx1, ty0, ty1
- t0 = min(tx0, ty0);
- t1 = min(tx1, ty1);
- if( t1 < t0 ) 射线与包围盒不相交
计算交点。
AABB的边界和坐标轴平行，因此AABB的四条边界方程大概是这样的：
// X0、X1、Y0、Y1为常数
// 且 X0 < X1, Y0 < Y1
x = X0; (方程1)
x = X1;
y = Y0;
y = Y1;
接下来就是联立方程了，因为 x=C 这样的方程，y是任意的，所以不太好联立，同时我们知道射线方程： P(t) = O + D·t是向量的写法，我们可以试着把向量展开，就能得到2个式子（这里我们还在假设2D情况）
Px(t) = Ox + Dx·t; (方程2)
Py(t) = Oy + Dy·t;
联立方程1与方程2，就能得到4个交点。
tx0 = (X0 - Ox) / Dx;
tx1 = (X1 - Ox) / Dx;
ty0 = (Y0 - Ox) / Dy;
ty1 = (Y1 - Ox) / Dy;
值得注意的是， 当Dx 或者 Dy 为零，这个等式似乎不太好在代码中实施，这意味着射线的方向和轴是平行的，交点肯定是不存在的。我们得针对平行的情况单独做处理。
相交测试
if( fabs(Dx) < FLOAT_EPSILON ) //射线和Y轴平行
return Oy < Y1 && Oy > Y0;
else ( fabs(Dy) < FLOAT_EPSILON ) //射线平行X轴
return Ox < X1 && Ox > X0;
else
{
tx0 = (X0 - Ox) / Dx;
tx1 = (X1 - Ox) / Dx;
ty0 = (Y0 - Ox) / Dy;
ty1 = (Y1 - Ox) / Dy;
t0 = max(tx0, ty0);
t1 = min(tx1, ty1);
return (t0 < t1);
}
//其实根据IEEE的特性，可以先计算1/Dx，得到一个无穷数
//再去用 invDx去乘 X0-Ox作为优化
//但是水平有限，不太好说明这个问题，而且这个优化需要依赖编译器
//等以后弄清楚了再聊
上头的测试有2个问题
- 当Dx或者Dy为负数的时候，t0 > t1。射线反向，先交x=X1再交x=X0我们需要t0是近点，t1是远点，所以这里还需要做下符号判断。
- 当近点 t0 < 0时，说明射线是在盒子内部的，但当时 远点 t1 < 0 时候，就说明射线是在负方向与盒子相交了。
所以我们稍作修改
if(Dx < 0)
{
tx1 = (X0 - Ox) / Dx;
tx0 = (X1 - Ox) / Dx;
}
else
{
tx0 = (X0 - Ox) / Dx;
tx1 = (X1 - Ox) / Dx;
}
....//omiitted
if(t0 > t1)
return false;
else if (t0 < 0)
{
if (t1 < 0)
return false;
t0 = t1;
}
return true;
AABB code
基本到这里，2D的射线-盒子相交检测就完工了。我们试着推导到3D的情况。 当在一个平面上有相交的情况，只要在剩下的两个平面（三个轴三个平面）中的其一，用相同的办法算出有相交情况就能确定射线和立方体的相交情况了。在这种情况下需要测试三个分支代码不太好书写，所以得换个思路从不相交判断上更容易书写，下面动手实操。
class AABB
{
GetExtend() { return Vector3(width, height, depth); }
GetCenter() { return Vector3(Cx, Cy, Cz); }
}
float t0[3];
float t1[3];
float tmin, tmax;
bool tinit = false;
for(int i = 0; i < 3; i++)
{
//先测试平行的情况，分别取出Dx，Dy，Dz来判断
if( fabs(D[i] ) < FLOAT_EPSILON )
//在区间之外
if( fabs( O[i] - aabb.GetCenter()[i] ) > aabb.GetExtend()[i])
return false;
else //不平行的话，就试试算个交点
{
if( D[i] > 0)
{
t0[i] = ( aabb.GetCenter()[i] - aabb.GetExtend()[i] - O[i] ) / D[i];
t1[i] = ( aabb.GetCenter()[i] + aabb.GetExtend()[i] - O[i] ) / D[i];
}
else
{
t0[i] = ( aabb.GetCenter()[i] + aabb.GetExtend()[i] - O[i] ) / D[i];
t1[i] = ( aabb.GetCenter()[i] - aabb.GetExtend()[i] - O[i] ) / D[i];
}
//if( t1[i] < t[0] ) //这个说明碰到射线反方向了，两个都为负数才会这样
// return false; //这个挪到 tinit里头也能判断，同时还判断了界外
if( tinit )
{
if( tmin < t0[i] ) tmin = t0[i];
if( tmax > t1[i] ) tax = t1[i];
if( tmin < tmax )
return false;
}
else
{
tmin = t0[i];
tmax = t1[i];
tinit = true;
}
}
}
if( tmax < 0 ) return false;
return true;
OBB
立方体可以用3个方向轴（就是xyz）和在在轴上的长度（就是width height depth)来定义。AABB三个轴会一直保持 x<1,0,0>, y<0,1,0> z<0,0,1>，而OBB除了三个轴向不同之外，别的都和AABB差不多的，我们的思路是把Ray射线投影到立方体的三个轴上，按照AABB的测试方法去做检测。（待续)，按照AABB往OBB的情况推导的话，有如下定义：
class Box
{
GetAxisX() { return Vector3(1, 0, 0); }
GetAxisY() { return Vector3(0, 1, 0); }
GetAxisZ() { return Vector3(0, 0, 1); }
GetExtend() { return Vector3(width, height, depth); }
GetCenter() { return Vector3(Cx, Cy, Cz); }
}
最终代码如下：
bool Intersect(const Ray& ray, const Box& box, float& t0, float& t1)
{
int parallelMask = 0;
bool found = false;
Vector3 dirDotAxis;
Vector3 ocDotAxis;
Vector3 oc = box.GetCenter() - ray.GetOrigin();
Vector3 axis[3] = { box.GetAxisX(), box.GetAxisY(), box.GetAxisZ() };
for (int i = 0; i < 3; ++i)
{
dirDotAxis[i] = dot(ray.GetDirection(), axis[i]);
ocDotAxis[i] = dot(oc, axis[i]);
if (fabs(dirDotAxis[i]) < FLOAT_EPISLON)
{
//垂直一个方向，说明与这个方向为法线的平面平行。
//先不处理，最后会判断是否在两个平面的区间内
parallelMask |= 1 << i;
}
else
{
float es = (dirDotAxis[i] > 0.0f) ? box.GetExtend()[i] : -box.GetExtend()[i];
float invDA = 1.0f / dirDotAxis[i]; //这个作为cos来使用，为了底下反算某轴向方向到 中心连线方向的长度
if (!found)
{
// 这一步骤算出在轴向方向上，连线和平面的交点。
// 这个平面的法线=轴
t0 = (ocDotAxis[i] - es) * invDA;
t1 = (ocDotAxis[i] + es) * invDA;
found = true;
}
else
{
float s = (ocDotAxis[i] - es) * invDA;
if (s > t0)
{
t0 = s;
}
s = (ocDotAxis[i] + es) * invDA;
if (s < t1)
{
t1 = s;
}
if (t0 > t1)
{
//这里 intersect0代表就近点, intersect1代表远点。
//t0 > t1，亦近点比远点大
//表明了 两个t 都是负数。
//说明了obb是在射线origin的反方向上。
//或者是在偏移到外部擦身而过了
return false;
}
}
}
}
if (parallelMask)
{
for (int i = 0; i < 3; ++i)
{
if (parallelMask & (1 << i))
{
if (fabs(ocDotAxis[i] - t0 * dirDotAxis[i]) > box.GetExtend()[i] ||
fabs(ocDotAxis[i] - t1 * dirDotAxis[i]) > box.GetExtend()[i])
{
return false;
}
}
}
}
//t1 < t0已经在最上头被短路了
if (t0 < 0)
{
if (t1 < 0)
{
return false;
}
t0 = t1;
}
return true;
}
网友评论