Changeset 4914 in orxonox.OLD for orxonox/trunk

Timestamp:

Jul 21, 2005, 11:17:54 AM (19 years ago)

Author:

patrick

Message:

orxonox/trunk: the hashing function now works perfect

Location:

orxonox/trunk/src/lib/graphics/spatial_separation

Files:

• quadtree.cc (modified) (2 diffs)
• quadtree_node.cc (modified) (2 diffs)
• spatial_separation.cc (modified) (1 diff)

orxonox/trunk/src/lib/graphics/spatial_separation/quadtree.cc

@@ -52 +52 @@
    int* index = new int; *index = 0;
    for(int i = 0; i < (int)pow(2, treeDepth); ++i)
+   {
+     printf("============================\n");
      this->rootNode->buildHashTable(this->nodes, index);
+   }
 }
 
@@ -74 +77 @@
 {
   //this->rootNode->drawTree(depth, drawMode);
-  for(int i = 0; i < 4; ++i)
+  for(int i = 0; i < (int)pow(4, this->treeDepth); ++i)
   {
     this->nodes[i]->drawTree(0, 0);

orxonox/trunk/src/lib/graphics/spatial_separation/quadtree_node.cc

@@ -101 +101 @@
 
   this->offset = 0.0f;
-  this->nodeIter = 0;
+  this->nodeIter = -1;
 
   this->parent = NULL;
@@ -136 +136 @@
 void QuadtreeNode::buildHashTable(QuadtreeNode** nodeList, int* index)
 {
-  int elCount = (int)pow(4, maxDepth - treeDepth) / 2;
-  int loopLimit = (this->nodeIter < elCount)?2:4;
-
-  for( int i = 0; i < this->treeDepth; ++i)
-    printf(" ");
-  printf("entering %i: hit counts: %i/%i\n", treeDepth, nodeIter, elCount);
+  if( this->nodeIter == -1)
+    this->nodeIter = *index;
+
+  /*              offset              #of elements in a row            #of rows in a quadtree          */
+  int threshold = this->nodeIter + (int)pow(2, this->maxDepth) * (int)pow(2, maxDepth - treeDepth - 1);
+  int loopLimit = (*index < threshold)?2:4;
 
   /* is it a leaf? */
   if( this->treeDepth < this->maxDepth)
-  {
-    for(int i = (this->nodeIter < elCount)?0:2; i < loopLimit; ++i)
-    {
-      for( int j = 0; j < this->treeDepth; ++j)
-        printf(" ");
-      printf("-> %i @ depth: %i, %i/%i \n", i, this->treeDepth, nodeIter, elCount);
-
+    for(int i = (*index < threshold)?0:2; i < loopLimit; ++i)
       this->nodes[i]->buildHashTable(nodeList, index);
-      ++this->nodeIter;
-    }
-  }
   else
-  {
-    for( int j = 0; j < this->treeDepth; ++j)
-      printf(" ");
-    printf("        leaf, index: %i, pointer: %p\n", *index, this);
     nodeList[(*index)++] = this;
-  }
 }
 

orxonox/trunk/src/lib/graphics/spatial_separation/spatial_separation.cc

@@ -99 +99 @@
 Quadtree* SpatialSeparation::createQuadtree(AbstractModel* model)
 {
-  this->quadtree = new Quadtree(model->getModelInfo(), 1);
+  this->quadtree = new Quadtree(model->getModelInfo(), 4);
 
   return this->quadtree;