Changeset 302 for trunk


Ignore:
Timestamp:
09/29/05 18:42:04 (19 years ago)
Author:
mattausch
Message:

added surface area heuristic for bsp

Location:
trunk/VUT/GtpVisibilityPreprocessor
Files:
6 edited

Legend:

Unmodified
Added
Removed
  • trunk/VUT/GtpVisibilityPreprocessor/scripts/default.env

    r301 r302  
    7676        #splitPlaneStrategy 12 
    7777        #axis aligned + vertical axis 
    78         #splitPlaneStrategy 66 
     78        splitPlaneStrategy 66 
    7979        # axis aligned + balanced view cells 
    80         splitPlaneStrategy 18 
     80        # splitPlaneStrategy 18 
    8181        # largest polygon area 
    8282        #splitPlaneStrategy 32 
     
    8989        maxViewCells 999999 
    9090        Termination { 
    91                 maxPolysForAxisAligned 20 
     91                maxPolysForAxisAligned 200 
    9292                maxPolygons 0 
    9393                maxDepth 100 
  • trunk/VUT/GtpVisibilityPreprocessor/src/AxisAlignedBox3.cpp

    r295 r302  
    657657{ 
    658658  Vector3 ext = mMax - mMin; 
     659  
    659660  return 2.0 * (ext.x * ext.y + 
    660661                ext.x * ext.z + 
  • trunk/VUT/GtpVisibilityPreprocessor/src/AxisAlignedBox3.h

    r295 r302  
    198198  virtual float SurfaceArea() const; 
    199199  virtual float GetVolume() const { 
    200     return (mMax.x -mMin.x) * (mMax.y -mMin.y) * (mMax.z - mMin.z); 
     200    return (mMax.x - mMin.x) * (mMax.y - mMin.y) * (mMax.z - mMin.z); 
    201201  } 
    202202 
  • trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.cpp

    r301 r302  
    1919int BspTree::sConstructionMethod = VIEW_CELLS; 
    2020int BspTree::sTermMaxPolysForAxisAligned = 50; 
     21 
     22float BspTree::sCt_div_ci = 1.0f; 
     23float BspTree::sSplitBorder = 1.0f; 
     24float BspTree::sMaxCostRatio = 0.9; 
    2125 
    2226//-- factors for bsp tree split plane heuristics 
     
    581585        if ((tData.mPolygons->size() <= sTermMaxPolygons) || (tData.mDepth >= sTermMaxDepth)) 
    582586        { 
    583 #ifdef _DEBUG 
     587//#ifdef _DEBUG 
    584588                Debug << "subdivision terminated at depth " << tData.mDepth << ", #polys: " << (int)tData.mPolygons->size() << endl; 
    585 #endif 
     589//#endif 
    586590 
    587591                EvaluateLeafStats(tData); 
     
    691695 
    692696        // add the new nodes to the tree + select subdivision plane 
    693         BspInterior *interior = new BspInterior(SelectPlane(*polys));  
     697        BspInterior *interior = new BspInterior(SelectPlane(leaf, *polys));  
    694698 
    695699#ifdef _DEBUG 
     
    719723} 
    720724 
    721 Plane3 BspTree::SelectPlane(const PolygonContainer &polys)  const 
     725void BspTree::SortSplitCandidates(const PolygonContainer &polys,  
     726                                                                  const int axis,  
     727                                                                  vector<SortableEntry> &splitCandidates) const 
     728{ 
     729  splitCandidates.clear(); 
     730   
     731  int requestedSize = 2 * (int)polys.size(); 
     732  // creates a sorted split candidates array   
     733  splitCandidates.reserve(requestedSize); 
     734   
     735  PolygonContainer::const_iterator it, it_end = polys.end(); 
     736 
     737  AxisAlignedBox3 box; 
     738 
     739  // insert all queries  
     740  for(it = polys.begin(); it != it_end; ++ it) 
     741  { 
     742          box.Initialize(); 
     743          box.Include(*(*it)); 
     744           
     745          splitCandidates.push_back(SortableEntry(SortableEntry::POLY_MIN, box.Min(axis), *it)); 
     746      splitCandidates.push_back(SortableEntry(SortableEntry::POLY_MAX, box.Max(axis), *it)); 
     747  } 
     748   
     749  stable_sort(splitCandidates.begin(), splitCandidates.end()); 
     750} 
     751 
     752 
     753float BspTree::BestCostRatio(const PolygonContainer &polys, 
     754                                                         const AxisAlignedBox3 &box, 
     755                                                         const int axis, 
     756                                                         float &position, 
     757                                                         int &objectsBack, 
     758                                                         int &objectsFront) const 
     759{ 
     760        vector<SortableEntry> splitCandidates; 
     761 
     762        SortSplitCandidates(polys, axis, splitCandidates); 
     763         
     764        // go through the lists, count the number of objects left and right 
     765        // and evaluate the following cost funcion: 
     766        // C = ct_div_ci  + (ol + or)/queries 
     767         
     768        int objectsLeft = 0, objectsRight = (int)polys.size(); 
     769         
     770        float minBox = box.Min(axis); 
     771        float maxBox = box.Max(axis); 
     772        float boxArea = box.SurfaceArea(); 
     773   
     774        float minBand = minBox + sSplitBorder * (maxBox - minBox); 
     775        float maxBand = minBox + (1.0f - sSplitBorder) * (maxBox - minBox); 
     776         
     777        float minSum = 1e20f; 
     778        vector<SortableEntry>::const_iterator ci, ci_end = splitCandidates.end(); 
     779 
     780        for(ci = splitCandidates.begin(); ci != ci_end; ++ ci)  
     781        { 
     782                switch ((*ci).type)  
     783                { 
     784                        case SortableEntry::POLY_MIN: 
     785                                ++ objectsLeft; 
     786                                break; 
     787                        case SortableEntry::POLY_MAX: 
     788                            -- objectsRight; 
     789                                break; 
     790                        default: 
     791                                break; 
     792                } 
     793                 
     794                if ((*ci).value > minBand && (*ci).value < maxBand)  
     795                { 
     796                        AxisAlignedBox3 lbox = box; 
     797                        AxisAlignedBox3 rbox = box; 
     798                        lbox.SetMax(axis, (*ci).value); 
     799                        rbox.SetMin(axis, (*ci).value); 
     800 
     801                        float sum = objectsLeft * lbox.SurfaceArea() +  
     802                                                objectsRight * rbox.SurfaceArea(); 
     803       
     804                        if (sum < minSum)  
     805                        { 
     806                                minSum = sum; 
     807                                position = (*ci).value; 
     808 
     809                                objectsBack = objectsLeft; 
     810                                objectsFront = objectsRight; 
     811                        } 
     812                } 
     813        } 
     814   
     815        float oldCost = (float)polys.size(); 
     816        float newCost = sCt_div_ci + minSum / boxArea; 
     817        float ratio = newCost / oldCost; 
     818 
     819 
     820#if 0 
     821  Debug << "====================" << endl; 
     822  Debug << "costRatio=" << ratio << " pos=" << position<<" t=" << (position - minBox)/(maxBox - minBox) 
     823      << "\t o=(" << objectsBack << "," << objectsFront << ")" << endl; 
     824#endif 
     825  return ratio; 
     826} 
     827 
     828Plane3 BspTree::SelectPlane(BspLeaf *leaf, const PolygonContainer &polys)  const 
    722829{ 
    723830        if (polys.size() == 0) 
     
    741848                Vector3 position; 
    742849 
    743                 for (int i=0; i < 3; i++)  
     850                for (int i = 0; i < 3; ++ i)  
    744851                { 
    745852                        float p = 0; 
    746                         float r = 0;/*BestCostRatio(leaf, 
    747                                                                         box, 
    748                                                                         i, 
    749                                                                         p, 
    750                                                                         objectsBack, 
    751                                                                         objectsFront);*/ 
     853                        float r = BestCostRatio(polys, box, i, p, objectsBack, objectsFront); 
     854                         
    752855                        if (r < costRatio) 
    753856                        { 
     
    758861                } 
    759862                 
    760                 //if (costRatio > mMaxCostRatio) axis = -1; 
    761                 Vector3 norm(0,0,0); norm[axis] = 1.0f; 
    762                 return Plane3(norm, position); 
    763  
     863                if (costRatio < sMaxCostRatio) 
     864                { 
     865                        Vector3 norm(0,0,0); norm[axis] = 1.0f; 
     866                        return Plane3(norm, position); 
     867                } 
    764868                /*int axis = box.Size().DrivingAxis(); 
    765869                Vector3 norm(0,0,0); norm[axis] = 1; 
    766870                Vector3 pt = (box.Min()[axis] + box.Max()[axis]) * 0.5f;*/ 
    767                 //Debug << "splitting axis aligned" << endl; 
     871                 
    768872                //return Plane3(norm, pt); 
    769873        } 
     
    775879        } 
    776880 
    777         /*if (sSplitPlaneStrategy & VERTICAL_AXIS) 
    778         { 
    779                 const float dot_thres = 0.999; 
    780                 PolygonContainer::const_iterator it, it_end = polys->end(); 
    781                  
    782                 for (it = polys->begin(); it != it_end; ++ it) 
    783                 { 
    784                         if (DotProd((*it)->GetSupportingPlane().mNormal, mVerticalAxis) > dot_thres) 
    785                                 return (*it)->GetSupportingPlane(); 
    786                 } 
    787         }*/ 
    788          
    789881        // use heuristics to find appropriate plane 
    790882        return SelectPlaneHeuristics(polys, sMaxCandidates); 
     
    9321024        environment->GetIntValue("BspTree.maxCandidates", sMaxCandidates); 
    9331025        environment->GetIntValue("BspTree.splitPlaneStrategy", sSplitPlaneStrategy); 
     1026 
     1027        // need kdtree criteria for axis aligned split 
     1028        environment->GetFloatValue("MeshKdTree.Termination.ct_div_ci", sCt_div_ci); 
     1029        environment->GetFloatValue("MeshKdTree.splitBorder", sSplitBorder); 
     1030        environment->GetFloatValue("MeshKdTree.Termination.maxCostRatio", sMaxCostRatio); 
    9341031 
    9351032    Debug << "BSP max depth: " << sTermMaxDepth << endl; 
  • trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.h

    r297 r302  
    244244}; 
    245245 
    246  
    247246/** Implementation of the ViewCell BSP tree. */ 
    248247class BspTree  
     
    331330protected: 
    332331         
     332        // -------------------------------------------------------------- 
     333        // For sorting objects 
     334        // -------------------------------------------------------------- 
     335        struct SortableEntry 
     336        { 
     337                enum {POLY_MIN, POLY_MAX}; 
     338     
     339                int type; 
     340                float value; 
     341                Polygon3 *poly; 
     342                SortableEntry() {} 
     343                SortableEntry(const int t, const float v, Polygon3 *poly):  
     344                type(t), value(v), poly(poly) {} 
     345                 
     346                bool operator<(const SortableEntry &b) const  
     347                { 
     348                        return value < b.value; 
     349                }   
     350        }; 
     351 
    333352        /** Constructs the tree from the given list of polygons. 
    334353                @param viewCells if not NULL, new view cells are  
     
    355374 
    356375        /** Selects a splitting plane.  
     376                @param leaf the leaf to be split 
    357377                @param polys the polygon list on which the split decition is based 
    358378        */ 
    359         Plane3 SelectPlane(const PolygonContainer &polys) const; 
     379        Plane3 SelectPlane(BspLeaf *leaf, const PolygonContainer &polys) const; 
    360380 
    361381        /** Filters next view cell down the tree and inserts it into the appropriate leaves 
     
    445465                                                  const bool extractBack) const; 
    446466         
     467        /** Computes best cost ratio for the suface area heuristics for axis aligned 
     468                splits. This heuristics minimizes the cost for ray traversal. 
     469                @param polys the polygons guiding the ratio computation 
     470                @param box the bounding box of the leaf 
     471                @param axis the current split axis 
     472                @param position returns the split position 
     473                @param objectsBack the number of objects in the back of the split plane 
     474                @param objectsFront the number of objects in the front of the split plane 
     475        */ 
     476        float BestCostRatio(const PolygonContainer &polys, 
     477                                                const AxisAlignedBox3 &box, 
     478                                                const int axis, 
     479                                                float &position, 
     480                                                int &objectsBack, 
     481                                                int &objectsFront) const; 
     482         
     483        /** Sorts split candidates for surface area heuristics for axis aligned splits. 
     484                @param polys the input for choosing split candidates 
     485                @param axis the current split axis 
     486                @param splitCandidates returns sorted list of split candidates 
     487        */ 
     488        void SortSplitCandidates(const PolygonContainer &polys,  
     489                                                         const int axis,  
     490                                                         vector<SortableEntry> &splitCandidates) const; 
     491 
    447492        /// Pointer to the root of the tree 
    448493        BspNode *mRoot; 
     
    490535        static int sTermMaxPolysForAxisAligned; 
    491536 
     537        static float sCt_div_ci; 
     538        static float sSplitBorder; 
     539        static float sMaxCostRatio; 
     540 
    492541        // factors to guid the split plane heuristics 
    493542        static float sLeastSplitsFactor; 
  • trunk/VUT/GtpVisibilityPreprocessor/src/main.cpp

    r297 r302  
    5454  p->Export("vc_bsptree.x3d", false, false, true); 
    5555 
    56   //-- export the complementary view cells, i.e., the view cells not associated with leafs in the tree. 
     56  //-- export the complementary view cells 
     57  // i.e., the view cells not associated with leafs in the tree. 
    5758  Exporter *exporter = Exporter::GetExporter("viewcells_compl.x3d"); 
    5859 
Note: See TracChangeset for help on using the changeset viewer.