VDB(Volumetric Dynamic B+tree)는 3차원 그리드에 이산화된 희소(sparse), 동적(dynamic), 시변(time-varying) 볼류메트릭 데이터를 효율적으로 저장하고 조작하기 위해 설계된 컴팩트한 계층적 자료 구조이다.1 이 구조는 DreamWorks Animation의 Ken Museth에 의해 처음 개발되었으며, 시각 효과(VFX) 산업에서 연기, 구름, 물과 같은 복잡한 현상을 표현하기 위한 목적으로 시작되었다.1 이후 그 성능과 유연성을 인정받아 로보틱스, 과학 시뮬레이션, 의료 영상, 3D 재구성 등 다양한 분야로 그 적용 범위를 성공적으로 확장해왔다.4
본 보고서를 시작하기에 앞서, 용어의 혼동을 방지하기 위해 중요한 개념적 구분을 명확히 할 필요가 있다. 최근 인공지능(AI) 및 데이터 과학 분야에서 부상하고 있는 ‘VDB’는 주로 ‘벡터 데이터베이스(Vector Database)’를 지칭한다. 이는 텍스트, 이미지, 오디오 등에서 추출된 고차원 벡터 임베딩을 저장하고, 유사도 기반의 빠른 검색을 수행하는 시스템이다.6 본 보고서에서 다루는 Volumetric Dynamic B+tree는 이름의 약어(VDB)가 동일할 뿐, 컴퓨터 그래픽스와 시뮬레이션을 위한 3차원 공간 데이터 구조로서 벡터 데이터베이스와는 근본적으로 다른 목적과 구조, 기술적 배경을 가진다. 따라서 본 보고서의 ‘VDB’는 전적으로 Volumetric Dynamic B+tree를 의미한다.
VDB의 개발 배경에는 기존 볼류메트릭 데이터 표현 방식의 근본적인 한계가 존재했다. 가장 직관적인 방식인 밀집 그리드(dense grid), 즉 3차원 배열은 데이터의 해상도가 증가함에 따라 메모리 요구량이 해상도의 세제곱에 비례하여($O(N3)$) 폭발적으로 증가한다.7 이는 연기나 구름처럼 대부분의 공간이 비어있는 희소(sparse) 데이터의 경우, 막대한 양의 메모리를 낭비하는 결과를 초래한다. VDB는 이러한 문제를 해결하기 위해 탄생했다. VDB의 핵심 목표는 사실상 무한한(unbounded) 3차원 인덱스 공간을 제공하면서도, 데이터가 존재하는 영역만을 효율적으로 저장하여 메모리 사용량을 최소화하고, 데이터의 삽입, 삭제, 조회가 빈번한 동적 환경에서도 빠른 랜덤 및 순차 접근 성능을 보장하는 것이다.1
3차원 공간상의 데이터를 표현하는 가장 간단한 방법은 공간을 균일한 격자, 즉 복셀(voxel)로 나누고 각 복셀의 값을 3차원 배열에 저장하는 밀집 그리드 방식이다. 이 방식은 특정 위치의 데이터에 $O(1)$시간 복잡도로 즉시 접근할 수 있다는 장점이 있지만, 치명적인 단점을 내포하고 있다. 그리드의 해상도가 각 축으로 $N$배 증가하면, 필요한 총 메모리 양은\(N^3\)에 비례하여 기하급수적으로 늘어난다.7 고해상도 시뮬레이션이나 렌더링에서 이는 곧 수십, 수백 기가바이트의 메모리를 요구하게 되어 현실적으로 사용이 불가능한 경우가 많다.
문제는 실제 세계의 많은 볼륨 데이터가 본질적으로 희소하다는 점에 있다. 예를 들어, 피어오르는 연기, 하늘에 떠 있는 구름, 혹은 레벨셋(level set) 기법에서 물체의 표면을 표현하는 좁은 밴드(narrow-band)는 전체 3차원 공간 중 극히 일부만을 차지한다.8 이러한 데이터에 밀집 그리드를 사용하는 것은 대부분의 메모리를 ‘빈 공간’ 또는 의미 없는 배경 값으로 채우는 것과 같다. 따라서 데이터가 실제로 존재하는 ‘활성(active)’ 영역만을 효율적으로 저장하는 희소 자료 구조의 필요성이 대두되었다. 하지만 VDB 이전의 많은 희소 볼륨 자료 구조들은 데이터의 토폴로지(topology)가 변하지 않는 정적(static) 상황을 가정하거나, 특정 접근 패턴(예: 순차 접근)에만 최적화되어 있어 데이터의 구조가 실시간으로 변하는 동적 시뮬레이션 환경에서는 무작위 접근(random access) 속도가 느려지는 등의 한계를 보였다.4
VDB는 이러한 도전 과제를 해결하기 위해 두 가지 핵심 철학에 기반하여 설계되었다. 첫째는 공간적 일관성(spatial coherency)의 적극적인 활용이다.4 이는 자연계의 현상이나 시뮬레이션 데이터가 무작위로 흩어져 있기보다는 공간적으로 서로 뭉쳐서 나타나는 경향이 있다는 관찰에 기반한다. 즉, 특정 복셀 주변의 다른 복셀들은 유사하거나 동일한 값을 가질 확률이 높다. VDB는 이러한 특성을 이용하여 데이터를 계층적인 트리 구조로 묶고, 값이 동일한 넓은 영역을 상위 노드에서 하나의 ‘타일(tile)’ 값으로 압축하여 표현함으로써 메모리 효율성을 극대화한다.
둘째는 VDB의 가장 중요한 설계 원칙 중 하나인 토폴로지-데이터 분리(separation of topology and data)이다.4 이는 데이터의 공간적 위치와 구조를 정의하는 ‘토폴로지’와, 해당 위치에 저장된 실제 ‘데이터 값(value)’을 물리적으로 분리하여 관리하는 것을 의미한다. 토폴로지는 VDB 트리의 노드와 포인터 구조로 표현되며, 실제 float, vector, boolean 등의 데이터 값들은 리프 노드에 밀집된 데이터 블록(data block) 형태로 별도로 저장된다. 이러한 분리 구조는 데이터베이스 시스템에서 B+tree가 인덱스(키)와 실제 데이터 레코드를 가리키는 포인터를 분리하여 관리하는 철학과 매우 유사하다.9 이 덕분에 토폴로지 구조의 변경 없이 데이터 값만 효율적으로 업데이트하거나, 반대로 동일한 토폴로지 구조를 여러 다른 데이터셋(예: 밀도, 온도, 속도 필드)이 공유하는 인스턴싱(instancing)이 가능해져 높은 수준의 유연성과 메모리 효율성을 동시에 달성할 수 있다.8
VDB라는 이름 자체는 이 자료 구조의 핵심적인 특성을 함축하고 있다.
여기서 VDB의 ‘Dynamic’이라는 특성은 이중적인 의미를 지닌다. 런타임(runtime) 관점에서는 복셀 데이터의 추가 및 삭제에 따라 트리의 토폴로지가 동적으로 변화할 수 있다는 것을 의미한다.4 하지만 OpenVDB 구현체의 관점에서 보면, 트리의 레벨 수나 각 노드의 분기 계수(branching factor)와 같은 핵심적인 구조적 ‘구성(configuration)’은 C++ 템플릿을 통해 컴파일 타임(compile-time)에 고정된다.1 이 두 가지 특성은 언뜻 모순처럼 보일 수 있지만, 실제로는 성능과 유연성을 모두 잡기 위한 정교한 설계의 결과이다. ‘컴파일 타임 정적성’은 특정 데이터 타입과 트리 구조에 대해 컴파일러가 코드를 완벽하게 인라이닝하고 최적화하여 최고의 실행 성능을 이끌어내기 위한 전략적 선택이다. 반면, ‘런타임 동적성’은 이렇게 최적화된 고정된 ‘틀’ 안에서 데이터의 존재 유무(활성/비활성 상태)가 자유롭게 변할 수 있음을 의미한다. 이 이중적 특성이야말로 VDB가 고성능과 높은 유연성을 동시에 제공하는 비결이다.
궁극적으로 VDB의 혁신은 완전히 새로운 개념의 ‘발명’이라기보다는, B+tree, 옥트리(Octree), 희소 그리드 등 기존에 존재하던 여러 아이디어들을 통합하고, 3D 볼류메트릭 데이터라는 특정 도메인의 문제 해결을 위해 극도로 최적화한 ‘공학적 성취’에 가깝다. VDB는 B+tree로부터 넓고 얕은 구조와 키-데이터 분리 철학을 9, 옥트리로부터는 공간 분할 아이디어를 차용했다. 그러나 VDB의 진정한 독창성은 3D 공간 좌표를 직접 해싱하여 자식 노드를 찾는 고유한 인덱싱 방식, 토폴로지와 데이터를 명확히 분리한 아키텍처, 그리고 현대 CPU의 캐시 구조에 극도로 최적화된 메모리 레이아웃 설계에 있다.4 이는 이론적 순수성보다는 VFX 프로덕션 현장에서 마주하는 ‘고해상도의 동적 희소 데이터를 실시간에 가깝게 처리해야 한다’는 실용적인 요구사항을 해결하기 위한 고도의 엔지니어링적 절충과 통합의 산물이라 할 수 있다.
VDB는 그 이름에서 알 수 있듯이 데이터베이스 인덱싱에 널리 사용되는 B+tree와 여러 중요한 특성을 공유하지만, 3차원 공간 데이터를 다루기 위해 근본적인 차이점을 가진다.
데이터는 리프에만 (Data in Leaves, Conceptually): B+tree에서 실제 데이터 포인터가 리프 노드에만 존재하는 것처럼, VDB에서도 실제 개별 복셀 값들은 주로 최하위 레벨인 리프 노드에 저장된다.8 상위의 내부 노드(Internal Node)들은 자식 노드들을 가리키는 인덱스, 즉 공간을 분할하는 가이드 역할을 수행한다. 다만 VDB는 ‘타일(tile)’이라는 개념을 통해 내부 노드에도 균일한 값을 저장할 수 있는 유연성을 추가로 제공한다.8
VDB 트리는 일반적으로 3개에서 5개의 레벨로 구성된 계층 구조를 가진다.1 OpenVDB에서 가장 널리 사용되는 표준 4레벨 구성(FloatGrid 등)은 다음과 같은 노드들로 이루어진다.8
레벨 3 (RootNode): 트리의 최상위 노드로, 모든 탐색의 시작점이다. 다른 노드들과 달리 동적인 분기 계수(dynamic branching factor)를 가진다. 즉, 자식 노드의 수에 제한이 없다. 이 특징 덕분에 VDB는 사실상 무한한 3D 인덱스 공간을 표현할 수 있다. 루트 노드는 해시 테이블과 유사한 구조를 사용하여 3D 좌표에 해당하는 최상위 내부 노드(레벨 2)를 관리한다.1
레벨 2 (InternalNode): OpenVDB에서는 종종 ‘5-node’라고 불리며, 고정된 분기 계수를 가진다. 예를 들어, 각 차원당 2^5=32$개씩, 총 32×32×32=32,768개의 자식(레벨 1 노드)을 가리키는 포인터 배열을 가진다.12
레벨 1 (InternalNode): ‘4-node’라고 불리며, 마찬가지로 고정된 분기 계수를 가진다. 각 차원당 $2^4=16$
개씩, 총 16×16×16=4,096개의 자식(레벨 0 노드) 포인터를 가진다.12
레벨 0 (LeafNode): ‘3-node’라고도 불리며, 트리의 가장 마지막 레벨이다. 이 노드는 더 이상 자식 노드를 가리키지 않고, 실제 복셀 데이터 값들을 담고 있는 밀집된 3D 블록을 저장한다. 일반적으로 각 차원당 $2^3=8$ 개씩, 총 8×8×8=512개의 복셀 값을 저장하는 배열을 가진다.8
이러한 계층 구조는 3D 공간을 효율적으로 분할하고 인덱싱한다. 특정 복셀의 전역 좌표 $(i, j, k)$가 주어지면, 각 레벨에서 해당 좌표의 특정 비트들을 추출하여 자식 노드 배열 내의 지역 인덱스(local index)를 계산한다. 예를 들어, 8×8×8 리프 노드 내의 지역 좌표는 전역 좌표의 하위 3비트($2^3=8$)로 결정되고, 그 상위 레벨인 4-node 내의 자식 인덱스는 그 다음 4비트($2^4=16$)로 결정되는 식이다. 이 계산은 단순한 비트 연산으로 이루어지므로 매우 빠르다. 구체적인 인덱스 계산 공식의 예는 다음과 같다 12:
리프 노드 (3-node, 83) 내 복셀 인덱스:
index=(i & 7)≪6+(j & 7)≪3+(k & 7)
(자료 12의 z + y*8 + x*64는 x, y, z 순서가 다를 뿐 원리는 동일)
상위 노드 (5-node, 323) 내 자식 인덱스:
index=((i≫3) & 31)≪10+((j≫3) & 31)≪5+((k≫3) & 31)
(자료 12의 z + y*32 + x*1024와 원리 동일)
VDB는 메모리 사용량을 최적화하고 데이터 접근을 가속화하기 위해, 데이터를 단일 형태가 아닌 세 가지의 논리적 형태로 구분하여 저장한다.8
이러한 데이터 표현과 더불어, VDB는 활성/비활성 상태와 비트마스크(bitmask)를 통해 희소성을 적극적으로 관리한다. 모든 내부 노드와 리프 노드는 자신의 자식들(자식 노드 또는 복셀)이 ‘활성’ 상태인지, 즉 배경 값과 다른 유의미한 데이터를 담고 있는지 여부를 나타내는 비트마스크를 가진다.1 예를 들어, 8×8×8 리프 노드는 512개의 복셀 각각의 활성 상태를 나타내는 512비트(64바이트) 크기의 비트마스크를 갖는다. 데이터에 접근하거나 그리드를 순회할 때, 이 비트마스크를 먼저 검사하여 비활성 상태인 자식 노드나 복셀 영역 전체를 신속하게 건너뛸 수 있다. 이는 특히 활성 복셀만 순회하는 이터레이터의 성능을 극적으로 향상시키는 핵심 요소이다.1
VDB의 계층적 구조와 인덱싱 방식은 현대 컴퓨터의 가상 메모리 시스템이 작동하는 방식과 놀라울 정도로 유사하다. 가상 메모리 시스템은 페이지 테이블(Page Table)이라는 다단계 트리 구조를 사용하여 프로그램의 거대한 논리 주소 공간을 실제 물리 메모리 주소로 변환(address translation)한다. 이 과정의 속도를 높이기 위해 TLB(Translation Lookaside Buffer)라는 고속 캐시를 사용한다. VDB의 구조는 이러한 하드웨어적 접근법을 소프트웨어적으로 정교하게 모방한 것으로 볼 수 있다.10 VDB의 거대한 3D 인덱스 공간은 논리 주소 공간에, 루트-내부-리프 노드로 이어지는 트리는 페이지 테이블에, 그리고 실제 데이터가 저장된 리프 노드의 메모리 위치는 물리 주소에 해당한다. 특히, VDB의 Value Accessor가 사용하는 소프트웨어 캐시는 최근 접근한 노드의 주소 변환 결과를 저장하여 후속 접근을 가속화하는데 1, 이는 CPU의 TLB와 정확히 동일한 역할을 수행한다. 경쟁 자료 구조인 SPGrid가 VDB의 소프트웨어 캐시 대신 하드웨어 TLB를 직접 활용하도록 설계되었다는 점은 10, VDB의 설계 철학이 하드웨어 메모리 관리 방식과 얼마나 깊은 연관성을 갖는지 명확히 보여준다.
또한, 토폴로지와 데이터의 분리는 단순한 메모리 절약을 넘어 ‘알고리즘적 유연성’이라는 더 큰 가치를 제공한다. 표면적으로 이 분리는 동일한 공간 구조를 여러 데이터 그리드(밀도, 온도 등)가 공유하여 메모리를 절약하는 데 사용된다.8 하지만 더 깊은 차원에서 이는 알고리즘의 분리를 가능하게 한다. 예를 들어, 충돌 감지, 최근접 이웃 탐색, 거리 필드 계산과 같은 기하학적 연산은 대부분 복셀의 실제 값보다는 토폴로지, 즉 활성 복셀의 위치에만 의존한다. VDB는 토폴로리만 순회하는 이터레이터와 값을 포함하여 순회하는 이터레이터를 별도로 제공함으로써 8, 기하 연산은 가벼운 토폴로리 트리만 순회하고, 렌더링이나 물리 계산처럼 실제 값이 필요한 경우에만 데이터 블록에 접근하도록 할 수 있다. 이러한 아키텍처 덕분에
VDB-GPDF 14나 로보틱스의 3D 재구성 9 같은 복잡한 응용 프로그램에서, 맵의 구조(토폴로지)를 구축하는 작업과 표면의 색상이나 거리 값(데이터)을 갱신하는 작업을 독립적으로, 심지어 병렬적으로 처리할 수 있는 강력한 알고리즘적 기반이 마련된다.
VDB의 설계는 단순히 메모리를 효율적으로 사용하는 것을 넘어, 데이터 접근 및 조작의 성능을 극대화하는 데 초점이 맞춰져 있다. 특히 평균 $O(1)$ 랜덤 접근과 캐시 친화적인 순차 접근은 VDB를 다른 희소 자료 구조와 차별화하는 핵심 성능 특성이다.
전통적인 트리 기반 자료 구조의 탐색 시간 복잡도는 일반적으로 트리의 높이에 비례하는 \(O(\log N)\)으로 알려져 있다. 하지만 VDB는 평균(average) $O(1)$ 랜덤 접근 성능을 제공한다고 주장하는데 2, 이는 이론과 실제 사이의 간극처럼 보일 수 있다. 이 놀라운 성능은 다음 세 가지 핵심 원리의 조합을 통해 달성된다.
Value Accessor 객체는 내부적으로 캐시를 유지한다.1 사용자가 특정 복셀에 접근하면, Value Accessor는 루트 노드부터 해당 복셀이 포함된 리프 노드까지의 경로(path)에 있는 각 레벨의 노드 포인터들을 캐시에 저장한다. 이후 사용자가 이전에 접근했던 복셀과 공간적으로 인접한 다른 복셀에 접근할 경우(이는 시뮬레이션 및 렌더링에서 매우 흔한 패턴이다), Value Accessor는 루트부터 다시 탐색을 시작하는 대신 캐시된 상위 또는 중간 레벨 노드 포인터를 재사용하여 목표 리프 노드까지의 경로를 훨씬 짧게 단축한다. 이 캐싱 덕분에 연속적인 접근에 대한 상각(amortized) 시간 복잡도가 실질적으로 \(O(1)\)에 수렴하게 된다.결론적으로, VDB의 $O(1)$ 성능 주장은 모든 접근이 단일 연산으로 끝난다는 이론적 시간 복잡도에 대한 선언이 아니라, 일반적인 작업 부하(spatially coherent access) 하에서 상각 실행 시간이 상수처럼 동작한다는 ‘실질적 처리량(Amortized Throughput)’에 대한 공학적 선언으로 해석해야 한다. 이는 VDB가 순수 컴퓨터 과학의 이론적 보장보다는, 고성능 컴퓨팅(HPC) 분야에서 실제 애플리케이션의 성능을 극대화하기 위한 실용적인 문제 해결 방식에 더 가깝다는 것을 보여준다.
VDB는 현대 CPU 아키텍처의 핵심인 캐시 메모리를 최대한 활용하도록 설계되었다. 이는 데이터 지역성(data locality) 원리를 극대화함으로써 달성된다.
VDB의 리프 노드는 $8×8×8$과 같은 작은 3D 블록 단위로 복셀 데이터를 저장하며, 이 데이터 블록은 메모리 상에 연속적으로 배치된다.8 따라서 애플리케이션이 특정 복셀 하나에 접근하면, 해당 복셀을 포함하는 전체 데이터 블록이 CPU의 L1, L2 캐시 라인(cache line)에 함께 로드될 확률이 매우 높다. 이로 인해 스텐실(stencil) 연산(예: 유체 시뮬레이션에서 이웃 복셀 6개의 값을 참조하는 연산)이나 특정 영역을 순차적으로 순회하는 작업 시, 대부분의 메모리 접근이 주 메모리가 아닌 매우 빠른 캐시 메모리 내에서 처리된다. 이는 캐시 미스(cache miss) 발생을 최소화하여, 희소 자료 구조임에도 불구하고 마치 밀집 배열(dense array)에 접근하는 것과 유사한 높은 메모리 대역폭과 처리량을 달성하게 해준다.10 VDB가 캐시 일관성을 고려한(cache-coherent) 빠른 데이터 접근을 제공하도록 설계되었다는 언급은 바로 이 점을 의미한다.2
OpenVDB는 사용 사례에 따라 최적의 성능을 낼 수 있도록 두 가지 주요 데이터 접근 메커니즘을 제공한다.
값 접근자 (Value Accessor): 좌표 기반의 랜덤 접근에 최적화된 ‘가속기’ 객체이다.1 앞서 설명한 경로 캐싱 기능을 내장하여 반복적인 랜덤 접근 성능을 극대화한다.
getValue(ijk) 및 setValue(ijk, value)와 같은 메서드를 제공하여 직관적인 사용이 가능하다.13 하지만 중요한 점은, 이 내부 캐싱 메커니즘 때문에 Value Accessor 객체 자체가 본질적으로 스레드에 안전하지 않다(not thread-safe)는 것이다. 따라서 멀티스레드 환경에서는 각 스레드가 자신만의 독립적인 Value Accessor 인스턴스를 생성하여 사용해야 한다.1
이터레이터 (Iterators): 데이터 그리드의 순차적인 접근을 위해 설계된 강력한 도구이다. OpenVDB는 다양한 목적에 맞는 특화된 이터레이터를 제공하여 불필요한 연산을 최소화한다.8
ValueOnCIter / ValueOnIter: ‘활성(active)’ 상태인 복셀들만 건너뛰며 순회한다. 희소 데이터를 처리하는 대부분의 작업에서 핵심적으로 사용된다.
ValueOffIter: ‘비활성(inactive)’ 상태인 복셀들, 즉 배경 값을 가진 영역을 순회한다.
LeafNodeIter: 복셀 단위가 아닌 리프 노드 단위로 순회한다. 이는 각 스레드가 서로 다른 리프 노드를 독립적으로 처리하는 방식의 병렬 처리에 매우 유용하다.13
이러한 이터레이터들은 내부적으로 각 노드의 비트마스크를 효율적으로 검사하여 데이터가 없는 빈 공간을 통째로 건너뛰기 때문에, 전체 그리드를 무작정 순회하는 것보다 월등히 높은 성능을 보인다.1
VDB의 이론적 개념은 오픈소스 라이브러리인 OpenVDB를 통해 실제 애플리케이션에서 널리 사용되고 있다. OpenVDB는 VDB 자료 구조의 C++ 구현체이자, 이를 활용한 다양한 도구와 유틸리티의 집합이다. OpenVDB의 에코시스템을 이해하기 위해서는 핵심 구성 요소인 Grid, Tree, Transform의 관계를 파악하는 것이 중요하다.
OpenVDB에서 데이터를 다룰 때 사용자는 주로 세 가지 핵심 객체와 상호작용하게 된다.8
Tree: 지금까지 설명한 VDB의 핵심 계층적 자료 구조 그 자체이다. Tree는 저장될 데이터의 타입(예: float, bool, openvdb::Vec3s)과 트리의 구성(레벨 수, 각 레벨의 분기 계수 등)이 C++ 템플릿 파라미터로 결합되어 구체적인 타입으로 정의된다.1 예를 들어, 부동소수점 데이터를 저장하는 표준 4레벨 트리는 openvdb::v11_0::tree::Tree<openvdb::v11_0::tree::RootNode<openvdb::v11_0::tree::InternalNode<openvdb::v11_0::tree::InternalNode<openvdb::v11_0::tree::LeafNode<float, 3u> , 4u>, 5u> > > 와 같이 복잡한 템플릿으로 정의되며, 보통 openvdb::FloatTree와 같은 타입 별칭(type alias)으로 사용된다.
Grid: Tree를 감싸는 고수준의 컨테이너 객체이다. Grid는 핵심 데이터인 Tree에 더하여, 그리드의 이름이나 단위와 같은 메타데이터, 그리고 가장 중요하게는 Transform 객체를 포함한다.8 대부분의 경우, 애플리케이션 개발자는 저수준의 Tree 객체를 직접 조작하기보다는 Grid 객체가 제공하는 편리한 인터페이스(예: getAccessor())를 통해 데이터에 접근한다. 하나의 Tree는 여러 Grid 객체에 의해 스마트 포인터로 참조될 수 있으며, 각 Grid는 서로 다른 Transform을 가질 수 있다. 이를 통해 동일한 볼륨 데이터를 여러 다른 위치에 복사본 없이 배치(instancing)하는 것이 가능하다.8
Transform: 복셀의 이산적인 정수 인덱스 좌표 $(i, j, k)$를 실제 물리적 공간의 연속적인 월드 좌표 $(x, y, z)$로 변환하는 역할을 담당한다.8
Transform을 통해 그리드 전체를 이동(translation), 회전(rotation), 크기 조절(scaling)할 수 있다. 이 변환 로직은 내부적으로 Map이라는 객체에 의해 관리되며, applyMap (인덱스 -> 월드) 및 applyInverseMap (월드 -> 인덱스) 메서드를 제공해야 한다.8
OpenVDB의 높은 성능과 유연성은 C++ 템플릿 메타프로그래밍(template metaprogramming)의 광범위한 활용에 크게 의존한다.1 사용자는 저장하고자 하는 데이터의 타입(float, int, bool 등)뿐만 아니라, 트리의 계층 구조(예: 레벨 2, 3, 4의 로그 차원)를 컴파일 시점에 자유롭게 지정하여 자신만의 커스텀 그리드를 정의할 수 있다.
이러한 정적 구성 방식은 런타임에 설정을 변경하는 방식에 비해 명백한 성능상의 이점을 가진다. 컴파일러는 특정 그리드 타입(예: FloatGrid와 BoolGrid)에 대해 모든 함수 호출과 데이터 접근을 인라이닝(inlining)하고, 타입에 특화된 최적화된 기계어 코드를 생성할 수 있다. 이는 가상 함수 호출이나 런타임 타입 체크와 같은 오버헤드를 원천적으로 제거하여 최고 수준의 성능을 이끌어낸다.1 OpenVDB의 API 설계는 이처럼 성능을 최우선으로 고려하는 철학을 명확히 보여준다.
Value Accessor와 같은 가속기 객체의 사용이나 컴파일 타임 구성은, 사용 편의성이나 완전한 추상화보다는 ‘전문가 사용자가 올바르게 사용할 때 최고의 성능을 얻을 수 있다’는 설계 사상을 반영한다. 이는 OpenVDB가 범용 라이브러리가 아니라, 성능이 가장 중요한 VFX 및 시뮬레이션 분야의 요구에 철저히 맞춰진 전문가용 도구임을 시사한다.
OpenVDB가 멀티코어 CPU 환경에서 효율적으로 작동하는지, 즉 스레드에 안전한지에 대한 질문의 답은 “예, 그리고 아니오(Yes and no)”이다.1
Value Accessor의 내부 캐시 상태나, 새로운 노드를 할당하는 메모리 관리 로직이 여러 스레드의 동시 접근을 고려하여 설계되지 않았기 때문이다.Value Accessor 인스턴스를 생성하여 사용함으로써 캐시 상태의 충돌을 피해야 한다.1VDB의 특성과 장점을 더 명확히 이해하기 위해, 이를 다른 주요 볼류메트릭 데이터 표현 방식들과 비교 분석하는 것은 매우 유용하다.
옥트리는 공간을 재귀적으로 8개의 동일한 크기의 자식 노드로 분할하는, 가장 잘 알려진 3D 공간 분할 자료 구조 중 하나이다. VDB와 옥트리는 모두 계층적 구조를 갖지만 몇 가지 중요한 차이점이 있다.
적응성(Adaptivity): 옥트리는 데이터가 밀집된 영역은 깊게 분할하고 희소한 영역은 얕게 분할하는 진정한 의미의 ‘공간 적응성(spatial adaptivity)’을 가진다. 즉, 공간에 따라 해상도 자체가 달라질 수 있다. 반면, OpenVDB의 표준 구현에서 트리는 모든 리프 노드가 동일한 깊이에 위치하는 고정된 높이를 가진다. 따라서 VDB는 데이터 값의 존재 유무(활성/비활성)에 따른 희소성은 완벽하게 표현하지만(OpenVDB 문서에서는 이를 ‘adaptive in the first sense’라고 표현), 밉맵(mipmap)처럼 공간에 따라 해상도 자체를 다르게 하지는 않는다(‘not adaptive in the second sense’).1
다음 표는 VDB와 다른 주요 볼류메트릭 자료 구조들의 핵심 특성을 요약하여 비교한 것이다.
| 특성 (Attribute) | 밀집 그리드 (Dense Grid) | 옥트리 (Octree) | VDB (Volumetric Dynamic B+tree) | 해싱 그리드 (Hashing Grid) |
|---|---|---|---|---|
| 핵심 아이디어 | 3차원 배열 | 공간의 재귀적 8분할 | 넓고 얕은 B+tree 유사 구조 | 공간 좌표의 해시 매핑 |
| 메모리 사용량 | 매우 높음 (O(N3)) 7 | 희소성에 비례 (중간) | 희소성에 비례 (낮음, 압축 효율 높음) 8 | 희소성에 비례 (매우 낮음) |
| 랜덤 접근 속도 | O(1) | O(logN)15 | 평균 O(1) 2 | 평균 O(1), 최악의 경우 충돌 처리 비용 |
| 순차/이웃 접근 | 매우 빠름 (최적) | 보통 (포인터 추적 필요) | 매우 빠름 (캐시 효율적) 10 | 느림 (지역성 보장 안됨) |
| 동적 업데이트 | 비효율적 | 보통 (트리 재구성 필요 가능) | 매우 효율적 (평균 O(1)) 4 | 매우 효율적 |
| 주요 응용 분야 | 저해상도, 밀집 데이터 | 공간 분할, 충돌 감지 | VFX, 시뮬레이션, 렌더링, 로보틱스 4 | 실시간 3D 스캐닝, 동적 재구성 |
VDB는 그 뛰어난 성능과 유연성을 바탕으로 초기 개발 목적인 시각 효과 분야를 넘어 다양한 첨단 기술 분야에서 핵심적인 역할을 수행하고 있다. 또한, 컴퓨팅 환경의 변화에 발맞춰 끊임없이 진화하고 있다.
VDB는 매우 성공적인 자료 구조이지만, 근본적인 한계 또한 존재한다. 이러한 한계를 극복하기 위해 VDB 생태계는 새로운 기술과 결합하며 진화하고 있다.
이러한 VDB의 진화 방향은 현대 컴퓨팅의 두 가지 거대한 기술적 흐름을 명확히 따르고 있다. 첫째는 하드웨어 아키텍처의 변화이다. 컴퓨팅의 중심이 멀티코어 CPU에서 대규모 병렬 처리가 가능한 GPU로 이동함에 따라, VDB의 핵심 철학은 유지하되 구현을 GPU에 맞게 재설계한 NanoVDB가 등장했다. 둘째는 데이터 표현 패러다임의 변화이다. 데이터 표현 방식이 모든 값을 명시적으로 저장하는 방식(explicit storage)에서, 함수나 신경망을 통해 연속적인 공간을 표현하는 암시적 표현(implicit representation)으로 변화하고 있다. NeuralVDB는 이 두 세계를 영리하게 결합한 시도이다. VDB의 효율적인 희소 공간 분할 능력과 신경망의 강력한 데이터 압축 및 표현 능력을 결합함으로써, 두 방식의 장점을 모두 취하는 하이브리드 접근법을 제시한다. 따라서 VDB의 미래는 단일 구조의 점진적 개선을 넘어, 새로운 하드웨어와 데이터 표현 패러다임을 적극적으로 수용하는 ‘하이브리드 자료 구조’로 진화하고 있으며, 이는 VDB가 여전히 살아있는 생태계임을 보여준다.
VDB(Volumetric Dynamic B+tree)는 넓고 얕은 B+tree 유사 구조, 토폴로지와 데이터의 근본적인 분리, 그리고 현대 CPU 캐시 아키텍처에 최적화된 설계를 통해, 희소 볼류메트릭 데이터를 다루는 데 있어 세 가지 핵심적인 난제를 동시에 해결한 혁신적인 자료 구조이다. 첫째, 뛰어난 메모리 효율성을 통해 고해상도 데이터도 실용적인 메모리 공간 내에서 처리할 수 있게 했으며, 둘째, 경로 캐싱과 직접 좌표 해싱을 통해 평균 \(O(1)\)의 빠른 랜덤 및 순차 접근 속도를 달성했다. 셋째, 복잡한 분할/병합 로직 없이 유연하고 효율적인 동적 토폴로지 지원을 가능하게 했다.
시각 효과(VFX) 산업의 특정 문제를 해결하기 위해 탄생했지만, VDB의 설계 철학이 가진 근본적인 우수성은 그 적용 범위를 로보틱스, 과학 컴퓨팅, 의료 영상 등 희소 고차원 데이터를 다루는 거의 모든 분야로 확장시켰고, 오늘날 이들 분야에서 표준적인 핵심 도구 중 하나로 자리매김했다.
더 나아가, NanoVDB와 NeuralVDB의 등장은 VDB가 과거의 유산에 머물러 있는 정적인 기술이 아니라, 컴퓨팅 환경의 급격한 변화에 발맞춰 끊임없이 진화하는 살아있는 생태계임을 명확히 보여준다. GPU 컴퓨팅의 부상과 인공지능 기반의 새로운 데이터 표현 패러다임이라는 거대한 흐름과 적극적으로 융합함으로써, VDB는 미래에도 더욱 방대하고 복잡해질 가상 세계를 시뮬레이션하고, 분석하며, 시각화하는 데 있어 핵심적인 역할을 계속해서 수행할 것으로 전망된다. VDB는 앞으로도 데이터 구조 설계가 어떻게 특정 도메인의 문제를 해결하고, 나아가 기술의 발전을 선도할 수 있는지를 보여주는 탁월한 사례로 남을 것이다.
| OpenVDB 11.0 Updates | LightWave, accessed August 5, 2025, https://docs.lightwave3d.com/2025/openvdb-11-0-updates.html |