Changeset 1027

Timestamp:

06/21/06 09:44:39 (18 years ago)

Author:

mattausch

Message:

 

Location:

GTP/trunk/Lib/Vis/Preprocessing/src

Files:

• Environment.cpp (modified) (1 diff)
• RssPreprocessor.cpp (modified) (1 diff)
• ViewCell.cpp (modified) (1 diff)
• ViewCellBsp.cpp (modified) (6 diffs)
• ViewCellBsp.h (modified) (4 diffs)
• ViewCellsManager.cpp (modified) (21 diffs)
• ViewCellsManager.h (modified) (4 diffs)
• VspBspTree.cpp (modified) (14 diffs)
• VspBspTree.h (modified) (2 diffs)
• VspOspTree.cpp (modified) (52 diffs)
• VspOspTree.h (modified) (18 diffs)
• VssPreprocessor.cpp (modified) (1 diff)

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

@@ -2089 +2089 @@
 
 
-/************************************************************************************/
-/*                 View space partition tree related options                        */
-/************************************************************************************/
+/***************************************************************************/
+/*                 View space partition tree related options               */
+/***************************************************************************/
 
         
+        RegisterOption("VspTree.Construction.samples",
+                                        optInt,
+                                        "vsp_construction_samples=",
+                                        "10000");
+
         RegisterOption("VspTree.Termination.maxDepth",
                                         optInt,

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

@@ -490 +490 @@
           box.SetMin(0, box.Min(0) + s);
           box.SetMax(0, box.Max(0) + s);
+         
           mViewCellsManager->SetViewSpaceBox(box);
         }

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

@@ -381 +381 @@
         Debug << "max memory: " << mMaxMemory << endl;
         Debug << "refining view cells: " << mRefineViewCells << endl;
-        Debug << "============= view cell tree options ================\n";
+        Debug << "=========== end view cell tree options ===============\n";
 
         MergeCandidate::sRenderCostWeight = mRenderCostWeight;

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

@@ -60 +60 @@
 
 
-bool BspNode::IsRoot() const 
-{
-        return mParent == NULL;
-}
-
-
-BspInterior *BspNode::GetParent() 
-{ 
-        return mParent; 
-}
-
-
-void BspNode::SetParent(BspInterior *parent)
-{
-        mParent = parent;
-}
-
-
 bool BspNode::IsSibling(BspNode *n) const
 {
@@ -127 +109 @@
 }
 
-bool BspInterior::IsLeaf() const
-{ 
-        return false; 
-}
-
-BspNode *BspInterior::GetBack() 
-{
-        return mBack;
-}
-
-BspNode *BspInterior::GetFront() 
-{
-        return mFront;
-}
-
-Plane3 BspInterior::GetPlane() const
-{
-        return mPlane;
-}
-
-void BspInterior::ReplaceChildLink(BspNode *oldChild, BspNode *newChild) 
-{
-        if (mBack == oldChild)
-                mBack = newChild;
-        else
-                mFront = newChild;
-}
 
 void BspInterior::SetupChildLinks(BspNode *b, BspNode *f) 
@@ -193 +148 @@
 BspNode(parent), mViewCell(viewCell), mPvs(NULL)
 {
-}
-
-ViewCellLeaf *BspLeaf::GetViewCell() const
-{
-        return mViewCell;
-}
-
-void BspLeaf::SetViewCell(ViewCellLeaf *viewCell)
-{
-        mViewCell = viewCell;
-}
-
-
-bool BspLeaf::IsLeaf() const 
-{ 
-        return true; 
 }
 
@@ -1010 +949 @@
                 // generate new view cell for each leaf
                 if (mGenerateViewCells)
+                {
                         viewCell = new BspViewCell();
+                }
                 else
+                {
                         // add view cell to leaf
                         viewCell = dynamic_cast<BspViewCell *>(tData.mViewCell);
-                
+                }
+
                 leaf->SetViewCell(viewCell);
                 viewCell->mLeaf = leaf;
@@ -1036 +979 @@
                 }
 
-                EvaluateLeafStats(tData);
+                if (1)
+                        EvaluateLeafStats(tData);
                 
                 //-- clean up
@@ -1045 +989 @@
                 CLEAR_CONTAINER(*tData.mRays);
 
-                DEL_PTR(tData.mPolygons);
-                DEL_PTR(tData.mRays);
-                DEL_PTR(tData.mGeometry);
+                delete tData.mPolygons;
+                delete tData.mRays;
+                delete tData.mGeometry;
 
                 return leaf;

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

@@ -278 +278 @@
 
         /** Determines whether this node is a root
-        @return true if root
-        */
-        virtual bool IsRoot() const;
+                @return true if root
+        */
+        virtual bool IsRoot() const
+        {
+                return mParent == NULL;
+        }
 
         /** Returns parent node.
         */
-        BspInterior *GetParent();
+        inline BspInterior *GetParent()
+        { 
+                return mParent; 
+        }
 
         /** Sets parent node.
         */
-        void SetParent(BspInterior *parent);
+        inline void BspNode::SetParent(BspInterior *parent)
+        {
+                mParent = parent;
+        }
+
 
         /** Returns true if this node is a sibling of node n.
@@ -334 +344 @@
         BspInterior(const Plane3 &plane);
         ~BspInterior();
+
         /** @return false since it is an interior node 
         */
-        bool IsLeaf() const;
-
-        BspNode *GetBack();
-        BspNode *GetFront();
-
+        bool IsLeaf() const
+        { 
+                return false; 
+        }
+        BspNode *GetBack() 
+        {
+                return mBack;
+        }
+
+        BspNode *GetFront() 
+        {
+                return mFront;
+        }
+        
         /** Returns split plane.
         */
-        Plane3 GetPlane() const;
+        Plane3 BspInterior::GetPlane() const
+        {
+                return mPlane;
+        }
 
         /** Replace front or back child with new child.
         */
-        void ReplaceChildLink(BspNode *oldChild, BspNode *newChild);
+        inline void ReplaceChildLink(BspNode *oldChild, BspNode *newChild)
+        {
+                if (mBack == oldChild)
+                        mBack = newChild;
+                else
+                        mFront = newChild;
+        }
+
         /** Replace front and back child.
         */
@@ -383 +413 @@
         ~BspLeaf();
 
+        /** Returns pointer of view cell.
+        */
+        inline ViewCellLeaf *GetViewCell() const
+        {
+                return mViewCell;
+        }
+
+        /** Sets pointer to view cell.
+        */
+        inline void SetViewCell(ViewCellLeaf *viewCell)
+        {
+                mViewCell = viewCell;
+        }
+
         /** @return true since it is an interior node 
         */
-        bool IsLeaf() const;
-        
-        /** Returns pointer of view cell.
-        */
-        ViewCellLeaf *GetViewCell() const;
-
-        /** Sets pointer to view cell.
-        */
-        void SetViewCell(ViewCellLeaf *viewCell);
+        bool BspLeaf::IsLeaf() const 
+        { 
+                return true; 
+        }
+        
 
         /// Rays piercing this leaf.
@@ -403 +443 @@
         /// Probability that the view point lies in this leaf
         float mProbability;
+
 
 protected:

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

@@ -181 +181 @@
 
 
-        Debug << "***********View Cells options ****************" << endl;
+        Debug << "************ View Cells options ***************" << endl;
         Debug << "color code: " << mColorCode << endl;
 
@@ -417 +417 @@
                   << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
 
-//return 0;
+
         // take post processing time
         startTime = GetTime();
@@ -1727 +1727 @@
 {
         mViewSpaceBox = box;
-
+        Debug << "here111 " << mViewSpaceBox << endl;
+        // hack: create clip plane relative to new view space box
         CreateClipPlane();
-        
+        // the total area of the view space has changed
         mTotalAreaValid = false;
 }
