Changeset 294 for trunk


Ignore:
Timestamp:
09/20/05 02:39:50 (19 years ago)
Author:
mattausch
Message:

vertical splitr criterium

Location:
trunk/VUT/GtpVisibilityPreprocessor
Files:
6 edited

Legend:

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

    r292 r294  
    6565 
    6666BspTree { 
    67 #       splitPlaneStrategy leastSplits 
    68         splitPlaneStrategy balancedTree 
    69 #       splitPlaneStrategy nextPolygon 
    70 #       splitPlaneStrategy combined 
     67        splitPlaneStrategy 14 
    7168#       constructionMethod rays 
    7269        constructionMethod viewCells 
  • trunk/VUT/GtpVisibilityPreprocessor/src/Polygon3.cpp

    r293 r294  
    6161                                //-- plane - line intersection 
    6262                                Vector3 splitPt = partition->FindIntersection(ptA, ptB); 
    63                                 Debug << "fpg " << splitPt << " side " << partition->Side(splitPt, SIDE_TOLERANCE) <<  
    64                                         "\nptA " << ptA << " side " << sideA << "\nptB " << ptB << " side " << sideB << " " << Distance(ptB, splitPt) << endl; 
     63                         
    6564                                if (!foundSplit || (SqrDistance(splitPt, prevSplitPt) > SIDE_TOLERANCE_SQRD)) 
    6665                                { 
     
    8180                                //-- plane - line intersection 
    8281                                Vector3 splitPt = partition->FindIntersection(ptA, ptB); 
    83                         //      if (foundSplit) Debug << "back split pt " << splitPt << " prev " << prevSplitPt << endl; 
     82                         
    8483                                if (!foundSplit || (SqrDistance(splitPt, prevSplitPt) > SIDE_TOLERANCE_SQRD)) 
    8584                                { 
    86                                         //Debug << "add back split vertex " << splitPt << endl; 
    8785                                        // add vertex to both polygons 
    8886                                        front->mVertices.push_back(splitPt); 
     
    9189                                        foundSplit = true; 
    9290                                        prevSplitPt = splitPt; 
    93                                 }//else Debug << "reject back split vertex " << splitPt << endl;         
     91                                }        
    9492                        } 
    9593                        back->mVertices.push_back(ptB); 
     
    125123        bool onFrontSide = false; 
    126124        bool onBackSide = false; 
     125        // threshold for coincident classification 
     126        const float dot_thres = 0.99f; 
    127127 
    128128        int count = 0; 
     
    131131        { 
    132132                int side = plane.Side(*it, SIDE_TOLERANCE); 
    133                 //Debug << "side: " << side << " " << plane.Distance(*it) << endl; 
    134  
     133                 
    135134                if (side > 0) 
    136135                        onFrontSide = true; 
     
    147146                { 
    148147                        // Decide if plane and surface normal are same 
    149                         if (DotProd(plane.mNormal, GetSupportingPlane().mNormal) > 0.99) 
     148                        if (DotProd(plane.mNormal, GetSupportingPlane().mNormal) > dot_thres) 
    150149                                return COINCIDENT; // plane and polygon are coincident 
    151150                        else  
     
    164163 
    165164        // Decide if plane and surface normal are same 
    166         if (DotProd(plane.mNormal, GetSupportingPlane().mNormal) > float(1.0 - 1.0e-5)) 
     165        if (DotProd(plane.mNormal, GetSupportingPlane().mNormal) > dot_thres) 
    167166                return COINCIDENT; // plane and polygon are coincident 
    168167        else  
  • trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.cpp

    r293 r294  
    1313#include "Exporter.h" 
    1414 
    15 #define INITIAL_COST 999999// unreachable high initial cost for heuristic evaluation 
    16  
    1715int BspTree::sTermMaxPolygons = 10; 
    1816int BspTree::sTermMaxDepth = 20; 
     
    2422        contribution for a balanced tree. 
    2523*/ 
    26 int BspTree::sLeastSplitsTable[4] = {0, 0, 1, 0}; 
     24float BspTree::sLeastSplitsTable[] = {0, 0, 1, 0}; 
    2725/** Evaluates split plane classification with respect to the plane's  
    2826        contribution for a minimum number splits in the tree. 
    2927*/ 
    30 int BspTree::sBalancedTreeTable[4] = {-1, 1, 0, 0}; 
    31  
    32 const int FACTOR_BALANCE = 1; 
    33 const int FACTOR_LEAST_SPLITS = 1; 
     28float BspTree::sBalancedTreeTable[] = {-1, 1, 0, 0}; 
    3429 
    3530//int counter = 0; 
    36 //bool BspTree::displayDebug = false; 
     31 
    3732/****************************************************************/ 
    3833/*                  class BspNode implementation                */ 
     
    151146        Polygon3 *splitPoly = NULL; 
    152147#ifdef _Debug 
    153         Debug << "Splitting polygons of node " << this << " with plane " << mPlane << endl; 
     148        Debug << "splitting polygons of node " << this << " with plane " << mPlane << endl; 
    154149#endif 
    155150        while (!polys->empty()) 
     
    183178                                front_piece = new Polygon3(poly->mParent); 
    184179                                back_piece = new Polygon3(poly->mParent); 
    185 Debug << "*************\n"; 
    186 Debug << "initial poly\n" << *poly << endl; 
     180 
    187181                                //-- split polygon into front and back part 
    188182                                poly->Split(&mPlane, front_piece, back_piece); 
    189183 
    190184                                ++ splits; // increase number of splits 
    191                          
    192                                 if (front_piece->mVertices.size() >= 3) // check if polygon still valid  
     185                                // check if polygon still valid  
     186                                if (front_piece->mVertices.size() >= 3) 
    193187                                        frontPolys->push_back(front_piece); 
    194                                 else{ 
    195                                         Debug << "poly\n" << *poly << "split front piece not valid\n" << *front_piece << endl; 
    196                                         DEL_PTR(front_piece);} 
     188                                else 
     189                                        DEL_PTR(front_piece); 
     190                                // check if polygon still valid 
     191                                if (back_piece->mVertices.size() >= 3) 
     192                                        backPolys->push_back(back_piece); 
     193                                else                             
     194                                        DEL_PTR(back_piece); 
    197195                                 
    198                                 if (back_piece->mVertices.size() >= 3) // check if polygon still valid 
    199                                         backPolys->push_back(back_piece); 
    200                                 else{ 
    201                                         Debug << "poly\n" << *poly << "split back piece not valid\n" << *back_piece << endl; 
    202                                         DEL_PTR(back_piece);} 
    203                                  
    204 Debug << "*************\n"; 
    205196#ifdef _DEBUG 
    206197                                Debug << "split " << *poly << endl << *front_piece << endl << *back_piece << endl; 
     
    214205                } 
    215206        } 
    216         //Debug << "inside: " << inside << endl; 
    217207} 
    218208 
     
    258248mTermMaxDepth(0),  
    259249mRoot(NULL),  
     250mVerticalAxis(Vector3(0, 0, 1)), 
    260251//mStorePolys(true) 
    261252mStorePolys(false) 
     
    570561 
    571562        Debug << "**** Finished tree construction ****\n"; 
    572         Debug << "BSP tree contruction time: "<< TimeDiff(startTime, GetTime())*1e-3 << "s" << endl; 
     563        Debug << "BSP tree contruction time: " << TimeDiff(startTime, GetTime())*1e-3 << "s" << endl; 
    573564} 
    574565 
     
    594585                        leaf->SetViewCell(viewCell); 
    595586                        viewCells->push_back(viewCell); 
    596                         Debug << "creating new viewcell" << endl; 
     587                        // Debug << "creating new viewcell" << endl; 
    597588                } 
    598589                //-- add viewcell stored in split polygon 
     
    602593                                Debug << "ERROR: leaf already has view cell " << endl;//leaf->mViewCellIdx << endl; 
    603594 
    604                         //leaf->mViewCellIdx = counter; 
    605                         Debug << "insert view cell " << tData.mViewCell << endl; 
    606  
     595                        //leaf->mViewCellIdx = counter; Debug << "insert view cell " << tData.mViewCell << endl; 
    607596                        leaf->SetViewCell(dynamic_cast<ViewCell *>(tData.mViewCell)); 
    608597                } 
     
    627616                                                                                  &coincident); 
    628617 
    629         if ((backPolys->size() == 0) && (coincident.size() > 1))  
    630         { 
    631                 Debug << "WARNING: size " << (int)coincident.size() << " at depth " << tData.mDepth << ", #back polys: " << (int)backPolys->size() << ", #front polys: " << (int)frontPolys->size() << endl; 
    632                 for (int i=0; i<coincident.size(); ++i) 
    633                         Debug << "coincident poly " << i << ", vc: " << coincident[i]->mParent << "\n" << *coincident[i] <<  
    634                         "dotprod: " << DotProd(coincident[i]->GetSupportingPlane().mNormal, interior->GetPlane()->mNormal) << endl; 
    635         } 
    636         //Debug << "coincident size: " << coincident.size() << endl; 
    637  
    638         // get view cell associated with the first split polygon 
     618        // view cell associated with the first split polygon 
    639619        ViewCell *viewCell = (coincident.size() > 0) ?  
    640620                                        dynamic_cast<ViewCell *>(coincident.front()->mParent) : NULL; 
     
    700680 
    701681        // simple strategy: just take next polygon 
    702         if (sSplitPlaneStrategy == NEXT_POLYGON) 
     682        if (sSplitPlaneStrategy & NEXT_POLYGON) 
    703683        { 
    704684                return polys->front()->GetSupportingPlane(); 
    705685        } 
    706686         
     687    if (sSplitPlaneStrategy & VERTICAL_AXIS) 
     688        { 
     689                const float dot_thres = 0.999; 
     690                PolygonContainer::const_iterator it, it_end = polys->end(); 
     691                 
     692                for (it = polys->begin(); it != it_end; ++ it) 
     693                { 
     694                        if (DotProd((*it)->GetSupportingPlane().mNormal, mVerticalAxis) > dot_thres) 
     695                                return (*it)->GetSupportingPlane(); 
     696                } 
     697        } 
    707698        // use heuristics to find appropriate plane 
    708699        return SelectPlaneHeuristics(polys, sMaxCandidates); 
     
    711702Plane3 BspTree::SelectPlaneHeuristics(PolygonContainer *polygons, int maxTests) const 
    712703{ 
    713         int lowestCost = INITIAL_COST; 
     704        float lowestCost = MAX_FLOAT; 
    714705        int bestPlaneIdx = 0; 
    715706         
     
    718709        for (int i = 0; i < limit; ++ i) 
    719710        { 
    720                 int candidateIdx = Random((int)polygons->size()); // TODO:  avoid testing same plane 2 times 
     711                int candidateIdx = Random((int)polygons->size()); // TODO: avoid testing same plane 2 times 
    721712                Plane3 candidatePlane = (*polygons)[candidateIdx]->GetSupportingPlane(); 
    722713                 
    723714                // evaluate current candidate 
    724                 int candidateCost = EvalSplitPlane(polygons, candidatePlane); 
     715                float candidateCost = EvalSplitPlane(polygons, candidatePlane); 
    725716                         
    726717                if (candidateCost < lowestCost) 
     
    728719                        bestPlaneIdx = candidateIdx; 
    729720                        lowestCost = candidateCost; 
    730                         //Debug << "new plane cost " << lowestCost << endl; 
    731721                } 
    732722        } 
     
    736726} 
    737727 
    738 int BspTree::EvalSplitPlane(PolygonContainer *polygons, const Plane3 &candidatePlane) const 
     728float BspTree::EvalSplitPlane(PolygonContainer *polygons, const Plane3 &candidatePlane) const 
    739729{ 
    740730        PolygonContainer::const_iterator it; 
    741731 
    742         int sumBalanced = 0, sumLeastSplits = 0; 
     732        float sumBalanced = 0, sumLeastSplits = 0; 
    743733 
    744734        for (it = polygons->begin(); it != polygons->end(); ++ it) 
     
    746736                int classification = (*it)->ClassifyPlane(candidatePlane); 
    747737                 
    748                 if ((sSplitPlaneStrategy == COMBINED) || (sSplitPlaneStrategy == BALANCED_TREE)) 
     738                if (sSplitPlaneStrategy & BALANCED_TREE) 
    749739                { 
    750740                        sumBalanced += sBalancedTreeTable[classification]; 
    751741                } 
    752742                 
    753                 if ((sSplitPlaneStrategy == COMBINED) || (sSplitPlaneStrategy == LEAST_SPLITS)) 
     743                if (sSplitPlaneStrategy & LEAST_SPLITS) 
    754744                { 
    755745                        sumLeastSplits += sLeastSplitsTable[classification]; 
     
    758748 
    759749        // return linear combination of both sums 
    760         return FACTOR_BALANCE * abs(sumBalanced) + FACTOR_LEAST_SPLITS *abs(sumLeastSplits); 
     750        return fabs(sumBalanced) + fabs(sumLeastSplits); 
    761751} 
    762752 
     
    766756        environment->GetIntValue("BspTree.Termination.maxPolygons", sTermMaxPolygons); 
    767757        environment->GetIntValue("BspTree.maxCandidates", sMaxCandidates); 
     758        environment->GetIntValue("BspTree.splitPlaneStrategy", sSplitPlaneStrategy); 
    768759 
    769760        Debug << "BSP max depth: " << sTermMaxDepth << endl; 
    770761        Debug << "BSP max polys: " << sTermMaxPolygons << endl; 
    771762        Debug << "BSP max candidates: " << sMaxCandidates << endl; 
    772  
    773         //-- extract strategy to choose the next split plane 
    774         char splitPlaneStrategyStr[60]; 
    775  
    776         environment->GetStringValue("BspTree.splitPlaneStrategy", splitPlaneStrategyStr); 
    777          
    778         sSplitPlaneStrategy = BspTree::NEXT_POLYGON; 
    779          
    780         if (strcmp(splitPlaneStrategyStr, "nextPolygon") == 0) 
    781                 sSplitPlaneStrategy = BspTree::NEXT_POLYGON; 
    782         else if (strcmp(splitPlaneStrategyStr, "leastSplits") == 0) 
    783                 sSplitPlaneStrategy = BspTree::LEAST_SPLITS; 
    784         else if (strcmp(splitPlaneStrategyStr, "balancedTree") == 0) 
    785                 sSplitPlaneStrategy = BspTree::BALANCED_TREE; 
    786         else if (strcmp(splitPlaneStrategyStr, "combined") == 0) 
    787                 sSplitPlaneStrategy = BspTree::COMBINED; 
    788         else  
    789         { 
    790                 cerr << "Wrong BSP split plane strategy " << splitPlaneStrategyStr << endl; 
    791                 exit(1); 
    792     } 
    793  
    794         Debug << "Split plane heuristic: " << splitPlaneStrategyStr << endl; 
    795763 
    796764        //-- parse BSP tree construction method 
  • trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.h

    r289 r294  
    344344 
    345345        /** Evaluates the contribution of the candidate split plane. 
    346         */ 
    347         int EvalSplitPlane(PolygonContainer *polygons, const Plane3 &candidatePlane) const; 
     346                @returns the cost of the candidate split plane 
     347        */ 
     348        float EvalSplitPlane(PolygonContainer *polygons, const Plane3 &candidatePlane) const; 
    348349 
    349350        /** Evaluates tree stats in the BSP tree leafs. 
     
    442443 
    443444        /// Strategies for choosing next split plane. 
    444         enum {NEXT_POLYGON, LEAST_SPLITS, BALANCED_TREE, COMBINED}; 
     445        enum {NEXT_POLYGON = 0,  
     446                  LEAST_SPLITS = 2,  
     447                  BALANCED_TREE = 4,  
     448                  VERTICAL_AXIS = 8,  
     449                  AXIS_ALIGNED = 16}; 
    445450 
    446451        /// box around the whole view domain 
    447452        AxisAlignedBox3 mBox; 
    448453 
    449                 /// if view cell calculation is incremential 
    450         bool mIsIncremential; 
    451  
    452454        /// if polygons should be stored in the tree 
    453455        bool mStorePolys; 
    454456 
     457        /// vertical axis of scene 
     458        Vector3 mVerticalAxis; 
    455459public: 
    456460        /// Parses the environment and stores the global BSP tree parameters 
     
    472476                contribution for a balanced tree. 
    473477        */ 
    474         static int sLeastSplitsTable[4]; 
     478        static float sLeastSplitsTable[4]; 
    475479        /** Evaluates split plane classification with respect to the plane's  
    476480                contribution for a minimum number splits in the tree. 
    477481        */ 
    478         static int sBalancedTreeTable[4]; 
     482        static float sBalancedTreeTable[4]; 
    479483}; 
    480484 
  • trunk/VUT/GtpVisibilityPreprocessor/src/X3dParser.cpp

    r262 r294  
    517517                Mesh *mesh = mViewCells->back()->GetMesh(); 
    518518#ifdef _DEBUG 
    519                 Debug << "Viewcell :"  
     519                Debug << "Viewcell: "  
    520520                          << mesh->mVertices[0] << " " << mesh->mVertices[1] << " " << mesh->mVertices[2] << " "  
    521521                          << mesh->mVertices[3] << " " << mesh->mVertices[4] << " " << mesh->mVertices[5] << "\n"; 
  • trunk/VUT/GtpVisibilityPreprocessor/src/main.cpp

    r292 r294  
    5454  p->Export("vc_bsptree.x3d", false, false, true); 
    5555 
    56  
    57   // export the complementary view cells, i.e., the view cells not in the tree. 
     56  //-- export the complementary view cells, i.e., the view cells not associated with leafs in the tree. 
    5857  Exporter *exporter = Exporter::GetExporter("viewcells_compl.x3d"); 
    5958 
    6059  ViewCellContainer::iterator vc_compl_it; 
    6160  ViewCellContainer vc_compl(p->mViewCells.size() + X3dExporter::foundViewCells.size()); 
    62  
    63   Debug << "here1" << endl; 
     61   
    6462  sort(p->mViewCells.begin(), p->mViewCells.end()); 
    65   Debug << "here2.5 " << X3dExporter::foundViewCells.size() << endl; 
    66    
    6763  vc_compl_it = set_difference(p->mViewCells.begin(), p->mViewCells.end(),  
    6864                                 X3dExporter::foundViewCells.begin(), X3dExporter::foundViewCells.end(), 
    6965                                 vc_compl.begin()); 
    70  
    71   Debug << "here2" << endl; 
    72   
    7366  vc_compl.erase(vc_compl_it, vc_compl.end()); 
    7467   
    75   Debug << "Complementary view cells: " << vc_compl.size() << endl; 
    7668 
    7769  if (exporter)  
     
    7971          exporter->ExportViewCells(&vc_compl); // export view cells 
    8072          delete exporter; 
    81   }Debug << "here4" << endl; 
     73  } 
    8274 
    8375#endif 
Note: See TracChangeset for help on using the changeset viewer.