Changeset 495

Timestamp:

01/04/06 10:02:28 (18 years ago)

Author:

mattausch

Message:

fixed bug in tree collapse

Location:

trunk/VUT/GtpVisibilityPreprocessor

Files:

• scripts/default.env (modified) (4 diffs)
• src/ViewCellBsp.cpp (modified) (1 diff)
• src/ViewCellsManager.cpp (modified) (6 diffs)
• src/VspBspTree.cpp (modified) (15 diffs)
• src/VspBspTree.h (modified) (3 diffs)
• src/VspKdTree.cpp (modified) (10 diffs)
• src/VspKdTree.h (modified) (2 diffs)

trunk/VUT/GtpVisibilityPreprocessor/scripts/default.env

@@ -28 +28 @@
 VssPreprocessor {
         samplesPerPass  100000
-        initialSamples 1000000
+        initialSamples 500000
         vssSamples 200000
         vssSamplesPerPass 100000
         useImportanceSampling true
-        loadInitialSamples  true
+        loadInitialSamples  false
         storeInitialSamples false
 }
@@ -236 +236 @@
 VspBspTree {
         Construction {
-                samples 300000
+                samples 500000
                 epsilon 0.005
                 randomize false
@@ -266 +266 @@
         Termination {
                 # parameters used for autopartition
-                minRays                 20
+                minRays                 100
                 minPolygons             -1
                 maxDepth                30
                 minPvs                  20
                 #minArea                0.0001
-                #minArea                0.000
+                minArea                 0.000
                 maxRayContribution      0.005
                 maxCostRatio            0.9
@@ -277 +277 @@
                 #maxAccRayLength        100
                 
-                maxViewCells            5000
+                maxViewCells            20000
                 
                 # used for pvs criterium

trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.cpp

@@ -1340 +1340 @@
         }
         
-        // choose candidate planes extracted from rays
+        //-- choose candidate planes extracted from rays
         for (int i = 0; i < mMaxRayCandidates; ++ i)
         {

trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellsManager.cpp

@@ -1387 +1387 @@
 
         // collapse siblings belonging to the same view cell
-        mVspKdTree->CollapseTree(mVspKdTree->GetRoot());
-        
+        mVspKdTree->CollapseTree();
+
         // collapse siblings belonging to the same view cell
         mVspKdTree->RefineViewCells(rays);
@@ -1763 +1763 @@
         // collapse invalid regions
         cout << "collapsing invalid tree regions ... ";
-        mVspBspTree->CollapseTree(mVspBspTree->GetRoot()); 
-        cout << "finished" << endl;
+        long startTime = GetTime();
+        mVspBspTree->CollapseTree(); 
+        Debug << "tree collapsed in " << TimeDiff(startTime, GetTime()) * 1e-3 << " seconds" << endl;
+    cout << "finished" << endl;
+        
         cout << "reseting view cell stats ... ";
         ResetViewCells();
@@ -1782 +1785 @@
                         ExportViewCells(exporter);
 
-                        //if (mExportRays)
-                        //      exporter->ExportRays(postProcessRays, RgbColor(1, 1, 0));
+                        if (0 && mExportRays)
+                                exporter->ExportRays(rays, RgbColor(1, 1, 1));
                         
                         if (mExportGeometry)
@@ -1793 +1796 @@
         }
 
-        long startTime = GetTime();
+        startTime = GetTime();
         cout << "Computing remaining ray contributions ... ";
         // recast rest of rays
@@ -1942 +1945 @@
         
         // collapse sibling leaves that share the same view cell
-        mVspBspTree->CollapseTree(mVspBspTree->GetRoot());
+        mVspBspTree->CollapseTree();
+
         // reset view cells and stats
         ResetViewCells();
@@ -2132 +2136 @@
                 //-- export rays piercing this view cell
 #if 1
-                exporter->ExportRays(vcRays, RgbColor(0, 1, 0));
+                exporter->ExportRays(vcRays, RgbColor(1, 1, 1));
 #endif
 #if 0

trunk/VUT/GtpVisibilityPreprocessor/src/VspBspTree.cpp

@@ -35 +35 @@
 float BspMergeCandidate::sOverallCost = 0;
 
-
-/// Adds object to the pvs of the front and back node
-inline void AddObject2Pvs(Intersectable *object,
-                                                  const int side,
-                                                  int &pvsBack,
-                                                  int &pvsFront)
-{
-        if (!object)
-                return;
-
-        if (side <= 0)
-        {
-                if (!object->Mailed() && !object->Mailed(2))
-                {
-                        ++ pvsBack;
-
-                        if (object->Mailed(1))
-                                object->Mail(2);
-                        else
-                                object->Mail();
-                }
-        }
-
-        if (side >= 0)
-        {
-                if (!object->Mailed(1) && !object->Mailed(2))
-                {
-                        ++ pvsFront;
-
-                        if (object->Mailed())
-                                object->Mail(2);
-                        else
-                                object->Mail(1);
-                }
-        }
-}
-
-
 /****************************************************************/
 /*                  class VspBspTree implementation             */
@@ -83 +45 @@
 mViewCellsManager(NULL),
 mStoreRays(false),
-mOnlyDrivingAxis(false),
 mOutOfBoundsCell(NULL)
 {
@@ -794 +755 @@
 float VspBspTree::SelectAxisAlignedPlane(Plane3 &plane,
                                                                                  const VspBspTraversalData &tData,
-                                                                                 int &bestAxis)
+                                                                                 int &axis,
+                                                                                 float &position,
+                                                                                 int &raysBack,
+                                                                                 int &raysFront,
+                                                                                 int &pvsBack,
+                                                                                 int &pvsFront)
 {
         AxisAlignedBox3 box;
@@ -810 +776 @@
         float nPosition[3];
         float nCostRatio[3];
-        bestAxis = -1;
+        int bestAxis = -1;
 
         const int sAxis = box.Size().DrivingAxis();
 
-        for (int axis = 0; axis < 3; ++ axis)
+        for (axis = 0; axis < 3; ++ axis)
         {
                 if (!mOnlyDrivingAxis || axis == sAxis)
@@ -851 +817 @@
         }
 
-        //-- assign best axis
+        //-- assign values
+        axis = bestAxis;
+        position = nPosition[bestAxis];
+
+        raysBack = 0;//nRaysBack[bestAxis];
+        raysFront = 0;//nRaysFront[bestAxis];
+
+        pvsBack = 0;//nPvsBack[bestAxis];
+        pvsFront = 0;//nPvsFront[bestAxis];
+
         Vector3 normal(0,0,0); normal[bestAxis] = 1;
         plane = Plane3(normal, nPosition[bestAxis]);
@@ -1070 +1045 @@
 }
 
+
 bool VspBspTree::SelectPlaneHeuristics(Plane3 &bestPlane,
                                                                            BspLeaf *leaf,
@@ -1086 +1062 @@
         for (int i = 0; i < limit; ++ i)
         {
-                // assure that no index is taken twice
+                //-- assure that no index is taken twice
                 const int candidateIdx = (int)RandomValue(0, (Real)(-- maxIdx));
-                //Debug << "current Idx: " << maxIdx << " cand idx " << candidateIdx << endl;
-
                 Polygon3 *poly = (*data.mPolygons)[candidateIdx];
 
@@ -1109 +1083 @@
         //-- axis aligned splits
         int axis;
-        candidateCost = SelectAxisAlignedPlane(plane, data, axis);
+        float position;
+        int raysBack;
+        int raysFront;
+        int pvsFront;
+        int pvsBack;
+
+        candidateCost = SelectAxisAlignedPlane(plane, 
+                                                                                   data, 
+                                                                                   axis,
+                                                                                   position,
+                                                                                   raysBack,
+                                                                                   raysFront,
+                                                                                   pvsFront,
+                                                                                   pvsBack);
 
         if (candidateCost < lowestCost)
@@ -1116 +1103 @@
                 {
                         useAxisAlignedPlane = true;
+                        //if (data.mPolygons->size() > 0)
+                        //      Debug << "haha" << endl;
                         //! error also computed if cost ratio is missed
                         ++ mStat.splits[axis];
@@ -1142 +1131 @@
         Intersectable::NewMail(); sFrontAndBackId = ViewCell::sMailId;
 }
+
 
 float VspBspTree::SplitPlaneCost(const Plane3 &candidatePlane,
@@ -1159 +1149 @@
         float pBack = 0;
 
-        const bool pvsUseLen = false;
-
         if (mSplitPlaneStrategy & PVS)
         {
-// matt: change back!!
-Intersectable::NewMail(3);
                 // create unique ids for pvs heuristics
-                //GenerateUniqueIdsForPvs();
+                GenerateUniqueIdsForPvs();
 
                 if (mPvsUseArea) // use front and back cell areas to approximate volume
@@ -1227 +1213 @@
                         // assure that we only count the object
                         // once for the front and once for the back side of the plane
-
-                        // add the termination object
-                        //AddObjToPvs(ray->mTerminationObject, cf, frontPvs, backPvs);
-                        AddObject2Pvs(ray->mTerminationObject, cf, frontPvs, backPvs);
-                        // add the source object
-                        //AddObjToPvs(ray->mOriginObject, cf, frontPvs, backPvs);
+                        AddObjToPvs(ray->mTerminationObject, cf, frontPvs, backPvs);
+                        AddObjToPvs(ray->mOriginObject, cf, frontPvs, backPvs);
 
                         // use number of rays to approximate volume
                         if (!mPvsUseArea)
                         {
-                                ++ pOverall;
+                                pOverall = (float)data.mRays->size();
 
                                 if (cf >= 0)
@@ -1253 +1235 @@
 
         if (mSplitPlaneStrategy & BALANCED_RAYS)
-                cost += mBalancedRaysFactor * fabs(sumBalancedRays) /  raysSize;
+                cost += mBalancedRaysFactor * fabs(sumBalancedRays) / raysSize;
 
         // pvs criterium
@@ -2125 +2107 @@
 BspNode *VspBspTree::CollapseTree(BspNode *node)
 {
-    if (node->IsLeaf())
+        if (node->IsLeaf())
                 return node;
 
@@ -2156 +2138 @@
         }
 
+        return node;
+}
+
+
+void VspBspTree::CollapseTree()
+{
+        CollapseTree(mRoot);
         // revalidate leaves
         RepairVcLeafLists();
-
-        return node;
 }
 

trunk/VUT/GtpVisibilityPreprocessor/src/VspBspTree.h

@@ -257 +257 @@
         int RefineViewCells(const VssRayContainer &rays);
 
-        /** Collapses the tree with respect to the view cell partition,
-                i.e. leaves having the same view cell are collapsed.
-                @returns node of type leaf if the node could be collapsed, 
-                this node otherwise
-        */
-        BspNode *CollapseTree(BspNode *node);
+        /** Collapses the tree with respect to the view cell partition.
+        */
+        void CollapseTree();
 
   ViewCell *
@@ -315 +312 @@
         };
 
+        /** Collapses the tree with respect to the view cell partition,
+                i.e. leaves having the same view cell are collapsed.
+                @returns node of type leaf if the node could be collapsed, 
+                this node otherwise
+        */
+        BspNode *CollapseTree(BspNode *node);
         /** Shuffles the leaves, i.e., tests if exchanging
                 the leaves helps in improving the view cells.
@@ -421 +424 @@
         int AddMeshToPolygons(Mesh *mesh, PolygonContainer &polys, MeshInstance *parent);
 
-        /** Selects a plane axis aligned.
+        /** Selects an axis aligned for the next split.
+                @returns cost for this split
         */
         float SelectAxisAlignedPlane(Plane3 &plane, 
                                                                  const VspBspTraversalData &tData,
-                                                                 int &bestAxis);
+                                                                 int &axis,
+                                                                 float &position,
+                                                                 int &raysBack,
+                                                                 int &raysFront,
+                                                                 int &pvsBack,
+                                                                 int &pvsFront);
 
         /** Sorts split candidates for surface area heuristics for axis aligned splits.

trunk/VUT/GtpVisibilityPreprocessor/src/VspKdTree.cpp

@@ -188 +188 @@
                                          const int maxCostMisses):
 VspKdNode(p), mRays(), mPvsSize(0), mValidPvs(false), mViewCell(NULL),
-mMaxCostMisses(maxCostMisses)
+mMaxCostMisses(maxCostMisses), mPvs(NULL), mVolume(0)
 {
         mRays.reserve(nRays);
@@ -195 +195 @@
 VspKdLeaf::~VspKdLeaf()
 {
+        DEL_PTR(mPvs);
 }
 
@@ -785 +786 @@
         if (1) //-- area substitute for probability
         {
-                
+                pOverall = box.SurfaceArea();
+
                 const bool useMidSplit = true;
-                //const bool useMidSplit = false;
-                        
-                pOverall = box.SurfaceArea();
-                        
+                //const bool useMidSplit = false;       
+                                        
                 if (!useMidSplit)
                 {
@@ -892 +892 @@
         pvsFront = nPvsFront[bestAxis];
 
+        if (bestAxis == 1)
+                Debug << "y axis!" << endl;
         return nCostRatio[bestAxis];
 }
@@ -1887 +1889 @@
         RayInfoContainer::const_iterator it, it_end = globalRays.end();
 
-        // TODO
+        Intersectable::NewMail();
 
         // warning: implicit conversion from VssRay to Ray
         for (it = globalRays.begin(); it != globalRays.end(); ++ it)
-                pvsSize += box.GetMinMaxT(*(*it).mRay, NULL, NULL);
-
+        {
+                VssRay *ray = (*it).mRay;
+
+                // ray intersects node bounding box
+                if (box.GetMinMaxT(*ray, NULL, NULL))
+                {
+                        if (ray->mTerminationObject && !ray->mTerminationObject->Mailed())
+                        {
+                                ray->mTerminationObject->Mail();
+                                ++ pvsSize;
+                        }
+                }
+        }
         return pvsSize;
 }
@@ -2345 +2358 @@
         }
 
+        return node;
+}
+
+
+void VspKdTree::CollapseTree()
+{
+        CollapseTree(mRoot);
         // revalidate leaves
         RepairVcLeafLists();
-
-        return node;
-}
-
+}
 
 int VspKdTree::RefineViewCells(const VssRayContainer &rays)
@@ -2379 +2396 @@
                 const bool wasShuffled = false;
                         //ShuffleLeaves(mc.GetLeaf1(), mc.GetLeaf2());
-                
+                        // matt: restore
                 //-- stats
                 if (wasShuffled)
@@ -2403 +2420 @@
 float GetShuffledVcCost(VspKdLeaf *leaf, VspKdViewCell *vc1, VspKdViewCell *vc2)
 {
-#if 0 // TODO
         const int pvs1 = SubtractedPvsSize(vc1->GetPvs(), *leaf->mPvs);
         const int pvs2 = AddedPvsSize(vc2->GetPvs(), *leaf->mPvs);
 
-        const float area1 = vc1->GetArea() - leaf->mArea;
-        const float area2 = vc2->GetArea() + leaf->mArea;
-
-        const float cost1 = pvs1 * area1;
-        const float cost2 = pvs2 * area2;
+        const float vol1 = vc1->GetVolume() - leaf->mVolume;
+        const float vol2 = vc2->GetVolume() + leaf->mVolume;
+
+        const float cost1 = pvs1 * vol1;
+        const float cost2 = pvs2 * vol2;
 
         return cost1 + cost2;
-#else
-        return -1;
-#endif
 }
 
@@ -2424 +2437 @@
                                                         VspKdViewCell *vc2) const
 {
-#if 0 // TODO
         // compute new pvs and area
         vc1->GetPvs().SubtractPvs(*leaf->mPvs);
         vc2->GetPvs().AddPvs(*leaf->mPvs);
         
-        vc1->SetArea(vc1->GetArea() - leaf->mArea);
-        vc2->SetArea(vc2->GetArea() + leaf->mArea);
+        vc1->SetArea(vc1->GetVolume() - leaf->mVolume);
+        vc2->SetArea(vc2->GetVolume() + leaf->mVolume);
 
         /// add to second view cell
@@ -2442 +2454 @@
 
         leaf->SetViewCell(vc2);  // finally change view cell
-#endif
 }
 

trunk/VUT/GtpVisibilityPreprocessor/src/VspKdTree.h

@@ -390 +390 @@
         
         static void NewMail();
-
         static int sMailId;
 
-        
+        ObjectPvs *mPvs;
+        float mVolume;
+
 protected:
 
@@ -616 +617 @@
 
         /** Collapses the tree with respect to the view cell partition.
-                @returns node of type leaf if the node could be collapsed, this node otherwise
+        */
+        void CollapseTree();
+
+protected:
+
+        /** Collapses the tree with respect to the view cell partition.
+                @returns node of type leaf if the node could be collapsed, 
+                this node otherwise
         */
         VspKdNode *CollapseTree(VspKdNode *node);
-
-protected:
-
         // incremental construction
         virtual void UpdateRays(VssRayContainer &remove, VssRayContainer &add);