@@ -2928 +2929 @@
                                                                                                  const Plane3 *clipPlane) const
 {
+        // export mesh if available
         if (vc->GetMesh())
         {
                 exporter->ExportMesh(vc->GetMesh());
-        
                 return;
         }
-
-        
+        // otherwise construct from leaves
         if (clipPlane)
         {
@@ -4787 +4787 @@
 ViewCellsManager(), mVspTree(vspTree), mOspTree(ospTree)
 {
-        Environment::GetSingleton()->GetIntValue("VspBspTree.Construction.samples", mInitialSamples);
+        mHierarchyManager = new HierarchyManager(*vspTree, *ospTree);
+        Environment::GetSingleton()->GetIntValue("VspTree.Construction.samples", mInitialSamples);
         mVspTree->SetViewCellsManager(this);
         mVspTree->mViewCellsTree = mViewCellsTree;
@@ -4795 +4796 @@
 VspOspViewCellsManager::~VspOspViewCellsManager()
 {
+        DEL_PTR(mHierarchyManager);
 }
 
@@ -4835 +4837 @@
         mMaxPvsSize = (int)(mMaxPvsRatio * (float)objects.size());
 
+        Debug << "here125 view space box " << mViewSpaceBox << endl;
+
         // if view cells were already constructed
         if (ViewCellsConstructed())
@@ -4858 +4862 @@
         long startTime;
 
-#if TODO
-        if (1)
-                mVspTree->Construct(constructionRays, &mViewSpaceBox);
-        else
-                mVspTree->Construct(rays, &mViewSpaceBox);
-#endif
-        // collapse invalid regions
-        cout << "collapsing invalid tree regions ... ";
-        startTime = GetTime();
-        const int collapsedLeaves = mVspTree->CollapseTree();
-        Debug << "collapsed in " << TimeDiff(startTime, GetTime()) * 1e-3 
-                  << " seconds" << endl;
-
-    cout << "finished" << endl;
-
+        mHierarchyManager->Construct(constructionRays, objects, &mViewSpaceBox);
+
+        
         //-- stats
         Debug << mVspTree->GetStatistics() << endl;
@@ -4917 +4909 @@
 
 
-        // view cells already finished before post processing step 
-        // (i.e. because they were loaded)
+        // take this step only if 
+        // view cells already constructed before post processing step 
+        // (e.g., because they were loaded)
         if (mViewCellsFinished)
         {
@@ -5154 +5147 @@
 
 
+void VspOspViewCellsManager::ExportViewCellGeometry(Exporter *exporter,
+                                                                                                        ViewCell *vc,
+                                                                                                        const Plane3 *clipPlane) const
+{
+        ViewCellContainer leaves;
+
+        mViewCellsTree->CollectLeaves(vc, leaves);
+        ViewCellContainer::const_iterator it, it_end = leaves.end();
+
+        for (it = leaves.begin(); it != it_end; ++ it)
+        {
+                VspViewCell *vspVc = dynamic_cast<VspViewCell *>(*it);
+                VspLeaf *l = vspVc->mLeaf;
+
+                const AxisAlignedBox3 box = mVspTree->GetBBox(vspVc->mLeaf);
+
+                if (!clipPlane || !box.Side(*clipPlane))
+                        exporter->ExportBox(box);
+        }
+}
+
+
 bool VspOspViewCellsManager::ViewPointValid(const Vector3 &viewPoint) const
 {
@@ -5161 +5176 @@
 
   //    return mViewSpaceBox.IsInside(viewPoint) &&
-  //               mVspBspTree->ViewPointValid(viewPoint);
+  //               mVspTree->ViewPointValid(viewPoint);
 }
 
@@ -5170 +5185 @@
         if (!ViewCellsConstructed())
                 return;
-#if TODO
+
         VssRayContainer visRays;
         GetRaySets(sampleRays, mVisualizationSamples, visRays);
@@ -5208 +5223 @@
 
                         // HACK: export without clip plane
-                        const bool b = mUseClipPlaneForViz;
-                        mUseClipPlaneForViz = false;
+                        //const bool b = mUseClipPlaneForViz;
+                        //mUseClipPlaneForViz = false;
 
                         ExportViewCellsForViz(exporter);
                         
-                        mUseClipPlaneForViz = b;
+                        //mUseClipPlaneForViz = b;
                         delete exporter;
 
@@ -5220 +5235 @@
 
                 mColorCode = savedColorCode;
-        }
-
-
-        if (0)
-        {
-                cout << "exporting depth map ... ";
-
-                Exporter *exporter = Exporter::GetExporter("depth_map.x3d");
-                if (exporter)
-                {
-                        if (1)
-                        {
-                                exporter->SetWireframe();
-                                exporter->ExportBox(mViewSpaceBox);
-                                exporter->SetFilled();
-                        }
-
-                        if (mExportGeometry)
-                        {
-                                exporter->ExportGeometry(objects);
-                        }
-
-                        const int maxDepth = mVspBspTree->mBspStats.maxDepth;
-
-                        ViewCellContainer::const_iterator vit, vit_end = mViewCells.end();
-
-                        for (vit = mViewCells.begin(); vit != mViewCells.end(); ++ vit)
-                        {
-                                ViewCell *vc = *vit;
-
-                                ViewCellContainer leaves;
-                                mViewCellsTree->CollectLeaves(vc, leaves);
-
-                                ViewCellContainer::const_iterator lit, lit_end = leaves.end();
-
-                                for (lit = leaves.begin(); lit != lit_end; ++ lit)
-                                {
-                                        BspLeaf *leaf = dynamic_cast<BspViewCell *>(*lit)->mLeaf;
-
-                                        Material m; 
-
-                                        float relDepth = (float)leaf->GetDepth() / (float)maxDepth;
-                                        m.mDiffuseColor.r = relDepth;
-                                        m.mDiffuseColor.g = 0.0f;
-                                        m.mDiffuseColor.b = 1.0f - relDepth;
-
-                    exporter->SetForcedMaterial(m);
-                                
-
-                                        BspNodeGeometry geom;
-                                        mVspBspTree->ConstructGeometry(leaf, geom);
-                                        exporter->ExportPolygons(geom.GetPolys());
-                                }
-                        }
-
-                        delete exporter;
-                }
-
-
-                cout << "finished" << endl;
-        }
-
-        //-- visualization of the BSP splits
-
-        bool exportSplits = false;
-        Environment::GetSingleton()->GetBoolValue("VspBspTree.Visualization.exportSplits", exportSplits);
-
-        if (exportSplits)
-        {
-                cout << "exporting splits ... ";
-                ExportSplits(objects, visRays);
-                cout << "finished" << endl;
         }
 
         //-- export single view cells
         ExportBspPvs(objects, visRays);
-#endif
 }
 
@@ -5482 +5424 @@
 
 
-void VspOspViewCellsManager::ExportViewCellGeometry(Exporter *exporter,
-                                                    ViewCell *vc,
-                                                                                                        const Plane3 *clipPlane) const
-{
-        // matt: TODO
-}
-
-
 bool VspOspViewCellsManager::ExportViewCells(const string filename, 
                                                                                          const bool exportPvs, 
@@ -5537 +5471 @@
 
         //-- export the view cells and the pvs
-        stream << "<HierarchyType name=\"vspBspTree\" />" << endl;
+        stream << "<HierarchyType name=\"vspTree\" />" << endl;
 
         const int numViewCells = mCurrentViewCellsStats.viewCells;
@@ -5566 +5500 @@
 
 
-ViewCell *VspOspViewCellsManager::GetViewCell(const Vector3 &point, const bool active) const
+ViewCell *VspOspViewCellsManager::GetViewCell(const Vector3 &point, 
+                                                                                          const bool active) const
 {
         if (!ViewCellsConstructed())
@@ -5582 +5517 @@
         // matt: TODO
         Mesh *mesh = MeshManager::GetSingleton()->CreateResource();
+
+        ViewCellContainer leaves;
+        mViewCellsTree->CollectLeaves(vc, leaves);
+
+        ViewCellContainer::const_iterator it, it_end = leaves.end();
+
+    for (it = leaves.begin(); it != it_end; ++ it)
+        {
+                VspLeaf *leaf = dynamic_cast<VspViewCell *>(*it)->mLeaf;
+                const AxisAlignedBox3 box = mVspTree->GetBBox(leaf);
+
+        IncludeBoxInMesh(box, *mesh);
+        }
+
         vc->SetMesh(mesh);
 }
@@ -5596 +5545 @@
                                                                           const bool createMesh)
 {
-#if TODO
         float area = 0;
         float volume = 0;
@@ -5607 +5555 @@
     for (it = leaves.begin(); it != it_end; ++ it)
         {
-                BspNodeGeometry geom;
-                BspLeaf *leaf = dynamic_cast<BspViewCell *>(*it)->mLeaf;
-                mVspBspTree->ConstructGeometry(leaf, geom);
-
-                const float lVol = geom.GetVolume();
-                const float lArea = geom.GetArea();
+                VspLeaf *leaf = dynamic_cast<VspViewCell *>(*it)->mLeaf;
+                
+                const AxisAlignedBox3 box = mVspTree->GetBBox(leaf);
+
+                const float lVol = box.GetVolume();
+                const float lArea = box.SurfaceArea();
 
                 //(*it)->SetVolume(vol);
@@ -5625 +5573 @@
         viewCell->SetVolume(volume);
         viewCell->SetArea(area);
-#endif
 }
         

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

@@ -35 +35 @@
 class OspTree;
 class VspNode;
-
+class HierarchyManager;
 
 struct BspRay;
@@ -298 +298 @@
         /** Writes view cells to disc.
         */
-        virtual bool ExportViewCells(const string filename, const bool exportPvs, const ObjectContainer &objects);
+        virtual bool ExportViewCells(const string filename, 
+                                                                 const bool exportPvs, 
+                                                                 const ObjectContainer &objects);
 
         /** Casts beam to collect view cells.
@@ -983 +985 @@
         void CreateMesh(ViewCell *vc);
 
-        bool ExportViewCells(const string filename, const bool exportPvs, const ObjectContainer &objects);
+        bool ExportViewCells(const string filename, 
+                                                 const bool exportPvs, 
+                                                 const ObjectContainer &objects);
 
         int CastBeam(Beam &beam);
 
+        void Finalize(ViewCell *viewCell, const bool createMesh);
+
+
+protected:
+
+        
+        /** Exports view cell geometry.
+        */
         void ExportViewCellGeometry(Exporter *exporter, 
                                                                 ViewCell *vc,
                                                                 const Plane3 *clipPlane = NULL) const;
 
-        void Finalize(ViewCell *viewCell, const bool createMesh);
-
-
-protected:
-
         int ComputeBoxIntersections(const AxisAlignedBox3 &box, ViewCellContainer &viewCells) const;
         
@@ -1020 +1027 @@
         VspTree *mVspTree;
         OspTree *mOspTree;
+
+        HierarchyManager *mHierarchyManager;
 };
 

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

@@ -197 +197 @@
         Debug << endl;
 }
-/*
-VspBspTree::VspBspTree():
-mRoot(NULL),
-mUseAreaForPvs(false),
-mCostNormalizer(Limits::Small),
-mViewCellsManager(NULL),
-mOutOfBoundsCell(NULL),
-mStoreRays(false),
-mRenderCostWeight(0.5),
-mUseRandomAxis(false),
-mTimeStamp(1),
-mEpsilon(1e-6f)
-{
-}*/
+
 
 BspViewCell *VspBspTree::GetOutOfBoundsCell()
@@ -343 +330 @@
 
 
+void VspBspTree::ComputeBoundingBox(const VssRayContainer &sampleRays,
+                                                                        AxisAlignedBox3 *forcedBoundingBox) 
+{
+        if (forcedBoundingBox)
+        {
+                mBox = *forcedBoundingBox;
+        }
+        else // compute vsp tree bounding box
+        {
+                mBox.Initialize();
+
+                VssRayContainer::const_iterator rit, rit_end = sampleRays.end();
+
+                //-- compute bounding box
+        for (rit = sampleRays.begin(); rit != rit_end; ++ rit)
+                {
+                        VssRay *ray = *rit;
+
+                        // compute bounding box of view space
+                        mBox.Include(ray->GetTermination());
+                        mBox.Include(ray->GetOrigin());
+                }
+        }
+}
+
+
 void VspBspTree::Construct(const VssRayContainer &sampleRays,
                                                    AxisAlignedBox3 *forcedBoundingBox)
 {
-        mBspStats.nodes = 1;
-        mBox.Initialize();      // initialise BSP tree bounding box
-
-        if (forcedBoundingBox)
-                mBox = *forcedBoundingBox;
+        // Compute the bounding box from the rays
+        ComputeBoundingBox(sampleRays, forcedBoundingBox);
         
         PolygonContainer polys;
         RayInfoContainer *rays = new RayInfoContainer();
 
+        //-- extract polygons from rays if there are polygon candidates
+        if (mMaxPolyCandidates) 
+        {
+                int numObj = 0;
+
+                Intersectable::NewMail();
+
+        cout << "Extracting polygons from rays ... ";
+
+                long startTime = GetTime();
+
+        VssRayContainer::const_iterator rit, rit_end = sampleRays.end();
+
+                //-- extract polygons intersected by the rays
+                for (rit = sampleRays.begin(); rit != rit_end; ++ rit)
+                {
+                        VssRay *ray = *rit;
+                        Intersectable *obj = ray->mTerminationObject;
+
+                        if ((mBox.IsInside(ray->mTermination) || !forcedBoundingBox) &&
+                                obj && !obj->Mailed())
+                        {
+                                obj->Mail();
+
+                                // transformed mesh instance and mesh instance handle mesh differently
+                                if (obj->Type() == Intersectable::TRANSFORMED_MESH_INSTANCE)
+                                {
+                                        Mesh mesh;
+                                
+                                        TransformedMeshInstance *tmobj = 
+                                                dynamic_cast<TransformedMeshInstance *>(obj);
+                                
+                                        tmobj->GetTransformedMesh(mesh);
+                                        AddMeshToPolygons(&mesh, polys, tmobj);
+                                }
+                                else // MeshInstance
+                                {
+                                        MeshInstance *mobj = dynamic_cast<MeshInstance *>(obj);
+                                        AddMeshToPolygons(mobj->GetMesh(), polys, mobj);
+                                }
+
+                                ++ numObj;
+
+                                //-- compute bounding box
+                                if (!forcedBoundingBox)
+                                        mBox.Include(ray->mTermination);
+                        }
+
+                        if ((mBox.IsInside(ray->mOrigin) || !forcedBoundingBox) &&
+                                ray->mOriginObject && 
+                                !ray->mOriginObject->Mailed())
+                        {               
+                                ray->mOriginObject->Mail();
+                                MeshInstance *obj = dynamic_cast<MeshInstance *>(ray->mOriginObject);
+                                AddMeshToPolygons(obj->GetMesh(), polys, obj);
+                                
+                                ++ numObj;
+                        }
+                }
+
+                // throw out unnecessary polygons
+                PreprocessPolygons(polys);
+
+                cout << "finished" << endl;
+
+                Debug << "\n" << (int)polys.size() << " polys extracted from "
+                  << (int)sampleRays.size() << " rays in "
+                  << TimeDiff(startTime, GetTime())*1e-3 << " secs" << endl << endl;
+        }
+        
+        Debug << "maximal pvs (i.e., pvs still considered as valid): " 
+                  << mViewCellsManager->GetMaxPvsSize() << endl;
+
         VssRayContainer::const_iterator rit, rit_end = sampleRays.end();
-
-        long startTime = GetTime();
-
-        cout << "Extracting polygons from rays ... ";
-
-        Intersectable::NewMail();
-
-        int numObj = 0;
-
-        //-- extract polygons intersected by the rays
-        for (rit = sampleRays.begin(); rit != rit_end; ++ rit)
-        {
-                VssRay *ray = *rit;
-                Intersectable *obj = ray->mTerminationObject;
-
-                if ((mBox.IsInside(ray->mTermination) || !forcedBoundingBox) &&
-                        obj && !obj->Mailed())
-                {
-                        obj->Mail();
-
-                        // transformed mesh instance and mesh instance handle mesh differently
-                        if (obj->Type() == Intersectable::TRANSFORMED_MESH_INSTANCE)
-                        {
-                                Mesh mesh;
-                                
-                                TransformedMeshInstance *tmobj = 
-                                        dynamic_cast<TransformedMeshInstance *>(obj);
-                                
-                                tmobj->GetTransformedMesh(mesh);
-                                AddMeshToPolygons(&mesh, polys, tmobj);
-                        }
-                        else // MeshInstance
-                        {
-                                MeshInstance *mobj = dynamic_cast<MeshInstance *>(obj);
-                                AddMeshToPolygons(mobj->GetMesh(), polys, mobj);
-                        }
-
-                        ++ numObj;
-
-                        //-- compute bounding box
-                        if (!forcedBoundingBox)
-                                mBox.Include(ray->mTermination);
-                }
-
-                if ((mBox.IsInside(ray->mOrigin) || !forcedBoundingBox) &&
-                        ray->mOriginObject && 
-                        !ray->mOriginObject->Mailed())
-                {
-                        ray->mOriginObject->Mail();
-                        MeshInstance *obj = dynamic_cast<MeshInstance *>(ray->mOriginObject);
-                        AddMeshToPolygons(obj->GetMesh(), polys, obj);
-                        ++ numObj;
-
-                        //-- compute bounding box
-                        if (!forcedBoundingBox)
-                                mBox.Include(ray->mOrigin);
-                }
-        }
-        
-        Debug << "maximal pvs (i.e., pvs still considered as valid) : " 
-                  << mViewCellsManager->GetMaxPvsSize() << endl;
 
         //-- store rays
@@ -446 +468 @@
                 mTermMinProbability *= mBox.GetVolume();
 
-        // throw out unnecessary polygons
-        PreprocessPolygons(polys);
-
+
+        mBspStats.nodes = 1;
         mBspStats.polys = (int)polys.size();
         mGlobalCostMisses = 0;
 
-        cout << "finished" << endl;
-
-        Debug << "\nPolygon extraction: " << (int)polys.size() << " polys extracted from "
-                  << (int)sampleRays.size() << " rays in "
-                  << TimeDiff(startTime, GetTime())*1e-3 << " secs" << endl << endl;
 
         // use split cost priority queue
@@ -684 +700 @@
                 {
                         nViewCells += 500;
-
                         cout << "generated " << mCreatedViewCells << " viewcells" << endl;
                 }
@@ -847 +862 @@
 
                 // should I check here?
-                if (0 && !mViewCellsManager->CheckValidity(viewCell, 0, mViewCellsManager->GetMaxPvsSize()))
+                if (0 && !mViewCellsManager->CheckValidity(viewCell, 0, 
+                        mViewCellsManager->GetMaxPvsSize()))
                 {
                         viewCell->SetValid(false);
@@ -866 +882 @@
 
                 // finally evaluate stats until this leaf
-                EvaluateLeafStats(tData);               
+                if (0)
+                        EvaluateLeafStats(tData);               
         }
 
@@ -875 +892 @@
 }
 
-// subdivide using a split plane queue
+
+// subdivide node using a split plane queue
 BspNode *VspBspTree::Subdivide(VspBspSplitQueue &tQueue,
                                                            VspBspSplitCandidate &splitCandidate)
@@ -990 +1008 @@
 
                 // finally evaluate stats until this leaf
-                EvaluateLeafStats(tData);               
+                if (0)
+                        EvaluateLeafStats(tData);               
         }
 
@@ -1031 +1050 @@
 
         // TODO: reuse
-        DEL_PTR(frontData.mGeometry);
-        DEL_PTR(backData.mGeometry);
+        delete frontData.mGeometry;
+        delete backData.mGeometry;
         
         // compute global decrease in render cost
@@ -1910 +1929 @@
 
                 // something is wrong with the volume
-                if ((pFront < 0.0) || (pBack < 0.0))
+                if (0 && ((pFront < 0.0) || (pBack < 0.0)))
                 {
                         Debug << "ERROR in volume:\n"
@@ -2025 +2044 @@
                 {
                         //Debug << "error f: " << pFront << " b: " << pBack << endl;
-                        // high penalty for this split
+
+                        // high penalty for degenerated / wrong split
                         return 99999.9f;
                 }
@@ -2382 +2402 @@
                   << "Depth: " << data.mDepth << " (max: " << mTermMaxDepth << "), "
                   << "PVS: " << data.mPvs << " (min: " << mTermMinPvs << "), "
-          //              << "Area: " << data.mProbability << " (min: " << mTermMinProbability << "), "
-                  << "#rays: " << (int)data.mRays->size() << " (max: " << mTermMinRays << "), "
-                  << "#pvs: " << leaf->GetViewCell()->GetPvs().GetSize() << "=, "
+                  << "#rays: " << (int)data.mRays->size() << " (max: " << mTermMinRays << "), "
+                  << "#pvs: " << leaf->GetViewCell()->GetPvs().GetSize() << "), "
                   << "#avg ray contrib (pvs): " << (float)data.mPvs / (float)data.mRays->size() << endl;
 #endif
@@ -2660 +2679 @@
         // preprocess: throw out polygons coincident to the view space box (not needed)
         PolygonContainer boxPolys;
-        /*mBox.ExtractPolys(boxPolys);
+        
+        mBox.ExtractPolys(boxPolys);
         vector<Plane3> boxPlanes;
 
@@ -2699 +2719 @@
                         polys.pop_back();
                 }
-        }*/
+        }
 }
 

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

@@ -227 +227 @@
         /** Returns box which bounds the whole tree.
         */
-        AxisAlignedBox3 GetBoundingBox()const;
+        AxisAlignedBox3 GetBoundingBox() const;
 
         /** Returns root of BSP tree.
@@ -389 +389 @@
                 }
         };
+
+        void ComputeBoundingBox(const VssRayContainer &sampleRays, 
+                                                        AxisAlignedBox3 *forcedBoundingBox);
 
         /** faster evaluation of split plane cost for kd axis aligned cells.

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

@@ -53 +53 @@
 void VspTreeStatistics::Print(ostream &app) const
 {
-#if TODO
-        app << "===== BspTree statistics ===============\n";
+        app << "===== VspTree statistics ===============\n";
 
         app << setprecision(4);
@@ -65 +64 @@
 
         app << "#N_LEAVES ( Number of leaves )\n" << Leaves() << "\n";
-
-        app << "#N_POLYSPLITS ( Number of polygon splits )\n" << polySplits << "\n";
 
         app << "#AXIS_ALIGNED_SPLITS (number of axis aligned splits)\n" << splits[0] + splits[1] + splits[2] << endl;
@@ -100 +97 @@
         app << "#AVGDEPTH ( average depth )\n" << AvgDepth() << endl;
 
-        app << "#N_INPUTPOLYGONS (number of input polygons )\n" << polys << endl;
-
         app << "#N_INVALIDLEAVES (number of invalid leaves )\n" << invalidLeaves << endl;
 
@@ -107 +102 @@
         //app << "#N_PVS: " << pvs << endl;
 
-        app << "#N_ROUTPUT_INPUT_POLYGONS ( ratio polygons after subdivision / input polygons )\n" <<
-                 (polys + polySplits) / (double)polys << endl;
-        
-        app << "===== END OF BspTree statistics ==========\n";
-#endif
+        app << "===== END OF VspTree statistics ==========\n";
 }
 
@@ -267 +258 @@
         return Interior;
 }
+
+
 
 /****************************************************************/
@@ -449 +442 @@
 {
         mVspStats.nodes = 1;
-        mBoundingBox.Initialize();      // initialise vsp tree bounding box
-
+        
         if (forcedBoundingBox)
+        {
                 mBoundingBox = *forcedBoundingBox;
-        
-        VssRayContainer::const_iterator rit, rit_end = sampleRays.end();
-
-        Intersectable::NewMail();
-
-        //-- compute bounding box
-        for (rit = sampleRays.begin(); rit != rit_end; ++ rit)
-        {
-                VssRay *ray = *rit;
-
-                // compute bounding box of view space
-                if (!forcedBoundingBox)
-                {
+        }
+        else // compute vsp tree bounding box
+        {
+                mBoundingBox.Initialize();
+
+                VssRayContainer::const_iterator rit, rit_end = sampleRays.end();
+
+                //-- compute bounding box
+        for (rit = sampleRays.begin(); rit != rit_end; ++ rit)
+                {
+                        VssRay *ray = *rit;
+
+                        // compute bounding box of view space
                         mBoundingBox.Include(ray->GetTermination());
                         mBoundingBox.Include(ray->GetOrigin());
                 }
-        }
-
-        mTermMinProbability *= mBoundingBox.GetVolume();
-        mGlobalCostMisses = 0;
+
+                mTermMinProbability *= mBoundingBox.GetVolume();
+                mGlobalCostMisses = 0;
+        }
 }
 
@@ -480 +473 @@
                                                                   const float splitCandidateCost,
                                                                   const float totalRenderCost,
-                                                                         const float avgRenderCost)
+                                                                  const float avgRenderCost)
 {
         mSubdivisionStats 
@@ -507 +500 @@
 {
         return
+#if TODO
                 (((int)data.mRays->size() <= mTermMinRays) ||
                  (data.mPvs <= mTermMinPvs)   ||
@@ -512 +506 @@
                  (data.GetAvgRayContribution() > mTermMaxRayContribution) ||
                  (data.mDepth >= mTermMaxDepth));
+#else
+                false;
+#endif
 }
 
@@ -518 +515 @@
 {
         return
+#if TODO
                 (mOutOfMemory || 
                 (mVspStats.Leaves() >= mMaxViewCells) || 
                 (mGlobalCostMisses >= mTermGlobalCostMissTolerance));
+#else
+                (mVspStats.Leaves() >= mMaxViewCells) ;         
+#endif
 }
 
@@ -633 +634 @@
 
 void VspTree::EvalSplitCandidate(VspTraversalData &tData,
-                                                                 VspSplitCandidate &splitData)
+                                                                 VspSplitCandidate &splitCandidate)
 {
         float frontProb;
-        float backtProb;
+        float backProb;
         
         VspLeaf *leaf = dynamic_cast<VspLeaf *>(tData.mNode);
@@ -642 +643 @@
         // compute locally best split plane
         const bool success = 
-                SelectPlane(tData, splitData.mSplitPlane,
-                                        frontProb, backtProb);
-
-        //TODO
+                SelectSplitPlane(tData, splitCandidate.mSplitPlane,     frontProb, backProb);
+
         // compute global decrease in render cost
-        splitData.mPriority = EvalRenderCostDecrease(splitData.mSplitPlane, tData);
-        splitData.mParentData = tData;
-        splitData.mMaxCostMisses = success ? tData.mMaxCostMisses : tData.mMaxCostMisses + 1;
+        splitCandidate.mPriority = EvalRenderCostDecrease(splitCandidate.mSplitPlane, tData);
+        splitCandidate.mParentData = tData;
+        splitCandidate.mMaxCostMisses = success ? tData.mMaxCostMisses : tData.mMaxCostMisses + 1;
+
+        Debug << "p: " << tData.mNode << " depth: " << tData.mDepth << endl;
 }
 
