Changeset 4911 in orxonox.OLD for orxonox

Timestamp:

Jul 21, 2005, 12:09:36 AM (20 years ago)

Author:

patrick

Message:

orxonox/trunk: creating lookup table with a very fancy algorithm

Location:

orxonox/trunk/src/lib/graphics/spatial_separation

Files:

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

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

@@ -50 +50 @@
    /* make an array with access to the leafs of the Quad-Tree */
    this->nodes = new QuadtreeNode*[(int)pow(4, treeDepth)];
+   int* index = new int; *index = 0;
+   for(int i = 0; i < (int)pow(2, treeDepth); ++i)
+     this->rootNode->buildHashTable(this->nodes, index);
 }
 

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

@@ -101 +101 @@
 
   this->offset = 0.0f;
+  this->nodeIter = 0;
 
   this->parent = NULL;
@@ -108 +109 @@
   this->nodeD = NULL;
   this->nodes = new QuadtreeNode*[4];
+  for(int i = 0; i < 4; ++i)
+    this->nodes[i] = NULL;
 
   if( this->treeDepth < this->maxDepth)
@@ -127 +130 @@
   if( this->nodeD != NULL)
     delete this->nodeD;
+}
+
+
+
+void QuadtreeNode::buildHashTable(QuadtreeNode** nodeList, int* index)
+{
+  int loopLimit = (this->nodeIter < ((int)pow(4, maxDepth - treeDepth) / 2))?2:4;
+
+  printf("buildHashTable depth: %i, nodeIter : %i, limit: %i, @nodeIndex: %i\n", this->treeDepth, nodeIter, loopLimit, indexNode);
+  /* is it a leaf? */
+  if( this->treeDepth < this->maxDepth)
+  {
+    for(int i = (this->nodeIter < ((int)pow(4, maxDepth - treeDepth) / 2))?0:2; i < loopLimit; ++i)
+    {
+      this->nodes[i]->buildHashTable(nodeList, index);
+      ++this->nodeIter;
+    }
+  }
+  else
+  {
+    printf("leaf, index: %i\n", *index);
+    nodeList[(*index)++] = this;
+  }
 }
 

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

@@ -27 +27 @@
     virtual ~QuadtreeNode();
 
+    void buildHashTable(QuadtreeNode** nodeList, int* index);
+
     float getHeight(const Vector& position);
 
@@ -47 +49 @@
     QuadtreeNode*                   nodeD;              //!< reference to the node D
     QuadtreeNode**                  nodes;              //!< reference to the quadtree nodes
-
+    int                             nodeIter;           //!< temp helping variable for the hashing algorithm
 
   private: