Booil Jung

희소 복셀 옥트리(SVO)

3차원 공간을 디지털로 표현하고 처리하는 기술은 컴퓨터 그래픽스의 역사와 그 궤를 같이 해왔다. 수십 년간 이 분야의 지배적인 패러다임은 폴리곤 메시(Polygon Mesh)였다. 삼각형이나 사각형과 같은 다각형의 집합으로 객체의 표면(surface)을 근사하는 이 방식은, 현대의 그래픽 처리 장치(GPU)가 래스터라이제이션(rasterization)을 통해 극도로 효율적으로 처리할 수 있도록 설계되어 있어 실시간 렌더링의 표준으로 자리 잡았다. 하지만 표면 기반 표현 방식은 본질적인 한계를 내포한다. 객체의 내부나 부피에 대한 정보가 없으므로, 실시간으로 지형을 변형하거나 건물을 파괴하는 등의 동적인 상호작용을 구현하기가 매우 복잡하다. 이러한 연산은 표면 메시를 절단하고, 새로운 정점을 생성하며, 깨진 단면을 다시 삼각형으로 채우는(re-meshing) 복잡한 기하학적 알고리즘을 요구한다.

이러한 한계를 극복하기 위한 대안으로 복셀(Voxel, Volume-Pixel의 합성어) 표현 방식이 부상했다. 복셀은 2D의 픽셀을 3D로 확장한 개념으로, 객체의 표면이 아닌 부피(volume) 전체를 작은 정육면체 단위로 채워 표현한다.1 마인크래프트(Minecraft)와 같은 게임에서 볼 수 있듯이, 각 블록이 하나의 복셀에 해당하며, 이는 색상, 재질, 밀도 등 다양한 속성을 가질 수 있다. 복셀 표현의 가장 큰 장점은 공간적 질의(spatial query)와 수정이 직관적이고 간단하다는 점이다. 특정 위치의 복셀을 추가하거나 삭제하는 것은 단순히 3차원 배열의 특정 원소를 변경하는 문제로 귀결된다. 이는 복잡한 교차 연산과 표면 재구성 과정 없이도 동적인 월드를 손쉽게 구현할 수 있는 길을 열어주었다.1

그러나 복셀 표현 방식은 ‘조밀 복셀 그리드(Dense Voxel Grid)’라는 근본적인 문제에 직면했다. 3차원 배열을 사용하여 공간을 표현하는 가장 직관적인 이 방법은 해상도가 증가함에 따라 메모리 요구량이 기하급수적으로 폭증한다. 해상도가 N인 정육면체 공간을 표현하기 위해서는 $O(N^3)$의 메모리가 필요하다.2 예를 들어, 단지 1024x1024x1024 해상도의 공간을 표현하는 데에도 10억 개 이상의 복셀이 필요하며 3, 각 복셀이 1바이트의 정보만 가져도 1GB의 메모리가 소모된다. 이는 대규모 월드를 구현해야 하는 현대의 게임이나 시뮬레이션 환경에서는 실질적으로 사용 불가능한 수준이다.

이러한 메모리 문제에 대한 해결의 실마리는 3D 장면 대부분이 본질적으로 ‘희소(sparse)’하다는 관찰에서 시작되었다.1 광활한 하늘, 땅 속 깊은 곳, 건물의 내부 등 대부분의 공간은 비어있거나(empty) 혹은 단일한 물질로 균일하게(homogeneous) 채워져 있다. 이러한 희소성을 효율적으로 활용하기 위해 등장한 것이 바로 계층적 공간 분할(Hierarchical Spatial Partitioning) 자료 구조이며, 그중 가장 대표적인 것이 옥트리(Octree)이다. 옥트리는 3차원 공간을 재귀적으로 8개의 동일한 크기의 하위 공간, 즉 옥탄트(octant)로 분할하는 트리 구조이다.2

희소 복셀 옥트리(Sparse Voxel Octree, SVO)는 바로 이 옥트리 구조를 복셀 데이터에 적용하여 메모리 효율성을 극대화한 자료 구조이다.5 SVO의 핵심 아이디어는 균일한 공간을 더 이상 분할하지 않는 것이다. 만약 어떤 노드가 표현하는 공간 전체가 비어있거나, 혹은 단 하나의 물질로 가득 차 있다면, 그 노드는 8개의 자식 노드로 분할되지 않고 그 자체로 리프 노드(leaf node)가 된다.4 이 간단한 규칙 덕분에, 거대한 빈 공간이나 균일한 영역은 트리의 상위 레벨에 위치한 단 하나의 노드로 표현될 수 있다. 결과적으로 SVO는 월드의 크기에 비례하는 선형적인 메모리 대신, 월드 크기의 로그에 비례하는 메모리($\log$)만으로도 방대한 공간을 표현할 수 있게 된다.1 이는 지구 크기의 가상 세계를 만드는 데 있어 엄청난 이점을 제공한다.

이러한 SVO의 효율성은 근본적으로 3차원 공간이 가진 정보량의 불균일성을 자료 구조에 직접 반영한 결과로 해석될 수 있다. 조밀 그리드가 공간의 모든 지점에 동일한 정보량(예: 1바이트)을 할당하는, 즉 정보 엔트로피가 균일하다고 가정하는 방식이라면, SVO는 정보 엔트로피가 높은 영역과 낮은 영역을 차별적으로 다룬다. 복잡한 기하학적 구조가 밀집된 표면 근처(높은 엔트로피)는 트리의 가장 깊은 레벨까지 상세하게 분할되어 많은 비트가 할당되는 반면, 텅 빈 공간이나 균일한 재질의 내부(낮은 엔트로피)는 트리의 상위 레벨에 위치한 단일 노드, 즉 적은 비트로 간결하게 표현된다. 이러한 관점은 SVO가 왜 무작위적인 노이즈로 가득 찬, 즉 정보 엔트로피가 전체적으로 높은 장면에서는 압축 효율이 떨어지고 성능이 저하되는지에 대한 근본적인 이유를 설명해 준다.7 결국 조밀 그리드의 비효율성이라는 문제에서 출발하여, 3D 씬의 희소성이라는 특성을 관찰하고, 이를 계층적 분할이라는 아이디어로 해결한 것이 바로 희소 복셀 옥트리의 탄생 배경이라 할 수 있다.

희소 복셀 옥트리의 성능과 효율성은 그 내부 구조, 즉 노드를 어떻게 정의하고 메모리에 배치하는지에 따라 결정된다. SVO의 구조를 논리적, 물리적 관점에서 깊이 있게 분석하는 것은 이 자료 구조의 잠재력을 최대한 활용하기 위한 필수적인 과정이다.

SVO의 각 노드는 자신이 담당하는 3차원 공간 영역과 8개의 자식 노드에 대한 위상(topology) 정보를 담고 있다. 특히 비-리프 노드(non-leaf node)의 경우, 이 정보를 얼마나 압축적으로 효율적으로 저장하는지가 전체 SVO의 성능을 좌우한다.

이 분야에서 가장 널리 참조되는 구현 중 하나는 NVIDIA의 “Efficient Sparse Voxel Octrees” 연구에서 제안된 64비트 자식 디스크립터(Child Descriptor) 구조이다.8 이 구조는 GPU의 단일 메모리 읽기(single memory read) 연산으로 노드의 모든 위상 정보를 가져올 수 있도록 설계되어, 메모리 접근 지연 시간이 큰 GPU 환경에서 접근 횟수를 최소화하려는 의도가 담겨 있다. 이 64비트 디스크립터는 다음과 같은 비트 필드로 구성된다 8:

이러한 노드 디자인은 단순히 데이터를 저장하는 것을 넘어, 현대 하드웨어, 특히 GPU의 성능 특성을 최대한 활용하기 위한 치밀한 엔지니어링의 결과물이다. 메모리 접근 패턴과 데이터 관리의 유연성을 고려한 설계가 SVO의 실질적인 성능을 결정짓는 핵심 요소인 것이다.

SVO의 수많은 노드를 1차원 메모리 공간에 어떻게 배열하는가는 캐시 효율성과 직결되는 중요한 문제이다. 만약 공간적으로 인접한 노드들이 메모리 상에서는 멀리 떨어져 있다면, 트리 순회 시 불규칙적인 메모리 점프가 발생하여 캐시 미스(cache miss)가 빈번하게 일어나고 성능이 크게 저하될 것이다.7

이 문제를 해결하기 위해 모튼 코드(Morton Code) 또는 Z-order curve라는 공간 채움 곡선이 널리 사용된다.3 모튼 코드는 3차원 좌표 $(x, y, z)$의 각 비트를 인터리빙(interleaving)하여 하나의 1차원 값으로 매핑하는 기법이다. 예를 들어, 2차원 좌표 (x, y)가 이진수로 $(x_1x_0, y_1y_0)$일 때, 모튼 코드는 $y_1x_1y_0x_0$가 된다. 이 방식의 가장 중요한 특징은 3차원 공간에서 가까운 두 점이 1차원 모튼 코드 값으로 변환되었을 때도 높은 확률로 가까운 값을 유지한다는 것이다.

SVO 노드들을 모튼 코드 순서에 따라 메모리에 선형으로 배열하면 다음과 같은 장점을 얻는다 3:

  1. 데이터 지역성 향상: 공간적으로 인접한 노드들이 메모리 상에서도 인접하게 배치되어 캐시 효율성이 극대화된다.
  2. 효율적인 순회: 모튼 코드 순서는 옥트리의 깊이 우선 탐색(DFS) 순회 순서와 유사하여, 순차적인 메모리 접근 패턴을 유도한다.
  3. 스트리밍 기반 구축: 모튼 코드로 정렬된 복셀 데이터 스트림을 순차적으로 읽으면서 SVO를 상향식(bottom-up)으로 효율적으로 구축할 수 있다. 이는 전체 데이터를 메모리에 올릴 필요가 없는 외부 코어(Out-of-Core) 알고리즘의 기반이 된다.9

SVO에서 부모 노드와 자식 노드를 연결하는 방식은 크게 두 가지로 나뉜다.

SVO를 디스크에 저장하거나 네트워크를 통해 전송하기 위해서는 트리 구조를 선형적인 바이트 스트림으로 변환하는 직렬화 과정이 필요하다.5

일반적으로 깊이 우선 탐색(Depth-First Search, DFS) 순서로 트리를 순회하며 각 노드의 정보를 순차적으로 기록한다. DFS는 재귀 호출 대신 스택(stack) 자료 구조만으로 현재 순회 상태를 추적할 수 있어 메모리 사용량이 적고 구현이 비교적 간단하다는 장점이 있다.5

직렬화 과정에서는 다양한 인코딩 기법을 사용하여 압축 효율을 더욱 높일 수 있다. 예를 들어, 자식 노드가 없는 경우, 자식 노드가 단일 색상으로 채워진 경우, 자식 노드가 또 다른 서브트리를 가리키는 포인터인 경우 등을 구분하여 각기 다른 비트 패턴과 가변 길이 인코딩을 적용할 수 있다. 한 연구에서는 자식 포인터의 길이를 8비트, 16비트, 32비트로 다양화하여 포인터가 차지하는 공간을 최적화하는 기법(CSVO)을 제안하기도 했다.11

다음 표는 SVO 노드 구조에 대한 몇 가지 구체적인 구현 예시를 비교하여 보여준다.

구현 명칭 출처 총 비트 수 비트 필드 상세 핵심 아이디어
NVIDIA ESVO 8 64 valid_mask(8), leaf_mask(8), contour_mask(8), child_ptr(24), contour_ptr(8), far_ptr_flag(1), 기타(7) 자식 노드의 데이터(윤곽선, 셰이딩 속성)를 부모 노드에 함께 저장하여 리프 노드 할당을 최소화하고 압축 효율 증대.
CSVO (Internal Node) 11 가변 LCHNM(16), 가변 길이 포인터 (8/16/32) 자식 노드 포인터의 길이를 8, 16, 32비트로 가변적으로 사용하여 포인터 데이터의 크기를 최적화.
SVT-64 (64-tree) 12 96 (12 바이트) IsLeaf(1), ChildPtr(31), ChildMask(64) 8분할(옥트리) 대신 64분할(4x4x4)을 사용하여 트리의 깊이를 줄이고, 64비트 마스크를 활용하여 현대 아키텍처에 최적화.

