Changeset 1779

Timestamp:

11/22/06 10:49:09 (18 years ago)

Author:

mattausch

Message:

warning: this version contains bugs!!

Location:

GTP/trunk/Lib/Vis/Preprocessing/src

Files:

• BvHierarchy.cpp (modified) (28 diffs)
• BvHierarchy.h (modified) (9 diffs)
• Environment.cpp (modified) (1 diff)
• HierarchyManager.cpp (modified) (27 diffs)
• HierarchyManager.h (modified) (3 diffs)
• OspTree.cpp (modified) (2 diffs)
• OspTree.h (modified) (1 diff)
• Preprocessor.cpp (modified) (1 diff)
• VspTree.cpp (modified) (2 diffs)
• VspTree.h (modified) (1 diff)

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

@@ -41 +41 @@
 
 /// sorting operator
-inline static bool ilt2(Intersectable *obj1, Intersectable *obj2)
+inline static bool smallerSize(Intersectable *obj1, Intersectable *obj2)
 {
         return obj1->GetBox().SurfaceArea() < obj2->GetBox().SurfaceArea();
@@ -221 +221 @@
 BvHierarchy::BvHierarchy():
 mRoot(NULL),
-mTimeStamp(1)
+mTimeStamp(1),
+mIsInitialSubdivision(false)
 {
         ReadEnvironment();
         mSubdivisionCandidates = new SortableEntryContainer;
-        for (int i = 0; i < 4; ++ i)
-                mSortedObjects[i] = NULL;
+//      for (int i = 0; i < 4; ++ i)
+//              mSortedObjects[i] = NULL;
 }
 
@@ -236 +237 @@
 
         // delete the presorted objects
-        for (int i = 0; i < 4; ++ i)
+        /*for (int i = 0; i < 4; ++ i)
         {
                 DEL_PTR(mSortedObjects[i]);
-        }
+        }*/
         
         // delete the tree
@@ -249 +250 @@
 {
         bool randomize = false;
-        Environment::GetSingleton()->GetBoolValue("VspTree.Construction.randomize", randomize);
+        Environment::GetSingleton()->GetBoolValue("BvHierarchy.Construction.randomize", randomize);
          
         // initialise random generator for heuristics
@@ -290 +291 @@
         mSubdivisionStats.open(subdivisionStatsLog);
 
-        Environment::GetSingleton()->GetFloatValue(
-                "BvHierarchy.Construction.renderCostDecreaseWeight", mRenderCostDecreaseWeight);
-        Environment::GetSingleton()->GetBoolValue(
-                "BvHierarchy.Construction.useGlobalSorting", mUseGlobalSorting);
+        Environment::GetSingleton()->GetFloatValue("BvHierarchy.Construction.renderCostDecreaseWeight", mRenderCostDecreaseWeight);
+        Environment::GetSingleton()->GetBoolValue("BvHierarchy.Construction.useGlobalSorting", mUseGlobalSorting);
         Environment::GetSingleton()->GetIntValue("BvHierarchy.minRaysForVisibility", mMinRaysForVisibility);
         Environment::GetSingleton()->GetIntValue("BvHierarchy.maxTests", mMaxTests);
-
+        Environment::GetSingleton()->GetBoolValue("BvHierarchy.Construction.useInitialSubdivision", mApplyInitialPartition);
+        
+        mApplyInitialPartition = true;
         //mMemoryConst = (float)(sizeof(VspLeaf) + sizeof(VspViewCell));
         //mMemoryConst = (float)sizeof(BvhLeaf);
@@ -326 +327 @@
         Debug << "minimal rays for visibility: " << mMinRaysForVisibility << endl;
         Debug << "bvh mem const: " << mMemoryConst << endl;
-
+        Debug << "apply initial partition: " << mApplyInitialPartition << endl;
         Debug << endl;
 }
@@ -457 +458 @@
                                                                 const bool globalCriteriaMet)
 {
-        BvhSubdivisionCandidate *sc = dynamic_cast<BvhSubdivisionCandidate *>(splitCandidate);
+        BvhSubdivisionCandidate *sc = 
+                dynamic_cast<BvhSubdivisionCandidate *>(splitCandidate);
         BvhTraversalData &tData = sc->mParentData;
 
@@ -484 +486 @@
                 //-- push the new split candidates on the queue
                 
-                BvhSubdivisionCandidate *frontCandidate = new BvhSubdivisionCandidate(tFrontData);
-                BvhSubdivisionCandidate *backCandidate = new BvhSubdivisionCandidate(tBackData);
+                BvhSubdivisionCandidate *frontCandidate = 
+                                new BvhSubdivisionCandidate(tFrontData);
+                BvhSubdivisionCandidate *backCandidate = 
+                                new BvhSubdivisionCandidate(tBackData);
 
                 EvalSubdivisionCandidate(*frontCandidate);
@@ -519 +523 @@
 
 
+float BvHierarchy::EvalPriority(const BvhSubdivisionCandidate &splitCandidate,
+                                                                const float renderCostDecr,
+                                                                const float oldRenderCost) const
+{
+        float priority;
+
+        if (mIsInitialSubdivision)
+        {
+                priority = (float)-splitCandidate.mParentData.mDepth;
+                return priority;
+        }
+
+        BvhLeaf *leaf = splitCandidate.mParentData.mNode;
+
+        // surface area heuristics is used when there is 
+        // no view space subdivision available. 
+        // In order to have some prioritized traversal, 
+        // we use this formula instead
+        if (mHierarchyManager->GetViewSpaceSubdivisionType() == 
+                HierarchyManager::NO_VIEWSPACE_SUBDIV)
+        {
+                priority = EvalSahCost(leaf);
+        }
+        else
+        {
+                // take render cost of node into account 
+                // otherwise danger of being stuck in a local minimum!
+                const float factor = mRenderCostDecreaseWeight;
+
+                priority = factor * renderCostDecr + (1.0f - factor) * oldRenderCost;
+                
+                if (mHierarchyManager->mConsiderMemory)
+                {
+                        priority /= ((float)splitCandidate.GetPvsEntriesIncr() + mMemoryConst);
+                }
+        }
+
+        // hack: don't allow empty splits to be taken
+        if (splitCandidate.mFrontObjects.empty() || splitCandidate.mBackObjects.empty())
+                priority = 0;
+
+        return priority;
+}
+
+
 void BvHierarchy::EvalSubdivisionCandidate(BvhSubdivisionCandidate &splitCandidate, 
                                                                                    bool computeSplitPlane)
@@ -543 +592 @@
                 const int previousMisses = splitCandidate.mParentData.mMaxCostMisses;
 
-                splitCandidate.SetMaxCostMisses(maxCostRatioViolated ? previousMisses + 1 : previousMisses);
-
+                splitCandidate.SetMaxCostMisses(
+                        maxCostRatioViolated ? previousMisses + 1 : previousMisses);
         }
 
@@ -570 +619 @@
 #endif
 
-        float priority;
-
-        // surface area heuristics is used when there is 
-        // no view space subdivision available. 
-        // In order to have some prioritized traversal, 
-        // we use this formula instead
-        if (mHierarchyManager->GetViewSpaceSubdivisionType() == 
-                HierarchyManager::NO_VIEWSPACE_SUBDIV)
-        {
-                priority = EvalSahCost(leaf);
-        }
-        else
-        {
-                // take render cost of node into account 
-                // otherwise danger of being stuck in a local minimum!
-                const float factor = mRenderCostDecreaseWeight;
-
-                if (1)
-                {
-                        priority = factor * renderCostDecr + (1.0f - factor) * oldRenderCost;
-                        if (mHierarchyManager->mConsiderMemory)
-                        {
-                                priority /= ((float)splitCandidate.GetPvsEntriesIncr() + mMemoryConst);
-                        }
-                }
-                else
-                {
-                        if (!mHierarchyManager->mConsiderMemory)
-                        {
-                                priority = factor * renderCostDecr + (1.0f - factor) * oldRenderCost;
-                        }
-                        else
-                        {
-                                const float ratio = 
-                                        renderCostDecr / ((float)splitCandidate.GetPvsEntriesIncr() + mMemoryConst);
-
-                                priority = factor * ratio + (1.0f - factor) * oldRenderCost;
-                        }
-                }
-        }
-
-        // hack: don't allow empty splits to be taken
-        if (splitCandidate.mFrontObjects.empty() || splitCandidate.mBackObjects.empty())
-                priority = 0;
+        const float priority = EvalPriority(splitCandidate, 
+                                                                                oldRenderCost, 
+                                                                                renderCostDecr);
+        
         // compute global decrease in render cost
         splitCandidate.SetPriority(priority);