@@ -673 +674 @@
                           *backData.mRays);
 
+        Debug << "f: " << frontData.mRays->size() << " b: " << backData.mRays->size() << "d: " << tData.mRays->size() << endl;
         //-- compute pvs
         frontData.mPvs = ComputePvsSize(*frontData.mRays);
@@ -831 +833 @@
 
 
-float VspTree::BestCostRatioHeuristics(const RayInfoContainer &rays,
-                                                                                  const AxisAlignedBox3 &box,
-                                                                                  const int pvsSize,
-                                                                                  const int axis,
-                                          float &position)
+float VspTree::EvalLocalCostHeuristics(const RayInfoContainer &rays,
+                                                                           const AxisAlignedBox3 &box,
+                                                                           const int pvsSize,
+                                                                           const int axis,
+                                                                           float &position)
 {
         const float minBox = box.Min(axis);
@@ -1003 +1005 @@
 
 
-float VspTree::SelectPlane(const VspTraversalData &tData,
-                                                   AxisAlignedPlane &plane,
-                                                   float &pFront,
-                                                   float &pBack)
+float VspTree::SelectSplitPlane(const VspTraversalData &tData,
+                                                                AxisAlignedPlane &plane,
+                                                                float &pFront,
+                                                                float &pBack)
 {
         float nPosition[3];
@@ -1019 +1021 @@
         int bestAxis = -1;
 
-
         // if we use some kind of specialised fixed axis
     const bool useSpecialAxis = 
                 mOnlyDrivingAxis || mCirculatingAxis;
 
+        int parentAxis = 0;
+        VspNode *parent = tData.mNode->GetParent();
+
+        if (parent)
+                parentAxis = dynamic_cast<VspInterior *>(parent)->GetAxis();
+
         if (mCirculatingAxis)
-                sAxis = (tData.mAxis + 1) % 3;
+                sAxis = (parentAxis + 1) % 3;
         else if (mOnlyDrivingAxis)
                 sAxis = box.Size().DrivingAxis();
@@ -1039 +1046 @@
                         {
                                 nCostRatio[axis] =
-                                        BestCostRatioHeuristics(*tData.mRays,
-                                                                                    box,
+                                        EvalLocalCostHeuristics(*tData.mRays,
+                                                                                        box,
                                                                                         tData.mPvs,
                                                                                         axis,
@@ -1049 +1056 @@
                                 nPosition[axis] = (box.Min()[axis] + box.Max()[axis]) * 0.5f;
 
-                                nCostRatio[axis] = EvalSplitCost(tData,
-                                                                                                 box,
-                                                                                                 axis,
-                                                                                                 nPosition[axis],
-                                                                                                 nProbFront[axis], 
-                                                                                                 nProbBack[axis]);
+                                nCostRatio[axis] = EvalLocalSplitCost(tData,
+                                                                                                          box,
+                                                                                                          axis,
+                                                                                                          nPosition[axis],
+                                                                                                          nProbFront[axis], 
+                                                                                                          nProbBack[axis]);
                         }
                                                 
@@ -1091 +1098 @@
                                                                           const VspTraversalData &data) const
 {
+#if 1
+        return -data.mDepth;
+#endif
         float pvsFront = 0;
         float pvsBack = 0;
@@ -1112 +1122 @@
                 float t;
                 VssRay *ray = rayInf.mRay;
+
                 const int cf = 
                         rayInf.ComputeRayIntersection(candidatePlane.mAxis, 
@@ -1120 +1131 @@
                 AddObjToPvs(ray->mOriginObject, cf, pvsFront, pvsBack, totalPvs);
         }
+
 
         AxisAlignedBox3 frontBox;
@@ -1145 +1157 @@
         const float renderCostDecrease = (oldRenderCost - newRenderCost) / mBoundingBox.GetVolume();
         
-
-#if 1
         // take render cost of node into account 
         // otherwise danger of being stuck in a local minimum!!
+        const float factor = 0.99f;
+
         const float normalizedOldRenderCost = oldRenderCost / mBoundingBox.GetVolume();
-        return 0.99f * renderCostDecrease + 0.01f * normalizedOldRenderCost;
-#else
-        return renderCostDecrease;
-#endif
-}
-
-
-float VspTree::EvalSplitCost(const VspTraversalData &data,
-                                                         const AxisAlignedBox3 &box,
-                                                         const int axis,
-                                                         const float &position,                                                                           
-                                                         float &pFront,
-                                                         float &pBack) const
+        return factor * renderCostDecrease + (1.0f - factor) * normalizedOldRenderCost;
+}
+
+
+float VspTree::EvalLocalSplitCost(const VspTraversalData &data,
+                                                                  const AxisAlignedBox3 &box,
+                                                                  const int axis,
+                                                                  const float &position,
+                                                                  float &pFront,
+                                                                  float &pBack) const
 {
         float pvsTotal = 0;
@@ -1190 +1199 @@
 
         //-- compute heurstics
-        //-- we take simplified computation for mid split
-                
+        
         pOverall = data.mProbability;
+        // we take simplified computation for mid split
         pBack = pFront = pOverall * 0.5f;
         
@@ -1210 +1219 @@
 
 void VspTree::AddObjToPvs(Intersectable *obj,
-                                                         const int cf,
-                                                         float &frontPvs,
-                                                         float &backPvs,
-                                                         float &totalPvs) const
+                                                  const int cf,
+                                                  float &frontPvs,
+                                                  float &backPvs,
+                                                  float &totalPvs) const
 {
         if (!obj)
@@ -1352 +1361 @@
         ++ mCreatedViewCells;
 
-#ifdef _DEBUG
+//#ifdef _DEBUG
         Debug << "BSP stats: "
                   << "Depth: " << data.mDepth << " (max: " << mTermMaxDepth << "), "
                   << "PVS: " << data.mPvs << " (min: " << mTermMinPvs << "), "
-          //              << "Area: " << data.mProbability << " (min: " << mTermMinProbability << "), "
                   << "#rays: " << (int)data.mRays->size() << " (max: " << mTermMinRays << "), "
-                  << "#pvs: " << leaf->GetViewCell()->GetPvs().GetSize() << "=, "
+                  << "#pvs: " << leaf->GetViewCell()->GetPvs().GetSize() << "), "
                   << "#avg ray contrib (pvs): " << (float)data.mPvs / (float)data.mRays->size() << endl;
-#endif
+//#endif
 }
 
@@ -1605 +1613 @@
                         
                         if (GetBBox(interior->GetBack()).Side(plane) < 0)
+                        {
                                 next = interior->GetFront();
+                        }
             else
+                        {
                                 if (GetBBox(interior->GetFront()).Side(plane) < 0)
+                                {
                                         next = interior->GetBack();
+                                }
                                 else 
                                 {
@@ -1618 +1631 @@
                                         mask = mask >> 1;
                                 }
-
-                                nodeStack.push(next);
+                        }
+                        
+                        nodeStack.push(next);
                 }
         }
