CDT Triangulation キット v2.0

 CDT Triangulation キットを大幅に更新いたしました。最初のバージョンをリリースした際に、Conforming Delaunay TriangulationでFEMなどで使用するような最適化された三角形を生成するようにできないかとのリクエストがあり、これに対応するため最初のバージョンで使用していたCDTライブラリをCGALに変更いたしました。CGAL(Computational Geometry Algorithms Library)は、幾何計算分野における歴史のあるライブラリで多くの優秀な幾何計算アルゴリズを利用することができます。オープンソースで利用する場合は、GPL、LGPLライセンスに基づいて利用することができます。ModoはCGALの商用ライセンスは取得していなかったので、今回初めて個人のオープンソースプロジェクトで利用させていただきました。

Constraint Delaunay Triangulationに関しては、最初のバージョンと処理結果は変わりません。元のポリゴンのエッジを拘束条件として、元の頂点のみを使用して三角形分割の処理を行います。

Conforming Delaunay Triangulationのために新たに追加したのは、三角形の最長エッジサイズ(Minimum Edge Size)と最小角度(Maximum Angle)です。最長エッジサイズは、分割した三角形のエッジのサイズを規制するもので、このサイズが短いほど細かな三角形が生成されます。CGALのライブラリでは絶対的な長さを設定するのですが、このキットでは元のポリゴンのサイズに対する相対的なサイズでも指定することができるようにしています。これにより元のポリゴンの大きさが変わっても同じ分割を維持することができます。最小角度は、生成する三角形のコーナーの角度を指定するものです。理想的な角度は正三角形の60°ですが、ここではデフォルトを20.7°としています。いろいろ試してみたのですがこの値を大きくし過ぎるとハングしてしまうことがあったため、上限を30°にしています。三角形の密度は最長エッジサイズを主としてコントロールしたほうが良さそうです。

その他、v2.0では分割した新しい三角形とそのエッジと頂点をSelect By Previous Operationで利用できるように変更いたしました。

CGALには、他にも素晴らしいアルゴリズムが数多く公開されています。このライブラリを使って、もっといろいろなプロジェクトにチャレンジしてみたいと思います。