Changeset 1084

Timestamp:

07/06/06 08:55:06 (18 years ago)

Author:

mattausch

Message:

 

Location:

GTP/trunk/Lib/Vis/Preprocessing/src

Files:

• ViewCellBsp.h (modified) (1 diff)
• VspBspTree.h (modified) (1 diff)
• VspOspTree.cpp (modified) (11 diffs)
• VspOspTree.h (modified) (7 diffs)

GTP/trunk/Lib/Vis/Preprocessing/src/ViewCellBsp.h

@@ -882 +882 @@
                                                 int &objectsFront) const;
         
-        /** Sorts split candidates for surface area heuristics for axis aligned splits.
+        /** Sorts split candidates for cost heuristics using axis aligned splits.
                 @param polys the input for choosing split candidates
                 @param axis the current split axis

GTP/trunk/Lib/Vis/Preprocessing/src/VspBspTree.h

@@ -559 +559 @@
                                                                  const bool useKdSplit);
 
-        /** Sorts split candidates for surface area heuristics for axis aligned splits.
+        /** Sorts split candidates for cost heuristics using axis aligned splits.
                 @param polys the input for choosing split candidates
                 @param axis the current split axis

GTP/trunk/Lib/Vis/Preprocessing/src/VspOspTree.cpp

@@ -399 +399 @@
         Debug << "maxband: " << mMaxBand << endl;
         Debug << "pvs count method: " << mPvsCountMethod << endl;
-        
+
 
         mSplitCandidates = new vector<SortableEntry>;
@@ -805 +805 @@
         float pos;
 
-        // insert all queries
+        //-- insert all queries
         for (RayInfoContainer::const_iterator ri = rays.begin(); ri < rays.end(); ++ ri)
         {
@@ -2559 +2559 @@
         Environment::GetSingleton()->GetFloatValue("VspTree.Construction.maxBand", mMaxBand);
         
+        mSplitBorder = 0.1f;
+
 
         //-- debug output
@@ -2740 +2742 @@
 
 void OspTree::EvalSplitCandidate(OspTraversalData &tData,
-                                                                 OspSplitCandidate &splitData)
+                                                                 OspSplitCandidate &splitCandidate)
 {
         float frontProb;
@@ -2748 +2750 @@
 
         // compute locally best split plane
-        const bool success = false;
-#if TODO
-        SelectPlane(tData, splitData.mSplitPlane,
-                                frontData.mProbability, backData.mProbability);
+        const bool success = 
+                SelectSplitPlane(tData, splitCandidate.mSplitPlane,     frontProb, backProb);
 
         //TODO
@@ -2758 +2758 @@
         splitData.mParentData = tData;
         splitData.mMaxCostMisses = success ? tData.mMaxCostMisses : tData.mMaxCostMisses + 1;
-#endif
 }
 
@@ -2842 +2841 @@
 
 
-/*
-float OspTree::EvalLocalCostHeuristics(const RayInfoContainer &rays,
+float OspTree::EvalLocalCostHeuristics(KdLeaf *node,
                                                                            const AxisAlignedBox3 &box,
-                                                                           int pvsSize,
                                                                            const int axis,
-                                                                           float &position)
-{
+                                                                           float &position,
+                                                                           int &objectsBack,
+                                                                           int &objectsFront)
+{
+        
+        SortSplitCandidates(node, 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 pvsSize = PrepareHeuristics(node->mObjects);;
+        int pvsl = 0, pvsr = pvsSize;
+  
         const float minBox = box.Min(axis);
         const float maxBox = box.Max(axis);
 
         const float sizeBox = maxBox - minBox;
-
-        const float minBand = minBox + mMinBand * sizeBox;
-        const float maxBand = minBox + mMaxBand * sizeBox;
-
-        SortSplitCandidates(rays, axis, minBand, maxBand);
-
-        // prepare the sweep 
-        // (note: returns pvs size, so there would be no need 
-        // to give pvs size as argument)
-        pvsSize = PrepareHeuristics(rays);
-
-        Debug << "here45 pvs: " << pvsSize << endl;
-
-        // go through the lists, count the number of objects left and right
-        // and evaluate the following cost funcion:
-        // C = ct_div_ci  + (ql*rl + qr*rr)/queries
-
-        int pvsl = 0;
-        int pvsr = pvsSize;
-
-        int pvsBack = pvsl;
-        int pvsFront = pvsr;
-
-        float sum = (float)pvsSize * sizeBox;
-        float minSum = 1e20f;
-
-        
+        
+                        
         // if no good split can be found, take mid split
         position = minBox + 0.5f * sizeBox;
@@ -2886 +2870 @@
         float ratio = 99999999.0f;
         bool splitPlaneFound = false;
-
-        Intersectable::NewMail();
-        KdLeaf::NewMail();
-
+  
+        float minBand = minBox + mSplitBorder * (maxBox - minBox);
+        float maxBand = minBox + (1.0f - mSplitBorder) * (maxBox - minBox);
+
+    float minSum = 1e20f;
+
+        int pvsBack = pvsl;
+        int pvsFront = pvsr;
+
+        float sum = (float)pvsSize * sizeBox;
 
         vector<SortableEntry>::const_iterator ci, ci_end = mSplitCandidates->end();
@@ -2946 +2936 @@
         return ratio;
 }
-*/
-
-float OspTree::EvalLocalCostHeuristics(BspLeaf *node,
-                                                                           const AxisAlignedBox3 &box,
-                                                                           const int axis,
-                                                                           float &position,
-                                                                           int &objectsBack,
-                                                                           int &objectsFront)
-{
-        
-        /*SortSplitCandidates(node, 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
-
-        float totalIntersections = 0.0f;
-        
-        vector<SortableEntry>::const_iterator ci, ci_end = splitCandidates.end();
-
-        for(ci = splitCandidates->begin(); ci != ci_end; ++ ci)
-        {
-                 if ((*ci).type == SortableEntry::BOX_MIN) 
-                 {
-                         totalIntersections += (*ci).intersectable->IntersectionComplexity();
-                 }
-        }
-        
-        float intersectionsLeft = 0;
-        float intersectionsRight = totalIntersections;
-
-        
-        int objectsLeft = 0, objectsRight = (int)node->mObjects.size();
-  
-        float minBox = box.Min(axis);
-        float maxBox = box.Max(axis);
-        
-        float boxArea = box.SurfaceArea();
-  
-        float minBand = minBox + mSplitBorder*(maxBox - minBox);
-        float maxBand = minBox + (1.0f - mSplitBorder)*(maxBox - minBox);
-
-    float minSum = 1e20f;
-  
-        for(ci = splitCandidates->begin(); ci != ci_end; ++ ci)
-        {
-                EvalPvsIncr(ci, pvsl, pvsr);
-
-                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;
-                        
-                        if (mSahUseFaces)
-                                sum = intersectionsLeft*lbox.SurfaceArea() + intersectionsRight*rbox.SurfaceArea();
-                        else
-                                sum = objectsLeft*lbox.SurfaceArea() + objectsRight*rbox.SurfaceArea();
-      
-                        //      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;
-                        }
-                }
-        }
-  
-        float oldCost = mSahUseFaces ? totalIntersections : node->mObjects.size();
-        float newCost = mCt_div_ci + minSum/boxArea;
-        float ratio = newCost/oldCost;
-  
-#if 0
-        cout<<"===================="<<endl;
-        cout<<"costRatio="<<ratio<<" pos="<<position<<" t="<<(position - minBox)/(maxBox - minBox)
-                <<"\t o=("<<objectsBack<<","<<objectsFront<<")"<<endl;
-#endif
-        
-        return ratio;
-        */
-        return 0;
-}
-
-
-void OspTree::SortSplitCandidates(const RayInfoContainer &rays,
-                                                                  const int axis, 
-                                                                  float minBand, 
-                                                                  float maxBand)
-{
-        // TODO
+
+void OspTree::SortSplitCandidates(KdLeaf *node, const int axis)
+{
+        mSplitCandidates->clear();
+
+        int requestedSize = 2*(int)node->mObjects.size();
+        
+        // creates a sorted split candidates array
+        if (mSplitCandidates->capacity() > 500000 &&
+                requestedSize < (int)(mSplitCandidates->capacity()/10)) 
+        {
+                delete mSplitCandidates;
+                mSplitCandidates = new vector<SortableEntry>;
+        }
+
+        mSplitCandidates->reserve(requestedSize);
+        
+        ObjectContainer::const_iterator mi, mi_end = node->mObjects.end();
+
+        // insert all queries 
+        for(mi = node->mObjects.begin(); mi != mi_end; ++ mi) 
+        {
+                AxisAlignedBox3 box = (*mi)->GetBox();
+
+                mSplitCandidates->push_back(SortableEntry(SortableEntry::BOX_MIN,
+                                        box.Min(axis), *mi));
+
+
+                mSplitCandidates->push_back(SortableEntry(SortableEntry::BOX_MAX,
+                                        box.Max(axis), *mi));
+        }
+
+        stable_sort(mSplitCandidates->begin(), mSplitCandidates->end());
 }
 
@@ -3075 +2999 @@
 
 
-int OspTree::PrepareHeuristics(const RayInfoContainer &rays)
+int OspTree::PrepareHeuristics(const ObjectContainer &objects)
 {       
         Intersectable::NewMail();
-        KdNode::NewMail();
+        ViewCell::NewMail();
 
         int pvsSize = 0;
 
-        RayInfoContainer::const_iterator ri, ri_end = rays.end();
-
-        //-- set all kd nodes as belonging to the front pvs
-
-        for (ri = rays.begin(); ri != ri_end; ++ ri)
-        {
-                Intersectable *oObject = (*ri).mRay->mOriginObject;
-
-                if (oObject)
-                {
-                        pvsSize += PrepareHeuristics(oObject);          
-                }
-
-                Intersectable *tObject = (*ri).mRay->mTerminationObject;
-
-                if (tObject)
-                {
-                        pvsSize += PrepareHeuristics(tObject);  
-                }
+        ObjectContainer::const_iterator oit, oit_end = objects.end();
+
+        //-- set all pvs as belonging to the front pvs
+        for (oit = objects.begin(); oit != oit_end; ++ oit)
+        {
+                Intersectable *obj = *oit;
+
+                pvsSize += PrepareHeuristics(obj);              
         }
 
@@ -3156 +3069 @@
                 }
         }
+}
+
+
+float OspTree::SelectSplitPlane(const VspTraversalData &tData,
+                                                                AxisAlignedPlane &plane,
+                                                                float &pFront,
+                                                                float &pBack)
+{
+        float nPosition[3];
+        float nCostRatio[3];
+        float nProbFront[3];
+        float nProbBack[3];
+
+        // create bounding box of node geometry
+        AxisAlignedBox3 box = tData.mBoundingBox;
+                
+        int sAxis = 0;
+        int bestAxis = -1;
+
+        if (mOnlyDrivingAxis)
+        {
+                sAxis = box.Size().DrivingAxis();
+        }
+
+        //sAxis = 2;
+        for (int axis = 0; axis < 3; ++ axis)
+        {
+                if (!mOnlyDrivingAxis || (axis == sAxis))
+                {
+                        //-- place split plane using heuristics
+
+                        if (mUseCostHeuristics)
+                        {
+                                nCostRatio[axis] =
+                                        EvalLocalCostHeuristics(*tData.mRays,
+                                                                                        box,
+                                                                                        tData.mPvs,
+                                                                                        axis,
+                                                                                        nPosition[axis]);                       
+                        }
+                        else //-- split plane position is spatial median
+                        {
+                                nPosition[axis] = (box.Min()[axis] + box.Max()[axis]) * 0.5f;
+
+                                nCostRatio[axis] = EvalLocalSplitCost(tData,
+                                                                                                          box,
+                                                                                                          axis,
+                                                                                                          nPosition[axis],
+                                                                                                          nProbFront[axis], 
+                                                                                                          nProbBack[axis]);
+                        }
+                                                
+                        if (bestAxis == -1)
+                        {
+                                bestAxis = axis;
+                        }
+                        else if (nCostRatio[axis] < nCostRatio[bestAxis])
+                        {
+                                bestAxis = axis;
+                        } 
+                }
+        }
+
+
+        //-- assign values
+        
+        plane.mAxis = bestAxis;
+        // split plane position
+    plane.mPosition = nPosition[bestAxis];
+
+        pFront = nProbFront[bestAxis];
+        pBack = nProbBack[bestAxis];
+
+        //Debug << "val: " << nCostRatio[bestAxis] << " axis: " << bestAxis << endl;
+        return nCostRatio[bestAxis];
 }
 

GTP/trunk/Lib/Vis/Preprocessing/src/VspOspTree.h

@@ -871 +871 @@
                 The split candidates are generated on possible visibility
                 events (i.e., where ray segments intersect the ray boundaries).
-                The sorted candidates are needed to compute the SAH.
+                The sorted candidates are needed to compute the heuristics.
 
                 @param polys the input for choosing split candidates
@@ -882 +882 @@
                                                          float maxBand);
 
-        /** Computes pvs increase with respect to the previous pvs for SAH.
+        /** Computes pvs increase with respect to the previous pvs for heuristics.
         */
         int GetPvsIncr(Intersectable *object, const KdPvsMap &activeNodes);
@@ -910 +910 @@
         void AddContriToPvs(KdLeaf *leaf, int &pvs) const;
 
-        /** Prepares objects for SAH.
+        /** Prepares objects for the heuristics.
                 @returns pvs size of the ray container
         */
@@ -1438 +1438 @@
                                           float &pBack);
 
-        /** Sorts split candidates for surface area heuristics for axis aligned splits.
-                @param polys the input for choosing split candidates
+        /** Sorts split candidates for cost heuristics using axis aligned splits.
+                @param node the current node
                 @param axis the current split axis
-                @param splitCandidates returns sorted list of split candidates
-        */
-        void SortSplitCandidates(const RayInfoContainer &rays, 
-                                                         const int axis, 
-                                                         float minBand, 
-                                                         float maxBand);
+        */
+        void SortSplitCandidates(KdLeaf *node, const int axis);
 
         /** Computes best cost for axis aligned planes.
         */
