Jump to content
  • Advertisement
Sign in to follow this  
george7378

Dealing With Quadtree Terrain Cracks

This topic is 774 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'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!

Share this post


Link to post
Share on other sites
Advertisement

However I'm a bit stuck on the best way to gather this information


You already mentioned that cracks occur where the level of detail is different ( and that is to be expected ). The cracks occur because the vertices along the edges of the patches of different LODs are in different position. On way to solve this would be to enforce some policy that ensure that maximum difference in LOD is 1 level. Given this, you could construct your vertex buffer for LOD n by skipping every other vertex such that it will line up with LOD n+1. Hopefully, that make sense...( someone need to find a way to make it easy to just draw a simple diagram  directly into the post :D  as you would better understand what I mentioned with an illustration. )

Share this post


Link to post
Share on other sites

1) Detect edge vertices when generating a mesh.
2) Detect which edge vertices are 'odd', these are the ones that mismatch with the next LOD and create holes.
3) Get the neighboring even-vertex-edge positions.

4) Set the odd-vertex position to the average of the two neighboring even positions.

This should close your cracks. The higher-LOD vertices follow a straight line between the two even positions, where the more detailed mesh just has another sample point at the half-way mark.

Then your next problem is knowing when to close the cracks on a side. The most straightforward approach is probably to regenerate a mesh whenever a neighboring mesh changes LOD.

There is another approach where you store two positions per vertex (the main position, and an edge transition position) and a bitflag mask for which edge a vertex is on (or zero if it isn't on an edge), and then when you render the mesh you pass in a bitflag for which edges of the mesh are bordering higher LODs. In the shader you check the edge mask of the vertex against the neighboring LOD bit mask, and if the vertex is on the edge with the higher LOD you set the output position to the transition position. The extra vertex data isn't that bad in the grand scheme of things, and this lets you use the same pre-generated mesh without having to recalculate it every time a neighboring LOD changes. All you have to do is pass in the neighboring-higher-LOD bitmask.
 

Edited by DementedCarrot

Share this post


Link to post
Share on other sites
Thanks very much for the replies. I really like the idea of averaging the positions of the vertices - that should need very little overhead at all.

I've wondered about whether my algorithm can ever give me a situation were two adjacent tiles differ by more than one LOD value, but having tried a bunch of things empirically, I think it naturally enforces this. The decision to split a cell is based on camera distance as a multiple of the cell's side length which seems to produce cascading areas which differ by one LOD only.

I'll give these ideas a go and see what happens :)

Share this post


Link to post
Share on other sites

What about creating a "transitional group of cells"?

 

You can easily check if the whole cell is within the LOD distance or just part of it... if it's just partially within the LOD distance you know what side of your cell is in the LOD n and which in the LOD n-1... so you create a transitional group of cells which holds the positions from the lowest LOD on one side, and the positions of the highest LOD on the other, and interpolate the in-between vertices position of that group from LOD n to LOD n-1...

Share this post


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

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!