Axis-Aligned Bounding Box

• 別名: AABB
• カテゴリ: Planning & manipulation › Motion planning
• タグ: collision-detection, computational-geometry, motion-planning, bounding-volume, simulation

選んだ座標系の座標軸に辺が平行で、物体を囲む最小の箱。最小と最大の角として保持され、高速な重なり判定と距離判定に使われる。

定義

軸平行境界ボックス（AABB）（axis-aligned bounding box）は、物体を囲み、その面が選んだ座標系の軸に平行な箱である。3D では 6 つの数値、すなわち物体の x、y、z の最小値と最大値で、あるいは同等に中心と 3 つの半辺長で完全に記述される。2D では長方形となり、ほとんどの画像物体検出器が描く枠はピクセル座標における AABB である。

AABB の価値は、それに対する判定が非常に安価なことにある。2 つの AABB が重なるのは、すべての軸で区間が重なる場合に限られ、その判定は数回の比較で済む。2 つの箱の間の距離は、各軸で区間どうしの隙間（重なっていればゼロ）を計算し、その 3 つの隙間のユークリッドノルムをとることで求まる。このため AABB は衝突検出の標準的な第一段階である。物理エンジンや衝突ライブラリはブロードフェーズでこれを使い、多くの場合、境界ボリューム階層と呼ばれる木構造にまとめて、残ったペアに厳密な判定を行う前に、接触しえない物体のペアを除外する。

代償は当てはまりの緩さである。AABB はある座標系に対して定義されるため、物体が回転すると世界座標系での AABB を計算し直す必要があり、一般に大きくなる。45 度傾けて持った細長い工具の箱は、工具そのものよりずっと大きい。したがって AABB による判定は保守的である。2 つの箱が重ならなければ物体も重ならないが、箱が重なっても接触の証明にはならず、箱どうしの距離は真の距離の下界である。有向境界ボックス（OBB）、境界球、カプセル、凸包、符号付き距離場は、より高いコストと引き換えにより厳密な答えを与える。

重要な理由

AABB は衝突チェック、作業空間の制限、空間クエリのための最も安価な幾何学的代理であり、ほぼすべてのモーションプランナー、シミュレーター、知覚パイプラインに登場する。AABB が保守的で座標系に依存することを知っていれば、なぜこれほど広く使われるのか、そしてなぜそれに基づくチェックが誤った衝突を報告したり、2 つの物体の近さを過大に見積もったりしうるのかがわかる。

主な用途

• シミュレーターとモーションプランナーにおけるブロードフェーズ衝突検出
• 高速な距離クエリとレイクエリのための境界ボリューム階層
• 点群を関心領域や作業空間に切り出す処理
• 画像における 2D 物体検出の枠
• 生成されたロボットプログラムと軌道の高速なクリアランスチェック

実際の使われ方

言語モデルが生成したロボットプログラムをチェックするツールは、計画された各ウェイポイントを順にたどる。各ウェイポイントで、グリッパーの衝突メッシュを世界座標系に変換し、頂点座標の最小値と最大値からその AABB を計算し、テーブル上の各物体の AABB までの距離を計算する。距離がクリアランスのしきい値を下回るウェイポイントは、関係する物体とともにフラグが立てられ、プログラムを修正できるようにする。箱は保守的なので、回転したグリッパーが背の高いボトルの近くを通ると、余裕があってもフラグが立つことがある。フラグが立ったケースについては、ツールは実際の問題として報告する前に、衝突ライブラリの厳密なメッシュ距離クエリに切り替える。

よくある誤解

• AABB が重なれば物体は衝突している — 重なりは接触の可能性を示すだけであり、確認には厳密な判定が必要である
• AABB は物体の固定された性質である — 座標系と物体の向きに依存し、物体が回転したら計算し直す必要がある
• AABB の距離は物体間の真の距離である — それは下界であり、回転した形状や不規則な形状では実際の隙間よりずっと小さいことが多い
• 物体を囲む箱はどれも AABB である — 物体自身の主軸に揃えた箱は有向境界ボックス（OBB）である

知っておくべき人

• モーションプランニングと衝突チェックのエンジニア
• シミュレーションとゲーム物理の開発者
• 点群や検出結果を扱う知覚エンジニア
• ロボット向けプログラム検証ツールの開発者

関連技術

• 有向境界ボックス（Oriented Bounding Box）
• 境界ボリューム階層（Bounding Volume Hierarchy）
• Flexible Collision Library（FCL）
• GJK 距離アルゴリズム（GJK Distance Algorithm）
• スイープアンドプルーン（Sweep and Prune）
• Bullet Physics

関連用語

• Obstacle Avoidance
• Motion Planning
• Signed Distance Field
• Octree
• Point Cloud
• End-User Robot Programming

関連プロジェクト

• GENESIS: World's fastest physics engine: 43M FPS for embodied AI learning
• LeRobot: HuggingFace ML library for real-world robotics in PyTorch
• PyBullet: Python physics simulator for robotics and RL research with fast CPU-based simulation
• RLinf: Scalable infrastructure for post-training foundation models via RL
• Webots: Cross-platform robot simulator with built-in models, sensors, and development environment
• NVIDIA Isaac Sim: NVIDIA Omniverse app for AI-driven robot simulation and testing

動画

• COMP4300 - Game Programming - Lecture 08 - Collision Detection & AABB: Dave Churchill