CDT Triangulation キット

 標準の三角形分割の機能よりも品質の良い三角形を生成するCDT TriangulationキットをGitHubにリリースしました。以前からModoのアルファテスターの方々からModoの三角形分割のアルゴリズムを改善してほしいとの要望がありました。将来リリース予定のModoで実装する準備をしていたのですが、開発が中止になりましたので、オープンソースのライブラリを利用してModoのプラグインの形式で作り直すことにいたしました。コマンド版とメッシュオペレータ形式の２つがキットに含まれています。

今回実装した三角形分割は、制約付きドロネー三角形分割（Constraint Delaunary Triangulation）というアルゴリズムを使っています。 制約付きドロネー三角形分割は、ドロネー三角形分割に元のポリゴンエッジを必ず使用するという制約を付加したもので、多くのアプリケーションで広く使われています。

CDT三角形分割を実現するModoのプラグインを実装するにあたり、今回はartem-ogreさんが、Githubで公開しているCDTのオープンソースライブラリを利用させていただきました。このライブラリの実装はとても堅牢で、外ループに加えて、穴を表現する内ループも任意に追加することができるので便利です。

Modoの場合、鍵穴ポリゴン(Keyhole Polygon)と読んでいるちょっとイレギュラーなポリゴンを許容しているので、これを外ループと内ループに分解してCDTに三角形分割させることができました。鍵穴ポリゴンは、外ループと内ループを繋ぐ双方向のブリッジエッジを持つポリゴンで、四角形をそれよりも小さい四角形を使って軸ドリルをすると内と外を繋ぐエッジを持った穴の空いたポリゴンができます。これが鍵穴ポリゴンで、穴のあるテキスト文字をフリーズした時に生成されます。たとえば「虫」という文字をフリーズすると双方向のエッジが二つ追加された一筆書きの一つのポリゴンが生成されます。ポリゴンの頂点リストに同じ頂点が複数存在するポリゴンなので、Modoのモデリングツールはこのような特殊なポリゴンもサポートする必要があるので注意が必要です。他の3DCGアプリケーションでは、エラーになりそうな気がしますので、他のファイル形式に出力する際には三角形分割などして対応した方が良さそうです。

下記はModoの標準の三角形分割コマンドで上記のポリゴンを分割した結果（上）とCDTで分割した結果（下）の比較です。明らかにCDTで生成した三角形の方が正三角形に近いきれいな三角形が生成されています。

あるユーザーさんから、CDT以外にも有限要素法などで使われているポリゴンの内部に頂点を追加し、内部に三角形を密集するタイプの適応型ドロネー三角形分割もサポートできないかというリクエストをいただきました。これはまた今後の研究で考えてみたいと思います。