VDB / OpenVDB
VDB 是一種淺而寬、高度平衡的階層式稀疏體積資料結構，概念近似 B+ 樹：常見設定為以雜湊表或 std::map 實作的可動態擴充根節點，接兩層固定分支 32³ 與 16³ 的內部節點，最底層為 8³ 體素的葉節點，並以位元遮罩分開編碼拓樸與數值。由於深度與分支在編譯期固定，可直接由全域座標以位元運算求得各層偏移，隨機存取平均為 O(1)，再以快取最近走訪節點的反向（由下而上）走訪加速空間連貫的存取。原為電影特效的動態稀疏體積與位準集設計，後被 VDBFusion 用來儲存 TSDF。
本頁內容
A hierarchical, B+tree-like sparse volume data structure with a virtually infinite index space and average O(1) random access.
技術屬性
欄位內容為文獻擷取紀錄的原文用語（英文），以原文為據；「未查證」表示本研究尚未讀到該資訊，不代表該方法不具備此能力。
| 感測輸入 | 未記錄 |
|---|---|
| 原文測試平台 | 未記錄 |
| 狀態估計 | 不適用 |
| 資料關聯 | 不適用 |
| 時間表示 | 不適用 |
| 去畸變 | 不適用 |
| 迴圈閉合 | 不適用 |
| 全域最佳化 | none |
| 地圖表示 | shallow height-balanced B+tree-like sparse grid: dynamic root node (hash map or std::map) over internal nodes with 32^3 and 16^3 branching and 8^3-voxel leaf nodes; bit masks encode active topology and child pointers, values stored at any level as voxels or tiles; optional out-of-core leaf buffers |
| 先驗資訊 | none |
| 可輸出幾何 | sparse volumetric grids such as narrow-band level sets and density volumes; meshes and rendered images are downstream products (Fig. 4, Sec. 4.5-4.7) |
| 計算需求 | CPU, C++ templates; benchmarks on dual quad-core Intel Nehalem-EP W5590 with 48 GB RAM, single thread unless noted; e.g. one Enright step at 4096^3 took 39.1 s single-threaded and 4.39 s multithreaded (Sec. 5, Table III) |
使用設備
原文使用的感測器、運算硬體與載具（equipment）。型號保留原文寫法，連結到設備頁中同一型號的歸併名稱；角色依原文用途分為方法輸入、資料集感測器、執行運算平台、參考或真值量測（reference or ground truth）與比較對象設備。
| 類別 | 型號（原文寫法） | 角色 | 資料集 | 原文規格 | 出處 |
|---|---|---|---|---|---|
| 運算硬體 | dual quad-core Intel Nehalem-EP W5590 | 執行運算平台 | 未標示 | 4x32KB L1, 4x256KB L2, 8MB L3, 48 GB DDR3-1333 RAM, Red Hat Enterprise Linux 5.4 | (Museth, 2013, Sec. 5) |
作者報告的優勢與限制
優勢
- Fast average O(1) insert/retrieve/delete without topology restrictions (abstract).
- Level-set advection about 3.9x faster than DT-Grid on one thread and 30x to 35x faster when multithreaded (Table III).
- Author summary: over 10x faster spatially coherent lookup, 3x to 4x faster writes, 7x faster dilation and over 100x faster CSG than DT-Grid (Sec. 7, Tables VI, VII, IX).
- A dragon level set with 228 million active voxels needs 1 GB against about a quarter TB for a dense grid (Fig. 4).
限制
- Less memory efficient than DT-Grid for narrow-band level sets; the author states the difference is under 1.5x for [Hash,5,4,3] in Table II (the tabulated values give about 1.7x for the Enright set, 420 vs 253 MB, and 1.9x for the 8x variant, 2,257 vs 1,182 MB) and under 2x in the conclusion, because leaf nodes are only partly filled with active voxels (Sec. 6, 7, Tables II and IV).
- Large branching factors make a single VDB a poor choice for multiresolution sampling; mipmapping within one tree is not supported (Sec. 6).
- Out-of-core mode is read-only and does not support dynamic topology or stencil computations (Sec. 5.3, 6).
- Random insertion and deletion are not thread safe; the authors use one grid per thread and merge (Appendix B).
- Absolute random-access timings depend on the test, hardware and compiler; only relative times are reported (Sec. 5.1).
營建工程相關證據
原文以電影特效的雲、流體與位準集示範，未涉及量測或營建；與本主題的關係在於 VDBFusion 等 LiDAR TSDF 管線採用其資料結構（推論）。
報告的性能數據
以下是原文作者報告的性能數值（author-reported results），不是本研究重新量測的結果。每張圖只並列同一個比較組（comparison group，同一張表、同一組實驗設定）內的方法；不同比較組之間的數值不可直接比較，也不構成排名。
本方法共出現在 4 個比較組，合計 96 筆紀錄。
Museth, 2013 · Table II 本方法 48 筆
表格設定（擷取紀錄原文）：Enright sphere and 8x variant at effective resolution 4096^3 (51,033,829 and 263,418,462 active voxels, 10-voxel band); relative time per random lookup (1 unit, about half a second for 10^7 x 100 lookups, equals the cached leaf-coherent VDB lookup); VDB times listed are the worst-case top-down traversal (Sec. 3.1); memory in MB as reported by the OS; single thread (Museth, 2013, Table II)
memory footprint (MB)，Enright test · 4096^3
只並列這張表在相同設定下報告的方法；以「本方法：」開頭者為本頁方法。失敗、未執行與未報告以標記呈現，不是 0。
按 Tab 進入圖表後，用上下方向鍵逐一瀏覽各類別，Esc 關閉提示框；也可開啟表格檢視閱讀全部數值。
這些是 Museth, 2013 在此表設定下報告的數值（author-reported results），只能在同一個比較組內對照，不代表方法在其他資料或設定下的表現。
資料來源作者報告值(Museth, 2013, Table II)
| 方法（原文寫法） | 報告值 | 出處 |
|---|---|---|
| [7,6,5,4,3]本方法原文提出硬體：Dual quad-core Intel Nehalem-EP W5590, 48 GB DDR3-1333, RHEL 5.4; single thread unless noted | 439 MB | (Museth, 2013, Table II) |
| [6,5,4,3]本方法原文提出硬體：Dual quad-core Intel Nehalem-EP W5590, 48 GB DDR3-1333, RHEL 5.4; single thread unless noted | 422 MB | (Museth, 2013, Table II) |
| [6,4,3]本方法原文提出硬體：Dual quad-core Intel Nehalem-EP W5590, 48 GB DDR3-1333, RHEL 5.4; single thread unless noted | 420 MB | (Museth, 2013, Table II) |
| [10,3]本方法原文提出硬體：Dual quad-core Intel Nehalem-EP W5590, 48 GB DDR3-1333, RHEL 5.4; single thread unless noted | 8723 MB | (Museth, 2013, Table II) |
| [6,5,4,5]本方法原文提出硬體：Dual quad-core Intel Nehalem-EP W5590, 48 GB DDR3-1333, RHEL 5.4; single thread unless noted | 1078 MB | (Museth, 2013, Table II) |
| [6,5,4,4]本方法原文提出硬體：Dual quad-core Intel Nehalem-EP W5590, 48 GB DDR3-1333, RHEL 5.4; single thread unless noted | 625 MB | (Museth, 2013, Table II) |
| [6,5,4,3] (row 7)本方法原文提出硬體：Dual quad-core Intel Nehalem-EP W5590, 48 GB DDR3-1333, RHEL 5.4; single thread unless noted | 422 MB | (Museth, 2013, Table II) |
| [6,5,4,2]本方法原文提出硬體：Dual quad-core Intel Nehalem-EP W5590, 48 GB DDR3-1333, RHEL 5.4; single thread unless noted | 389 MB | (Museth, 2013, Table II) |
| [6,6,6,6]本方法原文提出硬體：Dual quad-core Intel Nehalem-EP W5590, 48 GB DDR3-1333, RHEL 5.4; single thread unless noted | 1977 MB | (Museth, 2013, Table II) |
| [5,5,5,5]本方法原文提出硬體：Dual quad-core Intel Nehalem-EP W5590, 48 GB DDR3-1333, RHEL 5.4; single thread unless noted | 1072 MB | (Museth, 2013, Table II) |
| [4,4,4,4]本方法原文提出硬體：Dual quad-core Intel Nehalem-EP W5590, 48 GB DDR3-1333, RHEL 5.4; single thread unless noted | 625 MB | (Museth, 2013, Table II) |
| [3,3,3,3]本方法原文提出硬體：Dual quad-core Intel Nehalem-EP W5590, 48 GB DDR3-1333, RHEL 5.4; single thread unless noted | 413 MB | (Museth, 2013, Table II) |
| [Hash,4,3,2]本方法原文提出硬體：Dual quad-core Intel Nehalem-EP W5590, 48 GB DDR3-1333, RHEL 5.4; single thread unless noted | 362 MB | (Museth, 2013, Table II) |
| [Hash,5,4,3]本方法原文提出硬體：Dual quad-core Intel Nehalem-EP W5590, 48 GB DDR3-1333, RHEL 5.4; single thread unless noted | 420 MB | (Museth, 2013, Table II) |
| [Map,4,3,2]本方法原文提出硬體：Dual quad-core Intel Nehalem-EP W5590, 48 GB DDR3-1333, RHEL 5.4; single thread unless noted | 362 MB | (Museth, 2013, Table II) |
| [Map,5,4,3]本方法原文提出硬體：Dual quad-core Intel Nehalem-EP W5590, 48 GB DDR3-1333, RHEL 5.4; single thread unless noted | 420 MB | (Museth, 2013, Table II) |
| [F3DSF,3]硬體：Dual quad-core Intel Nehalem-EP W5590, 48 GB DDR3-1333, RHEL 5.4; single thread unless noted | 33156 MB | (Museth, 2013, Table II) |
| [F3DSF,4]硬體：Dual quad-core Intel Nehalem-EP W5590, 48 GB DDR3-1333, RHEL 5.4; single thread unless noted | 4698 MB | (Museth, 2013, Table II) |
| [F3DSF,5]硬體：Dual quad-core Intel Nehalem-EP W5590, 48 GB DDR3-1333, RHEL 5.4; single thread unless noted | 1586 MB | (Museth, 2013, Table II) |
| Octree# (depth 13)硬體：Dual quad-core Intel Nehalem-EP W5590, 48 GB DDR3-1333, RHEL 5.4; single thread unless noted | 390 MB | (Museth, 2013, Table II) |
| Octree* (depth 18)硬體：Dual quad-core Intel Nehalem-EP W5590, 48 GB DDR3-1333, RHEL 5.4; single thread unless noted | 390 MB | (Museth, 2013, Table II) |
| DT-Grid硬體：Dual quad-core Intel Nehalem-EP W5590, 48 GB DDR3-1333, RHEL 5.4; single thread unless noted | 253 MB | (Museth, 2013, Table II) |
Museth, 2013 · Table IV 本方法 24 筆
指標memory footprint (MB)
表格設定（擷取紀錄原文）：Memory footprint (MB) of the standard Enright dataset; VDB given in-core and partially out-of-core; no compression or quantization in-core; F3DSF block size 16^3 (Museth, 2013, Table IV)
memory footprint (MB)，Enright test · 512^3
只並列這張表在相同設定下報告的方法；以「本方法：」開頭者為本頁方法。失敗、未執行與未報告以標記呈現，不是 0。
按 Tab 進入圖表後，用上下方向鍵逐一瀏覽各類別，Esc 關閉提示框；也可開啟表格檢視閱讀全部數值。
這些是 Museth, 2013 在此表設定下報告的數值（author-reported results），只能在同一個比較組內對照，不代表方法在其他資料或設定下的表現。
資料來源作者報告值(Museth, 2013, Table IV)
| 方法（原文寫法） | 報告值 | 出處 |
|---|---|---|
| DT-Grid硬體：Dual quad-core Intel Nehalem-EP W5590, 48 GB DDR3-1333, RHEL 5.4; single thread unless noted | 4.3 MB | (Museth, 2013, Table IV) |
| [F3DSF,4]硬體：Dual quad-core Intel Nehalem-EP W5590, 48 GB DDR3-1333, RHEL 5.4; single thread unless noted | 10.5 MB | (Museth, 2013, Table IV) |
| [Hash,4,3,2] in-core本方法原文提出硬體：Dual quad-core Intel Nehalem-EP W5590, 48 GB DDR3-1333, RHEL 5.4; single thread unless noted | 5.7 MB | (Museth, 2013, Table IV) |
| [Hash,4,3,2] out-of-core本方法原文提出硬體：Dual quad-core Intel Nehalem-EP W5590, 48 GB DDR3-1333, RHEL 5.4; single thread unless noted | 1 MB | (Museth, 2013, Table IV) |
| [Hash,5,4,3] in-core本方法原文提出硬體：Dual quad-core Intel Nehalem-EP W5590, 48 GB DDR3-1333, RHEL 5.4; single thread unless noted | 6.7 MB | (Museth, 2013, Table IV) |
| [Hash,5,4,3] out-of-core本方法原文提出硬體：Dual quad-core Intel Nehalem-EP W5590, 48 GB DDR3-1333, RHEL 5.4; single thread unless noted | 0.4 MB | (Museth, 2013, Table IV) |
Museth, 2013 · Table III 本方法 12 筆
指標CPU time per integration step (s)
表格設定（擷取紀錄原文）：CPU seconds for one Enright time step (advection, three renormalizations, narrow-band rebuild; TVD-RK3, WENO5, band 10); [6,5,4,3]|| is multithreaded on two quad-core CPUs (Museth, 2013, Table III)
CPU time per integration step (s)，Enright test · 512^3
只並列這張表在相同設定下報告的方法；以「本方法：」開頭者為本頁方法。失敗、未執行與未報告以標記呈現，不是 0。
按 Tab 進入圖表後，用上下方向鍵逐一瀏覽各類別，Esc 關閉提示框；也可開啟表格檢視閱讀全部數值。
這些是 Museth, 2013 在此表設定下報告的數值（author-reported results），只能在同一個比較組內對照，不代表方法在其他資料或設定下的表現。
資料來源作者報告值(Museth, 2013, Table III)
| 方法（原文寫法） | 報告值 | 出處 |
|---|---|---|
| DT-Grid硬體：Dual quad-core Intel Nehalem-EP W5590, 48 GB DDR3-1333, RHEL 5.4; single thread unless noted | 2.4 s | (Museth, 2013, Table III) |
| [6,5,4,3]本方法原文提出硬體：Dual quad-core Intel Nehalem-EP W5590, 48 GB DDR3-1333, RHEL 5.4; single thread unless noted | 0.61 s | (Museth, 2013, Table III) |
| [6,5,4,3] multithreaded本方法原文提出硬體：Dual quad-core Intel Nehalem-EP W5590, 8 cores | 0.08 s | (Museth, 2013, Table III) |
Museth, 2013 · Table VII 本方法 12 筆
指標dilation time (s)
表格設定（擷取紀錄原文）：CPU seconds for dilating the Enright narrow band by one voxel; Optimal = fastest available algorithm, Brute-Force = VDB random-access insertion (Museth, 2013, Table VII)
dilation time (s)，Enright test · 512^3
只並列這張表在相同設定下報告的方法；以「本方法：」開頭者為本頁方法。失敗、未執行與未報告以標記呈現，不是 0。
- 僅報告範圍
按 Tab 進入圖表後，用上下方向鍵逐一瀏覽各類別，Esc 關閉提示框；也可開啟表格檢視閱讀全部數值。
這些是 Museth, 2013 在此表設定下報告的數值（author-reported results），只能在同一個比較組內對照，不代表方法在其他資料或設定下的表現。
資料來源作者報告值(Museth, 2013, Table VII)
| 方法（原文寫法） | 報告值 | 出處 |
|---|---|---|
| DT-Grid Optimal硬體：Dual quad-core Intel Nehalem-EP W5590, 48 GB DDR3-1333, RHEL 5.4; single thread unless noted | 0.03 s | (Museth, 2013, Table VII) |
| [6,5,4,3] Optimal本方法原文提出硬體：Dual quad-core Intel Nehalem-EP W5590, 48 GB DDR3-1333, RHEL 5.4; single thread unless noted | 無數值僅報告範圍註記（擷取紀錄）：reported as < 0.01 s | (Museth, 2013, Table VII) |
| [6,5,4,3] Brute-Force本方法原文提出硬體：Dual quad-core Intel Nehalem-EP W5590, 48 GB DDR3-1333, RHEL 5.4; single thread unless noted | 0.05 s | (Museth, 2013, Table VII) |
來源
Museth, 2013
（2013）VDB: High-resolution sparse volumes with dynamic topologyACM Transactions on Graphics, 32(3):1-22
DOI 10.1145/2487228.2487235程式碼
同儕審查已出版已讀全文經典查證後修正
相關版本
- 程式碼釋出：OpenVDB (open-source implementation of VDB, per VDBFusion Sec. 3) https://github.com/AcademySoftwareFoundation/openvdb
程式碼：https://github.com/AcademySoftwareFoundation/openvdb（授權：Apache-2.0 (current AcademySoftwareFoundation/openvdb LICENSE; licence of earlier releases not checked)）。有公開程式碼不等於已被重現，也不代表目前版本與論文版本相同。