Changeset 1640 for GTP/trunk/Lib/Vis/Preprocessing/src/HierarchyManager.cpp

Timestamp:

10/18/06 18:17:27 (18 years ago)

Author:

mattausch

Message:

worked on vsp osp methodsd

File:

• GTP/trunk/Lib/Vis/Preprocessing/src/HierarchyManager.cpp (modified) (35 diffs)

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

@@ -109 +109 @@
                 "Hierarchy.Construction.levels", mNumMultiLevels);
 
+        Environment::GetSingleton()->GetIntValue(
+                "Hierarchy.Construction.minStepsOfSameType", mMinStepsOfSameType);
+        
+
         char subdivisionStatsLog[100];
         Environment::GetSingleton()->GetStringValue("Hierarchy.subdivisionStats", subdivisionStatsLog);
@@ -116 +120 @@
                 "Hierarchy.Construction.recomputeSplitPlaneOnRepair", mRecomputeSplitPlaneOnRepair);
 
-        Debug << "******** Hierachy Manager Parameters ***********" << endl;
+        Debug << "******** Hierachy Manager Options ***********" << endl;
         Debug << "max leaves: " << mTermMaxLeaves << endl;
         Debug << "min global cost ratio: " << mTermMinGlobalCostRatio << endl;
@@ -124 +128 @@
         Debug << "number of multilevels: " << mNumMultiLevels << endl;
         Debug << "recompute split plane on repair: " << mRecomputeSplitPlaneOnRepair << endl;
+        Debug << "minimal number of steps from same type: " << mMinStepsOfSameType << endl;
 
         switch (mConstructionType)
@@ -228 +233 @@
 void HierarchyManager::EvalSubdivisionStats()
 {
+        // TODO
+        const float objectSpaceMem = GetObjectSpaceMemUsage();
+        const float viewSpaceMem = mVspTree->GetMemUsage();
+        
+        // calculate cost in MB
+        const float memoryCost = mHierarchyStats.mMemory  / (1024.0f * 1024.0f)
+                                                         + objectSpaceMem + viewSpaceMem;
+
         //cout << "pvs entries " << mHierarchyStats.pvsEntries << endl;
         AddSubdivisionStats(mHierarchyStats.Leaves(),
@@ -233 +246 @@
                                                 mHierarchyStats.mTotalCost,
                                                 mHierarchyStats.mPvsEntries,
-                                                mHierarchyStats.mMemory,
-                                                1.0f / (mHierarchyStats.mTotalCost * mHierarchyStats.mMemory)
+                                                memoryCost,
+                                                1.0f / (mHierarchyStats.mTotalCost * memoryCost)
                                                 );
 }
@@ -243 +256 @@
                                                                                    const float totalRenderCost,
                                                                                    const int pvsEntries,
-                                                                                   const int memory,
+                                                                                   const float memory,
                                                                                    const float renderCostPerStorage)
 {
@@ -309 +322 @@
         
         mHierarchyStats.mNodes = 2;
-        
+
+        // create first nodes
+        mVspTree->Initialise(sampleRays, forcedViewSpace);
+        InitialiseObjectSpaceSubdivision(objects);
+
+        // hack: assume that object space can be seen from view space
         mHierarchyStats.mTotalCost = (float)objects.size();
+        mHierarchyStats.mPvsEntries = 1;
+        mHierarchyStats.mMemory = sizeof(PvsData) + sizeof(Intersectable *) / (1024.0f * 1024.0f);
+
+        EvalSubdivisionStats();
         Debug << "setting total cost to " << mHierarchyStats.mTotalCost << endl;
 
@@ -316 +338 @@
         cout << "Constructing view space / object space tree ... \n";
         
-        // compute view space bounding box
-        mVspTree->ComputeBoundingBox(sampleRays, forcedViewSpace);
-
         SplitQueue objectSpaceQueue;
         SplitQueue viewSpaceQueue;
@@ -326 +345 @@
         mSavedViewSpaceSubdivisionType = mViewSpaceSubdivisionType;
         mViewSpaceSubdivisionType = NO_VIEWSPACE_SUBDIV;
-
-        mSavedObjectSpaceSubdivisionType = mObjectSpaceSubdivisionType;
+        //mSavedObjectSpaceSubdivisionType = mObjectSpaceSubdivisionType;
 
         // number of initial splits
-        int minSteps = 200;
+        const int minSteps = mMinStepsOfSameType;
         float renderCostDecr = Limits::Infinity;
 
@@ -337 +355 @@
         
         objectSpaceQueue.Push(osc);
+
 
         /////////////////////////
@@ -349 +368 @@
                 RunConstruction(objectSpaceQueue, dirtyVspList, renderCostDecr, minSteps);
 
-        cout << ospSteps << " object space partition steps taken" << endl;
-
+        cout << "\n" << ospSteps << " object space partition steps taken" << endl;
+
+        // create view space
         SubdivisionCandidate *vsc = 
                         PrepareViewSpaceSubdivision(sampleRays, objects);
 
         viewSpaceQueue.Push(vsc);
-
+        
         // view space subdivision was constructed
         mViewSpaceSubdivisionType = mSavedViewSpaceSubdivisionType;
 
-        // don't terminate on max steps
-        //maxSteps = mTermMaxLeaves;
+        // the priorities were calculated for driving sha.
+        // => recalculate "real" priorities taking visibility into
+        // account so we can compare to view space splits
+        ResetQueue(objectSpaceQueue, false);
+
+        
+        // lower number of minsteps: the decicion of which domain to subdivide
+        // should be decided using the render cost decrease from now
+        //minSteps = 1;
 
         // This method subdivides view space / object space 
@@ -370 +397 @@
         while (!(viewSpaceQueue.Empty() && objectSpaceQueue.Empty()))
         {
+                const float vspPriority = viewSpaceQueue.Empty() ? 0 : viewSpaceQueue.Top()->GetPriority();
+                const float ospPriority = objectSpaceQueue.Empty() ? 0 : objectSpaceQueue.Top()->GetPriority();
+
+                cout << "new decicion, vsp: " << vspPriority << ", osp: " << ospPriority << endl;
+
                 // should view or object space be subdivided further?
-                if (viewSpaceQueue.Empty() ||
-                        (!objectSpaceQueue.Empty() &&
-                        (objectSpaceQueue.Top()->GetPriority() > viewSpaceQueue.Top()->GetPriority())))
-                {
-                        // use splits of one kind until rendercost slope is reached
-                        //renderCostDecr = mHierarchyStats.mRenderCostDecrease;
-                        
-                        // lower number of minsteps: this should be solved 
-                        // with render cost decrease from now
-                        //minSteps = 5; 
-
+                if (ospPriority >= vspPriority)
+                {
+                        // use splits of one kind until rendercost decrease of other domain is reached
+                        renderCostDecr = vspPriority;
+                        cout << "comparing with this render cost: " << renderCostDecr << endl;
                         // dirtied view space candidates
                         SubdivisionCandidateContainer dirtyVspList;
@@ -391 +417 @@
                                 RunConstruction(objectSpaceQueue, dirtyVspList, renderCostDecr, minSteps);
 
-                        cout << ospSteps << " object space partition steps taken" << endl;
+                        cout << "\n" << ospSteps << " object space partition steps taken" << endl;
                 
-                        // object space subdivision constructed
-                        mObjectSpaceSubdivisionType = mSavedObjectSpaceSubdivisionType;
-
-                        /// Repair split queue
+                        /// Repair split queue, i.e., affected view space candidates
                         cout << "repairing queue ... " << endl;
                         RepairQueue(dirtyVspList, viewSpaceQueue, true);
-                        cout << "repaired " << dirtyVspList.size() << " candidates" << endl;
+                        cout << "\nrepaired " << (int)dirtyVspList.size() << " candidates" << endl;
                 }
                 else
                 {
                         // use splits of one kind until rendercost slope is reached
-                //      renderCostDecr = mHierarchyStats.mRenderCostDecrease;
+                        renderCostDecr = ospPriority;
+                        cout << "comparing with this render cost: " << renderCostDecr << endl;
 
                         /////////////////
@@ -415 +439 @@
                                 RunConstruction(viewSpaceQueue, dirtyOspList, renderCostDecr, minSteps);
 
-                        cout << vspSteps << " view space partition steps taken" << endl;
+                        cout << "\n" << vspSteps << " view space partition steps taken" << endl;
 
                         // view space subdivision constructed
@@ -423 +447 @@
                         cout << "repairing queue ... " << endl;
                         RepairQueue(dirtyOspList, objectSpaceQueue, true);
-                        cout << "repaired " << dirtyOspList.size() << " candidates" << endl;
+                        cout << "repaired " << (int)dirtyOspList.size() << " candidates" << endl;
                 }
         }
@@ -443 +467 @@
         mHierarchyStats.Start();
         mHierarchyStats.mNodes = 2; // two nodes for view space and object space
-
+        mHierarchyStats.mPvsEntries = 1;
+        mHierarchyStats.mMemory = sizeof(PvsData) + sizeof(Intersectable *) / (1024.0f * 1024.0f);
         mHierarchyStats.mTotalCost = (float)objects.size();
+
         mHierarchyStats.mRenderCostDecrease = 0;
 
@@ -453 +479 @@
         cout << "Constructing view space / object space tree ... \n";
         
-        // compute view space bounding box
-        mVspTree->ComputeBoundingBox(sampleRays, forcedViewSpace);
+        // create only roots
+        mVspTree->Initialise(sampleRays, forcedViewSpace);
+        InitialiseObjectSpaceSubdivision(objects);
 
         // use objects for evaluating vsp tree construction in the 
@@ -464 +491 @@
         mViewSpaceSubdivisionType = NO_VIEWSPACE_SUBDIV;
 
-        // create just one view cell
-        SubdivisionCandidate *vspSc = 
-                PrepareViewSpaceSubdivision(sampleRays, objects);
-
         // start view space subdivison immediately?
         if (StartViewSpaceSubdivision())
         {
                 // prepare vsp tree for traversal
-                mViewSpaceSubdivisionType = mSavedViewSpaceSubdivisionType;
+        mViewSpaceSubdivisionType = mSavedViewSpaceSubdivisionType;
+                SubdivisionCandidate *vspSc = 
+                        PrepareViewSpaceSubdivision(sampleRays, objects);
+
                 mTQueue.Push(vspSc);
         }
@@ -489 +515 @@
                                         sampleRays, 
                                         objects, 
-                                        forcedViewSpace,// 
-                                        vspSc);
+                                        forcedViewSpace);
         
         cout << "\nfinished in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
@@ -519 +544 @@
 
         return vsc;
+}
+
+
+float HierarchyManager::GetObjectSpaceMemUsage() const
+{
+        if (mObjectSpaceSubdivisionType == KD_BASED_OBJ_SUBDIV)
+        {
+                // TODO;
+        }
+        else if (mObjectSpaceSubdivisionType == BV_BASED_OBJ_SUBDIV)
+        {
+                return mBvHierarchy->GetMemUsage();
+        }
+
+        return -1;
+}
+
+void HierarchyManager::InitialiseObjectSpaceSubdivision(const ObjectContainer &objects)
+{
+        if (mObjectSpaceSubdivisionType == KD_BASED_OBJ_SUBDIV)
+        {
+                // TODO;
+        }
+        else if (mObjectSpaceSubdivisionType == BV_BASED_OBJ_SUBDIV)
+        {
+                mBvHierarchy->Initialise(objects);
+        }
 }
 
@@ -608 +660 @@
         }
         
-        mHierarchyStats.mTotalCost -= sc->GetRenderCostDecrease();
-        
         cout << sc->Type() << " ";
                 
+        /////////////
         // update stats
+
         mHierarchyStats.mNodes += 2;
-        
-        const int pvsEntries = sc->GetPvsEntriesIncr();
-        mHierarchyStats.mPvsEntries += pvsEntries;
-        
-        //cout << "pvs entries: " << pvsEntries << " " << mHierarchyStats.pvsEntries << endl;
-        mHierarchyStats.mMemory += 0; // TODO
+        mHierarchyStats.mTotalCost -= sc->GetRenderCostDecrease();
+
+        const int pvsEntriesIncr = sc->GetPvsEntriesIncr();
+        mHierarchyStats.mPvsEntries += pvsEntriesIncr;
+        //cout << "pvs entries: " << pvsEntriesIncr << " " << mHierarchyStats.pvsEntries << endl;
+
+        const int sizeOfEntry = sizeof(PvsData) + sizeof(Intersectable *);
+        // memory size in byte
+        mHierarchyStats.mMemory += float(pvsEntriesIncr * sizeOfEntry);
         mHierarchyStats.mRenderCostDecrease = sc->GetRenderCostDecrease();
 
-        // subdivision successful
+        // output stats
         EvalSubdivisionStats();
                 
@@ -656 +711 @@
 
 
+int HierarchyManager::GetObjectSpaceSubdivisionLeaves() const
+{
+        int maxLeaves= 0;
+
+        if (mObjectSpaceSubdivisionType == KD_BASED_OBJ_SUBDIV)
+        {
+                maxLeaves = mOspTree->mOspStats.Leaves();
+        }
+        else if (mObjectSpaceSubdivisionType == BV_BASED_OBJ_SUBDIV)
+        {
+                maxLeaves = mBvHierarchy->mBvhStats.Leaves();
+        }
+
+        return maxLeaves;
+}
+
+
 bool HierarchyManager::StartObjectSpaceSubdivision() const
 {
@@ -673 +745 @@
         return 
                 ((mConstructionType == INTERLEAVED) && 
-                 (mMinDepthForObjectSpaceSubdivion <= mVspTree->mVspStats.maxDepth));
+                 (mMinStepsOfSameType <= mVspTree->mVspStats.nodes));
 }
 
@@ -694 +766 @@
         return 
                 ((mConstructionType == INTERLEAVED) && 
-                 (mMinDepthForViewSpaceSubdivion <= GetObjectSpaceSubdivisionDepth()));
+                 (mMinStepsOfSameType <= GetObjectSpaceSubdivisionLeaves()));
 }
 
@@ -701 +773 @@
                                                                            const VssRayContainer &sampleRays,
                                                                            const ObjectContainer &objects,
-                                                                           AxisAlignedBox3 *forcedViewSpace,
-                                                                           SubdivisionCandidate *firstVsp)
+                                                                           AxisAlignedBox3 *forcedViewSpace)
 {
         while (!FinishedConstruction())
@@ -719 +790 @@
                         mObjectSpaceSubdivisionType = mSavedObjectSpaceSubdivisionType;
 
-                        cout << "\nstarting object space subdivision at depth " 
-                                 << mVspTree->mVspStats.maxDepth << " (" 
-                                 << mMinDepthForObjectSpaceSubdivion << ") " << endl;
+                        cout << "\nstarting object space subdivision after " 
+                                 << mVspTree->mVspStats.nodes << " (" 
+                                 << mMinStepsOfSameType << ") " << endl;
 
                         SubdivisionCandidate *ospSc = PrepareObjectSpaceSubdivision(sampleRays, objects);
+                        
+                        cout << "reseting queue ... ";
+                        ResetQueue(mTQueue, mRecomputeSplitPlaneOnRepair);
+                        cout << "finished" << endl;
+
                         mTQueue.Push(ospSc);
+                }
+
+                if (StartViewSpaceSubdivision())
+                {
+                        mViewSpaceSubdivisionType = mSavedViewSpaceSubdivisionType;
+
+                        cout << "\nstarting view space subdivision at depth " 
+                                 << GetObjectSpaceSubdivisionLeaves() << " (" 
+                                 << mMinStepsOfSameType << ") " << endl;
+
+                        SubdivisionCandidate *vspSc = PrepareViewSpaceSubdivision(sampleRays, objects);
 
                         cout << "reseting queue ... ";
-                        ResetQueue();
+                        ResetQueue(mTQueue, mRecomputeSplitPlaneOnRepair);
                         cout << "finished" << endl;
-                }
-
-                if (StartViewSpaceSubdivision())
-                {
-                        mViewSpaceSubdivisionType = mSavedViewSpaceSubdivisionType;
-
-                        cout << "\nstarting view space subdivision at depth " 
-                                 << GetObjectSpaceSubdivisionDepth() << " (" 
-                                 << mMinDepthForViewSpaceSubdivion << ") " << endl;
-
-                        //SubdivisionCandidate *vspSc = PrepareViewSpaceSubdivision(sampleRays, objects);
-                        mTQueue.Push(firstVsp);
-
-                        cout << "reseting queue ... ";
-                        ResetQueue();
-                        cout << "finished" << endl;
+
+                        // push view space candidate                    
+                        mTQueue.Push(vspSc);
                 }
 
@@ -784 +858 @@
                 if ((sc->GetRenderCostDecrease() < minRenderCostDecr) &&
                         !(steps < minSteps))
+                {
+                        cout << "breaking on " << sc->GetRenderCostDecrease() << " smaller than " << minRenderCostDecr << endl;
                         break;
-
+                }
                 ////////
                 //-- subdivide leaf node of either type
@@ -826 +902 @@
                 
                         mHierarchyStats.mTotalCost = mBvHierarchy->mTotalCost;
-
+                        
+                        // bug!! pvs entries could be much higher at this stage
                         mHierarchyStats.mNodes = 2;
-                        mHierarchyStats.mPvsEntries = 0;
+                        mHierarchyStats.mPvsEntries = 1;
                         mHierarchyStats.mRenderCostDecrease = 0;
 
@@ -861 +938 @@
         
         mHierarchyStats.mNodes = 2;
-        mHierarchyStats.mPvsEntries = 0;
+        // bug!! pvs entries could be much higher at this stage
+        mHierarchyStats.mPvsEntries = 1;
         mHierarchyStats.mRenderCostDecrease = 0;
 
+        // evaluate new stats before first subdivsiion
         EvalSubdivisionStats();
 
@@ -884 +963 @@
         cout << "Constructing view space / object space tree ... \n";
         
-        // compute view space bounding box
-        mVspTree->ComputeBoundingBox(sampleRays, forcedViewSpace);
+        // initialise view / object space
+        mVspTree->Initialise(sampleRays, forcedViewSpace);
+        InitialiseObjectSpaceSubdivision(objects);
 
         // use sah for evaluating osp tree construction 
@@ -892 +972 @@
         mSavedViewSpaceSubdivisionType = mViewSpaceSubdivisionType;
         mViewSpaceSubdivisionType = NO_VIEWSPACE_SUBDIV;
-        
-        // first view cell
-        SubdivisionCandidate *vspVc = PrepareViewSpaceSubdivision(sampleRays, objects);
 
         mSavedObjectSpaceSubdivisionType = mObjectSpaceSubdivisionType;
-        //mObjectSpaceSubdivisionType = NO_OBJ_SUBDIV;
+        mObjectSpaceSubdivisionType = NO_OBJ_SUBDIV;
 
         const int limit = mNumMultiLevels;
@@ -935 +1012 @@
                 // subdivide view space with respect to the objects
 
-                if (!ViewSpaceSubdivisionConstructed())
-                {
-                        mTQueue.Push(vspVc);
-                        
-                        // view space subdivision constructed
-                        mViewSpaceSubdivisionType = mSavedViewSpaceSubdivisionType;
-                }
-                else
-                {
-                        ResetViewSpaceSubdivision(sampleRays, objects);
-                }
+                SubdivisionCandidate *vspVc = ResetViewSpaceSubdivision(sampleRays, objects);
+                mTQueue.Push(vspVc);
+
+                // view space subdivision constructed
+                mViewSpaceSubdivisionType = mSavedViewSpaceSubdivisionType;
+                
 
                 // process view space candidates
@@ -969 +1041 @@
         FinishObjectSpaceSubdivision(objects);
 }
+
+
+void HierarchyManager::OptimizeMultiLevel(const VssRayContainer &sampleRays,                                                                                     
+                                                                                  const ObjectContainer &objects,
+                                                                                  AxisAlignedBox3 *forcedViewSpace)
+{
+        mHierarchyStats.Reset();
+        mHierarchyStats.Start();
+        mHierarchyStats.mNodes = 2;
+        
+        mHierarchyStats.mTotalCost = (float)objects.size();
+        Debug << "setting total cost to " << mHierarchyStats.mTotalCost << endl;
+
+        const long startTime = GetTime();
+        cout << "Constructing view space / object space tree ... \n";
+        
+        // initialise view / object space
+        mVspTree->Initialise(sampleRays, forcedViewSpace);
+        InitialiseObjectSpaceSubdivision(objects);
+
+        // use sah for evaluating osp tree construction 
+        // in the first iteration of the subdivision
+        
+        mSavedViewSpaceSubdivisionType = mViewSpaceSubdivisionType;
+        mViewSpaceSubdivisionType = NO_VIEWSPACE_SUBDIV;
+
+        mSavedObjectSpaceSubdivisionType = mObjectSpaceSubdivisionType;
+        mObjectSpaceSubdivisionType = NO_OBJ_SUBDIV;
+
+        const int limit = mNumMultiLevels;
+        int i = 0;
+
+        // This method subdivides view space / object space 
+        // in order to converge to some optimal cost for this partition
+        // start with object space partiton
+        // then optimizate view space partition for the current osp
+        // and vice versa until iteration depth is reached.
+        while (1)
+        {
+                char subdivisionStatsLog[100];
+                sprintf(subdivisionStatsLog, "tests/i3d/subdivision-%04d.log", i);
+                mSubdivisionStats.open(subdivisionStatsLog);
+
+                // subdivide object space first
+                ResetObjectSpaceSubdivision(sampleRays, objects);
+
+                // process object space candidates
+                RunConstruction(false);
+
+                // object space subdivision constructed
+                mObjectSpaceSubdivisionType = mSavedObjectSpaceSubdivisionType;
+
+                cout << "iteration " << i << " of " << limit << " finished" << endl;
+
+                mSubdivisionStats.close();
+
+                if ((i ++) >= limit)
+                        break;
+
+                sprintf(subdivisionStatsLog, "tests/i3d/subdivision-%04d.log", i);
+                mSubdivisionStats.open(subdivisionStatsLog);
+
+                /////////////////
+                // subdivide view space with respect to the objects
+
+                SubdivisionCandidate *vspVc = ResetViewSpaceSubdivision(sampleRays, objects);
+                mTQueue.Push(vspVc);
+
+                // view space subdivision constructed
+                mViewSpaceSubdivisionType = mSavedViewSpaceSubdivisionType;
+                
+
+                // process view space candidates
+                RunConstruction(false);
+
+                cout << "iteration " << i << " of " << limit << " finished" << endl;
+
+                mSubdivisionStats.close();
+
+                if ((i ++) >= limit)
+                        break;
+        }
+        
+        cout << "\nfinished in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
+
+/*#if _DEBUG
+        cout << "view space: " << GetViewSpaceBox() << endl;
+        cout << "object space:  " << GetObjectSpaceBox() << endl;
+#endif*/
+
+        mHierarchyStats.Stop();
+        mVspTree->mVspStats.Stop();
+        FinishObjectSpaceSubdivision(objects);
+}
+
 
 
@@ -1067 +1234 @@
 
 
-void HierarchyManager::ResetQueue()
+void HierarchyManager::ResetQueue(SplitQueue &splitQueue, const bool recomputeSplitPlane)
 {
         SubdivisionCandidateContainer mCandidateBuffer;
 
         // remove from queue
-        while (!mTQueue.Empty())
-        {
-                SubdivisionCandidate *candidate = NextSubdivisionCandidate(mTQueue);
+        while (!splitQueue.Empty())
+        {
+                SubdivisionCandidate *candidate = NextSubdivisionCandidate(splitQueue);
                  // reevaluate local split plane and priority
-                candidate->EvalPriority();
+                candidate->EvalPriority(recomputeSplitPlane);
                 cout << ".";
                 mCandidateBuffer.push_back(candidate);
@@ -1085 +1252 @@
     for (sit = mCandidateBuffer.begin(); sit != sit_end; ++ sit)
         {
-                mTQueue.Push(*sit);
+                splitQueue.Push(*sit);
         }
 }