用於球體移動的射線球體測試的良好加速結構

Question

我正在尋找合適的加速結構來進行射線球體相交測試（在遊戲中）。應用以下條件：

-there是角落找尋100個球體和100倍的光線，以測試針對彼此每幀

-the球體在每幀移動，所以做射線

-there可以是射線/球加入/每一幀中移除（但大多會在兩幀之間的相同，只是略微移動）

-whole事情是在3D

kd-樹是用於光線相交非常好的測試，但自球體移動，我不得不在每一幀重建KD樹，這是昂貴的

Oct樹更容易維護，但對射線相交測試非常無效。

100線對100個球似乎並不太大，但我編碼在非常低的資源，所以我找了一些加速爲

任何人都可以給我一些提示嗎？

Answer 1

100x100 = 10k，優化後的蠻力似乎並不一致，尤其是射線/球形相交測試只涉及加/乘。您總是可以在主循環之前預先計算所有歸一化的射線矢量。如果你假設你生活在一個有界的宇宙中，並且球體和光線的空間密度相對均勻，那麼你可以使用一個固定的空間網格（固定的八叉樹） - 就像一個16x16x16的網格，或緩慢 - ，和：

• 預先計算用於每個球體相交細胞（容易計算，只涉及少數增加和比較）在每個小區中，存儲相交球體的列表，
• 對每條射線，在一個循環：
  • 計算單元格列表ra y十字架（基於Bresenham算法的方法可以做到這一點）
  • 對此單元格列表中的所有球體進行相交測試。

這樣，你沒有任何射線存儲在任何樹，只有球。這種方法的效率取決於比例單元尺寸/球體尺寸，如果球體尺寸沒有太多分散，它可能是一個很好的提示。

如果球不相互交叉和球體的大小有一個最低限度，你甚至可以綁定的領域列表中小區列表（適當數量就留給exercice讀者......）

HTH