Ignore:
Timestamp:
08/10/05 17:09:29 (19 years ago)
Author:
mattausch
Message:

updated bsp viewcells

File:
1 edited

Legend:

Unmodified
Added
Removed

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

    r225 r233  
    6767} 
    6868 
    69 /****************************************************************/ 
    70 /*                  class BspLeaf implementation                */ 
    71 /****************************************************************/ 
    72  
    73 BspLeaf::BspLeaf(ViewCell *viewCell): mViewCell(viewCell)  
    74 { 
    75 } 
    76  
    77 ViewCell *BspLeaf::GetViewCell() 
    78 { 
    79         return mViewCell; 
    80 } 
    81  
    82 bool BspLeaf::IsLeaf() const  
    83 {  
    84         return true;  
    85 } 
    86  
    87 /****************************************************************/ 
    88 /*                  class Polygon implementation                */ 
    89 /****************************************************************/ 
    90  
    91 Polygon::Polygon() 
    92 {} 
    93  
    94 Polygon::Polygon(const VertexContainer &vertices): mVertices(vertices)  
    95 {} 
    96  
    97 Polygon::Polygon(Face *face, Mesh *parent) 
    98 { 
    99         VertexIndexContainer::const_iterator it; 
    100  
    101         for (it = face->mVertexIndices.begin(); it != face->mVertexIndices.end(); ++ it) 
    102         { 
    103                 mVertices.push_back(parent->mVertices[*it]); 
    104         } 
    105 } 
    106  
    107 Plane3 Polygon::GetSupportingPlane() 
    108 { 
    109         return Plane3(mVertices[0], mVertices[1], mVertices[2]); 
    110 } 
    111  
    112 void Polygon::DeletePolygons(PolygonQueue *polys) 
    113 { 
    114         // don't need to store polygon information = delete polygons 
    115         while(!polys->empty()) 
     69void BspInterior::SplitPolygons(PolygonQueue *polys, PolygonQueue *frontPolys, PolygonQueue *backPolys) 
     70{ 
     71        while (!polys->empty()) 
    11672        { 
    11773                Polygon *poly = polys->front(); 
     74 
    11875                polys->pop(); 
    119                 DEL_PTR(poly); 
    120         } 
    121  
    122 } 
    123  
    124 void Polygon::Split(Plane3 *partition, Polygon *front, Polygon *back) 
    125 { 
    126         Vector3 ptA = mVertices[mVertices.size() - 1];; 
    127          
    128         int sideA = partition->Side(ptA); 
    129          
    130         VertexContainer::const_iterator it; 
    131  
    132         // find line - plane intersections 
    133         for (it = mVertices.begin(); it != mVertices.end(); ++ it) 
    134         { 
    135                 Vector3 ptB = (*it); 
    136                 int sideB = partition->Side(ptB); 
    137  
    138                 // vertices on different sides => split 
    139                 if ((sideA != 0) && (sideB != 0) && (sideA != sideB))  
    140                 { 
    141                         Vector3 v = ptB - ptA; // line from A to B 
    142                         float dv = DotProd(partition->mNormal, v); 
    143                         float t = 0; 
    144                          
    145                         if (dv) 
    146                         { 
    147                                 t = - partition->Distance(ptA) / dv; 
    148                         } 
    149                 } 
    150                 if (sideB >= 0) 
    151                 { 
    152                         back->mVertices.push_back(ptB); 
    153                 } 
    154                 else if (sideB <= 0) 
    155                 { 
    156                         front->mVertices.push_back(ptB); 
    157                 } 
    158  
    159                 ptA = ptB; 
    160                 sideA = sideB; 
    161         } 
    162 } 
    163  
    164 int Polygon::Side(Plane3 *plane) 
    165 { 
    166         VertexContainer::const_iterator it; 
    167  
    168         bool onFrontSide = false; 
    169         bool onBackSide = false; 
    170  
    171         // find line - plane intersections 
    172         for (it = mVertices.begin(); it != mVertices.end(); ++ it) 
    173         { 
    174                 int side = plane->Side(*it); 
    175                  
    176                 if (side > 0) 
    177                 { 
    178                         onFrontSide = true; 
    179                 } 
    180                 else if (side < 0) 
    181                 { 
    182                         onBackSide = true; 
    183                 } 
    184  
    185                 if (onFrontSide && onBackSide) // splits 
    186                         return SPLIT; 
    187         } 
    188  
    189         if (onBackSide) 
    190         { 
    191                 return BACK_SIDE; 
    192         } 
    193         else if (onFrontSide) 
    194         { 
    195                 return FRONT_SIDE; 
    196         } 
    197  
    198         return COINCIDENT; 
    199 } 
    200  
    201 /****************************************************************/ 
    202 /*                  class BspTree implementation                */ 
    203 /****************************************************************/ 
    204  
    205 BspTree::BspTree(const ViewCellContainer &viewCells):  
    206 mMaxPolys(0), mMaxDepth(0), mRoot(NULL) 
    207 { 
    208         //mRootCell = cell; 
    209         Subdivide(viewCells); 
    210 } 
    211  
    212 BspTree::BspTree(const ObjectContainer &objects, int maxPolys, int maxDepth): 
    213 mMaxPolys(maxPolys), mMaxDepth(maxDepth) 
    214 { 
    215         mRoot = new BspLeaf(); 
    216  
    217         Subdivide(objects); 
    218 } 
    219   
    220 BspTree::~BspTree() 
    221 { 
    222         std::stack<BspNode *> tStack; 
    223  
    224         tStack.push(mRoot); 
    225  
    226         while (!tStack.empty()) 
    227         { 
    228                 BspNode *node = tStack.top(); 
    229  
    230             tStack.pop(); 
    231          
    232                 if (!node->IsLeaf()) 
    233                 { 
    234                         BspInterior *interior = dynamic_cast<BspInterior *>(node); 
    235  
    236                         // push the children on the stack (there are always two children) 
    237                         interior->GetBack()->mParent = NULL; 
    238                         interior->GetFront()->mParent = NULL; 
    239  
    240                         tStack.push(interior->GetBack()); 
    241                         tStack.push(interior->GetFront()); 
    242                 } 
    243  
    244                 DEL_PTR(node); 
    245         } 
    246 } 
    247  
    248  
    249 void BspTree::InsertViewCell(ViewCell *viewCell) 
    250 { 
    251         std::stack<BspTraversalData> tStack; 
    252          
    253         PolygonQueue polys; 
    254         // copy polygon information to guide the split process 
    255         CopyMesh2Polygon(viewCell->GetMesh(), polys); 
    256  
    257         tStack.push(BspTraversalData(mRoot, NULL, &polys, 0)); 
    258  
    259         while (!tStack.empty()) 
    260         { 
    261                 /*BspNode *node = tStack.top(); 
    262  
    263             tStack.pop(); 
    264          
    265                 if (!node->IsLeaf()) 
    266                 { 
    267                         BspInterior *interior = dynamic_cast<BspInterior *>(node); 
    268  
    269                         // push the children on the stack (there are always two children) 
    270                         interior->GetBack()->mParent = NULL; 
    271                         interior->GetFront()->mParent = NULL; 
    272  
    273                         tStack.push(interior->GetBack()); 
    274                         tStack.push(interior->GetFront()); 
    275                 } 
    276  
    277                 DEL_PTR(node);*/ 
    278         } 
    279 /*      BspNode *currentNode = mRoot; 
    280    
    281         std::stack<BspTraversalData> tStack; 
    282         //  stack<STraversalData> tStack; 
    283  
    284         //tStack.push(tdata); 
    285  
    286         while (!tStack.empty())  
    287         { 
    288             BspTraversalData data = tStack.top(); 
    289  
    290             tStack.pop(); 
    291      
    292                 Mesh backPolys; 
    293                 Mesh frontPolys; 
    294  
    295                 if (data.mNode->IsLeaf()) // if we have a leaf => subdivide 
    296                 { 
    297                         BspNode *node = SubdivideNode(dynamic_cast<BspLeaf *>(data.mNode), 
    298                                                                                   data.mParent, 
    299                                                                                   data.mPolys, 
    300                                                                               data.mDepth, 
    301                                                                                   backPolys, 
    302                                                                                   frontPolys); 
    303          
    304                         if (!node->IsLeaf()) // node was subdivided 
    305                         { 
    306                                 BspInterior *interior = dynamic_cast<BspInterior *>(node); 
    307  
    308                                 // push the children on the stack (there are always two children) 
    309                                 //tStack.push(BspTraversalData(interior->GetBack(), interior, backPolys, data.mDepth + 1)); 
    310                                 //tStack.push(BspTraversalData(interior->GetFront(), interior, frontPolys, data.mDepth + 1)); 
    311                         } 
    312                 } 
    313         }*/ 
    314 } 
    315  
    316 void BspTree::Subdivide(const ViewCellContainer &viewCells) 
    317 { 
    318 } 
    319  
    320 void BspTree::CopyMesh2Polygon(Mesh *mesh, PolygonQueue &polys) 
    321 { 
    322         FaceContainer::const_iterator fi; 
    323         // copy the face data to polygons 
    324         for (fi = mesh->mFaces.begin(); fi != mesh->mFaces.end(); ++ fi) 
    325         { 
    326                 Polygon *poly = new Polygon((*fi), mesh); 
    327                 polys.push(poly); 
    328         } 
    329 } 
    330  
    331 void BspTree::Copy2PolygonSoup(const ObjectContainer &objects, PolygonQueue &polys) 
    332 { 
    333         ObjectContainer::const_iterator it, it_end = objects.end(); 
    334  
    335         for (it = objects.begin(); it != it_end; ++ it) 
    336         { 
    337                 Intersectable *object = *it; 
    338  
    339                 // extract the mesh instances 
    340                 if (object->Type() == Intersectable::MESH_INSTANCE) 
    341                 { 
    342                         MeshInstance *inst = dynamic_cast<MeshInstance *>(object); 
    343  
    344                         Mesh *mesh = inst->GetMesh(); 
    345  
    346                         // copy the mesh data to polygons 
    347                         CopyMesh2Polygon(mesh, polys); 
    348                 } 
    349         } 
    350 } 
    351  
    352 void BspTree::Subdivide(const ObjectContainer &objects) 
    353 { 
    354         std::stack<BspTraversalData> tStack; 
    355         PolygonQueue polys; 
    356          
    357         // copy mesh instance polygons into one big polygon soup 
    358         Copy2PolygonSoup(objects, polys); 
    359  
    360         BspTraversalData tdata(mRoot, mRoot->GetParent(), &polys, 0); 
    361         tStack.push(tdata); 
    362  
    363         while (!tStack.empty())  
    364         { 
    365             BspTraversalData data = tStack.top(); 
    366  
    367             tStack.pop(); 
    368      
    369                 PolygonQueue *backPolys = new PolygonQueue(); 
    370                 PolygonQueue *frontPolys = new PolygonQueue(); 
    371  
    372                 BspNode *node = SubdivideNode(dynamic_cast<BspLeaf *>(data.mNode), 
    373                                                                           data.mParent, 
    374                                                                           data.mPolys, 
    375                                                                       data.mDepth, 
    376                                                                           backPolys, 
    377                                                                           frontPolys); 
    378          
    379                 if (!node->IsLeaf()) // node was subdivided 
    380                 { 
    381                         BspInterior *interior = dynamic_cast<BspInterior *>(node); 
    382  
    383                         // push the children on the stack (there are always two children) 
    384                         tStack.push(BspTraversalData(interior->GetBack(), interior, backPolys, data.mDepth + 1)); 
    385                         tStack.push(BspTraversalData(interior->GetFront(), interior, frontPolys, data.mDepth + 1)); 
    386                 } 
    387         } 
    388 } 
    389  
    390 Plane3 BspTree::SelectPlane(PolygonQueue *polyQueue)  
    391 { 
    392         // TODO: more sophisticated criteria 
    393         return polyQueue->front()->GetSupportingPlane(); 
    394 } 
    395  
    396 BspNode *BspTree::SubdivideNode(BspLeaf *leaf, BspInterior *parent,  
    397                                                                 PolygonQueue *polys, const int depth,  
    398                                                                 PolygonQueue *frontPolys, PolygonQueue *backPolys) 
    399 { 
    400         // terminate traversal if no more faces in mesh 
    401         if ((polys->size() <= mMaxPolys) || (depth >= mMaxDepth)) 
    402         { 
    403                 // don't need to store polygon information = delete polygons 
    404                 Polygon::DeletePolygons(polys); 
    405                  
    406                 return leaf; 
    407         } 
    408  
    409         // add the new nodes to the tree + select subdivision plane 
    410         BspInterior *node = new BspInterior(SelectPlane(polys));  
    411  
    412         while (!polys->empty()) 
    413         { 
    414                 Polygon *poly = polys->front(); 
    415  
    416                 polys->pop(); 
    417  
    418                 int  result = 0;// = node->GetPlane()->Side(node->GetPlane()); 
     76 
     77                int result = poly->Side(&mPlane); 
    41978 
    42079                Polygon *front_piece = NULL; 
    … …  
    42483                { 
    42584                        case Polygon::COINCIDENT: 
     85                                break; 
    42686                        case Polygon::FRONT_SIDE: 
    42787                                frontPolys->push(poly); 
    … …  
    43595 
    43696                                //-- split polygon 
    437                 poly->Split(node->GetPlane(), front_piece, back_piece); 
    438  
     97                poly->Split(&mPlane, front_piece, back_piece); 
    43998 
    44099                                backPolys->push(back_piece); 
    … …  
    445104                                break; 
    446105                        default: 
    447                                 frontPolys->push(poly); 
    448106                                break; 
    449107                } 
    450108        } 
    451  
    452         // backside of convex view cell polygon => outside 
     109        // delete old polygons 
     110        Polygon::DeletePolygons(polys); 
     111} 
     112 
     113/****************************************************************/ 
     114/*                  class BspLeaf implementation                */ 
     115/****************************************************************/ 
     116 
     117BspLeaf::BspLeaf(ViewCell *viewCell): mViewCell(viewCell)  
     118{ 
     119} 
     120 
     121ViewCell *BspLeaf::GetViewCell() 
     122{ 
     123        return mViewCell; 
     124} 
     125 
     126bool BspLeaf::IsLeaf() const  
     127{  
     128        return true;  
     129} 
     130 
     131/****************************************************************/ 
     132/*                  class Polygon implementation                */ 
     133/****************************************************************/ 
     134 
     135Polygon::Polygon() 
     136{} 
     137 
     138Polygon::Polygon(const VertexContainer &vertices): mVertices(vertices)  
     139{} 
     140 
     141Polygon::Polygon(Face *face, Mesh *parent) 
     142{ 
     143        VertexIndexContainer::const_iterator it; 
     144 
     145        for (it = face->mVertexIndices.begin(); it != face->mVertexIndices.end(); ++ it) 
     146        { 
     147                mVertices.push_back(parent->mVertices[*it]); 
     148        } 
     149} 
     150 
     151Plane3 Polygon::GetSupportingPlane() 
     152{ 
     153        return Plane3(mVertices[0], mVertices[1], mVertices[2]); 
     154} 
     155 
     156void Polygon::DeletePolygons(PolygonQueue *polys) 
     157{ 
     158        // don't need to store polygon information = delete polygons 
     159        while(!polys->empty()) 
     160        { 
     161                Polygon *poly = polys->front(); 
     162                polys->pop(); 
     163                DEL_PTR(poly); 
     164        } 
     165} 
     166 
     167void Polygon::Split(Plane3 *partition, Polygon *front, Polygon *back) 
     168{ 
     169        Vector3 ptA = mVertices[mVertices.size() - 1];; 
     170         
     171        int sideA = partition->Side(ptA); 
     172         
     173        VertexContainer::const_iterator it; 
     174 
     175        // find line - plane intersections 
     176        for (it = mVertices.begin(); it != mVertices.end(); ++ it) 
     177        { 
     178                Vector3 ptB = (*it); 
     179                int sideB = partition->Side(ptB); 
     180 
     181                // vertices on different sides => split 
     182                if ((sideA != 0) && (sideB != 0) && (sideA != sideB))  
     183                { 
     184                        Vector3 v = ptB - ptA; // line from A to B 
     185                        float dv = DotProd(partition->mNormal, v); 
     186                        float t = 0; 
     187                         
     188                        if (dv) 
     189                        { 
     190                                t = - partition->Distance(ptA) / dv; 
     191                        } 
     192                } 
     193                if (sideB >= 0) 
     194                { 
     195                        back->mVertices.push_back(ptB); 
     196                } 
     197                else if (sideB <= 0) 
     198                { 
     199                        front->mVertices.push_back(ptB); 
     200                } 
     201 
     202                ptA = ptB; 
     203                sideA = sideB; 
     204        } 
     205} 
     206 
     207int Polygon::Side(Plane3 *plane) 
     208{ 
     209        VertexContainer::const_iterator it; 
     210 
     211        bool onFrontSide = false; 
     212        bool onBackSide = false; 
     213 
     214        // find line - plane intersections 
     215        for (it = mVertices.begin(); it != mVertices.end(); ++ it) 
     216        { 
     217                int side = plane->Side(*it); 
     218                 
     219                if (side > 0) 
     220                { 
     221                        onFrontSide = true; 
     222                } 
     223                else if (side < 0) 
     224                { 
     225                        onBackSide = true; 
     226                } 
     227 
     228                if (onFrontSide && onBackSide) // splits 
     229                        return SPLIT; 
     230        } 
     231 
     232        if (onBackSide) 
     233        { 
     234                return BACK_SIDE; 
     235        } 
     236        else if (onFrontSide) 
     237        { 
     238                return FRONT_SIDE; 
     239        } 
     240 
     241        return COINCIDENT; 
     242} 
     243 
     244/****************************************************************/ 
     245/*                  class BspTree implementation                */ 
     246/****************************************************************/ 
     247 
     248BspTree::BspTree(const ViewCellContainer &viewCells):  
     249mMaxPolys(0), mMaxDepth(0), mRoot(NULL) 
     250{ 
     251        //mRootCell = cell; 
     252        Subdivide(viewCells); 
     253} 
     254 
     255BspTree::BspTree(const ObjectContainer &objects, int maxPolys, int maxDepth): 
     256mMaxPolys(maxPolys), mMaxDepth(maxDepth) 
     257{ 
     258        mRoot = new BspLeaf(); 
     259 
     260        Subdivide(objects); 
     261} 
     262  
     263BspTree::~BspTree() 
     264{ 
     265        std::stack<BspNode *> tStack; 
     266 
     267        tStack.push(mRoot); 
     268 
     269        while (!tStack.empty()) 
     270        { 
     271                BspNode *node = tStack.top(); 
     272 
     273            tStack.pop(); 
     274         
     275                if (!node->IsLeaf()) 
     276                { 
     277                        BspInterior *interior = dynamic_cast<BspInterior *>(node); 
     278 
     279                        // push the children on the stack (there are always two children) 
     280                        interior->GetBack()->mParent = NULL; 
     281                        interior->GetFront()->mParent = NULL; 
     282 
     283                        tStack.push(interior->GetBack()); 
     284                        tStack.push(interior->GetFront()); 
     285                } 
     286 
     287                DEL_PTR(node); 
     288        } 
     289} 
     290 
     291 
     292void BspTree::InsertViewCell(ViewCell *viewCell) 
     293{ 
     294        std::stack<BspTraversalData> tStack; 
     295         
     296        PolygonQueue polys; 
     297        // copy polygon information to guide the split process 
     298        CopyMesh2Polygon(viewCell->GetMesh(), polys); 
     299 
     300        tStack.push(BspTraversalData(mRoot, NULL, &polys, 0, viewCell)); 
     301 
     302        while (!tStack.empty()) 
     303        { 
     304                // filter polygons donw the tree 
     305                BspTraversalData tData = tStack.top(); 
     306 
     307            tStack.pop(); 
     308         
     309        if (!tData.mNode->IsLeaf()) 
     310                { 
     311                        BspInterior *interior = dynamic_cast<BspInterior *>(tData.mNode); 
     312 
     313                        // filter polygons down the tree. 
     314                        PolygonQueue *frontPolys = new PolygonQueue(); 
     315                        PolygonQueue *backPolys = new PolygonQueue(); 
     316 
     317                        interior->SplitPolygons(tData.mPolys, frontPolys, backPolys); 
     318 
     319                        // push the children on the stack 
     320                        if (frontPolys->size() > 0) 
     321                                tStack.push(BspTraversalData(interior->GetFront(), interior->GetParent(), frontPolys, tData.mDepth + 1)); 
     322                        else 
     323                                delete frontPolys; 
     324 
     325                        if (backPolys > 0) 
     326                                tStack.push(BspTraversalData(interior->GetBack(), interior->GetParent(), backPolys, tData.mDepth + 1)); // TODO: really need to keep viewcell?? 
     327                        else 
     328                                delete backPolys; 
     329                } 
     330                else // reached leaf and must split 
     331                { 
     332                        BuildTree(tStack, tData); 
     333                } 
     334        } 
     335/*      BspNode *currentNode = mRoot; 
     336   
     337        std::stack<BspTraversalData> tStack; 
     338        //  stack<STraversalData> tStack; 
     339 
     340        //tStack.push(tdata); 
     341 
     342        while (!tStack.empty())  
     343        { 
     344            BspTraversalData data = tStack.top(); 
     345 
     346            tStack.pop(); 
     347     
     348                Mesh backPolys; 
     349                Mesh frontPolys; 
     350 
     351                if (data.mNode->IsLeaf()) // if we have a leaf => subdivide 
     352                { 
     353                        BspNode *node = SubdivideNode(dynamic_cast<BspLeaf *>(data.mNode), 
     354                                                                                  data.mParent, 
     355                                                                                  data.mPolys, 
     356                                                                              data.mDepth, 
     357                                                                                  data.viewCell, 
     358                                                                                  backPolys, 
     359                                                                                  frontPolys); 
     360         
     361                        if (!node->IsLeaf()) // node was subdivided 
     362                        { 
     363                                BspInterior *interior = dynamic_cast<BspInterior *>(node); 
     364 
     365                                // push the children on the stack (there are always two children) 
     366                                //tStack.push(BspTraversalData(interior->GetBack(), interior, backPolys, data.mDepth + 1)); 
     367                                //tStack.push(BspTraversalData(interior->GetFront(), interior, frontPolys, data.mDepth + 1)); 
     368                        } 
     369                } 
     370        }*/ 
     371} 
     372 
     373void BspTree::Subdivide(const ViewCellContainer &viewCells) 
     374{ 
     375} 
     376 
     377void BspTree::CopyMesh2Polygon(Mesh *mesh, PolygonQueue &polys) 
     378{ 
     379        FaceContainer::const_iterator fi; 
     380        // copy the face data to polygons 
     381        for (fi = mesh->mFaces.begin(); fi != mesh->mFaces.end(); ++ fi) 
     382        { 
     383                Polygon *poly = new Polygon((*fi), mesh); 
     384                polys.push(poly); 
     385        } 
     386} 
     387 
     388void BspTree::Copy2PolygonSoup(const ObjectContainer &objects, PolygonQueue &polys) 
     389{ 
     390        ObjectContainer::const_iterator it, it_end = objects.end(); 
     391 
     392        for (it = objects.begin(); it != it_end; ++ it) 
     393        { 
     394                Intersectable *object = *it; 
     395 
     396                // extract the mesh instances 
     397                if (object->Type() == Intersectable::MESH_INSTANCE) 
     398                { 
     399                        MeshInstance *inst = dynamic_cast<MeshInstance *>(object); 
     400 
     401                        Mesh *mesh = inst->GetMesh(); 
     402 
     403                        // copy the mesh data to polygons 
     404                        CopyMesh2Polygon(mesh, polys); 
     405                } 
     406        } 
     407} 
     408 
     409void BspTree::Subdivide(const ObjectContainer &objects) 
     410{ 
     411        std::stack<BspTraversalData> tStack; 
     412        PolygonQueue *polys = new PolygonQueue(); 
     413         
     414        // copy mesh instance polygons into one big polygon soup 
     415        Copy2PolygonSoup(objects, *polys); 
     416 
     417        BspTraversalData tData(mRoot, mRoot->GetParent(), polys, 0, NULL); 
     418        tStack.push(tData); 
     419 
     420        while (!tStack.empty())  
     421        { 
     422            tData = tStack.top(); 
     423 
     424            tStack.pop(); 
     425     
     426                BuildTree(tStack, tData); 
     427        } 
     428} 
     429 
     430void BspTree::BuildTree(BspTraversalStack &tStack, BspTraversalData &currentData) 
     431{ 
     432        PolygonQueue *backPolys = new PolygonQueue(); 
     433        PolygonQueue *frontPolys = new PolygonQueue(); 
     434 
     435        BspNode *node = SubdivideNode(dynamic_cast<BspLeaf *>(currentData.mNode), 
     436                                                                  currentData.mParent, 
     437                                                                  currentData.mPolys, 
     438                                                                  currentData.mDepth, 
     439                                                                  currentData.mViewCell, 
     440                                                                  backPolys, 
     441                                                                  frontPolys); 
     442         
     443        if (!node->IsLeaf()) // node was subdivided 
     444        { 
     445                BspInterior *interior = dynamic_cast<BspInterior *>(node); 
     446 
     447                // push the children on the stack (there are always two children) 
     448                tStack.push(BspTraversalData(interior->GetBack(), interior, backPolys, currentData.mDepth + 1, NULL)); 
     449                tStack.push(BspTraversalData(interior->GetFront(), interior, frontPolys, currentData.mDepth + 1, currentData.mViewCell)); 
     450        } 
     451} 
     452 
     453Plane3 BspTree::SelectPlane(PolygonQueue *polyQueue)  
     454{ 
     455        // TODO: more sophisticated criteria 
     456        return polyQueue->front()->GetSupportingPlane(); 
     457} 
     458 
     459BspNode *BspTree::SubdivideNode(BspLeaf *leaf,  
     460                                                                BspInterior *parent,  
     461                                                                PolygonQueue *polys,  
     462                                                                const int depth,  
     463                                                                ViewCell *viewCell, 
     464                                                                PolygonQueue *frontPolys,  
     465                                                                PolygonQueue *backPolys) 
     466{ 
     467        // terminate traversal if no more faces in mesh 
     468        if ((polys->size() <= mMaxPolys) || (depth >= mMaxDepth)) 
     469        { 
     470                // don't need to store polygon information = delete polygons 
     471                Polygon::DeletePolygons(polys); 
     472                 
     473                return leaf; 
     474        } 
     475 
     476        // add the new nodes to the tree + select subdivision plane 
     477        BspInterior *node = new BspInterior(SelectPlane(polys));  
     478 
     479        // split polygon according to current plane 
     480        node->SplitPolygons(polys, frontPolys, backPolys); 
     481         
     482        // two new leaves 
    453483        BspLeaf *back = new BspLeaf(); 
    454         BspLeaf *front = new BspLeaf(); 
     484        BspLeaf *front = new BspLeaf(viewCell); 
    455485 
    456486        // replace a link from node's parent 
    … …  
    467497        return node; 
    468498} 
    469  
    470499//} // GtpVisibilityPreprocessor 
Note: See TracChangeset for help on using the changeset viewer.