Changeset 483

Timestamp:

12/27/05 19:32:16 (18 years ago)

Author:

mattausch

Message:

 

Location:

trunk/VUT/GtpVisibilityPreprocessor

Files:

• scripts/default.env (modified) (6 diffs)
• src/Polygon3.cpp (modified) (1 diff)
• src/ViewCellBsp.cpp (modified) (1 diff)
• src/ViewCellsManager.cpp (modified) (20 diffs)
• src/VspBspTree.cpp (modified) (4 diffs)
• src/VspBspTree.h (modified) (1 diff)
• src/VspKdTree.cpp (modified) (10 diffs)
• src/VspKdTree.h (modified) (4 diffs)
• src/X3dExporter.cpp (modified) (1 diff)

trunk/VUT/GtpVisibilityPreprocessor/scripts/default.env

@@ -13 +13 @@
 #;../data/vienna/vienna-plane.x3d
 #       filename ../data/vienna/viewcells-25-sel.x3d
-        filename ../data/atlanta/atlanta2.x3d
+#       filename ../data/atlanta/atlanta2.x3d
 #       filename ../data/soda/soda.dat
-#       filename ../data/soda/soda5.dat
+        filename ../data/soda/soda5.dat
 }
 
@@ -146 +146 @@
         loadFromFile false
         #type kdTree
-        type vspKdTree
+        #type vspKdTree
         #type bspTree
-        #type vspBspTree
+        type vspBspTree
         
         #type sceneDependent
@@ -196 +196 @@
         Termination {
                 maxDepth                40
-                minPvs                  50
+                minPvs                  1
                 minRays                 300
                 minSize                 0.1
-                maxCostRatio            1.8
-                missTolerance           2
-                maxRayContribution      0.5
+                maxCostRatio            0.9
+                missTolerance           6
+                maxRayContribution      0.3
         }
         
@@ -214 +214 @@
         PostProcess {
                 maxCostRatio 0.005
-                minViewCells 300
+                minViewCells 50
                 maxPvsSize   50000
         }
@@ -220 +220 @@
         
         Visualization {
-                exportRays false
-                exportGeometry false
+                exportRays true
+                exportGeometry true
         }
 }
@@ -276 +276 @@
                 exportSplits true
                 exportRays true
-                exportGeometry false
+                exportGeometry true
         }
         

trunk/VUT/GtpVisibilityPreprocessor/src/Polygon3.cpp

@@ -1 +1 @@
 #include "Polygon3.h"
 #include "Mesh.h"
-#include "ViewCellBsp.h" // TODO: erase this
 #include "Mesh.h"
 #include "AxisAlignedBox3.h"

trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.cpp

