Changeset 1176

Timestamp:

08/02/06 09:09:03 (18 years ago)

Author:

mattausch

Message:

corrected errors in the object space partition, but still buggy!

Location:

GTP/trunk/Lib/Vis

Files:

• Preprocessing/src/Intersectable.h (modified) (2 diffs)
• Preprocessing/src/KdTree.cpp (modified) (1 diff)
• Preprocessing/src/KdTree.h (modified) (2 diffs)
• Preprocessing/src/Pvs.cpp (modified) (1 diff)
• Preprocessing/src/ViewCellsManager.cpp (modified) (4 diffs)
• Preprocessing/src/VspOspTree.cpp (modified) (44 diffs)
• Preprocessing/src/VspOspTree.h (modified) (12 diffs)
• shared/scripts/GtpVisibility.suo (modified) (previous)

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

@@ -45 +45 @@
                 };
   
-  Intersectable():mMailbox(0), mReferences(0) {}
+  Intersectable(): mMailbox(0), mReferences(0) {}
 
         void SetId(const int id) { mId = id; }
@@ -62 +62 @@
         bool Mailed(const int mailbox) const { return mMailbox == sMailId + mailbox; }
 
-        int IncMail() { return ++mMailbox - sMailId; }
+        int IncMail() { return ++ mMailbox - sMailId; }
 
 

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

@@ -12 +12 @@
 namespace GtpVisibilityPreprocessor {
 
-int KdNode::mailID = 1;
-
-KdNode::KdNode(KdInterior *parent):mParent(parent), mailbox(0)
+int KdNode::sMailId = 1;
+int KdNode::sReservedMailboxes = 1;
+
+KdNode::KdNode(KdInterior *parent):mParent(parent), mMailbox(0)
 {
   if (parent)

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

@@ -64 +64 @@
 
   int Nodes() const {return nodes;}
-  int Interior() const { return nodes/2; }
-  int Leaves() const { return (nodes/2) + 1; }
+  int Interior() const { return nodes / 2; }
+  int Leaves() const { return (nodes / 2) + 1; }
 
   void Reset() {
@@ -95 +95 @@
 class KdNode {
 public:
-  static int mailID;
-  int mailbox;
-  
-  void Mail() { mailbox = mailID; }
-  static void NewMail() { mailID++; }
-  bool Mailed() const { return mailbox == mailID; }
+  
+        static int sMailId;
+        static int sReservedMailboxes;
+  int mMailbox;
+  
+  void Mail() { mMailbox = sMailId; }
+  //static void NewMail() { sMailId ++; }
+  bool Mailed() const { return mMailbox == sMailId; }
+ 
+  static void NewMail(const int reserve = 1) {
+                sMailId += sReservedMailboxes;
+                sReservedMailboxes = reserve;
+        }
+        void Mail(const int mailbox) { mMailbox = sMailId + mailbox; }
+        bool Mailed(const int mailbox) const { return mMailbox == sMailId + mailbox; }
 
   virtual ~KdNode(){};

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

@@ -22 +22 @@
 
         Intersectable::NewMail();
-        KdNode::NewMail();
+        KdLeaf::NewMail();
 
         ObjectPvsMap::const_iterator it, it_end = mEntries.end();

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

@@ -3547 +3547 @@
         while (node->mParent && node->mDepth > mKdPvsDepth)
                 node = node->mParent;
+
         return node;
 }
@@ -3810 +3811 @@
         }
 
-        if (0) // export merged view cells using pvs coding
-        {
-                mColorCode = 1;
-
+        if (0) 
+        {
+                mColorCode = 1; // export merged view cells using pvs coding
                 Exporter *exporter = Exporter::GetExporter("merged_view_cells_pvs.wrl");
-        
+
                 cout << "exporting view cells after merge (pvs size) ... ";     
 
@@ -4886 +4886 @@
         long startTime;
 
-        if (!mOspTree->GetRoot())
-        {
-                Debug << "constructing vsp and osp tree" << endl;
-                //mHierarchyManager->Construct(constructionRays, objects, &mViewSpaceBox);
-                mHierarchyManager->Construct2(constructionRays, objects, &mViewSpaceBox);
-        }
-        else // just build view space partition tree
-        {
-                Debug << "constructing only vsp tree" << endl;
-                mHierarchyManager->Construct3(constructionRays, objects, &mViewSpaceBox);
-        }
+        //mHierarchyManager->Construct(constructionRays, objects, &mViewSpaceBox);
+        mHierarchyManager->Construct2(constructionRays, objects, &mViewSpaceBox);
+
 
         // print subdivision statistics
@@ -5689 +5681 @@
                                         if (!mStoreKdPvs)
                                         {
-                                                viewcell->AddPvsSample(ray.mTerminationObject, ray.mPdf, ray.mRelativePvsContribution);
+                                                viewcell->AddPvsSample(ray.mTerminationObject, 
+                                                        ray.mPdf, ray.mRelativePvsContribution);
                                         }
                                         else

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

@@ -370 +370 @@
 
 
-/******************************************************************************/
-/*                       class VspTree implementation                      */
-/******************************************************************************/
+/*************************************************************************/
+/*                       class VspTree implementation                    */
+/*************************************************************************/
 
 
@@ -642 +642 @@
         
         AddSubdivisionStats(mVspStats.Leaves(),
-                                                -costDecr,
+                                                costDecr,
                                                 mTotalCost,
                                                 (float)mTotalPvsSize / (float)mVspStats.Leaves());
@@ -887 +887 @@
         
         return interior;
-}
-
-
-KdNode *VspTree::GetKdNode(VssRay &ray, const bool termination) const
-{
-        if (termination)
-        {
-                if (!ray.mTerminationNode)
-                {
-                        ray.mTerminationNode = mOspTree->GetRoot();
-                }
-
-                ray.mTerminationNode = 
-                        mOspTree->GetLeaf(ray.mTermination, ray.mTerminationNode);
-
-                return ray.mTerminationNode;
-        }
-        else
-        {
-                if (!ray.mOriginNode)
-                {
-                        ray.mOriginNode = mOspTree->GetRoot();
-                }
-
-                ray.mOriginNode = 
-                        mOspTree->GetLeaf(ray.mOrigin, ray.mOriginNode);
-
-                return ray.mOriginNode;
-        }
 }
 
@@ -1045 +1016 @@
                 {
                         // potentially visible kd cells
-                        if (mUseKdPvsForHeuristics)
-                        {
-                                KdLeaf *leaf = mOspTree->GetLeaf(ray->mOrigin, ray->mOriginNode);       
-                                AddKdLeafToPvs(leaf, vc, ray->mPdf, contribution);
-                        }
-                        else
+                        if (!mUseKdPvsForHeuristics) // matt TODo: remove storekdpvs!!
                         {
                                 if (vc->AddPvsSample(obj, ray->mPdf, contribution))
@@ -1057 +1023 @@
                                 }
                         }
+                        else
+                        {
+                                KdLeaf *leaf = mOspTree->GetLeaf(ray->mOrigin, ray->mOriginNode);       
+                                AddKdLeafToPvs(leaf, vc, ray->mPdf, contribution);
+                        }
+                        
+                        
 
                         sc += contribution;
@@ -1208 +1181 @@
                                         oObject->Mail();
                                         oObject->mCounter = 1;
+
                                         ++ pvsSize;
                                 }
@@ -1342 +1316 @@
                         }
                 }
