source: orxonox.OLD/orxonox/trunk/src/lib/graphics/spatial_separation/quadtree_node.cc @ 4855

/*
   orxonox - the future of 3D-vertical-scrollers

   Copyright (C) 2004 orx

   This program is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; either version 2, or (at your option)
   any later version.

   ### File Specific:
   main-programmer: Patrick Boenzli
   co-programmer: ...
*/

#define DEBUG_SPECIAL_MODULE DEBUG_MODULE_SPATIAL_SEPARATION

#include "quadtree_node.h"
#include "list.h"
#include "vector.h"

using namespace std;


/**
 *  standard constructor
*/
QuadtreeNode::QuadtreeNode (sTriangleExt* triangles, int numTriangles, Quadtree* quadtree)
{
  this->init();
}


/**
 *  standard constructor
 */
QuadtreeNode::QuadtreeNode(modelInfo* pModelInfo)
{
  this->pModelInfo = pModelInfo;
  
  /* create an array of triangle references */
  this->pTriangles = new sTriangleExt*[this->pModelInfo->numTriangles];
  this->numTriangles = this->pModelInfo->numTriangles;
  this->pVertices = this->pModelInfo->pVertices;
  for( int i = 0; i < this->pModelInfo->numTriangles; ++i)
    this->pTriangles[i] = &this->pModelInfo->pTriangles[i];

  this->init();
}


/**
 * takes the rest of the initialisation process
 */
void QuadtreeNode::init()
{
  this->setClassID(CL_QUADTREE_NODE, "QuadtreeNode");

  this->offset = 0.0f;
}

 
/**
 *  standard deconstructor
 */
QuadtreeNode::~QuadtreeNode ()
{
}


/**
 *  gives the signal to separate the model into a quadtree
 * @param treeDepth the max depth, the steps to go if treeDept == 0 leaf reached
 */
void QuadtreeNode::separateNode(int treeDepth)
{
  this->separateNode();
}


/**
 *  gives the signal to separate the model into a quadtree
 * @param treeDepth the max depth, the steps to go if treeDept == 0 leaf reached
*/
void QuadtreeNode::separateNode(float minLength)
{
  this->separateNode();
}


/**
 *  gives the signal to separate the model into a quadtree
 * @param treeDepth the max depth, the steps to go if treeDept == 0 leaf reached
*/
void QuadtreeNode::separateNode()
{
  PRINTF(0)("got command to separate node\n");

  this->pDimension = this->getDimension(this->pModelInfo);

  tList<sTriangleExt*>*           listA = new tList<sTriangleExt*>();    //!< triangle list of nodeA
  tList<sTriangleExt*>*           listB = new tList<sTriangleExt*>();    //!< triangle list of nodeB
  tList<sTriangleExt*>*           listC = new tList<sTriangleExt*>();    //!< triangle list of nodeC
  tList<sTriangleExt*>*           listD = new tList<sTriangleExt*>();    //!< triangle list of nodeD
  const float*                    pVert;                                 //!< pointer to the vertices
  const Vector*                   rectCenter;                            //!< vector to the center of the rect

  rectCenter = this->pDimension->getCenter();
  for( int i = 0; i < this->numTriangles; ++i)
    {
      for( int j = 0; j < 3; ++j)
        {
          pVert = &this->pVertices[this->pTriangles[i]->indexToVertices[j]];
          if( pVert[0] > rectCenter->x + this->offset && pVert[2] > rectCenter->z + this->offset)
            listA->add(&this->pTriangles[i]);
          if( pVert[0] > rectCenter->x + this->offset && pVert[2]< rectCenter->z + this->offset) 
            listB->add(&this->pTriangles[i]);
          if( pVert[0] < rectCenter->x + this->offset && pVert[2] > rectCenter->z + this->offset)
            listC->add(&this->pTriangles[i]);
          if( pVert[0] < rectCenter->x + this->offset && pVert[2] < rectCenter->z + this->offset)
            listD->add(&this->pTriangles[i]);
        }
    }
  printf("Temp. list Num. o El: A: %i, B: %i, C: %i, D: %i\n", listA->getSize(), listB->getSize(), listC->getSize(), listD->getSize());

  
  /* Separating into to the triangle lists  */
  sTriangleExt**                 pTriA;                                 //!< Triangle array A
  sTriangleExt**                 pTriB;                                 //!< Triangle array B
  sTriangleExt**                 pTriC;                                 //!< Triangle array C
  sTriangleExt**                 pTriD;                                 //!< Triangle array D
  float                          lenA;                                  //!< length array A
  float                          lenB;                                  //!< length array B
  float                          lenC;                                  //!< length array C
  float                          lenD;                                  //!< length array D
  tIterator<sTriangleExt*>*      iterator;                              //!< iterator for the list iterations
  sTriangleExt**                 tempTri;                               //!< temp save place for triangle pointer
  int                            counter;                               //!< counter for the while loops

  lenA = listA->getSize();
  lenB = listB->getSize();
  lenC = listC->getSize();
  lenD = listD->getSize();
  
  pTriA = new sTriangleExt*[listA->getSize()];
  pTriB = new sTriangleExt*[listB->getSize()];
  pTriC = new sTriangleExt*[listC->getSize()];  
  pTriD = new sTriangleExt*[listD->getSize()];


  counter = 0;
  iterator = listA->getIterator();
  tempTri = iterator->nextElement();
  while( tempTri)
    {
      pTriA[counter] = *tempTri;
      tempTri = iterator->nextElement();
      ++counter;
    }

  counter = 0;
  iterator = listB->getIterator();
  tempTri = iterator->nextElement();
  while( tempTri)
    {
      pTriB[counter] = *tempTri;
      tempTri = iterator->nextElement();
      ++counter;
    }
  
  counter = 0;
  iterator = listC->getIterator();
  tempTri = iterator->nextElement();
  while( tempTri)
    {
      pTriC[counter] = *tempTri;
      tempTri = iterator->nextElement();
      ++counter;
    }

  counter = 0;
  iterator = listD->getIterator();
  tempTri = iterator->nextElement();
  while( tempTri)
    {
      pTriD[counter] = *tempTri;
      tempTri = iterator->nextElement();
      ++counter;
    }

  PRINTF(0)("separation complete\n");
}



