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

/*
   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->sortHashTable(this->nodes);
   this->revertHashTable(this->nodes);

   for(int i = 0; i < (int)pow(4, treeDepth); ++i)
   {
     printf("node %i, %f, %f \n", i, this->nodes[i]->getDimension()->getCenter()->x, this->nodes[i]->getDimension()->getCenter()->z);
   }
}


/**
 *  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;
    }
  }
}


void Quadtree::sortHashTable(QuadtreeNode** nodes)
{
  int                  len         = (int)pow(2, this->treeDepth);          //!< the length of a quadtree side
  float a,b;
  QuadtreeNode* tmpNode;

  for(int i = 0; i < len; ++i)
  {
    for(int j = 0; j < len; ++j)
    {
      for(int k = j + 1; k < len; ++k)
      {
        a = this->nodes[i * len + j]->getDimension()->getCenter()->z;
        b = this->nodes[i * len + k]->getDimension()->getCenter()->z;

        if( b > a)
        {
          tmpNode = this->nodes[i * len + j];
          this->nodes[i * len + j] = this->nodes[i * len + k];
          this->nodes[i * len + k] = tmpNode;
        }
      }

    }

  }
}



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

  Vector edge;
  float xOff = r->getCenter()->x - r->getAxis();
  float yOff = r->getCenter()->z - r->getAxis();
  edge.x = xOff, edge.z = yOff;

  /* shift into model space */
  v = position - edge;
  /* map */
  int i = (int)(v.x / len);
  int j = (int)(v.z / len);

  int max = (int)pow(2, this->treeDepth);

  if( i < max && j < max)
  {
    printf("-----------\nthe array coordinates are: %i, %i\n", i, j);
    printf("position: %f,%f, center %f, %f\n", position.x, position.z, this->nodes[i + j * max]->getDimension()->getCenter()->x, this->nodes[i + j * max]->getDimension()->getCenter()->z);

    //this->nodes[i + j * max]->draw();
    this->nodes[i + j * max]->includesPoint(position);
  }
  else
    printf("object has left terrain\n");
}


/**
 *  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]->draw();
  }


}