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

Answer 1

因为这个盒子是和坐标轴对齐的，所以你只需要检查每个坐标的区间是否相交就可以了。

下面是一个用Python写的例子，还有一些测试。请注意，这个方法适用于任意维度，而且盒子之间相交的算法是一样的：

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'

Answer 2

为了把这个问题记录下来，提供一些背景信息（上面的回答似乎没有涵盖一些碰撞情况）：

这个问题看起来和前面提到的很相似，而且有个不错的答案。

在这篇论文中，问题通过图片和描述在第15到19页进行了详细解释。

这个链接随着时间的推移已经失效了

Answer 3

首先，你可能在你的条件判断中应该用 and 而不是 or，否则它总是会返回真。其次，如果你只是想测试是否有交点，其实可以更快地做到这一点（不需要浮点除法）：

• 你可以用向量数学来判断每个平面上某个点在哪一侧：
  side = dot(my_point - plane_point, plane_normal)
  如果 side 是正数，说明 my_point 在平面的“前面”（也就是在法线指向的那一侧）；如果是负数，说明它在平面的“后面”。如果 side 是零，说明你的点正好在平面上。

• 你可以通过检查起点和终点是否在不同的侧面来判断你的线段是否与一个（无限的）平面相交：

  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
  

• 你也可以用“侧面”检查来判断轴对齐的立方体是否相交（其实这对任何平行六面体都适用）：

  • 把你的盒子看作是六个平面的集合
  • 确保这些平面的法线都是指向盒子的“外面”或“里面”。我假设你是用“外面”
  • 要让某个点在你的盒子里，它必须在所有六个平面的“后面”。如果不在，那它就在盒子外面。
  • 要让某个线段与盒子相交，必须有一个点在外面，一个在里面。
  • 就这样！

编辑：最后一点其实是错误的；正如你所说，即使两个端点都在外面，体素也可以相交。所以这并不是完整的解决方案——实际上，如果不计算交点，你是无法做到这一点的。不过，你仍然可以使用“侧面测试”作为一种 提前拒绝 的机制，这样可以减少需要进行的完整计算次数：如果两个点在任意一个六个平面上的同一侧，就不可能有交点。

至于你的具体情况，看起来你是想找出某条给定线段的所有相交体素？在这种情况下，使用类似于 Bresenham's 的算法来明确计算路径，可能会更有效，而不是对所有体素进行交点测试……