Changeset 2237 for GTP/trunk/Lib/Vis/Preprocessing/src/VspTree.cpp

Timestamp:

03/12/07 18:30:52 (17 years ago)

Author:

mattausch

Message:

worked on optimization. warning: not tested yet

File:

• GTP/trunk/Lib/Vis/Preprocessing/src/VspTree.cpp (modified) (36 diffs)

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

@@ -32 +32 @@
 #define VISUALIZE_SPLIT 0
 #define USE_FIXEDPOINT_T 0
+#define HACK_PERFORMANCE 1
+
 
 /////////////
@@ -513 +515 @@
         //////////////////////////////////////////////
         // bounding box of view space includes all visibility events
+
         mBoundingBox.Initialize();
         VssRayContainer::const_iterator rit, rit_end = rays.end();
@@ -802 +805 @@
         VspLeaf *leaf = static_cast<VspLeaf *>(splitCandidate.mParentData.mNode);
 
+                //////////////
+        //-- compute global decrease in render cost
+
+        const AxisAlignedPlane candidatePlane = splitCandidate.mSplitPlane;
+
+        RayInfoContainer::const_iterator rit, rit_end = splitCandidate.mParentData.mRays->end();
+
+        float frontRenderCost = 0, backRenderCost = 0, totalRenderCost = 0;
+        int  frontSize = 0, backSize = 0, totalSize = 0;
+
+        Intersectable::NewMail(3);
+        KdLeaf::NewMail(3);
+
+        for (rit = splitCandidate.mParentData.mRays->begin(); rit != rit_end; ++ rit)
+        {
+                RayInfo rayInf = *rit;
+
+                float t;
+                
+                // classify ray
+                const int cf = rayInf.ComputeRayIntersection(candidatePlane.mAxis, 
+                                                                                                         candidatePlane.mPosition, 
+                                                                                                         t);
+
+                VssRay *ray = rayInf.mRay;
+#if HACK_PERFORMANCE
+                Intersectable *obj = (*ray).mTerminationObject;
+
+                BvhLeaf *leaf = mBvHierarchy->GetLeaf(obj);
+
+                // evaluate contribution of ray endpoint to front 
+                // and back pvs with respect to the classification
+                UpdateContributionsToPvs(leaf, cf, 
+                                                                 frontRenderCost, backRenderCost, totalRenderCost),
+                                                                 frontSize, backSize, totalSize;
+
+#if COUNT_ORIGIN_OBJECTS
+
+                obj = (*ray).mOriginObject;
+
+                if (obj)
+                {
+                        leaf = mBvHierarchy->GetLeaf(obj);
+
+                        UpdateContributionsToPvs(leaf, cf, 
+                                                                         frontRenderCost, backRenderCost, totalRenderCost,
+                                                                         frontSize, backSize, totalSize);
+                }
+#endif
+
+#else
+                cerr << "TODO classify" << endl;
+#endif
+        }
+
         /////////////
         // avg ray contri
 
-        const int pvs = EvalPvsEntriesSize(*splitCandidate.mParentData.mRays);
-
-        const float avgRayContri = (float)pvs / 
+        const float avgRayContri = (float)totalSize / 
                 ((float)splitCandidate.mParentData.mRays->size() + Limits::Small);
 
@@ -813 +869 @@
 
         const float avgRaysPerObject = 
-                (float)splitCandidate.mParentData.mRays->size() / ((float)pvs + Limits::Small);
+                (float)splitCandidate.mParentData.mRays->size() / ((float)totalSize + Limits::Small);
 
         splitCandidate.SetAvgRayContribution(avgRayContri);
         splitCandidate.SetAvgRaysPerObject(avgRaysPerObject);
 
-        // compute global decrease in render cost
+
         float oldRenderCost;
-        const float renderCostDecr = EvalRenderCostDecrease(splitCandidate, oldRenderCost);
+        const float renderCostDecr = EvalRenderCostDecrease(splitCandidate, oldRenderCost,
+                                                                                                                 totalRenderCost, frontRenderCost, backRenderCost);
         splitCandidate.SetRenderCostDecrease(renderCostDecr);
 
         // the increase in pvs entries num induced by this split
-        const int pvsEntriesIncr = EvalPvsEntriesIncr(splitCandidate);
+        const int pvsEntriesIncr = EvalPvsEntriesIncr(splitCandidate, totalSize, frontSize, backSize);
         splitCandidate.SetPvsEntriesIncr(pvsEntriesIncr);
 
