情報処理学会論文誌

Vol.54 No.10 2316–2324 (Oct. 2013)

推薦論文

例示ベース弾性変形の実時間計算手法
小山 裕己1,a)

高山 健志1,†1,b)

梅谷 信行1,†2,c)

五十嵐 健夫1,d)

受付日 2013年4月6日, 採録日 2013年6月14日

概要：本論文では，実時間で計算可能な例示ベース弾性変形の手法を提案する．例示ベース弾性変形とはMartin らによって提案された手法であり，弾性体の変形形状を例示することによって直感的に変形の様子を制御することができるものである．しかしながら，Martin らの有限要素法に基づいたアプローチでは計算コストの高い非線形最適化計算を解く必要があり，ゲームなどの実時間アプリケーションでの使用は困難である．そこで我々は，高速かつ頑健で，実装が容易な手法として知られている Shape Matching 法に基づいて，非線形最適化計算を用いずに例示ベース弾性変形を実現する手法を開発した．我々の手法はMartin らの手法に比べ，同等の例示ベース弾性変形の効果を表現でき，かつ数百から数千倍程度高速に計算可能である．
キーワード：弾性体シミュレーション，Shape Matching 法，アーティスト制御

Real-Time Example-Based Elastic Deformation
Yuki Koyama1,a)Kenshi Takayama1,†1,b)

Nobuyuki Umetani1,†2,c)Takeo Igarashi1,d)Received: April 6, 2013, Accepted: June 14, 2013

Abstract: We present an example-based elastic deformation method that runs in real time. Example-basedelastic deformation was originally presented by Martin et al., where an artist can intuitively control elastic material behaviors by simply giving example deformed poses. Their FEM-based approach is, however,computationally expensive requiring nonlinear optimization, which hinders its use in real-time applications
such as games. Our contribution is to formulate an analogous concept using the shape matching framework,
which is fast, robust, and easy to implement, without using nonlinear optimization. Our approach is two or
three orders of magnitude faster than Martin et al.’s approach while producing comparable example-basedelastic deformations.
Keywords: elastic simulation, shape matching dynamics, artist control

1. はじめに
リアリスティックなコンピュータアニメーションを製作するには物理シミュレーションを用いることが効果的である．そこで，アーティストの演出意図に沿ってシミュレー

ション結果を制御できることが重要となる．そのようなアーティスト制御を目的とした物理シミュレーション手法
としては，流体 [16]，剛体 [17]，布 [1]，弾性体 [6] などを対象とした様々な手法が提案されてきた．
そのような中，Martin ら [7] は例示ベース弾性体という概念を提案した．これは弾性体の変形アニメーションの製

1
†1
†2
a)
b)
c)
d)

東京大学
The University of Tokyo, Bunkyo, Tokyo 113–0033, Japan
現在，ETH Zürich
Presently with ETH Zürich
現在，Autodesk ResearchPresently with Autodesk Research
koyama@is.s.u-tokyo.ac.jp
kenshi84@gmail.com
n.umetani@gmail.com
takeo@acm.org

c 2013 Information Processing Society of Japan作を支援するもので，弾性体の変形形状の例（例示形状）
をアーティストが指定することで，その形状に変形しやす
い弾性体を実現できるというものである．例示ベース弾性
本論文の内容は 2012 年 6 月の Visual Computing/グラフィク
スと CAD 合同シンポジウムで報告され，グラフィクスと CAD研究会主査により情報処理学会論文誌ジャーナルへの掲載が推薦された論文である．

2316

情報処理学会論文誌

Vol.54 No.10 2316–2324 (Oct. 2013)

体の表現に基づいており，保存力を計算する代わりに弾性体の目標の形状そのものを動的に変化させながらシミュ
レーションを行うことによって，非線形最適化を用いずに例示による効果を実現している．本提案手法は Martin らの手法と似たような変形を再現しつつ，数百から数千倍程
度高速に計算でき，特に実時間アプリケーションでも使用することができる．

Shape Matching 法は Martin らの用いた有限要素法に比べると物理的な正確さの保証という点では劣るが，見た目には十分自然な挙動を表現できており，また特にアーティストの演出意図が重視される文脈においては見た目以上の物理的な正確さはあまり重要でないと考えられるため，
図 1 (a) 通常の弾性体オブジェクト（ここでは四角柱）の床との衝本提案手法は十分実用性があるものと考えられる．また突のアニメーションの例．(b) 例示ベース弾性体のためのユー

Martin らと同様に，本提案手法においても例示の効果を局

ザによる入力形状と，それによって生成された例示ベース弾性
体オブジェクトの床との衝突のアニメーションの例

Fig. 1 (a) An example of an animation where a conventionalelastic cuboid bounces oﬀ the ﬂoor. (b) An example
of user-speciﬁed input data for example-based elastic
materials and a result animation of the example-basedelastic cuboid generated from the input data.

所化させる拡張を行うことが可能である．

