Changeset 1684 for GTP/trunk/Lib/Vis/Preprocessing/src

Timestamp:

10/26/06 19:35:43 (18 years ago)

Author:

mattausch

Message:

found constant for ratio

Location:

GTP/trunk/Lib/Vis/Preprocessing/src

Files:

• BvHierarchy.cpp (modified) (7 diffs)
• BvHierarchy.h (modified) (3 diffs)
• Environment.cpp (modified) (1 diff)
• HierarchyManager.cpp (modified) (21 diffs)
• HierarchyManager.h (modified) (2 diffs)
• SubdivisionCandidate.h (modified) (2 diffs)
• VspTree.cpp (modified) (1 diff)
• VspTree.h (modified) (1 diff)

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

@@ -338 +338 @@
         //AssociateObjectsWithLeaf(node->GetFront());
    
-        node->mRenderCostDecr += sc.GetRenderCostDecrease();
-        node->mPvsEntriesIncr += sc.GetPvsEntriesIncr();
-
+        node->mRenderCostDecr = sc.GetRenderCostDecrease();
+        node->mPvsEntriesIncr = sc.GetPvsEntriesIncr();
 }
                                                                         
@@ -370 +369 @@
         AxisAlignedBox3 bbox = EvalBoundingBox(sc.mBackObjects, &parentBox);
 
-        BvhLeaf *back = 
-                new BvhLeaf(bbox, node, (int)sc.mBackObjects.size());
-        BvhLeaf *front = 
-                new BvhLeaf(fbox, node, (int)sc.mFrontObjects.size());
+        BvhLeaf *back = new BvhLeaf(bbox, node, (int)sc.mBackObjects.size());
+        BvhLeaf *front = new BvhLeaf(fbox, node, (int)sc.mFrontObjects.size());
 
         BvhInterior *parent = leaf->GetParent();
@@ -428 +425 @@
         backData.mMaxCostMisses = sc.GetMaxCostMisses();
         
-        // set the time stamp so the order of traversal can be reconstructed
-        node->mTimeStamp = mHierarchyManager->mTimeStamp ++;
-        //cout << "here4 " << node->mTimeStamp << endl;
-        node->mRenderCostDecr = sc.GetRenderCostDecrease();
-        node->mPvsEntriesIncr = sc.GetPvsEntriesIncr();
+        //node->mRenderCostDecr = sc.GetRenderCostDecrease();
+        //node->mPvsEntriesIncr = sc.GetPvsEntriesIncr();
 
         // assign the objects in sorted order
@@ -465 +459 @@
                 currentNode = SubdivideNode(*sc, tFrontData, tBackData);
         
+                // set the time stamp so the order of traversal can be reconstructed
+                currentNode->mTimeStamp = mHierarchyManager->mTimeStamp ++;
+                //currentNode->mRenderCostDecr = sc.GetRenderCostDecrease();
+                //currentNode->mPvsEntriesIncr = sc.GetPvsEntriesIncr();
+
                 // decrease the weighted average cost of the subdivisoin
                 mTotalCost -= sc->GetRenderCostDecrease();
@@ -1293 +1292 @@
                                 if (useVisibilityBasedHeuristics)
                                 {
-                                        cout << "v";
+                                        //cout << "v rays: " << tData.mNumRays << " " << endl;
                                         ///////////
                                         //-- heuristics using objects weighted by view cells volume
@@ -1300 +1299 @@
                                 }
                                 else
-                                {       cout << "e";
+                                {       cout << "e rays: " << tData.mNumRays << " ";
                                         //////////////////
                                         //-- view cells not constructed yet     => use surface area heuristic                   
@@ -2124 +2123 @@
 
 
-}
+SubdivisionCandidate *BvHierarchy::CreateSubdivisionCandidate(BvhInterior *oldNode)
+{
+        return new BvhSubdivisionCandidate(BvhTraversalData());
+}
+
+
+BvhNode *BvHierarchy::SubdivideAndCopy(SplitQueue &tQueue,
+                                                                           SubdivisionCandidate *splitCandidate,
+                                                                           const bool globalCriteriaMet,
+                                                                           BvhNode *originalNode)
+{
+        BvhSubdivisionCandidate *sc = dynamic_cast<BvhSubdivisionCandidate *>(splitCandidate);
+        BvhTraversalData &tData = sc->mParentData;
+
+        BvhNode *currentNode = tData.mNode;
+        BvhNode *oldNode = (BvhNode *)splitCandidate->mEvaluationHack;
+
+        if (!oldNode->IsLeaf())
+        {       
+                //////////////
+                //-- continue subdivision
+
+                BvhTraversalData tFrontData;
+                BvhTraversalData tBackData;
+                        
+                BvhInterior *oldInterior = dynamic_cast<BvhInterior *>(oldNode);
+                //sc->SetSplitPlane(oldInterior->mSplitPlane);
+
+                oldInterior->GetFront()->CollectObjects(sc->mFrontObjects);
+                oldInterior->GetBack()->CollectObjects(sc->mBackObjects);
+                EvalSubdivisionCandidate(*sc);
+
+                // create new interior node and two leaf node
+                currentNode = SubdivideNode(*sc, tFrontData, tBackData);
+        
+                // evaluate the changes in render cost and pvs entries
+                EvalSubdivisionCandidate(*sc, false);
+
+                currentNode->mRenderCostDecr = oldNode->mRenderCostDecr + sc->GetRenderCostDecrease();
+                currentNode->mPvsEntriesIncr = oldNode->mPvsEntriesIncr + sc->GetPvsEntriesIncr();
+
+                ///////////////////////////
+                //-- push the new split candidates on the queue
+                
+                BvhSubdivisionCandidate *frontCandidate = new BvhSubdivisionCandidate(tFrontData);
+                BvhSubdivisionCandidate *backCandidate = new BvhSubdivisionCandidate(tBackData);
+
+                frontCandidate->SetPriority((float)-oldInterior->GetFront()->mTimeStamp);
+                backCandidate->SetPriority((float)-oldInterior->GetFront()->mTimeStamp);
+
+                frontCandidate->mEvaluationHack = oldInterior->GetFront();
+                backCandidate->mEvaluationHack = oldInterior->GetBack();
+
+                // cross reference
+                tFrontData.mNode->SetSubdivisionCandidate(frontCandidate); 
+                tBackData.mNode->SetSubdivisionCandidate(backCandidate);
+
+                //cout << "f: " << frontCandidate->GetPriority() << " b: " << backCandidate->GetPriority() << endl;
+                tQueue.Push(frontCandidate);
+                tQueue.Push(backCandidate);
+        }
+
+        /////////////////////////////////
+        //-- node is a leaf => terminate traversal
+
+        if (currentNode->IsLeaf())
+        {
+                // this leaf is no candidate for splitting anymore
+                // => detach subdivision candidate
+                tData.mNode->SetSubdivisionCandidate(NULL); 
+                // detach node so we don't delete it with the traversal data
+                tData.mNode = NULL;
+        }
+        
+        return currentNode;
+}
+
+
+}

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

@@ -271 +271 @@
 
         virtual void CollectObjects(ObjectContainer &objects);
+
 protected:
 
@@ -306 +307 @@
                 mSubdivisionCandidate = candidate; 
         }
-virtual void CollectObjects(ObjectContainer &objects);
+        
+        virtual void CollectObjects(ObjectContainer &objects);
+
 public:
 
@@ -597 +600 @@
         float GetMemUsage() const;
 
-void UpdateNode(const BvhSubdivisionCandidate &sc);
+
+        ///////////////////////////
+        // hacks in order to provide interleaved heurisitcs
+
+        void UpdateNode(const BvhSubdivisionCandidate &sc);
+
+        SubdivisionCandidate *CreateSubdivisionCandidate(BvhInterior *oldNode);
+
+        BvhNode *SubdivideAndCopy(SplitQueue &tQueue,
+                                                          SubdivisionCandidate *splitCandidate,
+                                                          const bool globalCriteriaMet,
+                                                          BvhNode *originalNode);
+
+        /////////////////////////////////
 
 protected:

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

@@ -2566 +2566 @@
                                         "200");
 
+        RegisterOption("Hierarchy.Construction.maxStepsOfSameType",
+                                        optInt,
+                                        "hierarchy_construction_max_steps_same_type=",
+                                        "700");
+
         RegisterOption("Hierarchy.Construction.recomputeSplitPlaneOnRepair",
                                         optBool,

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

@@ -112 +112 @@
                 "Hierarchy.Construction.minStepsOfSameType", mMinStepsOfSameType);
         
+        Environment::GetSingleton()->GetIntValue(
+                "Hierarchy.Construction.maxStepsOfSameType", mMaxStepsOfSameType);
+
         char subdivisionStatsLog[100];
         Environment::GetSingleton()->GetStringValue("Hierarchy.subdivisionStats", subdivisionStatsLog);
@@ -128 +131 @@
                 "Hierarchy.Termination.maxMemory", mTermMaxMemory);
 
-        Environment::GetSingleton()->GetFloatValue(
-                "Hierarchy.Termination.memoryConst", mMemoryConst);
+        if (1 && mConsiderMemory2)
+        {
+                mMemoryConst = (float)(sizeof(VspLeaf *) + sizeof (VspViewCell *));
+        }
+        else
+        {
+                Environment::GetSingleton()->GetFloatValue(
+                        "Hierarchy.Termination.memoryConst", mMemoryConst);
+        }
 
         // compare to bytes
@@ -147 +157 @@
         Debug << "consider memory2: " << mConsiderMemory << endl;
         Debug << "mem const: " << mMemoryConst << endl;
+        Debug << "min steps of same kind: " << mMinStepsOfSameType << endl;
+        Debug << "max steps of same kind: " << mMaxStepsOfSameType << endl;
 
         switch (mConstructionType)
@@ -377 +389 @@
         SplitQueue viewSpaceQueue;
 
+        int vspSteps, ospSteps;
+
         // use sah for evaluating osp tree construction 
         // in the first iteration of the subdivision
@@ -385 +399 @@
         // number of initial splits
         const int minSteps = mMinStepsOfSameType;
-        const int maxSteps = mMinStepsOfSameType + 500;
-        float renderCostDecr = Limits::Infinity;
+        const int maxSteps = mMaxStepsOfSameType;
 
         SubdivisionCandidate *osc = PrepareObjectSpaceSubdivision(sampleRays, objects);
-        
         objectSpaceQueue.Push(osc);
 
@@ -396 +408 @@
         // calulcate initial object space splits
         
-        SubdivisionCandidateContainer dirtyVspList;
+        SubdivisionCandidateContainer dirtyList;
 
         // subdivide object space first
         // for first round, use sah splits. Once view space partition
         // has started, use render cost heuristics instead
-        const int ospSteps = 
-                RunConstruction(objectSpaceQueue, dirtyVspList, NULL, minSteps, maxSteps);
-
+        ospSteps = RunConstruction(objectSpaceQueue, dirtyList, NULL, minSteps, maxSteps);
         cout << "\n" << ospSteps << " object space partition steps taken" << endl;
 
         // create view space
         SubdivisionCandidate *vsc = PrepareViewSpaceSubdivision(sampleRays, objects);
-
         viewSpaceQueue.Push(vsc);
-        
+
+        dirtyList.clear();
+
         // view space subdivision started
         mViewSpaceSubdivisionType = mSavedViewSpaceSubdivisionType;
 
-        // 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);
+        if (1)
+        {
+                // rather also start with 100 view space splits to avoid initial bias.
+                vspSteps = RunConstruction(viewSpaceQueue, dirtyList, NULL, minSteps, maxSteps);
+                cout << "\n" << vspSteps << " view space partition steps taken" << endl;
+                
+                /// Repair split queue
+                cout << "repairing queue ... " << endl;
+                RepairQueue(dirtyList, objectSpaceQueue, true);
+                cout << "repaired " << (int)dirtyList.size() << " candidates" << endl;
+
+                dirtyList.clear();
+        }
+        else
+        {
+                // the priorities were calculated for driving sah.
+                // => recalculate "real" priorities taking visibility into
+                // account so we can compare to view space splits
+                ResetQueue(objectSpaceQueue, false);
+        }
 
         // This method subdivides view space / object space 
@@ -424 +451 @@
         // then optimizate view space partition for the current osp
         // and vice versa until iteration depth is reached.
-bool lastSplitWasOsp = true;
+        bool lastSplitWasOsp = true;
+
         while (!(viewSpaceQueue.Empty() && objectSpaceQueue.Empty()))
         {
@@ -434 +462 @@
 
                 // should view or object space be subdivided further?
-                //if (ospPriority >= vspPriority)
-                if (!lastSplitWasOsp)
+                if (ospPriority >= vspPriority)
+                //if (!lastSplitWasOsp)
                 {
                         lastSplitWasOsp = true;
                         cout << "osp" << endl;
+                        
                         // dirtied view space candidates
                         SubdivisionCandidateContainer dirtyVspList;
@@ -445 +474 @@
                         // for first round, use sah splits. Once view space partition
                         // has started, use render cost heuristics instead
-                        const int ospSteps = RunConstruction(objectSpaceQueue, 
-                                                                                                 dirtyVspList, 
-                                                                                                 viewSpaceQueue.Top(), 
-                                                                                                 minSteps, 
-                                                                                                 maxSteps);
+                        const int ospSteps = 
+                                RunConstruction(objectSpaceQueue, dirtyVspList, viewSpaceQueue.Top(), minSteps, maxSteps);
 
                         cout << "\n" << ospSteps << " object space partition steps taken" << endl;
-                
+                        Debug << "\n" << ospSteps << " object space partition steps taken" << endl;
+
                         /// Repair split queue, i.e., affected view space candidates
                         cout << "repairing queue ... " << endl;
@@ -466 +493 @@
                         // subdivide view space with respect to the objects
 
+                        // dirtied object space candidates
                         SubdivisionCandidateContainer dirtyOspList;
 
@@ -473 +501 @@
 
                         cout << "\n" << vspSteps << " view space partition steps taken" << endl;
+                        Debug << "\n" << vspSteps << " view space partition steps taken" << endl;
 
                         // view space subdivision constructed
@@ -717 +746 @@
         {
                 memoryCount += 100000;
-                cout << "\nstorage cost: " << mHierarchyStats.mMemory / float(1024 * 1024) << " MB, steps: " << mHierarchyStats.Leaves() << endl;
+                cout << "\nstorage cost: " << mHierarchyStats.mMemory / float(1024 * 1024) 
+                         << " MB, steps: " << mHierarchyStats.Leaves() << endl;
         }
 
@@ -917 +947 @@
                 const float threshold = oldCandidate ? oldCandidate->GetPriority() : 1e20;
                 SubdivisionCandidate *sc = NextSubdivisionCandidate(splitQueue); 
-                //cout << "here2 " << sc->GetRenderCostDecrease() << " " << threshold << endl;
+                
                 float rc = (float)sc->GetRenderCostDecrease() / (mInitialRenderCost - mHierarchyStats.mTotalCost + 1.0f);
                 float mc = (float)sc->GetPvsEntriesIncr() / (float)mHierarchyStats.mPvsEntries; 
@@ -940 +970 @@
                 {
                         sc->CollectDirtyCandidates(dirtyCandidates, true);
-                        //cout << "collected " << dirtyCandidates.size() << "dirty candidates" << endl;
                         ++ steps;
                 }
@@ -1281 +1310 @@
         
 
-        /////////////////////////////////
+        ///////////////////////////
         //-- reevaluate the dirty list
 
@@ -1611 +1640 @@
 
         VspTree *oldVspTree = mVspTree;
-        //BvHierarchy *oldHierarchy = mBvHierarchy;
-
-        //mBvHierarchy = new BvHierarchy();
-        //mBvHierarchy->mHierarchyManager = this;
+        BvHierarchy *oldHierarchy = mBvHierarchy;
+
+        mBvHierarchy = new BvHierarchy();
+        mBvHierarchy->mHierarchyManager = this;
         
         mVspTree = new VspTree();
@@ -1636 +1665 @@
         cout << "Constructing view space / object space tree ... \n";
         
-        ExportStats(filename, objects, oldVspTree);
+        ExportStats(filename, objects, oldVspTree, oldHierarchy);
 
         cout << "\nfinished in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
@@ -1649 +1678 @@
 void HierarchyManager::ExportStats(const string &mergeStats,
                                                                    const ObjectContainer &objects,
-                                                                   VspTree *oldVspTree)
+                                                                   VspTree *oldVspTree,
+                                                                   BvHierarchy *oldHierarchy)
 {
         ofstream stats;
         stats.open(mergeStats.c_str());
+        SplitQueue tQueue;
+
+        BvhNode *oldBvhRoot = oldHierarchy->GetRoot();
+        VspNode *oldVspRoot = oldVspTree->GetRoot();
+
+        SubdivisionCandidate *firstVsp = mVspTree->CreateSubdivisionCandidate(dynamic_cast<VspInterior *>(oldVspRoot));
+        SubdivisionCandidate *firstBvh = mBvHierarchy->CreateSubdivisionCandidate(dynamic_cast<BvhInterior *>(oldBvhRoot));
+
 /*
         BvhQueue bvhQueue;
@@ -1674 +1712 @@
         /////////////
         //-- first view cell
-//      UpdateStats(stats, 2, totalRenderCost, entriesInPvs, memoryCost, true);
-
-
-/*
-
+        UpdateStats(stats, 2, totalRenderCost, entriesInPvs, memoryCost, true);
 
         //-- go through tree in the order of render cost decrease
@@ -1684 +1718 @@
         //-- or the reverse order of subdivision for subdivision-only 
         //-- view cell hierarchies.
-        int i = 0;
+        int steps = 0;
+        while (!tQueue.Empty())
+        {
+                SubdivisionCandidate *nextCandidate = NextSubdivisionCandidate(tQueue);
+                
+                cout << "next candidate: " << nextCandidate->GetPriority() << endl;
+                nextCandidate->Apply(tQueue, false);
+
+                totalRenderCost -= nextCandidate->GetRenderCostDecrease();
+                entriesInPvs += nextCandidate->GetPvsEntriesIncr();
+
+                ++ steps;
+                
+                const float memoryCost = (float)entriesInPvs * (float)ObjectPvs::GetEntrySize();
+                UpdateStats(stats, steps, totalRenderCost, entriesInPvs, memoryCost, false);
+
+                /*if (nextCandidate->Type() == SubdivisionCandidate::VIEW_SPACE)
+                {
+                        cout << "v";
+                        VspNode *vspNode = NULL;
+
+                        //vspNode->mParent->SetupChildLink();
+                        if (!vspNode->IsLeaf()) 
+                        {       
+                                SubdivisionCandidate sc = new VspSubdivisionCandidate();
+
+                                mVspTree->EvalPriority(sc, false);
+
+                                UpdateStats(stats, splits
+                                totalRenderCost -= vspNode->mRenderCostDecr;
+                                entriesInPvs += vspNode->mPvsEntriesIncr;               
+
+                                steps ++;
+
+                                const float memoryCost = (float)entriesInPvs * (float)ObjectPvs::GetEntrySize();        
+                                UpdateStats(stats, steps, totalRenderCost, entriesInPvs, memoryCost, true);
+
+                                VspNode *front = dynamic_cast<VspInterior *>(vspNode)->GetFront();
+                                VspNode *back= dynamic_cast<VspInterior *>(vspNode)->GetBack();
+
+                                RecreateLeaves();
+                                if (!front->IsLeaf())
+                                {
+                                SuddivisionCandidate *candidate = new SubdivisionCandidate;
+                                candidate->mParentData.mNode ? front;
+                                candidate->mParentData.mrays = 0;
+                        
+                                SuddivisionCandidate *candidate2 = new SubdivisionCandidate;
+                                candidate->mParentData.mNode = back;
+                                candidate->mParentData.mrays = 0;
+
+
+                                        vspQueue.push(front);
+                                if (!back->IsLeaf())
+                                        vspQueue.push(back);
+                                
+                        }
+                }
+                else // object space split
+                {
+                        cout << "o";
+                        
+                        BvhNode *bvhNode = NULL;
+                
+                        if (!bvhNode->IsLeaf()) 
+                        {       
+                                totalRenderCost -= bvhNode->mRenderCostDecr;
+                                entriesInPvs += bvhNode->mPvsEntriesIncr;               
+
+                                steps ++;
+                                const float memoryCost = (float)entriesInPvs * (float)ObjectPvs::GetEntrySize();        
+                                UpdateStats(stats, steps, totalRenderCost, entriesInPvs, memoryCost, false);
+                                
+                        //      BvhNode *front = dynamic_cast<BvhInterior *>(bvhNode)->GetFront();
+                        //      BvhNode *back= dynamic_cast<BvhInterior *>(bvhNode)->GetBack();
+
+                        //      if (!front->IsLeaf())
+                        //              bvhQueue.push(front);
+                        //      if (!back->IsLeaf())
+                        //              bvhQueue.push(back);
+                        }
+                }*/
+        }
+        stats.close();
+}
+
+        /*
         while (!(bvhQueue.empty() && vspQueue.empty()))
         {
@@ -1775 +1895 @@
         }
 */
-        stats.close();
-}
-
-
-}
+
+
+}

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

@@ -444 +444 @@
                                                 const string &filename);
 
-void ExportStats(const string &mergeStats, const ObjectContainer &objects, VspTree *oldVspTree);
+void ExportStats(const string &mergeStats, const ObjectContainer &objects, VspTree *oldVspTree, BvHierarchy *oldBvHierarchy);
 protected:
 
@@ -509 +509 @@
         /// number of minimal steps of the same type
         int mMinStepsOfSameType;
+        int mMaxStepsOfSameType;
 
         /// statistics about the hierarchy

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

@@ -38 +38 @@
         */
         virtual bool GlobalTerminationCriteriaMet() const = 0;
-        /** Collects #of subdivision candidates that were affected by the
+        /** Collects subdivision candidates that were affected by the
                 application of this one.
         */
@@ -117 +117 @@
         static int sReservedMailboxes;
 
+        void *mEvaluationHack;
 protected:
 

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

@@ -3321 +3321 @@
 
 
-}
+SubdivisionCandidate *VspTree::CreateSubdivisionCandidate(VspInterior *oldNode)
+{
+        return new VspSubdivisionCandidate(oldNode->GetPlane(), VspTraversalData());
+}
+
+}

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

@@ -694 +694 @@
 
         void UpdateNode(const AxisAlignedPlane &splitPlane,
-                                                         VspTraversalData &tData,
-                                                        VspTraversalData &frontData,
-                                                         VspTraversalData &backData);
+                                    VspTraversalData &tData,
+                                        VspTraversalData &frontData,
+                                        VspTraversalData &backData);
+
+        SubdivisionCandidate *CreateSubdivisionCandidate(VspInterior *oldNode);
+
 protected: