Changeset 2210 for GTP/trunk

Timestamp:

03/08/07 13:23:13 (18 years ago)

Author:

mattausch

Message:

improved performance of osp

Location:

GTP/trunk/Lib/Vis/Preprocessing

Files:

• scripts/preprocess_visibility.env (modified) (2 diffs)
• src/BvHierarchy.cpp (modified) (42 diffs)
• src/BvHierarchy.h (modified) (11 diffs)
• src/HierarchyManager.cpp (modified) (1 diff)
• src/Mutation.cpp (modified) (2 diffs)
• src/SamplingStrategy.cpp (modified) (2 diffs)
• src/ViewCell.cpp (modified) (8 diffs)
• src/VspTree.cpp (modified) (16 diffs)
• src/VspTree.h (modified) (2 diffs)

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

@@ -24 +24 @@
         useGlDebugger false
 # 0 = INTERNAL          1 = MLRT
-        rayCastMethod 0
+        rayCastMethod 1
         
         type combined
@@ -128 +128 @@
         importRandomViewCells false
 
-        useKdPvs true
+        useKdPvs false
         useKdPvsAfterFiltering true
         # samples used for view cell construction

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

@@ -237 +237 @@
 mRoot(NULL),
 mTimeStamp(1),
-mIsInitialSubdivision(false),
-mCachedObjects(NULL)
+mIsInitialSubdivision(false)
 {
         ReadEnvironment();
@@ -394 +393 @@
         mNodeTimer.Entry();
 
+/*
 #if STORE_VIEWCELLS_WITH_BVH
-        AssociateViewCellsWithObjects(sc.mFrontObjects);
-        AssociateViewCellsWithObjects(sc.mBackObjects);
+        AssociateViewCellsWithObjects(sc.mSampledFrontObjects);
+        AssociateViewCellsWithObjects(sc.mSampledBackObjects);
 #endif  
+*/
         const BvhTraversalData &tData = sc.mParentData;
         BvhLeaf *leaf = tData.mNode;
@@ -451 +452 @@
         backData.mNode = back;
 
+        backData.mSampledObjects = new ObjectContainer();
+        frontData.mSampledObjects = new ObjectContainer();
+
+        *backData.mSampledObjects = sc.mSampledBackObjects;
+        *frontData.mSampledObjects = sc.mSampledFrontObjects;
+
         back->mObjects = sc.mBackObjects;
         front->mObjects = sc.mFrontObjects;
@@ -456 +463 @@
         // if the number of rays is too low, no assumptions can be made
         // (=> switch to surface area heuristics?)
-        frontData.mNumRays = CountRays(sc.mFrontObjects);
-        backData.mNumRays = CountRays(sc.mBackObjects);
+        frontData.mNumRays = CountRays(sc.mSampledFrontObjects);
+        backData.mNumRays = CountRays(sc.mSampledBackObjects);
 
         AssociateObjectsWithLeaf(back);
@@ -465 +472 @@
         //-- compute pvs correction to cope with undersampling
 
-        frontData.mPvs = (float)CountViewCells(front->mObjects);
-        backData.mPvs = (float)CountViewCells(back->mObjects);
+        frontData.mPvs = (float)sc.mNumFrontViewCells;//(float)CountViewCells(sc.mSampledFrontObjects);
+        backData.mPvs = (float)sc.mNumBackViewCells;//(float)CountViewCells(sc.mSampledBackObjects);
 
         frontData.mCorrectedPvs = sc.mCorrectedFrontPvs;
@@ -474 +481 @@
         // compute probability of this node being visible, 
         // i.e., volume of the view cells that can see this node
-        frontData.mVolume = EvalViewCellsVolume(sc.mFrontObjects) / GetViewSpaceVolume();
-        backData.mVolume = EvalViewCellsVolume(sc.mBackObjects) / GetViewSpaceVolume();
+        frontData.mVolume = sc.mVolumeFrontViewCells;//EvalViewCellsVolume(sc.mSampledFrontObjects) / GetViewSpaceVolume();
+        backData.mVolume = sc.mVolumeBackViewCells;//EvalViewCellsVolume(sc.mSampledBackObjects) / GetViewSpaceVolume();
 
         frontData.mCorrectedVolume = sc.mCorrectedFrontVolume;
@@ -493 +500 @@
                 AssignSortedObjects(sc, frontData, backData);
         }
-
+/*
 #if STORE_VIEWCELLS_WITH_BVH
-        ReleaseViewCells(sc.mFrontObjects);
-        ReleaseViewCells(sc.mBackObjects);
+        ReleaseViewCells(sc.mSampledFrontObjects);
+        ReleaseViewCells(sc.mSampledBackObjects);
 #endif
-
+*/
         mNodeTimer.Exit();
 
@@ -637 +644 @@
 #if STORE_VIEWCELLS_WITH_BVH
         // fill view cells cache