2. 関連研究2.1 Shape Matching 法
Shape Matching 法は Müller ら [9] によって提案された
幾何学的方法に基づく柔軟物体の表現手法である．過重を取り除くと基本形状に戻るという弾性体の性質をよくモデ体の例を図 1 に示す．この例は四角柱の形状を持つ弾性

ル化できている手法であり，有限要素法などに基づく他の体に対し，ねじれた形状を例示形状として与えた場合の挙弾性体シミュレーション手法に比べて高速で頑健である

動を示したものであり，このようにねじれやすい性質を持といった特徴があるため，特にインタラクティブな用途でつ四角柱を簡単に表現できる．例示ベース弾性体を用いるの活躍が期待されている弾性体シミュレーション手法でことで，このようなアニメーションを製作する際に非直感ある．この手法は Müller らによって初めて提案されて以的な物理パラメタの調整をする必要がなく，変形の性質を

来，様々な拡張が提案されてきた．FastLSM [10] は格子状

直接，直感的にデザインできるという利点がある．また，にパーティクルを配置した構造に対して効率的に計算を行

キーフレームを用いたアプローチ [6] に比べ，アニメーショ

う手法である．Steinemann ら [14] はこれに対し八分木のンのシナリオが固定である必要がないという点も，例示

データ構造を導入することで，さらに効率的に計算する手

ベース弾性体の特徴である．すなわち，どのようなシーン

法を提案した．Chain Shape Matching 法 [11], [12] は鎖状でどのような時系列で外力を受けて変形するかなどといっに並んだパーティクル群に対して Shape Matching 法を適た情報は，弾性体の変形の性質をデザインする段階では必用する手法で，髪の毛や紐状の弾性体を表現することがで要ない．これにより，様々なシナリオで同じ弾性体を使いきる手法である．Oriented Particles [8] は各パーティクル

回すことができたり，シナリオを事前に決定できないインに対して位置だけでなく向きの情報も持たせることによっタラクティブなアプリケーションでも使用することができて，非常に少ないパーティクルでも安定したシミュレー

たりするといった利点が期待される．

ションを行えるようにした拡張であり，鎖状や平面状に配しかしながら，Martin らの手法は計算コストが高く，例置されたパーティクル群に対しても適用することができる

示ベース弾性変形を実時間で計算することができないとい手法となっている．また，体積保存を考慮して変形させる

う問題点がある．Martin らの手法は有限要素法による弾拡張 [3], [18] や，粘弾性体を表現するための拡張 [15] も存性体の表現を用いており，例示の効果を実現するための特在する．このように，Shape Matching 法は様々な拡張が別な保存力を計算する．その際に非線形最適化が必要とな提案されているが，我々の知る限り，例示ベース弾性変形

り，これが計算のボトルネックとなっている．これによっを実現するものは本提案手法が最初である．

て，インタラクティブなアプリケーションでの使用が制限されている．

また ProcDef [5] や実時間心臓拍動シミュレータ [4] はShape Matching 法を拡張することで柔軟物体の能動的な

このような制限を克服するため，本論文では特に実時間動作を生成する手法であり，これらの手法では各局所領域でも計算できる高速な例示ベース弾性変形の計算手法を提の目標の形状を能動的に変えていくことで全体の動きを表案する．本提案手法は Shape Matching 法 [9] による弾性現している．本提案手法でも各局所領域の目標の形状を変c 2013 Information Processing Society of Japan


2317

情報処理学会論文誌

Vol.54 No.10 2316–2324 (Oct. 2013)

えるというアプローチをとっているが，目標の形状がそのときの変形の状態に応じて受動的に変わっていくという点

4. 提案手法の詳細で大きく異なっている．

4.1 Shape Matching 法の拡張

2.2 例示ベース弾性体法による弾性体の表現を拡張することで例示ベースの弾本提案手法は，Müller ら [9] の提案した Shape Matching
例示ベース弾性体はアーティストフレンドリな弾性体シ性体を表現する．特に，本提案手法では互いにオーバラッ

ミュレーション手法として Martin ら [7] が提案したものでプした局所領域を持つ構造の Shape Matching 法（これあるが，先に述べたとおり，Martin らの手法は計算コスト

は [5], [10] などでも使用されている．）を扱う．この方法が非常に高いという問題点がある．我々の手法は，Martin

は，局所領域ごとに Shape Matching 法を適用し，それららの手法と同様の効果を実時間で計算するというものであの影響を合併して全体の変形を実現する方法である．

る．また，Schumacher ら [13] も例示ベース弾性体を高速本提案手法におけるユーザの入力は，モデルの基本形状に計算するための手法を提案しているが，実時間で計算す（初期形状）を表す四面体メッシュと，N 種類の例示形状

るには至っていない．Schumacher らの手法と我々の手法である．例示形状とは基本形状を変形させたもので，基本との間の共通点や相違点については 6.2 節で説明する．

形状の四面体メッシュと同じ構造を保ったまま，頂点の位置を自由に移動させたものである．また，四面体メッシュ

3. 実行時の計算の概要

