v Δ t > w + 2 r

計算の裏側

衝突判定とすり抜け

Collision detection and tunneling

速い弾は、壁の手前と向こうにしか現れない。

速い物体が薄い壁をすり抜ける理由を、1 コマで進む距離から考える。離散的な判定と連続的な判定、広域と詳細の判定、跳ね返りの力積、刻みと壁の厚さの決め方まで。

種類: 計算の裏側
公式: 3 本
人物: アイザック・ニュートン

運動方程式三平方の定理二次方程式の解の公式

場面

壁を通り抜ける弾

ゲームを作っていると、速く飛ばした弾やボールが、薄い壁や床を通り抜けてしまうことがある。ゆっくり転がすと必ず止まるのに、強く撃つと抜ける。細いレールの上を速く走るビー玉が、レールを突き抜けて落ちる。物理エンジンの文書にも、この現象の名前と対策が書かれている。

理由は単純である。計算機の中の物体は、1 コマごとの位置にしか存在しない。1 秒に 60 コマ(フレーム)で計算するとき、秒速 30 m のボールは 1 コマに 0.5 m 進む。半径 15 cm のボールが厚さ 10 cm の壁に向かうと、あるコマでは壁の手前に、次のコマではもう壁の向こうにいることがある。どちらのコマでも壁と重なっていないので、計算機は何にもぶつからなかったと判断する。これをすり抜け(トンネリング)と呼ぶ。

この記事では、すり抜けが起こる条件を式で表し、物理エンジンがそれをどう防いでいるか、たくさんの物体の中からぶつかりそうな組をどう速く探すか、ぶつかったあとの跳ね返りをどう計算するかを順に考える。

考え方

1 コマで進む距離

最も簡単な衝突判定は、1 コマ進めたあとで、物体どうしが重なっているかを調べる方法である。これを離散的な判定と呼ぶ。重なっていれば、重なりの浅い向きへ押し戻し、速度を変える。

半径 $r$ のボールが、厚さ $w$ の壁に向かってまっすぐ進むとする。ボールの中心が壁と重なる範囲は、手前の面より $r$ だけ手前から、向こうの面より $r$ だけ先までの、幅 $w + 2 r$ の区間である。1 コマで進む距離 $v Δ t$ がこの幅より大きいと、中心の位置がこの区間を飛び越えることがある。

落とし穴はもう 1 つある。重なりを見つけても、中心がすでに壁の真ん中を越えていると、浅いほうの面、つまり向こう側へ押し出してしまう。正しく跳ね返すには、最初に重なったときの中心が壁の手前半分に入っている必要がある。手前半分の幅は $r + w /2$ なので、 $v Δ t$ がこれより短ければ、どこから撃っても正しく跳ね返る。

撃つ位置が 1 コマの範囲で一様にばらつくとすると、抜ける確率は $1 - (r + w /2) / (v Δ t)$ になる。 $r = 15$ cm、 $w = 10$ cm、1 秒に 60 コマ( $Δ t = 1/60$ 秒)で計算すると、秒速 12 m までは必ず跳ね返る。秒速 15 m では 20 %、30 m(時速 108 km)では 60 %、60 m では 80 % の確率で抜ける。1 秒に 240 コマに増やせば、必ず跳ね返る速さは秒速 48 m まで上がる。

式

式で見る

速さ $v$ でまっすぐ進むボールの中心は、コマごとに $v Δ t$ ずつ飛び飛びに進む。
$x_{n} = x_{0} + n v Δ t$
手前の面が $x_{w}$ で厚さ $w$ の壁と、半径 $r$ のボールが重なる条件。
$x_{w} - r < x_{n} < x_{w} + w + r$
幅 $w + 2 r$ の区間に、間隔 $v Δ t$ の点が 1 つも入らないことがある条件。これがすり抜けの条件である。
$v Δ t > w + 2 r$
最初に重なる位置が壁の手前半分に入る割合から、離散的な判定で抜ける確率 $P$ が出る( $v Δ t > r + w /2$ のとき)。
$P = 1 - \frac{r + w /2}{v Δ t}$
連続的な判定。コマの初めの位置 $x_{n}$ から、ボールの面が壁の面に触れる時刻 $t^{*}$ を解く。 $0 \leq t^{*} \leq Δ t$ なら、そのコマの途中でぶつかっている。
$x_{n} + v t^{*} + r = x_{w} ⟹ t^{*} = \frac{x _{w} - r - x _{n}}{v}$
2 つの円がどちらも動くときは、相対位置 $p$ と相対速度 $u$ で考え、中心の距離が半径の和 $r_{1} + r_{2}$ になる時刻を解く。 $t$ の二次方程式になり、小さいほうの解が最初に触れる時刻である。
$∣ u ∣^{2} t^{2} + 2 (p \cdot u) t + ∣ p ∣^{2} - (r_{1} + r_{2})^{2} = 0$
跳ね返り。接触点で物体 2 から物体 1 へ向かう単位法線を $n$ 、相対速度を $v_{rel} = v_{1} - v_{2}$ 、反発係数を $e$ とする。近づいている( $v_{rel} \cdot n < 0$ )とき、力積の大きさは次のとおりである(回転を考えない場合)。
$j = \frac{- ( 1 + e ) v _{rel} \cdot n}{1/ m _{1} + 1/ m _{2}}$
力積を互いに逆向きに加える。ぶつかったあとの法線の向きの相対速度は、前の $- e$ 倍になる。壁のように $m_{2}$ がとても大きければ $1/ m_{2} = 0$ として扱える。
$v_{1}^{'} = v_{1} + \frac{j}{m _{1}} n, v_{2}^{'} = v_{2} - \frac{j}{m _{2}} n$

手順 6 は二次方程式の解の公式で解ける。判別式が負ならすれ違い、 $p \cdot u > 0$ なら離れていく向きなのでぶつからない。手順 7 の力積は運動方程式を短い時間で積分したもので、2 つの物体の運動量の合計は変わらない。

図

2 つの判定

上は離散的な判定。ボールは 1 コマごとの位置にしか現れず、壁の手前と向こうのどちらの位置も壁と重ならないので、ぶつかったことに気づかない。下は連続的な判定。1 コマの間にボールが通る範囲(点の網)と壁が交わることから、壁に触れる時刻 t* を求めて跳ね返す。

シミュレーション

薄い壁にボールを撃つ

厚さ 10 cm の壁に、半径 15 cm のボールを撃つ。点は 1 コマごとの中心の位置で、速さ $v$ と刻み $Δ t$ を上げると点の間が開き、壁を飛び越えるようになる。撃つ位置を毎回 1 コマぶんの範囲でずらしているので、はじめの設定(秒速 30 m、1 秒に 60 コマ)では跳ね返ったり抜けたりし、発数を重ねると抜けた割合が式の予想 60 % に近づく。「連続的な判定」を入れると、どの速さでも衝突の時刻 $t^{*}$ で止まって跳ね返り、跳ね返ったあとの速さは反発係数 $e$ 倍になる。

考え方

広域の判定と詳細な判定

画面に物体が 1000 個あれば、2 つずつの組は $1000 \times 999/2 = 499, 500$ 組ある。毎コマすべての組を細かく調べると、それだけで計算が追いつかない。そこで物理エンジンは、判定を 2 段に分ける。

広域の判定(ブロードフェーズ)。 各物体を、座標軸に平行な箱(AABB)で囲む。箱どうしの重なりは、座標の大小を比べるだけで分かる。そのうえで、箱が重なりそうな組だけを速く拾い出す。空間を同じ大きさのマス目に分け、同じマスや隣のマスの物体だけを比べるのが格子の方法である。箱の端の座標を軸に沿って並べ替え、区間が重なる組だけを残すのがスイープ・アンド・プルーンで、1995 年の I-COLLIDE は、前のコマの並びを挿入ソートで直せば、物体が少しずつしか動かない限りほぼ線形の時間で済むことを使った。Matter.js の判定も、物体を箱の左端で並べ替えて横に走査している。Box2D は、箱を木の形にまとめた動的な AABB 木を使う。

