Planet
navi homePPSaboutscreenshotsdownloaddevelopmentforum

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

Last change on this file since 5304 was 5233, checked in by patrick, 19 years ago

orxonox/trunk: filled some other memory leaks with safer code

File size: 17.6 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_node.h"
19
20#include "quadtree.h"
21#include "material.h"
22#include "abstract_model.h"
23#include "list.h"
24#include "vector.h"
25#include "debug.h"
26
27using namespace std;
28
29
30/**
31 *  standard constructor
32 */
33QuadtreeNode::QuadtreeNode (sTriangleExt** triangles, int numTriangles,
34                            const float* pVertices, int numVertices,
35                            Quadtree* quadtree, QuadtreeNode* parent,
36                            Rectangle* rect, int treeDepth, const int maxDepth, int index
37                           )
38{
39  /* save all important variables localy */
40  this->numTriangles = numTriangles;
41  this->pTriangles = triangles;
42  this->numVertices = numVertices;
43  this->pVertices = pVertices;
44
45  this->quadtree = quadtree;
46  this->parent = parent;
47  this->pDimension = rect;
48  this->treeDepth = treeDepth;
49  this->maxDepth = maxDepth;
50  this->indexNode = index;
51
52  /* debug output */
53  for( int i = 0; i < this->treeDepth; ++i)
54    PRINT(3)(" |");
55  PRINT(3)(" | +-| (Event) Building Node Nr. %i Depth: %i/%i, pointer: %p\n", this->indexNode, treeDepth, maxDepth, this);
56
57  for( int i = 0; i < this->treeDepth; ++i)
58    PRINT(3)(" |");
59  PRINT(3)(" | +-| (II) Rectangle Center (%5.2f, %5.2f), half axis length: %5.2f\n",
60  this->pDimension->getCenter().x, this->pDimension->getCenter().z, this->pDimension->getAxis());
61
62  this->init();
63}
64
65
66/**
67 *  standard constructor
68 */
69QuadtreeNode::QuadtreeNode(modelInfo* pModelInfo, Quadtree* quadtree, const int maxDepth)
70{
71  /* save all important variables localy */
72  this->pModelInfo = pModelInfo;
73  this->quadtree = quadtree;
74  this->maxDepth = maxDepth;
75  this->treeDepth = 0;
76  this->indexNode = 0;
77
78  /* create an array of triangle references */
79  this->pTriangles = new sTriangleExt*[this->pModelInfo->numTriangles];
80  this->numTriangles = this->pModelInfo->numTriangles;
81  this->pVertices = this->pModelInfo->pVertices;
82  this->numVertices = this->pModelInfo->numVertices;
83  for( int i = 0; i < this->pModelInfo->numTriangles; ++i)
84    this->pTriangles[i] = &this->pModelInfo->pTriangles[i];
85
86  /* debug output */
87  for( int i = 0; i < this->treeDepth; ++i)
88    PRINT(3)(" |");
89  PRINT(3)(" | +-| (Event) Building Node Nr. %i Depth: %i/%i, pointer: %p\n", this->indexNode, treeDepth, maxDepth, this);
90
91  /* set some important variables */
92  this->pDimension = this->getDimFromModel();
93
94  this->init();
95}
96
97
98/**
99 *  takes the rest of the initialisation process
100 */
101void QuadtreeNode::init()
102{
103  this->setClassID(CL_QUADTREE_NODE, "QuadtreeNode");
104
105  /* init the rest of the variables for both init types */
106  this->offset = 0.0f;
107  this->nodeIter = -1;
108  this->bDraw = false;
109
110  this->parent = NULL;
111  this->nodeA = NULL;
112  this->nodeB = NULL;
113  this->nodeC = NULL;
114  this->nodeD = NULL;
115  this->nodes = new QuadtreeNode*[4];
116  for(int i = 0; i < 4; ++i)
117    this->nodes[i] = NULL;
118
119  /* now separate the nodes */
120  if( this->treeDepth < this->maxDepth)
121    this->separateNode();
122}
123
124
125/**
126 *  standard deconstructor
127 */
128QuadtreeNode::~QuadtreeNode ()
129{
130  if( this->nodeA)
131    delete this->nodeA;
132  if( this->nodeB)
133    delete this->nodeB;
134  if( this->nodeC)
135    delete this->nodeC;
136  if( this->nodeD)
137    delete this->nodeD;
138
139  if( this->nodes)
140    delete [] this->nodes;
141
142  if( this->pTriangles)
143    delete [] this->pTriangles;
144
145  if( this->pDimension)
146    delete this->pDimension;
147}
148
149
150
151/**
152 *  this functions builds up a hash table containing all leafs of the Quadtree in a sorted array
153 * @param nodeList the nodelist array to add them
154 * @param index the current index in the array
155
156  The algorithm used for this purpose is home-brown. its not to fast but and the nodes are not always in the right
157  order. this is why there will be needed a quicksort later on.
158 */
159void QuadtreeNode::buildHashTable(QuadtreeNode** nodeList, int* index)
160{
161  if( this->nodeIter == -1)
162    this->nodeIter = *index;
163
164  /*              offset              #of elements in a row            #of rows in a quadtree          */
165  int threshold = this->nodeIter + (int)pow(2, this->maxDepth) * (int)pow(2, maxDepth - treeDepth - 1);
166  int loopLimit = (*index < threshold)?2:4;
167
168  /* is it a leaf? */
169  if( this->treeDepth < this->maxDepth)
170    for(int i = (*index < threshold)?0:2; i < loopLimit; ++i)
171      this->nodes[i]->buildHashTable(nodeList, index);
172  else
173    nodeList[(*index)++] = this;
174}
175
176
177
178/**
179 *  gives the signal to separate the model into a quadtree
180 * @param treeDepth the max depth, the steps to go if treeDept == 0 leaf reached
181
182 * @todo ATTENION: This function is currently not used and not implemented, but would be a nice addon
183 */
184void QuadtreeNode::separateNode(float minLength)
185{
186  /* dimension calculation & limit checking */
187  if( minLength <= this->pDimension->getAxis())
188    return;
189
190  /* node separation */
191//   this->separateNode();
192//   this->nodeA->separateNode(minLength);
193//   this->nodeB->separateNode(minLength);
194//   this->nodeC->separateNode(minLength);
195//   this->nodeD->separateNode(minLength);
196}
197
198
199/**
200 *  gives the signal to separate the model into a quadtree
201 * @param treeDepth the max depth, the steps to go if treeDept == 0 leaf reached
202 */
203void QuadtreeNode::separateNode()
204{
205  /* separate the four regions into the four lists */
206  tList<sTriangleExt*>*           listA = new tList<sTriangleExt*>();    //!< triangle list of nodeA
207  tList<sTriangleExt*>*           listB = new tList<sTriangleExt*>();    //!< triangle list of nodeB
208  tList<sTriangleExt*>*           listC = new tList<sTriangleExt*>();    //!< triangle list of nodeC
209  tList<sTriangleExt*>*           listD = new tList<sTriangleExt*>();    //!< triangle list of nodeD
210  const float*                    pVert;                                 //!< pointer to the vertices
211  Vector                          rectCenter;                            //!< vector to the center of the rect
212
213  rectCenter = this->pDimension->getCenter();
214  for( int i = 0; i < this->numTriangles; ++i)
215  {
216    for( int j = 0; j < 3; ++j)
217    {
218      pVert = &this->pVertices[this->pTriangles[i]->indexToVertices[j]];
219      if( pVert[0] > rectCenter.x + this->offset && pVert[2] > rectCenter.z + this->offset)
220        listA->add(&this->pTriangles[i]);
221      if( pVert[0] < rectCenter.x + this->offset && pVert[2] > rectCenter.z + this->offset)
222        listB->add(&this->pTriangles[i]);
223      if( pVert[0] < rectCenter.x + this->offset && pVert[2] < rectCenter.z + this->offset)
224        listC->add(&this->pTriangles[i]);
225      if( pVert[0] > rectCenter.x + this->offset && pVert[2] < rectCenter.z + this->offset)
226        listD->add(&this->pTriangles[i]);
227    }
228  }
229  for( int i = 0; i < treeDepth; ++i)
230    PRINT(3)(" |");
231  PRINT(3)(" | +-| (II) Quadtree Counts - separating: A: %i, B: %i, C: %i, D: %i\n", listA->getSize(), listB->getSize(), listC->getSize(), listD->getSize());
232
233
234  /* Separating into to the triangle arrays */
235  sTriangleExt**                 pTriA;                                 //!< Triangle array A
236  sTriangleExt**                 pTriB;                                 //!< Triangle array B
237  sTriangleExt**                 pTriC;                                 //!< Triangle array C
238  sTriangleExt**                 pTriD;                                 //!< Triangle array D
239  int                            lenA;                                  //!< length array A
240  int                            lenB;                                  //!< length array B
241  int                            lenC;                                  //!< length array C
242  int                            lenD;                                  //!< length array D
243  tIterator<sTriangleExt*>*      iterator;                              //!< iterator for the list iterations
244  sTriangleExt**                 tempTri;                               //!< temp save place for triangle pointer
245  int                            counter;                               //!< counter for the while loops
246
247  lenA = listA->getSize();
248  lenB = listB->getSize();
249  lenC = listC->getSize();
250  lenD = listD->getSize();
251
252  pTriA = new sTriangleExt*[lenA];
253  pTriB = new sTriangleExt*[lenB];
254  pTriC = new sTriangleExt*[lenC];
255  pTriD = new sTriangleExt*[lenD];
256
257  counter = 0;
258  iterator = listA->getIterator();
259  tempTri = iterator->firstElement();
260  while( tempTri)
261  {
262    pTriA[counter] = *tempTri;
263    tempTri = iterator->nextElement();
264    ++counter;
265  }
266  delete iterator;
267
268  counter = 0;
269  iterator = listB->getIterator();
270  tempTri = iterator->firstElement();
271  while( tempTri)
272  {
273    pTriB[counter] = *tempTri;
274    tempTri = iterator->nextElement();
275    ++counter;
276  }
277  delete iterator;
278
279  counter = 0;
280  iterator = listC->getIterator();
281  tempTri = iterator->firstElement();
282  while( tempTri)
283  {
284    pTriC[counter] = *tempTri;
285    tempTri = iterator->nextElement();
286    ++counter;
287  }
288  delete iterator;
289
290  counter = 0;
291  iterator = listD->getIterator();
292  tempTri = iterator->firstElement();
293  while( tempTri)
294  {
295    pTriD[counter] = *tempTri;
296    tempTri = iterator->nextElement();
297    ++counter;
298  }
299  delete iterator;
300
301  /* now do cleanup */
302  delete listA;
303  delete listB;
304  delete listC;
305  delete listD;
306
307
308  /* now create the rectangle dimensions */
309  Vector                     v;                                                             //!< temp saving place
310  Rectangle*                 rA;                                                            //!< new size of the node A
311  Rectangle*                 rB;                                                            //!< new size of the node B
312  Rectangle*                 rC;                                                            //!< new size of the node C
313  Rectangle*                 rD;                                                            //!< new size of the node D
314
315
316  v.x = this->pDimension->getCenter().x + this->pDimension->getAxis() / 2.0f;
317  v.y = 0.0;
318  v.z = this->pDimension->getCenter().z + this->pDimension->getAxis() / 2.0f;
319  rA = new Rectangle(v, this->pDimension->getAxis() / 2.0f);
320
321  v.z = this->pDimension->getCenter().z - this->pDimension->getAxis() / 2.0f;
322  rB = new Rectangle(v, this->pDimension->getAxis() / 2.0f);
323
324  v.x = this->pDimension->getCenter().x - this->pDimension->getAxis() / 2.0f;
325  rC = new Rectangle(v, this->pDimension->getAxis() / 2.0f);
326
327  v.z = this->pDimension->getCenter().z + this->pDimension->getAxis() / 2.0f;
328  rD = new Rectangle(v, this->pDimension->getAxis() / 2.0f);
329
330
331  /* now create the new nodes  */
332  this->nodeA = new QuadtreeNode(pTriA, lenA, this->pVertices, this->numVertices, this->quadtree, this, rA, this->treeDepth + 1, this->maxDepth, (this->treeDepth + 1) * 10 + 0);
333  this->nodeB = new QuadtreeNode(pTriB, lenB, this->pVertices, this->numVertices, this->quadtree, this, rB, this->treeDepth + 1, this->maxDepth, (this->treeDepth + 1) * 10 + 1);
334  this->nodeC = new QuadtreeNode(pTriC, lenC, this->pVertices, this->numVertices, this->quadtree, this, rC, this->treeDepth + 1, this->maxDepth, (this->treeDepth + 1) * 10 + 2);
335  this->nodeD = new QuadtreeNode(pTriD, lenD, this->pVertices, this->numVertices, this->quadtree, this, rD, this->treeDepth + 1, this->maxDepth, (this->treeDepth + 1) * 10 + 3);
336
337  /* map the array references, this is for faster and automatical interfacing  \todo: use only array */
338  this->nodes[0] = this->nodeA;
339  this->nodes[1] = this->nodeB;
340  this->nodes[2] = this->nodeC;
341  this->nodes[3] = this->nodeD;
342}
343
344
345/**
346 *  gets the maximal dimension of a model
347 * @return the dimension of the AbstractModel as a Rectangle
348
349   The rectangle is x-z axis aligned. ATTENTION: if there are any vertices in the model, that exceed the
350   size of 999999.0, there probably will be some errors in the dimensions calculations. Write an email to
351   patrick@orxonox.ethz.ch if you will ever encounter a model bigger than 999999.0 units, I will realy be
352   happy to see orxonox used to extensivly :)
353 */
354Rectangle* QuadtreeNode::getDimFromModel()
355{
356  float            maxX, maxY;                       //!< the maximal coordinates axis
357  float            minX, minY;                       //!< minimal axis coorindates
358  const float*     pVertices;                        //!< pointer to the current vertices
359
360  maxX = -999999; maxY = -999999;
361  minX =  999999; minY =  999999;
362  /* get maximal/minimal x/y */
363  for( int i = 0; i < this->numTriangles; ++i)
364  {
365    for( int j = 0; j < 3; ++j)
366    {
367
368      pVertices = &this->pVertices[this->pTriangles[i]->indexToVertices[j]];
369      if( pVertices[0] > maxX)
370        maxX = pVertices[0];
371      if( pVertices[2] > maxY)
372        maxY = pVertices[2];
373
374      if( pVertices[0] < minX)
375        minX = pVertices[0];
376      if( pVertices[2] < minY)
377        minY = pVertices[2];
378    }
379  }
380
381  Rectangle* rect = new Rectangle();
382  rect->setCenter((maxX + minX) / 2.0f, 0.0f, (maxY + minY) / 2.0f); /* this is little strange, since y is in opengl the up vector */
383  rect->setAxis(fmax(((fabs(maxX) + fabs(minX)) / 2.0f), ((fabs(maxY) + fabs(minY)) / 2.0f)));
384
385  for( int i = 0; i < this->treeDepth; ++i)
386    PRINT(3)(" |");
387  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());
388  return rect;
389}
390
391
392 /**
393 * checks if a point is included in this quadtree
394 * @param v the vector to be checked
395 * @returns true if the vector is included
396  */
397bool QuadtreeNode::includesPoint(const Vector& v) const
398{
399  Vector center = this->pDimension->getCenter();
400  float ax = this->pDimension->getAxis();
401
402  if( v.x > center.x - ax && v.x < center.x + ax &&
403      v.z > center.z - ax && v.z < center.z + ax )
404    return true;
405  return false;
406}
407
408
409
410float QuadtreeNode::getHeight(const Vector& position) const
411{
412  Vector a, b, c;
413  sTriangleExt* tri;
414
415  for( int i = 0; i < this->numTriangles; ++i)
416  {
417    a = *(sVec3D*)&this->pVertices[this->pTriangles[i]->indexToVertices[0]];
418    b = *(sVec3D*)&this->pVertices[this->pTriangles[i]->indexToVertices[1]];
419    c = *(sVec3D*)&this->pVertices[this->pTriangles[i]->indexToVertices[2]];
420
421    if( unlikely(this->pointInTriangle(position, a, b, c)))
422    {
423      tri = this->pTriangles[i];
424      break;
425    }
426  }
427
428  /* calculate height out of the data collected above */
429
430}
431
432
433/**
434 *  get triangles that includes the position
435 * @param position the position that is going to be checked
436 * @returns the triangle in which the position is included, NULL if there is no such triangle
437
438 There is some random behaviour if there are more than one triangle at the same y
439 coordinate. At the moment the function just takes the first triangle, that included the
440 vector
441 */
442sTriangleExt* QuadtreeNode::getTriangle(const Vector& position) const
443{
444  Vector a, b, c;
445  PRINTF(0)("Get Triangle, %i\n", this->numTriangles);
446
447  for( int i = 0; i < numTriangles; ++i)
448    {
449
450      a = *(sVec3D*)&this->pVertices[this->pTriangles[i]->indexToVertices[0]];
451      b = *(sVec3D*)&this->pVertices[this->pTriangles[i]->indexToVertices[1]];
452      c = *(sVec3D*)&this->pVertices[this->pTriangles[i]->indexToVertices[2]];
453
454      if( unlikely(this->pointInTriangle(position, a, b, c)))
455        return this->pTriangles[i];
456
457    }
458  return NULL;
459}
460
461
462/**
463 *  checks if the point is in the triangle
464 * @param point to be checked
465 * @param rectangle edge a
466 * @param rectangle edge b
467 * @param rectangle edge c
468 * @returns true if the point is inside
469 */
470bool QuadtreeNode::pointInTriangle(const Vector&p, const Vector& a, const Vector& b, const Vector& c) const
471{
472
473  PRINTF(0)("p: (%f, %f, %f)\n", p.x, p.y, p.z);
474  PRINTF(0)("a: (%f, %f, %f)\n", a.x, a.y, a.z);
475  PRINTF(0)("b: (%f, %f, %f)\n", b.x, b.y, b.z);
476  PRINTF(0)("c: (%f, %f, %f)\n", c.x, c.y, c.z);
477
478  if( this->sameSide(p, a, b, c) && this->sameSide(p, b, a, c) && sameSide(p, c, a, b))
479    return true;
480  return false;
481}
482
483
484/**
485 *  checks if two points are on the same side
486 * @param point one to be checked
487 * @param point two to be checked
488 * @param begining point of the line
489 * @param end of the line
490 */
491bool QuadtreeNode::sameSide(const Vector& p1, const Vector&p2, const Vector& a, const Vector& b) const
492{
493  Vector cp1 = (b - a).cross(p1 - a);
494  Vector cp2 = (b - a).cross(p2 - a);
495
496  if( unlikely(cp1.dot(cp2) >= 0)) return true;
497  return false;
498}
499
500
501/**
502 *  draws all the debug quadtree squares
503 */
504void QuadtreeNode::drawTree() const
505{
506  if( this->treeDepth == this->maxDepth)
507  {
508    Vector t1 = this->pDimension->getCenter();
509    float ax = this->pDimension->getAxis();
510    float h = 50.0f;
511
512    this->quadtree->getMaterial(this->indexNode)->select();
513    glBegin(GL_QUADS);
514    glVertex3f(t1.x + ax, h - this->treeDepth * 10.0f, t1.z + ax);
515    glVertex3f(t1.x - ax, h - this->treeDepth * 10.0f, t1.z + ax);
516    glVertex3f(t1.x - ax, h - this->treeDepth * 10.0f, t1.z - ax);
517    glVertex3f(t1.x + ax, h - this->treeDepth * 10.0f, t1.z - ax);
518    glEnd();
519  }
520
521
522  if( this->nodeA != NULL)
523    this->nodeA->drawTree();
524  if( this->nodeB != NULL)
525    this->nodeB->drawTree();
526  if( this->nodeC != NULL)
527    this->nodeC->drawTree();
528  if( this->nodeD != NULL)
529    this->nodeD->drawTree();
530}
531
532
533/**
534 *  draws only this quadtree square
535 */
536void QuadtreeNode::draw() const
537{
538  if( likely(!this->bDraw))
539    return;
540
541  Vector t1 = this->pDimension->getCenter();
542  float ax = this->pDimension->getAxis();
543  float h = 70.0f;
544
545  glBegin(GL_QUADS);
546  this->quadtree->getMaterial(this->indexNode)->select();
547
548  glVertex3f(t1.x + ax, h, t1.z + ax);
549  glVertex3f(t1.x - ax, h, t1.z + ax);
550  glVertex3f(t1.x - ax, h, t1.z - ax);
551  glVertex3f(t1.x + ax, h, t1.z - ax);
552
553  glEnd();
554}
Note: See TracBrowser for help on using the repository browser.