Changeset 1145 for GTP/trunk/Lib/Vis/Preprocessing/src/VspOspTree.cpp

Timestamp:

07/24/06 10:12:34 (18 years ago)

Author:

mattausch

Message:

vsposp debug version

File:

• GTP/trunk/Lib/Vis/Preprocessing/src/VspOspTree.cpp (modified) (60 diffs)

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

@@ -103 +103 @@
 
 
+void OspTreeStatistics::Print(ostream &app) const
+{
+        app << "=========== OspTree statistics ===============\n";
+
+        app << setprecision(4);
+
+        app << "#N_CTIME  ( Construction time [s] )\n" << Time() << " \n";
+
+        app << "#N_NODES ( Number of nodes )\n" << nodes << "\n";
+
+        app << "#N_INTERIORS ( Number of interior nodes )\n" << Interior() << "\n";
+
+        app << "#N_LEAVES ( Number of leaves )\n" << Leaves() << "\n";
+
+        app << "#AXIS_ALIGNED_SPLITS (number of axis aligned splits)\n" << splits[0] + splits[1] + splits[2] << endl;
+
+        app << "#N_SPLITS ( Number of splits in axes x y z)\n";
+
+        for (int i = 0; i < 3; ++ i)
+                app << splits[i] << " ";
+        app << endl;
+
+        app << "#N_PMAXDEPTHLEAVES ( Percentage of leaves at maximum depth )\n" 
+                <<      maxDepthNodes * 100 / (double)Leaves() << endl;
+
+        app << "#N_PMINPVSLEAVES  ( Percentage of leaves with mininimal PVS )\n" 
+                << minPvsNodes * 100 / (double)Leaves() << endl;
+
+        //app << "#N_PMINRAYSLEAVES  ( Percentage of leaves with minimal number of rays)\n" 
+        //      << minRaysNodes * 100 / (double)Leaves() << endl;
+
+        app << "#N_MAXCOSTNODES  ( Percentage of leaves with terminated because of max cost ratio )\n"
+                << maxCostNodes * 100 / (double)Leaves() << endl;
+
+        app << "#N_PMINPROBABILITYLEAVES  ( Percentage of leaves with mininum probability )\n"
+                << minProbabilityNodes * 100 / (double)Leaves() << endl;
+
+//      app << "#N_PMAXRAYCONTRIBLEAVES  ( Percentage of leaves with maximal ray contribution )\n" 
+//              <<      maxRayContribNodes * 100 / (double)Leaves() << endl;
+
+        app << "#N_PMAXDEPTH ( Maximal reached depth )\n" << maxDepth << endl;
+
+        app << "#N_PMINDEPTH ( Minimal reached depth )\n" << minDepth << endl;
+
+        app << "#AVGDEPTH ( average depth )\n" << AvgDepth() << endl;
+
+        app << "#N_INVALIDLEAVES (number of invalid leaves )\n" << invalidLeaves << endl;
+
+//      app << "#N_RAYS (number of rays / leaf)\n" << AvgRays() << endl;
+        //app << "#N_PVS: " << pvs << endl;
+
+        app << "========== END OF VspTree statistics ==========\n";
+}
+
+
 /******************************************************************/
 /*                  class VspNode implementation                  */
@@ -471 +526 @@
 void VspTree::AddSubdivisionStats(const int viewCells,
                                                                   const float renderCostDecr,
-                                                                  const float splitCandidateCost,
                                                                   const float totalRenderCost,
                                                                   const float avgRenderCost)
@@ -478 +532 @@
                         << "#ViewCells\n" << viewCells << endl
                         << "#RenderCostDecrease\n" << renderCostDecr << endl 
-                        << "#SplitCandidateCost\n" << splitCandidateCost << endl
                         << "#TotalRenderCost\n" << totalRenderCost << endl
                         << "#AvgRenderCost\n" << avgRenderCost << endl;
