Changeset 2124

Timestamp:

02/19/07 02:51:22 (17 years ago)

Author:

mattausch

Message:

 

Location:

GTP/trunk/Lib/Vis

Files:

• OnlineCullingCHC/ObjReader/include/ObjMeshData.h (deleted)
• OnlineCullingCHC/ObjReader/include/ObjNode.h (deleted)
• OnlineCullingCHC/ObjReader/include/ObjReader.h (modified) (2 diffs)
• OnlineCullingCHC/ObjReader/src/ObjMeshData.cpp (deleted)
• OnlineCullingCHC/ObjReader/src/ObjNode.cpp (deleted)
• OnlineCullingCHC/ObjReader/src/ObjReader.cpp (modified) (6 diffs)
• Preprocessing/scripts/preprocess_visibility.sh (modified) (1 diff)
• Preprocessing/src/AxisAlignedBox3.cpp (modified) (6 diffs)
• Preprocessing/src/AxisAlignedBox3.h (modified) (5 diffs)
• Preprocessing/src/BvHierarchy.cpp (modified) (2 diffs)
• Preprocessing/src/BvHierarchy.h (modified) (1 diff)
• Preprocessing/src/Environment.cpp (modified) (3 diffs)
• Preprocessing/src/Exporter.cpp (modified) (2 diffs)
• Preprocessing/src/Exporter.h (modified) (3 diffs)
• Preprocessing/src/HierarchyManager.cpp (modified) (4 diffs)
• Preprocessing/src/HierarchyManager.h (modified) (1 diff)
• Preprocessing/src/KdTree.cpp (modified) (1 diff)
• Preprocessing/src/Mutation.cpp (modified) (5 diffs)
• Preprocessing/src/Plane3.cpp (modified) (2 diffs)
• Preprocessing/src/Preprocessor.cpp (modified) (3 diffs)
• Preprocessing/src/PreprocessorFactory.cpp (modified) (1 diff)
• Preprocessing/src/TraversalTree.cpp (modified) (29 diffs)
• Preprocessing/src/TraversalTree.h (modified) (11 diffs)
• Preprocessing/src/ViewCell.cpp (modified) (2 diffs)
• Preprocessing/src/ViewCell.h (modified) (3 diffs)
• Preprocessing/src/ViewCellsManager.cpp (modified) (4 diffs)
• Preprocessing/src/ViewCellsManager.h (modified) (1 diff)
• Preprocessing/src/VrmlExporter.h (modified) (2 diffs)
• Preprocessing/src/VspBspTree.cpp (modified) (1 diff)
• Preprocessing/src/VspTree.cpp (modified) (1 diff)
• Preprocessing/src/VspTree.h (modified) (1 diff)
• Preprocessing/src/X3dExporter.cpp (modified) (1 diff)
• Preprocessing/src/X3dExporter.h (modified) (1 diff)

GTP/trunk/Lib/Vis/OnlineCullingCHC/ObjReader/include/ObjReader.h

@@ -9 +9 @@
 namespace  GtpVisibilityPreprocessor {
 class Intersectable;
+class Preprocessor;
 }
 
@@ -31 +32 @@
         Ogre::SceneManager *mSceneManager;
         GtpVisibilityPreprocessor::ObjectContainer mPvsObjects;
+        GtpVisibilityPreprocessor::Preprocessor *mPreprocessor;
 };
 

GTP/trunk/Lib/Vis/OnlineCullingCHC/ObjReader/src/ObjReader.cpp

@@ -13 +13 @@
 
 ObjReader::ObjReader(Ogre::SceneManager *sceneManager):
-mSceneManager(sceneManager)
-{}
+mSceneManager(sceneManager), mPreprocessor(NULL)
+{
+}
 
 
@@ -20 +21 @@
 {
         CLEAR_CONTAINER(mPvsObjects);
+        
+        DEL_PTR(mPreprocessor);
 }
 
@@ -29 +32 @@
         GtpVisibilityPreprocessor::Debug.open("debug.log");
         // HACK: get any preprocessor to load file
-        GtpVisibilityPreprocessor::Preprocessor *preprocessor = 
+        // note should be preserved to allow manual mesh reloading,
+        // but then geometry has to be stored two times
+        mPreprocessor = 
                 GtpVisibilityPreprocessor::PreprocessorFactory::CreatePreprocessor("vss");
 
         // hack
-        preprocessor->mLoadMeshes = false;
+        mPreprocessor->mLoadMeshes = false;
 
         Ogre::LogManager::getSingleton().logMessage("loading obj scene");
 
