Axis-Aligned Bounding Box

• Detto anche: AABB
• Categoria: Planning & manipulation › Motion planning
• Tag: collision-detection, computational-geometry, motion-planning, bounding-volume, simulation

Il più piccolo box con spigoli paralleli agli assi coordinati di un sistema di riferimento scelto che racchiude un oggetto, memorizzato come vertici minimo e massimo e usato per test rapidi di sovrapposizione e di distanza.

Definizione

Una bounding box allineata agli assi (axis-aligned bounding box, AABB) è un parallelepipedo che racchiude un oggetto e le cui facce sono parallele agli assi di un sistema di coordinate scelto. In 3D è descritta completamente da sei numeri: i valori minimi e massimi di x, y e z dell'oggetto o, in modo equivalente, un centro e tre semiampiezze. In 2D è un rettangolo, e i riquadri disegnati dalla maggior parte dei rilevatori di oggetti nelle immagini sono AABB in coordinate pixel.

Il pregio di una AABB è che i test su di essa sono molto economici. Due AABB si sovrappongono solo se i loro intervalli si sovrappongono su ogni asse, il che richiede una manciata di confronti. La distanza tra due box si ottiene calcolando, su ogni asse, lo scarto tra gli intervalli (zero se si sovrappongono) e prendendo la norma euclidea dei tre scarti. Per questo le AABB sono il primo stadio standard del rilevamento delle collisioni: i motori fisici e le librerie per le collisioni le usano nella broad phase, spesso organizzate in un albero chiamato gerarchia di volumi di contenimento, per scartare le coppie di oggetti che non possono essere in contatto prima di eseguire test esatti sulle coppie rimanenti.

Il prezzo è un adattamento lasco. Una AABB è definita rispetto a un sistema di riferimento, quindi quando un oggetto ruota la sua AABB nel sistema del mondo va ricalcolata e in genere si ingrandisce; un utensile lungo e sottile tenuto a 45 gradi ha un box molto più grande dell'utensile stesso. I test sulle AABB sono quindi conservativi: se due box non si sovrappongono, non si sovrappongono neanche gli oggetti, ma box sovrapposti non dimostrano un contatto, e la distanza tra box è un limite inferiore della distanza reale. Le bounding box orientate (OBB), le sfere di contenimento, le capsule, gli inviluppi convessi e i campi di distanza con segno danno risposte più precise a un costo maggiore.

Perché è importante

Le AABB sono l'approssimazione geometrica più economica per la verifica delle collisioni, i limiti dello spazio di lavoro e le interrogazioni spaziali, e compaiono in quasi ogni pianificatore del movimento, simulatore e pipeline di percezione. Sapere che sono conservative e dipendenti dal sistema di riferimento spiega sia perché sono così diffuse sia perché i controlli basati su di esse possono segnalare false collisioni o sovrastimare quanto due oggetti siano vicini.

Applicazioni principali

• Rilevamento delle collisioni in broad phase nei simulatori e nei pianificatori del movimento
• Gerarchie di volumi di contenimento per interrogazioni rapide di distanza e di raggi
• Ritaglio di nuvole di punti su una regione di interesse o sullo spazio di lavoro
• Riquadri di rilevamento di oggetti 2D nelle immagini
• Verifiche rapide delle distanze di sicurezza su programmi e traiettorie del robot generati

In pratica

Uno strumento che verifica i programmi per robot generati da un modello linguistico percorre uno per uno i waypoint pianificati. In ciascuno trasforma la mesh di collisione della pinza nel sistema di riferimento del mondo, calcola la sua AABB dalle coordinate minime e massime dei vertici e calcola la distanza dalla AABB di ogni oggetto sul tavolo. Ogni waypoint in cui la distanza scende sotto una soglia di distanza di sicurezza viene segnalato insieme all'oggetto coinvolto, così che il programma possa essere rivisto. Poiché i box sono conservativi, una pinza ruotata che passa vicino a una bottiglia alta può essere segnalata anche quando lo spazio c'è; per i casi segnalati lo strumento ricorre a un'interrogazione esatta della distanza tra mesh in una libreria per le collisioni prima di segnalare un problema reale.

Idee sbagliate comuni

• AABB sovrapposte significano che gli oggetti collidono — la sovrapposizione mostra solo che il contatto è possibile; serve un test esatto per confermarlo
• Una AABB è una proprietà fissa di un oggetto — dipende dal sistema di riferimento e dall'orientamento dell'oggetto, e va ricalcolata quando l'oggetto ruota
• La distanza tra AABB è la distanza reale tra gli oggetti — è un limite inferiore, spesso molto più piccolo della distanza effettiva per forme ruotate o irregolari
• Qualsiasi box attorno a un oggetto è una AABB — un box allineato agli assi principali dell'oggetto stesso è una bounding box orientata (OBB)

Chi dovrebbe saperlo

• Ingegneri di pianificazione del movimento e verifica delle collisioni
• Sviluppatori di simulazione e di fisica per videogiochi
• Ingegneri della percezione che lavorano con nuvole di punti e rilevamenti
• Sviluppatori di strumenti di verifica dei programmi per robot

Tecnologie correlate

• Bounding box orientata (Oriented Bounding Box)
• Gerarchia di volumi di contenimento (Bounding Volume Hierarchy)
• Flexible Collision Library (FCL)
• Algoritmo di distanza GJK (GJK Distance Algorithm)
• Sweep and Prune
• Bullet Physics

Termini correlati

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

Progetti correlati

• 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

Video

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