Shape Matching

This explanation is currently available in Japanese.

ひとことで

柔らかい物体を、点同士をばねでつながずに、「元の形をいちばんよく重ねられる回転と位置」を毎ステップ求め、その重ねた形へ各点を引き戻すことで動かす方法です。Müller らが 2005 年に発表した「Meshless Deformations Based on Shape Matching」がもとで、どんな形のメッシュにもそのまま使え、非常に安定しているのが特徴です。

ゲームでの使いどころ

• ゼリー・スライム・柔らかいキャラクター：ぷるぷる揺れて、つぶれても必ず元の形に戻る物体。
• 軽量なソフトボディ：メッシュの頂点をそのまま点として使えるので、ばねの網や四面体分割を作る手間がいりません。
• 小物の揺れ：果物、クッション、風船など、軽くて数の多い物に向いています。
• 位置ベース物理との組み合わせ：シェイプマッチングの目標の形への引き戻しは、位置ベース物理の拘束の 1 つとして扱えるので、布や衝突と同じ仕組みで解けます。NVIDIA FleX の柔らかい物体がこの方式です。

しくみ

元の形の各点の位置を $\mathbf{x}^0_i$、今の位置を $\mathbf{x}_i$ とします。

1. 重心：元の形の重心 $\mathbf{c}^0$ と、今の重心 $\mathbf{c}$ を求め、各点の重心からの位置 $\mathbf{q}_i = \mathbf{x}^0_i - \mathbf{c}^0$、$\mathbf{p}_i = \mathbf{x}_i - \mathbf{c}$ を作ります。

2. 形の対応を表す行列：

これは「元の形の点 $\mathbf{q}_i$ を今の点 $\mathbf{p}_i$ に移す変形」の手がかりです。

3. 回転を取り出す：$\mathbf{A}_{pq}$ を「回転 $\mathbf{R}$」と「伸び縮み」に分解し（極分解）、回転 $\mathbf{R}$ だけを使います。これが、元の形を最小二乗の意味でいちばんよく重ねられる回転です。

4. 目標の形：元の形を回転させて今の重心に置いたものが、各点の目標位置です。

5. 引き戻す：各点を目標位置へ、割合 $\alpha$（0〜1）だけ近づけるよう速度を加えます。$\alpha = 1$ で完全な剛体、小さいほど柔らかくなります。

点同士が直接つながっていないので、どれだけつぶれても目標の形は常に正しい元の形で、裏返ったまま戻らない、ということが起こりません。

線形モードでは、回転の代わりに $\mathbf{A} = \mathbf{A}_{pq}\mathbf{A}_{qq}^{-1}$（体積が変わらないよう正規化したもの）を回転と混ぜて使い、伸び縮みやせん断も少し許します。ぐにゃっとした大きな変形になります。

実装のポイント

• 極分解は反復法が安定：特異値分解（SVD）でも求まりますが、ゲームでは前のフレームの回転から始める反復法（Müller 2016）が速く、つぶれて平らになっても破綻しません。
• 大きな物は領域に分ける：1 つの形全体で重ねると、長い物（しっぽ、ロープ）はほとんど曲がりません。重なり合う小さな領域ごとにシェイプマッチングを行い、結果を平均すると、局所的に曲がる柔らかさが出ます。
• $\mathbf{A}_{qq}^{-1}$ は最初に一度だけ：線形モードで使う元の形の行列は、形が変わらない限り再計算不要です。

つまずきやすい点

• 元の形を 1 つしか覚えない：塑性変形（へこんだまま戻らない）を表すには、元の形そのものを少しずつ今の形に近づけます。
• $\alpha$ と時間刻み：$\alpha$ は 1 ステップで引き戻す割合なので、時間刻みやサブステップ数で柔らかさが変わります。フレームレートに依存させたくない場合は、刻みに応じて換算します。
• 点が 1 平面や 1 直線に並ぶ：点が平らに並んだ形では、$\mathbf{A}_{qq}$ が逆行列を持たず、線形モードが使えません。回転モードだけを使います。

デモで試すこと

1. 「落とす」を押すと、球・ドーナツ・結び目の形の塊が階段に落ち、つぶれて弾み、元の形に戻ります。点同士はまったくつながっていません。
2. 「形に戻る強さ α」を 1 に近づけると剛体のようにカチッとし、0.05 くらいまで下げると、大きくつぶれてゆっくり戻る柔らかいゼリーになります。
3. 「目標の形を表示」をオンにすると、各点から目標の形への引き戻しが青緑の線で見えます。
4. 「伸び縮みも許す（線形）」に切り替えると、回転だけでなく伸び縮みも目標の形に含まれるので、より大きく、ぐにゃっと変形します。
5. 地面をクリックすると、近くの塊を下からつつけます。