-        AssociateViewCellsWithObjects(*splitCandidate.mParentData.mSortedObjects[3]);
+        AssociateViewCellsWithObjects(*splitCandidate.mParentData.mSampledObjects);
 #endif
 
         if (computeSplitPlane)
         {
+                splitCandidate.mFrontObjects.clear();
+                splitCandidate.mBackObjects.clear();
+                splitCandidate.mSampledFrontObjects.clear();
+                splitCandidate.mSampledBackObjects.clear();
+
                 const bool sufficientSamples = 
                         splitCandidate.mParentData.mNumRays > mMinRaysForVisibility;
@@ -663 +675 @@
                 splitCandidate.SetMaxCostMisses(maxCostRatioViolated ? 
                                                                                 previousMisses + 1 : previousMisses);
-        }
+
+                StoreSampledObjects(splitCandidate.mSampledFrontObjects, splitCandidate.mFrontObjects);
+                StoreSampledObjects(splitCandidate.mSampledBackObjects, splitCandidate.mBackObjects);
+        }
+
         mPlaneTimer.Exit();
 
@@ -672 +688 @@
 
         // avg contribution of a ray to a pvs
-        const float pvs = (float)CountViewCells(leaf->mObjects);
+        const float pvs = (float)CountViewCells(*tData.mSampledObjects);
         const float avgRayContri = AvgRayContribution((int)pvs, tData.mNumRays);
 
@@ -679 +695 @@
         const float viewSpaceVol = GetViewSpaceVolume();
 
-        const float oldVolume = EvalViewCellsVolume(leaf->mObjects) / viewSpaceVol;
+        const float oldVolume = EvalViewCellsVolume(*tData.mSampledObjects) / viewSpaceVol;
         const float oldRatio = (tData.mVolume) > 0 ? oldVolume / tData.mVolume : 1;
         const float parentVol = tData.mCorrectedVolume * oldRatio;
@@ -685 +701 @@
         // this leaf is a pvs entry in all the view cells
         // that see one of the objects.
-        const float frontVol = EvalViewCellsVolume(splitCandidate.mFrontObjects) / viewSpaceVol;
-        const float backVol = EvalViewCellsVolume(splitCandidate.mBackObjects) / viewSpaceVol;
+        splitCandidate.mVolumeFrontViewCells = EvalViewCellsVolume(splitCandidate.mSampledFrontObjects) / viewSpaceVol;
+        splitCandidate.mVolumeBackViewCells = EvalViewCellsVolume(splitCandidate.mSampledBackObjects) / viewSpaceVol;
+
+        splitCandidate.mNumFrontViewCells = CountViewCells(splitCandidate.mSampledFrontObjects);
+        splitCandidate.mNumBackViewCells = CountViewCells(splitCandidate.mSampledBackObjects);
 
         splitCandidate.mCorrectedFrontVolume = 
-                mHierarchyManager->EvalCorrectedPvs(frontVol, parentVol, avgRayContri);
+                mHierarchyManager->EvalCorrectedPvs(splitCandidate.mVolumeFrontViewCells, parentVol, avgRayContri);
         
         splitCandidate.mCorrectedBackVolume = 
-                mHierarchyManager->EvalCorrectedPvs(backVol, parentVol, avgRayContri);
+                mHierarchyManager->EvalCorrectedPvs(splitCandidate.mVolumeBackViewCells, parentVol, avgRayContri);
         
         const float relfrontCost = splitCandidate.mCorrectedFrontVolume * 
@@ -707 +726 @@
 
         // increase in pvs entries
-        const int pvsEntriesIncr = EvalPvsEntriesIncr(splitCandidate, avgRayContri);
+        const int pvsEntriesIncr = EvalPvsEntriesIncr(splitCandidate, 
+                                                                                                  avgRayContri, 
+                                                                                                  (int)pvs, 
+                                                                                                  splitCandidate.mNumFrontViewCells, 
+                                                                                                  splitCandidate.mNumBackViewCells);
+
         splitCandidate.SetPvsEntriesIncr(pvsEntriesIncr);
 
@@ -715 +739 @@
                  << " avg ray contri: " << avgRayContri << " ratio: " << oldRatio 
                  << " parent: " << parentVol << " old vol: " << oldVolume 
-                 << " frontvol: " << frontVol << " corr. " << splitCandidate.mCorrectedFrontVolume 
-                 << " backvol: " << backVol << " corr. " << splitCandidate.mCorrectedBackVolume << endl;
+                 << " frontvol: " << splitCandidate.mVolumeFrontViewCells << " corr. " << splitCandidate.mCorrectedFrontVolume 
+                 << " backvol: " << splitCandidate.mVolumeBackViewCells << " corr. " << splitCandidate.mCorrectedBackVolume << endl;
         }
 
@@ -733 +757 @@
 
 #if STORE_VIEWCELLS_WITH_BVH
-        ReleaseViewCells(*splitCandidate.mParentData.mSortedObjects[3]);
+        ReleaseViewCells(*splitCandidate.mParentData.mSampledObjects);
 #endif
 
