Advertisement Jump to content
Sign in to follow this  

Care to take a look at my dynamic terrain algorithm?

This topic is 841 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi everyone,

I really like the idea of creating a simulation of a (virtually) unlimited terrain using something like a perlin noise algorithm to determine the height of any (x, z) location and applying the height to a grid of vertices. Doing this requires some sort of dynamic LOD system to simplify the distant terrain while making nearby sections appear more detailed depending on camera distance. I have a rough working version right now which is built something like this:
- The terrain consists of a quadtree where each node represents a single tile. A tile contains four vertices and may contain four immediate child tiles of the same type. This allows the quadtree to be stored by creating a set of 'base' tiles and adding/removing children recursively as requierd. My terrain tiles are defined like this:
struct TerrainCell
    float sideLength;
    D3DXVECTOR3 centre;
    TerrainVertex vertices[4]; //bottom-left, top-left, bottom-right, top-right
    vector <TerrainCell> children;
    TerrainCell(D3DXVECTOR2 in_centre, float in_sideLength)
        //Logic to determine locations of vertices using the centre and sideLength.
- Each frame, I traverse the ENTIRE quadtree starting at the base cells. For each cell I add or remove child cells depending on the camera distance. If a cell needs to become more detailed, I add the four children if they do not already exist. I then process the children recursively in the same way. Eventually, I reach a point where a given cell decides it should NOT split. At this point, I add a reference to that cell into a 'render queue' so that I know to draw it on this frame.
Note: the logic used to determine whether cells should split is simple, and it is currently governed by this function:
bool ShouldCellSplit(TerrainCell *cell)
    return D3DXVec3Length(&(cell->centre - mainCam.pos)) < 10*cell->sideLength;
- Once this frame's render queue is built, I loop through all the cells in there and add them sequentially to a vertex buffer. The size of the buffer is hard-coded - at the moment I have made it large enough to contain 1000 cells (each with 4 vertices). It is created using the following parameters when the program starts: d3ddev->CreateVertexBuffer(vertBufferSize*4*sizeof(TerrainVertex), D3DUSAGE_DYNAMIC | D3DUSAGE_WRITEONLY, 0, D3DPOOL_DEFAULT, &vertexBuffer, 0). vertBufferSize is 1000 (i.e. the buffer can contain up to 1000 cells). Here is how I then add and render the cells:
unsigned numTilesProcessed = 0;
for (unsigned rqc = 0; rqc < renderQueue.size(); rqc++) //Loop through all the cells in the render queue
    void* pVoid;
    if (numTilesProcessed >= vertBufferSize) //The vertex buffer is full - need to render the contents and empty it
        if (FAILED(d3ddev->SetVertexDeclaration(vertexDecleration))){return false;} //A declaration matching the content of a TerrainVertex
        if (FAILED(d3ddev->SetStreamSource(0, vertexBuffer, 0, sizeof(TerrainVertex)))){return false;}
        for (unsigned prt = 0; prt < vertBufferSize; prt++) //Draw the tiles one by one
            if (FAILED(d3ddev->DrawPrimitive(D3DPT_TRIANGLESTRIP, prt*4, 2))){return false;}
        if (FAILED(vertexBuffer->Lock(0, 0, (void**)&pVoid, D3DLOCK_DISCARD))){return false;}
        numTilesProcessed = 0;
    else //This will occur if we have not reached the buffer's size limit yet
        if (FAILED(vertexBuffer->Lock(numTilesProcessed*4*sizeof(TerrainVertex), 4*sizeof(TerrainVertex), (void**)&pVoid, D3DLOCK_NOOVERWRITE))){return false;}
    memcpy(pVoid, renderQueue[rqc]->vertices, 4*sizeof(TerrainVertex));
    if (FAILED(vertexBuffer->Unlock())){return false;}
    numTilesProcessed += 1;
(There is also some more very similar code afterwards to handle the final batch of tiles which probably won't fill the vertex buffer up to its capacity).
...and that's pretty much it! The thing is, I came up with this algorithm having had little experience of terrain rendering or quadtrees before, so I suspect that people more experienced in this area will see ways to improve it or optimise certain parts. Perhaps it's ugly and could be entirely re-written in a much cleverer way! So what do you think?
Thanks for taking a look - any comments would be much appreciated :)
Edited by george7378

Share this post

Link to post
Share on other sites

Some ideas:

Instead of processing entire tree top down, cache the result of visible nodes and at each frame decide if they should collapse to parent, subdivide to children, or stay the same.

This should be faster especially if you port it to GPU compute, which could also generate the index buffers (all should take less than 1ms finally).

Compute shader would also remove costly data transfer, and using indirect draw / dispatch draw calls should also reduce to one or two.

Share this post

Link to post
Share on other sites
Sign in to follow this  

  • Advertisement

Important Information

By using, you agree to our community Guidelines, Terms of Use, and Privacy Policy. is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!