Changeset 564 for trunk/VUT/GtpVisibilityPreprocessor/src/VspBspTree.cpp

Timestamp:

01/23/06 02:56:48 (18 years ago)

Author:

mattausch

Message:

 

File:

• trunk/VUT/GtpVisibilityPreprocessor/src/VspBspTree.cpp (modified) (30 diffs)

trunk/VUT/GtpVisibilityPreprocessor/src/VspBspTree.cpp

@@ -30 +30 @@
 
 int BspMergeCandidate::sMaxPvsSize = 0;
+//int BspMergeCandidate::sMinPvsSize = 0;
 
 int VspBspTree::sFrontId = 0;
@@ -66 +67 @@
         environment->GetFloatValue("VspBspTree.Termination.maxCostRatio", mTermMaxCostRatio);
         environment->GetIntValue("VspBspTree.Termination.missTolerance", mTermMissTolerance);
+        environment->GetIntValue("VspBspTree.Termination.maxViewCells", mMaxViewCells);
+        //-- max cost ratio for early tree termination
+        environment->GetFloatValue("VspBspTree.Termination.maxCostRatio", mTermMaxCostRatio);
 
         //-- factors for bsp tree split plane heuristics
@@ -72 +76 @@
         environment->GetFloatValue("VspBspTree.Termination.ct_div_ci", mCtDivCi);
 
-        //-- max cost ratio for early tree termination
-        environment->GetFloatValue("VspBspTree.Termination.maxCostRatio", mTermMaxCostRatio);
 
         //-- partition criteria
@@ -83 +85 @@
         environment->GetIntValue("VspBspTree.maxTests", mMaxTests);
 
-        // maximum and minimum number of view cells
-        environment->GetIntValue("VspBspTree.Termination.maxViewCells", mMaxViewCells);
-
+        // if only the driving axis is used for axis aligned split
         environment->GetBoolValue("VspBspTree.splitUseOnlyDrivingAxis", mOnlyDrivingAxis);
 
@@ -103 +103 @@
         environment->GetFloatValue("VspBspTree.maxStaticMemory", mMaxMemory);
 
-        
+        environment->GetBoolValue("VspBspTree.Visualization.exportMergedViewCells", mExportMergedViewCells);
+        environment->GetBoolValue("VspBspTree.PostProcess.exportMergeStats", mExportMergeStats);
+        
+
         mStats.open("bspStats.log");
 
@@ -123 +126 @@
         Debug << "using area for pvs: " << mUseAreaForPvs << endl;
         Debug << "Split plane strategy: ";
