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!