Changeset 2093

Timestamp:

02/05/07 16:17:40 (17 years ago)

Author:

mattausch

Message:

 

Location:

GTP/trunk/Lib/Vis/Preprocessing/src

Files:

• BvHierarchy.cpp (modified) (2 diffs)
• BvHierarchy.h (modified) (2 diffs)
• HierarchyManager.cpp (modified) (2 diffs)
• TraversalTree.cpp (modified) (19 diffs)
• TraversalTree.h (modified) (3 diffs)
• ViewCellsManager.cpp (modified) (2 diffs)
• ViewCellsParser.cpp (modified) (6 diffs)
• ViewCellsParserXerces.h (modified) (1 diff)

GTP/trunk/Lib/Vis/Preprocessing/src/BvHierarchy.cpp

@@ -1845 +1845 @@
 
 
+void BvHierarchy::CollectNodes(BvhNode *root, vector<BvhNode *> &nodes) const
+{
+        stack<BvhNode *> nodeStack;
+        nodeStack.push(root);
+
+        while (!nodeStack.empty()) 
+        {
+                BvhNode *node = nodeStack.top();
+                nodeStack.pop();
+
+                nodes.push_back(node);
+                
+                if (!node->IsLeaf()) 
+                {
+                        BvhInterior *interior = (BvhInterior *)node;
+
+                        nodeStack.push(interior->GetBack());
+                        nodeStack.push(interior->GetFront());
+                }
+        }
+}
+
+
 AxisAlignedBox3 BvHierarchy::GetBoundingBox(BvhNode *node) const
 {
@@ -2785 +2808 @@
 
 
-}
+void BvHierarchy::SetUniqueNodeIds()
+{
+        // export bounding boxes
+        vector<BvhNode *> nodes;
+
+        // hack: should also expect interior nodes
+        CollectNodes(mRoot, nodes);
+
+        vector<BvhNode *>::const_iterator oit, oit_end = nodes.end();
+
+        int id = 0;
+
+        for (oit = nodes.begin(); oit != oit_end; ++ oit, ++ id)
+        {
+                (*oit)->SetId(id);
+        }
+}
+
+
+}

GTP/trunk/Lib/Vis/Preprocessing/src/BvHierarchy.h

@@ -562 +562 @@
         void CollectLeaves(BvhNode *root, vector<BvhLeaf *> &leaves) const;
 
+        /** Returns vector of leaves.
+        */
+        void CollectNodes(BvhNode *root, vector<BvhNode *> &nodes) const;
+
         /** Returns bounding box of the whole tree (= bbox of root node)
         */
@@ -924 +928 @@
         bool InitialTerminationCriteriaMet(const BvhTraversalData &tData) const;
 
+        /** Sets the bvh node ids.
+        */
+        void SetUniqueNodeIds();
 
 protected:

GTP/trunk/Lib/Vis/Preprocessing/src/HierarchyManager.cpp

@@ -391 +391 @@
                 cout << "finished" << endl;
         }
+
+        if (mObjectSpaceSubdivisionType == BV_BASED_OBJ_SUBDIV)
+        {
+                mBvHierarchy->SetUniqueNodeIds();
+        }
 }
 
@@ -1662 +1667 @@
                 }
         }