+
         if (mSplitPlaneStrategy & RANDOM_POLYGON)
         {
@@ -329 +333 @@
                 float minT, maxT;
 
-                //static Ray hray;
-                //hray.Init(ray.GetOrigin(), ray.GetDir(), Ray::LINE_SEGMENT);
+                static Ray hray;
+                hray.Init(*ray);
 
                 // TODO: not very efficient to implictly cast between rays types
-                if (mBox.GetRaySegment(*ray, minT, maxT))
+                if (mBox.GetRaySegment(hray, minT, maxT))
                 {
                         float len = ray->Length();
@@ -515 +519 @@
                                 leaf->mVssRays.push_back((*it).mRay);
                 }
-                
+                // should I check here?
                 if (0 && !mViewCellsManager->CheckValidity(viewCell, 0, mViewCellsManager->GetMaxPvsSize()))
                 {
@@ -1726 +1730 @@
                 if (node->IsLeaf())
                 {
-                        if (!onlyValid ||node->TreeValid())
+                        if (!onlyValid || node->TreeValid())
                         {
                                 ViewCell *viewCell = dynamic_cast<BspLeaf *>(node)->GetViewCell();
@@ -2572 +2576 @@
 
         // clean up old view cells
-        if (0)
+        if (mExportMergedViewCells)
         {
                 DEL_PTR(fVc);
@@ -2631 +2635 @@
                         if ((*nit)->GetViewCell() != leaf->GetViewCell())
                         {
-                                mMergeQueue.push(BspMergeCandidate(leaf, *nit));
+                                BspMergeCandidate mc(leaf, *nit);
+                                mc.EvalMergeCost();
+
+                                mMergeQueue.push(mc);
                                 ++ candidates;
                         }
@@ -2637 +2644 @@
         }
 
-        Debug << "found " << candidates << " new merge candidates" << endl;
+        Debug << "mergequeue: " << (int)mMergeQueue.size() << endl;
+        Debug << "leaves in queue: " << candidates << endl;
+        Debug << "overall cost: " << BspMergeCandidate::sOverallCost << endl;
+
 
         return (int)leaves.size();
@@ -2726 +2736 @@
                         if (!found)
                         {
-                                // this pair is not in map already
+                                // this pair is not in map yet
                                 // => insert into the neighbor map and the queue
                                 neighbors.push_back(prevLeaf);
@@ -2734 +2744 @@
                                 prevLeaf->Mail();
                 
-                                mMergeQueue.push(BspMergeCandidate(leaf, prevLeaf));
+                                BspMergeCandidate mc(leaf, prevLeaf);
+                                mc.EvalMergeCost();
+
+                                mMergeQueue.push(mc);
+
+                                if (((int)mMergeQueue.size() % 1000) == 0)
+                                {
+                                        cout << "collected " << (int)mMergeQueue.size() << " merge candidates" << endl;
+                                }
                         }
         }
         }
+
         Debug << "neighbormap size: " << (int)neighborMap.size() << endl;
         Debug << "mergequeue: " << (int)mMergeQueue.size() << endl;
@@ -2804 +2823 @@
 {
         BspMergeCandidate::sMaxPvsSize = mViewCellsManager->GetMaxPvsSize();
+        //BspMergeCandidate::sMinPvsSize = mViewCellsManager->GetMinPvsSize();
         BspMergeCandidate::sUseArea = mUseAreaForPvs;
 
         // the current view cells are kept in this container
         ViewCellContainer viewCells;
-        ViewCell::NewMail();
-        CollectViewCells(mRoot, true, viewCells, true);
+        if (mExportMergedViewCells)
+        {
+                ViewCell::NewMail();
+                CollectViewCells(mRoot, true, viewCells, true);
+        }
         ViewCell::NewMail();
 
         MergeStatistics mergeStats;
         mergeStats.Start();
-        // TODO: REMOVE LATER for performance!
-        const bool showMergeStats = false;
-
+        
         //BspMergeCandidate::sOverallCost = mBox.SurfaceArea() * mStat.maxPvs;
         long startTime = GetTime();
 
+        cout << "collecting merge candidates ... ";
+        
         if (mUseRaysForMerge)
         {
-                cout << "collecting merge candidates (rays) ... ";
                 mergeStats.nodes = CollectMergeCandidates(rays);
-                cout << "fininshed collecting candidates" << endl;
         }
         else
@@ -2832 +2853 @@
                 mergeStats.nodes = CollectMergeCandidates(leaves);
         }
-                
+        
+        cout << "fininshed collecting candidates" << endl;
 
         mergeStats.collectTime = TimeDiff(startTime, GetTime());
@@ -2840 +2862 @@
         // number of view cells withouth the invalid ones
         int nViewCells = mStat.Leaves() - mStat.invalidLeaves;
-        Debug << "number of view cells taken into account: " << nViewCells << endl;
+        
+        
         // pass is needed for statistics. the last n passes are
         // recorded
         const int maxPasses = 1000;
+        const int nextPass = 50;
+
         int pass = max(nViewCells - mMergeMinViewCells - maxPasses, 0);
-        const int nextPass = 50;
-
-        cout << "starting merge ... " << endl;
+        
+        cout << "actual merge starts now ... " << endl;
 
         //-- use priority queue to merge leaf pairs
@@ -2881 +2905 @@
                         ++ mergeStats.merged;
 
-                        if (showMergeStats)
+                        if ((mergeStats.merged % 500) == 0)
+                                cout << "merged " << mergeStats.merged << " view cells" << endl;
+
+                        // stats and visualizations
+                        if (mExportMergeStats)
                         {
                                 if (mc.GetLeaf1()->IsSibling(mc.GetLeaf2()))
@@ -2892 +2920 @@
                                 mergeStats.accTreeDist += dist;
 
-                                //Debug << "viewcells: " << nViewCells << " mergemin " << mMergeMinViewCells << endl;
                                 if ((mergeStats.merged == pass) || (nViewCells == mMergeMinViewCells))
                                 {
@@ -2903 +2930 @@
                                                 << "#CurrentCost\n" << mergeCost << endl
                                                 << "#RelativeCost\n" << mergeCost / BspMergeCandidate::sOverallCost << endl
-                                                << "#CurrentPvs\n" << mc.GetLeaf1()->GetViewCell()->GetPvs().GetSize() << endl;
-                                        
-                                        ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
-                                        
-                                        // find all already merged view cells and remove them from view cells
-                                        int i = 0;
-                                        while (1)
-                                        {
-                                                //while (!viewCells.empty() && (viewCells.back()->mMailbox == -1))
-                                                while (!viewCells.empty() && (viewCells.back()->GetId() == -2))
-                                                {
-                                                        //DEL_PTR(viewCells.back());
-                                                        viewCells.pop_back();
-                                                }
-                                                // all merged view cells have been found
-                                                if (i >= viewCells.size()) 
-                                                        break;
-
-                                                // already merged view cell, put it to end of vector
-                                                //if (viewCells[i]->mMailbox == -1)
-                                                if (viewCells[i]->GetId() == -2)
-                                                        swap(viewCells[i], viewCells.back());
-                                                
-                                                ++ i;
-                                        }
-                                
-                                        int newVcSize = 0;
-                                        // add new view cells to container only if they don't have been 
-                                        // merged in the mean time
-                                        while (!mNewViewCells.empty())
-                                        {
-                                                if (mNewViewCells.back()->GetId() != -2)
-                                                {
-                                                        viewCells.push_back(mNewViewCells.back());
-                                                        ++ newVcSize;
-                                                }
-
-                                                mNewViewCells.pop_back();
-                                        }
-
-                                        // delete the view cells which were merged
-                                        CLEAR_CONTAINER(mOldViewCells);
-
-                                        char s[64];
-                                        sprintf(s, "merged_viewcells%07d.x3d", nViewCells);
-                                        Exporter *exporter = Exporter::GetExporter(s);
-                                
-                                        if (exporter)
-                                        {
-                                                cout << "exporting " << nViewCells << " merged view cells ... ";
-                                                exporter->ExportGeometry(objects);
-                                                //Debug << "vc size " << (int)viewCells.size() << " merge queue size: " << (int)mMergeQueue.size() << endl;
-                                                ViewCellContainer::const_iterator it, it_end = viewCells.end();
-                
-                                                int i = 0;
-                                                for (it = viewCells.begin(); it != it_end; ++ it)
-                                                {
-                                                        Material m;
-                                                        // assign special material to new view cells
-                                                        // new view cells are on the back of container
-                                                        if (i ++ >= (viewCells.size() - newVcSize))
-                                                        {
-                                                                //m = RandomMaterial();
-                                                                m.mDiffuseColor.r = RandomValue(0.5f, 1.0f);
-                                                                m.mDiffuseColor.g = RandomValue(0.5f, 1.0f);
-                                                                m.mDiffuseColor.b = RandomValue(0.5f, 1.0f);
-                                                        }
-                                                        else
-                                                        {
-                                                                float col = RandomValue(0.1f, 0.4f);
-                                                                m.mDiffuseColor.r = col;
-                                                                m.mDiffuseColor.g = col;
-                                                                m.mDiffuseColor.b = col;
-                                                        }
-
-                                                        exporter->SetForcedMaterial(m);
-                                                        mViewCellsManager->ExportVcGeometry(exporter, *it);
-                                                }
-                                                delete exporter;
-                                                cout << "finished" << endl;
-                                        }
-                                        
+                                                << "#CurrentPvs\n" << mc.GetLeaf1()->GetViewCell()->GetPvs().GetSize() << endl
+                                                << "#MergedSiblings\n" << mergeStats.siblings << endl
+                                                << "#AvgTreeDist\n" << mergeStats.AvgTreeDist() << endl;
+
+                                                if (mExportMergedViewCells)
+                                                        ExportMergedViewCells(viewCells, objects, nViewCells);   
                                 }
                         }
-                        mNewViewCells.clear();
                 }
                 // merge candidate not valid, because one of the leaves was already
@@ -2998 +2948 @@
         }
 
