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

首先，你的意思可能and不是orif 条件，否则它总是返回 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”
  • 对于位于盒子内的任何点，它必须位于所有六个平面的“后面” 。如果不是，它就位于盒子外面。
  • 对于与盒子相交的任何线段，一个点必须位于盒子外部，一个点位于盒子内部。
  • 就这样！

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

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