に対してレンダリング用の三角形メッシュを埋め込むこと

本提案手法の詳細を記述する前に，まず本提案手法の実も可能であり，本研究では結果アニメーションの生成の際行時の計算の概要を示す．本提案手法では，次の 2 つの操にシミュレーション用に粗い四面体メッシュ，レンダリン

作を各タイムステップで行うことで，例示ベース弾性変形

グ用に詳細な三角形メッシュを用いることで，計算コストを実現する．

を抑えつつ見た目の質を上げる工夫を行った．

( 1 ) 現在の形状を例示集合 E（4.2 節）に投影（4.3 節）する．

四面体メッシュの頂点はそれぞれ Shape Matching 法( 2 ) 投影先の点を目標の形状とし，現在の形状を目標の形

における 1 つのパーティクルとして扱われ，パーティク
ル i に対して 1 つの局所領域 Ni が定義される．局所領域

状に向かって引っ張る（4.1 節）．
以上の操作を模式的に表したのが図 2 である．この例でNi の要素は，パーティクル i とその一近傍頂点（1-ring

は，直方体の 1 つの基本形状に対し，2 つの例示形状を与

neighborhood [5]）とする．なお，本研究では四面体メッ

えた場合を表しており，それぞれの形状は高次元ベクトル

シュを基にした局所領域の定義を採用したが，文献 [10] のとして記述（4.2 節）されている．Martin らの手法との最ように格子状の構造によって局所領域を定義する場合にも大きな違いは，Martin らの手法ではこれらの高次元ベク

も，本提案手法はそのまま適用可能である．

トルの非線形な補間として例示集合 E を定義していたのにパーティクル i に対応する初期位置，現在位置，質量を対し，我々の手法では単純な線形補間によって例示集合 Eそれぞれ x0i , xi , mi とする．各タイムステップについて，を表現している点である．これによって，我々の手法では

まず局所領域 r における初期形状からその時点における形投影の操作を行う際に非線形最適化を用いることなく，効状への変換を近似した線形変換行列

率的に計算を行うことができる．

Ar =




m̃i pi qTi




i∈r

m̃i qi qTi

−1∈ R3×3i∈rを計算する．ここで，m̃i は有効質量 [10]，c0r =

(1)


0
i∈r m̃i xi

,
m̃
i
i∈r


i∈r m̃i xi

はそれぞれ初期状態とその時点での局所領i∈r m̃i域 r における重心，pi = xi − cr , qi = x0i − c0r は重心から

cr =の相対位置を表している．続いて線形変換行列 Ar をその歪み成分である Sr =

ATr Ar ∈ R3×3 と回転成分である

Rr = Ar S−1
r に分解する．次に，このタイムステップにおけるパーティクル i の局所領域 r に関する目標位置 gr,i を
図 2計算するのだが，従来の Shape Matching 法では初期形状
実行時の計算の概要．ここでは直方体の基本形状に対して 2
つの例示形状を与えた場合を表しており，現在の形状はその時点における変形形状を表している

Fig. 2 Overview of run-time operations.

Here, the elastic

cuboid model has its rest pose, current deformed pose,and two example poses.

c 2013 Information Processing Society of Japan

の形状保存変換，すなわち

gr,i = Rr x0i − c0r + cr

(2)

によって計算していたのに対し，本提案手法では


gr,i = Rr S̃r x0i − c0r + cr

(3)

2318

情報処理学会論文誌

Vol.54 No.10 2316–2324 (Oct. 2013)

図 3 本提案手法における目標位置の計算方法．パーティクル i の局所領域 r における目標位置 gr,i を計算するために，従来のShape Matching 法では基本形状を変形させずに目標形状としていたのに対し，本提案手法では投影（4.3 節）によって得られる S̃r を用いて適切に基本形状を変形させたものを目標形状として用いている

Fig. 3 Our method for calclating the goal positions. In order to obtain the goal position gr,i of particle i in local
region r, the rest shape of the region is appropriately
deformed by the strain S̃r that is obtained by projection (Section 4.3) in our method, while the standard
shape matching uses the undeformed rest shape as thegoal shape.

図 4 Martin らの手法と我々の手法の比較．Martin らの手法では例示集合 E と投影が非線形だったのに対し，我々の手法では，例示集合 E は単純な線形補間によって定義されており，したがって投影を簡単に扱うことができる

Fig. 4 Comparison between Martin et al.’s and our approach.
In Martin et al.’s approach, example manifold E andthe projection are nonlinearly deﬁned. In contrast, in
our approach, example manifold E can be deﬁned as asimple linear interpolation, thus the projection can be

によって計算する（図 3）．ここで，S̃r ∈ R

3×3

は目標の形

handled easily.

状を歪ませる要素であり，4.2 節で説明する例示集合 E に対して，4.3 節で説明する投影という操作を行うことで得線形結合 w1 E(x1 ) + w2 E(x2 ) は一般には F の要素ではなることができる．

く，これに対応する有効な変形形状は存在しない．そこで最後に従来の Shape Matching 法と同様，パーティクルi の目標位置 gi を，パーティクル i が属するすべての局所
領域での目標位置の平均 gi = gr,i ri とし，これを用いてパーティクル i の位置 xi と速度 vi を

彼らは，{

N

k=0 wk E(xk)}（ただし x0 は初期形状，xk は

k 番目の例示形状を表す）によって得られる凸包を実現可能集合 F に投影して得られる集合 E を例示集合と定義した．このように定義された例示集合 E に対し，各タイムス

fext (t)gi (t) − xi (t)+hvi (t + h) = vi (t) + αhmixi (t + h) = xi (t) + hvi (t + h)

(4)
(5)

テップにおける変形形状を非線形最適化によって投影する
ことで，特別な保存力の計算に必要な目標となる変形形状x̃ を得る．また，この非線形最適化が計算のボトルネックのように更新する．ここで h は 1 タイムステップあたりのとなっている（図 4，左）．

時間幅，α ∈ [0, 1] は硬さに関するパラメタ，fext は外力を4.2.2 我々の手法
Martin らが特別な保存力を計算することによって例示表す．

の効果を実現していたのに対し，本提案手法では Shape4.2 変形記述子と例示集合

Matching 法における各局所領域の目標の形状を適切に歪ま4.2.1 Martin らの手法

せる（図 3）ことによって例示の効果を実現する．まず変形

Martin らの手法は，例示の効果を実現するために好ま

記述子の定義についてであるが，付録 A.1 で詳しく説明する

しい変形形状の集合（例示集合）のうち，その時点におけように，式 (1) で計算される線形変換行列 Ar は局所領域 rる変形形状に最も近い変形形状を探し，その変形形状に近における変形勾配テンソルの近似と考えることができ，したづくように特別な保存力を計算するというものである．そがってその歪み成分である対称行列 Sr は右ストレッチテン

こで彼らはまず，グリーンの歪みテンソルを用いて変形記ソルの近似と考えることができる．そこで本提案手法では，



述子を定義した．具体的には，四面体の数が M ，頂点のグリーンの歪みテンソルの代わりに右ストレッチテンソル

数が M の四面体メッシュの変形時の頂点の位置 x ∈ Rを用いて，変形記述子を S(x) = (ST1 , ST2 , . . . , STM )T ∈ R6M

に対し，四面体 i のグリーンの歪みテンソルを Ei として，と定義する．なお，ここでは 3 × 3 の対称行列である SrE(x) = (ET1 , ET2 , . . . , ETM  )T ∈ R6M を変形 x に対する変を 6 次元のベクトルとして表現している．ここで，Shape

形記述子と定義した．なお，グリーンの歪みテンソルはMatching 法では局所領域ごとに独立にパーティクルの目

3 × 3 の対称行列として得られるものであるが，その自由標位置を計算するため，記述子に対応する変形形状が実際

度は 6 であるので，ここでは 6 次元のベクトルとして表に存在しない場合でも有効な変形を実現できるという点

6M 

現している．ここで，写像 x → E(x) の値域 F ⊂ Rが，有限要素法を用いた Martin らの手法と大きく異なっ（実現可能集合と呼ぶ）は非線形な集合である．すなわち，ている．これにより，本提案手法では記述子の単純な線形

3M

c 2013 Information Processing Society of Japan


2319

Vol.54 No.10 2316–2324 (Oct. 2013)

情報処理学会論文誌

結合 {

N

k=0 wk S(xk)} によって得られる凸包を例示集合 Eと定義することができる．このように定義した例示集合 Eに対して，その時点における変形形状を線形投影（詳しくは 4.3 節で説明する）することによって，目標となる変形
記述子 S̃，さらに局所領域 r における目標となる形状を変形させる成分 S̃r を得ることができる（図 4，右）．
図 5 β の値にともなって変化する例示ベース弾性変形の効果

Fig. 5 Varying the magnitude of the example-based elastic de-

4.3 例示集合への投影

formation eﬀect by changing β.

基本形状と k 番目の例示形状を表した変形記述子をそれぞれ S0 = S(x0 ), Sk = S(xk ) と表すと，例示集合 E に対してその時点における変形形状 S = S(x) を投影するとは，

S に最も近い例示集合 E の要素 S̃ =N

k=0 wk S

kを得るということである．そこでまず
N



 

w k Sk − S0 − S − S0

2

(6)

k=1

を最小にする重み w1 , w2 , . . . , wN を計算する．具体的には，w = (w1 , w2 , . . . , wN )T ∈ RN , L = (S1 − S0 , S2 −S0 , . . . , SN − S0 ) ∈ R6M ×N として
−1 T
w = LT L
L (S − S0 )図 6

2 つの独立したグループに分けられたテディ

Fig. 6 A teddy bear whose local regions are divided into two
separate groups at its middle.

