移動物體的空間數據結構？

Question

我想知道什麼是處理大量移動物體（球體，三角形，盒子，點等）的最佳數據結構？我試圖回答兩個問題，最近鄰居和Collsion檢測。

我也知道傳統上，用於近鄰查詢和Oct/KD/BSP如R樹數據結構用於處理靜態的物體，或者幾乎沒有任何移動的物體碰撞檢測的問題。

我只希望有別的東西在那裏，是更好的。

我很感謝所有的幫助。

Answer 1

Bounding Spheres可能會幫助你處理許多運動物體;你計算物體的半徑平方，並從它的中心跟蹤它。如果兩個物體的中心之間的平方距離小於兩個物體的平方半徑的總和，那麼你就有可能發生碰撞。一切都以平方距離完成。沒有平方根。

你可以通過你的對象之間的最小平方距離最近的鄰居進行排序。當然，碰撞檢測可能會變得很複雜，並且對於非球形物體，Bounding Spheres不一定會獲得碰撞信息，但它可以很好地修剪需要比較的物體樹。

你需要，當然要跟蹤對象的中心;理想情況下，您希望每個對象都是剛性的，以避免重新計算邊界球尺寸（儘管重新計算並不特別困難，特別是如果您使用一個剛性對象樹，每個對象都有自己的邊界球）是非剛性的;但它變得複雜）。

基本上，回答你關於數據結構的問題，你可以將所有的主數組中的對象;我有一組「區域」數組，它們是對主數組中的對象的引用，您可以根據對象的笛卡爾座標快速地對對象進行分類; 「區域」陣列應該有一個重疊定義，至少是主對象數組中的最大對象半徑的2倍（如果這是可行的話;對象邊界球體縮放問題與對象數顯然會出現）

一次通過比較一個區域內所有對象之間的距離，可以做一個快速的碰撞測試;再次，這是區域定義變得重要的地方，因爲您正在進行區域數量與數量的顯着折衷但是，它有點簡單，只是因爲你的距離比較歸結爲簡單的減法運算（當然也包括abs（）操作）。

當然，那麼你必須在你的非球面之間做實際的碰撞檢測對象，並且可以不是t rivial，但是在這一點上你已經大大減少了潛在比較的數量。

基本上，這是一個雙層系統;第一個是區域數組，您可以在場景中粗略地排序。其次，你有你的區域內距離比較;其中您將對碰撞的物體進行基本碰撞檢測和碰撞標記。

有可能是房間裏這種算法中使用的動態區域確定，甚至出你的區域大小，以確保您的區域大小不會與「擁擠」的區域增長過快的樹木;儘管如此，這種事情並不是微不足道的，因爲對於不同大小的對象，對密度的排序變得......複雜，至少可以說。

Answer 2

一個有趣的做衝突檢測的方法是使用軸向對齊的邊界框（AABB's）組織在一個特殊的八叉樹結構中。 AABB的幫助，因爲他們使得粗略的碰撞計算非常快速，因爲您只需要執行多達6次比較。

這裏有幾個技巧，你應該用八叉樹結構用：

1）一個節點佔據應該是兩倍大，因爲這將是一個正常的八叉樹（八叉樹分區的位置的邊界區域空間不重疊）。由於每個節點應與其相鄰節點的一半面積重疊。由於AABB只能屬於一個節點，因此這種額外的大小和重疊允許它在較長的時間內保持在一個節點中。

2）同樣在每個節點中 - 也許在層次結構的每個級別中 - 都會保留到節點鄰居的鏈接。這將涉及大量額外的代碼，但它將允許您在接近O（1）時間而不是O（2logn）時間之間在節點之間移動元素。

如果八叉樹佔用太多內存，則可以將它改爲使用稀疏八叉樹結構，只保留實際包含實體的遊戲世界各部分的樹。然而，這意味着當實體在世界中移動時，你必須對每一幀執行更多的計算。

您可能想嘗試的其他想法不是八叉樹，而是使用kd-tree（我相信這是正確的名稱），或者使用AABB從底層構建結構。

KD樹（來自內存）使用軸向對齊的平面分隔空間，因此它們非常適合與AABB一起使用。

另一個想法是，而不是從上而下，迫使八叉樹代（從一個盒子envoloping整個世界），你從基礎的實體建立起來，構建更大的AABB的是增長，直到最大的一個涵蓋整個世界。雖然我不確定它如何與許多快速移動的實體一起工作。

（這已經有一段時間，因爲我已經做了這種空間的遊戲開發編碼。）

Answer 3

1. 您可以在八叉樹分區現場，並利用現場的一致性。您正在測試的移動對象將根據其速度，位於樹的特定節點中以獲取特定數量的幀。這意味着您可以假定它將位於節點中，因此可以快速刪除很多不在節點中的對象。當然，棘手的一點是當你的物體接近你的分區的邊緣時，你必須確保你更新了該物體所處的那個節點。

2. 移動物體有方向和速度。您可以通過使用與對象移動方向垂直的分割，輕鬆地將場景分爲兩部分。不需要檢查該分部錯誤的任何物體。當然補償其他物體的速度。所以如果另一個對象是合理的緩慢的話，你可以很容易地將它從進一步的檢查中刪除。

3. 總是使用像軸對齊邊界框之類的東西來簡化您正在測試的任何形狀。初始碰撞測試

4. 您可以將物體與另一個移動物體之間的距離加上速度。如果另一個運動物體以更快的速度以相同的總體方向移動，則可以將其從檢查中消除。

5. 根據物體的形狀還有很多其他的優化。圓形或正方形或更復雜的形狀都可以在移動時做特定的優化。

6. 假設某些物體停止或停止移動，您可以跟蹤停止的物體。這些對象可以被視爲靜態對象，因此檢查速度更快，您可以將所有靜態優化技術應用於它們。

7. 我知道更多，但想不到任何關閉我的頭頂。有一段時間沒有這樣做。

現在當然這取決於你如何在做碰撞檢測。您是否逐漸更新基於速度的對象位置並檢查它是否是靜態的。或者你是通過擠出形狀並找出初始碰撞點來補償速度。前者需要快速移動物體的一小步。後者更復雜，成本更高，但效果更好。另外，如果你要旋轉物體，那麼事情會變得更棘手。

Answer 4

掃描剪枝寬泛階段+ GJK窄相

Answer 5

RDC可以使用的，特別是如果你的對象是稀疏的（未許多交叉點）。