ポイントが 3D メッシュ内にあるかどうかを判断するための高速なアルゴリズムは何ですか? 簡単にするために、メッシュはすべて三角形で穴がないと仮定できます。
私がこれまでに知っていることは、光線がメッシュを横切ったかどうかを判断する一般的な方法の 1 つは、光線/三角形の交差の数を数えることです。触覚医療シミュレーションに使用しているため、高速である必要があります。したがって、光線の交差についてすべての三角形をテストすることはできません。どの三角形が関連しているかを判断するために、三角形を格納するための何らかのハッシングまたはツリー データ構造が必要です。
また、頂点の任意の 2D 投影がある場合、単純な点/三角形の交差テストがすべて必要であることもわかっています。ただし、どの三角形が関連しているか、さらにどの三角形がポイントの前にあるかを知り、それらの三角形のみをテストする必要があります。
私は自分の問題を解決しました。基本的に、任意の 2D 投影 (座標の 1 つを破棄) を取得し、三角形の AABB (Axis Aligned Bounding Boxes) を 2D 配列にハッシュします。(titus が言及した 3D 立方体のセットは、一定の速度向上しか得られないため、やり過ぎです。) 2D 配列と、テストしているポイントの 2D 投影を使用して、三角形の小さなセットを取得します。 3D 光線/三角形の交差テスト (3Dでの光線、セグメント、平面、および三角形の交差を参照)) そして、z 座標 (スローされた座標) が点の z 座標よりも大きい、光線の交点の三角形の数を数えます。偶数の交点は、メッシュの外側にあることを意味します。交点の数が奇数であるということは、それがメッシュの内側にあることを意味します。この方法は高速であるだけでなく、実装が非常に簡単です (まさに私が探していたものです)。
このアルゴリズムは、データ構造を構築する時間を正当化するために多くのクエリがある場合にのみ効率的です。
スペースを同じサイズの立方体に分割します (後でサイズを計算します)。各立方体について、どの三角形に少なくとも点が含まれているかを確認します。何も入っていない立方体は捨てます。ウィキペディアに示されているようにレイ キャスティング アルゴリズムを実行しますが、代わりに線が各三角形と交差するかどうかをテストし、線と交差するすべての立方体を取得してから、これらの立方体の三角形のみでレイ キャスティングを実行します。2 つの立方体に存在するため、同じ三角形を複数回テストしないように注意してください。
適切な立方体のサイズを見つけるのは難しいことです。大きすぎても小さすぎてもいけません。試行錯誤によってのみ見つけることができます。number of cubesiscとnumber of trianglesisとしましょうt。
立方体の三角形の平均数はt/c
k、光線と交差する立方体の平均数です
これらの立方体の線と立方体の交点 + 線と三角形の交点は最小でなければなりませ
ん
c+k*t/c=minimal=>が真にc=sqrt(t*k)
なるまで、立方体のサイズの値をテストする必要があります
。パースペクティブ、1M 三角形の場合、1k 交点のオーダーでテストしますc=sqrt(t*k)sqrt(mesh width)
Ray Triangle Intersection は、精度に関しては優れたアルゴリズムのようです。Wikiにはさらにいくつかのアルゴリズムがあります。ここにリンクしていますが、すでに見たことがあるかもしれません。
ポイントとポイントが頂点を作る平面との間の関係のマトリックスを維持することによって、おそらく即興できますか? この主題は、学界での調査のトピックのようです。これに関連するその他のディスカッションにアクセスする方法がわかりません。