重新包裝體素數據以獲得高效存儲

Question

我已經獲得了三維體素數據，並且我想重新打包以提高內存效率和快速訪問。數據以常規八叉樹生成，每個單元格一個整數值。不幸的是，數據並不稀疏，但應該連接具有相同值的單元。

Example for one slice: 
[11122] 
[11223] 
[12222] 
[44444] 

我目前的想法是使用kD樹，最好是左平衡，但我不知道是否有一個有效的算法來生成這個。 我已經有了一些想法，但我希望這是一個已經建立的算法，或至少一個名字我可以谷歌的問題之一。

Answer 1

OctoMap怎麼樣？據我所知，它就像八叉樹，但將相鄰的佔用區域合併到區域以節省內存。但我對此不甚瞭解。

編輯

你也可以試試我PH-Tree。它像八叉樹一樣工作，但內存效率很高，因爲每個節點只存儲與父節點不同的位。您實際上可以將您的整數值存儲爲第四維。與直覺相反，4D樹可能比3D樹需要更少的空間，並且速度可能更快（可以在上面的鏈接中找到PDF的解釋）。如果你的整數是第四維，那麼樹中的任何子樹只會有「相似」整數的條目，可能對你的情況來說足夠了？此外，任何節點只包含近鄰，但近鄰不一定在相同（或相鄰）節點中。

Answer 2

另一個鏈接：http://www.openvdb.org/。爲什麼我在問這個問題後才發現這個問題？這就像在超市裏要求什麼東西，只是爲了發現你站在旁邊。

我結束了做簡單的東西，因爲我需要一個解決方案：我的體素體積轉換成2D平面的堆疊，每個平面中，保存在該點值變化到下一個更高的境界。這樣，體素數據只能垂直壓縮，但現在看起來「足夠好」。如果我有空閒時間，我會爲其他數據結構的數字（空間需求與性能）緊密結合。