久しぶりにModoのキットを作ってみました。最近はYT-Toolsの機能拡張ばかりを行っていましたので、プログラミングもPythonばかりでC++を忘れてしまいそうだったのでリハビリも兼ねてDecimateキットというポリゴンリダクションのツールを作ってみました。研究目的の実験的なツールなので、あまり実用性はないかもしれません。
今回もCGALライブラリを利用しており、Triangulated Surface Mesh Simplificationをベースに実装しています。このパッケージで提供するポリゴンリダクションのアルゴリズムはプライオリティキューに入れたエッジを順番に折りたたみ、結合した2つの頂点の位置を再配置するという従来からのアルゴリズムで折りたたむエッジの順番を評価し、結合頂点を再配置するCost Strategyに関する手法がいろいろ研究されています。
近年では高密度のメッシュからアニメーションなどでも利用可能な最適化されたトポロジーをメッシュを求める手法が主流になっていて、リトポロジーの操作も半自動でできるツールも出てきています。実用的にはエッジを折りたたむ従来からのポリゴンリダクションはもうあまり出番がないかもしれませんが、単純にポリゴン数を減らしたい場合などにはまだ活躍できるかもしれません。
このキットではCGALが提供する３つのアルゴリズムをCost Strategyというオプションから選べるようにしています。
Edge Lengthは、最も単純な方法で長さの短いエッジから順番にエッジを折りたたみ、結合した頂点はエッジの中間位置に再配置します。単純ですが一番高速です。ModoのPolygon Reductionもこの方法に近いです。
Lindstrom-Turk Cost and Placement Strategyは、簡略化された表面メッシュを各ステップで元の表面メッシュ（または前のステップの表面メッシュ）と比較しない手法をとっていて、元の表面メッシュや局所的な変更履歴といった追加情報を保持しないため、メモリコストに優れています。Decimateキットではこれをデフォルトにしています。
Garland-Heckbert Cost and Placement Strategyは、結果のメッシュを元のメッシュと比較せず、局所的な変更履歴にも依存しまが、各頂点に割り当てられた二次行列を用いて、元のメッシュへのおおよその距離を符号化します。これにより均一な三角形分割を作成できるようになり、特徴感度を維持しながらノイズに対する耐性が向上するという手法らしいです。
また、境界のポリゴンにあるエッジやマテリアルとマテリアルの間にあるエッジなど重要なエッジを指定するオプションを用意しました。これらに該当するエッジはCGALのedge_collapse関数に拘束エッジ（constrained edges）としてインプットされます。Modo上でロックを設定したエッジは自動的に拘束エッジになります。
リダクション処理を終了する条件は、全体のエッジ数に対する比率もしくは折りたたむエッジの数で指定します。Decimateキットでは内部的に対象ポリゴンを三角形に分割してから処理を行っているため、最終的なポリゴン数は元のメッシュのエッジ数からの比率にはならないことに注意してください。縮退しなかった三角形は可能な限り元のポリゴンに戻しています。
