1

巨大な 3D グリッドを想像してみてください (手続き的に定義され、無限になる可能性があります。少なくとも、1 辺あたり 10^6 座標です)。各グリッド座標には、プリミティブがあります (たとえば、球、ボックス、またはその他の簡単で数学的に簡単に定義できる関数)。

グリッドの要素に対して、グリッドの外側の原点とそれに入る方向で、光線を交差させるアルゴリズムが必要です。つまり、レイはこの巨大なグリッドの途中まで移動し、プリミティブに当たる可能性があります。グリッドの範囲のため、反復法 [編集: (レイ マーチングなど)] は容認できないほど遅くなります。私が必要としているのは、プリミティブ ヒットを見つけるための閉じた形式の [編集:一定時間] ソリューションです。

私が考えた 1 つの可能なアプローチは、x、y、z のそれぞれのモジュラー算術空間でグリッド セルを囲む 8 つの座標のそれぞれのプリミティブに向かって各タイム ステップでレイが収束する量を決定し、次に除算することです。光線の方向によって最小距離を取ります。これが機能する可能性があると考える証拠は直感以外になく、Google も役に立ちません。「グリッドを交差させる」とは、グリッドの面を交差させることを意味します。

ノート：

  • 私は本当にプリミティブの表面法線だけを気にします (交点までの距離があれば簡単に見つけることができますが、距離自体は気にしません)。
  • この時点では、交差するプリミティブのタイプは重要ではありません。理想は箱です。2 番目の選択肢、球。ただし、どのようなアルゴリズムが使用されていても、他のプリミティブに一般化できる可能性があると想定しています。最悪の事態が発生したとしても、このアプリケーションにとってはそれほど重要ではありません。

ありがとう、
イアン

4

4 に答える 4

1

ここに別のアイデアがあります: x、y、z 座標のすべてが整数値に近い場合にのみ、光線がプリミティブに当たることができます。光線のパラメトリック方程式を考えると、線上の点は次の式で与えられます。

p=p0 + t * v

ここで、p0 は開始点で、v は光線の方向ベクトルです。光線からの距離を各軸の整数値に teg の関数としてプロットできます。

dx = abs( ( p0.x + t * v.x + 0.5 ) % 1 - 0.5 )

これにより、周期が方向ベクトルの成分に依存する 3 つの鋸歯状プロットが得られます (たとえば、方向ベクトルが (1, 0, 0) の場合、x プロットは周期 1 で 0 から 0.5 の間で直線的に変化しますが、他のプロットは、p0 が何であれ一定のままです。

プリミティブのサイズによって決定される、3 つのプロットすべてがあるしきい値レベルを下回る t の最初の値を見つける必要があります。したがって、より高い頻度のプロットをチェックする前に、最初に最も長い (無限ではない) 周期を持つプロットを検討することで、チェックする t 値の数を大幅に減らすことができます。

3 つのプロットの周期に基づいて t の正しい値を計算できる可能性があるという感覚を揺るがすことはできませんが、原点ではない開始位置によって台無しにされないものを思い付くことはできません。 、およびしきい値がゼロではありません。:-/

于 2012-08-03T15:14:38.083 に答える
0

基本的には、線を関数の形で表現する必要があります。そこから、光線が各オブジェクトと交差するかどうかを数学的に計算する必要があります。交差する場合は、ソースに最も近いものと衝突することを確認します。

これは高速ではないため、ここで多くの最適化を行う必要があります。最も明白なことは、実際の形状の代わりにバウンディング ボックスを使用することです。そこから、オクトリーや BST (Binary Space Partitioning) などを使用できます。

とにかく、私が見落としていることがありますが、それはシステムに追加の制限があることで可能になりますが、それがコース用のレイ トレーサーを作成する方法でした。

于 2012-04-21T05:26:31.383 に答える
0

あなたは質問で、反復的な解決策は容認できないほど遅いと述べています-グリッド内のすべてのオブジェクトを線に対してテストするという意味で反復的なことを意味していると思います。

代わりに、線が交差するグリッド キューブを反復処理し、キューブごとに、キューブが交差する 8 つのオブジェクトをテストします。線が交差する立方体を見つける方法については、Bresenham の線描画アルゴリズムを参照してください。Bresenham は、光線が交差するすべての立方体を絶対に返すわけではありませんが、テストするプリミティブを見つけるには、それで十分であると確信しています。また、次の優れたプロパティもあります。

  1. 非常にシンプル - これは GPU で実行している場合に便利です
  2. 光線に沿って繰り返し結果を返すため、ヒットを見つけたらすぐに停止できます。
于 2012-04-23T11:08:54.293 に答える
0

このアプローチを試してください：

  1. 光線の機能を決定します。

  2. グリッドが z 軸の異なる平面に分割されているとします。光線は各「z 平面」(同じ高さのグリッド ノードがある平面) と交差し、座標 (x、y、z) を簡単に計算できます。 ) 光線関数からの交点;

  3. Z平面をスワイプすると、どの交点が立方体または球体にあるかを簡単に判断できます。

  4. ただし、光線は z 平面間の立方体/球体と交差する可能性があるため、x、y 軸で 1 ～ 3 ステップを繰り返す必要があります。これにより、交差点が取り残されないことが保証されます。

  5. x、y、z 方向の検索で見つかった立方体/球体の繰り返しを破棄します。

于 2012-07-21T17:01:20.493 に答える