source: orxonox.OLD/orxonox/trunk/src/lib/graphics/spatial_separation/quadtree.cc @ 4919

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

using namespace std;


/**
 *  standard constructor
   @todo this constructor is not jet implemented - do it
*/
Quadtree::Quadtree (modelInfo* pModelInfo, const int treeDepth)
{
   this->setClassID(CL_QUADTREE, "Quadtree");
   this->pModelInfo = pModelInfo;
   this->treeDepth = treeDepth;

   /* initialize the materials for debug draw */
   this->materials = new Material*[4];
   for(int i = 0; i < 4; ++i)
   {
     materials[i] = new Material();
     materials[i]->setIllum(3);
   }
   materials[0]->setAmbient(0.0, 0.3, 0.0);
   materials[1]->setAmbient(0.4, 0.0, 0.2);
   materials[2]->setAmbient(1.0, 0.0, 0.0);
   materials[3]->setAmbient(5.0, 3.0, 1.0);

   /* build the tree */
   this->rootNode = new QuadtreeNode(this->pModelInfo, this, this->treeDepth);

   /* make an array with access to the leafs of the Quad-Tree */
   this->nodes = new QuadtreeNode*[(int)pow(4, treeDepth)];
   int* index = new int; *index = 0;
   for(int i = 0; i < (int)pow(2, treeDepth); ++i)
   {
     printf("============================\n");
     this->rootNode->buildHashTable(this->nodes, index);
   }
   this->revertHashTable(this->nodes);
}


/**
 *  standard deconstructor

*/
Quadtree::~Quadtree ()
{
  // delete what has to be deleted here
  delete [] this->nodes;
  delete this->rootNode;
}


/**

  since the original matrix is counted from the right upper edge to the right lower one, we have to reorganize the elements
  to be able to easily correlate the hashtable array indexes with the coorindates.
 */
void Quadtree::revertHashTable(QuadtreeNode** nodes)
{
  int                  len         = (int)pow(2, this->treeDepth);          //!< the length of a quadtree side
  int                  iterator    = 0;                                     //!< iterator used for mapping
  QuadtreeNode*        tmpNode     = NULL;                                  //!< temp saving place
  int                  offset      = 0;                                     //!< offset used in the calc

  for(int i = len - 1; i >= 0; --i)
  {
    for(int j = len - 1; j >= 0; --j)
    {
      offset = j * len + i;
      /* only swap the elements in one direction */
      if( offset > iterator)
      {
        tmpNode = nodes[offset];
        nodes[offset] = nodes[iterator];
        nodes[iterator] = tmpNode;
      }
      ++iterator;
    }
  }
}


QuadtreeNode* Quadtree::getQuadtreeFromPosition(const Vector& position)
{
  Vector v = position;
  Rectangle* r = this->rootNode->getDimension();
  float len = this->nodes[0]->getDimension()->getAxis() * 2.0f;
  float xOff = r->getCenter()->x - r->getAxis();
  float yOff = r->getCenter()->z - r->getAxis();

  int i = (int)(( position.x - xOff) / len) + 1;
  int j = (int)(( position.z - yOff) / len) + 1;

  printf("the array coordinates are: %i, %i\n", i, j);
}


/**
 *  draws the debug quadtree boxes around the model
 */
void Quadtree::drawTree(int depth, int drawMode) const
{
  //this->rootNode->drawTree(depth, drawMode);
  for(int i = 0; i < (int)pow(4, this->treeDepth); ++i)
  {
    this->nodes[i]->drawTree(0, 0);
  }


}