-        if (preprocessor->LoadScene(sceneName))
+        if (mPreprocessor->LoadScene(sceneName))
         {
                 Ogre::LogManager::getSingleton().logMessage("scene loaded, loading objects");
                 // form objects from the scene triangles
-                if (!preprocessor->LoadObjects(visibilitySolution, mPvsObjects, preprocessor->mObjects))
+                if (!mPreprocessor->LoadObjects(visibilitySolution, mPvsObjects, mPreprocessor->mObjects))
                 {
                         Ogre::LogManager::getSingleton().logMessage("objects cannot be loaded");
@@ -54 +59 @@
 
         std::stringstream d; 
-        d << "successfully loaded " << mPvsObjects.size() << " objects from " << preprocessor->mObjects.size() << " preprocessor objects";
+        d << "successfully loaded " << (int)mPvsObjects.size() 
+          << " objects from " << (int)mPreprocessor->mObjects.size() << " preprocessor objects";
 
         Ogre::LogManager::getSingleton().logMessage(d.str());
@@ -65 +71 @@
                 if (i % 5000 == 4999)
                 {
-                        d << i << " objects created" << endl;
+                        d << i << " objects created";
+                        Ogre::LogManager::getSingleton().logMessage(d.str());
                 }
         
@@ -84 +91 @@
         }
 
-        delete preprocessor;
+        //delete preprocessor;
 
         return true;

GTP/trunk/Lib/Vis/Preprocessing/scripts/preprocess_visibility.sh

@@ -1 +1 @@
 #!/bin/sh
 
-PREPROCESSOR=../bin/release/preprocessor.exe
-#PREPROCESSOR=../bin/debug/preprocessor.exe
+#PREPROCESSOR=../bin/release/preprocessor.exe
+PREPROCESSOR=../bin/debug/preprocessor.exe
 
 if [ $# -ne 3 ]

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

@@ -209 +209 @@
 int
 AxisAlignedBox3::ComputeMinMaxT(const Ray &ray,
-                                float *tmin,
-                                float *tmax) const
+                                                                float *tmin,
+                                                                float *tmax) const
 {
   float minx, maxx, miny, maxy, minz, maxz;
@@ -301 +301 @@
 int
 AxisAlignedBox3::ComputeMinMaxT(const Ray &ray,
-                                float *tmin,
-                                float *tmax) const
+                                                                float *tmin,
+                                                                float *tmax) const
 {
   const float dirEps = 1e-8f;
@@ -396 +396 @@
 // of intersection with the ray; it returns 1 if the ray hits
 // the bounding box and 0 if it does not.
-int
-AxisAlignedBox3::ComputeMinMaxT(const Ray &ray, float *tmin, float *tmax,
-                                EFaces &entryFace, EFaces &exitFace) const
+int AxisAlignedBox3::ComputeMinMaxT(const Ray &ray, float *tmin, float *tmax,
+                                                                        EFaces &entryFace, EFaces &exitFace) const
 {
   float minx, maxx, miny, maxy, minz, maxz;
@@ -532 +531 @@
 
 // computes the signed distances for case tmin<tmax and tmax>0
-int
-AxisAlignedBox3::GetMinMaxT(const Ray &ray, float *tmin, float *tmax,
-                            EFaces &entryFace, EFaces &exitFace) const
+int AxisAlignedBox3::GetMinMaxT(const Ray &ray, 
+                                                                float *tmin, 
+                                                                float *tmax,
+                                                                EFaces &entryFace,
+                                                                EFaces &exitFace) const
 {
   if (!ComputeMinMaxT(ray, tmin, tmax, entryFace, exitFace))
@@ -583 +584 @@
       b.mMax.y <= mMax.y &&
       b.mMax.z <= mMax.z);
-
 }
 
 
 // compute the coordinates of one vertex of the box
-Vector3
-AxisAlignedBox3::GetVertex(int xAxis, int yAxis, int zAxis) const
+Vector3 AxisAlignedBox3::GetVertex(int xAxis, int yAxis, int zAxis) const
 {
   Vector3 p;
@@ -2389 +2388 @@
  }
 
-/*
-int inline GetIntersection(const float fDst1, 
-                                                   const float fDst2, 
-                                                   const Vector3 p1, 
-                                                   const Vector3 p2, 
-                                                   const Vector3 &hit) 
-{
-        if ((fDst1 * fDst2) >= 0.0f) 
-                return 0;
-    
-        if (fDst1 == fDst2) 
-                return 0; 
-    
-        hit = p1 + (p2 - p1) * (-fDst1 / (fDst2 - fDst1));
-        
-        return 1;
-}
-
-
-int inline InBox( CVec3 Hit, CVec3 B1, CVec3 B2, const int Axis) {
-if ( Axis==1 && Hit.z > B1.z && Hit.z < B2.z && Hit.y > B1.y && Hit.y < B2.y) return 1;
-if ( Axis==2 && Hit.z > B1.z && Hit.z < B2.z && Hit.x > B1.x && Hit.x < B2.x) return 1;
-if ( Axis==3 && Hit.x > B1.x && Hit.x < B2.x && Hit.y > B1.y && Hit.y < B2.y) return 1;
-return 0;
-}
-
-// returns true if line (L1, L2) intersects with the box (B1, B2)
-// returns intersection point in Hit
-int CheckLineBox( CVec3 B1, CVec3 B2, CVec3 L1, CVec3 L2, CVec3 &Hit)
-{
-if (L2.x < B1.x && L1.x < B1.x) return false;
-if (L2.x > B2.x && L1.x > B2.x) return false;
-if (L2.y < B1.y && L1.y < B1.y) return false;
-if (L2.y > B2.y && L1.y > B2.y) return false;
-if (L2.z < B1.z && L1.z < B1.z) return false;
-if (L2.z > B2.z && L1.z > B2.z) return false;
-if (L1.x > B1.x && L1.x < B2.x &&
-    L1.y > B1.y && L1.y < B2.y &&
-    L1.z > B1.z && L1.z < B2.z) 
-    {Hit = L1; 
-    return true;}
-if ( (GetIntersection( L1.x-B1.x, L2.x-B1.x, L1, L2, Hit) && InBox( Hit, B1, B2, 1 ))
-  || (GetIntersection( L1.y-B1.y, L2.y-B1.y, L1, L2, Hit) && InBox( Hit, B1, B2, 2 )) 
-  || (GetIntersection( L1.z-B1.z, L2.z-B1.z, L1, L2, Hit) && InBox( Hit, B1, B2, 3 )) 
-  || (GetIntersection( L1.x-B2.x, L2.x-B2.x, L1, L2, Hit) && InBox( Hit, B1, B2, 1 )) 
-  || (GetIntersection( L1.y-B2.y, L2.y-B2.y, L1, L2, Hit) && InBox( Hit, B1, B2, 2 )) 
-  || (GetIntersection( L1.z-B2.z, L2.z-B2.z, L1, L2, Hit) && InBox( Hit, B1, B2, 3 )))
-        return true;
-
-return false;
-}
-*/
-
-}
-
+
+bool AxisAlignedBox3::Intersects(const Vector3 &lStart, 
+                                                                 const Vector3 &lEnd) const
+{
+   float st, et, fst = 0, fet = 1;
+   float const *bmin = &mMin.x;
+   float const *bmax = &mMax.x;
+   float const *si = &lStart.x;
+   float const *ei = &lEnd.x;
+
+   for (int i = 0; i < 3; ++ i) 
+   {
+      if (*si < *ei) 
+          {
+                  if (*si > *bmax || *ei < *bmin)
+                          return false;
+
+         const float di = *ei - *si;
+                 
+                 st = (*si < *bmin)? (*bmin - *si) / di : 0;
+         et = (*ei > *bmax)? (*bmax - *si) / di : 1;
+      }
+          else 
+          {
+                  if (*ei > *bmax || *si < *bmin)
+                          return false;
+                  
+                  const float di = *ei - *si;
+                  
+                  st = (*si > *bmax)? (*bmax - *si) / di : 0;
+                  et = (*ei < *bmin)? (*bmin - *si) / di : 1;
+      }
+
+      if (st > fst) fst = st;
+      if (et < fet) fet = et;
+      if (fet < fst)
+                  return false;
+          
+          ++ bmin; ++ bmax;
+      ++ si; ++ ei;
+   }
+
+   //*time = fst;
+   return true;
+}
+
+}
+

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

@@ -72 +72 @@
   void Reduce(int axis, int right, float value); 
   
+  bool Intersects(const Vector3 &lStart, const Vector3 &lEnd) const;
 
   // the size of the box along all the axes
@@ -93 +94 @@
   void Include(const int &axis, const float &newBound);
 
-
-  int
-  Side(const Plane3 &plane) const;
+  int Side(const Plane3 &plane) const;
 
   // Overlap returns 1 if the two axis-aligned boxes overlap .. even weakly
@@ -121 +120 @@
   bool Includes(const AxisAlignedBox3 &b) const;
 
+  /** Returns true if this point is inside box.
+  */
   virtual int IsInside(const Vector3 &v) const;
   
+  /** Returns true if start and endpoint of the ray is inside box.
+  */
   virtual int IsInside(const VssRay &v) const;
 
@@ -203 +206 @@
   // Returns the intersection of two axis-aligned boxes.
   friend inline AxisAlignedBox3 Intersect(const AxisAlignedBox3 &x,
-                                 const AxisAlignedBox3 &y);
+                                                                                  const AxisAlignedBox3 &y);
 
   // Given 4x4 matrix, transform the current box to new one.
   friend inline AxisAlignedBox3 Transform(const AxisAlignedBox3 &box,
-                                          const Matrix4x4 &tform);
+                                                                                  const Matrix4x4 &tform);
 
   
   // returns true when two boxes are completely equal
-  friend inline int operator== (const AxisAlignedBox3 &A, const AxisAlignedBox3 &B);
+  friend inline int operator== (const AxisAlignedBox3 &A, 
+                                                                const AxisAlignedBox3 &B);
   
   virtual float SurfaceArea() const;
-  virtual float GetVolume() const {
-    return (mMax.x - mMin.x) * (mMax.y - mMin.y) * (mMax.z - mMin.z);
+  virtual float GetVolume() const 
+  {
+          return (mMax.x - mMin.x) * (mMax.y - mMin.y) * (mMax.z - mMin.z);
   }
 
   // Six faces are distuinguished by their name.
-  enum EFaces { ID_Back = 0, ID_Left = 1, ID_Bottom = 2, ID_Front = 3,
-                ID_Right = 4, ID_Top = 5};
-  
-  int
-  ComputeMinMaxT(const Vector3 &origin,
-                                 const Vector3 &direction,
-                                 float *tmin,
-                                 float *tmax) const;
+  enum EFaces {ID_Back = 0, 
+                           ID_Left = 1, 
+                           ID_Bottom = 2, 
+                           ID_Front = 3,
+                           ID_Right = 4, 
+                           ID_Top = 5};
+  
+  int  ComputeMinMaxT(const Vector3 &origin,
+                                          const Vector3 &direction,
+                                          float *tmin,
+                                          float *tmax) const;
         
   // Compute tmin and tmax for a ray, whenever required .. need not pierce box
@@ -243 +251 @@
   // computes the signed distances for case: tmin < tmax and tmax > 0
   int GetMinMaxT(const Ray &ray, float *tmin, float *tmax,
-                 EFaces &entryFace, EFaces &exitFace) const;
+                                 EFaces &entryFace, EFaces &exitFace) const;
   
   // Writes a brief description of the object, indenting by the given

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

@@ -335 +335 @@
         Debug << "use surface area heuristics: " << mUseSah << endl;
         Debug << "subdivision stats log: " << subdivisionStatsLog << endl;
-        Debug << "split borders: " << mSplitBorder << endl;
+        //Debug << "split borders: " << mSplitBorder << endl;
         Debug << "render cost decrease weight: " << mRenderCostDecreaseWeight << endl;
         Debug << "use global sort: " << mUseGlobalSorting << endl;
@@ -1439 +1439 @@
         if (sortEntries)
         {       // no presorted candidate list
-                //stable_sort((*subdivisionCandidates)->begin(), (*subdivisionCandidates)->end());
-                sort((*subdivisionCandidates)->begin(), (*subdivisionCandidates)->end());
+                stable_sort((*subdivisionCandidates)->begin(), (*subdivisionCandidates)->end());
+                //sort((*subdivisionCandidates)->begin(), (*subdivisionCandidates)->end());
         }
 }

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

@@ -1009 +1009 @@
         int mCreatedLeaves;
         /// represents min and max band for sweep
-        float mSplitBorder;
+        //float mSplitBorder;
         /// weight between render cost decrease and node render cost
         float mRenderCostDecreaseWeight;

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

@@ -1378 +1378 @@
 
         RegisterOption("ViewCells.type",
-                        optString,
-                        "view_cells_type=",
-                        "vspBspTree");
+                                        optString,
+                                        "view_cells_type=",
+                                        "vspBspTree");
 
         RegisterOption("ViewCells.samplingType",
-                        optString,
-                        "view_cells_sampling_type=",
-                        "box");
+                                        optString,
+                                        "view_cells_sampling_type=",
+                                        "box");
 
         RegisterOption("ViewCells.mergeStats",
@@ -2182 +2182 @@
 
         RegisterOption("VspBspTree.Termination.AxisAligned.maxCostRatio",
-                optFloat,
-                "vsp_bsp_term_axis_aligned_max_cost_ratio=",
-                "1.5");
+                                        optFloat,
+                                        "vsp_bsp_term_axis_aligned_max_cost_ratio=",
+                                        "1.5");
 
         RegisterOption("VspBspTree.useCostHeuristics",
-                optBool,
-                "vsp_bsp_use_cost_heuristics=",
-                "false");
+                                        optBool,
+                                        "vsp_bsp_use_cost_heuristics=",
+                                        "false");
 
         RegisterOption("VspBspTree.Termination.maxViewCells",
-                optInt,
-                "vsp_bsp_term_max_view_cells=",
-                "10000");
+                                        optInt,
+                                        "vsp_bsp_term_max_view_cells=",
+                                        "10000");
 
         RegisterOption("VspBspTree.Termination.maxCostRatio",
-                optFloat,
-                "vsp_bsp_term_max_cost_ratio=",
-                "1.5");
+                                        optFloat,
+                                        "vsp_bsp_term_max_cost_ratio=",
+                                        "1.5");
 
         RegisterOption("VspBspTree.Termination.missTolerance",
-                optInt,
-                "vsp_bsp_term_miss_tolerance=",
-                "4");
+                                        optInt,
+                                        "vsp_bsp_term_miss_tolerance=",
+                                        "4");
 
         RegisterOption("VspBspTree.splitPlaneStrategy",
@@ -2785 +2785 @@
                                         "99990.0");
         
+
+        ///////////////////////////////////////////////////////
+
+         RegisterOption("TraversalTree.Termination.minCost",
+                                 optInt,
+                                 "kd_term_min_cost=",
+                                 "1");
+  
+  RegisterOption("TraversalTree.Termination.maxNodes",
+                                 optInt,
+                                 "kd_term_max_nodes=",
+                                 "200000");
+  
+  RegisterOption("TraversalTree.Termination.maxDepth",
+                                 optInt,
+                                 "kd_term_max_depth=",
+                                 "20");
+
+  RegisterOption("TraversalTree.Termination.maxCostRatio",
+                                 optFloat,
+                                 "kd_term_max_cost_ratio=",
+                                 "1.5");
+
+  RegisterOption("TraversalTree.Termination.ct_div_ci",
+                                 optFloat,
+                                 "kd_term_ct_div_ci=",
+                                 "1.0");
+
+  RegisterOption("TraversalTree.splitMethod",
+                                 optString,
+                                 "kd_split_method=",
+                                 "spatialMedian");
+
+  RegisterOption("TraversalTree.splitBorder",
+                                 optFloat,
+                                 "kd_split_border=",
+                                 "0.1");
+
+  RegisterOption("TraversalTree.sahUseFaces",
+                                 optBool,
+                                 "kd_sah_use_faces=",
+                                 "true");
+
         /////////////////////////////////////////////////////////////////
 

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

@@ -7 +7 @@
 #include "Triangle3.h"
 #include "Polygon3.h"
+#include "TraversalTree.h"
 
 
@@ -305 +306 @@
 
 
-
-}
+bool Exporter::ExportTraversalTree(const TraversalTree &tree, 
+                                                                          const bool exportGeometry)
+{
+        stack<TraversalNode *> tStack;
+
+        tStack.push(tree.GetRoot());
+
+        Mesh *mesh = new Mesh;
+
+        SetWireframe();
+
+        while (!tStack.empty()) 
+        {
+                TraversalNode *node = tStack.top();
+                tStack.pop();
+                const AxisAlignedBox3 box = tree.GetBox(node);
+
+                // add 6 vertices of the box
+                const int index = (int)mesh->mVertices.size();
+
+                SetForcedMaterial(RandomMaterial());
+
+                for (int i=0; i < 8; i++) 
+                {
+                        Vector3 v;
+                        box.GetVertex(i, v);
+                        mesh->mVertices.push_back(v);
+                }
+
+                mesh->AddFace(new Face(index + 0, index + 1, index + 3, index + 2) );
+                mesh->AddFace(new Face(index + 0, index + 2, index + 6, index + 4) );
+                mesh->AddFace(new Face(index + 4, index + 6, index + 7, index + 5) );
+
+                mesh->AddFace(new Face(index + 3, index + 1, index + 5, index + 7) );
+                mesh->AddFace(new Face(index + 0, index + 4, index + 5, index + 1) );
+                mesh->AddFace(new Face(index + 2, index + 3, index + 7, index + 6) );
+
+                if (!node->IsLeaf()) 
+                {
+                        TraversalInterior *interior = static_cast<TraversalInterior *>(node);
+
+                        tStack.push(interior->mFront);
+                        tStack.push(interior->mBack);
+                }
+                else if (exportGeometry)
+                {
+                        SetFilled();
+                        SetForcedMaterial(RandomMaterial());
+
+                        ExportViewCells(static_cast<TraversalLeaf *>(node)->mViewCells);        
+                        SetWireframe();
+                }
+        }
+
+        ExportMesh(mesh);
+        delete mesh;
+
+        return true;
+}
+
+
+}

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

@@ -9 +9 @@
 #include "Material.h"
 #include "Containers.h"
-//#include "VssRay.h"
 #include "AxisAlignedBox3.h"
 
@@ -32 +31 @@
 class MeshInstance;
 class VssRay;
-//class Material;
+class TraversalTree;
+
 
 struct VssRayContainer;
@@ -64 +64 @@
   virtual bool
   ExportKdTree(const KdTree &tree, const bool exportGeometry = false) = 0;
+
+  virtual bool
+  ExportTraversalTree(const TraversalTree &tree, const bool exportViewCells);
 
   virtual bool

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

@@ -383 +383 @@
         }
 
-        // hack: should be different parameter name
+        // hack
         if (mUseMultiLevelConstruction)
         {
                 cout << "starting optimizing multilevel ... " << endl;
-                // try to optimize on the above hierarchy
+                // try to optimize the hierarchy from above
                 OptimizeMultiLevel(sampleRays, objects, forcedViewSpace);
                 
@@ -398 +398 @@
         }
 
-        if (0) CreateTraversalTree();
+        // create a traversal tree which is optimized for view cell casting 
+        if (1) 
+        {
+                CreateTraversalTree();
+        }
 }
 
@@ -2488 +2492 @@
 
         ViewCellContainer viewCells;
-
-        // add mesh instances of the scene graph to the root of the tree
-        TraversalLeaf *root = (TraversalLeaf *)mTraversalTree->GetRoot();
-
-        //mVspTree->CollectViewCells(root->mViewCells, false);
-        
-        const long startTime = GetTime();
+        mVspTree->CollectViewCells(viewCells, false);
+
+        const long startTime = GetTime();
+        
         cout << "building traversal tree ... " << endl;
 
-        mTraversalTree->Construct();
-
-        cout << "finished kd tree construction in " << TimeDiff(startTime, GetTime()) * 1e-3 
+        mTraversalTree->Construct(viewCells);
+
+        cout << "finished traversal tree construction in " << TimeDiff(startTime, GetTime()) * 1e-3 
                  << " secs " << endl;
+
+        Debug << "*** TraversalTree Stats ***" << endl;
+        Debug << mTraversalTree->GetStatistics() << endl;
+
+        if (1) 
+        {
+                Exporter *exporter = Exporter::GetExporter("traversal.wrl");
+                exporter->ExportTraversalTree(*mTraversalTree, true);
+                delete exporter;
+        }
 }
 
@@ -2510 +2521 @@
 {
         if (!mTraversalTree)
+        {
                 return mVspTree->CastLineSegment(origin,termination, viewcells, useMailboxing);
+        }
         else
+        {
                 return mTraversalTree->CastLineSegment(origin,termination, viewcells, useMailboxing);
-}
-
-
-}
+        }
+}
+
+
+}

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

@@ -188 +188 @@
 class HierarchyManager
 {
+        friend class VspOspViewCellsManager;
+
 public:
+        
         /** Constructor with the view space partition tree and
                 the object space hierarchy type as argument.
         */
         HierarchyManager(const int objectSpaceHierarchyType);
+        
         /** Hack: OspTree will copy the content from this kd tree.
                 Only view space hierarchy will be constructed.

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

@@ -188 +188 @@
  
         if (criteriaMet)
-                cerr<<"\n OBJECTS="<<leaf->mObjects.size()<<endl;
+                cerr<<"\n OBJECTS="<<(int)leaf->mObjects.size()<<endl;
 
         return criteriaMet;

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

@@ -186 +186 @@
         for (int i=0; i < contributingRays; i++, index--) {
           if (index < 0)
-                index = mRays.size()-1;
+                index = (int)mRays.size()-1;
           mRays[index].mImportance = importance;
         }
@@ -196 +196 @@
   // reset the start of the buffer
   mBufferStart = 0;
-  mLastIndex = mRays.size();
+  mLastIndex = (int)mRays.size();
   cout<<"Mutation candidates sorted in "<<TimeDiff(t1, GetTime())<<" ms."<<endl;
 #endif
@@ -214 +214 @@
   cout<<"Importance = "<<
         GetEntry(0).mImportance<<" "<<
-        GetEntry(mRays.size()-1).mImportance<<endl;
+        GetEntry((int)mRays.size()-1).mImportance<<endl;
 
   cout<<"Sampling factor = "<<
         GetEntry(0).GetSamplingFactor()<<" "<<
-        GetEntry(mRays.size()-1).GetSamplingFactor()<<endl;
+        GetEntry((int)mRays.size()-1).GetSamplingFactor()<<endl;
 
   cerr<<"Mutation update done."<<endl;
@@ -564 +564 @@
   index = mLastIndex - 1;
   if (index < 0 || index >= mRays.size()-1) {
-        index = mRays.size() - 1;
+        index = (int)mRays.size() - 1;
   } else
         if (
@@ -573 +573 @@
           //      cout<<mLastIndex<<endl;
           //      cout<<index<<endl;
-          index = mRays.size() - 1;
+          index = (int)mRays.size() - 1;
         }
 #else

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

@@ -40 +40 @@
   mz.SetColumns(sx, sy, sd);
   
-  double det = md.Det3x3();
+  const float det = md.Det3x3();
 
   if (abs(det)<TRASH)
@@ -46 +46 @@
 
   result.SetValue(mx.Det3x3()/det,
-                  my.Det3x3()/det,
-                  mz.Det3x3()/det);
+                                  my.Det3x3()/det,
+                                  mz.Det3x3()/det);
   
   return true;

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

@@ -747 +747 @@
                 if (0) LoadObjects(buf, pvsObjects, mObjects);
 
+                const bool finalizeViewCells = true;
                 cout << "loading view cells from " << buf << endl;
 
@@ -752 +753 @@
                                                                                                                         pvsObjects,
                                                                                                                         mObjects, 
-                                                                                                                        true, 
+                                                                                                                        finalizeViewCells, 
                                                                                                                         NULL);
 
@@ -1366 +1367 @@
         
                 if ((int)rays.size() > 100000 && i % 100000 == 0)
-                        //cout << "here2 " << vssRays.size()<<endl;
                         cout<<"\r"<<i<<"/"<<(int)rays.size()<<"\r";
         }

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

@@ -14 +14 @@
 Preprocessor *PreprocessorFactory::CreatePreprocessor(const string &preprocessorType)
 {
-        Debug << "here9191" << endl;
         if (preprocessorType == "vss")
-        {Debug << "here21112" << endl;
+        {
                 return new VssPreprocessor();
         }

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

@@ -7 +7 @@
 #include "ViewCell.h"
 #include "Beam.h"
+#include "Exporter.h"
 
 
@@ -59 +60 @@
 
 
-void TraversalInterior::ReplaceChildLink(TraversalNode *oldChild, TraversalNode *newChild) 
+void TraversalInterior::ReplaceChildLink(TraversalNode *oldChild, 
+                                                                                 TraversalNode *newChild) 
 {
         if (mBack == oldChild)
@@ -71 +73 @@
 TraversalNode(parent)
 {
-        mObjects.reserve(objects);
+        mViewCells.reserve(objects);
 }
 
@@ -88 +90 @@
 TraversalTree::TraversalTree()
 { 
-        mRoot = new TraversalLeaf(NULL, 0);
+        TraversalLeaf *leaf = new TraversalLeaf(NULL, 0);
+        leaf->mDepth = 0;
+        mRoot = leaf;
 
         Environment::GetSingleton()->GetIntValue("TraversalTree.Termination.maxNodes", mTermMaxNodes);
@@ -102 +106 @@
         Environment::GetSingleton()->GetStringValue("TraversalTree.splitMethod", splitType);
 
+        splitCandidates = NULL;
         mSplitMethod = SPLIT_SPATIAL_MEDIAN;
+
         if (strcmp(splitType, "spatialMedian") == 0)
         {
@@ -121 +127 @@
                         else 
                         {
-                                cerr<<"Wrong kd split type "<<splitType<<endl;
+                                cerr << "Wrong kd split type " << splitType << endl;
                                 exit(1);
                         }
-                        
-                        splitCandidates = NULL;
-                }
-        }
+                }
+        }
+        cout << "Traversal Tree Split method: " << mSplitMethod << endl;
 }
 
@@ -137 +142 @@
 
 
-bool
-TraversalTree::Construct()
-{
-
+bool TraversalTree::Construct(const ViewCellContainer &viewCells)
+{
         if (!splitCandidates)
         {
@@ -149 +152 @@
         TraversalLeaf *leaf = static_cast<TraversalLeaf *>(mRoot);
 
+        leaf->mViewCells = viewCells;
         mStat.nodes = 1;
-
         mBox.Initialize();
 
-        ObjectContainer::const_iterator mi;
-        for ( mi = leaf->mObjects.begin(); mi != leaf->mObjects.end(); ++ mi) 
+        ViewCellContainer::const_iterator mi;
+
+        for ( mi = leaf->mViewCells.begin(); mi != leaf->mViewCells.end(); ++ mi) 
         {
                 mBox.Include((*mi)->GetBox());
@@ -163 +167 @@
         
         // remove the allocated array
-        CLEAR_CONTAINER(*splitCandidates);
-        delete splitCandidates;
-
+        if (splitCandidates)
+        {
+                CLEAR_CONTAINER(*splitCandidates);
+                delete splitCandidates;
+        }
+        
         return true;
 }
@@ -182 +189 @@
         while (!tStack.empty()) 
         {
-                //      cout<<mStat.Nodes() << " " << mTermMaxNodes << endl;
                 if (mStat.Nodes() > mTermMaxNodes) 
                 {
@@ -226 +232 @@
 bool TraversalTree::TerminationCriteriaMet(const TraversalLeaf *leaf)
 {
-        const bool criteriaMet =
-                ((int)leaf->mObjects.size() <= mTermMinCost) ||
-                (leaf->mDepth >= mTermMaxDepth);
+        const bool criteriaMet = (
+                ((int)leaf->mViewCells.size() <= mTermMinCost) ||
+                 (leaf->mDepth >= mTermMaxDepth) 
+                 || (GetBox(leaf).SurfaceArea() < 0.00001f)
+                 );
 
         if (criteriaMet)
-                cerr<< "\n OBJECTS=" << (int)leaf->mObjects.size() << endl;
+        {
+                cerr << "\nOBJECTS=" << (int)leaf->mViewCells.size() << endl;
+                cerr << "\nDEPTH=" << (int)leaf->mDepth << endl;
+        }
 
         return criteriaMet;
@@ -248 +259 @@
                 {
                         axis = box.Size().DrivingAxis();
-                        position = (box.Min()[axis] + box.Max()[axis])*0.5f;
+                        position = (box.Min()[axis] + box.Max()[axis]) * 0.5f;
                         break;
                 }
@@ -254 +265 @@
                 {
                         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 costRatio = 99999;//MAX_FLOAT;
+
+                        for (int i=0; i < 3; ++ i) 
+                        {
+                                float p;
+                                float r = BestCostRatio(leaf,
+                                                                                box,
+                                                                                i,
+                                                                                p,
+                                                                                objectsBack,
+                                                                                objectsFront);
+        
+                                if (r < costRatio) 
                                 {
-                                        float p;
-                                        float r = BestCostRatio(leaf,
-                                                box,
-                                                i,
-                                                p,
-                                                objectsBack,
-                                                objectsFront);
-        
-                                        if (r < costRatio) 
-                                        {
-                                                costRatio = r;
-                                                axis = i;
-                                                position = p;
-                                        }
+                                        costRatio = r;
+                                        axis = i;
+                                        position = p;
                                 }
                         }
@@ -292 +287 @@
                         if (costRatio > mMaxCostRatio) 
                         {
-                                //cout<<"Too big cost ratio "<<costRatio<<endl;
+                                cout << "Too big cost ratio " << costRatio << endl;
                                 axis = -1;
                         }
@@ -318 +313 @@
 
         if (axis == -1) {
+                cout << "terminate on cost ratio" << endl;
                 return leaf;
         }
@@ -341 +337 @@
         frontBBox.SetMin(axis, position);
 
-        ObjectContainer::const_iterator mi;
-
-        for ( mi = leaf->mObjects.begin();
-                mi != leaf->mObjects.end();
-                mi++)
+        ViewCellContainer::const_iterator mi, mi_end = leaf->mViewCells.end();
+
+        for (mi = leaf->mViewCells.begin(); mi != mi_end; ++ mi)
         {
                 // determine the side of this ray with respect to the plane
                 AxisAlignedBox3 box = (*mi)->GetBox();
-                if (box.Max(axis) > position ) 
-                        objectsFront++;
-
-                if (box.Min(axis) < position )
+                if (box.Max(axis) > position) 
+                        ++ objectsFront;
+
+                if (box.Min(axis) < position)
                         ++ objectsBack;
         }
-
 
         TraversalLeaf *back = new TraversalLeaf(node, objectsBack);
         TraversalLeaf *front = new TraversalLeaf(node, objectsFront);
 
+        back->mDepth = front->mDepth = leaf->mDepth + 1;
 
         // replace a link from node's parent
@@ -370 +364 @@
         node->SetupChildLinks(back, front);
 
-        for (mi = leaf->mObjects.begin(); mi != leaf->mObjects.end(); ++ mi) 
+        for (mi = leaf->mViewCells.begin(); mi != mi_end; ++ mi) 
         {
                 // determine the side of this ray with respect to the plane
@@ -377 +371 @@
                 if (box.Max(axis) >= position )
                 {
-                        front->mObjects.push_back(*mi);
+                        front->mViewCells.push_back(*mi);
                 }
 
                 if (box.Min(axis) < position )
                 {
-                        back->mObjects.push_back(*mi);
-                }
-
-                mStat.objectRefs -= (int)leaf->mObjects.size();
+                        back->mViewCells.push_back(*mi);
+                }
+
+                mStat.objectRefs -= (int)leaf->mViewCells.size();
                 mStat.objectRefs += objectsBack + objectsFront;
         }
@@ -404 +398 @@
 
         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";
+
+        for (int i = 0; i < 7; ++ i)
+                app << splits[i] << " ";
+        app << endl;
 
         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_AVGOBJECTREFS  ( Avg number of object refs / leaf )\n" <<
+                totalObjectRefs / (double)Leaves() << "\n";
 
         app << "#N_LEAFDOMAINREFS  ( Number of query domain Refs / leaf )\n" <<
-                objectRefs/(double)Leaves() << "\n";
+                objectRefs / (double)Leaves() << "\n";
+
+        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 << 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";
-
+        app << "======= END OF TraversalTree statistics ========\n";
 }
 
@@ -455 +431 @@
 void TraversalTree::EvaluateLeafStats(const TraversalData &data)
 {
-
-  // the node became a leaf -> evaluate stats for leafs
-  TraversalLeaf *leaf = (TraversalLeaf *)data.mNode;
-
-  if (data.mDepth > mTermMaxDepth)
-    mStat.maxDepthNodes++;
-  
-  if ( (int)(leaf->mObjects.size()) < mTermMinCost)
-    mStat.minCostNodes++;
-  
-  
-  if ( (int)(leaf->mObjects.size()) > mStat.maxObjectRefs)
-    mStat.maxObjectRefs = (int)leaf->mObjects.size();
-  
-}
-
+        // the node became a leaf -> evaluate stats for leafs
+        TraversalLeaf *leaf = (TraversalLeaf *)data.mNode;
+
+        if (data.mDepth > mTermMaxDepth)
+                ++ mStat.maxDepthNodes;
+
+        if ((int)(leaf->mViewCells.size()) < mTermMinCost)
+                ++ mStat.minCostNodes;
+
+        mStat.totalObjectRefs += (int)leaf->mViewCells.size();
+
+        if ((int)(leaf->mViewCells.size()) > mStat.maxObjectRefs)
+                mStat.maxObjectRefs = (int)leaf->mViewCells.size();
+}
 
 
@@ -480 +454 @@
         //splitCandidates->clear();
 
-    int requestedSize = 2*(int)node->mObjects.size();
+    int requestedSize = 2 * (int)node->mViewCells.size();
         
         // creates a sorted split candidates array
         if (splitCandidates->capacity() > 500000 &&
-                requestedSize < (int)(splitCandidates->capacity()/10) ) 
+                requestedSize < (int)(splitCandidates->capacity() / 10) ) 
         {               
                 delete splitCandidates;
@@ -492 +466 @@
         splitCandidates->reserve(requestedSize);
 
+        
         // insert all queries 
-        for(ObjectContainer::const_iterator mi = node->mObjects.begin();
-                mi != node->mObjects.end();
+        for(ViewCellContainer::const_iterator mi = node->mViewCells.begin();
+                mi != node->mViewCells.end();
+                mi++) 
+        {
+                AxisAlignedBox3 box = (*mi)->GetBox();
+
+                splitCandidates->push_back(new SortableEntry(SortableEntry::BOX_MAX,
+                        box.Max(axis),
+                        *mi)
+                        );
+        }
+
+        // insert all queries 
+        for(ViewCellContainer::const_iterator mi = node->mViewCells.begin();
+                mi != node->mViewCells.end();
                 mi++) 
         {
@@ -503 +491 @@
                         *mi)
                         );
-
-                splitCandidates->push_back(new SortableEntry(SortableEntry::BOX_MAX,
+                /*splitCandidates->push_back(new SortableEntry(SortableEntry::BOX_MAX,
                         box.Max(axis),
                         *mi)
-                        );
+                        );*/
         }
 