@@ -630 +639 @@
 
 
-inline bool BvHierarchy::LocalTerminationCriteriaMet(const BvhTraversalData &data) const
+inline bool BvHierarchy::LocalTerminationCriteriaMet(const BvhTraversalData &tData) const
 {
         const bool terminationCriteriaMet =
                         (0
-                        || ((int)data.mNode->mObjects.size() <= 1)//mTermMinObjects)
+                        || ((int)tData.mNode->mObjects.size() <= 1)//mTermMinObjects)
                         //|| (data.mProbability <= mTermMinProbability)
                         //|| (data.mNumRays <= mTermMinRays)
@@ -643 +652 @@
         {
                 cout << "bvh local termination criteria met:" << endl;
-                cout << "objects: " << data.mNode->mObjects.size() << " " << mTermMinObjects << endl;
+                cout << "objects: " << tData.mNode->mObjects.size() << " " << mTermMinObjects << endl;
         }
 #endif
@@ -1168 +1177 @@
                                                                                    ObjectContainer &objectsBack)
 {
-        ///////////////////////////////////////////////////////
-        //-- go through the lists, count the number of objects left 
-        //-- and right and evaluate the cost funcion
-
-        // prepare the heuristics by setting mailboxes and counters.
+        /////////////////////////////////////////////
+        //-- go through the lists, count the number of objects 
+        //-- left and right and evaluate the cost funcion
+
+        // prepare the heuristics by setting mailboxes and counters
         const float totalVol = PrepareHeuristics(tData, axis);
         
@@ -1183 +1192 @@
         float nObjectsRight = nTotalObjects;
 
-        const float viewSpaceVol = mViewCellsManager->GetViewSpaceBox().GetVolume();
+        const float viewSpaceVol = 
+                mViewCellsManager->GetViewSpaceBox().GetVolume();
 
         SortableEntryContainer::const_iterator backObjectsStart = 
@@ -1228 +1238 @@
                 nObjectsRight -= rc;
                 
-                const bool noValidSplit = ((nObjectsLeft <= Limits::Small) || (nObjectsRight <= Limits::Small));
+                // split is only valid if #objects on left and right is not zero
+                const bool noValidSplit = ((nObjectsLeft <= Limits::Small) || 
+                                                                   (nObjectsRight <= Limits::Small));
 
                 // the heuristics
@@ -1254 +1266 @@
         }
 
-        ////////////////////////////////////////////
+        ////////////////////////////////////////
         //-- assign object to front and back volume
 
@@ -1442 +1454 @@
                                                                                  bool useVisibilityBasedHeuristics)
 {
+        if (mIsInitialSubdivision)
+        {
+                ApplyInititialSplit(tData, 
+                                                        frontObjects, 
+                                                        backObjects);
+
+                return 0;
+        }
+        
+
         ObjectContainer nFrontObjects[3];
         ObjectContainer nBackObjects[3];
@@ -1632 +1654 @@
 
 
-float BvHierarchy::EvalSahCost(BvhLeaf *leaf)
+float BvHierarchy::EvalSahCost(BvhLeaf *leaf) const
 {
         ////////////////
@@ -2063 +2085 @@
 
 
-SubdivisionCandidate *BvHierarchy::PrepareConstruction(const VssRayContainer &sampleRays,
-                                                                                                           const ObjectContainer &objects)
+void BvHierarchy::PrepareConstruction(SplitQueue &tQueue,
+                                                                          const VssRayContainer &sampleRays,
+                                                                          const ObjectContainer &objects)
 {
         ///////////////////////////////////////
@@ -2105 +2128 @@
         if (mUseGlobalSorting)
         {
-                AssignInitialSortedObjectList(oData);
+                AssignInitialSortedObjectList(oData, objects);
         }
         
@@ -2112 +2135 @@
         //-- add first candidate for object space partition     
 
-        BvhSubdivisionCandidate *oSubdivisionCandidate = new BvhSubdivisionCandidate(oData);
+        BvhSubdivisionCandidate *oSubdivisionCandidate = 
+                new BvhSubdivisionCandidate(oData);
 
         // evaluate priority
@@ -2123 +2147 @@
         PrintSubdivisionStats(*oSubdivisionCandidate);
         
-        return oSubdivisionCandidate;
-}
-
-
-void BvHierarchy::AssignInitialSortedObjectList(BvhTraversalData &tData)
+        if (mApplyInitialPartition)
+        {
+                ApplyInitialSubdivision(oSubdivisionCandidate, tQueue);         
+        }
+        else
+        {
+                tQueue.Push(oSubdivisionCandidate);
+        }
+}
+
+
+void BvHierarchy::AssignInitialSortedObjectList(BvhTraversalData &tData,
+                                                                                                const ObjectContainer &objects)
 {
         // we sort the objects as a preprocess so they don't have
@@ -2133 +2165 @@
         for (int i = 0; i < 3; ++ i)
         {
-                // create new objects
-                if (!mSortedObjects[i])
-                {
-                        mSortedObjects[i] = new SortableEntryContainer();
-                        CreateLocalSubdivisionCandidates(tData.mNode->mObjects, &mSortedObjects[i], true, i);
-                }
-
+                SortableEntryContainer *sortedObjects = new SortableEntryContainer();
+
+                CreateLocalSubdivisionCandidates(objects, 
+                                                                             &sortedObjects, 
+                                                                                 true, 
+                                                                                 i);
+                
                 // copy list into traversal data list
                 tData.mSortedObjects[i] = new ObjectContainer();
-                tData.mSortedObjects[i]->reserve((int)mSortedObjects[i]->size());
-
-                SortableEntryContainer::const_iterator oit, oit_end = mSortedObjects[i]->end();
-
-                for (oit = mSortedObjects[i]->begin(); oit != oit_end; ++ oit)
+                tData.mSortedObjects[i]->reserve((int)objects.size());
+
+                SortableEntryContainer::const_iterator oit, oit_end = sortedObjects->end();
+
+                for (oit = sortedObjects->begin(); oit != oit_end; ++ oit)
                 {
                         tData.mSortedObjects[i]->push_back((*oit).mObject);
                 }
-        }
-
-        // create new objects
-        if (!mSortedObjects[3])
-        {
-                mSortedObjects[3] = new SortableEntryContainer();
-        }
-/*
+
+                delete sortedObjects;
+        }
+
         // last sorted list: by size
         tData.mSortedObjects[3] = new ObjectContainer();
-        tData.mSortedObjects[3]->reserve((int)mSortedObjects[i]->size());
-
-        SortableEntryContainer::const_iterator oit, oit_end = mSortedObjects[i]->end();
-
-        for (oit = mSortedObjects[3]->begin(); oit != oit_end; ++ oit)
-        {
-                tData.mSortedObjects[3]->push_back((*oit).mObject);
-        }
-*/
+        tData.mSortedObjects[3]->reserve((int)objects.size());
+
+        *(tData.mSortedObjects[3]) = objects;
+
+        stable_sort(tData.mSortedObjects[3]->begin(), tData.mSortedObjects[3]->end(), smallerSize);
 }
 
@@ -2212 +2236 @@
 
 
-SubdivisionCandidate *BvHierarchy::Reset(const VssRayContainer &sampleRays, 
-                                                                                 const ObjectContainer &objects)
+void BvHierarchy::Reset(SplitQueue &tQueue,
+                                                const VssRayContainer &sampleRays, 
+                                                const ObjectContainer &objects)
 {
         // reset stats
@@ -2243 +2268 @@
         BvhTraversalData oData(bvhLeaf, 0, prop, nRays);
 
-        AssignInitialSortedObjectList(oData);
+        AssignInitialSortedObjectList(oData, objects);
         
 
@@ -2260 +2285 @@
         PrintSubdivisionStats(*oSubdivisionCandidate);
 
-        return oSubdivisionCandidate;
+        tQueue.Push(oSubdivisionCandidate);
 }
 
@@ -2473 +2498 @@
 
 
-void BvHierarchy::InititialSubdivision(ObjectContainer &objects)
-{
-        /*std::stable_sort(objects.begin(), objects.end(), ilt2);
-        ObjectContainer::iterator oit;
-
-        stack<BvhLeaf *> tStack;
-
-        while (!tStack.empty())
-        {
-                BvhLeaf *leaf = tStack.top();
-
-                if (!InitialTerminationCriteriaMet(leaf))
-                {
-                        ChooseSplitIndex(objects, oit);
-                        SubdivideLeaf(leaf, oit);
-                }
-        }*/
-}
-
-
-void BvHierarchy::ChooseSplitIndex(const ObjectContainer &objects, 
-                                                                   ObjectContainer::const_iterator &oit)
-{
-        ObjectContainer::const_iterator oit2, oit2_end = objects.end();
+void BvHierarchy::ApplyInitialSubdivision(SubdivisionCandidate *firstCandidate,
+                                                                                  SplitQueue &tQueue)
+{
+        mIsInitialSubdivision = true;
+
+        SplitQueue tempQueue;
+
+        while (!tempQueue.Empty())
+        {
+                SubdivisionCandidate *candidate = tQueue.Top();
+                tQueue.Pop();
+
+                BvhSubdivisionCandidate *bsc = 
+                        dynamic_cast<BvhSubdivisionCandidate *>(candidate);
+
+                const bool globalCriteriaMet = 
+                        GlobalTerminationCriteriaMet(bsc->mParentData);
+
+                if (!InitialTerminationCriteriaMet(bsc->mParentData))
+                {
+                        BvhNode *node = Subdivide(tempQueue, bsc, globalCriteriaMet);
+
+                        // not needed anymore
+                        delete bsc;
+                }
+                else // initial preprocessing  finished for this candidate
+                {
+                        tQueue.Push(bsc);
+                }
+        }
+
+        mIsInitialSubdivision = false;
+}
+
+
+void BvHierarchy::ApplyInititialSplit(const BvhTraversalData &tData,
+                                                                          ObjectContainer &frontObjects,
+                                      ObjectContainer &backObjects)
+{
+        ObjectContainer *objects = tData.mSortedObjects[3];
+
+        ObjectContainer::const_iterator oit, oit_end = objects->end();
     
         float maxAreaDiff = 0.0f;
 
-        for (oit2 = objects.begin(); oit2 != (objects.end() - 1); ++ oit2)
-        {
-                Intersectable *obj = *oit2;
-                Intersectable *obj2 = *(oit2 + 1);
+        ObjectContainer::const_iterator backObjectsStart = objects->begin();
+
+    for (oit = objects->begin(); oit != (objects->end() - 1); ++ oit)
+        {
+                Intersectable *objS = *oit;
+                Intersectable *objL = *(oit + 1);
                 
                 const float areaDiff = 
-                        fabs(obj->GetBox().SurfaceArea() - obj2->GetBox().SurfaceArea());
+                        fabs(objS->GetBox().SurfaceArea() - objL->GetBox().SurfaceArea());
 
                 if (areaDiff > maxAreaDiff)
                 {
                         maxAreaDiff = areaDiff;
-                        oit = oit2;
-                }
-        }
-}
-
-
-bool BvHierarchy::InitialTerminationCriteriaMet(BvhLeaf *leaf) const
-{
-        if (((int)leaf->mObjects.size() < mInititialObjectsSize) ||
-                (leaf->mObjects.back()->GetBox().SurfaceArea() < mMinInitialSurfaceArea))
-
-        {
-                return true; 
-        }
-
-        return false;
-}
-
-
-}
+                        backObjectsStart = oit + 1;
+                }
+        }
+
+        // belongs to back bv
+        for (oit = objects->begin(); oit != backObjectsStart; ++ oit)
+        {
+                backObjects.push_back(*oit);
+        }
+
+        // belongs to front bv
+        for (oit = backObjectsStart; oit != oit_end; ++ oit)
+        {
+                frontObjects.push_back(*oit);
+        }
+}
+
+
+bool BvHierarchy::InitialTerminationCriteriaMet(const BvhTraversalData &tData) const
+{
+        return (0
+                    || ((int)tData.mNode->mObjects.size() < mInititialObjectsSize)
+                        || (tData.mNode->mObjects.back()->GetBox().SurfaceArea() < mMinInitialSurfaceArea)
+                        );
+}
+
+
+}

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

@@ -685 +685 @@
                                   ObjectContainer &objectsBack);
 
-        /** Computes priority of the traversal data and stores it in tData.
-        */
-        void EvalPriority(BvhTraversalData &tData) const;
 
         /** Evaluates render cost of the bv induced by these objects
@@ -755 +752 @@
                                                                                                  const bool sort,
                                                                                                  const int axis);
+
+        float EvalPriority(const BvhSubdivisionCandidate &splitCandidate,
+                                           const float renderCostDecr,
+                                           const float oldRenderCost) const;
 
         /** Computes object partition with the best cost according to the heurisics.
@@ -788 +789 @@
         /** Evaluates cost for a leaf given the surface area heuristics.
         */
-        float EvalSahCost(BvhLeaf *leaf);
+        float EvalSahCost(BvhLeaf *leaf) const;
 
         ////////////////////////////////////////////////
@@ -862 +863 @@
                 the first subdivision candidate.
         */
-        SubdivisionCandidate *PrepareConstruction(const VssRayContainer &sampleRays,
-                                                                                          const ObjectContainer &objects);
+        void PrepareConstruction(SplitQueue &tQueue,
+                                                         const VssRayContainer &sampleRays,
+                                                         const ObjectContainer &objects);
 
         /** Resets bv hierarchy. E.g. deletes root and resets stats.
         */
-        SubdivisionCandidate *Reset(const VssRayContainer &rays, 
-                                                                const ObjectContainer &objects);
+        void Reset(SplitQueue &tQueue,
+                           const VssRayContainer &rays, 
+                           const ObjectContainer &objects);
 
         /** Evaluates volume of view cells that see the objects.
@@ -876 +879 @@
         /** Assigns or newly creates initial list of sorted objects.
         */
-        void AssignInitialSortedObjectList(BvhTraversalData &tData);
+        void AssignInitialSortedObjectList(BvhTraversalData &tData,
+                                                                           const ObjectContainer &objects);
 
         /** Assigns sorted objects to front and back data.
@@ -890 +894 @@
 
 
-        ///////////////////////////////////
+        ////////////////////
         // initial subdivision
 
@@ -896 +900 @@
                 some criteria (size, shader)
         */
-        void InititialSubdivision(ObjectContainer &objects);
-
-        void ChooseSplitIndex(const ObjectContainer &objects, 
-                                                  ObjectContainer::const_iterator &oit);
-
-        bool InitialTerminationCriteriaMet(BvhLeaf *leaf) const;
+        void ApplyInitialSubdivision(SubdivisionCandidate *firstCandidate,
+                                                                 SplitQueue &tQueue);
+
+        void ApplyInititialSplit(const BvhTraversalData &tData,
+                                                         ObjectContainer &frontObjects,
+                                                         ObjectContainer &backObjects);
+
+        bool InitialTerminationCriteriaMet(const BvhTraversalData &tData) const;
+
         float mMinInitialSurfaceArea;
-int mInititialObjectsSize;
+        int mInititialObjectsSize;
+
 protected:
         
@@ -990 +998 @@
         bool mUseBboxAreaForSah;
 
-        SortableEntryContainer *mSortedObjects[4];
+        //SortableEntryContainer *mSortedObjects[4];
 
         int mMinRaysForVisibility;
@@ -997 +1005 @@
         float mMemoryConst;
 
+        bool mIsInitialSubdivision;
+
+        bool mApplyInitialPartition;
+
         int mMaxTests;
 };

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

@@ -2488 +2488 @@
                                         "bvh_construction_use_global_sorting=",
                                         "true");
+        
+        RegisterOption("BvHierarchy.Construction.useInitialSubdivisio",
+                                        optBool,
+                                        "bvh_construction_use_initial_subdivision=",
+                                        "false");
 
         RegisterOption("BvHierarchy.minRaysForVisibility",

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

@@ -416 +416 @@
         const int maxSteps = mMaxStepsOfSameType;
 
-        SubdivisionCandidate *osc = 
-                PrepareObjectSpaceSubdivision(sampleRays, objects);
-        objectSpaceQueue.Push(osc);
-
+        PrepareObjectSpaceSubdivision(objectSpaceQueue, sampleRays, objects);
+        
         /////////////////////////
         // calulcate initial object space splits
@@ -437 +435 @@
 
         // create view space
-        SubdivisionCandidate *vsc = PrepareViewSpaceSubdivision(sampleRays, objects);
-        viewSpaceQueue.Push(vsc);
+        PrepareViewSpaceSubdivision(viewSpaceQueue, sampleRays, objects);
 
         dirtyList.clear();
@@ -589 +586 @@
                 // prepare vsp tree for traversal
         mViewSpaceSubdivisionType = mSavedViewSpaceSubdivisionType;
-                SubdivisionCandidate *vspSc = 
-                        PrepareViewSpaceSubdivision(sampleRays, objects);
-
-                mTQueue.Push(vspSc);
+                
+                PrepareViewSpaceSubdivision(mTQueue, sampleRays, objects);
         }
         
@@ -599 +594 @@
         {
                 mObjectSpaceSubdivisionType = mSavedObjectSpaceSubdivisionType;
-                SubdivisionCandidate *ospSc =
-                        PrepareObjectSpaceSubdivision(sampleRays, objects);
-                mTQueue.Push(ospSc);
+                PrepareObjectSpaceSubdivision(mTQueue, sampleRays, objects);
         }
 
@@ -619 +612 @@
 
 
-SubdivisionCandidate *HierarchyManager::PrepareViewSpaceSubdivision(const VssRayContainer &sampleRays,
-                                                                                                                                        const ObjectContainer &objects)
+void HierarchyManager::PrepareViewSpaceSubdivision(SplitQueue &tQueue,
+                                                                                                   const VssRayContainer &sampleRays,
+                                                                                                   const ObjectContainer &objects)
 {
         cout << "\npreparing view space hierarchy construction ... " << endl;
@@ -628 +622 @@
 
         RayInfoContainer *viewSpaceRays = new RayInfoContainer();
-        SubdivisionCandidate *vsc = 
-                mVspTree->PrepareConstruction(sampleRays, *viewSpaceRays);
+        mVspTree->PrepareConstruction(tQueue, sampleRays, *viewSpaceRays);
 
         /////////
@@ -635 +628 @@
 
         mHierarchyStats.mTotalCost = mVspTree->mTotalCost;
-        
         cout << "\nreseting cost for vsp, new total cost: " << mHierarchyStats.mTotalCost << endl;
-
-        return vsc;
 }
 