-        // view cells which were merged and are not part of any leaf
-        CLEAR_CONTAINER(mOldViewCells);
-        
-        cout << "finished merge" << endl;
+        mergeStats.overallCost = BspMergeCandidate::sOverallCost;
+
         mergeStats.mergeTime = TimeDiff(startTime, GetTime());
         mergeStats.Stop();
 
-        if (showMergeStats)
-                Debug << mergeStats << endl << endl;
+        Debug << mergeStats << endl << endl;
+        
+        // delete the view cells which were already merged
+        CLEAR_CONTAINER(mOldViewCells);
         
 
@@ -3047 +2997 @@
 
 
-int VspBspTree::RefineViewCells(const VssRayContainer &rays)
+void VspBspTree::ExportMergedViewCells(ViewCellContainer &viewCells, 
+                                                                           const ObjectContainer &objects,
+                                                                           const int nViewCells)
+{
+        ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
+                                        
+        // find all already merged view cells and remove them from view cells
+        int i = 0;
+
+        while (1)
+        {
+                //while (!viewCells.empty() && (viewCells.back()->mMailbox == -1))
+                while (!viewCells.empty() && (viewCells.back()->GetId() == -2))
+                {
+                        //DEL_PTR(viewCells.back());
+                        viewCells.pop_back();
+                }
+                // all merged view cells have been found
+                if (i >= viewCells.size()) 
+                        break;
+
+                // already merged view cell, put it to end of vector
+                //if (viewCells[i]->mMailbox == -1)
+                if (viewCells[i]->GetId() == -2)
+                        swap(viewCells[i], viewCells.back());
+                
+                ++ i;
+        }
+
+        int newVcSize = 0;
+        // add new view cells to container only if they don't have been 
+        // merged in the mean time
+        while (!mNewViewCells.empty())
+        {
+                if (mNewViewCells.back()->GetId() != -2)
+                {
+                        viewCells.push_back(mNewViewCells.back());
+                        ++ newVcSize;
+                }
+
+                mNewViewCells.pop_back();
+        }
+
+        char s[64];
+        sprintf(s, "merged_viewcells%07d.x3d", nViewCells);
+        Exporter *exporter = Exporter::GetExporter(s);
+
+        if (exporter)
+        {
+                cout << "exporting " << nViewCells << " merged view cells ... ";
+                exporter->ExportGeometry(objects);
+                //Debug << "vc size " << (int)viewCells.size() << " merge queue size: " << (int)mMergeQueue.size() << endl;
+                ViewCellContainer::const_iterator it, it_end = viewCells.end();
+
+                int i = 0;
+                for (it = viewCells.begin(); it != it_end; ++ it)
+                {
+                        Material m;
+                        // assign special material to new view cells
+                        // new view cells are on the back of container
+                        if (i ++ >= (viewCells.size() - newVcSize))
+                        {
+                                //m = RandomMaterial();
+                                m.mDiffuseColor.r = RandomValue(0.5f, 1.0f);
+                                m.mDiffuseColor.g = RandomValue(0.5f, 1.0f);
+                                m.mDiffuseColor.b = RandomValue(0.5f, 1.0f);
+                        }
+                        else
+                        {
+                                float col = RandomValue(0.1f, 0.4f);
+                                m.mDiffuseColor.r = col;
+                                m.mDiffuseColor.g = col;
+                                m.mDiffuseColor.b = col;
+                        }
+
+                        exporter->SetForcedMaterial(m);
+                        mViewCellsManager->ExportVcGeometry(exporter, *it);
+                }
+                delete exporter;
+                cout << "finished" << endl;
+        }
+
+        // delete the view cells which were merged
+        CLEAR_CONTAINER(mOldViewCells);
+        // remove the new view cells
+        mNewViewCells.clear();
+}
+
+
+int VspBspTree::RefineViewCells(const VssRayContainer &rays, const ObjectContainer &objects)
 {
         int shuffled = 0;
@@ -3055 +3094 @@
 
         // Use priority queue of remaining leaf pairs 
-        // These candidates either share the same view cells or
+        // The candidates either share the same view cells or
         // are border leaves which share a boundary.
         // We test if they can be shuffled, i.e.,
@@ -3061 +3100 @@
         // leaf is made part of the other view cell. It is tested if the
         // remaining view cells are "better" than the old ones.
+        //
+        // repeat the merging test numPasses times. For example, it could be
+        // that a shuffle only makes sense if another pair was shuffled before.
+        // Therefore we keep two queues and shift the merge candidates between
+        // those two queues until numPasses is reached
+        
+        queue<BspMergeCandidate> queue1;
+        queue<BspMergeCandidate> queue2;
+
+        queue<BspMergeCandidate> *shuffleQueue = &queue1;
+        queue<BspMergeCandidate> *backQueue = &queue2;
+
+    Exporter *exporter = Exporter::GetExporter("neighors.x3d");
+
+        if (exporter)
+        {
+                cout << "exporting neighbors ... ";
+                exporter->ExportGeometry(objects);
+        }
+
+        // HACK for visualization
+        ViewCellContainer viewCells;
+        ViewCell::NewMail();
+        CollectViewCells(mRoot, true, viewCells, true);
+        for (int i = 0; i < viewCells.size(); ++i)
+                viewCells[i]->SetId((int)RandomValue(0, Real(256*256*256)));
+        
+        Material m;
+        m.mDiffuseColor.r = 0;
+        m.mDiffuseColor.g = 0;
+        m.mDiffuseColor.b = 0;
+
         while (!mMergeQueue.empty())
         {
                 BspMergeCandidate mc = mMergeQueue.top();
+                shuffleQueue->push(mc);
                 mMergeQueue.pop();
 
-                // both view cells equal or already shuffled
-                if ((mc.GetLeaf1()->GetViewCell() == mc.GetLeaf2()->GetViewCell()) ||
-                        (mc.GetLeaf1()->Mailed()) || (mc.GetLeaf2()->Mailed()))
-                        continue;
+                m = RandomMaterial();
+                // visualize neighbors
+                exporter->SetForcedMaterial(m);
                 
-                // candidate for shuffling
-                const bool wasShuffled = 
-                        ShuffleLeaves(mc.GetLeaf1(), mc.GetLeaf2());
+                BspNodeGeometry geom1, geom2;
+
+                ConstructGeometry(mc.GetLeaf1(), geom1);
+                ConstructGeometry(mc.GetLeaf1(), geom2);
+
+                //m.mDiffuseColor.r = (mc.GetLeaf1()->GetViewCell()->GetId() & 256)/ 255.0f;
+                //m.mDiffuseColor.g = ((mc.GetLeaf1()->GetViewCell()->GetId()>>8) & 256)/ 255.0f;
+                //m.mDiffuseColor.b = ((mc.GetLeaf1()->GetViewCell()->GetId()>>16) & 256)/ 255.0f;
+                exporter->SetForcedMaterial(m);
+
+                exporter->ExportPolygons(geom1.mPolys);
                 
-                //-- stats
-                if (wasShuffled)
-                        ++ shuffled;
+                //m.mDiffuseColor.r = (mc.GetLeaf2()->GetViewCell()->GetId() & 256)/ 255.0f;
+                //m.mDiffuseColor.g = ((mc.GetLeaf2()->GetViewCell()->GetId()>>8) & 256)/ 255.0f;
+                //m.mDiffuseColor.b = ((mc.GetLeaf2()->GetViewCell()->GetId()>>16) & 256)/ 255.0f;
+                //exporter->SetForcedMaterial(m);
+
+                exporter->ExportPolygons(geom2.mPolys);
+        }
+
+        if (exporter)
+        {
+                cout << "finished" << endl;
+                delete exporter;
+        }
+
+        const int numPasses = 5;
+        int pass = 0;
+        int passShuffled = 0;
+
+
+        do
+        {
+                passShuffled = 0;
+                while (!shuffleQueue->empty())
+                {
+                        BspMergeCandidate mc = shuffleQueue->front();
+                        shuffleQueue->pop();
+
+                        // both view cells equal or already shuffled
+                        if ((mc.GetLeaf1()->GetViewCell() == mc.GetLeaf2()->GetViewCell()))// ||
+                        //      (mc.GetLeaf1()->Mailed()) || (mc.GetLeaf2()->Mailed()))
+                                continue;
+                
+                        // candidate for shuffling
+                        const bool wasShuffled = 
+                                ShuffleLeaves(mc.GetLeaf1(), mc.GetLeaf2());
+                
+                        if (wasShuffled)
+                                ++ passShuffled;
+                        else
+                                backQueue->push(mc);
+                }
+
+                // now the back queue is the current shuffle queue
+                swap(shuffleQueue, backQueue);
+                shuffled += passShuffled;
+                Debug << "shuffled in pass: " << passShuffled << endl;
+        }
+        while (((++ pass) < numPasses) && passShuffled);
+
+        while (!shuffleQueue->empty())
+        {
+                shuffleQueue->pop();
         }
 
@@ -3312 +3440 @@
 mLeaf2Id(l2->GetViewCell()->mMailbox)
 {
-        EvalMergeCost();
+        //EvalMergeCost();
 }
 
@@ -3336 +3464 @@
         BspViewCell *vc = mLeaf2->GetViewCell();
         return GetCost(vc);
+}
+
+
+int ComputeMergedPvsSize(const ObjectPvs &pvs1, const ObjectPvs &pvs2)
+{
+        int pvs = pvs1.GetSize();
+
+        // compute new pvs size
+        ObjectPvsMap::const_iterator it, it_end =  pvs1.mEntries.end();
+
+        Intersectable::NewMail();
+
+        for (it = pvs1.mEntries.begin(); it != it_end; ++ it)
+        {
+                (*it).first->Mail();
+        }
+
+        it_end = pvs2.mEntries.end();
+
+        for (it = pvs2.mEntries.begin(); it != it_end; ++ it)
+        {
+                Intersectable *obj = (*it).first;
+                if (!obj->Mailed())
+                        ++ pvs;
+        }
+
+        return pvs;
 }
 
