Planet
navi homePPSaboutscreenshotsdownloaddevelopmentforum

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

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

orxonox/trunk: merged the NewModel branche back to the trunk.
merged with command
svn merge branches/newModel/ trunk/ -r 6016:HEAD
no conflicts

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