(7)を計算すればよい．ここで，各タイムステップにおいて(LT L)−1 LT は不変であるので，シミュレーションの前に
N
一度だけ計算すれば良い．続いて，w0 = 1 − k=1 wk を計算する．
このような操作だけでは負の重みも許してしまっている
ため，例示された変形形状の外挿を計算してしまう可能性がある．これは，アーティストが変形の様子をデザインするという目的を考えると望ましくないことである．そこで

図7

全体で 1 つの例示集合を形成した場合（左）と，各局所領域でそれぞれ独立な例示集合を形成した場合（右）比較Fig. 7 Comparison between the case of using globally deﬁned
example manifold (left) and the case where each lo-

負の重みを除去するために「最も小さい負の重みを選び，

cal region has its own example manifold independently

それを 0 にし，そのときの絶対値を N で割った値を残り(right).

のすべての重みから引く」という操作を，負の重みがなくなるまで繰り返し行う．

4.4 例示による効果の局所化に関する拡張

別の問題としては，弾性体が例示集合 E のある要素

Martin らの手法と同様，本提案手法においても例示にが表す変形形状になったまま静止し，基本形状に戻らよる効果を局所化させる拡張を行うことが可能である．そない可能性があるという問題が考えられる．これは，本のためには，局所領域全体を複数の独立したグループに分提案手法では各局所領域の目標の形状そのものを変形け，それぞれのグループで例示集合を考え，投影を行えばさせる（図 3）ため，その時点での変形形状と目標の形

良い．図 6 は弾性体を縦に 2 つのグループに分けた例で状が完全に一致してしまうことがあり得るためである．

あり，図中の丸はユーザによる制御点を表している（こここのような問題を避けるため，上記のような方法で求では重力はなく，弾性体は腹部に当たる部分で空間に固定めた重みに対し，新たに導入するパラメタ β を用いてされている）．

w0 = w0 + (1 − β)N
k=1 wk , wk = βwk (k = 1, 2, · · · , N )また，各局所領域をそれぞれ独立なグループとする（こによって得られる重みを用いる．ここで β は 1 よりもわずのとき，それぞれのグループにおける例示集合は 6 次元空かに小さい（β = 0.995 など）だけでも十分に効果があり，間上に定義される）ことによって，各局所領域における変β が小さくなるほど例示による効果は小さくなる．図 5 は形が局所的な振舞いによってのみ決まるという点で，物理

図 1 と同様の弾性体を重力下で床に静止させたときに，β的により自然な，異方性弾性体のような変形が表現できる．

の値に応じてどのように例示の効果が変わるかを示したも

図 7 は図 1 と同様の弾性体を重力下で床に落下させた際のである．

の変形を表しており，左は全体で 1 つのグループ，右は各

c 2013 Information Processing Society of Japan


2320

情報処理学会論文誌

Vol.54 No.10 2316–2324 (Oct. 2013)

図 10 壁に激突する車のアニメーションの様子．1 つは例示形状を与えた場合，残りの 3 つはそれぞれ異なる例示形状を与えた
図 8 2 種類の例示べース弾性体（直方体に対してねじれた形状と S場合である

字形の例示形状をそれぞれ与えたもの）を用いて生成した坂道

Fig. 10 Cars colliding against the wall. One (upper left) isのシーンにおけるアニメーションの様子．シーン全体で 2,250

simulated without any example pose, and the others

個のパーティクルを含んでおり，49 FPS で実行されている

are simulated with diﬀerent kinds of example poses.

Fig. 8 An animation of a slope scene containing two types ofexample-based elastic cuboids (generated from twistshaped and S-shaped example poses) represented by

表 1

1 タイムステップあたりの計算時間（単位は ms）

Table 1 Timings per time step in milliseconds.

2,250 particles in total; this scene is simulated at 49
frames per second.

モデル#パーティクル

tsm

tproj

ttot

直方体

225

0.21

0.091

0.33

直方体（局所化）

225

0.21

0.17

0.40
3.1

円筒

2,025

2.0

0.86

テディ

1,280

1.3

0.72

2.2

車

192

0.17

0.078

0.27

図 9 円柱型の四面体メッシュに円筒型の三角形メッシュを埋め込んだ例示ベース弾性体のアニメーションの様子

Fig. 9 Four cylinders undergoing very diﬀerent elastic deformations.

図 11 本論文でアニメーション生成のために用いた四面体メッシュ

Fig. 11 Tetrahedral meshes used in this paper for generating
the animations.

局所領域をそれぞれ独立なグループとした場合を表しておいた場合の計算時間の増加はわずかである．また，図 11

り，前者は全体で一様に例示の効果が表れているのに対し，に結果生成のために用いた四面体メッシュを示す．

後者は部位によって例示の効果の表れ方が異なっている．

5. 結果

6. 考察
6.1 Martin らの手法との結果の比較

図 8，図 9，図 10 に，本提案手法を用いて生成した例

図 12 に，ねじれた形状を例示として与えた直方体を重示ベース弾性体のアニメーションの例を示す．これらは，力下においた場合に関する，Martin らの手法と我々の手法いずれも実時間で計算している．表 1 はそれぞれのシミュの結果の簡単な比較を示す．ただし，ここではシミュレー

