CDT Triangulation キット v1.1

 CDT Triangulation キットをv1.1に更新いたしました。主な変更はバグフィックスですが、テスト的にQuad Ruleというオプションもつけてみました。CDTのアルゴリズムは、穴の空いた複数のループを考慮して高い品質の三角形が生成できますが、入力するループに捩れによる交差などがあるとエラーが起こってしまいます。このキットリリース後にDiscordなどでクラッシュバグの報告があったため調べたところ下記のように捩れて線分同士が交差するポリゴンだとクラッシュしてしまうことが判明しました。

対応策として、入力ポリゴンのループが自己交差している場合には、CDTは使用せずにModo標準の三角形分割アルゴリズムを使用することでクラッシュを回避するように変更いたしました。Modo標準の三角形分割は、ILxPolygonクラスのGenerateTrianglesメソッドで提供されていますが、今回はlxu_geometry_triangulation.hppにあるlx::TriangulateFaceを使用しています。こちらの方が標準のポリゴン三角形分割に近い実装です（いつの間に誰が公開しちゃったんでしょう。気が付かなかったです）。GenerateTrianglesは、いわゆるEarClippingアルゴリズムで高速ですが品質はあまり良くありません。

また、ポリゴンが凸包の四角形の場合は、単純に対角線上にポリゴンを分割すれば良いので高速化のために別に処理をするように変更しました。せっかくなので分割する対角線の方向を指定するオプションも追加しておきました。ただし、これは分割する全てのポリゴンに対して適用されるため、まだあまり実用的ではないかもしれません。左右対称に分割されるような処理などが必要そうです。これは今後の課題にしたいと思います。このキットに関してなにかバグや要望がございましたらGithubのIssuesに投稿をお願いいたします。

今回のポリゴンのコーナーが捩れて交差してしまうのは、ポリゴンベベルなどでポリゴンのループをインセットした時、このような捩れができてしまうのがそもそもの原因です。これはまた、別の機会に捩れのないポリゴンインセットができるようなプラグインの開発に挑戦してみたいと思います。