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.
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.
Hope you enjoyed this quick peek under the hood!
Hi, I have a few questions and remarks.
ReplyDeleteFirst, a remark on the world size: I don't think you can have "4.3 billion blocks in every direction: a few times larger than our own sun", and I don't like people saying that minecraft can create world bigger than the earth. Maybe what you mean if that if we had huge hard-drive, then we could have a world of this size, but in practice this is out of reach.
For example, how much memory would we need to create a world of the size of the earth? According to wikipedia, the earth surface area is 510,072,000 km2 so around 5*10^14 m2. The everest is 8,848 m high and the deepest sea is around 10,000 m so we need around 20km height for the world size, in total that's around 10^19 cubes and with 16 Bits (2Bytes) per cube that's 2.10^19 Bytes which is 20,000,000 TeraBytes. I don't know about you, but I don't have that kind of storage at home!
Then, I was wandering how did you managed to sort out the faces in near-to-far and far-to-near order to implement transparency? There's a lot of faces!
Nick
Yes, you're right, the size of the game world is limited by the amount of storage you have. The "19 septillion chunks" remark was a bit tongue-in-cheek; of course it would be unfeasible to actually populate it. (A quick back-of-the envelope calculation shows that the surface of the earth would require hundreds of terabytes; a fully populated game world wouldn't even fit in the 2^64 file size limit.)
DeleteHowever, if you can define your world procedurally, and you drop old, unchanged chunks from the DB, then it would become possible. It's still pretty useless, I don't think anyone would spend 14 years to walk to the edge. ;P
Sorting the geometry looks daunting at first, but luckily the blocky nature of the world allows for some shortcuts. There are two stages. First, the chunks around the player are kept in an array of hash tables. The array index is the Manhattan distance to the player. Even though the ordering of the chunks within the same Manhattan distance is pretty random, as long as you keep the order of the array, the chunks are guaranteed to be drawn front-to-back (or the other way around for transparent materials). Every time the camera moves to a new chunk, this data structure needs to be updated accordingly.
Second, the geometry within a chunk is ordered in the direction of the face normal. So there are six groups (the cardinal directions), and each has a number of "slices" with a bunch of block faces per slice. This doesn't need updating -- even if the camera is inside the chunk, everything is drawn in the correct order, or it gets backface-culled.