Changeset 452

Timestamp:

12/05/05 20:33:53 (19 years ago)

Author:

mattausch

Message:

started to add view cell merging to vsp kd tree

Location:

trunk/VUT/GtpVisibilityPreprocessor

Files:

• scripts/default.env (modified) (4 diffs)
• src/RssPreprocessor.cpp (modified) (4 diffs)
• src/SamplingPreprocessor.cpp (modified) (4 diffs)
• src/ViewCellBsp.cpp (modified) (1 diff)
• src/ViewCellsManager.cpp (modified) (15 diffs)
• src/ViewCellsManager.h (modified) (5 diffs)
• src/VspBspTree.cpp (modified) (1 diff)
• src/VspKdTree.cpp (modified) (9 diffs)
• src/VspKdTree.h (modified) (6 diffs)
• src/VssPreprocessor.cpp (modified) (4 diffs)

trunk/VUT/GtpVisibilityPreprocessor/scripts/default.env

@@ -19 +19 @@
 
 Preprocessor {
-        type sampling
-#       type vss
+#       type sampling
+        type vss
 #       type rss
 }
 
 VssPreprocessor {
-        samplesPerPass  100000
-        initialSamples 500000
-        vssSamples 1000000
-        vssSamplesPerPass 50000
+        samplesPerPass  10000
+        initialSamples 100000
+        vssSamples 300000
+        vssSamplesPerPass 10000
         useImportanceSampling true
 }
@@ -64 +64 @@
 RssPreprocessor {
         samplesPerPass  100000
-        initialSamples 500000
-        vssSamples 5000000
+        initialSamples 400000
+        vssSamples 1000000
         vssSamplesPerPass 100000
         useImportanceSampling true
@@ -279 +279 @@
 
         Construction {
-                samples 100000
+                samples 300000
         }
         
         Termination {
                 maxDepth                40
-                minPvs                  50
-                minRays                 1
+                minPvs                  40
+                minRays                 100
                 minSize                 0.1
                 maxCostRatio            999.0
@@ -330 +330 @@
         Termination {
                 # parameters used for autopartition
-                minRays 200
+                minRays 100
                 minPolygons -1
-                maxDepth 40
+                maxDepth 30
                 minPvs 100
                 minArea 0.01

trunk/VUT/GtpVisibilityPreprocessor/src/RssPreprocessor.cpp

@@ -10 +10 @@
 #include "RssTree.h"
 #include "ViewCellsManager.h"
-
-static bool useViewSpaceBox = true;//true;
+#include "RenderSimulator.h"
+
+static bool useViewSpaceBox = true;
 static bool use2dSampling = false;
 static bool fromBoxVisibility = true;
@@ -423 +424 @@
           Vector3 direction = GetDirection(viewpoint, mViewSpaceBox);
                         
-          CastRay(viewpoint, direction, mVssRays);
+          sampleContributions = CastRay(viewpoint, direction, mVssRays);
                         
                         
@@ -587 +588 @@
         cout<<"*****************************\n";
         cout<<samples<<" avgPVS ="<<pvs<<endl;
+        cout<<"sample contributions ="<<sampleContributions<<endl;
+        cout<<"contributing sample ="<<contributingSamples<<endl;
         cout<<"RssTree root PVS size = "<<rssTree->GetRootPvsSize()<<endl;
         cout<<"*****************************\n";
@@ -603 +606 @@
   }
   
+  //-- post process view cells
+  mViewCellsManager->PostProcess(mObjects, storedRays);
+
+  //-- several visualizations and statistics
+  Debug << "===== Final view cells statistics ==========" << endl;
+
+  mViewCellsManager->PrintStatistics(Debug);
+
+  //-- render simulation after merge
+  cout << "\nevaluating render time of final view cells ... ";
+                 
+  const SimulationStatistics ss = mViewCellsManager->SimulateRendering();
+                 
+  cout << " finished" << endl;
+
+  cout << ss << endl;
+  Debug << ss << endl;
+
+  mViewCellsManager->Visualize(mObjects, storedRays);
+
   delete rssTree;
   

trunk/VUT/GtpVisibilityPreprocessor/src/SamplingPreprocessor.cpp

@@ -390 +390 @@
                 delete exporter;
         }
-
-        //-- post process view cells
+        
+        // construct view cells if not already constructed
+        if (!mViewCellsManager->ViewCellsConstructed())
+                mViewCellsManager->Construct(objects, mVssSampleRays);
+
         mViewCellsManager->PostProcess(objects, mSampleRays);
-                
-
+        
         //-- several visualizations and statistics
-                 
+        Debug << "===== Final view cells statistics ==========" << endl;
+
+        mViewCellsManager->PrintStatistics(Debug);
+
         //-- render simulation after merge
         cout << "\nevaluating bsp view cells render time after merge ... ";
@@ -406 +411 @@
         Debug << ss << endl;
         
-
         mViewCellsManager->Visualize(objects, mSampleRays);     
     
@@ -423 +427 @@
         if (!mViewCellsManager->ViewCellsConstructed())
         {
-                RayContainer::const_iterator it, it_end = newRays.end();
-
-                if ((int)mVssSampleRays.size() < 
-                        mViewCellsManager->GetConstructionSamples())
+                if ((int)mVssSampleRays.size() < mViewCellsManager->GetConstructionSamples())
                 {
+                        RayContainer::const_iterator it, it_end = newRays.end();
+
                         for (it = newRays.begin(); it != it_end; ++ it)
-                        {
                                 mVssSampleRays.push_back(new VssRay(*(*it)));
-                        }
                 }
                 else
@@ -443 +444 @@
         }
         // Need rays (with ordered intersections) for post processing => collect new rays
-        else if (((int)mSampleRays.size() < mViewCellsManager->GetPostProcessSamples()) ||
-                         ((int)mSampleRays.size() < mViewCellsManager->GetVisualizationSamples()))
+        if (((int)mSampleRays.size() < mViewCellsManager->GetPostProcessSamples()) ||
+            ((int)mSampleRays.size() < mViewCellsManager->GetVisualizationSamples()))
         {
                 RayContainer::const_iterator it, it_end = newRays.end();

trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.cpp

@@ -1589 +1589 @@
 
                 // give penalty to unbalanced split
-                if (1)
+                if (0)
                 if (((pFront * 0.2 + Limits::Small) > pBack) || 
                         (pFront < (pBack * 0.2 + Limits::Small)))

trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellsManager.cpp

@@ -78 +78 @@
         RayContainer::const_iterator it, it_end = rays.end();
 
+        sampleContributions = 0;
+        contributingSamples = 0;
+
     for (it = rays.begin(); it != it_end; ++ it)
         {
@@ -329 +332 @@
         }
 
-
         //-- post processing of bsp view cells
     int vcSize = 0;
@@ -420 +422 @@
                  << TimeDiff(startTime, GetTime()) *1e-3 << " secs" << endl;
 
-        // statistics after post process
-        vcStats.Reset();
-        mBspTree->EvaluateViewCellsStats(vcStats);
-        Debug << "post processed view cell partition:\n" << vcStats << endl;
-
         return merged;
 }
@@ -775 +772 @@
 }
 