-                        
-
         }
         
@@ -1615 +1587 @@
         // create unique ids for pvs heuristics
         Intersectable::NewMail(3);
-        
+        KdLeaf::NewMail(3);
+
         RayInfoContainer::const_iterator rit, rit_end = data.mRays->end();
 
@@ -1629 +1602 @@
                                                                                   candidatePlane.mPosition, t);
 
-                // find front and back pvs for origing and termination object
-                AddObjToPvs(ray->mTerminationObject, cf, pvsFront, pvsBack, totalPvs);
-                AddObjToPvs(ray->mOriginObject, cf, pvsFront, pvsBack, totalPvs);
+                if (!mUseKdPvsForHeuristics)
+                {
+                        // find front and back pvs for origing and termination object
+                        UpdateObjPvsContri(ray->mTerminationObject, cf, pvsFront, pvsBack, totalPvs);
+                        UpdateObjPvsContri(ray->mOriginObject, cf, pvsFront, pvsBack, totalPvs);
+                }
+                else
+                {
+                        if (ray->mTerminationObject)
+                        {
+                                KdLeaf *leaf = mOspTree->GetLeaf(ray->mTermination, ray->mTerminationNode);
+                                UpdateKdLeafPvsContri(leaf, cf, pvsFront, pvsBack, totalPvs);
+                        }
+
+                        if (ray->mOriginObject)
+                        {
+                                KdLeaf *leaf = mOspTree->GetLeaf(ray->mOrigin, ray->mOriginNode);
+                                UpdateKdLeafPvsContri(leaf, cf, pvsFront, pvsBack, totalPvs);
+                        }
+                }
         }
 
@@ -1661 +1651 @@
         const float renderCostDecrease = (oldRenderCost - newRenderCost) / viewSpaceVol;
         
