给定一个边界框和一条线（两个点），确定该线是否与该框相交

Question

给定一个边界框，其定义如 bounds.min.(x/y/z)、bounds.max.(x/y/z) 以及3D空间（表示为Vector3对象），如何确定两点所构成的线是否与边界框相交？

Answer 1

JavaScript 版本，基于 SpikeX 答案和 glMatrix：

// all args are Vec3, Hit will be filled by this algo
function checkLineBox( B1, B2, L1, L2, Hit)
{
    if (L2[0] < B1[0] && L1[0] < B1[0]) return false;
    if (L2[0] > B2[0] && L1[0] > B2[0]) return false;
    if (L2[1] < B1[1] && L1[1] < B1[1]) return false;
    if (L2[1] > B2[1] && L1[1] > B2[1]) return false;
    if (L2[2] < B1[2] && L1[2] < B1[2]) return false;
    if (L2[2] > B2[2] && L1[2] > B2[2]) return false;
    if (L1[0] > B1[0] && L1[0] < B2[0] &&
        L1[1] > B1[1] && L1[1] < B2[1] &&
        L1[2] > B1[2] && L1[2] < B2[2])
    {
        vec3.set( L1, Hit);
        return true;
    }

    if ((getIntersection(L1[0] - B1[0], L2[0] - B1[0], L1, L2, Hit) && inBox(Hit, B1, B2, 1))
      || (getIntersection(L1[1] - B1[1], L2[1] - B1[1], L1, L2, Hit) && inBox(Hit, B1, B2, 2))
      || (getIntersection(L1[2] - B1[2], L2[2] - B1[2], L1, L2, Hit) && inBox(Hit, B1, B2, 3))
      || (getIntersection(L1[0] - B2[0], L2[0] - B2[0], L1, L2, Hit) && inBox(Hit, B1, B2, 1))
      || (getIntersection(L1[1] - B2[1], L2[1] - B2[1], L1, L2, Hit) && inBox(Hit, B1, B2, 2))
      || (getIntersection(L1[2] - B2[2], L2[2] - B2[2], L1, L2, Hit) && inBox(Hit, B1, B2, 3)))
        return true;

    return false;
}

var temp = vec3.create();
function getIntersection( fDst1, fDst2, P1, P2, Hit)
{
    if ((fDst1 * fDst2) >= 0) return false;
    if (fDst1 == fDst2) return false;

    vec3.subtract(P2, P1, temp);
    vec3.scale( temp, (-fDst1 / (fDst2 - fDst1)));
    vec3.add( temp, P1, Hit);

    return true;
}

function inBox(Hit, B1, B2, Axis)
{
    if (Axis == 1 && Hit[2] > B1[2] && Hit[2] < B2[2] && Hit[1] > B1[1] && Hit[1] < B2[1]) return true;
    if (Axis == 2 && Hit[2] > B1[2] && Hit[2] < B2[2] && Hit[0] > B1[0] && Hit[0] < B2[0]) return true;
    if (Axis == 3 && Hit[0] > B1[0] && Hit[0] < B2[0] && Hit[1] > B1[1] && Hit[1] < B2[1]) return true;
    return false;
}

Answer 2

您可以将边界框表示为 12 个三角形（6 个面各 2 个）。然后你可以检查你的线与每条线的交点。我有一个线-三角形相交函数，但它是为我自己的软件渲染引擎编写的，而不是为 D3D 编写的。如果您需要代码，我可以尝试转换它。

Answer 3

添加 Python 实现。未经广泛测试，请不要依赖它！

from __future__ import annotations  # allow using Vec3 within Vec3
from dataclasses import dataclass


# based on https://gist.github.com/davidnuon/3816736
@dataclass
class Vec3:
    # default of 'inf' means 'unset'
    x: float = float('inf')
    y: float = float('inf')
    z: float = float('inf')

    # String represntation
    def __str__(self):
        return '<%s, %s, %s>' % (self.x, self.y, self.z)

    # Produce a copy of itself
    def __copy(self):
        return Vec3(self.x, self.y, self.z)

    # Signing
    def __neg__(self):
        return Vec3(-self.x, -self.y, -self.z)

    # Scalar Multiplication
    def __mul__(self, number):
        return Vec3(self.x * number, self.y * number, self.z * number)

    # Arithmetic Operations
    def __add__(self, operand):
        return Vec3(self.x + operand.x, self.y + operand.y, self.z + operand.z)

    def __sub__(self, operand):
        return self.__copy() + -operand

    def assign_from(self, another: Vec3):
        self.x = another.x
        self.y = another.y
        self.z = another.z


