1. ## Quad tree neighbors solved

Since the old thread is 10 days old I started a new one.

In short I figured out how to get the N,S,E and W neighbors of any node in the tree.

NW - NE, SW
- East = NE
- South = SW

NE - NW,SE
- West = NE
- South = SE

SW - NW, SE
- East = SE
- West = NW

SE - NE,SW
- West = SW
- North = NE

Code:
...
...

pNode->NW->E_id = NE_id;
pNode->NW->S_id = SW_id;

pNode->NE->W_id = NW_id;
pNode->NE->S_id = SE_id;

pNode->SW->E_id = SE_id;
pNode->SW->N_id = NW_id;

pNode->SE->W_id = SW_id;
pNode->SE->N_id = NE_id;
...
...
So during render:

Code:
...

if (getNode(pNode->W_id)->LOD != pNode->LOD)
{
//West patch LOD does not match current patch LOD
//West side of current patch must be altered to 'seam' into neighbor patch
}
...
...
Of course more checks need to be in place to see if the patch has a valid N,S,E,W neighbor but that's quite simple.

Incidentally do other terrain render algorithms such as ROAM and Ruetger's (sp?) use a quad tree?

3. Rutger's (I can't spell it either, ask me two years ago) original paper used a quadtree-based method very similar to what you're doing, but ROAM uses an adaptive triangle mesh iirc. Rutger used a 2d array to keep track of the neighbors, however, where he would have a spot for each node that would be set to 0 or 1 based on whether it was split. He had some clever way of going through the array to figure out the neighbors of a particular node to do the edge reconciling, but I never succeeded in deciphering it and ended up implementing geomipping myself.

4. Hi Bubba. It is interesting, you choose to build the neighbors into the tree when constructed? I think it's called building "ropes" into the tree. How do you build the tree and what are members of the tree nodes? Could you post more source code, I am not sure I follow your solution correctly

5. Code:
float Width,
float wx,
float wz,
float wx2,
float wz2)
{
float patch_width = (wx2 - wx);
float radius = fabs(patch_width * 0.5f);

D3DXVECTOR3 vecPatchPos;
vecPatchPos.x = (wx + wx2) * 0.5f;
vecPatchPos.y = 0.0f;
vecPatchPos.z = (wz + wz2) * 0.5f;

pNode->bound_sphere.m_vecPos = vecPatchPos;
m_num_nodes++;

if (patch_width == Width)
{
pNode->isLeaf = true;
m_num_patches++;
return;
}

pNode->isLeaf = false;

float midwx = (wx2 + wx) * 0.5f;
float midwz = (wz2 + wz) * 0.5f;

pNode->NW =  new TerrainPatch();
pNode->NW->patch_direction = NORTH_WEST;
pNode->NW->Parent = pNode;

pNode->NE =  new TerrainPatch();
pNode->NE->Parent = pNode;
pNode->NE->patch_direction = NORTH_EAST;

pNode->SW =  new TerrainPatch();
pNode->SW->Parent = pNode;
pNode->SW->patch_direction = SOUTH_WEST;

pNode->SE =  new TerrainPatch();
pNode->SE->Parent = pNode;
pNode->SE->patch_direction = SOUTH_EAST;

pNode->NW->E_id = pNode->NE->patchID;
pNode->NW->S_id = pNode->SW->patchID;

pNode->NE->W_id = pNode->NW->patchID;
pNode->NE->S_id = pNode->SE->patchID;

pNode->SW->N_id = pNode->NW->patchID;
pNode->SW->E_id = pNode->SE->patchID;

pNode->SE->W_id = pNode->SW->patchID;
pNode->SE->N_id = pNode->NE->patchID;

}
That's the code for building the quad tree.

6. Thanks Bubba.

Maybe I am reading it wrong but doesn't it only answer what the N,S,E,W are within the same node (maybe that is all you need to know)? For instance; does it allow a node (of type NW) to know its W neighbor? Wouldn't that require traversing up and down the tree (unless of course all four neighbors for any nodes are stored as members in the node)?

7. Roettgers' Algorithm uses a quad tree. echo ichijoji on the "ask me two years ago" about the details. I haven't looked at that code in ages.

8. Since it's a recursive algorithm and the node neighbors are implemented in each node this means that all nodes now know about their neighbors.

The only trouble spot would be at the quad-tree boundaries.

9. Code:
float midwx = (wx2 + wx) * 0.5f;
float midwz = (wz2 + wz) * 0.5f;
I might be wrong, but shouldn't this be:
Code:
float midwx = ((wx2 - wx) * 0.5f) + wx;
float midwz = ((wz2 - wz) * 0.5f) + wz;
I don't really understand how you're using wx/wx2/wz/wz2.

10. I might be wrong, but shouldn't this be:
The results are the same mathematically with my approach requiring less operations.

Case 1
wx2 = 10
wx = 5

Approach 1
midwx = (10 + 5) * 0.5f;
midwx = (15) * 0.5f;
midwx = 7.5

Approach 2
midwx = (10 - 5) * 0.5f + 5;
midwx = (5) * 0.5f + 5;
midwx = 2.5 + 5;
midwx = 7.5;

Case 2
wx2 = 100
wx = 50

Approach 1
midwx = (100 + 50) * 0.5f;
midwx = (150) * 0.5f;
midwx = 75

Approach 2
midwx = (100 - 50) * 0.5f + 50;
midwx = (50) * 0.5f + 50;
midwx = 25 + 50
midwx = 75

I don't really understand how you're using wx/wx2/wz/wz2.
At the start of the quad tree construction the variables are:

terrain_world_width = cellsize * num_map_columns;
terrain_world_depth = cellsize * num_map_rows;

wx = - (terrain_world_width) * 0.5f;
wz = (terrain_world_depth) * 0.5f;

wx2 = -wx;
wz2 = -wz;

A patch of terrain needs the following variables in order to be created and/or rendered
• NumVertsRow - number of vertices per row
• NumVertsCol - number of vertices per column
• NumCellsRow - number of cells per row (NumVertsRow - 1)
• NumCellsCol - number of cells per column (NumCellsRow - 1)
• NumVerts = NumVertsRow * NumVertsCol
• NumCells = NumCellsRow * NumCellsCol
• NumTris = NumCells * 2 ---> 2 triangles per quad or terrain cell
• NumIndices = NumTris * 3 ---> 3 indices per triangle
• patch_cells_width - width of the patch expressed in cells
• patch_cells_depth - depth of the patch expressed in cells
• patch_world_width - width of the patch expressed in world units
• patch_world_depth - depth of the patch expressed in world units
• patch_pos - world position of the 'center' of the patch
• patch_ID - index of this patch in the terrain's patch container
• NW - Northwest neighbor
• NE - Northeast neighbor
• SW - Southwest neighbor
• SE - Southeast neighbor
• N_ID - North neighbor patch ID
• E_ID - East neighbor patch ID
• S_ID - South neighbor patch ID
• W_ID - West neighbor patch ID
• patch_LOD - current level of detail for this patch (0 to MAX_LOD)
• AABB - the axis-aligned bounding box for this patch
• BSphere - the bounding sphere for this patch

Most of the patch extents data can be pre-computed and just re-used since it never changes. Right now I had to move back to a vertex buffer per patch because I could not get vertex texturing to work correctly. I'm also running out of texture samplers for the shader.

• One master vertex buffer and thus a HUGE savings in video memory
• Height data is computed in the shader
• Extremely fast
• Texture coords readily available for both normal mapping and height data
• Easy to morph terrain by simply altering the underlying height map
• This method does NOT require a vertex buffer lock to page in new height data