Frankly, that's not uncommon[1]. But no, Z order curves, morton ordering, and how it all relates to spatial partitioning are, and I'm being kind here, "not exactly obvious".I don't understand what Z order curves are, or, to be honest, what they're useful for. I tried reading the Wikipedia article, but it didn't help
The major problem is that, although binary trees, quadtrees and even octrees are fairly easy to envisage, it's not easy to visualise how "Z order curves" fit into things. So let's start from something easy to visualise. One dimension. Now, we're writing a game in one dimension[2], so objects in the game need to be placed along that line somewhere. They have one coordinate, we'll call it x. So, to find all objects near to a target object t, we iterate through the list of game objects, checking for each candidate object c to see if its x coordinate falls within a window of (xt -r) < xc < (xt + r), where r is the radius of the "nearness" circle and xc and xt are the co-ordinates of the candidate and target objects respectively.
"Blimey!", I hear you say. "That means iterating through the list of all game objects once for each object. That's too much work!" And, indeed, it is. For n objects, we do n times n comparisons, or a complexity of O(n^2). "If only there were some better way of doing things", you sigh. And there is, dear reader, there is.
This is where binary trees come in. We take our great big array of game objects, and we split it in two. In one half, we put the objects that are to the left of the centre of the line, and in the other half we put the objects that are to the right of the centre of the line. Then we do the same with each sub-array, splitting at the centre of its "footprint" on the line, again and again, until we have a tree that looks a bit like this:
Imagine our "game world" as being the horizontal axis of the image - our tree spans it completely. So, at the "leaves" of this inverted tree we have a collection of objects whose x coordinate falls within the bounds of the imagined left and right sides of that leaf's "shadow" on our game world. So searching for candidate objects near our target object t now involves calculating which leaves fall in radius r, and then comparing the objects in those leaves. As we are no longer scanning the whole array, our average complexity falls to O(nlogn), although worst case is still O(n^2) (all the objects could be in range of each other).
Are you still with me?
"Trees are all well and good", I hear you mutter, "but there's a lot of buggering about moving objects from leaf to leaf and rebuilding the tree every time something moves". And this is also true. As is the fact that building and tearing down a tree is expensive in terms of space as well as time. And that you need to tit about with variable length lists at every leaf. Trees are useful, but manipulating them is a pain in the rear.
What we can do, then, is, rather than building an actual tree, store the path you'd need to take through the tree to get to each object. By which I mean this:
Look at the above tree, and label the branches. Print it out and do it by hand if it helps. Every left branch is "0", every right branch is "1". The path to a leaf is the concatenation of each branch's label as we go from the root to the leaf. So for the 4th leaf, it would be "0" + "0" + "1" + "1". And, if you label all the leaves, you'll notice (or you should, at least) something that should have been obvious from the start : the leaves form a binary sequence, in this case binary numbers from 0 to 15. If we add another level to the tree, we go from 0 to 31, then 0 to 63, and so on.
What's less obvious is that, if we use as our coordinate x a value between 0 and y^2 - 1 where y is some number greater than the depth of the tree, the path for each leaf is the same as the most significant[3] n bits of the coordinate for all objects which will be contained in that leaf node, and no others. Or, conversely, every object in the game world will be contained on one of the leaves, determined by the most significant n bits of its coordinate.
"What?"
OK, I'll say it differently. Let's say that we use, as our coordinate x, an 8 bit unsigned integer between 0x00 and 0xff. Any object with a coordinate between 0x00 and 0x0f will fall in the leftmost leaf of the diagram above. Between 0x10 and 0x1f, the second leaf. And so on.
We already know the leaf in which a given object will fall, from the most significant bits of its coordinate[4]. Those bits are the morton code for the one dimensional case.
For any two objects, their respective morton codes will tend to be close if the objects are close to each other, and further part if the objects are further apart. This should be entirely unsurprising if you've read the previous paragraph and have a grasp of subtraction. This feature of morton codes holds as we increase the number of dimensions, and the difference between two morton codes can be used as a measure of spatial closeness. Which is why they get used for spatial indexing.
Armed with the ability to create morton codes, we can avoid building a tree. Instead we build a list - for every object we store its morton code, and a pointer[5] to the object itself, and we sort this list by morton code. That's an index, and it's usually more space-efficient than storing a full tree. Then we create a second index, with one entry for each morton code, with a pointer to the first entry in the main index having that morton code (and, potentially, a second pointer to the last), and it's as though we had a full tree, but with less memory overhead, and no buggering about with variable length lists and so on.
Binary trees, morton codes, indexes, they're all 100% equivalent ways of indexing objects spatially.
Now, earlier I glossed over searching:
Go back and look at the tree diagram above. Let's assume we're interested in objects near to an object that falls in the 4th leaf (which is to say the leaf having morton code 0011). Let's also assume that our radius includes not only that leaf, but also impinges on the 2nd, 3rd, 5th and 6th leaves. The morton codes we're interested in are 0001, 0010, 0011, 0100, 0101. We can split that into 3 separate subtrees we need to search, viz: leaf 0001, everything under branch 001 and everything under branch 010. That's the basis of window querying, and although for the one-dimensional case ranges are always contiguous, that's not the case for 2 dimensions or more. Window querying is a subject in and of itself, this is a pretty good paper and googling "window query morton code" should help as well.tufty wrote:… calculating which leaves fall in radius r …
Now. Higher dimensions.
For the 2 dimensional case, the equivalent to the full binary tree is the quadtree. As each branch has 4 subbranches or leaves, numbering is from 00 to 11. Going across then down gives us the classic "Z order curve"[6], and as we drill down through the levels of the tree we have something of a fractal. Again, we can create a morton code by concatenating the branch and leaf labels during tree traversal. In this case, the morton code for an object is equivalent to the most significant n bits of its x and y coordinates, interleaved[7] with each other - an 8 bit morton code for 2 dimensions consists of the top 4 bits of x and y, as follows[8]:
Code: Select all
%yxyxyxyxIn all cases, the morton code retains its "spatial closeness" attribute.
And it all scales nicely as we move into higher dimensions (which are more useful for stuff like medical and astronomical datasets than games).
Hope that's a bit helpful. And, with a bit of luck, easier to read than wikipedia.
Simon
[1] Especially with regards to Wikipedia, which (or rather, "whose editors"), frankly, should be nuked from orbit. That's what happens when you actively drive away experts with cries of "Original research! Original research! Kill the outsider!"
[2] Rather like the storylines and characters of most games, actually
[3] or "leftmost"
[4] If we don't use integers, or convenient ranges, conversions and scalings get us there as well, at a small cost.
[5] Not necessarily object_t *, it could be an index into an array, for example.
[6] As it only looks like a Z in 2 dimensions, I've avoided referring to it as such
[7] There are bit twiddling hacks to do the interleaving extremely rapidly.
[8] you don't have to do it y-x, x-y works exactly as well, but that gives you a "sort-of-reversed-capital-n-order", which doesn't trip nearly as nicely off the tongue
Advertising
