Changeset 238 for trunk


Ignore:
Timestamp:
08/15/05 20:50:00 (19 years ago)
Author:
mattausch
Message:

bsp viewcell stuff
fixed some bugs
left debug messages
added heuristics
added bsp options

Location:
trunk/VUT/GtpVisibilityPreprocessor
Files:
9 edited

Legend:

Unmodified
Added
Removed

  • trunk/VUT/GtpVisibilityPreprocessor/include/Polygon3.h

    r235 r238  
    4848        /** Deletes all polygons om the queue. 
    4949        */ 
    50         static void DeletePolygons(PolygonQueue *polys); 
     50        static void DeletePolygons(PolygonContainer *polys); 
    5151 
    5252        /// vertices are connected in counterclockwise order. 

  • trunk/VUT/GtpVisibilityPreprocessor/scripts/default.env

    r237 r238  
    6060BspTree { 
    6161#       splitPlaneStrategy leastSplits 
    62         splitPlaneStrategy nextPolygon 
     62        splitPlaneStrategy balancedTree 
     63#       splitPlaneStrategy nextPolygon 
    6364#       constructionMethod viewCells 
    6465        constructionMethod sceneGeometry 
     66        maxCandidates 20 
     67        maxViewCells 100 
    6568        Termination { 
    6669                maxPolygons 4 

  • trunk/VUT/GtpVisibilityPreprocessor/src/Environment.cpp

    r235 r238  
    11701170          "-bsp_construction_method=", 
    11711171          "viewCells"); 
     1172 
     1173  RegisterOption("BspTree.maxCandidates", 
     1174          optInt, 
     1175          "-bsp_max_candidates=", 
     1176          "20"); 
     1177 
     1178  RegisterOption("BspTree.maxViewCells", 
     1179          optInt, 
     1180          "-bsp_max_viewcells=", 
     1181          "100"); 
    11721182} 
    11731183 

  • trunk/VUT/GtpVisibilityPreprocessor/src/Plane3.h

    r237 r238  
    4444  { 
    4545          const Vector3 v = b - a; // line from A to B 
    46  
    4746          float dv = DotProd(mNormal, v); 
    4847          float u = 0; 
    4948         
    50           if (dv) 
     49          if (signum(dv) != 0) 
    5150          { 
    5251                  u = - Distance(a) / dv; 
    53                   Debug << "t: " << u << ", dv: " << dv << endl; 
     52                  Debug << "t: " << u << ", b - a: " << v << ", norm: " << mNormal << ", dist(a): " << - Distance(a) << ", dv: " << dv << endl; 
    5453                  if (coplanar) (*coplanar) = false; 
    5554          } 
    5655          else { 
    57                   Debug << "OHOH: " << u << endl; 
    5856                  if (coplanar) (*coplanar) = true;        
    5957          } 
    6058          if (t) (*t) = u; 
    61           Debug << "A: " << a << ", B: " << b << ", result: " << (a + (u * v)) << endl; 
     59          Debug << "result of intersection with A: " << a << ", B: " << b << ":\n" << (a + u * b - u * a) << "\n" << (a + u*v) << "\n\n"; 
    6260           
    63           return a + (u * v); 
     61          return a + u * b - u * a; // NOTE: gives better precision than calclulating a + u * v 
     62          //return a + (u * v); 
    6463  } 
    6564 

  • trunk/VUT/GtpVisibilityPreprocessor/src/Polygon3.cpp

    r237 r238  
    11#include "Polygon3.h" 
    22#include "Mesh.h" 
     3 
     4#define SIDE_TOLERANCE 0.002 
    35 
    46Polygon3::Polygon3() 
    … …  
    2123} 
    2224 
    23 Plane3 Polygon3::GetSupportingPlane() 
     25Plane3 Polygon3::GetSupportingPlane() const 
    2426{ 
     27        Debug << "creating plane using vertices: " << mVertices[0] << mVertices[1] << mVertices[2] << endl; 
     28        Vector3 v1 = mVertices[0] - mVertices[1]; 
     29                Vector3 v2 = mVertices[2] - mVertices[1]; 
     30        Debug << "plane has vectors " <<  v1 << v2  << endl; 
    2531        return Plane3(mVertices[0], mVertices[1], mVertices[2]); 
    2632} 
    2733 
    28 void Polygon3::DeletePolygons(PolygonQueue *polys) 
     34void Polygon3::DeletePolygons(PolygonContainer *polys) 
    2935{ 
    30         // don't need to store polygon information = delete polygons 
     36        // don't need to store polygon information => delete polygons 
    3137        while(!polys->empty()) 
    3238        { 
    33                 Polygon3 *poly = polys->front(); 
    34                 polys->pop(); 
     39                Polygon3 *poly = polys->back(); 
     40                polys->pop_back(); 
    3541                DEL_PTR(poly); 
    3642        } 
    … …  
    4248        Vector3 ptA = mVertices[mVertices.size() - 1]; 
    4349         
    44         int sideA = partition->Side(ptA); 
     50        int sideA = partition->Side(ptA, SIDE_TOLERANCE); 
    4551         
    4652        VertexContainer::const_iterator it; 
     53 
     54        Debug << "\n\nvertex A: " << ptA << ", side A: " << sideA << " (" << partition->Distance(ptA) << ")"; 
    4755 
    4856        // find line - plane intersections 
    … …  
    5058        { 
    5159                Vector3 ptB = (*it); 
    52                 int sideB = partition->Side(ptB); 
     60                int sideB = partition->Side(ptB, SIDE_TOLERANCE); 
     61                Debug << " <=> vertex B: " << ptB << ", side B: " << sideB << " (" << partition->Distance(ptB) << ")\n\n"; 
    5362 
    5463                // vertices on different sides => split 
    … …  
    6271                                // add vertex to both polygons 
    6372                                front->mVertices.push_back(splitPt); 
    64                                 back->mVertices.push_back(splitPt); 
     73                                back->mVertices.push_back(splitPt); Debug << "front and back polygon + " << splitPt << endl; 
    6574                         
    6675                                ++ splits; 
    6776                        } 
    68                         front->mVertices.push_back(ptB); 
     77                        front->mVertices.push_back(ptB); Debug << "front polygon + " << ptB << endl; 
    6978                } 
    7079                else if (sideB < 0) 
    … …  
    7786                                // add vertex to both polygons 
    7887                                front->mVertices.push_back(splitPt); 
    79                                 back->mVertices.push_back(splitPt); 
     88                                back->mVertices.push_back(splitPt); Debug << "front and back polygon + " << splitPt << endl; 
    8089 
    8190                                ++ splits; 
    8291                        } 
    83                         back->mVertices.push_back(ptB); 
     92                        back->mVertices.push_back(ptB); Debug << "back polygon + " << ptB << endl; 
    8493                } 
    8594                else 
    … …  
    8796                        // vertex on plane => add vertex to both polygons 
    8897                        front->mVertices.push_back(ptB); 
    89                         back->mVertices.push_back(ptB); 
     98                        back->mVertices.push_back(ptB); Debug << "front and back polygon + " << ptB << endl; 
    9099                } 
    91100         
    92101                ptA = ptB; 
    93102                sideA = sideB; 
     103                Debug << "vertex A: " << ptA << ", side A: " << sideA << " (" << partition->Distance(ptA) << ")"; 
    94104        } 
     105        Debug << "\n*********************\n"; 
    95106} 
    96107 
    97 int Polygon3::Side(Plane3 *plane) 
     108int Polygon3::Side(const Plane3 &plane) const 
     109{ 
     110        int classification = ClassifyPlane(plane); 
     111         
     112        if (classification == BACK_SIDE) 
     113                return -1; 
     114        else if (classification == FRONT_SIDE) 
     115                return 1; 
     116 
     117        return 0; 
     118} 
     119 
     120int Polygon3::ClassifyPlane(const Plane3 &plane) const 
    98121{ 
    99122        VertexContainer::const_iterator it; 
    … …  
    102125        bool onBackSide = false; 
    103126 
    104         // find line - plane intersections 
     127        // find possible line-plane intersections 
    105128        for (it = mVertices.begin(); it != mVertices.end(); ++ it) 
    106129        { 
    107                 int side = plane->Side(*it); 
     130                int side = plane.Side(*it, SIDE_TOLERANCE); 
    108131                 
    109132                if (side > 0) 
    … …  
    116139                } 
    117140 
    118                 if (onFrontSide && onBackSide) // split 
     141                if (onFrontSide && onBackSide) // split //TODO: check if through vvertex 
    119142                { 
    120143                        return SPLIT; 
    … …  
    131154        } 
    132155 
     156        // plane and polygon are coincident 
    133157        return COINCIDENT; 
    134158} 

  • trunk/VUT/GtpVisibilityPreprocessor/src/Polygon3.h

    r237 r238  
    1313class Face; 
    1414 
    15  
    16 /** Queue storing a soup of polygons used during BSP tree construction 
     15/** Container storing polygons used during BSP tree construction 
    1716*/ 
    18 typedef queue<Polygon3 *> PolygonQueue; 
     17typedef vector<Polygon3 *> PolygonContainer; 
    1918 
    2019/** Class representing a general planar polygon in 3d. 
    … …  
    3231        /** Returns supporting plane of this polygon. 
    3332        */ 
    34         Plane3 GetSupportingPlane(); 
     33        Plane3 GetSupportingPlane() const; 
    3534 
    3635        /** Splits polygon. 
    … …  
    4443        enum {BACK_SIDE, FRONT_SIDE, SPLIT, COINCIDENT}; 
    4544 
    46         /** Side of the plane where the polygon is located. 
     45        /** Classify polygon with respect to the plane. 
    4746            @returns one of BACK_SIDE, FRONT_SIDE, SPLIT, COINCIDENT 
    4847        */ 
    49         int Side(Plane3 *plane); 
     48        int ClassifyPlane(const Plane3 &plane) const; 
     49 
     50        /** Side of the polygon with respect to the plane. 
     51                @returns 1 if on front side, -1 if on back side, 0 else. 
     52        */ 
     53        int Side(const Plane3 &plane) const; 
    5054 
    5155        /** Deletes all polygons om the queue. 
    5256        */ 
    53         static void DeletePolygons(PolygonQueue *polys); 
     57        static void DeletePolygons(PolygonContainer *polys); 
    5458 
    5559        /// vertices are connected in counterclockwise order. 

  • trunk/VUT/GtpVisibilityPreprocessor/src/Preprocessor.cpp

    r237 r238  
    6868 
    6969        char constructionMethodStr[64]; 
     70        int maxViewCells = 0; 
    7071 
     72        environment->GetIntValue("BspTree.maxViewCells", maxViewCells); 
    7173        environment->GetStringValue("BspTree.constructionMethod", constructionMethodStr); 
    7274 
    … …  
    9092                 
    9193                // derive viewcells from the scene objects 
    92                 ViewCell::DeriveViewCells(objects, mViewcells, 1000); 
     94                ViewCell::DeriveViewCells(objects, mViewcells, maxViewCells); 
    9395                 
    9496                mBspTree->Construct(mViewcells); 

  • trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.cpp

    r237 r238  
    44#include "common.h" 
    55#include "ViewCell.h" 
    6 #include <stack> 
    76#include "Environment.h" 
    87#include "Polygon3.h" 
     8 
     9#include <stack> 
     10#include <time.h> 
     11#include <iomanip> 
    912 
    1013int BspTree::sTermMaxPolygons = 10; 
    1114int BspTree::sTermMaxDepth = 20; 
    1215int BspTree::sSplitPlaneStrategy = NEXT_POLYGON;  
    13  
     16int BspTree::sMaxCandidates = 10; 
    1417 
    1518/****************************************************************/ 
    … …  
    8588} 
    8689 
    87 void BspInterior::SplitPolygons(PolygonQueue *polys,  
    88                                                                 PolygonQueue *frontPolys,  
    89                                                                 PolygonQueue *backPolys,  
     90void BspInterior::SplitPolygons(PolygonContainer *polys,  
     91                                                                PolygonContainer *frontPolys,  
     92                                                                PolygonContainer *backPolys,  
    9093                                                                int &splits) 
    9194{ 
    92         while (!polys->empty()) 
    93         { 
    94                 Polygon3 *poly = polys->front(); 
    95  
    96                 polys->pop(); 
     95        while (!polys->empty()) 
     96        { 
     97                Polygon3 *poly = polys->back(); 
     98 
     99                polys->pop_back(); 
    97100 
    98101                Debug << (*poly); 
    99102 
    100                 int result = poly->Side(&mPlane); 
     103                int result = poly->ClassifyPlane(mPlane); 
    101104 
    102105                Polygon3 *front_piece = NULL; 
    … …  
    106109                { 
    107110                        case Polygon3::COINCIDENT: 
    108                                 //break; //TODO: comment in 
     111                                Debug << "coincident\n"; 
     112                                break; // do nothing 
    109113                        case Polygon3::FRONT_SIDE: 
    110                                 frontPolys->push(poly); 
     114                                Debug << "front\n"; 
     115                                frontPolys->push_back(poly); 
    111116                                break; 
    112117                        case Polygon3::BACK_SIDE: 
    113                                 backPolys->push(poly); 
     118                                Debug << "back\n"; 
     119                                backPolys->push_back(poly); 
    114120                                break; 
    115121                        case Polygon3::SPLIT: 
    … …  
    117123                                back_piece = new Polygon3(); 
    118124 
     125                                Debug << "\n\n**************SPLIT***************\n"; 
     126                                Debug << "Split plane: " << mPlane << "\noriginal " << (*poly) << endl; 
     127 
    119128                                //-- split polygon 
    120129                                poly->Split(&mPlane, front_piece, back_piece, splits); 
    121130                         
    122                                 Debug << "SPLIT, plane: " << mPlane << "\norginal: " << (*poly) << "\nback: " << (*back_piece) << "\nfront: " << (*front_piece) << endl; 
    123                                 backPolys->push(back_piece); 
    124                                 frontPolys->push(front_piece); 
    125  
     131                                Debug << "new front " << (*front_piece) << endl; 
     132                                Debug << "new back " << (*back_piece) << endl; 
     133 
     134                                frontPolys->push_back(front_piece); 
     135                                backPolys->push_back(back_piece); 
     136                                 
    126137                                // don't need polygon anymore 
    127138                                DEL_PTR(poly); 
    … …  
    129140                                break; 
    130141                        default: 
     142                                Debug << "SHOULD NEVER COME HERE\n"; 
    131143                                break; 
    132144                } 
    … …  
    160172{ 
    161173        mRoot = new BspLeaf(); 
     174        Randomize(); // initialise random generator for heuristics 
    162175} 
    163176  
    … …  
    170183{ 
    171184        app << "===== BspTree statistics ===============\n"; 
     185 
     186        app << setprecision(4); 
    172187 
    173188        app << "#N_RAYS Number of rays )\n" 
    … …  
    200215        objectRefs/(double)Leaves() << "\n"; 
    201216 
    202         //  app << setprecision(4); 
    203  
    204217        app << "#N_PEMPTYLEAVES  ( Percentage of leaves with zero query domains )\n"<< 
    205218        zeroQueryNodes*100/(double)Leaves()<<endl; 
    … …  
    255268void BspTree::InsertViewCell(ViewCell *viewCell) 
    256269{ 
     270        Debug << "Inserting view cells\n"; 
    257271        std::stack<BspTraversalData> tStack; 
    258272         
    259         PolygonQueue polys; 
     273        PolygonContainer polys; 
    260274        // copy polygon information to guide the split process 
    261275        CopyMesh2Polygons(viewCell->GetMesh(), polys); 
    … …  
    275289 
    276290                        // filter polygons down the tree. 
    277                         PolygonQueue *frontPolys = new PolygonQueue(); 
    278                         PolygonQueue *backPolys = new PolygonQueue(); 
     291                        PolygonContainer *frontPolys = new PolygonContainer(); 
     292                        PolygonContainer *backPolys = new PolygonContainer(); 
    279293 
    280294                        int splits = 0; 
    … …  
    289303                                delete frontPolys; 
    290304 
    291                         if (backPolys > 0) // if polygons on this side of bsp tree 
     305                        if (backPolys->size() > 0) // if polygons on this side of bsp tree 
    292306                                tStack.push(BspTraversalData(interior->GetBack(), interior->GetParent(),  
    293307                                                        backPolys, tData.mDepth + 1)); 
    … …  
    319333} 
    320334 
    321 void BspTree::CopyMesh2Polygons(Mesh *mesh, PolygonQueue &polys) 
     335void BspTree::CopyMesh2Polygons(Mesh *mesh, PolygonContainer &polys) 
    322336{ 
    323337        FaceContainer::const_iterator fi; 
    … …  
    327341        { 
    328342                Polygon3 *poly = new Polygon3((*fi), mesh); 
    329                 polys.push(poly); 
    330         } 
    331 } 
    332  
    333 void BspTree::Copy2PolygonSoup(const ObjectContainer &objects, PolygonQueue &polys) 
     343                polys.push_back(poly); 
     344        } 
     345} 
     346 
     347void BspTree::Copy2PolygonSoup(const ObjectContainer &objects, PolygonContainer &polys, int maxPolys) 
    334348{ 
    335349        ObjectContainer::const_iterator it, it_end = objects.end(); 
    336350 
    337         int limit = min((int)objects.size(), 1); 
     351        int limit = maxPolys != 0 ? min((int)objects.size(), maxPolys) : (int)objects.size(); 
    338352 
    339353        //for (it = objects.begin(); it != it_end; ++ it) 
    … …  
    375389 
    376390        std::stack<BspTraversalData> tStack; 
    377         PolygonQueue *polys = new PolygonQueue(); 
     391        PolygonContainer *polys = new PolygonContainer(); 
    378392         
    379393        // copy mesh instance polygons into one big polygon soup 
    380         Copy2PolygonSoup(objects, *polys); 
     394        Copy2PolygonSoup(objects, *polys, 100); 
    381395 
    382396        BspTraversalData tData(mRoot, mRoot->GetParent(), polys, 0); 
    … …  
    395409{ 
    396410        //Debug << "Subdividing node\n"; 
    397  
    398         PolygonQueue *backPolys = new PolygonQueue(); 
    399         PolygonQueue *frontPolys = new PolygonQueue(); 
    400  
     411        PolygonContainer *backPolys = new PolygonContainer(); 
     412        PolygonContainer *frontPolys = new PolygonContainer(); 
     413int polySize = tData.mPolygons->size(); 
    401414        BspNode *node = SubdivideNode(dynamic_cast<BspLeaf *>(tData.mNode), 
    402415                                                                  tData.mParent, 
    … …  
    404417                                                                  tData.mDepth, 
    405418                                                                  viewCell, 
    406                                                                   backPolys, 
    407                                                                   frontPolys); 
    408          
     419                                                                  frontPolys, 
     420                                                                  backPolys); 
     421Debug << "Level " << tData.mDepth << ", all: " << polySize << ", front: " << frontPolys->size() << ", back: " << backPolys->size() << endl; 
    409422        if (!node->IsLeaf()) // node was subdivided 
    410423        { 
    … …  
    423436} 
    424437 
    425 Plane3 BspTree::SelectPlane(PolygonQueue *polyQueue)  
    426 { 
    427         // TODO: more sophisticated criteria 
    428         switch (sSplitPlaneStrategy) 
    429         { 
    430         case LEAST_SPLITS: 
    431                 break; 
    432         case NEXT_POLYGON: 
    433         return polyQueue->front()->GetSupportingPlane(); 
    434                 break; 
    435         default: 
    436                 break; 
    437         } 
     438Plane3 BspTree::SelectPlane(PolygonContainer *polygons)  const 
     439{ 
     440        // most simple strategy: just take next polygon 
     441        if (sSplitPlaneStrategy == NEXT_POLYGON) 
     442        { 
     443                Debug << "simple plane selection\n"; 
     444                return polygons->front()->GetSupportingPlane(); 
     445        } 
     446         
     447        return SelectPlaneHeuristics(polygons, sMaxCandidates); 
     448} 
     449 
     450Plane3 BspTree::SelectPlaneHeuristics(PolygonContainer *polygons, int maxTests) const 
     451{ 
     452        Debug << "selecting plane heuristics\n"; 
     453 
     454        int bestValue = 999999; 
     455 
     456        Plane3 *bestPlane = NULL; 
     457         
     458        int limit = min((int)polygons->size(), maxTests); 
     459 
     460        for (int i = 0; i < limit; ++i) 
     461        { 
     462                int candidateIdx = Random((int)polygons->size()); 
     463                Plane3 candidatePlane = (*polygons)[candidateIdx]->GetSupportingPlane(); 
     464                Debug << "choosing new candidate: " << limit << endl; 
     465                // evaluate current candidate 
     466                int candidateValue = EvalSplitPlane(polygons, candidatePlane); 
     467                         
     468                if (candidateValue < bestValue) 
     469                { 
     470                        bestPlane = &candidatePlane; 
     471                        bestValue = candidateValue; 
     472                        Debug << "new plane value " << bestValue << endl; 
     473                } 
     474        } 
     475        Debug << "%%%%%%%%%%found value: " << bestValue << endl; 
     476                 
     477        return *bestPlane; 
     478} 
     479 
     480int BspTree::EvalSplitPlane(PolygonContainer *polygons, const Plane3 &candidatePlane) const 
     481{ 
     482        PolygonContainer::const_iterator it; 
     483 
     484        int sum = 0, sum2 = 0; 
     485 
     486        for (it = polygons->begin(); it < polygons->end(); ++ it) 
     487        { 
     488                int classification = (*it)->ClassifyPlane(candidatePlane); 
     489                 
     490                if ((sSplitPlaneStrategy == BALANCED_TREE) || (sSplitPlaneStrategy == COMBINED)) 
     491                { 
     492                        sum += EvalForBalancedTree(classification); 
     493                } 
     494                 
     495                if ((sSplitPlaneStrategy == LEAST_SPLITS) || (sSplitPlaneStrategy == COMBINED)) 
     496                { 
     497                        sum2 += EvalForLeastSplits(classification); 
     498                } 
     499        } 
     500 
     501        // return linear combination of both sums 
     502        return abs(sum) + abs(sum2); 
     503} 
     504 
     505int BspTree::EvalForBalancedTree(const int classification) 
     506{ 
     507        if (classification == Polygon3::FRONT_SIDE) 
     508                return 1; 
     509        else if (classification == Polygon3::BACK_SIDE) 
     510                return -1; 
     511 
     512        return 0; 
     513} 
     514 
     515int BspTree::EvalForLeastSplits(const int classification) 
     516{ 
     517        if (classification == Polygon3::SPLIT) 
     518                return 1; 
     519 
     520        return 0; 
    438521} 
    439522 
    440523BspNode *BspTree::SubdivideNode(BspLeaf *leaf,  
    441524                                                                BspInterior *parent,  
    442                                                                 PolygonQueue *polys,  
     525                                                                PolygonContainer *polys,  
    443526                                                                const int depth,  
    444527                                                                ViewCell *viewCell, 
    445                                                                 PolygonQueue *frontPolys,  
    446                                                                 PolygonQueue *backPolys) 
     528                                                                PolygonContainer *frontPolys,  
     529                                                                PolygonContainer *backPolys) 
    447530{ 
    448531        // terminate traversal 
    … …  
    460543        // split polygon according to current plane 
    461544        int splits = 0; 
     545        int polySize = polys->size(); 
     546         
    462547        node->SplitPolygons(polys, frontPolys, backPolys, splits); 
     548        Debug << "$$ " << polySize << " " << frontPolys->size() << " " << backPolys->size() << endl;  
    463549        mStat.splits += splits; 
    464550 
    … …  
    485571        environment->GetIntValue("BspTree.Termination.maxDepth", sTermMaxDepth); 
    486572        environment->GetIntValue("BspTree.Termination.maxPolygons", sTermMaxPolygons); 
     573        environment->GetIntValue("BspTree.maxCandidates", sMaxCandidates); 
    487574 
    488575        //-- extract strategy to choose the next split plane 
    … …  
    497584        else if (strcmp(splitPlaneStrategyStr, "leastSplits") == 0) 
    498585                sSplitPlaneStrategy = BspTree::LEAST_SPLITS; 
     586        else if (strcmp(splitPlaneStrategyStr, "balancedTree") == 0) 
     587                sSplitPlaneStrategy = BspTree::BALANCED_TREE; 
    499588        else  
    500589        { 
    … …  
    508597  // the node became a leaf -> evaluate stats for leafs 
    509598  BspLeaf *leaf = dynamic_cast<BspLeaf *>(data.mNode); 
     599 
     600  Debug << "evaluating leaf stats\n"; 
    510601 
    511602  if (data.mDepth >= mTermMaxDepth) 

  • trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.h

    r237 r238  
    1616class Polygon3; 
    1717 
    18 /** Queue storing a soup of polygons used during BSP tree construction 
     18/** Container storing a soup of polygons used during BSP tree construction 
    1919*/ 
    20 typedef std::queue<Polygon3 *> PolygonQueue; 
     20typedef std::vector<Polygon3 *> PolygonContainer; 
    2121 
    2222class BspTreeStatistics // TODO: should have common superclass with KdTreeStatistics 
    … …  
    143143                @param splits number of splits 
    144144        */ 
    145         void SplitPolygons(PolygonQueue *polys, PolygonQueue *frontPolys, PolygonQueue *backPolys, int &splits); 
     145        void SplitPolygons(PolygonContainer *polys, PolygonContainer *frontPolys,  
     146                                           PolygonContainer *backPolys, int &splits); 
    146147 
    147148        friend ostream &operator<<(ostream &s, const BspInterior &A) 
    … …  
    194195                BspInterior *mParent; 
    195196                /// polygonal data for splitting 
    196                 PolygonQueue *mPolygons; 
     197                PolygonContainer *mPolygons; 
    197198                /// current depth 
    198199                int mDepth; 
    … …  
    200201                BspTraversalData() {} 
    201202                 
    202                 BspTraversalData(BspNode *node, BspInterior *parent, PolygonQueue *polys, const int depth):  
     203                BspTraversalData(BspNode *node, BspInterior *parent, PolygonContainer *polys, const int depth):  
    203204                mNode(node), mParent(parent), mPolygons(polys), mDepth(depth) {} 
    204205    }; 
    … …  
    231232 
    232233protected: 
     234         
     235        /** Evaluates plane classification with respect to the plane's  
     236                contribution for a balanced tree. 
     237        */ 
     238        static inline int EvalForBalancedTree(const int classficiation); 
     239        /** Evaluates plane classification with respect to the plane's  
     240                contribution for a minimum number splits in the tree. 
     241        */ 
     242        static inline int EvalForLeastSplits(const int classification); 
     243 
     244        /** Evaluates the contribution of the candidate split plane. 
     245        */ 
     246        int EvalSplitPlane(PolygonContainer *polygons, const Plane3 &candidatePlane) const; 
     247 
     248        /** Evaluates tree stats in the BSP tree leafs. 
     249        */ 
    233250        void EvaluateLeafStats(const BspTraversalData &data); 
    234251 
    … …  
    241258 
    242259        /** Selects a splitting plane.  
    243                 @param polyQueue the polygon data on which the split decition is based 
    244         */ 
    245         Plane3 SelectPlane(PolygonQueue *polyQueue); 
     260                @param polygons the polygon data on which the split decition is based 
     261        */ 
     262        Plane3 SelectPlane(PolygonContainer *polygons) const; 
    246263 
    247264        /** Filters next viewcell down the tree and inserts it into the appropriate leaves 
    … …  
    259276        */ 
    260277        BspNode *SubdivideNode(BspLeaf *leaf, BspInterior *parent,  
    261                                                         PolygonQueue *polys, const int depth,  
     278                                                        PolygonContainer *polys, const int depth,  
    262279                                                        ViewCell *viewCell, 
    263                                                         PolygonQueue *frontPolys, PolygonQueue *backPolys); 
     280                                                        PolygonContainer *frontPolys, PolygonContainer *backPolys); 
    264281 
    265282        /** Filters polygons down the tree. 
    … …  
    269286                @param backPolys returns the polygons in the back of the split plane 
    270287        */ 
    271         void FilterPolygons(BspInterior *node, PolygonQueue *polys,  
    272                                                 PolygonQueue *frontPolys, PolygonQueue *backPolys); 
     288        void FilterPolygons(BspInterior *node, PolygonContainer *polys,  
     289                                                PolygonContainer *frontPolys, PolygonContainer *backPolys); 
     290 
     291        /** Selects the split plane in order to get a balanced tree. 
     292                @param polygons container of polygons 
     293                @param maxTests the maximal number of candidate tests 
     294        */ 
     295        Plane3 SelectPlaneHeuristics(PolygonContainer *polygons, int maxTests) const; 
    273296 
    274297        /** Extracts the meshes of the objects and copies them into the mesh. 
    275298        */ 
    276         static void Copy2PolygonSoup(const ObjectContainer &objects, PolygonQueue &polys); 
     299        static void Copy2PolygonSoup(const ObjectContainer &objects, PolygonContainer &polys, int maxPolys); 
    277300 
    278301        /** copy this mesh into polygons. 
    279302        */ 
    280         static void CopyMesh2Polygons(Mesh *mesh, PolygonQueue &polys); 
     303        static void CopyMesh2Polygons(Mesh *mesh, PolygonContainer &polys); 
    281304 
    282305        /// Pointer to the root of the tree 
    … …  
    293316 
    294317        /// Strategies for choosing next split plane. 
    295         enum {NEXT_POLYGON, LEAST_SPLITS}; 
     318        enum {NEXT_POLYGON, LEAST_SPLITS, BALANCED_TREE, COMBINED}; 
    296319 
    297320public: 
    … …  
    303326        /// maximal possible depth 
    304327        static int sTermMaxDepth; 
    305  
     328        /// strategy to get the best split plane 
    306329        static int sSplitPlaneStrategy; 
     330        /// number of candidates evaluated for the next split plane 
     331        static int sMaxCandidates; 
    307332}; 
    308333 
Note: See TracChangeset for help on using the changeset viewer.