四叉樹用於二維碰撞檢測

Question

我試圖用四叉樹進行二維碰撞檢測，但我對如何實現它有點難住。首先，我會有一個四叉樹，其中包含四個子樹（一個代表每個象限），以及一個不適合單個子樹的對象集合。

當檢查樹碰撞的對象，我會做這樣的事情（感謝QuadTree for 2D collision detection）：

1. 檢查對象的碰撞與當前節點的任何對象。
2. 對於其空間與對象重疊的任何子樹，遞歸。

要找到一個四叉樹中的所有碰撞：

1. 入住針對當前節點互相對象的當前節點的每個對象。
2. 檢查每個子樹中當前節點中的每個對象。

要插入一個四叉樹：

1. 如果對象適合多個子樹，然後將其添加到當前節點，並返回。
2. 否則，遞歸到哪個子樹包含它。

要更新的四叉樹：

1. 遞歸到每個子樹。
2. 如果當前節點中的任何元素不再完全適合當前樹，請將其移至父級。
3. 如果當前節點中的任何元素都適合子樹，則將其插入子樹中。

這樣好嗎？可以改進嗎？

Answer 1

你的四叉樹結構不是最優的。每個節點存儲4個子樹是正確的，但實際的對象只能存儲在樹葉內部，而不是內部節點。因此，保存實際物體的集合需要移動到葉子上。

讓我們來看看操作執行：

1. 插入對象到四叉樹：
   檢查的對象相交當前節點。如果是這樣，遞歸。如果您已達到葉級別，請將該對象插入到集合中。
2. 從四叉樹刪除對象：
   執行完全一樣的步驟，如果插入對象，但是當你到達葉級別從集合中刪除。
3. 測試如果一個物體相交的四叉樹內的任何對象：
   執行完全一樣的步驟，如果插入的對象，但是當你已經達到了碰撞集合中的所有對象的葉級檢查。
4. 測試四叉樹內所有對象之間的所有碰撞：
   對於四叉樹中的每個對象執行單個對象碰撞測試。
5. 更新四叉樹：
   刪除位置已被修改的四叉樹的所有對象，並再次插入它們。

這有幾個優點：

• 通過只存儲在葉子是很容易處理的四叉樹操作（較少的特殊情況下）對象
• 四叉樹可以有葉子不同的深度，因此您可以根據它所覆蓋的空間區域調整四叉樹的密度。這種適應可以在運行時發生，從而保持對象/節點比率最佳。

只有disatvantage：

• 對象可以屬於四叉樹內部的多個集合。您需要在四叉樹外部額外添加一個線性集合來枚舉每個對象而不重複。

Answer 2

我不知道它是多麼的CPU仍然有效，但它似乎是工作在Eclipse中我的酷睿雙核細，仍超過2400 fps的笑..運行

基本上，我加了一個列表使可碰撞對象存儲對我關聯對象（通過插入四叉樹）的四叉樹節點對象的引用。我還爲每個四叉樹節點添加了一個列表，該列表存儲對該節點範圍內所有對象的引用。所以每個節點只會有一個對象出現。每個節點還存儲一個對其父節點的引用，用於導航到附近的節點，如果我想檢查它們中的任何節點以確保進一步的衝突準確性。

這是很容易得到一個細胞的所有其他對象的引用：

list temp_checklist = object.cells[cell_index].objects 
//('objects' being some sort of array or list of object references as described above) 

希望幫助別人;）

Answer 3

四樹並不總是碰撞檢測的最佳數據結構。四叉樹的開銷可能是無限的（如果不限制樹的深度），最壞的情況是根本不加速。相反，您可能需要考慮使用稀疏網格，該網格只比四叉樹具有更好的性能，而不會增加遍歷多個樹級別的額外開銷。

還有其他完全不同的方法可能會更好。例如，你可以嘗試實施Zomorodian和Edelsbrunner的算法，因爲我下面的模塊中所做的：

• https://github.com/mikolalysenko/box-intersect

這裏也有一些文章，我寫了詳細討論這些問題：

• http://0fps.net/2015/01/07/collision-detection-part-1/
• http://0fps.net/2015/01/18/collision-detection-part-2/
• http://0fps.net/2015/01/23/collision-detection-part-3-benchmarks/

特別是，如果你看一下在最後一節的基準，你會看到，所有被調查的圖書館，四叉樹往往比其他碰撞檢測方法，如R-樹來表現相當糟糕，網格或段樹木。