kdtree - 重新打包体素数据以实现高效存储

Question

我有 3D 体素数据，我想重新打包它以提高内存效率和快速访问。数据以常规八叉树的形式生成，每个单元格一个整数值。不幸的是，数据并不稀疏，但应该连接具有相同值的单元格。

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

我目前的想法是使用 kD-Tree，最好是左平衡的，但我不确定是否有有效的算法来生成它。我有一些想法，但我希望这是已经建立算法的问题之一，或者至少是我可以在谷歌上搜索的名称。

Answer 1

OctoMap怎么样？据我了解，它就像一个八叉树，但将相邻的占用区域合并为区域以节省内存。但我对此知之甚少。

编辑

你也可以试试我的PH-Tree。它像八叉树一样工作，但内存效率很高，因为每个节点只存储与父节点不同的位。您实际上可以将整数值存储为第四维。与直觉相反，4D 树可能比 3D 树需要更少的空间，并且可能更快（解释在 PDF 中，可以在上面的链接中找到）。如果您的整数是第 4 维，那么树中的任何子树都只会包含具有“相似”整数的条目，这对您的情况是否足够？此外，任何节点都只包含近邻，但近邻不一定在相同（或相邻）节点中。

Answer 2

另一个链接：http ://www.openvdb.org/ 。为什么我问了这个问题后才发现这个？这就像在超市里要东西，却发现你站在它旁边。

我最终做了一些更简单的事情，因为我需要一个解决方案：我将体素体积转换为一堆 2D 平面，每个平面存储在哪个点值更改为下一个更高平面。这样体素数据只会垂直压缩，但目前看来“足够好”。如果我有空闲时间，我会计算其他数据结构的数字（空间需求与性能）。