Quad tree issues

This is a discussion on Quad tree issues within the Game Programming forums, part of the General Programming Boards category; I've gotten the rendering for the quad tree system to work but there is a major problem. I'm not sure ...

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

    Quad tree issues

    I've gotten the rendering for the quad tree system to work but there is a major problem.

    I'm not sure how to correctly extract the height data from the map given that each terrain 'piece' holds only world coordinates. Extracting the index into the heightmap from the world coordinates is proving to be messy.

    I still need some type of LOD method because with 360500 triangles I'm still only getting about 26 to 30 FPS.

    Because the height data is not extracting correctly, I'm getting some very strange maps.

    But the quad-tree portion works fine and splits the terrain up correctly.

    Code:
    void CTerrain::CreateVertices(TerrainNode *pNode,
                                  int x,int z,int x2,int z2,
                                  int DesiredSize)
    {
       
      //Check for leaf condition
        //char txt[100];
    	  //sprintf(txt,"X:%d\n Z:%d\n X2:%d\n Z2:%d\n W:%d\n D:%d\n DS:%d",x,z,x2,x,x2-x,z2-z,DesiredSize);
    	  //::MessageBox(0,txt,0,0);
    	pNode->vMin=D3DXVECTOR3((float)x,-32767.0f,(float)z);
      pNode->vMax=D3DXVECTOR3((float)x2,32767.0f,(float)z2);
    
      if ((x2-x)<=DesiredSize) 
      {
        //Yes, we are a leaf
        pNode->iType=QUAD_LEAF;
        
        //Set min/max in prep for later frustum cull
        
        //Get extents of vertex buffer
        pNode->iNumVertsPerRow=((x2-x)/m_iCellSize)+1;
        pNode->iNumVertsPerCol=((z2-z)/m_iCellSize)+1;
        pNode->iNumCellsPerRow=pNode->iNumVertsPerRow-1;
        pNode->iNumCellsPerCol=pNode->iNumVertsPerCol-1;
    
    	  pNode->iNumVerts=pNode->iNumVertsPerRow*pNode->iNumVertsPerCol;
    	  pNode->iNumTris=(pNode->iNumCellsPerRow*pNode->iNumCellsPerCol)*2;
    
    	  pNode->iMapWidth=(x2-x)/m_iCellSize;
    	  pNode->iMapDepth=(z2-z)/m_iCellSize;
    	  
    	  //sprintf(txt,"%d %d %d %d %d",pNode->iNumVertsPerRow,
    	  //                             pNode->iNumVertsPerCol,
    	  //                             pNode->iNumCellsPerRow,
    	  //                             pNode->iNumCellsPerCol,
    	  //                             pNode->iNumVerts);
    	  //::MessageBox(0,txt,0,0);
    	  
        //Allocate vertex memory
    	  HRESULT hr=m_pDevice->CreateVertexBuffer(pNode->iNumVerts*sizeof(TerrainVertex),
    	  		  			                             D3DUSAGE_WRITEONLY,
    	  		  			                             TerrainVertex::FVF,
    	  		  			                             D3DPOOL_MANAGED,
    	  		  			                             &pNode->pVB,0);
    				  	                     
      	if (FAILED(hr)) 
    	  {
    	    ::MessageBox(0,"Cannot create mesh",0,0);
    	    return;
    	  }
    	 	//Create vertices
    	  int StartX=x;
    	  int StartZ=z;
    	  int EndX=x2;
    	  int EndZ=z2;
    
      	//Lock vertex buffer
    
    	  TerrainVertex *Vertices=0;
    
    	  pNode->pVB->Lock(0,0,(void **)&Vertices,0);
      	int index=0;
    	
    	  int lastindex=0;
    	  //Generate vertices
    	  float TexU=fabs(StartX/(float)m_dwWorldWidth);
    	  float TexV=fabs(StartZ/(float)m_dwWorldDepth);
    	  float StartTexU=TexU;
    	  
    	  float TexInc=1.0f/(float)m_iMapWidth;
    	  
    	  int row=0,col=0;
    	  
    	  if (StartX<0)
    	  {
    	    row=(m_dwWorldWidth2+StartX)/m_iCellSize;
    	  } else row=(m_dwWorldWidth2-StartX)/m_iCellSize;
    	  
    	  if (StartZ<0)
    	  {
    	    col=(m_dwWorldDepth2+StartZ)/m_iCellSize;
    	  } else col=(m_dwWorldDepth2-StartZ)/m_iCellSize;
    	  
    	  int startcol=col;
    	  
    	  //char txt[100];
    	  //sprintf(txt,"%d %d %u %u %d %d",row,col,m_dwWorldWidth2,m_dwWorldDepth2,StartX,StartZ);
    	  //::MessageBox(0,txt,0,0);
    	  
    	  
    	  float minheight=0.0f;
    	  float maxheight=0.0f;
    	  
    	  for (int i=StartZ;i<=EndZ;i+=m_iCellSize)
    	  {
    		  col=0;
    		  for (int j=StartX;j<=EndX;j+=m_iCellSize)
    		  {
            float height=(float)(m_puHeightMap[row*m_iNumVertsPerRow+col]<<2);
            if (minheight<=height) minheight=height;
            if (maxheight>=height) maxheight=height;
                 
            Vertices[index]=TerrainVertex((float)j,height,(float)i,
                  										    TexU,TexV);
    			  Vertices[index].Diffuse=D3DXCOLOR(0.0f,0.0f,0.0f,1.0f);
    			  Vertices[index].Specular=D3DXCOLOR(0.0f,0.0f,0.0f,1.0f);
            Vertices[index].DetailTexU=128.0f*TexU;
            Vertices[index].DetailTexV=128.0f*TexV;        
            Vertices[index].LightU=TexU;
            Vertices[index].LightV=TexV;        
    			 
    			  index++;
    			  TexU+=TexInc;
    			  col++;
    		  }
    	    //sprintf(txt,"VB Index:%d\n VB Max:%d  Diff:%d",index-1,pNode->iNumVerts,
    	    //index-lastindex);
          //::MessageBox(0,txt,0,0);
          //lastindex=index;
          TexV+=TexInc;
          TexU=StartTexU;
          row++;
          col=startcol;
        }
        
        //::MessageBox(0,"Vertex buffer done",0,0);
        
    	  pNode->pVB->Unlock();
    
    	  
        pNode->vMin.y=maxheight;
        pNode->vMax.y=minheight;
        
        //Generate indices
        index=0;
    	  hr=m_pDevice->CreateIndexBuffer(pNode->iNumTris*3*sizeof(WORD),
    	                                  D3DUSAGE_WRITEONLY,
    	                                  D3DFMT_INDEX16,
    	                                  D3DPOOL_MANAGED,
    	                                  &pNode->pIB,
    	                                  0);
        if (FAILED(hr))
        {
          ::MessageBox(0,"Cannot create index buffer",0,0);
          return;
        }
                                  
    	  WORD *Indices=0;
    	  
    	  pNode->pIB->Lock(0,0,(void **)&Indices,0);
    	  	  
    	  for (int i=0;i<pNode->iNumCellsPerCol;i++)
    	  {
    		  for (int j=0;j<pNode->iNumCellsPerRow;j++)
    		  {
    			  Indices[index]=i*pNode->iNumVertsPerRow+j;
    			  Indices[index+1]=i*pNode->iNumVertsPerRow+(j+1);
    			  Indices[index+2]=(i+1)*pNode->iNumVertsPerRow+j;
    			
    			  Indices[index+3]=i*pNode->iNumVertsPerRow+(j+1);
    			  Indices[index+4]=(i+1)*pNode->iNumVertsPerRow+(j+1);
    			  Indices[index+5]=(i+1)*pNode->iNumVertsPerRow+j;
    			  index+=6;
    		
    		  }
    	    //sprintf(txt,"%d %d",index,pNode->iNumIndices);
    	    //::MessageBox(0,txt,0,0);
    	  }
    	  
    	  //::MessageBox(0,"Index buffer done",0,0);
    	  
    	  pNode->pIB->Unlock();
    	
    	//End recursion
    
    	return;
      }
      
      //This is a node, not a leaf 
      pNode->iType=QUAD_NODE;
    
      //Find centers
      int midx=(x2-x)>>1;
      int midz=(z2-z)>>1;
      midx+=x;
      midz+=z;
      
      //char txt[100];
      //sprintf(txt,"%d %d %d %d MX:%d MZ:%d",x,z,x2,z2,midx,midz);
      //::MessageBox(0,txt,0,0);
      
    
      //Create children and recurse into tree
      pNode->ChildUL=new TerrainNode();
      CreateVertices(pNode->ChildUL,x,z,midx,midz,DesiredSize);
      
      pNode->ChildUR=new TerrainNode();
      CreateVertices(pNode->ChildUR,midx,z,x2,midz,DesiredSize);
      
      pNode->ChildLL=new TerrainNode();
      CreateVertices(pNode->ChildLL,x,midz,midx,z2,DesiredSize);
      
      pNode->ChildLR=new TerrainNode();
      CreateVertices(pNode->ChildLR,midx,midz,x2,z2,DesiredSize);
    }
    Last edited by VirtualAce; 01-28-2006 at 01:34 PM.

  2. #2
    Super Moderator VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,596
    Finally got it working and turned god awful vsync off. Fairly satisfied with framerates thus far considering there isn't any CLOD here.

    Params for this screenie:
    • Node size: 32x32
    • Cell size:32
    • View distance:7000.0f
    • HFOV: D3DX_PI*.33f
    • Terrain height coef: 8.0f
    • Fog start: 6000.0f
    • Fog end: 7000.0f
    • Height map size: 1024x1024
    • Light map size: 1024x1024 (pre-computed)
    • Detail texture size: 512x512
    • Detail texture blend size: 512x512 (extremely detailed - 1 terrain cell=1 full detail texture)
    • Terrain type: GIMP generated Cloud plasma, detail of 15, 2 Tiled blurs with size of 13
    • Triangle cull mode: CW
    • Engine cull mode: Box in frustum using pos and neg vertices of bounding box

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

  4. #4

    Join Date
    May 2005
    Posts
    1,041
    Hey looks very nice, no visible artifacts. Anything being executed on shaders?

    Future plans?

    Keep up the good work.
    I'm not immature, I'm refined in the opposite direction.

  5. #5
    Super Moderator VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,596
    No shaders yet.

    Working on reflecting the geometry about the water plane. Plans are to use cubic environment mapping. To perturb the reflection I'll need to use a shader that utilizes the fresnel term to make it look right. I'm currently reworking the entire engine to prepare it for environment mapping. I must call render twice, but I also must tell the renderer that during the cubic rendering I don't want to draw the water plane. The water is not a mesh and I do not have any plans to make it one. D3D seems to work very well with large quads and I feel making it a mesh will kill the frames while not adding any more visual quality to the frame.

    Shaders are in the works and thus far I'm ready to use specular bump mapping, but they are not enabled yet. I'm also working on a renderer class that will render everything it needs from one huge vertex and index buffer using consecutive DrawIndexedPrimitive calls for geometry. Static geometry will use this system and dynamic will most likely use ID3DXMesh:rawSubset().

    I'm also wanting to use an adaptive quad tree for rendering, but none of it is trivial code so it might take some time.

    Thanks for your comments.
    Last edited by VirtualAce; 01-30-2006 at 12:41 PM.

  6. #6

    Join Date
    May 2005
    Posts
    1,041
    Hey that all sounds really great Bubba, I'm anxious for updates.

    Terrain type: GIMP generated Cloud plasma, detail of 15, 2 Tiled blurs with size of 13
    GIMP? I'm guessing it's a heightfield generating program or something?


    Also, I'm guessing you're currently using D3D's built-in fog, correct? Are you using that as eye-candy or more as a culling method? What is the falloff on the fog (how quickly does it obscure objects in its field...linearly? exponentially, etc)

    EDIT:

    I feel making it a mesh will kill the frames while not adding any more visual quality to the frame.
    Probably...you would be able to do geometric waves that oscillate, but one of the purposes of having all these fancy bump mapping schemes is that you can make flat ........ look...bumpy! And seeing as how shaders is your thing, well, that just makes a whole lot more sense.
    Last edited by BobMcGee123; 01-30-2006 at 01:37 PM.
    I'm not immature, I'm refined in the opposite direction.

  7. #7
    Slave MadCow257's Avatar
    Join Date
    Jan 2005
    Posts
    735
    GIMP? I'm guessing it's a heightfield generating program or something?
    You don't know of The GIMP? The way to make clouds is filter->render->clouds->plasma

  8. #8
    Crazy Fool Perspective's Avatar
    Join Date
    Jan 2003
    Location
    Canada
    Posts
    2,640
    >GIMP? I'm guessing it's a heightfield generating program or something?

    More like open source Photo-shop.


    Looks good Bubba, I'm looking forward to a post on your water reflection implementation

  9. #9

    Join Date
    May 2005
    Posts
    1,041
    >>You don't know of The GIMP?

    No I just enjoy asking questions about things I am already familiar with because it makes me look cool.
    I'm not immature, I'm refined in the opposite direction.

  10. #10
    Super Moderator VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,596
    GIMP is an impressive image editing program. It does just about everything I would ever need and everything you hoped that expensive paint program you just bought does, but doesn't.

    GIMP rocks.

    The fog is simple D3D pixel fog or card-based pixel fog and the ranges are:

    FogStart: 4000.0f
    FogEnd: 6500.0f;
    Type: Linear pixel-based

    When underwater:
    FogStart: 50.0f
    FogEnd: 400.0f
    Type: Linear pixel-based

  11. #11
    Super Moderator VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,596
    This is a very early version of planar water reflection. The FPS drop through the floor on my video card. I will prob only dynamically update the cube map if the card is fast enough, otherwise I will alternate cube maps every 15 frames or so. This makes the cube map lag behind the camera, but most games also suffer from this on lower end cards.

    Again lots of issues to fix here. Namely I cannot use a single quad for the water since the camera space reflection vector is computed using the vertex's position and the vertex normal. This is what is causing the huge stretchy thing in the distance. So the more resolute the water grid, the better the reflections.

    I will implement a quad tree culled water grid next and test this system out.

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. Binary Tree, couple questions
    By scoobasean in forum C Programming
    Replies: 3
    Last Post: 03-12-2005, 08:09 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