Block Land 5

From DaveWiki

Last Time we added some basic visual effects and landscape generation and produced some good looking world scenes. In this article we'll look at an obvious optimization and discuss various performance and world size issues.

An Obvious Optimization

So far our mesh chunking has allowed us to greatly reduce the number of triangles it takes to display a scene composed of a large number of blocks. For example:

256 Block Landscaped World With a 64 Block Chunk

This shows the sides of a 256x256x256 block world with 64 sized chunks using a simple landscape generation. The chunking has reduced the number of triangles by a factor of 40 or so to 1.5 million. If you look more closely at the above image, however, you can see that we are still creating all sides of each chunk, whether they are visible or not. The original reason behind this is that if we are creating a MineCraft clone then each block has to be destructible. The basic concept is that when a player mines/destroys a block we would have to recreate that chunk to update the display (or modify the existing chunk). If we create the sides of the chunk from the start then each block destruction is limited to that chunk and no other. If, on the other hand, we don't create the chunk sides then removing a block on the edge of a chunk also would have to update the adjacent chunk.

Let's try this optimization on our block world and see how well it fares. All it requires are some minor changes to the mesh chunking method:

void TestBlockLandApplication::createChunk (const int StartX, const int StartY, const int StartZ)
{
	Ogre::ManualObject* MeshChunk = new Ogre::ManualObject("MeshManChunk" + Ogre::StringConverter::toString(m_ChunkID));
	MeshChunk->begin("BoxColor");
 
	int iVertex = 0;
	block_t Block;
	block_t Block1;
 
		/* Only create visible faces of each chunk */
	block_t DefaultBlock = 1;
	int SX = 0;
	int SY = 0;
	int SZ = 0;
	int MaxSize = WORLD_SIZE;
 
	for (int z = StartZ; z < CHUNK_SIZE + StartZ; ++z)
	{
		for (int y = StartY; y < CHUNK_SIZE + StartY; ++y)
		{
			for (int x = StartX; x < CHUNK_SIZE + StartX; ++x)
			{
				Block = GetBlock(x,y,z);
				if (Block == 0) continue;
 
					//x-1
				Block1 = DefaultBlock;
				if (x > SX) Block1 = GetBlock(x-1,y,z);
 
				if (Block1 == 0)
				{
					MeshChunk->position(x, y,   z+1);	MeshChunk->normal(-1,0,0);	MeshChunk->textureCoord(0, 1);
					MeshChunk->position(x, y+1, z+1);	MeshChunk->normal(-1,0,0);	MeshChunk->textureCoord(1, 1);
					MeshChunk->position(x, y+1, z);		MeshChunk->normal(-1,0,0);	MeshChunk->textureCoord(1, 0);
					MeshChunk->position(x, y,   z);		MeshChunk->normal(-1,0,0);	MeshChunk->textureCoord(0, 0);
 
					MeshChunk->triangle(iVertex, iVertex+1, iVertex+2);
					MeshChunk->triangle(iVertex+2, iVertex+3, iVertex);
 
					iVertex += 4;
				}
 
					//x+1
				Block1 = DefaultBlock;
				if (x < SX + MaxSize - 1) Block1 = GetBlock(x+1,y,z);
 
				if (Block1 == 0)
				{
					MeshChunk->position(x+1, y,   z);	MeshChunk->normal(1,0,0); MeshChunk->textureCoord(0, 1);
					MeshChunk->position(x+1, y+1, z);	MeshChunk->normal(1,0,0); MeshChunk->textureCoord(1, 1);
					MeshChunk->position(x+1, y+1, z+1);	MeshChunk->normal(1,0,0); MeshChunk->textureCoord(1, 0);
					MeshChunk->position(x+1, y,   z+1);	MeshChunk->normal(1,0,0); MeshChunk->textureCoord(0, 0);
 
					MeshChunk->triangle(iVertex, iVertex+1, iVertex+2);
					MeshChunk->triangle(iVertex+2, iVertex+3, iVertex);
 
					iVertex += 4;
				}
 
					//y-1
				Block1 = DefaultBlock;
				if (y > SY) Block1 = GetBlock(x,y-1,z);
 
				if (Block1 == 0)
				{
					MeshChunk->position(x,   y, z);		MeshChunk->normal(0,-1,0); MeshChunk->textureCoord(0, 1);
					MeshChunk->position(x+1, y, z);		MeshChunk->normal(0,-1,0); MeshChunk->textureCoord(1, 1);
					MeshChunk->position(x+1, y, z+1);	MeshChunk->normal(0,-1,0); MeshChunk->textureCoord(1, 0);
					MeshChunk->position(x,   y, z+1);	MeshChunk->normal(0,-1,0); MeshChunk->textureCoord(0, 0);
 
					MeshChunk->triangle(iVertex, iVertex+1, iVertex+2);
					MeshChunk->triangle(iVertex+2, iVertex+3, iVertex);
 
					iVertex += 4;
				}
 
 
					//y+1
				Block1 = DefaultBlock;
				if (y < SY + MaxSize - 1) Block1 = GetBlock(x,y+1,z);
 
				if (Block1 == 0)
				{
					MeshChunk->position(x,   y+1, z+1);		MeshChunk->normal(0,1,0); MeshChunk->textureCoord(0, 1);
					MeshChunk->position(x+1, y+1, z+1);		MeshChunk->normal(0,1,0); MeshChunk->textureCoord(1, 1);
					MeshChunk->position(x+1, y+1, z);		MeshChunk->normal(0,1,0); MeshChunk->textureCoord(1, 0);
					MeshChunk->position(x,   y+1, z);		MeshChunk->normal(0,1,0); MeshChunk->textureCoord(0, 0);
 
					MeshChunk->triangle(iVertex, iVertex+1, iVertex+2);
					MeshChunk->triangle(iVertex+2, iVertex+3, iVertex);
 
					iVertex += 4;
				}
 
					//z-1
				Block1 = DefaultBlock;
				if (z > SZ) Block1 = GetBlock(x,y,z-1);
 
				if (Block1 == 0)
				{
					MeshChunk->position(x,   y+1, z);		MeshChunk->normal(0,0,-1); MeshChunk->textureCoord(0, 1);
					MeshChunk->position(x+1, y+1, z);		MeshChunk->normal(0,0,-1); MeshChunk->textureCoord(1, 1);
					MeshChunk->position(x+1, y,   z);		MeshChunk->normal(0,0,-1); MeshChunk->textureCoord(1, 0);
					MeshChunk->position(x,   y,   z);		MeshChunk->normal(0,0,-1); MeshChunk->textureCoord(0, 0);
 
					MeshChunk->triangle(iVertex, iVertex+1, iVertex+2);
					MeshChunk->triangle(iVertex+2, iVertex+3, iVertex);
 
					iVertex += 4;
				}
 
 
					//z+1
				Block1 = DefaultBlock;
				if (z < SZ + MaxSize - 1) Block1 = GetBlock(x,y,z+1);
 
				if (Block1 == 0)
				{
					MeshChunk->position(x,   y,   z+1);		MeshChunk->normal(0,0,1); MeshChunk->textureCoord(0, 1);
					MeshChunk->position(x+1, y,   z+1);		MeshChunk->normal(0,0,1); MeshChunk->textureCoord(1, 1);
					MeshChunk->position(x+1, y+1, z+1);		MeshChunk->normal(0,0,1); MeshChunk->textureCoord(1, 0);
					MeshChunk->position(x,   y+1, z+1);		MeshChunk->normal(0,0,1); MeshChunk->textureCoord(0, 0);
 
					MeshChunk->triangle(iVertex, iVertex+1, iVertex+2);
					MeshChunk->triangle(iVertex+2, iVertex+3, iVertex);
 
					iVertex += 4;
				}
 
			}
		}
	}
 
	MeshChunk->end();
	mSceneMgr->getRootSceneNode()->createChildSceneNode()->attachObject(MeshChunk);
 
	++m_ChunkID;
}

We just changed how we check for block neighbors at the chunk and world boundaries. Running this on our same landscape results in:

Chunks With Only Visible Faces Displayed

The landscape itself has remain unchanged but as you can see the technically hidden faces of the chunks have been removed. This alone has reduced the number of triangles by over a factor of 7 (1.5 to 0.2 million) which is a significant improvement. So significant, in fact, that we can easily try larger worlds then we could of before, for example:

Very Large 1024 x 1024 x 1024 Block World

Optimization Discussion

This simple, and powerful, optimization is not without its consequences though. As previously mentioned, ultimately our block world is going to be very dynamic as players can both destroy and create blocks within the world. When that occurs we are going to have to update our mesh chunks somehow to reflect this change. We can compare the basic steps of updating the world when a block is removed or added in both cases:

In the unoptimized chunking method we just have to update the chunk that the updated block is in. However, in the new optimized method we may have to update up to three additional chunks depending on what action we take and exactly where in the chunk we are. The exact reason, if not clear, can be explained by an example. Consider a player digging deep underground in an area where the chunks are completely solid (no empty areas) and has just dug out a block that happens to be at a chunk boundary. In the empty space of that block the player will be able to see the the adjacent block which will be in the adjacent chunk. In the original, unoptimized case, this chunk already has all its outer faces so this just exposed block is now automatically visible. In the new optimized case, however, the chunk, and the new block, have no faces as these were not created when the chunk was made as they were hidden at that time. In order to display this newly exposed block we would have to recreate the adjacent block. The worst case, removing a block in the corner of a block, potentially requires the three adjacent chunks to be rebuilt.

