查找兩個三角形是否相交或不

（（X1，Y1，Z1），（X2，Y2，Z2），（X3，Y3，Z3））和

（（p1，q1，r1），（p2，q2，r2），（p3，q3，r3））在3D空間中形成三角形。

如何找出這些三角形是否相交？

這個問題的一個明顯的解決方案是找到由每個三角形形成的平面方程。如果平面平行，則它們不相交。

否則，用這些平面的法向矢量找出由這些平面相交形成的直線方程。

現在，如果這條線位於兩個三角形區域中，那麼這兩個三角形相交，否則不相交。

trianglesIntersect(Triangle T1, Triangle T2) 
{ 
    if(trianglesOnParallelPlanes(T1, T2)) 
    { 
     return false 
    } 
    Line L1 = lineFromPlanes(planeFromTriangle(T1), planeFromTriangle(T2)) 
    if(lineOnTriangle(T1, L1) AND lineOnTriangle(T2, L1)) 
    { 
     return true 
    } 
    return false 
}

既然我知道怎麼寫上面的功能，我應該考慮什麼trianglesIntersect的其他實現？

有沒有更快的算法來解決這個問題？訪問禮貌realtimerendering.com

來源

2011-08-18 Atishay

嘗試詢問[math.stackexchange.com]（http://math.stackexchange.com））代替。 SO是編程問題。 – PengOne

http://www.applet-magic.com/trintersection.htm – Jacob

+17

我很失望，這個問題已經結束。這是一個衆所周知的編程問題，在計算機圖形學，光線追蹤，視頻遊戲等方面出現。我已經不止一次地編寫了它。這怎麼可能成爲題外話題？ –

this table of geometric intersection algorithms，看看在三角形/三角形交叉進入，並遵循引用，例如克里斯特埃裏克森，Real-Time Collision Detection，172頁（一本書，我建議高度。）

的基本想法很簡單。如果兩個三角形相交，則一個三角形的任意兩個邊相交（下圖中的左邊配置），或者每個三角形的一個邊相交（右邊的配置）。

enter image description here

所以執行的六個線段 - 三角形相交測試，看看是否任一這些結構的發現。

現在，你問，你怎麼做一個線段/三角形的交叉點測試？好吧，這很容易。請訪問this table of geometric intersection algorithms，查看線段（射線）/三角形交點的條目，並參考參考文獻...

（重要的是要提到上面簡單的測試不能正確處理共面三角形。這並不重要：例如，當檢測到三角形網格之間的碰撞時，共面情況是不明確的，因此返回哪個結果並不重要，但是如果您的應用程序是例外情況之一，則需要檢查作爲一種特殊情況，或者在Ericson上閱讀其他一些方法，例如separating-axis method或TomasMöller的interval overlap method。）

來源

2011-08-19 20:12:48

共面三角形（相當容易用平面方程檢測，用normal1 == normal2 __and__ d1 == d2）可以很容易地用[ptInPoly測試使用重心座標]進行測試（http://gamedev.stackexchange.com/questions/23743/什麼是最有效的方式找到重心座標）在所有三角形的角落。 – bobobobo

順便說一下，[穆勒的區間重疊方法在這裏]的C代碼（http://web.archive.org/web/19990203013328/http://www.acm.org/jgt/papers/Moller97/tritri.html ）。 – bobobobo

查找兩個三角形是否相交或不

回答

相關問題