@@ -1912 +1912 @@
                                                          vector<ViewCell *> &viewcells)
 {
-  int hits = 0;
-  stack<BspRayTraversalData> tStack;
-  
-  float mint = 0.0f, maxt = 1.0f;
-  
-  Intersectable::NewMail();
-  
-  Vector3 entp = origin;
-  Vector3 extp = termination;
-  
-  BspNode *node = mRoot;
-  BspNode *farChild = NULL;
-  
-  while (1) {
-        if (!node->IsLeaf())  {
-          BspInterior *in = dynamic_cast<BspInterior *>(node);
-          
-          Plane3 splitPlane = in->GetPlane();
-          const int entSide = splitPlane.Side(entp);
-          const int extSide = splitPlane.Side(extp);
-          
-          if (entSide < 0) {
-                node = in->GetBack();
-                
-                if(extSide <= 0) // plane does not split ray => no far child
-                  continue;
-                
-                farChild = in->GetFront(); // plane splits ray
-                
-          } else
-                if (entSide > 0) {
-                  node = in->GetFront();
-                  
-                  if (extSide >= 0) // plane does not split ray => no far child
-                        continue;
-                  
-                  farChild = in->GetBack(); // plane splits ray                 
-                }
-                else // ray and plane are coincident
-                  {
-                        // WHAT TO DO IN THIS CASE ?
-                        //break;
-                        node = in->GetFront();
-                        continue;
-                  }
-          
-          // push data for far child
-          tStack.push(BspRayTraversalData(farChild, extp, maxt));
-          
-          // find intersection of ray segment with plane
-          float t;
-          extp = splitPlane.FindIntersection(origin, extp, &t);
-          maxt *= t;
-          
-        } else {
-          // reached leaf => intersection with view cell
-          BspLeaf *leaf = dynamic_cast<BspLeaf *>(node);
-          
-          if (!leaf->mViewCell->Mailed()) {
-                viewcells.push_back(leaf->mViewCell);
-                leaf->mViewCell->Mail();
-                hits++;
-          }
-          
-          //-- fetch the next far child from the stack
-          if (tStack.empty())
-                break;
-      
-          entp = extp;
-          mint = maxt; // NOTE: need this?
-          
-          BspRayTraversalData &s = tStack.top();
-          
-          node = s.mNode;
-          extp = s.mExitPoint;
-          maxt = s.mMaxT;
-          
-          tStack.pop();
-        }
-  }
-  return hits;
+        int hits = 0;
+        stack<BspRayTraversalData> tStack;
+
+        float mint = 0.0f, maxt = 1.0f;
+
+        Intersectable::NewMail();
+
+        Vector3 entp = origin;
+        Vector3 extp = termination;
+
+        BspNode *node = mRoot;
+        BspNode *farChild = NULL;
+
+        while (1) 
+        {
+                if (!node->IsLeaf())  
+                {
+                        BspInterior *in = dynamic_cast<BspInterior *>(node);
+                
+                        Plane3 splitPlane = in->GetPlane();
+                        
+                        const int entSide = splitPlane.Side(entp);
+                        const int extSide = splitPlane.Side(extp);
+
+                        if (entSide < 0) 
+                        {
+                                node = in->GetBack();
+                
+                                if(extSide <= 0) // plane does not split ray => no far child
+                                        continue;
+                
+                                farChild = in->GetFront(); // plane splits ray
+                
+                        } 
+                        else if (entSide > 0) 
+                        {
+                                node = in->GetFront();
+                        
+                                if (extSide >= 0) // plane does not split ray => no far child
+                                        continue;
+                        
+                                farChild = in->GetBack(); // plane splits ray                   
+                        }
+                        else // ray and plane are coincident
+                        {
+                                // WHAT TO DO IN THIS CASE ?
+                                //break;
+                                node = in->GetFront();
+                                continue;
+                        }
+                
+                        // push data for far child
+                        tStack.push(BspRayTraversalData(farChild, extp, maxt));
+                
+                        // find intersection of ray segment with plane
+                        float t;
+                        extp = splitPlane.FindIntersection(origin, extp, &t);
+                        maxt *= t;  
+                } 
+                else 
+                {
+                        // reached leaf => intersection with view cell
+                        BspLeaf *leaf = dynamic_cast<BspLeaf *>(node);
+                
+                        if (!leaf->mViewCell->Mailed()) 
+                        {
+                                viewcells.push_back(leaf->mViewCell);
+                                leaf->mViewCell->Mail();
+                                hits++;
+                        }
+                
+                        //-- fetch the next far child from the stack
+                        if (tStack.empty())
+                                break;
+            
+                        entp = extp;
+                        mint = maxt; // NOTE: need this?
+                
+                        BspRayTraversalData &s = tStack.top();
+                
+                        node = s.mNode;
+                        extp = s.mExitPoint;
+                        maxt = s.mMaxT;
+                
+                        tStack.pop();
+                }
+        }
+        return hits;
 }
 

trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellsManager.cpp

@@ -286 +286 @@
         ViewCellContainer viewcells;
         
