Changeset 233 for trunk

Timestamp:

08/10/05 17:09:29 (19 years ago)

Author:

mattausch

Message:

updated bsp viewcells

Location:

trunk/VUT/GtpVisibilityPreprocessor/src

Files:

• ViewCellBsp.cpp (modified) (5 diffs)
• ViewCellBsp.h (modified) (2 diffs)

trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.cpp

@@ -67 +67 @@
 }
 
-/****************************************************************/
-/*                  class BspLeaf implementation                */
-/****************************************************************/
-
-BspLeaf::BspLeaf(ViewCell *viewCell): mViewCell(viewCell) 
-{
-}
-
-ViewCell *BspLeaf::GetViewCell()
-{
-        return mViewCell;
-}
-
-bool BspLeaf::IsLeaf() const 
-{ 
-        return true; 
-}
-
-/****************************************************************/
-/*                  class Polygon implementation                */
-/****************************************************************/
-
-Polygon::Polygon()
-{}
-
-Polygon::Polygon(const VertexContainer &vertices): mVertices(vertices) 
-{}
-
-Polygon::Polygon(Face *face, Mesh *parent)
-{
-        VertexIndexContainer::const_iterator it;
-
-        for (it = face->mVertexIndices.begin(); it != face->mVertexIndices.end(); ++ it)
-        {
-                mVertices.push_back(parent->mVertices[*it]);
-        }
-}
-
-Plane3 Polygon::GetSupportingPlane()
-{
-        return Plane3(mVertices[0], mVertices[1], mVertices[2]);
-}
-
-void Polygon::DeletePolygons(PolygonQueue *polys)
-{
-        // don't need to store polygon information = delete polygons
-        while(!polys->empty())
+void BspInterior::SplitPolygons(PolygonQueue *polys, PolygonQueue *frontPolys, PolygonQueue *backPolys)
+{
+        while (!polys->empty())
         {
                 Polygon *poly = polys->front();
+
                 polys->pop();
-                DEL_PTR(poly);
-        }
-
-}
-
-void Polygon::Split(Plane3 *partition, Polygon *front, Polygon *back)
-{
-        Vector3 ptA = mVertices[mVertices.size() - 1];;
-        
-        int sideA = partition->Side(ptA);
-        
-        VertexContainer::const_iterator it;
-
-        // find line - plane intersections
-        for (it = mVertices.begin(); it != mVertices.end(); ++ it)
-        {
-                Vector3 ptB = (*it);
-                int sideB = partition->Side(ptB);
-
-                // vertices on different sides => split
-                if ((sideA != 0) && (sideB != 0) && (sideA != sideB)) 
-                {
-                        Vector3 v = ptB - ptA; // line from A to B
-                        float dv = DotProd(partition->mNormal, v);
-                        float t = 0;
-                        
-                        if (dv)
-                        {
-                                t = - partition->Distance(ptA) / dv;
-                        }
-                }
-                if (sideB >= 0)
-                {
-                        back->mVertices.push_back(ptB);
-                }
-                else if (sideB <= 0)
-                {
-                        front->mVertices.push_back(ptB);
-                }
-
-                ptA = ptB;
-                sideA = sideB;
-        }
-}
-
-int Polygon::Side(Plane3 *plane)
-{
-        VertexContainer::const_iterator it;
-
-        bool onFrontSide = false;
-        bool onBackSide = false;
-
-        // find line - plane intersections
-        for (it = mVertices.begin(); it != mVertices.end(); ++ it)
-        {
-                int side = plane->Side(*it);
-                
-                if (side > 0)
-                {
-                        onFrontSide = true;
-                }
-                else if (side < 0)
-                {
-                        onBackSide = true;
-                }
-
-                if (onFrontSide && onBackSide) // splits
-                        return SPLIT;
-        }
-
-        if (onBackSide)
-        {
-                return BACK_SIDE;
-        }
-        else if (onFrontSide)
-        {
-                return FRONT_SIDE;
-        }
-
-        return COINCIDENT;
-}
-
-/****************************************************************/
-/*                  class BspTree implementation                */
-/****************************************************************/
-
-BspTree::BspTree(const ViewCellContainer &viewCells): 
-mMaxPolys(0), mMaxDepth(0), mRoot(NULL)
-{
-        //mRootCell = cell;
-        Subdivide(viewCells);
-}
-
-BspTree::BspTree(const ObjectContainer &objects, int maxPolys, int maxDepth):
-mMaxPolys(maxPolys), mMaxDepth(maxDepth)
-{
-        mRoot = new BspLeaf();
-
-        Subdivide(objects);
-}
- 
-BspTree::~BspTree()
-{
-        std::stack<BspNode *> tStack;
-
-        tStack.push(mRoot);
-
-        while (!tStack.empty())
-        {
-                BspNode *node = tStack.top();
-
-            tStack.pop();
-        
-                if (!node->IsLeaf())
-                {
-                        BspInterior *interior = dynamic_cast<BspInterior *>(node);
-
-                        // push the children on the stack (there are always two children)
-                        interior->GetBack()->mParent = NULL;
-                        interior->GetFront()->mParent = NULL;
-
-                        tStack.push(interior->GetBack());
-                        tStack.push(interior->GetFront());
-                }
-
-                DEL_PTR(node);
-        }
-}
-
-
-void BspTree::InsertViewCell(ViewCell *viewCell)
-{
-        std::stack<BspTraversalData> tStack;
-        
-        PolygonQueue polys;
-        // copy polygon information to guide the split process
-        CopyMesh2Polygon(viewCell->GetMesh(), polys);
-
-        tStack.push(BspTraversalData(mRoot, NULL, &polys, 0));
-
-        while (!tStack.empty())
-        {
-                /*BspNode *node = tStack.top();
-
-            tStack.pop();
-        
-                if (!node->IsLeaf())
-                {
-                        BspInterior *interior = dynamic_cast<BspInterior *>(node);
-
-                        // push the children on the stack (there are always two children)
-                        interior->GetBack()->mParent = NULL;
-                        interior->GetFront()->mParent = NULL;
-
-                        tStack.push(interior->GetBack());
-                        tStack.push(interior->GetFront());
-                }
-
-                DEL_PTR(node);*/
-        }
-/*      BspNode *currentNode = mRoot;
-  
-        std::stack<BspTraversalData> tStack;
-        //  stack<STraversalData> tStack;
-
-        //tStack.push(tdata);
-
-        while (!tStack.empty()) 
-        {
-            BspTraversalData data = tStack.top();
-
-            tStack.pop();
-    
-                Mesh backPolys;
-                Mesh frontPolys;
-
-                if (data.mNode->IsLeaf()) // if we have a leaf => subdivide
-                {
-                        BspNode *node = SubdivideNode(dynamic_cast<BspLeaf *>(data.mNode),
-                                                                                  data.mParent,
-                                                                                  data.mPolys,
-                                                                              data.mDepth,
-                                                                                  backPolys,
-                                                                                  frontPolys);
-        
-                        if (!node->IsLeaf()) // node was subdivided
-                        {
-                                BspInterior *interior = dynamic_cast<BspInterior *>(node);
-
-                                // push the children on the stack (there are always two children)
-                                //tStack.push(BspTraversalData(interior->GetBack(), interior, backPolys, data.mDepth + 1));
-                                //tStack.push(BspTraversalData(interior->GetFront(), interior, frontPolys, data.mDepth + 1));
-                        }
-                }
-        }*/
-}
-
-void BspTree::Subdivide(const ViewCellContainer &viewCells)
-{
-}
-
-void BspTree::CopyMesh2Polygon(Mesh *mesh, PolygonQueue &polys)
-{
-        FaceContainer::const_iterator fi;
-        // copy the face data to polygons
-        for (fi = mesh->mFaces.begin(); fi != mesh->mFaces.end(); ++ fi)
-        {
-                Polygon *poly = new Polygon((*fi), mesh);
-                polys.push(poly);
-        }
-}
-
-void BspTree::Copy2PolygonSoup(const ObjectContainer &objects, PolygonQueue &polys)
-{
-        ObjectContainer::const_iterator it, it_end = objects.end();
-
-        for (it = objects.begin(); it != it_end; ++ it)
-        {
-                Intersectable *object = *it;
-
-                // extract the mesh instances
-                if (object->Type() == Intersectable::MESH_INSTANCE)
-                {
-                        MeshInstance *inst = dynamic_cast<MeshInstance *>(object);
-
-                        Mesh *mesh = inst->GetMesh();
-
-                        // copy the mesh data to polygons
-                        CopyMesh2Polygon(mesh, polys);
-                }
-        }
-}
-
-void BspTree::Subdivide(const ObjectContainer &objects)
-{
-        std::stack<BspTraversalData> tStack;
-        PolygonQueue polys;
-        
-        // copy mesh instance polygons into one big polygon soup
-        Copy2PolygonSoup(objects, polys);
-
-        BspTraversalData tdata(mRoot, mRoot->GetParent(), &polys, 0);
-        tStack.push(tdata);
-
-        while (!tStack.empty()) 
-        {
-            BspTraversalData data = tStack.top();
-
-            tStack.pop();
-    
-                PolygonQueue *backPolys = new PolygonQueue();
-                PolygonQueue *frontPolys = new PolygonQueue();
-
-                BspNode *node = SubdivideNode(dynamic_cast<BspLeaf *>(data.mNode),
-                                                                          data.mParent,
-                                                                          data.mPolys,
-                                                                      data.mDepth,
-                                                                          backPolys,
-                                                                          frontPolys);
-        
-                if (!node->IsLeaf()) // node was subdivided
-                {
-                        BspInterior *interior = dynamic_cast<BspInterior *>(node);
-
-                        // push the children on the stack (there are always two children)
-                        tStack.push(BspTraversalData(interior->GetBack(), interior, backPolys, data.mDepth + 1));
-                        tStack.push(BspTraversalData(interior->GetFront(), interior, frontPolys, data.mDepth + 1));
-                }
-        }
-}
-
-Plane3 BspTree::SelectPlane(PolygonQueue *polyQueue) 
-{
-        // TODO: more sophisticated criteria
-        return polyQueue->front()->GetSupportingPlane();
-}
-
-BspNode *BspTree::SubdivideNode(BspLeaf *leaf, BspInterior *parent, 
-                                                                PolygonQueue *polys, const int depth, 
-                                                                PolygonQueue *frontPolys, PolygonQueue *backPolys)
-{
-        // terminate traversal if no more faces in mesh
-        if ((polys->size() <= mMaxPolys) || (depth >= mMaxDepth))
-        {
-                // don't need to store polygon information = delete polygons
-                Polygon::DeletePolygons(polys);
-                
-                return leaf;
-        }
-
-        // add the new nodes to the tree + select subdivision plane
-        BspInterior *node = new BspInterior(SelectPlane(polys)); 
-
-        while (!polys->empty())
-        {
-                Polygon *poly = polys->front();
-
-                polys->pop();
-
-                int  result = 0;// = node->GetPlane()->Side(node->GetPlane());
+
+                int result = poly->Side(&mPlane);
 
                 Polygon *front_piece = NULL;
@@ -424 +83 @@
                 {
                         case Polygon::COINCIDENT:
+                                break;
                         case Polygon::FRONT_SIDE:
                                 frontPolys->push(poly);
@@ -435 +95 @@
 
                                 //-- split polygon
-                poly->Split(node->GetPlane(), front_piece, back_piece);
-
+                poly->Split(&mPlane, front_piece, back_piece);
 
                                 backPolys->push(back_piece);
@@ -445 +104 @@
                                 break;
                         default:
-                                frontPolys->push(poly);
                                 break;
                 }
         }
-
-        // backside of convex view cell polygon => outside
+        // delete old polygons
+        Polygon::DeletePolygons(polys);
+}
+
+/****************************************************************/
+/*                  class BspLeaf implementation                */
+/****************************************************************/
+
+BspLeaf::BspLeaf(ViewCell *viewCell): mViewCell(viewCell) 
+{
+}
+
+ViewCell *BspLeaf::GetViewCell()
+{
+        return mViewCell;
+}
+
+bool BspLeaf::IsLeaf() const 
+{ 
+        return true; 
+}
+
+/****************************************************************/
+/*                  class Polygon implementation                */
+/****************************************************************/
+
+Polygon::Polygon()
+{}
+
+Polygon::Polygon(const VertexContainer &vertices): mVertices(vertices) 
+{}
+
+Polygon::Polygon(Face *face, Mesh *parent)
+{
+        VertexIndexContainer::const_iterator it;
+
+        for (it = face->mVertexIndices.begin(); it != face->mVertexIndices.end(); ++ it)
+        {
+                mVertices.push_back(parent->mVertices[*it]);
+        }
+}
+
+Plane3 Polygon::GetSupportingPlane()
+{
+        return Plane3(mVertices[0], mVertices[1], mVertices[2]);
+}
+
+void Polygon::DeletePolygons(PolygonQueue *polys)
+{
+        // don't need to store polygon information = delete polygons
+        while(!polys->empty())
+        {
+                Polygon *poly = polys->front();
+                polys->pop();
+                DEL_PTR(poly);
+        }
+}
+
+void Polygon::Split(Plane3 *partition, Polygon *front, Polygon *back)
+{
+        Vector3 ptA = mVertices[mVertices.size() - 1];;
+        
+        int sideA = partition->Side(ptA);
+        
+        VertexContainer::const_iterator it;
+
+        // find line - plane intersections
+        for (it = mVertices.begin(); it != mVertices.end(); ++ it)
+        {
+                Vector3 ptB = (*it);
+                int sideB = partition->Side(ptB);
+
+                // vertices on different sides => split
+                if ((sideA != 0) && (sideB != 0) && (sideA != sideB)) 
+                {
+                        Vector3 v = ptB - ptA; // line from A to B
+                        float dv = DotProd(partition->mNormal, v);
+                        float t = 0;
+                        
+                        if (dv)
+                        {
+                                t = - partition->Distance(ptA) / dv;
+                        }
+                }
+                if (sideB >= 0)
+                {
+                        back->mVertices.push_back(ptB);
+                }
+                else if (sideB <= 0)
+                {
+                        front->mVertices.push_back(ptB);
+                }
+
+                ptA = ptB;
+                sideA = sideB;
+        }
+}
+
+int Polygon::Side(Plane3 *plane)
+{
+        VertexContainer::const_iterator it;
+
+        bool onFrontSide = false;
+        bool onBackSide = false;
+
+        // find line - plane intersections
+        for (it = mVertices.begin(); it != mVertices.end(); ++ it)
+        {
+                int side = plane->Side(*it);
+                
+                if (side > 0)
+                {
+                        onFrontSide = true;
+                }
+                else if (side < 0)
+                {
+                        onBackSide = true;
+                }
+
+                if (onFrontSide && onBackSide) // splits
+                        return SPLIT;
+        }
+
+        if (onBackSide)
+        {
+                return BACK_SIDE;
+        }
+        else if (onFrontSide)
+        {
+                return FRONT_SIDE;
+        }
+
+        return COINCIDENT;
+}
+
+/****************************************************************/
+/*                  class BspTree implementation                */
+/****************************************************************/
+
+BspTree::BspTree(const ViewCellContainer &viewCells): 
+mMaxPolys(0), mMaxDepth(0), mRoot(NULL)
+{
+        //mRootCell = cell;
+        Subdivide(viewCells);
+}
+
+BspTree::BspTree(const ObjectContainer &objects, int maxPolys, int maxDepth):
+mMaxPolys(maxPolys), mMaxDepth(maxDepth)
+{
+        mRoot = new BspLeaf();
+
+        Subdivide(objects);
+}
+ 
+BspTree::~BspTree()
+{
+        std::stack<BspNode *> tStack;
+
+        tStack.push(mRoot);
+
+        while (!tStack.empty())
+        {
+                BspNode *node = tStack.top();
+
+            tStack.pop();
+        
+                if (!node->IsLeaf())
+                {
+                        BspInterior *interior = dynamic_cast<BspInterior *>(node);
+
+                        // push the children on the stack (there are always two children)
+                        interior->GetBack()->mParent = NULL;
+                        interior->GetFront()->mParent = NULL;
+
+                        tStack.push(interior->GetBack());
+                        tStack.push(interior->GetFront());
+                }
+
+                DEL_PTR(node);
+        }
+}
+
+
+void BspTree::InsertViewCell(ViewCell *viewCell)
+{
+        std::stack<BspTraversalData> tStack;
+        
+        PolygonQueue polys;
+        // copy polygon information to guide the split process
+        CopyMesh2Polygon(viewCell->GetMesh(), polys);
+
+        tStack.push(BspTraversalData(mRoot, NULL, &polys, 0, viewCell));
+
+        while (!tStack.empty())
+        {
+                // filter polygons donw the tree
+                BspTraversalData tData = tStack.top();
+
+            tStack.pop();
+        
+        if (!tData.mNode->IsLeaf())
+                {
+                        BspInterior *interior = dynamic_cast<BspInterior *>(tData.mNode);
+
+                        // filter polygons down the tree.
+                        PolygonQueue *frontPolys = new PolygonQueue();
+                        PolygonQueue *backPolys = new PolygonQueue();
+
+                        interior->SplitPolygons(tData.mPolys, frontPolys, backPolys);
+
+                        // push the children on the stack
+                        if (frontPolys->size() > 0)
+                                tStack.push(BspTraversalData(interior->GetFront(), interior->GetParent(), frontPolys, tData.mDepth + 1));
+                        else
+                                delete frontPolys;
+
+                        if (backPolys > 0)
+                                tStack.push(BspTraversalData(interior->GetBack(), interior->GetParent(), backPolys, tData.mDepth + 1)); // TODO: really need to keep viewcell??
+                        else
+                                delete backPolys;
+                }
+                else // reached leaf and must split
+                {
+                        BuildTree(tStack, tData);
+                }
+        }
+/*      BspNode *currentNode = mRoot;
+  
+        std::stack<BspTraversalData> tStack;
+        //  stack<STraversalData> tStack;
+
+        //tStack.push(tdata);
+
+        while (!tStack.empty()) 
+        {
+            BspTraversalData data = tStack.top();
+
+            tStack.pop();
+    
+                Mesh backPolys;
+                Mesh frontPolys;
+
+                if (data.mNode->IsLeaf()) // if we have a leaf => subdivide
+                {
+                        BspNode *node = SubdivideNode(dynamic_cast<BspLeaf *>(data.mNode),
+                                                                                  data.mParent,
+                                                                                  data.mPolys,
+                                                                              data.mDepth,
+                                                                                  data.viewCell,
+                                                                                  backPolys,
+                                                                                  frontPolys);
+        
+                        if (!node->IsLeaf()) // node was subdivided
+                        {
+                                BspInterior *interior = dynamic_cast<BspInterior *>(node);
+
+                                // push the children on the stack (there are always two children)
+                                //tStack.push(BspTraversalData(interior->GetBack(), interior, backPolys, data.mDepth + 1));
+                                //tStack.push(BspTraversalData(interior->GetFront(), interior, frontPolys, data.mDepth + 1));
+                        }
+                }
+        }*/
+}
+
+void BspTree::Subdivide(const ViewCellContainer &viewCells)
+{
+}
+
+void BspTree::CopyMesh2Polygon(Mesh *mesh, PolygonQueue &polys)
+{
+        FaceContainer::const_iterator fi;
+        // copy the face data to polygons
+        for (fi = mesh->mFaces.begin(); fi != mesh->mFaces.end(); ++ fi)
+        {
+                Polygon *poly = new Polygon((*fi), mesh);
+                polys.push(poly);
+        }
+}
+
+void BspTree::Copy2PolygonSoup(const ObjectContainer &objects, PolygonQueue &polys)
+{
+        ObjectContainer::const_iterator it, it_end = objects.end();
+
+        for (it = objects.begin(); it != it_end; ++ it)
+        {
+                Intersectable *object = *it;
+
+                // extract the mesh instances
+                if (object->Type() == Intersectable::MESH_INSTANCE)
+                {
+                        MeshInstance *inst = dynamic_cast<MeshInstance *>(object);
+
+                        Mesh *mesh = inst->GetMesh();
+
+                        // copy the mesh data to polygons
+                        CopyMesh2Polygon(mesh, polys);
+                }
+        }
+}
+
+void BspTree::Subdivide(const ObjectContainer &objects)
+{
+        std::stack<BspTraversalData> tStack;
+        PolygonQueue *polys = new PolygonQueue();
+        
+        // copy mesh instance polygons into one big polygon soup
+        Copy2PolygonSoup(objects, *polys);
+
+        BspTraversalData tData(mRoot, mRoot->GetParent(), polys, 0, NULL);
+        tStack.push(tData);
+
+        while (!tStack.empty()) 
+        {
+            tData = tStack.top();
+
+            tStack.pop();
+    
+                BuildTree(tStack, tData);
+        }
+}
+
+void BspTree::BuildTree(BspTraversalStack &tStack, BspTraversalData &currentData)
+{
+        PolygonQueue *backPolys = new PolygonQueue();
+        PolygonQueue *frontPolys = new PolygonQueue();
+
+        BspNode *node = SubdivideNode(dynamic_cast<BspLeaf *>(currentData.mNode),
+                                                                  currentData.mParent,
+                                                                  currentData.mPolys,
+                                                                  currentData.mDepth,
+                                                                  currentData.mViewCell,
+                                                                  backPolys,
+                                                                  frontPolys);
+        
+        if (!node->IsLeaf()) // node was subdivided
+        {
+                BspInterior *interior = dynamic_cast<BspInterior *>(node);
+
+                // push the children on the stack (there are always two children)
+                tStack.push(BspTraversalData(interior->GetBack(), interior, backPolys, currentData.mDepth + 1, NULL));
+                tStack.push(BspTraversalData(interior->GetFront(), interior, frontPolys, currentData.mDepth + 1, currentData.mViewCell));
+        }
+}
+
+Plane3 BspTree::SelectPlane(PolygonQueue *polyQueue) 
+{
+        // TODO: more sophisticated criteria
+        return polyQueue->front()->GetSupportingPlane();
+}
+
+BspNode *BspTree::SubdivideNode(BspLeaf *leaf, 
+                                                                BspInterior *parent, 
+                                                                PolygonQueue *polys, 
+                                                                const int depth, 
+                                                                ViewCell *viewCell,
+                                                                PolygonQueue *frontPolys, 
+                                                                PolygonQueue *backPolys)
+{
+        // terminate traversal if no more faces in mesh
+        if ((polys->size() <= mMaxPolys) || (depth >= mMaxDepth))
+        {
+                // don't need to store polygon information = delete polygons
+                Polygon::DeletePolygons(polys);
+                
+                return leaf;
+        }
+
+        // add the new nodes to the tree + select subdivision plane
+        BspInterior *node = new BspInterior(SelectPlane(polys)); 
+
+        // split polygon according to current plane
+        node->SplitPolygons(polys, frontPolys, backPolys);
+        
+        // two new leaves
         BspLeaf *back = new BspLeaf();
-        BspLeaf *front = new BspLeaf();
+        BspLeaf *front = new BspLeaf(viewCell);
 
         // replace a link from node's parent
@@ -467 +497 @@
         return node;
 }
-
 //} // GtpVisibilityPreprocessor

trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.h

@@ -5 +5 @@
 #include "Containers.h"
 #include <queue>
+#include <stack>
 
 class ViewCell;
@@ -15 +16 @@
 class Polygon;
 
-  /**
-     BspNode abstract class serving for interior and leaf node implementation
-  */
-  class BspNode 
-  {
-          friend BspTree;
-
-  public:
-          /** Determines whether this node is a leaf or not
-          @return true if leaf
-          */
-          virtual bool IsLeaf() const = 0;
-    
-          /** Determines whether this node is a root
-          @return true if root
-          */
-          virtual bool IsRoot() const;
-
-          /** Returns parent node.
-          */
-          BspInterior *GetParent();
-          
-  protected:
-
-          /// parent of this node
-          BspInterior *mParent;
-  };
-
-  /** BSP interior node implementation 
-  */
-  class BspInterior : public BspNode 
-  {
-  public:
-          /** Standard contructor taking split plane as argument.
-          */
-          BspInterior(Plane3 plane);
-          /** @return false since it is an interior node 
-          */
-          bool IsLeaf() const;
-
-          BspNode *GetBack();
-          BspNode *GetFront();
-
-          Plane3 *GetPlane();
-
-          void ReplaceChildLink(BspNode *oldChild, BspNode *newChild);
-          void SetupChildLinks(BspNode *b, BspNode *f);
-
-  protected:
+typedef std::queue<Polygon *> PolygonQueue;
+
+/**
+    BspNode abstract class serving for interior and leaf node implementation
+*/
+class BspNode 
+{
+        friend BspTree;
+
+public:
+        /** Determines whether this node is a leaf or not
+        @return true if leaf
+        */
+        virtual bool IsLeaf() const = 0;
+
+        /** Determines whether this node is a root
+        @return true if root
+        */
+        virtual bool IsRoot() const;
+
+        /** Returns parent node.
+        */
+        BspInterior *GetParent();
+        
+protected:
+
+        /// parent of this node
+        BspInterior *mParent;
+};
+
+/** BSP interior node implementation 
+*/
+class BspInterior : public BspNode 
+{
+public:
+        /** Standard contructor taking split plane as argument.
+        */
+        BspInterior(Plane3 plane);
+        /** @return false since it is an interior node 
+        */
+        bool IsLeaf() const;
+
+        BspNode *GetBack();
+        BspNode *GetFront();
+
+        Plane3 *GetPlane();
+
+        void ReplaceChildLink(BspNode *oldChild, BspNode *newChild);
+        void SetupChildLinks(BspNode *b, BspNode *f);
+
+        /** Splits polygons.
+                @param polys the polygons to be split
+                @param frontPolys returns the polygons in the front of the split plane
+                @param backPolys returns the polygons in the back of the split plane
+        */
+        void SplitPolygons(PolygonQueue *polys, PolygonQueue *frontPolys, PolygonQueue *backPolys);
+
+protected:
+        
+        /// Splitting plane corresponding to this node
+        Plane3 mPlane;
+        /// back node
+        BspNode *mBack;
+        /// front node
+        BspNode *mFront;
+};
+
+
+/** BSP leaf node implementation */
+class BspLeaf : public BspNode 
+{
+public:
+        BspLeaf(ViewCell *viewCell = NULL);
+
+        /** @return true since it is an interior node */
+        bool IsLeaf() const;
+        ViewCell *GetViewCell();
+
+protected:
+
+        /// polygonal representation of this viewcell
+        /// if NULL this note does not correspond to feasible viewcell
+        ViewCell *mViewCell;
+};
+
+
+/** Class representing a polygon.
+*/
+class Polygon
+{
+public:
+        Polygon();
+        Polygon(const VertexContainer &vertices);
+
+        /** Copies all the vertices of the face.
+        */
+        Polygon(Face *face, Mesh *parent);
+        
+        /** Returns supporting plane of this polygon.
+        */
+        Plane3 GetSupportingPlane();
+
+        /** Splits polygon.
+                @param partition the split plane
+                @param front the front polygon
+                @param back the back polygon
+        */
+        void Split(Plane3 *partition, Polygon *front, Polygon *back);
+
+        enum {BACK_SIDE, FRONT_SIDE, SPLIT, COINCIDENT};
+
+        /** Side of the plane where the polygon is located.
+            @returns one of BACK_SIDE, FRONT_SIDE, SPLIT, COINCIDENT
+        */
+        int Side(Plane3 *plane);
+
+        static void DeletePolygons(PolygonQueue *polys);
+
+        /// vertices are connected in counterclockwise order.
+        VertexContainer mVertices;
+};
+
+/** Implementation of the ViewCell BSP tree. */
+class BspTree 
+{
+public:
+                
+        /** Additional data which is passed down the BSP tree during traversal.
+        */
+        struct BspTraversalData
+        {  
+                /// the current node
+                BspNode *mNode;
+                /// parent of current node
+                BspInterior *mParent;
+                /// polygonal data for splitting
+                PolygonQueue *mPolys;
+                /// current depth
+                int mDepth;
                 
-          /// Splitting plane corresponding to this node
-          Plane3 mPlane;
-          /// back node
-          BspNode *mBack;
-          /// front node
-          BspNode *mFront;
-  };
-  
-  
-  /** BSP leaf node implementation */
-  class BspLeaf : public BspNode 
-  {
-  public:
-          BspLeaf(ViewCell *viewCell = NULL);
-    
-          /** @return true since it is an interior node */
-          bool IsLeaf() const;
-          ViewCell *GetViewCell();
-
-  protected:
-   
-          /// polygonal representation of this viewcell
-          /// if NULL this note does not correspond to feasible viewcell
-          ViewCell *mViewCell;
-  };
-  
-  typedef std::queue<Polygon *> PolygonQueue;
-
-  /** Class representing a polygon.
-  */
-  class Polygon
-  {
-  public:
-          Polygon();
-          Polygon(const VertexContainer &vertices);
-
-          /** Copies all the vertices of the face.
-          */
-          Polygon(Face *face, Mesh *parent);
-         
-           /** Returns supporting plane of this polygon.
-          */
-          Plane3 GetSupportingPlane();
-
-          /** Splits polygon.
-                  @param partition the split plane
-                  @param front the front polygon
-                  @param back the back polygon
-          */
-          void Split(Plane3 *partition, Polygon *front, Polygon *back);
-
-          enum {BACK_SIDE, FRONT_SIDE, SPLIT, COINCIDENT};
-
-          /** Side of the plane where the polygon is located.
-              @returns one of BACK_SIDE, FRONT_SIDE, SPLIT, COINCIDENT
-          */
-          int Side(Plane3 *plane);
-
-          static void DeletePolygons(PolygonQueue *polys);
-
-          /// vertices are connected in counterclockwise order.
-          VertexContainer mVertices;
-  };
-
-  /** Implementation of the ViewCell BSP tree. */
-  class BspTree 
-  {
-  public:
-                  
-          /** Additional data which is passed down the BSP tree during traversal.
-          */
-          struct BspTraversalData
-          {  
-                  /// the current node
-                  BspNode *mNode;
-                  /// parent of current node
-                  BspInterior *mParent;
-                  /// polygonal data for splitting
-                  PolygonQueue *mPolys;
-                  /// current depth
-                  int mDepth;
-                      
-                  BspTraversalData() {}
-                  
-                  BspTraversalData(BspNode *node, BspInterior *parent, PolygonQueue *polys, const int depth): 
-                  mNode(node), mParent(parent), mPolys(polys), mDepth(depth) {}
-      };
-
-
-          /** Constructs BSP tree from list of view cells.
-          */ 
-          BspTree(const ViewCellContainer &viewCells);
-          /** Constructs BSP tree from list of objects.
-                  @param object list of intersectables
-                  @param maxPolys maximal allowed number of polygons
-                  @param maxDepth maximal allowed BSP tree depth
-          */
-          BspTree(const ObjectContainer &objects, int maxPolys, int maxDepth);
-  
-          ~BspTree();
-
-  protected:
-          /** Selects a splitting plane from the given polygons. 
-          */
-          Plane3 SelectPlane(PolygonQueue *polyQueue);
-
-          /** Filters next viewcell down the tree and inserts it into the appropriate leaves
-                  (i.e., possibly more than one leaf).
-          */
-          void InsertViewCell(ViewCell *viewCell);
-
-          /** Subdivides tree according to the given list of viewcells.
-          */
-          void Subdivide(const ViewCellContainer &viewCells);
-          /** Subdivides tree according to the given list of objects.
-          */
-          void Subdivide(const ObjectContainer &objects);
-           
-          /** Subdivides leaf.
-                  @param leaf the leaf to be subdivided
-                  @param parent the parent node of this leaf
-                  @param polys the input polygons
-                  @param depth the current tree depth
-                  @param frontPolys the polygons of the front child node as a result from splitting
-                  @param backPolys the polygons of the back child node as a result from splitting
-          */
-          BspNode *SubdivideNode(BspLeaf *leaf, BspInterior *parent, 
-                                                         PolygonQueue *polys, const int depth, 
-                                                         PolygonQueue *frontPolys, PolygonQueue *backPolys);
-
-          /** Extracts the mesh instances of the objects and copies them into the mesh.
-          */
-          static void Copy2PolygonSoup(const ObjectContainer &objects, PolygonQueue &polys);
-
-          static void CopyMesh2Polygon(Mesh *mesh, PolygonQueue &polys);
-
-          /// Pointer to the root of the tree
-          BspNode *mRoot;
-          /// Pointer to the root cell of the viewspace
-          // ViewCell *mRootCell;
-          /// maximal number of polygons allowed in leaf
-          int mMaxPolys;
-          /// maximal depth
-          int mMaxDepth;
-  };
-  
+                BspTraversalData() {}
+                
+                BspTraversalData(BspNode *node, BspInterior *parent, PolygonQueue *polys, const int depth): 
+                mNode(node), mParent(parent), mPolys(polys), mDepth(depth) {}
+    };
+
+        typedef std::stack<BspTraversalData> BspTraversalStack;
+
+        /** Constructs BSP tree from list of view cells.
+        */ 
+        BspTree(const ViewCellContainer &viewCells);
+        /** Constructs BSP tree from list of objects.
+                @param object list of intersectables
+                @param maxPolys maximal allowed number of polygons
+                @param maxDepth maximal allowed BSP tree depth
+        */
+        BspTree(const ObjectContainer &objects, int maxPolys, int maxDepth);
+
+        ~BspTree();
+
+protected:
+        /** Builds a new extension of the tree.
+        */
+        void BuildTree(BspTraversalStack &tStack, BspTraversalData &currentData);
+
+        /** Selects a splitting plane from the given polygons. 
+        */
+        Plane3 SelectPlane(PolygonQueue *polyQueue);
+
+        /** Filters next viewcell down the tree and inserts it into the appropriate leaves
+                (i.e., possibly more than one leaf).
+        */
+        void InsertViewCell(ViewCell *viewCell);
+
+        /** Subdivides tree according to the given list of viewcells.
+        */
+        void Subdivide(const ViewCellContainer &viewCells);
+        /** Subdivides tree according to the given list of objects.
+        */
+        void Subdivide(const ObjectContainer &objects);
+        
+        /** Subdivides leaf.
+                @param leaf the leaf to be subdivided
+                @param parent the parent node of this leaf
+                @param polys the input polygons
+                @param depth the current tree depth
+                @param frontPolys the polygons of the front child node as a result from splitting
+                @param backPolys the polygons of the back child node as a result from splitting
+        */
+        BspNode *SubdivideNode(BspLeaf *leaf, BspInterior *parent, 
+                                                        PolygonQueue *polys, const int depth, 
+                                                        ViewCell *viewCell,
+                                                        PolygonQueue *frontPolys, PolygonQueue *backPolys);
+
+        /** Filters polygons down the tree.
+                @param node the current BSP node
+                @param polys the polygons to be filtered
+                @param frontPolys returns the polygons in front of the split plane
+                @param backPolys returns the polygons in the back of the split plane
+        */
+        void FilterPolygons(BspInterior *node, PolygonQueue *polys, PolygonQueue *frontPolys, PolygonQueue *backPolys);
+
+        /** Extracts the mesh instances of the objects and copies them into the mesh.
+        */
+        static void Copy2PolygonSoup(const ObjectContainer &objects, PolygonQueue &polys);
+
+        static void CopyMesh2Polygon(Mesh *mesh, PolygonQueue &polys);
+
+        /// Pointer to the root of the tree
+        BspNode *mRoot;
+        /// Pointer to the root cell of the viewspace
+        // ViewCell *mRootCell;
+        /// maximal number of polygons allowed in leaf
+        int mMaxPolys;
+        /// maximal depth
+        int mMaxDepth;
+};
+
 //}; // GtpVisibilityPreprocessor