math - 使用 morton 代码压缩数据 - 如何？

Question

我一直在阅读有关 morton 代码的内容，并且我发现本地性保留在生成的数字序列中。

我不明白的是如何使用这些信息来压缩数据或有效地并行构造数据。

资料来源：http ://www.forceflow.be/2013/10/07/morton-encodingdecoding-through-bit-interleaving-implementations/

Answer 1

莫顿排序本身并不与数据压缩相关。这只是一种在内存中布置空间数据的方式，这样对连续空间块的查询往往会映射到连续的内存块——从而提高缓存效率。

在您引用的链接中引用的算法论文中，莫顿顺序用于提高磁盘读写效率。

该算法将复杂的三角形网格转换为高分辨率体素中间表示（按莫顿顺序存储），然后将该表示转换为稀疏（压缩）输出形式。

莫顿顺序的一个特性是它匹配从深度优先遍历八叉树（或二维四叉树）获得的顺序。这提供了输出八叉树数据结构和中间数据结构之间的方便对齐。因此，在输出八叉树中构造一个节点需要来自中间结构中一组连续索引的数据。这让算法在给定的步骤中只读取它需要的数据，保持低内存占用和高缓存效率。

所以这里的 Morton 排序本身并没有提供特别的压缩或并行化优势——你可以编写一个等效的算法，其压缩输出相同，在其中间使用线性排序，但它的写入和读取会更加分散，所以它可能会处理数据的速度几乎没有。

但是，如果您使用四叉树或八叉树来压缩数据，莫顿排序可以使您的数据索引更清晰，性能更高。