對象間高效碰撞檢測的最佳算法

Question

我很困惑。好吧，不要混淆，儘可能不想做6個測試程序，看看哪個算法是最好的。所以我想我會問我在這裏的專家朋友給我的經驗好處。

的方案是一種3D場景具有潛在比較比較，它裏面的物體的尺寸的大面積。場景中可能有數千個對象。物體的大小從十分之一到十單位不等，但不大（或更小）。對象傾向於聚集在一起，但這些聚類可能會出現在場景中的任何位置。所有對象都是動態的和移動的。集羣往往一起移動，但是當它們的速度可能不一直是相同的時候。還有靜態幾何要考慮。儘管有大量的動態對象，但場景中還有一些靜態對象（靜態對象往往比動態對象大一個或兩個數量級）。

現在，我要的是爲場景中的所有項目有效地進行碰撞檢測的空間數據結構。如果算法也支持可視化查詢（對於渲染管線），那將是非常好的。爲簡單起見，假設這裏的碰撞檢測是寬相位的（即所有動態物體都是完美的球體）。

所以，在我的研究，我可以使用的一個：

（1）八叉樹 （2）鬆散八叉樹 （3）線性八叉樹（+鬆） （4）kd樹 （5）BSP樹 （6）散列

到目前爲止，（6）是唯一一個我試過。如果場景中的物體平均分佈均勻，則在速度方面實際上是非常好的（我的系統在1ms以下檢測到8192個物品碰撞）。如果所有的物體都變成了一個更小的區域，那麼我認爲這是不可能的。

有沒有人有一些見解，以使用其中一個，或任何技巧，我可以聘請加快速度？我在想，無論發生什麼，我都可以爲靜態幾何體使用單獨的BSP樹。我想這裏的動態「領域」是我最關心的。注意：沒有CUDA，這只是CPU：p。

感謝

編輯：好的，感謝弗瑞斯，我發現了大約AABB樹的更多信息。 GameDev在這裏有一箇舊的討論：http://www.gamedev.net/topic/308665-aabb-tree---wheres-the-poly-o_o/。看起來像一個很好的妥協。

最終編輯：決定不重新發明輪子。子彈物理庫可能會爲我完成所有這些（它裏面有AABB樹，可能還有很好的優化）。

Answer 1

偉大的問題。

你基本上之間複雜的權衡：一個完整​​的碰撞檢測階段更新

架空/維護數據結構的

1. 速度爲對象走動

壞消息是，由於這一點，沒有「完美」的答案 - 它將真正依賴於你的情況獨特的許多不同因素。例如，當BSP用大量的靜態平面幾何進行預先計算時，它們的速度會快於1，這就解釋了它們在早期FPS遊戲中如此盛行的原因。

我個人的猜測是，在每個底層邊界框中有一個合理數量的對象（5-10？）的鬆散AABB（軸對齊邊界框）樹可能在您的情況下效果最好。理由：

• 你有相當大/稀疏的空間與對象的羣集。 AABB樹木往往會對此有所幫助，因爲您可以削減很多您需要的水平。
• 你假設完美的球體。球體碰撞測試非常便宜，因此您可以輕鬆負擔每個底層節點的10-45測試。對於N的小數值，基本上N^2是很好的:-)
• 軸對齊使更新樹更簡單，相交測試比大多數替代方案便宜得多。由於您假設的是大致球形的物體，因此我認爲您不會從定向包圍盒中獲得太多收益（如果您在有趣的角度上有很多很長/較薄的形狀，這隻會給您帶來好處）。
• 通過允許邊界框鬆動幷包含合理數量的對象，可以減少任何單個對象的運動將其帶到AABB邊界之外的機會。除非發生這種情況，否則不需要更新樹。這將爲您節省很多樹更新時間。當它發生時，用一點餘量擴展邊界，以便您不必立即再次重新延伸下一幀 - 請記住，大多數運動趨向於以相同的方向持續幾幀！

對不起，有點毛茸茸的答案，但我希望這給你一些有用的想法/事情來考慮！

Answer 2

許多物理引擎使用AABBTree（軸對齊包圍盒樹），它細分對象，以小件。使用這個算法你可以得到非常好的碰撞檢測。這棵樹看起來有點像八叉樹。

的OOBBTree（導向型包圍盒），將它更好地打擊部分。