-        
         Debug << "\n==== eval render cost decrease ===" << endl
                   << "back pvs: " << pvsBack << " front pvs " << pvsFront << " total pvs: " << totalPvs << endl 
@@ -1697 +1686 @@
                 const int side = (*rit).ComputeRayIntersection(axis, position, t);
         
-                AddObjToPvs((*rit).mRay->mTerminationObject, side, pvsFront, pvsBack, pvsTotal);
-                AddObjToPvs((*rit).mRay->mOriginObject, side, pvsFront, pvsBack, pvsTotal);
+                UpdateObjPvsContri((*rit).mRay->mTerminationObject, side, pvsFront, pvsBack, pvsTotal);
+                UpdateObjPvsContri((*rit).mRay->mOriginObject, side, pvsFront, pvsBack, pvsTotal);
         }
 
@@ -1721 +1710 @@
 
 
-void VspTree::AddObjToPvs(Intersectable *obj,
+void VspTree::UpdateObjPvsContri(Intersectable *obj,
                                                   const int cf,
                                                   float &frontPvs,
@@ -1727 +1716 @@
                                                   float &totalPvs) const
 {
-        if (!obj)
-                return;
+        if (!obj) return;
 
         //const float renderCost = mViewCellsManager->SimpleRay &raynderCost(obj);
@@ -1773 +1761 @@
 
 
+void VspTree::UpdateKdLeafPvsContri(KdLeaf *leaf,
+                                                                        const int cf,
+                                                                        float &frontPvs,
+                                                                        float &backPvs,
+                                                                        float &totalPvs) const
+{
+        if (!leaf) return;
+
+        // the objects which are referenced in this and only this leaf
+        const int contri = (int)(leaf->mObjects.size() - leaf->mMultipleObjects.size());
+        
+        // newly found leaf
+        if (!leaf->Mailed() && !leaf->Mailed(1) && !leaf->Mailed(2))
+        {
+                totalPvs += contri;
+        }
+
+        // compute contribution of yet unclassified objects
+        ObjectContainer::const_iterator oit, oit_end = leaf->mMultipleObjects.end();
+
+        for (oit = leaf->mMultipleObjects.begin(); oit != oit_end; ++ oit)
+        {       
+                UpdateObjPvsContri(*oit, cf, frontPvs, backPvs, totalPvs);
+    }   
+        
+        // QUESTION matt: is it safe to assume that 
+        // the object belongs to no pvs in this case?
+        //if (cf == Ray::COINCIDENT) return;
+
+        if (cf >= 0) // front pvs
+        {
+                if (!leaf->Mailed() && !leaf->Mailed(2))
+                {
+                        frontPvs += contri;
+                
+                        // already in back pvs => in both pvss
+                        if (leaf->Mailed(1))
+                                leaf->Mail(2);
+                        else
+                                leaf->Mail();
+                }
+        }
+
+        if (cf <= 0) // back pvs
+        {
+                if (!leaf->Mailed(1) && !leaf->Mailed(2))
+                {
+                        backPvs += contri;
+                
+                        // already in front pvs => in both pvss
+                        if (leaf->Mailed())
+                                leaf->Mail(2);
+                        else
+                                leaf->Mail(1);
+                }
+        }
+}
+
+
 void VspTree::CollectLeaves(vector<VspLeaf *> &leaves, 
-                                                           const bool onlyUnmailed,
-                                                           const int maxPvsSize) const
+                                                        const bool onlyUnmailed,
+                                                        const int maxPvsSize) const
 {
         stack<VspNode *> nodeStack;
@@ -2219 +2266 @@
 {
         int pvsSize = 0;
+        Intersectable::NewMail();
 
         RayInfoContainer::const_iterator rit, rit_end = rays.end();
 
-        Intersectable::NewMail();
-
-        for (rit = rays.begin(); rit != rays.end(); ++ rit)
-        {
-                VssRay *ray = (*rit).mRay;
-
-                if (ray->mOriginObject)
-                {
-                        if (!ray->mOriginObject->Mailed())
-                        {
-                                ray->mOriginObject->Mail();
-                                ++ pvsSize;
-                        }
-                }
-                if (ray->mTerminationObject)
-                {
-                        if (!ray->mTerminationObject->Mailed())
-                        {
-                                ray->mTerminationObject->Mail();
-                                ++ pvsSize;
+        if (!mUseKdPvsForHeuristics)
+        {
+                for (rit = rays.begin(); rit != rays.end(); ++ rit)
+                {
+                        VssRay *ray = (*rit).mRay;
+
+                        if (ray->mOriginObject)
+                        {
+                                if (!ray->mOriginObject->Mailed())
+                                {
+                                        ray->mOriginObject->Mail();
+                                        ++ pvsSize;
+                                }
+                        }
+                        if (ray->mTerminationObject)
+                        {
+                                if (!ray->mTerminationObject->Mailed())
+                                {
+                                        ray->mTerminationObject->Mail();
+                                        ++ pvsSize;
+                                }
+                        }
+                }
+        }
+        else
+        {
+                KdNode::NewMail();
+
+                for (rit = rays.begin(); rit != rays.end(); ++ rit)
+                {
+                        VssRay *ray = (*rit).mRay;
+
+                        if (ray->mTerminationObject)
+                        {
+                                KdLeaf *leaf = mOspTree->GetLeaf(ray->mTermination, ray->mTerminationNode);
+
+                                if (!leaf->Mailed())
+                                {
+                                        leaf->Mail();
+                                        pvsSize += (int)(leaf->mObjects.size() - leaf->mMultipleObjects.size());
+                                
+                                        ObjectContainer::const_iterator oit, oit_end = leaf->mMultipleObjects.end();
+                                        for (oit = leaf->mMultipleObjects.begin(); oit != oit_end; ++ oit)
+                                        {
+                                                Intersectable *obj = *oit;
+
+                                                if (!obj->Mailed())
+                                                {
+                                                        obj->Mail();
+                                                        ++ pvsSize;
+                                                }
+                                        }
+                                }
+                        }
+
+                        if (ray->mOriginObject)
+                        {
+                                KdLeaf *leaf = mOspTree->GetLeaf(ray->mOrigin, ray->mOriginNode);
+
+                                if (!leaf->Mailed())
+                                {
+                                        leaf->Mail();
+                                        pvsSize += (int)(leaf->mObjects.size() - leaf->mMultipleObjects.size());
+                                
+                                        ObjectContainer::const_iterator oit, oit_end = leaf->mMultipleObjects.end();
+                                        for (oit = leaf->mMultipleObjects.begin(); oit != oit_end; ++ oit)
+                                        {
+                                                Intersectable *obj = *oit;
+
+                                                if (!obj->Mailed())
+                                                {
+                                                        obj->Mail();
+                                                        ++ pvsSize;
+                                                }
+                                        }
+                                }
                         }
                 }
@@ -2763 +2867 @@
 
 
-void VspTree::ProcessRays(const VssRayContainer &sampleRays,
-                                                  RayInfoContainer &rays)
+void VspTree::PreprocessRays(const VssRayContainer &sampleRays,
+                                                         RayInfoContainer &rays)
 {
         VssRayContainer::const_iterator rit, rit_end = sampleRays.end();
@@ -2841 +2945 @@
         }
 
-        // if not using kd tree root
+        // if not using kd tree root, delete tree (otherwise mKdTree has to do the job)
         if (!mCopyFromKdTree)
                 DEL_PTR(mRoot);
+
+        mSubdivisionStats.close();
 }
 
@@ -2927 +3033 @@
                 Intersectable *object = *oit;
                 
-                // initialise
+                // initialise leaf references of objects
                 if (parent->IsRoot())
                         object->mReferences = 1;
@@ -3296 +3402 @@
 
         //-- traverse through events and find best split plane
-
         vector<SortableEntry>::const_iterator ci, ci_end = mSplitCandidates->end();
 
@@ -3306 +3411 @@
                                                                    *ci, 
                                                                    voll, volr, 
-                                                                   pvsl, pvsr,
-                                                                   vcl, vcr);
+                                                                   pvsl, pvsr
+                                                                  );
 
                 // Note: sufficient to compare size of bounding boxes of front and back side?
@@ -3313 +3418 @@
                 if (((*ci).mPos >= minBand) && ((*ci).mPos <= maxBand))
                 {
-                        sum = voll * pvsl + volr * pvsr;
+                        // voll = view cells that see only left node (i.e., left pvs)
+                        // volr = view cells that see only right node (i.e., right pvs)
+                        // rest = view cells that see both nodes (i.e., total pvs)
+            sum = voll * pvsl + volr * pvsr + (totalVol - voll - volr) * totalPvs;
 
                         float currentPos;
                         
                         // HACK: current positition is BETWEEN visibility events
-                        if (0 && ((ci + 1) != ci_end))
+                        if (1 && ((ci + 1) != ci_end))
                                 currentPos = ((*ci).mPos + (*(ci + 1)).mPos) * 0.5f;
                         else
@@ -3349 +3457 @@
         }
         
-
         //-- compute cost
-
-        const int lowerPvsLimit = mViewCellsManager->GetMinPvsSize();
-        const int upperPvsLimit = mViewCellsManager->GetMaxPvsSize();
-
-        const float pOverall = totalVol;
-        const float pBack = volBack;
-        const float pFront = volFront;
-
-        const float penaltyOld = (float)totalPvs;
-    const float penaltyFront = (float)pvsFront;
-        const float penaltyBack = (float)pvsBack;
-        
-        const float oldRenderCost = penaltyOld * pOverall + Limits::Small;
-        const float newRenderCost = penaltyFront * pFront + penaltyBack * pBack;
+        const float frontAndBackVol = totalVol - volFront - volBack;
+
+        const float oldRenderCost = (float)totalPvs * totalVol + Limits::Small;
+        const float newRenderCost = 
+                (float)pvsFront * volFront + 
+                (float)pvsBack * volBack +
+                (float)totalPvs * frontAndBackVol;
 
 
@@ -3380 +3480 @@
         Debug << "\n§§§§ eval local cost §§§§" << endl
                   << "back pvs: " << pvsBack << " front pvs: " << pvsFront << " total pvs: " << totalPvs << endl 
-                  << "back p: " << pBack / viewSpaceVol << " front p " << pFront / viewSpaceVol << " p: " << pOverall / viewSpaceVol << endl
+                  << "back p: " << volBack / viewSpaceVol << " front p " << volFront / viewSpaceVol << " p: " << totalVol / viewSpaceVol << endl
                   << "old rc: " << oldRenderCost / viewSpaceVol << " new rc: " << newRenderCost / viewSpaceVol << endl
                   << "render cost decrease: " << oldRenderCost / viewSpaceVol - newRenderCost / viewSpaceVol << endl;
@@ -3443 +3543 @@
                                                           );
                 }
+
+
+
 
                 if (ray->mTerminationObject && (GetLeaf(ray->mTermination, ray->mTerminationNode) == leaf))
@@ -3572 +3675 @@
                                                                                  float &volRight,
                                                                                  int &pvsLeft,
-                                                                                 int &pvsRight,
-                                                                                 int &viewCellsLeft,
-                                                                                 int &viewCellsRight)
+                                                                                 int &pvsRight
+                                                                                 )
 {
         Intersectable *obj = ci.mObject;
         VssRay *ray = ci.mRay;
-        
+
+        // switch between different types of events
         switch (ci.mType) 
         {
@@ -3592 +3695 @@
                 // compute volume contribution from view cells
                 case SortableEntry::BOX_INTERSECT:
+                                // process ray if the hit point with termination / origin object 
+                                // is inside this kd leaf
                                 if ((ray->mOriginObject && (GetLeaf(ray->mOrigin, ray->mOriginNode) == leaf)) ||
                                         (ray->mTerminationObject && (GetLeaf(ray->mTermination, ray->mTerminationNode) == leaf)))
                                 {
-                                        EvalVolumeContribution(*ray, volLeft, volRight, viewCellsLeft, viewCellsRight);
+                                        EvalVolumeContribution(*ray, volLeft, volRight);
                                 }
                         break;
@@ -3609 +3714 @@
 void OspTree::EvalVolumeContribution(const VssRay &ray, 
                                                                          float &volLeft, 
-                                                                         float &volRight,
-                                                                         int &viewCellsLeft,
-                                                                         int &viewCellsRight)
+                                                                         float &volRight)
 {
         ViewCellContainer viewCells;
@@ -3617 +3720 @@
         mVspTree->GetViewCells(ray, viewCells);
 
+        /// classify view cells and compute volume contri accordingly
+        /// possible view cell classifications:
+        /// view cell mailed => view cell can be seen from left child node
+        /// view cell counter > 0 view cell can be seen from right child node
+        /// combined: view cell volume belongs to both nodes
         ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
         
         for (vit = viewCells.begin(); vit != vit_end; ++ vit)
         {
-                // add view cells volume to left child node
+                // view cells can also be seen from left child node
                 ViewCell *viewCell = *vit;
 
+                const float vol = viewCell->GetVolume();
+
                 if (!viewCell->Mailed())
                 {
                         viewCell->Mail();
-                        
-                        volLeft += viewCell->GetVolume();
-
-                        ++ viewCellsLeft;
-                }
-
-                // remove from right child node
+
+                        // we now see view cell from both nodes 
+                        // => remove ref to right child node
+                        volRight -= vol;
+                }
+
+                // last reference into the right node
                 if (-- viewCell->mCounter == 0)
                 {
-                        volRight -= viewCell->GetVolume();
-
-                        -- viewCellsRight;
+#if 0
+                        // view cell was previousy seen from right node only
+                        // => remove from right node (matt: need this?)
+                        if (!viewCell->Mailed())
+                                volRight -= vol;
+                        else
+#endif
+                        // view cell was previously seen from both nodes  =>
+                        // contributes only to left node now
+                        volLeft += vol;
                 }
         }
@@ -3753 +3870 @@
 {
         const float costDecr = sc.GetRenderCostDecrease();
-        Debug << "**********************$$$$$$$$$$$$$$"<< endl;
-Debug << "here78 " << mOspStats.Leaves() << " " << mTotalCost << endl;
+
         AddSubdivisionStats(mOspStats.Leaves(),
                                                 costDecr,
@@ -3766 +3882 @@
                                                                   const float renderCostDecr,
                                                                   const float totalRenderCost)
-                                                                  //const float avgRenderCost)
-{Debug << "here64 " << totalRenderCost << " " << renderCostDecr << endl;
+{
         mSubdivisionStats 
                         << "#Leaves\n" << leaves << endl
@@ -3818 +3933 @@
         float pFront = 0;
         float pBack = 0;
+        float pFrontAndBack = 0;
+
 
         const float viewSpaceVol = mVspTree->GetBoundingBox().GetVolume();
@@ -3856 +3973 @@
         // => the volume is the weight for the render cost equation
         ViewCell::NewMail(3);
-        
+
         RayInfoContainer::const_iterator rit, rit_end = tData.mRays->end();
+
+        ViewCellContainer collectedViewCells;
 
         for (rit = tData.mRays->begin(); rit < rit_end; ++ rit)
@@ -3873 +3992 @@
                         const int classification = ClassifyRay(ray, leaf, candidatePlane);
 
-                        ViewCellContainer viewCells;            
+                        ViewCellContainer viewCells;
                         mVspTree->GetViewCells(*ray, viewCells);
                         
                         ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
 
-                        // evaluate view cells volume contribution
+                        // mail view cell
                         for (vit = viewCells.begin(); vit != vit_end; ++ vit)
                         {
-                                AddViewCellVolume(*vit, classification, pFront, pBack, pOverall);
-                        }
-                }
+                                ViewCell *vc = *vit;
+
+                                // if not previously mailed
+                                if (!vc->Mailed() && !vc->Mailed(1) && !vc->Mailed(2))
+                                        collectedViewCells.push_back(vc);
+
+                                MailViewCell(*vit, classification);     
+                        }
+                }
+        }
+
+        // these are non-overlapping sets
+        pOverall = pFront + pBack + pFrontAndBack;
+
+        ViewCellContainer::const_iterator vit, vit_end = collectedViewCells.end();
+
+        // evaluate view cells volume contribution with respect to mail box
+        for (vit = collectedViewCells.begin(); vit != vit_end; ++ vit)
+        {
+                AddViewCellVolumeContri(*vit, pFront, pBack, pFrontAndBack);
         }
 