@@ -1704 +1718 @@
 
 int VspTree::CastLineSegment(const Vector3 &origin,
-                                                                const Vector3 &termination,
-                                                                ViewCellContainer &viewcells)
+                                                         const Vector3 &termination,
+                             ViewCellContainer &viewcells)
 {
         int hits = 0;
@@ -1722 +1736 @@
         VspNode *node = mRoot;
         VspNode *farChild;
+
+        float position;
+        int axis;
+
+        while (1)
+        {
+                if (!node->IsLeaf())
+                {
+                        VspInterior *in = dynamic_cast<VspInterior *>(node);
+                        position = in->GetPosition();
+                        axis = in->GetAxis();
+
+                        if (entp[axis] <= position)
+                        {
+                                if (extp[axis] <= position)
+                                {
+                                        node = in->GetFront();
+                                        // cases N1,N2,N3,P5,Z2,Z3
+                                        continue;
+                                } else
+                                {
+                                        // case N4
+                                        node = in->GetFront();
+                                        farChild = in->GetBack();
+                                }
+                        }
+                        else
+                        {
+                                if (position <= extp[axis])
+                                {
+                                        node = in->GetBack();
+                                        // cases P1,P2,P3,N5,Z1
+                                        continue;
+                                }
+                                else
+                                {
+                                        node = in->GetBack();
+                                        farChild = in->GetFront();
+                                        // case P4
+                                }
+                        }
+
+                        // $$ modification 3.5.2004 - hints from Kamil Ghais
+                        // case N4 or P4
+                        const float tdist = (position - origin[axis]) / dir[axis];
+                        tStack.push(LineTraversalData(farChild, extp, maxt)); //TODO
+
+                        extp = origin + dir * tdist;
+                        maxt = tdist;
+                }
+                else
+                {
+                        // compute intersection with all objects in this leaf
+                        VspLeaf *leaf = dynamic_cast<VspLeaf *>(node);
+                        ViewCell *vc = leaf->GetViewCell();
+
+                        if (!vc->Mailed())
+                        {
+                                vc->Mail();
+                                viewcells.push_back(vc);
+                                ++ hits;
+                        }
+#if 0
+                        leaf->mRays.push_back(RayInfo(new VssRay(origin, termination, NULL, NULL, 0)));
+#endif
+                        // get the next node from the stack
+                        if (tStack.empty())
+                                break;
+
+                        entp = extp;
+                        mint = maxt;
+                        
+                        LineTraversalData &s  = tStack.top();
+                        node = s.mNode;
+                        extp = s.mExitPoint;
+                        maxt = s.mMaxT;
+                        tStack.pop();
+                }
+        }
+
+        return hits;
+}
+
+
+int VspTree::CastRay(Ray &ray)
+{
+        int hits = 0;
+
+        stack<LineTraversalData> tStack;
+        const Vector3 dir = ray.GetDir();
+
+        float maxt, mint;
+
+        if (!mBoundingBox.GetRaySegment(ray, mint, maxt))
+                return 0;
+
+        Intersectable::NewMail();
+        ViewCell::NewMail();
+
+        Vector3 entp = ray.Extrap(mint);
+        Vector3 extp = ray.Extrap(maxt);
+
+        const Vector3 origin = entp;
+
+        VspNode *node = mRoot;
+        VspNode *farChild = NULL;
 
         float position;
@@ -1741 +1861 @@
                                         // cases N1,N2,N3,P5,Z2,Z3
                                         continue;
-                                } else
+                                } 
+                                else
                                 {
                                         // case N4
@@ -1768 +1889 @@
                         const float tdist = (position - origin[axis]) / dir[axis];
                         tStack.push(LineTraversalData(farChild, extp, maxt)); //TODO
-
                         extp = origin + dir * tdist;
                         maxt = tdist;
@@ -1781 +1901 @@
                         {
                                 vc->Mail();
-                                viewcells.push_back(vc);
+                                // todo: add view cells to ray
                                 ++ hits;
                         }
@@ -1804 +1924 @@
         return hits;
 }
-
-
-int VspTree::CastRay(Ray &ray)
-{
-        int hits = 0;
-
-        stack<LineTraversalData> tStack;
-        const Vector3 dir = ray.GetDir();
-
-        float maxt, mint;
-
-        if (!mBoundingBox.GetRaySegment(ray, mint, maxt))
-                return 0;
-
-        Intersectable::NewMail();
-        ViewCell::NewMail();
-
-        Vector3 entp = ray.Extrap(mint);
-        Vector3 extp = ray.Extrap(maxt);
-
-        const Vector3 origin = entp;
-
-        VspNode *node = mRoot;
-        VspNode *farChild = NULL;
-
-        float position;
-        int axis;
-
-        while (1)
-        {
-                if (!node->IsLeaf())
-                {
-                        VspInterior *in = dynamic_cast<VspInterior *>(node);
-                        position = in->GetPosition();
-                        axis = in->GetAxis();
-
-                        if (entp[axis] <= position)
-                        {
-                                if (extp[axis] <= position)
-                                {
-                                        node = in->GetBack();
-                                        // cases N1,N2,N3,P5,Z2,Z3
-                                        continue;
-                                } 
-                                else
-                                {
-                                        // case N4
-                                        node = in->GetBack();
-                                        farChild = in->GetFront();
-                                }
-                        }
-                        else
-                        {
-                                if (position <= extp[axis])
-                                {
-                                        node = in->GetFront();
-                                        // cases P1,P2,P3,N5,Z1
-                                        continue;
-                                }
-                                else
-                                {
-                                        node = in->GetFront();
-                                        farChild = in->GetBack();
-                                        // case P4
-                                }
-                        }
-
-                        // $$ modification 3.5.2004 - hints from Kamil Ghais
-                        // case N4 or P4
-                        const float tdist = (position - origin[axis]) / dir[axis];
-                        tStack.push(LineTraversalData(farChild, extp, maxt)); //TODO
-                        extp = origin + dir * tdist;
-                        maxt = tdist;
-                }
-                else
-                {
-                        // compute intersection with all objects in this leaf
-                        VspLeaf *leaf = dynamic_cast<VspLeaf *>(node);
-                        ViewCell *vc = leaf->GetViewCell();
-
-                        if (!vc->Mailed())
-                        {
-                                vc->Mail();
-                                // todo: add view cells to ray
-                                ++ hits;
-                        }
-#if 0
-                        leaf->mRays.push_back(RayInfo(new VssRay(origin, termination, NULL, NULL, 0)));
-#endif
-                        // get the next node from the stack
-                        if (tStack.empty())
-                                break;
-
-                        entp = extp;
-                        mint = maxt;
-                        
-                        LineTraversalData &s  = tStack.top();
-                        node = s.mNode;
-                        extp = s.mExitPoint;
-                        maxt = s.mMaxT;
-                        tStack.pop();
-                }
-        }
-
-        return hits;
-}
-
-
-VspNode *VspTree::CollapseTree(VspNode *node, int &collapsed)
-{
-// TODO
-#if HAS_TO_BE_REDONE
-        if (node->IsLeaf())
-                return node;
-
-        VspInterior *interior = dynamic_cast<VspInterior *>(node);
-
-        VspNode *front = CollapseTree(interior->GetFront(), collapsed);
-        VspNode *back = CollapseTree(interior->GetBack(), collapsed);
-
-        if (front->IsLeaf() && back->IsLeaf())
-        {
-                VspLeaf *frontLeaf = dynamic_cast<VspLeaf *>(front);
-                VspLeaf *backLeaf = dynamic_cast<VspLeaf *>(back);
-
-                //-- collapse tree
-                if (frontLeaf->GetViewCell() == backLeaf->GetViewCell())
-                {
-                        BspViewCell *vc = frontLeaf->GetViewCell();
-
-                        VspLeaf *leaf = new VspLeaf(interior->GetParent(), vc);
-                        leaf->SetTreeValid(frontLeaf->TreeValid());
-
-                        // replace a link from node's parent
-                        if (leaf->GetParent())
-                                leaf->GetParent()->ReplaceChildLink(node, leaf);
-                        else
-                                mRoot = leaf;
-
-                        ++ collapsed;
-                        delete interior;
-
-                        return leaf;
-                }
-        }
-#endif
-        return node;
-}
-
-
-int VspTree::CollapseTree()
-{
-        int collapsed = 0;
-
-        (void)CollapseTree(mRoot, collapsed);
-        // revalidate leaves
-        RepairViewCellsLeafLists();
-
-        return collapsed;
-}
-
-
-void VspTree::RepairViewCellsLeafLists()
-{
-// TODO
-#if HAS_TO_BE_REDONE
-        // list not valid anymore => clear
-        stack<VspNode *> nodeStack;
-        nodeStack.push(mRoot);
-
-        ViewCell::NewMail();
-
-        while (!nodeStack.empty())
-        {
-                VspNode *node = nodeStack.top();
-                nodeStack.pop();
-
-                if (node->IsLeaf())
-                {
-                        VspLeaf *leaf = dynamic_cast<VspLeaf *>(node);
-
-                        BspViewCell *viewCell = leaf->GetViewCell();
-
-                        if (!viewCell->Mailed())
-                        {
-                                viewCell->mLeaves.clear();
-                                viewCell->Mail();
-                        }
-        
-                        viewCell->mLeaves.push_back(leaf);
-
-                }
-                else
-                {
-                        VspInterior *interior = dynamic_cast<VspInterior *>(node);
-
-                        nodeStack.push(interior->GetFront());
-                        nodeStack.push(interior->GetBack());
-                }
-        }
-// TODO
-#endif
-}
-
 
 
@@ -2171 +2087 @@
                 //-- test if start point behind or in front of plane
                 const int side = plane.ComputeRayIntersection(bRay, t);