@@ -3345 +3500 @@
         BspViewCell *vc2 = mLeaf2->GetViewCell();
 
-        const int diff1 = vc1->GetPvs().Diff(vc2->GetPvs());
-        const int newPvs = diff1 + vc1->GetPvs().GetSize();
+        //const int diff1 = vc1->GetPvs().Diff(vc2->GetPvs());
+        //const int newPvs = diff1 + vc1->GetPvs().GetSize();
+        const int newPvs = ComputeMergedPvsSize(vc1->GetPvs(), vc2->GetPvs());
 
         //-- compute ratio of old cost
@@ -3360 +3516 @@
         if (newPvs > sMaxPvsSize) // strong penalty if pvs size too large
         {
-                mMergeCost = 1e15f;
+                mMergeCost = 1e15;
         }
         else
@@ -3417 +3573 @@
 
 /************************************************************************/
-/*                  MergeStatistics implementation                      */
+/*                    MergeStatistics implementation                    */
 /************************************************************************/
 
@@ -3438 +3594 @@
 
         app << "#N_MERGEDSIBLINGS ( Number of merged siblings )\n" << siblings << "\n";
+
+        app << "#OVERALLCOST ( overall merge cost )\n" << overallCost << "\n";
+
         app << "#N_MERGEDNODES ( Number of merged nodes )\n" << merged << "\n";