Axis-Aligned Bounding Box

• Auch genannt: AABB
• Kategorie: Planning & manipulation › Motion planning
• Schlagwörter: collision-detection, computational-geometry, motion-planning, bounding-volume, simulation

Der kleinste Quader mit Kanten parallel zu den Koordinatenachsen eines gewählten Koordinatensystems, der ein Objekt umschließt, gespeichert als minimale und maximale Ecke und genutzt für schnelle Überlappungs- und Abstandstests.

Definition

Ein achsenparalleler Hüllquader (Axis-aligned bounding box, AABB) ist ein Quader, der ein Objekt umschließt und dessen Seitenflächen parallel zu den Achsen eines gewählten Koordinatensystems liegen. In 3D wird er vollständig durch sechs Zahlen beschrieben: das minimale und maximale x, y und z des Objekts, oder gleichwertig durch einen Mittelpunkt und drei halbe Kantenlängen. In 2D ist er ein Rechteck, und die Boxen, die die meisten Objektdetektoren für Bilder zeichnen, sind AABBs in Pixelkoordinaten.

Der Wert eines AABB liegt darin, dass Tests darauf sehr billig sind. Zwei AABBs überlappen nur, wenn sich ihre Intervalle auf jeder Achse überlappen, was eine Handvoll Vergleiche erfordert. Der Abstand zwischen zwei Quadern ergibt sich, indem man auf jeder Achse die Lücke zwischen den Intervallen berechnet (null, wenn sie überlappen) und die euklidische Norm der drei Lücken bildet. Deshalb sind AABBs die Standard-Erststufe der Kollisionserkennung: Physik-Engines und Kollisionsbibliotheken nutzen sie in der Broad Phase, oft organisiert in einem Baum, der Hüllkörperhierarchie genannt wird, um Objektpaare zu verwerfen, die sich nicht berühren können, bevor exakte Tests auf den verbleibenden Paaren laufen.

Der Preis ist eine lockere Passform. Ein AABB ist relativ zu einem Koordinatensystem definiert, daher muss sein AABB im Weltkoordinatensystem neu berechnet werden, wenn sich ein Objekt dreht, und er wird im Allgemeinen größer; ein langes, dünnes Werkzeug, das unter 45 Grad gehalten wird, hat einen Quader, der viel größer ist als das Werkzeug selbst. Tests an AABBs sind daher konservativ: Wenn zwei Quader nicht überlappen, tun es die Objekte auch nicht, aber überlappende Quader beweisen keinen Kontakt, und der Abstand zwischen den Quadern ist eine untere Schranke für den wahren Abstand. Orientierte Hüllquader (OBBs), Hüllkugeln, Kapseln, konvexe Hüllen und vorzeichenbehaftete Distanzfelder liefern genauere Antworten bei höheren Kosten.

Warum es wichtig ist

AABBs sind der billigste geometrische Stellvertreter für Kollisionsprüfung, Arbeitsraumgrenzen und räumliche Abfragen, und sie tauchen in fast jedem Bewegungsplaner, Simulator und jeder Wahrnehmungspipeline auf. Wer weiß, dass sie konservativ und vom Koordinatensystem abhängig sind, versteht sowohl, warum sie so verbreitet sind, als auch, warum darauf beruhende Prüfungen Scheinkollisionen melden oder überschätzen können, wie nah sich zwei Objekte sind.

Wichtige Anwendungen

• Kollisionserkennung in der Broad Phase in Simulatoren und Bewegungsplanern
• Hüllkörperhierarchien für schnelle Abstands- und Strahlabfragen
• Zuschneiden von Punktwolken auf einen interessierenden Bereich oder Arbeitsraum
• 2D-Boxen der Objekterkennung in Bildern
• Schnelle Freiraumprüfungen an generierten Roboterprogrammen und Trajektorien

In der Praxis

Ein Werkzeug, das von einem Sprachmodell generierte Roboterprogramme prüft, geht jeden geplanten Wegpunkt durch. An jedem transformiert es das Kollisionsnetz des Greifers ins Weltkoordinatensystem, berechnet seinen AABB aus den minimalen und maximalen Eckpunktkoordinaten und berechnet den Abstand zum AABB jedes Objekts auf dem Tisch. Jeder Wegpunkt, an dem der Abstand unter eine Freiraumschwelle fällt, wird mit dem beteiligten Objekt markiert, damit das Programm überarbeitet werden kann. Weil die Quader konservativ sind, kann ein gedrehter Greifer, der nah an einer hohen Flasche vorbeifährt, markiert werden, selbst wenn Platz ist; für markierte Fälle greift das Werkzeug auf eine exakte Netzabstandsabfrage in einer Kollisionsbibliothek zurück, bevor es ein echtes Problem meldet.

Häufige Missverständnisse

• Überlappende AABBs bedeuten, dass die Objekte kollidieren — die Überlappung zeigt nur, dass ein Kontakt möglich ist; zur Bestätigung ist ein exakter Test nötig
• Ein AABB ist eine feste Eigenschaft eines Objekts — er hängt vom Koordinatensystem und der Orientierung des Objekts ab und muss neu berechnet werden, wenn sich das Objekt dreht
• Der AABB-Abstand ist der wahre Abstand zwischen Objekten — er ist eine untere Schranke, bei gedrehten oder unregelmäßigen Formen oft viel kleiner als die tatsächliche Lücke
• Jeder Quader um ein Objekt ist ein AABB — ein Quader, der an den eigenen Hauptachsen des Objekts ausgerichtet ist, ist ein orientierter Hüllquader (OBB)

Wer das wissen sollte

• Ingenieure für Bewegungsplanung und Kollisionsprüfung
• Entwickler von Simulationen und Spielphysik
• Wahrnehmungsingenieure, die mit Punktwolken und Detektionen arbeiten
• Entwickler von Programmverifikationswerkzeugen für Roboter

Verwandte Technologien

• Orientierter Hüllquader (Oriented Bounding Box)
• Hüllkörperhierarchie (Bounding Volume Hierarchy)
• Flexible Collision Library (FCL)
• GJK-Abstandsalgorithmus (GJK Distance Algorithm)
• Sweep and Prune
• Bullet Physics

Verwandte Begriffe

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

Verwandte Projekte

• 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

Videos

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