1 (a) (b) Fig. 1 (a) An example of an animation where a conventional elastic cuboid bounces off the floor. (b) An example of user-specified input data

Size: px

Start display at page:

Download "1 (a) (b) Fig. 1 (a) An example of an animation where a conventional elastic cuboid bounces off the floor. (b) An example of user-specified input data"

こうざぶろうしもとり
7 years ago
Views:

1 1,a) 1, 1,b) 1, 2,c) 1,d) , Martin Martin Shape Matching Martin Shape Matching Real-Time Example-Based Elastic Deformation Yuki Koyama 1,a) Kenshi Takayama 1, 1,b) Nobuyuki Umetani 1, 2,c) Takeo Igarashi 1,d) Received: April 6, 2013, Accepted: June 14, 2013 Abstract: We present an example-based elastic deformation method that runs in real time. Example-based elastic 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-based elastic deformations. Keywords: elastic simulation, shape matching dynamics, artist control 1. 1 The University of Tokyo, Bunkyo, Tokyo , Japan 1 ETH Zürich Presently with ETH Zürich 2 Autodesk Research Presently with Autodesk Research a) koyama@is.s.u-tokyo.ac.jp b) kenshi84@gmail.com c) n.umetani@gmail.com d) takeo@acm.org [16] [17] [1] [6] Martin [7] Visual Computing/ CAD CAD c 2013 Information Processing Society of Japan 2316

the input data. 1 [6] Martin Martin Shape Matching [9] Martin Shape Matching Martin Martin 2.

2 1 (a) (b) Fig. 1 (a) An example of an animation where a conventional elastic cuboid bounces off the floor. (b) An example of user-specified input data for example-based elastic materials and a result animation of the example-based elastic cuboid generated from the input data. 1 [6] Martin Martin Shape Matching [9] Martin Shape Matching Martin Martin Shape Matching Shape Matching Müller [9] Müller FastLSM [10] Steinemann [14] Chain Shape Matching [11], [12] Shape Matching Oriented Particles [8] [3], [18] [15] Shape Matching ProcDef [5] [4] Shape Matching c 2013 Information Processing Society of Japan 2317

2.2 Martin [7] Martin Martin Schumacher [13] Schumacher 6.2 3. 2 (1) E 4.2 4.3 (2) 4.1 2 1 2 4.2 Martin Martin E E 2 2 Fig. 2 Overview of run-time operations.

4.1 Shape Matching Müller [9] Shape Matching Shape Matching [5], [10] Shape Matching N Shape Matching 1 i 1 N i N i i 1-ring neighborhood [5] [10] i x 0 i, x i,m i r ( )( ) 1 A r = m i p i q T

3 2.2 Martin [7] Martin Martin Schumacher [13] Schumacher (1) E (2) Martin Martin E E 2 2 Fig. 2 Overview of run-time operations. Here, the elastic cuboid model has its rest pose, current deformed pose, and two example poses Shape Matching Müller [9] Shape Matching Shape Matching [5], [10] Shape Matching N Shape Matching 1 i 1 N i N i i 1-ring neighborhood [5] [10] i x 0 i, x i,m i r ( )( ) 1 A r = m i p i q T i m i q i q T i R 3 3 (1) i r i r m i [10] c 0 r = i r mixi i r mix0 i i r mi, c r = i r mi r p i = x i c r, q i = x 0 i c0 r A r S r = A T r A r R 3 3 R r = A r S 1 r i r g r,i Shape Matching g r,i = R r ( x 0 i c 0 r) + cr (2) g r,i = R r Sr ( x 0 i c 0 r) + cr (3) c 2013 Information Processing Society of Japan 2318

3) in our method, while the standard shape matching uses the undeformed rest shape as the goal shape. 3 S r R 3 3 4.2 E 4.

4 3 i r g r,i Shape Matching 4.3 S r Fig. 3 Our method for calclating the goal positions. In order to obtain the goal position g r,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 the goal shape. 3 S r R E 4.3 Shape Matching i g i i g i = g r,i r i i x i v i v i (t + h) =v i (t)+α g i(t) x i (t) + h f ext(t) (4) h m i x i (t + h) =x i (t)+hv i (t + h) (5) h 1 α [0, 1] f ext Martin Martin M M x R 3M i E i E(x) =(E T 1, ET 2,...,ET M )T R 6M x x E(x) F R 6M 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 and the projection are nonlinearly defined. In contrast, in our approach, example manifold E can be defined as a simple linear interpolation, thus the projection can be handled easily. w 1 E(x 1 )+w 2 E(x 2 ) F { N k=0 w ke(x k )} x 0 x k k F E E x Martin Shape Matching 3 A.1 (1) A r r S r S(x) =(S T 1, ST 2,...,ST M )T R 6M 3 3 S r 6 Shape Matching Martin c 2013 Information Processing Society of Japan 2319