class Geometry:
    # based on https://stackoverflow.com/a/3235596/913347
    @staticmethod
    def CheckLineBox(B1: Vec3, B2: Vec3, L1: Vec3, L2: Vec3, Hit: Vec3) -> bool:

        def GetIntersection(fDst1: float, fDst2: float, P1: Vec3, P2: Vec3) -> bool:
            if (fDst1 * fDst2) >= 0.0:  # both line values are at same side relative to box side
                return False
            if fDst1 == fDst2:  # can't happen!
                return False
            Hit.assign_from(P1 + (P2 - P1) * (-fDst1 / (fDst2 - fDst1)))
            return True

        def InBox(Axis: int):
            if Axis == 1 and B1.z < Hit.z < B2.z and B1.y < Hit.y < B2.y:
                return True
            if Axis == 2 and B1.z < Hit.z < B2.z and B1.x < Hit.x < B2.x:
                return True
            if Axis == 3 and B1.x < Hit.x < B2.x and B1.y < Hit.y < B2.y:
                return True
            return False

        def VerifyBox():
            # box must be specified correctly with nearest and farthest corners
            ok = B1.x < B2.x and B1.y < B2.y and B1.z < B2.z
            if not ok:
                print('bad box data')
            return ok

        print(f'Box: ({B1}:{B2}), Line: {L1}:{L2}')
        if not VerifyBox():
            return False
        # if at any axis, the line values are before/after the box, return False:
        if ((L2.x < B1.x and L1.x < B1.x) or
                (L2.x > B2.x and L1.x > B2.x) or
                (L2.y < B1.y and L1.y < B1.y) or
                (L2.y > B2.y and L1.y > B2.y) or
                (L2.z < B1.z and L1.z < B1.z) or
                (L2.z > B2.z and L1.z > B2.z)):
            return False
        # if L1 is within the box, return it
        if B1.x < L1.x < B2.x and B1.y < L1.y < B2.y and B1.z < L1.z < B2.z:
            Hit.assign_from(L1)
            return True
        if ((GetIntersection(L1.x - B1.x, L2.x - B1.x, L1, L2) and InBox(1))
                or (GetIntersection(L1.y - B1.y, L2.y - B1.y, L1, L2) and InBox(2))
                or (GetIntersection(L1.z - B1.z, L2.z - B1.z, L1, L2) and InBox(3))
                or (GetIntersection(L1.x - B2.x, L2.x - B2.x, L1, L2) and InBox(1))
                or (GetIntersection(L1.y - B2.y, L2.y - B2.y, L1, L2) and InBox(2))
                or (GetIntersection(L1.z - B2.z, L2.z - B2.z, L1, L2) and InBox(3))):
            return True

        return False


g = Geometry()
hit = Vec3()
rc = g.CheckLineBox(Vec3(0, 0, 0), Vec3(3, 3, 3), Vec3(-1, -1, -1), Vec3(0.1, 0, 0), hit)
print(f'rc={rc}, hit={hit}')

Answer 4

这里有一个在线 C++ 实现：Line Box Intersection ( http://www.3dkingdoms.com/weekly/weekly.php?a= 3）

另一个链接，包含大量交叉测试的参考（和代码）：http: //www.realtimerendering.com/intersections.html

如果您想了解有关相交测试的更多信息，这就是圣经：实时碰撞检测 (Amazon)

编辑：此 论文（“一种高效且鲁棒的射线盒相交算法”，Amy Williams 和 Steve Barrus 以及 R. Keith Morley 和 Peter Shirley；图形、GPU 和游戏工具杂志，第 1 卷） 10(1), 49-54, 2005) 看起来特别简洁，并且还附带 (C++) 源代码。

Answer 5

如果您想自己进行数学计算，可以采用以下一种方法：将线与边界框创建的 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 + tdx、y = y1 + tdy、z = z1 + t* dz，替换平面方程中的 x、y 和 z。求解 t。由于 6 个平面中的每一个都将平行于由 2 个轴创建的平面，因此您的问题变得更容易；例如，对于与 x 和 y 轴创建的平面平行的平面，平面方程只需变为 z = c，而 c 是边界框点之一的 z 坐标，依此类推。

现在使用 t 计算直线与平面的交点。 （如果 t < 0 或 > 1，则您的线在 P1-P2 外部相交，如果 t >= 0 且 t <= 1，则您的线与 P1 和 P2 之间的某个平面相交）

现在您'还没有完成。平面方程给出了一个平面，而不是一个矩形，因此与平面的交点实际上可能在矩形之外，但由于您现在有了交点的坐标（x = x1 + t * dx 等等），您可以轻松查看该点是否在边界框的矩形内。现在，您的问题减少为检查 2D 空间中的点是否位于边界框矩形内，这很容易检查。

当然，如果您实际使用此解决方案，您应该做的第一件事是检查该线是否也沿一个轴对齐，因为在这种情况下，您的相交代码变得微不足道，并且它还将解决线不相交的问题一些平面，例如大量或少量的t，甚至可能上溢或下溢。

我敢打赌有更快的方法可以做到这一点，但它会起作用。

Answer 6

这是似乎有效的代码，从 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;
}