/**
 *  draws the debug quadtree boxes around the model
 */
void QuadtreeNode::drawTree(int depth, int drawMode) const
{}


/**
  \brief gets the maximal dimension of a model
 * @param playerModel the model that this measurement is based on
    \return the dimension of the AbstractModel as a Rectangle

    The rectangle is x-z axis aligned. ATTENTION: if there are any vertices in the model, that exceed the
    size of 999999.0, there probably will be some errors in the dimensions calculations. Write an email to
    patrick@orxonox.ethz.ch if you will ever encounter a model bigger than 999999.0 units, I will realy be
    happy to see orxonox used to extensivly :)
 */
Rectangle* QuadtreeNode::getDimension(modelInfo* pModelInfo)
{
  float            maxX, maxY;                       //!< the maximal coordinates axis
  float            minX, minY;                       //!< minimal axis coorindates
  const float*     pVertices;                        //!< pointer to the current vertices

  maxX = -999999; maxY = -999999;
  minX =  999999; minY =  999999;
  /* get maximal/minimal x/y */
  for( int i = 0; i < pModelInfo->numVertices; ++i)
  {
    pVertices = &pModelInfo->pVertices[i * 3];
    if( pVertices[0] > maxX)
      maxX = pVertices[0];
    if( pVertices[2] > maxY)
      maxY = pVertices[2];

    if( pVertices[0] < minX)
      minX = pVertices[0];
    if( pVertices[2] < minY)
      minY = pVertices[2];
  }

  Rectangle* rect = new Rectangle();
  rect->setCenter((maxX + minX) / 2.0f, 0.0f, (maxY + minY) / 2.0f); /* this is little strange, since y is in opengl the up vector */
  rect->setAxis(fmax(((fabs(maxX) + fabs(minX)) / 2.0f), ((fabs(maxY) + fabs(minY)) / 2.0f)));

  PRINTF(0)("Dimension Informationation: X: min/max %f/%f Y: min/max %f/%f\n", minX, maxX, minY, maxY);
  PRINTF(0)("Center: %f, %f, %f   Axis: %f\n", rect->getCenter()->x, rect->getCenter()->y, rect->getCenter()->z, rect->getAxis());
  return rect;
}