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而非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之類的東西來顯式計算路徑，而不是測試所有體素的交點。

Answer 2

由於框是軸對齊的，所以您只需檢查每個座標中的區間交集。

這是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' 

Answer 3

正好有這個存檔足夠的背景（以上問題的答案似乎不包括某些碰撞情況下）：

This question looks to be quite the same, with a good answer.

More detailed, and with a better pre-check here.