@@ -3889 +4025 @@
         //-- pvs rendering heuristics
         const float oldRenderCost = pOverall * totalPvs;
-        const float newRenderCost = pvsFront * pFront + pvsBack * pBack;
+        const float newRenderCost = pvsFront * pFront + pvsBack * pBack + totalPvs * pFrontAndBack;
 
         // normalize volume with view space volume
         const float renderCostDecrease = (oldRenderCost - newRenderCost) / viewSpaceVol;
 
-        Debug << "\n==== eval render cost decrease ====" << endl
+        Debug << "\n(((( eval render cost decrease ))))" << endl
                   << "back pvs: " << pvsBack << " front pvs " << pvsFront << " total pvs: " << totalPvs << endl 
-                  << "back p: " << pBack / viewSpaceVol << " front p " << pFront / viewSpaceVol << " p: " << pOverall / viewSpaceVol << endl
+                  << "back p: " << pBack / viewSpaceVol << " front p " << pFront / viewSpaceVol 
+                  << " front and back p " << pFrontAndBack / viewSpaceVol << " p: " << pOverall / viewSpaceVol << endl
                   << "old rc: " << oldRenderCost / viewSpaceVol << " new rc: " << newRenderCost / viewSpaceVol << endl
                   << "render cost decrease: " << renderCostDecrease << endl;