-
+void BspViewCellsManager::PrintStatistics(ostream &s) const
+{
+        BspViewCellsStatistics vcStats;
+        mBspTree->EvaluateViewCellsStats(vcStats);
+        s << vcStats << endl;
+}
 
 /**********************************************************************/
@@ -963 +965 @@
 
 
+void KdViewCellsManager::PrintStatistics(ostream &s) const
+{
+}
 
 /**********************************************************************/
@@ -983 +988 @@
         if (ViewCellsConstructed())
                 return 0;
-
+                
+        VssRayContainer sampleRays;
+
+        int limit = min (mConstructionSamples, (int)rays.size());
+
+    for (int i = 0; i < limit; ++ i)
+                sampleRays.push_back(rays[i]);
+
+        Debug << "constructing vsp kd tree using " << (int)sampleRays.size() << " samples" << endl;
         mVspKdTree->Construct(rays, sceneBbox);
+
+        Debug << mVspKdTree->GetStatistics() << endl;
+
         return 0;
 }
@@ -1022 +1038 @@
                 return;
 
+        //-- export tree leaves
         if (1)
         {
@@ -1033 +1050 @@
                         exporter->ExportGeometry(objects);
 
-                bool exportRays = true;
+                bool exportRays = false;
 
                 if (exportRays) 
@@ -1086 +1103 @@
 
                         for (it = vssRays.begin(); it != it_end; ++ it)
-                        {
-                                //if (!(*it)->mOriginObject && !(*it)->mTerminationObject)
-                                        rays.push_back(*it);
-
-                                //if (!(*it)->mOriginObject && !(*it)->mTerminationObject)
-                                //      Debug << "ERR: " << (*it)->mOrigin << " " << (*it)->mTermination << endl;
-                        }
-
+                                rays.push_back(*it);
+                        
                         exporter->ExportRays(rays, RgbColor(1, 0, 0));
 
@@ -1112 +1123 @@
 }
 
+void VspKdViewCellsManager::PrintStatistics(ostream &s) const
+{
+}
+
 
 /**********************************************************************/
@@ -1231 +1246 @@
         int pvsSize = 0;
 
+        
         BspViewCellsStatistics vcStats;
         mVspBspTree->EvaluateViewCellsStats(vcStats);
@@ -1307 +1323 @@
                  << TimeDiff(startTime, GetTime()) *1e-3 << " secs" << endl;
 
-        // statistics after post process
-        vcStats.Reset();
-        mVspBspTree->EvaluateViewCellsStats(vcStats);
-        Debug << "post processed view cell partition:\n" << vcStats << endl;
 
         return merged;
@@ -1429 +1441 @@
                         RayContainer vcRays;
                         cout << "creating output for view cell " << i << " ... ";
+                        
                         // check whether we can add the current ray to the output rays
-                        /*for (int k = 0; k < raysOut; ++ k) 
+                        for (int k = 0; k < raysOut; ++ k) 
                         {
                                 Ray *ray = sampleRays[k];
@@ -1444 +1457 @@
                                 }
                         }
-                        */
+                        
 
                         Intersectable::NewMail();
@@ -1613 +1626 @@
 
 
+void VspBspViewCellsManager::PrintStatistics(ostream &s) const
+{
+        BspViewCellsStatistics vcStats;
+        mVspBspTree->EvaluateViewCellsStats(vcStats);
+        s << vcStats << endl;
+}
+
 bool VspBspViewCellsManager::MergeVspBspLeafViewCells(BspLeaf *front, 
                                                                                                           BspLeaf *back) const

trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellsManager.h

@@ -71 +71 @@
         virtual int ComputeSampleContributions(Ray &ray, const bool castRay = true) = 0;
 
+        /** Prints out statistics of the view cells.
+        */
+        virtual void PrintStatistics(ostream &s) const = 0;
+
         /** Post processes view cells givemŽa number of rays.
         */
@@ -215 +219 @@
         bool ViewCellsConstructed() const;
 
+        void PrintStatistics(ostream &s) const;
+
 protected:
 
@@ -269 +275 @@
 
 
+        /** Prints out statistics of this approach.
+        */
+        virtual void PrintStatistics(ostream &s) const;
+
 protected:
 
@@ -309 +319 @@
         bool ViewCellsConstructed() const;
 
+        virtual void PrintStatistics(ostream &s) const;
 
 protected:
@@ -346 +357 @@
         bool ViewCellsConstructed() const;
 
+        void PrintStatistics(ostream &s) const;
+
 protected:
 

trunk/VUT/GtpVisibilityPreprocessor/src/VspBspTree.cpp

@@ -946 +946 @@
 
                 // give penalty to unbalanced split
-                if (1)
+                if (0)
                 if (((pFront * 0.2 + Limits::Small) > pBack) || 
                         (pFront < (pBack * 0.2 + Limits::Small)))

trunk/VUT/GtpVisibilityPreprocessor/src/VspKdTree.cpp

@@ -180 +180 @@
 /**************************************************************/
 VspKdTreeLeaf::VspKdTreeLeaf(VspKdTreeInterior *p,      const int nRays):
-VspKdTreeNode(p), mRays(), mPvsSize(0), mValidPvs(false) 
+VspKdTreeNode(p), mRays(), mPvsSize(0), mValidPvs(false), mViewCell(NULL)
 {
         mRays.reserve(nRays);
@@ -447 +447 @@
 VspKdTree::Construct(const VssRayContainer &rays,
                                          AxisAlignedBox3 *forcedBoundingBox)
-{Debug << "here888" << endl;
+{
         mStat.Start();
-  Debug << "here1000" << endl;
+ 
         mMaxMemory = mMaxStaticMemory;
-        Debug << "here1" << endl;
         DEL_PTR(mRoot);
 
@@ -461 +460 @@
         mStat.nodes = 1;
         mBox.Initialize();
-Debug << "here2" << endl;
+
         //-- compute bounding box
         if (forcedBoundingBox)
@@ -468 +467 @@
                 for (VssRayContainer::const_iterator ri = rays.begin(); ri != rays.end(); ++ ri)
                 {
-                        mBox.Include((*ri)->GetOrigin());
-                        mBox.Include((*ri)->GetTermination()); 
+                        if ((*ri)->mOriginObject)
+                mBox.Include((*ri)->GetOrigin());
+                        if ((*ri)->mTerminationObject)
+                                mBox.Include((*ri)->GetTermination()); 
                 }
 
@@ -676 +677 @@
         }       
 
-        float ratio = 0;
-        
         if (0)
         {
@@ -702 +701 @@
                 const float oldCost = (float)pvsSize;
                 
-                float ratio = newCost / oldCost;
-        }
-        
-        return ratio;
+                return newCost / oldCost;
+        }
 }
 
