Springhead:An open source physics simulator 物理シミュレーションの現状と未来 Physics simulation, state of the art and future ○長谷川晶一 東京工業大学精密工学研究所/JSTさきがけ 田崎勇一 東京工業大学大学院情報環境学専攻 http://springhead.info/ hasevr あっと gmail.com 1 Springhead:An open source physics simulator 目次 物理シミュレーションの役割 物理シミュレーションのしくみ 計算法 安定性と誤差の解消 Articulated Bodyのシミュレーション(Featherstone法） ペナルティ法 接触検出 前進（Explicit）積分と後退（Implicit）積分 誤差の解消法 その他の物理シミュレーション手法 剛体の運動．拘束力．運動方程式への拘束の組み込み 大まかな判定 詳細な判定 物理シミュレータの今後 並列・専用ハード/性能と安定性 さまざまな応用 2 Springhead:An open source physics simulator 物理シミュレーションとは コンピュータの中で物理世界の物の動きを再現 物理世界（実世界） 質量・摩擦係数・跳ね返り係数・位置・速度 … 物体の動きを決める法則と数値計算 物理シミュレーション： 物体の運動 物体の動きを決めるパラメータ（初期条件）を持つ 3DCGモデル：色・形 運動方程式（ニュートン、オイラー、ナビエ・ストークス） 数値計算（オイラー、ルンゲクッタ、前進積分、後退積分） 未来の状態が計算で求まる 3 Springhead:An open source physics simulator 「ふつうの」物理シミュレーション 目的：何かを知りたい・理解したい 例： 銀河の生成 観測結果にあう シミュレーション →銀河のこれま でが分かる SPH法など 楕円銀河の光度進化[Kobayashi 2004] 気候 今日の天気の観測 →明日の天気が分かる 地球シミュレータ グリッド法 大気循環モデル [地球シミュレータセンター大気・海洋シミュレーション研究グループ] 4 Springhead:An open source physics simulator 「ふつうの」物理シミュレーション 例 応力 目に見えない 力を見たい 有限要素法 (FEM) 流体 ANSYSによる構造解析の例 [ANSYS Inc] 目に見えない 流れを見たい エンジン開発のための三次元流体シミュレーションの結果[NASUDA NEWS No.261] 5 Springhead:An open source physics simulator エンタテインメントのための物理シミュレーション 目的：楽しみを感じたい エンタテインメントの対象が感じられる必要がある リアルタイム インタラクティブ 人の作用に反応 反作用を感じる そこに世界があると 感じられる リアルタイムの1/10 リアルタイム 6 Springhead:An open source physics simulator エンタテインメントの対象と物理シミュレーション ゲーム 画面 計算機 コンピュータの中 コントローラ 対象 バーチャルリアリティ コンピュータの中 コンピュータの中の世界に 入り込める 実世界指向 実世界 コンピュータが実世界を 理解・制御 計算機 対象 没入映像 インタフェース 実世界を再現 計算機 センサ 実世界のモデル 実世界を 認識・制御 ロボット 対象 7 Springhead:An open source physics simulator コンピュータの使い方 実世界の課題をコンピュータで 旧来の使い方 記録，計算，検索．．． 人間が実世界とつなぐ 実世界 の課題 新しい使い方 実世界の課題 身近な課題へ利用 身体でコンピュータを使う 実世界のモデル 人間のモデル 計算機 実世界のモデル 人間のモデル センサ インタフェース 実世界 の課題 ロボット ディスプレイ 8 Springhead:An open source physics simulator コンピュータの使い方 実世界志向 実世界を理解・制御 するための シミュレーション 計算機 センサ 実世界のモデル 実世界を 認識・制御 バーチャルリアリティ コンピュータの中に 実世界を作るための シミュレーション ロボット 課題 計算機 ディスプレイ 課題 インタフェース 実世界を再現 9 Springhead:An open source physics simulator 物理シミュレーションの役割 実世界の面白さ 実世界は、行動に応じて変化 多様な行動・多様な変化 ビデオゲーム・バーチャルリアリティ 行動に応じてさまざまに変化するものを作るには？ たくさんの変化の結果を用意 → 場合分けの爆発・膨大な手間と時間 物理シミュレーション → 多様でリアルな変化を自動生成 従来の新技術と同じこと 多量の2次元画像 ストーリの分岐 → → ３DCG 束構造に 10 Springhead:An open source physics simulator バーチャルバスケット 1998 11 Springhead:An open source physics simulator バーチャルカヌー 2005 12 Springhead:An open source physics simulator 物理シミュレーションの役割 実世界指向 実世界の便利さ、面白さをそのまま利用 計算機による実世界の認識・実世界への介入を補助 Virtual Rubik’s cube 指先の位置から手全体の位置姿勢を認識 13 Springhead:An open source physics simulator 物理シミュレーションの役割 実世界指向 実世界の認識を補助 作品Kobito 紅茶缶を画像から、こびとたちと インタラクション可能な物体として認識 14 Springhead:An open source physics simulator まとめ 「ふつうの」物理シミュレーション →物理現象の理解予測 エンタテインメントのための物理シミュレーション →物理世界の楽しさを感じたい 物理世界は楽しい 人の行動に応じて変化する 半分制御可能・半分制御不可能 物理シミュレーションは、 ゲーム・VRでは、これを再現する 実世界指向では、変化する世界を捉える 15 Springhead:An open source physics simulator 物理シミュレーションのしくみ 剛体の運動 拘束力 運動方程式への組み込み 16 Springhead:An open source physics simulator 物理シミュレーションのしくみ 物理法則(現実世界)は微分方程式で記述できる たとえば 質点の運動 f mx 剛体の運動 mv f , Iω 流体の運動 シミュレーションは微分方程式の数値解の計算 運動方程式： f mx f t m x(t t ) x(t ) x (t )t 差分方程式にすると： x (t t ) x (t ) 順番に求めて行く： x(t ) x (t )t x(0) x(2t ) ... x(3t ) ...... m f x … x(0) x(t) x(2t) 17 Springhead:An open source physics simulator 剛体運動のシミュレーション 剛体 硬いもの，変形しないもの 剛体でないもの 積み木，ボール，ロボット・・・ スポンジ，粘土，水・・・ 剛体のシミュレーション 剛体だと思えるものは多い 机・椅子・箱・石… 剛体だと思えることは多い 人や動物の体の動きなど、 本当は剛体ではないけれど、剛体だと思って計算すると 運動が再現できる こんな感じに 18 Springhead:An open source physics simulator 剛体の運動 v: 速度 w:角速度 運動方程式 m: 質量 I: 慣性テンソル f: 外力 mv f v(t t ) v(t ) ft / m τ Iω I(t t )ω(t t ) I (t )ω(t ) τt f 0, τ 0 ならば，速度一定・角運動量一定 19 Springhead:An open source physics simulator 剛体に働く力 重力→ f=mg… 定数 バネ→ f=kx… 位置に比例 拘束力 力の大きさは不明 剛体同士の位置・速度関係が決まっている mg kx 蝶番：2物体の相対位置が一定 抗力：2物体が互いに侵入しない 静止摩擦力：物体が滑らない 拘束力の計算が難しい fn ft 20 Springhead:An open source physics simulator 物理シミュレータの種類 拘束力の計算法が違う 多体の剛体運動(Multi Body Dynamics)シミュレータ 解析法 撃力法 ペナルティ法 全自由度法 Hahn 88 Mirtich 96 Jean Jacques Moreau の方法 自由度削減法 LCPによる定式化 加速度 ベース 速度ベース Stewart 96 ODE Baraff 89 Moore & Williams 89 Springhead1 Armstrong 79 Springhead2 Featherstone 83 OpenTissue 速度ベース・LCPへ定式化 もっとも良く使われている 参考： Havok Novodex ODE … Kenny Erleben: Multibody Dynamics Animation Lecture 12 Department of Computer Science Copenhagen University 21 Springhead:An open source physics simulator 剛体の運動方程式 2物体＋拘束＋外力 mj I j vj wj ri 慣性 M 速度 u 角速度 fc その他の外力 拘束力 重力とか f e rj mi I i vi wi たくさんの剛体＋拘束＋外力 22 Springhead:An open source physics simulator 拘束の例 関節(蝶番の例、接触などは後で) 連結点での相対速度・角速度 w l j 連結点に作用する拘束力・トルク w 1, l1 i e1 w 4, l4 e2 w2,, l2 w 6 , l6 w 3 , l3 e3 w 5 , l5 拘束の座標系 速度 蝶番の軸e3まわりの回転以外は相対運動をしない： 蝶番の軸e3まわりは自由に回転＝トルクは働かない： 力 速度 力 23 Springhead:An open source physics simulator 拘束を運動方程式に組み込む 拘束を剛体の座標系で書きたい→ w,lを書いてみる vj ,wj rj w ri Jrow1 vi ,wi u 外積の行列表示 Jrow4 w2 w3, w5 w6,も同様に書ける u 24 Springhead:An open source physics simulator 拘束を運動方程式に組み込む vj ,wj rj w ri w 拘束座標での 速度・角速度 vi ,wi u 剛体座標の速度・角速度 f j , j rj l ri f i , i fc 剛体座標での 力・トルク l 拘束座標での力・トルク 25 Springhead:An open source physics simulator 拘束の組み込み 拘束を考えやすいように、運動方程式を変形 拘束条件と連立させる(蝶番の例) 拘束： 運動方程式に代入： 連立方程式を解いて求める 26 Springhead:An open source physics simulator シミュレーションの手順 拘束力l を計算 剛体の速度を更新 剛体の位置を更新 全剛体の 位置姿勢 計算法のところで説明 位置 姿勢 Quaternion 速度を Quaternionの微分に 変換する行列 27 Springhead:An open source physics simulator 接触の拘束 接触 接触点での相対速度 接触点に作用する接触力 お互いに侵入しない ＝力が働いて止まる 又は 力は働かず離れる： 速度 力 静止摩擦か動摩擦： 速度 力 トルクは0： 速度 力 28 Springhead:An open source physics simulator 拘束の組み込み(接触の例） 拘束を考えやすいように変形した運動方程式 拘束条件と連立させる 速度 力 速度 力 一見、 1本の式に変数が2つあるように 見えるけれど、 実はどちらか片方しか動かないので解ける 29 Springhead:An open source physics simulator まとめ 速度ベースの拘束法・LCPへ定式化する方法 が良く使われている LCPに定式化して拘束力を求め、積分を繰り返す 剛体の運動方程式をヤコビアンJで座標変換 → wとlの運動方程式 拘束を相対速度wと拘束力lについての式に定式化 wとlの運動方程式に代入LCPになる LCPを解いてlを求め、剛体の速度・位置を更新 拘束 関節は直線、接触は折れ線 ２変数あるように見えて実は１変数 30 Springhead:An open source physics simulator 計算法 連立方程式の解法 LCPの近似解法 誤差の解消法 31 Springhead:An open source physics simulator 連立方程式の解き方 拘束を組み込んだ運動方程式 式1本で変数が2つ 線形相補問題 (LCP:Linear Complementary Problem) LCPを解く ピボッティング法 ・・・ 厳密．低速 反復解法 ・・・ 高速．精度は反復回数に依る 行列分割法 ヤコビ法 ガウス・ザイデル法,SOR法 ニュートン法 32 Springhead:An open source physics simulator ガウスザイデル法・SOR法 行列分割法 巨大な連立方程式の近似解を少ない計算で解く 方法のひとつ もし、漸化式 が収束するなら なので、求めたい となる。 Aが正定値対称行列なら収束する 細長いもの・慣性テンソルが小さいものは 収束しにくい Dは対角行列のような簡単な行列にする。 DをAの対角成分とし、残りをFとしたのがヤコビ法 それを工夫したのがガウスザイデル法 33 Springhead:An open source physics simulator ガウスザイデル法・SOR法 ガウスザイデル法 ヤコビ法：lを一度に更新 ガウス・ザイデル法： lを1行ずつ更新 更新済み 更新中 未更新 SOR法 ガウスザイデル法をちょっとだけ加速 ガウスザイデル法 1.6倍加速 早く収束することもある 34 Springhead:An open source physics simulator LCPとガウスザイデル法 ガウスザイデル法は1行ずつ更新 更新済み 更新中 未更新 接触力をうまく計算できる お互いに侵入しない＝力が働いて止まる 又は 力は働かず離れる： l1を更新するたびに、 l1>0をチェック 負になったら l10に設定 静止摩擦か動摩擦： 更新したl1を使って ml1 <l2< ml1をチェック はみ出したら、l1m l1でクリップ 35 Springhead:An open source physics simulator シミュレーション例 36 Springhead:An open source physics simulator 解析法とペナルティ法の計算の比較 どちらも繰り返し計算で接触力を求めるが： 解析法（ガウスザイデル法） ペナルティ法 解析法は，最初から接触力同士の相互作用を考慮 少ない回数で解にたどり着く可能性がある 37 Springhead:An open source physics simulator 安定性と誤差の解消法 前進（Explicit）積分と後退（Implicit）積分 バネダンパの例 拘束を満たす時刻と安定性 誤差の解消法 この項については，以下で発表をしています： 田崎勇一, 長谷川晶一, “拘束法の動力学シミュレータのための安定なバネダンパモデル”, 情報処理学会 グラフィクスとCAD研究会第124回研究発表会資料, 2006.8 38 Springhead:An open source physics simulator 安定性と積分の方法 前進（Explicit）積分と後退（Implicit）積分 バネ・ダンパの運動方程式 K m Explicit Euler 法 B バネ・ダンパ係数やステップ幅 を大きくすると不安定となる 39 Springhead:An open source physics simulator バネ・ダンパの計算法 （Explicit Euler法） なぜ不安定か？ 安定となるための バネ・ダンパ係数の領域 現在時刻の位置・速度から現在時刻の力を計算 → 積分誤差による不安定化 40 Springhead:An open source physics simulator バネ・ダンパの計算法 （Implicit Euler法） 次の時刻の位置・速度から現在時刻の力を計算 全域で安定 41 Springhead:An open source physics simulator 拘束を満たす時刻と安定性 加速度ベース [baraff 89など] 解析法 全自由度法 Jean Jacques Moreau の方法 自由度削減法 LCP 加速度 ベース Baraff 89 速度ベース Stewart 96 ODE Springhead2 OpenTissue Armstrong 79 Featherstone 83 運動方程式 拘束式 （加速度レベル） この瞬間[t]に、拘束を満たす 連立 速度更新 位置更新 積分誤差の累積によるドリフト 42 Springhead:An open source physics simulator 拘束運動の計算法 速度ベース [Stewart96など] 解析法 全自由度法 Jean Jacques Moreau の方法 自由度削減法 LCP 加速度 ベース Baraff 89 速度ベース Stewart 96 ODE Springhead2 OpenTissue Armstrong 79 Featherstone 83 運動方程式 連立 速度更新 拘束式 （速度レベル） 次の時刻[t+1]に拘束を満たす 位置更新 積分（速度更新）を考慮して拘束力を計算→ドリフトが少ない 43 Springhead:An open source physics simulator 拘束の組み込み 拘束を考えやすいように、運動方程式を変形 ここが、w[t+1]なので、 拘束条件と連立させる(蝶番の例) 拘束： 拘束は、w[t+1]についての拘束になっている 運動方程式に代入： 連立方程式を解いて求める 44 Springhead:An open source physics simulator Implicitのバネダンパ 時刻[t+1]にバネダンパの制約を満たす 関節にバネダンパー 並進のバネダンパー 関節角度 伸び（定数） 関節角速度 伸びの速度 関節トルク バネダンパ力 LCPに組み込むことができる 45 Springhead:An open source physics simulator 安定性の評価 剛体5つ 蝶番5つ，4つにバネダンパ バネダンパ1つ 重力 このバネ・ダンパについて Implicit版とExplicit版を比較 46 Springhead:An open source physics simulator 誤差の解消法 誤差がたまる原因は…もう一度拘束を考えてみる vj ,wj rj p,w ri vi ,wi 関節位置での相対速度がwi[t+1]=0 となるように、拘束力lを計算している 速度を積分した相対位置には、誤差がたまる →誤差を解消する必要あり 誤差の解消法 速度を変化させる方法（ペナルティ法） ODE, 誤差が残る(隙間が開いたりする)が自然で安定 位置を変化させる方法（位置についての解析法） OpenTissue, 誤差が見えないが、不安定になることがある 47 Springhead:An open source physics simulator 誤差の解消法１：速度を変化させる方法 拘束＋運動方程式 e に速度の修正を加える 誤差が減るような速度になるような拘束力l’が求まる 48 Springhead:An open source physics simulator 誤差の解消法２：位置についての解析法 運動方程式から作った速度の更新式 e の位置版を考える。 位置版に、拘束条件の変形をする 速度版 位置版 ガウスザイデル法でlを求め、s’を求める 49 Springhead:An open source physics simulator 誤差の解消法：どちらがよいか 速度を変化 位置の解析法 誤差はすぐには解消しない ペナルティ法的 毎回、誤差を0にしてくれる 解析法的 わずかな式変形 Al+bのAは再利用できるが 計算はとても少ない あとは計算が必要 ガウスザイデルをもう1つ解く 速度に影響がない 速度が変化する 誤差 誤差 ステップ ステップ 50 Springhead:An open source physics simulator 誤差の解消法：どちらがよいか 強い外力の影響 強い外力feに対抗する 関節の拘束力l ガウス・ザイデル法の 打ち切りのため、 | l | < | fe | となり、剛体はだんだん加速。 速度変化で解消の場合 位置の解析法で解消の場合 fe w e l で位置sを補正するが、速度wは補正なし→加速し続ける 速度変化は必須、位置の補正は誤差を隠してくれる 51 Springhead:An open source physics simulator ガウスザイデル法の誤差 計算のイメージ どちらから近づくか 内側（原点側）から近づく →真の値より小さな値 →安定、ダンパ気味 外側から近づく →真の値より大きな値 →不安定 １つ前のシミュレーションで求めた lprevからスタートすると収束が早い が、外側から近づく危険あり 不安定になりやすい（例） 1.0 0.8 1.2 lprev 0 52 Springhead:An open source physics simulator その他の物理シミュレーション手法 フェザーストーン法 ペナルティ法 53 Springhead:An open source physics simulator Articulated Bodyのシミュレーション Articulated Body 解析法 全自由度法 Jean Jacques Moreau の方法 自由度削減法 LCP 速度ベース 加速度 ベース Baraff 89 Stewart 96 ODE Springhead2 Armstrong 79 Featherstone 83 OpenTissue 多数の剛体を関節でつないだもの 動物や人間の体，ロボットなど 普通にLCPでも解けるが… 自由度削減法 可動関節だけをシミュレーション 剛体が輪になっていない＝木構造 で高速な手法 輪になっている例 54 Springhead:An open source physics simulator 解析法で求めると．．． l2 l1 l3 l5 l4 l6 からlを解いて、剛体の速度uを更新 uから剛体の姿勢sを更新 uの誤差→sに誤差がたまる →蝶番がずれたりする 55 Springhead:An open source physics simulator Featherstoneの方法 状態変数 根のリンクの速度・角速度，位置・姿勢 各関節の可動部分の角度，角速度 リンクの位置・速度など他の値は持たない 関節が外れることはない fi , t i リンクi 葉のリンク v i , ωi 葉のリンク リンクi と，より葉側のリンク 根のリンク Springhead:An open source physics simulator 関節の拘束力の計算 Featherstoneの方法 木構造のリンク用 リンクiの運動方程式は， fi v i I i Z i i ti ω Ii: リンクIと葉側のリンクの慣性項 Zi: 外力，重力，コリオリ力による項 Ii,Ziは関節加速度によらない のように，書ける． Ziはリンクiと葉側のリンクの 姿勢・速度で決まる fi , t i リンクi Ii , Zi を葉から順に計算 根側から，v, wを計算 葉のリンク v i , ωi 葉のリンク リンクi と，より葉側のリンク 根のリンク Springhead:An open source physics simulator FeatherstoneのLCPへの組み込み LCPによる定式化では、 剛体の質量・慣性を並べて運動方程式を作った これにArticulated Bodyを加えると 解析法 全自由度法 Jean Jacques Moreau の方法 加速度 ベース Baraff 89 wjoint IA vbase wjoint 自由度削減法 LCP wbase 速度ベース Armstrong 79 Stewart 96 ODE Springhead2 OpenTissue wjoint wjoint Featherstone 83 wjoint wjoint 参考： S. Redon et al. "Adaptive Dynamics of Articulated Bodies" SIGGRAPH 2005 58 Springhead:An open source physics simulator 解析法 全自由度法 ここまでで取り上げた方式 利点 動作が安定 低速更新が可能 ペナルティ法 解析法 撃力法 Jean Jacques Moreau の方法 自由度 削減法 LCPによる定式化 速度ベース 欠点 1ステップの計算量はある程度多い. ⇒低速更新 安定だが精度が悪い 59 Springhead:An open source physics simulator ペナルティ法 ペナルティ法 解析法 撃力法 全自由度法 Jean LCPによる定式化 Jacques 速度ベース Moreau の方法 拘束を満たす向きに適当な力を加える 自由度 削減法 . 侵入量 d，侵入量の速度 d fn k nd bn d バネ ダンパ . 滑り量 l，滑り速度l ff k f l b f l バネ ダンパ 欠点 利点 ｔを小さくしなければならない 1ステップの計算が速い. O(n) 安定性が低い ⇒高速更新可能 高速更新⇒高精度 Featherstone法と簡単に組み合わせ られる 60 Springhead:An open source physics simulator 接触体積の形状を考えたペナルティ法 広い接触面があるとき バネダンパモデルはどこに置けばよいか？ ? 最侵入点にした場合 61 Springhead:An open source physics simulator 広い接触面の扱い バネダンパモデルはどこに置けばよいか？ ? 頂点にした場合 Top view 62 Springhead:An open source physics simulator 広い接触面の扱い バネダンパモデルはどこに置けばよいか？ ? うまく働くが， 計算時間がかかりすぎる 多点でサンプリング 63 Springhead:An open source physics simulator 広い接触面の扱い ! 分散バネ・ダンパモデル 3角形ごとに分散バネ・ダンパモデルからの力を積分 64 Springhead:An open source physics simulator 処理の手順 接触力の計算 1. 2. 3. 接触体積内の1点と法線を求める（GJK) 接触体積の形状を求める(Muller and Preparata) 接触面にかかった力を積分する 65 Springhead:An open source physics simulator 接触解析 接触部分= 2つの凸多面体の交差部分. D. E. Muller and F.P.Preparata: “Finding the intersection of two convex” (1978) 2つの凸多面体と交差部分上の1点が与えられたとき， 交差部分の形状を求める 66 Springhead:An open source physics simulator 力の積分 抗力 動摩擦力 最大静止摩擦力 分散バネ・ダンパモデルからの力を3角形ごとに積分 67 Springhead:An open source physics simulator 3角形ごとの積分 p2 p3 p 3 h3 抗力バネモデルによる力 f k h p ndS h2 p1 ptri 1 k (h1 h2 h3 ) n 3 抗力バネモデルによるトルク τ k p hpndS ptri 1 k (( h1 h2 h3 ) (p1 p 2 p3 ) 3(h1p1 h2p 2 h3p3 ) ) 36 68 Springhead:An open source physics simulator フォースフィードバックへの応用例 高速更新なので、フォースフィードバックの感覚が良 い 69 Springhead:An open source physics simulator ペナルティ法と解析法の拘束力と動作の比較 解析法 次のステップで拘束を満たすlを 繰り返し計算で求める 位置の 誤差 ペナルティ法 拘束違反を減らす向きのlを 毎ステップ加える lp l\ l20 速度の 誤差 70 Springhead:An open source physics simulator 接触検出 大まかな判定 バウンディングボックス ソート 詳細な判定 GJK 接触形状 71 Springhead:An open source physics simulator 接触検出 接触の拘束を考えるためには、接触検出が必要 高速化のための工夫 まず大まかな判定をして、明らかに接触してないものを候 補からはずす。 その後詳細な判定をする。 72 Springhead:An open source physics simulator 接触検出と計算速度 接触力を求める→高速な衝突判定が必要 階層化 簡単な境界で囲む 階層的に境界を作る 大まかに判定してから，詳細な判定をする 境界（Bounding）の例 球 判定簡単 K-DOP AABB ぴったりフィット 73 Springhead:An open source physics simulator 階層化と計算時間 階層化すると log2n 回の検出で終わる log2n n 74 Springhead:An open source physics simulator アルゴリズムの速度 a を検索 ランダム AdhjJLfC gMalmD bpEH UVstwQ RWYxzOZ 頭から見ていく O(n) ソートされている場合 ACDEHJLMOQRUVWYZabdfghjlmpstwxz あたりをつけてみていく O(log n) きちんと並んでいる場合 ABCDEFGHIJKLMNOPQRSTUVWXYZabcde どこにあるか分かる O(1) 75 Springhead:An open source physics simulator アルゴリズムの速度 対象に対する知識があるほど速く出来る ランダム a = = ? しか分からない場合 ソートされている場合 知識なし 左＜右 ＜演算が定義されている きちんと並んでいる場合 右－左＝3 何がどこにあるか分かっている 76 Springhead:An open source physics simulator アルゴリズムの速度（ソート） 総当りソート： O(n2) 5 7 3 6 9 1 2 1 5 7 6 9 3 2 1 2 5 7 6 9 3 最小を先頭へ 最小を先頭へ クイックソート： O(n log n) 5 7 3 6 9 1 2 <5を前へ 3 1 2 5 7 6 9 3 1 2 <3を前へ 7 6 9 <7を前へ n回比較 n回 n回比較 n回比較 log n回 n回比較 バケツソート： O(n) 5 7 3 6 9 1 2 1 2 3 1 2 3 4 5 6 7 5 6 7 8 9 9 n回移動 1回 77 Springhead:An open source physics simulator 運動する物の接触検出 物体が動き回る場合，毎回境界の更新が必要 境界の更新に時間がかかる 総当りも時間がかかる ５ ２ ４１ ３ ６ 1-2 1-3 1-4 1-5 1-6 2-3 2-4 3-4 2-5 3-5 4-5 2-6 3-6 4-6 5-6 n n O(n2 ) 78 Springhead:An open source physics simulator 運動する物の接触検出 ソート＝境界を作りながら判定 ５ ２ ４１ ３ ６ 1より左？ 1-2 1-3 1-4 1-5 1-6 1より右？ 1-3 1-4 1-6 ５ ２ ４ ４１ 要判定 ３ 2より左？ 2-5 2-4 ６ 4より左？ 2-4 1-4 の判定 O(n log n) 79 Springhead:An open source physics simulator 接触検出 中身の判定 中身は 三角形？ 凸多面体 多面体？ 凸形状 凸形状 距離が極小となる点が1点 非凸形状 最近傍点が簡単に求まる GJK algorithm E. G. Gilbert, D. W. Johnson and S. S. Keerthi A Fast Procedure for Computing the Distance between Complex Objects in Three-Dimensional Space (1988) ほかにLin-Canny algorithm というのもあります Ming Lin, John Canny A fast algorithm for incremental distance calculation (1991) 80 Springhead:An open source physics simulator GJK 凸形状A上の点から，凸形状B上の点へのベクトルを 原点を始点に並べる（Minkowski sum）と ベクトルの終点の集合も凸形状になる 元の図形 Minkowski Sum をとったもの 81 Springhead:An open source physics simulator GJK V0 : 凸形状内の任意の点 Wi :OViとOWiの内積が最小の点(support point) １ OVi ２ Wi OVi Wi Vi :三角形Wi-2 Wi-1 Wi内の点で原点に一番近い点 Vi = s Wi-2 +t Wi-1 +(1-s-t) Wi W3 ３ ４ V W2 W1 元の図形上で、最近傍点が求まる 82 Springhead:An open source physics simulator 速度を考慮したGJK 衝突の瞬間（Time of Impact TOI）と 衝突の位置・法線が分かる． 接触点 もとの図形 Minkowski Sum 83 Springhead:An open source physics simulator GJKを使った接触点の計算 １ r r ３ 0 ２ r ４ 参照： Continuous Collision Detection of General Convex Objects under Translation [G. van den Bergen] 84 Springhead:An open source physics simulator GJKの結果の解釈 法線 そのまま実世界の法線 接触点 Support point を内分した点 →実世界の Support points を内分して求める． これを求める→実世界の頂点の引き算 どれを使ったか覚えておけば元に戻せる 85 Springhead:An open source physics simulator GJKの結果の解釈２ 重なっていると，戻せない Minkowski Sum 元の形状 元の形状でのの3つの点は，変換した形状では1点 →どこだか分からない． 86 Springhead:An open source physics simulator 接触解析 衝突部分の形状（切り口）を求める方法 切り口の頂点に接触の拘束を考える D. E. Muller and F.P.Preparata: “Finding the intersection of two convex” (1978) 凸形状２つの交差部分の形を求める 共有点１点が必要（GJKで求められる） 切り口の形、頂点を知ることができる 切り口 上から見た図 断面図 87 Springhead:An open source physics simulator 接触解析(2) ２つの凸形状の交差部 半空間表現 88 Springhead:An open source physics simulator 接触解析(3) ２つの凸形状の交差部(2) 半空間表現 双対変換 交差部の頂点 双対変換 Quick hull n log n 89 Springhead:An open source physics simulator 物理シミュレーションのこれから 並列化・ハードウェア化 スピードと安定性 いろいろな利用 90 Springhead:An open source physics simulator 並列化について 物理シミュレーションは たくさんのものに同じ法則を適用 →並列化に向いている 粗い判定： n2の並列計算も可能 GJK・接触解析： 接触ペアの数だけ並列計算 ガウスザイデル： 行列の1行ごとに並列計算 専用計算機向きか？ GRAPE 剛体・流体…は？ 天体シミュレーション用 (1991 15GFPS ＠ i486の時代) 重力計算が主 → 専用ハードが作りやすい データが複雑（特に接触検出・解析） 対象がさまざま →専用チップ化にはあまり向かない CELL/PhysX は並列汎用計算機。 GPGPUはソートなどあと一歩。 91 Springhead:An open source physics simulator スピードと安定性 剛体はスピードより安定性 そろそろ数は十分 どんなシミュレータも発振する 制御の安定性の保証がほしい Havok FXの例 PD制御発振の例 Wrotek et al. 2006 92 Springhead:An open source physics simulator スピードと安定性 流体はまだまだスピードがたりない 2次元の波面 → 十分リアルタイム 3次元のメッシュ → かなり厳しい 3次元の粒子 → たくさんの量は扱えない 組み合わせが必要かもしれない A Fluid Resistance Map Method for Real-time Haptic Interaction with Fluids [Y. Dobashi et al. 2006] 3次元流体シミュレーション 圧力場・流速 (FRM :Fluid Resistance Map) 事前計算 パドルの速度 水の速度 R 力覚フィードバック リアルタイム波シミュレーション リアルタイム Efficient Simulation of Large Bodies of Water by Coupling Two- and Three-Dimensional Techniques [G. Irving et al. 2006] 93 Springhead:An open source physics simulator 物理シミュレーションの利用 リアルな動きの生成に利用 ゲームの物理 キャラクタモーション 身体のシミュレーション 実世界とバーチャル世界をつなぐ 実世界の認識の補助 実世界で再現可能なバーチャル世界を作る 94 Springhead:An open source physics simulator キャラクタモーション Oshita 2001 PD制御で加速度を決める ← トルク/ZMPの制約 ○ PDの調整が簡単。 △外力が加わった場合の動作 トルクではなく、加速度 Liu et al.2005 軌道全体を最適化 ○ 高度な最適化 △ リアルタイム生成は困難 Zordan et al. 2005, Zordan and Hodgins 2002, Natural Motion Endorphin コントローラ＋シミュレーション． 関節角度をPD制御 ○ リアルタイム生成 △ コントローラの作成 95 Springhead:An open source physics simulator キャラクタモーション モーションキャプチャデータの変換 人体モデルのマーカ位置を キャプチャした データ位置に PD制御 関節角を記録 関節トルク・床反力の計算 関節をPD制御して動作を再生 関節と床から働く力を計算 96 Springhead:An open source physics simulator キャラクタモーション Hasegawa et.al 2005 関節と手先位置をPD制御 力覚インタフェース 物理シミュレータ 力フィード バック Motion Controller Reaching motion Default posture 手の位置 The World State transition Attack 予測用シミュレータ Guard 行動ルール Wait Virtual human’s mind 97 Springhead:An open source physics simulator 身体のシミュレーション 筋骨格系＋神経系のシミュレーション M. Otake and Y. Nakamura 2005 98 Springhead:An open source physics simulator ロボット・作業のシミュレーション レスキュー 機構シミュレーション ロボカップ 99 Springhead:An open source physics simulator まとめ エンタテインメントのための物理シミュレーション 物理シミュレーションのしくみ 人が物理を感じられるシミュレーション リアルタイム・インタラクティブ 定式化、LCPの近似解法 安定性と誤差の解消 Featherstone法・ペナルティ法 接触検出（GJK, 接触部分の形状） 物理シミュレータの今後 並列・専用ハード/スピードと安定性 さまざまな応用 100
© Copyright 2024 ExpyDoc
