给定边界框和一条线(两个点),确定该线是否与框相交

Question

给定一个边界框,在3D空间中定义像bounds.min.(x/y/z),bounds.max.(x/y/z)和两个点(表示为Vector3对象),如何确定两个点所形成的线是否与边界框相交？

Answer 1

让我谷歌那个为你:Line Box Intersection(http://www.3dkingdoms.com/weekly/weekly.php?a=3)

另一个链接,带有很多交集测试的引用(和代码):http://www.realtimerendering.com/intersections.html

如果你想了解更多关于交叉口测试的信息,这个是圣经:实时碰撞检测(亚马逊)

编辑:在本算法论文("一个高效,强大的雷盒交法",艾米·威廉姆斯和史蒂夫Barrus和R.基思·莫雷和彼得·雪莉,显卡,GPU和游戏工具的期刊,第10(1) ,49-54,2005)看起来特别简洁,并附带(C++)源代码.

Answer 2

如果您想自己进行数学运算,可以采用以下方法:将线条与边界框创建的6个平面中的每一个相交.

线的矢量表示是X = B + t*D,其中B是基点的元组(x,y,z)(比如,你的第一个点),D是线的方向,再次表示为元组(dx,dy,dz).你通过从另一个点中减去一个点得到方向,所以如果你有点P1(x1,y1,z1)和P2(x2,y2,z2),那么D = P2 - P1和B = P1,意思是D =(x2-x1,y2-y1,z2-z1).我们将调用此向量的元素dx,dy和dz.

平面的参数表示是x + y + z = c.因此,将边界框转换为此表示,然后使用线的参数表示,例如三个等式x = x1 + t dx,y = y1 + t dy,z = y1 + t*dz,以替换x,y和平面方程中的z.解决问题.由于您的6个平面中的每个平面都将与由2个轴创建的平面平行,因此您的问题变得更加容易; 例如,对于与x和y轴创建的平面平行的平面,平面方程只是变为z = c,而c是其中一个边界框点的z坐标,依此类推.

现在用t来计算直线与平面的交点.(如果t <0或> 1,那么你的线与P1-P2的OUTSIDE相交,如果t> = 0且t <= 1,则你的线与P1和P2之间的某个平面相交)

现在你还没有完成.平面方程为您提供一个平面,而不是一个矩形,因此与平面的交点实际上可能在您的矩形外面,但由于您现在有了交点的坐标(x = x1 + t*dx等),你可以很容易地看到这个点是否在你的边界框的矩形内.现在缩小您的问题以检查2D空间中的点是否在边界框矩形内,这很容易检查.

当然,如果你实际使用这个解决方案,你应该做的第一件事是检查线是否也沿着一个轴对齐,因为在这种情况下,你的交叉码变得微不足道,它也会处理线不相交的问题一些平面,例如巨大或微小数量的t,甚至可能是上溢或下溢.

我打赌有更快的方法来做到这一点,但它会奏效.

Answer 3

这是似乎有效的代码，从Greg S的答案转换为C＃：

bool CheckLineBox(Vector3 B1, Vector3 B2, Vector3 L1, Vector3 L2, ref Vector3 Hit)
{
    if (L2.x < B1.x && L1.x < B1.x) return false;
    if (L2.x > B2.x && L1.x > B2.x) return false;
    if (L2.y < B1.y && L1.y < B1.y) return false;
    if (L2.y > B2.y && L1.y > B2.y) return false;
    if (L2.z < B1.z && L1.z < B1.z) return false;
    if (L2.z > B2.z && L1.z > B2.z) return false;
    if (L1.x > B1.x && L1.x < B2.x &&
        L1.y > B1.y && L1.y < B2.y &&
        L1.z > B1.z && L1.z < B2.z)
    {
        Hit = L1;
        return true;
    }
    if ((GetIntersection(L1.x - B1.x, L2.x - B1.x, L1, L2, ref Hit) && InBox(Hit, B1, B2, 1))
      || (GetIntersection(L1.y - B1.y, L2.y - B1.y, L1, L2, ref Hit) && InBox(Hit, B1, B2, 2))
      || (GetIntersection(L1.z - B1.z, L2.z - B1.z, L1, L2, ref Hit) && InBox(Hit, B1, B2, 3))
      || (GetIntersection(L1.x - B2.x, L2.x - B2.x, L1, L2, ref Hit) && InBox(Hit, B1, B2, 1))
      || (GetIntersection(L1.y - B2.y, L2.y - B2.y, L1, L2, ref Hit) && InBox(Hit, B1, B2, 2))
      || (GetIntersection(L1.z - B2.z, L2.z - B2.z, L1, L2, ref Hit) && InBox(Hit, B1, B2, 3)))
        return true;

    return false;
}

bool GetIntersection(float fDst1, float fDst2, Vector3 P1, Vector3 P2, ref Vector3 Hit)
{
    if ((fDst1 * fDst2) >= 0.0f) return false;
    if (fDst1 == fDst2) return false;
    Hit = P1 + (P2 - P1) * (-fDst1 / (fDst2 - fDst1));
    return true;
}

bool InBox(Vector3 Hit, Vector3 B1, Vector3 B2, int Axis)
{
    if (Axis == 1 && Hit.z > B1.z && Hit.z < B2.z && Hit.y > B1.y && Hit.y < B2.y) return true;
    if (Axis == 2 && Hit.z > B1.z && Hit.z < B2.z && Hit.x > B1.x && Hit.x < B2.x) return true;
    if (Axis == 3 && Hit.x > B1.x && Hit.x < B2.x && Hit.y > B1.y && Hit.y < B2.y) return true;
    return false;
}