Using morton codes to compress data - how?

Question

I've been reading something about morton codes and I got that locality is preserved in the sequence of generated numbers.

What I don't understand is how this information can be used to compress data or to efficiently construct data in parallel.

Source: http://www.forceflow.be/2013/10/07/morton-encodingdecoding-through-bit-interleaving-implementations/

Answer 1

Morton ordering isn't inherently related to data compression on its own. It's just a way of laying out spatial data in memory such that queries about a contiguous block of space tend to map to contiguous blocks of memory - making for good cache efficiency.

In the algorithm paper referenced in the link you cite, Morton order is used to improve efficiency of disc reads & writes.

The algorithm converts a complex triangle mesh into a high-resolution voxel intermediate representation (stored in Morton order), and then converts that representation into a sparse (compressed) output form.

One of the properties of Morton order is that it matches the order obtained from depth-first traversal of an octree (or quadtree in 2D). This gives a convenient alignment between the output octree data structure and the intermediate. So constructing a node in the output octree requires data from a contiguous set of indices in the intermediate structure. This lets the algorithm read only the data it needs at a given step, keeping the memory footprint low and cache efficiency high.

So the Morton ordering here provides no particular compression or parallelization advantage on its own - you could write an equivalent algorithm with the same compression output that used linear ordering in its intermediate, but its writes and reads would be much more scattered and so it probably wouldn't process data nearly as quickly.

But if you're using quadtrees or octrees to compress data, Morton ordering can make your indexing of data cleaner and higher performance.