옥트리

수치해석 컴퓨터 그래픽스 게임 개발 마지막 수정: 2026-08-29 04:47:39

1. 개요[편집]

정육면체를 여덟 조각으로 자르고, 필요한 조각만 다시 자른다. 그게 전부다. 나머지는 그 단순함을 얼마나 싸게 표현하느냐의 문제다.

옥트리(octree, 팔진트리)는 축 정렬 정육면체 영역을 세 좌표축의 중점에서 잘라 여덟 개의 자식 정육면체로 나누는 조작을 재귀적으로 반복해 만든 트리 자료구조다. 2차원 판이 쿼드트리, 1차원 판은 그냥 이진 탐색 트리다. 도널드 미거가 1980년 무렵 3차원 물체 표현 기법으로 정리하며 이름을 붙였고, 그 뒤로 렌더링·물리·로보틱스·수치해석이 각자 독립적으로 같은 구조를 재발명해 왔다.

핵심은 분할 위치가 데이터와 무관하게 언제나 셀 중심이라는 것이다. KD-트리가 중앙값이나 표면적 휴리스틱을 보고 자를 곳을 고르는 것과 정반대다. 이 「멍청한」 규칙 덕분에 세 가지가 공짜로 따라온다 — 셀이 영원히 정육면체이고(종횡비 1), 좌표만 알면 트리를 안 보고도 어느 셀에 속하는지 계산할 수 있으며, 레벨 $\ell$ 이 곧 물리적 해상도 $s/2^\ell$ 이다. 자료구조 전체의 조감도는 공간 분할 자료구조에 있고, 여기서는 옥트리 자체의 표현·연산·응용을 판다.

2. 점 옥트리와 영역 옥트리[편집]

같은 이름 아래 사실 성격이 다른 둘이 섞여 있다.

점 옥트리(point octree)는 데이터 점 자체를 분할점으로 삼는다. 삽입된 점이 그 노드의 8분할 중심이 되고, 다음 점은 자기 위치에 해당하는 자식으로 내려가 다시 중심이 된다. 이진 탐색 트리의 3차원 판이며 핑켈·벤틀리의 점 쿼드트리(1974)의 확장이다. 트리 모양이 삽입 순서에 의존하고 셀이 정육면체가 아니게 되며, 균형을 맞추기 까다롭다. 그래서 요즘은 거의 안 쓴다 — 같은 자리에서 KD-트리가 더 잘한다.

영역 옥트리(region octree)는 공간을 반씩 접는다. 분할점은 언제나 셀의 기하학적 중심이라 데이터와 무관하고, 그래서 셀이 영원히 정육면체다. 실무에서 「옥트리」라 하면 사실상 이쪽이며, 담는 내용에 따라 다시 갈린다.

PR 옥트리(point-region). 잎에 점을 담고, 잎 안의 점이 용량(보통 8~32개)을 넘으면 쪼갠다. 점군·입자 검색용.
점유 옥트리(occupancy). 잎이 «찼다/비었다/부분적»의 셋 중 하나를 들고, 균질한 영역은 쪼개지 않는다. 원래 미거가 고체 모델링용으로 쓴 형태이고, 복셀 자료와 로보틱스 지도가 이것이다.

깊이에 관해 한 가지 함정이 있다. 영역 옥트리의 깊이는 점 개수가 아니라 점들의 「퍼짐 비」(spread, 최대 거리 ÷ 최소 거리)가 정한다. 아주 가까이 붙은 두 점을 갈라놓으려면 그 둘이 다른 자식에 떨어질 때까지 계속 쪼개야 하고, 그동안 만들어지는 노드는 자식이 하나뿐인 빈 사슬이다. 점이 두 개뿐이어도 깊이 40이 나올 수 있다는 뜻이다. 처방은 둘 — 최대 깊이 상한을 걸거나, 자식이 하나뿐인 사슬을 접어 버리는 압축 옥트리(compressed octree)를 쓴다. 후자면 노드 수가 $O(n)$ 으로 보장된다.¹

3. 선형 옥트리 — 트리를 정수 배열로[편집]

포인터로 노드를 잇는 구현은 캐시에 나쁘고, 분산 환경에서 프로세스 사이로 쪼개기가 지옥이다. 선형 옥트리(가르간티니, 1982)는 포인터를 통째로 없애고 셀 하나를 정수 하나로 표현한다. 그 정수가 공간 채움 곡선 중 모턴 코드(Z-차수)다.

레벨 $\ell$ 의 셀 좌표 $(i,j,k)$ 를 $\ell$ 비트 정수로 쓰고 비트를 셋씩 번갈아 끼운다.

