何千もの光線と三角形があります。すべての交点を取得する必要があります。通常の 2 レベル ループを使用する場合、O(m n) 時間の複雑さが必要です。時間の複雑さを O(m n) から O(m* logn) または O(logm*n) に下げる方法はありますか?
よろしくお願いします、
6 に答える
8
おそらく見たいのは、ある種の空間分割技術です。これにより、三角形のコレクションをすばやく除外できます。
おそらく、球形のBounding Volume Hierarchiesを使用したアプローチを検討したいと思います。しかし、検討したい他のテクニックは、BSP (Binary Space Partitioning) Trees / KD TreesまたはOctreeの使用です。
于 2009-12-23T09:45:51.280 に答える
2
この問題に対する古典的な解決策は、三角形に基づいて KD ツリーを構築し、各光線に対してクエリを実行することです。予想されるクエリの種類に合わせてツリーを最適化できます。光線がランダムに分布している場合、ヒットの確率は問題の表面積に比例します。
実際にレイ トレーシングを行っていない場合でも、この問題は現在、レイ トレーシングの主なパフォーマンスのボトルネックであるため、おそらくそれに関する文献を確認する必要があります。
于 2009-12-25T02:14:53.830 に答える
2
いいえ。理由は簡単です。実際には O(m * n) 個の交点が存在する可能性があります。それらのリストを作成するだけでも O(n * m) です。
于 2009-12-23T09:35:29.893 に答える
0
2D にはSweepLineアルゴリズムがあります。3D用に一般化できるように見えます。
于 2009-12-23T09:34:18.867 に答える
0
明らかに、光線と各三角形の間の交点を反復して計算する必要がある場合、複雑さは O(mn) になります。ただし、特定の光線と潜在的に交差する可能性のある三角形のみに関心がある場合は、空間分割グリッドのバリアント、たとえば階層的四分木グリッド ( http://graphics.stanford.edu/courses/cs468- 06-fall/Slides/steve.pdf )。
于 2014-02-07T20:40:43.570 に答える
0
立方体で互いに近い三角形をグループ化できます。次に、各光線について: 立方体に当たらない場合は、立方体内の三角形の 1 つに当たらないことが確実であるため、この特定の光線のそれらの三角形とのすべての交差計算をスキップできます。
于 2009-12-23T09:44:34.380 に答える