3D线段框相交

Question

寻找代码以检测3D线段（不是线/射线）与3D盒子（不一定是立方体，但总是轴对齐）之间的交点。这些盒子是体素，因此它们具有规则的间距。

已经有了查找线段/平面交点的代码。理想情况下，我希望能够找到一个有效的解决方案来适应矩形，针对3D盒子的每个面进行重复，并且然后迭代成千上万次的线段和盒子。

seg_start = array([x1,y1,z1])
seg_end = array([x2,y2,z2])
plane_point = array([x3,y3,z3])
plane_normal = array([x4,y4,z4])
u = seg_end - seg_start
w = seg_start - plane_point
D = dot(plane_normal,u)
N = -dot(plane_normal,w)
sI = N / D
if sI >= 0 and sI <= 1:
    return 1

- jbrown

Answer 1

首先，您可能是想用and而不是or来表示if条件，否则它将始终返回true。其次，如果您只是测试是否存在交集，您可以更快地完成它（无需使用浮点除法）：

• You can determine which "side" of each plane any given point is on using vector math:
  side = dot(my_point - plane_point, plane_normal)
  Now if side is positive, my_point is "in front of" the plane (i.e. it's on the side the normal is pointing towards); if negative, it's "behind" the plane. If side is zero, your point lies on the plane.

• You can check whether your segment intersects an (infinite) plane by just testing to see if the start point and end point are on different sides:

  start_side = dot(seg_start - plane_point, plane_normal)
  end_side = dot(seg_end - plane_point, plane_normal)
  return start_side * end_side
  #if < 0, both points lie on different sides, hence intersection
  #if = 0, at least one point lies on the plane
  #if > 0, both points lie on the same side, i.e. no intersection
  

• You can use the "side" check to do the axis-aligned-cuboid intersection too (actually, this will work for any parallelpiped):

  • Treat your box as a set of six planes
  • Make sure the plane normals are all pointing either "outwards" or "inwards" from the box. I'll assume you're using "outwards"
  • For any point to lie inside your box, it has to be "behind" all six planes. If it isn't, it lies outside the box.
  • For any segment to intersect the box, one point has to lie outside it and one inside.
  • That's all!

编辑： 最后一点实际上是错误的；正如你所说，即使两个端点都在外面，体素也可以相交。因此这不是整个解决方案 - 实际上，你不能真正做到这一点而不计算交点。但是，您仍然可以使用“侧面测试”作为早期拒绝机制，以减少需要进行完整计算的数量：如果两个点在任何一个六个平面的同一侧，就不可能有交点。

就您具体的情况而言，似乎您正在尝试找到某个给定线段的所有相交体素？在这种情况下，您最好使用类似于Bresenham算法来明确计算路径，而不是针对所有体素测试相交...

- tzaman

---

谢谢 - 非常有帮助！如果线段的两个点位于不相邻的体素中，并且我想测试线段是否与中间的体素相交（通过该线段通过，但两个点都在外面），该怎么办？ - jbrown

@jbrown - 是的，我也意识到了；我已经修改了我的答案，请看一下。 - tzaman

为了后人的参考：Bresenham算法不能返回线段相交的每个盒子。如果这些盒子形成像素化的网格，那么可以轻松修改一个简单的算法，沿着3D线段均匀采样点并返回它所击中的盒子，以返回线段相交的所有盒子。假设采样足够密集，在每个步幅处，必须检查与前一个体素相比增加了多少维度。如果2或3个维度不同，则可以显式地检查潜在遗漏的体素（仅在一个维度上与前一个或下一个体素相差1）。 - Greg Kramida

这是一个针对显式网格对齐框检查的算法：https://dev59.com/1E7Sa4cB1Zd3GeqP5KJn#59074742 - Greg Kramida

Answer 2

为了有足够的背景存档（上面的答案似乎没有包括一些碰撞情况）：

这个问题看起来非常相似，有一个很好的答案。

更详细，并且在此处进行更好的预检查。

- mike

---

第二个链接很遗憾地已经失效。 - undefined

Answer 3

由于盒子是轴对齐的，所以你只需要在每个坐标上检查区间交集。

下面是一个Python示例，并附有一些测试。请注意，它适用于N个维度，并且是盒子盒子相交的相同算法：

def are_intervals_intersecting(a0, a1, b0, b1):
    '''
    @param a0: float
    @param a1: float
    @param b0: float
    @param b1: float
    '''
    if (a1 < a0):
        a1, a0 = a0, a1

    if (b1 < b0):
        b1, b0 = b0, b1

    # 6 conditions:

    # 1)
    #        a0 ---------- a1                              a0 < b0 and a1 < b0
    #                             b0 ---------- b1         (no intersection)

    # 2)
    #               a0 ---------- a1
    #                      b0 ---------- b1                (intersection)

    # 3)
    #               a0 ------------------------ a1
    #                      b0 ---------- b1                (intersection)

    # 4)
    #                      a0 ---------- a1         
    #               b0 ------------------------ b1         (intersection)

    # 5)
    #                             a0 ---------- a1         (intersection)
    #                      b0 ---------- b1

    # 6)
    #                                    a0 ---------- a1  b0 < a0 and b1 < a0         
    #               b0 ---------- b1                       (no intersection)

    if b0 < a0:
        # conditions 4, 5 and 6
        return a0 < b1 # conditions 4 and 5
    else:
        # conditions 1, 2 and 3
        return b0 < a1 # conditions 2 and 3


def is_segment_intersecting_box(P0, P1, B0, B1):
    '''
    @param P0: tuple(float)
    @param P1: tuple(float)
    @param B0: tuple(float)
    @param B1: tuple(float)
    '''
    for i in xrange(len(P0)):
        if not are_intervals_intersecting(P0[i], P1[i], B0[i], B1[i]):
            return False
    return True


if __name__ == '__main__':
    assert not is_segment_intersecting_box(
        (0.0, 0.0, 0.0), (1.0, 1.0, 1.0), (2.0, 2.0, 2.0), (3.0, 3.0, 3.0))

    assert not is_segment_intersecting_box(
        (0.0, 0.0, 0.0), (4.0, 1.0, 1.0), (2.0, 2.0, 2.0), (3.0, 3.0, 3.0))

    assert not is_segment_intersecting_box(
        (1.5, 1.5, 0.0), (4.0, 2.5, 1.0), (2.0, 2.0, 2.0), (3.0, 3.0, 3.0))

    assert is_segment_intersecting_box(
        (1.5, 1.5, 0.0), (4.0, 2.5, 2.5), (2.0, 2.0, 2.0), (3.0, 3.0, 3.0))

    assert is_segment_intersecting_box(
        (1.5, 1.5, 1.5), (2.5, 2.5, 2.5), (2.0, 2.0, 2.0), (3.0, 3.0, 3.0))

    assert is_segment_intersecting_box(
        (2.5, 2.5, 2.5), (2.6, 2.6, 2.6), (2.0, 2.0, 2.0), (3.0, 3.0, 3.0))

    assert is_segment_intersecting_box(
        (2.5, 2.5), (2.5, 3.5), (2.0, 2.0), (3.0, 3.0))

    print 'ok'

- e.tadeu

---

一个更简单的区间测试是 (a0 < b1) and (b0 < a1)。 - e.tadeu

由於盒子是軸向對齊的，你只需要在每個坐標上檢查間隔是否相交。這是錯誤的。考慮盒子(0, 0), (2, 2)和線段(-1, 2), (2, -1)，它們相交，但你的代碼對於兩者都返回了True。而線段(-2, 1), (1, -2)不相交，但你的代碼也返回了True。 - Artyom