高效地確定3D盒的交集

Question

我想開發一種算法來確定這兩個盒子（但我認爲它適用於任何凸多面體）相交。我將用它來進行碰撞檢測。

每個多面體的狀態表示爲其質心的平移向量和一個方向矩陣（3×3正交表示對象空間座標）。

我的一般想法是取兩個多面體的每個面，找出它的平面方程（應用多面體方向和平移分量），並遍歷另一個多面體的每個頂點，並確定是否他們全都在飛機的同一側，如果是，我確定這兩個物體不相交。

至於碰撞檢測部分，我會檢測它們是否相交，如果他們這樣做，我會在它們碰觸的時刻進行二分搜索，並嘗試在那一刻通過查找另一個對象的頂點來找到碰撞的頂點這與我之前發現的確定接觸點的平面最接近。

我的問題是，這個算法是否正確，如果是的話，這是否是一種矯枉過正？我能以某種方式抽出一些檢查，或加快進程？

Answer 1

我認爲你的算法是正確的，並且與你將要獲得的效率一樣。要清楚你需要檢查的每一個面多面體，並且如果你發現任何情況下，其他多面體的每個頂點都在無限平面的「外部」，那麼就沒有交點。

出於性能：

1預先計算的封閉領域，所以你可以做一個最初的「粗」檢查

2預先計算的所有外向法向量，並通過你的旋轉進行改造他們 - 應該比做更便宜一堆交叉產品，

找到相交的「點」我認爲可以使用相同的算法完成，並假定相交狀態和非相交狀態之間存在線性插值，並尋找一個頂點恰好位於一個平面上的解決方案。