Text archives Help

---

Author: bigler
Date: Wed Mar 22 17:18:12 2006
New Revision: 991

Modified:
   trunk/Model/Groups/KDTreeLoaderIW.cc
Log:

Some more progress to parsing out Ingo's bsp data.  It could work
pretty soon here.


Modified: trunk/Model/Groups/KDTreeLoaderIW.cc
==============================================================================
--- trunk/Model/Groups/KDTreeLoaderIW.cc        (original)
+++ trunk/Model/Groups/KDTreeLoaderIW.cc        Wed Mar 22 17:18:12 2006
@@ -28,10 +28,13 @@
 
 #include <Model/Groups/KDTree.h>
 #include <Model/Groups/KDTreeLoaderIW.h>
+
+#include <stack>
 #include <stdio.h>
 
 using namespace Manta;
 using namespace Kdtree;
+using namespace std;
 
 /* This is the text that Ingo gave me on the file format
 
@@ -73,8 +76,7 @@
 '"N %c=%f,d=%i",&uchar_axis_dim,&float_axis_pos, &int_depth", and will
 by its two subtrees.
 
-the axis_dim is 'x', 'y', or 'z', the depth can be ignored
-(debugging purposes only).
+the axis_dim is 'x', 'y', or 'z', the depth can be ignored.
 
 Should be pretty easy to parse, I hope....
 
@@ -82,9 +84,63 @@
 
 Ingo
 
+
+N x=%g,d=%d
+  N
+    L 0
+    N
+      L 1
+      L 0
+  N
+    N
+      L 1
+      L 1
+    L 0
 */
 
 
+struct IWNode {
+  IWNode()
+    : left(0), right(0), parent(0),
+      split(0), flags(0),
+      num_tris(0), tri_ids(0),
+      index(0)
+  {}
+  IWNode(IWNode* parent)
+    : left(0), right(0), parent(parent),
+      split(0), flags(0),
+      num_tris(0), tri_ids(0),
+      index(0)
+  {}
+  ~IWNode() {
+    if (left) delete left;
+    if (right) delete right;
+    if (tri_ids) delete[] tri_ids;
+  }
+
+  void setRight(IWNode* node) {
+    right = node;
+    flags |= KDNODE_RIGHT_CHILD_MASK;
+  }
+  void setLeft(IWNode* node) {
+    left = node;
+    flags |= KDNODE_LEFT_CHILD_MASK;
+  }
+  bool isNode() const {
+    return flags & KDNODE_INTERNAL_MASK;
+  }
+  bool isLeaf() const {
+    return (flags & KDNODE_INTERNAL_MASK) == 0;
+  }
+  
+  IWNode *left, *right, *parent;
+  float split;
+  int flags;
+  unsigned int num_tris;
+  int* tri_ids;
+  unsigned index;
+};
+
 // Load the specified file (and associated kdtree files) using the
 // given number of processors.  The geometry should be found in
 // geom_filename and the bsp data should be found in bsp_filename.
@@ -202,8 +258,225 @@
   free(vtxnormals);
   fclose(geomf);
 
+
+  ///////////////////////////////////////////////////////
   // Load in the BSP stuff
 