@@ -669 +659 @@
 
 
-SubdivisionCandidate *HierarchyManager::PrepareObjectSpaceSubdivision(const VssRayContainer &sampleRays,
-                                                                                                                                          const ObjectContainer &objects)
+void HierarchyManager::PrepareObjectSpaceSubdivision(SplitQueue &tQueue,
+                                                                                                         const VssRayContainer &sampleRays,
+                                                                                                         const ObjectContainer &objects)
 {
         // hack: reset global cost misses
@@ -677 +668 @@
         if (mObjectSpaceSubdivisionType == KD_BASED_OBJ_SUBDIV)
         {
-                return PrepareOspTree(sampleRays, objects);
+                return PrepareOspTree(tQueue, sampleRays, objects);
         }
         else if (mObjectSpaceSubdivisionType == BV_BASED_OBJ_SUBDIV)
         {
-                return PrepareBvHierarchy(sampleRays, objects);
-        }
-        
-        return NULL;
-}
-
-
-SubdivisionCandidate *HierarchyManager::PrepareBvHierarchy(const VssRayContainer &sampleRays,
-                                                                                                                   const ObjectContainer &objects)
+                return PrepareBvHierarchy(tQueue, sampleRays, objects);
+        }
+}
+
+
+void HierarchyManager::PrepareBvHierarchy(SplitQueue &tQueue,
+                                                                                  const VssRayContainer &sampleRays,
+                                                                                  const ObjectContainer &objects)
 {
         const long startTime = GetTime();
@@ -696 +686 @@
         
         // compute first candidate
-        SubdivisionCandidate *sc =
-                mBvHierarchy->PrepareConstruction(sampleRays, objects);
+        mBvHierarchy->PrepareConstruction(tQueue, sampleRays, objects);
 
         mHierarchyStats.mTotalCost = mBvHierarchy->mTotalCost;
@@ -704 +693 @@
         cout << "finished bv hierarchy preparation in " 
                  << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
-         
-        return sc;
-}
-
-
-SubdivisionCandidate *HierarchyManager::PrepareOspTree(const VssRayContainer &sampleRays,
-                                                                                                           const ObjectContainer &objects)
+}
+
+
+void HierarchyManager::PrepareOspTree(SplitQueue &tQueue,
+                                                                          const VssRayContainer &sampleRays,
+                                                                          const ObjectContainer &objects)
 {
         cout << "starting osp tree construction ... " << endl;
@@ -720 +708 @@
 
         // compute first candidate
-        SubdivisionCandidate *osc =
-                mOspTree->PrepareConstruction(sampleRays, objects, *objectSpaceRays);
+        mOspTree->PrepareConstruction(tQueue, sampleRays, objects, *objectSpaceRays);
 
         mHierarchyStats.mTotalCost = mOspTree->mTotalCost;
         Debug << "\nreseting cost for osp, new total cost: " << mHierarchyStats.mTotalCost << endl;
-        
-    return osc;
 }
 
@@ -919 +904 @@
                                  << mHierarchyStats.mMemory / float(1024 * 1024) << " MB" << endl;
 
-                        SubdivisionCandidate *ospSc = PrepareObjectSpaceSubdivision(sampleRays, objects);
+                        PrepareObjectSpaceSubdivision(mTQueue, sampleRays, objects);
                         
                         cout << "reseting queue ... ";
                         ResetQueue(mTQueue, mRecomputeSplitPlaneOnRepair);
                         cout << "finished" << endl;
-
-                        mTQueue.Push(ospSc);
                 }
 
@@ -937 +920 @@
                                  << mHierarchyStats.mMemory / float(1024 * 1024) << " MB" << endl;
 
-                        SubdivisionCandidate *vspSc = PrepareViewSpaceSubdivision(sampleRays, objects);
+                        PrepareViewSpaceSubdivision(mTQueue, sampleRays, objects);
 
                         cout << "reseting queue ... ";
                         ResetQueue(mTQueue, mRecomputeSplitPlaneOnRepair);
                         cout << "finished" << endl;
-
-                        // push view space candidate                    
-                        mTQueue.Push(vspSc);
                 }
 
@@ -1014 +994 @@
 
 
-SubdivisionCandidate *HierarchyManager::ResetObjectSpaceSubdivision(const VssRayContainer &sampleRays, 
-                                                                                                                                        const ObjectContainer &objects)
+void HierarchyManager::ResetObjectSpaceSubdivision(SplitQueue &tQueue,
+                                                                                                   const VssRayContainer &sampleRays, 
+                                                                                                   const ObjectContainer &objects)
 {       
         SubdivisionCandidate *firstCandidate;
@@ -1034 +1015 @@
                         mBvHierarchy->Initialise(objects);
         
-                        firstCandidate = mBvHierarchy->Reset(sampleRays, objects);
+                        mBvHierarchy->Reset(tQueue, sampleRays, objects);
 
                         mHierarchyStats.mTotalCost = mBvHierarchy->mTotalCost;
@@ -1055 +1036 @@
                 // TODO
         default:
-                firstCandidate = NULL;
                 break;
         }
-
-        return firstCandidate;
-}
-
-
-SubdivisionCandidate *HierarchyManager::ResetViewSpaceSubdivision(const VssRayContainer &sampleRays, 
-                                                                                                                                  const ObjectContainer &objects,
-                                                                                                                                  AxisAlignedBox3 *forcedViewSpace)
+}
+
+
+void HierarchyManager::ResetViewSpaceSubdivision(SplitQueue &tQueue,
+                                                                                                 const VssRayContainer &sampleRays, 
+                                                                                                 const ObjectContainer &objects,
+                                                                                                 AxisAlignedBox3 *forcedViewSpace)
 {
         ViewCellsManager *vm = mVspTree->mViewCellsManager;
@@ -1078 +1057 @@
         mVspTree->Initialise(sampleRays, forcedViewSpace);
         
+        //////////
         //-- reset stats
-    mHierarchyStats.mNodes = GetObjectSpaceSubdivisionNodes();//-mVspTree->mVspStats.nodes + 1;
-        
-        SubdivisionCandidate *vsc = PrepareViewSpaceSubdivision(sampleRays, objects);
+    mHierarchyStats.mNodes = GetObjectSpaceSubdivisionNodes();
+                //-mVspTree->mVspStats.nodes + 1;
+        
+        PrepareViewSpaceSubdivision(mTQueue, sampleRays, objects);
         
         mHierarchyStats.mPvsEntries = mVspTree->mPvsEntries;
         mHierarchyStats.mRenderCostDecrease = 0;
 
-        mHierarchyStats.mMemory = (float)mHierarchyStats.mPvsEntries * ObjectPvs::GetEntrySizeByte();
+        mHierarchyStats.mMemory = 
+                (float)mHierarchyStats.mPvsEntries * ObjectPvs::GetEntrySizeByte();
 
         // evaluate new stats before first subdivsiion
         EvalSubdivisionStats();
-
-        return vsc;
 }
 
@@ -1119 +1099 @@
         mViewSpaceSubdivisionType = NO_VIEWSPACE_SUBDIV;
 
-        SubdivisionCandidate *osc = 
-                PrepareObjectSpaceSubdivision(sampleRays, objects);
-        mTQueue.Push(osc);
+        PrepareObjectSpaceSubdivision(mTQueue, sampleRays, objects);
 
         //////////////////////////
@@ -1141 +1119 @@
 
                 // subdivide object space first
-                osc = ResetObjectSpaceSubdivision(sampleRays, objects);
-                mTQueue.Push(osc);
+                ResetObjectSpaceSubdivision(mTQueue, sampleRays, objects);
 
                 // process object space candidates
@@ -1163 +1140 @@
                 // subdivide view space with respect to the objects
 
-                SubdivisionCandidate *vspVc = 
-                        ResetViewSpaceSubdivision(sampleRays, objects, forcedViewSpace);
-                mTQueue.Push(vspVc);
-
+                ResetViewSpaceSubdivision(mTQueue, sampleRays, objects, forcedViewSpace);
+                
                 // view space subdivision constructed
                 mViewSpaceSubdivisionType = mSavedViewSpaceSubdivisionType;
@@ -1229 +1204 @@
 
                 // subdivide object space first
-                SubdivisionCandidate *ospVc = 
-                        ResetObjectSpaceSubdivision(sampleRays, objects);
+                ResetObjectSpaceSubdivision(mTQueue, sampleRays, objects);
         
                 // set the number of leaves 'evaluated' from the previous methods
                 // we go for the same numbers, but we try to optimize both subdivisions
                 mBvHierarchy->mTermMaxLeaves = maxObjectSpaceLeaves;
-                mTQueue.Push(ospVc);
 
                 // process object space candidates
@@ -1252 +1225 @@
                 // subdivide view space with respect to the objects
 
-                SubdivisionCandidate *vspVc = 
-                        ResetViewSpaceSubdivision(sampleRays, objects, forcedViewSpace);
+                ResetViewSpaceSubdivision(mTQueue, sampleRays, objects, forcedViewSpace);
 
                 mVspTree->mMaxViewCells = maxViewSpaceLeaves;
-                mTQueue.Push(vspVc);
 
                 // process view space candidates
@@ -2046 +2017 @@
                                                                                    const string &filename)
 {
+#if 0
         VspTree *oldVspTree = mVspTree;
         ViewCellsManager *vm = mVspTree->mViewCellsManager;
@@ -2075 +2047 @@
         
         SubdivisionCandidate *firstVsp = mVspTree->PrepareConstruction(sampleRays, *viewSpaceRays);
-        SubdivisionCandidate *firstBvh = mBvHierarchy->PrepareConstruction(sampleRays, objects);
+        mBvHierarchy->PrepareConstruction(tQueue, sampleRays, objects);
 
     firstVsp->mEvaluationHack = oldVspRoot;
@@ -2084 +2056 @@
 
         tQueue.Push(firstVsp);
-        tQueue.Push(firstBvh);
-
+        
         ExportStats(stats, tQueue, objects);
 
@@ -2114 +2085 @@
                 mBvHierarchy->AssociateObjectsWithLeaf(*bit);
         }
+#endif
 }
 

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

@@ -304 +304 @@
                 first split candidates.
         */
-        SubdivisionCandidate *PrepareObjectSpaceSubdivision(const VssRayContainer &sampleRays,
-                                                                                                                const ObjectContainer &objects);
+        void PrepareObjectSpaceSubdivision(SplitQueue &tQueue,
+                                                                           const VssRayContainer &sampleRays,
+                                                                           const ObjectContainer &objects);
 
 
@@ -412 +413 @@
         /** Prepare bv hierarchy for subdivision
         */
-        SubdivisionCandidate *PrepareBvHierarchy(const VssRayContainer &sampleRays,
-                                                                           const ObjectContainer &objects);
+        void PrepareBvHierarchy(SplitQueue &tQueue,
+                                                        const VssRayContainer &sampleRays,
+                                                        const ObjectContainer &objects);
 
         /** Prepare object space kd tree for subdivision.
         */
-        SubdivisionCandidate *PrepareOspTree(const VssRayContainer &sampleRays,
-                                                                   const ObjectContainer &objects);
+        void PrepareOspTree(SplitQueue &tQueue,
+                                                const VssRayContainer &sampleRays,
+                                                const ObjectContainer &objects);
 
         /** Prepare view space subdivision and add candidate to queue.
         */
-        SubdivisionCandidate *PrepareViewSpaceSubdivision(const VssRayContainer &sampleRays,
-                                                                                                          const ObjectContainer &objects);
+        void PrepareViewSpaceSubdivision(SplitQueue &tQueue,
+                                                                         const VssRayContainer &sampleRays,
+                                                                         const ObjectContainer &objects);
 
         /** Was object space subdivision already constructed?
@@ -488 +492 @@
                 so construction can be restarted.
         */
-        SubdivisionCandidate *ResetObjectSpaceSubdivision(const VssRayContainer &rays, 
-                                                                                                          const ObjectContainer &objects);
-
-        SubdivisionCandidate *ResetViewSpaceSubdivision(const VssRayContainer &rays, 
-                                                                                                        const ObjectContainer &objects,
-                                                                                                        AxisAlignedBox3 *forcedViewSpace);
+        void ResetObjectSpaceSubdivision(SplitQueue &tQueue,
+                                                                         const VssRayContainer &rays, 
+                                                                         const ObjectContainer &objects);
+
+        void ResetViewSpaceSubdivision(SplitQueue &tQueue,
+                                                                   const VssRayContainer &rays, 
+                                                                   const ObjectContainer &objects,
+                                                                   AxisAlignedBox3 *forcedViewSpace);
 
 
         ///////////////////////////
 
-        void ExportStats(ofstream &stats, SplitQueue &tQueue, const ObjectContainer &objects);
+        void ExportStats(ofstream &stats, 
+                                         SplitQueue &tQueue, 
+                                         const ObjectContainer &objects);
 
         void CollectBestSet(const int maxSplits,

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

@@ -2374 +2374 @@
 
 
-SubdivisionCandidate * OspTree::PrepareConstruction(const VssRayContainer &sampleRays,
-                                                                                                        const ObjectContainer &objects,
-                                                                                                        RayInfoContainer &rays)
+void OspTree::PrepareConstruction(SplitQueue &tQueue,
+                                                                  const VssRayContainer &sampleRays,
+                                                                  const ObjectContainer &objects,
+                                                                  RayInfoContainer &rays)
 {
         // store pointer to this tree
@@ -2421 +2422 @@
         EvalSubdivisionStats(*oSubdivisionCandidate);
 
-        return oSubdivisionCandidate;
+        tQueue.Push(oSubdivisionCandidate);
 }
 

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

@@ -740 +740 @@
 
         void SubtractObjectContribution(KdLeaf *leaf,
-                                                                        Intersectable * obj,
+                                                                        Intersectable *obj,
                                                                         ViewCellContainer &touchedViewCells,
                                                                         float &renderCost);
 
-        SubdivisionCandidate *PrepareConstruction(const VssRayContainer &sampleRays,
-                                                                                          const ObjectContainer &objects,
-                                                                                          RayInfoContainer &rays);
+        void PrepareConstruction(SplitQueue &tQueue,
+                                                         const VssRayContainer &sampleRays,
+                                                         const ObjectContainer &objects,
+                             RayInfoContainer &rays);
 
 

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

@@ -883 +883 @@
                 samples.push_back(new VssRay(origin, termination, sourceObj, termObj));
         }
-
 #endif
+
         samplesIn.close();
 

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

@@ -2884 +2884 @@
 
 
-SubdivisionCandidate *VspTree::PrepareConstruction(const VssRayContainer &sampleRays,
-                                                                                                   RayInfoContainer &rays)
+void VspTree::PrepareConstruction(SplitQueue &tQueue,
+                                                                  const VssRayContainer &sampleRays,
+                                                                  RayInfoContainer &rays)
 {       
         mVspStats.Reset();
@@ -2939 +2940 @@
         EvalSubdivisionStats(*splitCandidate);
 
-        return splitCandidate;
+        tQueue.Push(splitCandidate);
 }
 

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

@@ -1010 +1010 @@
         void EvalSubdivisionStats(const SubdivisionCandidate &tData);
 
-        SubdivisionCandidate *PrepareConstruction(
-                const VssRayContainer &sampleRays,
-                RayInfoContainer &rays);
+        void PrepareConstruction(SplitQueue &tQueue,
+                                                         const VssRayContainer &sampleRays,
+                                                         RayInfoContainer &rays);
 
         /** Evaluates pvs contribution of this ray.