{ N k=0 w ks(x k )} E E 4.3 S r S r 4 4.3 k S 0 = S(x 0 ), S k = S(x k ) E S = S(x) S E S = N k=0 w ks k N ( w k S k S 0) ( 2 S S 0) (6) k=1 w 1,w 2,...,w N w =(w 1,w 2,.

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

5 { N k=0 w ks(x k )} E E 4.3 S r S r k S 0 = S(x 0 ), S k = S(x k ) E S = S(x) S E S = N k=0 w ks k N ( w k S k S 0) ( 2 S S 0) (6) k=1 w 1,w 2,...,w N w =(w 1,w 2,...,w N ) T R N, L =(S 1 S 0, S 2 S 0,...,S N S 0 ) R 6M N 5 β Fig. 5 Varying the magnitude of the example-based elastic deformation effect by changing β. 6 2 Fig. 6 A teddy bear whose local regions are divided into two separate groups at its middle. w = ( L T L ) 1 L T (S S 0 ) (7) (L T L) 1 L T w 0 =1 N k=1 w k 0 N E 3 β w 0 = w 0 +(1 β) N k=1 w k,w k = βw k(k =1, 2,,N) β 1 β =0.995 β 5 1 β 7 1 Fig. 7 Comparison between the case of using globally defined example manifold (left) and the case where each local region has its own example manifold independently (right). 4.4 Martin c 2013 Information Processing Society of Japan 2320

情報処理学会論文誌 Vol.54 No.10 2316 2324 (Oct. 2013) 図 10 壁に激突する車のアニメーションの様子 1 つは例示形状を与えた場合残りの 3 つはそれぞれ異なる例示形状を与えた図 8 2 種類の例示べース弾性体直方体に対してねじれた形状と S 場合である字形の例示形状をそれぞれ与えたものを用いて生成した坂道 Fig.

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.

6 情報処理学会論文誌 Vol.54 No (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 of example-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 直方体直方体局所化円筒 2, テディ 1, 車図 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. 結果図 8 図 9 図 10 に本提案手法を用いて生成した例 6. 考察 6.1 Martin らの手法との結果の比較図 12 にねじれた形状を例示として与えた直方体を重示ベース弾性体のアニメーションの例を示すこれらは力下においた場合に関する Martin らの手法と我々の手法いずれも実時間で計算している表 1 はそれぞれのシミュの結果の簡単な比較を示すただしここではシミュレーレーションの 1 タイムステップあたりの計算時間単位はションやレンダリングの条件は厳密には同じでなくまた ms を表しており tsm は従来の Shape Matching 法の計有限要素法と Shape Matching 法ではシミュレーションの算にかかった時間 tproj は例示集合への投影にかかった時枠組みが異なるために例示ベース弾性変形の効果だけを厳間 ttot はタイムステップ全体の計算にかかった時間を表密に比較することが本質的に困難であるという点に注意さしているなおここではレンダリングに要した時間は含れたいしかしながらこの比較画像からも観察できるよんでいない計測は Intel Core i7 M GHz CPU をうに我々の手法は Martin らの手法と実質的に同様な効搭載したデスクトップ PC で行ったこの表から分かると果を生み出せていると我々は考えているまた計算コスおり従来の Shape Matching 法に比べ本提案手法を用トに関しても厳密な比較が難しいものの Martin らの手法 c 2013 Information Processing Society of Japan 2321

7 12 Martin [7] c 2011 Association for Computing Machinery, Inc. Reprinted by permission. Fig. 12 Comparison between Martin et al. s result and ours. The left image is from Ref. [7], c 2011 Association for Computing Machinery, Inc. Reprinted by permission Schumacher Schumacher [13] Schumacher E Schumacher Shape Matching Schumacher Martin Martin Schumacher 6.3 Martin Shape Matching Shape Matching 6.4 Martin Schumacher Martin Schumacher Shape Matching 7. Shape Matching 3 Shape Matching Chain Shape Matching [11], [12] Oriented Particles [8] 2 1 Schumacher [13] Explicit Weight Control Princeton Shape Benchmark c 2013 Information Processing Society of Japan 2322

8 [1] Bergou, M., Mathur, S., Wardetzky, M. and Grinspun, E.: TRACKS: Toward directable thin shells, ACM Trans. Graph., Vol.26 (2007). [2] Bonet, J. and Wood, R.D.: Nonlinear Continuum Mechanics for Finite Element Analysis, Cambridge University Press, 2 edition (2008). [3] Diziol, R., Bender, J. and Bayer, D.: Robust realtime deformation of incompressible surface meshes, Proc ACM SIGGRAPH/Eurographics Symposium on Computer Animation, pp , ACM (2011). [4] Ijiri, T., Ashihara, T., Umetani, N., Igarashi, T., Haraguchi, R., Yokota, H. and Nakazawa, K.: A Kinematic Approach for Efficient and Robust Simulation of the Cardiac Beating Motion, PLoS ONE, Vol.7, No.5, p.e36706 (2012). [5] 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 (2009). [6] Kondo, R., Kanai, T. and Anjyo, K.-I.: Directable animation of elastic objects, Proc ACM SIG- GRAPH/Eurographics Symposium on Computer Animation, pp , ACM (2005). [7] Martin, S., Thomaszewski, B., Grinspun, E. and Gross, M.: Example-based elastic materials, ACM Trans. Graph., Vol.30, pp.72:1 72:8 (2011). [8] Müller, M. and Chentanez, N.: Solid simulation with oriented particles, ACM Trans. Graph., Vol.30, pp.92:1 92:10 (2011). [9] Müller, M., Heidelberger, B., Teschner, M. and Gross, M.: Meshless deformations based on shape matching, ACM Trans. Graph., Vol.24, pp (2005). [10] Rivers, A.R. and James, D.L.: FastLSM: Fast lattice shape matching for robust real-time deformation, ACM Trans. Graph., Vol.26 (2007). [11] Rungjiratananon, W., Kanamori, Y. and Nishita, T.: Chain Shape Matching for Simulating Complex Hairstyles, Computer Graphics Forum, Vol.29, No.8, pp (2010). [12] Rungjiratananon, W., Kanamori, Y., Metaaphanon, N., Bando, Y., Chen, B.-Y. and Nishita, T.: Twisting, tearing and flicking effects in string animations, Proc. 4th International Conference on Motion in Games, pp , Springer-Verlag (2011). [13] Schumacher, C., Thomaszewski, B., Coros, S., Martin, S., Sumner, R. and Gross, M.: Efficient simulation of example-based materials, Proc. ACM SIG- GRAPH/Eurographics Symposium on Computer Animation, pp.1 8, Eurographics Association (2012). [14] Steinemann, D., Otaduy, M.A. and Gross, M.: Fast adaptive shape matching deformations, Proc ACM SIGGRAPH/Eurographics Symposium on Computer Animation, pp.87 94, Eurographics Association (2008). [15] Takamatsu, K. and Kanai, T.: A fast and practical method for animating particle-based viscoelastic fluids, The International Journal of Virtual Reality, Vol.10, No.1, pp (2011). [16] Thürey, N., Keiser, R., Pauly, M. and Rüde, U.: Detail-preserving fluid control, Proc ACM SIG- GRAPH/Eurographics Symposium on Computer Animation, pp.7 12, Eurographics Association (2006). [17] Twigg, C.D. and James, D.L.: Backward steps in rigid body simulation, ACM Trans. Graph., Vol.27, pp.25:1 25:10 (2008). [18] Vol.40, No.4, pp (2011). A.1 (1) A r r F r 1 r O x =(x 1,x 2,x 3 ) T u(x) O u i (x) = n=0,..., k+l+m=n Z = x u(x) = a k,l,m i x k 1x l 2x m 3 (i =1, 2, 3) (A.1) [2] u(x) a 1,0,0 1 a 0,1,0 1 a 0,0,1 1 a 1,0,0 2 a 0,1,0 2 a 0,0,1 2 a 1,0,0 3 a 0,1,0 3 a 0,0,1 3 (A.2) Z F F = I + Z 1 6 x 1 =( ɛ, 0, 0) T, x 2 =(ɛ, 0, 0) T, x 3 =(0, ɛ, 0) T, x 4 =(0,ɛ,0) T, (A.3) x 5 =(0, 0, ɛ) T, x 6 =(0, 0,ɛ) T (1) p i, q i c p i = x i + u(x i ) c, q i = x i (A.4) A (1) ( 6 )( 6 ) 1 A = p i q T i q i q T i (A.5) ( 6 )( 6 T T = I + u(x i )x i x i x i ( 6 cx i T ) 1 )( 6 ) 1 T x i x i (A.6) = I + B C (A.7) (A.1) (A.3) B c 2013 Information Processing Society of Japan 2323

9 B ij = a 1,0,0 i a 0,1,0 i a 0,0,1 i 6 cx T i = c + k=1 a2k+1,0,0 i ɛ 2k (j =1) + k=1 a0,2k+1,0 i ɛ 2k (j =2) + k=1 a0,0,2k+1 i ɛ 2k (j =3) 6 x T i = c0 T = 0 (A.8) (A.9) Autodesk Research C = 0 ɛ 0 B C Z A F A F 3 1 CG 2 1 CAD JST ERATO SIGGRAPH ETH Zurich c 2013 Information Processing Society of Japan 2324

IPSJ SIG Technical Report Vol.2012-CG-148 No /8/29 3DCG 1,a) On rigid body animation taking into account the 3D computer graphics came

IPSJ SIG Technical Report Vol.2012-CG-148 No /8/29 3DCG 1,a) On rigid body animation taking into account the 3D computer graphics came 3DCG 1,a) 2 2 2 2 3 On rigid body animation taking into account the 3D computer graphics camera viewpoint Abstract: In using computer graphics for making games or motion pictures, physics simulation is