My stoopid quadtree

  
#include "qtree.h"

#include "debugout.h"

int nCurrentSubdivision = 0;


void CQuadtree::GetSpaceSize(CVector3 *pVerts, int nNumVerts)
{
   float maxWidth = 0.0f, maxHeight = 0.0f, maxDepth = 0.0f;
   float tempWidth = 0.0f, tempHeight = 0.0f, tempDepth = 0.0f;

   
   for(int i=0; i < nNumVerts; i++)
   {
      //Find the center of the points given

      vCenter = vCenter + pVerts[i];
   }

   //Find the center of the points given

   vCenter.x /= nNumVerts;
   vCenter.y /= nNumVerts;
   vCenter.z /= nNumVerts;

   for(i=0; i < nNumVerts; i++)
   {
      //Find the point farthest from center.

      tempWidth  = abs(vCenter.x - pVerts[i].x);
      tempHeight = abs(vCenter.y - pVerts[i].y);
      tempDepth  = abs(vCenter.z - pVerts[i].z);

      if(tempWidth  > maxWidth)  maxWidth  = tempWidth;
      if(tempHeight > maxHeight) maxHeight = tempHeight;
      if(tempDepth  > maxDepth)  maxDepth  = tempDepth;
   }
  
   if(maxWidth > maxHeight && maxWidth > maxDepth)
      fWidth = maxWidth;
   else if(maxHeight > maxDepth)
      fWidth = maxHeight;
   else
      fWidth = maxDepth;

   fHalfWidth = fWidth / 2.0f;
}




//Get verticies (triangles)

//If there are more verticies then the max, divide them up in 4 groups

//Create 4 new quadrees.

//Use the pointer to those quadtrees to assign the verticies to them

//


int CQuadtree::CreateQuadTree(CVector3 *pVerts, int nNumVerts)
{
   int count1=0, count2=0, count3=0, count4=0;
   CVector3 *verts1, *verts2, *verts3, *verts4;
   CVector3 vTemp;


   //Get the center and with of this node

   GetSpaceSize(pVerts, nNumVerts);

   if((nNumVerts / 3) > nMaxTriangles && nCurrentSubdivision < nMaxDivisions)
   {
      //Since we haven''t passed the max number of division, and we have more triangles

      //than the max per node, divide this node into 4.

      bIsParent = true;

      nodes[0] = new CQuadtree;
      nodes[1] = new CQuadtree;
      nodes[2] = new CQuadtree;
      nodes[3] = new CQuadtree;

      for(int i=0; i < (nNumVerts); i+=3)
      {
         //Averages the three components, hopefully this gives the center of the triangle

         vTemp.x = (pVerts[i].x + pVerts[i+1].x + pVerts[i+2].x)/3.0f;
         vTemp.y = (pVerts[i].y + pVerts[i+1].y + pVerts[i+2].y)/3.0f;
         vTemp.z = (pVerts[i].z + pVerts[i+1].z + pVerts[i+2].z)/3.0f;

         //increment the count for the correct sector, sectors are laid out like this

         //-------------

         //|     |     |

         //|  2  |  1  |

         //|     |     |

         //-------------

         //|     |     |

         //|  3  |  4  |

         //|     |     |

         //-------------


         if(vTemp.x >= vCenter.x && vTemp.z >= vCenter.z)
            count1++;
         else if(vTemp.x <= vCenter.x && vTemp.z >= vCenter.z)
            count2++;
         else if(vTemp.x <= vCenter.x && vTemp.z <= vCenter.z)
            count3++;
         else
            count4++;
      }
         
         nCurrentSubdivision++;
   
         verts1 = new CVector3[count1*3];
         verts2 = new CVector3[count2*3];
         verts3 = new CVector3[count3*3];
         verts4 = new CVector3[count4*3];
         
         count1 = 0; count2 = 0;
         count3 = 0; count4 = 0;

         for(i = 0; i < (nNumVerts); i+=3)
         {
            vTemp.x = (pVerts[i].x + pVerts[i+1].x + pVerts[i+2].x)/3.0f;
            vTemp.y = (pVerts[i].y + pVerts[i+1].y + pVerts[i+2].y)/3.0f;
            vTemp.z = (pVerts[i].z + pVerts[i+1].z + pVerts[i+2].z)/3.0f;

            if(vTemp.x >= vCenter.x && vTemp.z >= vCenter.z)
            {
               verts1[count1]     = pVerts[i];
               verts1[count1 + 1] = pVerts[i+1];
               verts1[count1 + 2] = pVerts[i+2];
               count1 += 3;
            }
            else if(vTemp.x <= vCenter.x && vTemp.z >= vCenter.z)
            {
               verts2[count2]     = pVerts[i];
               verts2[count2 + 1] = pVerts[i+1];
               verts2[count2 + 2] = pVerts[i+2];
               count2 += 3;
            }
            else if(vTemp.x <= vCenter.x && vTemp.z <= vCenter.z)
            {
               verts3[count3]     = pVerts[i];
               verts3[count3 + 1] = pVerts[i+1];
               verts3[count3 + 2] = pVerts[i+2];
               count3 += 3;
            }
            else
            {
               verts4[count4]     = pVerts[i];
               verts4[count4 + 1] = pVerts[i+1];
               verts4[count4 + 2] = pVerts[i+2];
               count4 += 3;
            }
         }

         nodes[0]->CreateQuadTree(verts1, count1);
         nodes[1]->CreateQuadTree(verts2, count2);
         nodes[2]->CreateQuadTree(verts3, count3);
         nodes[3]->CreateQuadTree(verts4, count4);

         delete [] verts1;
         delete [] verts2;
         delete [] verts3;
         delete [] verts4;

         nCurrentSubdivision--;
   }
   else 
      AssignVerticies(pVerts, nNumVerts);

   return 0;
}

