Block Land 3

From DaveWiki

Jump to: navigation, search

Last Time we discussed a variety of potential improvements to displaying our block world including "chunking", or breaking our world up into sections and combining the blocks in those sections into a single mesh. In this article we will try and implement and test a program that will do exactly that.

Contents

World Setup

Before beginning we'll add a few members/methods to make handling our block world a little easier: 

typedef unsigned char block_t;
 
class TestBlockLandApplication : public BaseApplication
{
        ...
 
        static const int WORLD_SIZE = 16;	// We'll change these later for various test worlds
	static const int CHUNK_SIZE = 16;
 
	int m_ChunkID;		        // Used for uniquely naming our chunks
 
	block_t* m_Blocks;	        // Holds the block worlds in a [WORLD_SIZE][WORLD_SIZE][WORLD_SIZE] array
 
	        // Read/write access method for our block world (doesn't check input)
	block_t& GetBlock (const int x, const int y, const int z) 
	{
		return m_Blocks[x + y * WORLD_SIZE + z * WORLD_SIZE * WORLD_SIZE];
	}
 
	        // Used for filling our block world
        void initWorldBlocksRandom (const int Divisor);
	void initWorldBlocksSphere (void);
 
	        // Displays the world using our original "naive" method
	void displaySimpleWorld (void);
 
};

We're still dealing with a simple, fixed size block world. The basic world implementation is pretty basic: 

TestBlockLandApplication::TestBlockLandApplication(void)
{
	m_Blocks = new block_t[WORLD_SIZE * WORLD_SIZE * WORLD_SIZE + 16000];
        memset(m_Blocks, 0, sizeof(block_t) * WORLD_SIZE * WORLD_SIZE * WORLD_SIZE);
	initWorldBlocksSphere();
	m_ChunkID = 1;
}
 
TestBlockLandApplication::~TestBlockLandApplication(void)
{
	delete [] m_Blocks;
}

The following methods are for filling our block world with some useful structures: 

void TestBlockLandApplication::initWorldBlocksSphere (void)
{
	for (int z = 0; z < WORLD_SIZE; ++z)
	{
		for (int y = 0; y < WORLD_SIZE; ++y)
		{
			for (int x = 0; x < WORLD_SIZE; ++x)
			{
				if (sqrt((float) (x-WORLD_SIZE/2)*(x-WORLD_SIZE/2) + (y-WORLD_SIZE/2)*(y-WORLD_SIZE/2) + (z-WORLD_SIZE/2)*(z-WORLD_SIZE/2)) < WORLD_SIZE/2) GetBlock(x,y,z) = 1;
			}
		}
	}
}
 
void TestBlockLandApplication::initWorldBlocksRandom (const int Divisor)
{
	srand(12345); // To keep it consistent between runs
 
	for (int z = 0; z < WORLD_SIZE; ++z)
	{
		for (int y = 0; y < WORLD_SIZE; ++y)
		{
			for (int x = 0; x < WORLD_SIZE; ++x)
			{
				GetBlock(x,y,z) = rand() % Divisor;
			}
		}
	}
 
}

I originally used the random method but it is not generally a good approximation of a block world we'll be using so I moved to the spherical world which looks more interesting. The problem with a random world is that the chunking doesn't end up being very efficient depending on how full it is. For example if it is half full (Divisor = 2) there are a lot of empty blocks scattered throughout which reduces the number of hidden blocks that can be removed by the mesh chunking process.

The "displaySimpleWorld()" method is just our initial block world attempt for comparison purposes. 

void TestBlockLandApplication::displaySimpleWorld (void)
{
	Ogre::MaterialPtr mat = Ogre::MaterialManager::getSingleton().create("BoxColor", "General", true );
	Ogre::Technique* tech = mat->getTechnique(0);
	Ogre::Pass* pass = tech->getPass(0);
	Ogre::TextureUnitState* tex = pass->createTextureUnitState();
	tex->setColourOperationEx(Ogre::LBX_MODULATE, Ogre::LBS_MANUAL, Ogre::LBS_CURRENT, Ogre::ColourValue(0, 0.5, 0));
 
	Ogre::ManualObject* testBox  = createCubeMesh("TestBox1", "BoxColor");	
        Ogre::SceneNode* headNode = mSceneMgr->getRootSceneNode()->createChildSceneNode();
	Ogre::MeshPtr Mesh = testBox->convertToMesh("TestBox2");
	Ogre::StaticGeometry* pGeom = new Ogre::StaticGeometry (mSceneMgr, "Boxes");
 
	Ogre::Entity* pEnt = mSceneMgr->createEntity("TestBox2");
 
	pGeom->setRegionDimensions(Ogre::Vector3(300, 300, 300));
 
	for (int z = 0; z < WORLD_SIZE; ++z)
	{
		for (int y = 0; y < WORLD_SIZE; ++y)
		{
			for (int x = 0; x < WORLD_SIZE; ++x)
			{
				if (GetBlock(x,y,z)) pGeom->addEntity(pEnt, Ogre::Vector3(x,y,z));
			}
		}
	}
 
	pGeom->build ();
}

