Changeset 1143

Timestamp:

07/19/06 18:31:33 (18 years ago)

Author:

mattausch

Message:

worked on vsp osp tree

Location:

GTP/trunk/Lib/Vis/Preprocessing/src

Files:

• Environment.cpp (modified) (2 diffs)
• Intersectable.h (modified) (2 diffs)
• KdTree.cpp (modified) (2 diffs)
• KdTree.h (modified) (1 diff)
• Preprocessor.cpp (modified) (2 diffs)
• Pvs.cpp (modified) (2 diffs)
• ViewCellsManager.cpp (modified) (3 diffs)
• ViewCellsParser.cpp (modified) (1 diff)
• VspOspTree.cpp (modified) (33 diffs)
• VspOspTree.h (modified) (8 diffs)

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

@@ -1446 +1446 @@
         RegisterOption("ViewCells.PostProcess.avgCostMaxDeviation",
                         optFloat,
-                        "vsp_bsp_avgcost_max_deviations",
+                        "view_cells_avgcost_max_deviations",
                         "0.5");
 
@@ -2217 +2217 @@
                                         "true");
         
+
+
 /***************************************************************************/
 /*               Object space partition tree related options               */
 /***************************************************************************/
+
 
         RegisterOption("OspTree.Construction.randomize",

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

@@ -34 +34 @@
 
   /// # of object references
-  int mObjectRefs;
+  int mReferences;
 
   enum { MESH_INSTANCE, 
@@ -44 +44 @@
                 };
   
-  Intersectable():mMailbox(0), mObjectRefs(0) {}
+  Intersectable():mMailbox(0), mReferences(0) {}
 
         void SetId(const int id) { mId = id; }

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

@@ -295 +295 @@
     // determine the side of this ray with respect to the plane
     AxisAlignedBox3 box = (*mi)->GetBox();
-
-    if (box.Max(axis) >= position )
+                
+        // for handling multiple objects: keep track of references
+        if (leaf->IsRoot()) 
+                (*mi)->mReferences = 1; // initialise references at root
+        
+        -- (*mi)->mReferences; // remove parent ref
+
+
+        if (box.Max(axis) >= position )
+        {
       front->mObjects.push_back(*mi);
-    
+          ++ (*mi)->mReferences;
+        }
+        
     if (box.Min(axis) < position )
+        {
       back->mObjects.push_back(*mi);
-    
+          ++ (*mi)->mReferences;
+        }
+
+        // store objects referenced in more than one leaf
+        // for easy access
+        ProcessMultipleRefs(back);
+        ProcessMultipleRefs(front);
+
     mStat.objectRefs -= (int)leaf->mObjects.size();
     mStat.objectRefs += objectsBack + objectsFront;
@@ -308 +326 @@
   delete leaf;
   return node;
+}
+
+
+void KdTree::ProcessMultipleRefs(KdLeaf *leaf) const
+{
+        // find objects from multiple kd-leaves
+        ObjectContainer::const_iterator oit, oit_end = leaf->mObjects.end();
+
+        for (oit = leaf->mObjects.begin(); oit != oit_end; ++ oit)
+        {
+                Intersectable *object = *oit;
+                
+                if (object->mReferences > 1)
+                {
+                        leaf->mMultipleObjects.push_back(object);
+                }
+        }
 }
 

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

@@ -540 +540 @@
               );
 
+        /** does some post processing on the objects in the new child leaves.
+        */
+        void ProcessMultipleRefs(KdLeaf *leaf) const;
 
   int mTermMaxNodes;

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

