performance - Raytracer - 次の光線交点を見つけるための標準的なアプローチとその長所と短所

Question

レイと特定のプリミティブとの交点を計算する方法を尋ねているのではなく、シーン内の何百万ものプリミティブのどれがレイが次に交差するかをできるだけ早く決定するための現在のアプローチが何であるかを尋ねています。

octtrees と kd-trees が一般的に使用されていると聞きました。現在の候補でもある他の方法があるかどうかはわかりません。

八分木が使用されている場合、各キューブがその 8 つのサブキューブのいずれかがジオメトリと交差するかどうかを追跡できるようにするだけですか? 対応するブランチを取得しないサブキューブと、ブランチを取得する各サブキューブ。したがって、交差する限定された数のプリミティブを与える最終ノードが見つかるまで、ツリーを下りますか? そのような八分木を構築する場合、光線をその開始点から立方体を通ってそれぞれに下降する点まで移動することにより、光線を追跡することができます。少数のプリミティブ (光線が見逃す可能性があり、次の立方体に移動する必要がある)?

いずれにせよ、次の交差点をどのように見つけるかという問題は、大きなパフォーマンス要因のように見えるので、現在最も重要なアプローチは何ですか?また、それらの長所と短所は何ですか?

Answer 1

これは非常に大きなトピックです。この Web サイト www.scratchapixel.com でいくつかの情報を見つけることができます。加速テクニックのレッスンを見てください。レイ トレーシングは遅い (実際にはコンピューターが遅い) ため、シーンのすべての三角形をテストする単純な光線と三角形の交差テストを行うと、すぐに法外なコストがかかります。この問題を活用するには、アクセラレーション構造を使用できます。投稿でいくつかの手法について言及しました (octrees、kd trees)。一方と他方のパフォーマンスは非常に主観的であり、実装、必要なものなどによって異なります。BVH ツリーと kd ツリーはどちらも優れていると見なされます。著者がさまざまなタイプの加速構造、それらの長所と短所などをレビューしている論文をウェブ上で簡単に見つけることができます。加速構造の調査などです。