Augustです. 今回の記事も僕の学習記録として書いてる. アドカレ2025の最初の記事でもある.

早速始めよう. (この記事2万文字+動画かなりあり, 時間かかります)

起因

Godotを使って正式的にGame Programming入門した僕は, Unityを使う時常にやろうとすることは, 「これRigidBodyいらなくない? Colliderだけでいけるやろ, 部品一つ減るし」という考え.

実際にこの考えを, テストせずに無責任ながら他人に勧めたことがあって, 戻って考えば, あまり良くないと思う. これUnityのUXにも責任あると考える だって, 「Staticオブジェクトの移動は避けるべき」という警告も出ないし, なんなら何もなかった. そもそもRB2D.Type = Staticと, RBない物体と何が違うんのもわからない.

「何でRigidBody最低でも片方が着いてないと衝突・トリガー判定でない?」
「直接座標弄ってるのに, 何で敢えてRBつけないといけない?」
「そもそも何が違うんだ?」

という問いにある.

「RBつければいい問題に何でそこまでする必要がある?」って思う人も少なくないかもしれないが,

「解明しないと使うたび気に障る」としか言い返せない.

この記事は, まず物理エンジンがやってることから調べ, 最後に, 「跳ね返りなどしない飛び道具に, RBつけるのか?」という疑問を実際にProfiler使って実証しようとし, その結論について解釈つけようと考える.

自作物理エンジンで衝突判定の原理を0から探ってみよう

ここで, 描画用で, Processing(情報理工学部生なら1回生のとき使ってたはず) という描画ライブラリーで
自作簡易物理エンジン作ってみよう

そもそもゲームオブジェクトってどうやって移動する?

まず「ゲームオブジェクト」や「ゲームエンジン」という概念を捨てて, 単純に「点」から考え始めよう.

ここで, 点をA(0,0) からB(1,0) へ移動させ, 1秒ジャストで辿り着けさせる.

点が移動できる回数を10と設定したら, ジャスト1秒でジャスト1単位移動するには, 毎回0.1単位動けばいい

点の移動軌跡はこう見える.

「ジャスト1秒でジャスト1単位移動する」という表現が曲がりくどいので, 「V=1/s」ならわかりやすくなる.
「移動できる回数を10」 => フレームレート = 10 という意味する.

60FPSならこうなる.

Tunnelling (すり抜け, トンネル効果)

今の時代のゲームでは, 描画FPSが60や120, 144やそれ以上行く場合は少なくないが, 負荷を考え, 物理演算FPSは60以上いく場合は少ない.

これ自体はしょうがないが, 処理しないと, いくつか問題が生じる場合がある.
例えば, 移動速度が非常に高い場合, 毎フレームが移動する距離も長くなり, これにより,

薄い壁などを完全にすり抜ける場合が可能となる. これは, Tunnellingと呼ばれる.

僕の初めて作ったゲームにもTunnellingが発生していた.

この問題はどう解決する? そもそもゲームエンジンにおいての物理エンジンって, どういうことをやってる?

まず, 僕が作った簡易自作物理エンジンを使って徐々に調べよう.

簡易シミュレーション(Discrete, 離散的)

では, Processingを始めよう.

下準備とオブジェクト定義

まず壁となる四角を定義する

class Rectangle {
  float x, y, w, h;
  Rectangle(float x, float y, float w, float h) { this.x = x; this.y = y; this.w = w; this.h = h; }
}

次はゲームオブジェクトとなる円形

class Particle {
  PVector pos, vel;
  float r, mass;
  
  Particle(float x, float y, float r) {
    pos = new PVector(x, y);
    vel = PVector.random2D().mult(random(MAX_SPEED * 0.5, MAX_SPEED));
    this.r = r; 
    this.mass = r;
  }