@@ -3902 +4039 @@
         normalizedOldRenderCost = oldRenderCost / viewSpaceVol;
 
-        if (oldRenderCost < newRenderCost)
+        if (oldRenderCost < newRenderCost * 0.99)
                 Debug << "\nwarning2!!:\n" << "old rc: " << oldRenderCost * viewSpaceVol << " new rc: " << newRenderCost * viewSpaceVol << endl;
-        else
-                Debug << "here4" << endl;
-
-        if (pBack + pFront < pOverall * 0.9)
-                Debug << "\nwarning3!!:\n" << "p new: " << pBack + pFront << " p old: " << pOverall << endl;
-        else
-                Debug << "here55" << endl;
-
-        if (pvsBack + pvsFront < totalPvs)
-                Debug << "\nwarning4!!:\n" << "pvs new: " << pvsBack + pvsFront << " pvs old: " << totalPvs << endl;
-        else
-                Debug << "here25" << endl;
-
+        
         return renderCostDecrease;
 }
@@ -4148 +4273 @@
 
 
-void OspTree::ProcessRays(const VssRayContainer &sampleRays,
-                                                  RayInfoContainer &rays)
+void OspTree::PreprocessRays(const VssRayContainer &sampleRays,
+                                                         RayInfoContainer &rays)
 {
         VssRayContainer::const_iterator rit, rit_end = sampleRays.end();
@@ -4177 +4302 @@
 
                         rays.push_back(RayInfo(ray, minT / len, maxT / len));
+
+                        // HACK: reset nodes for the case we have used object kd tree for
+                        // tree building.
+                        ray->mOrigin = NULL;
+                        ray->mTerminationNode = NULL;
                 }
         }
