python - 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
  

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

  • 将您的盒子视为一组六个平面
  • 确保平面法线都指向盒子“向外”或“向内”。我假设您使用的是“向外”
  • 要使任何点位于您的框内，它必须位于所有六个平面“后面”。如果不是，则它位于框外。
  • 对于与框相交的任何线段，一个点必须位于框外，一个点位于框内。
  • 就是这样!

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

就您的具体情况而言，您似乎正在尝试为某个给定的线段找到所有相交的体素？在那种情况下，使用类似 Bresenham's 的内容可能会更好。显式计算路径，而不是针对所有体素测试交叉点...