05 - Chunk Management

Chunk Management


Once you have created your chunk class that is going to represent a big structure of voxels, you need to have some way of managing the chunk objects. Selecting the container type for your chunks can depend on what language you are using or what environment you are writing your voxel engine in. Since I am using C++, I have opted for a <vector> list of chunks. Using this container type allows me a few advantages which help later on in my voxel engine.

  • Firstly the ability to add additional chunks to my container easily. At this stage you don’t want to statically allocate your chunk data, because chunks will need to be dynamically loaded and unloaded a lot during runtime. If you have a static array of chunks,  such as m_pChunks[32][32][32], then adding and removing chunks from this structure becomes very CPU intensive when you want to delete and unload a chunk in the middle of this structure.
  • Using a <vector> container also allows for sequential access to the chunks. I can easily lookup m_pchunkList[index] to get a particular chunk, since vector containers allow direct access. Even though a vector container is a 1D structure, I can still easily work out an index value based on an X,Y,Z chunk position.
  • Iterating through a <vector> container is also very simple and fast. I can create an iterator and use this during my update and render methods. 

Inside my chunk manager I actually maintain a number of different chunk lists. This is important since chunks can be thought of as being in different ‘states’ during runtime. For example during the chunk loading phase I choose to load my chunks asynchronously and only load a certain number of chunks per frame (to increase framerate during load) So I maintain a ChunkLoadList that contains all the chunks that are waiting to be loaded. I also maintain a ChunkRenderList that is used during the render phase of my chunk manager. The importance of these other chunk lists is that they are a subset of the full chunk list, that means they only contain a small number of the overall chunks in the system and represent the chunks at different states during runtime. The other chunk subset lists that I maintain in my chunk manager are ChunkUnloadList, ChunkVisibilityList, ChunkSetupList.

I will go into a little detail about what these subset lists control, but essentially the implementation of how you manage your chunks will be dependent on your programming system and the design of your chunk manager. The important thing to remember here is to design a flexible system that isn’t static and can dynamically change and grow, since you want your voxel engine to be dynamic and able to cope with large data sets.

Chunk State and Flow


As I described above, the chunk manager has a number of different containers that hold the chunk objects at different states during program execution. Since I am doing asynchronous chunk loading I need to make sure that I don't try and load every single chunk at once, since this will drastically halt the program execution. Here is the general flow of the different states that a chunk goes through during the execution of the chunk managers update routine.

  1. Check if any chunks need to be loaded.
  2. Check if any chunks have been loaded, but need to be setup (voxel configuration, set active blocks, etc...).
  3. Check if any chunks need to be rebuilt (i.e. a chunk was modified last frame and needs mesh rebuild).
  4. Check if any chunks need to be unloaded.
  5. Update the chunk visibility list (this is a list of all chunks that could potentially be rendered)
  6. Update the render list.
One important distinction to make, it between the chunk visibility list and also the chunk render list. The visibility list contains a list of all chunks that could potentially be renderer. This means they are within visible distance of the camera. The update to the render list, takes all visible chunks and then decides if they should be rendered, so doing things like frustum culling, occlusion culling, removing empty chunks, etc... Having this distinction between these two containers and updating them separately allows us for a good level of optimization. For example we only have to update the visibility list when the camera moves across a chunk boundary and we need to unload/load chunks. Also it means the subset of chunks that we do final render culling checks on is fairly small.

Here is the high level update function for the chunk Manager:
void ChunkManager::Update(float dt, Vector3d cameraPosition, Vector3d cameraView)
{
    UpdateAsyncChunker();

    UpdateLoadList();

    UpdateSetupList();

    UpdateRebuildList();

    UpdateFlagsList();

    UpdateUnloadList();

    UpdateVisibilityList(cameraPosition);
	
    if(m_cameraPosition != cameraPosition || m_cameraView != cameraView)
    {
        UpdateRenderList();
    }

    m_cameraPosition = cameraPosition;
    m_cameraView = cameraView;
}

Chunk Loading


