intersection - レイトライアングル交差

Question

交差光線と三角形をテストするにはどうすればよいですか? また、存在する場合、光線の原点から交点までの距離を取得する方法を教えてください。私のプログラムで、1 つの光線から最大 10000 の三角形をチェックする必要がある場合、どのような最適化を使用できますか??

Answer 1

単一のポリゴンと光線の交差テストは自明であり、光線が少なくとも 1 つの側面を横切る (個別にチェックする) か、側面間の三角形によって定義される平面を横切ることを確認するだけです。最適化は、光線が交差する可能性がまったくないポリゴンをチェックしないようになります。作業している次元の高さ、領域の大きさ、および扱っているポリゴンの数に応じて、最も典型的な最適化はquadtrees、octrees、およびkd-treesです。これは、ほぼ実装の難易度の順序でもあります (ただし、quad と octtree は非常に似ています)。

Answer 2

おそらく初めて実装する必要が生じたとき、これらのスライドを見ましたが、非常に役立つと思います。

http://www.cs.princeton.edu/courses/archive/fall00/cs426/lectures/raycast/sld016.htm

まず、それがどのように機能するかを理解していることを確認してから、さまざまな最適化を行うことができます。例えば：

if (dot(V, N) >= 0)     // no intersection - ray points away from the triangle face
if (dot(P0, N) + d < 0) // no intersection - ray origin is behind the triangle face

私がかつて行っていた別の考えは、光線と面の交点を見つけたときです。法線の最大絶対値で軸をゼロに設定しているときに、2D で三角形内のポイントのチェックを行っていました... abs(Nx) > abs(Ny) > abs(Nz) の場合、チェックインを行いますYZ平面。

外接円の中心と半径を見つける最適化を実装する別の簡単な方法を提案できます（頻繁に行う必要がある場合は、重心のような簡単な中心を選択できます）。このポイントと半径は、三角形の周りに境界球を定義します。これで、光線球カリングをより高速に実行できるようになりました。

http://www.cs.princeton.edu/courses/archive/fall00/cs426/lectures/raycast/sld012.htm

多項式全体を解かないでください。光線/球体の交点は必要ありません。既存のルートを確認するだけです。

たとえば、他にも多くの最適化を行うことができます。頂点と法線をより SSE に適した構造に配置できる場合は、一度に 4 つのチェックを実行できます。これは、およそ 2.5 倍速くなる可能性があります。