Quadtree Terrain Stitching

Just some thoughts. Obviously on a terrain the quadtree is 2x2. For each node, there are 4 neighbors, 2 of which are local neighbors (ie: have the same parent node). Otherwise, I should be able to step up 1 level of the quadtree and check to see I then need to traverse down from there.

Hi,
I am doing this by checking the 4 neighbor nodes of the parent.
if one of the neighbor is not subdivided anymore, it means you need to stitch there.

Here is some pseudocode I am working on, currently only for finding northNeighbor



Node findNorthNeighbor(node)
{
if(node->type == typeRoot)
return NULL;
else if(node == getParent()->sw)
return parent->nw;
else if(node == getParent()->se)
return parent->ne;
else
traverseUpNodeForNorth(node->getParent(), node);
}

Node traverseUpNodeForNorth(parent, node)
{
if(parent->type == typeRoot)
return NULL;

if(parent->sw == node || parent->se == node) // Traverse Up Further
traverseNodeForNorth(parent->getParent(), node);

if(parent->direction == node->direction)
return traverseDownNodeForNorth(parent, node);
}

Node traverseDownNodeForthNorth(parent, node)
{
if(parent->depth == node->depth)
return parent->sw;
else
traverseDownNodeForNorth(parent->sw, node);
}


When you build your quadtree data struct, do you not store the neighbor?
So that you can call

node->GetNeighbor(i)

and by the way usually you dont need 16 indexbuffers, because it is quadtree and two sides will always have the same lod, so you need just 9 indexbuffers.

When you build your quadtree data struct, do you not store the neighbor?
So that you can call

node->GetNeighbor(i)

and by the way usually you dont need 16 indexbuffers, because it is quadtree and two sides will always have the same lod, so you need just 9 indexbuffers.

Yes, right now I am only storing the local parents neighbors (ie: only 2 of them), so will use this code to traverse up/down for the other 2 neighbors after I build the initial quadtree.

Regarding the index buffers, I was using this for reference but you might be right about only needing 9, that was my initial thought too.

I am still having quite a few issues with this quad tree neighbors and I haven't found very much on the internet searching. Does anyone know any good articles, examples or know any books that have a good explanation of the algorithm?

I am still having quite a few issues with this quad tree neighbors and I haven't found very much on the internet searching. Does anyone know any good articles, examples or know any books that have a good explanation of the algorithm?

