Changeset 822 for GTP/trunk/Lib/Vis/Preprocessing/src/VspBspTree.cpp

Timestamp:

04/26/06 08:11:30 (18 years ago)

Author:

mattausch

Message:

 

File:

• GTP/trunk/Lib/Vis/Preprocessing/src/VspBspTree.cpp (modified) (20 diffs)

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

@@ -130 +130 @@
         environment->GetFloatValue("VspBspTree.Construction.minBand", mMinBand);
         environment->GetFloatValue("VspBspTree.Construction.maxBand", mMaxBand);
+        environment->GetBoolValue("VspBspTree.Construction.useDrivingAxisForMaxCost", mUseDrivingAxisForMaxCost);
 
         //-- debug output
@@ -159 +160 @@
         Debug << "priority queue type: " << mNodePriorityQueueType << endl;
         Debug << "empty view cells merge: " << mEmptyViewCellsMergeAllowed << endl;
-        Debug << "octree: " << mCirculatingAxis << endl;
+        Debug << "circulating axis: " << mCirculatingAxis << endl;
         Debug << "minband: " << mMinBand << endl;
         Debug << "maxband: " << mMaxBand << endl;
-        
+        Debug << "use driving axis for max cost: " << mUseDrivingAxisForMaxCost << endl;
 
         Debug << "Split plane strategy: ";
@@ -728 +729 @@
                                 ++ mBspStats.polySplits;
 
+                        // if it was a kd node (i.e., a box) and the split axis is axis aligned, it is still a kd node
                         tFrontData.mIsKdNode = tBackData.mIsKdNode = (tData.mIsKdNode && (splitAxis < 3));
                         tFrontData.mAxis = tBackData.mAxis = splitAxis;
@@ -1219 +1221 @@
         const float minBox = box.Min(axis);
         const float maxBox = box.Max(axis);
+
         const float sizeBox = maxBox - minBox;
 
@@ -1239 +1242 @@
         float minSum = 1e20f;
 
+        
         // if no border can be found, take mid split
         position = minBox + 0.5f * sizeBox;
+        
+        // the relative cost ratio
+        float ratio = /*Limits::Infinity;*/99999999.0;
+        bool splitPlaneFound = false;
 
         Intersectable::NewMail();
@@ -1282 +1290 @@
         vector<SortableEntry>::const_iterator ci, ci_end = mSplitCandidates->end();
 
-        for (ci = mSplitCandidates->begin(); ci < ci_end; ++ ci)
+        for (ci = mSplitCandidates->begin(); ci != ci_end; ++ ci)
         {
                 VssRay *ray;
@@ -1325 +1333 @@
                 }
 
+                
+                
                 // Note: sufficient to compare size of bounding boxes of front and back side?
                 if (((*ci).value >= minBand) && ((*ci).value <= maxBand))
@@ -1330 +1340 @@
                         sum = pvsl * ((*ci).value - minBox) + pvsr * (maxBox - (*ci).value);
 
-                        //cout << "pos=" << (*ci).value << "\t pvs=(" <<  pvsl << "," << pvsr << ")" << endl;
-                        //cout<<"cost= "<<sum<<endl;
+                        //Debug  << "pos=" << (*ci).value << "\t pvs=(" <<  pvsl << "," << pvsr << ")" << endl;
+                        //Debug << "cost= " << sum << endl;
 
                         if (sum < minSum)
                         {
+                                splitPlaneFound = true;
+
                                 minSum = sum;
                                 position = (*ci).value;
@@ -1344 +1356 @@
         }
         
-        Debug << "pos: " << position << " sizebox: " << sizeBox << " pvs: " << pvsSize << endl;
-
+        
         // -- compute cost
         const int lowerPvsLimit = mViewCellsManager->GetMinPvsSize();
@@ -1362 +1373 @@
         const float newRenderCost = penaltyFront * pFront + penaltyBack * pBack;
 
-        float ratio = mPvsFactor * newRenderCost / (oldRenderCost + Limits::Small);
-
-        //Debug << "costRatio=" << ratio << " pos=" << position << " t=" << (position - minBox) / (maxBox - minBox)
-        //     <<"\t q=(" << queriesBack << "," << queriesFront << ")\t r=(" << raysBack << "," << raysFront << ")" << endl;
+        if (splitPlaneFound)
+        {
+                ratio = mPvsFactor * newRenderCost / (oldRenderCost + Limits::Small);
+        }
+        //if (axis != 1)
+        //Debug << "axis=" << axis << " costRatio=" << ratio << " pos=" << position << " t=" << (position - minBox) / (maxBox - minBox)
+         //    <<"\t pb=(" << pvsBack << ")\t pf=(" << pvsFront << ")" << endl;
 
         return ratio;
@@ -1388 +1402 @@
         BspNodeGeometry *nBackGeom[3];
 
+        // set to NULL, so I can find out which gemetry was stored
         for (int i = 0; i < 3; ++ i)
         {
@@ -1394 +1409 @@
         }
 
-        int bestAxis = -1;
-
         // create bounding box of node geometry
         AxisAlignedBox3 box;
