Axis-Aligned Bounding Box

Também chamado: AABB
Categoria: Planning & manipulation › Motion planning
Tags: collision-detection, computational-geometry, motion-planning, bounding-volume, simulation

A menor caixa com arestas paralelas aos eixos de coordenadas de um sistema escolhido que envolve um objeto, armazenada como cantos mínimo e máximo e usada em testes rápidos de sobreposição e de distância.

Definição

Uma caixa delimitadora alinhada aos eixos (axis-aligned bounding box, AABB) é uma caixa que envolve um objeto e cujas faces são paralelas aos eixos de um sistema de coordenadas escolhido. Em 3D, ela é totalmente descrita por seis números: os valores mínimo e máximo de x, y e z do objeto ou, de forma equivalente, um centro e três semiextensões. Em 2D, é um retângulo, e as caixas desenhadas pela maioria dos detectores de objetos em imagens são AABBs em coordenadas de pixel.

O valor de uma AABB é que os testes sobre ela são muito baratos. Duas AABBs se sobrepõem somente se seus intervalos se sobrepõem em todos os eixos, o que exige um punhado de comparações. A distância entre duas caixas é obtida calculando, em cada eixo, o vão entre os intervalos (zero se eles se sobrepõem) e tomando a norma euclidiana dos três vãos. Por isso, as AABBs são o primeiro estágio padrão na detecção de colisões: motores de física e bibliotecas de colisão as usam na fase ampla (broad phase), muitas vezes organizadas em uma árvore chamada hierarquia de volumes delimitadores, para descartar pares de objetos que não podem estar se tocando antes de executar testes exatos nos pares restantes.

O preço é um ajuste folgado. Uma AABB é definida em relação a um sistema de coordenadas, então, quando um objeto gira, sua AABB no sistema do mundo precisa ser recalculada e geralmente cresce; uma ferramenta longa e fina segurada a 45 graus tem uma caixa muito maior que a própria ferramenta. Os testes com AABBs são, portanto, conservadores: se duas caixas não se sobrepõem, os objetos também não, mas caixas sobrepostas não provam contato, e a distância entre caixas é um limite inferior da distância real. Caixas delimitadoras orientadas (OBBs), esferas delimitadoras, cápsulas, envoltórias convexas e campos de distância com sinal dão respostas mais justas a um custo maior.

Por que importa

As AABBs são o substituto geométrico mais barato para verificação de colisões, limites do espaço de trabalho e consultas espaciais, e aparecem em quase todo planejador de movimento, simulador e pipeline de percepção. Saber que elas são conservadoras e dependentes do sistema de coordenadas explica tanto por que são tão usadas quanto por que verificações baseadas nelas podem relatar colisões falsas ou superestimar o quanto dois objetos estão próximos.

Principais aplicações

Detecção de colisões na fase ampla em simuladores e planejadores de movimento
Hierarquias de volumes delimitadores para consultas rápidas de distância e de raios
Recorte de nuvens de pontos para uma região de interesse ou para o espaço de trabalho
Caixas de detecção de objetos 2D em imagens
Verificações rápidas de folga em programas e trajetórias de robô gerados

Na prática

Uma ferramenta que verifica programas de robô gerados por um modelo de linguagem percorre cada waypoint planejado. Em cada um, ela transforma a malha de colisão da garra para o sistema de coordenadas do mundo, calcula sua AABB a partir das coordenadas mínima e máxima dos vértices e calcula a distância até a AABB de cada objeto sobre a mesa. Qualquer waypoint em que a distância fique abaixo de um limiar de folga é sinalizado com o objeto envolvido, para que o programa possa ser revisado. Como as caixas são conservadoras, uma garra girada passando perto de uma garrafa alta pode ser sinalizada mesmo quando há espaço; nos casos sinalizados, a ferramenta recorre a uma consulta exata de distância entre malhas em uma biblioteca de colisão antes de relatar um problema real.

Equívocos comuns

AABBs sobrepostas significam que os objetos colidem — a sobreposição só mostra que o contato é possível; um teste exato é necessário para confirmá-lo
Uma AABB é uma propriedade fixa de um objeto — ela depende do sistema de coordenadas e da orientação do objeto, e precisa ser recalculada quando o objeto gira
A distância entre AABBs é a distância real entre os objetos — ela é um limite inferior, muitas vezes bem menor que a separação real para formas giradas ou irregulares
Qualquer caixa em volta de um objeto é uma AABB — uma caixa alinhada aos eixos principais do próprio objeto é uma caixa delimitadora orientada (OBB)

Quem deve saber

Engenheiros de planejamento de movimento e verificação de colisões
Desenvolvedores de simulação e de física para jogos
Engenheiros de percepção que trabalham com nuvens de pontos e detecções
Desenvolvedores de ferramentas de verificação de programas para robôs

Tecnologias relacionadas

Caixa delimitadora orientada (Oriented Bounding Box)
Hierarquia de volumes delimitadores (Bounding Volume Hierarchy)
Flexible Collision Library (FCL)
Algoritmo de distância GJK (GJK Distance Algorithm)
Sweep and Prune
Bullet Physics

Termos relacionados

Projetos relacionados

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

Vídeos

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