Axis-Aligned Bounding Box

Aussi appelé: AABB
Catégorie: Planning & manipulation › Motion planning
Mots-clés: collision-detection, computational-geometry, motion-planning, bounding-volume, simulation

La plus petite boîte aux arêtes parallèles aux axes de coordonnées d'un repère choisi qui enveloppe un objet, stockée sous forme de coins minimal et maximal et utilisée pour des tests rapides de chevauchement et de distance.

Définition

Une boîte englobante alignée sur les axes (Axis-aligned bounding box, AABB) est une boîte qui enveloppe un objet et dont les faces sont parallèles aux axes d'un repère de coordonnées choisi. En 3D, elle est entièrement décrite par six nombres : les x, y et z minimaux et maximaux de l'objet, ou de manière équivalente un centre et trois demi-dimensions. En 2D, c'est un rectangle, et les boîtes tracées par la plupart des détecteurs d'objets dans les images sont des AABB en coordonnées pixel.

L'intérêt d'une AABB est que les tests qui la concernent sont très peu coûteux. Deux AABB ne se chevauchent que si leurs intervalles se chevauchent sur chaque axe, ce qui demande une poignée de comparaisons. La distance entre deux boîtes s'obtient en calculant, sur chaque axe, l'écart entre les intervalles (nul s'ils se chevauchent) et en prenant la norme euclidienne des trois écarts. C'est pourquoi les AABB sont la première étape standard de la détection de collisions : les moteurs physiques et les bibliothèques de collision les utilisent dans la phase large (broad phase), souvent organisées en un arbre appelé hiérarchie de volumes englobants, pour écarter les paires d'objets qui ne peuvent pas être en contact avant d'exécuter des tests exacts sur les paires restantes.

Le prix à payer est un ajustement lâche. Une AABB est définie par rapport à un repère, donc lorsqu'un objet tourne, son AABB dans le repère monde doit être recalculée et grandit en général ; un outil long et fin tenu à 45 degrés a une boîte bien plus grande que l'outil lui-même. Les tests sur les AABB sont donc conservatifs : si deux boîtes ne se chevauchent pas, les objets non plus, mais des boîtes qui se chevauchent ne prouvent pas un contact, et la distance entre boîtes est une borne inférieure de la distance réelle. Les boîtes englobantes orientées (OBB), les sphères englobantes, les capsules, les enveloppes convexes et les champs de distance signée donnent des réponses plus serrées à un coût plus élevé.

Pourquoi c'est important

Les AABB sont l'approximation géométrique la moins coûteuse pour la vérification des collisions, les limites d'espace de travail et les requêtes spatiales, et elles apparaissent dans presque tous les planificateurs de mouvement, simulateurs et chaînes de perception. Savoir qu'elles sont conservatives et dépendantes du repère explique à la fois pourquoi elles sont si largement utilisées et pourquoi les vérifications qui s'appuient sur elles peuvent signaler de fausses collisions ou surestimer la proximité de deux objets.

Applications principales

Détection de collisions en phase large dans les simulateurs et les planificateurs de mouvement
Hiérarchies de volumes englobants pour des requêtes rapides de distance et de rayons
Recadrage de nuages de points sur une région d'intérêt ou un espace de travail
Boîtes de détection d'objets 2D dans les images
Vérifications rapides de dégagement sur des programmes robot et des trajectoires générés

En pratique

Un outil qui vérifie les programmes robot générés par un modèle de langage parcourt chaque point de passage planifié. À chacun, il transforme le maillage de collision de la pince dans le repère monde, calcule son AABB à partir des coordonnées minimales et maximales des sommets, et calcule la distance à l'AABB de chaque objet posé sur la table. Tout point de passage où la distance passe sous un seuil de dégagement est signalé avec l'objet concerné, afin que le programme puisse être révisé. Comme les boîtes sont conservatives, une pince tournée passant près d'une grande bouteille peut être signalée même s'il y a de la place ; pour les cas signalés, l'outil se rabat sur une requête exacte de distance entre maillages dans une bibliothèque de collision avant de signaler un vrai problème.

Idées reçues

Des AABB qui se chevauchent signifient que les objets entrent en collision — le chevauchement montre seulement qu'un contact est possible ; un test exact est nécessaire pour le confirmer
Une AABB est une propriété fixe d'un objet — elle dépend du repère et de l'orientation de l'objet, et doit être recalculée quand l'objet tourne
La distance entre AABB est la distance réelle entre les objets — c'est une borne inférieure, souvent bien plus petite que l'écart réel pour des formes tournées ou irrégulières
Toute boîte autour d'un objet est une AABB — une boîte alignée sur les axes principaux propres de l'objet est une boîte englobante orientée (OBB)

Qui devrait le savoir

Ingénieurs en planification de mouvement et en vérification de collisions
Développeurs de simulation et de physique de jeux
Ingénieurs en perception travaillant avec des nuages de points et des détections
Développeurs d'outils de vérification de programmes pour robots

Technologies associées

Boîte englobante orientée (Oriented Bounding Box)
Hiérarchie de volumes englobants (Bounding Volume Hierarchy)
Flexible Collision Library (FCL)
Algorithme de distance GJK (GJK Distance Algorithm)
Sweep and Prune
Bullet Physics

Termes associés

Projets associés

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

Vidéos

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