+  // First pass.
+  // 
+  // Count the number of triangle indecies and nodes needed.
+  unsigned int num_tri_indicies = 0;
+  unsigned int num_nodes = 0;
+  // Buffer for line.  This will be allocated by getline and
+  // reallocated as needed.  We will need to free it later, though.
+  char* bline = NULL;
+  size_t bline_len = 0;
+
+  IWNode* head = 0;
+  IWNode* top = head;
+
+  while((getline(&bline, &bline_len, bspf)) != -1) {
+    // Check the first token
+    char token;
+    sscanf(bline, "% c", &token);
+    if (token == 'N') {
+      num_nodes ++;
+
+      IWNode* node = new IWNode(top);
+      // Is this the first node?
+      if (top) {
+        if (top->left) {
+          top->setRight(node);
+        } else {
+          top->setLeft(node);
+        }
+      } else {
+        // Set the head to the first node
+        head = node;
+      }
+      // Decend
+      top = node;
+
+      char axis_c;
+      sscanf(bline, "% c=%f,d=%*", &axis_c, &(node->split));
+      switch (axis_c) {
+      case 'x': node->flags |= 0; break;
+      case 'y': node->flags |= 1; break;
+      case 'z': node->flags |= 2; break;
+      }
+
+    } else if (token == 'L') {
+      IWNode* node = new IWNode(top);
+
+      if (top->left) {
+        top->setRight(node);
+        // Finish up this level
+        while (top->right) {
+          top = top->parent;
+        }
+      } else {
+        top->setLeft(node);
+      }
+
+      // Grab how many objects we have
+      sscanf(bline, "%u", &(node->num_tris));
+      num_tri_indicies += node->num_tris;
+      if (node->num_tris) {
+        num_nodes++;
+
+        // If you ever change what type triIndices is you will need to
+        // update this bit of code.
+        int* tri_ids_p = node->tri_ids = new int[node->num_tris];
+        for(unsigned int i = 0; i < node->num_tris; ++i) {
+          sscanf(bline, "%d", tri_ids_p);
+          ++tri_ids_p;
+        }
+      }
+      // else empty leaf
+    } else {
+      fprintf(stderr, "Unrecongnized token (%c)\n", token);
+    }
+    
+  }
+
+  // Allocate space for the num_tri_indicies.  If this gets changed to
+  // unsigned int from int, you need up update the parser code below.
+  kdtree->triIndices = new VArray<int>(num_tri_indicies);
+  kdtree->triIndices->setLen(num_tri_indicies);
+
+  // Allocate space for the nodes
+  KDTreeNode* nodes =
+    reinterpret_cast<KDTreeNode*>(malloc(num_nodes*sizeof(KDTreeNode)));
+  KDTreeNode* current_node = nodes;
+  unsigned int current_node_index = 0;
+  KDTreeNode* parent = NULL;
+  
+  // Reset the file pointer
+  fseek(bspf, 0, SEEK_SET);
+
+  unsigned int current_tri_index = 0;
+  int* tri_ids_p = kdtree->triIndices->getArray();
+
+#if 1
+  // Now traverse the data structure and fill in the kd tree data.
+  top = head;
+  top->index = current_tri_index++;
+  stack<IWNode*> nodestack;
+  nodestack.push(top);
+  while(!nodestack.empty()) {
+    KDTreeNode& node = nodes[top->index];
+    if (top->isNode()) {
+      // NODE
+      node.internal.flags = top->flags;
+      node.internal.split = top->split;
+
+      node.internal.left = current_tri_index;
+      bool has_left;
+      // Need to leave enough space for the children
+      IWNode* child = top->left;
+      if (child && child->isLeaf() && child->num_tris) {
+        has_left = true;
+        child->index = current_tri_index;
+        ++current_tri_index;
+      } else {
+        has_left = false;
+      }
+
+      // Right
+      child = top->right;
+      if (child && child->isLeaf() && child->num_tris) {
+        if (!has_left) {
+          // we need to fix the index of the left
+          node.internal.left--;
+        }
+        child->index = current_tri_index;
+        ++current_tri_index;
+      } else {
+        has_left = false;
+      }
+
+      if (top->left) nodestack.push(top->left);
+      if (top->right) nodestack.push(top->right);
+      
+    } else {
+      // LEAF
+
+      if(top->num_tris > 0) {
+      
+        // Copy the indicies
+        for(unsigned int i = 0; i < top->num_tris; ++i) {
+          *tri_ids_p = top->tri_ids[i];
+          ++tri_ids_p;
+        }
+
+        node.leaf.flags = 0;
+        node.leaf.listBegin = current_tri_index;
+        node.leaf.listLen = top->num_tris;
+        current_tri_index += top->num_tris;
+
+        ++current_node_index;
+      }
+    }
+    top = nodestack.top();
+    nodestack.pop();
+  }
+#else
+  int depth = 0;
+  
+  while((getline(&bline, &bline_len, bspf)) != -1) {
+    // Check the first token
+    char token;
+    sscanf(bline, "% c", &token);
+    if (token == 'N') {
+      char axis_c;
+      float pos;
+      sscanf(bline, "% c=%f,d=%*", &axis_c, &pos);
+      int axis;
+      switch (axis_c) {
+      case 'x': axis = 0; break;
+      case 'y': axis = 1; break;
+      case 'z': axis = 2; break;
+      }
+      KDTreeNode* node = nodes[current_node_index];
+      node->internal.flags = axis;
+      node->internal.split = pos;
+
+      
+      // OK, so we've hit an internal node.  If this is a left child
+      // we need to leave space for it and it's right node.
+    } else if (token == 'L') {
+      // Grap how many objects we have
+      unsigned int num_tris;
+      sscanf(bspf, "%u", &num_tris);
+      if (num_tris) {
+        // If you ever change what type triIndices is you will need to
+        // update this bit of code.
+        for(unsigned int i = 0; i < num_tris; ++i) {
+          sscanf(bspf, "%d", tri_ids_p);
+          ++tri_ids_p;
+        }
+        KDTreeNode node;
+        node.leaf.flags = 0;
+        node.leaf.listBegin = current_tri_index;
+        node.leaf.listLen = num_tris;
+        current_tri_index += num_tris;
+      } else {
+        // empty leaf
+      }
+    } else {
+      fprintf(stderr, "Unrecongnized token (%c)\n", token);
+      // Eat to the end of the line.  In the unlikely event that you
+      // don't eat the whole line, you will loop back and grab the
+      // next character.  You may get really unlucky, you get an 'N'
+      // or 'L' where you left off on this line, otherwise you just
+      // eat more of the bad line.  I can't check everything....
+      char buf[1000];
+      fgets(buf, 1000, bspf);
+    }
+  }
+#endif
+
+  if (bline) free(bline);
   fclose(bspf);
 
   return 1;

---

• [MANTA] r991 - trunk/Model/Groups, bigler, 03/22/2006

---

Archive powered by MHonArc 2.6.16.