+        /*Vector3 origin = ray.mOrigin;
+        Vector3 termination = ray.mTermination;
+        static Ray hray;
+        float tmin = 0, tmax = 1.0;
+        hray.Init(ray.GetOrigin(), ray.GetDir(), Ray::LINE_SEGMENT);
+        GetSceneBbox().ComputeMinMaxT(hray, &tmin, &tmax);
+        if (tmin >= tmax)
+                return;
+
+        if (tmin > 0.0f)
+                origin = ray.Extrap(tmin);
+        
+        if (tmax < 1.0f)
+                termination = ray.Extrap(tmax);*/
+        
         CastLineSegment(ray.mOrigin,
                                         ray.mTermination,
@@ -490 +505 @@
                                                                          const VssRayContainer &rays)
 {
-        if (mBspRays.empty())
-                ConstructBspRays(rays, mConstructionSamples);
-        
         if (!ViewCellsConstructed())
         {
@@ -551 +563 @@
         vector<BspIntersection>::const_iterator iit;
 
+        if (mBspRays.empty())
+                ConstructBspRays(rays, mPostProcessSamples);
+        
         for (int i = 0; i < (int)mBspRays.size(); ++ i)
         {  
@@ -614 +629 @@
 
         if (mBspRays.empty())
-                ConstructBspRays(sampleRays, mConstructionSamples);
+                ConstructBspRays(sampleRays, mVisualizationSamples);
         
         if (1) // export view cells
@@ -881 +896 @@
                 ViewCellContainer viewCells;
 
+                // cast line segment to get intersections with bsp leaves
                 CastLineSegment(vssRay->mTermination, vssRay->mOrigin, viewCells);
 
                 ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
-                
                 for (vit = viewCells.begin(); vit != vit_end; ++ vit)
                 {
@@ -1297 +1312 @@
         ExportLeaves(objects, rays);
 
+        mVspKdTree->CollectMergeCandidates();
         // finally merge kd leaf building blocks to view cells
         const int merged = mVspKdTree->MergeLeaves();
@@ -1408 +1424 @@
                 VspKdViewCell *vc = dynamic_cast<VspKdViewCell *>(mViewCells[idx]); 
 
+                cout << "Output view cell " << i << " with pvs size " << vc->GetPvs().GetSize() << endl;
+                Debug << "Output view cell " << i << " with pvs size " << vc->GetPvs().GetSize() << endl;
                 //-- export geometry
                 Material m;
@@ -1429 +1447 @@
 
                                 VssRayContainer vssRays;
+
+                                VssRayContainer castRays;
+                                VssRayContainer initRays;
+
                                 leaf->GetRays(vssRays);
 
-                                VssRayContainer rays;
                                 VssRayContainer::const_iterator it, it_end = vssRays.end();
+                                const float prop = 200.0f / (float)vssRays.size();
 
                                 for (it = vssRays.begin(); it != it_end; ++ it)
-                                        rays.push_back(*it);
-                        
-                                exporter->ExportRays(rays, RgbColor(1, 0, 0));
+                                {
+                                        if (RandomValue(0, 1) < prop)
+                                                if ((*it)->mTerminationObject == NULL)
+                                                        castRays.push_back(*it);
+                                                else 
+                                                        initRays.push_back(*it);
+                                }
+
+                                exporter->ExportRays(castRays, RgbColor(1, 0, 0));
+                                exporter->ExportRays(initRays, RgbColor(0, 1, 0));
                         }
                 }
@@ -1444 +1473 @@
                 m.mDiffuseColor = RgbColor(1, 0, 0);
                 exporter->SetForcedMaterial(m);
+
+                Intersectable::NewMail();
 
                 ObjectPvsMap::const_iterator it,
@@ -1469 +1500 @@
         //-- export final view cells
         Exporter *exporter = Exporter::GetExporter("vspkdtree_merged.x3d"); 
-        exporter->SetFilled();
+        
+        /*if (exportGeometry) exporter->SetWireframe();
+        else exporter->SetFilled();*/
+
         ExportViewCells(exporter);
 
@@ -1492 +1526 @@
                         rays.push_back(sampleRays[i]);
                 }
-                exporter->ExportRays(rays, RgbColor(1, 0, 0));
+                exporter->ExportRays(rays, RgbColor(1, 0, 0));  
         }
 
@@ -1644 +1678 @@
         GetRaySets(rays, constructionRays, savedRays);
         
-        mVspBspTree->Construct(constructionRays);
+        mVspBspTree->Construct(constructionRays, sceneBbox);
         Debug << mVspBspTree->GetStatistics() << endl;
 
@@ -1669 +1703 @@
                 ViewCellContainer viewCells;
 
+                // cast line segment and store intersections with the rays
                 CastLineSegment(vssRay->mTermination, vssRay->mOrigin, viewCells);
 
@@ -1692 +1727 @@
                 return 0;
         }
