與軌跡網格碰撞

Question

我想避免我的玩家能夠站在牆內。每個遊戲都會勾選我的玩家移動一些小距離和/或旋轉。

TL; DR請提供經典線段的變體 - > - 三角形相交算法太返回近乎理想的，或以另一種方式線段如果它通過內相交解決問題給定三角形的距離。這個問題有很多微妙之處，比如三角形的軌跡拐角是圓形的，以及線段是否與三角形相切。

我有通常的射線/三角相交碼。

但是，射線對移動的玩家來說是一個非常糟糕的近似值！我的球員中鋒缺少邊緣，但球員網格穿過他們。

你如何有效地確定何時何地玩家與牆壁和障礙物在3D環境中發生碰撞？

一種通用方法是將具有接近未命中三角形代碼，其中該射線是球封端的圓筒。

我試過的一般解決方案是想象玩家是一個球體，把它從裏面翻出來，我試圖做出一個比實際的牆壁更大的半徑的網格，並且在那裏做碰撞射線。我想計算一個在這個網格前面的固定距離的網格，也就是說一個立方體會展開成一個稍大的具有圓形邊和角的立方體。 （我的網格比立方體更不規則，想象一下鍋爐房內部的網格表示，想象一下計算一個距離所有牆壁和鍋爐以及門框等20釐米的網格的那個網格）。這裏是在每桶一個簡單的目：

對於每個面我可以計算表面法線;這就是我知道哪種方式是'出'的。

我的頭腦風暴讓我想象乘以每個面的法線由固定距離，然後發射具有相應偏移量的三角形。

但這會在邊緣處留孔和便叫（？）會導致一些邊經過很緊銳角？

我也可以想象，將每個邊連接成球頭圓柱體等等。

我用於上述槍管的方法是計算平均正常所有面共享一個頂點，然後乘上碰撞半徑。它不能很好地處理銳角，以及如果頂點在相反兩側的面之間錯誤地共享，該怎麼辦？

我將計算這一目，然後執行射線的交點，在Javacsript。所以性能也是一個考慮因素。一個太細的網格物體在進行碰撞檢測時會很昂貴。

如何有效地計算一個足夠好的位點網格？或者做位點感知的模糊三角形交集？或者是否有更好的方法來完成碰撞，並且可以以某種方式模擬物體以弧線而不是直線移動？

Answer 1

（沒有人拿起賞金:(Nathan Reed on gamedev.stackexchange幫助的術語。它叫膠囊三角形十字路口。）

它令人驚訝的棘手的數學和谷歌搜索沒有找到許多現成的代碼複製。

A standard way是要擠出這個三角形的半徑，加上也測試三個三角形邊緣的每一個作爲膠囊。

要擠出三角形，只需將三角形的法線乘以膠囊半徑，然後將每個三角形角落偏移該量，然後對其進行法線三角測試。

每個三角形邊緣的膠囊測試是相當昂貴的，因爲你必須做三次。有可能使用三角測試中的重心座標有助於避免一些膠囊邊緣測試，但我沒有想到這一點。您還可以避免在與其他三角形共享的邊緣上進行膠囊測試，這些三角形足夠鈍;你可以計算這個並標記這些邊緣。我還沒有打擾過（還）。

我發現預先計算每張臉的邊界球並且與膠囊的邊界球進行相交測試是一種超便宜的方法，可以在大多數情況下避免這種昂貴的測試。我還預先計算了每張臉的法線，儘管這是一個較小的勝利。

由於測試如此昂貴，最好的辦法是將玩家視爲單一球體並讓十字路口代碼給出一張面部交叉點列表。然後，您可以將該玩家建模爲一系列飛行較小的球體，並且您只需爲面向第一次發現較大球體的面做膠囊面交叉點代碼。