Changeset 1625

Timestamp:

10/16/06 15:11:13 (18 years ago)

Author:

mattausch

Message:

worked on gradient method

Location:

GTP/trunk/Lib/Vis/Preprocessing/src

Files:

• HierarchyManager.cpp (modified) (14 diffs)
• HierarchyManager.h (modified) (9 diffs)

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

@@ -113 +113 @@
         mSubdivisionStats.open(subdivisionStatsLog);
 
-        mMinRenderCostDecrease = -1;
+        //mMinRenderCostDecrease = -1;
 
         Debug << "******** Hierachy Manager Parameters ***********" << endl;
@@ -123 +123 @@
         Debug << "repair queue: " << mRepairQueue << endl;
         Debug << "number of multilevels: " << mNumMultiLevels << endl;
-        Debug << "min render cost " << mMinRenderCostDecrease << endl;
+        //Debug << "min render cost " << mMinRenderCostDecrease << endl;
         Debug << endl;
 }
@@ -196 +196 @@
 
 
-SubdivisionCandidate *HierarchyManager::NextSubdivisionCandidate()
-{
-        SubdivisionCandidate *splitCandidate = mTQueue.Top();
-        mTQueue.Pop();
+SubdivisionCandidate *HierarchyManager::NextSubdivisionCandidate(SplitQueue &splitQueue)
+{
+        SubdivisionCandidate *splitCandidate = splitQueue.Top();
+        splitQueue.Pop();
 
         return splitCandidate;
@@ -211 +211 @@
                                                 mHierarchyStats.mRenderCostDecrease,
                                                 mHierarchyStats.mTotalCost,
-                                                mHierarchyStats.mPvsEntries
+                                                mHierarchyStats.mPvsEntries,
+                                                mHierarchyStats.mMemory,
+                                                1.0f / (mHierarchyStats.mTotalCost * mHierarchyStats.mMemory)
                                                 );
 }
@@ -219 +221 @@
                                                                                    const float renderCostDecr,
                                                                                    const float totalRenderCost,
-                                                                                   const int pvsEntries)
+                                                                                   const int pvsEntries,
+                                                                                   const int memory,
+                                                                                   const float renderCostPerStorage)
 {
         mSubdivisionStats
@@ -225 +229 @@
                         << "#RenderCostDecrease\n" << renderCostDecr << endl 
                         << "#TotalEntriesInPvs\n" << pvsEntries << endl
-                        << "#TotalRenderCost\n" << totalRenderCost << endl;
+                        << "#TotalRenderCost\n" << totalRenderCost << endl
+                        << "#Memory\n" << memory << endl
+                        << "#RcPerMb\n" << renderCostPerStorage << endl;
 }
 
@@ -236 +242 @@
                 || (mHierarchyStats.mGlobalCostMisses >= mTermGlobalCostMissTolerance)
                 || (candidate->GlobalTerminationCriteriaMet())
-                || (mHierarchyStats.mRenderCostDecrease < mMinRenderCostDecrease)
+                //|| (mHierarchyStats.mRenderCostDecrease < mMinRenderCostDecrease)
                 );
 
@@ -270 +276 @@
                                                                                          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";
+        
+        // compute view space bounding box
+        mVspTree->ComputeBoundingBox(sampleRays, forcedViewSpace);
+
+        // use sah for evaluating osp tree construction 
+        // in the first iteration of the subdivision
+        mSavedViewSpaceSubdivisionType = mViewSpaceSubdivisionType;
+        mViewSpaceSubdivisionType = NO_VIEWSPACE_SUBDIV;
+
+        mSavedObjectSpaceSubdivisionType = mObjectSpaceSubdivisionType;
+
+        SplitQueue objectSpaceQueue;
+        SplitQueue viewSpaceQueue;
+
+        int maxSteps = 200; // number of initial splits;
+        float renderCostDecr = 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)
+        {
+                // subdivide object space first
+                // for first round, use sah splits. Once view space partition
+                // has started, use render cost heuristics instead
+                SubdivisionCandidate *osc = ResetObjectSpaceSubdivision(sampleRays, objects);
+                objectSpaceQueue.Push(osc);
+
+                // process object space candidates using 
+                // render queue for objects until slope of previous subdivision 
+                // is reached
+                SubdivisionCandidateContainer ospContainer;
+
+                const int ospSteps = RunConstruction(objectSpaceQueue, ospContainer, renderCostDecr, maxSteps);
+            cout << ospSteps << " object space partition steps taken" << endl;
+
+                // use splits of one kind until rendercost slope is reached
+                renderCostDecr = mHierarchyStats.mRenderCostDecrease;
+                
+                // object space subdivision constructed
+                mObjectSpaceSubdivisionType = mSavedObjectSpaceSubdivisionType;
+
+                /// Repair split queue
+                cout << "repairing queue ... " << endl;
+                
+                vector<SubdivisionCandidate *> dirtyList;
+
+                CollectDirtyCandidates(ospContainer, dirtyList);
+                RepairQueue(dirtyList, viewSpaceQueue);
+
+                cout << "finished repairing queue ... " << endl;
+                
+                CLEAR_CONTAINER(ospContainer);
+
+                /////////////////
+                // subdivide view space with respect to the objects
+
+                SubdivisionCandidate *vsc = ResetViewSpaceSubdivision(sampleRays, objects);
+                viewSpaceQueue.Push(vsc);
+
+                SubdivisionCandidateContainer vspContainer;
+                // process view space candidates
+                const int vspSteps = RunConstruction(viewSpaceQueue, vspContainer, renderCostDecr, maxSteps);
+
+                cout << vspSteps << " object space partition steps taken" << endl;
+
+                // view space subdivision constructed
+                mViewSpaceSubdivisionType = mSavedViewSpaceSubdivisionType;
+
+                // use splits of one kind until rendercost slope is reached
+                renderCostDecr = mHierarchyStats.mRenderCostDecrease;
+
+                /// Repair split queue
+                cout << "repairing queue ... " << endl;
+                
+                CollectDirtyCandidates(vspContainer, dirtyList);
+                RepairQueue(dirtyList, objectSpaceQueue);
+
+                cout << "finished repairing queue ... " << endl;
+
+                CLEAR_CONTAINER(vspContainer);
+        }
+        
+        cout << "\nfinished in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
+
+        mHierarchyStats.Stop();
+        mVspTree->mVspStats.Stop();
+
+        FinishObjectSpaceSubdivision(objects);
+}
+
+
+void HierarchyManager::ConstructInterleaved(const VssRayContainer &sampleRays,
+                                                                                        const ObjectContainer &objects,
+                                                                                        AxisAlignedBox3 *forcedViewSpace)
+{
+        mHierarchyStats.Reset();
+        mHierarchyStats.Start();
+        mHierarchyStats.mNodes = 2; // two nodes for view space and object space
+
+        mHierarchyStats.mTotalCost = (float)objects.size();
+        mHierarchyStats.mRenderCostDecrease = 0;
+
+        EvalSubdivisionStats();
+        Debug << "setting total cost to " << mHierarchyStats.mTotalCost << endl;
+
+        const long startTime = GetTime();
+        cout << "Constructing view space / object space tree ... \n";
+        
+        // compute view space bounding box
+        mVspTree->ComputeBoundingBox(sampleRays, forcedViewSpace);
+
+        // use objects for evaluating vsp tree construction in the first levels
+        // of the subdivision
+        mSavedObjectSpaceSubdivisionType = mObjectSpaceSubdivisionType;
+        mObjectSpaceSubdivisionType = NO_OBJ_SUBDIV;
+
+        mSavedViewSpaceSubdivisionType = mViewSpaceSubdivisionType;
+        mViewSpaceSubdivisionType = NO_VIEWSPACE_SUBDIV;
+
+        // start with view space subdivison immediately?
+        if (StartViewSpaceSubdivision())
+        {
+                // prepare vsp tree for traversal
+                mViewSpaceSubdivisionType = mSavedViewSpaceSubdivisionType;
+                PrepareViewSpaceSubdivision(sampleRays, objects);
+        }
+        
+        // start object space subdivision immediately?
+        if (StartObjectSpaceSubdivision())
+        {
+                mObjectSpaceSubdivisionType = mSavedObjectSpaceSubdivisionType;
+                PrepareObjectSpaceSubdivision(sampleRays, objects);
+        }
+
+        // begin subdivision
+        RunConstruction(mRepairQueue, sampleRays, objects, forcedViewSpace);
+        
+        cout << "\nfinished in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
+
+        mObjectSpaceSubdivisionType = mSavedObjectSpaceSubdivisionType;
+        mViewSpaceSubdivisionType = mSavedViewSpaceSubdivisionType;
+
+        mHierarchyStats.Stop();
+        mVspTree->mVspStats.Stop();
+        FinishObjectSpaceSubdivision(objects);
+}
+
+
+SubdivisionCandidate *HierarchyManager::PrepareViewSpaceSubdivision(const VssRayContainer &sampleRays,
+                                                                                                                                        const ObjectContainer &objects)
+{
+        cout << "\nstarting view space hierarchy construction ... " << endl;
+
+        // hack: reset global cost misses
+        mHierarchyStats.mGlobalCostMisses = 0;
+
+        RayInfoContainer *viewSpaceRays = new RayInfoContainer();
+        SubdivisionCandidate *vsc = 
+                mVspTree->PrepareConstruction(sampleRays, *viewSpaceRays);
+
+        mHierarchyStats.mTotalCost = mVspTree->mTotalCost;
+        cout << "\nreseting cost for vsp, new total cost: " << mHierarchyStats.mTotalCost << endl;
+
+        return vsc;
+}
+
+
+SubdivisionCandidate *HierarchyManager::PrepareObjectSpaceSubdivision(const VssRayContainer &sampleRays,
+                                                                                                                                          const ObjectContainer &objects)
+{
+        // hack: reset global cost misses
+        mHierarchyStats.mGlobalCostMisses = 0;
+
+        if (mObjectSpaceSubdivisionType == KD_BASED_OBJ_SUBDIV)
+        {
+                return PrepareOspTree(sampleRays, objects);
+        }
+        else if (mObjectSpaceSubdivisionType == BV_BASED_OBJ_SUBDIV)
+        {
+                return PrepareBvHierarchy(sampleRays, objects);
+        }
+        
+        return NULL;
+}
+
+
+SubdivisionCandidate *HierarchyManager::PrepareBvHierarchy(const VssRayContainer &sampleRays,
+                                                                                                                   const ObjectContainer &objects)
+{
+        const long startTime = GetTime();
+
+        cout << "preparing bv hierarchy construction ... " << endl;
+        
+        // compute first candidate
+        SubdivisionCandidate *sc =
+                mBvHierarchy->PrepareConstruction(sampleRays, objects);
+
+        mHierarchyStats.mTotalCost = mBvHierarchy->mTotalCost;
+        Debug << "\nreseting cost, new total cost: " << mHierarchyStats.mTotalCost << endl;
+
+        cout << "finished bv hierarchy preparation in " 
+                 << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
+         
+        return sc;
+}
+
+
+SubdivisionCandidate *HierarchyManager::PrepareOspTree(const VssRayContainer &sampleRays,
+                                                                                                           const ObjectContainer &objects)
+{
+        cout << "starting osp tree construction ... " << endl;
+
+        RayInfoContainer *objectSpaceRays = new RayInfoContainer();
+
+        // start with one big kd cell - all objects can be seen from everywhere
+        // note: only true for view space = object space
+
+        // compute first candidate
+        SubdivisionCandidate *osc =
+                mOspTree->PrepareConstruction(sampleRays, objects, *objectSpaceRays);
+
+        mHierarchyStats.mTotalCost = mOspTree->mTotalCost;
+        Debug << "\nreseting cost for osp, new total cost: " << mHierarchyStats.mTotalCost << endl;
+        
+    return osc;
+}
+
+
+bool HierarchyManager::ApplySubdivisionCandidate(SubdivisionCandidate *sc, 
+                                                                                                 SplitQueue &splitQueue,
+                                                                                                 const bool repairQueue)
+{
+        // test if global termination criteria were met before this split
+        const bool terminationCriteriaMet = GlobalTerminationCriteriaMet(sc);
+        const bool vspSplit = (sc->Type() == SubdivisionCandidate::VIEW_SPACE);
+
+        bool success = false;
+
+        switch (sc->Type())
+        {
+        case SubdivisionCandidate::VIEW_SPACE:
+                {
+                        VspNode *n = mVspTree->Subdivide(splitQueue, sc, terminationCriteriaMet);
+                        // check if termination criteria failed
+                        success = !n->IsLeaf();
+                }
+                break;
+        case SubdivisionCandidate::OBJECT_SPACE:
+                {
+                        if (mObjectSpaceSubdivisionType == KD_BASED_OBJ_SUBDIV)
+                        {
+                                KdNode *n = mOspTree->Subdivide(splitQueue, sc, terminationCriteriaMet);
+
+                                // local or global termination criteria failed
+                                success = !n->IsLeaf();
+                        }
+                        else if (mObjectSpaceSubdivisionType == BV_BASED_OBJ_SUBDIV)
+                        {
+                                BvhNode *n = mBvHierarchy->Subdivide(splitQueue, sc, terminationCriteriaMet);
+
+                                // local or global termination criteria failed
+                                success = !n->IsLeaf();                                 
+                        }
+                }
+                break;
+        default:
+                break;
+        }
+
+        if (!success) // split was not taken
+        {
+                return false;
+        }
+
+        ///////////////
+        //-- split was successful => update stats and queue
+
+    // cost ratio of cost decrease / totalCost
+        const float costRatio = sc->GetRenderCostDecrease() / mHierarchyStats.mTotalCost;
+        //Debug << "ratio: " << costRatio << " min ratio: " << mTermMinGlobalCostRatio << endl;
+        
+        if (costRatio < mTermMinGlobalCostRatio)
+        {
+                ++ mHierarchyStats.mGlobalCostMisses;
+        }
+        
+        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.mRenderCostDecrease = sc->GetRenderCostDecrease();
+
+        // subdivision successful
+        EvalSubdivisionStats();
+                
+        if (repairQueue) 
+        {
+                // reevaluate candidates affected by the split for view space splits, 
+                // this would be object space splits and other way round
+                vector<SubdivisionCandidate *> dirtyList;
+                CollectDirtyCandidates(sc, dirtyList);
+
+                RepairQueue(dirtyList, splitQueue);
+        }
+
+        return true;
+}
+
+
+int HierarchyManager::GetObjectSpaceSubdivisionDepth() const
+{
+        int maxDepth = 0;
+
+        if (mObjectSpaceSubdivisionType == KD_BASED_OBJ_SUBDIV)
+        {
+                maxDepth = mOspTree->mOspStats.maxDepth;
+        }
+        else if (mObjectSpaceSubdivisionType == BV_BASED_OBJ_SUBDIV)
+        {
+                maxDepth = mBvHierarchy->mBvhStats.maxDepth;
+        }
+
+        return maxDepth;
+}
+
+
+bool HierarchyManager::StartObjectSpaceSubdivision() const
+{
+        // view space construction already started
+        if (ObjectSpaceSubdivisionConstructed())
+                return false;
+
+        // start immediately with object space subdivision?
+        if (mStartWithObjectSpace)
+                return true;
+
+        // is the queue empty again?
+        if (ViewSpaceSubdivisionConstructed() && mTQueue.Empty())
+                return true;
+
+        // has the depth for subdivision been reached?
+        return 
+                ((mConstructionType == INTERLEAVED) && 
+                 (mMinDepthForObjectSpaceSubdivion <= mVspTree->mVspStats.maxDepth));
+}
+
+
+bool HierarchyManager::StartViewSpaceSubdivision() const
+{
+        // view space construction already started
+        if (ViewSpaceSubdivisionConstructed())
+                return false;
+
+        // start immediately with view space subdivision?
+        if (!mStartWithObjectSpace)
+                return true;
+
+        // is the queue empty again?
+        if (ObjectSpaceSubdivisionConstructed() && mTQueue.Empty())
+                return true;
+
+        // has the depth for subdivision been reached?
+        return 
+                ((mConstructionType == INTERLEAVED) && 
+                 (mMinDepthForViewSpaceSubdivion <= GetObjectSpaceSubdivisionDepth()));
+}
+
+
+void HierarchyManager::RunConstruction(const bool repairQueue,
+                                                                           const VssRayContainer &sampleRays,
+                                                                           const ObjectContainer &objects,
+                                                                           AxisAlignedBox3 *forcedViewSpace)
+{
+        while (!FinishedConstruction())
+        {
+                SubdivisionCandidate *sc = NextSubdivisionCandidate(mTQueue);    
+                        
+                ///////////////////
+                //-- subdivide leaf node
+
+                ApplySubdivisionCandidate(sc, mTQueue, repairQueue);
+                                
+                // we use objects for evaluating vsp tree construction until 
+                // a certain depth once a certain depth existiert ...
+                if (StartObjectSpaceSubdivision())
+                {
+                        mObjectSpaceSubdivisionType = mSavedObjectSpaceSubdivisionType;
+
+                        cout << "\nstarting object space subdivision at depth " 
+                                 << mVspTree->mVspStats.maxDepth << " (" 
+                                 << mMinDepthForObjectSpaceSubdivion << ") " << endl;
+
+                        PrepareObjectSpaceSubdivision(sampleRays, objects);
+
+                        cout << "reseting queue ... ";
+                        ResetQueue();
+                        cout << "finished" << endl;
+                }
+
+                if (StartViewSpaceSubdivision())
+                {
+                        mViewSpaceSubdivisionType = mSavedViewSpaceSubdivisionType;
+
+                        cout << "\nstarting view space subdivision at depth " 
+                                 << GetObjectSpaceSubdivisionDepth() << " (" 
+                                 << mMinDepthForViewSpaceSubdivion << ") " << endl;
+
+                        PrepareViewSpaceSubdivision(sampleRays, objects);
+
+                        cout << "reseting queue ... ";
+                        ResetQueue();
+                        cout << "finished" << endl;
+                }
+
+                DEL_PTR(sc);
+        }
+}
+
+
+void HierarchyManager::RunConstruction(const bool repairQueue)
+{
+        //int i = 0;
+        // main loop
+        while (!FinishedConstruction())
+        {
+                SubdivisionCandidate *sc = NextSubdivisionCandidate(mTQueue);    
+                        
+                ////////
+                //-- subdivide leaf node of either type
+
+                ApplySubdivisionCandidate(sc, mTQueue, repairQueue);
+
+                DEL_PTR(sc);
+        }
+}
+
+
+int HierarchyManager::RunConstruction(SplitQueue &splitQueue,
+                                                                          SubdivisionCandidateContainer &chosenCandidates,
+                                                                          const float minRenderCostDecr,
+                                                                          const int maxSteps)
+{
+        int steps = 0;
+
+        // main loop
+        while (!splitQueue.Empty() && ((steps ++) < maxSteps))
+        {
+                SubdivisionCandidate *sc = NextSubdivisionCandidate(splitQueue); 
+                
+                // minimum slope reached
+                if (sc->GetRenderCostDecrease() < minRenderCostDecr)
+                        break;
+
+                ////////
+                //-- subdivide leaf node of either type
+
+                const bool repairQueue = false;
+                ApplySubdivisionCandidate(sc, splitQueue, repairQueue);
+
+                chosenCandidates.push_back(sc);
+        }
+
+        return steps;
+}
+
+
+SubdivisionCandidate *HierarchyManager::ResetObjectSpaceSubdivision(const VssRayContainer &sampleRays, 
+                                                                                                                                        const ObjectContainer &objects)
+{       
+        // no object space subdivision yet
+        if (!ObjectSpaceSubdivisionConstructed())
+        {
+                return PrepareObjectSpaceSubdivision(sampleRays, objects);
+        }
+
+        SubdivisionCandidate *firstCandidate = NULL;
+
+        // object space partition constructed => reconstruct
+        switch (mObjectSpaceSubdivisionType)
+        {
+        case BV_BASED_OBJ_SUBDIV:
+                {
+                        cout << "\nreseting bv hierarchy" << endl;
+                        Debug << "old bv hierarchy:\n " << mBvHierarchy->mBvhStats << endl;
+        
+                        SubdivisionCandidate *firstCandidate = 
+                                mBvHierarchy->Reset(sampleRays, objects);
+
+                        mHierarchyStats.mTotalCost = mBvHierarchy->mTotalCost;
+
+                        mHierarchyStats.mNodes = 2;
+                        mHierarchyStats.mPvsEntries = 0;
+                        mHierarchyStats.mRenderCostDecrease = 0;
+
+                        // evaluate stats before first subdivision
+                        EvalSubdivisionStats();
+                }
+                break;
+
+        case KD_BASED_OBJ_SUBDIV:
+                // TODO
+                break;
+        default:
+                break;
+        }
+
+        return firstCandidate;
+}
+
+
+SubdivisionCandidate *HierarchyManager::ResetViewSpaceSubdivision(const VssRayContainer &sampleRays, 
+                                                                                                                                  const ObjectContainer &objects)
+{
+        ViewCellsManager *vc = mVspTree->mViewCellsManager;
+
+        // HACK: rather not destroy vsp tree
+        DEL_PTR(mVspTree);
+        mVspTree = new VspTree();
+        mVspTree->mHierarchyManager = this;
+        mVspTree->mViewCellsManager = vc;
+
+        SubdivisionCandidate *vsc = PrepareViewSpaceSubdivision(sampleRays, objects);
+        
+        mHierarchyStats.mNodes = 2;
+        mHierarchyStats.mPvsEntries = 0;
+        mHierarchyStats.mRenderCostDecrease = 0;
+
+        EvalSubdivisionStats();
+
+        return vsc;
+}
+
+
+void HierarchyManager::ConstructMultiLevel(const VssRayContainer &sampleRays,                                                                                    
+                                                                                   const ObjectContainer &objects,
+                                                                                   AxisAlignedBox3 *forcedViewSpace)
 {
         mHierarchyStats.Reset();
@@ -307 +872 @@
                 mSubdivisionStats.open(subdivisionStatsLog);
 
-                float oldRenderCost = mHierarchyStats.mRenderCostDecrease;
-                const bool isObjectSpace = true;
-
-                // subdivide object space first
-                ResetObjectSpaceSubdivision(sampleRays, objects);
-
-                // process object space candidates using 
-                // render queue for objects
-                RunConstruction(false, isObjectSpace, oldRenderCost);
-        
-                oldRenderCost = mHierarchyStats.mRenderCostDecrease;
-        
-                // object space subdivision constructed
-                mObjectSpaceSubdivisionType = mSavedObjectSpaceSubdivisionType;
-
-                cout << "iteration " << i << " of " << limit << " finished" << endl;
-
-                mSubdivisionStats.close();
-                
-                sprintf(subdivisionStatsLog, "tests/i3d/subdivision-%04d.log", i);
-                mSubdivisionStats.open(subdivisionStatsLog);
-
-                /////////////////
-                // subdivide view space with respect to the objects
-
-                ResetViewSpaceSubdivision(sampleRays, objects);
-                
-                // process view space candidates
-                RunConstruction(false, !isObjectSpace, oldRenderCost);
-
-                // view space subdivision constructed
-                mViewSpaceSubdivisionType = mSavedViewSpaceSubdivisionType;
-        
-                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);
-}
-
-
-
-void HierarchyManager::ConstructInterleaved(const VssRayContainer &sampleRays,
-                                                                                        const ObjectContainer &objects,
-                                                                                        AxisAlignedBox3 *forcedViewSpace)
-{
-        mHierarchyStats.Reset();
-        mHierarchyStats.Start();
-        mHierarchyStats.mNodes = 2; // two nodes for view space and object space
-
-        mHierarchyStats.mTotalCost = (float)objects.size();
-        mHierarchyStats.mRenderCostDecrease = 0;
-
-        EvalSubdivisionStats();
-        Debug << "setting total cost to " << mHierarchyStats.mTotalCost << endl;
-
-        const long startTime = GetTime();
-        cout << "Constructing view space / object space tree ... \n";
-        
-        // compute view space bounding box
-        mVspTree->ComputeBoundingBox(sampleRays, forcedViewSpace);
-
-        // use objects for evaluating vsp tree construction in the first levels
-        // of the subdivision
-        mSavedObjectSpaceSubdivisionType = mObjectSpaceSubdivisionType;
-        mObjectSpaceSubdivisionType = NO_OBJ_SUBDIV;
-
-        mSavedViewSpaceSubdivisionType = mViewSpaceSubdivisionType;
-        mViewSpaceSubdivisionType = NO_VIEWSPACE_SUBDIV;
-
-        // start with view space subdivison immediately?
-        if (StartViewSpaceSubdivision())
-        {
-                // prepare vsp tree for traversal
-                mViewSpaceSubdivisionType = mSavedViewSpaceSubdivisionType;
-                PrepareViewSpaceSubdivision(sampleRays, objects);
-        }
-        
-        // start object space subdivision immediately?
-        if (StartObjectSpaceSubdivision())
-        {
-                mObjectSpaceSubdivisionType = mSavedObjectSpaceSubdivisionType;
-                PrepareObjectSpaceSubdivision(sampleRays, objects);
-        }
-
-        // begin subdivision
-        RunConstruction(mRepairQueue, sampleRays, objects, forcedViewSpace);
-        
-        cout << "\nfinished in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
-
-        mObjectSpaceSubdivisionType = mSavedObjectSpaceSubdivisionType;
-        mViewSpaceSubdivisionType = mSavedViewSpaceSubdivisionType;
-
-        mHierarchyStats.Stop();
-        mVspTree->mVspStats.Stop();
-        FinishObjectSpaceSubdivision(objects);
-}
-
-
-void HierarchyManager::PrepareViewSpaceSubdivision(const VssRayContainer &sampleRays,
-                                                                                                   const ObjectContainer &objects)
-{
-        cout << "\nstarting view space hierarchy construction ... " << endl;
-        // hack: reset global cost misses
-        mHierarchyStats.mGlobalCostMisses = 0;
-        
-        RayInfoContainer *viewSpaceRays = new RayInfoContainer();
-        SubdivisionCandidate *vsc = 
-                mVspTree->PrepareConstruction(sampleRays, *viewSpaceRays);
-
-        mHierarchyStats.mTotalCost = mVspTree->mTotalCost;
-        cout << "\nreseting cost for vsp, new total cost: " << mHierarchyStats.mTotalCost << endl;
-
-        mTQueue.Push(vsc);
-}
-
-
-void HierarchyManager::PrepareObjectSpaceSubdivision(const VssRayContainer &sampleRays,
-                                                                                                         const ObjectContainer &objects)
-{
-        mHierarchyStats.mGlobalCostMisses = 0; // hack: reset global cost misses
-
-        if (mObjectSpaceSubdivisionType == KD_BASED_OBJ_SUBDIV)
-        {
-                PrepareOspTree(sampleRays, objects);
-        }
-        else if (mObjectSpaceSubdivisionType == BV_BASED_OBJ_SUBDIV)
-        {
-                PrepareBvHierarchy(sampleRays, objects);
-        }
-}
-
-
-void HierarchyManager::PrepareBvHierarchy(const VssRayContainer &sampleRays,
-                                                                                  const ObjectContainer &objects)
-{
-        const long startTime = GetTime();
-
-        cout << "preparing bv hierarchy construction ... " << endl;
-        
-        // compute first candidate
-        SubdivisionCandidate *sc =
-                mBvHierarchy->PrepareConstruction(sampleRays, objects);
-
-        mHierarchyStats.mTotalCost = mBvHierarchy->mTotalCost;
-        Debug << "\nreseting cost, new total cost: " << mHierarchyStats.mTotalCost << endl;
-
-    mTQueue.Push(sc);
-        cout << "finished bv hierarchy preparation in " 
-                 << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
-}
-
-
-void HierarchyManager::PrepareOspTree(const VssRayContainer &sampleRays,
-                                                                          const ObjectContainer &objects)
-{
-        cout << "starting osp tree construction ... " << endl;
-
-        RayInfoContainer *objectSpaceRays = new RayInfoContainer();
-
-        // start with one big kd cell - all objects can be seen from everywhere
-        // note: only true for view space = object space
-
-        // compute first candidate
-        SubdivisionCandidate *osc =
-                mOspTree->PrepareConstruction(sampleRays, objects, *objectSpaceRays);
-
-        mHierarchyStats.mTotalCost = mOspTree->mTotalCost;
-        Debug << "\nreseting cost, new total cost: " << mHierarchyStats.mTotalCost << endl;
-        
-    mTQueue.Push(osc);
-}
-
-
-bool HierarchyManager::ApplySubdivisionCandidate(SubdivisionCandidate *sc, 
-                                                                                                 const bool repairQueue)
-{
-        // test if global termination criteria were met before this split
-        const bool terminationCriteriaMet = GlobalTerminationCriteriaMet(sc);
-        const bool vspSplit = (sc->Type() == SubdivisionCandidate::VIEW_SPACE);
-
-        bool success = false;
-
-        switch (sc->Type())
-        {
-        case SubdivisionCandidate::VIEW_SPACE:
-                {
-                        VspNode *n = mVspTree->Subdivide(mTQueue, sc, terminationCriteriaMet);
-                        // check if termination criteria failed
-                        success = !n->IsLeaf();
-                }
-                break;
-        case SubdivisionCandidate::OBJECT_SPACE:
-                {
-                        if (mObjectSpaceSubdivisionType == KD_BASED_OBJ_SUBDIV)
-                        {
-                                KdNode *n = mOspTree->Subdivide(mTQueue, sc, terminationCriteriaMet);
-                                // local or global termination criteria failed
-                                success = !n->IsLeaf();
-                        }
-                        else if (mObjectSpaceSubdivisionType == BV_BASED_OBJ_SUBDIV)
-                        {
-                                BvhNode *n = mBvHierarchy->Subdivide(mTQueue, sc, terminationCriteriaMet);
-                                // local or global termination criteria failed
-                                success = !n->IsLeaf();                                 
-                        }
-                }
-                break;
-        default:
-                break;
-        }
-
-        if (!success) // split was not taken
-        {
-                return false;
-        }
-
-        ///////////////
-        //-- split was successful => update stats and queue
-
-    // cost ratio of cost decrease / totalCost
-        const float costRatio = sc->GetRenderCostDecrease() / mHierarchyStats.mTotalCost;
-        //Debug << "ratio: " << costRatio << " min ratio: " << mTermMinGlobalCostRatio << endl;
-        
-        if (costRatio < mTermMinGlobalCostRatio)
-        {
-                ++ mHierarchyStats.mGlobalCostMisses;
-        }
-        
-        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.mRenderCostDecrease = sc->GetRenderCostDecrease();
-
-        // subdivision successful
-        EvalSubdivisionStats();
-                
-        if (repairQueue) 
-        {
-                // reevaluate candidates affected by the split for view space splits, 
-                // this would be object space splits and other way round
-
-                RepairQueue(sc);
-        }
-
-        return true;
-}
-
-
-int HierarchyManager::GetObjectSpaceSubdivisionDepth() const
-{
-        int maxDepth = 0;
-
-        if (mObjectSpaceSubdivisionType == KD_BASED_OBJ_SUBDIV)
-        {
-                maxDepth = mOspTree->mOspStats.maxDepth;
-        }
-        else if (mObjectSpaceSubdivisionType == BV_BASED_OBJ_SUBDIV)
-        {
-                maxDepth = mBvHierarchy->mBvhStats.maxDepth;
-        }
-
-        return maxDepth;
-}
-
-
-bool HierarchyManager::StartObjectSpaceSubdivision() const
-{
-        // view space construction already started
-        if (ObjectSpaceSubdivisionConstructed())
-                return false;
-
-        // start immediately with object space subdivision?
-        if (mStartWithObjectSpace)
-                return true;
-
-        // is the queue empty again?
-        if (ViewSpaceSubdivisionConstructed() && mTQueue.Empty())
-                return true;
-
-        // has the depth for subdivision been reached?
-        return 
-                ((mConstructionType == INTERLEAVED) && 
-                 (mMinDepthForObjectSpaceSubdivion <= mVspTree->mVspStats.maxDepth));
-}
-
-
-bool HierarchyManager::StartViewSpaceSubdivision() const
-{
-        // view space construction already started
-        if (ViewSpaceSubdivisionConstructed())
-                return false;
-
-        // start immediately with view space subdivision?
-        if (!mStartWithObjectSpace)
-                return true;
-
-        // is the queue empty again?
-        if (ObjectSpaceSubdivisionConstructed() && mTQueue.Empty())
-                return true;
-
-        // has the depth for subdivision been reached?
-        return 
-                ((mConstructionType == INTERLEAVED) && 
-                 (mMinDepthForViewSpaceSubdivion <= GetObjectSpaceSubdivisionDepth()));
-}
-
-
-void HierarchyManager::RunConstruction(const bool repairQueue,
-                                                                           const VssRayContainer &sampleRays,
-                                                                           const ObjectContainer &objects,
-                                                                           AxisAlignedBox3 *forcedViewSpace)
-{
-        int i = 0;
-        while (!FinishedConstruction())
-        {
-                SubdivisionCandidate *sc = NextSubdivisionCandidate();    
-                        
-                ///////////////////
-                //-- subdivide leaf node
-
-                ApplySubdivisionCandidate(sc, repairQueue);
-                                
-                // we use objects for evaluating vsp tree construction until 
-                // a certain depth once a certain depth existiert ...
-                if (StartObjectSpaceSubdivision())
-                {
-                        mObjectSpaceSubdivisionType = mSavedObjectSpaceSubdivisionType;
-
-                        cout << "\nstarting object space subdivision at depth " 
-                                 << mVspTree->mVspStats.maxDepth << " (" 
-                                 << mMinDepthForObjectSpaceSubdivion << ") " << endl;
-
-                        PrepareObjectSpaceSubdivision(sampleRays, objects);
-
-                        cout << "reseting queue ... ";
-                        ResetQueue();
-                        cout << "finished" << endl;
-                }
-
-                if (StartViewSpaceSubdivision())
-                {
-                        mViewSpaceSubdivisionType = mSavedViewSpaceSubdivisionType;
-
-                        cout << "\nstarting view space subdivision at depth " 
-                                 << GetObjectSpaceSubdivisionDepth() << " (" 
-                                 << mMinDepthForViewSpaceSubdivion << ") " << endl;
-
-                        PrepareViewSpaceSubdivision(sampleRays, objects);
-
-                        cout << "reseting queue ... ";
-                        ResetQueue();
-                        cout << "finished" << endl;
-                }
-
-                DEL_PTR(sc);
-        }
-}
-
-
-void HierarchyManager::RunConstruction(const bool repairQueue)
-{
-        //int i = 0;
-        // main loop
-        while (!FinishedConstruction())
-        {
-                SubdivisionCandidate *sc = NextSubdivisionCandidate();    
-                        
-                ////////
-                //-- subdivide leaf node of either type
-                ApplySubdivisionCandidate(sc, repairQueue);
-
-                DEL_PTR(sc);
-        }
-}
-
-
-void HierarchyManager::RunConstruction(const bool isObjectSpace,
-                                                                           const float oldRenderCostDecr)
-{
-        //int i = 0;
-        // main loop
-        while (!FinishedConstruction())
-        {
-                SubdivisionCandidate *sc = NextSubdivisionCandidate();    
-                        
-                ////////
-                //-- subdivide leaf node of either type
-                ApplySubdivisionCandidate(sc, repairQueue);
-
-                DEL_PTR(sc);
-        }
-}
-
-
-void HierarchyManager::ResetObjectSpaceSubdivision(const VssRayContainer &sampleRays, 
-                                                                                                   const ObjectContainer &objects)
-                                                                                                   //const bool startFromScratch)
-{       
-        // no object space subdivision yet
-        if (!ObjectSpaceSubdivisionConstructed())
-        {
-                return PrepareObjectSpaceSubdivision(sampleRays, objects);
-        }
-
-        // object space partition constructed => reconstruct
-        switch (mObjectSpaceSubdivisionType)
-        {
-        case BV_BASED_OBJ_SUBDIV:
-                {
-                        cout << "\nreseting bv hierarchy" << endl;
-                        Debug << "old bv hierarchy:\n " << mBvHierarchy->mBvhStats << endl;
-        
-                        //if (startFromScratch)
-                        //{
-                                SubdivisionCandidate *firstCandidate = 
-                                        mBvHierarchy->Reset(sampleRays, objects);
-
-                                mTQueue.Push(firstCandidate);
-                                mHierarchyStats.mTotalCost = mBvHierarchy->mTotalCost;
-
-                                mHierarchyStats.mNodes = 2;
-                                mHierarchyStats.mPvsEntries = 0;
-                                mHierarchyStats.mRenderCostDecrease = 0;
-
-                                EvalSubdivisionStats();
-                        /*}
-                        else
-                        {
-                        }*/
-                }
-                break;
-
-        case KD_BASED_OBJ_SUBDIV:
-                // TODO
-                break;
-        default:
-                break;
-        }
-}
-
-
-void HierarchyManager::ResetViewSpaceSubdivision(const VssRayContainer &sampleRays, 
-                                                                                                 const ObjectContainer &objects)
-{
-        ViewCellsManager *vc = mVspTree->mViewCellsManager;
-
-        // HACK: rather not destroy vsp tree
-        DEL_PTR(mVspTree);
-        mVspTree = new VspTree();
-        mVspTree->mHierarchyManager = this;
-        mVspTree->mViewCellsManager = vc;
-
-        PrepareViewSpaceSubdivision(sampleRays, objects);
-        
-        mHierarchyStats.mNodes = 2;
-        mHierarchyStats.mPvsEntries = 0;
-        mHierarchyStats.mRenderCostDecrease = 0;
-
-        EvalSubdivisionStats();
-}
-
-
-void HierarchyManager::ConstructMultiLevel(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";
-        
-        // compute view space bounding box
-        mVspTree->ComputeBoundingBox(sampleRays, forcedViewSpace);
-
-        // 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
 
@@ -961 +1001 @@
 
 
-void HierarchyManager::RepairQueue(SubdivisionCandidate *sc)
+void HierarchyManager::CollectDirtyCandidates(const SubdivisionCandidateContainer &chosenCandidates, 
+                                                                                          SubdivisionCandidateContainer &dirtyList)
+{
+        SubdivisionCandidateContainer::const_iterator sit, sit_end = chosenCandidates.end();
+
+        for (sit = chosenCandidates.begin(); sit != sit_end; ++ sit)
+        {
+                // we have either a object space or view space split
+                if ((*sit)->Type() == SubdivisionCandidate::VIEW_SPACE)
+                {
+                        CollectViewSpaceDirtyList(*sit, dirtyList);
+                }
+                else // object space split
+                {
+                        CollectObjectSpaceDirtyList(*sit, dirtyList);
+                }
+        }
+}
+
+
+void HierarchyManager::RepairQueue(const vector<SubdivisionCandidate *> &dirtyList, 
+                                                                   SplitQueue &splitQueue)
 {
         // for each update of the view space partition:
@@ -981 +1042 @@
         // collect list of "dirty" candidates
         const long startTime = GetTime();
-   
-        vector<SubdivisionCandidate *> dirtyList;
-        CollectDirtyCandidates(sc, dirtyList);
-        if (0) cout << "repairing " << (int)dirtyList.size() << " candidates ... ";
+        if (0) cout << "repairing " << (int)dirtyList.size() << " candidates ... ";
         
 
@@ -997 +1055 @@
                 const float rcd = sc->GetRenderCostDecrease();
                 
-                mTQueue.Erase(sc); // erase from queue
+                splitQueue.Erase(sc); // erase from queue
                 sc->EvalPriority(); // reevaluate
                 
@@ -1005 +1063 @@
                           << " old: " << rcd << " new " << sc->GetRenderCostDecrease() << endl;
 #endif  
-                mTQueue.Push(sc); // reinsert
+                splitQueue.Push(sc); // reinsert
                 cout << ".";
         }
 
-        long endTime = GetTime();
-        Real timeDiff = TimeDiff(startTime, endTime);
+        const long endTime = GetTime();
+        const Real timeDiff = TimeDiff(startTime, endTime);
+
         mHierarchyStats.mRepairTime += timeDiff;
 
@@ -1024 +1083 @@
         while (!mTQueue.Empty())
         {
-                SubdivisionCandidate *candidate = NextSubdivisionCandidate();
-                candidate->EvalPriority(); // reevaluate
+                SubdivisionCandidate *candidate = NextSubdivisionCandidate(mTQueue);
+                 // reevaluate local split plane and priority
+                candidate->EvalPriority();
                 cout << ".";
                 mCandidateBuffer.push_back(candidate);

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

@@ -239 +239 @@
 protected:
 
+        /** Returns true if the global termination criteria were met.
+        */
         bool GlobalTerminationCriteriaMet(SubdivisionCandidate *candidate) const;
 
@@ -244 +246 @@
                 first split candidates.
         */
-        void PrepareObjectSpaceSubdivision(
-                const VssRayContainer &sampleRays,
-                const ObjectContainer &objects);
-
-        void RunConstruction(
-                const bool repairQueue,
-                const VssRayContainer &sampleRays,
-                const ObjectContainer &objects,
-                AxisAlignedBox3 *forcedViewSpace);
-        
+        SubdivisionCandidate *PrepareObjectSpaceSubdivision(const VssRayContainer &sampleRays,
+                                                                                                                const ObjectContainer &objects);
+
+
+        //////////////////////////////
+        // the main loop
+        //////////////////////
+
+        /** This is for interleaved construction / sequential construction.
+        */
+        void RunConstruction(const bool repairQueue,
+                                                 const VssRayContainer &sampleRays,
+                                                 const ObjectContainer &objects,
+                                                 AxisAlignedBox3 *forcedViewSpace);
+        
+        /** This is for interleaved construction using some objects 
+                and some view space splits.
+        */
+        int RunConstruction(SplitQueue &splitQueue,
+                                                SubdivisionCandidateContainer &chosenCandidates,
+                                                const float minRenderCostDecr,
+                                                const int maxSteps);
+
+        /** Default subdivision method.
+        */
         void RunConstruction(const bool repairQueue);
                 
+        ////////////////////////////////////////////////
+
         /** Evaluates the subdivision candidate and executes the split.
         */
-        bool ApplySubdivisionCandidate(SubdivisionCandidate *sc, const bool repairQueue);
-
+        bool ApplySubdivisionCandidate(SubdivisionCandidate *sc, 
+                                                                   SplitQueue &splitQueue,
+                                                                   const bool repairQueue);
+
+        /** Tests if hierarchy construction is finished.
+        */
         bool FinishedConstruction() const;
 
-        SubdivisionCandidate *NextSubdivisionCandidate();
-
-        /** Repairs the dirty entries of the candidate queue.
-        */
-        void RepairQueue(SubdivisionCandidate *sc);
+        /** Returns next subdivision candidate from the split queue.
+        */
+        SubdivisionCandidate *NextSubdivisionCandidate(SplitQueue &splitQueue);
+
+        /** Repairs the dirty entries of the subdivision candidate queue. The
+                list of entries is given in the dirty list.
+        */
+        void RepairQueue(const vector<SubdivisionCandidate *> &dirtyList, SplitQueue &splitQueue);
+
+        /** Collect subdivision candidates which were affected by the splits from the
+                chosenCandidates list.
+        */ 
+        void CollectDirtyCandidates(const SubdivisionCandidateContainer &chosenCandidates, 
+                                                                SubdivisionCandidateContainer &dirtyList);
 
         /** Collect the list of dirty candidates after the current 
                 subdivision candidate split.
         */
-        void CollectDirtyCandidates(
-                SubdivisionCandidate *sc,
-                vector<SubdivisionCandidate *> &dirtyList);
+        void CollectDirtyCandidates(SubdivisionCandidate *sc,
+                                                                vector<SubdivisionCandidate *> &dirtyList);
 
         /** Evaluate subdivision stats for log.
@@ -279 +310 @@
         void EvalSubdivisionStats();
 
-        void AddSubdivisionStats(
-                const int splits,
-                const float renderCostDecr,
-                const float totalRenderCost,
-                const int totalPvsEntries);
-
-        bool AddSampleToPvs(
-                Intersectable *obj, 
-                const float pdf,
-                float &contribution) const;
-
-        void CollectViewSpaceDirtyList(
-                SubdivisionCandidate *sc,
-                SubdivisionCandidateContainer &dirtyList);
-
-        void CollectObjectSpaceDirtyList(
-                SubdivisionCandidate *sc,
-                SubdivisionCandidateContainer &dirtyList);
+        void AddSubdivisionStats(const int splits,
+                                                         const float renderCostDecr,
+                                                         const float totalRenderCost,
+                                                         const int totalPvsEntries, 
+                                                         const int memory,
+                                                         const float renderCostPerStorage);
+
+        bool AddSampleToPvs(Intersectable *obj, 
+                                                const float pdf,
+                                                float &contribution) const;
+
+        /** Collect affected view space candidates.
+        */
+        void CollectViewSpaceDirtyList(SubdivisionCandidate *sc,
+                                                                   SubdivisionCandidateContainer &dirtyList);
+
+        /** Collect affected object space candidates.
+        */
+        void CollectObjectSpaceDirtyList(SubdivisionCandidate *sc,
+                                                                         SubdivisionCandidateContainer &dirtyList);
                 
-        void ExportOspTree(
-                Exporter *exporter, 
-                const ObjectContainer &objects) const;
-
+        /** Export object space partition tree.
+        */
+        void ExportOspTree(Exporter *exporter, 
+                                           const ObjectContainer &objects) const;
+
+        /** Parse the environment variables.
+        */
         void ParseEnvironment();
 
@@ -307 +343 @@
         bool StartViewSpaceSubdivision() const;
 
-        void PrepareBvHierarchy(
-                const VssRayContainer &sampleRays,
-                const ObjectContainer &objects);
-
-        void PrepareOspTree(
-                const VssRayContainer &sampleRays,
-                const ObjectContainer &objects);
-
-        void PrepareViewSpaceSubdivision(
-                const VssRayContainer &sampleRays,
-                const ObjectContainer &objects);
-
+        ////////////////////////////
+        // Helper function for preparation of subdivision
+        ///////
+
+        /** Prepare bv hierarchy for subdivision
+        */
+        SubdivisionCandidate *PrepareBvHierarchy(const VssRayContainer &sampleRays,
+                                                                           const ObjectContainer &objects);
+
+        /** Prepare object space kd tree for subdivision.
+        */
+        SubdivisionCandidate *PrepareOspTree(const VssRayContainer &sampleRays,
+                                                                   const ObjectContainer &objects);
+
+        /** Prepare view space subdivision and add candidate to queue.
+        */
+        SubdivisionCandidate *PrepareViewSpaceSubdivision(const VssRayContainer &sampleRays,
+                                                                                                          const ObjectContainer &objects);
+
+        /** Was object space subdivision already constructed?
+        */
         bool ObjectSpaceSubdivisionConstructed() const;
+        
+        /** Was view space subdivision already constructed?
+        */
         bool ViewSpaceSubdivisionConstructed() const;
 
+        /** Reset the split queue, i.e., reevaluate the split candidates.
+        */
     void ResetQueue();
 
+        /** After the suddivision has ended, do some final tasks.
+        */
         void FinishObjectSpaceSubdivision(const ObjectContainer &objects) const;
 
+        /** Returns depth of object space subdivision.
+        */
         int GetObjectSpaceSubdivisionDepth() const;
 
+        /** Construct object space partition interleaved with view space partition.
+                Each time the best object or view space candidate is selected
+                for the next split.
+        */
         void ConstructInterleaved(
                 const VssRayContainer &sampleRays,
@@ -333 +391 @@
                 AxisAlignedBox3 *forcedViewSpace);
 
+        /** Construct object space partition interleaved with view space partition.
+                The method chooses a number candidates of each type for subdivision.
+                The number is determined by the "gradient", i.e., the render cost decrease.
+                Once this render cost decrease is lower than the render cost decrease
+                for the splits of previous type, the method will stop current subdivision and
+                evaluate if view space or object space would be the beneficial for the 
+                next number of split.
+        */
         void ConstructInterleaved2(
                 const VssRayContainer &sampleRays,
@@ -349 +415 @@
                 so construction can be restarted.
         */
-        void ResetObjectSpaceSubdivision(
-                const VssRayContainer &rays, 
-                const ObjectContainer &objects);
-
-        void HierarchyManager::ResetViewSpaceSubdivision(
-                const VssRayContainer &rays, 
-                const ObjectContainer &objects);
+        SubdivisionCandidate *ResetObjectSpaceSubdivision(const VssRayContainer &rays, 
+                                                                                                          const ObjectContainer &objects);
+
+        SubdivisionCandidate *ResetViewSpaceSubdivision(const VssRayContainer &rays, 
+                                                                                                        const ObjectContainer &objects);
 
 
@@ -390 +454 @@
         /// object space partition kd tree
         OspTree *mOspTree;
+
         public:
         /// bounding volume hierarchy
@@ -409 +474 @@
         ////////////////////
 
-        /// keeps track of cost during subdivision
-        //float mTotalCost;
         /// statistics about the hierarchy
         HierarchyStatistics mHierarchyStats;
@@ -417 +480 @@
         int mMinDepthForViewSpaceSubdivion;
         
-        int mMinRenderCostDecrease;
+        //int mMinRenderCostDecrease;
 
         ofstream mSubdivisionStats;