レーションの 1 タイムステップあたりの計算時間（単位はションやレンダリングの条件は厳密には同じでなく，またms）を表しており，tsm は従来の Shape Matching 法の計

有限要素法と Shape Matching 法ではシミュレーションの算にかかった時間，tproj は例示集合への投影にかかった時枠組みが異なるために例示ベース弾性変形の効果だけを厳間，ttot はタイムステップ全体の計算にかかった時間を表密に比較することが本質的に困難であるという点に注意さしている．なお，ここではレンダリングに要した時間は含れたい．しかしながら，この比較画像からも観察できるよんでいない．計測は Intel Core i7 M620 2.66 GHz CPU をうに，我々の手法は Martin らの手法と実質的に同様な効搭載したデスクトップ PC で行った．この表から分かると果を生み出せていると我々は考えている．また，計算コスおり，従来の Shape Matching 法に比べ，本提案手法を用トに関しても厳密な比較が難しいものの，Martin らの手法

c 2013 Information Processing Society of Japan


2321

情報処理学会論文誌

Vol.54 No.10 2316–2324 (Oct. 2013)

正確さの保証ができない．この点は本提案手法の欠点であるといえる．

6.4 入力形状について
本提案手法では，入力形状の補間の際に四面体要素間の衝突などを考慮していないため，例示形状によっては途中
図 12 Martin らの手法と我々の手法の結果の比較．左の画像は文の補間形状で自己干渉を起こしてしまう可能性がある．こc
Association for Computing
献 [7] のものである（2011のような問題は，Martin らの手法や Schumacher らの手法

Machinery, Inc. Reprinted by permission.）でも発生するものと考えられる．

Fig. 12 Comparison between Martin et al.’s result and ours.

また本提案手法では，Martin らの手法や Schumacher らcThe left image is from Ref. [7], 2011
Association forの手法と同様，基本形状と例示形状はすべて同じメッシュ

Computing Machinery, Inc. Reprinted by permission.

構造を持っている必要がある．このような制限はアーティストにとって大きな制約となってしまうと考えられるため，

では類似の条件で計算するのに 1 タイムステップあたり数

これを解決することは重要である．これには，メッシュ構秒程度かかるのに対し，我々の手法ではこれに比べ数百か造に依存しない変形記述子や例示集合を用いる必要がある

ら数千倍程度高速に計算できているといえる．

と考えられる．
入力形状の四面体メッシュについては，本提案手法にお6.2 Schumacher らの手法との共通点と相違点

いては各四面体要素の大きさが均一であることが望ましい

例示ベース弾性変形を高速に計算するための手法としと考えられる．その理由は，本提案手法では四面体要素のて，我々の手法の他に，Schumacher ら [13] の手法が知ら大きさに依存して局所領域の大きさが決定し，また互いにれている．Schumacher らの手法と我々の手法の共通点とオーバラップした局所領域を持つ構造の Shape Matching

しては，例示集合 E の定義として，入力形状の変形記述子

法では局所領域の大きさがその局所領域の硬さに影響するの単純な線形補間を用いているという点があげられる．こため，各四面体要素の大きさが不均一だとオブジェクトのれによって，投影によって得られる変形記述子は有効な形

硬さも部位によって不均一になってしまうからである．

状を表さなくなるが，我々の手法と同様，Schumacher らの手法でもそのような有効でない形状の変形記述子をそ7. まとめのまま用いて定式化することで，計算コストの削減を行っ

本論文では例示ベース弾性変形を実時間で計算することている．我々の手法との相違点としては，我々の手法ではができる高速な手法を提案した．既存手法が有限要素法にShape Matching 法と組み合わせて定式化したために非線基づいたもので，非線形最適化が必要であったのに対し，

形最適化計算を行う必要がなくなったが，Schumacher ら

本提案手法では Shape Matching 法による弾性体の表現をの手法は Martin らの手法と同様に有限要素法に基づいて拡張することで，非線形最適化を用いることなく例示ベーいるため，依然として非線形最適化計算を行う必要がある

ス弾性体を実現している．

点があげられる．Martin らの手法に比べ，Schumacher ら

本提案手法では 3 次元的な構造を持つ弾性体を扱ったの手法は非線形最適化計算の際の変数の数が少なく，計算が，Shape Matching 法の拡張である Chain Shape Match-

コストは小さくなっているものの，数十倍程度の高速化に

ing [11], [12] や Oriented Particles [8] などの手法と組み合とどまっており，実時間アプリケーションでの使用には不わせることで，布などの 2 次元的な構造や，髪の毛などの向きである．

1 次元的な構造に対しても本提案手法を応用していくこと
が将来研究として考えられる．また，Schumacher ら [13]6.3 物理的な正確さが Explicit Weight Control としてその応用例を提示してアーティストによる映像表現という文脈においては物理いるように，その時点における変形形状だけでなく，速度的な正確さの重要度は低いと考えられるものの，例示ベーや外力，周囲のオブジェクトとの相対位置など様々な情報