@@ -844 +901 @@
 
 
-int VspTree::EvalPvsEntriesIncr(VspSubdivisionCandidate &splitCandidate) const
-{
-        float oldPvsSize = 0;
-        float fPvsSize = 0;
-        float bPvsSize = 0;
-        
-        const AxisAlignedPlane candidatePlane = splitCandidate.mSplitPlane;
-        
-        Intersectable::NewMail(3);
-        KdLeaf::NewMail(3);
-
+int VspTree::EvalPvsEntriesIncr(VspSubdivisionCandidate &splitCandidate,
+                                                                const float oldPvsSize,
+                                                                const float fPvsSize,
+                                                                const float bPvsSize) const
+{
+        
         RayInfoContainer::const_iterator rit, rit_end = splitCandidate.mParentData.mRays->end();
-
-    // this is the main ray classification loop!
-        for(rit = splitCandidate.mParentData.mRays->begin(); rit != rit_end; ++ rit)
-        {
-                VssRay *ray = (*rit).mRay;
-                RayInfo rayInf = *rit;
-                
-                float t;
-                // classify ray
-                const int cf =  rayInf.ComputeRayIntersection(candidatePlane.mAxis, 
-                                                                                                          candidatePlane.mPosition, t);
-
-                UpdatePvsEntriesContribution(*ray, true, cf, fPvsSize, bPvsSize, oldPvsSize);
-#if COUNT_ORIGIN_OBJECTS
-                UpdatePvsEntriesContribution(*ray, false, cf, fPvsSize, bPvsSize, oldPvsSize);
-#endif
-        }
 
         const float oldPvsRatio = (splitCandidate.mParentData.mPvs > 0) ? 
@@ -1188 +1223 @@
 
 
-int VspTree::EvalMaxEventContribution(KdLeaf *leaf) const
-{
-        int pvs = 0;
+float VspTree::EvalMaxEventContribution(KdLeaf *leaf) const
+{
+        float pvs = 0;
 
         // leaf falls out of right pvs
         if (-- leaf->mCounter == 0)
         {
-                pvs -= ((int)leaf->mObjects.size() - (int)leaf->mMultipleObjects.size());
+                pvs -= ((float)leaf->mObjects.size() - (float)leaf->mMultipleObjects.size());
         }
 
@@ -1217 +1252 @@
 
 
-int VspTree::EvalMinEventContribution(KdLeaf *leaf) const
+float VspTree::EvalMinEventContribution(KdLeaf *leaf) const
 {
         if (leaf->Mailed())
@@ -1225 +1260 @@
 
         // add objects without those which are part of several kd leaves
-        int pvs = ((int)leaf->mObjects.size() - (int)leaf->mMultipleObjects.size());
+        float pvs = ((float)leaf->mObjects.size() - (float)leaf->mMultipleObjects.size());
 
         // separately handle objects which are part of several kd leaves 
@@ -1644 +1679 @@
 
 float VspTree::EvalRenderCostDecrease(VspSubdivisionCandidate &sc,
-                                                                          float &normalizedOldRenderCost) const
-{
-        float pvsFront = 0;
-        float pvsBack = 0;
-        float totalPvs = 0;
-
+                                                                          float &normalizedOldRenderCost,
+                                                                          const float totalPvs,
+                                                                          const float pvsFront,
+                                                                          const float pvsBack) const
+{
         const float viewSpaceVol = mBoundingBox.GetVolume();
         const VspTraversalData &tData = sc.mParentData;
@@ -1663 +1697 @@
         Intersectable::NewMail(3);
         KdLeaf::NewMail(3);
-
-        RayInfoContainer::const_iterator rit, rit_end = tData.mRays->end();
-
-        for (rit = tData.mRays->begin(); rit != rit_end; ++ rit)
-        {
-                RayInfo rayInf = *rit;
-
-                float t;
-                
-                // classify ray
-                const int cf = rayInf.ComputeRayIntersection(candidatePlane.mAxis, 
-                                                                                                         candidatePlane.mPosition, 
-                                                                                                         t);
-
-                VssRay *ray = rayInf.mRay;
-
-                // evaluate contribution of ray endpoint to front 
-                // and back pvs with respect to the classification
-                UpdateContributionsToPvs(*ray, true, cf, pvsFront, pvsBack, totalPvs);
-
-#if COUNT_ORIGIN_OBJECTS
-                UpdateContributionsToPvs(*ray, false, cf, pvsFront, pvsBack, totalPvs);
-#endif
-        }
     
         AxisAlignedBox3 frontBox;
@@ -1802 +1812 @@
         if (!obj) return;
 
-        const float renderCost = mViewCellsManager->EvalRenderCost(obj);
+        const float renderCost = ViewCellsManager::EvalRenderCost(obj);
 
         // object in none of the pvss => new object
@@ -1881 +1891 @@
                         backPvs += renderCost;
                 
+                        // already in front pvs => in both pvss
+                        if (leaf->Mailed())
+                                leaf->Mail(2);
+                        else
+                                leaf->Mail(1);
+                }
+        }
+}
+
+
+void VspTree::UpdateContributionsToPvs(BvhLeaf *leaf,
+                                                                           const int cf,
+                                                                           float &frontPvs,
+                                                                           float &backPvs,
+                                                                           float &totalPvs,
+                                                                           int &frontSize,
+                                                                           int &backSize,
+                                                                           int &totalSize) const
+{
+        const float renderCost = mBvHierarchy->EvalAbsCost(leaf->mObjects);
+        
+        // leaf in no pvs => new
+        if (!leaf->Mailed() && !leaf->Mailed(1) && !leaf->Mailed(2))
+        {
+                totalPvs += renderCost;
+                ++ totalSize;
+        }
+
+        if (cf >= 0) // front pvs
+        {
+                if (!leaf->Mailed() && !leaf->Mailed(2))
+                {
+                        frontPvs += renderCost;
+                        ++ frontSize;
+
+                        // 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 += renderCost;
+                        ++ backSize;
+
                         // already in front pvs => in both pvss
                         if (leaf->Mailed())
@@ -2379 +2439 @@
 
 {
-        
+
 #if HACK_PERFORMANCE
-        
-        BvhLeaf *bvhleaf = mBvHierarchy->GetLeaf(mTerminationObject);
+        Intersectable *obj = isTermination ? ray.mTerminationObject : ray.mOriginObject; 
+
+        if (!obj) return 0;
+        BvhLeaf *bvhleaf = mBvHierarchy->GetLeaf(obj);
 
         if (!bvhleaf->Mailed())
@@ -2389 +2451 @@
                 return 1;
         }
+
 #else
+
         Intersectable *obj; 
-        Vector3 pt;
+        static Vector3 pt;
         KdNode *node;
 
         ray.GetSampleData(isTermination, pt, &obj, &node);
-
+        
         if (!obj) return 0;
 
@@ -2961 +3025 @@
         Intersectable::NewMail();
 
+        ////////////////
         //-- store rays and objects
+        
+        VssRay *lastVssRay = NULL;
+
         for (rit = sampleRays.begin(); rit != rit_end; ++ rit)
         {
                 VssRay *ray = *rit;
-                float minT, maxT;
-                static Ray hray;
-
-                hray.Init(*ray);
+
+                // filter out double rays (last ray the same as this ray
+                if (!lastVssRay ||
+                        !(ray->mOrigin == lastVssRay->mTermination) ||
+                        !(ray->mTermination == lastVssRay->mOrigin)) 
+                {
+                        lastVssRay = ray;
+
+                        float minT, maxT;
+                        static Ray hray;
+
+                        hray.Init(*ray);
                 
-                // TODO: not very efficient to implictly cast between rays types
-                if (GetBoundingBox().GetRaySegment(hray, minT, maxT))
-                {
-                        float len = ray->Length();
-
-                        if (!len)
-                                len = Limits::Small;
-
-                        rays.push_back(RayInfo(ray, minT / len, maxT / len));
+                        // TODO: not very efficient to implictly cast between rays types
+                        if (GetBoundingBox().GetRaySegment(hray, minT, maxT))
+                        {
+                                const float len = ray->Length();
+
+                                if (len) // ray not degenerate 
+                                {       //len = Limits::Small;
+                                        rays.push_back(RayInfo(ray, minT / len, maxT / len));
+                                }
+                        }
+                }
+                else
+                {
+                        // store object only for one ray
+                        lastVssRay->mOriginObject = ray->mTerminationObject;
                 }
         }
@@ -3086 +3168 @@
 #if HACK_PERFORMANCE
 
+        Intersectable *obj = isTermination ? ray.mTerminationObject : ray.mOriginObject; 
+
+        if (!obj) return;
+
+        BvhLeaf *leaf = mBvHierarchy->GetLeaf(obj);
+
         SubdivisionCandidate *candidate;
-
-        BvhLeaf *leaf = mBvHierarchy->GetLeaf(ray.mTerminationObject);
 
         if (!leaf->Mailed())
@@ -3164 +3250 @@
         RayInfoContainer::const_iterator rit, rit_end = tData.mRays->end();
 
-        // add all kd nodes seen by the rays
+        // add all nodes seen by the rays
         for (rit = tData.mRays->begin(); rit != rit_end; ++ rit)
         {
@@ -3170 +3256 @@
                 
                 CollectDirtyCandidate(*ray, true, dirtyList, onlyUnmailed);
+
+#if COUNT_ORIGIN_OBJECTS
         CollectDirtyCandidate(*ray, false, dirtyList, onlyUnmailed);
-        }
-}
-
-
-int VspTree::EvalMaxEventContribution(const VssRay &ray, 
+#endif
+        }
+}
+
+
+float VspTree::EvalMaxEventContribution(const VssRay &ray, 
                                                                           const bool isTermination) const
 {
-        int pvs = 0;
-
 #if HACK_PERFORMANCE
 
-        BvhLeaf *leaf = mBvHierarchy->GetLeaf(ray.mTerminationObject);
+        Intersectable *obj = isTermination ? ray.mTerminationObject : ray.mOriginObject; 
+
+        if (!obj) return 0.0f;
+
+        BvhLeaf *leaf = mBvHierarchy->GetLeaf(obj);
                         
         // simple render cost evaluation
         if (-- leaf->mCounter == 0)
-                //pvs += (int)leaf->mObjects.size();
-                pvs += mBvHierarchy::EvalAbsCost((int)leaf->mObjects.size());
-
+                return BvHierarchy::EvalAbsCost(leaf->mObjects);
+        else
+                return 0.0f;
 #else
 
@@ -3197 +3288 @@
         ray.GetSampleData(isTermination, pt, &obj, &node);
 
-        if (!obj) return 0;
+        if (!obj) return 0.0f;
+
+        float pvs = 0.0f;
 
         switch (mHierarchyManager->GetObjectSpaceSubdivisionType())
@@ -3221 +3314 @@
                         // simple render cost evaluation
                         if (-- leaf->mCounter == 0)
-                                pvs += (int)leaf->mObjects.size();
-                                //pvs += (int)BvHierarchy::EvalAbsCost(leaf->mObjects);
+                                //pvs += (int)leaf->mObjects.size();
+                                pvs += BvHierarchy::EvalAbsCost(leaf->mObjects);
                         break;
                 }
@@ -3228 +3321 @@
                 break;
         }
+        return pvs;
+
 #endif
-        return pvs;
 }
 
@@ -3235 +3329 @@
 float VspTree::PrepareHeuristics(const VssRay &ray, const bool isTermination)
 {
+        
+#if HACK_PERFORMANCE
+        
+        Intersectable *obj = isTermination ? ray.mTerminationObject : ray.mOriginObject; 
+
+        if (!obj) return 0.0f;
+
+        BvhLeaf *leaf = mBvHierarchy->GetLeaf(obj);
+
+        if (!leaf->Mailed())
+        {
+                leaf->Mail();
+                leaf->mCounter = 1;
+                return BvHierarchy::EvalAbsCost(leaf->mObjects);
+        }
+        else
+        {
+                ++ leaf->mCounter;      
+                return 0.0f;
+        }
+
+#else
+
         float pvsSize = 0;
-        
-#if HACK_PERFORMANCE
-        BvhLeaf *leaf = mBvHierarchy->GetLeaf(ray.mTerminationObject);
-
-        if (!leaf->Mailed())
-        {
-                leaf->Mail();
-                leaf->mCounter = 0;
-                pvsSize += (int)leaf->mObjects.size();
-        }
-
-        ++ leaf->mCounter;      
-
-#else
-        
+
         Intersectable *obj;
         Vector3 pt;
@@ -3257 +3360 @@
         ray.GetSampleData(isTermination, pt, &obj, &node);
 
-        if (!obj) return 0;
+        if (!obj) return 0.0f;
 
         switch (mHierarchyManager->GetObjectSpaceSubdivisionType())
@@ -3287 +3390 @@
                                 leaf->Mail();
                                 leaf->mCounter = 0;
-                                pvsSize += (int)leaf->mObjects.size();
+                                pvsSize += BvHierarchy::EvalAbsCost(leaf->mObjects);
                         }
 
@@ -3296 +3399 @@
                 break;
         }
+        return pvsSize;
 #endif
-        return pvsSize;
-}
-
-
-int VspTree::EvalMinEventContribution(const VssRay &ray, 
-                                                                          const bool isTermination) const
+        
+}
+
+
+float VspTree::EvalMinEventContribution(const VssRay &ray, 
+                                                                                const bool isTermination) const
 {
 #if HACK_PERFORMANCE
 
-        BvhLeaf *leaf = mBvHierarchy->GetLeaf(ray.mTerminationObject);
+        Intersectable *obj = isTermination ? ray.mTerminationObject : ray.mOriginObject; 
+
+        if (!obj) return 0.0f;
+
+        BvhLeaf *leaf = mBvHierarchy->GetLeaf(obj);
         
         if (!leaf->Mailed())
         {
                 leaf->Mail();
-                pvs += (int)leaf->mObjects.size();
-        }
-
+                return BvHierarchy::EvalAbsCost(leaf->mObjects);
+        }
+        else
+        {
+                return 0.0f;
+        }
 #else
 
         Intersectable *obj;
