8

四面体がすべてばらばらであるが、互いに「接触」している四面体メッシュのポイント位置の証明されたデータ構造はありますか? つまり、ほとんどの面はちょうど 2 つの四面体の面です。

場所とは、特定の点がどの四面体にあるか、またはどの四面体にもないかを調べたいということです。

これまでのところ、私は試しました：

  1. シンプルな KD ツリー。平均的な木の深さが非常に高く、各葉でテストする個々の四面体がまだたくさんあったため、これは私のニーズには遅すぎました。

  2. 各セルの交差するすべての四面体を含むグリッド。これはかなりうまく機能しているように見えますが、まだ十分な速さではありませんでした。まず、メッシュ全体があまり「箱型」ではないため、グリッドに空のセルが多数含まれていました。第二に、実際に四面体を含むほとんどのセルには、多くの四面体 (10 以上) が含まれていました。これは、多くの四面体がすべての頂点を共有しているためであり、頂点がセル内にあるとすぐに、隣接するすべての四面体も共有されるためだと思います。

入力データに関するその他の情報: 通常、メッシュは凸状ではなく、穴や含有物がある場合があります。最後の 2 つはややありそうにありませんが、それらに対処する必要があります。これにより、(高価で複雑な?) 前処理なしでは「歩く」ことができなくなります。

4

3 に答える 3

6

隣接情報を持つ四面体で構成される 3D 三角形分割を扱っている場合は、単に walk を使用できます。これは、点の位置を特定するための標準的な手法であり、3D方向テストを使用します。

詳細については、Olivier Devillers らによる三角形分割での歩行に関する論文を参照してください。（ググるとPDFが出てきます。）

于 2012-08-08T07:28:03.163 に答える
1

いくつかの簡単な考え: octree はグリッド アプローチに似ていますが、空のグリッドをすばやく無視し、いっぱいになったグリッドを細分化することができます。

また、ポイントが四面体の内部にあるかどうかをテストする方法についても言及していません。久しぶりに見ましたが、重心座標で正四面体のテストを高速化できるのではないでしょうか? または、ポイントを含むスイープ ラインの明らかに反対側にある四面体の頂点に基づいて、四面体をすばやく除外するスイープ ライン アルゴリズム。

于 2012-08-07T21:37:09.223 に答える
0

これは確かに少しブレインストーミングです。

おそらく、軸に沿った平面ではなく面に沿った平面を使用する kdTree のカスタムです。

点が四面体の 4 つの平面すべての「正しい」側にある場合、その点は四面体の内側にある必要があります。(そうですか?) また、平面の間違った側にいる場合は、現在のテトを除外するだけでなく、平面のその側にある他のテットも除外できます。

各ノードが単一の平面であるツリーを構築できるように思われます。葉ノードは、1 つの特定のテットにいることを意味します (テットが交差しないと仮定します)。ツリーは深いかもしれませんが、各テストは (より高価なトライアングル テストではなく) 平面に対してのみ行われ、リーフ ノードは正確に 1 つの答えを返すため、高速であると思われます。

ツリーを効率的に構築するのは難しいかもしれません。

于 2012-08-07T20:06:29.540 に答える