Axis-Aligned Bounding Box

• 다른 이름: AABB
• 카테고리: Planning & manipulation › Motion planning
• 태그: collision-detection, computational-geometry, motion-planning, bounding-volume, simulation

선택한 좌표계의 좌표축과 모서리가 평행하면서 물체를 둘러싸는 가장 작은 상자로, 최소 및 최대 꼭짓점으로 저장되며 빠른 겹침 판정과 거리 판정에 쓰인다.

정의

축 정렬 경계 상자(Axis-aligned bounding box, AABB)는 물체를 둘러싸며, 면이 선택한 좌표계의 축과 평행한 상자다. 3D에서는 여섯 개의 수, 즉 물체의 x, y, z 최솟값과 최댓값, 또는 동등하게 중심과 세 개의 반폭으로 완전히 기술된다. 2D에서는 직사각형이며, 대부분의 이미지 객체 검출기가 그리는 상자는 픽셀 좌표의 AABB다.

AABB의 가치는 이에 대한 판정이 매우 저렴하다는 데 있다. 두 AABB는 모든 축에서 구간이 겹칠 때에만 겹치며, 이를 확인하는 데는 몇 번의 비교면 충분하다. 두 상자 사이의 거리는 각 축에서 구간 사이의 간격(겹치면 0)을 계산하고 세 간격의 유클리드 노름을 취해 구한다. 이 때문에 AABB는 충돌 감지의 표준 첫 단계다. 물리 엔진과 충돌 라이브러리는 광역 단계(broad phase)에서 AABB를 사용하며, 흔히 경계 볼륨 계층이라는 트리로 구성해, 남은 쌍에 정확한 판정을 실행하기 전에 접촉할 수 없는 물체 쌍을 걸러 낸다.

대가는 느슨한 맞춤이다. AABB는 좌표계를 기준으로 정의되므로, 물체가 회전하면 월드 좌표계 AABB를 다시 계산해야 하며 일반적으로 커진다. 45도로 들고 있는 길고 가는 공구는 공구 자체보다 훨씬 큰 상자를 가진다. 따라서 AABB에 대한 판정은 보수적이다. 두 상자가 겹치지 않으면 물체도 겹치지 않지만, 상자가 겹친다고 접촉이 증명되지는 않으며, 상자 간 거리는 실제 거리의 하한이다. 방향성 경계 상자(OBB), 경계 구, 캡슐, 볼록 껍질, 부호 거리 필드는 더 큰 비용으로 더 정확한 답을 준다.

중요한 이유

AABB는 충돌 검사, 작업 공간 한계, 공간 질의를 위한 가장 저렴한 기하 대용물이며, 거의 모든 모션 플래너, 시뮬레이터, 인식 파이프라인에 등장한다. AABB가 보수적이고 좌표계에 의존한다는 것을 알면, 왜 그렇게 널리 쓰이는지와 함께 왜 이를 기반으로 한 검사가 거짓 충돌을 보고하거나 두 물체가 얼마나 가까운지를 과대평가할 수 있는지 둘 다 설명된다.

주요 응용

• 시뮬레이터와 모션 플래너의 광역 단계 충돌 감지
• 빠른 거리 질의와 광선 질의를 위한 경계 볼륨 계층
• 점군을 관심 영역이나 작업 공간으로 잘라 내기
• 이미지의 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