Changeset 349 for trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.cpp

Timestamp:

10/26/05 19:18:30 (19 years ago)

Author:

mattausch

Message:

updated ray based subdivision

File:

• trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.cpp (modified) (29 diffs)

trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.cpp

@@ -43 +43 @@
         contribution for a minimum number splits in the tree.
 */
-float BspTree::sLeastSplitsTable[] = {0, 0, 1, 0};
+float BspTree::sLeastPolySplitsTable[] = {0, 0, 1, 0};
 /** Evaluates split plane classification with respect to the plane's 
         contribution for a balanced tree.
 */
-float BspTree::sBalancedTreeTable[] = {-1, 1, 0, 0};
+float BspTree::sBalancedPolysTable[] = {1, -1, 0, 0};
+
+/** Evaluates split plane classification with respect to the plane's 
+        contribution for a minimum number of ray splits.
+*/
+float BspTree::sLeastRaySplitsTable[] = {0, 0, 1, 1, 0};
+/** Evaluates split plane classification with respect to the plane's 
+        contribution for balanced rays.
+*/
+float BspTree::sBalancedRaysTable[] = {1, -1, 0, 0, 0};
 
 /****************************************************************/
@@ -158 +167 @@
 }
 
-void BspInterior::SplitRays(RayContainer &rays, 
-                                                        RayContainer &frontRays, 
-                                                        RayContainer &backRays)
-{
+int BspInterior::SplitRays(RayContainer &rays, 
+                                                   RayContainer &frontRays, 
+                                                   RayContainer &backRays,
+                                                   const AxisAlignedBox3 &box)
+{
+        int splits = 0;
+
         while (!rays.empty())
         {
@@ -172 +184 @@
         
                 // test with tree bounding box
-/*              if (!mBox.GetMinMaxT(*ray, &minT, &maxT))
+                if (!box.GetMinMaxT(*ray, &minT, &maxT))
                         continue;
+
                 if (minT < 0) // start ray from origin
                         minT = 0;
-*/
+
                 // bound ray
                 if ((ray->GetType() == Ray::LOCAL_RAY) && 
@@ -185 +198 @@
                 }
                 
-                int classification = ray->ClassifyPlane(mPlane, minT, maxT);
-                
+                const int classification = ray->ClassifyPlane(mPlane, minT, maxT);
+                
+                ray->SetId(classification);
+
                 switch (classification)
                 {
-                case Plane3::COINCIDENT:
+                case Ray::COINCIDENT:
                         break;
-                case Plane3::BACK_SIDE:
-                        ray->SetId(BACK_RAY);
+                case Ray::BACK:
                         backRays.push_back(ray);
                         break;
-                case Plane3::FRONT_SIDE:
-                        ray->SetId(FRONT_RAY);
+                case Ray::FRONT:
                         frontRays.push_back(ray);
                         break;
-                case Plane3::SPLIT:
-                        ray->SetId(SPLIT_RAY);
+                case Ray::FRONT_BACK:
+                        ray->SetId(Ray::FRONT_BACK);
+                        backRays.push_back(ray);
+                        ++ splits;                      
+                        break;
+                case Ray::BACK_FRONT:
                         frontRays.push_back(ray);
-                        backRays.push_back(ray);
-                        //extp = splitPlane->FindIntersection(ray.GetLoc(), extp, &maxt);
+                        ++ splits;
                         break;
                 default:
+                        Debug << "Should not come here" << endl;
                         break;
                 }
         }
+
+        return splits;
 }
 
@@ -215 +234 @@
                                                            PolygonContainer &backPolys, 
                                                            PolygonContainer &coincident,
-                                                           bool storePolys)
+                                                           const bool storePolys)
 {
         Polygon3 *splitPoly = NULL;
@@ -232 +251 @@
 
                 // classify polygon
-                int classification = poly->ClassifyPlane(mPlane);
+                const int classification = poly->ClassifyPlane(mPlane);
 
                 Polygon3 *front_piece = NULL;
@@ -241 +260 @@
                 switch (classification)
                 {
-                        case Plane3::COINCIDENT:
+                        case Polygon3::COINCIDENT:
                                 coincident.push_back(poly);
                                 break;                  
-                        case Plane3::FRONT_SIDE:        
+                        case Polygon3::FRONT_SIDE:      
                                 frontPolys.push_back(poly);
                                 break;
-                        case Plane3::BACK_SIDE:
+                        case Polygon3::BACK_SIDE:
                                 backPolys.push_back(poly);
                                 break;
-                        case Plane3::SPLIT:
+                        case Polygon3::SPLIT:
                                 front_piece = new Polygon3(poly->mParent);
                                 back_piece = new Polygon3(poly->mParent);
@@ -262 +281 @@
                                 ++ splits; // increase number of splits
 
-                                //-- inherit rays
-                                if (poly->mPiercingRays)
-                                        InheritRays(*poly, *front_piece, *back_piece);
-
+                                //-- inherit rays from parent polygon
+                                poly->InheritRays(*front_piece, *back_piece);
+                                Debug << "p: " << poly->mPiercingRays.size() << " f: " << front_piece->mPiercingRays.size() << " b: " << back_piece->mPiercingRays.size() << endl;
+                                
                                 // check if polygons still valid 
                                 if (front_piece->Valid())
@@ -280 +299 @@
                                 Debug << "split " << *poly << endl << *front_piece << endl << *back_piece << endl;
 #endif
-                                ProcessPolygon(&poly, storePolys);
-                                
+                                ProcessPolygon(&poly, storePolys);                      
                                 break;
                         default:
@@ -290 +308 @@
 
         return splits;
-}
-
-void BspInterior::InheritRays(const Polygon3 &poly, 
-                                                      Polygon3 &front_piece, 
-                                                      Polygon3 &back_piece)
-{
-        RayContainer *rays = poly.mPiercingRays;
-
-        RayContainer::const_iterator it, it_end = rays->end();
-
-        for (it = rays->begin(); it != it_end; ++ it)
-        {
-                switch((*it)->GetId())
-                {
-                case BACK_RAY:
-                        back_piece.GetPiercingRays()->push_back(*it);
-                        break;
-                case FRONT_RAY:
-                        front_piece.GetPiercingRays()->push_back(*it);
-                        break;
-                }
-        }
 }
 
@@ -664 +660 @@
                         if (it != facePolyMap.end()) 
                         {
-                                (*it).second->AddPiercingRay(ray);
+                                (*it).second->mPiercingRays.push_back(ray);
                         } 
                         else
@@ -670 +666 @@
                                 Polygon3 *poly = new Polygon3(face, obj->GetMesh());
                                 polys->push_back(poly);
-                                poly->AddPiercingRay(ray);
+                                poly->mPiercingRays.push_back(ray);
 
                                 facePolyMap[face] = poly;
@@ -842 +838 @@
                                                                         PolygonContainer &coincident,
                                                                         RayContainer &rays,
-                                                                        RayContainer &backRays,
-                                                                        RayContainer &frontRays)
+                                                                        RayContainer &frontRays,
+                                                                        RayContainer &backRays)
 {
         mStat.nodes += 2;
@@ -855 +851 @@
 #endif
         
-        // partition rays
-        interior->SplitRays(rays, frontRays, backRays);
+        // subdivide rays into front and back rays
+        interior->SplitRays(rays, frontRays, backRays, mBox);
         
         // split polygons with split plane
@@ -987 +983 @@
 }
 
+bool BspTree::SelectAxisAlignedPlane(Plane3 &plane, 
+                                                                         const PolygonContainer &polys) const
+{
+        AxisAlignedBox3 box;
+        box.Initialize();
+        
+        // create bounding box of region
+        Polygon3::IncludeInBox(polys, box);
+        
+        int objectsBack = 0, objectsFront = 0;
+        int axis = 0;
+        float costRatio = MAX_FLOAT;
+        Vector3 position;
+
+        //-- area subdivision
+        for (int i = 0; i < 3; ++ i) 
+        {
+                float p = 0;
+                float r = BestCostRatio(polys, box, i, p, objectsBack, objectsFront);
+                
+                if (r < costRatio)
+                {
+                        costRatio = r;
+                        axis = i;
+                        position = p;
+                }
+        }
+        
+        if (costRatio >= sMaxCostRatio)
+                return false;
+
+        Vector3 norm(0,0,0); norm[axis] = 1.0f;
+        plane = Plane3(norm, position);
+
+        return true;
+}
+
 Plane3 BspTree::SelectPlane(BspLeaf *leaf, 
                                                         PolygonContainer &polys, 
                                                         const RayContainer &rays)
 {
-        if (polys.size() == 0)
-        {
-                Debug << "Warning: No split candidate available\n";
-                return Plane3();
+        if (polys.empty())
+        {
+                Debug << "Warning: No autopartition polygon candidate available\n";
+        
+                // return axis aligned split
+                AxisAlignedBox3 box;
+                box.Initialize();
+        
+                // create bounding box of region
+                Polygon3::IncludeInBox(polys, box);
+
+                const int axis = box.Size().DrivingAxis();
+                const Vector3 position = (box.Min()[axis] + box.Max()[axis])*0.5f;
+
+                Vector3 norm(0,0,0); norm[axis] = 1.0f;
+                return Plane3(norm, position);
         }
 
@@ -1000 +1045 @@
                 ((int)polys.size() > sTermMaxPolysForAxisAligned))
         {
-                AxisAlignedBox3 box;
-                box.Initialize();
-        
-                // todo: area subdivision
-                Polygon3::IncludeInBox(polys, box);
-        
-                int objectsBack = 0, objectsFront = 0;
-                int axis = 0;
-                float costRatio = MAX_FLOAT;
-                Vector3 position;
-
-                for (int i = 0; i < 3; ++ i) 
-                {
-                        float p = 0;
-                        float r = BestCostRatio(polys, box, i, p, objectsBack, objectsFront);
-                        
-                        if (r < costRatio)
-                        {
-                                costRatio = r;
-                                axis = i;
-                                position = p;
-                        }
-                }
-                
-                if (costRatio < sMaxCostRatio)
-                {
-                        Vector3 norm(0,0,0); norm[axis] = 1.0f;
-                        return Plane3(norm, position);
-                }
+                Plane3 plane;
+                if (SelectAxisAlignedPlane(plane, polys))
+                        return plane;
         }
 
@@ -1074 +1093 @@
 int BspTree::GetNextCandidateIdx(int currentIdx, PolygonContainer &polys)
 {
-        int candidateIdx = Random(currentIdx --);
+        const int candidateIdx = Random(currentIdx --);
 
         // swap candidates to avoid testing same plane 2 times
@@ -1101 +1120 @@
         // needed for balanced view cells criterium
         ViewCell::NewMail();
-        int backId = ViewCell::sMailId;
+        const int backId = ViewCell::sMailId;
         ViewCell::NewMail();
-        int frontId = ViewCell::sMailId;
+        const int frontId = ViewCell::sMailId;
         ViewCell::NewMail();
-        int frontAndBackId = ViewCell::sMailId;
+        const int frontAndBackId = ViewCell::sMailId;
 
         PolygonContainer::const_iterator it, it_end = polys.end();
@@ -1111 +1130 @@
         for (it = polys.begin(); it != it_end; ++ it)
         {
-                int classification = (*it)->ClassifyPlane(candidatePlane);
+                const int classification = (*it)->ClassifyPlane(candidatePlane);
 
                 if (sSplitPlaneStrategy & BALANCED_POLYS)
-                        sumBalancedPolys += sBalancedTreeTable[classification];
+                        sumBalancedPolys += sBalancedPolysTable[classification];
                 
                 if (sSplitPlaneStrategy & LEAST_SPLITS)
-                        sumSplits += sLeastSplitsTable[classification];
+                        sumSplits += sLeastPolySplitsTable[classification];
 
                 if (sSplitPlaneStrategy & LARGEST_POLY_AREA)
                 {
-                        if (classification == Plane3::COINCIDENT)
+                        if (classification == Polygon3::COINCIDENT)
                                 sumPolyArea += (*it)->GetArea();
                         //totalArea += area;
@@ -1128 +1147 @@
                 if (sSplitPlaneStrategy & BLOCKED_RAYS)
                 {
-                        float blockedRays = (float)(*it)->GetPiercingRays()->size();
-                
-                        if (classification == Plane3::COINCIDENT)
+                        const float blockedRays = (float)(*it)->mPiercingRays.size();
+                
+                        if (classification == Polygon3::COINCIDENT)
                                 sumBlockedRays += blockedRays;
                         
@@ -1143 +1162 @@
                         // assure that we only count a view cell 
                         // once for the front and once for the back side of the plane
-                        if (classification == Plane3::FRONT_SIDE)
+                        if (classification == Polygon3::FRONT_SIDE)
                         {
                                 if ((viewCell->mMailbox != frontId) && 
@@ -1158 +1177 @@
                                 }
                         }
-                        else if (classification == Plane3::BACK_SIDE)
+                        else if (classification == Polygon3::BACK_SIDE)
                         {
                                 if ((viewCell->mMailbox != backId) &&
@@ -1190 +1209 @@
         if (sSplitPlaneStrategy & BLOCKED_RAYS)
                 if (totalBlockedRays != 0)
-                        val += sBlockedRaysFactor * sumBlockedRays / totalBlockedRays;
+                        val += sBlockedRaysFactor * (totalBlockedRays - sumBlockedRays) / totalBlockedRays;
 
         if (sSplitPlaneStrategy & BALANCED_VIEW_CELLS)
@@ -1218 +1237 @@
         
                 // test with tree bounding box
-                /*if (!mBox.GetMinMaxT(*ray, &minT, &maxT))
+                if (!mBox.GetMinMaxT(*ray, &minT, &maxT))
                         continue;
                 if (minT < 0) // start ray from origin
-                        minT = 0;*/
+                        minT = 0;
 
                 // bound ray
@@ -1231 +1250 @@
                 }
 
-                int classification = ray->ClassifyPlane(candidatePlane, minT, maxT);
+                const int classification = 
+                        ray->ClassifyPlane(candidatePlane, minT, maxT);
 
                 if (sSplitPlaneStrategy & LEAST_RAY_SPLITS)
                 {
-                        sumBalancedRays += sBalancedTreeTable[classification];
+                        sumBalancedRays += sBalancedRaysTable[classification];
                 }
                 
                 if (sSplitPlaneStrategy & BALANCED_RAYS)
                 {
-                        sumRaySplits += sLeastSplitsTable[classification];
+                        sumRaySplits += sLeastRaySplitsTable[classification];
                 }
         }
@@ -1332 +1352 @@
         environment->GetBoolValue("BspTree.storeSplitPolys", sStoreSplitPolys);
 
-        environment->GetFloatValue("BspTree.Construction.sideTolerance", Polygon3::sSideTolerance);
-        Polygon3::sSideToleranceSqrt = Polygon3::sSideTolerance * Polygon3::sSideTolerance;
+        environment->GetFloatValue("BspTree.Construction.sideTolerance", Vector3::sDistTolerance);
+        Vector3::sDistToleranceSqrt = Vector3::sDistTolerance * Vector3::sDistTolerance;
 
     Debug << "BSP max depth: " << sTermMaxDepth << endl;
@@ -1379 +1399 @@
                 {
                         BspInterior *interior = dynamic_cast<BspInterior *>(node);
+
                         nodeStack.push(interior->GetBack());
                         nodeStack.push(interior->GetFront());
@@ -1417 +1438 @@
         }
         
-#ifdef _DEBUG
+//#ifdef _DEBUG
         Debug << "BSP stats: "
                   << "Depth: " << data.mDepth << " (max: " << sTermMaxDepth << "), "
                   << "#polygons: " << (int)data.mPolygons->size() << " (max: " << sTermMaxPolygons << "), "
                   << "#rays: " << (int)data.mRays->size() << " (max: " << sTermMaxRays << ")" << endl;
-#endif
+//#endif
 }
 
@@ -1520 +1541 @@
                         entp = extp;
                         mint = maxt; // NOTE: need this?
+
+                         if (ray.GetType() == Ray::LINE_SEGMENT && mint > 1.0f)
+                                break;
+
                         BspRayTraversalData &s = tStack.top();