@@ -741 +765 @@
 
 int BvHierarchy::EvalPvsEntriesIncr(BvhSubdivisionCandidate &splitCandidate, 
-                                                                        const float avgRayContri) //const
-{
-        const float oldPvsSize = (float)CountViewCells(splitCandidate.mParentData.mNode->mObjects);
+                                                                        const float avgRayContri,
+                                                                        const int numParentViewCells,
+                                                                        const int numFrontViewCells,
+                                                                        const int numBackViewCells) //const
+{
+        const float oldPvsSize = (float)numParentViewCells;//CountViewCells(*splitCandidate.mParentData.mSampledObjects);
         const float oldPvsRatio = (splitCandidate.mParentData.mPvs > 0) ? oldPvsSize / splitCandidate.mParentData.mPvs : 1;
 
         const float parentPvs = splitCandidate.mParentData.mCorrectedPvs * oldPvsRatio;
 
-        const int frontViewCells = CountViewCells(splitCandidate.mFrontObjects);
-        const int backViewCells = CountViewCells(splitCandidate.mBackObjects);
+        const int frontViewCells = numFrontViewCells;//CountViewCells(splitCandidate.mSampledFrontObjects);
+        const int backViewCells = numBackViewCells;//CountViewCells(splitCandidate.mSampledBackObjects);
         
         splitCandidate.mCorrectedFrontPvs = 
@@ -976 +1003 @@
         const float cost = (tData.mNode->GetBoundingBox().Size().DrivingAxis() == axis) ? -1.0f : 0.0f;
 #else
-        const float oldRenderCost = EvalRenderCost(tData.mNode->mObjects);
+        const float oldRenderCost = EvalAbsCost(tData.mLeaf->mObjects) / EvalProbability(tData.mSampledObjects);
         const float newRenderCost = EvalRenderCost(objectsFront) + EvalRenderCost(objectsBack);
 
@@ -1196 +1223 @@
                 Intersectable *obj = (*cit).mObject;
 
-                const float renderCost = mViewCellsManager->EvalRenderCost(obj);
+                const float renderCost = ViewCellsManager::EvalRenderCost(obj);
                 
                 objectsLeft += renderCost;
@@ -1329 +1356 @@
         float volRight = totalVol;
         
-#if USE_BETTER_RENDERCOST_EST
+#if 1//USE_BETTER_RENDERCOST_EST
         const float nTotalObjects = EvalAbsCost(tData.mNode->mObjects);
         float nObjectsLeft = 0;
@@ -1386 +1413 @@
                 nObjectsLeft += rc;
                 nObjectsRight -= rc;
-                
-                // split is only valid if #objects on left and right is not zero
-                const bool noValidSplit = ((nObjectsLeft <= Limits::Small) || 
-                                                                   (nObjectsRight <= Limits::Small));
+        
 #else
                 ++ nObjectsLeft;
                 -- nObjectsRight;
-
+#endif
+        
                 // split is only valid if #objects on left and right is not zero
-                const bool noValidSplit = !nObjectsLeft || !nObjectsRight;
-
-#endif
-                
+                const bool noValidSplit = (nObjectsRight <= Limits::Small);
+
                 // the heuristics
             const float sum = noValidSplit ? 
@@ -1531 +1554 @@
 
         
-        CollectViewCells(tData.mNode->mObjects, 
+        CollectViewCells(*tData.mSampledObjects, 
                                          viewCells, 
                                          setCounter, 
@@ -1851 +1874 @@
         ///////////////
         //-- render cost heuristics
+        const float objRenderCost = EvalAbsCost(objects);
 
         const float viewSpaceVol = mViewCellsManager->GetViewSpaceBox().GetVolume();
@@ -1856 +1880 @@
         // probability that view point lies in a view cell which sees this node
         const float p = EvalViewCellsVolume(objects) / viewSpaceVol;
-    const float objRenderCost = EvalAbsCost(objects);
         
         return objRenderCost * p;
+}
+
+
+float BvHierarchy::EvalProbability(const ObjectContainer &objects)// const
+{       
+        const float viewSpaceVol = mViewCellsManager->GetViewSpaceBox().GetVolume();
+        
+        // probability that view point lies in a view cell which sees this node
+        return EvalViewCellsVolume(objects) / viewSpaceVol;
 }
 
@@ -1941 +1973 @@
 
 
+int BvHierarchy::CollectViewCells(const ObjectContainer &objects, 
+                                                                  ViewCellContainer &viewCells,
+                                                                  const bool setCounter,
+                                                                  const bool onlyUnmailedRays)// const
+{
+        ViewCell::NewMail();
+
+        ObjectContainer::const_iterator oit, oit_end = objects.end();
+
+        // use mailing to avoid dublicates
+        const bool useMailBoxing = true;
+
+        int numRays = 0;
+        // loop through all object and collect view cell pvs of this node
+        for (oit = objects.begin(); oit != oit_end; ++ oit)
+        {
+                // use mailing to avoid duplicates
+                numRays += CollectViewCells(*oit, viewCells, useMailBoxing, setCounter, onlyUnmailedRays);
+        }
+
+        return numRays;
+}
+
 
 #if STORE_VIEWCELLS_WITH_BVH
@@ -1953 +2008 @@
                 (*oit)->DelViewCells();
         }
-
-        DEL_PTR(mCachedObjects);
-}
-
-
-void BvHierarchy::AssociateViewCellsWithObjects(const ObjectContainer &objects)// const
+}
+
+
+void BvHierarchy::AssociateViewCellsWithObjects(const ObjectContainer &objects) const
 {
         ObjectContainer::const_iterator oit, oit_end = objects.end();
 
         const bool useMailBoxing = true;
-
-        mCachedObjects = new ObjectContainer();
+        VssRay::NewMail();
         
         for (oit = objects.begin(); oit != oit_end; ++ oit)
         {
-                if (!(*oit)->GetOrCreateRays()->empty())
-                {
                         ViewCell::NewMail();
                         // use mailing to avoid duplicates
                         AssociateViewCellsWithObject(*oit, useMailBoxing);
-                        
-                        mCachedObjects->push_back(*oit);
-                }
         }
 }
