使用多邊形碰撞檢測

Question

我想知道是否有人可以給我一個關於如何首先實現一個類來定義多邊形的想法，以及如何檢測使用這個類的兩個多邊形之間的碰撞。我在Android上的Java工作是更具體的，但我也可以使用NDK的C/C++。我想要定義我的多邊形，我只需要一個頂點數組吧？

當我做碰撞檢測時，我已經閱讀了有關分離軸定理和GJK算法的內容。這是正確的路要走，還是我讓這個過於複雜？只是試圖開始正確的方向。謝謝！

Answer 1

你聽起來像是你對這種事情相當陌生，這也許是你意識到的一個更大的問題。

我認爲你最好先定義你想要解決的問題，然後找到一個解決方案來解決這個問題。

讓我問你一些問題預選賽：

你說的是2D還是3D？

這是用於物理系統嗎？

你需要知道它們相交的地方嗎？或者只是它們相交？

你需要做的形狀布爾操作（如獲得交集或聯合或東西）？

Answer 2

這取決於多邊形的類型。

如果你的多邊形是凸的，那麼一個有序的頂點列表將描述一個，而分離軸和GJK都將是可應用的算法。

如果你的多邊形是凹的但是簡單的（即，邊從不相交），那麼有序的頂點列表仍然足夠，但是分離軸或GJK都不適合。

如果你的多邊形是複雜的（即邊可能相交），那麼你需要頂點列表和填充規則。該規則確定哪些部分的飛機被認爲是在多邊形內部，哪些在外部。

例如，假設像五角星的多邊形：

在填充規則的區別在於在中間的五邊孔是多邊形的部分或簡單的孔的差。

所有更復雜的多邊形類型都可以分解爲多種簡單多邊形的多個實例，因此只需在地面放置一面旗幟並聲明您只對凸多邊形感興趣就可以了 - 這就是例如，GPU正是如此。

假設您將碰撞定義爲兩個多邊形是否重疊，分離軸定理非常簡單，而且絕對是一種可行的方法。如果你打算製作一個包含很多多邊形的場景，那麼你可能還需要一個寬泛的階段，這是一個快速的方法來標記一堆多邊形，因爲在做昂貴的測試之前，它們絕對不會重疊，以找出哪個多邊形其餘的仍然是。

一個明顯的例子是bin排序 - 假設你將屏幕劃分爲16個像素的垂直條，然後對每個多邊形進行分類（i）確定它接觸的是哪個bin; （ii）針對已經在這些箱中的所有多邊形進行測試; （iii）將其添加到垃圾箱。這可能意味着你甚至從來沒有考慮過很多時候應用這個測試。這個具體的方案有一些明顯的問題，取決於你的場景，但存在更智能的算法。