m = i_{\ell-1}\,j_{\ell-1}\,k_{\ell-1}\ \ i_{\ell-2}\,j_{\ell-2}\,k_{\ell-2}\ \cdots\ i_0\,j_0\,k_0

이 한 줄에서 옥트리의 계층 구조가 통째로 튀어나온다.

부모 = m >> 3, $u$ 번째 자식 = (m << 3) | u. 상위 $3\ell'$ 비트가 곧 레벨 $\ell'$ 조상의 키다.
형제 8개는 하위 3비트만 다르다. 즉 연속한 8개 정수를 차지한다. 캐시 라인 하나에 형제가 다 들어온다는 뜻이다.
조상-자손 판정이 접두사 비교다. 트리를 타고 내려갈 필요가 없다.
레벨이 다른 셀들을 한 배열에 섞어 두려면 레벨 정보가 필요한데, 표준 트릭은 최상위에 1 한 비트를 씌워 두는 것이다. 그러면 최상위 세트 비트의 위치가 레벨을 알려 준다.

이 표현에서 옥트리를 짓는 절차는 「점마다 모턴 키를 계산하고 정렬한다」가 전부다. 정렬된 키 배열이 곧 깊이 우선 순회 순서이며, 인접 키의 공통 접두사 길이가 두 셀의 최소 공통 조상 레벨을 준다. 키가 정수이므로 기수 정렬이 그대로 먹히고, 그래서 GPU에서 수백만 개짜리 트리를 밀리초 단위로 다시 지을 수 있다. 실시간 레이 트레이싱의 LBVH 빌더가 정확히 이 방식이다.

4. 이웃 탐색 — 비트 산술로 끝낸다[편집]

옥트리 연산 중 제일 자주 필요하고 제일 귀찮은 것이 「이 셀의 $+x$ 쪽 이웃은 누구인가」다. 포인터 트리에서는 공통 조상까지 올라갔다 반대편으로 내려오는 재귀를 짜야 한다. 모턴 키에서는 좌표 필드 하나만 증감하면 되고, 그것이 비트 연산 몇 줄이다.

$x$ 비트들의 마스크를 X(3비트마다 하나씩 선 100100100...)라 하면

x_plus  = (((m |  ~X) + 1) & X) | (m & ~X)
x_minus = (((m &   X) - 1) & X) | (m & ~X)

원리는 자리올림 조작이다. 더할 때는 $x$ 가 아닌 자리를 전부 1로 채워 두면 캐리가 그 구간을 그냥 통과해 다음 $x$ 비트로 올라가고, 뺄 때는 반대로 0으로 비워 두면 빌림이 통과한다. 다른 축의 비트는 손대지 않은 채 $x$ 필드만 $\pm 1$ 된 셈이다. 이 상수 시간 이웃 탐색이 선형 옥트리를 쓰는 실질적 이유다.²

레벨이 섞인 트리에서는 여기에 조건이 하나 더 붙는다. 이웃 키를 계산했더니 그 셀이 실제로는 더 굵거나 더 잘게 쪼개져 있을 수 있으므로, 정렬된 배열에서 이진 탐색으로 실존하는 조상 또는 자손들을 찾아야 한다. 이 검색을 감당 가능하게 만드는 것이 2:1 균형 조건(면을 공유하는 두 잎의 레벨 차이가 1 이하)이다. 조건을 강제하면 이웃 후보가 「같은 레벨 하나, 부모 하나, 자식 넷」으로 유한하게 닫히고, 수치해석 쪽에서는 인접 셀 간 보간 스텐실이 유한하게 정의된다. 대신 균형화 자체가 옥트리 알고리즘 중 가장 손이 많이 가는 부분이라, AMR 프레임워크의 코드 절반이 여기에 들어간다.

5. 옥트리 vs KD-트리 vs BVH[편집]

브리핑 한 장으로 정리하면 이렇다.

	옥트리	KD-트리	경계 볼륨 계층
자르는 대상	공간	공간	객체
분할 위치	셀 중심 (데이터 무관)	중앙값·SAH (데이터 적응)	객체 묶기
자식 수	8	2	2
셀 모양	항상 정육면체	종횡비 임의	겹치는 상자
프리미티브 중복	걸치면 중복 등록	걸치면 중복 등록	없음
셀 주소	정수 키 하나	트리 순회 필요	트리 순회 필요

데이터 적응 분할이 언제나 이기는 것은 아니다. KD-트리는 점 분포에 맞춰 잘라 균형을 잡으니 최근접 이웃 질의에서 유리하지만, 셀 종횡비가 제멋대로라 「셀 크기」라는 스칼라가 잘 정의되지 않는다. 옥트리는 그 대가로 불균형을 감수하는 대신

셀 크기 $s$ 가 하나의 숫자다. 반스-헛 알고리즘의 개방 판정 $s/d < \theta$ 나 고속 다중극자법의 잘 분리된 상자 조건은 셀이 정육면체라야 오차 한계가 깔끔하게 나온다.
레벨과 해상도가 1:1이다. 밉맵·LOD·복셀 해상도 같은 다중해상도 개념이 트리 레벨에 그대로 대응한다.
주소 계산이 좌표 산술이다. 트리를 공유하지 않는 다른 프로세스도 좌표만으로 셀 키를 계산할 수 있어 분산 환경에서 결정적으로 유리하다.

그래서 「전수 대신 후보만」이라는 목적만 같을 뿐, 골라야 하는 상황이 갈린다. 정적 삼각형 장면의 광선 순회는 SAH KD-트리나 경계 볼륨 계층, 움직이는 강체 무리는 BVH, 해상도 계층 자체가 의미를 갖는 문제(복셀·중력·AMR)는 옥트리다.

6. 게임과 그래픽스에서[편집]

브로드페이즈 충돌 감지. 객체를 자기가 완전히 들어가는 가장 작은 셀에 등록하고, 같은 셀과 조상·자손 셀에 있는 것들만 후보로 삼는다. 고전적 약점은 경계에 걸친 작은 객체다 — 셀 경계 바로 위에 있는 지름 1짜리 공이 루트까지 올라가 버려서 모든 것과 후보 쌍이 된다. 처방이 느슨한 옥트리(loose octree)로, 각 셀의 판정 경계를 2배로 부풀려 겹치게 만든다. 그러면 자기 크기에만 의존해 등록 레벨이 정해지고 위치와 무관해진다.³
프러스텀 컬링. 노드 경계상자가 시야 절두체 밖이면 그 아래를 통째로 버리고, 완전히 안이면 자손 검사를 생략한다. 절두체-AABB 판정이 싸고 가지치기가 강해서 실내 씬 아닌 넓은 야외 씬의 기본값이다. 오클루전 컬링과 조합할 때도 옥트리 노드가 질의 단위가 된다.
스파스 복셀 옥트리(SVO). 복셀 격자를 통째로 들면 $n^3$ 이 즉사하지만, 표면 근처만 세분화하면 실질 $O(n^2)$ 이다. 라이네·카라스(2010)의 SVO는 이 구조로 광선 행진 렌더링을 실용화했고, 크라생 등의 복셀 콘 트레이싱은 옥트리 레벨을 3D 밉맵처럼 써서 전역 조명의 간접광을 근사한다 — 거친 레벨을 읽는 것이 곧 넓은 각도를 적분하는 것이라는 대응이 핵심이다. 여기서 한 걸음 더 나간 것이 복셀 DAG로, 모양이 같은 부분트리를 하나로 병합해 트리를 유향 비순환 그래프로 바꾼다. 반복이 많은 장면에서 압축률이 수십~수백 배 나온다.
색 양자화. RGB 세 채널을 좌표로 보고 옥트리를 지어 잎을 병합해 나가면 팔레트가 나온다. GIF 시절의 고전 알고리즘이고, 벡터 양자화를 옥트리로 근사한 물건이라고 보면 정확하다.

7. 수치해석과 로보틱스에서[편집]

$N$ 체 계층 분해. 반스-헛 알고리즘은 입자를 옥트리에 넣고 멀리 있는 셀을 질량중심 하나로 대체해 $O(N^2)$ 을 $O(N \log N)$ 으로 낮춘다. 고속 다중극자법은 같은 트리 위에서 다중극 전개와 국소 전개를 주고받아 $O(N)$ 까지 간다. 둘 다 셀이 정육면체라야 오차 한계가 성립하는 대표 사례이고, 실제 구현은 입자를 모턴 정렬하는 것으로 트리 구축을 대신한다.
적응 격자 세분화. 셀 단위 AMR은 계산 격자 자체가 옥트리다. 리프의 모턴 키 배열만 유지하고, 공간 채움 곡선 순서로 잘라 프로세스에 나눠 주면 부하 분산과 재분할이 정렬 문제로 환원된다. p4est는 아예 옥트리의 숲(forest of octrees)을 다뤄 복잡한 도메인을 여러 뿌리로 덮는다. 블록 구조 AMR과의 선택은 「셀마다 적응할 것인가, 균일 블록 단위로 적응할 것인가」 — 전자는 낭비가 적고 후자는 커널이 단순하다.
메시 생성. 도메인을 옥트리로 덮고 경계에 걸친 셀을 형상에 맞춰 잘라내는 방식이 자동 메셔의 근간이다. snappyHexMesh나 컷셀 메셔가 이 계열이며, 자세한 것은 해당 문서 참고.
점군과 점유 지도. PCL의 옥트리 모듈은 점군 정합 전처리의 복셀 다운샘플링과 반경 질의를 맡고, 로보틱스의 OctoMap은 잎마다 점유 확률을 로그 오즈로 누적해 미지 영역과 빈 영역을 구분하는 3차원 지도를 만든다. 라이다 한 스캔이 수십만 점인데 지도는 몇 MB로 유지되는 것이 이 구조 덕이다.
분자동역학·SPH? 여기서는 옥트리가 진다. 컷오프 반경이 고정이면 셀 변을 컷오프로 잡은 균일 격자가 질의당 $O(1)$ 이고 트리 구축 비용조차 없다. 밀도가 수십 자릿수로 불균일한 천체물리 계산에서야 트리가 값을 한다. 「반경이 고정이고 밀도가 고르면 격자」라는 판단 기준은 여기서도 그대로다.

