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:

---

...
...
UINT NW_id = pNode->BuildQuadTree(pNode->NW, ...
UINT NE_id = pNode->BuildQuadTree(pNode->NE, ...
UINT SW_id = pNode->BuildQuadTree(pNode->SW, ...
UINT SE_id = pNode->BuildQuadTree(pNode->SE, ...

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.

Thread 'pruned'

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

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.

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 :)

Code:

---

void CTerrain::BuildQuadTree(TerrainPatch *pNode,
                            float Width,
                            float wx,
                            float wz,
                            float wx2,
                            float wz2)
{
    float patch_width = (wx2 - wx);
    float radius = fabs(patch_width * 0.5f);
    pNode->bound_sphere.m_Radius = radius;
 
    D3DXVECTOR3 vecPatchPos;
    vecPatchPos.x = (wx + wx2) * 0.5f;
    vecPatchPos.y = 0.0f;
    vecPatchPos.z = (wz + wz2) * 0.5f;

    pNode->bound_sphere.m_vecPos = vecPatchPos;
    pNode->patchID = addPatchPos(vecPatchPos,pNode);
    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;
    BuildQuadTree(pNode->NW,Width,wx,wz,midwx,midwz);

    pNode->NE =  new TerrainPatch();
    pNode->NE->Parent = pNode;
    pNode->NE->patch_direction = NORTH_EAST;
    BuildQuadTree(pNode->NE,Width,midwx,wz,wx2,midwz);
   
    pNode->SW =  new TerrainPatch();
    pNode->SW->Parent = pNode;
    pNode->SW->patch_direction = SOUTH_WEST;
    BuildQuadTree(pNode->SW,Width,wx,midwz,midwx,wz2);
   
    pNode->SE =  new TerrainPatch();
    pNode->SE->Parent = pNode;
    pNode->SE->patch_direction = SOUTH_EAST;
    BuildQuadTree(pNode->SE,Width,midwx,midwz,wx2,wz2);

    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.

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)?

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.

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.

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.

Quote:

---

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

Quote:

---

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.

Vertex texturing advantages:

• 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

Vertex texturing dis-advantages:

• Requires a lot of shader inputs
• Vertex fetching does not work on all cards, even on cards that claim it does
• Several versions of NVidia drivers have severe problems with vertex fetches in vertex shaders
• ATI has next to no support for vertex textures except on extremely recent cards
• Vertex texturing can only be done with certain types of textures
• Documents in the SDK and on the internet about vertex texturing are either far too simplistic, not explained well, or just simply broken. Many use tex2D() which AFAIK can only be used in a PIXEL shader. For vertex texturing in HLSL tex2dlod() must be used.

Keep in mind I've not yet perfected this system nor do I have the geo-mipmapping completely implemented. So far it looks very good and can page in data on the fly. More screenshots to come as I improve the system.