[toc]
# 序言
通俗的来讲， Morton Code 的目的是 将N维数据降低为1维数据 但是为什么很多文章都在说 Morton Code 可以有效的提高稀疏数据结构的运行效率呢？
我准备以下面一篇文章 Out-of-Core Construction of Sparse Voxel Octrees 为题进行探讨 Out-of-Core Construction of Sparse Voxel Octrees Morton encoding/decoding through bit interleaving: Implementations
# A. 稀疏八叉树的流程
# MortonCode
MortonCode 通常用来对数据进行降维，通常网上会给出这样一张图 
这里简单介绍下
我们知道，在游戏或者 3D 空间内的数据很可能是稀疏的，即某一块没有，某一块有，这就导致在进行一些操作时会出现很严重的 CacheMiss
而 Morton 编码则可以将二维和三维降低到一维，即以一种固定的顺序去遍历二维 / 三维数据，并将其编码到一维的下标上
常见的 Morton 码如上图所示，其编码后的遍历顺序是一个类似于 Z 字形的曲线
MortonCode 有着很好的空间局部性，而且降维到一维也有利于在局部范围内的查找
# 为什么 MortonCode 效果优于一维随机访问？
这也是我之前一直迷惑的一个点
- 当我们使用顺序表存储二维数据时通常会得到下述的一个结构
![]()
但是当我们想要按照下面这种方式访问这个结构时 (篮圈内), 就会产生 CacheMiss (假设访问第二行时，第一行会被丢弃，L1Chache 需要重新读取第二行), 在极其稀疏的数据结构中，这种情况就会更加严重
为了解决这种问题，我们需要的是一个 局部紧密 的数据结构，即相邻的元素都在相邻的区块内，而不是顺序表这样跨越了大量的区块 (这里指的是内存排布) 而 MortonCode 就是一定程度上解决了这个问题，如下图，原始的二维数据是图中的网格所表示的，但是实际存储时使用的则是 MortonCode, 即 Z-Order, 实际在内存中的排布是图中的 Z 形曲线所表示的顺序，倘若我们需要频繁查询 / 访问二维中某一个区域内的空间数据，明显 Z-Order 的排布会更好
然后这里就可以得出为什么 MortonCode 优于一维数组
结论
MortonCode 在需要频繁地访问局部数据时，是优于一维数组的
在需要查询某个区块内存在的数据时，MortonCode 优于一维数组
查询相邻这类问题时，MortonCode 优于一维数组但是
如果查询的方式是随机查询，如 Find (x,y)
即使是 MortonCode 也无法避免可能存在的大量 CacheMiss
这种情况下就无法断言 MortonCode 优于一维数组
即 MortonCode 适用于 局部相关操作的数据结构，如八叉树 / BVH / 四叉树等
