碰撞檢測超出交集測試

Question

爲了說明這一點的目的，設想一個二維遊戲，玩家可以控制一個可以賦予任意速度的小精靈。它只受重力作用。它最初位於屏幕底部大部分的大平臺上，而在它上面的一小段距離是另一個更小的平臺。如果精靈直線向上跳，它將能夠穿過平臺的底部，在其上方行進一段時間，然後下降並落在上部平臺的頂部。它可以穿過底部，但不能穿過頂部。

可以通過在屏幕上查看每個實體邊緣作爲可以從右側，左側或兩側傳遞的矢量來做到這一點;在這個例子中，你需要一個邊緣作爲主基礎平臺的頂部（如果它從右角指向左角，那麼它將是不可滲透的），另一個用於較小平臺的頂部，還有更多對於精靈（四個，如果它是一個小矩形）。如果一個點以錯誤的方式通過邊緣，它會發送一個信號給衝突解決算法，以確保該點不會這樣做。

這一切都奏效奇妙，唯一的問題是效率不高。使用傳統的碰撞檢測機制，正方形是一個對象。如果你有一個n正方形來測試碰撞之間的列表，你必須運行 - 至多;大多數方法縮小這個數字 - n平方碰撞測試。使用點邊緣方法，每個正方形都有四條邊，每條邊都有兩個要測試的端點。這意味着對於n正方形，您將運行約（8 n）平方碰撞測試。碰撞測試次數的64倍;這太可怕了。

那麼，有沒有什麼廣泛使用或者更爲接受的碰撞檢測方法可以實現與點邊緣方法相同的功能，但是不會過度加重計算機的處理能力？請注意，這隻適用於2D;它意味着讓事物圖層代表一種軸內的形式，而3D完全能夠表示空間的所有三個維度並且不需要增強。

Answer 1

這通常使用邊界框的四叉樹完成。樹的每個節點都有包圍其直接子節點的邊界。對於n節點，您將最多需要k日誌（n）比較。這是一個二維搜索。

注意邊界框不一定完全對應您的方格。他們通過範圍比較爲便宜的命中測試對齊網格。

一旦你擊中了某個原子的邊界框，就對該原子進行完全命中測試。

這種方法最常與多邊形命中測試結合使用，對於具有多邊的多邊形（不稱爲複雜多邊形，複雜多邊形是與相交邊「扭曲」的多邊形）相當昂貴。