兩個普通六面體之間的碰撞檢測

Question

我有兩個六面體。唯一的保證是它們每個都有8個vertex3f（具有x，y和z分量的頂點）。鑑於此，我怎麼才能找出這些是否碰撞？

Answer 1

看來我太笨了，不能退出。

請考慮這一點。如果實體1的任何邊與實體2的任何面相交，就會發生碰撞。這不是很全面，因爲有一種情況是完全包含在另一箇中的情況，您可以通過確定其中一個的中心是否包含在另一箇中來進行測試。

---

檢查邊緣相交這樣工作。

1. 將邊緣定義爲從一個頂點到另一個頂點的向量。注意邊緣的長度，L。
2. 通過頂點，法線，面內基準以及該基礎中其餘頂點的位置來定義平面線段。
3. Find the intersection of the line and the plane。在通常的公式中，您將能夠獲得沿線的長度和交點的平面內座標，其中您選擇了。
4. 交叉點必須長度爲[0,L]，並且必須位於平面中的圖形內。最後一部分有點難度，但有a well known general solution。

這將工作。對於口才，我更喜歡R..'s solution。如果你需要速度......那麼你只需要嘗試一下並看看。

Answer 2

假設你的一個六面體H1的頂點爲(x_1, y_1, z_1), (x_2, y_2, z_2), ...。在每個座標中查找最大值和最小值：x_min = min(x_1, x_2, ...)，x_max = max(x_1, x_2,...)，依此類推。對另一個六面體H2做同樣的事情。

如果間隔[x_min(H1), x_max(H1)]與間隔[x_min(H2), x_max(H2)]不相交（即x_max(H1) < x_min(H2)或x_max(H2) < x_min(H1)），則六面體不可能發生碰撞。對於y和z座標重複此操作。定性地說，這就像看着x軸上每個六面體的陰影。如果它們不重疊，多面體不會相互碰撞。

如果任何間隔確實重疊，則必須繼續進行更精確的碰撞檢測。這將是一個棘手的問題。明顯的蠻力方法是檢查一個邊的任何邊是否與另一個的邊相交，但我想你可以做得比這更好。

蠻力的方法來檢查邊緣是否與臉部相交...首先，您會找到邊線與臉部定義的平面相交的線（例如，參見wikipedia）。然後你必須檢查這個點是否在邊緣和臉上。邊很容易 - 看看座標是否在定義邊的兩個頂點的座標之間。面部更棘手，特別是沒有保證凸面。在一般情況下，你只能看到每個邊所定義的半平面的哪一側。如果它在所有人的內側半平面上，它就在臉上。不幸的是，我現在沒有時間打字，但是我敢打賭，谷歌搜索可以幫助你。但是，當然，這是所有的蠻力，並且可能有更好的方法。 （並且dmckee指出了一個特殊情況，這不起作用）

Answer 3

我很猶豫，在刪除最後一個問題之後，我試圖回答它，並讓我失去了我的文章。請不要再這樣做。無論如何：

不一定是最佳的，但顯然是正確的，基於constructive solid geometry：

1. 表示兩個固體各自的6半空間的交點。請注意，這取決於凸面，但沒有別的，並延伸到具有更多側面的實體。我對半空間的首選表示是選擇每個表面上的一個點（例如，一個頂點）和指向該表面的指向外的單位法線向量。
2. 將所有12個半空間視爲新實體的定義半空間，將兩個實體相交。 （此步驟純粹是概念性的，可能不涉及任何實際代碼。）
3. 計算新固體的表面/邊緣表示並檢查它是否爲非空。這樣做的一種方法是，首先用12個半空間中每一個的一個表面填充表面/邊緣表示，邊界位於2個固體邊界之外，然後將其邊緣與其餘11個半空間中的每一個相交。

這聽起來像是一點工作，但沒有什麼複雜的。只有點積，交叉產品（獲得初始表示）和投影。