［CEDEC 2011］シリコンスタジオが紹介するゲームの未来。次世代型弾性体表現技術「Shape Matching」とは

田村尚希氏（シリコンスタジオ）

　日本ゲーム業界最大の開発者イベント「CEDEC 2011」が開幕。このところ「最先端のテクニカルな内容」は減少気味のCEDECなのだが，シリコンスタジオは毎回とびきり先端方面の話題を紹介してくれており，今回の講演にも注目が集まるところだ。
　本稿では，CEDEC初日に行われた田村尚希氏＆安田 廉氏による「コンピュータグラフィックス関連の最新論文紹介 〜Shape Matching法とその周辺技術〜」の概要を紹介してみたい。

Shape Matchingとは

　今回紹介された「Shape Matching法」とは，物体の変形に関係した技術で，弾性体の挙動を表現するものだと思っておけばいいだろう。
　ポリゴンメッシュで作られた物体というのは，基本的には固定された形状なのだが，頂点シェーダを使ってプルプル揺らしたりといった変形も広く行われている。今回紹介された手法は，そういった技術の次世代型といえるものだ。

　これまで出てきている弾性体の表現は，大半が「頂点間にばね係数を適用して，動きに対してある程度の変形を行う」といったものだった。ゲーマーなら，すでに多くの実装を目にしていると思うが，これらの処理は制御点が表面しかないため風船的な挙動になりがちだったり，（局所的な変形ならともかく）オブジェクト全体で変形させると計算量が大きくなりすぎたりするという問題があった。

　Shape Matchingは，これとは根本的に異なる手法となる。
　基本的なアイデアは，「ポリゴンの頂点をパーティクルとして扱う」ところから始まる。ポリゴンメッシュ単位で言うなら，「それぞれの頂点をパーティクル化しておく」のだ。
　そのうえで，力学的に変形したあとのメッシュに対し，「元のメッシュを回転させたもの」を用意し，元のメッシュに戻ろうとする力を加えたうえで，メッシュの再計算を行うというアプローチのようである。

　この処理では，元のメッシュの適切な回転角を求める部分がキモとなる。具体的には，移動前後の各頂点の距離の総和が最小となるような角度を求めるとのことで，計算が面倒そうな雰囲気もあるのだが，実はこれを一発で解く数式はすでに存在していたりする。
　ただ，それでもここがキモになるのは，変形時には，回転以外に拡大/縮小や剪断（せんだん）といった要素が絡んでくるため，そのままでは適用できないためだ。そこで，変形から回転要素だけを取り出して処理する「極分解」という処理を行って回転行列だけを取り出す。

　そのあたりの計算手法は下に示したスライドを見てほしいが，途中で3×3行列――元の点へ向かおうとするベクトルの総和みたいなもののようだ――を導き出し，それを極分解の関数に渡すという流れになっている。このようにして物体を変形させようというのがShape Matchingというわけだ。


　そんなShape Matchingの特徴は，高速であることと，必ずしも物理的に正確ではないながらも“それっぽい”動きになること，そして，固さを調整できることなどだ。ポイントベース（＝頂点の情報だけ）で処理できるため，ポリゴンなどより面倒が少ないというのもメリットのようである。
　欠点は，やっぱり物理的に正確ではないこと。そしてポイントベースなので，衝突判定が難しいということだ。

　以上，「欠陥がないわけではないのだが，利点も多い」という事情から，将来的にはゲームでの活用も期待されている。ただ，「高速」とはいっても，すぐ後で述べるクラスタリングを行うとまだまだ負荷は高い。現在は高速化技法や応用技法が模索されており，実際のところ，今回の講演も，「模索の内容」が中心だったりしていた。

Shape Matchingの実用化に向けて

　応用的な部分で最初に紹介されたのが，上でその名を挙げたクラスタリングだ。これは「オブジェクトを構成するメッシュなりパーティクルなりを計算するときに，どのような単位で計算を行うか」に関するもの。オブジェクト全体で1個の回転行列を扱うようでは，たいした変形は期待できない。そこで，複数の部分をつないだ構造を扱えるようにしたのがクラスタリングの手法だと思っておけばよいだろう。

　下の図の例だと，クラスタリングなしでは斜めにズレるだけのものが，クラスタリングすることによって，曲線的に曲がるようになるのが分かる。クラスタリングを細かく取るほど柔軟な物体の表現が可能になるため，Shape Matchingを実際に使う段では，クラスタリングがほぼ前提となってくるようだ。


　このクラスタリングでは，例えば10分割した物体を，そのまま10個のパーツとして扱うこともできれば，データが重複したものとして扱うこともできる。
　これは右の図を見てもらったほうが分かりやすいだろう。「重複している部分が多いと，変形が緩やかになる」傾向があるため，重複を多く取れば取るほど，物体が固そうな表現になるのである。

