ポリゴン間引き - カタチづくり

ポリゴンを間引きするプログラムを作った。
株式会社カタッチ / 研究室 / ポリゴン間引き

左が間引き前。右が間引き後。・・・って、見りゃ分かるか。

意外と苦労してしまった。以前に似たものを作った経験があったので、２〜３日でできるんじゃないかと甘く見ていた。いざやってみると、いろいろとツマラナイことでハマッてしまい、結局一週間近くかかってしまった。うーむ、まだまだ修行が足らんなぁ。

edge-collapse

間引き操作は edge-collapse という操作を繰り返すことで行う。では edge-collapse とはどんな操作なのか。説明するには図が必要だけど、図を描くのはめんどくさいなぁ。。。と思っていたら、分かりやすいPDF資料を発見。
http://www.cs.cornell.edu/boom/2003sp/ProjectArch/3DEffectsAnim/lodfig1.pdf

さらにGoogleのイメージ検索で次の図を発見。

http://acc6.its.brooklyn.cuny.edu/~lscarlat/graphics/LOD/LOD.htmより

"collapse" とは「崩壊」とか「倒壊」とかいう意味。だから edge-collapse を直訳すると「辺の崩壊」だ。辺の両端点を一点に重ね合わせるようにして、辺を「潰して」しまうイメージの操作となる。これは三角形メッシュに対する代表的な「オイラー操作」のひとつである。

edge-collapse 操作を一回行うと、

頂点が1つ減少
辺が3つ減少
面が2つ減少

する。この操作を繰り返すことで、徐々にポリゴンが間引かれていくのだ。

QEM

そうはいっても、めちゃくちゃにedge-collapse操作をしたら形状が崩れてしまう。元の形状をできるだけ維持するようにedge-collapseしなくてはならない。これには次のような戦略を採る。

edge-collapseを実行すると、多かれ少なかれ形状が歪む。その歪みの度合いを適切なエネルギー関数で点数付けするのだ。そうすると、すべてのエッジに対するひずみエネルギーが計算できる。そのひずみエネルギーが最も小さいエッジから順にedge-collapseしていけば良い。

ここで使える代表的なエネルギー関数としてQEM(Quadratic Error Metric)という手法がある。今回作ったプログラムもQEMを利用している。現実の複雑なデータに対してはもっとエネルギー関数を工夫する必要があるかもしれないが、現段階では基本どおりのナイーブな実装だ。

QEMの詳しい解説は面倒なのでパス。簡単に言うと、edge-collapse操作の前後で生じる体積変化を最小に抑えよう、という手法。（正確な表現ではない）

問題点

この間引きアルゴリズムはよく出来たすばらしい手法だと思うんだけど、問題もある。間引き前と間引き後でどれだけのひずみが累積したのかが分からないのだ。つまり、「元の形状から誤差0.001mmの範囲内で間引きを実行」という指定ができない。
CG(Computer Graphics)の目的ではこういった精度が問題になることはないけど、CADの目的では問題になるかもしれない。機会があったらこれを解決する方法も考えてみたい。