Thread: Quad tree neighbors solved

  1. #1
    Registered User VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,607

    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.

  2. #2
    Registered User VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,607
    Thread 'pruned'

    Incidentally do other terrain render algorithms such as ROAM and Ruetger's (sp?) use a quad tree?
    Last edited by VirtualAce; 05-17-2008 at 11:49 AM.

  3. #3
    GA ichijoji's Avatar
    Join Date
    Nov 2002
    Posts
    179
    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.
    Illusion and reality become impartiality and confidence.

  4. #4
    Registered User
    Join Date
    May 2008
    Posts
    2
    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. #5
    Registered User VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,607
    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.

  6. #6
    Registered User
    Join Date
    May 2008
    Posts
    2
    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. #7
    Crazy Fool Perspective's Avatar
    Join Date
    Jan 2003
    Location
    Canada
    Posts
    2,640
    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. #8
    Registered User VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,607
    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. #9
    Registered User
    Join Date
    Oct 2001
    Posts
    2,129
    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. #10
    Registered User VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,607
    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.

    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.
    Last edited by VirtualAce; 05-23-2008 at 09:35 PM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Interpreter.c
    By moussa in forum C Programming
    Replies: 4
    Last Post: 05-28-2008, 05:59 PM
  2. Quad tree neighbors
    By VirtualAce in forum Game Programming
    Replies: 10
    Last Post: 05-06-2008, 08:24 AM
  3. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM
  5. BST/Red and Black Tree
    By ghettoman in forum C++ Programming
    Replies: 0
    Last Post: 10-24-2001, 10:45 PM