@@ -550 +537 @@
         // 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();
+        int objectsLeft = 0, objectsRight = (int)node->mViewCells.size();
+
+        int dummy1 = objectsLeft, dummy2 = objectsRight;
 
         float minBox = box.Min(axis);
@@ -578 +557 @@
                 {
                 case SortableEntry::BOX_MIN:
-                        objectsLeft++;
-                        intersectionsLeft += (*ci)->intersectable->IntersectionComplexity();
+                        ++ objectsLeft;
                         break;
                 case SortableEntry::BOX_MAX:
-                        objectsRight--;
-                        intersectionsRight -= (*ci)->intersectable->IntersectionComplexity();
+                        -- objectsRight;
                         break;
                 }
 
-                if ((*ci)->value > minBand && (*ci)->value < maxBand) 
+                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;
+                        const float 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 oldCost = (float)node->mViewCells.size();
                                 float newCost = mCt_div_ci + sum/boxArea;
-                                float ratio = newCost/oldCost;
+                                float ratio = newCost / oldCost;
                                 costStream<<(*ci)->value<<" "<<ratio<<endl;
                         }
@@ -625 +598 @@
         }
 
-        const float oldCost = mSahUseFaces ? totalIntersections : node->mObjects.size();
-        const float newCost = mCt_div_ci + minSum/boxArea;
-        const float ratio = newCost/oldCost;
-
+        const float oldCost = (float)node->mViewCells.size();
+        const float newCost = mCt_div_ci + minSum / boxArea;
+        const float ratio = newCost / oldCost;
+
+        //if (boxArea == 0)
+        //      cout << "error: " << boxArea << endl;
+        if (ratio > 2)
+        {
+                cout << "costratio: " << ratio << " oldcost: " << oldCost << " box area: " << boxArea << " new: " << newCost << endl;
+                cout << "obj left: " <<objectsBack<< " obj right: " << objectsFront << endl;
+                cout << "dummy1: " << dummy1 << " dummy2: " << dummy2 << endl;
+        }
 #if 0
         cout<<"===================="<<endl;
@@ -634 +615 @@
                         <<"\t o=("<<objectsBack<<","<<objectsFront<<")"<<endl;
 #endif
+
         return ratio;
+}
+
+
+int TraversalTree::FindViewCellIntersections(const Vector3 &lStart, 
+                                                                                         const Vector3 &lEnd,
+                                                                                         const ViewCellContainer &viewCells,
+                                                                                         ViewCellContainer &hitViewCells,
+                                                                                         const bool useMailboxing)
+{
+        int hits = 0;
+        ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
+
+        for (vit = viewCells.begin(); vit != vit_end; ++ vit)
+        {
+                ViewCell *viewCell = *vit;
+                // don't have to mail if each view cell belongs to exactly one leaf
+                if (!useMailboxing || !viewCell->Mailed())
+                {
+                        if (useMailboxing)
+                viewCell->Mail();
+
+                        // hack: assume that we use vsp tree, 
+                        //P so we can just test intersection with bounding boxes
+                        if (viewCell->GetBox().Intersects(lStart, lEnd));
+                        {
+                                hitViewCells.push_back(viewCell);
+                                ++ hits;
+                        }
+                }
+        }
+
+        return hits;
 }
 
@@ -640 +654 @@
 int TraversalTree::CastLineSegment(const Vector3 &origin,
                                                                    const Vector3 &termination,
-                                                                   ViewCellContainer &viewcells,
+                                                                   ViewCellContainer &viewCells,
                                                                    const bool useMailboxing)
 {
@@ -709 +723 @@
                         // compute intersection with all objects in this leaf
                         TraversalLeaf *leaf = static_cast<TraversalLeaf *>(node);
-                        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;
-                        }
-
+
+                        hits += FindViewCellIntersections(origin, 
+                                                                                          termination, 
+                                                                                          leaf->mViewCells,
+                                                                                          viewCells,
+                                                                                          useMailboxing);
+                        
                         // get the next node from the stack
                         if (tStack.empty())

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

@@ -8 +8 @@
 #include "AxisAlignedBox3.h"
 #include "Ray.h"
-//#include "ObjectPvs.h"
-//#include "Viewcell.h"
-//#include "VssRay.h"
-//#include "IntersectableWrapper.h"
 
 
@@ -25 +21 @@
 class TraversalTree;
   
-//  TraversalTree *SceneTraversalTree;
 
 // --------------------------------------------------------------
@@ -55 +50 @@
   // max number of rays per node
   int maxObjectRefs;
+  // max number of rays per node
+  int totalObjectRefs;
   // number of dynamically added ray refs
   int addedRayRefs;
@@ -83 +80 @@
           minCostNodes = 0;
           maxObjectRefs = 0;
+          totalObjectRefs = 0;
           addedRayRefs = removedRayRefs = 0;
   }
@@ -121 +119 @@
         }
 
-        /** Parent of the node - the parent is a little overhead for maintanance of the tree,
-                but allows various optimizations of tree traversal algorithms 
+        /** 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;
@@ -217 +216 @@
 
         // pointers to view cells contained in this node
-        ObjectContainer mObjects;
+        ViewCellContainer mViewCells;
 
         short mDepth;
@@ -237 +236 @@
                 float mPriority;
 
-                TraversalData() {}
+                TraversalData(): mNode(NULL), mPriority(0), mDepth(0) {}
 
                 TraversalData(TraversalNode *n, const float p):
-                mNode(n), mPriority(p)
+                mNode(n), mPriority(p), mDepth(0)
                 {}
 
                 TraversalData(TraversalNode *n,
-                        const AxisAlignedBox3 &b,
-                        const int d):
-                mNode(n), mBox(b), mDepth(d) {}
+                                          const AxisAlignedBox3 &b,
+                                          const int d):
+                mNode(n), mBox(b), mDepth(d) 
+                {}
 
 
@@ -255 +255 @@
                         
                         return 
-                                leafa->mObjects.size() * mBox.SurfaceArea()
+                                leafa->mViewCells.size() * mBox.SurfaceArea()
                                 <
-                                leafb->mObjects.size() * b.mBox.SurfaceArea();
+                                leafb->mViewCells.size() * b.mBox.SurfaceArea();
                 }
 
 
-                        // comparator for the 
-                        struct less_priority: public 
+                // comparator for the 
+                struct less_priority: public 
                                 binary_function<const TraversalData, const TraversalData, bool> 
+                {
+                        bool operator()(const TraversalData a, const TraversalData b) 
                         {
-                bool operator()(const TraversalData a, const TraversalData b) 
-                                {
-                                        return a.mPriority < b.mPriority;
-                                }
-            };
+                                return a.mPriority < b.mPriority;
+                        }
+                };
         };
 
@@ -292 +292 @@
                                                 const bool useMailboxing);
 
-        virtual bool Construct();
+        virtual bool Construct(const ViewCellContainer &viewCells);
 
         /** 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
+                the environment as well as the subdivision method. By default surface area
                 heuristics is used.
 
@@ -372 +372 @@
                 {}
 
-                bool operator<(const SortableEntry &b) const 
+                /*bool operator<(const SortableEntry &b) const 
                 {
+                        // view cells usually adjacent 
+                        if (EpsilonEqual(value, b.value, 0.001))
+                                return (type == BOX_MAX);
+                        
                         return value < b.value;
-                }
+                }*/
         };
 
         inline static bool iltS(SortableEntry *a, SortableEntry *b)
         {
+                // view cells usually adjacent 
+                //if (EpsilonEqual(a->value, b->value))
+                //      return false;
+                //      return (a->type == SortableEntry::BOX_MAX);
+                        
                 return a->value < b->value;
         }
@@ -409 +418 @@
                                         float &position);
 
+        int FindViewCellIntersections(const Vector3 &lStart, 
+                                                                  const Vector3 &lEnd,
+                                                                  const ViewCellContainer &viewCells,
+                                                                  ViewCellContainer &hitViewCells,
+                                                                  const bool useMailboxing);
 
         ////////////////////////

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

@@ -261 +261 @@
                                                         float &contribution)
 { 
-        const bool result = mPvs.AddSample(sample, pdf);//, contribution);
+        const bool result = mPvs.AddSample(sample, pdf);
         // have to recompute pvs size
         mPvsSizeValid = false;
@@ -2376 +2376 @@
                 Intersectable *obj = it.Next();
 
-                // hack: just output full pvs
+                // hack: just output all the "elementary" objects
                 if (0 && (obj->Type() == Intersectable::BVH_INTERSECTABLE))
                 {

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

@@ -203 +203 @@
         */
         void SetMesh(Mesh *mesh);
-
         /** Sets this view cell to be a valid view cell according to some criteria.
         */
@@ -291 +290 @@
         void SetFilteredPvsSize(const int s) {
                 mFilteredPvsSize = s;
-  }
+        }
+
+        //virtual int ViewCellType;
 
 protected:
@@ -321 +322 @@
         bool mPvsSizeValid;
 
-
         /// Filter cost of the pvs
         int mFilteredPvsSize;

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

@@ -1051 +1051 @@
                                                                                                    bconverter);
 
-        //Debug << " view cells parsed in "
-        //        << TimeDiff(startTime, GetTime()) * 1e-3f << " secs" << endl;
-        
-
         if (!success)
         {
@@ -1063 +1059 @@
         }
         
-        //cout << "viewcells parsed " <<endl;
-
         if (0)
         {
@@ -1090 +1084 @@
         if (finalizeViewCells)
         {
-                // create the meshes and compute volumes
+                // create the meshes and compute view cell volumes
                 const bool createMeshes = true;
-                //const bool createMeshes = false;
-
                 vm->FinalizeViewCells(createMeshes);
         }
@@ -7025 +7017 @@
 #endif
 
-
-
-}
+void VspOspViewCellsManager::FinalizeViewCells(const bool createMesh)
+{       
+        ViewCellsManager::FinalizeViewCells(createMesh);
+
+        if (1)
+        {       // create a traversal tree for optimal view cell casting
+                mHierarchyManager->CreateTraversalTree();
+        }
+}
+
+
+}

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

@@ -1288 +1288 @@
         float UpdateObjectCosts();
 
+        virtual void FinalizeViewCells(const bool createMesh);
+
 protected:
 

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

@@ -39 +39 @@
   ~VrmlExporter();
 
-
-//    bool
-//    ExportRays(const vector<Ray> &rays,
-//           const float length=1000,
-//           const RgbColor &color = RgbColor(1,1,1));
-
-
   bool
   ExportKdTree(const KdTree &tree, const bool exportGeometry = false);
-
-  //bool ExportOspTree(const OspTree &tree);
 
   bool
@@ -141 +132 @@
   void ExportViewpoint(const Vector3 &point, const Vector3 &direction);
 
+  //virtual bool ExportTraversalTree(const KdTree &tree, const bool exportViewCells);
 };
 

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

@@ -1341 +1341 @@
         }
 
-        sort(mLocalSubdivisionCandidates->begin(), mLocalSubdivisionCandidates->end());
+        stable_sort(mLocalSubdivisionCandidates->begin(), mLocalSubdivisionCandidates->end());
 }
 

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

@@ -1097 +1097 @@
         }
 
-        //stable_sort(mLocalSubdivisionCandidates->begin(), mLocalSubdivisionCandidates->end());
-        sort(mLocalSubdivisionCandidates->begin(), mLocalSubdivisionCandidates->end());
+        stable_sort(mLocalSubdivisionCandidates->begin(), mLocalSubdivisionCandidates->end());
+        //sort(mLocalSubdivisionCandidates->begin(), mLocalSubdivisionCandidates->end());
 }
 

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

@@ -827 +827 @@
                         
                 @param tData data object holding, e.g., a pointer to the leaf
-                @param frontData returns the data (e.g.,  pointer to the leaf) in front of the split plane
-                @param backData returns the data (e.g.,  pointer to the leaf) in the back of the split plane
+                @param frontData returns the data (e.g., pointer to the leaf) in front of the split plane
+                @param backData returns the data (e.g., pointer to the leaf) in the back of the split plane
                 
                 @param rays the polygons to be filtered

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

@@ -1211 +1211 @@
 
 
-}
-
+
+
+
+}
+

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

@@ -29 +29 @@
 class X3dExporter : public Exporter
 {
-  std::ofstream stream;
+        std::ofstream stream;
 
 public:
 
-  X3dExporter(const string filename);
+        X3dExporter(const string filename);
 
-  ~X3dExporter();
+        ~X3dExporter();
 
+        bool
+                ExportKdTree(const KdTree &tree, const bool exportGeometry = false);
 
-//    bool
-//    ExportRays(const vector<Ray> &rays,
-//           const float length=1000,
-//           const RgbColor &color = RgbColor(1,1,1));
+        bool
+                ExportVssTree(const VssTree &tree);
 
+        bool
+                ExportVssTree2(const VssTree &tree,
+                const Vector3 direction);
 
-  bool
-  ExportKdTree(const KdTree &tree, const bool exportGeometry = false);
+        virtual bool
+                ExportRssTree2(const RssTree &tree,
+                const Vector3 direction);
 
-  bool
-  ExportVssTree(const VssTree &tree);
+        bool ExportBspTree(const BspTree &tree);
 
-  bool
-  ExportVssTree2(const VssTree &tree,
-                                 const Vector3 direction
-                                 );
+        bool
+                ExportScene(SceneGraphNode *root)
+        {
+                ExportSceneNode(root);
+                return true;
+        }
 
-  virtual bool
-  ExportRssTree2(const RssTree &tree,
-                                 const Vector3 direction
-                                 );
+        virtual void
+                ExportPolygon(Polygon3 *poly);
 
-  // bool ExportOspTree(const OspTree &tree);
+        virtual void
+                ExportPolygons(const PolygonContainer &polys);
 
-  bool ExportBspTree(const BspTree &tree);
+        virtual bool
+                ExportBox(const AxisAlignedBox3 &box);
 
-  bool
-  ExportScene(SceneGraphNode *root)
-  {
-    ExportSceneNode(root);
-    return true;
-  }
+        virtual void
+                ExportMesh(Mesh *mesh);
 
-  virtual void
-  ExportPolygon(Polygon3 *poly);
+        virtual void
+                ExportViewCell(ViewCell *viewCell);
 
-  virtual void
-  ExportPolygons(const PolygonContainer &polys);
+        bool
+                ExportRays(const RayContainer &rays,
+                const float length=1000,
+                const RgbColor &color = RgbColor(1,1,1));
 
-  virtual bool
-  ExportBox(const AxisAlignedBox3 &box);
+        bool
+                ExportRays(const VssRayContainer &rays,
+                const RgbColor &color = RgbColor(1,1,1));
 
-  virtual void
-  ExportMesh(Mesh *mesh);
+        virtual void
+                ExportBspSplitPlanes(const BspTree &tree);
 
-  virtual void
-  ExportViewCell(ViewCell *viewCell);
+        virtual void
+                ExportBspSplits(const BspTree &tree, const bool exportDepth);
 
-  bool
-  ExportRays(const RayContainer &rays,
-                         const float length=1000,
-                         const RgbColor &color = RgbColor(1,1,1));
+        virtual void
+                ExportLeavesGeometry(const BspTree &tree, const vector<BspLeaf *> &leaves);
 
-  bool
-  ExportRays(const VssRayContainer &rays,
-                         const RgbColor &color = RgbColor(1,1,1));
+        virtual void ExportBspLeaves(const BspTree &tree, const int maxPvs = 0);
 
-  virtual void
-  ExportBspSplitPlanes(const BspTree &tree);
+        virtual void ExportBspSplits(const VspBspTree &tree, const bool exportDepth);
 
-  virtual void
-  ExportBspSplits(const BspTree &tree, const bool exportDepth);
+        virtual void ExportBeam(const Beam &beam, const AxisAlignedBox3 &box);
 
-  virtual void
-  ExportLeavesGeometry(const BspTree &tree, const vector<BspLeaf *> &leaves);
+        bool ExportRaySets(const vector<VssRayContainer> &rays,
+                                           const RgbColor &color);
 
-  virtual void
-  ExportBspLeaves(const BspTree &tree, const int maxPvs = 0);
-
-  virtual void
-  ExportBspSplits(const VspBspTree &tree, const bool exportDepth);
-
-  virtual void ExportBeam(const Beam &beam, const AxisAlignedBox3 &box);
-
-  bool
-  ExportRaySets(const vector<VssRayContainer> &rays,
-                                const RgbColor &color);
 
 protected:
 
-  virtual void
-  ExportSceneNode(SceneGraphNode *node);
+        virtual void ExportSceneNode(SceneGraphNode *node);
 
-  bool
-  ExportKdTreeRayDensity(const KdTree &tree);
+        bool ExportKdTreeRayDensity(const KdTree &tree);
 
-  bool
-  ExportBspTreeRayDensity(const BspTree &tree);
+        bool ExportBspTreeRayDensity(const BspTree &tree);
 
-  void ExportBspNodeSplits(BspNode *root,
-                                                   const AxisAlignedBox3 &box,
-                                                   const bool exportDepth,
-                                                   const bool epsilon);
+        void ExportBspNodeSplits(BspNode *root,
+                                                         const AxisAlignedBox3 &box,
+                                                         const bool exportDepth,
+                                                         const bool epsilon);
 
-
-  void ExportViewpoint(const Vector3 &point, const Vector3 &direction);
-
+        void ExportViewpoint(const Vector3 &point, const Vector3 &direction);
 };