@@ -1402 +1415 @@
         if (1)
         {
+                // get bounding box from geometry
                 tData.mGeometry->GetBoundingBox(box);
         }
@@ -1414 +1428 @@
 
         int sAxis = 0;
+        int bestAxis;
+
+        if (mUseDrivingAxisForMaxCost)
+                bestAxis = box.Size().DrivingAxis();
+        else
+                bestAxis = -1;
+
+        // mximum cost ratio for axis to be valid:
+        // if exceeded, spatial mid split is used instead
+        const float maxCostRatio = 0.9f;
+
         // hack : subdivide along driving axis up to certain depth
         int maxDepthForDrivingAxis = 0;
+        const maxCostRatioForHeur = 0.99;
 
     const bool useSpecialAxis = mOnlyDrivingAxis || mUseRandomAxis || 
-                mCirculatingAxis || (tData.mDepth < maxDepthForDrivingAxis);
+                mCirculatingAxis;
 
 
@@ -1426 +1452 @@
         else if (mCirculatingAxis)
                 sAxis = (tData.mAxis + 1) % 3;
-        else if (mOnlyDrivingAxis || (tData.mDepth < maxDepthForDrivingAxis))
+        else if (mOnlyDrivingAxis)
                 sAxis = box.Size().DrivingAxis();
 
@@ -1433 +1459 @@
         //Debug << "axis: " << sAxis << " drivingaxis: " << box.Size().DrivingAxis();
 
-        for (axis = 0; axis < 3; ++ axis)
+        for (axis = 0; axis < 3 ; ++ axis)
         {
                 if (!useSpecialAxis || (axis == sAxis))
                 {
-                        if (!mUseCostHeuristics)
-                        {
+                        //-- place split plane using heuristics
+
+                        if (mUseCostHeuristics)
+                        {
+                                nCostRatio[axis] =
+                                        BestCostRatioHeuristics(*tData.mRays,
+                                                                                    box,
+                                                                                        tData.mPvs,
+                                                                                        axis,
+                                                                                        nPosition[axis]);                       
+                        }
+                        
+                        //-- split plane position is spatial median
+                        //-- use median split if cost ratio very low as
+                        //-- there are not enough visibility cues
+
+                        else //if (!mUseCostHeuristics || (nCostRatio[axis] > maxCostRatioForHeur))
+                        {
+
                                 nPosition[axis] = (box.Min()[axis] + box.Max()[axis]) * 0.5f;
                                 Vector3 normal(0,0,0); normal[axis] = 1.0f;
 
                                 // allows faster split because we have axis aligned kd tree boxes
-                                if (0 && isKdNode)
+                                if (isKdNode)
                                 {
                                         nCostRatio[axis] = EvalAxisAlignedSplitCost(tData,
@@ -1455 +1498 @@
                                         
                                         // create back geometry from box
+                                        // NOTE: the geometry is saved when possible
                                         pos = box.Max(); pos[axis] = nPosition[axis];
                                         AxisAlignedBox3 bBox(box.Min(), pos);
@@ -1462 +1506 @@
                                         nBackGeom[axis] = new BspNodeGeometry(fPolys);
         
-                                        // create front geometry from box
+                                        //-- create front geometry from box
                                         pos = box.Min(); pos[axis] = nPosition[axis];
                                         AxisAlignedBox3 fBox(pos, box.Max());
@@ -1481 +1525 @@
                                 }
                         }
-                        else
-                        {
-                                nCostRatio[axis] =
-                                        BestCostRatioHeuristics(*tData.mRays,
-                                                                                    box,
-                                                                                        tData.mPvs,
-                                                                                        axis,
-                                                                                        nPosition[axis]);
-                        }
-
-                        if (bestAxis == -1)
-                        {
-                                bestAxis = axis;
-                        }
-                        else if (nCostRatio[axis] < nCostRatio[bestAxis])
-                        {
-                                bestAxis = axis;
-                        }
-
+                                                
+
+                        if (!mUseDrivingAxisForMaxCost)
+                        {
+                                if (bestAxis == -1)
+                                {
+                                        bestAxis = axis;
+                                }
+                                else if (nCostRatio[axis] < nCostRatio[bestAxis])
+                                {
+                                        bestAxis = axis;
+                                }
+                        }
+                        else 
+                        {
+                                 // NOTE: takes longest axis split if cost ratio exceeds threshold
+                                if (nCostRatio[axis] < min(maxCostRatio, nCostRatio[bestAxis]))
+                                {
+                                        bestAxis = axis;
+                                }
+                                //else if (nCostRatio[axis] < nCostRatio[bestAxis])
+                                //      Debug << "warning!! different path taken: " << axis << " " << bestAxis << endl;
+                                
+                        }
                 }
         }
@@ -1520 +1569 @@
         plane = Plane3(normal, nPosition[bestAxis]);
 
+        //Debug << "best axis: " << bestAxis << " pos " << nPosition[bestAxis] << endl;
+        //Debug << "!!!!!!!!!!!!!!" << endl;
         return nCostRatio[bestAxis];
 }