Thread: Quad tree neighbors

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.

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

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.

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.

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.

Probably has to do with the implementation of D3DXPlaneNormalize not allowing the same buffer for the target and destination.

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.

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.

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.