공간 분할 기법 — Quadtree와 AABB

한 줄 요약

대용량 3D 데이터를 웹에서 효율적으로 렌더링하려면, 데이터를 공간적으로 분할하여 필요한 부분만 로드해야 한다. Quadtree와 AABB는 이 분할에 사용되는 대표적인 두 가지 기법이다.

왜 공간 분할이 필요한가

건물 하나의 BIM 데이터에 수천~수만 개의 건축 요소(벽, 기둥, 슬래브, 파이프 등)가 들어있다. 이걸 하나의 파일로 웹에 올리면 두 가지 문제가 발생한다:

로딩 문제: 파일이 수십~수백 MB에 달하므로, 첫 로드에 오랜 시간이 걸린다. 사용자는 건물 전체가 로드될 때까지 빈 화면을 보게 된다.

렌더링 문제: 카메라에서 안 보이는 부분(건물 뒷면, 먼 곳)까지 모두 GPU에 올리므로 메모리가 낭비된다.

공간 분할은 이 문제를 "전체를 한 번에 올리지 말고, 보이는 부분만 올리자"로 해결한다. 데이터를 공간적으로 잘게 나눈 뒤, 카메라 위치에 따라 필요한 타일만 로드하고 나머지는 로드하지 않는다.

Quadtree — 2차원 공간의 재귀적 4분할

원리

Quadtree는 2차원 평면을 재귀적으로 4등분하는 트리 구조다.

전체 영역
├── 좌상 (NW)
├── 우상 (NE)
├── 좌하 (SW)
└── 우하 (SE)

각 사분면 안에 데이터가 일정 수 이상 존재하면, 그 사분면을 다시 4등분한다. 이 과정을 원하는 깊이까지 반복하면, 데이터가 밀집된 영역은 세밀하게 분할되고, 데이터가 적은 영역은 큰 단위로 남는다.

장점

• 적응적 분할: 데이터 밀도에 따라 분할 깊이가 자동으로 달라진다. 건물이 밀집된 도심은 세밀하게, 빈 공간이 많은 외곽은 넓게 분할된다.
• 계층적 구조: 트리의 상위 노드는 넓은 영역을, 하위 노드는 좁은 영역을 대표한다. 이 구조가 3D Tiles의 LOD 계층과 자연스럽게 대응된다.

한계

• 2차원 기반: 기본적으로 x-y 평면을 분할하므로, 높이(z축) 방향의 분할은 별도로 처리해야 한다. 고층 건물처럼 수직으로 복잡한 구조에서는 Quadtree만으로 최적의 분할이 되지 않을 수 있다.
• 균일 4분할: 각 단계에서 반드시 4등분하므로, 데이터 분포가 한쪽에 치우쳐 있으면 빈 사분면이 많이 생긴다.

3D 확장: Octree

Quadtree를 3차원으로 확장한 것이 Octree다. 공간을 8등분(2×2×2)하여 x, y, z 축 모두를 분할한다. 높이 방향의 복잡성이 큰 데이터에서는 Octree가 더 적합할 수 있다.

AABB — 축 정렬 경계 박스

원리

AABB(Axis-Aligned Bounding Box)는 3D 객체를 감싸는 축에 정렬된 최소 직육면체다. "축에 정렬된"이란 박스의 각 면이 x, y, z 축에 평행하다는 뜻이다.

AABB = {
  min: (x_min, y_min, z_min),
  max: (x_max, y_max, z_max)
}

어떤 복잡한 형상이든, 6개의 숫자(최소/최대 x, y, z)만으로 그 형상이 차지하는 공간 범위를 표현할 수 있다.

용도

충돌 검사: 두 AABB가 겹치는지 확인하는 연산은 단순한 비교 연산 6회(각 축의 min/max 비교)로 가능하다. 복잡한 메쉬 간의 충돌을 직접 계산하는 것보다 수십~수백 배 빠르다.

공간 범위 정의: 3D Tiles의 boundingVolume.box가 정확히 AABB다. 각 타일이 3D 공간에서 어떤 범위를 차지하는지를 AABB로 정의한다. Cesium은 이 AABB를 활용하여 카메라에 보이는 타일만 골라서 로드한다.

이 과정을 좀 더 풀어서 설명하면, 카메라에는 시야 절두체(frustum)라는 것이 있다. 카메라가 바라보는 방향으로 뻗어나가는 사다리꼴 모양의 3D 영역이다. 이 영역 안에 들어오는 것만 화면에 보이고, 밖에 있는 것은 화면에 나타나지 않는다.

Cesium은 매 프레임마다 "이 타일의 AABB가 카메라의 frustum과 겹치는가?"를 검사한다. AABB는 min/max 좌표 6개로 표현되므로, 이 겹침 판정은 단순한 숫자 비교만으로 가능하다 — 복잡한 메쉬 형상을 계산할 필요가 없다. 겹치지 않는 타일은 아예 로드하지 않고, 겹치는 타일만 네트워크에서 받아온다. 이것이 대용량 3D 데이터를 웹에서 끊김 없이 렌더링할 수 있는 핵심 원리 중 하나다.

개별 요소의 공간 범위: IFC의 각 건축 요소(벽, 기둥 등)의 공간 범위를 AABB로 계산하면, 어떤 요소가 어떤 타일에 속하는지를 빠르게 결정할 수 있다.

장점

• 계산이 극히 빠르다: min/max 비교만으로 공간 관계를 판단할 수 있다.
• 구현이 단순하다: 6개의 숫자로 표현되므로 저장·전송·비교 모두 간단하다.

한계

• 회전된 객체에 비효율적: 축에 정렬되어 있으므로, 45도 회전된 긴 객체는 AABB가 실제 객체보다 훨씬 크게 잡힌다. 이 경우 OBB(Oriented Bounding Box, 방향 정렬 경계 박스)가 더 정밀하다.
• 분할 기법이 아니다: AABB 자체는 공간 분할 알고리즘이 아니라, 개별 객체의 공간 범위를 정의하는 도구다. 비유하면, Quadtree가 "서울을 16개 구역으로 나누는 방법"이라면, AABB는 "이 건물이 동서 30m, 남북 20m를 차지한다"는 개별 건물의 크기를 표현하는 것이다. AABB는 도시를 나누지 않는다 — 건물 하나의 범위만 알려준다. 공간을 분할하려면 Quadtree나 Octree 같은 알고리즘과 함께 사용해야 한다.

Quadtree와 AABB의 관계

두 기법은 경쟁 관계가 아니라 서로 다른 레벨에서 작동하는 상호 보완 관계다:

• Quadtree (또는 Octree): 전체 공간을 어떻게 분할할 것인가 (공간 분할 전략)
• AABB: 개별 객체가 어떤 공간을 차지하는가 (객체 범위 정의)

예를 들어, Quadtree로 건물 전체를 4×4 = 16개 영역으로 분할한 뒤, 각 건축 요소의 AABB를 계산하여 "이 벽은 3번 영역에 속한다"를 결정하는 식이다. Quadtree가 "어디를 자를 것인가"를 결정하고, AABB가 "이 요소는 어디에 있는가"를 알려준다.

3D Tiles에서는 이 분할 결과가 tileset.json의 계층적 타일 구조로 표현되고, 각 타일의 boundingVolume이 해당 타일의 공간 범위를 정의한다.

이 경험에서 추출한 원칙

1. "전부 보여주기"는 웹 3D에서 불가능하다. 대용량 3D 데이터를 웹에서 다루려면, "보이지 않는 것은 로드하지 않는다"가 출발점이다. frustum culling(시야 밖 제거)과 공간 분할(영역별 선택적 로드)은 이 원칙의 구체적 구현이다. 이것 없이는 수 GB의 데이터를 브라우저에서 렌더링하는 것 자체가 성립하지 않는다.

2. 단순한 데이터 구조가 복잡한 최적화를 가능하게 한다. AABB는 숫자 6개(min/max x, y, z)에 불과하지만, 이 6개의 숫자만으로 "이 타일이 카메라 시야에 보이는가?"를 매 프레임 빠르게 판단할 수 있다. 복잡한 메쉬 형상을 직접 비교하는 대신 단순한 박스끼리 비교하는 것이 실시간 렌더링을 가능하게 만드는 핵심이다.