如何將線段裁剪爲平截頭體？

Question

給出兩個載體A和B其形成線段L = A-B。 此外給定一個視錐體F它由左，右，下，上，近，遠平面定義。

我該如何剪輯L針對F？

也就是說，測試一個十字路口和哪裏就是那個路口發生？ （請注意，線段可以有一個以上的交叉點更與平截頭體，如果它在角部相交兩側。）

如果可能的話，提供一個代碼示例請（C++或Python優選的）。

Answer 1

我現在不想爲此編寫代碼，但如果我正確理解「平截頭體」，以下方法應該可以工作。

1. 相交都給飛機
2. 如果你有兩個交點大功告成線。
3. 如果只有一個交點計算前平面並相交。
4. 如果您仍然只有一個交點計算背板並相交。

但我可能完全誤解了。在這種情況下，請詳細說明:)

Answer 2

除了上文所述的下士Touchy，您還需要know how to intersect a line segment with a plane。在該頁面的描述中，u代表線路參數定義中的參數。首先，使用所描述的兩種方法之一來計算u。如果u的值落在0.0到1.0的範圍內，那麼該平面會將線段剪切到您網段上的某處。將u再插回到你的直線方程中可以給出你交點發生的位置。

另一種方法是找到飛機上每個點的directed distance。如果一點的距離是正值，另一點是負值，則它們位於飛機的兩側。然後你知道哪個點在你的平截頭體之外（基於你的平面正常點的哪個方向）。使用這種方法，通過基於定向距離的比例進行線性插值可以更快地找到交點。例如。如果一個點的距離爲+12，另一個點的距離爲-12，那麼您知道該平面會將該線段切成兩半，而您的u參數爲0.5。

希望這會有所幫助。

Answer 3

第一extract the planes from your view matrix。

然後用你的觀點定義一個向量，並將最小/最大值定義爲（0,1），然後迭代平面並將它們與該段相交，更新最小/最大值，如果min > max提前退出。

下面是一個純Python函數的例子，沒有外部代碼。

def clip_segment_v3_plane_n(p1, p2, planes): 
    """ 
    - p1, p2: pair of 3d vectors defining a line segment. 
    - planes: a sequence of (4 floats): `(x, y, z, d)`. 

    Returns 2 vector triplets (the clipped segment) 
    or (None, None) then segment is entirely outside. 
    """ 
    dp = sub_v3v3(p2, p1) 

    p1_fac = 0.0 
    p2_fac = 1.0 

    for p in planes: 
     div = dot_v3v3(p, dp) 
     if div != 0.0: 
      t = -plane_point_side_v3(p, p1) 
      if div > 0.0: # clip p1 lower bounds 
       if t >= div: 
        return None, None 
       if t > 0.0: 
        fac = (t/div) 
        if fac > p1_fac: 
         p1_fac = fac 
         if p1_fac > p2_fac: 
          return None, None 
      elif div < 0.0: # clip p2 upper bounds 
       if t > 0.0: 
        return None, None 
       if t > div: 
        fac = (t/div) 
        if fac < p2_fac: 
         p2_fac = fac 
         if p1_fac > p2_fac: 
          return None, None 

    p1_clip = add_v3v3(p1, mul_v3_fl(dp, p1_fac)) 
    p2_clip = add_v3v3(p1, mul_v3_fl(dp, p2_fac)) 

    return p1_clip, p2_clip 


# inline math library 
def add_v3v3(v0, v1): 
    return (
     v0[0] + v1[0], 
     v0[1] + v1[1], 
     v0[2] + v1[2], 
     ) 

def sub_v3v3(v0, v1): 
    return (
     v0[0] - v1[0], 
     v0[1] - v1[1], 
     v0[2] - v1[2], 
     ) 

def dot_v3v3(v0, v1): 
    return (
     (v0[0] * v1[0]) + 
     (v0[1] * v1[1]) + 
     (v0[2] * v1[2]) 
     ) 

def mul_v3_fl(v0, f): 
    return (
     v0[0] * f, 
     v0[1] * f, 
     v0[2] * f, 
     ) 

def plane_point_side_v3(p, v): 
    return dot_v3v3(p, v) + p[3]