穴のあるポリゴンの三角形分割
https://stackoverflow.com/questions/406301
-
03-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
ポリゴンを三角形に分解するためのアルゴリズムまたはライブラリ（より良い）を探しています。これらの三角形をDirect3Dアプリケーションで使用します。最適なオプションは何ですか？
これまでに見つけたものは次のとおりです。
- ベンディスコのメモ
- FIST：ポリゴンの高速産業強度三角測量
- CGAL は三角測量を提供することを知っていますが、穴をサポートしているかどうかはわかりません。
この分野での以前の経験を持つ人々からの意見を本当に感謝します。
編集：これは2Dポリゴンです。
解決
Jonathan Shewchukの三角形ライブラリは驚異的です。過去に三角測量の自動化に使用しました。小さい三角形や狭い三角形などを避けようとするように依頼することができます。三角形分割ではなく、三角形分割。
他のヒント
他のライブラリの選択肢をさらに提供するには：
Polyboolean。私はこれを試したことはありませんが、有望に見えます： http：//www.complex-a5。 ru / polyboolean / index.html
一般的なポリゴンクリッパー。これは実際には非常にうまく機能し、三角測量とクリッピングと穴の穴を行います： http://www.cs.man.ac.uk/~toby/alan/software/
個人的な推奨事項：GLU（OpenGL Utility Library）のテセレーションを使用します。コードは堅実で、GPCよりも高速で、生成される三角形が少なくなります。 libを使用するために、初期化されたOpenGL-Handleなどは必要ありません。
OpenXシステムライブラリをDirectXアプリケーションに含めるというアイデアが気に入らない場合は、解決策もあります。SGIOpenGLリファレンス実装コードをダウンロードして、そこから三角測量器を持ち上げます。 OpenGL-Typedefの名前と列挙型でいっぱいの名前を使用します。それでおしまい。コードを抽出して、1、2時間でスタンドアロンライブラリを作成できます。
一般に、私のアドバイスは、うまく機能するものを使用し、独自の三角測量を書き始めないことです。
耳切りアルゴリズムまたはスイープラインアルゴリズムについて読んだ場合は、独自のロールを作成するのは魅力的ですが、実際には、計算ジオメトリアルゴリズムは、安定して動作し、クラッシュせず、常に戻るように書くのは非常に難しいです意味のある結果。数値の丸め誤差は累積し、最終的にはあなたを殺します。
仕事をしている会社のCで三角測量アルゴリズムを作成しました。コアアルゴリズムを機能させるには2日間かかりました。あらゆる種類の縮退した入力で動作させるには、さらに2年かかりました（フルタイムで動作していませんでしたが、私を信じてください-必要以上に多くの時間を費やしました）。
CGALには必要なツールがあります。 制約付き三角測量
単純に、ポリゴンの境界（穴の境界を含む）を制約として指定できます（すべての頂点を挿入してから、制約をVertex_handlesのペアとして指定することをお勧めします）。
その後、任意のトラバーサルアルゴリズムによって三角形分割の三角形にタグを付けることができます：無限の頂点に入射する三角形から開始し、外側にあるとタグ付けし、制約を超えるたびに反対のタグに切り替えます（内側の場合以前に三角形をインサイダーとしてタグ付けしていた場合、以前は三角形をアウトサイダーとしてタグ付けしていました。
poly2triライブラリは、三角形分割に必要なものであることがわかりました。私が試した他のライブラリー（libtessを含む）よりもずっときれいなメッシュを生成し、穴もサポートします。それは多くの言語に変換されました。ライセンスは新しいBSD であるため、どのプロジェクトでも使用できます。
自分で比較的簡単に穴を追加できます。基本的に、CGALに従って入力ポイントの凸包に三角形分割し、次に、中心が穴ポリゴンのいずれか（または外部境界の外側）にある三角形を削除します。大規模なデータセットの多数の穴を処理する場合、マスキングプロセスを使用してこのプロセスを大幅に高速化できます。
編集：このテクニックの一般的な拡張は、船体の弱い三角形を取り除くことです。この場合、最長のエッジまたは最小の内角が所定の値を超えます。これにより、より優れた凹型船体が形成されます。
libtess2を試す
https://code.google.com/p/libtess2/downloads/list
元のSGI GLUテセレータに基づく（リベラルライセンス付き）。多数の小さなmallocに関するメモリ管理の問題を解決します。
これは有限要素解析の一般的な問題です。 「自動メッシュ生成」と呼ばれます。 Googleは、商用およびオープンソースへのリンクを含むこのサイトを見つけました。ソフトウェア。通常、開始するジオメトリの何らかのCAD表現を想定しています。
別のオプション（非常に柔軟なライセンスを使用）は、VTKからアルゴリズムを移植することです：
このアルゴリズムはかなりうまく機能します。直接使用することも可能ですが、VTKへのリンクが必要であり、必要以上のオーバーヘッドが発生する可能性があります（ただし、他にも多くの優れた機能があります）。
これは、制約（穴/境界など）をサポートし、XY平面にある必要のないサーフェスの三角測量をサポートします。また、他では見たことのない機能もサポートしています（アルファ値に関する注意を参照してください）。
C＃で3Dポリゴン triangulator を耳のクリッピング方法を使用して実装しました。使いやすく、穴をサポートし、数値的に堅牢で、（自己交差ではなく）凸/非凸ポリゴンをサポートします。