詳細な判定(ナローフェーズ)。 残った組について、本当に重なっているかを調べる。円と円なら、中心の距離が半径の和より小さいかどうかである。距離は三平方の定理で求まり、平方根を取らずに 2 乗どうしで比べれば計算が軽い。凸な多角形どうしには分離軸定理を使う。2 つの凸な図形が離れているなら、辺に垂直な向きのどれかの軸に図形を射影すると、射影した区間(影)が重ならない。2 次元では両方の図形の辺の法線だけを、3 次元の直方体どうしなら 15 本の軸を調べれば足りる。Matter.js は各物体の辺の法線で影の重なりを調べ、重なりの最も小さい向きを押し戻す向きにしている。Box2D は多角形どうしに分離軸の判定を使い、一般の凸な形の距離は GJK 法で求める。

図

分離軸

2 つの凸な図形 A と B を、A の辺に垂直な軸に射影する。影の区間の間にすき間があるので、A と B は離れている。凸な図形が重なっているなら、どの軸に射影しても影は重なる。

歴史

跳ね返りの係数と研究の歩み

跳ね返りの強さを表す反発係数 $e$ は、ニュートンの実験にさかのぼる。1687 年の『プリンキピア』で、運動の法則のあとに置いた注釈の中で、ニュートンは長さ 10 フィートの振り子で球をぶつけ、離れていく相対速度と近づく相対速度の比を測った。固く巻いた毛糸の球では約 5 : 9、鋼の球もほぼ同じ、コルクは少し小さく、ガラスの球では約 15 : 16 だった。同じ注釈で、レン、ウォリス、ホイヘンスがそれぞれ硬い物体の衝突の規則を定めたことにも触れている。

2 つの凸な物体の距離を反復で求める GJK 法は、ギルバート、ジョンソン、キールティの 3 人が 1988 年にロボット工学の雑誌に発表した。1995 年の I-COLLIDE は、たくさんの物体の組を並べ替えで速く絞り込む方法を、1996 年の OBBTree は、向きのついた箱を木にまとめ、直方体どうしを 15 本の分離軸で判定する方法を示した。カーネギーメロン大学のデビッド・バラフが 1997 年に SIGGRAPH の講座のためにまとめたノートは、衝突の時刻を二分法で絞り込み、上の手順 7 の力積で速度を変える手順を、プログラムつきで示している。

すり抜けへの備えは、いまも物理エンジンごとに違う。JavaScript の物理エンジン Matter.js の作者は 2014 年 2 月、自分のリポジトリに「物体が壁を通り抜けるのを防ぐ(連続的な判定を実装する)」という課題を立てた。2026 年 10 月の時点でも、この課題は開いたままである。作者は 2022 年に、速い物体や薄い物体にはサブステップがいちばん簡単な対策だと書き、2024 年 6 月の版 0.20.0 で、固定の刻みで進める Runner を加えた。

使いどころ

実務での使いどころ

まず数字で確かめる。 ゲームの中で最も速い物体の速さ $v_{m a x}$ に物理の刻み $Δ t$ を掛け、最も小さい物体の半径 $r$ と最も薄い壁の厚さ $w$ から求めた $r + w /2$ と比べる。 $v_{m a x} Δ t$ のほうが短ければ、離散的な判定でも抜けない。長ければ、次の手を組み合わせる。

壁を厚くする。見た目は薄いままでも、当たり判定の形だけを厚くすればよい。
刻みを細かくする。 $Δ t$ を小さくするか、1 コマを何回かに分けて、そのたびに位置を進めて重なりを調べ直す。Matter.js の作者が速い物体や薄い物体に勧めるサブステップはこの形で、計算の量は回数に比例して増える。なお、Box2D v3 の「サブステップ」(文書の勧めは 4 回)は、重なりの判定は 1 コマに 1 回のままで、そのあとの速度と位置の計算だけを細かく分ける。接触やジョイントの計算を正確にするためのもので、すり抜けは次の連続的な判定で防いでいる。
速い物体だけ連続的な判定にする。Box2D は、動く物体が止まっている物体(地面や壁)を通り抜けないよう、既定で連続的な判定を使う。古い位置から新しい位置まで形を掃引し、最初に触れる時刻(TOI)を求め、コマの終わりにその時刻の位置まで戻す。動く物体どうしには、計算を軽く保つため既定では使わない。速い弾を bullet(弾)に設定すると、動く物体どうしでも連続的な判定をする(弾どうしは除く)。文書は、この設定を控えめに使うよう勧めている。
非常に速い弾は、物体として動かさず、光線を飛ばして最初に当たる場所を求める(レイキャスト)。

