• FEATURED

View more

View more

View more

### Image of the Day Submit

IOTD | Top Screenshots

### The latest, straight to your Inbox.

Subscribe to GameDev.net Direct to receive the latest updates and exclusive content.

# Voxels Theory

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

6 replies to this topic

### #1TGrey  Members

Posted 10 February 2014 - 10:10 AM

Hi there. It is about one week i read different articles, faqs, check sources about voxel scene representation. There are tons of advices how to draw scene with best fps. But now im confused with all of this and maybe someone here can clear it?

I use Ogre3d engine and most people says that need draw objects with ManualObject what is wrapper around (opengl sample)

        glBegin(GL_TRIANGLES);
glColor3f(0.1, 0.2, 0.3);
glVertex3f(0, 0, 0);
glVertex3f(1, 0, 0);
glVertex3f(0, 1, 0);
glEnd();


Make own meshes with primitives.

The next big improvement is octree. Ogre has plugin OctreeSceneManager with frustum culling. I check many youtube videos, read articles, but i can't see the same picture of octree like in youtube videos. Cause of this, i think, is what i put to scene node whole mesh but octree works with vertices of meshe? right? I can't understand what element i should put to octree? And if i have complete mesh how i can split it and put to octree nodes?

I have tried create 32x32x32 block of triangles and each put to Octree Scene node and eventually get stack overflow but other peoples put there much more vertices.

### #2MarlboroKing  Members

Posted 10 February 2014 - 11:52 AM

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.

Edited by MarlboroKing, 10 February 2014 - 12:16 PM.

### #3samoth  Members

Posted 10 February 2014 - 12:30 PM

Before considering anything else, you will want to move away from using immediate mode.

Further, octrees are not optimal since they are not very good at iteration. Spatial hashing works better. Good overview of techniques and their advantages here.

### #4TGrey  Members

Posted 10 February 2014 - 02:30 PM

Thanks i will check out hashing method.

MalboroKing, thanks for code, but anyway my friend already did something similar. The question is how to store this data and best way to draw it? Event if you have 16x128x16 voxels i believe you don't draw all of them. You don't need draw underground blocks at all. As you noticed i must take visible blocks from frustum and cull invisible faces, right? Ok i think it will gain some FPS. But back to chunks, how i should store this data? I thought octree(or Spatial hashing structure) can help me. But i can't understand what kind of information keeps every leaf? The whole voxel block? Or bottom face triangle of front voxel side?

### #5Kaptein  Prime Members

Posted 11 February 2014 - 02:50 AM

MarlboroKing, if your chunks are in power of two size you can make mod easier:

So, assuming we have a class Chunk with static const int SIZE_XZ and SIZE_Y:

// for x and z axis
inline int fastmod_xz(int x)
{
return (x & (Chunk::SIZE_XZ-1));
}
// for that axis that points toward the sky and all that
inline int fastmod_y(int y)
{
return (y & (Chunk::SIZE_Y-1));
}

// These functions can also be static functions in Chunk, because they may be used alot
// Now let's make a wrapping function to determine both the chunk itself and the internal coordinates:

// assuming the coordinates we get in are local to our current grid
// (if they aren't we can still just mod() them to get local coordinates)
Chunk* Chunk::wrap(int& bx, int& by, int& bz)
{
int fx = bx >> 4; // replace 4,3,4 with whatever bitshifts you need
int fy = by >> 3;
int fz = bz >> 4;

// if the position is out of our local grid, we just return null ptr
if (fx < 0 || fx >= Chunks.getXZ() ||
fz < 0 || fz >= Chunks.getXZ() || // note: the total number of chunks with the current settings
fy < 0 || fy >= Chunks.CHUNKS_Y)  // and we are assuming a fixed number of chunks stacked in height
return nullptr;
// directly modifying the coordinates we got in
bx &= Chunk::SIZE_XZ - 1;
by &= Chunk::SIZE_Y  - 1;
bz &= Chunk::SIZE_XZ - 1;
// and returning the chunk as well
return Chunks.getChunkAt(fx, fy, fz);
}



Edited by Kaptein, 11 February 2014 - 02:53 AM.

### #6MarlboroKing  Members

Posted 11 February 2014 - 10:32 AM

TGrey, I wouldn't advise relying on frustrum culling. Every frame you would be doing that. So instead, take those faces out before hand instead of "taking those out every frame for 40,000 blocks".

@kaptein, wonderful! Never thought of that!

### #7TGrey  Members

Posted 11 February 2014 - 03:30 PM

Sorry, not sure that i understand what you mean? I cull faces only once? Or every frame?

And main question, how to store voxels data for best further drawing? If i correct, i need every frame draw only voxels from frustum but cull invisible faces, and in this time hide whole block that underground?

Please can you tell how you draw blocks? With ready meshes or with textured triangles with native OpenGL\DIrectX methods?

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.