@@ -4254 +4384 @@
 
 
+/*
 void OspTree::AddViewCellVolume(ViewCell *vc,
                                                                 const int cf,
@@ -4297 +4428 @@
         }
 }
+*/
+void OspTree::MailViewCell(ViewCell *vc, const int cf) const
+{
+        if (vc->Mailed(2)) // already classified
+                return;
+
+        if (cf >= 0) // front volume
+        {
+                 // already in back volume => in both volumes
+                if (vc->Mailed(1))
+                {
+                        vc->Mail(2);
+                }
+                else
+                {
+                        vc->Mail();
+                }
+        }
+
+        if (cf <= 0) // back volume
+        {
+                // already in front volume => in both volume
+                if (vc->Mailed())
+                {
+                        vc->Mail(2);
+                }
+                else
+                {
+                        vc->Mail(1);
+                }
+        }
+}
+
+
+void OspTree::AddViewCellVolumeContri(ViewCell *vc,
+                                                                          float &frontVol,
+                                                                          float &backVol,
+                                                                          float &frontAndBackVol) const
+{
+        if (vc->Mailed())
+                frontVol += vc->GetVolume();
+        else if (vc->Mailed(1))
+                backVol += vc->GetVolume();
+        else if (vc->Mailed(2))
+                frontAndBackVol += vc->GetVolume();
+}
+
 
 
@@ -4346 +4524 @@
 
         // get clipped rays