@@ -1982 +2029 @@
 int BvHierarchy::AssociateViewCellsWithObject(Intersectable *obj, const bool useMailBoxing) const
 {
+        int nRays = 0;
+
         if (!obj->GetOrCreateViewCells()->empty())
         {
-                cerr << "AssociateViewCellsWithObject: view cells cache error" << endl;
-                exit(0);
+                cerr << "AssociateViewCellsWithObject: view cells cache not working" << endl;
         }
 
@@ -2001 +2049 @@
                 //              continue;
                 mHierarchyManager->mVspTree->GetViewCells(*ray, *objViewCells);
-        }
-
-        return (int)vssRays->size();
+                
+                if (!useMailBoxing || !ray->Mailed())
+                {
+                        if (useMailBoxing)
+                                ray->Mail();
+
+                        ++ nRays;
+                }
+        }
+
+        return nRays;
 }
 
@@ -2014 +2070 @@
         if (obj->GetOrCreateViewCells()->empty())
         {
-                cerr << "h";//CountViewCells: view cells empty, view cells cache not working" << endl;
+                //cerr << "h";//CountViewCells: view cells empty, view cells cache not working" << endl;
                 return CountViewCellsFromRays(obj);
         }
@@ -2177 +2233 @@
 }
 
-
-int BvHierarchy::CollectViewCells(const ObjectContainer &objects, 
-                                                                  ViewCellContainer &viewCells,
-                                                                  const bool setCounter,
-                                                                  const bool onlyUnmailedRays)// const
-{
-        ViewCell::NewMail();
-
-        // use mailing to avoid dublicates
-        const bool useMailBoxing = true;
-
-        int numRays = 0;
-
-        if (mCachedObjects)
-        {
-                ObjectContainer::const_iterator oit, oit_end = mCachedObjects->end();
-
-                // loop through all object and collect view cell pvs of this node
-                for (oit = mCachedObjects->begin(); oit != oit_end; ++ oit)
-                {
-                        // use mailing to avoid duplicates
-                        numRays += CollectViewCells(*oit, viewCells, useMailBoxing, setCounter, onlyUnmailedRays);
-                }
-        }
-        else
-        {
-                ObjectContainer::const_iterator oit, oit_end = objects.end();
-
-                // loop through all object and collect view cell pvs of this node
-                for (oit = objects.begin(); oit != oit_end; ++ oit)
-                {
-                        // use mailing to avoid duplicates
-                        numRays += CollectViewCellsFromRays(*oit, viewCells, useMailBoxing, setCounter, onlyUnmailedRays);
-                }
-        }
-
-        return numRays;
-}
-
-
-int BvHierarchy::CountViewCells(const ObjectContainer &objects)// const
-{
-        int nViewCells = 0;
-
-        ViewCell::NewMail();
-        
-        if (mCachedObjects)
-        {
-                ObjectContainer::const_iterator oit, oit_end = mCachedObjects->end();
-
-                // loop through all object and collect view cell pvs of this node
-                for (oit = mCachedObjects->begin(); oit != oit_end; ++ oit)
-                {
-                        // use mailing to avoid duplicates
-                        nViewCells += CountViewCells(*oit);
-                }
-        }
-        else
-        {
-                ObjectContainer::const_iterator oit, oit_end = objects.end();
-
-                // loop through all object and collect view cell pvs of this node
-                for (oit = objects.begin(); oit != oit_end; ++ oit)
-                {
-                        nViewCells += CountViewCellsFromRays(*oit);
-                }
-        }
-
-        return nViewCells;
-}
-
-
 #else
-
-int BvHierarchy::CollectViewCells(const ObjectContainer &objects, 
-                                                                  ViewCellContainer &viewCells,
-                                                                  const bool setCounter,
-                                                                  const bool onlyUnmailedRays)// const
-{
-        ViewCell::NewMail();
-
-        ObjectContainer::const_iterator oit, oit_end = objects.end();
-
-        // use mailing to avoid dublicates
-        const bool useMailBoxing = true;
-
-        int numRays = 0;
-        // loop through all object and collect view cell pvs of this node
-        for (oit = objects.begin(); oit != oit_end; ++ oit)
-        {
-                // use mailing to avoid duplicates
-                numRays += CollectViewCells(*oit, viewCells, useMailBoxing, setCounter, onlyUnmailedRays);
-        }
-
-        return numRays;
-}
-
-
-int BvHierarchy::CountViewCells(const ObjectContainer &objects)// const
-{
-        int nViewCells = 0;
-
-        ViewCell::NewMail();
-        ObjectContainer::const_iterator oit, oit_end = objects.end();
-
-        // loop through all object and collect view cell pvs of this node
-        for (oit = objects.begin(); oit != oit_end; ++ oit)
-        {
-                nViewCells += CountViewCells(*oit);
-        }
-
-        return nViewCells;
-}
-
 
 int BvHierarchy::CountViewCells(Intersectable *obj) //const
@@ -2377 +2320 @@
 
 
+int BvHierarchy::CountViewCells(const ObjectContainer &objects)// const
+{
+        int nViewCells = 0;
+
+        ViewCell::NewMail();
+        ObjectContainer::const_iterator oit, oit_end = objects.end();
+
+        // loop through all object and collect view cell pvs of this node
+        for (oit = objects.begin(); oit != oit_end; ++ oit)
+        {
+                nViewCells += CountViewCells(*oit);
+        }
+
+        return nViewCells;
+}
+
 
 void BvHierarchy::CollectDirtyCandidates(BvhSubdivisionCandidate *sc, 
@@ -2387 +2346 @@
         ViewCellContainer viewCells;
         //ViewCell::NewMail();
-        int numRays = CollectViewCells(node->mObjects, viewCells, false, false);
+        int numRays = CollectViewCells(*tData.mSampledObjects, viewCells, false, false);
 
         if (0) cout << "collected " << (int)viewCells.size() << " dirty candidates" << endl;
@@ -2435 +2394 @@
 }
 
-
+#if 0
 BvhLeaf *BvHierarchy::GetLeaf(Intersectable *object, BvhNode *node) const
 {
-        // rather use the simple version
+        // hack: we use the simpler but faster version
         if (!object) 
                 return NULL;
+
         return object->mBvhLeaf;
         
         ///////////////////////////////////////
         // start from root of tree
-        
+        /*
         if (node == NULL)
                 node = mRoot;
@@ -2489 +2449 @@
   
         return leaf;
-}
-
+        */
+}
+#endif
 
 bool BvHierarchy::Export(OUT_STREAM &stream)
@@ -2586 +2547 @@
 
 
-/*
-Mesh *BvHierarchy::MergeLeafToMesh()
-{
-        vector<BvhLeaf *> leaves;
-        CollectLeaves(leaves);
-
-        vector<BvhLeaf *>::const_iterator lit, lit_end = leaves.end();
-
-        for (lit = leaves.begin(); lit != lit_end; ++ lit)
-        {
-                Mesh *mesh = MergeLeafToMesh(*lit);
-        }
-}*/
+void BvHierarchy::StoreSampledObjects(ObjectContainer &sampledObjects, const ObjectContainer &objects)
+{
+        ObjectContainer::const_iterator oit, oit_end = objects.end();
+
+        for (oit = objects.begin(); oit != objects.end(); ++ oit)
+        {
+                Intersectable *obj = *oit;
+
+                if (!obj->GetOrCreateRays()->empty())
+        {
+                        sampledObjects.push_back(obj);
+                }
+        }
+        }
 
 
@@ -2624 +2586 @@
         //cout << "using " << nRays << " of " << (int)sampleRays.size() << " rays" << endl;
         
+        ObjectContainer *sampledObjects = new ObjectContainer();
+        StoreSampledObjects(*sampledObjects, objects);
+
 #if STORE_VIEWCELLS_WITH_BVH
-        AssociateViewCellsWithObjects(objects);
+        AssociateViewCellsWithObjects(*sampledObjects);
 #endif
 
         // probability that volume is "seen" from the view cells
-        const float prop = EvalViewCellsVolume(objects) / GetViewSpaceVolume();
+        const float prop = EvalViewCellsVolume(*sampledObjects) / GetViewSpaceVolume();
 
         // create bvh traversal data
@@ -2640 +2605 @@
         }
         
+        oData.mSampledObjects = sampledObjects;
+        
         ///////////////////
         //-- add first candidate for object space partition     
 
         mTotalCost = EvalRenderCost(objects);
-        mPvsEntries = CountViewCells(objects);
+        mPvsEntries = CountViewCells(*sampledObjects);
 
         oData.mCorrectedPvs = oData.mPvs = (float)mPvsEntries;
@@ -2655 +2622 @@
 
 #if STORE_VIEWCELLS_WITH_BVH
-        ReleaseViewCells(objects);
+        ReleaseViewCells(*sampledObjects);
 #endif
 
@@ -2727 +2694 @@
         }
 
-        // last sorted list: by size
+        // next sorted list: by size (for initial criteria)
         tData.mSortedObjects[3] = new ObjectContainer();
         tData.mSortedObjects[3]->reserve((int)objects.size());
