logo标签列表

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

c#mathvectorc#-2.0
10

给定一个边界框，定义如下：bounds.min.(x/y/z)，bounds.max.(x/y/z)，以及两个在3D空间中的点（表示为Vector3对象），我该如何确定由这两个点组成的直线是否与边界框相交？

6个回答
12

这里有一个C++实现的在线版本：线框交叉(http://www.3dkingdoms.com/weekly/weekly.php?a=3)

另一个链接，提供了许多交叉测试的参考文献和代码：http://www.realtimerendering.com/intersections.html

如果您想了解更多关于交叉测试的内容，这本书是圣经：实时碰撞检测（亚马逊）

编辑：这篇论文中的算法（一种高效且强大的光线盒相交算法，Amy Williams、Steve Barrus、R. Keith Morley和Peter Shirley；图形、GPU和游戏工具杂志，第10卷（1），49-54，2005年）看起来特别简洁，并且也附带有（C++）源代码。

1
在将第一个链接中的代码转换为不那么丑陋的C++之后，它似乎大部分都能正常工作。我会在这里发布代码，供其他需要的人使用，这样他们就不必再进行转换了。 - qJake
7
这是一种自己计算的方法，如果你想要这么做的话：将该线与由边界框创建的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 = z1 + t * dz，将x、y和z替换到您的平面方程中。解决t。由于您的6个平面中的每一个都将与由2个轴创建的平面平行，因此您的问题变得更容易；例如对于与x轴和y轴创建的平面平行的平面，您的平面方程简单地变为z = c，其中c是您的边界框点之一的z坐标，以此类推。
现在使用t来计算线与平面的交点。（如果t < 0或t > 1，则您的线与P1-P2之外相交；如果t >= 0且t <= 1，则您的线在P1和P2之间某处与平面相交）
现在你还没有完成。平面方程给出了一个平面而不是矩形，因此与平面相交的点实际上可能在您的矩形之外，但由于您现在有了交点的坐标（例如x = x1 + t * dx等），因此您可以轻松地看到该点是否在您的边界框矩形内。现在，您的问题已经简化为检查二维空间中的点是否在边界框矩形内，这很容易检查。
当然，如果您实际使用此解决方案，您应该首先检查该线是否也沿着一个轴对齐，因为在这种情况下，您的交点代码变得微不足道，并且它还将处理线未与某些平面相交的问题，例如巨大或微小的t数量，甚至可能会发生溢出或下溢。我敢打赌有更快的方法来做到这一点，但它会起作用。
如果有更快的方法，我需要知道它们，因为这段代码将在每秒运行多达100次，并且我添加的每个计算都会减慢游戏速度。 - qJake
嗯，实际上我认为你发布的算法比我提出的更慢，因为它似乎使用向量进行计算，例如每次调用GetIntersection时需要执行大量加法和四次乘法，因为它没有优化你的边界框与坐标系对齐这一事实，这意味着你可以在每个平面交点处舍弃三个参数方程中的两个。我认为你可以通过每个交点进行单次乘法来解决问题。 - JeSuisse
抱歉，不好意思。忽略那个。你需要进行三次乘法才能计算出击中的坐标。该死。 - JeSuisse
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;
}
12年后我在思考：如果GetIntersection的第一个条件不匹配，第二个条件怎么可能匹配呢？ - ishahak
@ishahak 我几乎逐字复制了 C++ 代码，只是将其翻译成了 C#。我相信那些 if 语句可以合并或重新排序，以获得更高的效率，但这并没有影响我当时正在制作的游戏的性能。 - qJake
2

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

// 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;
}
1

你可以将包围盒表示为12个三角形（每个面2个）。然后，你可以检查你的线段与它们中的每一个的相交情况。我有一个线段-三角形相交函数，但它是为我的自己的软件渲染引擎编写的，而不是为D3D编写的。如果你需要代码，我可以尝试转换它。

我可以做这个，但我不知道它的性能如何...它每次“更新”都会运行很多次，每秒钟很多次，我不确定它会表现如何，但值得一试。如果您发布线/三角形相交的代码，并且我可以让它正常工作（而且不慢），我会给您的。 - qJake
0

添加一个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://dev59.com/Pk_Sa4cB1Zd3GeqP8gea#3235596
    @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}')
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接