-        mVspTree.ProcessRays(sampleRays, rays);
+        mVspTree.PreprocessRays(sampleRays, rays);
 
         const int pvsSize = mVspTree.ComputePvsSize(rays);
@@ -4414 +4592 @@
 
         // get clipped rays
-        mOspTree.ProcessRays(sampleRays, rays);
+        mOspTree.PreprocessRays(sampleRays, rays);
 
         // add first candidate for view space partition
@@ -4593 +4771 @@
         /////////////////////////////////////////////////////////////
 
-
+#if 0
         // makes no sense otherwise because only one kd cell available
         // during view space partition
@@ -4601 +4779 @@
         mVspTree.mUseKdPvsForHeuristics = false;
         mVspTree.mStoreKdPvs = false;
+#endif
 
         VspTree::VspSplitCandidate *vsc = 
@@ -4661 +4840 @@
         mOspTree.mOspStats.Stop();
 
+#if 0
         // reset parameters
         mVspTree.mUseKdPvsForHeuristics = savedCountMethod;
         mVspTree.mStoreKdPvs = savedStoreMethod;
+#endif
 }
 

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

@@ -965 +965 @@
                                   RayInfoContainer &backRays) const;
 
-        /** Adds the object to the pvs of the front and back leaf with a given classification.
+        /** Classfifies the object with respect to the 
+                pvs of the front and back leaf and updates pvs size
+                accordingly.
 
                 @param obj the object to be added
@@ -973 +975 @@
         
         */
