Planet
navi homePPSaboutscreenshotsdownloaddevelopmentforum

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

Last change on this file since 5070 was 4968, checked in by patrick, 19 years ago

orxonox/trunk: some fixeds in the quadtree framework. No debug draw anymore

File size: 5.7 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
25
26using namespace std;
27
28
29/**
30 *  standard constructor
31 */
32Quadtree::Quadtree (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*[4];
40  for(int i = 0; i < 4; ++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 = new int; *index = 0;
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  Vector* offset = new Vector();
68  float xOff = r->getCenter()->x - r->getAxis();
69  float yOff = r->getCenter()->z - r->getAxis();
70  this->offset = new Vector();
71  this->offset->x = xOff;
72  this->offset->z = yOff;
73  this->maxIndex = (int)pow(2, this->treeDepth);
74}
75
76
77/**
78 *  standard deconstructor
79 */
80Quadtree::~Quadtree ()
81{
82  // delete what has to be deleted here
83  delete [] this->nodes;
84  delete this->rootNode;
85  delete offset;
86}
87
88
89/**
90 *  this function rotates the array and mirrors it in the middle
91 * @param nodes: the nodes to translate
92
93  since the original matrix is counted from the right upper edge to the right lower one, we have to reorganize the elements
94  to be able to easily correlate the hashtable array indexes with the coorindates.
95 */
96void Quadtree::revertHashTable(QuadtreeNode** nodes)
97{
98  int                  len         = (int)pow(2, this->treeDepth);          //!< the length of a quadtree side
99  int                  iterator    = 0;                                     //!< iterator used for mapping
100  QuadtreeNode*        tmpNode     = NULL;                                  //!< temp saving place
101  int                  offset      = 0;                                     //!< offset used in the calc
102
103  for(int i = len - 1; i >= 0; --i)
104  {
105    for(int j = len - 1; j >= 0; --j)
106    {
107      offset = j * len + i;
108      /* only swap the elements in one direction */
109      if( offset > iterator)
110      {
111        tmpNode = nodes[offset];
112        nodes[offset] = nodes[iterator];
113        nodes[iterator] = tmpNode;
114      }
115      ++iterator;
116    }
117  }
118}
119
120
121/**
122 *  sorts the hash table using their positions
123 * @param nodes the nodes to use
124 */
125void Quadtree::sortHashTable(QuadtreeNode** nodes)
126{
127  int                  len         = (int)pow(2, this->treeDepth);          //!< the length of a quadtree side
128  float                a;                                                   //!< temp place for float a
129  float                b;                                                   //!< temp place for float b
130  QuadtreeNode*        tmpNode;                                             //!< tmp place for a QuadtreeNode
131
132  for( int i = 0; i < len; ++i)
133  {
134    for( int j = 0; j < len; ++j)
135    {
136      for( int k = j + 1; k < len; ++k)
137      {
138        a = this->nodes[i * len + j]->getDimension()->getCenter()->z;
139        b = this->nodes[i * len + k]->getDimension()->getCenter()->z;
140
141        if( b > a)
142        {
143          tmpNode = this->nodes[i * len + j];
144          this->nodes[i * len + j] = this->nodes[i * len + k];
145          this->nodes[i * len + k] = tmpNode;
146        }
147      }
148    }
149  }
150
151}
152
153
154/**
155 *  maps a position to a quadtree
156 * @param position the position so look for
157 * @return the quadtree
158
159  this function will return the quadtree that contains the position
160 */
161QuadtreeNode* Quadtree::getQuadtreeFromPosition(const Vector& position) const
162{
163  /* shift into model space */
164  Vector v = position - *this->offset;
165  /* map */
166  int i = (int)(v.x / quadLength);
167  int j = (int)(v.z / quadLength);
168
169  /* check if object is still inside the terrain - this check is not complete @todo check all 4 bounds */
170  if( i < this->maxIndex && j < this->maxIndex && i >= 0 && j >= 0)
171    return this->nodes[i + j * this->maxIndex];
172
173
174  PRINTF(4)("Object has left terrain\n");
175  return NULL;
176}
177
178
179/**
180 *  maps a position to a triangle
181 * @param position the position so look for
182 * @return the triangle
183
184  this function will return the quadtree that contains the position
185 */
186sTriangleExt* Quadtree::getTriangleFromPosition(const Vector& position) const
187{
188  QuadtreeNode* q = this->getQuadtreeFromPosition(position);
189
190  if( likely(q != NULL))
191    return q->getTriangle(position - *this->offset);
192  return NULL;
193}
194
195
196/**
197 *  draws the debug quadtree boxes around the model
198 */
199void Quadtree::drawTree() const
200{
201  //this->rootNode->drawTree();
202  for(int i = 0; i < (int)pow(4, this->treeDepth); ++i)
203  {
204    this->nodes[i]->draw();
205  }
206}
Note: See TracBrowser for help on using the repository browser.