應該在每一幀都重建八叉樹嗎？

Question

當在遊戲中使用octree進行碰撞檢測時，是否應該在每一幀中重建樹，或者假設一半物體在一幀中移動，是否有更好的方法？

Answer 1

如果場景隨着每一幀改變，那麼你必須重做樹。

Answer 2

如果場景中有很多靜態幾何，請考慮構建獨立的八叉樹。您還可以通過區分靜態和非靜態幾何體的更復雜的葉節點來表達相同的想法。

底線：只重新生成必須的東西。

Answer 3

如果你有非常動態的數據移動每一幀，仍然需要加速碰撞檢測，我實際上建議使用一個固定的3D網格。 2維當量：

它也可以增加一倍作爲一個自由列表以允許恆定時間清除，像這樣（利用next指數在相同的網格單元任一個索引到下一個元素或下一個空閒元件從自由堆，如果它已被刪除彈出關閉）：

又如：

現在在3個維度，這可能看起來像它需要爆炸性的記憶。然而，訣竅在於讓每個單元格將一個32位索引存儲到一個數組中，並基本上作爲單鏈接索引列表。這將每個單元的大小減小到32位。現在，如果你存儲一個100x100x100的網格（100萬個網格），那將會少於4兆字節。

當元素四處移動時，您可以將它們從它們佔據的單元中移除，移動它們並將它們插入新單元格中。爲了做到這一點，你所要做的就是操縱一些32位索引（沒有內存分配/釋放來將元素從一組單元轉移到其他單元）。這一切都是恆定的，並且不需要重新平衡樹木或分裂八分之一，變得太擁擠或類似的東西。

你也可以使用網格的層次結構（這可能聽起來像一個八叉樹但不同）。我的意思是你的場景中可能有一個粗糙的網格用於整個網格對象。然後，每個網格對象可能會爲其每個部分存儲一個粗糙的網格，例如10x10x10。然後每個部分爲其每個多邊形存儲細網格或八叉樹。這允許非有機網格，例如與像機器人一樣旋轉的部分剛性，以避免必須更新多邊形的細網格/八叉樹並且僅在更新其自己的粗網格部分和世界對象的粗網格時它開始旋轉它的腿和手臂，例如只有有機模型在骨骼變形時需要更新它們的細網格，例如，

八叉樹我會保留你的完全靜態元素/部分，永遠不需要更新每幀，我會用一個不錯的八叉樹，稀疏也許一些後處理緩存友好的內存訪問。如果可以假設八叉樹一旦構建就不需要更新，那麼您可以多花點時間來加速對這些搜索的搜索並最大限度地減少內存使用。