This phase of the chunk manager update iterates over the LoadList container and calls load for the chunks within this container.. there inst anything particular special to note about this phase, except that it has some additional code to only allow a certain number of chunks to be loaded each frame, so we get a sort of asynchronous loading system. This container is cleared every frame, and gets re-updated in the visibility update phase.

void ChunkManager::UpdateLoadList()
{
    int lNumOfChunksLoaded = 0;

    ChunkList::iterator iterator;   
    for(iterator = m_vpChunkLoadList.begin(); iterator != m_vpChunkLoadList.end() &&
                  (lNumOfChunksLoaded != ASYNC_NUM_CHUNKS_PER_FRAME); ++iterator)
    {
        Chunk* pChunk = (*iterator);

        if(pChunk->IsLoaded() == false)
        {
            if(lNumOfChunksLoaded != ASYNC_NUM_CHUNKS_PER_FRAME))
            {
                pChunk->Load();

                // Increase the chunks loaded count
                lNumOfChunksLoaded++;

                m_forceVisibilityUpdate = true;
            }
        }
    }

    // Clear the load list (every frame)
    m_vpChunkLoadList.clear();
}

Chunk Setup


The setup phase for a chunk is very similar to the load phase. We iterate over the SetupList container and setup any chunks within that list:
void ChunkManager::UpdateSetupList()
{
    // Setup any chunks that have not already been setup
    ChunkList::iterator iterator;
    for(iterator = m_vpChunkSetupList.begin(); iterator != m_vpChunkSetupList.end(); ++iterator)
    {
        Chunk* pChunk = (*iterator);

        if(pChunk->IsLoaded() && pChunk->IsSetup() == false)
        {
            pChunk->Setup();

            if(pChunk->IsSetup())
            {
                // Only force the visibility update if we actually setup the chunk, some chunks wait in the pre-setup stage...
                m_forceVisibilityUpdate = true;
            }
        }
    }

    // Clear the setup list (every frame)
    m_vpChunkSetupList.clear();
}

Chunk Rebuilding


Chunk rebuilding is the act of re-creating a chunks render buffer object, since some voxel information within the chunk has been modified (for example a voxel being turned on or off) This is fairly simple, but in my voxel engine I also do asynchronous chunk rebuilding, in a very similar way to how I do chunk loading. Basically I only want a certain number of chunks to be rebuilt each frame, to maintain a constant and steady frame rate.

Also another complication to chunk rebuilding occurs, since we do some chunk rendering optimizations with regards to chunk neighbors, so when we rebuild a chunk we also need to do some logic to check if the neighbor chunks also need to be updated.
void ChunkManager::UpdateRebuildList()
{
    // Rebuild any chunks that are in the rebuild chunk list
    ChunkList::iterator iterator;
    int lNumRebuiltChunkThisFrame = 0;
    for(iterator = m_vpChunkRebuildList.begin(); iterator != m_vpChunkRebuildList.end() &&
                  (lNumRebuiltChunkThisFrame != ASYNC_NUM_CHUNKS_PER_FRAME); ++iterator)
    {
        Chunk* pChunk = (*iterator);

        if(pChunk->IsLoaded() && pChunk->IsSetup())
        {
            if(lNumRebuiltChunkThisFrame != ASYNC_NUM_CHUNKS_PER_FRAME)
            {
                pChunk->RebuildMesh();

                // If we rebuild a chunk, add it to the list of chunks that need their render flags updated
                // since we might now be empty or surrounded
                m_vpChunkUpdateFlagsList.push_back(pChunk);

                // Also add our neighbours since they might now be surrounded too (If we have neighbours)
                Chunk* pChunkXMinus = GetChunk(pChunk->GetX()-1, pChunk->GetY(), pChunk->GetZ());
                Chunk* pChunkXPlus = GetChunk(pChunk->GetX()+1, pChunk->GetY(), pChunk->GetZ());
                Chunk* pChunkYMinus = GetChunk(pChunk->GetX(), pChunk->GetY()-1, pChunk->GetZ());
                Chunk* pChunkYPlus = GetChunk(pChunk->GetX(), pChunk->GetY()+1, pChunk->GetZ());
                Chunk* pChunkZMinus = GetChunk(pChunk->GetX(), pChunk->GetY(), pChunk->GetZ()-1);
                Chunk* pChunkZPlus = GetChunk(pChunk->GetX(), pChunk->GetY(), pChunk->GetZ()+1);

                if(pChunkXMinus != NULL) 
                    m_vpChunkUpdateFlagsList.push_back(pChunkXMinus);

                if(pChunkXPlus != NULL) 
                    m_vpChunkUpdateFlagsList.push_back(pChunkXPlus);

                if(pChunkYMinus != NULL) 
                    m_vpChunkUpdateFlagsList.push_back(pChunkYMinus);

                if(pChunkYPlus != NULL) 
                    m_vpChunkUpdateFlagsList.push_back(pChunkYPlus);

                if(pChunkZMinus != NULL) 
                    m_vpChunkUpdateFlagsList.push_back(pChunkZMinus);

                if(pChunkZPlus != NULL) 
                    m_vpChunkUpdateFlagsList.push_back(pChunkZPlus);

                // Only rebuild a certain number of chunks per frame
                lNumRebuiltChunkThisFrame++;

                m_forceVisibilityUpdate = true;
            }
        }
    }

    // Clear the rebuild list
    m_vpChunkRebuildList.clear();
}