反発係数の扱い。 反発係数は 0 から 1 の間に置く。Box2D は既定で 2 つの形の反発係数の大きいほうを使うので、よく跳ねるボールは跳ねない床の上でもよく跳ねる。また、ぶつかる速さが小さいときは跳ね返りを入れない。小さな跳ね返りが続いて物体が床の上で震えるのを防ぐためで、v3 の既定ではこのしきい値が秒速 1 m である。床に食い込んだ物体を床の上へ戻すだけの処理は、エネルギーを増やしたり減らしたりする。積分の方法との組み合わせで結果が変わる例は、オイラー法とルンゲ=クッタ法で計算した。

確かめ方。 最も速い速さで、壁に向けて撃つ位置を少しずつずらしながら何百回も撃つ試験を作る。このページのシミュレーションと同じ形で、抜けた回数が 0 になるまで、壁の厚さか刻みか判定の方法を変える。ビー玉のレースやガルトンボードのように、たくさんの玉が細い釘やレールにぶつかる場面では、玉が最も速くなる下のほうで確かめる。

縦の動画で見る。 ラボのビー玉のレースは、Matter.js で 8 つの玉を板の上に転がした。動画の 1 コマ(1/30 秒)のあいだに物理を 4 回進めていて、刻みは $Δ t = 1/120$ 秒である。上の「刻みを細かくする」の形にあたる。

ビー玉レース 1着はどれ？(Matter.js・乱数の種 75)声 VOICEVOX:玄野武宏・効果音と音楽は合成音

次にやること。 自分のゲームの最も速い物体と最も薄い壁について、 $v Δ t$ と $r + w /2$ を表にしておく。円と円の衝突の時刻を手順 6 の二次方程式で求める関数を書き、2 つの円をすれ違わせたり正面からぶつけたりして、判別式と解の符号の扱いを確かめる。

参考文献

E. Catto, Box2D documentation "Simulation"・"Collision"(box2d.org)と、ソースコード v3 の src/distance.c・src/manifold.c・src/types.c、v2.4.1 の b2_dynamic_tree.h・b2_time_of_impact.h
Matter.js, GitHub issue #5 "Prevent object passing through walls / tunneling (implement CCD)"(2014 年 2 月 27 日)、CHANGELOG 0.20.0(2024 年 6 月 23 日)、ソースコード src/collision/Detector.js・Collision.js
E. G. Gilbert, D. W. Johnson, S. S. Keerthi, "A fast procedure for computing the distance between complex objects in three-dimensional space", IEEE Journal of Robotics and Automation 4 (1988), 193-203.
J. D. Cohen, M. C. Lin, D. Manocha, M. Ponamgi, "I-COLLIDE: An Interactive and Exact Collision Detection System for Large-Scale Environments", Proceedings of the 1995 Symposium on Interactive 3D Graphics, 189-196.
S. Gottschalk, M. C. Lin, D. Manocha, "OBBTree: A Hierarchical Structure for Rapid Interference Detection", Proceedings of SIGGRAPH 96 (1996).
D. Baraff, "An Introduction to Physically Based Modeling: Rigid Body Simulation II, Nonpenetration Constraints", SIGGRAPH Course Notes (1997).
I. Newton, Philosophiae Naturalis Principia Mathematica, London, 1687, Axioms, or Laws of Motion, Scholium(A. Motte 訳 The Mathematical Principles of Natural Philosophy, 1729)