ス弾性変形による効果以外については，より物理的に正を考慮して例示集合に投影する仕組みを考えることで，興確であることが要求される状況も考えられる．Martin ら

味深い効果が得られることが期待できると考えている．

の手法が連続体力学に基づいた有限要素法を用いたアプ
ローチであるのに対し，本提案手法は幾何学に基づいた

謝辞 本研究で使わせていただいた車の形状データはPrinceton Shape Benchmark に含まれるものである．

Shape Matching 法を用いたアプローチであり，また ShapeMatching 法による弾性体表現の物理的な正確さの評価はまだ十分に研究されていないため，本提案手法は物理的なc 2013 Information Processing Society of Japan


2322

情報処理学会論文誌

Vol.54 No.10 2316–2324 (Oct. 2013)

参考文献
[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

Bergou, M., Mathur, S., Wardetzky, M. and Grinspun,
E.: TRACKS: Toward directable thin shells, ACM
Trans. Graph., Vol.26 (2007).
Bonet, J. and Wood, R.D.: Nonlinear Continuum Mechanics for Finite Element Analysis, Cambridge University Press, 2 edition (2008).
Diziol, R., Bender, J. and Bayer, D.: Robust realtime deformation of incompressible surface meshes, Proc.
2011 ACM SIGGRAPH/Eurographics Symposium on
Computer Animation, pp.237–246, ACM (2011).
Ijiri, T., Ashihara, T., Umetani, N., Igarashi, T.,
Haraguchi, R., Yokota, H. and Nakazawa, K.: A Kinematic Approach for Eﬃcient and Robust Simulation of
the Cardiac Beating Motion, PLoS ONE, Vol.7, No.5,
p.e36706 (2012).
Ijiri, T., Takayama, K., Yokota, H. and Igarashi,
T.: ProcDef: Local-to-global Deformation for Skeletonfree Character Animation, Computer Graphics Forum,Vol.28, No.7, pp.1821–1828 (2009).
Kondo, R., Kanai, T. and Anjyo, K.-I.: Directableanimation of elastic objects, Proc. 2005 ACM SIGGRAPH/Eurographics Symposium on Computer Animation, pp.127–134, ACM (2005).
Martin, S., Thomaszewski, B., Grinspun, E. and Gross,
M.: Example-based elastic materials, ACM Trans.
Graph., Vol.30, pp.72:1–72:8 (2011).
Müller, M. and Chentanez, N.: Solid simulation withoriented particles, ACM Trans. Graph., Vol.30, pp.92:1–
92:10 (2011).
Müller, M., Heidelberger, B., Teschner, M. and Gross,M.: Meshless deformations based on shape matching,
ACM Trans. Graph., Vol.24, pp.471–478 (2005).
Rivers, A.R. and James, D.L.: FastLSM: Fast lattice
shape matching for robust real-time deformation, ACM
Trans. Graph., Vol.26 (2007).
Rungjiratananon, W., Kanamori, Y. and Nishita,
T.: Chain Shape Matching for Simulating Complex
Hairstyles, Computer Graphics Forum, Vol.29, No.8,
pp.2438–2446 (2010).
Rungjiratananon, W., Kanamori, Y., Metaaphanon, N.,
Bando, Y., Chen, B.-Y. and Nishita, T.: Twisting, tearing and ﬂicking eﬀects in string animations, Proc. 4thInternational Conference on Motion in Games, pp.192–
203, Springer-Verlag (2011).
Schumacher, C., Thomaszewski, B., Coros, S., Martin,S., Sumner, R. and Gross, M.: Eﬃcient simulation of example-based materials, Proc. ACM SIGGRAPH/Eurographics Symposium on Computer Animation, pp.1–8, Eurographics Association (2012).
Steinemann, D., Otaduy, M.A. and Gross, M.: Fast
adaptive shape matching deformations, Proc. 2008 ACM
SIGGRAPH/Eurographics Symposium on Computer
Animation, pp.87–94, Eurographics Association (2008).
Takamatsu, K. and Kanai, T.: A fast and practicalmethod for animating particle-based viscoelastic ﬂuids,
The International Journal of Virtual Reality, Vol.10,
No.1, pp.29–35 (2011).
Thürey, N., Keiser, R., Pauly, M. and Rüde, U.:
Detail-preserving ﬂuid control, Proc. 2006 ACM SIGGRAPH/Eurographics Symposium on Computer Animation, pp.7–12, Eurographics Association (2006).
Twigg, C.D. and James, D.L.: Backward steps in rigid
body simulation, ACM Trans. Graph., Vol.27, pp.25:1–
25:10 (2008).

c 2013 Information Processing Society of Japan

[18]

高松賢二，金井 崇：シェイプマッチング法による体積保存を考慮した形状変形手法，画像電子学会誌，Vol.40,
No.4, pp.549–557 (2011).

付

録

A.1 変形勾配テンソルの近似としての線形変換行列
ここでは式 (1) によって計算される線形変換行列 Ar が局所領域 r の重心点における変形勾配テンソル Fr を近似していると考えることができることを示す．以下では 1 つの領域について考えるので，添字の r は適宜省略する．
後の計算を容易にするため，この領域の重心点の座標が原
点 O であるとすると，領域内の任意の点 x = (x1 , x2 , x3 )Tにおける変形時の変位 u(x)，すなわち変形による相対的な移動量は，原点 O におけるテイラー展開によって
n=0,...,∞ui (x) =ak,l,mxk1 xl2 xm
3i(i = 1, 2, 3)(A.1)

k+l+m=nと表すことができる．連続体力学 [2] では，変位 u(x) のヤ
コビ行列を，変位勾配テンソル⎛Z=

a11,0,0∂⎜u(x) = ⎝ a21,0,0∂x
a31,0,0

a10,1,0a10,0,1⎞

a20,1,0⎟
a20,0,1 ⎠a30,1,0a30,0,1(A.2)と定義している．この変位勾配テンソル Z を用いて，変形
勾配テンソル F は F = I + Z と計算される．
ここで，この領域が質量を 1 とする 6 つのパーティクル

x1 = (−, 0, 0)T ,x2 = (, 0, 0)T ,x3 = (0, −, 0)T ,x4 = (0, , 0)T ,T

T

x5 = (0, 0, −) ,x6 = (0, 0, )(A.3)

によって構成されているとする．このとき，式 (1) の pi , qi
は，c を領域の変位後の重心位置として

pi = xi + u(xi ) − c,qi = x i(A.4)と表され，この領域における線形変換行列 A は式 (1) より

A=

 6


pi qTi

 6


i=1

=I+

 6


i=1

u(xi )xi

i=1

−

 6


cxi

T

T

−1
qi qTi

 6


 6


i=1

=I+B−C

(A.5)

i=1

xi xi

T

−1
xi xi

T

−1
(A.6)

i=1

(A.7)

によって計算できる．式 (A.1) と式 (A.3) を代入して B を
具体的に計算すると，2323

情報処理学会論文誌

Vol.54 No.10 2316–2324 (Oct. 2013)⎧ 1,0,0 ∞ 2k+1,0,0⎪+ k=1 ai
2k
⎨ ai

∞
Bij =
ai0,1,0 + k=1 ai0,2k+1,0 2k⎪⎩ 0,0,1 ∞ 0,0,2k+1 2kai+ k=1 ai

梅谷 信行

(j = 1)(j = 2)(A.8)(j = 3)1983 年生．2012 年東京大学大学院情報理工学系研究科コンピュータ科学専
攻博士課程修了．現在，Autodesk Re-となる．またsearch にて，シミュレーションとユー
6


cxi T = c

i=1

6


xi T = c0T = 0

ザインタフェース研究開発に従事．

(A.9)

i=1

より，C = 0 となる．ここで  → 0 とすると B − C → Z

五十嵐 健夫 （正会員）となり，したがってこのとき A → F となることが分かる．

2000 年東京大学大学院工学系研究科博以上より，線形変換行列 A を変形勾配テンソル F の近似士（工学）．2002 年同大学院情報理工と考えることができることが確認できた．また，このこと

学系研究科講師，2005 年助教授，2011

は一般的なパーティクルの配置においても同様の手順で容年教授．2007〜2013 年 JST ERATO

易に示すことができる．

研究総括．学術振興会賞，SIGGRAPH
若手科学者賞等受賞．専門はユーザイ

推薦文

ンタフェースおよびグラフィクス．

本論文では 3 次元弾性体モデルの高速変形手法を提案している．もっともらしい変形の動きと制作者の演出意図を両立させる例示ベースの手法の 1 種であるが，非線形最適化計算を避けて線形補間をうまく使うことなどにより，従来手法に比べて数百倍の高速化を達成した．リアルタイム
で最終的な作品の品質での変形アニメーション実行が可能となったことにより，CG 映像制作プロセスに大きな変革を与えるだけでなく，その場で様々な変形を行うゲームなども実現できる．さらに，本論文のアイディアは，布のような 2 次元モデルや髪の毛のような 1 次元モデルにも適用できる可能性があり，将来の研究の拡がりも期待できる．
よって，論文誌での掲載価値を十分に有していると判断し，本研究会は本論文を推薦論文として推薦いたします．
（グラフィクスと CAD 研究会主査 柿本正憲）

小山 裕己 （学生会員）
1989 年生．2012 年東京大学理学部情報科学科卒業．同年同大大学院修士課
程進学．コンピュータグラフィクスの研究に従事．

高山 健志
1984 年生．2012 年東京大学大学院情報理工学系研究科コンピュータ科学専
攻博士課程修了．現在，ETH Zurichにて日本学術振興会海外特別研究員としてコンピュータグラフィクスの研究に従事．
c 2013 Information Processing Society of Japan

2324