As promised in the PM, here's the code I've been using (snipped a bit because it's been used in different places):

Some basic enums and some utilities to make things easier to read

enum QuadLocation
{
QL_NW = 0,
QL_NE,
QL_SW,
QL_SE,
QL_ROOT
};

enum QuadNeighborDirection
{
QND_NORTH = 0,
QND_EAST,
QND_SOUTH,
QND_WEST
};

// Neighborhood utilities

static const QuadNeighborDirection QuadNeighborDirectionOpposite[4] =
{
QND_SOUTH,
QND_WEST,
QND_NORTH,
QND_EAST
};

static const QuadLocation QuadChildrenDirections[4][2] =
{
{QL_NW, QL_NE}, // NORTH
{QL_NE, QL_SE}, // EAST
{QL_SW, QL_SE}, // SOUTH
{QL_NW, QL_SW} // WEST
};

static const QuadLocation QuadChildrenOppositeDirections[4][2] =
{
{QL_SW, QL_SE}, // NORTH Opposite
{QL_NW, QL_SW}, // EAST Opposite
{QL_NW, QL_NE}, // SOUTH Opposite
{QL_NE, QL_SE}
};


I'm leaving the camera/screen LOD calculations out of these functions as they're pretty specific for my setup, but here is the basic setup

void QuadNode::Update( )
{
if (HasChildren())
{
for (int i = 0; i < 4; i++)
{
mChildren->Update();
}
}

if (IsReadyToUnsplit())
{
UnsplitNode();

return;
}
else if (IsReadyToSplit())
{
SplitNode();

for (int i = 0; i < 4; i++)
{
mChildren->Update();
}
}
}


That lets me check first to see if anything needs updates for some of my render systems, then checks for unsplitting, then splitting (could be reversed there, but this works well for me).

A note about the following functions - I presume that the Root is Depth: 0 and go from there on down. I apologize for not having better documentation for these, but I have it all worked out in a little notebook that sketched all these possibilities out. I simplified it down to a basic loop checking all neighbors. If you need a better explanation, I'll see if I can dig up that notebook page and scan it (arcane scribblings).

bool QuadNode::IsReadyToSplit( )
{
if (HasChildren() || mDepth == mGridCell->GetGridManager()->GetMaxDepth())
return false;


// I check here for LOD calculation splitting


return false;
}

bool QuadNode::IsReadyToUnsplit( )
{
if (HasChildren() == false)
return false;

QuadNode* neighbor = NULL;

for (int i = 0; i < 4; i++)
{
neighbor = mNeighbor;
if (neighbor && neighbor->HasChildren() && neighbor->GetDepth() == mDepth)
{
if (
neighbor->GetChild(QuadChildrenOppositeDirections[0])->HasChildren() ||
neighbor->GetChild(QuadChildrenOppositeDirections[1])->HasChildren() )
return false;
}
}


// I check here for LOD unsplit calculations

return false;
}


And here is the main section of code for splitting/unsplitting the nodes.

void QuadNode::SplitNode()
{
DestroyTerrainMesh();

for (int i = 0; i < 4; i++)
{
mChildren = new QuadNode(mGridCell, this, i, mDepth + 1);
}

QuadNode* neighbor = NULL;

for (int i = 0; i < 4; i++)
{
neighbor = mNeighbor;
// This isn't 100% needed, but it's a simple speed-up - just skips checking internal neighborhood stuff
if (i != QuadNeighborDirectionOpposite && neighbor)
{
if ((neighbor->GetDepth()+1) == mDepth && (neighbor->HasChildren() == false))
{
neighbor->SplitNode();
}
}
}

QuadNeighborDirection reverseDirection;

QuadNode* myChild[] = {NULL,NULL};
QuadNode* neighborChild[] = {NULL,NULL};

for (int i = 0; i < 4; i++)
{
neighbor = mNeighbor;

if (neighbor)
{
reverseDirection = QuadNeighborDirectionOpposite;
myChild[0] = GetChild(QuadChildrenDirections[0]);
myChild[1] = GetChild(QuadChildrenDirections[1]);

if (neighbor->HasChildren() && (neighbor->GetDepth() == mDepth))
{
neighborChild[0] = neighbor->GetChild(QuadChildrenOppositeDirections[0]);
neighborChild[1] = neighbor->GetChild(QuadChildrenOppositeDirections[1]);

myChild[0]->SetNeighbor(neighborChild[0], i);
myChild[1]->SetNeighbor(neighborChild[1], i);

neighborChild[0]->SetNeighbor(myChild[0],reverseDirection);
neighborChild[1]->SetNeighbor(myChild[1],reverseDirection);

neighbor->SetNeighbor(this, reverseDirection);
}
else if ((neighbor->HasChildren() == false) && neighbor->GetDepth() == mDepth)
{
myChild[0]->SetNeighbor(neighbor, i);
myChild[1]->SetNeighbor(neighbor, i);

neighbor->SetNeighbor(this, reverseDirection);
}
else if ((neighbor->GetDepth()+1) == mDepth && neighbor->HasChildren())
{
neighborChild[0] = neighbor->GetChild(QuadChildrenOppositeDirections[0]);
neighborChild[1] = neighbor->GetChild(QuadChildrenOppositeDirections[1]);

if (mLocation == QuadChildrenDirections[0])
{
myChild[0]->SetNeighbor(neighborChild[0], i);
myChild[1]->SetNeighbor(neighborChild[0], i);

neighborChild[0]->SetNeighbor(this, reverseDirection);
SetNeighbor(neighborChild[0],i);
}
else if (mLocation == QuadChildrenDirections[1])
{
myChild[0]->SetNeighbor(neighborChild[1], i);
myChild[1]->SetNeighbor(neighborChild[1], i);

neighborChild[1]->SetNeighbor(this, reverseDirection);
SetNeighbor(neighborChild[1],i);
}

}
}
}

mChildren[QL_NW]->SetNeighbor(mChildren[QL_NE], QND_EAST);
mChildren[QL_NE]->SetNeighbor(mChildren[QL_NW], QND_WEST);

mChildren[QL_NW]->SetNeighbor(mChildren[QL_SW], QND_SOUTH);
mChildren[QL_SW]->SetNeighbor(mChildren[QL_NW], QND_NORTH);

mChildren[QL_SW]->SetNeighbor(mChildren[QL_SE], QND_EAST);
mChildren[QL_SE]->SetNeighbor(mChildren[QL_SW], QND_WEST);

mChildren[QL_SE]->SetNeighbor(mChildren[QL_NE], QND_NORTH);
mChildren[QL_NE]->SetNeighbor(mChildren[QL_SE], QND_SOUTH);

}

void QuadNode::UnsplitNode()
{
QuadNode* neighbor = NULL;
QuadNeighborDirection reverseDirection;

for (int i = 0; i < 4; i++)
{
neighbor = mNeighbor;
if (neighbor)
{
reverseDirection = QuadNeighborDirectionOpposite;

if (neighbor->HasChildren() && neighbor->GetDepth() == mDepth)
{
neighbor->GetChild(QuadChildrenOppositeDirections[0])->SetNeighbor(this, reverseDirection);
neighbor->GetChild(QuadChildrenOppositeDirections[1])->SetNeighbor(this, reverseDirection);
neighbor->SetNeighbor(this, reverseDirection);
}
else if (neighbor->HasChildren() == false && neighbor->GetDepth() == mDepth)
{
neighbor->SetNeighbor(this, reverseDirection);
}
}
}

for (int i = 0; i < 4; i++)
{
delete mChildren;
mChildren = NULL;
}

CreateTerrainMesh();
}


If you have paper handy and remember that it goes Root at Depth: 0 on down, it's fairly easy to work these out for one direction, and it's true for the rest. I've used this in a number of terrain projects in one form or another, but this is what I have in my current project (minus a bunch of LOD code). Just lemme know if you need any clarifications and I'll do what I can. Now, I'm gonna hit post before this stupid storm knocks my power out.

Thanks a ton Dave, I really appreciate it. Will let you know if I have any questions but I am very close to having it working now.

Just to let you know there exists other solutions than stitching. I personally use skirts instead. Completely hazzle free, and way simpler code..

http://www.gamedev.net/topic/315176-zbuffer-and-terrain-skirts/


Henning

Implemented HexiDave's code into my system (some minor adjustments obviously) but it works great. Wish I could give him 10x thumbs ups.