@@ -440 +440 @@
         {
                 mVspTree = new VspTree();
-                mOspTree = new OspTree();
+                //mOspTree = new OspTree();
+                // HACK
+                mOspTree = new OspTree(*mKdTree);
 
                 mViewCellsManager = new VspOspViewCellsManager(mVspTree, mOspTree);
@@ -446 +448 @@
         else if (strcmp(name, "sceneDependent") == 0)
         {
+                Debug << "view cell type: Bsp" << endl;
+
                 //TODO
                 mBspTree = new BspTree();
-
-                Debug << "view cell type: Bsp" << endl;
-                
                 mViewCellsManager = new BspViewCellsManager(mBspTree);
         }

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

@@ -30 +30 @@
                 Intersectable *obj = (*it).first;
 
+                // found kd node
+                // the pvs is the sum of the objects in the leaves in the subtree
+                // We eliminate already accounted kd nodes and objects
+                // using mailboxing. 
                 if (obj->Type() == Intersectable::KD_INTERSECTABLE)
                 {
@@ -51 +55 @@
                                 if (node->IsLeaf())
                                 {
-                                        
                                         KdLeaf *leaf = dynamic_cast<KdLeaf *>(node);
 
                                         pvs += (int)(leaf->mObjects.size() - leaf->mMultipleObjects.size());
 
-                                        ObjectContainer::const_iterator it, it_end = leaf->mMultipleObjects.end();
+                                        // Objects already accounted for can only be found among those
+                                        // which are referenced in more than one leaf
+                                        ObjectContainer::const_iterator oit, oit_end = leaf->mMultipleObjects.end();
+                                        for (oit = leaf->mMultipleObjects.begin(); oit != oit_end; ++ oit)
                                         {
-                                                Intersectable *object = *it;                                            
+                                                Intersectable *object = *oit;                                           
                                                 
                                                 if (!object->Mailed())

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

@@ -2217 +2217 @@
 
 
-
-
 void
 ViewCellsManager::ApplyFilter(ViewCell *viewCell,
@@ -4257 +4255 @@
                         }
 
-                        const int maxDepth = mVspBspTree->mBspStats.maxDepth;
+                        const int maxDepth = mVspBspTree->GetStatistics().maxDepth;
 
                         ViewCellContainer::const_iterator vit, vit_end = mViewCells.end();
@@ -4904 +4902 @@
         long startTime;
 
-        //mHierarchyManager->Construct(constructionRays, objects, &mViewSpaceBox);
-        //mHierarchyManager->Construct2(constructionRays, objects, &mViewSpaceBox);
-        mHierarchyManager->Construct3(constructionRays, objects, &mViewSpaceBox);
-
-        //-- stats
+        if (!mOspTree->GetRoot())
+        {
+                cout << "constructing vsp and osp tree" << endl;
+                //mHierarchyManager->Construct(constructionRays, objects, &mViewSpaceBox);
+                mHierarchyManager->Construct2(constructionRays, objects, &mViewSpaceBox);
+        }
+        else // just build view space partition tree
+        {
+                cout << "constructing only vsp tree" << endl;
+                mHierarchyManager->Construct3(constructionRays, objects, &mViewSpaceBox);
+        }
+
+        // print subdivision statistics
         Debug << mVspTree->GetStatistics() << endl;
 
+        // print view cell statistics
         ResetViewCells();
         Debug << "\nView cells after construction:\n" << mCurrentViewCellsStats << endl;

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

@@ -640 +640 @@
                 mOspTree = new OspTree();
 
-                //mCurrentBspNode = mVspBspTree->GetRoot();
+                // hack
                 mViewCellsManager = new VspOspViewCellsManager(mVspTree, mOspTree);
 

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

@@ -401 +401 @@
 
         if (!mUseKdPvsForHeuristics)
-                Debug << "pvs count method: per object" << endl;
+                Debug << "pvs heuristics: per object" << endl;
         else
-                Debug << "pvs count method: per kd node" << endl;
+                Debug << "pvs heuristics: per kd node" << endl;
 
         mSplitCandidates = new vector<SortableEntry>;
@@ -443 +443 @@
 
 
-void VspTree::ComputeBoundingBox(const RayInfoContainer &rays,
+void VspTree::ComputeBoundingBox(const VssRayContainer &rays,
                                                                  AxisAlignedBox3 *forcedBoundingBox) 
 {       
@@ -454 +454 @@
                 mBoundingBox.Initialize();
 
-                RayInfoContainer::const_iterator rit, rit_end = rays.end();
+                VssRayContainer::const_iterator rit, rit_end = rays.end();
 
                 //-- compute bounding box
         for (rit = rays.begin(); rit != rit_end; ++ rit)
                 {
-                        VssRay *ray = (*rit).mRay;
+                        VssRay *ray = *rit;
 
                         // compute bounding box of view space
@@ -499 +499 @@
 bool VspTree::LocalTerminationCriteriaMet(const VspTraversalData &data) const
 {
-        return(
+        const bool localTerminationCriteriaMet = (
                 ((int)data.mRays->size() <= mTermMinRays) ||
                 (data.mPvs <= mTermMinPvs)   ||
@@ -506 +506 @@
                 (data.mDepth >= mTermMaxDepth)
                 );
+
+        if (0 && localTerminationCriteriaMet)
+        {
+                Debug << "********local termination *********" << endl;
+                Debug << "rays: " << (int)data.mRays->size() << "  " << mTermMinRays << endl;
+                Debug << "pvs: " << data.mPvs << " " << mTermMinPvs << endl;
+                Debug << "p: " <<  data.mProbability << " " << mTermMinProbability << endl;
+                Debug << "avg contri: " << data.GetAvgRayContribution() << " " << mTermMaxRayContribution << endl;
+                Debug << "depth " << data.mDepth << " " << mTermMaxDepth << endl;
+        }
+
+        return localTerminationCriteriaMet;
                 
 }
@@ -512 +524 @@
 bool VspTree::GlobalTerminationCriteriaMet(const VspTraversalData &data) const
 {
-        Debug << "cost misses " << mGlobalCostMisses << " " << mTermGlobalCostMissTolerance << endl;
-        Debug << "leaves " << mVspStats.Leaves() << " " <<  mMaxViewCells << endl;
-
-        return (
-//              mOutOfMemory || 
+        const bool terminationCriteriaMet = (
+                // mOutOfMemory || 
                 (mVspStats.Leaves() >= mMaxViewCells) || 
         (mGlobalCostMisses >= mTermGlobalCostMissTolerance) 
-                );              
+                );
+
+        if (0 && terminationCriteriaMet)
+        {
+                Debug << "********* terminationCriteriaMet *********" << endl;
+                Debug << "cost misses: " << mGlobalCostMisses << " " << mTermGlobalCostMissTolerance << endl;
+                Debug << "leaves: " << mVspStats.Leaves() << " " <<  mMaxViewCells << endl;
+        }
+        return terminationCriteriaMet;
 }
 
@@ -559 +576 @@
         }
                 
+        //
         viewCell->mLeaf = leaf;
 
         viewCell->SetVolume(tData.mProbability);
     leaf->mProbability = tData.mProbability;
-
-        mVspStats.contributingSamples += conSamp;
-        mVspStats.sampleContributions += (int)sampCon;
-
-        // finally evaluate statistics for this leaf
-        EvaluateLeafStats(tData);
 }
 
@@ -632 +644 @@
                 
                 // delete old view cell
-                delete tData.mNode->GetViewCell();
+                delete tData.mNode->mViewCell;
                 // delete old leaf node
                 DEL_PTR(tData.mNode);
         }
 
-        // subdivision terminated
-        if (newNode->IsLeaf())
-        {
-                //-- create new view cell
-                //CreateViewCell(tData);
-        
+        if (newNode->IsLeaf()) // subdivision terminated
+        {
+                //CreateViewCell(tData); // create new view cell
+
+                VspLeaf *leaf = dynamic_cast<VspLeaf *>(newNode);
+                ViewCell *viewCell = leaf->GetViewCell();
+
+                int conSamp = 0;
+                float sampCon = 0.0f;
+
+
+                //-- store pvs optained from rays
+                AddSamplesToPvs(leaf, *tData.mRays, sampCon, conSamp);
+
+                // update scalar pvs size value
+                mViewCellsManager->SetScalarPvsSize(viewCell, viewCell->GetPvs().CountPvs());
+
+                mVspStats.contributingSamples += conSamp;
+                mVspStats.sampleContributions += (int)sampCon;
+
                 //-- store additional info
                 if (mStoreRays)
@@ -771 +797 @@
 
         // explicitely create front and back view cell
-        CreateViewCell(frontData, true);
-        CreateViewCell(backData, true);
+        CreateViewCell(frontData, false);
+        CreateViewCell(backData, false);
 
         
@@ -907 +933 @@
   
         ViewCellLeaf *vc = leaf->GetViewCell();
-  
-        
+ 
         // add contributions from samples to the PVS
         for (it = rays.begin(); it != it_end; ++ it)
@@ -922 +947 @@
                 if (obj) 
                 {
-                        Intersectable *entry;
-
                         // potentially visible kd cells
                         if (mStoreKdPvs)
@@ -945 +968 @@
                 if (obj) 
                 {
-                        Intersectable *entry;
-
                         // potentially visible kd cells
                         if (mUseKdPvsForHeuristics)
@@ -2684 +2705 @@
 OspTree::OspTree():
 mRoot(NULL),
-mTimeStamp(1)
+mTimeStamp(1),
+mCopyFromKdTree(false)
+{
+        ReadEnvironment();
+
+        mSplitCandidates = new vector<SortableEntry>;
+}
+
+
+OspTree::OspTree(const KdTree &kdTree)
+{
+        ReadEnvironment();
+
+        // copy values from kd tree
+        mCopyFromKdTree = true;
+        mBoundingBox = kdTree.GetBox();
+        mRoot = kdTree.GetRoot();
+}
+
+
+OspTree::~OspTree()
+{
+        KdIntersectableMap::iterator it, it_end = mKdIntersectables.end();
+
+        for (it = mKdIntersectables.begin(); it != mKdIntersectables.end(); ++ it)
+        {
+                DEL_PTR((*it).second);
+        }
+
+        // if not using kd tree root
+        if (!mCopyFromKdTree)
+                DEL_PTR(mRoot);
+}
+
+
+void OspTree::ReadEnvironment()
 {
         bool randomize = false;
@@ -2748 +2804 @@
         Debug << "split borders: " << mSplitBorder << endl;
         Debug << "render cost decrease weight: " << mRenderCostDecreaseWeight << endl;
-
-
-        mSplitCandidates = new vector<SortableEntry>;
-
         Debug << endl;
 }
 
 
-OspTree::~OspTree()
-{
-        KdIntersectableMap::iterator it, it_end = mKdIntersectables.end();
-
-        for (it = mKdIntersectables.begin(); it != mKdIntersectables.end(); ++ it)
-        {
-                DEL_PTR((*it).second);
-        }
-}
-
-
-void OspTree::SplitObjects(const AxisAlignedPlane & splitPlane,
+void OspTree::SplitObjects(KdLeaf *parent,
+                                                   const AxisAlignedPlane& splitPlane,
                                                    const ObjectContainer &objects,
                                                    ObjectContainer &front,
@@ -2777 +2819 @@
         {
                 Intersectable *object = *oit;
+                
+                // initialise
+                if (parent->IsRoot())
+                        object->mReferences = 1;
+
+                // remove parent ref
+                -- object->mReferences;
 
                 // determine the side of this ray with respect to the plane
@@ -2784 +2833 @@
                 {
             front.push_back(object);
-                        ++ object->mObjectRefs;
+                        ++ object->mReferences;
                 }
 
@@ -2790 +2839 @@
                 {
                         back.push_back(object);
-                        ++ object->mObjectRefs;
-                }
-
-                // remove parent reference
-                -- object->mObjectRefs;
+                        ++ object->mReferences;
+                }
         }
 
@@ -2890 +2936 @@
         node->SetupChildLinks(back, front);
 
-        SplitObjects(splitPlane, leaf->mObjects, front->mObjects, back->mObjects);
-        //ProcessLeafObjects(leaf, front, back);
-    
+        SplitObjects(leaf, splitPlane, leaf->mObjects, front->mObjects, back->mObjects);
+
+        ProcessMultipleRefs(front);
+    ProcessMultipleRefs(back);
+
         backData.mNode = back;
         frontData.mNode = front;
@@ -3604 +3652 @@
 
 
-#if DEPRECATED
-void OspTree::ProcessLeafObjects(KdLeaf *parent, KdLeaf *front, KdLeaf *back) const
-{
-        if (parent)
-        {
-                // remove the parents from the set
-                ObjectContainer::const_iterator oit, oit_end = parent->mObjects.end();
-
-                for (oit = parent->mObjects.begin(); oit != oit_end; ++ oit)
-                {
-                        Intersectable *object = *oit;
-
-                        set<KdLeaf *>::iterator kdit = object->mKdLeaves.find(parent);
-
-                        // remove parent leaf
-                        if (kdit != object->mKdLeaves.end())
-                                object->mKdLeaves.erase(kdit);
-                }
-        }
-
-        //Intersectable::NewMail();
-
-        if (front)
-        {
-                // Add front to leaf kd cells
-                ObjectContainer::const_iterator oit, oit_end = front->mObjects.end();
-
-                for (oit = front->mObjects.begin(); oit != oit_end; ++ oit)
-                {
-                        Intersectable *object = *oit;
-                        object->mKdLeaves.insert(front);
-                }
-        }
-
-        if (back)
-        {
-                // Add back to leaf kd cells
-                ObjectContainer::const_iterator oit, oit_end = back->mObjects.end();
-
-                for (oit = back->mObjects.begin(); oit != oit_end; ++ oit)
-                {
-                        Intersectable *object = *oit;
-                        object->mKdLeaves.insert(back); 
-                }
-        }
-
-        // note: can find out about multiple objects only now after adding and deleting
-        // finished 
-        if (front)
-        {
-                // find objects from multiple kd-leaves
-                ObjectContainer::const_iterator oit, oit_end = front->mObjects.end();
-
-                for (oit = front->mObjects.begin(); oit != oit_end; ++ oit)
-                {
-                        Intersectable *object = *oit;
-
-                        if (object->mKdLeaves.size() > 1)
-                                front->mMultipleObjects.push_back(object);
-                }
-        }
-
-        if (back) 
-        {
-                // find objects from multiple kd-leaves
-                ObjectContainer::const_iterator oit, oit_end = back->mObjects.end();
-
-                for (oit = back->mObjects.begin(); oit != oit_end; ++ oit)
-                {
-                        Intersectable *object = *oit;
-
-                        if (object->mKdLeaves.size() > 1)
-                                back->mMultipleObjects.push_back(object);
-                }
-        }
-        
-}
-#endif
+void OspTree::ProcessMultipleRefs(KdLeaf *leaf) const
+{
+        // find objects from multiple kd-leaves
+        ObjectContainer::const_iterator oit, oit_end = leaf->mObjects.end();
+
+        for (oit = leaf->mObjects.begin(); oit != oit_end; ++ oit)
+        {
+                Intersectable *object = *oit;
+                
+                if (object->mReferences > 1)
+                {
+                        leaf->mMultipleObjects.push_back(object);
+                }
+        }
+}
+
 
 void OspTree::CollectLeaves(vector<KdLeaf *> &leaves) const
@@ -3972 +3958 @@
 
 
+
 /********************************************************************/
 /*               class HierarchyManager implementation              */
@@ -4003 +3990 @@
                                                                                          RayInfoContainer &rays)
 {
-        // get clipped rays
-        mVspTree.ProcessRays(sampleRays, rays);
-
         // store pointer to this tree
         VspTree::VspSplitCandidate::sVspTree = &mVspTree;
@@ -4011 +3995 @@
 
         // compute view space bounding box
-        mVspTree.ComputeBoundingBox(rays, forcedViewSpace);
-
+        mVspTree.ComputeBoundingBox(sampleRays, forcedViewSpace);
+
+        // initialise termination criteria
         mVspTree.mTermMinProbability *= mBoundingBox.GetVolume();
         mVspTree.mGlobalCostMisses = 0;
 
+        // get clipped rays
+        mVspTree.ProcessRays(sampleRays, rays);
 
         const int pvsSize = mVspTree.ComputePvsSize(rays);
         
-        cout <<  "here450 pvs size: " << pvsSize << endl;
-        // -- prepare view space partition
+        Debug <<  "pvs size: " << pvsSize << endl;
+        Debug <<  "rays size: " << rays.size() << endl;
+
+        //-- prepare view space partition
 
         // add first candidate for view space partition
@@ -4038 +4027 @@
 
         // create first view cell
-        mVspTree.CreateViewCell(vData, true);
+        mVspTree.CreateViewCell(vData, false);
                 
         // add first view cell to all the objects view cell pvs
@@ -4088 +4077 @@
         const float prop = mOspTree.mBoundingBox.GetVolume();
 
-        cout <<  "here40 pvs size: " << pvsSize << endl;
         // first osp traversal data
         OspTree::OspTraversalData oData(kdleaf,
@@ -4098 +4086 @@
 
                 
-        //mOspTree.ProcessLeafObjects(NULL, kdleaf, NULL);
+        //mOspTree.ProcessMultipleRefs(NULL, kdleaf, NULL);
 
         // compute first split candidate
@@ -4133 +4121 @@
 
 
+void HierarchyManager::Construct(const VssRayContainer &sampleRays,
+                                                                 const ObjectContainer &objects,
+                                                                 AxisAlignedBox3 *forcedViewSpace)
+{
+        RayInfoContainer *objectSpaceRays = new RayInfoContainer();
+        RayInfoContainer *viewSpaceRays = new RayInfoContainer();
+
+        // prepare vsp and osp trees for traversal
+        PrepareConstruction(sampleRays, objects, forcedViewSpace, *viewSpaceRays, *objectSpaceRays);
+
+        mVspTree.mVspStats.Reset();
+        mVspTree.mVspStats.Start();
+
+        cout << "Constructing view space / object space tree ... \n";
+        const long startTime = GetTime();       
+        
+        int i = 0;
+        while (!FinishedConstruction())
+        {
+                mCurrentCandidate = NextSplitCandidate();
+           
+                const bool globalTerminationCriteriaMet = 
+                        GlobalTerminationCriteriaMet(mCurrentCandidate);
+
+                cout << "view cells: " << i ++ << endl;
+
+                // cost ratio of cost decrease / totalCost
+                const float costRatio = mCurrentCandidate->GetPriority() / mTotalCost;
+                //Debug << "cost ratio: " << costRatio << endl;
+
+                if (costRatio < mTermMinGlobalCostRatio)
+                        ++ mGlobalCostMisses;
+
+                //-- subdivide leaf node
+
+                // we have either a object space or view space split
+                if (mCurrentCandidate->Type() == SplitCandidate::VIEW_SPACE)
+                {
+                        VspTree::VspSplitCandidate *sc = 
+                                dynamic_cast<VspTree::VspSplitCandidate *>(mCurrentCandidate);
+
+                        VspNode *r = mVspTree.Subdivide(mTQueue, *sc, globalTerminationCriteriaMet);
+                }
+                else // object space split
+                {                       
+                        OspTree::OspSplitCandidate *sc = 
+                                dynamic_cast<OspTree::OspSplitCandidate *>(mCurrentCandidate);
+
+                        KdNode *r = mOspTree.Subdivide(mTQueue, *sc, globalTerminationCriteriaMet);
+                }
+
+                // reevaluate candidates affected by the split
+                // for view space splits, this would be object space splits
+                // and other way round
+                RepairQueue();
+
+                DEL_PTR(mCurrentCandidate);
+        }
+
+        cout << "finished in " << TimeDiff(startTime, GetTime())*1e-3 << " secs" << endl;
+
+        mVspTree.mVspStats.Stop();
+}
+
+
 void HierarchyManager::Construct2(const VssRayContainer &sampleRays,
                                                                   const ObjectContainer &objects,
@@ -4139 +4192 @@
         RayInfoContainer *viewSpaceRays = new RayInfoContainer();
         RayInfoContainer *objectSpaceRays = new RayInfoContainer();
+
+        /////////////////////////////////////////////////////////////
+        // view space space partition
+        /////////////////////////////////////////////////////////////
 
         // makes no sense otherwise because only one kd cell available
@@ -4148 +4205 @@
         mVspTree.mStoreKdPvs = false;
 
-        mTQueue.Push(PrepareVsp(sampleRays, forcedViewSpace, *viewSpaceRays));
+        SplitCandidate *sc = PrepareVsp(sampleRays, forcedViewSpace, *viewSpaceRays);
+        mTQueue.Push(sc);
 
         long startTime = GetTime();
         cout << "starting vsp contruction ... " << endl;
+
+        mVspTree.mVspStats.Reset();
+        mVspTree.mVspStats.Start();
+
         int i = 0;
 
@@ -4186 +4248 @@
         
         
-        ///////////////////////////////////////////////////////////////
-        //-- object space partition
+        /////////////////////////////////////////////////////////////
+        // object space partition
         /////////////////////////////////////////////////////////////
 
@@ -4239 +4301 @@
                                                                   AxisAlignedBox3 *forcedViewSpace)
 {
+        mVspTree.mVspStats.Reset();
+        mVspTree.mVspStats.Start();
+
         RayInfoContainer *viewSpaceRays = new RayInfoContainer();
-
+        
         SplitCandidate *sc = PrepareVsp(sampleRays, forcedViewSpace, *viewSpaceRays);
         mTQueue.Push(sc);
@@ -4257 +4322 @@
 
                 cout << "vsp nodes: " << i ++ << endl;
-
+                
                 // cost ratio of cost decrease / totalCost
                 const float costRatio = splitCandidate->GetPriority() / mTotalCost;
@@ -4266 +4331 @@
 
                 //-- subdivide leaf node
-
+        
                 // we have either a object space or view space split
                 VspTree::VspSplitCandidate *sc = 
@@ -4278 +4343 @@
 
         cout << "finished in " << TimeDiff(startTime, GetTime())*1e-3 << " secs" << endl;
-        mVspTree.mVspStats.Stop();
-}
-
-
-
-void HierarchyManager::Construct(const VssRayContainer &sampleRays,
-                                                                 const ObjectContainer &objects,
-                                                                 AxisAlignedBox3 *forcedViewSpace)
-{
-        RayInfoContainer *objectSpaceRays = new RayInfoContainer();
-        RayInfoContainer *viewSpaceRays = new RayInfoContainer();
-
-        // prepare vsp and osp trees for traversal
-        PrepareConstruction(sampleRays, objects, forcedViewSpace, *viewSpaceRays, *objectSpaceRays);
-
-        mVspTree.mVspStats.Reset();
-        mVspTree.mVspStats.Start();
-
-        cout << "Constructing view space / object space tree ... \n";
-        const long startTime = GetTime();       
-        
-        int i = 0;
-        while (!FinishedConstruction())
-        {
-                mCurrentCandidate = NextSplitCandidate();
-           
-                const bool globalTerminationCriteriaMet = 
-                        GlobalTerminationCriteriaMet(mCurrentCandidate);
-
-                cout << "view cells: " << i ++ << endl;
-
-                // cost ratio of cost decrease / totalCost
-                const float costRatio = mCurrentCandidate->GetPriority() / mTotalCost;
-                //Debug << "cost ratio: " << costRatio << endl;
-
-                if (costRatio < mTermMinGlobalCostRatio)
-                        ++ mGlobalCostMisses;
-
-                //-- subdivide leaf node
-
-                // we have either a object space or view space split
-                if (mCurrentCandidate->Type() == SplitCandidate::VIEW_SPACE)
-                {
-                        VspTree::VspSplitCandidate *sc = 
-                                dynamic_cast<VspTree::VspSplitCandidate *>(mCurrentCandidate);
-
-                        VspNode *r = mVspTree.Subdivide(mTQueue, *sc, globalTerminationCriteriaMet);
-                }
-                else // object space split
-                {                       
-                        OspTree::OspSplitCandidate *sc = 
-                                dynamic_cast<OspTree::OspSplitCandidate *>(mCurrentCandidate);
-
-                        KdNode *r = mOspTree.Subdivide(mTQueue, *sc, globalTerminationCriteriaMet);
-                }
-
-                // reevaluate candidates affected by the split
-                // for view space splits, this would be object space splits
-                // and other way round
-                RepairQueue();
-
-                DEL_PTR(mCurrentCandidate);
-        }
-
-        cout << "finished in " << TimeDiff(startTime, GetTime())*1e-3 << " secs" << endl;
-
         mVspTree.mVspStats.Stop();
 }

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

@@ -34 +34 @@
 class OspTree;
 class KdIntersectable;
-
-
-
+class KdTree;
+class VspTree;
 class KdTreeStatistics;
+
+
 
 template <typename T> class GtPriority
@@ -410 +411 @@
 class VspLeaf: public VspNode 
 {
+        friend VspTree;
 
 public:
@@ -802 +804 @@
                                                          float &pBack) const;
 
-        void ComputeBoundingBox(const RayInfoContainer &rays,
-                AxisAlignedBox3 *forcedBoundingBox);
+        void ComputeBoundingBox(const VssRayContainer &rays,
+                                                        AxisAlignedBox3 *forcedBoundingBox);
 
         /** Evaluates candidate for splitting.
@@ -1262 +1264 @@
         OspTree();
 
+        OspTree(const KdTree &kdTree);
+
         /** Default destructor.
         */
@@ -1481 +1485 @@
                 OspTraversalData &backData);
 
-        void SplitObjects(const AxisAlignedPlane & splitPlane,
+        void SplitObjects(KdLeaf *leaf,
+                                          const AxisAlignedPlane & splitPlane,
                                           const ObjectContainer &objects,
                                           ObjectContainer &front,
                                           ObjectContainer &back);
 
-#if DEPRECATED
-         /** does some post processing on the objects in the new child leaves.
-         */
-        void ProcessLeafObjects(KdLeaf *parent, KdLeaf *front, KdLeaf *back) const;
-#endif
+        /** does some post processing on the objects in the new child leaves.
+        */
+        void ProcessMultipleRefs(KdLeaf *leaf) const;
+
         /** Selects an axis aligned for the next split.
                 @returns cost for this split
@@ -1603 +1607 @@
         */
         void ComputeBoundingBox(const ObjectContainer &objects,
-                AxisAlignedBox3 *forcedBoundingBox);
+                                                        AxisAlignedBox3 *forcedBoundingBox);
 
         void CollectDirtyCandidates(OspSplitCandidate *sc,
@@ -1616 +1620 @@
                 RayInfoContainer &rays);
 
+
+        void ReadEnvironment();
 
 protected:
@@ -1700 +1706 @@
         /// stores the kd node intersectables used for pvs
         KdIntersectableMap mKdIntersectables;
+
+
+private:
+
+        bool mCopyFromKdTree;
 };