-        void AddObjToPvs(Intersectable *obj, 
+        void UpdateObjPvsContri(Intersectable *obj, 
                                          const int cf, 
                                          float &frontPvs, 
@@ -979 +981 @@
                                          float &totalPvs) const;
         
+        /** See UpdateObjPvsContri. 
+        */
+        void UpdateKdLeafPvsContri(KdLeaf *leaf,
+                const int cf,
+                float &frontPvs,
+                float &backPvs,
+                float &totalPvs) const;
+
+
         /** Computes PVS size induced by the rays.
         */
@@ -1002 +1013 @@
         */
         void AddSamplesToPvs(VspLeaf *leaf,
-                                  const RayInfoContainer &rays, 
-                                  float &sampleContributions,
-                                  int &contributingSamples);
-
-        bool AddKdLeafToPvs(KdLeaf *leaf, ViewCell *vc, float &pvs, float &contribution);
+                                                 const RayInfoContainer &rays, 
+                                                 float &sampleContributions,
+                                                 int &contributingSamples);
+
+        bool AddKdLeafToPvs(KdLeaf *leaf, 
+                                                ViewCell *vc, 
+                                                float &pvs, 
+                                                float &contribution);
 
         /** Propagates valid flag up the tree.
@@ -1025 +1039 @@
         float GetMemUsage() const;
 
+        /** Updates view cell pvs of objects.
+        */
         void ProcessViewCellObjects(ViewCell *parent, 
                 ViewCell *front, 
@@ -1031 +1047 @@
         void CreateViewCell(VspTraversalData &tData, const bool updatePvs);
 
+        /** Collect split candidates which are affected by the last split
+                and must be reevaluated.
+        */
         void CollectDirtyCandidates(VspSplitCandidate *sc, 
                 vector<SplitCandidate *> &dirtyList);
 
-        KdNode *GetKdNode(VssRay &ray, const bool termination) const;
-
-        void ProcessRays(const VssRayContainer &sampleRays,
+        /** Rays will be clipped to the bounding box.
+        */
+        void PreprocessRays(const VssRayContainer &sampleRays,
                 RayInfoContainer &rays);
 
+        /** Evaluate subdivision statistics.
+        */
         void EvalSubdivisionStats(const SplitCandidate &tData);
+
+
 protected:
 
@@ -1566 +1589 @@
         
         */
-        void AddObjToPvs(Intersectable *obj, 
+        void UpdateObjPvsContri(Intersectable *obj, 
                                          const int cf, 
                                          float &frontPvs, 
@@ -1602 +1625 @@
         float GetMemUsage() const;
 
-        /** Evaluates the influence on the pvs of the event.
+        /** Evaluate the contributions of view cell volume of the left and the right view cell.
+        */
+        void EvalVolumeContribution(const VssRay &ray, 
+                                                                        float &volLeft, 
+                                                                        float &volRight);
+
+/** Evaluates the influence on the pvs of the event.
                 @param ve the visibility event
                 @param pvsLeft updates the left pvs
@@ -1612 +1641 @@
                 float &volRight,
                 int &pvsLeft,
-                int &pvsRight,
-                int &viewCellsLeft,
-                int &viewCellsRight);
-
-        /** Evaluate the contributions of view cell volume of the left and the right view cell.
-        */
-        void EvalVolumeContribution(const VssRay &ray, 
-                                                                float &volLeft, 
-                                                                float &volRight,
-                                                                int &viewCellsLeft,
-                                                                int &viewCellsRight);
+                int &pvsRight);
 
         /** Prepares objects for the cost heuristics.
@@ -1646 +1665 @@
                 ViewCellContainer &viewCells);
 
-        void ProcessRays(const VssRayContainer &sampleRays,
+        /** Rays will be clipped to the bounding box.
+        */
+        void PreprocessRays(const VssRayContainer &sampleRays,
                 RayInfoContainer &rays);
 
@@ -1658 +1679 @@
         bool EndPointInsideNode(KdLeaf *leaf, VssRay &ray, bool isTermination) const;
 
-        void AddViewCellVolume(ViewCell *vc,
-                                                   const int cf,
-                                                   float &frontPvs,
-                                                   float &backPvs,
-                                                   float &totalPvs) const;
+        void AddViewCellVolumeContri(
+                ViewCell *vc, 
+                float &frontVol, 
+                float &backVol,
+                float &frontAndBackVol) const;
+
+        /** Classifies and mail view cell with respect to the heuristics contribution.
+                Set view cell mail box according to it's influence on 
+                front (0), back (1) and front / back node (2).
+        */
+        void  MailViewCell(ViewCell *vc, const int cf) const;
 
         int ClassifyRay(VssRay *ray, KdLeaf *leaf, const AxisAlignedPlane &plane) const;
@@ -1671 +1698 @@
                 const float renderCostDecr,
                 const float totalRenderCost);
+
+        void EvalViewCellsForHeuristics(const VssRay &ray, 
+                float &volLeft, 
+                float &volRight);
 
 protected: