I'm trying to stay away from octrees and similar, so I will semi-explain how my voxel game works:
We have a block class (nType, nSun, color)
This will be the main blocks such as grass or dirt. Obviously the best way to render and deal with this blocks is to split them up into "Chunks".
Now we have a chunk class (vecIndex, vecPosition, nState)
Did you notice we don't use blocks in this chunk class? Because constant allocation and deallocation is a big no. Instead of searching each chunk, create/destroy, etc., we see what our maximum cache distance is as for our BlockManager class
And our BlockManager class (Block* pBlocks)
I know, a single pointer-array. With this, we can index and grab quicker than an 3D array, and we won't have the overhead of new'ing or delete'ing a 16*128*16 array every time we go into a new chunk.
I will post some code in a minute when my wonderful Pentium 4 finally boots up.
Edit: Here we go. This is just a sample that I ripped apart from several sources inside my game. Could be error prone, and defiantly needs some tidying up.
#define CHUNK_WIDTH 16
#define CHUNK_HEIGHT 128
#define CHUNK_DEPTH 16
#define CHUNK_CACHE_RANGE 5
#define CHUNK_CACHE_VIEWRANGE 3
#define CHUNK_CACHESIZE_WIDTH ((CHUNK_CACHE_RANGE * 2) + 1) * CHUNK_WIDTH
#define CHUNK_CACHESIZE_DEPTH ((CHUNK_CACHE_RANGE * 2) + 1) * CHUNK_DEPTH
int MOD( int a, int b )
{
return (a % b + b) % b;
}
int OFFSET( int x, int z )
{
int nWrapX = MOD( x, CHUNK_CACHESIZE_WIDTH );
int nWrapZ = MOD( z, CHUNK_CACHESIZE_DEPTH );
if( nWrapX < 0 )
nWrapX += CHUNK_CACHESIZE_WIDTH;
if( nWrapZ < 0 )
nWrapZ += CHUNK_CACHESIZE_DEPTH;
return nWrapX * (CHUNK_CACHESIZE_WIDTH * CHUNK_HEIGHT) + nWrapZ * CHUNK_HEIGHT;
}
int OFFSET( int x, int y, int z )
{
int nWrapX = MOD( x, CHUNK_CACHESIZE_WIDTH );
int nWrapZ = MOD( z, CHUNK_CACHESIZE_DEPTH );
if( nWrapX < 0 )
nWrapX += CHUNK_CACHESIZE_WIDTH;
if( nWrapZ < 0 )
nWrapZ += CHUNK_CACHESIZE_DEPTH;
return nWrapX * (CHUNK_CACHESIZE_WIDTH * CHUNK_HEIGHT) + nWrapZ * CHUNK_HEIGHT + y;
}
class BlockManager
{
public:
Block* m_pBlocks;
BlockManager()
{
int nSize = CHUNK_CACHESIZE_WIDTH * CHUNK_CACHESIZE_DEPTH * CHUNK_HEIGHT + 1;
m_Blocks = new Block[nSize];
for( int i = 0; i < nSize; i++ )
m_Blocks[i] = Block();
}
Block BlockAt( int x, int y, int z )
{
if( !ChunkCache::IsInBounds( x, y, z ) )
return Block();
int nWrapX = MOD( x, CHUNK_CACHESIZE_WIDTH );
int nWrapZ = MOD( z, CHUNK_CACHESIZE_DEPTH );
if( nWrapX < 0 )
nWrapX += CHUNK_CACHESIZE_WIDTH;
if( nWrapZ < 0 )
nWrapZ += CHUNK_CACHESIZE_DEPTH;
int nOffset = nWrapX * (CHUNK_CACHESIZE_WIDTH * CHUNK_HEIGHT) + nWrapZ * CHUNK_HEIGHT;
return m_Blocks[nOffset];
}
};
Alright, now we can use a TerrainChunkGenerator, go from x = 0, y = 127, z = 0 and x++, y--, z++
Generate our chunks, and move to the LightingChunkGenerator. Perform some nasty recursive functions to spread out our light source from 16, and continue.
Now we are at VertexChunkGenerator. When creating the vertices, we check the current block's neighbors. So, if a block is above us, we don't create the top face. If a block is to its left but not to its right, don't create the left face and generate the right face.
Now we have this chunk that will only have visible blocks vertices and indicies. We just gave our performance steroids.