3차원 공간 데이터를 효율적으로 저장, 검색, 그리고 관리하는 기술은 현대 컴퓨터 과학의 여러 분야에서 핵심적인 과제로 자리 잡았다. 컴퓨터 그래픽스, 로봇 공학, 지리 정보 시스템(GIS), 자율 주행, 물리 시뮬레이션, 그리고 가상현실에 이르기까지, 방대한 양의 공간 정보를 실시간으로 처리하는 능력은 응용 프로그램의 성능과 직결된다. 이러한 데이터는 수백만 개에서 수십억 개에 이르는 점(point)이나 복셀(voxel)로 구성될 수 있으며, 이를 단순한 선형 배열에 저장하고 필요한 정보를 찾기 위해 순차적으로 탐색하는 소박한(naive) 접근법은 데이터의 양이 증가함에 따라 기하급수적으로 비효율적이 된다. 예를 들어, 특정 지점의 최근접 이웃(nearest neighbor)을 찾거나 특정 범위 내의 모든 점을 찾는 질의는 데이터셋의 모든 원소를 검사해야 하므로, 데이터의 개수가 N일 때 각각 O(N) 또는 $O(N^2)$의 시간 복잡도를 가지게 된다.1 이는 대규모 데이터셋에서는 실용적으로 사용될 수 없는 수준의 비효율성이다.
이러한 근본적인 한계를 극복하기 위해 공간 분할(Spatial Partitioning) 자료구조가 개발되었다. 공간 분할 자료구조의 핵심 철학은 거대한 탐색 공간을 관리하기 쉬운 작은 부분 공간으로 계층적으로 또는 균일하게 나누는 데 있다.1 공간을 분할함으로써, 특정 질의와 관련 없는 대부분의 데이터 영역을 탐색 과정에서 배제(pruning)할 수 있다. 이 원리를 통해 탐색 연산의 시간 복잡도를 평균적으로 로그 시간($O(logN)$)이나 경우에 따라서는 거의 상수 시간(O(1))에 가깝게 단축시킬 수 있으며, 이는 대규모 3차원 데이터의 실시간 처리를 가능하게 하는 핵심 기술이다.1
본 보고서는 점 데이터(point data)부터 희소(sparse) 및 밀집(dense) 복셀 데이터에 이르기까지 다양한 유형의 3차원 공간 데이터를 처리하기 위해 지난 수십 년간 제안되고 발전해 온 핵심적인 공간 분할 자료구조들을 심층적으로 비교하고 고찰하는 것을 목적으로 한다. 분석 대상은 학계와 산업계에서 중요하게 다루어지는 10가지 자료구조로, 다음과 같다:
본 보고서는 각 자료구조의 단순한 기능적 설명을 넘어, 그 기저에 깔린 수학적 원리와 알고리즘적 특성, 성능상의 장단점, 그리고 특정 응용 분야에 적합하게 된 진화적 맥락을 깊이 있게 파헤칠 것이다.
보고서는 독자의 이해를 돕기 위해 논리적 흐름에 따라 구성된다. 먼저 가장 기초가 되는 점 기반 공간 분할 구조인 kd-tree와 Octree를 분석하여 공간 분할의 두 가지 근본적인 접근법을 제시한다. 이후, 컴퓨터 그래픽스와 시각 효과(VFX) 분야에서 대두된 메모리 효율성 문제를 해결하기 위해 등장한 고도로 압축된 복셀 구조인 SVO, SVDAG, VDB를 다룬다. 다음으로, 로보틱스와 자율 주행 분야의 실시간 요구사항을 충족시키기 위해 극단적인 동적 업데이트 성능에 초점을 맞춰 발전한 동적 균형 Octree, iVox, RC-Vox를 분석한다.
각 자료구조에 대해 핵심 원리, 주요 연산 알고리즘, 시간 및 공간 복잡도, 그리고 주요 응용 분야를 상세히 기술한다. 마지막 장에서는 이 모든 분석을 종합하여, 10가지 자료구조의 성능과 특성을 다각적으로 비교하는 종합 표를 제시하고, 메모리 압축과 동적 업데이트 속도라는 두 가지 핵심 축을 기준으로 자료구조들을 그룹화하여 심층 분석한다. 최종적으로, 특정 응용 시나리오에 가장 적합한 자료구조를 선택할 수 있도록 실용적인 가이드라인을 제공하며 보고서를 마무리한다.
공간 분할 자료구조의 세계를 이해하기 위해서는 가장 근본이 되는 두 가지 구조, 즉 kd-트리와 옥트리에 대한 깊이 있는 이해가 선행되어야 한다. 이 두 구조는 공간을 분할하는 방식에서 근본적인 차이를 보이며, 이후에 등장하는 수많은 파생 및 고급 자료구조들의 사상적 기반을 형성한다. 본 장에서는 이 두 기초적인 구조의 원리, 성능 특성, 그리고 그 변형들을 상세히 분석한다.
k-d 트리는 다차원 공간에서의 점 데이터를 효율적으로 구성하고 검색하기 위해 설계된 가장 대표적인 공간 분할 자료구조 중 하나이다.
k-d 트리(k-dimensional tree)는 k-차원 공간에 분포된 점들을 저장하기 위한 이진 공간 분할(Binary Space Partitioning, BSP) 트리의 한 종류이다.4 k-d 트리의 각 비-리프 노드(non-leaf node)는 하나의 k-차원 점 데이터를 저장하며, 이 점을 통과하고 특정 축(axis)에 수직인 초평면(hyperplane)을 기준으로 공간을 두 개의 하위 공간(half-space)으로 분할한다.5 이 분할 기준이 되는 축을 ‘판별자(discriminator)’라고 부르며, 일반적으로 트리의 깊이(depth)에 따라 각 차원을 순환적으로 선택한다.6 예를 들어, 3차원 공간에서는 루트 노드에서 x축, 그 자식 노드들에서 y축, 손자 노드들에서 z축, 그리고 다시 x축으로 순환하는 방식이 널리 사용된다.8
이러한 분할 방식의 가장 중요한 특징은 분할 경계가 저장된 데이터의 분포에 따라 결정된다는 점이다. 즉, k-d 트리는 데이터 종속적(data-dependent) 분할 방식을 채택한다.9 이는 데이터가 밀집된 영역은 더 세밀하게, 희소한 영역은 더 넓게 분할하여 데이터 분포에 적응적인 공간 분할을 가능하게 한다.
k-d 트리의 성능은 트리의 균형 상태에 크게 좌우되며, 주요 연산은 다음과 같다.
구축 (Construction): 정적 k-d 트리를 구축하는 가장 일반적인 방법은 각 레벨에서 해당 분할 축을 기준으로 점들의 중앙값(median)을 찾아 피벗(pivot)으로 삼는 것이다. 이 피벗 점을 현재 노드에 저장하고, 피벗보다 작은 값들을 갖는 점들은 왼쪽 서브트리로, 큰 값들을 갖는 점들은 오른쪽 서브트리로 보내는 과정을 재귀적으로 반복한다.4 중앙값을 사용하면 각 분할에서 점들이 거의 절반씩 나뉘므로, 결과적으로 깊이가 $O(\log N)$에 가까운 비교적 균형 잡힌 트리를 생성할 수 있다. 매 레벨에서 중앙값을 찾기 위해 정렬을 사용하면 구축 시간 복잡도는 $O(N \log^2 N)$이 되며, 선형 시간 중앙값 찾기 알고리즘(median of medians)을 사용하면 $O(N \log N)$으로 최적화할 수 있다.5
탐색 (Search): 특정 점을 찾는 탐색 연산은 이진 탐색 트리(BST)와 매우 유사하다. 루트 노드부터 시작하여, 현재 노드의 깊이에 해당하는 분할 축 값을 기준으로 찾고자 하는 점의 좌표와 노드의 좌표를 비교한다. 찾고자 하는 점의 값이 노드의 값보다 작으면 왼쪽 자식으로, 크면 오른쪽 자식으로 이동하는 과정을 반복한다.4 균형 잡힌 트리에서의 평균 탐색 시간 복잡도는 $O(\log N)$이다.11
삽입 및 삭제 (Insertion and Deletion): 새로운 점의 삽입은 탐색과 유사한 과정을 통해 적절한 위치를 찾아 리프 노드로 추가하는 방식으로 이루어진다. 평균 시간 복잡도는 $O(\log N)$이다.4 그러나 반복적인 삽입은 트리의 불균형을 초래하여 최악의 경우 성능을 $O(N)$으로 저하시킬 수 있다. 삭제 연산은 더 복잡하다. 삭제할 노드가 리프 노드이면 간단히 제거할 수 있지만, 내부 노드일 경우 해당 노드의 서브트리에서 적절한 대체 노드(예: 해당 분할 축 기준의 최소값)를 찾아 그 자리를 메우고, 대체 노드를 원래 위치에서 삭제하는 과정이 필요하다. 이 과정은 서브트리의 구조를 유지해야 하므로 복잡하며, 균형을 유지하기 위한 추가적인 재구성 작업이 필요할 수 있다.4 균형이 잘 잡힌 트리에서의 삭제 연산은 평균적으로 $O(\log N)$의 시간 복잡도를 가진다.5
최근접 이웃(k-NN) 및 반경 탐색 (Range Search): k-d 트리의 가장 강력하고 핵심적인 응용 분야는 최근접 이웃 탐색(k-Nearest Neighbors, k-NN)과 반경 탐색(Range Search)이다.5
k-NN 탐색: 특정 질의점(query point)에 가장 가까운 k개의 점을 찾는 연산이다. 먼저 일반적인 탐색 방식으로 질의점이 속할 리프 노드까지 내려간다. 이후, 재귀적으로 부모 노드로 거슬러 올라가는 백트래킹(backtracking) 과정을 수행한다. 각 노드에서, 현재까지 찾은 가장 가까운 점과의 거리를 반지름으로 하는 구(hypersphere)와 현재 노드의 분할 평면이 교차하는지 확인한다. 만약 교차한다면, 분할 평면 반대편의 서브트리에도 더 가까운 점이 존재할 가능성이 있으므로 해당 서브트리를 추가로 탐색한다. 이 과정을 통해 탐색 공간을 효율적으로 가지치기(pruning)할 수 있다. 평균 시간 복잡도는 $O(\log N)$이지만, 데이터의 차원이 높아질수록 성능이 저하된다.5
반경 탐색: 특정 질의점을 중심으로 주어진 반경 내에 포함되는 모든 점을 찾는 연산이다. k-NN 탐색과 유사하게, 질의 구와 노드가 나타내는 공간 영역이 교차하는 경우에만 해당 서브트리를 탐색한다. 3차원 데이터의 경우, 시간 복잡도는 $O(N^{2/3} + m)$으로 알려져 있으며, 여기서 m은 반경 내에 발견된 점의 수이다.5 이 복잡도 공식은 k-d 트리가 ‘차원의 저주(curse of dimensionality)’에 취약함을 보여준다. 즉, 차원
k가 증가할수록 성능이 지수적으로 저하되어 고차원 공간에서는 선형 탐색과 다를 바 없어질 수 있다.
정적인 k-d 트리는 데이터셋이 변하지 않는 경우에 효과적이지만, 점의 삽입과 삭제가 빈번하게 발생하는 동적 환경에서는 심각한 성능 저하를 겪을 수 있다. 반복적인 삽입과 삭제는 트리의 균형을 깨뜨려 깊이가 비정상적으로 길어지게 만들고, 이는 탐색 성능을 최악의 경우 선형 시간(O(N))으로 떨어뜨린다. 이러한 문제를 해결하기 위해 등장한 것이 i-kd-tree (incremental k-d tree)이다.
i-kd-tree는 특히 실시간 LiDAR SLAM(Simultaneous Localization and Mapping)과 같은 응용 분야에서 그 중요성이 부각되었다. 예를 들어, Fast-LIO2 시스템에서는 주변 환경을 매핑하기 위해 지속적으로 들어오는 LiDAR 포인트 클라우드를 처리해야 하는데, 매 스캔마다 전체 k-d 트리를 재구축하는 것은 엄청난 계산 비용을 유발한다.13 i-kd-tree는 이러한 비효율성을 해결한다.
핵심 메커니즘은 전체 재구축을 피하고, 삽입 또는 삭제 연산이 발생했을 때 트리의 균형을 동적으로 유지하는 것이다. 이는 특정 서브트리의 크기나 깊이가 임계값을 초과하면 해당 서브트리만 재귀적으로 재구축하는 부분 재구축(partial rebuilding) 기법이나, 트리 회전(tree rotation)과 유사한 기법을 통해 구현될 수 있다. 이러한 증분 업데이트(incremental update) 방식을 통해, i-kd-tree는 동적인 데이터 변화 속에서도 트리의 깊이를 O(logN) 수준으로 유지하며, 삽입, 삭제, 검색 연산의 평균 시간 복잡도를 로그 시간으로 보장한다. 이는 실시간 응용에서 필수적인 빠른 업데이트 속도와 꾸준한 검색 성능을 동시에 만족시키는 핵심적인 역할을 한다.14
k-d 트리의 또 다른 흥미로운 변형은 Implicit k-d tree이다. 이 구조는 k-d 트리의 위상(topology), 즉 분할 평면의 위치와 방향을 메모리에 명시적으로 저장하지 않는다.5 대신, 기저에 깔린 정형 격자(rectilinear grid) 위에서 사전에 정의된 재귀적인 분할 함수(splitting function)를 통해 암시적으로(implicitly) 트리를 정의한다.15
예를 들어, ‘격자 중앙값 분할 함수(grid median splitting-function)’는 각 노드에 해당하는 하이퍼 사각형(hyperrectangle) 영역에서 가장 긴 축을 분할 축으로 선택하고, 해당 축의 격자 중앙에 가장 가까운 격자 평면을 분할 평면으로 결정한다.15 이처럼 노드를 방문할 때마다 분할 함수를 호출하여 필요한 분할 정보를 동적으로 계산한다.
이 방식의 가장 큰 장점은 메모리 효율성이다. 명시적인 포인터나 분할 값 저장이 필요 없으므로, 데이터 자체를 저장하는 격자 외에 아주 적은 추가 메모리만으로 k-d 트리의 가속 구조를 활용할 수 있다.15 이러한 특성 덕분에 Implicit k-d tree는 대규모 스칼라 필드 데이터(예: 의료 영상, 과학 시뮬레이션 데이터)의 등가곡면(isosurface) 렌더링이나 최대 강도 투사(Maximum Intensity Projection, MIP)와 같은 시각화 응용에서 매우 효과적으로 사용된다. 광선(ray)이 공간을 통과할 때, 각 노드에 미리 계산된 속성(예: 해당 영역의 최대/최소 스칼라 값)을 이용하여 관심 없는 영역을 통째로 건너뛸 수 있어 렌더링 속도를 크게 향상시킨다.15
옥트리는 3차원 공간을 분할하는 가장 직관적이고 널리 사용되는 계층적 자료구조 중 하나로, k-d 트리와는 다른 분할 철학을 가지고 있다.
옥트리(Octree)는 3차원 공간을 나타내는 정육면체 형태의 루트 노드(root node)에서 시작하여, 공간을 재귀적으로 8개의 동일한 크기를 가진 자식 정육면체, 즉 옥턴트(octant)로 분할하는 자료구조이다.19 이 분할은 항상 노드의 중심점을 지나고 각 좌표축(x, y, z)에 평행한 세 개의 평면에 의해 이루어진다.19 분할 과정은 특정 조건을 만족할 때까지 계속된다. 예를 들어, 노드 내에 포함된 데이터의 수가 특정 임계값 이하가 되거나, 노드의 크기가 최소 단위에 도달하거나, 노드가 완전히 비어있거나 완전히 채워져 있을 때 분할을 멈추고 해당 노드는 리프 노드(leaf node)가 된다.
k-d 트리가 데이터의 분포에 따라 분할 경계를 유연하게 결정하는 ‘데이터 종속적’ 방식인 것과 대조적으로, 옥트리는 데이터의 내용과 무관하게 항상 공간을 기하학적으로 균등하게 8등분한다. 이러한 특성 때문에 옥트리는 공간 주도적(space-driven) 분할 방식의 대표적인 예로 꼽힌다.
k-d 트리와 옥트리는 공간 분할이라는 동일한 목표를 가지지만, 그 접근 방식의 차이로 인해 성능과 특성에서 뚜렷한 차이를 보인다. 이 둘의 비교는 공간 분할 자료구조 설계의 핵심적인 트레이드오프를 보여준다.
이처럼 k-d 트리와 옥트리 간의 비교는 공간 분할 자료구조 설계에 있어 근본적인 설계 철학의 차이, 즉 데이터 종속적 분할과 공간 주도적 분할이라는 이분법을 명확히 보여준다. k-d 트리는 데이터의 기하학적 구조에 적응하여 분할을 최적화하는 반면, 옥트리는 데이터와 무관하게 공간 자체의 구조를 기반으로 분할한다. 이 차이점은 이후에 등장하는 복셀 기반 구조들(SVO, VDB 등)이 옥트리의 공간 주도적 특성을 계승하고, 포인트 클라우드 처리 구조들이 k-d 트리의 데이터 종속적 특성을 유지하는 경향으로 이어지는 중요한 맥락을 형성한다. 이 근본적인 분기를 이해하는 것이 전체 공간 분할 자료구조의 지형도를 파악하는 첫걸음이다.
기초적인 옥트리 구조는 공간을 효율적으로 표현하는 첫걸음이었지만, 컴퓨터 그래픽스와 시각 효과(VFX) 분야의 요구사항은 이를 훨씬 뛰어넘었다. 수십억, 수백억 개의 복셀로 이루어진 초고해상도 장면을 다루기 위해서는 단순한 공간 분할을 넘어, 데이터 자체의 희소성(sparsity)과 반복성(redundancy)을 적극적으로 활용하는 고도의 압축 기술이 필수적이었다. 본 장에서는 이러한 도전에 대응하기 위해 옥트리에서 진화한 세 가지 핵심적인 고급 복셀 구조, 즉 SVO, SVDAG, 그리고 VDB를 탐구한다. 이들의 발전 과정은 메모리 효율성을 향한 끊임없는 추구의 역사를 보여준다.
전통적인 밀집 복셀 그리드(dense voxel grid)는 3차원 공간을 균일한 격자로 표현하는 가장 간단한 방식이지만, 치명적인 확장성 문제를 안고 있다. 해상도가 한 축으로 N배 증가하면 필요한 메모리 양은 N3배로 폭발적으로 증가한다.24 예를 들어, 1cm 해상도로 100m x 100m x 100m 공간을 표현하려면 수 테라바이트의 메모리가 필요하다.25 이는 현실적으로 불가능하다.
희소 복셀 옥트리(Sparse Voxel Octree, SVO)는 이러한 문제를 해결하기 위해 등장했다. SVO의 핵심 아이디어는 대부분의 3차원 장면에서 실제 데이터가 차지하는 공간은 극히 일부이며, 나머지 대부분은 비어있다는 관찰에서 출발한다.26 SVO는 이 ‘희소성’을 활용하여, 데이터가 존재하는(non-empty) 영역만을 옥트리 구조를 사용해 계층적으로 표현하고, 비어있는(empty) 노드에 대해서는 저장 공간을 할당하지 않는다.16
이 방식을 통해 메모리 사용량을 장면의 전체 부피가 아닌, 실제 콘텐츠의 표면적이나 부피에 비례하도록 크게 줄일 수 있다. 동시에, 계층 구조는 탐색 시 광선(ray) 등이 비어있는 거대한 공간을 단 한 번의 연산으로 건너뛸 수 있게(skip) 하여, 렌더링과 같은 질의 연산의 속도를 극적으로 향상시킨다.26
SVO는 본질적으로 옥트리이지만, 그 구현은 성능 최적화를 위해 특별히 설계된다. 포인터 기반의 전통적인 트리 구조는 각 노드가 8개의 자식 포인터를 가지므로 메모리 오버헤드가 크고, 포인터 역참조(pointer dereferencing)로 인한 캐시 미스(cache miss)가 잦아 성능 저하의 원인이 될 수 있다.
이 문제를 해결하기 위해, 현대적인 SVO 구현에서는 트리 노드들을 포인터 대신 선형 배열(linear array)에 저장하는 방식을 선호한다. 이때 노드 간의 부모-자식 관계와 공간적 위치를 효율적으로 인코딩하기 위해 모튼 코드(Morton Code), 또는 Z-order 커브가 널리 사용된다.27 모튼 코드는 3차원 좌표 $(x, y, z)$의 이진 비트들을 서로 번갈아 끼워 넣어(interleaving) 하나의 1차원 정수 값으로 매핑하는 기법이다. 예를 들어, 2차원 좌표 $(x, y) = (x_1x_0, y_1y_0)$는 모튼 코드 $y_1x_1y_0x_0$로 인코딩된다.27 이 인코딩 방식은 공간적으로 가까운 점들이 1차원 코드 상에서도 가까운 값을 갖도록 하는 공간적 지역성(spatial locality)을 보존하는 중요한 특성을 가진다. 모튼 코드로 정렬된 선형 배열은 부모-자식-형제 노드 간의 이동을 간단한 비트 연산으로 수행할 수 있게 하여, 트리 순회를 매우 빠르고 캐시 친화적으로 만든다.28
SVO의 희소성과 가속 구조로서의 특성은 다음과 같은 분야에서 강력한 성능을 발휘한다.
SVO가 ‘비어있는 공간’을 압축하는 데 초점을 맞췄다면, 희소 복셀 방향성 비순환 그래프(Sparse Voxel Directed Acyclic Graph, SVDAG)는 여기서 한 걸음 더 나아가 ‘반복되는 공간’을 압축하는 혁신적인 아이디어를 제시한다.
SVDAG의 핵심 철학은 많은 3차원 씬, 특히 인공적인 환경(예: 건물, 도시)이나 절차적으로 생성된 자연 환경(예: 숲, 지형)에는 동일한 기하학적 구조가 반복적으로 나타난다는 관찰에 기반한다.31 예를 들어, 한 건물에는 수많은 동일한 모양의 창문이 있고, 숲에는 비슷한 모양의 나무들이 반복된다.
SVO에서는 이러한 동일한 구조들이 공간적으로 다른 위치에 있다는 이유만으로 각각 별도의 서브트리로 저장되어 메모리 중복을 유발한다. SVDAG는 이 중복을 제거한다. 구조적으로 동일한 모든 서브트리(또는 노드)를 식별하여 메모리에는 단 하나의 유일한 인스턴스(unique instance)만 저장한다. 그리고 원래 이 서브트리들을 자식으로 가졌던 모든 부모 노드들은 이제 이 공유된 단일 인스턴스를 가리키는 포인터를 갖게 된다.32 이 포인터 공유(pointer sharing)로 인해, 자료구조는 더 이상 분기 후 합쳐지지 않는 ‘트리’가 아니라, 여러 경로가 하나의 노드로 합쳐질 수 있는 방향성 비순환 그래프(Directed Acyclic Graph, DAG)의 형태를 띠게 된다.16
SVDAG를 구축하는 과정은 일반적으로 SVO를 먼저 구축한 후, 후처리 단계를 통해 이루어진다. 트리의 리프 노드부터 상향식(bottom-up)으로 순회하면서 각 노드의 구조적 정보를 해싱(hashing)하여 고유한 시그니처(signature)를 생성한다. 동일한 시그니처를 가진 노드들은 동일한 구조로 간주되어, 이전에 나타난 유일한 인스턴스를 가리키도록 포인터가 재지정되고 중복된 노드는 제거된다(de-duplication).33 이 과정을 통해 SVO 대비 수십 배에서 심지어 수백 배에 달하는 극적인 메모리 압축률을 달성할 수 있다.32 더 나아가, 거울 대칭(mirror symmetry)과 같은 변환(transformation)에 대해서도 동일한 것으로 간주하여 압축률을 더욱 높이는 연구도 진행되었다.16
SVDAG의 극단적인 압축률은 상당한 대가를 치른다.
HashDAG와 같은 구조가 제안되었는데, 이는 해시 맵을 사용하여 동적 편집을 가능하게 하지만, 해시 테이블 유지를 위한 추가적인 메모리 오버헤드와 복잡성을 감수해야 한다.34SVDAG는 건축 시각화, 디지털 도시 모델, 절차적으로 생성된 게임 월드와 같이 반복적인 구조가 많고, 데이터가 거의 변하지 않는 대규모 정적 씬의 저장, 전송, 그리고 오프라인 렌더링에 매우 효과적인 솔루션이다.
SVO와 SVDAG가 주로 정적인 씬의 메모리 효율성에 집중한 반면, VDB는 영화 산업의 특수한 요구사항, 즉 거대하고, 희소하며, 동적으로 끊임없이 변화하는 볼륨 데이터를 효율적으로 처리하기 위해 탄생했다.
VDB는 DreamWorks Animation에서 개발한 오픈 소스 라이브러리인 OpenVDB의 핵심 자료구조이다.35 그 이름(Volumetric, Dynamic, B-tree)이 암시하듯, VDB는 볼륨 데이터를 다루며, 동적 환경에 강하고, 데이터베이스 인덱싱에 널리 쓰이는 B+트리의 특성을 차용한 독특한 구조를 가진다.37 VDB의 설계 철학은 시뮬레이션 과정에서 매 프레임마다 형태가 변하는 연기, 불, 물, 구름과 같은 효과를 저장하고 조작하는 데 최적화되어 있다.
VDB는 기존 옥트리 기반 구조들과는 차별화되는 여러 독창적인 특징을 가진다.
VDB는 개발 초기부터 시각 효과(VFX) 산업의 요구에 맞춰 설계되었으며, 현재 이 분야의 사실상 표준(de facto standard)으로 자리 잡았다.35 유체 시뮬레이션(물, 연기, 불), 구름 및 대기 효과, 폭발, 지형 표현 등 희소하고 동적인 특성을 가진 다양한 볼륨 데이터를 저장, 처리, 렌더링하는 데 광범위하게 사용된다.38 최근에는 NanoVDB를 통해 GPU 가속을 지원하고, 로보틱스 분야의 맵 표현 등 다른 영역으로도 활용이 확대되고 있다.36
이 세 가지 고급 복셀 구조의 진화는 압축 전략의 발전을 명확히 보여준다. 옥트리와 SVO는 ‘비어있는 공간의 제거’라는 첫 번째 논리적 도약을 이루었다. SVDAG는 여기서 더 나아가 ‘반복되는 구조의 제거’라는 두 번째, 더 정교한 도약을 이루었다. 반면, VDB는 이들과는 다른 축, 즉 ‘동적 데이터의 효율적 관리’에 초점을 맞춰 발전했다. SVO가 희소성을 압축하고, SVDAG가 중복성을 압축하며, VDB가 역동성을 효율적으로 다루는 것처럼, 각각은 대규모 공간 데이터가 제기하는 서로 다른 종류의 문제에 대한 특화된 해결책이라 할 수 있다.
컴퓨터 그래픽스가 주로 정적이고 거대한 세계를 효율적으로 ‘저장’하고 ‘렌더링’하는 문제에 집중했다면, 로보틱스, 자율 주행, 실시간 시뮬레이션과 같은 분야는 다른 종류의 도전에 직면한다. 이 분야들의 핵심 과제는 정적인 세계를 표현하는 것이 아니라, 센서로부터 끊임없이 쏟아져 들어오는 데이터를 최소한의 지연 시간(latency)으로 ‘처리’하고, 그에 맞춰 빠르게 상태를 ‘업데이트’하는 것이다. 본 장에서는 이러한 실시간 동적 환경의 요구사항을 충족시키기 위해 발전한 고성능 자료구조들을 탐구한다. 이들의 진화는 복잡한 계층 구조를 유지하기보다는, 극단적인 업데이트 속도를 위한 빠른 인덱싱 기법으로 나아가는 경향을 보인다.
많은 과학 및 공학 시뮬레이션, 특히 유한 요소 해석(Finite Element Method, FEM)이나 전산 유체 역학(Computational Fluid Dynamics, CFD)에서는 계산에 사용되는 메시(mesh)의 품질이 해석의 정확성과 수치적 안정성에 결정적인 영향을 미친다. 옥트리를 메시 생성에 사용할 때, 인접한 셀(octant) 간의 크기 차이가 너무 급격하게 변하면 수치 오류나 불안정성을 야기할 수 있다.
이러한 문제를 방지하기 위해 2:1 균형 제약(2:1 balance constraint) 또는 ‘연속성 조건(continuity condition)’이 도입되었다.43 이 제약은 공간적으로 인접한(면 또는 모서리를 공유하는) 두 개의 리프 노드의 크기(즉, 레벨) 차이가 2배(즉, 1 레벨)를 초과해서는 안 된다는 조건이다.43 예를 들어, 레벨 4의 셀 옆에 레벨 2의 셀이 직접 위치할 수 없으며, 그 사이에는 반드시 레벨 3의 셀이 존재해야 한다. 이를 통해 메시의 크기가 공간에 걸쳐 부드럽게 변하도록 보장하여, T-교차점(T-junction) 문제를 완화하고 고품질의 메시를 생성할 수 있다.44
데이터의 추가(refinement)나 삭제(coarsening)로 인해 옥트리의 일부 영역에서 2:1 균형 제약이 깨질 수 있다. 이때, 제약을 다시 만족시키기 위해 옥트리를 수정하는 과정을 균형 재정의(balance refinement)라고 한다.43 예를 들어, 어떤 셀이 분할되어 그 자식 중 하나가 기존의 큰 이웃 셀과 2:1 제약을 위반하게 되면, 그 큰 이웃 셀 또한 강제로 분할되어야 한다. 이러한 분할은 또 다른 이웃과의 제약을 위반할 수 있으며, 이로 인해 수정 작업이 인접 노드로 연쇄적으로 전파되는 파급 효과(ripple propagation)가 발생할 수 있다.43 이 과정은 특히 병렬 환경에서 여러 프로세서에 걸쳐 데이터가 분산되어 있을 때 통신 오버헤드를 유발하는 복잡한 작업이 될 수 있다.44
수십억 개 이상의 옥턴트를 사용하는 대규모 시뮬레이션에서는 전체 옥트리를 메인 메모리에 상주시키는 것이 불가능하다. 이러한 대용량 데이터셋에서 동적 균형을 효율적으로 관리하기 위해 선형 옥트리(linear octree) 표현법이 널리 사용된다.43
선형 옥트리는 포인터로 노드들을 연결하는 전통적인 트리 구조 대신, 트리의 리프 노드들만을 리스트 형태로 저장한다. 각 리프 노드는 모튼 코드와 같은 위치 코드(locational code)를 통해 고유하게 식별된다. 이 위치 코드는 노드의 공간적 위치와 크기(레벨) 정보를 모두 인코딩한다.43 모든 리프 노드들의 위치 코드를 정렬하여 배열이나 리스트에 저장하면, 이 데이터 자체가 옥트리의 전체 구조를 암시적으로 표현하게 된다. 이 정렬된 리스트는 일반적으로 디스크 상에 B-트리(B-tree)와 같은 인덱스 구조를 사용하여 효율적으로 관리된다.43
이러한 접근법은 자료구조의 크기가 메모리가 아닌 디스크 용량에 의해 제한되도록 하여, 메모리 용량을 훨씬 초과하는 거대한 옥트리 데이터셋을 다룰 수 있게 해준다. 동적 균형 재정의 알고리즘은 이 선형 옥트리 위에서 디스크 기반의 정렬 및 병합 연산을 통해 수행된다.43
로보틱스, 특히 LiDAR-관성 주행 거리 측정(Lidar-Inertial Odometry, LIO) 분야는 또 다른 차원의 실시간성을 요구한다. 여기서는 매초 수십 번씩 수만 개의 점으로 구성된 LiDAR 스캔 데이터가 들어오며, 시스템은 이 데이터를 즉시 처리하여 로봇의 위치를 추정하고 맵을 업데이트해야 한다. 이러한 환경에서는 i-kd-tree조차도 트리 재균형에 드는 비용이 부담스러울 수 있다.
iVox(incremental Voxel)는 이러한 초고속 증분 업데이트 요구사항을 충족시키기 위해 설계된 자료구조이다. iVox의 핵심적인 발상은 복잡한 트리 구조를 완전히 버리고, 점들을 담고 있는 희소한 복셀들을 해시 맵(hash map, C++의 std::unordered_map)을 사용하여 직접 인덱싱하는 것이다.13 점의 공간 좌표를 해시 함수에 입력하여 해시 키를 계산하고, 이 키를 사용해 해당 복셀에 대한 데이터에 $O(1)$의 평균 시간 복잡도로 접근한다.
iVox는 복셀 내부에 점들을 저장하는 방식에 따라 두 가지 변형을 가진다.13
실험 결과에 따르면, iVox는 LIO 응용에서 기존의 트리 기반 구조들을 월등히 능가하는 성능을 보인다. 한 연구에서는 iVox가 i-kd-tree에 비해 트리 구축에서 64%, 점 삽입에서 66%, k-NN 탐색에서 30%, 반경 탐색에서 56%의 런타임 감소를 보였다고 보고했다.14 이는 iVox의 해시 기반 접근법이 실시간 동적 환경에 얼마나 효과적인지를 명확히 보여준다.
iVox가 해시 맵을 통해 트리 구조를 탈피했다면, RC-Vox(Robocentric Voxel map)는 여기서 한 걸음 더 나아가 해시 맵조차도 제거하고 원시적인 3D 배열을 사용하여 극단적인 속도 최적화를 추구한다.
RC-Vox는 LIO 시스템의 효율성을 극한까지 끌어올리기 위해 제안된 구조로, 그 핵심은 로봇을 중심으로 하는 고정된 크기의 2계층 3D 배열을 사용하는 것이다.49
2계층 배열 구조: RC-Vox는 두 개의 배열 계층으로 구성된다.
최상위 레벨 배열 (Top-Level Array, TLA): 상대적으로 낮은 해상도(예: 미터 단위)를 가진 3D 배열이다.
하위 레벨 배열 (Bottom-Level Array, BLA): TLA의 각 셀(grid)은 필요에 따라 내부에 더 높은 해상도의 BLA를 생성하여 실제 복셀들을 저장한다.
이 2계층 구조는 메모리 사용을 관리하면서도 빠른 접근을 가능하게 한다.49
로봇 중심 및 모듈러 연산: 이 배열은 가상의 무한한 공간을 표현하는 것이 아니라, 항상 현재 로봇의 위치를 중심으로 하는 고정된 크기의 로컬 맵을 나타낸다. 로봇이 이동하여 로컬 맵의 범위가 이 고정된 TLA 배열의 경계를 벗어나게 되면, 모듈러(modulo) 연산을 사용하여 벗어난 그리드를 배열의 반대편으로 다시 매핑하고 그 내용을 초기화(reset)한다.49 이는 마치 팩맨 게임의 맵처럼, 한쪽 끝으로 나가면 반대쪽 끝으로 나타나는 효과를 내며, 고정된 크기의 배열로 지속적으로 움직이는 로컬 맵을 효율적으로 관리할 수 있게 한다.
k-NN 탐색의 혁신적 최적화: RC-Vox의 가장 독창적인 부분은 k-NN 탐색을 최적화하는 방식에 있다. 전통적인 방식에서는 질의 시점(query time)에 주변 공간을 탐색하여 이웃 점들을 찾는다. 하지만 RC-Vox는 이 작업을 매핑 시점(mapping time)으로 옮긴다. 즉, 새로운 LiDAR 점이 시스템에 등록되어 특정 복셀에 추가될 때, 그 점을 해당 복셀에만 저장하는 것이 아니라, 그 주변의 인접한 26개 복셀에도 미리 복사하여 기록해 둔다.49 이 작업은 매핑 시점에 약간의 추가 비용을 발생시키지만, 매핑은 증분적으로 소수의 점에 대해서만 일어나므로 전체적인 부담은 미미하다.
이러한 사전 작업 덕분에, 실제 k-NN 질의가 필요한 시점에는 매우 빠른 속도를 자랑한다. 질의점의 이웃을 찾기 위해 주변 복셀들을 탐색할 필요 없이, 단순히 질의점이 속한 단 하나의 복셀을 조회하기만 하면 된다. 그 복셀에는 이미 필요한 모든 이웃 점들이 기록되어 있기 때문이다. 이 전략은 k-NN 탐색 과정을 사실상 $O(k)$의 간단한 거리 계산 및 정렬 문제로 바꾸어 버린다.
원시 배열의 직접 접근(O(1))과 혁신적인 k-NN 탐색 전략 덕분에, RC-Vox는 현존하는 LIO 시스템 중 가장 빠른 성능을 보인다. 한 연구에서는 RC-Vox의 단일 스레드 버전이 iVox를 사용하는 Faster-LIO의 병렬 가속 버전보다도 더 빠르다고 보고했다.49 이는 특히 로봇이 격렬하게 움직이는 공격적인 모션 시나리오에서도 안정적인 트래킹을 가능하게 하는 핵심 요인이다.
이러한 고성능 동적 구조들의 발전 과정은 실시간 응용을 위한 최적화 철학의 변화를 명확히 보여준다. 동적 균형 옥트리가 여전히 ‘트리’라는 복잡한 계층 구조를 유지하려 했다면, iVox는 “정말 트리가 필요한가? 빠른 조회가 핵심이 아닌가?”라는 질문을 던지며 해시 맵이라는 빠른 ‘인덱싱’으로 전환했다. RC-Vox는 여기서 더 나아가 “해시 맵보다 더 빠른 것은 없나?”라는 질문에 ‘원시 배열’이라는 답을 내놓았다. 이 과정은 풍부한 계층적 정보를 포기하는 대신, 오직 업데이트와 질의 속도를 극대화하기 위한 무자비한 최적화의 역사라 할 수 있다. LIO와 같은 응용에서는 전체 씬의 구조를 아는 것보다, ‘지금 당장’ 내 주변의 가장 가까운 점들을 찾는 것이 훨씬 중요하기 때문이다.
지금까지 개별적으로 분석한 10가지 공간 분할 자료구조의 특성을 종합하여, 이들의 관계와 성능 트레이드오프를 다각적으로 조명하고, 실제 응용에 적합한 자료구조를 선택하기 위한 실용적인 가이드라인을 제시한다.
본 보고서에서 다룬 10가지 자료구조의 핵심적인 특징, 기반 기술, 성능 복잡도, 그리고 주요 응용 분야를 요약하여 비교하면 다음과 같다. 이 표는 각 기술의 장단점을 한눈에 파악하고, 특정 요구사항에 맞는 기술을 필터링하는 데 유용한 기준을 제공한다.
표 1: 공간 분할 자료구조 종합 비교표
| 자료구조 (Data Structure) | 핵심 분할 전략 | 주요 기반 기술 | 동적 업데이트 지원 | 메모리 효율성/압축 | 주요 응용 분야 | 구축 시간 복잡도 | 탐색 시간 복잡도 (k-NN) | 탐색 시간 복잡도 (반경) | 삽입/삭제 시간 복잡도 |
|---|---|---|---|---|---|---|---|---|---|
| kd-tree | 데이터 종속 이진 분할 | BST | 비효율적 (불균형 유발) | 낮음 | k-NN 검색, 저차원 데이터 인덱싱 | O(NlogN) 5 | O(logN) avg. 5 | O(N1−1/k+m) 5 | O(logN) avg. 5 |
| i-kd-tree | 데이터 종속 이진 분할 | 동적 BST | 고효율 (부분 재구축) | 낮음 | 실시간 LiDAR SLAM, 동적 점 집합 | 증분적 | O(logN) avg. 14 | O(logN) avg. 14 | O(logN) avg. 14 |
| Octree | 공간 주도 8진 분할 | Tree | 부분적 지원 | 중간 (희소성 일부 반영) | 충돌 감지, 복셀 렌더링, GIS | O(NlogN) | O(N) worst 12 | O(logN) avg. 12 | O(logN) |
| 동적 균형 Octree | 공간 주도 8진 분할 (2:1 제약) | Linear Octree, B-Tree | 고효율 (균형 재정의) | 중간 (디스크 기반) | FEM/CFD 메시 생성, 대규모 시뮬레이션 | 증분적 43 | O(logN) | O(logN) | 증분적 43 |
| SVO | 희소 복셀 8진 분할 | Octree, Morton Code | 제한적 (정적 씬 위주) | 높음 (빈 공간 압축) | 실시간 레이트레이싱, 게임 AI 경로 탐색 | O(N) (복셀 수 기준) | N/A (주로 광선 추적) | O(logN) (광선 추적) | 비효율적 |
| SVDAG | 희소 복셀 DAG 분할 | SVO, DAG, Hashing | 매우 비효율적 (정적 전용) | 매우 높음 (중복 제거) | 대규모 정적 씬 렌더링 (건축, 도시) | O(N) + 해싱 33 | N/A (주로 광선 추적) | O(logN) 이상 33 | 매우 비효율적 34 |
| VDB | 넓고 얕은 B+트리 | B+Tree | 매우 고효율 | 높음 (희소성 및 동적 최적화) | VFX (연기, 불 등), 동적 볼륨 데이터 | 증분적 38 | O(1) avg. (stencil) | O(1) avg. (stencil) | O(1) avg. 39 |
| iVox (linear) | 희소 복셀 해싱 | Hash Map | 매우 고효율 | 중간 (로컬 맵) | 고속 LIO/SLAM | O(N) (점 수 기준) | O(nvox) 13 | O(nvox) | O(1) avg. 13 |
| iVox-PHC | 희소 복셀 해싱 + PHC | Hash Map, Hilbert Curve | 매우 고효율 | 중간 (로컬 맵) | 고속 LIO/SLAM (고밀도 복셀) | O(N) + PHC 구축 | O(lognvox) 13 | O(lognvox) | O(1) avg. 13 |
| RC-Vox | 로봇 중심 2계층 배열 | Array, Modulo Arithmetic | 극도로 고효율 | 낮음 (속도 최적화) | 초고속/고강건성 LIO (공격적 모션) | O(N) (점 수 기준) | O(k) 49 | N/A | O(1) 49 |
자료구조들을 특정 성능 축을 기준으로 그룹화하면, 이들의 진화적 맥락과 설계 철학을 더 깊이 이해할 수 있다.
이 그룹의 자료구조들은 주로 정적이거나 서서히 변하는 대규모 씬을 효율적으로 ‘저장’하는 문제에 집중한다. 이들의 진화는 압축 전략의 발전으로 요약될 수 있다.
이 그룹 내에는 명확한 트레이드오프가 존재한다. 압축률이 높아질수록(Octree –» SVO –» SVDAG), 일반적으로 구조가 복잡해지고 동적 업데이트가 어려워지며, 때로는 탐색 성능(특히 레이 트레이싱)이 저하될 수 있다.33 VDB는 이 축에서 약간 벗어나, 높은 압축률보다는 동적 성능과 유연성에 우선순위를 둔 독자적인 위치를 차지한다.
이 그룹의 자료구조들은 데이터가 실시간으로 빠르게 변하는 동적 환경에서의 ‘처리 속도’를 최적화하는 데 집중한다. 이들의 진화는 복잡한 트리 구조를 점차 버리고 단순하고 빠른 인덱싱 방식으로 나아가는 과정으로 볼 수 있다.
전통적 트리의 동적화: 정적 kd-tree나 Octree는 동적 업데이트에 취약하다. 이를 개선하기 위해 i-kd-tree는 부분 재구축 기법을 14,
동적 균형 Octree는 2:1 제약을 유지하기 위한 파급 효과 처리 메커니즘을 도입했다.43 이들은 여전히 ‘트리’라는 계층 구조의 틀 안에서 동적 성능을 개선하려는 시도이다.
새로운 패러다임 (B+트리): VDB는 B+트리의 특성을 차용하여, 트리 구조를 유지하면서도 평균 $O(1)$에 가까운 빠른 삽입/삭제 성능을 달성했다. 이는 전통적인 이진 트리나 옥트리와는 다른 접근법으로, 동적 성능과 구조적 유연성 사이의 뛰어난 균형을 제공한다.38
트리 구조의 탈피 (해시 맵): iVox는 LIO와 같은 극단적인 실시간 요구사항 앞에서 트리 구조 자체가 오버헤드라는 결론에 도달했다. 복잡한 계층적 관계를 버리고, 공간 좌표를 직접 해시 키로 변환하여 해시 맵에 접근하는 방식을 채택했다.13 이를 통해 트리 재균형과 관련된 모든 비용을 제거하고, 순수한
O(1) 평균 업데이트 성능을 달성했다.
구조의 극한적 단순화 (배열): RC-Vox는 iVox보다 한 걸음 더 나아가, 해시 맵의 잠재적인 충돌 및 오버헤드마저 제거하기 위해 원시 3D 배열을 사용한다.49 로봇 중심의 고정된 배열과 모듈러 연산을 결합하여 무한 공간을 시뮬레이션하고, k-NN 탐색 로직을 매핑 시점으로 이전하는 혁신을 통해 업데이트와 탐색 모두에서 극한의 속도를 추구한다.49
이 그룹 내의 트레이드오프는 업데이트 속도 vs. 구조적 정보의 풍부함으로 요약된다. RC-Vox로 갈수록 업데이트 속도는 빨라지지만, SVO나 VDB가 제공하는 전역적인 계층 구조나 다중 해상도 분석과 같은 풍부한 기능은 상실하게 된다.
어떤 자료구조가 ‘최고’라고 단정할 수는 없다. 최적의 선택은 전적으로 응용 프로그램의 구체적인 요구사항에 달려있다. 다음은 적절한 자료구조를 선택하는 데 도움이 되는 의사결정 가이드라인이다.
데이터의 특성은 무엇인가?
kd-tree 계열, 후자는 Octree 계열에서 출발하는 것이 자연스럽다.SVO, SVDAG가, 동적 데이터에는 i-kd-tree, VDB, iVox, RC-Vox가 적합하다.SVO, VDB) 기하학적 패턴이 많이 반복되는가? (SVDAG)주요 연산은 무엇인가?
읽기 vs. 쓰기: 데이터 질의(읽기)가 압도적으로 많은가, 아니면 업데이트(쓰기)가 빈번한가? 읽기 위주의 정적 씬 렌더링에는 SVDAG, 쓰기 위주의 실시간 매핑에는 RC-Vox가 극단에 위치한다.
k-NN vs. 반경 탐색: k-NN 탐색이 주 목적이라면 kd-tree가 전통적으로 강점을 보이지만 12, LIO와 같이 특화된 k-NN 탐색에서는
iVox, RC-Vox가 월등하다. 일반적인 반경 탐색은 Octree가 좋은 성능을 보일 수 있다.12
시스템 제약은 무엇인가?
SVDAG와 같은 고압축 구조가 유일한 대안일 수 있다.iVox나 RC-Vox를 고려해야 한다.kd-tree나 기본적인 Octree는 상대적으로 구현이 간단하지만, VDB나 SVDAG는 매우 복잡한 라이브러리를 필요로 한다.본 보고서에서 분석한 공간 분할 자료구조의 역사는 범용적인 초기 구조인 kd-tree와 octree에서 출발하여, 특정 응용 분야의 극한 요구사항을 만족시키기 위한 두 가지 주요 방향으로 분화하고 심화되어 왔음을 명확히 보여준다.
Octree는 SVO로 발전하여 빈 공간을 효율적으로 압축했고, 이는 다시 SVDAG로 진화하여 기하학적 중복성까지 제거하는 수준에 이르렀다. VDB는 이 흐름 속에서 동적 특성을 강화한 독자적인 경로를 개척했다. 이 흐름의 핵심 동인은 저장 효율성이다.kd-tree는 i-kd-tree로, Octree는 동적 균형 Octree로 발전했다. 그러나 진정한 돌파구는 트리 구조 자체를 버리는 데서 나왔다. iVox와 RC-Vox는 해시 맵과 원시 배열이라는 극도로 단순한 인덱싱 기법을 채택하여, 업데이트 지연 시간을 최소화했다. 이 흐름의 핵심 동인은 처리 속도이다.결론적으로, ‘최고의’ 공간 분할 자료구조는 존재하지 않으며, 모든 설계에는 근본적인 트레이드오프가 내재되어 있다. 본 보고서에서 분석한 모든 구조는 다음의 핵심적인 트레이드오프 관계 위에서 자신의 위치를 정의한다.
SVDAG처럼 압축률이 높을수록 구조가 복잡해지고 업데이트 및 특정 탐색 연산이 느려지는 경향이 있다.RC-Vox처럼 업데이트 성능을 극대화하면, 전역적인 계층 정보를 활용하는 복잡한 탐색 기능은 제한될 수 있다.kd-tree와 Octree는 다양한 문제에 적용될 수 있는 범용성을 가지지만, VDB나 RC-Vox는 각각 VFX와 LIO라는 특정 도메인의 문제에 대해 압도적인 성능을 발휘하도록 고도로 특화되어 있다.공간 분할 자료구조 분야는 계속해서 진화하고 있다. 향후 발전은 몇 가지 방향으로 예측될 수 있다. 첫째, GPU 아키텍처의 병렬 처리 능력을 최대한 활용하는 방향으로의 발전이 가속화될 것이다. OpenVDB의 NanoVDB는 VDB 구조를 GPU에 최적화하여 실시간 렌더링 및 시뮬레이션을 가능하게 한 좋은 예이다.36 둘째, 본 보고서에서 분석한 여러 구조의 장점을 결합한 하이브리드 자료구조에 대한 연구가 활발해질 것이다. 예를 들어, VDB의 동적 특성과 SVDAG의 압축률을 결합하려는 시도나, iVox의 빠른 업데이트와 kd-tree의 효율적인 탐색을 결합하려는 시도가 나타날 수 있다. 마지막으로, 최근 급부상하는 딥러닝 기반의 새로운 공간 표현 방식(예: NeRF, 3D Gaussian Splatting)이 전통적인 이산적 공간 분할 자료구조와 어떻게 상호작용하고 융합될 것인지가 중요한 연구 주제가 될 것이다.24 이러한 새로운 패러다임들은 기존 자료구조를 대체하기보다는, 특정 작업(예: 뷰 합성)에 대해 상호 보완적으로 사용되거나, 신경망 학습을 위한 기본 데이터 구조로 활용될 가능성이 높다. 결국, 미래의 공간 데이터 처리는 단일한 만능 해결책이 아닌, 문제의 특성에 따라 다양한 기술을 조합하여 사용하는 더욱 정교하고 다각적인 접근법을 요구하게 될 것이다.
| Wald’s [24] implicit kd-tree. | Download Scientific Diagram - ResearchGate, accessed August 5, 2025, https://www.researchgate.net/figure/Walds-24-implicit-kd-tree_fig1_38015491 |
| VoxelMap++: Mergeable Voxel Mapping Method for Online LiDAR(-inertial) Odometry | Request PDF - ResearchGate, accessed August 5, 2025, https://www.researchgate.net/publication/372961600_VoxelMap_Mergeable_Voxel_Mapping_Method_for_Online_LiDAR-inertial_Odometry |