I should also note that I've made very little attempt at creating "good" code including proper error checking, memory leaking, and optimization. At this stage I'm just creating temporary code for testing purposes that won't, or shouldn't, end up anywhere.


Mesh Creation

To make our mesh chunks we have to combine all the individual blocks within the chunk into a single mesh. The basic algorithm we are going to use follows these rules for each block:

  • If the current block is occupied:
  • If the "left" (x-1) of the current block is empty:
  • Create two triangles for this face of the block.
  • Repeat the previous check for (x+1), (y-1), (y+1), (z-1), and (z+1)
  • Blocks outside of the current chunk are considered to be empty.

Using these relatively simple rules we can create a basic 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;
 
	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 = 0;
				if (x > StartX) 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 = 0;
				if (x < StartX + CHUNK_SIZE - 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 = 0;
				if (y > StartY) 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 = 0;
				if (y < StartY + CHUNK_SIZE - 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 = 0;
				if (z > StartZ) 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 = 0;
				if (z < StartZ + CHUNK_SIZE - 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;
}

This is an exact copy of our basic chunking algorithm that creates up to 12 triangles of each block depending on how many neighbors it has. We also need a method to break the world into multiple chunks which is pretty straight forward: 

void TestBlockLandApplication::createWorldChunks (void)
{
	//std::vector<int> VertexArray;
	Ogre::MaterialPtr mat = Ogre::MaterialManager::getSingleton().create("BoxColor", "General", true );
	Ogre::Technique* tech = mat->getTechnique(0);
	Ogre::Pass* pass = tech->getPass(0);
	Ogre::TextureUnitState* tex = pass->createTextureUnitState();
	tex->setColourOperationEx(Ogre::LBX_MODULATE, Ogre::LBS_MANUAL, Ogre::LBS_CURRENT, Ogre::ColourValue(0, 0.5, 0));
 
	//Ogre::ManualObject* MeshChunk = new Ogre::ManualObject("MeshManChunk");
	//MeshChunk->begin("BoxColor");
 
	for (int z = 0; z < WORLD_SIZE; z += CHUNK_SIZE)
	{
		for (int y = 0; y < WORLD_SIZE; y += CHUNK_SIZE)
		{
			for (int x = 0; x < WORLD_SIZE; x += CHUNK_SIZE)
			{
				createChunk(x,y,z);
			}
		}
	}
 
}

Using a 16 world and chunk size to test we get:

16 Block Diameter Sphere in One Mesh Chunk

If we compare this chunked world with our original display method we see we display 10x fewer triangles by chunking (2554 vs 25478) despite the scene appearing identical. This looks good but let's try a bigger world and see what happens. For a 256 sized world with a 64 chunk size we get:

256 Block Diameter Sphere With 64 Block Sized Mesh Chunks

The old display method doesn't work with a sphere this larger but we can estimate we display 48x fewer triangles by chunking (2.2 vs 105 million). This also takes a lot less RAM than our original method, 370 MB in this case which is a lot but manageable, especially considering we've only begun to optimize.

Performance Comparisons

Using a variety of world sizes, chunk sizes, and random/spherical worlds we can get a rough idea on how much we can gain by chunking. Note that for random worlds the % given is the number of full blocks (or 100% is a completely full world).

Type World Size Chunk Size Triangles Gain
Sphere 256 None 105 million? -
Sphere 256 16 7.143 million 14x
Sphere 256 64 2.155 million 48x
Sphere 256 128 1.234 million 85x
Sphere 256 256 0.617 million 170x
Random(100%) 128 None 25 million -
Random(1%) 128 64 0.246 million 1.008x
Random(10%) 128 64 2.27 million 1.11x
Random(25%) 128 64 4.74 million 1.3x
Random(50%) 128 64 6.39 million 2x
Random(75%) 128 64 4.94 million ~5x
Random(90%) 128 64 1.55 million ~25x
Random(99%) 128 64 0.63 million ~39x
Random(100%) 128 64 0.39 million 64x

A few things we can see from the these results:

  • The larger the chunk size the more the potential improvement. This makes sense, of course, but ultimately there will be some balance chosen between the performance and chunk size.
  • Fuller worlds yield much better gains in performance from chunking.
  • Almost empty worlds gain very little.

Next Time

Next Time we'll spend a little bit of time making our world look better.

Retrieved from "http://dave.uesp.net/wiki/Block_Land_3"
Personal tools