Download

Morton code to grid position

Hello,

Currently I am trying to understand SVO, Morton code etc. a little bit more. In regards to Morton Code I have to open question in my mind and I hope somebody can point me in the right direction.

From my understanding, by interleaving I have translated my coords into an morton code. This morton code represents the nth cell of the Z Curve ordering.
So my first question is:

Assume I have a 10x10x10 grid and for each grid position I am calculating the morton code - in my case an uint64. How can I link the morton code to one of the grid cells (10x10x10) grid. I guess that should be easy since I know the morton code which represents it position, I know my grid dimensions. Any way to do that easily with morton?

My second question is more about octree, svo and Morton code in them.
Based on Z Curve ordering, we know for each layer node the parent node based on Z Curve ordering on the next level. The question is more is there an formula to calculate it?

I read a lot of papers, but none explain the calculation in details. The all just claim its trivial. I guess not trivial for me.

For reference these are some of the papers I have read:

http://research.michael-schwarz.com/publ/2010/vox/

https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.306.9501&rep=rep1&type=pdf

Any help and/or tip is really appreciated.

For the Morton code, for size 10^3, you could build a lookup table, or a hash table.

The more “procedural” way to do it is to un-slice the bits. Given that you only need 4 bits for each of the components, the masks are “0x249”, “0x492” and “0x924”
Once you have each of the codes, you have to use a hash table or careful shifting-masking to pack the bits back to an index. Very likely better done in C++ than in Blueprint.

void unmorton_3_4(int in, int &ox, int &oy, int &oz) {
    ox = uncode_3_4(in);
    oy = uncode_3_4(in >> 1);
    oz = uncode_3_4(in >> 2);
}

int uncode_3_4(int i) {
    return (i & 1) | ((i >> 1) & 2) | ((i >> 2) & 4) | ((i >> 3) & 8);
}

If you want arbitrary ranks and extents, either use a for loop, or write the appropriate recursive template.

But, why do you need this, really? What are you doing on data that is big enough that it won’t fit in L1 cache, yet is so performance sensitive that simple linear order isn’t good enough, and worth the additional coordinate calculation expense?

That is a good question. Honestly as more I am looking into the topic I realize how less I actually understand of that concept. Basically I want to build a navigationMesh to do some pathfinding on top that.

What I am currently doing is similar to the paper of Brewer.

  1. I generate L1 (above leaf nodes level) all nodes with geometry and keep a sorted list with morton codes
    (Here I just take for example in a 10x10x10 grid, the morton codes from 1-1000. So I always get a vector (1-1000,1-1000,1-1000) If I want the actual world locations of the cells I just simply multiply them with the cell size of that level)
  2. Based on that sorted list of nodes with geometry I calculate the numbers of leaves I need. And then will generate all 8 leaves for each level 1 node with geometry. Later I will do some actual rasterization of the leaf nodes.
  3. Then I want to build up the levels from the lowest level to the root.

Important here is each node has information of:
a) its parent as a link
b) its first child
C) neigbhours

A link is an int32 with 4 bits (layer index) 22bits (node index) 6bit (subnodes after rasterization of leaves).

Each layer will be in a sorted list by morton codes of the nodes on that layer.

One thing which is still confuses me, if an SVO adds empty nodes in the array? What I mean nodes without children on each level. The reason why I am asking this is that since I have the layer index, node index and a sorted list of all nodes on a layer, this list would have to be complete (with empty nodes) so that based on that I could access the nodes by index. If only child nodes are in there the index would not work anymore, correct? I would need a complete Z curve for each layer to be able to access nodes by its index.

I guess just writing about it, it makes it clear you will have to add empty nodes for padding so that linear lookup of each layers list will still work. … or keeping offsets but that does not sound right.

If the problem is “given an arbitrary point in space, find me the nearby things that might matter,” then use a hash grid (2D or 3D,) a quad tree (if 2D) or an octree (if 3D.)
These are well understood and described data structures, perform well, easy to understand and implement.
Note that Morton codes DO NOT make those queries easy, because at the boundaries between segments, the “ID” jumps are quite large and discontiguous. The codes only help in hardware-specific implementations that need the memory locality properties – eg, GPUs may re-pack texture data into this kind of layout.

If you need to ask the question “I’m on this part of the nav grid/mesh/graph, what are the next steps possible,” then you solve that with the “graph” bit – every piece keeps pointers (perhaps with estimated costs) to their neighbors.

And if the question is simply “how do I store/index all the things within a single level,” then either a simple coordinate packing scheme, or a hash grid/table, will work fine. Or just sort by X-then-Y-then-Z if all you need is “a deterministic order.”