Skeleton Extraction by Mesh Contractionを追実装 その１
修論審査やらで全く更新できず。少し落ち着いてきたので、ぼちぼち更新したいと思います。
某開発プロジェクトで、３Dキャラクタの体のパーツごとの対応付けをする必要があったので関連研究を調べてみた。骨を抽出できれば、間接ごとに分解できるんじゃ無いかと思い、見つけたのが、この論文
Skelton Extraction by Mesh Contraction
Oscar Kin-Chung Au, Chiew-Lan Tai, Hung-Kuo Chu, Daniel Cohen-Or, Tong-Yee Lee
Proceedings of SIGGRAPH 2007
メッシュの表面をラプラシアンで平滑化を重ね、線になるまで縮退した点群からボーンとなるような頂点を適切な感覚でサンプリングすると行った感じ。
対象のオブジェクトが閉じたメッシュでないといけないという制約があるものの、３Dキャラクタのポーズや形状にロバストなので、追実装してみようと思う。
ボーン抽出のプロセスは大きく分けて以下の三段階に分かれる。
- 離散ラプラシアンフィルタを使い、メッシュが線に縮退するまで収縮（contraction）させる
- 重複している点群から連続した点群列を生成するために、ハーフエッジによるエッジ削除を逐次行う
- メッシュの中心からはみ出てしまったボーンなどを最適化し、インプットの3Dメッシュの中にしっかりと埋め込まれるようにする
とりあえず、今日までで組んでみたのは、この１の部分だけ。
メッシュを縮小させるには、曲率流ラプラス演算子を使う。ラプラシアンの中身は以下のような感じ
ここで、αとβはある一つの辺を挟む三角形の対になる部分の角度
この各辺に対して、対になる頂点に逐次アクセスするためには、三角形メッシュと頂点情報しか持っていないとかなりめんどくさそう。なので、意を決してハーフエッジクラスを一から組むことにする。
今まで、２回くらいトライしようとして、結局三角形メッシュからの変換部分がよくわからず断念していたハーフエッジだけれども、筑波大の三谷先生の神資料を発見し、描画サイドへの受け渡し部分も含めて、いいクラスを組むことができた。感謝。
http://mitani.cs.tsukuba.ac.jp/lecture/jikken/polygon_operation.pdf
ただ、このラプラシアンを頂点データに掛け合わせたラプラス方程式では境界条件もないため、解が不定になってしまう。そこで、この論文では、元の位置にとどまろうとする制約項を追加し、最小二乗で以下のエネルギー関数を最小化するような頂点v’を計算する。
W_LとW_Hは収縮項と制約項のバランスを保つ重みづけ係数。
ただ、この式を一回解いただけでは、上の図に示すような線まで縮退させることができない。そこで、このW_LとW_Hを更新しながら、反復して上の最小二乗の式を解くことで、最終的に全体を線まで縮退させる。
自分はソルバとしてCG法をチョイス。対称性が高く、巨大行列にも対応できるので間違ってない選択のはず。。。（この状況でもっと適切なソルバがあれば、教えてください。。。）
これで出来た結果は...
このアルマジロのモデルが、
こんな感じに。足や腕など厚みが薄かった部分は線のように縮退しているのが確認できるけど、胴の分厚い部分は収縮しきらなかった。。。
おしい！！！
反復を重ねるとメッシュの縮退部分にかかる値が大きくなり過ぎ、対角成分に値が集中したせいでCG法が解に収束しなくなってしまったことが原因のようだ。論文中にもこの部分について言及があった。
We also check for degenerate faces and avoid any possible numerical errors, such as infinity values or divide-by-zero error.
いや、どうやってcheckしてavoidしてるんすか。。。
今のところ縮退自体をチェックすることは出来るけど、異常値を検出した部分に対してどういう処理をすればいいか、頭を悩ませている。それともソルバ変えた方がいいんですかね？？？
とりあえず、もう少し粘ってみようと思う。
あと一歩だと思うんだよな〜〜
