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

Timestamp:

01/16/06 03:23:29 (18 years ago)

Author:

mattausch

Message:

 

File:

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

trunk/VUT/GtpVisibilityPreprocessor/src/VspBspTree.cpp

@@ -278 +278 @@
 
         int numObj = 0;
+
         //-- extract polygons intersected by the rays
         for (rit = sampleRays.begin(); rit != rit_end; ++ rit)
@@ -313 +314 @@
         mMaxPvs = (int)(mMaxPvsRatio * (float)numObj);
         
-        Debug << "maximal pvs (i.e., view cell considered as valid: " << mMaxPvs << endl;
+        Debug << "maximal pvs (i.e., pvs still considered as valid) : " << mMaxPvs << endl;
         //-- store rays
         for (rit = sampleRays.begin(); rit != rit_end; ++ rit)
@@ -382 +383 @@
 
         mStat.Start();
-        cout << "Contructing vsp bsp tree ... ";
-
-        long startTime = GetTime();
-        
-        bool mOutOfMemory = false;
+        cout << "Contructing vsp bsp tree ... \n";
+
+        long startTime = GetTime();     
+        long interTime = GetTime();     
+        mOutOfMemory = false;
+
+        int nleaves = 500;
 
         while (!tStack.empty())
@@ -404 +407 @@
                 }
 
-                // subdivide leaf node
+                        // subdivide leaf node
                 BspNode *r = Subdivide(tStack, tData);
 
                 if (r == mRoot)
                         Debug << "VSP BSP tree construction time spent at root: "
-                                  << TimeDiff(startTime, GetTime())*1e-3 << "s" << endl << endl;
-        }
-
-        Debug << "Used Memory: " << GetMemUsage() << " MB" << endl;
+                                  << TimeDiff(startTime, GetTime())*1e-3 << "s" << endl;
+
+                if (mStat.Leaves() >= nleaves)
+                {
+                        nleaves += 500;
+                                
+                        cout << "leaves=" << mStat.Leaves() << endl;
+                        Debug << "needed "
+                          << TimeDiff(interTime, GetTime())*1e-3 << " secs to create 500 leaves" << endl;
+                        interTime = GetTime();
+                }
+        }
+
+        Debug << "Used Memory: " << GetMemUsage() << " MB" << endl << endl;
         cout << "finished\n";
 
@@ -436 +449 @@
         BspNode *newNode = tData.mNode;
 
-        if (!mOutOfMemory || !TerminationCriteriaMet(tData))
+        if (!mOutOfMemory && !TerminationCriteriaMet(tData))
         {
                 PolygonContainer coincident;
@@ -508 +521 @@
 
 
+
+
 BspNode *VspBspTree::SubdivideNode(VspBspTraversalData &tData,
                                                                    VspBspTraversalData &frontData,
@@ -517 +532 @@
         // select subdivision plane
         Plane3 splitPlane;
+        
         int maxCostMisses = tData.mMaxCostMisses;
-        bool success = SelectPlane(splitPlane, 
-                                                           leaf, 
-                                                           tData,
-                                                           frontData,
-                                                           backData);
+
+        const bool success = 
+                SelectPlane(splitPlane, leaf, tData, frontData, backData);
+
         if (!success)
         {
@@ -578 +593 @@
         if (mPvsUseArea)
         {
-                // if not already computed
+                // if geometry was not already computed
                 if (!frontData.mGeometry && !backData.mGeometry)
                 {
@@ -820 +835 @@
                                                                                  BspNodeGeometry **backGeom,
                                                                                  float &frontArea,
-                                                                                 float &backArea)
+                                                                                 float &backArea,
+                                                                                 bool useKdSplit)
 {
         const bool useCostHeuristics = false;
@@ -838 +854 @@
         AxisAlignedBox3 box;
         box.Initialize();
-        
+        //TODO: for kd split geometry already is box
         if (1 && mPvsUseArea)
         {
@@ -868 +884 @@
                                 Vector3 normal(0,0,0); normal[axis] = 1;
                                 
-                                nCostRatio[axis] = SplitPlaneCost(Plane3(normal, nPosition[axis]), 
-                                                                                                  tData, *nFrontGeom[axis], *nBackGeom[axis],
-                                                                                                  nFrontArea[axis], nBackArea[axis]);
+                                if (useKdSplit)
+                                {
+                                        nCostRatio[axis] = EvalAxisAlignedSplitCost(tData,
+                                                                                                                                box,
+                                                                                                                                axis,
+                                                                                                                                nPosition[axis]);
+                                        
+                                        Vector3 pos = box.Max(); pos[axis] = nPosition[axis];
+                                        AxisAlignedBox3 frontBox(box.Min(), pos);
+                                        frontBox.ExtractPolys(nFrontGeom[axis]->mPolys);
+                                        
+                                        pos = box.Min(); pos[axis] = nPosition[axis];
+                                        AxisAlignedBox3 backBox(pos, box.Max());
+                                        backBox.ExtractPolys(nBackGeom[axis]->mPolys);
+
+                                }
+                                else
+                                {
+                                        nCostRatio[axis] = SplitPlaneCost(Plane3(normal, nPosition[axis]), 
+                                                                                                          tData, *nFrontGeom[axis], *nBackGeom[axis],
+                                                                                                          nFrontArea[axis], nBackArea[axis]);
+                                }
                         }
                         else
@@ -903 +938 @@
         *frontGeom = nFrontGeom[bestAxis];
         *backGeom = nBackGeom[bestAxis];
+
         // and delete other geometry
         delete nFrontGeom[(bestAxis + 1) % 3];
@@ -913 +949 @@
         return nCostRatio[bestAxis];
 }
+
+
+float VspBspTree::EvalAxisAlignedSplitCost(const VspBspTraversalData &data,
+                                                                                   const AxisAlignedBox3 &box,
+                                                                                   const int axis,
+                                                                                   const float &position) const
+{
+        int pvsFront = 0;
+        int pvsBack = 0;
+        int pvsTotal = 0;
+
+        // create unique ids for pvs heuristics
+        GenerateUniqueIdsForPvs();
+
+        const int pvsSize = data.mPvs;
+
+        // this is the main ray classification loop!
+        for(RayInfoContainer::iterator ri = data.mRays->begin();
+                ri != data.mRays->end(); ++ ri)
+        {
+                if (!(*ri).mRay->IsActive())
+                        continue;
+
+                // determine the side of this ray with respect to the plane
+                float t;
+                int side = (*ri).ComputeRayIntersection(axis, position, t);
+        
+                AddObjToPvs((*ri).mRay->mTerminationObject, side, pvsFront, pvsBack, pvsTotal);
+                AddObjToPvs((*ri).mRay->mOriginObject, side, pvsFront, pvsBack, pvsTotal);
+        }
+
+        //-- only one of these options should be one
+        //-- pvs + probability heuristics
+        float pBack, pFront, pOverall;
+
+        if (1)
+        {
+                // box length substitute for probability
+                const float minBox = box.Min(axis);
+                const float maxBox = box.Max(axis);
+
+                pBack = position - minBox;
+                pFront = maxBox - position;
+                pOverall = maxBox - minBox;
+        }
+        else //-- area substitute for probability
+        {
+                pOverall = box.SurfaceArea();
+
+                const bool useMidSplit = true;
+                //const bool useMidSplit = false;       
+                                        
+                //-- simplified computation for mid split
+                const int axis2 = (axis + 1) % 3;
+                const int axis3 = (axis + 2) % 3;
+
+                const float faceArea = 
+                        (box.Max(axis2) - box.Min(axis2)) *
+                        (box.Max(axis3) - box.Min(axis3));
+
+                pBack = pFront = pOverall * 0.5f + faceArea;
+        }
+
+        //Debug << axis << " " << pvsSize << " " << pvsBack << " " << pvsFront << endl;
+        //Debug << pFront << " " << pBack << " " << pOverall << endl;
+
+        // float sum = raysBack*(position - minBox) + raysFront*(maxBox - position);
+        const float newCost = pvsBack * pBack + pvsFront * pFront;
+        //  float oldCost = leaf->mRays.size();
+        const float oldCost = (float)pvsSize * pOverall;
+
+        return  (mCtDivCi + newCost) / oldCost;
+}
+
 
 
@@ -984 +1094 @@
         candidateCost = SelectAxisAlignedPlane(plane, data, axis,
                                                                                    &fGeom, &bGeom, 
-                                                                                   fArea, bArea);                                                
+                                                                                   fArea, bArea,
+                                                                                   onlyAxisAligned);     
 
         if (candidateCost < lowestCost)
@@ -991 +1102 @@
                 lowestCost = candidateCost;
 
-                //-- assign already computed values
+                // assign already computed values
+                // we can do this because we always save the
+                // computed values from the axis aligned splits
                 frontData.mGeometry = fGeom;
                 backData.mGeometry = bGeom;
@@ -1123 +1236 @@
         int totalPvs = 0;
 
+        int limit;
+        bool useRand;
+
+        // choose test rays randomly if too much
+        if ((int)data.mRays->size() > mMaxTests)
+        {
+                useRand = true;
+                limit = mMaxTests;
+        }
+        else
+        {
+                useRand = false;
+                limit = (int)data.mRays->size();
+        }
+        
+        for (int i = 0; i < limit; ++ i)
+        {
+                const int testIdx = useRand ? 
+                        (int)RandomValue(0, (Real)((int)data.mRays->size() - 1)) : i;
+                RayInfo rayInf = (*data.mRays)[testIdx];
+
+                float t;
+                VssRay *ray = rayInf.mRay;
+                const int cf = rayInf.ComputeRayIntersection(candidatePlane, t);
+
+        if (cf >= 0)
+                        ++ raysFront;
+                if (cf <= 0)
+                        ++ raysBack;
+
+                if (mSplitPlaneStrategy & LEAST_RAY_SPLITS)
+                {
+                        sumBalancedRays += cf;
+                }
+
+                if (mSplitPlaneStrategy & BALANCED_RAYS)
+                {
+                        if (cf == 0)
+                                ++ sumRaySplits;
+                }
+
+                if (mSplitPlaneStrategy & PVS)
+                {
+                        // find front and back pvs for origing and termination object
+                        AddObjToPvs(ray->mTerminationObject, cf, pvsFront, pvsBack, totalPvs);
+                        AddObjToPvs(ray->mOriginObject, cf, pvsFront, pvsBack, totalPvs);
+                }
+        }
+
+        const float raysSize = (float)data.mRays->size() + Limits::Small;
         if (mSplitPlaneStrategy & PVS)
         {
@@ -1136 +1299 @@
                                                                                   mBox,
                                                                                   mEpsilon);
-
+#if 0
+                        AxisAlignedBox3 fbox;
+                        AxisAlignedBox3 bbox;
+                        AxisAlignedBox3 box;
+                        fbox.Initialize();
+                        bbox.Initialize();
+                        box.Initialize();
+
+                        geomFront.IncludeInBox(fbox);
+                        geomBack.IncludeInBox(bbox);
+                        data.mGeometry->IncludeInBox(box);
+
+                        areaFront = fbox.GetVolume();
+                        areaBack = bbox.GetVolume();
+
+                        pOverall = box.GetVolume();
+#else
                         areaFront = geomFront.GetArea();
                         areaBack = geomBack.GetArea();
 
+                        pOverall = data.mArea;
+#endif
                         pBack = areaBack;
                         pFront = areaFront;
-                        pOverall = data.mArea;
                 }
                 else // use number of rays to approximate volume
@@ -1152 +1332 @@
         }
 
-        int limit;
-        bool useRand;
-
-        // choose test rays randomly if too much
-        if ((int)data.mRays->size() > mMaxTests)
-        {
-                useRand = true;
-                limit = mMaxTests;
-        }
-        else
-        {
-                useRand = false;
-                limit = (int)data.mRays->size();
-        }
-        
-        for (int i = 0; i < limit; ++ i)
-        {
-                const int testIdx = useRand ? 
-                        (int)RandomValue(0, (Real)((int)data.mRays->size() - 1)) : i;
-                RayInfo rayInf = (*data.mRays)[testIdx];
-
-                float t;
-                VssRay *ray = rayInf.mRay;
-                const int cf = rayInf.ComputeRayIntersection(candidatePlane, t);
-
-        if (cf >= 0)
-                        ++ raysFront;
-                if (cf <= 0)
-                        ++ raysBack;
-
-                if (mSplitPlaneStrategy & LEAST_RAY_SPLITS)
-                {
-                        sumBalancedRays += cf;
-                }
-
-                if (mSplitPlaneStrategy & BALANCED_RAYS)
-                {
-                        if (cf == 0)
-                                ++ sumRaySplits;
-                }
-
-                if (mSplitPlaneStrategy & PVS)
-                {
-                        // find front and back pvs for origing and termination object
-                        AddObjToPvs(ray->mTerminationObject, cf, pvsFront, pvsBack, totalPvs);
-                        AddObjToPvs(ray->mOriginObject, cf, pvsFront, pvsBack, totalPvs);
-                }
-        }
-
-        const float raysSize = (float)data.mRays->size() + Limits::Small;
 
         if (mSplitPlaneStrategy & LEAST_RAY_SPLITS)
@@ -1473 +1603 @@
 }
 
+
+
+void VspBspTree::CheckValidy()
+{
+        stack<BspNode *> nodeStack;
+
+        if (!mRoot)
+                return;
+
+        nodeStack.push(mRoot);
+        
+        while (!nodeStack.empty()) 
+        {
+                BspNode *node = nodeStack.top();
+                nodeStack.pop();
+                
+                if (node->IsLeaf())
+                {
+                        BspLeaf *leaf = dynamic_cast<BspLeaf *>(node);
+
+                        if (node->TreeValid())
+                        {
+                                BspViewCell *viewCell = dynamic_cast<BspLeaf *>(node)->GetViewCell();
+                        
+                                if (viewCell->GetPvs().GetSize() > mMaxPvs)
+                                {
+                                        while (!viewCell->mLeaves.empty())
+                                        {
+                                                BspLeaf *l = viewCell->mLeaves.back();
+                                                l->SetTreeValid(false);
+                                                PropagateUpValidity(l);
+
+                                                l->SetViewCell(GetOrCreateOutOfBoundsCell());
+                                                viewCell->mLeaves.pop_back();
+                                        }
+
+                                        mOutOfBoundsCell->GetPvs().AddPvs(viewCell->GetPvs());
+
+                                        DEL_PTR(viewCell);
+                                }
+                        }
+                }
+                else
+                {
+                        BspInterior *interior = dynamic_cast<BspInterior *>(node);
+                
+                        nodeStack.push(interior->GetFront());
+                        nodeStack.push(interior->GetBack());
+                }
+        }
+}
 
 void VspBspTree::CollectViewCells(BspNode *root, 
@@ -2438 +2619 @@
 
         //-- collect the leaves which haven't been found by ray casting
-        vector<BspLeaf *> leaves;
-        CollectLeaves(leaves, true, mMaxPvs);
-        Debug << "found " << (int)leaves.size() << " new leaves" << endl << endl;
-        // TODO
-        CollectMergeCandidates(leaves);
+        if (0)
+        {
+                vector<BspLeaf *> leaves;
+                CollectLeaves(leaves, true, mMaxPvs);
+                Debug << "found " << (int)leaves.size() << " new leaves" << endl << endl;
+                CollectMergeCandidates(leaves);
+        }
 
         return numLeaves;
@@ -2519 +2702 @@
                     mMergeMaxCostRatio * BspMergeCandidate::sOverallCost))
         {
-                //Debug << "abs mergecost: " << mMergeQueue.top().GetMergeCost() << " rel mergecost: "
-                //        << mMergeQueue.top().GetMergeCost() / BspMergeCandidate::sOverallCost 
-                //        << " max ratio: " << mMergeMaxCostRatio << endl;
+                /*Debug << "abs mergecost: " << mMergeQueue.top().GetMergeCost() << " rel mergecost: "
+                          << mMergeQueue.top().GetMergeCost() / BspMergeCandidate::sOverallCost 
+                          << " max ratio: " << mMergeMaxCostRatio << endl;*/
                 BspMergeCandidate mc = mMergeQueue.top();
                 mMergeQueue.pop();
@@ -2532 +2715 @@
                 {
                         ViewCell::NewMail();
+        
                         MergeViewCells(mc.GetLeaf1(), mc.GetLeaf2());
                         -- nViewCells;
@@ -2709 +2893 @@
 
         leaf->SetViewCell(vc2); // finally change view cell
-        
-        //Debug << "new pvs: " << vc1->GetPvs().GetSize() + vc2->GetPvs().GetSize() 
-        //        << " (" << vc1->GetPvs().GetSize() << ", " << vc2->GetPvs().GetSize() << ")" << endl;
-
 }
 
@@ -2741 +2921 @@
         if (shuffledCost1 < shuffledCost2)
         {
-                //Debug << "old cost: " << oldCost << ", new cost: " << shuffledCost1 << endl;
                 ShuffleLeaf(leaf1, vc1, vc2);
                 leaf1->Mail();
@@ -2747 +2926 @@
         else
         {
-                //Debug << "old cost: " << oldCost << ", new cost: " << shuffledCost2 << endl;
                 ShuffleLeaf(leaf2, vc2, vc1);
                 leaf2->Mail();
@@ -2879 +3057 @@
 
         //-- compute ratio of old cost
-        //-- (added size of left and right view cell times pvs size)
-        //-- to new rendering cost (size of merged view cell times pvs size)
+        //   (i.e., added size of left and right view cell times pvs size)
+        //   to new rendering cost (i.e, size of merged view cell times pvs size)
         const float oldCost = GetLeaf1Cost() + GetLeaf2Cost();
 
@@ -2886 +3064 @@
                 (float)newPvs * (vc1->GetArea() + vc2->GetArea());
 
-        mMergeCost = newCost - oldCost;
         if (newPvs > sMaxPvsSize) // strong penalty if pvs size too large
-                mMergeCost += 1.0;
-}
+        {
+                mMergeCost = 1e15f;
+        }
+        else
+        {
+                mMergeCost = newCost - oldCost;
+        }
+}
+
 
 void BspMergeCandidate::SetLeaf1(BspLeaf *l)
@@ -2896 +3080 @@
 }
 
+
 void BspMergeCandidate::SetLeaf2(BspLeaf *l)
 {
@@ -2901 +3086 @@
 }
 
+
 BspLeaf *BspMergeCandidate::GetLeaf1()
 {
@@ -2906 +3092 @@
 }
 
+
 BspLeaf *BspMergeCandidate::GetLeaf2()
 {
         return mLeaf2;
 }
+
 
 bool BspMergeCandidate::Valid() const
@@ -2918 +3106 @@
 }
 
+
 float BspMergeCandidate::GetMergeCost() const
 {
         return mMergeCost;
 }
+
 
 void BspMergeCandidate::SetValid()