  void move(float dt) {
    pos.x += vel.x * dt;
    pos.y += vel.y * dt;
  }

ベクトルとして 位置pos, 速度vel, floatとして半径r, 質量massを定義する.
物体の移動速度, 半径は範囲内のランダムにする. 質量は半径と等しいとする.

物体は摩擦による減速は受けない. 移動する距離と方向は, 速度と等しい.
ここで, dtはdeltaTime (今回のフレームと前回との時間差, こうすることで, 物体の移動速度は現実時間単位となる)

衝突定義と計算(Naive)

ここで, 一番…愚直なやり方で衝突を作ろう

全てのゲームオブジェクト(Particle)において

まず, 壁と衝突しているかを確認する

void checkBoundary(Rectangle b) {
    if (pos.x < b.x + r) { pos.x = b.x + r; vel.x *= -1; }
    else if (pos.x > b.x + b.w - r) { pos.x = b.x + b.w - r; vel.x *= -1; }
    if (pos.y < b.y + r) { pos.y = b.y + r; vel.y *= -1; }
    else if (pos.y > b.y + b.h - r) { pos.y = b.y + b.h - r; vel.y *= -1; }
  }

簡単に説明すると, 上下左右の壁の位置+半径がオブジェクトの中心位置と比較し, 方向を逆転するか否かを確認する.

次に, オブジェクトどうしの衝突判定をチェックする.

void checkCollisionsNaive() {
  int count = particles.size();
  for (int i = 0; i < count; i++) {
    Particle a = particles.get(i);
    for (int j = i + 1; j < count; j++) {
      resolvePair(a, particles.get(j));
    }
  }
}

(P1, P2) -> (P1,P3) -> (P1, P4)… (P2,P3)->(P2,P4)->(P2,P5)… の順で

void resolvePair(Particle a, Particle b) {
  float dx = b.pos.x - a.pos.x;
  float dy = b.pos.y - a.pos.y;

  float distSq = dx*dx + dy*dy;
  float minDist = a.r + b.r;

  bool isColliding = distSq < (minDist * minDist)    // <- 距離^2が最短距離(両方半径の和)^2より短い?

衝突があったら, ここでまず前回の移動で重なり合った部分を静的に補完して被りを解く.
その後, 弾性衝突の物理式と運動量保存則で衝突後各オブジェクトが移動する方向と速度を計算する

if (distSq < minDist * minDist) {
    float distance = sqrt(distSq);
    if (distance == 0) return;
    
    float nx = dx / distance;
    float ny = dy / distance;
    float overlap = minDist - distance;
    
    // Static separation
    float correction = overlap * 0.5;
    a.pos.x -= nx * correction;
    a.pos.y -= ny * correction;
    b.pos.x += nx * correction;
    b.pos.y += ny * correction;
    
    // Dynamic bounce
    float rvx = b.vel.x - a.vel.x;
    float rvy = b.vel.y - a.vel.y;
    float vNormal = rvx * nx + rvy * ny;
    
    if (vNormal < 0) {
      float j = -2.0 * vNormal;
      j /= (1/a.mass + 1/b.mass);
      float ix = j * nx;
      float iy = j * ny;
      a.vel.x -= ix * (1/a.mass);
      a.vel.y -= iy * (1/a.mass);
      b.vel.x += ix * (1/b.mass);
      b.vel.y += iy * (1/b.mass);
    }
  }

上の式はDynamicなオブジェクトしか関係する. Triggerなら, ただここで”衝突した”という信号を出せばいい.


まぁ…いった通り, 愚直である

何故かというと, 計算する量が爆発するから.

ここで, もしオブジェクト

• 5個：5*4/2 = 10回
• 100個：4950回
• 1000個：499,500回(～50万)
• 5000個：12,497,500回 (～1250万)

毎フレーム. つまり60FPSならこれを毎秒60回計算する必要がある.

まぁ, 僕のノートパソコンで実際に計算させてみよう
(描画はOpenGLでGPUに任せているのでCPU負荷は～計算のみ)

まずは円形一個と壁だけ

なんの変哲もない, ただのボール

次は円形5個

円形100個ならどうなる?

まぁ, まだ60FPS保てる

円形1000個

毎秒50万回衝突演算をしてなお60FPS維持できる. まぁ, 現代のCPUはすごい

円形5000個

流石に毎秒60*1250万回計算は無理だな. FPSは~10しか維持できない.

円形以外の場合

円形は割と一番計算しやすい. 他の形の場合は更にひどくなる. ここではdemoしないが, 言おうとしていることは既にはっきりしている.

要は

考えば, そこまで計算しなくても良くないか?

そもそも, 何故全てのオブジェクトにおいてチェックしている?

void checkCollisionsNaive() {
  int count = particles.size();
  for (int i = 0; i < count; i++) {
    Particle a = particles.get(i);
    for (int j = i + 1; j < count; j++) {    //<----- 全部にする意味なくねぇ?
      resolvePair(a, particles.get(j));
    }
  }
}

実際に計算しているものは

void resolvePair(Particle a, Particle b) {
  float dx = b.pos.x - a.pos.x;
  float dy = b.pos.y - a.pos.y;

  float distSq = dx*dx + dy*dy;
  float minDist = a.r + b.r;

  bool isColliding = distSq < (minDist * minDist)    // <- 距離^2が最短距離(両方半径の和)^2より短い?

これ, 要は自分以外全てのオブジェクトとの距離を計算している

でも, 例えばこの図の例. これ, 遠方の物体は「見れば衝突してないやろう, 計算する必要ねぇ」って思わない?

じゃぁ, 「どうやって比較する対象の量を縮む?」

Spatial Partitioning(空間分割)で改良してみよう

Spatial Partitioning, 要は, 一つの空間を, 複数個小さい空間に分けて考える手法. 例えば, マインクラフトをプレイしたことのある人ならわかるかもしれないが, 世界を, 2次元のChunkとして分割して, Chunkも, Blockとして分割することができる.

Broad-Phase Collision Detectionの考え

ここで, 我々のオブジェクトが存在する空間を, Cellに分割して, その一個一個小さい空間の中に, オブジェがいるか否かから, 距離を比較する対象を激減することができる.
設定により,
1. 自分が存在する空間の中のメンバーどうしと比べる.
2. 隣接するCellがもしオブジェクトが存在するなら, それも調べる
これ以外は, 衝突する可能性がないとして, 無視.

この過程は, 物理・ゲームエンジンでは, Broad-Phase Collision Detectionと呼ぶ.

直近のセクションで述べた距離の計算, resolvePairの関数は,
Narrow-Phase Collision Detectionと呼ばれ, 今回記載したのは, そのうちの一種である.


この手法ので改良した計算量は, O(N*M),
Nはオブジェクト数で, MはCell平均オブジェクト数.

改良前のO(N^2)より遥かましになっている.

まずは等分割空間(Uniform Grid)

等分割, いわばGridにする.

強力だとわかるので, まず1万個入れよう.

(本当は余裕で60FPS維持するけど, 録画ソフトで多少落ちてる)

限界知りたいので, 10FPSになるまで試してみよう(7万2千個)

(目が…)

次はQuadTree

実際に等分割より, 更に改良する余地存在する.

QuadTree (2D, 3Dは Octreeという, 考えは一緒) という概念を説明しよう

これなにやってるかというと, 等分割を更に等分割しているだけ.

これは等分割空間の何を改良しているかというと,

例えば巨大な空間が存在する (100×100).
しかし，最小オブジェクトの半径が非常に小さい (0.1) とする.
このオブジェクト同士の衝突を「見落とさない」ためには，
理想的にはグリッドサイズを直径~0.2 前後に設定したくなる.

空間サイズ: 100
グリッドサイズ: 0.2
→ 1軸あたりのセル数: 100 / 0.2 = 500
→ 総セル数: 500 × 500 = 250,000セル

ここで問題になるのは：
ほとんどのセルが空になる可能性が高い
オブジェクトが密集しているのは空間のごく一部なのに，
等分割グリッドは空っぽのセルにもメモリと管理コストを割く.

セル配列そのもののサイズ 毎フレーム「全セルをクリア」「再度挿入」といった更新コスト

解像度を上げたい領域だけ細かくする，ということができない
一部だけ高解像度にしたいのに，等分割だと「全部まとめて細かくする」しか手段がない.

そこでクワッドツリー（あるいは一般の階層空間分割）の改良点はこういうところにある：
必要な場所だけ細かく割る 何もない広い領域 → 大きな1セルのまま
オブジェクトが密集している領域 → その領域だけ再帰的に subdivide して細かいセルにする

結果として：
有効に使われる“葉ノード”の数はオブジェクトの分布にだいたい比例 「空のセルの山」を延々と管理する必要が減る

実装：理屈は通るけど, 現実は違う

この構造の実装は…正直この記事ではあまり意味ない. 何故かというと, 「限界までオブジェを入れるから, 空のCellは少ない」から. 要は, このようなシミュレーション環境ではなく, 実世界や実ゲーム世界しかパフォーマンス改良できない.

更に, このシミュレーションにおいて, QuadTreeの計算コストは, 本当は等分割空間より高い.
これは, 木構造の定番で, 探索・差し入れコストが, O(logN) である. それと比べ, Gridは, O(1) で軽いからである.

でも, 一応作りたくないわけではないので作った

およそ4万2千個で10FPSまで下がった.

結果通り, (このシチュエーションにおいて) パフォーマンスは落ちている.

何故かというと, オブジェが1mmでも分割線を超える場合, 木全体を再構築する必要があり, これが(比較的に)重いから.

オブジェクト分割

まさに上に述べた(再構築コストなど)の理由で, 実際にゲームや物理エンジンにおいて, Quadtree/Octree は使われていない.

ここで一度これまでの方法の欠点を整理しよう：

• Naive: Broad-Phaseが存在しない. 論外
• Uniform Grid(等分割空間): 物体の配置が均一じゃない場合, 無駄にチェックするスペース多い
• Quad/Octree: 一個でも境界線超えたら再構築する必要があり, 探索コストが比較的に高い
• 空間分割全体： 境界線に立つオブジェは処理しないと同時に複数Cellに存在するになる. 動くたび, Cellの切り替えが発生する.

ここから行うのは, 根本的に違う考え方になる(調べないと自分では全くこの方向に向けて考えなたった).
「空間で分割するのではなく, オブジェクトで分割すればよくないか?」

Bounding Volume Hierarchy(BVH) (ゲーム・物理エンジン業界主流)

まずはビジュアルで探索・構築過程を見てみよう

ざっと言えば, 物体の分布の中位に分けて, それをAABB(Axis Alighed Bounding Box)で囲む. これをできなくなるまで続く.

空間分割の問題：物体の分布が空間的に均等じゃない場合, 木の重心も傾くので, 探索が遅くなる.
BVHなら： 物体の分布の中位に分けているため, 二分木の重心は安定なため, 探索が早い(毎ステップ目標までの距離半分縮める)


上のビジュアルは, BVHの最も基礎的な形に過ぎない. 実際にこれを見て, 「再構築のコストが高い」とわかる.

ゲーム・物理エンジンが行うBVHの最適化

まず, 共通アプローチとして:
1. Margin Padding: ちょっとだけの移動なら許す. 再ビルドしない. これはビルドコストを回避(Old School)でき, 安定さを増す.

2. Static(地形や障害物など)とDynamicを双生世界として管理し, Dynamic層の衝突判定はDynamic対Static, Dynamic対Dynamicに分けて二回行う. Static層は一般的(Unity編で重要となる)に再ビルドしない

3. 仮眠待機: 数秒間動かなかった物体は仮眠状態に入らせ, 再ビルドしない

次に, Dynamic層においてPhysXなど従来ののエンジンは, 再ビルドしないように更に:
1. AABBの拡大： 欠点は空きスペースによる空間肥大化
2. 重なりが多すぎる場合：木の回転(ノードの交換)
3. テレポート・高速移動する物体に対して, ノードを削除して再挿入を行う
などを行う. 基本的に, 再ビルドをコードで実行させない限り, 自発的木の再ビルドは発生しないらしい

メモリレイアウトの最適化 (Cache Locality)

JoltやUE5 Chaosのような現代物理エンジンにおける最大の発明は,

「遅いのは計算ではなく, CPUメモリへのアクセス方法, だから, Cacheでなんとかする」という手法だと思われる.

従来のポインタベースのツリー構造（Nodeがメモリ上にバラバラに散らばる）では, 探索のたびにCache Missが発生し, CPUがメモリ読み込み待ちで止まってしまう.

これを防ぐため、モダンなエンジンは木構造を線形な配列（Linear Array / Contiguous Memory）として管理する. 「親ノードのすぐ隣に子ノードのデータがある」状態を作ることで, CPUキャッシュにヒットしやすくし, 爆発的な高速化を実現している.
(流石に僕の手に余るので, 詳細は3次元座標をintに変換する手法である「Morton Code / Z-order Curve」や, 「Radix Sort」などで検索. )

結論：

ユーザー（開発者）視点で言えば, もし選択の余地がある(Godot4+など)なら迷わず Jolt Physics を選ぶべきだと考える. 枯れた技術の安定性と, 最新のメモリアクセス最適化の両方を備えている.

Sweep and Prune (SAP): かつての王者

なんか忘れたなともったら, 旧Unityが使うBroadPhaseアルゴリズムを載るのを忘れた

(もう一度説明するが, この圧力テストはあまり意味がない. この特定条件下でのシミュレーションは, Gridは最強だが, 現実は違う)


現代の物理エンジン（Jolt, UE5 Chaos, Havok, Unity DOTS など）はこぞってBVHを採用しているが, 一昔前の物理エンジン（PhysX(Unityなど), Bullet Physics）では, Sweep and Prune (SAP) が「ブロードフェーズの業界標準」として長らく君臨していた.

このアルゴリズムは, 単純に説明すると,
物体のとある軸(例えばX)だけ見て, それを順にソートする. 重ねる物体同士だけNarrowPhaseに移行.

なぜSAPはそれほど愛されたのか, その技術的背景を紐解く.

1. なぜSAPは「最強」だったのか？

魔法の言葉：「時間的コヒーレンス (Temporal Coherence)」

SAPが覇権を握った最大の理由は, 物理シミュレーション特有の「ある性質」を完璧にハックしていたから.
それは「物体は, 1フレーム程度ではそんなに遠くへ行かない」という.

• フレーム1: 物体A (x=10.0), 物体B (x=20.0)
• フレーム2: 物体A (x=10.1), 物体B (x=20.1)

通常のソートアルゴリズム（Quick Sortなど）は O(N log N) のコストがかかる. しかし,
「ほぼ整列済みのリスト」に対して挿入ソート (Insertion Sort) をかけると,
コストは O(N) にまで下がる.

かつてのCPUにとって, 複雑な木構造を辿る（ポインタを追う＝キャッシュミス多発）BVHなどよりも,
「単純な配列を, 前から順に処理するだけ」のSAPは, メモリ効率的にも圧倒的に高速だったのだ.

2. SAPの限界と「死のシナリオ」

しかし, ゲームのワールドが広大になり, オブジェクト数が増えるにつれて, SAPの致命的な弱点が露呈し始める.

弱点①：1次元クラスタリング問題 (The 1D Clustering Problem)

SAPは通常, X軸（またはY/Z軸）のどれか1つの軸に沿って物体をソートする.
ここで「世界の全員が, ある軸上に一直線に並ぶ」という最悪のケースを想像してほしい（例：高い塔から1000個の岩が垂直落下する）.

• 全員のX座標が同じになる.
• SAPは「X軸で重なっているペア」をすべて衝突候補としてマークする.
• 結果, 実際には上下(Y軸)で離れていても, 全員が全員と衝突判定を行う O(N^2) , 実質的にBroadPhaseがもたない状態に陥る.

PhysXなどはこれを防ぐために「Multi-Box Pruning (MBP)」などのグリッドハイブリッド技術を導入して延命を図ったが, 根本的な解決にはならなかった.

クラスタリング問題の解消? Multi-Box Pruning (MBP)

「全員がX軸上で重なると死ぬ」というSAPの弱点を克服するために, PhysXなどが導入したのが Multi-Box Pruning (MBP) だ.

仕組みは単純で, 「世界をグリッドで分割し, 各グリッドの中で個別にSAPを走らせる」という.

• SAPの弱点: 縦に積まれた100個の箱は, X軸への投影が全て重なるため, 判定が O(N^2) になる.
• MBPの解決策: 空間をY軸（高さ）でも分割してしまえば, 「上の箱」と「下の箱」は別のグリッド（別のSAPリスト）に所属することになる. リストが分断されれば, 互いにチェックする必要がなくなり, 計算量は劇的に減る.

MBPの代償（Trade-off）

しかし, 空間分割の要素を取り入れたことで, Grid特有の新たな悩みが発生した.

• 境界線のまたぎ問題 (Boundary Crossing):

  グリッドの境界線上にいる物体は, 両方のグリッドのSAPリストに登録しなければならない（多重管理）. 巨大な物体がいると, 多数のグリッドに跨ってしまい, 管理コストが跳ね上がる.

• 結局「密」には勝てない:

  もし「1つのグリッド内」に大量の物体が密集してしまったら? そのグリッド内部のSAPは結局パンクする.

  
  

MBPはSAPの寿命を数年延ばしたが, 最終的には「最初からBVHでよくない? 」という時代の波（マルチコア化）に飲み込まれる.

弱点②：マルチコア化への不適合

これが現代でSAPが捨てられた決定的な理由である.
挿入ソートは「前の結果に依存する」ため, 並列化（マルチスレッド化）が極めて難しい.

現代のCPUはコア数が命.
BVHは「左の枝」と「右の枝」を別々のコアで構築・更新できるため, コア数に応じてリニアに性能が伸びる. 一方, SAPはシングルスレッド性能に依存しやすく, 時代遅れとなってしまった.

結論：なぜ今はBVHなのか

Jolt PhysicsやUE5 Chaosが採用している「毎フレームBVHを全再構築する」アプローチは, 一見無駄に見える（O(N)の維持ではなく, 毎回コストを払うため）.
しかし, 現代のハードウェア事情では, これが正解となった.

• メモリレイアウト: 現代のBVHはポインタを追わず, 一直線の配列（Linear Array）として管理されるため, SAP同様にキャッシュ効率が良い.
• 並列性: ツリー構築は爆速で並列化できる.
• 安定性: 物体がどこにどう固まろうと, ツリー構造なら計算量は安定して O(N log N) を維持できる（SAPのようなワーストケース爆発がない）.

まとめ：
SAPは「シングルコア・低メモリ帯域」時代の英雄だった. しかし, 「メニーコア・広大なオープンワールド」の現代において, その座をBVHに譲ったのである.

で, 空間/オブジェクト分割はTunnellingとなんの関係がある?

CCDでTunnellingの解消

すり抜けを回避するには, 移動の過程でスキップされた空間をチェックすればいい. そのアルゴリズムの多くは離散的ではなく, “連続的”な数学式を使うため,「Continuous Collision Detection」, CCDと呼ばれる.

CCDは, 大まかに以下の種類がある:

• Swept Volumes / Sweep (ShapeCast), UnityではContinuous(Staticオブジェに対して演算) と Continuous Dynamic (全物理オブジェに対して演算)
• Speculative CCD, UnityではContinuous Speculative
• RayCast(あまり使わないがShapeCastの基礎)
• 数理計算(使わない)

Raycast:

数式

数学的に線を定義しよう：

Raycastは無限の長さを持たないから, ここでvを終点と始点の差として表す.

次に数式で平面を定義しよう：

ここで,
A は平面のアンカーポイント
P は調べたい任意のポイント
n は平面のノーマルベクトル

我々が調べたいのは平面と被るかどうかだから, d = 0のときしか興味はない.
つまり, どの時間tにおいて, 直線の点Pがこの平面と重ねる(d = 0)か, だ.

線の式を導入すると：

tを左に置くとこうなる：

ゲームエンジンが行う計算最適化(一部)

まず, v(線の方向) と n(平面のノーマル)が直交する場合, 除算できないし, 接触することもないため, その場で計算終了.

次に, RayCastの長さは無限ではないため,

このように場合分ける.







(もうスキップしなくていい, 数式はここで終わり)

よくある疑問

ここで, 「そもそも平面Aはどうやって知る? Raycastはただただ線を出してるだけで, 比較対象など知らないし, 知らせない方がいいのでは?」という疑問をもつ人(例えば自分)もいるかも知れない.

BVHによるRaycasting

「総当たり」から「枝切り」へ

光線を飛ばして何かに当たるか調べる際, シーン内の全てのポリゴンと交差判定を行うのは現実的ではない. ここでBVHが輝く.

アルゴリズムは単純な再帰（あるいはスタック処理）:

1. ルートAABBの判定： まず, 世界全体を囲むルートNodeのAABBとRayが交差するか調べる.
   → Noなら：その時点で終了. シーン内の何にも当たらない.
   → Yesなら：子ノードへ進む.
2. 再帰的な枝切り (Culling)：
   子NodeのAABBに対して判定を行う:
   もしRayが「左の枝のAABB」にかすりもしなければ,
   その先に何千個の物体があろうと, 左の枝はすべて無視（Cull）していい.
   右の枝だけを探索すれば良いことになる.
3. リーフ（葉）ノードでの本判定：
   最終的に「末端（Leaf）」である実際の物体（コライダー）に到達した場合のみ,
   重い形状同士の交差判定(Narrow Phase Collision Detection)を行う.

つまり, BVHにおけるレイキャストとは, 「当たらない可能性が高い広大な空間を, 低コストなAABB判定で即座に切り捨てるゲーム」と言える.

よくある疑問(その2)

僕がこれを勉強する時がもつもう一つの疑問は, 「物体の大きさによって, Raycast一個では足りないなら, 数個使えばカバーできるのでは?」
これに関して, こういった事例を考えよう：

Raycastは比較的にやすいとはいえ, 複数個追加しても, Tunnellingの確率を下げるだけである.

例えると, フォークを使ってスープを食べようとしても, 液体をすり抜けさせないためにはフォークの…フォークの本数? を増やせばいいけれど, どれだけ増やせたらスプーンの安定さに比べられるようになる? そもそもその時, まだフォークって言えるのか? 実質的にただただ質の悪い・過剰に複雑なスプーンに見えなくもなかろう.

で, そのスプーンが, これから紹介するShapeCastである.

ShapeCast

Shape Castは, 衝突判定の”Gold Standard”とも言われる. その理由は, 比較的に安いコストで 100%Tunnelling解消できるからである.

脳内イメージとしては, まぁ…図の通り, 点線ではなく, 形(例えば半径rの円)を伸びて衝突を検知するという

しかし, ここに大きな問題がある. 点ではなく, 形あるものを投影するのは, 非常に複雑である (形そのものが方向の異る点の集合であるため)

ここで出てくる考えは, 「Minkowski Sum」と呼ばれる.
数式自体は紹介しないが, 考え方として,

ShapeCastするShape(Sphere形)を, 点まで圧縮して,
その分, 比較する対象の形を, 等感覚に拡大させる.

ではなく, こう

ここで,B⊕(−A) = Minkowski sum, Aの形分拡大したBで, Bは静止コライダーである.

省略したものが多いが, こうしたことで, 解くべき数式が, こうなる.

(ここのAはRaycast時と同じく, 平面のアンカーポイントになってる)

(SphereCastした形はキャプセル)

その他の形の場合

円ではなく, 例えばキャプセルやBoxなどのPrimitiveな形もCast可能であり, 複雑な形(Convex Hull)でもCast可能であるが, コストがかなり高くなる.

非常に雑な比べになるが, 大まかに言うと
Raycastのコストを1にすると
現代ゲームエンジンが使う物理エンジン(Jolt, PhysXなど)の最適化下で,
Sphere ≈ 1.5~2
Capsule ≈ 2~3
Box ≈ 3~6 (角度や回転に影響される. 興味ある人は「Separating Axis Theorem」について調べて)
Convex ≈ 10~30+ (形による,数学的に解けないからループや数値解析で回す必要ある)

数値が厳密的正しくないかもしれないが, 関係性が見えてくる.

ShapeCastのコストが高くなるもう一つの理由

※注釈：このデモは極端な例である.
視覚的なわかりやすさを優先し, 狭い2D平面に物体を密集させた「Worst Case」を表示している.
実際のゲーム空間（特に3D）はもっと空間的余裕があるため, 通常ここまで極端な性能差にはならない.
しかし, 「太ったQuery（Fat AABB）が, 本来無関係なNodeまで巻き込んでチェックしてしまう」という原理的なコスト増は変わらない

これにより, Narrow Phaseがチェックすべきオブジェクトが増える.

Speculative CCD & Speculative Contacts

もしShapeCastが「正確さのGold Standard」なら, Speculative CCDは「コストパフォーマンスのGold Standard」と言える. Jolt PhysicsやUnity (DOTS Physics) など, 現代の高性能物理エンジンの多くがこれをデフォルト, あるいは推奨設定として採用している.

「未来の衝突」を「現在の接触」にすり替える

ShapeCast（Sweep）が高価なのは, 「いつ, どこで当たったか（Time of Impact）」を正確に計算しようとするからだ.

Speculative CCDは, もっと雑で賢いアプローチを取る.

「次のフレームでぶつかりそうなら, もう『今ぶつかってる』ことにして, 反発させればよくねぇ？」

1. 物体のAABBを, 現在の速度（Velocity）に基づいて拡張（Expand）する.
2. その「太ったAABB」が壁に触れたら, まだ物体自体は届いていなくても, 「接触点（Contact Constraint）」を生成してしまう.
3. 物理Solverがその拘束を解決しようとするとき, 「めり込みを防ぐ力」が働き, 結果として物体は壁の手前で減速・停止する.

この手法の最大の利点は, 「高価な幾何学計算（Minkowski SumやGJK）」が不要で, 単なるAABBチェックと既存のSolverの仕組みだけで完結するため, 圧倒的に高速であることだ.

Speculative CCDの致命的な弱点：Stale AABB Problem

Speculative CCDは「安い・早い」が売りだが, 特定の状況下でTunneling（すり抜け）を引き起こす.
「予測しているのにすり抜ける」とはどういうことか？ その原因は「予測が更新されない（Stale）」ことにある.

物理エンジンの処理フローが生む悲劇

上の図は”https://docs.unity3d.com/6000.2/Documentation/Manual/speculative-ccd.html”Unity公式

このすり抜けは, 物理エンジンが「衝突候補を探す（Broadphase）」と「実際に衝突を解決する（Solver）」を完全に分けて処理しているために起こる.

1. 予測フェーズ (Broadphase): フレームの最初に, エンジンは全オブジェクトにこう尋ねる. 「君たち, 今の速度だと, どこまで動きそう？」 ボールは答える.「左にちょっとだけ動きます」. エンジンは「よし, じゃあ左側の小さな範囲（AABB）だけ監視対象にして, それより遠くにある壁は無視リストに入れるね」と決定する.
2. 解決フェーズ (Solver): ここで予期せぬ事態が起きる. 回転するパドルがボールを強打する. ボールの速度は「左に1」から「右に100」へと激変する.
3. すり抜けの発生: ボールは猛スピードで右へ飛んでいき, 遠くの壁に到達する. しかし, エンジンはその壁を既に「無視リスト」に入れてしまっている. 「えっ, 速度変わったの？ でももうBroadphase終わっちゃったし, 今更リスト作り直すと重いから…今回はそのまま通っていいよ」 これがSpeculative CCDにおけるすり抜けの正体だ.

これを防ぐには, 速度が変わるたびにAABBを作り直す（Re-broadphase）必要があるが, それはパフォーマンス的に現実的ではない. したがって, 「予測不可能な超加速」が起きるゲーム（ピンボールや格闘ゲームなど）では, Speculative CCDは信頼できないということになる.

Speculative CCDのもう一つの副作用：Ghost Collision（幽霊衝突）

「雑」な判定には代償がある.

拡張されたAABBは単なる箱（Box）なので, 回転する物体や, 角（Corner）の近くを通る物体に対して,
「本当は当たらないのに, 当たったと判定される」現象が起きる.

これをGhost Collisionと呼ぶ. 以下のデモでその仕組みを見てみよう.

JoltなどはどうやってGhost Collisionを防ぐのか？ (Speculative Contacts)

前述の通り, Unityなどが提供する単純なSpeculative CCDは, 膨張させたAABBに触れた瞬間に「衝突」とみなして停止させるため, 空中で止まってしまう（Ghost Collision）.
一方で, Jolt PhysicsやBox2D v3が採用するSpeculative Contactsは, 以下のロジックでこれを解決している.

「今止める」のではなく「到着させる」

最大の違いは, Solverが「隙間」をどう扱うかにある.

• Naive Speculative (Unity等):
  「膨張したバリアに触れた！ 危険だ, 今すぐ止まれ！」
  → 結果：壁の手前で停止する.
• Speculative Contacts (Joltなど):
  「膨張した枠には入ったが, 実際の壁まではまだ距離があるな.
  よし, フレームの終了時にちょうど壁にタッチする速度に調整しておこう. 」
  → 結果：物体は隙間を通り抜け, 壁にピタリと着地する.

Joltは, Broadphase（大まかな判定）では「太ったAABB」を使うが, Solver（最終解決）の段階では「実際の形状（Sphereなど）との距離」を正確に計算し, その距離を埋めるための速度制御（拘束条件）を行う.
これにより, Ghost Collisionを排除しつつ, 高速なトンネル抜け防止を実現している.

採用している物理エンジン

この「第3世代」とも言える洗練された手法を採用しているのは, 主に以下のモダンなエンジンである.

• Jolt Physics (Godot 4+ の標準アドオン)
• Box2D v3 (2D物理のデファクトスタンダード最新版)
• Havok Physics (ゼルダの伝説 BotW / 多くのAAAタイトル)

数値解析(ただの例)

画像ソース：https://www.youtube.com/watch?v=eED4bSkYCB8, 英語だが非常に助かる動画
この例は共通解がないから解析以外当てにならないのでスキップ.

結論: 結局いつ何を使えばいい?

Discrete: 一番安い. 薄い壁+高速に移動する物体が存在しないや, たまに問題出ても気にしない(大半のゲーム) なら大丈夫, .
Continuous：弾丸だど, 高速に移動するがDynamicオブジェクトに物理的効果与えない, 壁などの静的障害物とだけ衝突するオブジェクトに
Continuous Dynamic: 一番正しくが, 高速回転する(Angular Velocityが高い)オブジェクトにはたまに問題がある
Continuous Speculative: Continuousの中では軽い, 回転に対応する. 問題はGhost Collision(Unity)や処理流れによるStale AABB.

つまり「完璧」という完璧な解決方法はないが, 正直これが問題になるようなゲームは, そもそもこの記事の範囲外でもある.

Unity Colliderトラブルシューティング

さて, ここまで物理エンジンの裏側（Broadphase, CCD, SAPなど）を調べてきた. これらを理解した今なら, Unityで頻発する「謎の衝突判定トラブル」の真の原因が見えてくるはずだ. 実際にトラブルシューティングに入ろう.

なぜUnityでは衝突判定にRigidBodyが必要なのか?

Unity初心者（あるいは中級者でも）が必ず一度はハマる罠がある.

「Colliderをつけたのに, OnCollisionEnter が呼ばれない！」

そして公式ドキュメントやフォーラムはこう答える. 「片方にRigidBodyをつけなさい」と.

なぜか？ それは物理エンジン（PhysX）に対して「私はStatic（静的）ではない, Dynamic（動的）な物体だ！」というIDカードを提示するためである.

RigidBodyがなかったら何が起こる?

Unityにおいて, RigidBodyコンポーネントを持たないColliderは, 自動的に「Static Collider（静的コライダー）」として扱われる.
つまり, 地面や壁, 家と同じ扱いになる.

前章の「Broadphase」の話を思い出してほしい. 物理エンジンは最適化のために「Staticな物体」と「Dynamicな物体」を別々の管理構造（ツリーやリスト）に入れている.

• Static Collider同士は衝突しない:

  地面と家が衝突判定をする必要はない. だから物理エンジンは, 最適化として「Staticグループ同士の衝突チェックを最初から放棄（Sleep）」している. RigidBodyがない物体同士をぶつけてもイベントが起きないのは, エンジンが「動かない壁同士がぶつかるわけない」と決めてかかっているからだ.

• 動かすとペナルティが発生する:

  RigidBodyがない物体を transform.position で無理やり動かすと, エンジンはパニックを起こす.「おい！ 不変であるはずのStaticツリーの構造が変わったぞ！」これにより, ツリー全体の再構築（Rebuild）が発生し, 巨大なスパイク（処理落ち）を引き起こす.

これが本当はコンソールに警告 “Static Collider Should Not Be Moved” などが出るはずなのに, 何故かUnityではそれがないのだ

では何故その警告がない? そもそもパフォーマンスはどう違う?

実際にテストして, 何故かKinematicBodyより, Static (RBなし)の方が遥かに(2～10倍以上)パフォーマンス高い

このシミュレーションは, Staticで移動しない物体2万個と, Static / Kinematic切り替えて移動する物体1個という設定で実行している

上の図はStaticの場合で, 下はKinematic RBつけた場合.

これは非常におかしい. 原理上, Static層の木の再構築は, 必ずコストが出るはず

つまり, そうなる結果から, 「木が再構築されていない」としか考えられない.

Moving Static Colliders will be a lot less expensive. A Static Collider is just a gameobject with a collider component on it, but without a Rigidbody component. Previously, since the SDK assumed that Static Colliders aren’t moved, moving a Static Collider would trigger an expensive AABB tree rebuild that affected overall performance badly.

In Unity 5, we’ll use the same data structure to handle the movement of both dynamic and static colliders. Unfortunately, we’ll lose the benefit of Static Colliders consuming less memory than dynamic ones. However, right now, the cost associated with moving Static Colliders is one of the top 3 causes of performance issues in Unity games. We wanted to change that.

https://unity.com/blog/2014/07/08/high-performance-physics-in-unity-5, 現代はアクセスできない.

これは, 2014年UnityがPhysX2.8から3+に移行する時発表した記事で,
要はStatic / Dynamicを双生世界で管理すると, 性能は高いが, Staticオブジェを移動しTreeの再構築を発生させる人があまりにも多すぎて, StaticをDynamicと同様に管理する仕組み(単一世界)に替えて, 一つのレイヤーで如何にうまく最適化することに注意改変した.

このような結論から考えば,
飛び道具など, 全く物理インタラクションしないオブジェは, 別にStatic, つまり, RigidBodyつけなくてもいいのでは? と考える.

物体が物理層でどう定義されるか

Unityにおけるコンポーネントの組み合わせと, 物理エンジン内部での扱いは以下の表のようになる.

物理相互作用以外, 種類によって, デフォルトで衝突判定しないタイプ種類同士が存在する. これは, 公式”https://docs.unity3d.com/6000.2/Documentation/Manual/collider-types-interaction.html”を参考しよう.

実際にProject Settingにはいて, 各自弄ることも可能.

Staticのオブジェは, 木は再構築しなくても, 移動自体は位置を直接触って実行しているため, 実質的に「テレポート」している. そのため, 物理相互作用は発生しない(RBないから当然)
つまり, 「動く床」や「開くドア」を作りたい場合, 自動物理演算は不要だとしても, RigidBodyをつけて IsKinematic = true にした方がいい.

他のエンジンはどうなっている?

Unityのこの仕様は「コンポーネント指向」の弊害とも言える. 「Colliderさえつければ当たり判定が出る」という手軽さの裏に, Static/Dynamicの暗黙的なルールが隠されているからだ.

他のエンジンでは, これをもっと「強制的（Explicit）」に管理していることが多い.
とはいえ, 同じユーザーによる誤作動が発生(Documentationの質によって多少改善しているが), 多少のStaticの移動は許される.

まとめ

随分長い記事になったが, 一応現代エンジンが使う手法の雑な説明は行ったと思う.

自分も帰て「結果なにが言いたいねん?」とおもったけど…
まぁ, 自分が「だた物理エンジンについて調べたい, ついでに考えや過程を整理したく, 記事としてまとめた」ぐらいかもしれない.

少なくても, これを機に, (もしまたUnityを使わなければならない時期が来たら)RigidBodyをつける時に, もう気に障ることは感じないと思う.