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してるんすか。。。
今のところ縮退自体をチェックすることは出来るけど、異常値を検出した部分に対してどういう処理をすればいいか、頭を悩ませている。それともソルバ変えた方がいいんですかね？？？
とりあえず、もう少し粘ってみようと思う。
あと一歩だと思うんだよな〜〜
デザインは自ら進化するのか？ "Fit and Diverse"
最近、Structure Synthesis系の論文を読み漁っているので、その中からちょっと紹介。
Fit and diverse: set evolution for inspiring 3D shape galleries
Kai Xu, Hao Zhang, Daniel Cohen-Or, Baoquan Chen
Proceedings of SIGGRAPH 2012
まとめ（普通の人向け）
家具や家電、キャラクターなどには様々なデザインが要求される。しかし、人間のアイデアから生まれるデザインは枯渇してしまうんじゃないだろうか？もう少し、現実問題で見ても、プロダクトデザイナーは０からデザインを考えるよりもいくつかのデザインの組み合わせでデザインを考えたりする場合もあるので、自分のインスピレーションを掻き立てるような新しいデザイン群を必要とする場合は多くある。今あるデザイン同士が交尾（？）して新しいデザインが勝手に生み出されてくれたら、デザイナーの苦労も軽減されそうである。
生物の世界では、さまざまな種のかけ合わせによって、より種に多様性を生み種の生存確率を向上させるのは周知の事実だ。この概念をデザインに適用してしまおうというのがこの研究だ。
親となるようなあらかじめ用意されたデザインの集合から、任意のデザイン同士を”交配”させることによって、新たなデザイン（子デザイン）が生み出される。これを何世代にも渡って繰り返すことによって、新しいデザイン群が作り出される。各世代において、（生存競争のような要領で）ユーザーが好みのデザインを選り分けることで、優性遺伝・劣性遺伝のように、自分の好みを反映させながら新しいデザインを生み出せるというのも大きなポイントだ。
ある程度形の決まっている家具だけでなく、TV向けモンスターをどんどん交配させて新しいキャラクターが作られているのはかなり衝撃である。将来的には、デジタルファブリケーションの技術と組み合わせて、生産機能を持たせることができればビジネスとしても十分に機能しそうだ。現状では物理的な拘束（重力下で倒れたりしないか？や体重がかかりすぎて折れてしまう部分はないか？）などの考慮は厳密にはされていないので、選別過程にフィルタリングしておくなどの処理で、実用化することも近いうちにできるんじゃないだろうか？
忘備録（研究者向け）
”交配”について具体的に説明すると、二つのデザインの意味空間上で等しいパーツ同士（背もたれなら背もたれ同士、脚なら脚同士）を「交換（Crossover)」「変形（Mutation)」させることによって親のデザイン特徴をキープしながら新しいデザインが生み出される。意味空間上で厳密な対応付けができない部分（たとえば背もたれの中の支え木的なもの）はFuzzy partと呼んで、形状ベースの対応からCrossoverとMutationを行っているらしい。2つのオブジェクトの距離のメトリックとして、ハウスドルフ距離（Hausdorff distance）というものがあるのを初めて知った。各パートを方向付きバウンディングボックスでフィットさせることで、各パーツ同士の比較が可能になっているというのも面白い。
ここらへんの領域は完全に、初体験ゾーンなので、実装レベルでの理解にはもう少しかかりそう。
カラダの中身を転写する ”Anatomy Transfer”
最近、解剖学的なアプローチの研究に興味があるので、その中から衝撃的だった研究を忘備録がてら紹介する。
Anatomy TransferDicko Ali-Hamadi, Tiantian Liu, Benjamin Gilles, Ladislav Kavan, Francois Faure, Olivier Palombi, Marie-Paule Cani
Proceedings of SIGGRAPH ASIA 2013
Fast Forward (CGの学会では、自分の発表に興味を持って見に来てもらうために、ファストフォワードという1分弱の中で自分の研究を紹介するセッションがある。仮装したりコメディ調で笑いを取りに来る人がかなり多くて、ある意味一番の見どころかもしれない笑)
Anatomy Transfer Fast Forward - YouTube
Long Version (Demo)
まとめ（普通の人向け）
MRIなどの、解析技術の発展により、人体のかなり精密なスキャンデータが取れるようになってきている。これによって、筋肉等も考慮した精密なシミュレーションができるようになったり、医療だけでなくCGや教育方面への応用なども期待されている。かといって、全員のカラダを長い時間かけてスキャンするのは大変なので、一つの精密な内臓モデル（筋肉、血管、骨、内臓、脳みそなど全部）を違う体に転写しちゃいましょうという研究。最大の肝は、体型がまったく異なったり、ポーズが異なったりするときでも内臓転写ができるというもの。（論文中では、シンプソンズのお父さんやポパイ、オリーブ、ダビデ像（！）や狼男なんかにも内臓を飛ばしている。上のムービーは必聴）
この汎用性と、解剖学的知見をしっかりあわせもてれば、表面の３Dスキャンだけで、内臓のスキャンまで済んでしまう。。。といった未来もそう遠くないかもしれない。ソースが見つからなかったが、噂によると今年のEurographicsで企業ブースがあったそうなので、どうやらこの研究をもって起業したらしい。近いうちに、どこかのメディアに取り上げられて目にする機会が増えるかもしれない。
忘備録（研究者向け）
転写のメソドロジー
結果がすごいので、ものすごく恐ろしいことをやっているように見えるが、コアの手法自体は比較的シンプル。大まかにいうと
- インプットのボディと、転写先のボディの表面のスキンの対応付け
- 転写先のボディの皮下脂肪を埋め込む（MRIなどの解剖学的アプローチで厳密にやる方法だけでなく、シンプソンのような架空のキャラにも適用するためファットマップと呼ばれるツールを使って皮下脂肪の厚さを調節できる）
- インプットのボディから骨だけを転写先のボディに内挿
- 転写先のポーズが左右非対称な場合（e.x.,ダビデ像）、骨がいびつに歪んでしまったり対称性が失われるので、骨はアフィン変換に限定し、弱いばねでポジションをコントール
- 皮下脂肪と骨の間に内臓が同じバランスで分布してる仮説のもと、Laplace Interpolation(画像の空白部分の穴埋めなんかに使われる手法を3次元拡張。境界条件はインプットの皮下脂肪と骨の境界部分)によって内部を埋める
といった感じ。要は、境界部分をしっかりと設定すれば、中はそれっぽく補完されてくれるということ。空間中に何かを埋め込んで、転写するというアイデアは、それなりに応用性がありそう。もしかしたら使えるかもしれない。
ポーズに依存せず、表面スキンの対応付けだけでここまで行くのは、にわかには信じがたい。ボーンの転写部分についてはもう少し読み込んでみようと思う。
デジタルファブリケーション最前線 風船デザイン
とりあえず、試験的に今日読んだ論文を紹介してみる。
Computational Design of Rubber Balloons
M. Skouras, B. Thomaszewski, B. Bickel, M. Gross
Proceedings of Eurographics
まとめ（普通の人向け）
風船が膨らんだときに、自分の好きな形に膨らんでくれたら。。。という願いをかなえる天下のディズニーリサーチ チューリッヒのデジタルファブリケーションの研究。好きな３Dモデル（動画だとアルマジロとかウサギとかがインプット）を用意したら風船が膨らんだときに、その３Dモデルにできるだけ近づくようにしぼんだ時の形を物理シミュレーションと数値最適化によって計算してくれるというもの。風船の素材が今のところシリコン限定だったり、凹の部分や平らな部分を再現するのは難しかったりと実用レベルではあと一歩のところだけれど、膨張時のゴムの物理モデルなどが改善されれば、より汎用性の高いシステムになりそうで楽しみ。
現状のデジタルファブリケーションの問題として、大型のものを作るには、パーツごとに分解して製造しなければならず、材料費、組み立てや部品分解も込みでそれなりにコストがかかるというものがあった。しかし、風船なら、膨らませることで欲しい形を再現することができるので、鋳型のサイズも小さくできるし、材料費もかなりうくという一石二鳥で超画期的。ディズニーはパーマンのコピーロボットを作ろうとしているのではないかと邪推している。（あ、駆動部がなきゃ動かないか。。）
このシステムと３Dスキャンの技術を組み合わせれば、オーダーメイドのダッチワイフが一家に一台の時代がやって来るかもしれない。。。
忘備録（研究者向け）
システムのアウトライン
入力の３Dモデルとバルーン膨張時のジオメトリをDiscrete Shell [Grinspun et al, 2004]の関係式に基づいてエネルギー関数化して最適化を行う。束縛条件に膨張状態の面内応力と圧力の平衡条件を入れることで、初期形状（しぼんだ状態）も同時に計算を行う。束縛条件を適用するためには、ペナルティ法や逐次計画法なんかがあるが、自由度を抑えることや安定性を考慮してラグランジュの未定乗数法を採用したとのこと。
バルーンの物理モデル
CGの世界でよく使われる弾性体モデルと実測のバルーンの変形を比較して、最適なモデルを選択しているのはとても興味深かった。
Neo Hokean体はまったく風船の変形を近似できておらず、Mooney Rivlin体やStVK体はまあまあだけれども、やはり風船の非線形な変形を近似できていない。そこで彼らは、不変量の指数関数（上の3つは指数関数でなく、多項式）で歪エネルギーを近似するHart Smith体を用いて、よりよい近似モデルを得ることに成功した。不変量の指数関数を用いるHart Smith体は聞いたことがなかったので、一ついい勉強になった。
ブログ始めます
最近まで2か月ほど、シリコンバレーで仕事をしながら研究していて、多くのスタートアップのエンジニアやCEOなんかと毎日のように顔を合わせていた。シリコンバレーなんて言ったら技術力の塊みたいなイメージを持ちがちだけど、かなりの数のスタートアップでリサーチャー的なバックグラウンドを持っている人がいなくて、アカデミックでは10年以上前に発表されたようなものが意外ともてはやされたりしていた（特にコンピュータビジョン）。コンピュータサイエンス出身の人でも大体は学部かマスターまでで、高い専門性を持ったPhDの人たちはそのままアカデミックにいるか、資金力のあるAdobeやGoogleみたいな大きい企業に行ってしまうようで、専門性の高い技術はあんまりスタートアップに流れていないんだな～という思いを漠然と抱きながら帰国して今に至る。
意外と「今アカデミックの世界でどんな研究がされているのかを違うクラスターの人に紹介する」っていうのは需要がありそうな気がしたので、自身の研究の忘備録もかねて、面白い研究を紹介してみることにする。前半は、研究のバックグラウンドがない人でもわかるように、「何ができるのか」「今後の世の中にどんなインパクトがある（と俺は思う）のか」に焦点を絞って簡潔に、後半は自分の忘備録がメインの目的なので、技術的なディテールなんかをまとめるつもり。同じような領域で研究している人が少しでも参考にしてくれるようになってくれたら感激の極み。
中には、技術的な面で理解が間違っている部分もあると思うので、「それ違うだろ」みたいな意見はどんどんコメント等していただけるとうれしいです。
