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

首先，你的 if 条件中可能指的是

and

而不是

or

，否则它总是返回 true。其次，如果您只是测试是否存在交集，您可以做得更快（无需浮点除法）：

• 您可以使用向量数学确定任何给定点位于每个平面的哪“一侧”：
  

  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
  

• 您也可以使用“侧面”检查来进行轴对齐长方体相交（实际上，这适用于任何平行六面体）：

  • 将您的盒子视为一组六个平面
  • 确保平面法线全部指向盒子“向外”或“向内”。我假设你使用的是“outwards”
  • 对于位于盒子内的任何点，它必须位于所有六个平面“后面”。如果不是，它就在盒子外面。
  • 对于与盒子相交的任何线段，一个点必须位于盒子外部，一个点位于盒子内部。
  • 仅此而已！

编辑： 最后一点实际上是不正确的；正如你所说，即使两个端点都位于外部，体素也可以相交。所以这不是完整的解决方案 - 实际上，如果不计算交点，你就无法真正做到这一点。但是，您仍然可以使用“侧面测试”作为early-reject机制，以减少需要执行的完整计算的数量：如果两个点位于任何一个的同一侧六个平面中不能有交集。

就您的具体情况而言，您似乎正在尝试查找某些给定线段的所有相交体素？在这种情况下，您可能会更好地使用类似 Bresenham's 的方法来显式计算路径，而不是测试所有体素的相交...

Answer 2

只是为了让这个存档有足够的背景（上面的答案似乎不包括一些碰撞案例）：

这个问题看起来很相似，答案很好。

本文通过第15-19页的图片和描述来解释问题。

随着时间的推移，链接变坏了

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'