Quad tree neighbors

This is a discussion on Quad tree neighbors within the Game Programming forums, part of the General Programming Boards category; The problem I need to calculate the N, S, E and W neighbors of a quad tree. However here is ...

  1. #1
    Super Moderator VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,596

    Quad tree neighbors

    The problem
    I need to calculate the N, S, E and W neighbors of a quad tree. However here is the data structure:

    Code:
    struct TerrainPatch
    {
        bool isLeaf;
        int currentLOD;
        D3DXVECTOR3 vecWorldPos;
       
        size_t patchID;
        TerrainPatch *Parent;
        TerrainPatch *NW;
        TerrainPatch *NE;
        TerrainPatch *SW;
        TerrainPatch *SE;
    
        X3DUtil::AABB Bounds;
    
        BSphere bound_sphere;
    
        TerrainPatch():vecWorldPos(0.0f,0.0f,0.0f),patchID(0),Parent(0),NW(0),NE(0),SW(0),SE(0),
                       isLeaf(false),currentLOD(0),Bounds(),bound_sphere() { }
      
    };
    I need to figure this out so I can add 'LOD patches' to connect the various LODs in my terrain. Somehow during render I need to dynamically 'patch' the index buffer. As of right now I'm not leaning in this direction since this would require a lock and unlock for all patches that were 'edge' cases (literally 'edge' cases ).

    Current system
    My system right now uses 1 vertex buffer and LOD * num_levels index buffers. The data is not held in the quadtree since the vertex buffer and the index buffer never change. To keep from dynamically locking the vertex buffer to add in the Y height values, I'm using vertex texturing in my vertex shader. The height is grabbed from a height texture, scaled, and then Y is set to this value. UV coordinates are computed in the vertex shader and passed onto the pixel shader. This means I can have a huge viewing area and yet only use 2 hardware buffers. At any one time only (patch_size * patch_size) vertices are streamed to the card. This algo is proving to be very hardware efficient. Keep in mind that patch LODs will only differ from each other by a factor of 2. So a patch LOD with 4 times less detail could only border a patch with 2 times more detail or a patch with 8 times less detai.

    The option I'm leaning towards for LOD patches is to pre-compute LOD index buffers and use those at the correct time. There would be 5 more index buffers per LOD. Vertex buffer data does not change. Since the index buffer affects how the triangles are drawn if I re-arrange the index buffer I've effectively reduced or increased the LOD up to a max LOD which is the cell_size of the terrain grid. At cell_size 1 heightmap texel corresponds to 1 vertex.
    The LOD index buffers just skip over several texels and vertices to create the final triangles.

    Static LOD index buffers explained

    Terrain patch 'edge' cases
    • North - different LOD's on the north edge (ignores vertex at: row * patch_cell_width + ( col + 1 ) )
    • East - different LOD's on the east edge (ignores vertex at: (row + 1) * patch_cell_width + ( col + 1 ) )
    • West - different LOD's on the west edge (ignores vertex at: (row + 1) * patch_cell_width + col )
    • North and East - different LOD's on both north and east edges
    • West and North - different LOD's on both west and north edges


    South edge cases do not matter since LOD's only differ as you move away from the camera. Essentially the south edge case of a patch with less LOD is the same as a north edge patch with more LOD.

    These of course would have to be pre-computed for all LODs. So the new number of index buffers would be LODs * num_levels * 6. This may seem like a lot but the advantage is they are all static and I just choose at render time which static index buffer to use.

    However for any of this to work I must know what the LOD of the patches to the N, S, E, and W are. This does not seem possible given the structure of a quad tree.

    Any ideas? Sorry so long but this is not exactly a simple rendering system to explain.
    Last edited by VirtualAce; 05-01-2008 at 09:39 PM.

  2. #2
    Super Moderator VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,596
    I didn't figure I would get any responses. Guess I have to figure this one out on my own. And to think I do this stuff as a hobby.

  3. #3
    Registered User
    Join Date
    Oct 2006
    Location
    UK/Norway
    Posts
    485
    Would love to help you out, but this is far more advance then anything what I have done before. If you wait a few years I might look into it for you...

    I recommend posting the same thing over at gameDev.net.

    BTW, how long have you been programming games?

    Best of luck

  4. #4
    Registered User
    Join Date
    Apr 2008
    Posts
    890
    Yeah, gamedev or forums.indiegamer.com would be good places to ask. I've never implemented a quad tree for the simple games I've written.

  5. #5
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681
    Have you tried seeing if any of the space filling algorithms would help you out? I just went to a talk where something very similar was discussed and space filling algorithms were used to put the data onto the disk in such a way that points near each other were kept close to each other on disk. You might be able to do something similar.

  6. #6
    Super Moderator VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,596
    I've found some major issues with my index buffers. Going to try to fix that before tackling this problem. Also fixed the frustum culling by creating the planes locally and then normalizing them and saving the result in the class. Weird b/c I was setting the class member via an assignment operator but when it normalized everything went haywire.


    Code:
    void Compute(D3DXMATRIX matView,D3DXMATRIX matProj)
        {
            D3DXMATRIX matClip =  matView * matProj;
            
            //D3DXMatrixMultiply( &matClip, &matView, lpMatProj);
    
            // Calculate the planes of the frustum 
            D3DXVECTOR4 col0(matClip(0,0),matClip(1,0),matClip(2,0),matClip(3,0));
            D3DXVECTOR4 col1(matClip(0,1),matClip(1,1),matClip(2,1),matClip(3,1));
            D3DXVECTOR4 col2(matClip(0,2),matClip(1,2),matClip(2,2),matClip(3,2));
            D3DXVECTOR4 col3(matClip(0,3),matClip(1,3),matClip(2,3),matClip(3,3));
    
            D3DXPLANE planes[6];
    
    
            planes[0]  =  (D3DXPLANE)(col2);  //near
            planes[1]  =  (D3DXPLANE)(col3 - col2);  //far
            planes[2]  =  (D3DXPLANE)(col3 + col0);  //left
            planes[3]  =  (D3DXPLANE)(col3 - col0); //right
            planes[4]  =  (D3DXPLANE)(col3 - col1); //top
            planes[5]  =  (D3DXPLANE)(col3 + col1); //bottom
    
            for (int i  =  0;i < 6; ++ i)
            {
                D3DXPlaneNormalize(&m_Planes[i],&planes[i]);
            }
    
        }
    This code works, but the following did not:

    Code:
    ...
      m_Planes[0]  =  (D3DXPLANE)(col2);  //near
      m_Planes[1]  =  (D3DXPLANE)(col3 - col2);  //far
      m_Planes[2]  =  (D3DXPLANE)(col3 + col0);  //left
      m_Planes[3]  =  (D3DXPLANE)(col3 - col0); //right
      m_Planes[4]  =  (D3DXPLANE)(col3 - col1); //top
      m_Planes[5]  =  (D3DXPLANE)(col3 + col1); //bottom
    
      for (int i  =  0;i < 6; ++ i)
     {
        D3DXPlaneNormalize(&m_Planes[i],&m_Planes[i]);
     }
    ...
    Why the first version works and the second does not is beyond me. They are doing the same thing.

  7. #7
    Crazy Fool Perspective's Avatar
    Join Date
    Jan 2003
    Location
    Canada
    Posts
    2,640
    Probably has to do with the implementation of D3DXPlaneNormalize not allowing the same buffer for the target and destination.

  8. #8
    Crazy Fool Perspective's Avatar
    Join Date
    Jan 2003
    Location
    Canada
    Posts
    2,640
    As for your original problem, it sounds like you're taking a bottom up approach, computing the neighbors of nodes to see if their LOD level differes. In my implementation I do it top down, never letting all divisions of a node differ by more than one LOD level. Then the "patching" can be done by adding additional edges from the lower LOD patch to the higher one.

    For example, look at the following screen shot. No two neighbors will ever differ by more than one LOD level, that way you can just hook up the centre vertex to the edges of the neighboring nodes.
    Attached Images Attached Images  

  9. #9
    Super Moderator VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,596
    Yeah my LOD setup is the same as yours. However your LOD appears to be based on Y value screen space difference where mine is purely based on distance from camera.

    I have some issues with computing the distance since it is only computing distance from camera to the center of the patch. This causes the LODs to get messed up.

    Lots of work left to do to get the LOD patches in. I don't want to lock the index buffer to accomplish this. When I get it done I still should only be using a minimum of video memory for 1 vertex buffer and about 6 to 8 index buffers.

  10. #10
    l'Anziano DavidP's Avatar
    Join Date
    Aug 2001
    Location
    Plano, Texas, United States
    Posts
    2,738
    Implementing quad trees and octrees is on my list of things to do...right after I finish writing my ray tracer which I am currently working on......
    My Website

    "Circular logic is good because it is."

  11. #11
    Crazy Fool Perspective's Avatar
    Join Date
    Jan 2003
    Location
    Canada
    Posts
    2,640
    Yeah, I use Roettgers algorithm which is a combination of distance and terrain roughness. That screen shot has the distance part disabled. I have a distance based screen shot on my website but it's not really close up enough to see how the differing LOD patches get connected. It works the same as in the roughness LOD though.

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 solved
    By VirtualAce in forum Game Programming
    Replies: 9
    Last Post: 05-23-2008, 09:03 PM
  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, 09:33 AM
  5. BST/Red and Black Tree
    By ghettoman in forum C++ Programming
    Replies: 0
    Last Post: 10-24-2001, 10:45 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21