Planet
navi homePPSaboutscreenshotsdownloaddevelopmentforum

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

Last change on this file since 8599 was 8293, checked in by bensch, 19 years ago

orxonox/trunk: merged the osX-branche back here
merged with command:
svn merge https://svn.orxonox.net/orxonox/branches/osx . -r7763:HEAD

conflicts resolved, and everything is working as expected (or at least i hope so :) )

File size: 5.9 KB
Line 
1/*
2   orxonox - the future of 3D-vertical-scrollers
3
4   Copyright (C) 2004 orx
5
6   This program is free software; you can redistribute it and/or modify
7   it under the terms of the GNU General Public License as published by
8   the Free Software Foundation; either version 2, or (at your option)
9   any later version.
10
11### File Specific:
12   main-programmer: Patrick Boenzli
13   co-programmer: ...
14*/
15
16#define DEBUG_SPECIAL_MODULE DEBUG_MODULE_SPATIAL_SEPARATION
17
18#include "quadtree.h"
19
20#include "quadtree_node.h"
21#include "vector.h"
22
23#include "material.h"
24#include "debug.h"
25
26using namespace std;
27#define QUADTREE_MATERIAL_COUNT       4
28
29/**
30 *  standard constructor
31 */
32Quadtree::Quadtree (const modelInfo* pModelInfo, const int treeDepth)
33{
34  this->setClassID(CL_QUADTREE, "Quadtree");
35  this->pModelInfo = pModelInfo;
36  this->treeDepth = treeDepth;
37
38  /* initialize the materials for debug draw */
39  this->materials = new Material*[QUADTREE_MATERIAL_COUNT];
40  for(int i = 0; i < QUADTREE_MATERIAL_COUNT; ++i)
41  {
42    materials[i] = new Material();
43    materials[i]->setIllum(3);
44  }
45  materials[0]->setAmbient(0.0, 0.3, 0.0);
46  materials[1]->setAmbient(0.4, 0.0, 0.2);
47  materials[2]->setAmbient(1.0, 0.0, 0.0);
48  materials[3]->setAmbient(5.0, 3.0, 1.0);
49
50  /* build the tree */
51  this->rootNode = new QuadtreeNode(this->pModelInfo, this, this->treeDepth);
52
53  /* make an array with access to the leafs of the Quad-Tree */
54  this->nodes = new QuadtreeNode*[(int)pow(4, treeDepth)];
55  int index = 0; //new int; *index = 0; // !!changed by bensch!!
56  for(int i = 0; i < (int)pow(2, treeDepth); ++i)
57  {
58    this->rootNode->buildHashTable(this->nodes, &index);
59  }
60  /* sort and revert the hash table to fit the right position */
61  this->sortHashTable(this->nodes);
62  this->revertHashTable(this->nodes);
63
64  /* define some important and often used variables */
65  this->quadLength = this->nodes[0]->getDimension()->getAxis() * 2.0f;
66  Rectangle* r = this->rootNode->getDimension();
67  float xOff = r->getCenter().x - r->getAxis();
68  float yOff = r->getCenter().z - r->getAxis();
69  this->offset = new Vector();
70  this->offset->x = xOff;
71  this->offset->z = yOff;
72  this->maxIndex = (int)pow(2, this->treeDepth);
73}
74
75
76/**
77 *  standard deconstructor
78 */
79Quadtree::~Quadtree ()
80{
81  // delete what has to be deleted here
82  if (this->materials != NULL)
83  {
84    for (unsigned int i = 0; i < QUADTREE_MATERIAL_COUNT; i++)
85      delete this->materials[i];
86    delete[] this->materials;
87  }
88
89  delete this->offset;
90
91  delete this->rootNode;
92  delete [] this->nodes;
93}
94
95
96/**
97 *  this function rotates the array and mirrors it in the middle
98 * @param nodes: the nodes to translate
99
100  since the original matrix is counted from the right upper edge to the right lower one, we have to reorganize the elements
101  to be able to easily correlate the hashtable array indexes with the coorindates.
102 */
103void Quadtree::revertHashTable(QuadtreeNode** nodes)
104{
105  int                  len         = (int)pow(2, this->treeDepth);          //!< the length of a quadtree side
106  int                  iterator    = 0;                                     //!< iterator used for mapping
107  QuadtreeNode*        tmpNode     = NULL;                                  //!< temp saving place
108  int                  offset      = 0;                                     //!< offset used in the calc
109
110  for(int i = len - 1; i >= 0; --i)
111  {
112    for(int j = len - 1; j >= 0; --j)
113    {
114      offset = j * len + i;
115      /* only swap the elements in one direction */
116      if( offset > iterator)
117      {
118        tmpNode = nodes[offset];
119        nodes[offset] = nodes[iterator];
120        nodes[iterator] = tmpNode;
121      }
122      ++iterator;
123    }
124  }
125}
126
127
128/**
129 *  sorts the hash table using their positions
130 * @param nodes the nodes to use
131 */
132void Quadtree::sortHashTable(QuadtreeNode** nodes)
133{
134  int                  len         = (int)pow(2, this->treeDepth);          //!< the length of a quadtree side
135  float                a;                                                   //!< temp place for float a
136  float                b;                                                   //!< temp place for float b
137  QuadtreeNode*        tmpNode;                                             //!< tmp place for a QuadtreeNode
138
139  for( int i = 0; i < len; ++i)
140  {
141    for( int j = 0; j < len; ++j)
142    {
143      for( int k = j + 1; k < len; ++k)
144      {
145        a = this->nodes[i * len + j]->getDimension()->getCenter().z;
146        b = this->nodes[i * len + k]->getDimension()->getCenter().z;
147
148        if( b > a)
149        {
150          tmpNode = this->nodes[i * len + j];
151          this->nodes[i * len + j] = this->nodes[i * len + k];
152          this->nodes[i * len + k] = tmpNode;
153        }
154      }
155    }
156  }
157
158}
159
160
161/**
162 *  maps a position to a quadtree
163 * @param position the position so look for
164 * @return the quadtree
165
166  this function will return the quadtree that contains the position
167 */
168QuadtreeNode* Quadtree::getQuadtreeFromPosition(const Vector& position) const
169{
170  /* shift into model space */
171  Vector v = position - *this->offset;
172  /* map */
173  int i = (int)(v.x / quadLength);
174  int j = (int)(v.z / quadLength);
175
176  /* check if object is still inside the terrain - this check is not complete @todo check all 4 bounds */
177  if( i < this->maxIndex && j < this->maxIndex && i >= 0 && j >= 0)
178    return this->nodes[i + j * this->maxIndex];
179
180
181  PRINTF(4)("Object has left terrain\n");
182  return NULL;
183}
184
185
186/**
187 *  maps a position to a triangle
188 * @param position the position so look for
189 * @return the triangle
190
191  this function will return the quadtree that contains the position
192 */
193sTriangleExt* Quadtree::getTriangleFromPosition(const Vector& position) const
194{
195  QuadtreeNode* q = this->getQuadtreeFromPosition(position);
196
197  if( likely(q != NULL))
198    return q->getTriangle(position - *this->offset);
199  return NULL;
200}
201
202
203/**
204 *  draws the debug quadtree boxes around the model
205 */
206void Quadtree::drawTree() const
207{
208  //this->rootNode->drawTree();
209  for(int i = 0; i < (int)pow(4, this->treeDepth); ++i)
210  {
211    this->nodes[i]->draw();
212  }
213}
Note: See TracBrowser for help on using the repository browser.