이 표는 추상적인 SVO 개념이 실제 고성능 시스템에서 어떻게 구체적인 엔지니어링 결정으로 이어지는지를 명확히 보여준다. 개발자는 자신의 애플리케이션 요구사항(메모리, 속도, 동적 수정 용이성)에 따라 이러한 설계 옵션들 사이에서 최적의 균형점을 찾아야 한다.

SVO의 가치는 그것을 생성하고, 탐색하며, 변경하는 알고리즘의 효율성에 의해 결정된다. 이 세 가지 핵심 연산은 서로 밀접하게 연관되어 있으며, 하나의 최적화가 다른 연산의 성능에 영향을 미치는 트레이드오프 관계에 있다.

SVO를 생성하는 과정은 크게 두 가지 접근법으로 나뉜다: 폴리곤 메시로부터 생성하는 복셀화 과정과, 복셀 데이터로부터 트리를 조립하는 상향식/하향식 구축 과정이다.

대부분의 3D 애셋은 폴리곤 메시 형태로 존재하므로, 이를 SVO로 변환하는 첫 단계는 복셀화이다. 이는 메시의 기하학적 정보를 복셀 그리드로 변환하는 과정이다.

상향식 구축은 모튼 코드로 정렬된 리프 노드(복셀) 목록에서 시작하여 계층적으로 상위 레벨의 부모 노드를 생성해 나가는 방식이다.

하향식 구축은 루트 노드에서 시작하여 공간을 재귀적으로 분할하며 트리를 생성하는 방식이다.

SVO의 계층 구조를 탐색하는 순회 알고리즘은 렌더링, 경로 탐색 등 다양한 응용의 핵심이다.

SVO의 가장 대표적인 응용은 광선 추적을 통한 렌더링이다. SVO 순회 알고리즘의 기반은 Amanatides와 Woo가 제안한 ‘빠른 복셀 순회 알고리즘’이다.8

SVO는 AI 에이전트의 3D 공간 내비게이션을 위한 경로 탐색에도 활용될 수 있다. 이 경우 SVO는 공간의 비어있는 영역을 나타내는 거대한 연결 그래프로 간주된다.3

실시간 상호작용이 중요한 게임이나 시뮬레이션에서는 SVO를 동적으로 수정(복셀 추가/삭제)하는 기능이 필수적이다.

이처럼 SVO의 구축, 순회, 수정 알고리즘은 서로 긴밀하게 얽혀 있다. 빠른 순회를 위해 선택한 복잡하고 압축적인 노드 구조는 동적 수정 비용을 증가시킨다. 반대로, 빈번한 수정을 염두에 둔 단순한 구조는 초기 구축 시의 압축률이나 순회 성능을 희생시킬 수 있다. 따라서 SVO를 설계하고 구현하는 것은 하나의 정답을 찾는 과정이 아니라, 대상 애플리케이션의 요구사항(정적 렌더링, 동적 게임플레이 등)에 맞춰 이 세 가지 연산 간의 성능 트레이드오프에서 최적의 균형점을 찾는 정교한 엔지니어링 과정이라 할 수 있다.

SVO의 실용성은 다른 자료 구조와 비교했을 때의 상대적인 성능 우위에 따라 결정된다. 메모리 효율성, 캐시 성능, 그리고 특정 연산에 대한 속도를 중심으로 SVO의 성능을 분석하고, 조밀 그리드, 해시 테이블, BVH 등 주요 경쟁 기술과 비교한다.

SVO의 가장 두드러진 장점은 방대한 3D 공간을 극도로 압축하여 표현하는 능력이다. 특히 대부분이 비어있는 희소한(sparse) 씬에서 SVO는 조밀 그리드 대비 수백, 수천 배의 메모리 절약을 달성할 수 있다. 한 사례에서는 5억에서 50억 개에 해당하는 복셀 공간을 단 50~200MB의 SVO로 표현하기도 했다.4 이 압축 능력은 SVO가 대규모 월드를 실현 가능하게 만드는 핵심 동력이다.

그러나 이러한 메모리 효율성은 공짜가 아니다. SVO는 다음과 같은 내재적 비용과 한계를 가진다.

조밀 그리드는 가장 단순한 복셀 표현 방식으로, 3차원 배열을 사용한다. SVO와의 비교는 희소성과 접근성 사이의 근본적인 트레이드오프를 보여준다.

해시 테이블은 존재하는 복셀의 3D 좌표 $(x, y, z)$를 키(key)로, 복셀 데이터를 값(value)으로 저장하는 방식이다.10 이는 SVO와는 다른 방식으로 희소성을 다룬다.

BVH와 k-d 트리는 SVO와 마찬가지로 공간 분할을 이용한 계층적 자료 구조이지만, 그 목적과 분할 방식에 차이가 있다. 이들은 주로 폴리곤 메시와 같은 개별 객체들의 집합을 효율적으로 관리하기 위해 사용된다.

“어떤 자료 구조가 최고인가?”라는 질문은 사실상 의미가 없다. 더 올바른 질문은 “나의 데이터(희소성, 균일성, 동적성)와 나의 문제(렌더링, 충돌 감지, 시뮬레이션)에 가장 적합한 자료 구조는 무엇인가?”이다. SVO가 진정으로 빛을 발하는 경우는 복셀의 크기가 텍셀(texel) 수준으로 매우 작아지는 ‘마이크로 복셀’ 씬이다.4 이 경우 대부분의 공간이 비어있게 되어 SVO의 압축 능력이 극대화되며, 이는 id Tech 6 엔진이 추구했던 비전과도 일치한다.2 반면, 마인크래프트처럼 복셀이 거친(coarse) 경우에는 SVO의 계층 구조가 주는 이점보다 포인터 오버헤드와 순회 복잡성이 더 클 수 있어, 청크 단위의 조밀 배열과 RLE(Run-Length Encoding) 압축을 결합한 방식이 더 효율적일 수 있다.7