void CQuadtree::AssignVerticies(CVector3 *pVerts, int nNumVerts)
{
   bIsParent = false;
   nNumTriangles = nNumVerts/3;
   pvVerts = new CVector3[nNumVerts];
   memcpy(pvVerts, pVerts, sizeof(CVector3) * nNumVerts);
}

void CQuadtree::DrawTree(CQuadtree *qTree)
{
   CVector3 campos;
   float dist;

   if(!Frustum.CubeInFrustum(qTree->vCenter.x, qTree->vCenter.y, qTree->vCenter.z, qTree->fWidth))
      return;

   campos = camera.GetPosition();

   dist =  sqrt( ((qTree->vCenter.x - campos.x)*(qTree->vCenter.x - campos.x)) + 
         ((qTree->vCenter.z - campos.z)*(qTree->vCenter.z - campos.z)) );
   if(dist > 3000.0f)
      return;

   if(qTree->bIsParent == false)
   {
      //Draw Verticies in this node


      //Setup textures and colors and lighting here, not sure how, but do it

      
      glBegin(GL_TRIANGLES);
 
      for(int i=0; i < qTree->nNumTriangles*3; i+=3)
      {
         glColor4f(0.0f, (qTree->pvVerts[i].y/3.5f)/256.0f, 0.0f, 1.0f);
         glVertex3f(qTree->pvVerts[i].x, qTree->pvVerts[i].y, qTree->pvVerts[i].z);
        
         glColor4f(0.0f, (qTree->pvVerts[i+1].y/3.5f)/256.0f, 0.0f, 1.0f);
         glVertex3f(qTree->pvVerts[i+1].x, qTree->pvVerts[i+1].y, qTree->pvVerts[i+1].z);
         
         glColor4f(0.0f, (qTree->pvVerts[i+2].y/3.5f)/256.0f, 0.0f, 1.0f);
         glVertex3f(qTree->pvVerts[i+2].x, qTree->pvVerts[i+2].y, qTree->pvVerts[i+2].z);
      }
      glEnd();

 //     glColor4f(1.0f, 0.0f, 0.0f, 1.0f);

 //     glPointSize(4.0f);

 //     glBegin(GL_POINTS);

 //        glVertex3f(qTree->vCenter.x, qTree->vCenter.y, qTree->vCenter.z);

//      glEnd();


   }
   else
   {
      //Draw each child node

      DrawTree(qTree->nodes[0]);
      DrawTree(qTree->nodes[1]);
      DrawTree(qTree->nodes[2]);
      DrawTree(qTree->nodes[3]);
   }
}