28

ポリゴンを三角形に分解するためのアルゴリズムまたはライブラリ（より良い）を探しています。Direct3Dアプリケーションでこれらの三角形を使用します。利用可能な最良のオプションは何ですか？

これが私がこれまでに見つけたものです：

  1. ベンディスコーのメモ
  2. FIST：ポリゴンの高速工業用強度三角形分割
  3. CGALが三角測量を提供することは知っていますが、穴をサポートするかどうかはわかりません。

この分野での経験のある方からのご意見をいただければ幸いです。

編集：これは2Dポリゴンです。

4

9 に答える 9

21

ライブラリの選択肢をさらに増やすには、次のようにします。

ポリブール。私はこれを試したことはありませんが、有望に見えます: http://www.complex-a5.ru/polyboolean/index.html

一般的なポリゴン クリッパー。これは実際には非常にうまく機能し、三角測量だけでなく、クリッピングと穴の穴も行います: http://www.cs.man.ac.uk/~toby/alan/software/

私の個人的な推奨事項: GLU (OpenGL Utility Library) のテッセレーションを使用します。コードは堅実で、GPC よりも高速で、生成される三角形が少なくなります。ライブラリを使用するために、初期化された OpenGL ハンドルなどは必要ありません。

DirectX アプリケーションに OpenGL システム ライブラリを含めるという考えが気に入らない場合は、解決策もあります。SGI OpenGL リファレンス実装コードをダウンロードして、そこから三角測量器を持ち上げるだけです。OpenGL-Typedef 名と列挙型を使用するだけです。それでおしまい。コードを抽出して、1 時間か 2 時間でスタンドアロンの lib を作成できます。

一般的に、私のアドバイスは、すでに機能しているものを使用し、独自の三角測量を書き始めないことです。

イヤークリッピング アルゴリズムやスイープライン アルゴリズムについて読んだことがあれば、独自のアルゴリズムを作成したくなるかもしれませんが、計算幾何学アルゴリズムは、安定して動作し、決してクラッシュせず、常に意味のある結果を返すように記述するのは非常に難しいというのが実情です。 . 数値の丸め誤差が蓄積され、最終的にはあなたを殺します。

一緒に働いている会社のために C で三角測量アルゴリズムを書きました。コア アルゴリズムが機能するようになるまでに 2 日かかりました。あらゆる種類の縮退された入力を処理するのに、さらに 2 年かかりました (私はフルタイムで作業していませんでしたが、信じてください。必要以上に多くの時間を費やしました)。

于 2009-01-02T12:26:25.023 に答える
20

Jonathan Shewchuk のTriangle ライブラリは驚異的です。過去に三角測量の自動化に使用しました。小さい/狭い三角形などを回避するように要求することができるので、単なる三角形分割ではなく、「適切な」三角形分割を考え出すことができます。

于 2009-03-09T13:48:29.860 に答える
12

CGAL には必要なツールがあります: 制約付き三角形分割

ポリゴンの境界 (穴の境界を含む) を制約として単純に指定できます (すべての頂点を挿入してから、制約を Vertex_handles のペアとして指定するのが最適です)。

次に、トラバーサル アルゴリズムによって三角形分割の三角形にタグを付けることができます。無限頂点に付随する三角形から始めて、外側としてタグ付けし、制約を越えるたびに、反対のタグに切り替えます (以前にタグ付けしていた場合は内側)。以前にトライアングルをインサイダーとしてタグ付けしていた場合は、トライアングルをアウトサイダーとして、アウトサイドとして）。

于 2009-01-02T12:22:02.393 に答える
5

poly2tri ライブラリは、まさに三角測量に必要なものであることがわかりました。私が試した他のライブラリ (libtess を含む) よりもはるかにクリーンなメッシュを生成し、穴もサポートしています。たくさんの言語に変換されています。ライセンスはNew BSDですので、どのプロジェクトでもご利用いただけます。

Google Code の Poly2tri ライブラリ

于 2014-02-13T00:35:02.223 に答える
3

libtes2を試す

https://code.google.com/p/libtess2/downloads/list

元の SGI GLU テッセレータ (リベラル ライセンス) に基づいています。多数の小さな malloc に関するメモリ管理の問題を解決します。

于 2013-08-08T20:57:35.567 に答える
2

自分で比較的簡単に穴を追加できます。基本的に、CGAL に従って、入力ポイントの凸包に三角形分割し、中心が穴ポリゴンの内側 (または外部境界の外側) にある三角形を削除します。大規模なデータセットで多数の穴を処理する場合、マスキング手法を使用してこのプロセスを大幅に高速化できます。

編集: この手法の一般的な拡張は、最長のエッジまたは最小の内角が特定の値を超える船体の弱い三角形を間引くことです。これにより、より良い凹面の船体が形成されます。

于 2009-01-02T09:08:18.800 に答える
1

これは、有限要素解析でよくある問題です。これは「自動メッシュ生成」と呼ばれます。Googleは、商用およびオープンソースソフトウェアへのリンクがあるこのサイトを見つけました。彼らは通常、開始するジオメトリのある種のCAD表現を想定しています。

于 2009-01-02T14:04:37.303 に答える
0

別のオプション（非常に柔軟なライセンスを使用）は、VTKからアルゴリズムを移植することです。

vtkDelaunay2D

このアルゴリズムはかなりうまく機能します。直接使用することは可能ですが、VTKへのリンクが必要です。これには、必要以上のオーバーヘッドが発生する可能性があります（ただし、他にも多くの優れた機能があります）。

制約（穴/境界など）をサポートするだけでなく、必ずしもXY平面にあるとは限らないサーフェスを三角形分割します。また、他では見たことのないいくつかの機能もサポートしています（アルファ値に関する注記を参照）。

于 2009-03-10T20:24:53.207 に答える