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

Timestamp:

12/23/05 21:35:53 (18 years ago)

Author:

mattausch

Message:

axis aligned split for vsp bsp view cells

File:

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

trunk/VUT/GtpVisibilityPreprocessor/src/VspBspTree.cpp

@@ -84 +84 @@
         environment->GetIntValue("VspBspTree.Termination.maxViewCells", mMaxViewCells);
         environment->GetIntValue("VspBspTree.PostProcess.minViewCells", mMergeMinViewCells);
-        environment->GetIntValue("VspBspTree.PostProcess.maxCostRatio", mMergeMaxCostRatio);
+        environment->GetFloatValue("VspBspTree.PostProcess.maxCostRatio", mMergeMaxCostRatio);
 
 
@@ -125 +125 @@
                 Debug << "pvs";
         }
+        
+        mSplitCandidates = new vector<SortableEntry>;
 
         Debug << endl;
@@ -140 +142 @@
         DEL_PTR(mRoot);
         DEL_PTR(mRootCell);
+        DEL_PTR(mSplitCandidates);
 }
 
@@ -236 +239 @@
         long startTime = GetTime();
 
-        cout << "Extracting polygons from rays ...";
+        cout << "Extracting polygons from rays ... ";
 
         Intersectable::NewMail();
@@ -430 +433 @@
                 ++ maxCostMisses;
 
-                if (maxCostMisses >= mTermMissTolerance)
+                if (maxCostMisses > mTermMissTolerance)
                 {
                         // terminate branch because of max cost
@@ -555 +558 @@
 }
 
-void VspBspTree::SortSplitCandidates(const PolygonContainer &polys, 
-                                                                         const int axis, 
-                                                                         vector<SortableEntry> &splitCandidates) const
-{
-        splitCandidates.clear();
-  
-        const int requestedSize = 2 * (int)polys.size();
-        
-        // creates a sorted split candidates array  
-        splitCandidates.reserve(requestedSize);
-  
-        PolygonContainer::const_iterator it, it_end = polys.end();
-
-        AxisAlignedBox3 box;
-
-        // insert all queries 
-        for(it = polys.begin(); it != it_end; ++ it)
-        {
-                box.Initialize();
-                box.Include(*(*it));
-          
-                splitCandidates.push_back(SortableEntry(SortableEntry::POLY_MIN, box.Min(axis), *it));
-                splitCandidates.push_back(SortableEntry(SortableEntry::POLY_MAX, box.Max(axis), *it));
-        }
-  
-        stable_sort(splitCandidates.begin(), splitCandidates.end());
-}
-
-
-float VspBspTree::BestCostRatio(const PolygonContainer &polys,
-                                                                const AxisAlignedBox3 &box,
-                                                                const int axis,
-                                                                float &position,
-                                                                int &objectsBack,
-                                int &objectsFront) const
-{
-        vector<SortableEntry> splitCandidates;
-
-        SortSplitCandidates(polys, axis, splitCandidates);
-        
+void VspBspTree::SortSplitCandidates(const RayInfoContainer &rays, const int axis)
+{
+        mSplitCandidates->clear();
+
+        int requestedSize = 2 * (int)(rays.size());
+        // creates a sorted split candidates array
+        if (mSplitCandidates->capacity() > 500000 &&
+                requestedSize < (int)(mSplitCandidates->capacity()/10) )
+        {
+        DEL_PTR(mSplitCandidates);
+                mSplitCandidates = new vector<SortableEntry>;
+        }
+
+        mSplitCandidates->reserve(requestedSize);
+
+        // insert all queries
+        for(RayInfoContainer::const_iterator ri = rays.begin(); ri < rays.end(); ++ ri)
+        {
+                bool positive = (*ri).mRay->HasPosDir(axis);
+                mSplitCandidates->push_back(SortableEntry(positive ? SortableEntry::ERayMin : SortableEntry::ERayMax,
+                                                                                                  (*ri).ExtrapOrigin(axis), (void *)&*ri));
+
+                mSplitCandidates->push_back(SortableEntry(positive ? SortableEntry::ERayMax : SortableEntry::ERayMin,
+                                                                                                  (*ri).ExtrapTermination(axis), (void *)&*ri));
+        }
+
+        stable_sort(mSplitCandidates->begin(), mSplitCandidates->end());
+}
+
+float VspBspTree::BestCostRatioHeuristics(const RayInfoContainer &rays,
+                                                                                  const AxisAlignedBox3 &box,
+                                                                                  const int pvsSize,
+                                                                                  int &axis,
+                                          float &position)
+{
+        //      AxisAlignedBox3 dirBox = GetDirBBox(node);
+        int raysBack;
+        int raysFront;
+        int pvsBack;
+        int pvsFront;
+
+        axis = box.Size().DrivingAxis();
+
+        SortSplitCandidates(rays, axis);
+
         // go through the lists, count the number of objects left and right
         // and evaluate the following cost funcion:
-        // C = ct_div_ci  + (ol + or)/queries
-        
-        int objectsLeft = 0, objectsRight = (int)polys.size();
-        
+        // C = ct_div_ci  + (ql*rl + qr*rr)/queries
+
+        int rl = 0, rr = (int)rays.size();
+        int pl = 0, pr = pvsSize;
+
         float minBox = box.Min(axis);
         float maxBox = box.Max(axis);
-        float boxArea = box.SurfaceArea();
-  
-        float minBand = minBox + mAxisAlignedSplitBorder * (maxBox - minBox);
-        float maxBand = minBox + (1.0f - mAxisAlignedSplitBorder) * (maxBox - minBox);
-        
+        float sizeBox = maxBox - minBox;
+
+        float minBand = minBox + 0.1f*(maxBox - minBox);
+        float maxBand = minBox + 0.9f*(maxBox - minBox);
+
+        float sum = rr*sizeBox;
         float minSum = 1e20f;
-        vector<SortableEntry>::const_iterator ci, ci_end = splitCandidates.end();
-
-        for(ci = splitCandidates.begin(); ci != ci_end; ++ ci) 
-        {
-                switch ((*ci).type) 
-                {
-                        case SortableEntry::POLY_MIN:
-                                ++ objectsLeft;
-                                break;
-                        case SortableEntry::POLY_MAX:
-                            -- objectsRight;
-                                break;
-                        default:
-                                break;
-                }
-                
-                if ((*ci).value > minBand && (*ci).value < maxBand) 
-                {
-                        AxisAlignedBox3 lbox = box;
-                        AxisAlignedBox3 rbox = box;
-                        lbox.SetMax(axis, (*ci).value);
-                        rbox.SetMin(axis, (*ci).value);
-
-                        float sum = objectsLeft * lbox.SurfaceArea() + 
-                                                objectsRight * rbox.SurfaceArea();
-      
-                        if (sum < minSum) 
+
+        Intersectable::NewMail();
+
+        // set all object as belonging to the fron pvs
+        for(RayInfoContainer::const_iterator ri = rays.begin(); ri != rays.end(); ++ ri)
+        {
+                if ((*ri).mRay->IsActive())
+                {
+                        Intersectable *object = (*ri).mRay->mTerminationObject;
+
+                        if (object)
+                                if (!object->Mailed())
+                                {
+                                        object->Mail();
+                                        object->mCounter = 1;
+                                }
+                                else
+                                        ++ object->mCounter;
+                }
+        }
+
+        Intersectable::NewMail();
+
+        for (vector<SortableEntry>::const_iterator ci = mSplitCandidates->begin();
+                ci < mSplitCandidates->end(); ++ ci)
+        {
+                VssRay *ray;
+
+                switch ((*ci).type)
+                {
+                        case SortableEntry::ERayMin:
+                                {
+                                        ++ rl;
+                                        ray = (VssRay *) (*ci).data;
+                                        Intersectable *object = ray->mTerminationObject;
+                                        if (object && !object->Mailed())
+                                        {
+                                                object->Mail();
+                                                ++ pl;
+                                        }
+                                        break;
+                                }
+                        case SortableEntry::ERayMax:
+                                {
+                                        -- rr;
+
+                                        ray = (VssRay *) (*ci).data;
+                                        Intersectable *object = ray->mTerminationObject;
+
+                                        if (object)
+                                        {
+                                                if (-- object->mCounter == 0)
+                                                -- pr;
+                                        }
+
+                                        break;
+                                }
+                }
+
+                // Note: sufficient to compare size of bounding boxes of front and back side?
+                if ((*ci).value > minBand && (*ci).value < maxBand)
+                {
+                        sum = pl*((*ci).value - minBox) + pr*(maxBox - (*ci).value);
+
+                        //  cout<<"pos="<<(*ci).value<<"\t q=("<<ql<<","<<qr<<")\t r=("<<rl<<","<<rr<<")"<<endl;
+                        // cout<<"cost= "<<sum<<endl;
+
+                        if (sum < minSum)
                         {
                                 minSum = sum;
                                 position = (*ci).value;
 
-                                objectsBack = objectsLeft;
-                                objectsFront = objectsRight;
+                                raysBack = rl;
+                                raysFront = rr;
+
+                                pvsBack = pl;
+                                pvsFront = pr;
+
                         }
                 }
         }
-  
-        const float oldCost = (float)polys.size();
-        const float newCost = mAxisAlignedCtDivCi + minSum / boxArea;
-        const float ratio = newCost / oldCost;
-
-
-#if 0
-  Debug << "====================" << endl;
-  Debug << "costRatio=" << ratio << " pos=" << position<<" t=" << (position - minBox)/(maxBox - minBox)
-      << "\t o=(" << objectsBack << "," << objectsFront << ")" << endl;
-#endif
-  return ratio;
-}
-
-bool VspBspTree::SelectAxisAlignedPlane(Plane3 &plane,
-                                        const PolygonContainer &polys) const
+
+        float oldCost = (float)pvsSize;
+        float newCost = mCtDivCi + minSum / sizeBox;
+        float ratio = newCost / oldCost;
+
+        //Debug << "costRatio=" << ratio << " pos=" << position << " t=" << (position - minBox) / (maxBox - minBox)
+        //     <<"\t q=(" << queriesBack << "," << queriesFront << ")\t r=(" << raysBack << "," << raysFront << ")" << endl;
+
+        return ratio;
+}
+
+
+float VspBspTree::SelectAxisAlignedPlane(Plane3 &plane, 
+                                                                                 const VspBspTraversalData &tData)
 {
         AxisAlignedBox3 box;
@@ -666 +719 @@
         
         // create bounding box of region
-        Polygon3::IncludeInBox(polys, box);
-        
-        int objectsBack = 0, objectsFront = 0;
+        RayInfoContainer::const_iterator ri, ri_end = tData.mRays->end();
+
+        for(ri = tData.mRays->begin(); ri < ri_end; ++ ri)
+                box.Include((*ri).ExtrapTermination());
+
         int axis = 0;
-        float costRatio = MAX_FLOAT;
-        Vector3 position;
-
-        //-- area subdivision
-        for (int i = 0; i < 3; ++ i) 
-        {
-                float p = 0;
-                const float r = BestCostRatio(polys, box, i, p, objectsBack, objectsFront);
+        const bool useCostHeuristics = false;
+
+        if (useCostHeuristics)
+        {
+                float position;
+
+                const float ratio = 
+                        BestCostRatioHeuristics(*tData.mRays,
+                                                                    box,
+                                                                        tData.mPvs,
+                                                                        axis,
+                                                                        position);
+
+                Vector3 normal(0,0,0); normal[axis] = 1;
+                plane = Plane3(normal, position);
+
+                return ratio;
+        }
+
+        //-- regular split
+        float nPosition[3];
+        float nCostRatio[3];
+        int bestAxis = -1;
+
+        bool mOnlyDrivingAxis = false;
+
+        const int sAxis = box.Size().DrivingAxis();
                 
-                if (r < costRatio)
-                {
-                        costRatio = r;
-                        axis = i;
-                        position = p;
-                }
-        }
-        
-        if (costRatio >= mTermMaxCostRatio)
-                return false;
-
-        Vector3 norm(0,0,0); norm[axis] = 1.0f;
-        plane = Plane3(norm, position);
-
-        return true;
-}
+        for (axis = 0; axis < 3; ++ axis)
+        {
+                if (!mOnlyDrivingAxis || axis == sAxis)
+                {
+                        if (!useCostHeuristics)
+                        {
+                                nPosition[axis] = (box.Min()[axis] + box.Max()[axis]) * 0.5f;
+                                Vector3 normal(0,0,0); normal[axis] = 1;
+
+                                nCostRatio[axis] = SplitPlaneCost(Plane3(normal, nPosition[axis]), tData);
+                        }
+                        
+                        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;
+                        }
+
+                }
+        }
+
+        //-- assign best axis
+        Vector3 normal(0,0,0); normal[bestAxis] = 1;
+        plane = Plane3(normal, nPosition[bestAxis]);
+
+        return nCostRatio[bestAxis];
+}
+
 
 bool VspBspTree::SelectPlane(Plane3 &plane, 
@@ -700 +793 @@
                                                          VspBspTraversalData &data)
 {
-        if ((mSplitPlaneStrategy & AXIS_ALIGNED) &&
-                ((int)data.mRays->size() > mTermMinRaysForAxisAligned))
-        {       // TODO: candidates should be rays
-                return SelectAxisAlignedPlane(plane, *data.mPolygons); 
-        }
-
         // simplest strategy: just take next polygon
         if (mSplitPlaneStrategy & RANDOM_POLYGON)
@@ -740 +827 @@
 }
 
+
 Plane3 VspBspTree::ChooseCandidatePlane(const RayInfoContainer &rays) const
 {       
@@ -752 +840 @@
         return Plane3(normal, pt);
 }
+
 
 Plane3 VspBspTree::ChooseCandidatePlane2(const RayInfoContainer &rays) const
@@ -822 +911 @@
         int maxIdx = (int)data.mPolygons->size();
         
+        float candidateCost;
+
         for (int i = 0; i < limit; ++ i)
         {
@@ -836 +927 @@
 
                 // evaluate current candidate
-                const float candidateCost = 
-                        SplitPlaneCost(poly->GetSupportingPlane(), data);
+                candidateCost = SplitPlaneCost(poly->GetSupportingPlane(), data);
 
                 if (candidateCost < lowestCost)
@@ -846 +936 @@
         }
         
+#if 0
         //-- choose candidate planes extracted from rays
         //-- different methods are available
@@ -851 +942 @@
         {
                 plane = ChooseCandidatePlane3(*data.mRays);
-                const float candidateCost = SplitPlaneCost(plane, data);
+                candidateCost = SplitPlaneCost(plane, data);
 
                 if (candidateCost < lowestCost)
@@ -858 +949 @@
                         lowestCost = candidateCost;
                 }
+        }
+#endif
+
+        // axis aligned splits
+        candidateCost = SelectAxisAlignedPlane(plane, data); 
+
+        if (candidateCost < lowestCost)
+        {
+                bestPlane = plane;      
+                lowestCost = candidateCost;
         }
 
@@ -880 +981 @@
 
 float VspBspTree::SplitPlaneCost(const Plane3 &candidatePlane, 
-                                                                 const VspBspTraversalData &data)
+                                                                 const VspBspTraversalData &data) const
 {
         float cost = 0;
@@ -1957 +2058 @@
         int merged = 0;
 
-        Debug << "mergecost: " << mergeQueue.top().GetMergeCost() / BspMergeCandidate::sOverallCost << " " << mMergeMaxCostRatio << endl;
-        Debug << "overall cost: " << BspMergeCandidate::sOverallCost << endl;
-
-        // use priority queue to merge leaves
+        //-- use priority queue to merge leaf pairs
         while (!mergeQueue.empty() && (vcSize > mMergeMinViewCells) &&
                    (mergeQueue.top().GetMergeCost() < 
                     mMergeMaxCostRatio * BspMergeCandidate::sOverallCost))
         {
-                Debug << "mergecost: " << mergeQueue.top().GetMergeCost() / BspMergeCandidate::sOverallCost << " " << mMergeMaxCostRatio << endl;
+                //Debug << "mergecost: " << mergeQueue.top().GetMergeCost() / BspMergeCandidate::sOverallCost << " " << mMergeMaxCostRatio << endl;
                 BspMergeCandidate mc = mergeQueue.top();
                 mergeQueue.pop();