重新包装体素数据以获得高效存储

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平面的堆叠，每个平面中，保存在该点值变化到下一个更高的境界。这样，体素数据只能垂直压缩，但现在看起来“足够好”。如果我有空闲时间，我会为其他数据结构的数字（空间需求与性能）紧密结合。