computational-geometry - メッシュ間の交点

Question

ある三角形メッシュが別の三角形メッシュと交差しているかどうかを判断する方法を説明しているライブラリまたは論文を探しています。

興味深いことに、私は空っぽになっています。CGALでそれを行う方法があれば、それは私を避けています。

三角形の交差が可能であり、各メッシュには有限数の三角形が含まれているため、明らかに可能であるように思われます。しかし、一方のメッシュに n 個の三角形があり、もう一方のメッシュに m 個の三角形がある明らかな O(n*m) アプローチよりも、より良い方法があるに違いないと思います。

score 8 · Accepted Answer

CGAL を使用して通常行う方法は、 CGAL::box_intersection_dを使用することです。

この例とこれを混ぜて作ることができます。

編集：

CGAL 4.12 以降、関数が追加されましたCGAL::Polygon_mesh_processing::do_intersect()。

score 4 · Accepted Answer

本Real-TimeCollisionDetectionには、そのようなアルゴリズムを実装するためのいくつかの良い提案があります。基本的なアプローチは、空間分割またはバウンディングボリュームを使用して、実行する必要のあるトライトライ交差テストの数を減らすことです。

プロキシミティクエリパッケージなど、この問題に対処する優れたアカデミックパッケージが多数あり、ノースカロライナ大学のGAMMA研究グループ、SWIFT、I-COLLIDE、およびRAPIDの他の研究はすべてよく知られています。これらのライブラリのライセンスが受け入れ可能であることを確認してください。

Open Dynamics Engine（ODE）は、多数の交差プリミティブの最適化された実装を含む物理エンジンです。ウィキで三角形と三角形の交差テストのドキュメントを確認できます。

score 1 · Accepted Answer

libiglでは、 cgalをラップして、頂点と面をCGAL::box_intersection_d持つメッシュを頂点とV面Fを持つ別のメッシュと交差させ、交差するファセットのペアを行としてに格納します。UGIF

igl::intersect_other(V,F,U,G,false,IF);

これは自己交差を無視します。完全を期すために、別の関数で自己交差もサポートしていることに言及します。

igl::self_intersect(V,F,...,IF);

score 1 · Accepted Answer

不足している検索用語はoverlayだと思います。たとえば、これはSurface Mesh Overlayに関する Web ページです。そのサイトには、すべて同じ著者による短い参考文献があります。このトピックに関する別の論文は次のとおりです。「インターリーブスパニングツリーを使用したオーバーレイメッシュ構築」、 INFOCOM 2004 : IEEE Computer and Communications Societies の第 23 回年次合同会議。GIS SE の質問「2 つの不規則三角網 (TIN) のオーバーレイを実行する」も参照してください。

5 に答える 5