-
-        if (mBspRays.empty())
-                ConstructBspRays(rays, mConstructionSamples);
 
         //-- post processing of bsp view cells
@@ -1717 +1749 @@
                         //exporter->SetWireframe();
                         exporter->SetFilled();
-                        
                         ExportViewCells(exporter);
 
-                        if (0)
+                        bool exportGeometry = false;
+                        environment->GetBoolValue("VspBspTree.Visualization.exportGeometry", exportGeometry);
+
+                        if (exportGeometry)
                         {
                                 Material m;
                                 m.mDiffuseColor = RgbColor(0, 1, 0);
                                 exporter->SetForcedMaterial(m);
-                                exporter->SetWireframe();
+                                exporter->SetFilled();
 
                                 exporter->ExportGeometry(objects);
@@ -1748 +1782 @@
         vector<BspIntersection>::const_iterator iit;
 
+        // matt TODO: remove
         if (0)
-        for (int i = 0; i < (int)mBspRays.size(); ++ i)
-        {  
-                BspRay *ray = mBspRays[i];
+        {
+                if (mBspRays.empty())
+                        ConstructBspRays(rays, mPostProcessSamples);
+
+                for (int i = 0; i < (int)mBspRays.size(); ++ i)
+                {
+                        BspRay *ray = mBspRays[i];
           
-                // traverse leaves stored in the rays and compare and merge consecutive
-                // leaves (i.e., the neighbors in the tree)
-                if (ray->intersections.size() < 2)
-                        continue;
+                        // traverse leaves stored in the rays and compare and merge consecutive
+                        // leaves (i.e., the neighbors in the tree)
+                        if (ray->intersections.size() < 2)
+                                continue;
           
-                iit = ray->intersections.begin();
-
-                BspLeaf *previousLeaf = (*iit).mLeaf;
-                ++ iit;
-                
-                for (; iit != ray->intersections.end(); ++ iit)
-                {
-                        BspLeaf *leaf = (*iit).mLeaf;
-
-                        if (ShouldMerge(leaf, previousLeaf))
-                        {                       
-                                MergeVspBspLeafViewCells(leaf, previousLeaf);
-
-                                ++ merged;
+                        iit = ray->intersections.begin();
+
+                        BspLeaf *previousLeaf = (*iit).mLeaf;
+                        ++ iit;
+                
+                        for (; iit != ray->intersections.end(); ++ iit)
+                        {
+                                BspLeaf *leaf = (*iit).mLeaf;
+
+                                if (ShouldMerge(leaf, previousLeaf))
+                                {                       
+                                        MergeVspBspLeafViewCells(leaf, previousLeaf);
+                                        ++ merged;
+                                }
+                                previousLeaf = leaf;
                         }
-                
-                        previousLeaf = leaf;
                 }
         }
@@ -1808 +1846 @@
                 return;
 
+#if 1
         if (mBspRays.empty())
-                ConstructBspRays(sampleRays, mConstructionSamples);
-        
+                ConstructBspRays(sampleRays, mVisualizationSamples);
+#endif
+
         if (1) // export view cells
         {
@@ -1911 +1951 @@
 #endif
         int limit = min(leafOut, (int)mViewCells.size()); 
-                
+
         for (int i = 0; i < limit; ++ i)
         {
@@ -1924 +1964 @@
                 cout << "creating output for view cell " << i << " ... ";
 
-#if 0
+#if 1
                 // check whether we can add the current ray to the output rays
                 for (int k = 0; k < raysOut; ++ k) 
@@ -1965 +2005 @@
                         
                 // export rays piercing this view cell
+#if 1
+                exporter->ExportRays(vcRays, RgbColor(0, 1, 0));
+#endif
 #if 0
-                exporter->ExportRays(vcRays, RgbColor(0, 1, 0));
-#else
                 vector<BspLeaf *>::const_iterator lit, lit_end = vc->mLeaves.end();
+
                 for (lit = vc->mLeaves.begin(); lit != lit_end; ++ lit)
                         exporter->ExportRays((*lit)->mVssRays);

trunk/VUT/GtpVisibilityPreprocessor/src/VspBspTree.cpp

@@ -223 +223 @@
 }
 
-void VspBspTree::Construct(const VssRayContainer &sampleRays)
+void VspBspTree::Construct(const VssRayContainer &sampleRays,
+                                                   AxisAlignedBox3 *forcedBoundingBox)
 {
     mStat.nodes = 1;
@@ -259 +260 @@
         }
 
-        // compute bounding box
-        Polygon3::IncludeInBox(polys, mBox);
+        //-- compute bounding box
+        if (forcedBoundingBox)
+                mBox = *forcedBoundingBox;
+        else
+                Polygon3::IncludeInBox(polys, mBox);
 
         //-- store rays
@@ -269 +273 @@
                 float minT, maxT;
 
-                // TODO: not very efficient to implictly cast between rays types ...
+                // TODO: not very efficient to implictly cast between rays types
                 if (mBox.GetRaySegment(*ray, minT, maxT))
                 {
@@ -1858 +1862 @@
                                 node = in->GetBack();
 
-                                if(extSide <= 0) // plane does not split ray => no far child
+                                if (extSide <= 0) // plane does not split ray => no far child
                                         continue;
 

trunk/VUT/GtpVisibilityPreprocessor/src/VspBspTree.h

@@ -159 +159 @@
                 created in the leafs and stored in the container
         */
-        void Construct(const VssRayContainer &sampleRays);
+        void Construct(const VssRayContainer &sampleRays,
+                                   AxisAlignedBox3 *forcedBoundingBox);
 
         /** Returns list of BSP leaves.

trunk/VUT/GtpVisibilityPreprocessor/src/VspKdTree.cpp

@@ -810 +810 @@
 
         //-- ray density substitute for probability
-        if (1)
+        if (0)
         {
                 pBack = (float)raysBack;
@@ -1979 +1979 @@
         const Vector3 dir = termination - origin;
 
-        stack<LineSegmentTraversalData > tStack;
+        stack<LineTraversalData> tStack;
 
         Intersectable::NewMail();
@@ -2033 +2033 @@
                         // case N4 or P4
                         float tdist = (position - origin[axis]) / dir[axis];
-                        //tStack.push(RayTraversalData(farChild, extp, maxt)); //TODO
+                        tStack.push(LineTraversalData(farChild, extp, maxt)); //TODO
                         extp = origin + dir * tdist;
                         maxt = tdist;
@@ -2050 +2050 @@
                         }
 
+                        if (1) //matt TODO: REMOVE LATER
+                                leaf->mRays.push_back(RayInfo(new VssRay(origin, termination, NULL, NULL, 0)));
+
                         // get the next node from the stack
                         if (tStack.empty())
@@ -2057 +2060 @@
                         mint = maxt;
                         
-                        LineSegmentTraversalData &s  = tStack.top();
+                        LineTraversalData &s  = tStack.top();
                         node = s.mNode;
                         extp = s.mExitPoint;
@@ -2139 +2142 @@
 }
 
-
-
-int VspKdTree::MergeLeaves()
-{
+void VspKdTree::CollectMergeCandidates()
+{
+        MergeCandidate::sOverallCost = 0;
         vector<VspKdLeaf *> leaves;
-        priority_queue<MergeCandidate> mergeQueue;
 
         // collect the leaves, e.g., the "voxels" that will build the view cells
         CollectLeaves(leaves);
-
-        int vcSize = (int)leaves.size();
-        int savedVcSize = vcSize;
 
         VspKdLeaf::NewMail();
@@ -2178 +2176 @@
                         for (nit = neighbors.begin(); nit != nit_end; ++ nit)
                         {
+                                // TODO: test if at least one ray goes from one leaf to the other
                                 MergeCandidate mc = MergeCandidate(leaf, *nit);
-                                mergeQueue.push(mc);
+                                mMergeQueue.push(mc);
 
                                 MergeCandidate::sOverallCost += mc.GetLeaf1Cost();
@@ -2186 +2185 @@
                 }
         }
-
+}
+
+/*
+void VspKdTree::CollectMergeCandidates(const vector<VspKdRay *> &rays)
+{
+        MergeCandidate::sOverallCost = 0;
+
+        vector<VspKdIntersection>::const_iterator iit;
+
+        for (int i = 0; i < (int)rays.size(); ++ i)
+        {  
+                //VspKdLeaf::NewMail();
+
+                VspKdRay *ray = rays[i];
+          
+                // traverse leaves stored in the rays and compare and merge consecutive
+                // leaves (i.e., the neighbors in the tree)
+                if (ray->intersections.size() < 2)
+                        continue;
+          
+                iit = ray->intersections.begin();
+
+                BspLeaf *previousLeaf = (*iit).mLeaf;
+        
+                ++ iit;
+                
+                for (; iit != ray->intersections.end(); ++ iit)
+                {
+            BspLeaf *leaf = (*iit).mLeaf;
+                        
+                        // TODO: how to sort out doubles?
+                        MergeCandidate mc = MergeCandidate(leaf, previousLeaf);
+                        mMergeQueue.push(mc);
+
+                        MergeCandidate::sOverallCost += mc.GetLeaf1Cost();
+                        MergeCandidate::sOverallCost += mc.GetLeaf2Cost();
+
+                        previousLeaf = leaf;
+        }
+        }
+}
+*/
+
+int VspKdTree::MergeLeaves()
+{
         int merged = 0;
 
+        int vcSize = mStat.nodes / 2 + 1;
         // use priority queue to merge leaves
-        while (!mergeQueue.empty() && (vcSize > mMergeMinViewCells) &&
-                   (mergeQueue.top().GetMergeCost() < 
+        while (!mMergeQueue.empty() && (vcSize > mMergeMinViewCells) &&
+                   (mMergeQueue.top().GetMergeCost() < 
                     mMergeMaxCostRatio * MergeCandidate::sOverallCost))
         {
                 //Debug << "mergecost: " << mergeQueue.top().GetMergeCost() / MergeCandidate::sOverallCost << " " << mMergeMaxCostRatio << endl;
-                MergeCandidate mc = mergeQueue.top();
-                mergeQueue.pop();
+                MergeCandidate mc = mMergeQueue.top();
+                mMergeQueue.pop();
 
                 // both view cells equal!
@@ -2218 +2262 @@
                         // validate and reinsert into queue
                         mc.SetValid();
-                        mergeQueue.push(mc);
+                        mMergeQueue.push(mc);
                         //Debug << "validate " << mc.GetMergeCost() << endl;
                 }
@@ -2228 +2272 @@
         RepairVcLeafLists();
 
-        Debug << "merged " << merged << " of " << savedVcSize << " leaves" << endl;
+        Debug << "merged " << merged << " of " << mStat.nodes / 2 + 1 << " leaves" << endl;
 
         //TODO: should return sample contributions

trunk/VUT/GtpVisibilityPreprocessor/src/VspKdTree.h

@@ -529 +529 @@
         };
         
-        struct LineSegmentTraversalData 
+        struct LineTraversalData 
         {
                 VspKdNode *mNode;
@@ -536 +536 @@
                 float mMaxT;
     
-                LineSegmentTraversalData () {}
-                LineSegmentTraversalData (VspKdNode *n,
+                LineTraversalData () {}
+                LineTraversalData (VspKdNode *n,
                                                                   const Vector3 &p,
                                                                   const float maxt):
@@ -608 +608 @@
         */
         void RefineViewCells();
+
+        /** Collects candidates for the merge in the merge queue.
+        */
+        void CollectMergeCandidates();
 
 protected:
@@ -770 +774 @@
         
         ViewCellsManager *mViewCellsManager;
+
+        priority_queue<MergeCandidate> mMergeQueue;
+
 
         /////////////////////////////

trunk/VUT/GtpVisibilityPreprocessor/src/X3dExporter.cpp

@@ -158 +158 @@
   for (; ri != rays.end(); ri++) {
     const Vector3 a = (*ri)->GetOrigin();
-        const Vector3 b = (*ri)->mTerminationObject ? (*ri)->GetTermination() : a + 1000 * Normalize((*ri)->GetDir());
-        
+        //const Vector3 b = (*ri)->mTerminationObject ? (*ri)->GetTermination() : a + 1000 * Normalize((*ri)->GetDir());
+        const Vector3 b = (*ri)->GetTermination(); // matt: change again!!
+
     stream<<a.x<<" "<<a.y<<" "<<a.z<<" ,";
         stream<<b.x<<" "<<b.y<<" "<<b.z<<" ,\n";