@@ -2734 +2701 @@
         
         stable_sort(tData.mSortedObjects[3]->begin(), tData.mSortedObjects[3]->end(), smallerSize);
-        //sort(tData.mSortedObjects[3]->begin(), tData.mSortedObjects[3]->end(), smallerSize);
 }
 
@@ -2796 +2762 @@
         mRoot = bvhleaf;
         
+        ObjectContainer *sampledObjects = new ObjectContainer();
+        StoreSampledObjects(*sampledObjects, objects);
+
 #if STORE_VIEWCELLS_WITH_BVH
-        AssociateViewCellsWithObjects(objects);
+        AssociateViewCellsWithObjects(*sampledObjects);
 #endif
 
@@ -2803 +2772 @@
         // probability that volume is "seen" from the view cells
         const float viewSpaceVol = mViewCellsManager->GetViewSpaceBox().GetVolume();
-        const float prop = EvalViewCellsVolume(objects);
-
-        const int nRays = CountRays(objects);
+        const float prop = EvalViewCellsVolume(*sampledObjects);
+
+        const int nRays = CountRays(*sampledObjects);
         BvhLeaf *bvhLeaf = static_cast<BvhLeaf *>(mRoot);
 
@@ -2811 +2780 @@
         BvhTraversalData oData(bvhLeaf, 0, prop, nRays);
 
+        oData.mSampledObjects = sampledObjects;
+
         if (mUseGlobalSorting)
                 AssignInitialSortedObjectList(oData, objects);
         
 #if STORE_VIEWCELLS_WITH_BVH
-        ReleaseViewCells(objects);
+        ReleaseViewCells(*sampledObjects);
 #endif
         ///////////////////

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

@@ -407 +407 @@
                 mPvs(0),
                 mCorrectedVolume(0),
-                mVolume(v)
+                mVolume(v),
+                mSampledObjects(NULL)
                 {
                         for (int i = 0; i < 4; ++ i)
@@ -420 +421 @@
                         for (int i = 0; i < 4; ++ i)
                                 DEL_PTR(mSortedObjects[i]);
+
+                        DEL_PTR(mSampledObjects);
                 }
 
@@ -441 +444 @@
                 float mCorrectedPvs;
 
-                /// the sorted objects for the three dimensions
+                /** the sorted objects for the three dimensions + one for the original
+                        order + one for the objects which have been sampled at least once
+                */
                 ObjectContainer *mSortedObjects[4];             
+                ObjectContainer *mSampledObjects;       
     };
 
@@ -511 +517 @@
                 ObjectContainer mBackObjects;
                         
+                /// the sampled objects on the front of the potential split
+                ObjectContainer mSampledFrontObjects;
+                /// the sampled objects on the back of the potential split
+                ObjectContainer mSampledBackObjects;
+
                 float mCorrectedFrontPvs;
                 float mCorrectedBackPvs;
@@ -516 +527 @@
                 float mCorrectedFrontVolume;
                 float mCorrectedBackVolume;
+
+                //int mNumFrontRays;
+                //int mNumBackRays;
+                
+                int mNumFrontViewCells;
+                int mNumBackViewCells;
+
+                float mVolumeFrontViewCells;
+                float mVolumeBackViewCells;
         };
 
@@ -620 +640 @@
         /** Returns leaf the point pt lies in, starting from root.
         */
-        BvhLeaf *GetLeaf(Intersectable *obj, BvhNode *root = NULL) const;
+        inline BvhLeaf *GetLeaf(Intersectable *object, BvhNode *root = NULL) const
+        {
+                // hack: we use the simpler but faster version
+                if (!object) 
+                        return NULL;
+
+                return object->mBvhLeaf;
+        }
 
         /** Sets a pointer to the view cells tree.
@@ -638 +665 @@
         void SetActive(BvhNode *node) const;
 
+
+        void StoreSampledObjects(ObjectContainer &sampledObjects, const ObjectContainer &objects);
 
         ///////////////////////////
@@ -711 +740 @@
         float EvalRenderCost(const ObjectContainer &objects);// const;
 
+        float EvalProbability(const ObjectContainer &objects);
+
         /** Evaluates tree stats in the BSP tree leafs.
         */
@@ -860 +891 @@
         int AssociateViewCellsWithObject(Intersectable *obj, const bool useMailBoxing) const;
 
-        void AssociateViewCellsWithObjects(const ObjectContainer &objects);// const;
+        void AssociateViewCellsWithObjects(const ObjectContainer &objects) const;
 
         void ReleaseViewCells(const ObjectContainer &objects);
@@ -876 +907 @@
         */
         int EvalPvsEntriesIncr(BvhSubdivisionCandidate &splitCandidate, 
-                                                   const float avgRayContri);// const;
+                                                   const float avgRayContri,
+                                                   const int numParentViewCells,
+                                                   const int numFrontViewCells,
+                                                   const int numBackViewCells);// const;
 
         /** Rays will be clipped to the bounding box.
@@ -975 +1009 @@
         HierarchyManager *mHierarchyManager;
 
-
-        ObjectContainer *mCachedObjects;
 
         ////////////////////

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

@@ -2524 +2524 @@
         // delete old "base" view cells: only pvss in the leaves are allowed
         ViewCellContainer::const_iterator oit, oit_end = mOldViewCells.end();
+
         for (oit = mOldViewCells.begin(); oit != oit_end; ++ oit)
         {

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

@@ -92 +92 @@
                 Intersectable *newObject = vssRays[i]->mTerminationObject;
 
-                Intersectable *oldObject =mRays[vssRays[i]->mGeneratorId].mRay->mTerminationObject;
+                Intersectable *oldObject = mRays[vssRays[i]->mGeneratorId].mRay->mTerminationObject;
                 
                 if (oldObject == newObject)
@@ -600 +600 @@
   //rr[0] = RandomValue(0,1);
   // use binary search to find index with this cdf
-  int l=0, r=mRays.size()-1;
+  int l=0, r=(int)mRays.size()-1;
   while(l<r) {
         int i = (l+r)/2;

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

@@ -438 +438 @@
 
 
-  // has to called before first usage
+/******************************************************************/
+/*           class MixtureDistribution implementation             */
+/******************************************************************/
+
+
+// has to be called before first usage
 void
 MixtureDistribution::Init()
@@ -683 +688 @@
 }
 
+
 bool HwGlobalLinesDistribution::GenerateSample(SimpleRay &ray) 
 {

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

@@ -238 +238 @@
 { 
         const bool result = mPvs.AddSample(sample, pdf);
-        // have to recompute pvs size
+        // we have to recompute pvs size
         mPvsSizeValid = false;
 
@@ -515 +515 @@
         /////////////
         //-- fill merge queue
+
         vector<MergeCandidate> candidates;
 
@@ -527 +528 @@
         }
 
-        Debug << "************************* merge ***********************************" << endl;  
+        Debug << "********************** merge ******************************" << endl;  
         Debug << "deviation: " << mDeviation << endl;
         Debug << "avg render cost: " << mAvgRenderCost << endl;
@@ -648 +649 @@
                         totalRenderCost += renderCostIncr;
                         mDeviation += mc.GetDeviationIncr();
-
-                                                
+                        
+                        ///////////
                         //-- merge the view cells of leaf1 and leaf2
+
                         float pvsDiff;
                         ViewCellInterior *mergedVc = 
@@ -834 +836 @@
                 if (!obj->Mailed())
                 {
-                        renderCost += mViewCellsManager->EvalRenderCost(obj);
+                        renderCost += ViewCellsManager::EvalRenderCost(obj);
                 }
         }
@@ -1028 +1030 @@
                 // set scalars
                 mViewCellsManager->UpdateScalarPvsSize(right, 
-                        right->GetPvs().EvalPvsCost(), 
-                        right->GetPvs().GetSize());
+                                                                                           right->GetPvs().EvalPvsCost(), 
+                                                                                           right->GetPvs().GetSize());
 
                 right->mPvsSizeValid = true;
@@ -1804 +1806 @@
                 return vc->GetPvs().GetSize();
         }
-        
-        // interior node
 
         // interior nodes: pvs is either stored as a scalar or
@@ -1987 +1987 @@
         Intersectable::NewMail();
 
-        ////////////////////////////////////////////////
-        // for interiors, pvs can be stored using different methods
+        /////////////////////////
+        //-- different storage methods for interiors
         
         switch (mViewCellsStorage)

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

@@ -881 +881 @@
                                                                                         splitCandidate.GetAvgRayContribution());
         
+        splitCandidate.mFrontPvs = fPvsSize;
+        splitCandidate.mBackPvs = bPvsSize;
+
         if (0)
         cout << "vsp pvs"
@@ -902 +905 @@
 
         const VspTraversalData &tData = sc.mParentData;
-        const AxisAlignedPlane splitPlane = sc.mSplitPlane;
+        const AxisAlignedPlane &splitPlane = sc.mSplitPlane;
 
         ///////////////
@@ -917 +920 @@
 
         //-- compute pvs
-        frontData.mPvs = (float)EvalPvsEntriesSize(*frontData.mRays);
-        backData.mPvs = (float)EvalPvsEntriesSize(*backData.mRays);
+        frontData.mPvs = sc.mFrontPvs;//(float)EvalPvsEntriesSize(*frontData.mRays);
+        backData.mPvs = sc.mBackPvs;//(float)EvalPvsEntriesSize(*backData.mRays);
         
         //-- compute pvs correction for coping with undersampling
@@ -934 +937 @@
 
         //-- compute render cost
-        frontData.mRenderCost = (float)EvalPvsCost(*frontData.mRays);
-        backData.mRenderCost = (float)EvalPvsCost(*backData.mRays);
+        frontData.mRenderCost = sc.mFrontRenderCost;//(float)EvalPvsCost(*frontData.mRays);
+        backData.mRenderCost = sc.mBackRenderCost;//(float)EvalPvsCost(*backData.mRays);
         
         frontData.mCorrectedRenderCost = sc.mCorrectedFrontRenderCost;
@@ -1275 +1278 @@
         const float maxBand = minBox + mMaxBand * sizeBox;
 
+        // sort by the current dimension
         SortSubdivisionCandidates(usedRays, axis, minBand, maxBand);
 
@@ -1589 +1593 @@
         sc.mCorrectedBackRenderCost = mHierarchyManager->EvalCorrectedPvs(pvsBack, penaltyOld, avgRayContri);
 
+        sc.mFrontRenderCost = pvsFront;
+        sc.mBackRenderCost = pvsBack;
+
         const float oldRenderCost = pOverall * penaltyOld;
         const float newRenderCost = sc.mCorrectedFrontRenderCost * pFront + 
@@ -1727 +1734 @@
 
         const float renderCost = countEntries ? 1 : 
-                mHierarchyManager->mBvHierarchy->EvalAbsCost(leaf->mObjects);
+                mBvHierarchy->EvalAbsCost(leaf->mObjects);
         
         // leaf in no pvs => new
@@ -2286 +2293 @@
         case HierarchyManager::BV_BASED_OBJ_SUBDIV:
                 {
-                        BvhLeaf *bvhleaf = mHierarchyManager->mBvHierarchy->GetLeaf(obj);
+                        BvhLeaf *bvhleaf = mBvHierarchy->GetLeaf(obj);
 
                         if (!bvhleaf->Mailed())
@@ -2901 +2908 @@
         VspSubdivisionCandidate::sVspTree = this;
         
+        mBvHierarchy = mHierarchyManager->mBvHierarchy;
+
         // initialise termination criteria
         mTermMinProbability *= mBoundingBox.GetVolume();
@@ -2969 +2978 @@
         case HierarchyManager::BV_BASED_OBJ_SUBDIV:
                 {
-                        BvhLeaf *leaf = mHierarchyManager->mBvHierarchy->GetLeaf(obj);
+                        BvhLeaf *leaf = mBvHierarchy->GetLeaf(obj);
 
                         if (!leaf->Mailed())
@@ -3049 +3058 @@
         case HierarchyManager::BV_BASED_OBJ_SUBDIV:
                 {
-                        BvhLeaf *leaf = mHierarchyManager->mBvHierarchy->GetLeaf(obj);
+                        BvhLeaf *leaf = mBvHierarchy->GetLeaf(obj);
 
                         if (-- leaf->mCounter == 0)
@@ -3098 +3107 @@
         case HierarchyManager::BV_BASED_OBJ_SUBDIV:
                 {
-                        BvhLeaf *leaf = mHierarchyManager->mBvHierarchy->GetLeaf(obj);
+                        BvhLeaf *leaf = mBvHierarchy->GetLeaf(obj);
 
                         if (!leaf->Mailed())
@@ -3151 +3160 @@
         case HierarchyManager::BV_BASED_OBJ_SUBDIV:
                 {
-                        BvhLeaf *leaf = mHierarchyManager->mBvHierarchy->GetLeaf(obj);
+                        BvhLeaf *leaf = mBvHierarchy->GetLeaf(obj);
                         if (!leaf->Mailed())
                         {
@@ -3198 +3207 @@
                 case HierarchyManager::BV_BASED_OBJ_SUBDIV:
                 {
-                        BvhLeaf *leaf = mHierarchyManager->mBvHierarchy->GetLeaf(obj);
+                        BvhLeaf *leaf = mBvHierarchy->GetLeaf(obj);
                         UpdateContributionsToPvs(leaf, cf, frontPvs, backPvs, totalPvs, false);
                         break;
@@ -3227 +3236 @@
         case HierarchyManager::BV_BASED_OBJ_SUBDIV:
                 {
-                        BvhLeaf *leaf = mHierarchyManager->mBvHierarchy->GetLeaf(obj);
+                        BvhLeaf *leaf = mBvHierarchy->GetLeaf(obj);
                         UpdateContributionsToPvs(leaf, cf, pvsFront, pvsBack, totalPvs, true);
                         break;
@@ -3269 +3278 @@
         case HierarchyManager::BV_BASED_OBJ_SUBDIV:
                 {
-                        BvhLeaf *bvhleaf = mHierarchyManager->mBvHierarchy->GetLeaf(obj);
+                        BvhLeaf *bvhleaf = mBvHierarchy->GetLeaf(obj);
 
                         if (!bvhleaf->Mailed())

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

@@ -551 +551 @@
                 float mCorrectedBackPvs;
 
+                float mFrontPvs;
+                float mBackPvs;
+
                 float mCorrectedFrontRenderCost;
                 float mCorrectedBackRenderCost;
-                float mCorrectedFrontVolume;
-                float mCorrectedBackVolume;
+                //float mCorrectedFrontVolume;
+                //float mCorrectedBackVolume;
+
+                float mFrontRenderCost;
+                float mBackRenderCost;
         };
 
@@ -1092 +1098 @@
 
         HierarchyManager *mHierarchyManager;
+        BvHierarchy *mBvHierarchy;
+
         //OspTree *mOspTree;
         //bool mUseKdPvsForHeuristics;