Got the brilliantly named Assimp library working, so I can now import every 3D file format known to man. I'm not a big fan of the high poly-count models seen in some other blocky games, but this axe just happened to be one of the example files, so I grabbed that one for testing.
The standard renderer that comes with the library uses direct calls. The axe model has tens of thousands of triangles, so it's a miracle I'm still getting 30 FPS. So the next step would be to look for/create a proper VBO-based renderer, and get skeletal animations working (for mobs and players).
The 0FPS blog has a great article about meshing, that ties in nicely with my latest couple of posts here, and explains it better and in more depth than I ever could. Go check it out!
And after recording and posting that video about transparent surfaces, I've ran into cases where the sorting method does not produce the desired results. Back to the drawing board. :)
Here's a screenshot in wireframe mode to show the merging in action:
In some of the large flat surfaces (grass and water) everything can be merged, and all that's left are the chunk boundaries. The polygon count is reduced by about 60% on average.
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!
The whole "send surfaces only instead of whole chunks" bit now works properly, so I thought I'd show you guys a video.
(Omagosh I'm allowed to embed Youtube videos again? yay!)
It seems the screen recorder didn't only kill the frame rate as per usual, but also messed with the occlusion queries. So you'll see the occasional hole in the terrain. Let's see if I can figure out why this happens...
Edit: Fixed it by changing the occlusion system. We'll leave that for another blog post. In the meantime:
I'm not the only one who tried to draw a couple of cubes after seeing Minecraft, and every now and then I get questions from other programmers about how to structure the data and make it fast. So let's take a look at the basics of cube rendering.
Structure and storage
At the bottom level, we have a block, which is nothing more than a 16-bit value. This means we can have over 65,000 block types, although special block types could take up multiple slots. (For example, a staircase that can be placed in four directions would require four ID numbers.) There is a separate table that holds all the info for a given block type, such as the name, durability, transparency, the collision box, Lua hooks, etc.
Then there's the chunk, a group of blocks arranged in a 16×16×16 cube. Or at least, that's the concept. In reality, it is an array of block types, and its size is fixed at 16³ = 4096 elements. (At 16 bits for a block type, that's 8192 bytes). The (x,y,z) position of a block is implicit: it is located in the array at index [x + y * 16 + z * 256].
Then, at the highest level, there's the game world. This is a really, really big cube (4.3 billion blocks in every direction: a few times larger than our own sun), and it's sliced up in chunks.
Unlike blocks, we don't have to keep all 19 septillion chunks in memory at all times. Chunks are positioned explicitly, meaning we store its position as well. This allows us to load and unload small sections of the game world as needed. I store them in a database, where the position is the primary key, and the chunk data is a blob of compressed data. Until recently it used 'deflate' as its compression algorithm. I switched to LZ4, because it is much faster (7 to 10 times) and compression is only a few percent worse on average.
Rendering
Drawing the cubes on screen seems simple enough. Load the chunks that are near the player, then go through every block in every chunk. Grab the right texture for that block type, draw a cube at this position (the chunk's own coordinates, plus the implicit position of the block). Ta dah.
This is really, really slow. We're drawing a lot of stuff the player can never see, so this is also easy to speed up. The only thing that is interesting for rendering, are the faces at the surface. So we still check every block, but we also look at the six neighbors. If the neighbor is of a different block type, and it is transparent, then we draw the face. Surfaces are stored as a list of a 16-bit chunk array index, plus a byte that indicates which of the six faces are exposed in the lowest 6 bits.
Much better already! Combined with frustum culling and occlusion culling (described in detail in an earlier post) performance will be boosted even further.
Opaque and transparent objects need to be drawn separately, so you'll have to generate two surfaces for each chunk. First you draw all opaque surfaces, in near-to-far order. Then you turn off z-buffer writes, and draw all transparent surfaces in reverse order, far-to-near.
Surface extraction
The step that converts a chunk to the visibile surfaces is now our new bottleneck. I know others have experimented with offloading this to the GPU, but this requires a rather modern card, and I'd like to support at least OpenGL 2.1. So for now, we're still CPU bound.
Hexahedra always runs in a client-server setup, even for single player. The server also looks for a chunk's surface, even though it doesn't render anything. It uses this for calculating light, and for collision handling. Now why don't we store this information in the database as well, and send only the surfaces to the client?
This has several advantages. Clients don't have to go through the same expensive step anymore. Network load will be reduced; a surface is usually smaller than the chunk it was generated from, with only a couple of worst-case scenarios as the rare exception. Cheating will be harder, since clients cannot see ores or other valuables hidden inside the walls.
Most people have already seen GLSL in action in several Minecraft mods, ranging from bump- and parallax mapping to bending the world into one giant acid trip. Other games, such as Mythruna, use it out of the box for effects like HDR bloom.
Personally, I prefer Hexahedra's current look, with the simple textures and the blocky lighting. But there are several other interesting things possible that have nothing to do with aesthetics.
One of them is the use of texture arrays. An old technique to speed up rendering is to use a texture atlas: a large texture that combines several smaller ones. The drawback is that such textures cannot be tiled, so every cube has to be drawn separately. Minecraft uses (used?) a texture atlas that is exactly one tile wide, so the textures can at least be tiled horizontally. Strips of cube faces can be merged together, which cuts back on the amount of work the GPU needs to do.
A texture array is a kind of 3-D texture. The individual textures are arranged in a stack. Each slice can now be tiled both horizontally and vertically, so we can merge even more faces. The gains are the most obvious for open water, where 256 cubes with the same texture and lighting can be merged into a single, large square.
And in one fell swoop, it also solves all problems with textures bleeding into each other at the edges because of mipmapping and rounding errors.
There's another advantage. Every corner used to be stored as three shorts (x, y, z) for the position, two floats (u, v) for the coordinates in the texture atlas, and three bytes (r, g, b) for the lighting. That's 68 bytes per face.
Such restrictions no longer exist in GLSL. We can put the coordinates in bytes. (I'd put them in nibbles, but the range is 0-16, not 0-15). Now that we're using texture arrays, we need a short to pick a slice, and two nibbles for the u,v coordinates. Three more nibbles for the lighting: ambient, sunlight, and artificial light. The actual light colors are grabbed from uniforms, global values we need to set only once. So we're down to 32 bytes per face. Nice!
Hmm... The u,v coordinates now move in lockstep with the vertex positions. It turns out that by storing a normal, we can go from world coordinates to texture coordinates by a simple multiplication. We only have six possible normals, so that's three bits. And we're down to 28 bytes per face. Even better, we can now use the normals for the ambient lighting as well. Dusk and dawn are going to look spectacular if we can give the west (c.q. east) faces a red or pink hue.
I look at the top of the screen where it says "20 FPS". Frown. Revert to previous shaders. 60 FPS. The fuck?
Turns out a simple lookup in a table with six 2x3 matrices is painfully slow in GLSL. It might not be worth the extra 4 bytes per face, but it would be neat to have anisotropic ambient light. Perhaps a lookup in a small 1D texture would solve this? I'll have to spend some more time on this.