@@ -584 +637 @@
 
 
+void VspTree::EvalSubdivisionStats(const VspTraversalData &tData,
+                                                                   const VspTraversalData &tFrontData,
+                                                                   const VspTraversalData &tBackData
+                                                                   )
+{
+        const float cFront = (float)tFrontData.mPvs * tFrontData.mProbability;
+        const float cBack = (float)tBackData.mPvs * tBackData.mProbability;
+        const float cData = (float)tData.mPvs * tData.mProbability;
+        
+        const float costDecr = 
+                (cFront + cBack - cData) / mBoundingBox.GetVolume();
+
+        mTotalCost += costDecr;
+        mTotalPvsSize += tFrontData.mPvs + tBackData.mPvs - tData.mPvs;
+
+        AddSubdivisionStats(mVspStats.Leaves(),
+                                                -costDecr,
+                                                mTotalCost,
+                                                (float)mTotalPvsSize / (float)mVspStats.Leaves());
+}
+
+
 VspNode *VspTree::Subdivide(SplitQueue &tQueue,
-                                                        VspSplitCandidate &splitCandidate,
+                                                        SplitCandidate *splitCandidate,
                                                         const bool globalCriteriaMet)
 {
-        VspTraversalData &tData = splitCandidate.mParentData;
+        // doto remove dynamic cast
+        VspSplitCandidate *sc = dynamic_cast<VspSplitCandidate *>(splitCandidate);
+        VspTraversalData &tData = sc->mParentData;
 
         VspNode *newNode = tData.mNode;
@@ -600 +677 @@
                 
                 // create new interior node and two leaf node
-                const AxisAlignedPlane splitPlane = splitCandidate.mSplitPlane;
+                const AxisAlignedPlane splitPlane = sc->mSplitPlane;
                 newNode = SubdivideNode(splitPlane, tData, tFrontData, tBackData);
         
-                const int maxCostMisses = splitCandidate.mMaxCostMisses;
+                const int maxCostMisses = sc->mMaxCostMisses;
 
 
@@ -611 +688 @@
                         
         
-                if (1)
-                {
-                        //-- subdivision statistics
-
-                        const float cFront = (float)tFrontData.mPvs * tFrontData.mProbability;
-                        const float cBack = (float)tBackData.mPvs * tBackData.mProbability;
-                        const float cData = (float)tData.mPvs * tData.mProbability;
-        
-                        const float costDecr = 
-                                (cFront + cBack - cData) / mBoundingBox.GetVolume();
-
-                        mTotalCost += costDecr;
-                        mTotalPvsSize += tFrontData.mPvs + tBackData.mPvs - tData.mPvs;
-
-                        AddSubdivisionStats(mVspStats.Leaves(),
-                                                                -costDecr,
-                                                                splitCandidate.GetPriority(),
-                                                                mTotalCost,
-                                                                (float)mTotalPvsSize / (float)mVspStats.Leaves());
-                }
-
-
+                if (1) //-- subdivision statistics
+                        EvalSubdivisionStats(tData, tFrontData, tBackData);
+                
                 //-- evaluate new split candidates for global greedy cost heuristics
+
                 VspSplitCandidate *frontCandidate = new VspSplitCandidate(tFrontData);
                 VspSplitCandidate *backCandidate = new VspSplitCandidate(tBackData);
@@ -645 +704 @@
                 // delete old view cell
                 delete tData.mNode->mViewCell;
+
                 // delete old leaf node
                 DEL_PTR(tData.mNode);
@@ -702 +762 @@
                 SelectSplitPlane(splitCandidate.mParentData, splitCandidate.mSplitPlane, frontProb, backProb);
 
+        float oldRenderCost;
+
         // compute global decrease in render cost
-        const float priority = EvalRenderCostDecrease(splitCandidate.mSplitPlane, splitCandidate.mParentData);
+        const float renderCostDecr = EvalRenderCostDecrease(splitCandidate.mSplitPlane, 
+                                                                                                                splitCandidate.mParentData,
+                                                                                                                oldRenderCost);
+
+        splitCandidate.SetRenderCostDecrease(renderCostDecr);
+
+#if 0
+        const float priority = (float)-data.mDepth;
+#else   
+
+        // take render cost of node into account 
+        // otherwise danger of being stuck in a local minimum!!
+        const float factor = mRenderCostDecreaseWeight;
+        const float priority = factor * renderCostDecr + (1.0f - factor) * oldRenderCost;
+#endif
+        
         splitCandidate.SetPriority(priority);
-        splitCandidate.mMaxCostMisses = success ? splitCandidate.mParentData.mMaxCostMisses : splitCandidate.mParentData.mMaxCostMisses + 1;
+
+        // max cost threshold violated?
+        splitCandidate.mMaxCostMisses = 
+                success ? splitCandidate.mParentData.mMaxCostMisses : splitCandidate.mParentData.mMaxCostMisses + 1;
         //Debug << "p: " << tData.mNode << " depth: " << tData.mDepth << endl;
 }
@@ -1404 +1484 @@
         
         //if (axis != 1)
-        Debug << "axis=" << axis << " costRatio=" << ratio << " pos=" << position << " t=" << (position - minBox) / (maxBox - minBox)
-              <<"\t pb=(" << pvsBack << ")\t pf=(" << pvsFront << ")" << endl;
+        //Debug << "axis=" << axis << " costRatio=" << ratio << " pos=" << position << " t=" << (position - minBox) / (maxBox - minBox)
+        //      <<"\t pb=(" << pvsBack << ")\t pf=(" << pvsFront << ")" << endl;
+
+        const float volRatio = tData.mBoundingBox.GetVolume() / (sizeBox * mBoundingBox.GetVolume());
+
+        Debug << "\n§§§§ eval local cost §§§§" << endl
+                  << "back pvs: " << penaltyBack << " front pvs: " << penaltyFront << " total pvs: " << penaltyOld << endl 
+                  << "back p: " << pBack * volRatio << " front p " << pFront * volRatio << " p: " << pOverall * volRatio << endl
+                  << "old rc: " << oldRenderCost * volRatio << " new rc: " << newRenderCost * volRatio << endl
+                  << "render cost decrease: " << oldRenderCost * volRatio - newRenderCost * volRatio << endl;
 
         return ratio;
@@ -1497 +1585 @@
 
 float VspTree::EvalRenderCostDecrease(const AxisAlignedPlane &candidatePlane,
-                                                                          const VspTraversalData &data) const
-{
-#if 0
-        return (float)-data.mDepth;
-#endif
+                                                                          const VspTraversalData &data,
+                                                                          float &normalizedOldRenderCost) const
+{
         float pvsFront = 0;
         float pvsBack = 0;
@@ -1511 +1597 @@
         float pBack = 0;
 
+        const float viewSpaceVol = mBoundingBox.GetVolume();
 
         // create unique ids for pvs heuristics
-        Intersectable::NewMail();
+        Intersectable::NewMail(3);
         
         RayInfoContainer::const_iterator rit, rit_end = data.mRays->end();
@@ -1555 +1642 @@
         const float newRenderCost = penaltyFront * pFront + penaltyBack * pBack;
 
+        normalizedOldRenderCost = oldRenderCost / viewSpaceVol;
+
         //Debug << "decrease: " << oldRenderCost - newRenderCost << endl;
-        const float renderCostDecrease = (oldRenderCost - newRenderCost) / mBoundingBox.GetVolume();
-        
-        // take render cost of node into account 
-        // otherwise danger of being stuck in a local minimum!!
-        const float factor = mRenderCostDecreaseWeight;
-
-        const float normalizedOldRenderCost = oldRenderCost / mBoundingBox.GetVolume();
-        return factor * renderCostDecrease + (1.0f - factor) * normalizedOldRenderCost;
+        const float renderCostDecrease = (oldRenderCost - newRenderCost) / viewSpaceVol;
+        
+        
+        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
+                  << "old rc: " << normalizedOldRenderCost << " new rc: " << newRenderCost / viewSpaceVol << endl
+                  << "render cost decrease: " << renderCostDecrease << endl;
+
+        return renderCostDecrease;
 }
 
@@ -1579 +1670 @@
         
         // create unique ids for pvs heuristics
-        Intersectable::NewMail();
+        Intersectable::NewMail(3);
 
         const int pvsSize = data.mPvs;
@@ -1601 +1692 @@
         pOverall = data.mProbability;
 
-        // we take simplified computation for spatial mid split
+        // we use spatial mid split => simplified computation
         pBack = pFront = pOverall * 0.5f;
         
@@ -1625 +1716 @@
                 return;
 
-        //const float renderCost = mViewCellsManager->EvalRenderCost(obj);
+        //const float renderCost = mViewCellsManager->SimpleRay &raynderCost(obj);
         const int renderCost = 1;
 
@@ -1634 +1725 @@
         }
 
-        // TODO: does this really belong to no pvs?
+        // QUESTION matt: is it safe to assume that 
+        // the object belongs to no pvs in this case?
         //if (cf == Ray::COINCIDENT) return;
 
@@ -2162 +2254 @@
 
         Intersectable::NewMail();
-        ViewCell::NewMail();
+        //ViewCell::NewMail();
 
         Vector3 entp = origin;
@@ -2225 +2317 @@
                         ViewCell *vc = leaf->GetViewCell();
 
-                        if (!vc->Mailed())
-                        {
-                                vc->Mail();
+                        // don't have to mail because each view cell belongs to exactly one leaf
+                        //if (!vc->Mailed())
+                        //{
+                        //      vc->Mail();
                                 viewcells.push_back(vc);
                                 ++ hits;
-                        }
+                        //}
 #if 0
                         leaf->mRays.push_back(RayInfo(new VssRay(origin, termination, NULL, NULL, 0)));
@@ -2785 +2878 @@
         //-- debug output
 
-        Debug << "******* OSP options ******** " << endl;
+        Debug << "******* OSP tree options ******** " << endl;
 
     Debug << "max depth: " << mTermMaxDepth << endl;
@@ -2951 +3044 @@
 
 KdNode *OspTree::Subdivide(SplitQueue &tQueue,
-                                                   OspSplitCandidate &splitCandidate,
+                                                   SplitCandidate *splitCandidate,
                                                    const bool globalCriteriaMet)
 {
-        OspTraversalData &tData = splitCandidate.mParentData;
+        OspSplitCandidate *sc = dynamic_cast<OspSplitCandidate *>(splitCandidate);
+        OspTraversalData &tData = sc->mParentData;
+
         KdNode *newNode = tData.mNode;
 
@@ -2965 +3060 @@
                 
                 // create new interior node and two leaf node
-                const AxisAlignedPlane splitPlane = splitCandidate.mSplitPlane;
+                const AxisAlignedPlane splitPlane = sc->mSplitPlane;
                 
                 newNode = SubdivideNode(splitPlane, 
@@ -2972 +3067 @@
                                                                 tBackData);
         
-                const int maxCostMisses = splitCandidate.mMaxCostMisses;
+                const int maxCostMisses = sc->mMaxCostMisses;
 
                 // how often was max cost ratio missed in this branch?
@@ -3015 +3110 @@
                 SelectSplitPlane(splitCandidate.mParentData, splitCandidate.mSplitPlane, frontProb, backProb);
 
-        const float priority = EvalRenderCostDecrease(splitCandidate.mSplitPlane, splitCandidate.mParentData);
+        float oldRenderCost;
+
+        // compute global decrease in render cost
+        const float renderCostDecr = EvalRenderCostDecrease(splitCandidate.mSplitPlane, 
+                                                                                                                splitCandidate.mParentData,
+                                                                                                                oldRenderCost);
+
+        splitCandidate.SetRenderCostDecrease(renderCostDecr);
+
+#if 0
+        const float priority = (float)-data.mDepth;
+#else   
+        // take render cost of node into account 
+        // otherwise danger of being stuck in a local minimum!!
+        const float factor = mRenderCostDecreaseWeight;
+        const float priority = factor * renderCostDecr + (1.0f - factor) * oldRenderCost;
+
+#endif
+
         // compute global decrease in render cost
         splitCandidate.SetPriority(priority);
@@ -3112 +3225 @@
         SortSplitCandidates(tData, axis, minBand, maxBand);
 
-        float totalVol = PrepareHeuristics(tData);
+        int numViewCells;
+
+        float totalVol = PrepareHeuristics(tData, numViewCells);
         float voll = 0;
         float volr = totalVol;
+
+        int vcl = 0;
+        int vcr = numViewCells;
   
         const int totalPvs = tData.mNode->mObjects.size();
@@ -3121 +3239 @@
         int pvsr = totalPvs;
 
-        // if no good split can be found, take mid split
+        float sum = (float)totalVol * sizeBox;
+
+        /////////////////////////////////
+
+        // note: initialised to take mid split 
+        // if no good split can be found,
         position = minBox + 0.5f * sizeBox;
         
@@ -3127 +3250 @@
         float ratio = 99999999.0f;
         bool splitPlaneFound = false;
-   
-    float minSum = 1e20f;
 
         float volBack = voll;
         float volFront = volr;
 
-        int pvsBack = 0;
-        int pvsFront = 0;
-        
-
-        float sum = (float)totalVol * sizeBox;
+        int pvsBack = pvsl;
+        int pvsFront = pvsr;
+        
+        float minSum = 1e20f;
+
+        /////////////////////////////
 
         Intersectable::NewMail();
@@ -3150 +3272 @@
                 Intersectable *object = (*ci).mObject;
 
-                EvalHeuristicsContribution(*ci, voll, volr, pvsl, pvsr);
-
-                cout << "incr: " << ci->mObject->mViewCellPvs.GetSize() << " obj id " 
-                         << ci->mObject->GetId() << endl;
+                EvalHeuristicsContribution(tData.mNode, 
+                                                                   *ci, 
+                                                                   voll, volr, 
+                                                                   pvsl, pvsr,
+                                                                   vcl, vcr);
 
                 // Note: sufficient to compare size of bounding boxes of front and back side?
+
                 if (((*ci).mPos >= minBand) && ((*ci).mPos <= maxBand))
                 {
-                        //sum = costl * ((*ci).value - minBox) + costr * (maxBox - (*ci).value);
-                        sum = voll * pvsBack + volr * pvsFront;
-
-                        cout << "pos: " << (*ci).mPos 
-                                 << "\t (pvsl: " << pvsBack << ", pvsr: " << pvsFront << ")"
+                        sum = voll * pvsl + volr * pvsr;
+
+                        // note matt: can happen that volr is less than zero: bug or numerical error?
+                        //if (volr < 0)         Debug << "warning!! " << totalVol << " " << volRightDecr << " " << volRightDecr - totalVol << endl;
+
+                        /*Debug << "pos: " << (*ci).mPos 
+                                 << "\t (pvsl: " << pvsl << ", pvsr: " << pvsr << ")"
                                  << "\t (voll: " << voll << ", volr: " << volr << ")"
-                                 << "\t sum: " << sum << endl;
+                                 << "\t (vcl: " << vcl << ", vcr: " << vcr << ", nvc: " << numViewCells << ")"
+                                 << "\t sum: " << sum << endl;*/
 
                         if (sum < minSum)
@@ -3193 +3320 @@
         const float pFront = volFront;
 
-        const float penaltyOld = (float)totalPvs;//EvalPvsPenalty(pvsSize, lowerPvsLimit, upperPvsLimit);
-    const float penaltyFront = (float)pvsFront;//EvalPvsPenalty(pvsFront, lowerPvsLimit, upperPvsLimit);
-        const float penaltyBack = (float)pvsBack;//EvalPvsPenalty(pvsBack, lowerPvsLimit, upperPvsLimit);
+        const float penaltyOld = (float)totalPvs;
+    const float penaltyFront = (float)pvsFront;
+        const float penaltyBack = (float)pvsBack;
         
         const float oldRenderCost = penaltyOld * pOverall + Limits::Small;
@@ -3206 +3333 @@
         }
         
-        //if (axis != 1)
-        Debug << "axis=" << axis << " costRatio=" << ratio << " pos=" 
-                  << position << " t=" << (position - minBox) / (maxBox - minBox)
-              << "\t pb=(" << volBack << ")\t pf=(" << volFront << ")" << endl;
+        //Debug << "axis=" << axis << " costRatio=" << ratio << " pos=" 
+        //        << position << " t=" << (position - minBox) / (maxBox - minBox)
+        //      << "\t pb=(" << volBack << ")\t pf=(" << volFront << ")" << endl;
+
+        const float viewSpaceVol = mVspTree->GetBoundingBox().GetVolume();
+
+        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
+                  << "old rc: " << oldRenderCost / viewSpaceVol << " new rc: " << newRenderCost / viewSpaceVol << endl
+                  << "render cost decrease: " << oldRenderCost / viewSpaceVol - newRenderCost / viewSpaceVol << endl;
 
         return ratio;
@@ -3255 +3389 @@
                 
                 // if hitpoint with object is inside this node
-                if (GetLeaf(ray->mOrigin, ray->mOriginNode) == leaf)
+                if (ray->mOriginObject && (GetLeaf(ray->mOrigin, ray->mOriginNode) == leaf))
                 {
                         pos = ray->mOrigin[axis];
@@ -3267 +3401 @@
                 }
 
-                if (GetLeaf(ray->mTermination, ray->mTerminationNode) == leaf)
+                if (ray->mTerminationObject && (GetLeaf(ray->mTermination, ray->mTerminationNode) == leaf))
                 {
                         pos = ray->mTermination[axis];
@@ -3274 +3408 @@
                                 SortableEntry(SortableEntry::BOX_INTERSECT, 
                                                           pos, 
-                                                          ray->mOriginObject, 
+                                                          ray->mTerminationObject, 
                                                           ray)
                                                           );
@@ -3319 +3453 @@
 
 
-float OspTree::PrepareHeuristics(const VssRay &ray)
+float OspTree::PrepareHeuristics(const VssRay &ray, int &numViewCells)
 {
         float vol = 0;
+        numViewCells = 0;
 
         ViewCellContainer viewCells;
 
         mVspTree->GetViewCells(ray, viewCells);
-    
+        
         ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
 
@@ -3335 +3470 @@
                 if (!vc->Mailed())
                 {
+                        //Debug << "single vol: "<< vc->GetVolume() << endl;
                         vc->Mail();
                         vc->mCounter = 0;
                         vol += vc->GetVolume();
-                }
+                        ++ numViewCells;
+                }
+                
+                // view cell volume already added => just increase counter
+                ++ vc->mCounter;
         }
 