　ただ，クラスタリングすればするほど，回転行列をたくさん求めなければならないわけで，計算負荷は高くなる。これを解決しようというのが高速化アルゴリズムであり，今回の講演では2種類が紹介されている。

　まず，両方の高速化アルゴリズムで共通なのが，「物体をボクセルで分割し，（メッシュそのものではなく）メッシュを囲むボクセルの変形を行って，そこで出てきた変形をメッシュに適用しようというアプローチである。


　1つは「Fast LSM」（LSM：Lattice Shape Matching）法で，これは，部分部分で回転行列を求めるときに，データの総和として「3×3行列を作る部分」を最適化したものである。要するに，「隣り合った部分だと，同じ頂点群でのデータを足し合わせることは確定しているので，なんとかまとめられないか」という話だ。Fast LSMは，縦・横・奥行き独立で総和処理を行い，演算の中間値を流用していくものだと思っていいだろう。


　もう1つは「ASM」（Adaptive Shape Matching）法で，八分木を用いた階層構造を利用するものである。
　空間を再帰的に2分割していく構造体はゲームでも多用されているが，ASMでは，最小単位のボクセルの側から2倍単位で大きくなるようなデータ構造になっている。単位空間を倍・倍にしていって，8個分（2×2×2）の立方体を親ノードとし，さらにその上のノードなども設定したうえで，子ノードの構成要素に対する総和処理の値（先ほどの3×3行列となるもの）が当該ノードの値となるように設定されている。
　この考えをうまく使って計算量を減らしていこうというアプローチなのである。


　2方式それぞれの利点や欠点などは表にまとめられているが，どちらが実装しやすいかというと「圧倒的にASM」だそうで，Fast LSMのほうは，隣に要素があるかないかなどの判定が煩雑で，デモ作成はあきらめたとのことだった。

Shape Matchingにおけるコリジョン

　続いて，Shape Matchingでは難しいとされる当たり判定について。今回のシリコンスタジオのデモでは，当たり判定は球体で近似したものが使用されている。下の図を見れば大体の雰囲気は分かってもらえると思うが，当たり判定をボクセルの内径そのものに設定すると「めり込み」が起きやすいので，ちょっと大きな球を使用しているとのこと。セルフコリジョンは判定していないそうだが，判定球自体が最初からめり込みあっているわけだから，これはいたしかたない。
　球での近似で大丈夫なのかという疑問も出てくるのだが，実際のデモを見てもほとんど不自然には見えなかったので，かなり現実的な手法のように思われた。


　枠組みとしてのボクセルの変形については以上のようにASMなどを使って行うとして，「ボクセルの中に入っている実際のメッシュをどのように変形させていくか」というスキニングの部分についても少し解説が行われた。
　ここは意外と落とし穴のある部分のようで，「Shape Matchingの計算途中に使った行列を流用しても，変形後の座標そのものが算出できるわけではない」とのこと。この問題を解決するために，「Position Based Dynamics」という手法を用いているそうだが，今回，細かい解説は行われていない。


　以上の処理をCompute Shaderを使いつつ実装した様子をムービーで紹介しておこう。


　「GeForce GTX 560 Ti」を差したPCでは，かなりの量の物体を出しても20fpsくらいは出るとのこと。プログラム最適化の余地はまだ相当にあるそうだが，PCで実装できれば，それほど遠くない将来，やたらとボヨンボヨンしたゲームが出てきてもおかしくはない。

　「現状のコンシューマゲーム機では，（負荷的に）ほぼ無理」とのことで，これは次世代機待ちということになる。ただ，現行世代機においても2Dでの実装は十分可能だそうなので，2Dで実装した画像変形などを含むゲームが登場する可能性はありそうだ。

弾性体を150体落としているところ。右の図で色の濃い部分がボクセルで，明るい部分が親ノード
お堅そうな都庁もグニャグニャに

デモを担当した安田 廉氏（シリコンスタジオ）

　Shape MatchingそのものはNVIDIAの関係者が特許を持っているとかで，そのあたりの問題はクリアになっていないのだが，次世代の弾性体表現で非常に有望な方式なのは確かなので，基礎的な理屈を把握しておくのは無駄ではないだろう。

　それにしても，恐ろしく難しいことを平易に解説し，発表されたばかりの論文で実働デモを作るという，相変わらずの離れ業を披露してくれたシリコンスタジオは，やはり素晴らしい。気は早いが，来年の講演にも期待したいところだ。

シリコンスタジオ

CEDEC 2011レポート記事一覧