3d - 3Dでポイントから三角形までの距離を計算する最速の方法は?

Question

ポイントから 3D 三角形までの最小距離を計算する明白な方法の 1 つは、ポイントを三角形の平面に投影し、結果のポイントの重心座標を決定し、それらを使用して、投影されたポイントが三角形内にあるかどうかを決定することです。そうでない場合は、その重心座標を [0,1] の範囲にクランプすると、三角形の内側にある最も近い点が得られます。

これを高速化または単純化する方法はありますか?

Answer 1

点 P0 から三角形 P1、P2、P3 までの距離を求めるには、さまざまな方法があります。

1. 3D メソッド。ポイントを三角形の平面に投影し、重心座標またはその他の手段を使用して、三角形の最も近い点を見つけます。距離は通常の方法で求められます。

2. 2D メソッド。P1 が原点、P2 が z 軸、P3 が yz 平面になるように、ポイントに移動/回転を適用します。点 P0 の投影は自明です (x 座標は無視してください)。これにより、2D の問題が発生します。エッジ方程式を使用すると、三角形の最も近い頂点またはエッジを決定できます。距離の計算は簡単です。

この論文では、両者のパフォーマンスを 2D メソッドの勝利と比較します。

Answer 2

既知の高速アルゴリズムの 1 つを使用していると仮定すると、高速化する唯一の方法は、多数の三角形に対して多数の測定を行う場合です。その場合、「エッジ」または「ワインディング」構造で事前計算された多くの量を保持できます。3 点を保存する代わりに、エッジ構造で構成されるメッシュを保存します。その後、射影は非常に高速になり、分岐予測可能になるように重心テストをコーディングできます。

本当の鍵は、すべてをキャッシュに保持することです。プロセッサはほぼ 1 クロック サイクルで MUL と DIV を実行できるため、通常はメモリがボトルネックになります。

また、 SSE3または同様のもの ( Mono の SIMD サポートなど)でアルゴを作成することを検討してください。これは大変な作業ですが、十分に考えれば、通常、一度にいくつかの三角形を作成できます。

このトピックに関するいくつかの論文を見つけようとしますが、「Ray Mesh Intersection」を Google で検索することをお勧めします。これにより、80 年代と 90 年代の人々がこのようなものを最適化するために懸命に取り組んだ偉大な仕事がすべて持ち出されます。