+        else if (mObjectSpaceSubdivisionType == BV_BASED_OBJ_SUBDIV)
+        {
+                // export bounding boxes
+        vector<BvhNode *> nodes;
+
+                // hack: should also expect interior nodes
+                mBvHierarchy->CollectNodes(mBvHierarchy->GetRoot(), nodes);
+
+                vector<BvhNode *>::const_iterator oit, oit_end = nodes.end();
+
+                for (oit = nodes.begin(); oit != oit_end; ++ oit)
+                {
+                        const AxisAlignedBox3 box = (*oit)->GetBox();
+                        const int id = (*oit)->GetId();
+                        
+                        stream << "<BoundingBox" << " id=\"" << (*oit)->GetId() << "\""
+                                   << " min=\"" << box.Min().x << " " << box.Min().y << " " << box.Min().z << "\""
+                                   << " max=\"" << box.Max().x << " " << box.Max().y << " " << box.Max().z << "\" />" << endl;
+                }
+        }
         else
         {

GTP/trunk/Lib/Vis/Preprocessing/src/TraversalTree.cpp

@@ -24 +24 @@
 
 
-TraversalNode::TraversalNode(TraversalInterior *parent):mParent(parent), mMailbox(0), mIntersectable(NULL)
-
-{
-  if (parent)
-    mDepth = parent->mDepth+1;
-  else
-    mDepth = 0;
+TraversalNode::TraversalNode(TraversalInterior *parent): 
+mParent(parent), mMailbox(0)
+{
+}
+
+
+TraversalInterior::TraversalInterior(TraversalInterior *parent): 
+TraversalNode(parent), mBack(NULL), mFront(NULL) 
+{
 }
 
@@ -42 +44 @@
 
 
+bool TraversalInterior::IsLeaf() const 
+{ 
+        return false; 
+}
+
+
+void TraversalInterior::SetupChildLinks(TraversalNode *b, TraversalNode *f) 
+{
+        mBack = b;
+        mFront = f;
+        
+        b->mParent = f->mParent = this;
+}
+
+
+void TraversalInterior::ReplaceChildLink(TraversalNode *oldChild, TraversalNode *newChild) 
+{
+        if (mBack == oldChild)
+                mBack = newChild;
+        else
+                mFront = newChild;
+}
+
+
+TraversalLeaf::TraversalLeaf(TraversalInterior *parent, const int objects):
+TraversalNode(parent)
+{
+        mObjects.reserve(objects);
+}
+
+
+bool TraversalLeaf::IsLeaf() const 
+{ 
+        return true; 
+}
+
+
 TraversalLeaf::~TraversalLeaf()
 {
-        DEL_PTR(mViewCell);  
 }
 
 
 TraversalTree::TraversalTree()
-{
-
-  
-  mRoot = new TraversalLeaf(NULL, 0);
-  Environment::GetSingleton()->GetIntValue("TraversalTree.Termination.maxNodes", mTermMaxNodes);
-  Environment::GetSingleton()->GetIntValue("TraversalTree.Termination.maxDepth", mTermMaxDepth);
-  Environment::GetSingleton()->GetIntValue("TraversalTree.Termination.minCost", mTermMinCost);
-  Environment::GetSingleton()->GetFloatValue("TraversalTree.Termination.maxCostRatio", mMaxCostRatio);
-  Environment::GetSingleton()->GetFloatValue("TraversalTree.Termination.ct_div_ci", mCt_div_ci);
-  Environment::GetSingleton()->GetFloatValue("TraversalTree.splitBorder", mSplitBorder);
-
-  Environment::GetSingleton()->GetBoolValue("TraversalTree.sahUseFaces", mSahUseFaces);
-
-  char splitType[64];
-  Environment::GetSingleton()->GetStringValue("TraversalTree.splitMethod", splitType);
-  
-  mSplitMethod = SPLIT_SPATIAL_MEDIAN;
-  if (strcmp(splitType, "spatialMedian") == 0)
-    mSplitMethod = SPLIT_SPATIAL_MEDIAN;
-  else
-    if (strcmp(splitType, "objectMedian") == 0)
-      mSplitMethod = SPLIT_OBJECT_MEDIAN;
-    else
-      if (strcmp(splitType, "SAH") == 0)
-        mSplitMethod = SPLIT_SAH;
-      else {
-        cerr<<"Wrong kd split type "<<splitType<<endl;
-        exit(1);
-      }
-  splitCandidates = NULL;
+{ 
+        mRoot = new TraversalLeaf(NULL, 0);
+
+        Environment::GetSingleton()->GetIntValue("TraversalTree.Termination.maxNodes", mTermMaxNodes);
+        Environment::GetSingleton()->GetIntValue("TraversalTree.Termination.maxDepth", mTermMaxDepth);
+        Environment::GetSingleton()->GetIntValue("TraversalTree.Termination.minCost", mTermMinCost);
+        Environment::GetSingleton()->GetFloatValue("TraversalTree.Termination.maxCostRatio", mMaxCostRatio);
+        Environment::GetSingleton()->GetFloatValue("TraversalTree.Termination.ct_div_ci", mCt_div_ci);
+        Environment::GetSingleton()->GetFloatValue("TraversalTree.splitBorder", mSplitBorder);
+
+        Environment::GetSingleton()->GetBoolValue("TraversalTree.sahUseFaces", mSahUseFaces);
+
+        char splitType[64];
+        Environment::GetSingleton()->GetStringValue("TraversalTree.splitMethod", splitType);
+
+        mSplitMethod = SPLIT_SPATIAL_MEDIAN;
+        if (strcmp(splitType, "spatialMedian") == 0)
+        {
+                mSplitMethod = SPLIT_SPATIAL_MEDIAN;
+        }
+        else
+        {
+                if (strcmp(splitType, "objectMedian") == 0)
+                {
+                        mSplitMethod = SPLIT_OBJECT_MEDIAN;
+                }
+                else
+                {
+                        if (strcmp(splitType, "SAH") == 0)
+                        {
+                                mSplitMethod = SPLIT_SAH;
+                        }
+                        else 
+                        {
+                                cerr<<"Wrong kd split type "<<splitType<<endl;
+                                exit(1);
+                        }
+                        
+                        splitCandidates = NULL;
+                }
+        }
 }
 
@@ -85 +134 @@
 {
     DEL_PTR(mRoot);
-
-        CLEAR_CONTAINER(mKdIntersectables);
 }
 
@@ -94 +141 @@
 {
 
-  if (!splitCandidates)
-    splitCandidates = new vector<SortableEntry *>;
-
-  // first construct a leaf that will get subdivide
-  TraversalLeaf *leaf = (TraversalLeaf *) mRoot;
-
-  mStat.nodes = 1;
-
-  mBox.Initialize();
-  ObjectContainer::const_iterator mi;
-  for ( mi = leaf->mObjects.begin();
-        mi != leaf->mObjects.end();
-        mi++) {
-        //      cout<<(*mi)->GetBox()<<endl;
-        mBox.Include((*mi)->GetBox());
-  }
-
-  cout <<"TraversalTree Root Box:"<<mBox<<endl;
-  mRoot = Subdivide(TraversalData(leaf, mBox, 0));
-
-  // remove the allocated array
-  CLEAR_CONTAINER(*splitCandidates);
-  delete splitCandidates;
-
-  float area = GetBox().SurfaceArea()*KD_PVS_AREA;
-
-  SetPvsTerminationNodes(area);
-  
-  return true;
-}
-
-TraversalNode *
-TraversalTree::Subdivide(const TraversalData &tdata)
-{
-
-  TraversalNode *result = NULL;
-
-  priority_queue<TraversalData> tStack;
-  //  stack<STraversalData> tStack;
-  
-  tStack.push(tdata);
-  AxisAlignedBox3 backBox, frontBox;
-
-  while (!tStack.empty()) {
-        //      cout<<mStat.Nodes()<<" "<<mTermMaxNodes<<endl;
-        if (mStat.Nodes() > mTermMaxNodes) {
-          //    if ( GetMemUsage() > maxMemory ) {
-      // count statistics on unprocessed leafs
-      while (!tStack.empty()) {
-                EvaluateLeafStats(tStack.top());
+        if (!splitCandidates)
+        {
+                splitCandidates = new vector<SortableEntry *>;
+        }
+
+        // first construct a leaf that will get subdivide
+        TraversalLeaf *leaf = static_cast<TraversalLeaf *>(mRoot);
+
+        mStat.nodes = 1;
+
+        mBox.Initialize();
+        ObjectContainer::const_iterator mi;
+        for ( mi = leaf->mObjects.begin(); mi != leaf->mObjects.end(); ++ mi) 
+        {
+                //      cout<<(*mi)->GetBox()<<endl;
+                mBox.Include((*mi)->GetBox());
+        }
+
+        cout << "TraversalTree Root Box:" << mBox << endl;
+        mRoot = Subdivide(TraversalData(leaf, mBox, 0));
+        
+        // remove the allocated array
+        CLEAR_CONTAINER(*splitCandidates);
+        delete splitCandidates;
+
+        return true;
+}
+
+
+TraversalNode *TraversalTree::Subdivide(const TraversalData &tdata)
+{
+        TraversalNode *result = NULL;
+
+        //priority_queue<TraversalData> tStack;
+        stack<TraversalData> tStack;
+
+        tStack.push(tdata);
+        AxisAlignedBox3 backBox, frontBox;
+
+        while (!tStack.empty()) 
+        {
+                //      cout<<mStat.Nodes() << " " << mTermMaxNodes << endl;
+                if (mStat.Nodes() > mTermMaxNodes) 
+                {
+                        while (!tStack.empty()) 
+                        {
+                                EvaluateLeafStats(tStack.top());
+                                tStack.pop();
+                        }
+                        break;
+                }
+
+                TraversalData data = tStack.top();
                 tStack.pop();
-      }
-      break;
-    }
-          
-        
-    TraversalData data = tStack.top();
-    tStack.pop();
-    
-    TraversalNode *node = SubdivideNode((TraversalLeaf *) data.mNode,
-                                                                 data.mBox,
-                                                                 backBox,
-                                                                 frontBox
-                                                                 );
-
-        if (result == NULL)
-      result = node;
-    
-    if (!node->IsLeaf()) {
-
-      TraversalInterior *interior = (TraversalInterior *) node;
-      // push the children on the stack
-      tStack.push(TraversalData(interior->mBack, backBox, data.mDepth+1));
-      tStack.push(TraversalData(interior->mFront, frontBox, data.mDepth+1));
-      
-    } else {
-      EvaluateLeafStats(data);
-    }
-  }
-  
-  return result;
-
-}
-
-
-bool
-TraversalTree::TerminationCriteriaMet(const TraversalLeaf *leaf)
+
+                TraversalLeaf *tLeaf = static_cast<TraversalLeaf *> (data.mNode);
+                TraversalNode *node = SubdivideNode(tLeaf,
+                                                                                        data.mBox,
+                                                                                        backBox,
+                                                                                        frontBox);
+
+                if (result == NULL)
+                        result = node;
+
+                if (!node->IsLeaf()) 
+                {
+                        TraversalInterior *interior = static_cast<TraversalInterior *>(node);
+
+                        // push the children on the stack
+                        tStack.push(TraversalData(interior->mBack, backBox, data.mDepth + 1));
+                        tStack.push(TraversalData(interior->mFront, frontBox, data.mDepth + 1));
+
+                } 
+                else 
+                {
+                        EvaluateLeafStats(data);
+                }
+        }
+
+        return result;
+}
+
+
+bool TraversalTree::TerminationCriteriaMet(const TraversalLeaf *leaf)
 {
         const bool criteriaMet =
                 ((int)leaf->mObjects.size() <= mTermMinCost) ||
-                 (leaf->mDepth >= mTermMaxDepth);
- 
+                (leaf->mDepth >= mTermMaxDepth);
+
         if (criteriaMet)
-                cerr<<"\n OBJECTS="<<leaf->mObjects.size()<<endl;
+                cerr<< "\n OBJECTS=" << (int)leaf->mObjects.size() << endl;
 
         return criteriaMet;
@@ -193 +237 @@
 
 
-int
-TraversalTree::SelectPlane(TraversalLeaf *leaf,
-                                        const AxisAlignedBox3 &box,
-                                        float &position
-                                        )
-{
-  int axis = -1;
-  
-  switch (mSplitMethod)
-    {
-    case SPLIT_SPATIAL_MEDIAN: {
-      axis = box.Size().DrivingAxis();
-      position = (box.Min()[axis] + box.Max()[axis])*0.5f;
-      break;
-    }
-    case SPLIT_SAH: {
-      int objectsBack, objectsFront;
-      float costRatio;
-      bool mOnlyDrivingAxis = true;
-
-          if (mOnlyDrivingAxis) {
-                axis = box.Size().DrivingAxis();
-                costRatio = BestCostRatio(leaf,
-                                                                  box,
-                                                                  axis,
-                                                                  position,
-                                                                  objectsBack,
-                                                                  objectsFront);
-      } else {
-                costRatio = MAX_FLOAT;
-                for (int i=0; i < 3; i++) {
-                  float p;
-                  float r = BestCostRatio(leaf,
-                                                                  box,
-                                                                  i,
-                                                                  p,
-                                                                  objectsBack,
-                                                                  objectsFront);
-                  if (r < costRatio) {
-                        costRatio = r;
-                        axis = i;
-                        position = p;
-                  }
-                }
-      }
-      
-      if (costRatio > mMaxCostRatio) {
-                //cout<<"Too big cost ratio "<<costRatio<<endl;
-                axis = -1;
-      }
-      break;
-    }
-    
-    }
-  return axis;
-}
+int TraversalTree::SelectPlane(TraversalLeaf *leaf,
+                                                           const AxisAlignedBox3 &box,
+                                                           float &position)
+{
+        int axis = -1;
+
+        switch (mSplitMethod)
+        {
+        case SPLIT_SPATIAL_MEDIAN: 
+                {
+                        axis = box.Size().DrivingAxis();
+                        position = (box.Min()[axis] + box.Max()[axis])*0.5f;
+                        break;
+                }
+        case SPLIT_SAH: 
+                {
+                        int objectsBack, objectsFront;
+                        float costRatio;
+                        bool mOnlyDrivingAxis = true;
+
+                        if (mOnlyDrivingAxis) 
+                        {
+                                axis = box.Size().DrivingAxis();
+                                costRatio = BestCostRatio(leaf,
+                                        box,
+                                        axis,
+                                        position,
+                                        objectsBack,
+                                        objectsFront);
+                        } 
+                        else 
+                        {
+                                costRatio = MAX_FLOAT;
+
+                                for (int i=0; i < 3; i++) 
+                                {
+                                        float p;
+                                        float r = BestCostRatio(leaf,
+                                                box,
+                                                i,
+                                                p,
+                                                objectsBack,
+                                                objectsFront);
+        
+                                        if (r < costRatio) 
+                                        {
+                                                costRatio = r;
+                                                axis = i;
+                                                position = p;
+                                        }
+                                }
+                        }
+
+                        if (costRatio > mMaxCostRatio) 
+                        {
+                                //cout<<"Too big cost ratio "<<costRatio<<endl;
+                                axis = -1;
+                        }
+                        break;
+                }
+        }
+
+        return axis;
+}
+
 
 TraversalNode *TraversalTree::SubdivideNode(TraversalLeaf *leaf,
                                                                                         const AxisAlignedBox3 &box,
                                                                                         AxisAlignedBox3 &backBBox,
-                                                                                        AxisAlignedBox3 &frontBBox
-                                                                                        )
+                                                                                        AxisAlignedBox3 &frontBBox)
 {
 
@@ -301 +353 @@
 
                 if (box.Min(axis) < position )
-                        objectsBack++;
+                        ++ objectsBack;
         }
 
@@ -310 +362 @@
 
         // replace a link from node's parent
-        if (  leaf->mParent )
+        if (leaf->mParent)
+        {               
                 leaf->mParent->ReplaceChildLink(leaf, node);
+        }
 
         // and setup child links
@@ -321 +375 @@
                 AxisAlignedBox3 box = (*mi)->GetBox();
 
-                // matt: no more ref
-                // for handling multiple objects: keep track of references
-                //if (leaf->IsRoot()) 
-                //      (*mi)->mReferences = 1; // initialise references at root
-
-                // matt: no more ref
-                //-- (*mi)->mReferences; // remove parent ref
-
-
                 if (box.Max(axis) >= position )
                 {
                         front->mObjects.push_back(*mi);
-                        //++ (*mi)->mReferences;
                 }
 
@@ -339 +383 @@
                 {
                         back->mObjects.push_back(*mi);
-                        // matt: no more ref
-                        //  ++ (*mi)->mReferences;
                 }
 
@@ -347 +389 @@
         }
 
-        // store objects referenced in more than one leaf
-        // for easy access
-        ProcessMultipleRefs(back);
-        ProcessMultipleRefs(front);
-
         delete leaf;
+
         return node;
 }
 
 
-void
-TraversalTreeStatistics::Print(ostream &app) const
-{
-  app << "===== TraversalTree statistics ===============\n";
-
-  app << "#N_NODES ( Number of nodes )\n" << nodes << "\n";
-
-  app << "#N_LEAVES ( Number of leaves )\n" << Leaves() << "\n";
-
-  app << "#N_SPLITS ( Number of splits in axes x y z dx dy dz)\n";
-  for (int i=0; i<7; i++)
-    app << splits[i] <<" ";
-  app <<endl;
-
-  app << "#N_RAYREFS ( Number of rayRefs )\n" <<
-    rayRefs << "\n";
-
-  app << "#N_RAYRAYREFS  ( Number of rayRefs / ray )\n" <<
-    rayRefs/(double)rays << "\n";
-
-  app << "#N_LEAFRAYREFS  ( Number of rayRefs / leaf )\n" <<
-    rayRefs/(double)Leaves() << "\n";
-
-  app << "#N_MAXOBJECTREFS  ( Max number of object refs / leaf )\n" <<
-    maxObjectRefs << "\n";
-
-  app << "#N_NONEMPTYRAYREFS  ( Number of rayRefs in nonEmpty leaves / non empty leaf )\n" <<
-    rayRefsNonZeroQuery/(double)(Leaves() - zeroQueryNodes) << "\n";
-
-  app << "#N_LEAFDOMAINREFS  ( Number of query domain Refs / leaf )\n" <<
-    objectRefs/(double)Leaves() << "\n";
-
-  //  app << setprecision(4);
-
-  app << "#N_PEMPTYLEAVES  ( Percentage of leaves with zero query domains )\n"<<
-    zeroQueryNodes*100/(double)Leaves()<<endl;
-
-  app << "#N_PMAXDEPTHLEAVES ( Percentage of leaves at maxdepth )\n"<<
-    maxDepthNodes*100/(double)Leaves()<<endl;
-
-  app << "#N_PMINCOSTLEAVES  ( Percentage of leaves with minCost )\n"<<
-    minCostNodes*100/(double)Leaves()<<endl;
-
-  app << "#N_ADDED_RAYREFS  (Number of dynamically added ray references )\n"<<
-    addedRayRefs<<endl;
-
-  app << "#N_REMOVED_RAYREFS  (Number of dynamically removed ray references )\n"<<
-    removedRayRefs<<endl;
-
-  //  app << setprecision(4);
-
-  //  app << "#N_CTIME  ( Construction time [s] )\n"
-  //      << Time() << " \n";
-
-  app << "===== END OF TraversalTree statistics ==========\n";
-
-}
-
-
-
-void
-TraversalTree::EvaluateLeafStats(const TraversalData &data)
+void TraversalTreeStatistics::Print(ostream &app) const
+{
+        app << "===== TraversalTree statistics ===============\n";
+
+        app << "#N_NODES ( Number of nodes )\n" << nodes << "\n";
+
+        app << "#N_LEAVES ( Number of leaves )\n" << Leaves() << "\n";
+
+        app << "#N_SPLITS ( Number of splits in axes x y z dx dy dz)\n";
+        for (int i=0; i<7; i++)
+                app << splits[i] <<" ";
+        app <<endl;
+
+        app << "#N_RAYREFS ( Number of rayRefs )\n" <<
+                rayRefs << "\n";
+
+        app << "#N_RAYRAYREFS  ( Number of rayRefs / ray )\n" <<
+                rayRefs/(double)rays << "\n";
+
+        app << "#N_LEAFRAYREFS  ( Number of rayRefs / leaf )\n" <<
+                rayRefs/(double)Leaves() << "\n";
+
+        app << "#N_MAXOBJECTREFS  ( Max number of object refs / leaf )\n" <<
+                maxObjectRefs << "\n";
+
+        app << "#N_NONEMPTYRAYREFS  ( Number of rayRefs in nonEmpty leaves / non empty leaf )\n" <<
+                rayRefsNonZeroQuery/(double)(Leaves() - zeroQueryNodes) << "\n";
+
+        app << "#N_LEAFDOMAINREFS  ( Number of query domain Refs / leaf )\n" <<
+                objectRefs/(double)Leaves() << "\n";
+
+        //  app << setprecision(4);
+
+        app << "#N_PEMPTYLEAVES  ( Percentage of leaves with zero query domains )\n"<<
+                zeroQueryNodes*100/(double)Leaves()<<endl;
+
+        app << "#N_PMAXDEPTHLEAVES ( Percentage of leaves at maxdepth )\n"<<
+                maxDepthNodes*100/(double)Leaves()<<endl;
+
+        app << "#N_PMINCOSTLEAVES  ( Percentage of leaves with minCost )\n"<<
+                minCostNodes*100/(double)Leaves()<<endl;
+
+        app << "#N_ADDED_RAYREFS  (Number of dynamically added ray references )\n"<<
+                addedRayRefs<<endl;
+
+        app << "#N_REMOVED_RAYREFS  (Number of dynamically removed ray references )\n"<<
+                removedRayRefs<<endl;
+
+        //  app << setprecision(4);
+
+        //  app << "#N_CTIME  ( Construction time [s] )\n"
+        //      << Time() << " \n";
+
+        app << "===== END OF TraversalTree statistics ==========\n";
+
+}
+
+
+void TraversalTree::EvaluateLeafStats(const TraversalData &data)
 {
 
@@ -439 +474 @@
 
 void
-TraversalTree::SortSubdivisionCandidates(
-                            TraversalLeaf *node,
-                            const int axis
-                            )
+TraversalTree::SortSubdivisionCandidates(TraversalLeaf *node,
+                                                                                 const int axis)
 {
         CLEAR_CONTAINER(*splitCandidates);
@@ -451 +484 @@
         // creates a sorted split candidates array
         if (splitCandidates->capacity() > 500000 &&
-                requestedSize < (int)(splitCandidates->capacity()/10) ) {               
-                        delete splitCandidates;
-                        splitCandidates = new vector<SortableEntry *>;
-  }
+                requestedSize < (int)(splitCandidates->capacity()/10) ) 
+        {               
+                delete splitCandidates;
+                splitCandidates = new vector<SortableEntry *>;
+        }
   
-  splitCandidates->reserve(requestedSize);
-  
-  // insert all queries 
-  for(ObjectContainer::const_iterator mi = node->mObjects.begin();
-      mi != node->mObjects.end();
-      mi++) 
-  {
-          AxisAlignedBox3 box = (*mi)->GetBox();
-
-          splitCandidates->push_back(new SortableEntry(SortableEntry::BOX_MIN,
-                                                                 box.Min(axis),
-                                                                 *mi)
-                                                                 );
-    
-      splitCandidates->push_back(new SortableEntry(SortableEntry::BOX_MAX,
-                                                                 box.Max(axis),
-                                                                 *mi)
-                                                                 );
-  }
-  
-  stable_sort(splitCandidates->begin(), splitCandidates->end(), iltS);
+        splitCandidates->reserve(requestedSize);
+
+        // insert all queries 
+        for(ObjectContainer::const_iterator mi = node->mObjects.begin();
+                mi != node->mObjects.end();
+                mi++) 
+        {
+                AxisAlignedBox3 box = (*mi)->GetBox();
+
+                splitCandidates->push_back(new SortableEntry(SortableEntry::BOX_MIN,
+                        box.Min(axis),
+                        *mi)
+                        );
+
+                splitCandidates->push_back(new SortableEntry(SortableEntry::BOX_MAX,
+                        box.Max(axis),
+                        *mi)
+                        );
+        }
+
+        stable_sort(splitCandidates->begin(), splitCandidates->end(), iltS);
 }
 
 
 float
-TraversalTree::BestCostRatio(
-                                          TraversalLeaf *node,
-                                          const AxisAlignedBox3 &box,
-                                          const int axis,
-                                          float &position,
-                                          int &objectsBack,
-                                          int &objectsFront
-                                          )
+TraversalTree::BestCostRatio(TraversalLeaf *node,
+                                                         const AxisAlignedBox3 &box,
+                                                         const int axis,
+                                                         float &position,
+                                                         int &objectsBack,
+                                                         int &objectsFront
+                                                         )
 {
 
@@ -494 +527 @@
 
 #if DEBUG_COST
-  static int nodeId = -1;
-  char filename[256];
-  
-  static int lastAxis = 100;
-  if (axis <= lastAxis)
-        nodeId++;
-
-  lastAxis = axis;
-  
-  sprintf(filename, "sah-cost%d-%d.log", nodeId, axis);
-  ofstream costStream;
-  
-  if (nodeId < 100)
-        costStream.open(filename);
+        static int nodeId = -1;
+        char filename[256];
+
+        static int lastAxis = 100;
+        if (axis <= lastAxis)
+                nodeId++;
+
+        lastAxis = axis;
+
+        sprintf(filename, "sah-cost%d-%d.log", nodeId, axis);
+        ofstream costStream;
+
+        if (nodeId < 100)
+                costStream.open(filename);
 
 #endif
-  
-  SortSubdivisionCandidates(node, axis);
-  
-  // go through the lists, count the number of objects left and right
-  // and evaluate the following cost funcion:
-  // C = ct_div_ci  + (ol + or)/queries
-
-  float totalIntersections = 0.0f;
-  vector<SortableEntry *>::const_iterator ci;
-
-  for(ci = splitCandidates->begin();
-      ci < splitCandidates->end();
-      ci++) 
-    if ((*ci)->type == SortableEntry::BOX_MIN) {
-      totalIntersections += (*ci)->intersectable->IntersectionComplexity();
-    }
-        
-  float intersectionsLeft = 0;
-  float intersectionsRight = totalIntersections;
-        
-  int objectsLeft = 0, objectsRight = (int)node->mObjects.size();
-  
-  float minBox = box.Min(axis);
-  float maxBox = box.Max(axis);
-  float boxArea = box.SurfaceArea();
-  
-  float minBand = minBox + mSplitBorder*(maxBox - minBox);
-  float maxBand = minBox + (1.0f - mSplitBorder)*(maxBox - minBox);
-  
-  float minSum = 1e20f;
-  
-  for(ci = splitCandidates->begin();
-      ci < splitCandidates->end();
-      ci++) {
-    switch ((*ci)->type) {
-    case SortableEntry::BOX_MIN:
-      objectsLeft++;
-      intersectionsLeft += (*ci)->intersectable->IntersectionComplexity();
-      break;
-    case SortableEntry::BOX_MAX:
-      objectsRight--;
-      intersectionsRight -= (*ci)->intersectable->IntersectionComplexity();
-      break;
-    }
-
-    if ((*ci)->value > minBand && (*ci)->value < maxBand) {
-      AxisAlignedBox3 lbox = box;
-      AxisAlignedBox3 rbox = box;
-      lbox.SetMax(axis, (*ci)->value);
-      rbox.SetMin(axis, (*ci)->value);
-
-      float sum;
-      if (mSahUseFaces)
-                sum = intersectionsLeft*lbox.SurfaceArea() + intersectionsRight*rbox.SurfaceArea();
-      else
-                sum = objectsLeft*lbox.SurfaceArea() + objectsRight*rbox.SurfaceArea();
-      
-      //      cout<<"pos="<<(*ci).value<<"\t q=("<<ql<<","<<qr<<")\t r=("<<rl<<","<<rr<<")"<<endl;
-      //      cout<<"cost= "<<sum<<endl;
+
+        SortSubdivisionCandidates(node, axis);
+
+        // go through the lists, count the number of objects left and right
+        // and evaluate the following cost funcion:
+        // C = ct_div_ci  + (ol + or)/queries
+
+        float totalIntersections = 0.0f;
+        vector<SortableEntry *>::const_iterator ci;
+
+        for(ci = splitCandidates->begin(); ci < splitCandidates->end(); ++ ci) 
+        if ((*ci)->type == SortableEntry::BOX_MIN) 
+        {
+                totalIntersections += (*ci)->intersectable->IntersectionComplexity();
+        }
+
+        float intersectionsLeft = 0;
+        float intersectionsRight = totalIntersections;
+
+        int objectsLeft = 0, objectsRight = (int)node->mObjects.size();
+
+        float minBox = box.Min(axis);
+        float maxBox = box.Max(axis);
+        float boxArea = box.SurfaceArea();
+
+        float minBand = minBox + mSplitBorder*(maxBox - minBox);
+        float maxBand = minBox + (1.0f - mSplitBorder)*(maxBox - minBox);
+
+        float minSum = 1e20f;
+
+        for(ci = splitCandidates->begin(); ci < splitCandidates->end(); ++ ci) 
+        {
+                switch ((*ci)->type) 
+                {
+                case SortableEntry::BOX_MIN:
+                        objectsLeft++;
+                        intersectionsLeft += (*ci)->intersectable->IntersectionComplexity();
+                        break;
+                case SortableEntry::BOX_MAX:
+                        objectsRight--;
+                        intersectionsRight -= (*ci)->intersectable->IntersectionComplexity();
+                        break;
+                }
+
+                if ((*ci)->value > minBand && (*ci)->value < maxBand) 
+                {
+                        AxisAlignedBox3 lbox = box;
+                        AxisAlignedBox3 rbox = box;
+                        lbox.SetMax(axis, (*ci)->value);
+                        rbox.SetMin(axis, (*ci)->value);
+
+                        float sum;
+                
+                        if (mSahUseFaces)
+                                sum = intersectionsLeft*lbox.SurfaceArea() + intersectionsRight*rbox.SurfaceArea();
+                        else
+                                sum = objectsLeft*lbox.SurfaceArea() + objectsRight*rbox.SurfaceArea();
+
+                        //      cout<<"pos="<<(*ci).value<<"\t q=("<<ql<<","<<qr<<")\t r=("<<rl<<","<<rr<<")"<<endl;
+                        //      cout<<"cost= "<<sum<<endl;
 
 #if DEBUG_COST
-  if (nodeId < 100) {
-        float oldCost = mSahUseFaces ? totalIntersections : node->mObjects.size();
-        float newCost = mCt_div_ci + sum/boxArea;
-        float ratio = newCost/oldCost;
-        costStream<<(*ci)->value<<" "<<ratio<<endl;
-  }
+                        if (nodeId < 100) 
+                        {
+                                float oldCost = mSahUseFaces ? totalIntersections : node->mObjects.size();
+                                float newCost = mCt_div_ci + sum/boxArea;
+                                float ratio = newCost/oldCost;
+                                costStream<<(*ci)->value<<" "<<ratio<<endl;
+                        }
 #endif
-          
-      if (sum < minSum) {
-                minSum = sum;
-                position = (*ci)->value;
-                
-                objectsBack = objectsLeft;
-                objectsFront = objectsRight;
-      }
-    }
-  }
-  
-  float oldCost = mSahUseFaces ? totalIntersections : node->mObjects.size();
-  float newCost = mCt_div_ci + minSum/boxArea;
-  float ratio = newCost/oldCost;
-  
+
+                        if (sum < minSum) 
+                        {
+                                minSum = sum;
+                                position = (*ci)->value;
+
+                                objectsBack = objectsLeft;
+                                objectsFront = objectsRight;
+                        }
+                }
+        }
+
+        const float oldCost = mSahUseFaces ? totalIntersections : node->mObjects.size();
+        const float newCost = mCt_div_ci + minSum/boxArea;
+        const float ratio = newCost/oldCost;
+
 #if 0
-  cout<<"===================="<<endl;
-  cout<<"costRatio="<<ratio<<" pos="<<position<<" t="<<(position - minBox)/(maxBox - minBox)
-      <<"\t o=("<<objectsBack<<","<<objectsFront<<")"<<endl;
+        cout<<"===================="<<endl;
+        cout<<"costRatio="<<ratio<<" pos="<<position<<" t="<<(position - minBox)/(maxBox - minBox)
+                        <<"\t o=("<<objectsBack<<","<<objectsFront<<")"<<endl;
 #endif
-  return ratio;
+        return ratio;
 }
 
 
 int TraversalTree::CastLineSegment(const Vector3 &origin,
-                                                        const Vector3 &termination,
-                                                        ViewCellContainer &viewcells)
+                                                                   const Vector3 &termination,
+                                                                   ViewCellContainer &viewcells,
+                                                                   const bool useMailboxing)
 {
         int hits = 0;
@@ -611 +648 @@
         const Vector3 dir = termination - origin;
 
-        stack<RayTraversalData> tStack;
-
-        Intersectable::NewMail();
-
-        //maxt += Limits::Threshold;
+        stack<LineTraversalData> tStack;
 
         Vector3 entp = origin;
@@ -641 +674 @@
                                         // cases N1,N2,N3,P5,Z2,Z3
                                         continue;
-                                } 
-                                else
+                                } else
                                 {
                                         // case N4
@@ -667 +699 @@
                         // $$ modification 3.5.2004 - hints from Kamil Ghais
                         // case N4 or P4
-                        float tdist = (position - origin[axis]) / dir[axis];
-                        //tStack.push(RayTraversalData(farChild, extp, maxt)); //TODO
+                        const float tdist = (position - origin[axis]) / dir[axis];
+                        tStack.push(LineTraversalData(farChild, extp, maxt)); //TODO
+
                         extp = origin + dir * tdist;
                         maxt = tdist;
@@ -676 +709 @@
                         // compute intersection with all objects in this leaf
                         TraversalLeaf *leaf = static_cast<TraversalLeaf *>(node);
-
-                        // add view cell to intersections
-                        ViewCell *vc = leaf->mViewCell;
-
-                        if (!vc->Mailed())
-                        {
-                                vc->Mail();
-                                viewcells.push_back(vc);
+                        ViewCell *viewCell = NULL;
+
+#if TODO
+                        if (0)
+                                viewCell = mViewCellsTree->GetActiveViewCell(leaf->GetViewCell());
+                        else
+                                viewCell = leaf->mViewCell;
+#endif
+                        // don't have to mail if each view cell belongs to exactly one leaf
+                        if (!useMailboxing || !viewCell->Mailed())
+                        {
+                                if (useMailboxing)
+                                        viewCell->Mail();
+
+                                viewcells.push_back(viewCell);
                                 ++ hits;
                         }
@@ -694 +734 @@
                         mint = maxt;
                         
-                        RayTraversalData &s  = tStack.top();
+                        LineTraversalData &s  = tStack.top();
                         node = s.mNode;
                         extp = s.mExitPoint;
                         maxt = s.mMaxT;
+
                         tStack.pop();
                 }
@@ -706 +747 @@
 
 
-void
-TraversalTree::CollectLeaves(vector<TraversalLeaf *> &leaves)
-{
-  stack<TraversalNode *> nodeStack;
-  nodeStack.push(mRoot);
-
-  while (!nodeStack.empty()) {
-    TraversalNode *node = nodeStack.top();
-    nodeStack.pop();
-    if (node->IsLeaf()) {
-      TraversalLeaf *leaf = (TraversalLeaf *)node;
-      leaves.push_back(leaf);
-    } else {
-      TraversalInterior *interior = (TraversalInterior *)node;
-      nodeStack.push(interior->mBack);
-      nodeStack.push(interior->mFront);
-    }
-  }
-}
-
-
-}
+void TraversalTree::CollectLeaves(vector<TraversalLeaf *> &leaves)
+{
+        stack<TraversalNode *> nodeStack;
+        nodeStack.push(mRoot);
+
+        while (!nodeStack.empty()) 
+        {
+                TraversalNode *node = nodeStack.top();
+                nodeStack.pop();
+                
+                if (node->IsLeaf()) 
+                {
+                        TraversalLeaf *leaf = (TraversalLeaf *)node;
+                        leaves.push_back(leaf);
+                } 
+                else 
+                {
+                        TraversalInterior *interior = (TraversalInterior *)node;
+                        nodeStack.push(interior->mBack);
+                        nodeStack.push(interior->mFront);
+                }
+        }
+}
+
+
+AxisAlignedBox3 TraversalTree::GetBox(const TraversalNode *node) const 
+{       
+        TraversalInterior *parent = node->mParent;
+        
+        if (parent == NULL)
+                return mBox;
+
+        if (!node->IsLeaf())
+                return ((TraversalInterior *)node)->mBox;
+
+        AxisAlignedBox3 box(parent->mBox);
+        
+        if (parent->mFront == node)
+                box.SetMin(parent->mAxis, parent->mPosition);
+        else
+                box.SetMax(parent->mAxis, parent->mPosition);
+        return box;
+}
+
+}

GTP/trunk/Lib/Vis/Preprocessing/src/TraversalTree.h

@@ -61 +61 @@
   
   // Constructor
-  TraversalTreeStatistics() {
-    Reset();
+  TraversalTreeStatistics() 
+  {
+          Reset();
   }
 
@@ -69 +70 @@
   int Leaves() const { return (nodes / 2) + 1; }
 
-  void Reset() {
-    nodes = 0;
-    for (int i=0; i<7; i++)
-      splits[i] = 0;
-    rays = queryDomains = 0;
-    rayRefs = rayRefsNonZeroQuery = objectRefs = 0;
-    zeroQueryNodes = 0;
-    maxDepthNodes = 0;
-    minCostNodes = 0;
-    maxObjectRefs = 0;
-    addedRayRefs = removedRayRefs = 0;
+  void Reset() 
+  {
+          nodes = 0;
+          
+          for (int i=0; i<7; i++)
+                  splits[i] = 0;
+          
+          rays = queryDomains = 0;
+          rayRefs = rayRefsNonZeroQuery = objectRefs = 0;
+          zeroQueryNodes = 0;
+          maxDepthNodes = 0;
+          minCostNodes = 0;
+          maxObjectRefs = 0;
+          addedRayRefs = removedRayRefs = 0;
   }
 
-  void
-  Print(ostream &app) const;
-
-  friend ostream &operator<<(ostream &s, const TraversalTreeStatistics &stat) {
-    stat.Print(s);
-    return s;
+  void Print(ostream &app) const;
+
+  friend ostream &operator<<(ostream &s, const TraversalTreeStatistics &stat) 
+  {
+          stat.Print(s);
+          return s;
   }
   
@@ -94 +98 @@
   
 class TraversalInterior;
-/** Abstract class for kd-tree node */
-class TraversalNode {
+
+/** Abstract class for kd-tree node 
+*/
+class TraversalNode 
+{
 public:
-  
-  static int sMailId;
-  static int sReservedMailboxes;
-  int mMailbox;
-
-  KdIntersectable *mIntersectable;
-  
-  void Mail() { mMailbox = sMailId; }
-  //static void NewMail() { sMailId ++; }
-  bool Mailed() const { return mMailbox == sMailId; }
- 
-  static void NewMail(const int reserve = 1) {
+
+        virtual ~TraversalNode(){};
+        
+        TraversalNode(TraversalInterior *parent);
+        /** Determines whether this node is a leaf or interior node
+        @return true if leaf
+        */
+        virtual bool IsLeaf() const = 0;
+
+        /** Determines whether this node is the root of the tree
+        @return true if root
+        */
+        virtual bool IsRoot() const 
+        {
+                return mParent == NULL;
+        }
+
+        /** Parent of the node - the parent is a little overhead for maintanance of the tree,
+                but allows various optimizations of tree traversal algorithms 
+        */
+        TraversalInterior *mParent;
+
+
+        /////////////////// 
+        // mailing stuff
+
+public:
+
+        void Mail() 
+        { 
+                mMailbox = sMailId; 
+        }
+
+        bool Mailed() const 
+        { 
+                return mMailbox == sMailId; 
+        }
+
+        static void NewMail(const int reserve = 1) 
+        {
                 sMailId += sReservedMailboxes;
                 sReservedMailboxes = reserve;
         }
-        void Mail(const int mailbox) { mMailbox = sMailId + mailbox; }
-        bool Mailed(const int mailbox) const { return mMailbox == sMailId + mailbox; }
-
-  virtual ~TraversalNode(){};
-  TraversalNode(TraversalInterior *parent);
-
-  /** Determines whether this node is a leaf or interior node
-      @return true if leaf
-  */
-  virtual bool IsLeaf() const = 0;
-
-  /** Determines whether this node is the root of the tree
-      @return true if root
-  */
-  virtual bool IsRoot() const {
-    return mParent == NULL;
-  }
-
-  /** Parent of the node - the parent is a little overhead for maintanance of the tree,
-      but allows various optimizations of tree traversal algorithms */
-  TraversalInterior *mParent;
-  short mDepth;
-  short mPvsTermination;
+
+        void Mail(const int mailbox) 
+        { 
+                mMailbox = sMailId + mailbox; 
+        }
+
+
+        bool Mailed(const int mailbox) const 
+        { 
+                return mMailbox == sMailId + mailbox; 
+        }
+
+        int mMailbox;
+
+        static int sMailId;
+        static int sReservedMailboxes;
 };
 
-/** Implementation of the kd-tree interior node */
-class TraversalInterior : public TraversalNode {
-
+
+/** Implementation of the kd-tree interior node 
+*/
+class TraversalInterior : public TraversalNode 
+{
 public:
-    
-  TraversalInterior(TraversalInterior *parent):TraversalNode(parent), mBack(NULL), mFront(NULL) {}
-
-  ~TraversalInterior();
-
-  /** \sa TraversalNode::IsLeaf() */
-  virtual bool IsLeaf() const { return false; }
-
-  /** splitting axis */
-  int mAxis;
-  /** splitting position, absolute position within the bounding box of this node */
-  float mPosition;
-  /** bounding box of interior node */
-  AxisAlignedBox3 mBox;
-
-  /** back node */
-  TraversalNode *mBack;
-  /** front node */
-  TraversalNode *mFront;
-
-  void SetupChildLinks(TraversalNode *b, TraversalNode *f) {
-    mBack = b;
-    mFront = f;
-    b->mParent = f->mParent = this;
-  }
-  
-  void ReplaceChildLink(TraversalNode *oldChild, TraversalNode *newChild) {
-    if (mBack == oldChild)
-      mBack = newChild;
-    else
-      mFront = newChild;
-  }
-  
-  
+
+        TraversalInterior(TraversalInterior *parent);
+        ~TraversalInterior();
+
+        /** \sa TraversalNode::IsLeaf() 
+        */
+        bool IsLeaf() const;
+
+        void SetupChildLinks(TraversalNode *b, TraversalNode *f);
+
+        void ReplaceChildLink(TraversalNode *oldChild, TraversalNode *newChild);
+
+
+        //////////////////////////
+
+        /// splitting axis
+        int mAxis;
+        /// splitting position, absolute position within the bounding box of this node.
+        float mPosition;
+        /// bounding box of interior node
+        AxisAlignedBox3 mBox;
+
+        /// back node 
+        TraversalNode *mBack;
+        /// front node
+        TraversalNode *mFront;  
 };
-  
-class SubdivisionCandidate;
-  
-/** Implementation of the kd-tree leaf node */
-class TraversalLeaf : public TraversalNode {
+
+  
+/** Implementation of the kd-tree leaf node 
+*/
+class TraversalLeaf : public TraversalNode 
+{
 public:
-  TraversalLeaf(TraversalInterior *parent, const int objects):
-          TraversalNode(parent), mViewCell(NULL) {
-    mObjects.reserve(objects);
-  }
-  
-  void AddPassingRay(const Ray &ray, const int contributions) {
-    mPassingRays.AddRay(ray, contributions);
-                //              Debug << "adding passing ray" << endl;
-  }
-
-  ~TraversalLeaf();
-        
-        void AddPassingRay2(const Ray &ray,
-                                                const int objects,
-                                                const int viewcells
-                                                ) {
-    mPassingRays.AddRay2(ray, objects, viewcells);
-                //              Debug << "adding passing ray" << endl;
-  }
-
-  /** \sa TraversalNode::IsLeaf() */
-  virtual bool IsLeaf() const { return true; }
-
-
-  /** pointers to occluders contained in this node */
-  ObjectContainer mObjects;
-
-  /** Ray set description of the rays passing through this node */
-  PassingRaySet mPassingRays;
-        
-  /** PVS consisting of visible TraversalTree nodes */
-  KdPvs mKdPvs;
-
-  /// pvs of view cells seeing this node.
-  SubdivisionCandidate *mSubdivisionCandidate;
-
-  /// pointer to view cell.
-  KdViewCell *mViewCell;
-
-  VssRayContainer mVssRays;
-
-   /// Objects that are referenced in more than one leaf.
-  ObjectContainer mMultipleObjects;
-
-  /// universal counter
-  int mCounter;
+
+        TraversalLeaf(TraversalInterior *parent, const int objects);
+
+        ~TraversalLeaf();
+
+        /** \sa TraversalNode::IsLeaf() 
+        */
+        virtual bool IsLeaf() const;
+
+        /////////////////////////////////
+
+        // pointers to view cells contained in this node
+        ObjectContainer mObjects;
+
+        short mDepth;
 };
 
 
-/** TraversalTree for indexing scene entities - occluders/occludees/viewcells */
-class TraversalTree {
-  
+/** TraversalTree for indexing scene entities - occluders/occludees/viewcells 
+*/
+class TraversalTree 
+{
+
 protected:
-  struct TraversalData
-  {  
-    TraversalNode *mNode;
-    AxisAlignedBox3 mBox;
-    int mDepth;
-    float mPriority;
-    
-    TraversalData() {}
-
-    TraversalData(TraversalNode *n, const float p):
-      mNode(n), mPriority(p)
-    {}
-    
-    TraversalData(TraversalNode *n,
-                   const AxisAlignedBox3 &b,
-                   const int d):
-      mNode(n), mBox(b), mDepth(d) {}
-    
-
-    bool operator<(
-                                   const TraversalData &b) const {
-      TraversalLeaf *leafa = (TraversalLeaf *) mNode;
-      TraversalLeaf *leafb = (TraversalLeaf *) b.mNode;
-      return 
-                leafa->mObjects.size()*mBox.SurfaceArea()
-                <
-                leafb->mObjects.size()*b.mBox.SurfaceArea();
-    }
-
-
-    // comparator for the 
-    struct less_priority : public
-    binary_function<const TraversalData, const TraversalData, bool> {
-      
-      bool operator()(const TraversalData a, const TraversalData b) {
-                                return a.mPriority < b.mPriority;
-      }
-      
-    };
-
-  };
-
-  
+
+        struct TraversalData
+        {  
+                TraversalNode *mNode;
+                AxisAlignedBox3 mBox;
+                int mDepth;
+                float mPriority;
+
+                TraversalData() {}
+
+                TraversalData(TraversalNode *n, const float p):
+                mNode(n), mPriority(p)
+                {}
+
+                TraversalData(TraversalNode *n,
+                        const AxisAlignedBox3 &b,
+                        const int d):
+                mNode(n), mBox(b), mDepth(d) {}
+
+
+                bool operator<(const TraversalData &b) const 
+                {
+                        TraversalLeaf *leafa = (TraversalLeaf *) mNode;
+                        TraversalLeaf *leafb = (TraversalLeaf *) b.mNode;
+                        
+                        return 
+                                leafa->mObjects.size() * mBox.SurfaceArea()
+                                <
+                                leafb->mObjects.size() * b.mBox.SurfaceArea();
+                }
+
+
+                        // comparator for the 
+                        struct less_priority: public 
+                                binary_function<const TraversalData, const TraversalData, bool> 
+                        {
+                bool operator()(const TraversalData a, const TraversalData b) 
+                                {
+                                        return a.mPriority < b.mPriority;
+                                }
+            };
+        };
+
 
 public:
 
-  enum {SPLIT_OBJECT_MEDIAN,
-        SPLIT_SPATIAL_MEDIAN,
-        SPLIT_SAH};
-  
-  TraversalTree();
-
-  ~TraversalTree();
-    
-  /** Insert view cell into the tree */
-  virtual void InsertViewCell(ViewCell *viewCell) {
-    //      mRoot->mViewcells.push_back(viewCell);
-  }
-
-  virtual bool Construct();
-
-  /** Check whether subdivision criteria are met for the given subtree.
-      If not subdivide the leafs of the subtree. The criteria are specified in
-      the environment as well as the subdivision method. By default surface area
-      heuristics is used.
-        
-      @param subtree root of the subtree
-
-      @return true if subdivision was performed, false if subdivision criteria
-      were already met
-  */
-  virtual TraversalNode *Subdivide(const TraversalData &tdata);
-
-  /** Get the root of the tree */
-  TraversalNode *GetRoot() const {
-    return mRoot;
-  }
-
-
-  AxisAlignedBox3 GetBox() const { return mBox; }
-
-  int
-  CastRay(
-                  Ray &ray
-                  );
-  
-
-  int
-  CastBeam(
-                   Beam &beam
-                   );
-  
-  
-  /** Casts line segment into tree.
-          @returns intersected view cells.
-  */
-  int CastLineSegment(const Vector3 &origin,
-                                          const Vector3 &termination,
-                                          vector<ViewCell *> &viewcells);
-
-
-  const TraversalTreeStatistics &GetStatistics() const {
-    return mStat;
-  }
-
-  /** Returns or creates a new intersectable for use in a kd based pvs.
-          The OspTree is responsible for destruction of the intersectable.
-  */
-  KdIntersectable *GetOrCreateKdIntersectable(TraversalNode *node);
-
-
-  void
-  SetPvsTerminationNodes(
-                                                 const float maxArea);
-  
-  TraversalNode *
-  GetPvsNode(const Vector3 &point) const;
-  
-
-  void
-  CollectKdObjects(const AxisAlignedBox3 &box,
-                                   ObjectContainer &objects
-                                   );
-
-  void
-  CollectObjects(TraversalNode *n, ObjectContainer &objects);
-
-  void
-  CollectObjects(const AxisAlignedBox3 &box,
-                                 ObjectContainer &objects);
-
-  void
-  CollectLeaves(vector<TraversalLeaf *> &leaves);
-        
-  /** If the kd tree is used as view cell container, this
-          methods creates the view cells.
-          @returns the newly created view cells in a view cell container
-  */
-  void
-  CreateAndCollectViewCells(ViewCellContainer &viewCells) const;
-
-  AxisAlignedBox3 GetBox(const TraversalNode *node) const {
-    TraversalInterior *parent = node->mParent;
-    if (parent == NULL)
-      return mBox;
-    
-    if (!node->IsLeaf())
-      return ((TraversalInterior *)node)->mBox;
-    
-    AxisAlignedBox3 box(parent->mBox);
-    if (parent->mFront == node)
-      box.SetMin(parent->mAxis, parent->mPosition);
-    else
-      box.SetMax(parent->mAxis, parent->mPosition);
-    return box;
-  }
-
-  float GetSurfaceArea(const TraversalNode *node) const {
-        return GetBox(node).SurfaceArea();
-  }
-
-  
-  TraversalNode *
-  FindRandomNeighbor(TraversalNode *n,
-                                         bool onlyUnmailed
-                                         );
-  
-  TraversalNode *
-  TraversalTree::GetRandomLeaf(const Plane3 &halfspace);
-
-  TraversalNode *
-  GetRandomLeaf(const bool onlyUnmailed = false);
-
-
-  TraversalNode *
-  GetNode(const Vector3 &point, const float maxArea) const;
-
-  void GetBoxIntersections(const AxisAlignedBox3 &box, 
-                                                  vector<TraversalLeaf *> &leaves);
-
-  int
-  FindNeighbors(TraversalNode *n,
-                                vector<TraversalNode *> &neighbors,
-                                bool onlyUnmailed
-                                );
-
-  int
-  CollectLeafPvs();
-
-  bool ExportBinTree(const string &filename);
-  bool LoadBinTree(const string &filename, ObjectContainer &object);
+        enum {SPLIT_OBJECT_MEDIAN,
+                  SPLIT_SPATIAL_MEDIAN,
+                  SPLIT_SAH};
+
+        TraversalTree();
+
+        ~TraversalTree();
+
+
+        /** Casts line segment into tree.
+                @returns intersected view cells.
+        */
+        int CastLineSegment(const Vector3 &origin,
+                                                const Vector3 &termination,
+                                                ViewCellContainer &viewcells,
+                                                const bool useMailboxing);
+
+        virtual bool Construct();
+
+        /** Check whether subdivision criteria are met for the given subtree.
+                If not subdivide the leafs of the subtree. The criteria are specified in
+                        the environment as well as the subdivision method. By default surface area
+                heuristics is used.
+
+                @param subtree root of the subtree
+
+                @return true if subdivision was performed, false if subdivision criteria
+                were already met
+        */
+        virtual TraversalNode *Subdivide(const TraversalData &tdata);
+
+        /** Get the root of the tree 
+        */
+        TraversalNode *GetRoot() const 
+        {
+                return mRoot;
+        }
+
+        AxisAlignedBox3 GetBox() const 
+        { 
+                return mBox; 
+        }
+
+        const TraversalTreeStatistics &GetStatistics() const 
+        {
+                return mStat;
+        }
+
+        void CollectObjects(TraversalNode *n, ObjectContainer &objects);
+
+        void CollectObjects(const AxisAlignedBox3 &box, ObjectContainer &objects);
+
+        void CollectLeaves(vector<TraversalLeaf *> &leaves);
+
+        float GetSurfaceArea(const TraversalNode *node) const 
+        {
+                return GetBox(node).SurfaceArea();
+        }
+
+        AxisAlignedBox3 GetBox(const TraversalNode *node) const;
+
 
 protected:
 
-  struct RayData {
-    // pointer to the actual ray
-    Ray *ray;
-    
-    // endpoints  - do we need them?
-#if USE_FIXEDPOINT_T
-    short tmin, tmax;
-#else
-    float tmin, tmax;
+        /** Struct for traversing line segment.
+        */
+        struct LineTraversalData 
+        {               
+                LineTraversalData () {}
+                LineTraversalData (TraversalNode *n, const Vector3 &p, const float maxt):
+                mNode(n), mExitPoint(p), mMaxT(maxt) {}
+
+                TraversalNode *mNode;
+                Vector3 mExitPoint;
+                float mMaxT;
+        };
+
+        // --------------------------------------------------------------
+        // For sorting objects
+        // --------------------------------------------------------------
+        struct SortableEntry
+        {
+                enum 
+                {
+                        BOX_MIN,
+                        BOX_MAX
+                };
+
+                int type;
+                float value;
+                Intersectable *intersectable;
+
+                SortableEntry() {}
+                SortableEntry(const int t, const float v, Intersectable *i):
+                type(t), value(v), intersectable(i) 
+                {}
+
+                bool operator<(const SortableEntry &b) const 
+                {
+                        return value < b.value;
+                }
+        };
+
+        inline static bool iltS(SortableEntry *a, SortableEntry *b)
+        {
+                return a->value < b->value;
+        }
+
+        // reusable array of split candidates
+        vector<SortableEntry *> *splitCandidates;
+
+        float BestCostRatio(TraversalLeaf *node,
+                                                const AxisAlignedBox3 &box,
+                                                const int axis,
+                                                float &position,
+                                                int &objectsBack,
+                                                int &objectsFront);
+
+        void SortSubdivisionCandidates(TraversalLeaf *node, const int axis);
+
+        void EvaluateLeafStats(const TraversalData &data);
+
+        TraversalNode *SubdivideNode(TraversalLeaf *leaf,
+                                                                 const AxisAlignedBox3 &box,
+                                                                 AxisAlignedBox3 &backBBox,
+                                                                 AxisAlignedBox3 &frontBBox
+                                                                 );
+
+        bool TerminationCriteriaMet(const TraversalLeaf *leaf);
+
+        int SelectPlane(TraversalLeaf *leaf,
+                                        const AxisAlignedBox3 &box,
+                                        float &position);
+
+
+        ////////////////////////
+
+        int mTermMaxNodes;
+        float mSplitBorder;
+        int mTermMaxDepth;
+        int mTermMinCost;
+        float mMaxCostRatio;
+        float mCt_div_ci;
+        int mSplitMethod;
+        bool mSahUseFaces;
+
+        /// root of the tree
+        TraversalNode *mRoot;
+        /// bounding box of the tree root
+        AxisAlignedBox3 mBox;
+        TraversalTreeStatistics mStat;
+
+};
+
+
+}
+
 #endif
-
-    RayData():ray(NULL) {}
-    RayData(Ray *r):ray(r), tmin(0),
-
-#if USE_FIXEDPOINT_T
-#define FIXEDPOINT_ONE 0x7FFE
-                          //                      tmax(0xFFFF)
-                          tmax(FIXEDPOINT_ONE)
-#else
-      tmax(1.0f)
-#endif
-    {}
-
-    RayData(Ray *r,
-            const float _min,
-            const float _max
-            ):ray(r) {
-      SetTMin(_min);
-      SetTMax(_max);
-    }
-
-    RayData(Ray *r,
-            const short _min,
-            const float _max
-            ):ray(r), tmin(_min) {
-      SetTMax(_max);
-    }
-
-    RayData(Ray *r,
-            const float _min,
-            const short _max
-            ):ray(r), tmax(_max) {
-      SetTMin(_min);
-    }
-
-    friend bool operator<(const RayData &a, const RayData &b) {
-      return a.ray < b.ray;
-    }
-    
-    
-    float ExtrapOrigin(const int axis) const {
-      return ray->GetLoc(axis) + GetTMin()*ray->GetDir(axis);
-    }
-    
-    float ExtrapTermination(const int axis) const {
-      return ray->GetLoc(axis) + GetTMax()*ray->GetDir(axis);
-    }
-    
-#if USE_FIXEDPOINT_T
-    float GetTMin () const { return tmin/(float)(FIXEDPOINT_ONE); }
-    float GetTMax () const { return tmax/(float)(FIXEDPOINT_ONE); }
-
-    void SetTMin (const float t) {
-      tmin = (short) (t*(float)(FIXEDPOINT_ONE));
-    }
-    
-    void SetTMax (const float t) {
-      tmax = (short) (t*(float)(FIXEDPOINT_ONE));
-      tmax++;
-      //      if (tmax!=0xFFFF)
-      //        tmax++;
-    }
-#else
-    float GetTMin () const { return tmin; }
-    float GetTMax () const { return tmax; }
-
-    void SetTMin (const float t) { tmin = t; }
-    void SetTMax (const float t) { tmax = t; }
-#endif 
-  };
-
-  struct RayTraversalData {
-    TraversalNode *mNode;
-    Vector3 mExitPoint;
-    float mMaxT;
-    
-    RayTraversalData() {}
-    RayTraversalData(TraversalNode *n,
-                     const Vector3 &p,
-                     const float maxt):
-      mNode(n), mExitPoint(p), mMaxT(maxt) {}
-  };
-
-  // --------------------------------------------------------------
-  // For sorting objects
-  // --------------------------------------------------------------
-  struct  SortableEntry
-  {
-    enum {
-      BOX_MIN,
-      BOX_MAX
-    };
-    
-    int type;
-    float value;
-    Intersectable *intersectable;
-    
-    SortableEntry() {}
-    SortableEntry(const int t, const float v, Intersectable *i):type(t),
-                                                                value(v),
-                                                                intersectable(i) {}
-    
-    bool operator<(const SortableEntry &b) const {
-      return value < b.value;
-    }
-    
-  };
-
-  inline static bool iltS(SortableEntry *a, SortableEntry *b)
-  {
-          return a->value < b->value;
-  }
-
-  // reusable array of split candidates
-  vector<SortableEntry *> *splitCandidates;
-
-  float
-  BestCostRatio(
-                TraversalLeaf *node,
-                const AxisAlignedBox3 &box,
-                const int axis,
-                float &position,
-                int &objectsBack,
-                int &objectsFront
-                );
-
-  void
-  SortSubdivisionCandidates(
-                      TraversalLeaf *node,
-                      const int axis
-                      );
-
-  void
-  EvaluateLeafStats(const TraversalData &data);
-
-  TraversalNode *
-  SubdivideNode(
-                TraversalLeaf *leaf,
-                const AxisAlignedBox3 &box,
-                AxisAlignedBox3 &backBBox,
-                AxisAlignedBox3 &frontBBox
-                );
-
-  bool
-  TerminationCriteriaMet(const TraversalLeaf *leaf);
-  
-  int
-  SelectPlane(TraversalLeaf *leaf,
-              const AxisAlignedBox3 &box,
-              float &position
-              );
-
-        /** does some post processing on the objects in the new child leaves.
-        */
-        void ProcessMultipleRefs(TraversalLeaf *leaf) const;
-
-        void ExportBinLeaf(OUT_STREAM  &stream, TraversalLeaf *leaf);
-        void ExportBinInterior(OUT_STREAM &stream, TraversalInterior *interior);
-        TraversalLeaf *ImportBinLeaf(IN_STREAM &stream, TraversalInterior *parent, const ObjectContainer &objects);
-        TraversalInterior *ImportBinInterior(IN_STREAM  &stream, TraversalInterior *parent);
-        TraversalNode *LoadNextNode(IN_STREAM  &stream, TraversalInterior *parent, const ObjectContainer &objects);
-        
-        /** Adds this objects to the kd leaf objects.
-                @warning: Can corrupt the tree
-        */
-        void InsertObjects(TraversalNode *node, const ObjectContainer &objects);
-
-  int mTermMaxNodes;
-  float mSplitBorder;
-  int mTermMaxDepth;
-  int mTermMinCost;
-  float mMaxCostRatio;
-  float mCt_div_ci;
-  int mSplitMethod;
-  bool mSahUseFaces;
-  /// root of the tree
-  TraversalNode *mRoot;
-  /// bounding box of the tree root
-  AxisAlignedBox3 mBox;
-  TraversalTreeStatistics mStat;
-public:
-  /// stores the kd node intersectables used for pvs
-  vector<KdIntersectable *> mKdIntersectables;
-  
-};
-
-
-}
-
-#endif

GTP/trunk/Lib/Vis/Preprocessing/src/ViewCellsManager.cpp

@@ -6604 +6604 @@
                                 const AxisAlignedBox3 box = obj->GetBox();
 
-                                // set kd id
+                                // set kd node id
                                 obj->SetId(id);
 
@@ -6617 +6617 @@
                 }
         }
+
 
         //////////////////////////

GTP/trunk/Lib/Vis/Preprocessing/src/ViewCellsParser.cpp

@@ -64 +64 @@
 static SAXParser::ValSchemes    valScheme       = SAXParser::Val_Auto;
 
+// hack for loading bvh nodes
 #define PVS_HACK 0
 
@@ -582 +583 @@
                         // to sumof pdfs, i.e. its relative visibility
                         // temporarily set to 1.0f
-                        //cout << "r";
-
                         pvs.AddSample(*oit, 1.0f);
                 }
@@ -833 +832 @@
 
 
-ViewCell *ViewCellsParseHandlers::GetOrCreateViewCell(const int id, const bool isLeaf)
-{/*
-        ViewCellsMap::iterator vit = mViewCells.find(id);
-
-        if (vit != mViewCells.end())
-        {
-                return (*vit).second;
-        }
-        else
-        {
-                ViewCell *vc;
-                if (isLeaf)
-                {
-                        vc = new ViewCellLeaf();
-                }
-                else
-                {
-                        vc = new ViewCellInterior();
-                }
-
-                vc->SetId(id);
-                mViewCells[id] = vc;
-                return vc;
-        }*/
-        return NULL;
-}
-
-
 void ViewCellsParseHandlers::StartViewCell(AttributeList& attributes, const bool isLeaf)
 {
@@ -867 +838 @@
         const int len = attributes.getLength();
         float mergeCost;
-        //ObjectPvs pvs;
-
-        //viewCell = GetOrCreateViewCell(id, isLeaf);
-
+        
         if (isLeaf)
         {
@@ -892 +860 @@
 
                         // create new view cell, otherwise use reference.
-                        //viewCell = GetOrCreateViewCell(id, isLeaf);
                         viewCell->SetId(id);
 
@@ -1322 +1289 @@
         if (PVS_HACK)
         {
-                if (1) // Temp matt: should HAVE right id
-                {
+                if (0) // Temp matt: should already have right id
                         leaf->SetId((int)mBvhLeaves.size());
-                }
+                
                 mBvhLeaves.push_back(leaf);     
-                                
-                //cout << "i";
         }
 }

GTP/trunk/Lib/Vis/Preprocessing/src/ViewCellsParserXerces.h

@@ -131 +131 @@
 
   // Handlers for X3D
-  ViewCell *GetOrCreateViewCell(const int id, const bool isLeaf);
-
+  
   void StartBspLeaf(AttributeList& attributes);
   void StartBspInterior(AttributeList& attributes);