1

ポイントを含む 3D ソリッド ボックスが与えられます。四面体でメッシュ化されたボックスが与えられます。両方のボックスの寸法は同じです。

ソリッドのポイントをメッシュ内のそれぞれの四面体にマッピングするアルゴリズムを見つける必要があります。

次のアルゴリズムを使用しました。

  1. オクトリーでソリッドをリファインする
  2. メッシュ内の四面体を反復処理し、それが八分木の枝または葉と交差するかどうかを確認します。(Ratschek & Rockne のアルゴリズム)
  3. 交差する場合は、八分木から四面体にポイントをマッピングします。

しかし、アルゴリズムは非常に遅く、さらに、ボックスと四面体の交差をチェックするのに大きな問題があります。

八分木を使い続けることもできますが、交点をチェックするために合理的なものが必要なのは間違いありません。どんなコメントでも大歓迎です。

更新: 200 万のソリッド ポイントと 200k の四面体があります。

更新 2: 三角測量でウォーキングを実装しようとしています

4

2 に答える 2

1

left四面体の頂点を知っていると仮定すると、点が四面体の内側にあるかどうかを確認できますright。たとえば、左が法線に沿って指されている側であるとします。

ポイントが平面の左または右にあるかどうかを判断するための計算は簡単です。

私が見つけた別の方法がありますが、私の答えの変形のようです。

もちろん、点が tet 内にある場合は、tet にマップされます。このメソッドは、頂点シェーダーまたは OpenCL/CUDA カーネルとして実装でき、高度に並列化されます。

于 2014-03-14T18:36:19.210 に答える
1

標準的な単純化の 1 つは、最初に、軸に沿った境界ボックスを使用しておおよその八分木と四面体の交点を計算することです。結果として得られる交差テストは非常に単純です。

次に、ツリーのリーフ レベルまで移動したら、正確なテストを使用して、特定の四面体に含まれるポイントを特定できます。

要約すると：

Form an octree T for your points X

for (all tetrahedrons ti in mesh M)

    Form a minimal axis-aligned bounding-box Bi for tetrahedron ti

    Traverse T from root, accumulating a list Li of all leaf nodes 
    that overlap with box Bi

    for (all leaf nodes li in list L)
        for (all points pi in leaf node li)

            if (point pi is inside tetrahedron ti /*exact test*/ )
                Associate point pi with tetrahedron ti
            endif

        endfor
    endfor

endfor

このアルゴリズムは、次(i)の場合に効率的です: ポイントXがメッシュ内に適切に分散されてMおり(ii)、四面体のMアスペクト比が適切である。

優れたパフォーマンスを達成するための鍵は、ツリー トラバーサル ステップをできるだけ効率的に実装することです。

四面体内の点テストは、特定の点piが四面体の 4 つの面の「内側」側にあるかどうかをチェックすることによって実行できます。四面体が与えられた場合、点が面の「反対側」の頂点と同じ側にある場合[i,j,k,l]、点piは面の「内側」側にあります。[i,j,k][i,j,k]l

これらの方向テストは、適応精度演算を使用して確実に実行できます。Jonathan Shewchuk は、そのような実装をここで提供しています。

于 2014-03-13T19:40:51.400 に答える