Ten Minute Physicsを動かしてみる

Ten Minute Physicsという、スクラッチで物理シミュレーションを作るというページがあったので一通り動かしてみた。

• 動画による説明もあってわかりやすい
• 実際にブラウザ上で動作するコードも提供されている
• 簡単なボールのバウンドから始まって、衝突、クロスシミュ、GPU、流体、など
• Matthias Müller氏はPBD (Position Based Dynamics)の研究者らしい

メモ

01 - Introduction to 2d web browser physics

• htmlファイル1つで、中に書かれたJavaScriptで実行
• 描画にはHTMLキャンバスを利用
• ボールに重力が働いているという単純なシーン
• シンプレクティック・オイラー法（速度を更新してから位置を更新する）
  • シミュレーションが安定する

var gravity = { x: 0.0, y: -10.0};
var timeStep = 1.0 / 60.0;

function simulate() {
  ball.vel.x += gravity.x * timeStep;
  ball.vel.y += gravity.y * timeStep;
  ball.pos.x += ball.vel.x * timeStep;
  ball.pos.y += ball.vel.y * timeStep;
  ...

• 誤差を少なくする方法
  • ❌方程式を解く：簡単な問題にしか使えない
  • ❌洗練された積分：遅い、衝突時には改善されない
  • ✅dtを小さく：シンプル、うまくいく！

02 - Introduction to 3d and VR web browser physics

• THREE.js を使って3D表示
• ライト、マテリアル、メッシュ、ベクトル、カメラ、とお作法が大変だけど、シミュレーションのキモは変わらず：

class Ball {
  ...
  simulate()
  {
    this.vel.addScaledVector(physicsScene.gravity, physicsScene.dt);
    this.pos.addScaledVector(this.vel, physicsScene.dt);
    ...

03 - Ball collision handling in 2d

• いくつもの円がお互いに衝突するデモ（いったん2Dに戻る）
• 衝突後の相対速度＝衝突前の相対速度＊反発係数　になる（１で完全弾性）
  • 速度を直接変更する
• ボール同士のコリジョンは二重ループですべてのペアについて調べる($O(n^2)$)
  • めり込んだ距離を押し戻すという処理をしている（質量に関係なく等分に）
  • 速度が衝突する方向か？という判定はしてない

04 How to write a pinball simulation

• ピンボール
• フリッパーは角速度で動かして角度に制限をつける
• フリッパーのコリジョン：カプセル形状（四角の先端に半円を被せた形）
  • フリッパーの速度は、角速度から衝突地点の速度を計算
  • 衝突で変化するのはボール側の速度だけで、フリッパーは影響を受けないものとしている
• ボールがバンパー（当たると勢いよく弾かれるやつ）と当たった場合は、指定の速度になるよう押し出している

05 The simplest possible physics simulation method

• 拘束を扱う方法の候補：
  • ばね：硬さの調整が必要、硬くしすぎると不安定になる
  • 一般化座標系：複雑
  • 拘束力を解く：ずれ(drift)を打ち消すトリックが必要
• 単純な方法：無理やり位置を合わす！
  • 速度もいじる：（新たな位置 - 以前の位置）/dt

while simulating
  v <- v + g dt
  p <- x
  x <- x + v dt
  satisfyConstraint(x)
  v <- (x - p) / dt
end

• シミュレーションを進めるサブステップを1000とか100とかしてる、強烈…！
• 解析的に解いて動かした場合との比較：サブステップを増やせば解析的に解いた場合に収束する
• Position Based Dynamics (PBD)、Verlet法などと言われる方法

06 Writing a triple pendulum simulation is simple

• 三重振り子
• 長さを拘束するために位置を動かす、根元の方から計算していくが、末端側の位置だけを動かす、とかではなく両方動かす
  • なので拘束の解決後も微妙にずれてはいるハズ
• サブステップ数はShortで100
• 解析的に解いた版との比較も見れる
  • 一部解析的ではなく数値積分してる（omega、thetaの更新）
• XPBD (extended position-based dynamics)：はソフト拘束には有効だが、このハード拘束の場合はPBDと同じ正確度とのこと

07 Intuitive 3d Vector Math for Simulation

• ３次元ベクトルの数学

08 Providing user interaction with a 3d scene

• ３次元ビューをマウス操作で物体を掴んだりできる便利クラス Grabber
  • レイキャスト：THREE.jsのRaycasterクラスintersectObjectsメソッド

09 Getting ready to simulate the world with XPBD

• 力ベースシミュレーション／撃力ベースシミュレーション
• 位置ベースシミュレーション
  • 陰的オイラー積分に非常に近い
  • ソフトさを扱う場合のみ非物理的→XPBDで修正
• イテレーション（拘束処理だけ何回かやる） vs サブステップ（dtを何分割かする）
  • サブステップの方が効果的
• 拘束をソフトに：
  • PBD：補正量に定数 $k \in [0, 1]$ を乗算（タイムステップによって硬さが変わってしまう）
  • XPBD：$\lambda$計算時に$\alpha / \Delta t^2$を考慮
• 三角錐の体積を保持する拘束：ソフトボディ

10 Simple and unbreakable simulation of soft bodies

• ソフトボディ：
  • 連続モデル＆グローバルソルバー：コンピュータ以前、数式で解くための方法
  • 離散モデル＆ローカルソルバー：質点を簡単な拘束でつなげる（自然！）
• 離散モデル：テッセレーションが挙動に強く影響する
  • → ユニフォームメッシュを使う、非等方性非連続シミュレートを利用
• ローカルソルバー：収束が遅い
  • → サブステップを使う
• スタンフォードバニー：四面体メッシュ化
  • 頂点ごとに１質点、辺ごとに１距離拘束
  • 四面体ごとに１体積拘束
• デモ：
  • サブステップ：10
  • 体積拘束のソフトさは０で、距離拘束のソフトさをいじれる

11 Finding overlaps among thousands of objects blazing fast

• ナイーブに衝突判定すると$O(n^2)$
• レギュラーグリッド：空間を一定間隔の格子に分割する
• 質点の半径をr、グリッドサイズh = 2rとすると、隣接する格子だけチェックすればよい
• 密集グリッド表現：パーティクル数のサイズの配列を別途用意
  • セル順にソート
  • セルに含まれるパーティクルの個数は次のセルの番号との差分から求められる
• 範囲の制限をなくす：hash(xi, yi) % tableSize
  • ハッシュが衝突しても大丈夫
• 構築はかなり巧妙…！
• ボールごとにクエリして、対象のボールに対して衝突判定する
  • （完全に理解したとは言い難い）

12 100x speedup for soft body simulations

• ソフトボディの高速化：削減したシミュレーション用メッシュで計算
• 詳細なモデルの頂点を削減したものにどう割り当てるかという話？よくわからず…

13 Writing a Tetrahedralizer for Blender

• Blenderのプラグインとそのアルゴリズム
• インクリメンタルドロネーメッシュ

14 The secret of cloth simulation

• 布シミュの秘密：布は曲がるだけ！（ほとんど伸びない）
• 曲げ拘束：
  • 隣接する三角形の頂点に距離拘束を入れる：今回はこっち
  • 角度拘束を入れる：より重い

15 Self-collisions, solving the hardest problem in animation

• 布シミュでセルフコリジョンを扱う
  • コリジョンはパーティクルで行っていて、三角形で行うわけではない
• サブステップ10
  • サブステップを大きくしてそもそも抜けが発生しないようにするのが重要ぽい
• 布：パーティクルを0.01[m]間隔で配置、横30 x 縦200
• 布の厚さ(thickness)：0.01 [m]　（＝パーティクルの直径）

16 Simulation on the GPU

• Python+Warp、Nvidia Omniverseで動かす
• 速度の更新だけGPUにやらせる
• 拘束で複数のスレッドが位置を書き換えると問題が起こる件

17 How to write an Eulerian Fluid Simulator with 200 lines of code.

• カルマン渦、いいよね
• オイラリアン（グリッドベース）
• 圧力計算：Overrelaxationを入れる

18 How to write a FLIP Water Simulator.

• パーティクルとグリッドを併用する感じ？
• PIC (Particle In Cell)とFLIP (FLuid Implicit Particle)のブレンド

19 Differential equations and calculus from scratch

• なぜここでこの内容なのかわからず…動画長い…

20 How to write a height-field water simulation.

• 波動方程式を隣接するセルとの高さの差分で解くやつ
• 屈折で水面下が歪むのがいいね

感想

• 後半は理解せずに流してしまった…
• WebGPUとか使って、ブラウザ上でGPUで動かしたい
• PBD、XPBDを見てみる

リンク

• Ten Minute Physics
  • YouTube: Ten Minute Physics - YouTube
  • リポジトリ： https://github.com/matthias-research/pages/tree/master/tenMinutePhysics
  • Twitter: TenMinutePhysics（@TenMinPhysics） / Twitter

PBD関連

• Position Based Dynamics : XPBD、SubstepXPBDをUnityで実装してみた - Qiita
• ［CEDEC 2014］剛体から流体まで，セガのプログラマーが語る「位置ベース物理シミュレーション」の最前線
• Extended Position Based Dynamics | XPBD | Carmen’s Graphics Blog