Moller と Trumbore による Fast Minimum Storage Ray/Triangle Intersection が頻繁に推奨されていることがわかりました。
問題は、交差点をスピードアップする限り、データを事前に計算して保存することを気にしません。
だから私の質問は、メモリを気にしないで、光線と三角形の交差を行う最速の方法は何ですか?
編集: 三角形を移動しません。つまり、静的なシーンです。
質問する
20829 次
4 に答える
10
他の人が述べたように、物事を高速化する最も効果的な方法は、加速構造を使用して、必要な光線と三角形の交差の数を減らすことです。とはいえ、光線と三角形の交差は高速である必要があります。事前計算に満足している場合は、次のことを試すことができます。
光線と三角形のエッジをPlücker 座標に変換します。これにより、レイ ラインがエッジごとに 6 回の乗算/加算で三角形を通過するかどうかを判断できます。レイの開始点と終了点を三角形の平面と比較する必要があります (ポイントごとに 4 回の乗算/加算)。実際に三角形に当たることを確認します。
最悪の場合のランタイム費用は、合計 26 回の乗算/加算です。また、レイ/エッジの組み合わせごとに 1 回だけレイ/エッジの符号を計算する必要があることに注意してください。そのため、メッシュを評価している場合は、各エッジの評価を 2 回使用できる場合があります。
また、これらの数値は、すべてが同次座標で行われていることを前提としています。事前に正規化することで、乗算の数を減らすことができる場合があります。
于 2012-10-31T21:35:26.290 に答える
3
1 つの提案は、octree (http://en.wikipedia.org/wiki/Octree) アルゴリズムを実装して、3D 空間を非常に細かいブロックに分割することです。パーティショニングが細かくなればなるほど、より多くのメモリが必要になりますが、ツリーの精度は向上します。
光線/三角形の交差を確認する必要がありますが、光線が三角形に当たらないことが保証されているため、光線/三角形の交差をいつスキップできるかをツリーが教えてくれるという考え方です。
ただし、三角形を動かし始めると、オクツリーを更新する必要があり、それによって何かが保存されるかどうかはわかりません。
于 2012-10-31T17:13:10.773 に答える
2
Dan Sunday によるこの記事を見つけました。
最初の拒否テストまでに実行された操作のカウントに基づくと、このアルゴリズムは MT (Möller & Trumbore) アルゴリズムよりも効率が少し劣ります [...]。ただし、MT アルゴリズムは 2 つの外積を使用しますが、このアルゴリズムでは 1 つのみを使用します。使用するアルゴリズムは、ライン パラメーターrIの計算に必要な三角形の平面の法線ベクトルを計算します。しかし、法線ベクトルが事前に計算され、シーン内のすべての三角形に対して保存されている場合 (よくあることですが)、アルゴリズムはこの外積を計算する必要はまったくありません。ただし、この場合、MT アルゴリズムは依然として 2 つの外積を計算するため、アルゴリズムよりも効率的ではありません。
于 2014-11-01T02:05:19.570 に答える