@@ -731 +728 @@
                 if (!mOnlyDrivingAxis || axis == sAxis) 
                 {
+                        
                         nPosition[axis] = (sBox.Min()[axis] + sBox.Max()[axis]) * 0.5f;
                                                 
@@ -740 +738 @@
                                                                                          nPvsBack[axis],
                                                                                          nPvsFront[axis]);
+                        if (bestAxis == -1)
+                        {
+                                bestAxis = axis;
+                        }
+                        else if (nCostRatio[axis] < nCostRatio[bestAxis])
+                        {
+                                /*Debug << "pvs front " << nPvsBack[axis] 
+                                          << " pvs back " << nPvsFront[axis]
+                                          << " overall pvs " << leaf->GetPvsSize() << endl;*/
+                                bestAxis = axis;
+                        }
                         
-                        if (bestAxis == -1)
-                                bestAxis = axis;
-                        else
-                                if (nCostRatio[axis] < nCostRatio[bestAxis])
-                                {
-                                        Debug << "pvs front " << nPvsBack[axis]
-                                                  << " pvs back " << nPvsFront[axis]
-                                                  << " overall pvs " << leaf->GetPvsSize() << endl;
-                                        bestAxis = axis;
-                                }
                 }
         }
@@ -1786 +1785 @@
         }
 }
+
+int VspKdTree::FindNeighbors(VspKdTreeLeaf *n,
+                                                         vector<VspKdTreeLeaf *> &neighbors,
+                                                         bool onlyUnmailed)
+{
+        stack<VspKdTreeNode *> nodeStack;
+  
+        nodeStack.push(mRoot);
+
+        AxisAlignedBox3 box = GetBBox(n);
+
+        while (!nodeStack.empty()) 
+        {
+                VspKdTreeNode *node = nodeStack.top();
+                nodeStack.pop();
+
+                if (node->IsLeaf()) 
+                {
+                        VspKdTreeLeaf *leaf = dynamic_cast<VspKdTreeLeaf *>(node);
+
+                        if (leaf != n && (!onlyUnmailed || !leaf->Mailed())) 
+                                neighbors.push_back(leaf);
+                } 
+                else 
+                {
+                        VspKdTreeInterior *interior = dynamic_cast<VspKdTreeInterior *>(node);
+
+                        if (interior->mPosition > box.Max(interior->mAxis))
+                                nodeStack.push(interior->mBack);
+                        else
+                        {
+                                if (interior->mPosition < box.Min(interior->mAxis))
+                                        nodeStack.push(interior->mFront);
+                                else 
+                                {
+                                        // random decision
+                                        nodeStack.push(interior->mBack);
+                                        nodeStack.push(interior->mFront);
+                                }
+                        }
+                }
+        }
+
+        return (int)neighbors.size();
+}
+
+void VspKdTree::MergeLeaves()
+{
+        vector<VspKdTreeLeaf *> leaves;
+        priority_queue<LeafPair> mergeCandidates;
+        vector<VspKdTreeLeaf *> neighbors;
+
+        CollectLeaves(leaves);
+
+        VspKdTreeLeaf::NewMail();
+
+        vector<VspKdTreeLeaf *>::const_iterator it, it_end = leaves.end();
+
+
+        for (it = leaves.begin(); it != it_end; ++ it)
+        {
+                VspKdTreeLeaf *leaf = *it;
+
+                if (!leaf->Mailed())
+                {
+                        FindNeighbors(leaf, neighbors, true);
+
+                        vector<VspKdTreeLeaf *>::const_iterator nit, nit_end = neighbors.end();
+
+                        for (nit = neighbors.begin(); nit != neighbors.end(); ++ nit)
+                                mergeCandidates.push(LeafPair(leaf, *nit));
+                        
+                        leaf->Mail();
+                }
+        }
+}
+
+
+
+/*********************************************************************/
+/*                MergeCandidate implementation                      */
+/*********************************************************************/
+
+
+MergeCandidate::MergeCandidate(VspKdTreeLeaf *l1, VspKdTreeLeaf *l2):
+mLeaf1(l1), mLeaf2(l2)
+{}
+
+int MergeCandidate::ComputePvsDifference() const
+{
+        return 0;
+}
+
+float MergeCandidate::EvaluateMergeCost() const
+{
+        return 0;
+}

