{"id":98,"date":"2025-12-12T10:15:02","date_gmt":"2025-12-12T10:15:02","guid":{"rendered":"https:\/\/3d-galaxy.com\/blog\/?p=98"},"modified":"2025-12-13T05:40:27","modified_gmt":"2025-12-13T05:40:27","slug":"z-order-curves","status":"publish","type":"post","link":"https:\/\/3d-galaxy.com\/blog\/index.php\/2025\/12\/12\/z-order-curves\/","title":{"rendered":"Z-Order Curves"},"content":{"rendered":"\n

\u261d\ufe0f\ud83e\udd13 First off, Z-order curves have nothing to do with rendering order or Z-depth.<\/p>\n\n\n\n

Rather, such a “curve” is a useful mathematical tool for calculating a value, or code, for some entity, such as a point or a triangle, which approximates the relative position of that entity within some spatial grid. Entities which are closer together in space will have closer values, and entities which are far away from each other will have a greater difference in their calculated value.<\/p>\n\n\n\n

The Z-order curve is named the way that it is because each successive code in the sequence takes a zigzagging, Z-shaped path. Sometimes the Z-order curve value is referred to as a Morton code.<\/p>\n\n\n\n

Z-order curves provide an effective way to sort points, triangles, or other spatially located items in N-dimensional-space such that they fill space efficiently in an ordered way. For example, all of the triangles which are spatially near each other in 3D space will have a tendency to be near each other along a Z-order curve, and so it provides an effective way of packing points and triangles based on how close they are to each other.<\/p>\n\n\n\n

The diagram below demonstrates how a Z-order curve works in 2D.<\/p>\n\n\n\n

\"\"<\/figure>\n\n\n\n

Essentially, for a given XY integer coordinate, we take the binary representation of the X component, and the Y component, and then we interleave them together in order to get the resulting Z-order curve value.<\/p>\n\n\n\n

For example, take the case where we have an 8×8, 2D grid. We have a point in the grid which we have determined falls within cell (3,5), so X=3 (011) and Y=5 (101).<\/p>\n\n\n\n

\n
\"\"<\/figure>
\n

To get a Z-order value, we need to interleave our binary X and Y values. So we take the lowest order bit of the X value and use it as the first (lowest order) bit of our binary Z-order curve value. For the next bit, we take the lowest order bit of the Y value. We then go back to the X value, but we take the next bit, then swap back to Y, etc., until we have our number.<\/p>\n<\/div><\/div>\n\n\n\n

After we interleave, we end up with a result of 100111 in binary, which is 39 in decimal. Imagine that we have 1 point within each cell of our 8×8 grid. Once we have computed Z-order curve values for each point and sorted them from lowest to highest, our point (which has a value of 39) would be 40th in the list (don’t forget to count 0!). And if you look at the picture of a 6-bit Z-order curve above, you can see that if you count to the 40th position along it, the value is indeed 100111.<\/p>\n\n\n\n

If we have a 6-bit number, and we’re encoding 2 dimensions (X and Y) into our Z-order curve value, we can represent 8 possible coordinates along each axis, since we have 3 bits per axis, and with 3 bits we can represent the numbers 0-7.<\/p>\n\n\n\n

\n

For 3D, we use the same process, but we have to interleave our Z coordinate as well, so after we add each Y coordinate bit, the next highest order bit in our Z-order curve value will be a bit from our calculated Z coordinate.<\/p>\n<\/div>

\"\"<\/figure><\/div>\n<\/div>\n\n\n\n

In 3D, it’s common to use a 32-bit integer to store a Z-order curve value. So that gives us 10 bits each, or 210<\/sup> (1024) possible coordinates in each dimension (X, Y, and Z), since we have 30 bits available for 3D coordinate representation. If you really wanted to, you could encode an additional two values into the remaining 2 bits, giving you 2048 possible coordinates in both the X and Y dimensions (or however you wanna slice it), but we’re not gonna do that here. We’ll just leave the other 2 bits for our critter friends to chew on. \ud83d\udc07\ud83d\udc3f\ufe0f<\/p>\n\n\n\n

The Z-Order Curve Value Computation Algorithm<\/h2>\n\n\n\n

The general algorithm to determine the Z-order curve value for a 3D coordinate looks like this:<\/p>\n\n\n\n

<\/circle><\/circle><\/circle><\/g><\/svg><\/span>