7

（ゲームで）光線と球体の交差テストを行うための適切な加速構造を探しています。次の条件が適用されます。

-フレームごとに互いにテストする約100個の球と100個の光線があります

-球は各フレームで移動するので、光線も移動します

-各フレームに追加/削除された光線/球が存在する可能性があります (ただし、それらのほとんどは 2 つのフレーム間で同じで、わずかに移動しただけです)

-すべてが3Dです

KD ツリーはレイ交差テストには非常に適していますが、球が移動するため、すべてのフレームで KD ツリーを再構築する必要があり、コストがかかります。

Oct-tree は保守が容易ですが、光線交差テストには非常に効果的ではありません。

100 個の球体に対して 100 個のレイはあまりないように見えますが、非常に少ないリソースでコーディングしているので、そのためのアクセラレーションを探しています

誰でもそれについてのヒントを教えてもらえますか?

4

1 に答える 1

2

100x100 = 10kの場合、最適化されたブルートフォースは一貫性がないようには見えません。特に、光線/球の交差テストには加算/乗算のみが含まれます。メインループの前に、正規化されたすべての光線ベクトルをいつでも事前計算できます。

境界のある宇宙に住んでいて、球と光線の空間密度が比較的均一であると仮定すると、固定空間グリッド（固定オクトツリー）（16x16x16セルグリッドなど）を使用できます。 、 と：

  • セルと交差する球ごとに事前計算し（計算が簡単で、追加と比較がほとんど必要ありません）、交差する球のリストを各セルに保存します。
  • 光線ごとに、ループ内：
    • 光線が交差するセルのリストを計算します（ブレゼンハムのアルゴリズムに基づく方法でうまくいく可能性があります）
    • このセルリスト内のすべての球に対して交差テストを実行します。

そうすれば、光線をツリーに保存する必要はなく、球だけを保存できます。この方法の効率は、セルサイズ/球サイズの比率に依存します。球サイズにあまり分散していない場合は、良いヒントになります。

球が互いに交差せず、球のサイズが最小の場合は、セルリストで球リストをバインドすることもできます（適切な数は読者の演習として残されています...）

HTH

于 2010-02-23T10:13:14.690 に答える