At this we can start considering the best chunk size in both methods.

Chunk Sizes

For the original chunking method the chunk size had a big effect on how efficient the resulting mesh was: the larger the chunk the more efficient it was. This was entirely due to the number of hidden faces on the edges of the chunks. With the new optimized chunking method we are removing all these faces with the result that the chunk size no longer has any effect on the number of triangles in the chunked mesh. This is now important as in the new method we may have to recreate more chunks when a block is removed so we would prefer smaller chunks to make this faster and more manageable. In fact, smaller chunks probably helps us out where ever a block is a added/removed as the chunk recreation process will be faster. We don't want a noticeable pause in the game whenever we update a block. In this regard, the optimized chunking method is better as it allows us freedom to choose the chunk size without having to worry about the final performance of the scene.

World Sizes and Types

There are two basic types of world to consider:

1. Fixed Size
2. Unlimited Size (or almost unlimited)

A fixed size world is like Dwarf Fortress where the playable world size is fixed at the start of the game and you cannot ever exceed those dimensions. This is basically the type of world we have now where we specify a size at compile time and the program creates and displays the whole world at once.

An unlimited size world is more like MineCraft where the playable area may be technically finite but is so large to be essentially infinite. For example, if MineCraft really is 8x the surface area of the Earth then mining one block a second would take you nearly 2 continuous years of mining to get from one side of the world to another (64 million blocks at one block per meter).

For either type of world larger the sizes we've been playing with (1024 cubed at most so far) it will be too large to create and display all at once which means we have to create/display it a little bit at a time as needed. The simplest method is to just create the world surrounding the player to start up to whatever the visual limit is. As the player moves more of the world in that direction is created as needed. This is typically known as "paging". We already have the concept of using chunks to better display the world and we'll probably use these divisions in the world for paging purposes as well.

Some basic timings of the creation of the landscape (random land generation) and mesh chunks (reducing the land blocks to meshes and adding them to the scene):

Note that the Time Per Chunk column is merely the average from the given row. Depending on exactly how we dynamically create the landscape and chunks this could go up or down some.

Next Time

Next Time we'll look at adding more block types and the problems it causes.