trunk/VUT/GtpVisibilityPreprocessor/src/VspKdTree.h

@@ -33 +33 @@
 #include "RayInfo.h"
 #include "Containers.h"
+
+class VspKdTreeLeaf;
+
+/**
+        Candidate for leaf merging based on priority.
+*/
+class MergeCandidate
+{  
+public:
+        VspKdTreeLeaf *mLeaf1;
+        VspKdTreeLeaf *mLeaf2;
+
+        MergeCandidate(VspKdTreeLeaf *l1, VspKdTreeLeaf *l2);
+
+        /** Computes PVS difference between the leaves.
+        */
+        int ComputePvsDifference() const;
+
+        /** Evaluates the merge costs of this leaf.
+        */
+        float EvaluateMergeCost() const;
+
+        friend bool operator<(const MergeCandidate &leafa, const MergeCandidate &leafb) 
+        {
+                return leafa.ComputePvsDifference() < leafb.ComputePvsDifference();
+        }
+};
+
+
 
 /**
@@ -294 +323 @@
         static int mailID;
 
-
 protected:
 
@@ -306 +334 @@
         RayInfoContainer mRays;
         bool mValidPvs;
-        
+
+        ViewCell *mViewCell;
 private:
         int mPvsSize;
@@ -453 +482 @@
         void CollectLeaves(vector<VspKdTreeLeaf *> &leaves) const;
 
+        /** Merges leaves of this tree according to some criteria.
+        */
+        void MergeLeaves();
+
+        /** Finds neighbours of this node.
+                @param n the input node
+                @param neighbours the neighbors of the input node
+                @param onlyUnmailed if only unmailed neighbors are collected
+        */
+        int FindNeighbors(VspKdTreeLeaf *n, 
+                                          vector<VspKdTreeLeaf *> &neighbors, 
+                                          bool onlyUnmailed);
+
 protected:
 
@@ -547 +589 @@
 
 protected:
+        
+
         /////////////////////////////
         // The core pointer
@@ -610 +654 @@
         float mTermMaxRayContribution;
 
-
         bool mOnlyDrivingAxis;
+
+        typedef std::pair<VspKdTreeLeaf *, VspKdTreeLeaf *> LeafPair;
+
         /////////////////////////////
         VspKdStatistics mStat;  

trunk/VUT/GtpVisibilityPreprocessor/src/VssPreprocessor.cpp

@@ -10 +10 @@
 #include "VssTree.h"
 #include "ViewCellsManager.h"
+#include "RenderSimulator.h"
 
 bool useViewSpaceBox = true;//true;
@@ -440 +441 @@
   cout << "#totalRayStackSize=" << mVssRays.size() << endl <<flush;
         
-  int numExportRays = 10000;
-  // int numExportRays = 0;
+  //int numExportRays = 10000;
+  int numExportRays = 0;
 
   if (numExportRays) {
@@ -564 +565 @@
         cout<<"*****************************\n";
         cout<<samples<<" avgPVS ="<<pvs<<endl;
+        cout<<"sample contributions ="<<sampleContributions<<endl;
+        cout<<"contributing sample ="<<contributingSamples<<endl;
         cout<<"VssTree root PVS size = "<<vssTree->GetRootPvsSize()<<endl;
         cout<<"*****************************\n";
@@ -573 +576 @@
   //-- post process view cells
   mViewCellsManager->PostProcess(objects, storedRays);
+
+  //-- several visualizations and statistics
+  Debug << "===== Final view cells statistics ==========" << endl;
+
+  mViewCellsManager->PrintStatistics(Debug);
+
+  //-- render simulation after merge
+  cout << "\nevaluating bsp view cells render time after merge ... ";
+                 
+  const SimulationStatistics ss = mViewCellsManager->SimulateRendering();
+                 
+  cout << " finished" << endl;
+  cout << ss << endl;
+  Debug << ss << endl;
+
   mViewCellsManager->Visualize(objects, storedRays);
 
   CLEAR_CONTAINER(storedRays);
-
+  
   delete vssTree;