-        Vector3 pt;
+        static Vector3 pt;
         KdNode *node;
 
@@ -3324 +3435 @@
         if (!obj) return 0;
 
-        int pvs = 0;
+        float pvs = 0.0f;
 
         switch (mHierarchyManager->GetObjectSpaceSubdivisionType())
@@ -3350 +3461 @@
                         {
                                 leaf->Mail();
-                                pvs += (int)leaf->mObjects.size();
+                                pvs += BvHierarchy->EvalAbsCost(leaf->mObjects);
                         }
                         break;
@@ -3357 +3468 @@
                 break;
         }
+        return pvs;
+
 #endif
-        return pvs;
 }
 
@@ -3377 +3489 @@
 
         Intersectable *obj;
-        Vector3 pt;
+        static Vector3 pt;
         KdNode *node;
 
@@ -3421 +3533 @@
         UpdateContributionsToPvs(leaf, cf, pvsFront, pvsBack, totalPvs, true);
 
-
 #else
 
         Intersectable *obj;
-        Vector3 pt;
+        static Vector3 pt;
         KdNode *node;
 
@@ -3443 +3554 @@
                 }
         default:
-                UpdateContributionsToPvs(obj, cf, pvsFront, pvsBack, totalPvs); 
-                break;
+                {
+                        UpdateContributionsToPvs(obj, cf, pvsFront, pvsBack, totalPvs); 
+                        break;
+                }
         }
 #endif