-/*      float EvalLocalCostHeuristics(const RayInfoContainer &rays,
-                                                                  const AxisAlignedBox3 &box,
-                                                                  const int pvsSize,
-                                                                  const int axis,
-                                                                  float &position);
-*/
-        float EvalLocalCostHeuristics(BspLeaf *node,
+        float EvalLocalCostHeuristics(KdLeaf *node,
                 const AxisAlignedBox3 &box,
                 const int axis,
@@ -1504 +1494 @@
         inline bool GlobalTerminationCriteriaMet(const OspTraversalData &data) const;
 
+        float SelectSplitPlane(const VspTraversalData &tData,
+                                                                AxisAlignedPlane &plane,
+                                                                float &pFront,
+                                                                float &pBack);
         /** Adds ray sample contributions to the PVS.
                 @param sampleContributions the number contributions of the samples
@@ -1543 +1537 @@
         void AddContriToPvs(Intersectable *object, int &pvs) const;
 
-        /** Prepares objects for SAH.
-                @returns pvs size of the ray container
-        */
-        int PrepareHeuristics(const RayInfoContainer &rays);
+        /** Prepares objects for the cost heuristics.
+                @returns pvs size of the node
+        */
+        int PrepareHeuristics(const ObjectContainer &objects);
 
         int PrepareHeuristics(Intersectable *object);
@@ -1631 +1625 @@
         int mCreatedViewCells;
 
+        float mSplitBorder;
+
+
 private: