Hi everyone,
I'm working on a quadtree-based dynamic terrain program which subdivides a virtual mesh to change level of detail depending on camera distance to the terrain. My world is built with cells defined by the following structure:
struct TerrainCell
{
float sideLength;
D3DXVECTOR3 centre;
TerrainVertex vertices[4]; //bottom-left, top-left, bottom-right, top-right
vector <TerrainCell> children;
};
...Note that every cell has a list of child cells which may be empty or populated with four children depending on camera distance to the cell.
At the moment, my program works as follows:
- Hold an array of 'base' TerrainCells whose sideLength is the largest allowed.
- Each frame, build a 'render queue' by traversing the quadtree for each base cell, creating or removing child cells recursively depending on distance. This render queue is simply a Vector containing pointers to all the cells which will be rendered this frame. It is built with the following recursive function:
void ProcessCell(TerrainCell *cell)
{
//No children if camera is too far away or cell is minimum size
if (!ShouldCellSplit(cell) || cell->sideLength <= sideLengthLimit)
{
cell->children.clear();
renderQueue.push_back(cell);
return;
}
//If the cell SHOULD have children but DOESN'T, add them
if (cell->children.size() != 4)
{
cell->children.clear();
float halfSize = cell->sideLength/2, quarterSize = cell->sideLength/4;
cell->children.push_back(TerrainCell(D3DXVECTOR2(cell->centre.x - quarterSize, cell->centre.z + quarterSize), halfSize));
cell->children.push_back(TerrainCell(D3DXVECTOR2(cell->centre.x + quarterSize, cell->centre.z + quarterSize), halfSize));
cell->children.push_back(TerrainCell(D3DXVECTOR2(cell->centre.x + quarterSize, cell->centre.z - quarterSize), halfSize));
cell->children.push_back(TerrainCell(D3DXVECTOR2(cell->centre.x - quarterSize, cell->centre.z - quarterSize), halfSize));
}
//Recursively process the children
ProcessCell(&cell->children[0]);
ProcessCell(&cell->children[1]);
ProcessCell(&cell->children[2]);
ProcessCell(&cell->children[3]);
}
- I then loop through the render queue, put the vertices for each cell into a D3DUSAGE_DYNAMIC buffer and draw them one at a time using as TriangleStrips using DrawPrimitive().
This creates my desired effect very well, i.e. a dynamic terrain surface which subdivides in certain places depending on camera distance:
[attachment=32622:wf.png]
...however, I have the problem of cracks between adjacent cells which have different detail levels:
[attachment=32621:sld.png]
I'm aware that this is a problem which can be solved using a few approaches, but I'm quite stuck as to how I should implement these into my own algorithm. My favourite idea is to build up a library of where the cracks exist and fill them in with a separate rendering pass by drawing some new triangles using the vertices that define the cracks. However I'm a bit stuck on the best way to gather this information. How do I actually find out which cells are contributing to a crack and how can I find the vertices of the associated triangle?
Any thoughts that you might have on how you would go about solving this issue would be much appreciated - I feel like I just need something to push me in the right direction and get me started :)
Thanks!