Chunk Unloading


Chunk unloading is the inverse of a chunk load, this is where all the block data gets deleted and the memory is freed back to the pool. Again there is a separate UnloadList that is maintained for this purpose.
void ChunkManager::UpdateUnloadList()
{
    // Unload any chunks
    ChunkList::iterator iterator;
    for(iterator = m_vpChunkUnloadList.begin(); iterator != m_vpChunkUnloadList.end(); ++iterator)
    {
        Chunk* pChunk = (*iterator);

        if(pChunk->IsLoaded())
        {
            pChunk->Unload();

            m_forceVisibilityUpdate = true;
        }
    }

    // Clear the unload list (every frame)
    m_vpChunkUnloadList.clear();
}

Chunk Visibility


This is the update phase that brings most of the ChunkManager concepts to life. The visibility update phase is used to update the VilibilityList with all the potential blocks that might be visible to the current camera. Also the visibility list is used to update all the other list, for only chunks that are visible can be set to load,setup,rebuild and render.
  • // TODO : include code

Chunk Render


The render update phase is a simple culling process, in my voxel engine I do frustum culling and some other rendering optimizations but the basic logic is the same. We have a VisibilityList that we calculated in the visibility phase and just cull away any chunks that dont need to be rendered. For example completely empty chunks, chunks that are completely surrounded by their neighbors, occluded chunks, etc...
void ChunkManager::UpdateRenderList()
{
    // Clear the render list each frame BEFORE we do our tests to see what chunks should be rendered
    m_vpChunkRenderList.clear();

    ChunkList::iterator iterator;
    for(iterator = m_vpChunkVisibilityList.begin(); iterator != m_vpChunkVisibilityList.end(); ++iterator)
    {
        Chunk* pChunk = (*iterator);

        if(pChunk != NULL)
        {
            if(pChunk->IsLoaded() && pChunk->IsSetup())
            {
                if(pChunk->ShouldRender()) // Early flags check so we don't always have to do the frustum check...
                {
                    // Check if this chunk is inside the camera frustum
                    float c_offset = (Chunk::CHUNK_SIZE * Block::BLOCK_RENDER_SIZE)-Block::BLOCK_RENDER_SIZE;
                    Vector3d chunkCenter = pChunk->GetPosition() + Vector3d(c_offset, c_offset, c_offset);

                    float c_size = Chunk::CHUNK_SIZE * Block::BLOCK_RENDER_SIZE;
                    if(m_pRenderer->CubeInFrustum(m_pRenderer->GetActiveViewPort(), chunkCenter, c_size, c_size, c_size))
                    {
                        m_vpChunkRenderList.push_back(pChunk);
                    }
                }
            }
        }
    }
}

Comments