はじめに
現在、私は C++ のアルゴリズムインターンとして働いており、日々さまざまな空間データ構造やアルゴリズムの最適化に取り組んでいます。そのなかでも特に実用的で学びが多かったのが AABB ツリー（Axis-Aligned Bounding Box Tree） です。
本記事では、AABB ツリーのアルゴリズムの仕組みをゼロから解説し、どんな場面でメリットがあるのかをまとめます。
AABB とは？
AABB（Axis-Aligned Bounding Box） とは、各軸に平行な辺を持つ直方体（2D なら矩形）で、オブジェクトをすっぽり囲む最小のボックスのことです。
┌──────────┐
│ ／＼ │ ← オブジェクト（任意の形状）
│ ／ ＼ │
│／ ＼│
└──────────┘ ← AABB（軸に平行な矩形で囲む）
AABB の特徴は以下の通りです。
- 2 つの点（
minとmax）だけで表現できる - 重なり判定が非常に高速（各軸の区間比較のみ）
- 回転すると再計算が必要になるが、それでもシンプル
AABB ツリーとは？
AABB ツリーは、複数の AABB を 二分木（Binary Tree） の構造で階層的に管理するデータ構造です。各ノードは子ノード群を囲む AABB を保持し、リーフ（葉）ノードが実際のオブジェクトに対応します。
[Root AABB]
/ \
[AABB A] [AABB B]
/ \ / \
[Obj1] [Obj2] [Obj3] [Obj4]
ノードの構造（C++）
struct AABB {
Vec3 min;
Vec3 max;
bool overlaps(const AABB& other) const {
return (min.x <= other.max.x && max.x >= other.min.x) &&
(min.y <= other.max.y && max.y >= other.min.y) &&
(min.z <= other.max.z && max.z >= other.min.z);
}
AABB merge(const AABB& other) const {
return {
{std::min(min.x, other.min.x), std::min(min.y, other.min.y), std::min(min.z, other.min.z)},
{std::max(max.x, other.max.x), std::max(max.y, other.max.y), std::max(max.z, other.max.z)}
};
}
float surfaceArea() const {
Vec3 d = max - min;
return 2.0f * (d.x * d.y + d.y * d.z + d.z * d.x);
}
};
struct Node {
AABB aabb;
int left = -1; // 子ノードのインデックス（-1 ならリーフ）
int right = -1;
int parent = -1;
int objectId = -1; // リーフの場合のみ有効
bool isLeaf() const { return left == -1 && right == -1; }
};
AABB ツリーの主要な操作
1. 挿入（Insert）
新しいオブジェクトを挿入する際は、表面積ヒューリスティック（SAH: Surface Area Heuristic） を用いて最適な挿入位置を見つけます。SAH のアイデアは「ツリー全体の AABB の表面積の増加量が最小になる位置に挿入する」というものです。
int AABBTree::insertLeaf(int leafIndex) {
if (root == -1) {
root = leafIndex;
return leafIndex;
}
int bestSibling = root;
float bestCost = nodes[root].aabb.merge(nodes[leafIndex].aabb).surfaceArea();
std::queue<std::pair<int, float>> queue;
queue.push({root, 0.0f});
while (!queue.empty()) {
auto [current, inheritedCost] = queue.front();
queue.pop();
AABB merged = nodes[current].aabb.merge(nodes[leafIndex].aabb);
float directCost = merged.surfaceArea();
float cost = directCost + inheritedCost;
if (cost < bestCost) {
bestCost = cost;
bestSibling = current;
}
float lowerBound = nodes[leafIndex].aabb.surfaceArea() + inheritedCost
+ (directCost - nodes[current].aabb.surfaceArea());
if (lowerBound < bestCost && !nodes[current].isLeaf()) {
float newInherited = inheritedCost + directCost
- nodes[current].aabb.surfaceArea();
queue.push({nodes[current].left, newInherited});
queue.push({nodes[current].right, newInherited});
}
}
int newParent = allocateNode();
int oldParent = nodes[bestSibling].parent;
nodes[newParent].left = bestSibling;
nodes[newParent].right = leafIndex;
nodes[newParent].aabb = nodes[bestSibling].aabb.merge(nodes[leafIndex].aabb);
nodes[newParent].parent = oldParent;
nodes[bestSibling].parent = newParent;
nodes[leafIndex].parent = newParent;
refitAncestors(newParent);
return leafIndex;
}
2. 削除（Remove）
リーフを削除する際は、そのリーフの兄弟を親の位置に持ち上げ、不要になったノードを解放します。
void AABBTree::removeLeaf(int leafIndex) {
if (leafIndex == root) { root = -1; return; }
int parent = nodes[leafIndex].parent;
int grandParent = nodes[parent].parent;
int sibling = (nodes[parent].left == leafIndex)
? nodes[parent].right : nodes[parent].left;
if (grandParent != -1) {
if (nodes[grandParent].left == parent)
nodes[grandParent].left = sibling;
else
nodes[grandParent].right = sibling;
nodes[sibling].parent = grandParent;
refitAncestors(grandParent);
} else {
root = sibling;
nodes[sibling].parent = -1;
}
freeNode(parent);
}
3. クエリ（Query） ― 衝突ペアの検出
AABB ツリーの最大の威力を発揮するのがクエリです。あるオブジェクトの AABB と重なる可能性があるノードだけを再帰的に探索します。
void AABBTree::query(const AABB& target, std::vector<int>& results) const {
std::stack<int> stack;
stack.push(root);
while (!stack.empty()) {
int nodeIndex = stack.top();
stack.pop();
if (nodeIndex == -1) continue;
const Node& node = nodes[nodeIndex];
if (!node.aabb.overlaps(target)) continue;
if (node.isLeaf()) {
results.push_back(node.objectId);
} else {
stack.push(node.left);
stack.push(node.right);
}
}
}
この探索は重ならない枝を即座にスキップするため、O(n) の総当たりに比べて 平均 O(log n) の計算量で衝突候補を絞り込めます。
AABB ツリーの計算量
| 操作 | 平均計算量 | 最悪計算量 |
|---|---|---|
| 挿入 | O(log n) | O(n) |
| 削除 | O(log n) | O(n) |
| クエリ（衝突検索） | O(log n) | O(n) |
| 全ペア衝突検出 | O(n log n) | O(n²) |
ツリーのバランスが極端に偏ると最悪ケースに近づきますが、SAH を使うことで実用上は十分にバランスの取れたツリーが構築できます。
どんな時にメリットがあるのか？
1. ゲームエンジンの衝突判定（Broad Phase）
最も代表的なユースケースです。数千〜数万のオブジェクトが存在するゲームシーンで、総当たり（O(n²)）の衝突判定を行うのは現実的ではありません。AABB ツリーを使えば、各オブジェクトの衝突候補を O(log n) で絞り込めるため、全体として O(n log n) で Broad Phase を完了できます。とはいえ、これは僕自身がやっていることではなく友達から聞いたことなので実際にゲームエンジンで活躍できるかどうかはわからないので自分自身の目で確かめていただけると幸いです。
ですが、Box2D や Bullet Physics など、多くの物理エンジンが AABB ツリーを採用しているので一定数の信頼性はあるでしょうけど。。。
2. レイキャスティング / レイトレーシング
光線（Ray）がシーン内のどのオブジェクトと交差するかを調べる際にも、AABB ツリーは有効です。ルートから順に光線と AABB の交差判定を行い、交差しない枝を丸ごとスキップすることで、探索を大幅に高速化できます。これが僕が実際にインターンでやっていることですが、体感計算速度が100倍になったので大幅な性能改善に寄与していると思われます。
3. 動的なシーン（オブジェクトが頻繁に移動する場合）
AABB ツリーの大きな強みは、オブジェクトの動的な追加・削除・移動に対応しやすいことです。BVH（Bounding Volume Hierarchy）を毎フレーム再構築するのはコストが高いですが、AABB ツリーでは以下のテクニックで効率的に更新できます。
- Fat AABB（膨張AABB）: 実際の AABB より少し大きめの AABB を登録しておくことで、小さな移動ではツリーの更新が不要になる
- 増分更新: 移動したオブジェクトだけを削除→再挿入し、祖先ノードの AABB を再計算する
4. 空間クエリ全般
衝突判定以外にも、以下のような空間クエリに活用できます。
- 範囲検索: ある領域内に含まれるオブジェクトの列挙
- 最近傍探索: 最も近いオブジェクトを効率的に見つける
- フラスタムカリング: カメラの視錐台内のオブジェクトだけを描画対象にする
5. 他の空間分割手法と比べた優位性
| 手法 | 動的オブジェクト | メモリ効率 | 実装の容易さ |
|---|---|---|---|
| AABB ツリー | ◎ | ○ | ○ |
| 均一グリッド | △（密度偏りに弱い） | △ | ◎ |
| Octree / Quadtree | ○ | △ | ○ |
| k-d Tree | △（再構築コスト大） | ◎ | △ |
AABB ツリーは特にオブジェクトサイズや密度が不均一な動的シーンで優位性を発揮します。
インターンでの学び
C++ アルゴリズムインターンを通じて、AABB ツリーの実装と最適化に取り組むなかで、以下のような実践的な知見を得ました。
-
メモリレイアウトの重要性: ノードを
std::vectorで連続メモリに配置し、ノードプールを使って動的確保を避けることで、キャッシュ効率が大幅に向上した - SAH の効果: 表面積ヒューリスティックを導入する前後でクエリ性能が 2〜3 倍改善した
-
プロファイリングの習慣:
perfやVTuneを使ってボトルネックを特定し、SIMD 化やブランチの削減といった低レベル最適化を行うサイクルが身についた
アルゴリズムの理論だけでなく、実際のコードに落とし込んでパフォーマンスを計測・改善するプロセスは、インターンならではの貴重な経験でした。
まとめ
AABB ツリーは、空間内のオブジェクトを階層的に管理し、衝突判定や空間クエリを高速化する実用的なデータ構造です。
- 仕組み: 二分木の各ノードが子ノード群を囲む AABB を保持し、重ならない枝を枝刈りすることで探索を高速化
- 計算量: 平均 O(log n) のクエリ性能
- メリットが大きい場面: 動的なオブジェクトが多数存在するゲームやシミュレーション、レイトレーシング、空間クエリ全般
C++ で実装する場合は、メモリレイアウトや SAH の活用がパフォーマンスに直結するため、理論とともに実装上の工夫もぜひ意識してみてください。アルゴリズムは歴史が深く、新しい方法ばかりがいい方法とは限らず古典的な手法が意外に役に立ったりするので色々調べてみてください。
参考文献
- Erin Catto, "Dynamic AABB Tree" (Box2D の実装解説)
- Real-Time Collision Detection, Christer Ericson
- Bullet Physics Library ソースコード (
btDbvt)