다음 표는 주요 공간 분할 자료 구조의 특성을 요약하여 비교한다. 이 표는 개발자가 자신의 프로젝트 요구사항에 맞는 최적의 기술을 선택하는 데 유용한 가이드가 될 것이다.

자료 구조 기본 원리 메모리 효율성 순회 속도 (광선 추적) 임의 접근 속도 동적 수정 비용 최적 사용 사례
조밀 그리드 3차원 배열 매우 낮음 느림 (모든 셀 검사) 매우 빠름 ($O(1)`) 매우 낮음 조밀하고 동적인 소규모 데이터 (예: 청크 내부)
SVO 계층적 공간 8분할 매우 높음 (희소 시) 빠름 (빈 공간 스킵) 느림 ($O(\log N)`) 중간~높음 희소한 대규모 복셀 월드, LOD, VCT
해시 테이블 좌표 기반 해싱 높음 (채워진 셀 비례) 매우 느림 (공간 정보 부재) 매우 빠름 (평균 $O(1)`) 매우 낮음 극도로 동적인 씬, 개별 복셀의 빠른 수정
BVH 객체 기반 계층적 그룹화 중간 (객체 수 비례) 매우 빠름 (객체 컬링) 해당 없음 중간 (트리 재구성) 폴리곤 메시 기반 광선 추적, 충돌 감지
k-d 트리 공간 기반 축 기준 이진 분할 중간 (객체 수 비례) 빠름 (객체 컬링) 해당 없음 높음 (트리 재구성) 정적 씬의 광선 추적 (주로 CPU)

SVO는 단순한 데이터 저장소를 넘어, 그 계층적 구조를 활용하여 기존에는 실시간으로 구현하기 어려웠던 고급 그래픽스 기법들을 가능하게 하는 강력한 프레임워크를 제공한다. SVO의 진정한 힘은 ‘다중 해상도 쿼리(Multi-resolution Query)’ 능력에 있다. 이는 필요한 곳에만 계산 자원을 집중하는 ‘적응형(adaptive)’ 처리를 가능하게 하여, 전역 조명, 실시간 그림자, 충돌 감지 등의 복잡한 연산을 효율적으로 수행할 수 있게 한다.

전역 조명(GI)은 광원에서 나온 빛이 장면에 있는 물체 표면에서 여러 번 반사되어 만들어내는 간접광(indirect light)까지 계산하여 극적인 사실감을 부여하는 기술이다.23 복셀 콘 트레이싱(Voxel Cone Tracing, VCT)은 SVO를 활용하여 이 복잡한 현상을 실시간으로 근사하는 대표적인 기법이다.

VCT의 작동 원리는 다음과 같은 단계로 이루어진다:

  1. 복셀화(Voxelization): 먼저, 렌더링할 3D 씬의 기하학적 정보와 재질 속성(반사율, 법선 벡터, 자체 발광 여부 등)을 SVO로 변환한다. 그리고 씬의 모든 광원으로부터 직접광을 계산하여, 빛을 받는 복셀에 그 방사휘도(radiance) 값을 저장한다. 이 과정은 씬의 라이팅 정보를 담고 있는 3차원 볼륨 데이터를 생성하는 것과 같다.24
  2. 밉맵 생성(Mip-mapping): 복셀화된 SVO에 대해 밉맵(mipmap) 계층을 생성한다. SVO의 각 상위 레벨 노드는 하위 8개 자식 노드의 평균적인 라이팅 정보를 담게 된다. 이는 마치 3D 텍스처에 밉맵을 생성하는 것과 같으며, 더 큰 공간 영역에 대한 저해상도의 필터링된 라이팅 정보를 제공하는 역할을 한다.24
  3. 콘 트레이싱(Cone Tracing): 마지막으로, 카메라 시점에서 씬을 렌더링할 때 각 픽셀(프래그먼트)에서 간접광을 계산한다. 전통적인 경로 추적(path tracing)이 수많은 개별 광선을 추적하는 대신, VCT는 원뿔(cone) 형태의 볼륨을 추적한다.
    • 원뿔은 픽셀 위치에서 특정 방향으로 뻗어 나가며, SVO를 따라 전진한다.
    • 원뿔이 전진하여 원점으로부터 멀어질수록 그 반경은 점점 커진다. VCT는 이 커지는 반경에 맞춰 SVO의 더 높은 밉맵 레벨(더 흐릿하고 넓은 영역의 정보)을 샘플링한다.
    • 이 과정을 통해 단일 원뿔 추적으로 수많은 광선을 쏘아 보낸 것과 유사한 적분 효과를 매우 저렴한 비용으로 근사할 수 있다.25

VCT는 간접광의 종류에 따라 다른 형태의 원뿔을 사용한다:

SVO를 사용하지 않고 조밀한 3D 텍스처로 VCT를 구현할 수도 있지만, 이 경우 막대한 GPU 메모리가 소모된다(예: 256³ 해상도에서 350MB 이상).25 SVO는 비어있는 공간을 효율적으로 건너뛰게 해주어 콘 트레이싱 과정의 성능을 크게 향상시키고 메모리 요구량을 줄이는 핵심적인 역할을 한다.27

전통적인 그림자 생성 기법인 그림자 맵(shadow map)은 해상도에 따른 앨리어싱(계단 현상)이나 그림자 경계의 부정확성(shadow acne)과 같은 고질적인 문제를 안고 있다.18 SVO 기반의 광선 추적은 이러한 문제에 대한 우아한 해결책을 제시한다.

알고리즘은 매우 직관적이다. 씬을 렌더링할 때, 표면의 각 지점에서 광원(light source)을 향해 그림자 광선(shadow ray)을 쏜다. 이 광선이 SVO를 순회하며 광원에 도달하기 전에 불투명한 복셀과 먼저 교차한다면, 해당 지점은 광원으로부터 가려져 있으므로 그림자 속에 있다고 판단한다.28

SVO의 계층 구조는 이 과정의 효율성을 극대화한다. 그림자 광선은 씬의 광활한 빈 공간을 트리의 상위 레벨 노드를 통해 단 몇 단계 만에 건너뛸 수 있으며, 복잡한 물체 근처에서만 하위 레벨로 내려가 정밀한 교차 검사를 수행한다. 이를 통해 하드 섀도우(hard shadow)는 물론, 여러 개의 광선을 쏘아 반그림자(penumbra) 영역을 샘플링함으로써 부드러운 그림자(soft shadow) 효과까지 실시간으로 구현할 수 있다.28

물리 시뮬레이션이나 게임에서 객체 간의 충돌을 감지하는 것은 매우 계산 비용이 높은 작업이다. N개의 객체에 대해 모든 쌍을 검사하는 무차별 대입 방식은 $O(N^2)$의 복잡도를 가져 비현실적이다. SVO는 이러한 충돌 감지 과정의 광역 단계(Broad-phase)에서 잠재적으로 충돌하지 않는 객체 쌍을 효율적으로 걸러내는(culling) 강력한 도구로 사용될 수 있다.29

계층적 충돌 감지 알고리즘은 다음과 같이 동작한다:

  1. 충돌을 감지할 두 객체(또는 객체 그룹)를 포함하는 SVO를 각각 생성하거나, 하나의 SVO에 두 객체를 모두 등록한다.
  2. 두 SVO의 루트 노드에서 시작하여, 두 트리를 동시에 재귀적으로(또는 스택 기반으로) 순회한다.31
  3. 만약 현재 단계에서 두 노드가 차지하는 공간(경계 상자)이 서로 겹치지 않는다면, 그 하위에 있는 모든 자식 노드들 역시 절대 충돌할 수 없다. 따라서 해당 서브트리 전체에 대한 검사를 생략하고 다음으로 넘어간다(가지치기).
  4. 만약 두 노드가 겹치고, 두 노드가 모두 최종 리프 노드라면, 이 리프 노드에 포함된 실제 기하학적 프리미티브(예: 삼각형, 복셀)에 대해 정밀한 충돌 검사(협역 단계, Narrow-phase)를 수행한다.

이러한 계층적 접근 방식은 계산량을 잠재적으로 충돌 가능한 영역에만 집중시켜 성능을 극적으로 향상시킨다.30 하지만 SVO는 축에 정렬된(axis-aligned) 분할 방식을 사용하므로, 회전하거나 빠르게 움직이는 동적 객체의 충돌을 정확하게 처리하는 데는 추가적인 기법이 필요하며, 때로는 어려움을 겪을 수 있다.19

SVO의 잠재력을 최대한 발휘하기 위해서는 현대 병렬 컴퓨팅의 핵심인 GPU(Graphics Processing Unit)에 효율적으로 구현하는 것이 필수적이다. GPU 기반 구현은 CPU의 재귀 호출 한계를 극복하고, 수천 개의 코어를 활용하여 SVO의 구축 및 순회 연산을 병렬로 처리하며, 대용량 데이터를 관리하기 위한 정교한 메모리 전략을 요구한다.

전통적인 트리 순회 알고리즘은 재귀(recursion)를 사용하여 간결하게 표현되지만, 이는 GPU 환경에 치명적인 약점을 가진다. 대부분의 GPU는 제한된 크기의 하드웨어 스택을 가지거나, 재귀 호출을 직접적으로 지원하지 않아 심각한 성능 저하를 유발한다.18

이 문제를 해결하기 위해, CPU의 암시적인 호출 스택을 GPU에서 명시적인 스택(stack)으로 시뮬레이션하는 비재귀적(non-recursive) 순회 방식이 사용된다. 이 방식은 일반적으로 고정된 크기의 배열을 스택으로 할당하여 작동한다 33:

  1. 순회를 시작할 때, 루트 노드에 대한 정보를 스택에 넣는다(push).
  2. 루프 내에서 스택의 최상단(top)에 있는 노드를 꺼내(pop) 처리한다.
  3. 만약 현재 노드가 내부 노드라면, 광선이 통과하는 자식 노드들의 정보를 계산하여 다시 스택에 넣는다. 이때, 광선이 자식 노드들을 통과하는 순서의 역순으로 스택에 넣어야 올바른 깊이 우선 탐색이 이루어진다.
  4. 만약 현재 노드가 리프 노드라면, 광선과 실제 데이터의 교차 판정을 수행한다.
  5. 스택이 빌 때까지 이 과정을 반복한다.

이러한 스택 기반의 비재귀적 순회는 GPU의 아키텍처에 완벽하게 부합하며, 고성능 SVO 구현의 표준적인 접근법으로 자리 잡았다.

NVIDIA의 CUDA(Compute Unified Device Architecture)와 같은 GPGPU(General-Purpose computing on GPU) 플랫폼은 SVO 관련 연산을 대규모로 병렬화할 수 있는 강력한 도구를 제공한다.

SVO 데이터는 수 기가바이트에 달할 수 있으므로, 제한된 GPU 메모리(VRAM)를 효율적으로 관리하는 전략이 매우 중요하다.

GPU 기반 SVO 구현의 핵심 과제는 하드웨어의 동작 방식을 깊이 이해하고, 병렬 처리의 효율을 저해하는 요소를 최소화하는 데 있다. GPU는 수십 개의 스레드를 하나의 ‘워프(Warp)’ 또는 ‘웨이브프론트(Wavefront)’라는 단위로 묶어 동일한 명령을 동시에 실행(SIMT, Single Instruction, Multiple Threads)한다. 이때 워프 내의 스레드들이 서로 다른 작업을 수행하게 되면 성능이 급격히 저하된다. 이러한 현상은 크게 두 가지로 나뉜다.

첫째는 제어 흐름 분기(Control Flow Divergence)이다. 만약 워프 내의 일부 스레드(광선)는 SVO의 빈 공간을 통과하고 다른 스레드는 물체를 통과하여 if-else 문에서 서로 다른 코드 경로를 타게 되면, GPU는 두 경로를 모두 순차적으로 실행하고 해당되지 않는 스레드들을 비활성화시켜야 한다. 이는 워프의 실행 효율을 절반 또는 그 이하로 떨어뜨리는 심각한 병목 현상이다.

둘째는 메모리 접근 비일관성(Memory Access Divergence)이다. 워프 내의 스레드들이 메모리 상에서 서로 멀리 떨어진 위치(예: SVO의 완전히 다른 부분에 있는 노드들)에 접근하면, 메모리 컨트롤러는 여러 번의 개별적인 메모리 트랜잭션을 발생시켜야 한다. 이는 인접한 메모리 주소들을 한 번의 트랜잭션으로 묶어서 읽어오는 ‘병합된 접근(coalesced access)’에 비해 훨씬 비효율적이다.

결국, Laine과 Karras의 알고리즘 33, 모튼 코드 정렬 3, 데이터 블록화 8 등 GPU를 위한 모든 SVO 최적화 기법들은 근본적으로 이 두 가지 분기 문제를 해결하려는 시도라고 볼 수 있다. 광선들을 방향에 따라 미리 정렬하거나(ray sorting), 데이터 레이아웃을 최적화하여 인접한 픽셀에서 시작된 광선들이 최대한 SVO의 비슷한 부분을 비슷한 순서로 순회하도록 유도하는 것이 핵심 목표이다. 이를 통해 제어 흐름과 메모리 접근 패턴을 최대한 일관성 있게 만들어 GPU의 병렬 처리 능력을 100%에 가깝게 활용하는 것이 고성능 SVO 구현의 관건이다.

SVO는 희소한 공간을 압축하는 데 탁월한 성능을 보이지만, 그 구조적 특성상 명백한 압축의 한계를 가지고 있다. 이러한 한계를 극복하기 위해 SVO의 개념을 일반화한 희소 복셀 방향성 비순환 그래프(SVDAG)가 등장했으며, 이는 복셀 표현 기술의 새로운 지평을 열었다.

SVO의 압축 원리는 ‘비어있는 공간’을 효율적으로 표현하는 데 있다. 그러나 만약 공간이 비어있지는 않지만, 동일한 구조가 반복적으로 나타나는 경우에는 압축 효과를 전혀 발휘하지 못한다. 예를 들어, 동일한 디자인의 창문이 여러 개 있는 건물이나, 같은 패턴의 벽돌로 이루어진 벽을 생각해 보자. SVO에서는 이 창문이나 벽돌 패턴이 공간적으로 서로 다른 위치에 존재하기 때문에, 각각을 완전히 별개의 독립적인 서브트리(subtree)로 저장해야만 한다. 이로 인해 ‘구조적 중복성(structural redundancy)’이 데이터 내에 그대로 남아있게 된다.34

희소 복셀 방향성 비순환 그래프(SVDAG)는 이러한 SVO의 한계를 극복하기 위해 제안된 자료 구조이다. 그 핵심 아이디어는 매우 간단하면서도 강력하다: “완벽하게 동일한 구조를 가진 서브트리는 단 한 번만 저장하고, 여러 부모 노드가 이 공유된 서브트리를 함께 가리키도록 허용한다.”.28

이러한 공유를 허용하는 순간, 자료 구조는 더 이상 엄격한 의미의 트리(tree)가 아니라, 여러 부모를 가질 수 있는 노드가 존재하는 방향성 비순환 그래프(Directed Acyclic Graph, DAG)가 된다.

이러한 SVO에서 SVDAG로의 진화는 데이터 압축의 패러다임이 ‘공간적 희소성’의 활용에서 ‘구조적 중복성’의 활용으로 확장되었음을 의미한다. 이는 컴퓨터 과학의 다른 분야에서 발견되는 일반적인 패턴과 유사하다. 예를 들어, 텍스트 압축에 사용되는 Lempel-Ziv(LZ) 계열 알고리즘은 반복적으로 나타나는 문자열을 사전(dictionary)에 저장하고 포인터로 대체하는 방식을 사용하는데, SVDAG는 본질적으로 3D 공간에 대한 Lempel-Ziv 압축의 한 형태로 볼 수 있다. 이 패러다임의 전환은 단순히 메모리를 절약하는 것을 넘어, 3D 콘텐츠 제작 방식 자체에 영향을 미칠 잠재력을 가진다. 아티스트들은 메모리 제약에서 훨씬 자유로워져, 반복적인 모듈과 패턴을 사용하여 이전에는 상상할 수 없었던 규모와 복잡도를 가진 가상 세계를 구축할 수 있게 된다.

SVDAG의 압축 효율성은 실제 데이터 비교를 통해 명확하게 확인할 수 있다. Kämpe 등이 발표한 SVDAG 논문에서는 유명한 테스트 씬인 ‘Epic Citadel’을 다양한 해상도로 복셀화하여 SVO와 SVDAG의 메모리 사용량을 비교했다.28

해상도 SVO 메모리 (MB) SVDAG 메모리 (MB) SVDAG 절감률 (%)
2K³ 2 3 -50.0%
4K³ 5 7 -40.0%
8K³ 20 19 5.0%
16K³ 81 53 34.6%
32K³ 324 142 56.2%
64K³ 1301 371 71.5%
128K³ 5100 (추정) 945 81.5% (추정)

데이터 출처:.28 128K³ SVO 데이터는 메모리 부족으로 구축되지 못했음.

이 표는 SVDAG의 위력을 명확히 보여준다. 저해상도에서는 포인터 구조의 복잡성으로 인해 SVDAG가 오히려 약간 더 많은 메모리를 사용할 수 있으나, 해상도가 8K³ 이상으로 높아지면서 SVDAG의 압축 효율이 SVO를 압도하기 시작한다. 특히 64K³ 해상도에서는 SVO 대비 70% 이상의 메모리를 절약하는 놀라운 결과를 보여준다. 이는 고해상도, 고품질 복셀 렌더링에서 SVDAG가 필수적인 기술임을 시사한다.

SVO와 SVDAG를 기반으로 한 연구는 지금도 계속해서 발전하고 있다.

희소 복셀 옥트리(SVO)는 3차원 공간을 표현하는 방식에 있어 중요한 이정표를 제시한 자료 구조이다. 조밀 그리드의 엄청난 메모리 요구량이라는 근본적인 한계를 ‘희소성’이라는 개념을 통해 극복함으로써, 이전에는 불가능했던 규모의 가상 세계를 실시간으로 다룰 수 있는 가능성을 열었다. 본 보고서는 SVO의 기본 원리부터 구조, 핵심 알고리즘, 성능 특성, 그리고 SVDAG로의 진화에 이르기까지 그 전반을 심층적으로 분석했다. 이를 바탕으로 SVO에 대한 종합적인 평가와 미래 전망을 제시하며 결론을 맺는다.

SVO의 기술적 가치는 그 명확한 장점과 뚜렷한 한계의 공존 속에서 이해되어야 한다.

SVO는 만능 해결책이 아니라, 특정 문제 영역에서 강력한 성능을 발휘하는 전문화된 도구로 자리매김하고 있다. 특히 실시간 복셀 기반 렌더링 분야에서 그 중요성은 여전히 유효하다. 복셀 콘 트레이싱(VCT)을 이용한 실시간 전역 조명이나 광선 추적 기반 그림자 구현에 있어 SVO는 핵심적인 가속 구조로 활용된다.

하지만 SVO가 항상 최선의 선택은 아니다. 씬의 특성(정적/동적, 희소/조밀, 거친/미세 복셀)과 주된 연산의 종류(렌더링/수정/임의 접근)에 따라 조밀 그리드, 해시 테이블, BVH 등과 경쟁하거나 혹은 이들과 결합된 하이브리드 형태로 사용되어야 최적의 성능을 얻을 수 있다. SVO의 ‘최적성’은 절대적인 것이 아니라, 문제의 맥락에 따라 결정되는 상대적인 개념이다.

SVO와 그 파생 기술들은 앞으로도 계속해서 발전해 나갈 것으로 전망된다.

  1. 압축 기술의 고도화: SVDAG를 넘어, 손실 압축 기법과의 결합 37이나 대칭성(symmetry)을 활용하는 등 새로운 차원의 중복성을 찾아내어 압축률을 극한까지 높이려는 연구가 계속될 것이다.
  2. 동적 환경 지원 강화: GPU 기반 해시 테이블을 활용하여 SVDAG를 실시간으로 편집하는 연구 34와 같이, 동적 환경에서의 수정 비용을 낮추는 알고리즘이 주요 연구 주제가 될 것이다. 정적 씬의 렌더링과 동적 객체의 상호작용을 효율적으로 결합하는 하이브리드 시스템이 더욱 정교해질 것이다.
  3. 하드웨어 아키텍처와의 융합: 64-tree 5처럼 현대 CPU/GPU 아키텍처에 더 친화적인 새로운 계층 구조에 대한 탐구가 지속될 것이다. 또한, RTX 코어와 같은 전용 하드웨어 가속기를 SVO/SVDAG 순회에 직접적으로 활용하여 성능을 비약적으로 향상시키는 방안이 모색될 것이다.
  4. 응용 분야의 확장: SVO는 렌더링을 넘어 물리 시뮬레이션, AI를 위한 3D 비행 경로 탐색 3, 그리고 CT나 MRI와 같은 3D 의료 영상 데이터의 효율적인 시각화 및 분석 39 등 다양한 분야로 그 응용 범위를 넓혀가며, 3차원 공간 데이터를 다루는 보편적인 핵심 기술 중 하나로 그 위상을 공고히 할 것이다.

결론적으로, 희소 복셀 옥트리는 3D 데이터 처리의 근본적인 문제에 대한 우아하고 강력한 해법을 제시했으며, SVDAG로의 진화를 통해 그 잠재력을 더욱 확장했다. 앞으로도 하드웨어의 발전과 새로운 알고리즘의 등장 속에서 끊임없이 진화하며 미래의 디지털 세계를 구축하는 데 핵심적인 역할을 수행할 것으로 기대된다.

  1. 시작: 희소 복셀 옥트리 : r/rust_gamedev - Reddit, accessed August 4, 2025, https://www.reddit.com/r/rust_gamedev/comments/2zy20e/started_sparse_voxel_octree/?tl=ko
  2. what are sparse voxel octrees? - Stack Overflow, accessed August 4, 2025, https://stackoverflow.com/questions/985893/what-are-sparse-voxel-octrees
  3. 3D Flight Navigation Using Sparse Voxel Octrees - Game AI Pro, accessed August 4, 2025, http://www.gameaipro.com/GameAIPro3/GameAIPro3_Chapter21_3D_Flight_Navigation_Using_Sparse_Voxel_Octrees.pdf
  4. Sparse Voxel Octrees? : r/VoxelGameDev - Reddit, accessed August 4, 2025, https://www.reddit.com/r/VoxelGameDev/comments/7hg7p4/sparse_voxel_octrees/
  5. Sparse Voxel Octree, accessed August 4, 2025, https://eisenwave.github.io/voxel-compression-docs/svo/svo.html
  6. What’s the difference between a ‘regular’ octree and a ‘sparse voxel octree?’ - Reddit, accessed August 4, 2025, https://www.reddit.com/r/VoxelGameDev/comments/16u132r/whats_the_difference_between_a_regular_octree_and/
  7. Are sparse voxel octrees really (always) the best voxel data structure? : r/VoxelGameDev, accessed August 4, 2025, https://www.reddit.com/r/VoxelGameDev/comments/1jb8uol/are_sparse_voxel_octrees_really_always_the_best/
  8. Efficient Sparse Voxel Octrees – Analysis, Extensions, and Implementation - Research at NVIDIA, accessed August 4, 2025, https://research.nvidia.com/sites/default/files/pubs/2010-02_Efficient-Sparse-Voxel/laine2010tr1_paper.pdf
  9. Out-of-Core Construction of Sparse Voxel Octrees - Computer …, accessed August 4, 2025, https://graphics.cs.kuleuven.be/publications/BLD14OCCSVO/BLD14OCCSVO_paper.pdf
  10. How to design a Sparse Voxel Octree : r/VoxelGameDev - Reddit, accessed August 4, 2025, https://www.reddit.com/r/VoxelGameDev/comments/ke6r11/how_to_design_a_sparse_voxel_octree/
  11. CSVO: Clustered Sparse Voxel Octrees-A Hierarchical Data Structure for Geometry Representation of Voxelized 3D Scenes - MDPI, accessed August 4, 2025, https://www.mdpi.com/2073-8994/14/10/2114
  12. A guide to fast voxel ray tracing using sparse 64-trees - GitHub Pages, accessed August 4, 2025, https://dubiousconst282.github.io/2024/10/03/voxel-ray-tracing/
  13. byumjin/Vulkan-VXGI-VR-FrameWork - GitHub, accessed August 4, 2025, https://github.com/byumjin/Vulkan-VXGI-VR-FrameWork
  14. DYNAMIC UPDATE OF SPARSE VOXEL OCTREE BASED ON MORTON CODE, accessed August 4, 2025, https://hammer.purdue.edu/ndownloader/files/27771012
  15. A Fast Voxel Traversal Algorithm for Ray Tracing, accessed August 4, 2025, http://www.cse.yorku.ca/~amana/research/grid.pdf
  16. (PDF) A Fast Voxel Traversal Algorithm for Ray Tracing - ResearchGate, accessed August 4, 2025, https://www.researchgate.net/publication/2611491_A_Fast_Voxel_Traversal_Algorithm_for_Ray_Tracing
  17. Amanatides and Woo’s fast Voxel Traversal - MΛX, accessed August 4, 2025, https://m4xc.dev/articles/amanatides-and-woo/
  18. Sparse Voxel Octrees - Development Blog - Leadwerks Community, accessed August 4, 2025, https://www.leadwerks.com/community/blogs/entry/2736-sparse-voxel-octrees/
  19. Sparse Voxel Octrees - YouTube, accessed August 4, 2025, https://www.youtube.com/watch?v=NjCp-HIZTcA
  20. An evaluation of Kd-Trees vs Bounding Volume Hierarchy (BVH) acceleration structures in modern CPU architectures - Redalyc, accessed August 4, 2025, https://www.redalyc.org/journal/6998/699875484008/html/
  21. Performance Comparison of Bounding Volume Hierarchies and Kd-trees for GPU Ray Tracing, accessed August 4, 2025, https://dcgi.fel.cvut.cz/home/bittner/publications/vinklerCGF2015B.pdf
  22. When would you use an octree in a voxel Engine? - Game Development Stack Exchange, accessed August 4, 2025, https://gamedev.stackexchange.com/questions/70831/when-would-you-use-an-octree-in-a-voxel-engine
  23. EVALUATION OF PERFORMANCE AND IMAGE QUALITY FOR VOXEL CONE TRACING - DiVA portal, accessed August 4, 2025, https://www.diva-portal.org/smash/get/diva2:1637733/FULLTEXT01.pdf
  24. Interactive Indirect Illumination Using Voxel-Based Cone Tracing: An Insight - ResearchGate, accessed August 4, 2025, https://www.researchgate.net/publication/220721533_Interactive_Indirect_Illumination_Using_Voxel-Based_Cone_Tracing_An_Insight
  25. Voxel Cone Traced Global Illumination - Leif Node, accessed August 4, 2025, https://leifnode.com/2015/05/voxel-cone-traced-global-illumination/
  26. Documentation - Environment Editor - CRYENGINE, accessed August 4, 2025, https://www.cryengine.com/docs/static/engines/cryengine-5/categories/23756816/pages/56658466
  27. Gi = global illumination PDF 3-D Graphics Computer Software and Applications, accessed August 4, 2025, https://www.slideshare.net/slideshow/gi-global-illumination/27926938
  28. High Resolution Sparse Voxel DAGs, accessed August 4, 2025, https://icg.gwu.edu/sites/g/files/zaxdzs6126/files/downloads/highResolutionSparseVoxelDAGs.pdf
  29. A literature review of bounding volumes hierarchy focused on collision detection, accessed August 4, 2025, http://www.scielo.org.co/scielo.php?script=sci_arttext&pid=S0123-30332015000100005
  30. Octree-based Collision Detection in iMSTK - Kitware, Inc., accessed August 4, 2025, https://www.kitware.com/octree-collision-imstk/
  31. An Architecture for Hierarchical Collision Detection ∗ - CiteSeerX, accessed August 4, 2025, https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&doi=c5535731aeb5ad2c7d0964e8501c782d58612a0d
  32. Collision detection - Wikipedia, accessed August 4, 2025, https://en.wikipedia.org/wiki/Collision_detection
  33. GPU SVO algorithm resources? : r/VoxelGameDev - Reddit, accessed August 4, 2025, https://www.reddit.com/r/VoxelGameDev/comments/196no8t/gpu_svo_algorithm_resources/
  34. Editing Compact Voxel Representations on the GPU - Eurographics Association, accessed August 4, 2025, https://diglib.eg.org/bitstream/handle/10.2312/pg20241310/pg20241310.pdf
  35. GPU-Accelerated Ray Tracing for Visualizing Monte Carlo Models - EPJ Web of Conferences, accessed August 4, 2025, https://www.epj-conferences.org/articles/epjconf/pdf/2024/12/epjconf_snamc2024_11001.pdf
  36. Forceflow/ooc_svo_builder: Out-Of-Core Construction of Sparse Voxel Octrees - GitHub, accessed August 4, 2025, https://github.com/Forceflow/ooc_svo_builder
  37. Delft University of Technology Lossy Geometry Compression for High Resolution Voxel Scenes, accessed August 4, 2025, https://pure.tudelft.nl/ws/files/90809458/LossyGeometryCompressionForHighResolutionVoxelScenes.pdf
  38. Building a High-Performance Voxel Engine in Unity: A Step-by-Step Guide Part 6: High Resolution Sparse Voxel DAGs - Medium, accessed August 4, 2025, https://medium.com/@adamy1558/building-a-high-performance-voxel-engine-in-unity-a-step-by-step-guide-part-6-high-resolution-e0217efd56d2
  39. Silicon Valley Medical Imaging – Providing Clarity, accessed August 4, 2025, https://svmedicalimaging.com/
  40. Medical imaging - Wikipedia, accessed August 4, 2025, https://en.wikipedia.org/wiki/Medical_imaging
  41. Medical Imaging Toolbox - MATLAB - MathWorks, accessed August 4, 2025, https://www.mathworks.com/products/medical-imaging.html