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

/*
   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 "abstract_model.h"
#include "list.h"
#include "vector.h"

using namespace std;


/**
 *  standard constructor
*/
QuadtreeNode::QuadtreeNode (sTriangleExt** triangles, int numTriangles,
                            const float* pVertices, int numVertices,
                            Quadtree* quadtree, QuadtreeNode* parent)
{
  this->pTriangles = triangles;
  this->numTriangles = numTriangles;
  this->pVertices = pVertices;
  this->numVertices = numVertices;
  this->quadtree = quadtree;
  this->treeDepth = 0;
  this->parent = parent;

  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;
  this->numVertices = this->pModelInfo->numVertices;
  for( int i = 0; i < this->pModelInfo->numTriangles; ++i)
    this->pTriangles[i] = &this->pModelInfo->pTriangles[i];
  this->treeDepth = 0;

  this->init();
}


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

  this->offset = 0.0f;
  this->parent = NULL;
  this->nodeA = NULL;
  this->nodeB = NULL;
  this->nodeC = NULL;
  this->nodeD = NULL;
}


/**
 *  standard deconstructor
 */
QuadtreeNode::~QuadtreeNode ()
{
  if( this->nodeA != NULL)
    delete this->nodeA;
  if( this->nodeB != NULL)
    delete this->nodeB;
  if( this->nodeC != NULL)
    delete this->nodeC;
  if( this->nodeD != NULL)
    delete this->nodeD;
}


/**
 *  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, const int maxDepth)
{
  this->treeDepth = treeDepth;
  /* debug output */
  for( int i = 0; i < treeDepth; ++i)
    PRINT(3)(" |");
  PRINT(3)(" | +-| (Event) Separating Node Depth: %i/%i\n", treeDepth, maxDepth);

  /* dimension calculation & limit checking */
  this->pDimension = this->getDimension();
  if( treeDepth >= maxDepth)
    return;

  /* node separation */
  this->separateNode();
  this->nodeA->separateNode(treeDepth + 1, maxDepth);
  this->nodeB->separateNode(treeDepth + 1, maxDepth);
  this->nodeC->separateNode(treeDepth + 1, maxDepth);
  this->nodeD->separateNode(treeDepth + 1, maxDepth);
}


/**
 *  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)
{
  /* dimension calculation & limit checking */
  this->pDimension = this->getDimension();
  if( minLength <= this->pDimension->getAxis())
    return;

  /* node separation */
  this->separateNode();
  this->nodeA->separateNode(minLength);
  this->nodeB->separateNode(minLength);
  this->nodeC->separateNode(minLength);
  this->nodeD->separateNode(minLength);
}


/**
 *  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()
{
  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]);
        }
    }
    for( int i = 0; i < treeDepth; ++i)
      PRINT(3)(" |");
    PRINT(3)(" | +-| (II) Quadtree Counts: 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
  int                            lenA;                                  //!< length array A
  int                            lenB;                                  //!< length array B
  int                            lenC;                                  //!< length array C
  int                            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;
    }

  /* now do cleanup */
  delete listA;
  delete listB;
  delete listC;
  delete listD;
  delete iterator;

  /* now propagate */
  this->nodeA = new QuadtreeNode(pTriA, lenA, this->pVertices, this->numVertices, this->quadtree, this);
  this->nodeB = new QuadtreeNode(pTriB, lenB, this->pVertices, this->numVertices, this->quadtree, this);
  this->nodeC = new QuadtreeNode(pTriC, lenC, this->pVertices, this->numVertices, this->quadtree, this);
  this->nodeD = new QuadtreeNode(pTriD, lenD, this->pVertices, this->numVertices, this->quadtree, this);
}



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

  Vector t1 = *this->pDimension->getCenter();
  float ax = this->pDimension->getAxis();
  float h = 50.0f;

  glBegin(GL_QUADS);
  glVertex3f(t1.x + ax, h - depth * 10.0f, t1.z + ax);
  glVertex3f(t1.x - ax, h - depth * 10.0f, t1.z + ax);
  glVertex3f(t1.x - ax, h - depth * 10.0f, t1.z - ax);
  glVertex3f(t1.x + ax, h - depth * 10.0f, t1.z - ax);
  glEnd();

  if( this->nodeA != NULL)
    this->nodeA->drawTree(depth - 1, drawMode);
  if( this->nodeB != NULL)
    this->nodeB->drawTree(depth - 1, drawMode);
  if( this->nodeC != NULL)
    this->nodeC->drawTree(depth - 1, drawMode);
  if( this->nodeD != NULL)
    this->nodeD->drawTree(depth - 1, drawMode);
}


/**
  \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)));

  for( int i = 0; i < this->treeDepth; ++i)
    PRINT(3)(" |");
  PRINT(3)(" | +-| (II) Rectangle Dimension  (%5.2f, %5.2f) to (%5.2f, %5.2f), Center (%5.2f, %5.2f)\n", minX, minY, maxX, maxY, rect->getCenter()->x, rect->getCenter()->z, rect->getAxis());
  return rect;
}


/**
   \brief gets the maximal dimension of a model
   \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()
{
  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 < this->numTriangles; ++i)
  {
    for( int j = 0; j < 3; ++j)
    {

      pVertices = &this->pVertices[this->pTriangles[i]->indexToVertices[j]];
      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)));

  for( int i = 0; i < this->treeDepth; ++i)
    PRINT(3)(" |");
  PRINT(3)(" | +-| (II) Rectangle Dimension  (%5.2f, %5.2f) to (%5.2f, %5.2f), Center (%5.2f, %5.2f)\n", minX, minY, maxX, maxY, rect->getCenter()->x, rect->getCenter()->z, rect->getAxis());
  return rect;
}