Saturday, June 9, 2012

Sorting in depth

A while back (too long!) I explained how to draw a bunch of cubes, and made a nonchalant remark about how it is important to draw everything in a front-to-back (or back-to-front, for transparent polys) order. Sorting all voxels by distance every time the camera moves is not an option, so we need to think of something else.

At the chunk level

The first thing we'll do is to sort all the chunks by their Manhattan distance. Instead of calculating the distance using the Pythagorean theorem (what we usually think of as "distance", also known as Euclidean distance), it is the sum of the differences of all three ordinates. If the camera is in chunk (1,2,3) and we want to measure the distance to chunk (5,7,9), the differences in the x, y and z directions are 4, 5, and 6 respectively, and their sum is 15.

The nice thing about the Manhattan distance is that, in our voxel world, it is always a whole number. We use this number to group the chunks, one group for each distance. Group 1 has no more than 6 chunks in it, while group 2 has no more than 18. (Try to imagine how this looks in 3D and you'll see why.)

Grouping chunks by Manhattan distance
It's kind of a lazy version of a bucket sort. We only need to do this once. Whenever we want to render the scene, we traverse this data structure in order. The ordering of the individual chunks does not matter; no two chunks with the same distance  can never overlap each other from the camera's perspective. This gives us more freedom to pick a suitable data structure, e.g. a hash table.

The drawback is that every time the camera enters a different chunk, we need to shuffle this data structure.  Luckily most of the operations are quite cheap. (For very, very large view ranges and slow CPUs, this can even be done in the background. Nobody will notice if one or two frames still use the previous, almost-correct sorting order.)

At the block level

The individual blocks within the chunk must also be sorted. This is trickier, because not only does the sorting order change every time the camera enters a different block, it also changes for some of the surrounding chunks.

We split the surface that needs to be rendered (the set of exposed block faces) into six stacks of 16×16 grid "slices". Six, because there's one stack for each cardinal direction.

Here we see an example. The stack of slices that corresponds to "up" holds the faces A and B. A is at (1,1) o slice 0, B at (1, 2) on slice 1, one level deeper. So in this case, the z-axis corresponds to the actual z-axis of the game world.

The stack that corresponds to "east" (or "right") holds I and II. Although A and B ended up in different slices, I and II end up in the same slice because the z-axis now runs west-to-east.

All six stacks are then drawn in their z-order. Here's an example of the player looking north, down the slices of an eastward grid:

The slices are drawn in right-to-left order in this case. Faces J and K are drawn normally. K is closer to the player, and is drawn on top of J. L is drawn even earlier, if it weren't for backface culling. (It would be possible to start drawing a K's slice, based on the camera position, but finding the right index in the vertex buffer is nontrivial. Besides, the GPU can do backface culling so fast it's not even funny. It's likely you'll spend more time on the CPU trying to find the right starting point.)

This is also where identical, adjacent faces are merged in OpenGL 3.x mode. It isn't difficult to detect the two "N" textures can be merged into a rectangle. Determining the optimal way to merge the faces is an expensive operation, so Hexahedra uses a simple greedy algorithm. (Start at the top-left texture, and keep expanding a rectangle to the right and to the bottom until you encounter a different texture anywhere. Remove all textures in this rectangle, and repeat until the slice is empty.)

Für die Lulz

And because boring wall of text is boring, a video!


  1. Thank you for this new article, very interesting. In fact I was hoping you would talk about how to sort the polygons, because it's compulsory to use alpha transparency properly.
    Still, the technique is quite complex, I don't understand why there isn't a "sort method" directly in OpenGl to sort the polygons on the GPU.
    Merging adjacent faces is a good idea, and should improve the framerate a lot. And allow bigger landscape too, what is the maximum view distance that you can have with a decent framerate?
    Anyway, thank you again for this series of articles, please keep making them!
    Have you implemented the game in a client/server way? If yes, are you going to talk about network programming?

  2. Yes, merging the faces does help. I can play comfortably with a view radius of 768, and even reasonably well on 1024 (although I get glitches at that point -- I'll have to hunt down that bug). I've added a video at the top, that one was recorded at 640.

    The game is indeed client-server, but the network part isn't all that interesting at the moment. Heck, it's still TCP. :/ Recently, some guy posted an analysis of Id Software's source code (Quake, Doom, etc). There's some really good information in there about how to properly design a UDP protocol with lag compensation and all that. I'd like to incorporate those ideas in Hexahedra as well, but that's pretty far in the future.