@@ -3450 +3563 @@
 
 
-int VspTree::EvalContributionToPvs(const VssRay &ray, const bool isTermination) const
+float VspTree::EvalContributionToPvs(const VssRay &ray, const bool isTermination) const
 {
 
 #if HACK_PERFORMANCE
-        int pvs = 0;
-
-        BvhLeaf *bvhleaf = mBvHierarchy->GetLeaf(ray.mTerminationObject);
-
-        if (!bvhleaf->Mailed())
-        {
-                bvhleaf->Mail();
-                pvs += (int)bvhleaf->mObjects.size();
+
+        Intersectable *obj = isTermination ? ray.mTerminationObject : ray.mOriginObject; 
+
+        if (!obj) return 0;
+
+        BvhLeaf *leaf = mBvHierarchy->GetLeaf(obj);
+
+        if (!leaf->Mailed())
+        {
+                leaf->Mail();
+                return BvHierarchy::EvalAbsCost(leaf->mObjects);
+        }
+        else
+        {
+                return 0.0f;
         }
 
 #else
-                
+        
         Intersectable *obj; 
-        Vector3 pt;
+        static Vector3 pt;
         KdNode *node;
 
@@ -3474 +3594 @@
         if (!obj) return 0;
 
-        int pvs = 0;
+        float pvs = 0.0f;
 
         switch (mHierarchyManager->GetObjectSpaceSubdivisionType())
@@ -3500 +3620 @@
                         {
                                 bvhleaf->Mail();
-                                pvs += (int)bvhleaf->mObjects.size();
+                                pvs += BvHierarchy::EvalAbsCost(bvhleaf->mObjects);
                         }
                         break;
@@ -3507 +3627 @@
                 break;
         }
+        return pvs;
+
 #endif
-        return pvs;
-}
-
-
-int VspTree::EvalContributionToPvs(KdLeaf *leaf) const
+}
+
+
+float VspTree::EvalContributionToPvs(KdLeaf *leaf) const
 {
         if (leaf->Mailed()) // leaf already mailed
@@ -3520 +3641 @@
 
         // this is the pvs which is uniquely part of this kd leaf
-        int pvs = (int)(leaf->mObjects.size() - leaf->mMultipleObjects.size());
+        float pvs = (float)(leaf->mObjects.size() - leaf->mMultipleObjects.size());
 
         ObjectContainer::const_iterator oit, oit_end = leaf->mMultipleObjects.end();