8. 구현할 때 밟는 지뢰[편집]

깊이 상한을 안 걸었다. 좌표가 같은 점이 둘 있으면 재귀가 영원히 안 끝난다. 부동소수점 오차로 «거의 같은» 점이 생기는 것만으로도 깊이가 수십으로 튄다. 상한 + 잎 용량 두 개를 함께 걸어라.
키 비트 예산을 계산하지 않았다. 64비트 정수에 3좌표를 끼우면 축당 21비트, 즉 레벨 21이 한계다. 넉넉해 보이지만 레벨 표시용 비트와 여유를 빼면 실제로는 그보다 낮고, 지구 규모 좌표계에서는 금방 바닥난다.
경계 위의 점. 셀 중심에 정확히 놓인 점이 어느 자식으로 갈지 규칙을 한 번 정하고(< 또는 <= 중 하나로) 모든 곳에서 같게 써야 한다. 삽입과 질의가 다른 규칙을 쓰면 있는 점을 못 찾는 유령 버그가 난다.
자식 8개를 항상 할당한다. 대부분의 옥트리는 자식 대다수가 비어 있다. 포인터 8개를 무조건 잡으면 메모리가 실제 필요량의 몇 배가 되고 캐시가 죽는다. 자식 존재 여부를 8비트 마스크로 들고 존재하는 것만 연속 배열에 두는 표현이 표준이며, SVO는 이 마스크 + 자식 블록 오프셋으로 노드 하나를 8바이트에 욱여넣는다.
동적 장면에서 매 프레임 전체 재구축. 옥트리는 국소 갱신이 어려운 편이다. 물체가 계속 움직인다면 경계 볼륨 계층의 refit 전략이 낫거나, 아예 모턴 키 정렬 기반의 GPU 재구축으로 가는 편이 낫다.

9. 관련 문서[편집]

공간 분할 자료구조 · KD-트리 · 경계 볼륨 계층 · 쿼드트리 · BSP 트리
공간 채움 곡선 · 기수 정렬 · 부하 분산 · 병렬 컴퓨팅
반스-헛 알고리즘 · 고속 다중극자법 · 적응 격자 세분화
충돌 감지 · 프러스텀 컬링 · 레이 트레이싱 · 전역 조명
마칭 큐브 · 볼륨 렌더링 · 레벨 오브 디테일 · 밉맵
메시 생성 · 점군 정합 · 최근접 이웃 탐색 · 격자

「점 두 개짜리 옥트리의 깊이가 40」은 농담이 아니라 현장에서 실제로 터진다. 레이저 스캐너가 같은 표면을 두 번 훑어 0.1 mm 떨어진 중복 점을 만들면, 그 둘을 갈라놓느라 트리가 지구 크기에서 밀리미터까지 내려간다. 점군 파이프라인이 옥트리를 짓기 전에 항상 복셀 다운샘플링부터 하는 이유. ↩
선형 쿼드트리·옥트리의 상수 시간 이웃 탐색은 슈락(1992)이 정리했다. 재귀로 짜면 스무 줄이고 캐리 트릭으로 짜면 두 줄인데, 두 줄짜리를 처음 보면 무슨 짓을 하는지 이해하는 데 스무 줄짜리를 짜는 것보다 오래 걸린다는 것이 이 바닥의 정서다. ↩
셀을 부풀린다는 것은 형제끼리 영역이 겹친다는 뜻이라, “공간 분할”이라는 이름을 스스로 배신하는 구조다. 그 대가로 얻는 것은 등록 레벨이 위치와 무관해진다는 성질 하나뿐인데, 프레임마다 수천 개가 움직이는 게임에서는 그 하나가 전부다. 이론적 순수성과 프레임 예산이 붙으면 이기는 쪽은 늘 정해져 있다. ↩

옥트리