@@ -3345 +3485 @@
 
 
-float OspTree::PrepareHeuristics(const OspTraversalData &tData)
+float OspTree::PrepareHeuristics(const OspTraversalData &tData, int &numViewCells)
 {       
+        float vol = 0;
+
         Intersectable::NewMail();
         ViewCell::NewMail();
-
-        float vol = 0;
+        numViewCells = 0;
 
         KdLeaf *leaf = tData.mNode;
@@ -3359 +3500 @@
         {
                 VssRay *ray = (*rit).mRay;
+
+                int newViewCells;
 
                 // if hitpoint with one of the objects is inside this node, we
                 // evaluate the volume of the view cells seen by this ray
-                if ((GetLeaf(ray->mOrigin, ray->mOriginNode) == leaf) ||
-                        (GetLeaf(ray->mTermination, ray->mTerminationNode) == leaf))
-                {
-            vol += PrepareHeuristics(tData);
-                }
-        }
-
+                if (ray->mOriginObject && (GetLeaf(ray->mOrigin, ray->mOriginNode) == leaf))
+                {
+            vol += PrepareHeuristics(*ray, newViewCells);
+                        numViewCells += newViewCells;
+                }
+
+                // count double if both hit points are within the kd node
+                if (ray->mTerminationObject && (GetLeaf(ray->mTermination, ray->mTerminationNode) == leaf))
+                {
+                        vol += PrepareHeuristics(*ray, newViewCells);
+                        numViewCells += newViewCells;
+                }
+        }
+
+        //Debug << "vol: " << vol << endl;
         return vol;
 }
 
 
-void OspTree::EvalHeuristicsContribution(const SortableEntry &ci,
+void OspTree::EvalHeuristicsContribution(KdLeaf *leaf,
+                                                                                 const SortableEntry &ci,
                                                                                  float &volLeft,
                                                                                  float &volRight,
                                                                                  int &pvsLeft,
-                                                                                 int &pvsRight)
+                                                                                 int &pvsRight,
+                                                                                 int &viewCellsLeft,
+                                                                                 int &viewCellsRight)
 {
         Intersectable *obj = ci.mObject;
         VssRay *ray = ci.mRay;
-
+        
         switch (ci.mType) 
         {
@@ -3395 +3549 @@
                 // compute volume contribution from view cells
                 case SortableEntry::BOX_INTERSECT:
-                        EvalVolumeContribution(*ray, volRight, volLeft);
+                                if ((ray->mOriginObject && (GetLeaf(ray->mOrigin, ray->mOriginNode) == leaf)) ||
+                                        (ray->mTerminationObject && (GetLeaf(ray->mTermination, ray->mTerminationNode) == leaf)))
+                                {
+                                        EvalVolumeContribution(*ray, volLeft, volRight, viewCellsLeft, viewCellsRight);
+                                }
                         break;
                 default:
@@ -3406 +3564 @@
 
 
-void OspTree::EvalVolumeContribution(const VssRay &ray, float &volLeft, float &volRight)
+void OspTree::EvalVolumeContribution(const VssRay &ray, 
+                                                                         float &volLeft, 
+                                                                         float &volRight,
+                                                                         int &viewCellsLeft,
+                                                                         int &viewCellsRight)
 {
         ViewCellContainer viewCells;
@@ -3413 +3575 @@
 
         ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
-
+        
         for (vit = viewCells.begin(); vit != vit_end; ++ vit)
         {
-                // view cells comes to left child node
+                // add view cells volume to left child node
                 ViewCell *viewCell = *vit;
 
@@ -3422 +3584 @@
                 {
                         viewCell->Mail();
+                        
                         volLeft += viewCell->GetVolume();
+
+                        ++ viewCellsLeft;
                 }
 
                 // remove from right child node
-
                 if (-- viewCell->mCounter == 0)
                 {
                         volRight -= viewCell->GetVolume();
+
+                        -- viewCellsRight;
                 }
         }
@@ -3520 +3686 @@
         pBack = nProbBack[bestAxis];
 
-        //Debug << "val: " << nCostRatio[bestAxis] << " axis: " << bestAxis << endl;
+        Debug << "val: " << nCostRatio[bestAxis] << " axis: " << bestAxis << endl;
         return nCostRatio[bestAxis];
 }
 
 
+bool OspTree::EndPointInsideNode(KdLeaf *leaf, 
+                                                                 VssRay &ray, 
+                                                                 bool isTermination) const
+{
+        // test if the leaf where the hitpoint is located is the current leaf
+        if (isTermination)
+        {
+                 return ray.mTerminationObject && (GetLeaf(ray.mTermination, ray.mOriginNode) == leaf);
+        }
+        else
+        {
+                 return ray.mOriginObject && (GetLeaf(ray.mOrigin, ray.mOriginNode) == leaf);
+        }
+}
+
+
+#if TODO
+void OspTree::EvalSubdivisionStats(const VspTraversalData &tData,
+                                                                   const VspTraversalData &tFrontData,
+                                                                   const VspTraversalData &tBackData
+                                                                   )
+{
+        const float cFront = (float)tFrontData.mPvs * tFrontData.mProbability;
+        const float cBack = (float)tBackData.mPvs * tBackData.mProbability;
+        const float cData = (float)tData.mPvs * tData.mProbability;
+        
+        const float costDecr = 
+                (cFront + cBack - cData) / mBoundingBox.GetVolume();
+
+        mTotalCost += costDecr;
+        mTotalPvsSize += tFrontData.mPvs + tBackData.mPvs - tData.mPvs;
+
+        AddSubdivisionStats(mVspStats.Leaves(),
+                                                -costDecr,
+                                                sc->GetPriority(),
+                                                mTotalCost,
+                                                (float)mTotalPvsSize / (float)mVspStats.Leaves());
+}
+#endif
+
+
+int OspTree::ClassifyRay(VssRay *ray, 
+                                                 KdLeaf *leaf, 
+                                                 const AxisAlignedPlane &plane) const
+{
+        const bool originInside = EndPointInsideNode(leaf, *ray, false);
+    const bool terminationInside = EndPointInsideNode(leaf, *ray, true);
+
+        const bool originGt = 
+                ray->mOrigin[plane.mAxis] > plane.mPosition;
+                
+        const bool terminationGt = 
+                ray->mTermination[plane.mAxis] > plane.mPosition;
+
+        // add view cell volume to front volume
+        const bool addToFront = ((originInside && originGt) || (terminationInside && terminationGt));
+
+        // add view cell volume to back volume
+        const bool addToBack = ((originInside && !originGt) || (terminationInside && !terminationGt));
+
+        // classify ray with respect to the child nodes the view cells contribute
+        if (addToFront && addToBack)
+                return 0;
+        else if (addToBack)
+                return -1;
+        else if (addToFront)
+                return 1;
+
+        return -2;
+}
+
+
 float OspTree::EvalRenderCostDecrease(const AxisAlignedPlane &candidatePlane,
-                                                                          const OspTraversalData &tData) const
-{
-#if 0
-        return (float)-tData.mDepth;
-#endif
-
+                                                                          const OspTraversalData &tData,
+                                                                          float &normalizedOldRenderCost) const
+{
         float pvsFront = 0;
         float pvsBack = 0;
@@ -3541 +3776 @@
         float pBack = 0;
 
-        Intersectable::NewMail();
+        const float viewSpaceVol = mVspTree->GetBoundingBox().GetVolume();
+
+        //Intersectable::NewMail();
         KdLeaf::NewMail();
         ViewCell::NewMail();
@@ -3549 +3786 @@
 
         // evaluate reverse pvs and view cell volume on left and right cell
+        // note: should I take all leaf objects or rather the objects hit by rays?
         for (oit = leaf->mObjects.begin(); oit != oit_end; ++ oit)
         {
@@ -3556 +3794 @@
                 ++ totalPvs;
 
-                cout << "totalpvs " << totalPvs << endl;
-
+                //cout << "totalpvs " << totalPvs << endl;
+
+                // test if box falls in left / right child node
                 if (box.Max(candidatePlane.mAxis) > candidatePlane.mPosition)
                 {
@@ -3569 +3808 @@
 
 
-        ViewCell::NewMail();
+        // sum up volume seen from the objects of left and right children
+        // => the volume is the weight for the render cost equation
+        ViewCell::NewMail(3);
         
         RayInfoContainer::const_iterator rit, rit_end = tData.mRays->end();
@@ -3577 +3818 @@
                 VssRay *ray = (*rit).mRay;
 
-                // if hitpoint with one of the objects is inside this node
-                if (GetLeaf(ray->mOrigin, ray->mOriginNode) == leaf)
-                {
+                // test if intersection point with one of the objects is inside this node
+                const bool originInside = EndPointInsideNode(leaf, *ray, false);
+        const bool terminationInside = EndPointInsideNode(leaf, *ray, true);
+
+                if (originInside || terminationInside)
+                {
+                        // add volume to volumes of left and / or right children
+                        // if one of the ray end points is inside
+                        const int classification = ClassifyRay(ray, leaf, candidatePlane);
+
                         ViewCellContainer viewCells;            
                         mVspTree->GetViewCells(*ray, viewCells);
@@ -3585 +3833 @@
                         ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
 
-                        // add view cells volume to front       
+                        // evaluate view cells volume contribution
                         for (vit = viewCells.begin(); vit != vit_end; ++ vit)
                         {
-                                ViewCell *vc = *vit;
-
-                                if (!vc->Mailed())
-                                {
-                                        vc->Mail();
-
-                                        const float vol = vc->GetVolume();
-                                        pOverall += vol;
-
-                                        if (ray->mOrigin[candidatePlane.mAxis] > candidatePlane.mPosition)
-                                                pFront += vol;
-                                        else
-                                                pBack += vol;
-                                }
+                                AddViewCellVolume(*vit, classification, pFront, pBack, pOverall);
                         }
                 }
@@ -3611 +3846 @@
         const float newRenderCost = pvsFront * pFront + pvsBack * pBack;
 
-        Debug << "total pvs: " << totalPvs << " p " << pOverall << endl
-                  << "old: " << oldRenderCost << " new: " << newRenderCost << " decrease: " 
-                  << oldRenderCost - newRenderCost << endl;
-
-        // todo matt§§: how to normalize volume??
-        const float renderCostDecrease = (oldRenderCost - newRenderCost);// / mBoundingBox.GetVolume();
-        
-        // take render cost of node into account 
-        // otherwise danger of being stuck in a local minimum!!
-        const float factor = mRenderCostDecreaseWeight;
-
-        const float normalizedOldRenderCost = oldRenderCost;// / mBoundingBox.GetVolume();
-        return factor * renderCostDecrease + (1.0f - factor) * normalizedOldRenderCost;
+        // normalize volume with view space volume
+        const float renderCostDecrease = (oldRenderCost - newRenderCost) / viewSpaceVol;
+
+        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
+                  << "old rc: " << oldRenderCost / viewSpaceVol << " new rc: " << newRenderCost / viewSpaceVol << endl
+                  << "render cost decrease: " << renderCostDecrease << endl;
+
+        normalizedOldRenderCost = oldRenderCost / viewSpaceVol;
+
+        return renderCostDecrease;
 }
 
@@ -3741 +3975 @@
                 }
         }
-
 }
 
@@ -3961 +4194 @@
 
 
+void OspTree::AddViewCellVolume(ViewCell *vc,
+                                                                const int cf,
+                                                                float &frontVol,
+                                                                float &backVol,
+                                                                float &totalVol) const
+{
+        //const float renderCost = mViewCellsManager->SimpleRay &raynderCost(obj);
+        const float vol = vc->GetVolume();
+
+        // view cell not found yet => new
+        if (!vc->Mailed() && !vc->Mailed(1) && !vc->Mailed(2))
+        {
+                totalVol += vol;
+        }
+
+        if (cf >= 0) // front volume
+        {
+                if (!vc->Mailed() && !vc->Mailed(2))
+                {
+                        frontVol += vol;
+                
+                        // already in back volume => in both volumes
+                        if (vc->Mailed(1))
+                                vc->Mail(2);
+                        else
+                                vc->Mail();
+                }
+        }
+
+        if (cf <= 0) // back volume
+        {
+                if (!vc->Mailed(1) && !vc->Mailed(2))
+                {
+                        backVol += vol;
+                
+                        // already in front volume => in both volume
+                        if (vc->Mailed())
+                                vc->Mail(2);
+                        else
+                                vc->Mail(1);
+                }
+        }
+}
+
 
 /********************************************************************/
@@ -3989 +4266 @@
 
 
-SplitCandidate *HierarchyManager::PrepareVsp(const VssRayContainer &sampleRays,
+VspTree::VspSplitCandidate *HierarchyManager::PrepareVsp(const VssRayContainer &sampleRays,
                                                                                          AxisAlignedBox3 *forcedViewSpace,
                                                                                          RayInfoContainer &rays)
@@ -4009 +4286 @@
         const int pvsSize = mVspTree.ComputePvsSize(rays);
         
-        Debug <<  "pvs size: " << pvsSize << endl;
-        Debug <<  "rays size: " << rays.size() << endl;
+        Debug <<  "pvs size: " << (int)pvsSize << endl;
+        Debug <<  "rays size: " << (int)rays.size() << endl;
 
         //-- prepare view space partition
@@ -4052 +4329 @@
 
 
-SplitCandidate * HierarchyManager::PrepareOsp(const VssRayContainer &sampleRays,
+OspTree::OspSplitCandidate * HierarchyManager::PrepareOsp(const VssRayContainer &sampleRays,
                                                                                           const ObjectContainer &objects,
                                                                                           AxisAlignedBox3 *forcedObjectSpace,
@@ -4139 +4416 @@
         const long startTime = GetTime();       
         
-        int i = 0;
+        RunConstruction(true);
+
+        cout << "finished in " << TimeDiff(startTime, GetTime())*1e-3 << " secs" << endl;
+
+        mVspTree.mVspStats.Stop();
+}
+
+
+bool HierarchyManager::SubdivideSplitCandidate(SplitCandidate *sc)
+{
+        const bool globalTerminationCriteriaMet = 
+                        GlobalTerminationCriteriaMet(sc);
+
+        const bool vspSplit = (sc->Type() == SplitCandidate::VIEW_SPACE);
+
+        if (vspSplit)
+        {
+                mVspTree.Subdivide(mTQueue, sc, globalTerminationCriteriaMet);
+                return true;
+        }
+        else
+        {
+                mOspTree.Subdivide(mTQueue, sc, globalTerminationCriteriaMet);
+                return false;
+        }
+}
+
+
+void HierarchyManager::RunConstruction(const bool repair)
+{
+        int numNodes = 0;
+
         while (!FinishedConstruction())
         {
-                mCurrentCandidate = NextSplitCandidate();
-           
-                const bool globalTerminationCriteriaMet = 
-                        GlobalTerminationCriteriaMet(mCurrentCandidate);
-
-                cout << "view cells: " << i ++ << endl;
-
+                SplitCandidate *splitCandidate = NextSplitCandidate();
+            
+                cout << "nodes: " << ++ numNodes << endl;
+
+                mTotalCost -= splitCandidate->GetRenderCostDecrease();
+
+                //-- subdivide leaf node
+                SubdivideSplitCandidate(splitCandidate);
+                
                 // cost ratio of cost decrease / totalCost
-                const float costRatio = mCurrentCandidate->GetPriority() / mTotalCost;
-                //Debug << "cost ratio: " << costRatio << endl;
+                const float costRatio = splitCandidate->GetRenderCostDecrease() / mTotalCost;
+                
+                Debug << "\n**********" << endl
+                          << "total cost: " << mTotalCost << " render cost decr: " 
+                          << splitCandidate->GetRenderCostDecrease() 
+                          << " cost ratio: " << costRatio << endl << 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();
+                if (repair)
+                        RepairQueue();
+
+                DEL_PTR(splitCandidate);
+        }
 }
 
@@ -4195 +4488 @@
         RayInfoContainer *objectSpaceRays = new RayInfoContainer();
 
+
         /////////////////////////////////////////////////////////////
         // view space space partition
         /////////////////////////////////////////////////////////////
+
 
         // makes no sense otherwise because only one kd cell available
@@ -4207 +4502 @@
         mVspTree.mStoreKdPvs = false;
 
-        SplitCandidate *sc = PrepareVsp(sampleRays, forcedViewSpace, *viewSpaceRays);
-        mTQueue.Push(sc);
+        VspTree::VspSplitCandidate *vsc = 
+                PrepareVsp(sampleRays, forcedViewSpace, *viewSpaceRays);
+        // add to queue
+        mTQueue.Push(vsc);
 
         long startTime = GetTime();
@@ -4218 +4515 @@
         int i = 0;
 
-        while (!FinishedConstruction())
-        {
-                SplitCandidate *splitCandidate = NextSplitCandidate();
-            
-                const bool globalTerminationCriteriaMet = 
-                        GlobalTerminationCriteriaMet(splitCandidate);
-
-                cout << "vsp nodes: " << i ++ << endl;
-
-                // cost ratio of cost decrease / totalCost
-                const float costRatio = splitCandidate->GetPriority() / mTotalCost;
-                //cout << "cost ratio: " << costRatio << endl;
-
-                if (costRatio < mTermMinGlobalCostRatio)
-                        ++ mGlobalCostMisses;
-
-                //-- subdivide leaf node
-
-                // we have either a object space or view space split
-                VspTree::VspSplitCandidate *sc = 
-                        dynamic_cast<VspTree::VspSplitCandidate *>(splitCandidate);
-
-        
-                VspNode *r = mVspTree.Subdivide(mTQueue, *sc, globalTerminationCriteriaMet);
-
-                DEL_PTR(splitCandidate);
-        }
+        // all objects can be seen from everywhere
+        mTotalCost = (float)vsc->mParentData.mPvs;
+
+        const bool repairQueue = false;
+
+        // process view space candidates
+        RunConstruction(repairQueue);
 
         cout << "finished in " << TimeDiff(startTime, GetTime())*1e-3 << " secs" << endl;
         mVspTree.mVspStats.Stop();
         
-        
+
+
         /////////////////////////////////////////////////////////////
         // object space partition
         /////////////////////////////////////////////////////////////
 
-        Debug << "**************** osp construction **************" << endl;
+        Debug << "\n$$$$$$$$$ osp tree construction $$$$$$$$$$\n" << endl;
         cout << "starting osp contruction ... " << endl;
 
+        // compute first candidate
+        OspTree::OspSplitCandidate *osc =
+                PrepareOsp(sampleRays, objects, forcedViewSpace, *objectSpaceRays);
+
+    mTQueue.Push(osc);
+
+        mOspTree.mOspStats.Reset();
+        mOspTree.mOspStats.Start();
+
         startTime = GetTime();
 
-        SplitCandidate *osc =
-                PrepareOsp(sampleRays, objects, forcedViewSpace, *objectSpaceRays);
-
-    mTQueue.Push(osc);
-
-
-        i = 0;
-        while (!FinishedConstruction())
-        {
-                SplitCandidate *splitCandidate = NextSplitCandidate();
-            
-                const bool globalTerminationCriteriaMet = 
-                        GlobalTerminationCriteriaMet(splitCandidate);
-
-                // cost ratio of cost decrease / totalCost
-                const float costRatio = splitCandidate->GetPriority() / mTotalCost;
-                
-                //Debug << "cost ratio: " << costRatio << endl;
-                //cout << "kd nodes: " << i ++ << endl;
-
-                if (costRatio < mTermMinGlobalCostRatio)
-                        ++ mGlobalCostMisses;
-
-                //-- subdivide leaf node
-
-                // object space split
-                OspTree::OspSplitCandidate *sc = 
-                        dynamic_cast<OspTree::OspSplitCandidate *>(splitCandidate);
-
-                KdNode *r = mOspTree.Subdivide(mTQueue, *sc, globalTerminationCriteriaMet);
-                
-                DEL_PTR(splitCandidate);
-        }
-        
-        cout << "finished in " << TimeDiff(startTime, GetTime())*1e-3 << " secs" << endl;
-
+        // reset cost
+        // start with one big kd cell - all objects can be seen from everywhere
+        // note: only true for view space = object space
+        mTotalCost = (float)osc->mParentData.mNode->mObjects.size();//(float)sc->mParentData.mPvs;
+
+        Debug << "reseting cost, new total cost: " << mTotalCost << endl;
+
+        // process object space candidates
+        RunConstruction(repairQueue);
+        
+        cout << "finished in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
+
+        mOspTree.mOspStats.Stop();
+
+        // reset parameters
         mVspTree.mUseKdPvsForHeuristics = savedCountMethod;
         mVspTree.mStoreKdPvs = savedStoreMethod;
@@ -4304 +4570 @@
                                                                   AxisAlignedBox3 *forcedViewSpace)
 {
+        // only view space partition
+        // object kd tree is taken for osp
+
         mVspTree.mVspStats.Reset();
         mVspTree.mVspStats.Start();
@@ -4315 +4584 @@
 
         long startTime = GetTime();
-        int i = 0;
-
-        while (!FinishedConstruction())
-        {
-                SplitCandidate *splitCandidate = NextSplitCandidate();
-            
-                const bool globalTerminationCriteriaMet = 
-                        GlobalTerminationCriteriaMet(splitCandidate);
-
-                cout << "vsp nodes: " << i ++ << endl;
-                
-                // cost ratio of cost decrease / totalCost
-                const float costRatio = splitCandidate->GetPriority() / mTotalCost;
-                //cout << "cost ratio: " << costRatio << endl;
-
-                if (costRatio < mTermMinGlobalCostRatio)
-                        ++ mGlobalCostMisses;
-
-                //-- subdivide leaf node
-        
-                // we have either a object space or view space split
-                VspTree::VspSplitCandidate *sc = 
-                        dynamic_cast<VspTree::VspSplitCandidate *>(splitCandidate);
-
-        
-                VspNode *r = mVspTree.Subdivide(mTQueue, *sc, globalTerminationCriteriaMet);
-
-                DEL_PTR(splitCandidate);
-        }
+
+        RunConstruction(false);
 
         cout << "finished in " << TimeDiff(startTime, GetTime())*1e-3 << " secs" << endl;
@@ -4350 +4592 @@
 
 
-bool HierarchyManager::FinishedConstruction()
+bool HierarchyManager::FinishedConstruction() const
 {
         return mTQueue.Empty();