c++ - 堅牢で高速な複雑なポリゴン (穴あり) の三角形分割 C/C++ ライブラリ (寛容なライセンス付き)

Question

私はオープンソースゲームのBitfighterの開発者です。次の SO 投稿によると、ゲーム内 AI (ロボット) で使用するメッシュゾーン生成に優れた「Triangle」ライブラリを使用しました。

しかし、ゲームを Debian 用にパッケージ化しようとしたときに、小さな問題が発生しました。「Triangle」ライブラリを使用すると、ゲームが「非フリー」と見なされてしまいます。

「Triangle」ライブラリのパフォーマンスには非常に満足しており、手放したくありません。ただし、ライセンスの問題に対処するのも好きではありません。したがって、私たちは、堅牢性と速度において「Triangle」に匹敵する、適切で寛容にライセンスされた代替品を見つけるための探求に着手しました。

大規模で複雑な領域を三角形に分割するための C または C++ ライブラリを探しています。これは、穴だけでなく、任意の方法で一緒に配置された任意のタイプの不規則な多角形を処理できます。堅牢性は私たちの主なニーズであり、スピードも同様に重要です。

poly2triを見つけましたが、エッジが一致するポリゴンを処理できないというバグに悩まされています。

いくつかのライブラリを見つけましたが、いずれも遅すぎるか、ホールを処理しないか、何らかのバグに悩まされているかのいずれかであると思われます。現在、ポリパーティションをテストしており、大きな期待を寄せています。

優れた「Triangle」ライブラリに代わる最良の代替手段は何ですか?ただし、ライセンスは許可されていますか?

score 19 · Accepted Answer

解決策を見つけました。結局、これはpoly2triであり、優れたClipperライブラリを使用し、入力にいくつかのマイナーなアルゴリズムを追加しました。

私たちのプロセスは次のとおりです。

NonZero ワインディングのユニオンを使用して、すべての穴をクリッパーに通します (これは、内側の穴が外側の穴と反対方向に巻かれることを意味します)。また、Clipper は、イプシロン内で繰り返しのないきれいな入力ポイントを保証します。
反時計回りと時計回りに巻かれた穴にフィルターをかけます。時計回りの穴は、穴が遠回りで、三角測量が必要な別の同心円状の領域が内部にあることを意味しました
poly2tri を使用して、外側の境界と見つかった各時計回りのポリゴンを三角形化し、残りの穴が境界の 1 つ内で見つかった場合は poly2tri への入力として使用します。

結果: poly2tri は Triangle とほぼ同じ速さで三角測量を行うように見え、これまでのところ、私たちが投入したすべてのものに対して非常に堅牢です。

興味のある方は、コードの変更をご覧ください。

アップデート

私は、クリッパーから poly2tri へのコードを、堅牢性を追加した別のライブラリに引き出そうとしました。

score 1 · Accepted Answer

CGAL の 2D Triangulations パッケージを見ることができます。穴のある多角形を三角測量する例をここに示します。パッケージのライセンスは GPLv3+ です。

必要に応じて、このパッケージだけを抽出するのは難しくありません。

score 1 · Accepted Answer

ちょっとした補足として：

私は最近、窓枠を家の壁に切り込むための複雑なポリゴンクリッパーと三角測量機を実装する必要がありました。

Vatti クリッパーの結果には満足していましたが、poly2tri で使用されている Delaunay 三角形分割は重すぎて、壁の面の重心座標に沿ってウィンドウフレームをスムーズにドラッグできませんでした。少し頭を悩ませた後、このはるかに単純な三角形をだまして穴を操作することになりました。

私がしたことは、最も短いクリッピングポリゴンの高さで壁面を水平方向に分割することでした。私の場合、それらは常に長方形ですが、そうである必要はありません。とにかく、クリッパーは通常のポリゴンまたは凹面ポリゴンでのみ動作するように強制されるため、安価な三角形分割法を使用できます。

これが機能していることを示すスクリーンショットを次に示します。

お役に立てれば。

3 に答える 3