-
+#if 1
                 if (side == 0)
                 {
@@ -2195 +2111 @@
                         backRays.push_back(bRay);
                 }
-
+#else
+                if (side == 0)
+                {
+                        ++ splits;
+
+                        if (ray->HasPosDir(plane.mAxis))
+                        {
+                                backRays.push_back(RayInfo(ray, bRay.GetMaxT(), t));
+                                frontRays.push_back(RayInfo(ray, t, bRay.GetMinT()));
+                        }
+                        else
+                        {
+                                frontRays.push_back(RayInfo(ray, bRay.GetMaxT(), t));
+                                backRays.push_back(RayInfo(ray, t, bRay.GetMinT()));
+                        }
+                }
+                else if (side == 1)
+                {
+                        backRays.push_back(bRay);
+                }
+                else
+                {
+                        frontRays.push_back(bRay);
+                        
+                }
+#endif
         }
 
@@ -2216 +2157 @@
         AxisAlignedBox3 box(parent->GetBoundingBox());
 
-        if (parent->GetFront() == node)
+        if (parent->GetBack() == node)
                 box.SetMin(parent->GetAxis(), parent->GetPosition());
         else
@@ -2230 +2171 @@
                                                                          ViewCellContainer &viewCells) const
 {
-#if TODO
-        stack<bspNodePair> nodeStack;
-        BspNodeGeometry *rgeom = new BspNodeGeometry();
-
-        ConstructGeometry(mRoot, *rgeom);
-
-        nodeStack.push(bspNodePair(mRoot, rgeom));
-  
+        stack<VspNode *> nodeStack;
+ 
         ViewCell::NewMail();
 
         while (!nodeStack.empty()) 
         {
-                BspNode *node = nodeStack.top().first;
-                BspNodeGeometry *geom = nodeStack.top().second;
+                VspNode *node = nodeStack.top();
                 nodeStack.pop();
 
-                const int side = geom->ComputeIntersection(box);
-                
-                switch (side)
-                {
-                case -1:
+                const AxisAlignedBox3 bbox = GetBBox(node);
+
+                if (bbox.Includes(box))
+                {
                         // node geometry is contained in box
                         CollectViewCells(node, true, viewCells, true);
-                        break;
-
-                case 0:
+                }
+                else if (Overlap(bbox, box))
+                {
                         if (node->IsLeaf())
                         {
@@ -2268 +2201 @@
                         else 
                         {
-                                BspInterior *interior = dynamic_cast<BspInterior *>(node);
+                                VspInterior *interior = dynamic_cast<VspInterior *>(node);
                         
-                                BspNode *first = interior->GetFront();
-                                BspNode *second = interior->GetBack();
+                                VspNode *first = interior->GetFront();
+                                VspNode *second = interior->GetBack();
             
-                                BspNodeGeometry *firstGeom = new BspNodeGeometry();
-                                BspNodeGeometry *secondGeom = new BspNodeGeometry();
-
-                                geom->SplitGeometry(*firstGeom,
-                                                                        *secondGeom,
-                                                                        interior->GetPlane(),
-                                                                        mBox,
-                                                                        //0.0000001f);
-                                                                        mEpsilon);
-
-                                nodeStack.push(bspNodePair(first, firstGeom));
-                                nodeStack.push(bspNodePair(second, secondGeom));
-                        }
-                        
-                        break;
-                default:
-                        // default: cull
-                        break;
-                }
-                DEL_PTR(geom);
-        }
-
-#endif
+                                nodeStack.push(first);
+                                nodeStack.push(second);
+                        }
+                }       
+                // default: cull
+        }
+
         return (int)viewCells.size();
 }
@@ -2304 +2221 @@
 /*                class OspTree implementation                   */
 /*****************************************************************/
+
 
 OspTree::OspTree():
@@ -2499 +2417 @@
                 // create new interior node and two leaf node
                 const AxisAlignedPlane splitPlane = splitCandidate.mSplitPlane;
+                
                 newNode = SubdivideNode(dynamic_cast<KdLeaf *>(newNode), 
                                                                 splitPlane, 
@@ -2635 +2554 @@
           //              << "Area: " << data.mProbability << " (min: " << mTermMinProbability << "), "
                   << "#rays: " << (int)data.mRays->size() << " (max: " << mTermMinRays << "), "
-                  << "#pvs: " << leaf->GetViewCell()->GetPvs().GetSize() << "=, "
+                  << "#pvs: " << leaf->GetViewCell()->GetPvs().GetSize() << "), "
                   << "#avg ray contrib (pvs): " << (float)data.mPvs / (float)data.mRays->size() << endl;
 #endif
@@ -2647 +2566 @@
 /*********************************************************************/
 
-HierarchyManager::HierarchyManager()
+HierarchyManager::HierarchyManager(VspTree &vspTree, OspTree &ospTree):
+mVspTree(vspTree), mOspTree(ospTree)
 {
 }
@@ -2655 +2575 @@
 {
         SplitCandidate *splitCandidate = mTQueue.top();
+        Debug << "priority: " << splitCandidate->GetPriority() << endl;
         mTQueue.pop();
 
@@ -2662 +2583 @@
 
 void HierarchyManager::PrepareConstruction(const VssRayContainer &sampleRays,
+                                                                                   const ObjectContainer &objects,
                                                                                    AxisAlignedBox3 *forcedViewSpace,
                                                                                    RayInfoContainer &rays)
 {
+        mVspTree.PrepareConstruction(sampleRays, forcedViewSpace);
+
+        long startTime = GetTime();
+
+        cout << "storing rays ... ";
+
+        Intersectable::NewMail();
+
         VssRayContainer::const_iterator rit, rit_end = sampleRays.end();
-
-        long startTime = GetTime();
-
-        cout << "storing rays ... ";
-
-        Intersectable::NewMail();
-
-        mVspTree->PrepareConstruction(sampleRays, forcedViewSpace);
 
         //-- store rays
@@ -2684 +2606 @@
                 static Ray hray;
                 hray.Init(*ray);
-
+                
                 // TODO: not very efficient to implictly cast between rays types
-                if (mBoundingBox.GetRaySegment(hray, minT, maxT))
+                if (mVspTree.GetBoundingBox().GetRaySegment(hray, minT, maxT))
                 {
                         float len = ray->Length();
@@ -2697 +2619 @@
         }
 
-        cout << "finished" << endl;
+        cout << "finished in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
+
+        /// add first candidate for view space partition
+        mVspTree.mRoot = new VspLeaf();
+        const float prop = mVspTree.mBoundingBox.GetVolume();
+
+        /// first traversal data
+        VspTree::VspTraversalData tData(mVspTree.mRoot,
+                                                                        0,
+                                                                        &rays,
+                                                                        (int)objects.size(),
+                                                                        //mVspTree.ComputePvsSize(rays),
+                                                                        prop,
+                                                                        mVspTree.mBoundingBox);
+
+        // compute first split candidate
+        VspTree::VspSplitCandidate *splitCandidate = new VspTree::VspSplitCandidate();
+    mVspTree.EvalSplitCandidate(tData, *splitCandidate);
+
+        mTQueue.push(splitCandidate);
 
         //mOspTree->PrepareConstruction(sampleRays, forcedViewSpace, rays);
@@ -2710 +2651 @@
                         dynamic_cast<VspTree::VspSplitCandidate *>(candidate);
                 
-                return mVspTree->GlobalTerminationCriteriaMet(sc->mParentData);
+                return mVspTree.GlobalTerminationCriteriaMet(sc->mParentData);
         }
 
@@ -2724 +2665 @@
         
         // prepare vsp and osp trees for traversal
-        PrepareConstruction(sampleRays, forcedViewSpace, *rays);
-
-        mVspTree->mVspStats.Start();
+        PrepareConstruction(sampleRays, objects, forcedViewSpace, *rays);
+
+        mVspTree.mVspStats.Reset();
+        mVspTree.mVspStats.Start();
 
         cout << "Constructing view space / object space tree ... \n";
@@ -2738 +2680 @@
                         GlobalTerminationCriteriaMet(splitCandidate);
 
+                Debug << "cost: " << splitCandidate->GetPriority();
+
                 // cost ratio of cost decrease / totalCost
                 const float costRatio = splitCandidate->GetPriority() / mTotalCost;
@@ -2744 +2688 @@
                 if (costRatio < mTermMinGlobalCostRatio)
                         ++ mGlobalCostMisses;
-        
+
                 //-- subdivide leaf node
                 //-- either a object space or view space split
@@ -2752 +2696 @@
                                 dynamic_cast<VspTree::VspSplitCandidate *>(splitCandidate);
 
-                        VspNode *r = mVspTree->Subdivide(mTQueue, *sc, globalTerminationCriteriaMet);
+                        VspNode *r = mVspTree.Subdivide(mTQueue, *sc, globalTerminationCriteriaMet);
                 }
                 else // object space split
                 {
 #if TODO
-                        KdNode *r = mKdtree->Subdivide(tOspQueue, dynamic_cast<OspSplitCandidate<(splitCandidate));
+                        KdNode *r = mKdtree.Subdivide(tOspQueue, dynamic_cast<OspSplitCandidate<(splitCandidate));
 #endif
                 }
@@ -2766 +2710 @@
         cout << "finished in " << TimeDiff(startTime, GetTime())*1e-3 << "secs" << endl;
 
-        mVspTree->mVspStats.Stop();
+        mVspTree.mVspStats.Stop();
 }
 

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

@@ -34 +34 @@
 class KdTreeStatistics;
 
+template <typename T> class GtPriority
+{
+public:
+        bool operator() (const T c1, const T c2) const
+        {
+                //return false;
+                return c1->GetPriority() < c2->GetPriority();
+        }
+};
+
 /** A definition for an axis aligned plane.
 */
@@ -84 +94 @@
         float GetPriority() const
         {
-#if 1
                 return mPriority;
-#else
-                return (float) (-mDepth); // for kd tree
-#endif
         }
 
-        friend bool operator<(const SplitCandidate &a, const SplitCandidate &b)
+        /*friend bool operator<(const SplitCandidate &a, const SplitCandidate &b)
         {
                 return a.GetPriority() < b.GetPriority();
-        }
+        }*/
 };
 
@@ -461 +467 @@
 
 
-typedef std::priority_queue<SplitCandidate *> SplitQueue;
-
+typedef std::priority_queue<SplitCandidate *, 
+                                                        std::vector<SplitCandidate *>, 
+                                                        GtPriority<std::vector<SplitCandidate *>::value_type> > SplitQueue;
 
 #if TODO
@@ -511 +518 @@
                 /// how often this branch has missed the max-cost ratio
                 int mMaxCostMisses;
-                // current axis
-                int mAxis;
                 // current priority
                 float mPriority;
@@ -532 +537 @@
                 mProbability(0.0),
                 mMaxCostMisses(0), 
-                mPriority(0),
-                mAxis(0)
+                mPriority(0)
                 {}
                 
@@ -549 +553 @@
                 mBoundingBox(box),
                 mMaxCostMisses(0),
-                mPriority(0),
-                mAxis(0)
+                mPriority(0)
                 {}
 
@@ -562 +565 @@
                 mProbability(0),
                 mMaxCostMisses(0),
-                mAxis(0),
                 mBoundingBox(box)
                 {}
@@ -698 +700 @@
         */
         void SetViewCellsManager(ViewCellsManager *vcm);
-
-
-        /** Collapses the tree with respect to the view cell partition.
-                @returns number of collapsed nodes
-        */
-        int CollapseTree();
 
         /** Returns view cell the current point is located in.
@@ -785 +781 @@
                 }
                 
-                friend bool operator<(const SortableEntry &a, const SortableEntry &b) 
+                friend bool operator<(const SortableEntry &a, const SortableEntry &b)
                 {
                         return a.value < b.value;
@@ -793 +789 @@
         /** faster evaluation of split plane cost for kd axis aligned cells.
         */
-        float EvalSplitCost(const VspTraversalData &data,
-                                                const AxisAlignedBox3 &box,
-                                                const int axis,
-                                                const float &position,
-                                                float &pFront,
-                                                float &pBack) const;
+        float EvalLocalSplitCost(const VspTraversalData &data,
+                                                         const AxisAlignedBox3 &box,
+                                                         const int axis,
+                                                         const float &position,
+                                                         float &pFront,
+                                                         float &pBack) const;
 
         void PrepareConstruction(const VssRayContainer &sampleRays,
@@ -806 +802 @@
         */
         void EvalSplitCandidate(VspTraversalData &tData, VspSplitCandidate &splitData);
-
-        /** Computes priority of the traversal data and stores it in tData.
-        */
-        void EvalPriority(VspTraversalData &tData) const;
 
         /** Evaluates render cost decrease of next split.
@@ -882 +874 @@
                 @returns cost for this split
         */
-        float SelectPlane(const VspTraversalData &tData,
-                                          AxisAlignedPlane &plane,
-                                          float &pFront,
-                                          float &pBack);
+        float SelectSplitPlane(const VspTraversalData &tData,
+                                                   AxisAlignedPlane &plane,
+                                                   float &pFront,
+                                                   float &pBack);
 
         /** Sorts split candidates for surface area heuristics for axis aligned splits.
@@ -899 +891 @@
         /** Computes best cost for axis aligned planes.
         */
-        float BestCostRatioHeuristics(const RayInfoContainer &rays,
+        float EvalLocalCostHeuristics(const RayInfoContainer &rays,
                                                                   const AxisAlignedBox3 &box,
                                                                   const int pvsSize,
@@ -1339 +1331 @@
         /** faster evaluation of split plane cost for kd axis aligned cells.
         */
-        float EvalSplitCost(const OspTraversalData &data,
-                                                const AxisAlignedBox3 &box,
-                                                const int axis,
-                                                const float &position,
-                                                float &pFront,
-                                                float &pBack) const;
+        float EvalLocalSplitCost(const OspTraversalData &data,
+                                                         const AxisAlignedBox3 &box,
+                                                         const int axis,
+                                                         const float &position,
+                                                         float &pFront,
+                                                         float &pBack) const;
 
         /** Evaluates candidate for splitting.
@@ -1429 +1421 @@
         /** Computes best cost for axis aligned planes.
         */
-        float BestCostRatioHeuristics(const RayInfoContainer &rays,
+        float EvalLocalCostHeuristics(const RayInfoContainer &rays,
                                                                   const AxisAlignedBox3 &box,
                                                                   const int pvsSize,
@@ -1622 +1614 @@
 class HierarchyManager
 {
-        /** Default constructor.
-        */
-        HierarchyManager();
+public:
+        /** Constructor taking an object space partition and a view space partition tree.
+        */
+        HierarchyManager(VspTree &vspTree, OspTree &ospTree);
 
         /** Constructs the view space and object space subdivision from a given set of rays
@@ -1636 +1629 @@
 
 public:
-        VspTree *mVspTree;
-        OspTree *mOspTree;
+        VspTree &mVspTree;
+        OspTree &mOspTree;
 
 protected:
@@ -1644 +1637 @@
 
         void PrepareConstruction(const VssRayContainer &sampleRays,
+                                                         const ObjectContainer &objects,
                                                          AxisAlignedBox3 *forcedViewSpace,
                                                          RayInfoContainer &rays);

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

@@ -616 +616 @@
   if (!mLoadViewCells)
   {
+           Debug << "here923 " << vbox << endl;
           mViewCellsManager->SetViewSpaceBox(vbox);
           // construct view cells using it's own set of samples