source: trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.cpp @ 263

#include "Plane3.h"
#include "ViewCellBsp.h"
#include "Mesh.h"
#include "common.h"
#include "ViewCell.h"
#include "Environment.h"
#include "Polygon3.h"
#include "Ray.h"
#include "AxisAlignedBox3.h"
#include <stack>
#include <time.h>
#include <iomanip>
#include "Exporter.h"

#define INITIAL_COST 999999// unreachable high initial cost for heuristic evaluation

int BspTree::sTermMaxPolygons = 10;
int BspTree::sTermMaxDepth = 20;
int BspTree::sSplitPlaneStrategy = NEXT_POLYGON; 
int BspTree::sMaxCandidates = 10;
int BspTree::sConstructionMethod = VIEW_CELLS;

/** Evaluates split plane classification with respect to the plane's 
        contribution for a balanced tree.
*/
int BspTree::sLeastSplitsTable[4] = {0, 0, 1, 0};
/** Evaluates split plane classification with respect to the plane's 
        contribution for a minimum number splits in the tree.
*/
int BspTree::sBalancedTreeTable[4] = {-1, 1, 0, 0};

/****************************************************************/
/*                  class BspNode implementation                */
/****************************************************************/

BspNode::BspNode(): mParent(NULL)
{}

BspNode::BspNode(BspInterior *parent): mParent(parent)
{}


bool BspNode::IsRoot() const 
{
        return mParent == NULL;
}

BspInterior *BspNode::GetParent() 
{ 
        return mParent; 
}

void BspNode::SetParent(BspInterior *parent)
{
        mParent = parent;
}

PolygonContainer *BspNode::GetPolygons()
{
        return &mPolygons;
}

void BspNode::AddPolygons(PolygonContainer *polys)
{
        while (!polys->empty())
        {
                mPolygons.push_back(polys->back());
                polys->pop_back();
        }
}


/****************************************************************/
/*              class BspInterior implementation                */
/****************************************************************/


BspInterior::BspInterior(const Plane3 &plane): 
mPlane(plane), mFront(NULL), mBack(NULL)
{}

bool BspInterior::IsLeaf() const
{ 
        return false; 
}

BspNode *BspInterior::GetBack() 
{
        return mBack;
}

BspNode *BspInterior::GetFront() 
{
        return mFront;
}

Plane3 *BspInterior::GetPlane()
{
        return &mPlane;
}

void BspInterior::ReplaceChildLink(BspNode *oldChild, BspNode *newChild) 
{
        if (mBack == oldChild)
        {
                mBack = newChild;
        }
    else
        {
                mFront = newChild;
        }
}

void BspInterior::SetupChildLinks(BspNode *b, BspNode *f) 
{
    mBack = b;
    mFront = f;
}

void BspInterior::ProcessPolygon(Polygon3 *poly, bool storePolys)
{
        if (storePolys) 
                mPolygons.push_back(poly);
        else
                delete poly;
}

void BspInterior::SplitPolygons(PolygonContainer *polys, 
                                                                PolygonContainer *frontPolys, 
                                                                PolygonContainer *backPolys, 
                                                                int &splits, bool storePolys)
{
        while (!polys->empty())
        {
                Polygon3 *poly = polys->back();
                polys->pop_back();

                // test if split is neccessary
                int result = poly->ClassifyPlane(mPlane);

                Polygon3 *front_piece = NULL;
                Polygon3 *back_piece = NULL;

                switch (result)
                {
                        case Polygon3::COINCIDENT:
                                // discard polygons or saves them in node
                                ProcessPolygon(poly, storePolys);
                                break;
                        case Polygon3::FRONT_SIDE:
                                frontPolys->push_back(poly);
                                break;
                        case Polygon3::BACK_SIDE:
                                backPolys->push_back(poly);
                                break;
                        case Polygon3::SPLIT:
                                front_piece = new Polygon3();
                                back_piece = new Polygon3();

                                //-- split polygon
                                poly->Split(&mPlane, front_piece, back_piece, splits);

                                frontPolys->push_back(front_piece);
                                backPolys->push_back(back_piece);

#ifdef _DEBUG
                                Debug << "split " << *poly << endl << *front_piece << endl << *back_piece << endl;
#endif
                                // save or discard polygons
                                ProcessPolygon(poly, storePolys);
                                
                                break;
                        default:
                Debug << "SHOULD NEVER COME HERE\n";
                                break;
                }
        }

        // contains nothing
        delete polys;
}

/****************************************************************/
/*                  class BspLeaf implementation                */
/****************************************************************/
BspLeaf::BspLeaf(): mViewCell(NULL)
{
}

BspLeaf::BspLeaf(ViewCell *viewCell): mViewCell(viewCell) 
{
}

BspLeaf::BspLeaf(BspInterior *parent): BspNode(parent), mViewCell(NULL)
{}

ViewCell *BspLeaf::GetViewCell()
{
        return mViewCell;
}

void BspLeaf::SetViewCell(ViewCell *viewCell)
{
        mViewCell = viewCell;
}

bool BspLeaf::IsLeaf() const 
{ 
        return true; 
}

/****************************************************************/
/*                  class BspTree implementation                */
/****************************************************************/

BspTree::BspTree(): 
mTermMaxPolygons(0), 
mTermMaxDepth(0), 
mRoot(NULL), 
mIsIncremential(false),
mStorePolys(true)
{
        Randomize(); // initialise random generator for heuristics
}
 
const BspTreeStatistics &BspTree::GetStatistics() const 
{
        return mStat;
}

void BspTreeStatistics::Print(ostream &app) const
{
        app << "===== BspTree statistics ===============\n";

        app << setprecision(4);

        app << "#N_RAYS Number of rays )\n"
                << rays << endl;
        app << "#N_DOMAINS  ( Number of query domains )\n"
                << queryDomains <<endl;

        app << "#N_NODES ( Number of nodes )\n" << nodes << "\n";

        app << "#N_LEAVES ( Number of leaves )\n" << Leaves() << "\n";

        app << "#N_SPLITS ( Number of splits)\n" << splits << "\n";

        app << "#N_RAYREFS ( Number of rayRefs )\n" <<
        rayRefs << "\n";

        app << "#N_RAYRAYREFS  ( Number of rayRefs / ray )\n" <<
        rayRefs/(double)rays << "\n";

        app << "#N_LEAFRAYREFS  ( Number of rayRefs / leaf )\n" <<
        rayRefs/(double)Leaves() << "\n";

        app << "#N_MAXOBJECTREFS  ( Max number of rayRefs / leaf )\n" <<
        maxObjectRefs << "\n";

        app << "#N_NONEMPTYRAYREFS  ( Number of rayRefs in nonEmpty leaves / non empty leaf )\n" <<
        rayRefsNonZeroQuery/(double)(Leaves() - zeroQueryNodes) << "\n";

        app << "#N_LEAFDOMAINREFS  ( Number of query domain Refs / leaf )\n" <<
        objectRefs/(double)Leaves() << "\n";

        app << "#N_PEMPTYLEAVES  ( Percentage of leaves with zero query domains )\n"<<
        zeroQueryNodes*100/(double)Leaves() << endl;

        app << "#N_PMAXDEPTHLEAVES ( Percentage of leaves at maxdepth )\n"<<
        maxDepthNodes * 100 / (double)Leaves() << endl;

        app << "#N_PMAXDEPTH ( Maximal reached depth )\n" << maxDepth <<endl;

        app << "#N_ADDED_RAYREFS  (Number of dynamically added ray references )\n"<<
        addedRayRefs<<endl;

        app << "#N_REMOVED_RAYREFS  (Number of dynamically removed ray references )\n"<<
        removedRayRefs<<endl;

        //  app << setprecision(4);

        //  app << "#N_CTIME  ( Construction time [s] )\n"
        //      << Time() << " \n";

        app << "===== END OF BspTree statistics ==========\n";
}

BspTree::~BspTree()
{
        std::stack<BspNode *> tStack;

        tStack.push(mRoot);

        while (!tStack.empty())
        {
                BspNode *node = tStack.top();

            tStack.pop();
        
                /// if we stored the polygons
                CLEAR_CONTAINER(node->mPolygons);

                if (!node->IsLeaf())
                {
                        BspInterior *interior = dynamic_cast<BspInterior *>(node);

                        // push the children on the stack (there are always two children)
                        tStack.push(interior->GetBack());
                        tStack.push(interior->GetFront());
                }

                DEL_PTR(node);
        }
}


void BspTree::InsertViewCell(ViewCell *viewCell)
{       
        std::stack<BspTraversalData> tStack;
                Debug << "getting polygons" << endl; Debug.flush();
        PolygonContainer *polys = new PolygonContainer();

        // extract polygons that guide the split process
        AddMesh2Polygons(viewCell->GetMesh(), *polys);
        mBox.Include(viewCell->GetBox()); // add to BSP aabb

         // traverse tree or create new one
        BspNode *firstNode = mRoot ? mRoot : new BspLeaf();

        tStack.push(BspTraversalData(firstNode, NULL, polys, 0));

        Debug << "starting traversal" << endl; Debug.flush();
        while (!tStack.empty())
        {
                Debug << "new traversal step" << endl; Debug.flush();
                
                // filter polygons donw the tree
                BspTraversalData tData = tStack.top();
            tStack.pop();
                        
                Debug << "popped stack" << endl; Debug.flush();
                if (!tData.mNode)
                        Debug << "ERROR NO NODE\n"; Debug.flush();
                if (!tData.mNode->IsLeaf())
                {
                        Debug << "no leaf" << endl; Debug.flush();
                        BspInterior *interior = dynamic_cast<BspInterior *>(tData.mNode);

                        //-- filter view cell polygons down the tree until a leaf is reached
                        PolygonContainer *frontPolys = new PolygonContainer();
                        PolygonContainer *backPolys = new PolygonContainer();

                        int splits = 0;
                
                        if ((int)tData.mPolygons->size() > 0)
                        {
                                Debug << "traversing down tree" << endl; Debug.flush();
                                // split viecell polygons with respect to split plane
                                interior->SplitPolygons(tData.mPolygons, frontPolys, backPolys, splits, mStorePolys);
                                Debug << "polygon splitted" << endl; Debug.flush();
                                //Debug << "Reached level " << tData.mDepth << " bk: " << backPolys->size() << " frnt: " << frontPolys->size() << endl;
                                mStat.splits += splits;

                                // push the children on the stack
                                tStack.push(BspTraversalData(interior->GetFront(), interior->GetParent(), 
                                                        frontPolys, tData.mDepth + 1));
                        
                                tStack.push(BspTraversalData(interior->GetBack(), interior->GetParent(), 
                                                        backPolys, tData.mDepth + 1));
                        
                        }
                        else
                        {
                                Debug << "deleting data" << endl; Debug.flush();
                                DEL_PTR(tData.mPolygons);
                                Debug << "deleted data" << endl; Debug.flush();
                        }
                }
                else // reached leaf => subdivide current viewcell
                {
                        Debug << "reached leaf" << endl; Debug.flush();
                        BspNode *root = Subdivide(tStack, tData, viewCell);             

            // tree empty => new root
                        if (!mRoot)
                                mRoot = root;           
                        Debug << "subdivision done" << endl; Debug.flush();
                }
                Debug << "ended one traversal step" << endl; Debug.flush();
        }
        Debug << "ended traversal" << endl; Debug.flush();
}

void BspTree::InitTree(int maxPolygons, int maxDepth)
{
        mTermMaxPolygons = maxPolygons;
        mTermMaxDepth = maxDepth;
        mStat.nodes = 1;
        
        mBox.Initialize();      // initialise bsp tree bounding box
}



void BspTree::AddMesh2Polygons(Mesh *mesh, PolygonContainer &polys)
{
        FaceContainer::const_iterator fi;
        
        // copy the face data to polygons
        for (fi = mesh->mFaces.begin(); fi != mesh->mFaces.end(); ++ fi)
        {
                Polygon3 *poly = new Polygon3((*fi), mesh);
                polys.push_back(poly);
        }
}

void BspTree::Copy2PolygonSoup(const ViewCellContainer &viewCells, PolygonContainer &polys, int maxObjects)
{
        int limit = (maxObjects > 0) ? Min((int)viewCells.size(), maxObjects) : (int)viewCells.size();
  
        for (int i = 0; i < limit; ++i)
        {
                if (viewCells[i]->GetMesh()) // copy the mesh data to polygons
                {
                        mBox.Include(viewCells[i]->GetBox()); // add to BSP tree aabb
                        AddMesh2Polygons(viewCells[i]->GetMesh(), polys);
                }
        }
}

void BspTree::Copy2PolygonSoup(const ObjectContainer &objects, PolygonContainer &polys, int maxObjects)
{
        int limit = (maxObjects > 0) ? Min((int)objects.size(), maxObjects) : (int)objects.size();
  
        for (int i = 0; i < limit; ++i)
        {
                Intersectable *object = objects[i];//*it;
                Mesh *mesh = NULL;

                switch (object->Type()) // extract the meshes
                {
                case Intersectable::MESH_INSTANCE:
                        mesh = dynamic_cast<MeshInstance *>(object)->GetMesh();
                        break;
                case Intersectable::VIEWCELL:
                        mesh = dynamic_cast<ViewCell *>(object)->GetMesh();
                        break;
                        // TODO: handle transformed mesh instances
                default:
                        break;
                }
                
        if (mesh) // copy the mesh data to polygons
                {
                        mBox.Include(object->GetBox()); // add to BSP tree aabb
                        AddMesh2Polygons(mesh, polys);
                }
        }

        Debug << "Number of polygons: " << (int)polys.size() << ", BSP root box: " << mBox << endl;
}

void BspTree::Construct(const ViewCellContainer &viewCells)
{
        //-- Construct tree using the given viewcells
        
        /* for this type of construction we filter all viewcells down the 
         * tree. If there is no polygon left, the last split plane
         * decides inside or outside of the viewcell.
    */
        InitTree(sTermMaxPolygons, sTermMaxDepth);

    bool savedStorePolys = mStorePolys;

        // tree is completely constructed once before 
        // view cells are inserted one after another => 
        // global tree optimization possible
        if (!mIsIncremential)
        {
                // copy view cell meshes into one big polygon soup
                PolygonContainer *polys = new PolygonContainer();
                Copy2PolygonSoup(viewCells, *polys, sMaxCandidates);

                // polygons are stored only during view cell insertion
                mStorePolys = false;

                // construct tree from viewcell polygons
                Construct(polys);
                //Export("bsp.x3d");
        }
        
        //-- insert all viewcells
        ViewCellContainer::const_iterator it;

        mStorePolys = savedStorePolys;

        int counter = 0;

        Debug << "\n**** Started view cells insertion ****\n\n";
        for (it = viewCells.begin(); it != viewCells.end(); ++ it)
        {
                Debug << "*** Inserting view cell " << counter << " ***" << endl;
                InsertViewCell(*it);
                Debug << "*** view cell " << ++ counter << " inserted ***" << endl;
        }
        Debug << "**** finished view cells insertion ****" << endl; Debug.flush();
}


void BspTree::Construct(const ObjectContainer &objects, ViewCellContainer *viewCells)
{
        // take termination criteria from globals
        InitTree(sTermMaxPolygons, sTermMaxDepth);
        
        PolygonContainer *polys = new PolygonContainer();
        
        // copy mesh instance polygons into one big polygon soup
        Copy2PolygonSoup(objects, *polys, sMaxCandidates);

        // construct tree from polygon soup
        Construct(polys);

        // TODO: generate view cells
}

void BspTree::Construct(const RayContainer &rays, ViewCellContainer *viewCells)
{
        // TODO
}

void BspTree::Construct(PolygonContainer *polys)
{
        std::stack<BspTraversalData> tStack;
        
        BspTraversalData tData(new BspLeaf(), NULL, polys, 0);

        tStack.push(tData);

        Debug << "**** Contructing tree using objects ****\n";
        while (!tStack.empty()) 
        {
                tData = tStack.top();
            tStack.pop();
        
                // subdivide leaf node
                BspNode *root = Subdivide(tStack, tData);

                // empty tree => new root corresponding to unbounded space
                if (!mRoot) 
                        mRoot = root;
        }

        Debug << "**** tree construction finished ****\n";
}


BspNode * BspTree::Subdivide(BspTraversalStack &tStack, 
                                                         BspTraversalData &tData, 
                                                         ViewCell *viewCell)
{
        Debug << "subdividing" << endl; Debug.flush();
        PolygonContainer *backPolys = new PolygonContainer();
        PolygonContainer *frontPolys = new PolygonContainer();

        BspNode *node = SubdivideNode(dynamic_cast<BspLeaf *>(tData.mNode),
                                                                  tData.mParent,
                                                                  tData.mPolygons,
                                                                  tData.mDepth,
                                                                  frontPolys,
                                                                  backPolys);

        if (!node->IsLeaf()) // node was subdivided
        {
                Debug << "node was subdivided" << endl; Debug.flush();
                BspInterior *interior = dynamic_cast<BspInterior *>(node);

                // push the children on the stack (there are always two children)
                tStack.push(BspTraversalData(interior->GetBack(), interior, backPolys, tData.mDepth + 1));
                tStack.push(BspTraversalData(interior->GetFront(), interior, frontPolys, tData.mDepth + 1));
        }
        else // traversal terminates
        {
                Debug << "eval stats" << endl; Debug.flush();
                EvaluateLeafStats(tData);

        BspLeaf *leaf = dynamic_cast<BspLeaf *>(node);

                // add view cell if in negative halfspace (== inside object) 
                // or if there is still geometry left
                if (viewCell && 
                        (!node->GetParent() || (node == node->GetParent()->GetBack()) || 
                         (tData.mPolygons->size() > 0)))
                {
                        Debug << "** view cell inserted **\n";
                        leaf->SetViewCell(viewCell);
                }

                Debug << "storing or deleting polygons: " << mStorePolys << endl; Debug.flush();
                // add or delete remaining polygons
                if (mStorePolys)
                        leaf->AddPolygons(tData.mPolygons);
                else
                        CLEAR_CONTAINER(*tData.mPolygons);

                DEL_PTR(tData.mPolygons);
                Debug << "deleted polygon container" << endl; Debug.flush();
        }

        return node;
}


BspNode *BspTree::SubdivideNode(BspLeaf *leaf, 
                                                                BspInterior *parent, 
                                                                PolygonContainer *polys, 
                                                                const int depth, 
                                                                PolygonContainer *frontPolys, 
                                                                PolygonContainer *backPolys)
{
        if (leaf->GetViewCell() && (polys->size() == 0))
                Debug << "error: no distinct view cells!!!!!!!!!!!\n";
        
        // terminate traversal  
        if (//!leaf->GetViewCell() && 
                ((polys->size() <= mTermMaxPolygons) || (depth >= mTermMaxDepth)))
        {Debug << "subdividing node termination" << endl; Debug.flush();
                return leaf;
        }

         mStat.nodes += 2;

        // add the new nodes to the tree + select subdivision plane
        BspInterior *node = new BspInterior(SelectPlane(polys)); 

#ifdef _DEBUG
        Debug << node << endl;
#endif

        // split polygon according to current plane
        int splits = 0;
                
        Debug << "splipoly" << endl; Debug.flush();
        node->SplitPolygons(polys, frontPolys, backPolys, splits, mStorePolys);
        
        mStat.splits += splits;

        // two new leaves
        BspLeaf *back = new BspLeaf(node);
        BspLeaf *front = new BspLeaf(node);

        // replace a link from node's parent
        if (parent)
                parent->ReplaceChildLink(leaf, node);
        
        // and setup child links
        node->SetupChildLinks(back, front);
        
        DEL_PTR(leaf); // leaf not member of tree anymore
        
        return node;
}

Plane3 BspTree::SelectPlane(PolygonContainer *polys)  const
{
        if (polys->size() == 0)
        {
                Debug << "Warning: No split candidate available\n";
                return Plane3();
        }

        // simple strategy: just take next polygon
        if (sSplitPlaneStrategy == NEXT_POLYGON)
        {
                return polys->front()->GetSupportingPlane();
        }
        
        // use heuristics to find appropriate plane
        return SelectPlaneHeuristics(polys, sMaxCandidates);
}

Plane3 BspTree::SelectPlaneHeuristics(PolygonContainer *polygons, int maxTests) const
{
        int lowestCost = INITIAL_COST;
        Plane3 *bestPlane = NULL;
        
        int limit = Min((int)polygons->size(), maxTests);

        for (int i = 0; i < limit; ++i)
        {
                int candidateIdx = Random((int)polygons->size());
                Plane3 candidatePlane = (*polygons)[candidateIdx]->GetSupportingPlane();
                
                // evaluate current candidate
                int candidateCost = EvalSplitPlane(polygons, candidatePlane);
                        
                if (candidateCost < lowestCost)
                {
                        bestPlane = &candidatePlane;
                        lowestCost = candidateCost;
                        //Debug << "new plane cost " << lowestCost << endl;
                }
        }
                
        return *bestPlane;
}

int BspTree::EvalSplitPlane(PolygonContainer *polygons, const Plane3 &candidatePlane) const
{
        PolygonContainer::const_iterator it;

        int sum = 0, sum2 = 0;

        for (it = polygons->begin(); it < polygons->end(); ++ it)
        {
                int classification = (*it)->ClassifyPlane(candidatePlane);
                
                if ((sSplitPlaneStrategy == BALANCED_TREE) || (sSplitPlaneStrategy == COMBINED))
                {
                        sum += sBalancedTreeTable[classification];
                }
                
                if ((sSplitPlaneStrategy == LEAST_SPLITS) || (sSplitPlaneStrategy == COMBINED))
                {
                        sum2 += sLeastSplitsTable[classification];
                }
        }

        // return linear combination of both sums
        return abs(sum) + abs(sum2);
}

void BspTree::ParseEnvironment()
{
        environment->GetIntValue("BspTree.Termination.maxDepth", sTermMaxDepth);
        environment->GetIntValue("BspTree.Termination.maxPolygons", sTermMaxPolygons);
        environment->GetIntValue("BspTree.maxCandidates", sMaxCandidates);

        //-- extract strategy to choose the next split plane
        char splitPlaneStrategyStr[60];

        environment->GetStringValue("BspTree.splitPlaneStrategy", splitPlaneStrategyStr);
        
        sSplitPlaneStrategy = BspTree::NEXT_POLYGON;
        
        if (strcmp(splitPlaneStrategyStr, "nextPolygon") == 0)
                sSplitPlaneStrategy = BspTree::NEXT_POLYGON;
        else if (strcmp(splitPlaneStrategyStr, "leastSplits") == 0)
                sSplitPlaneStrategy = BspTree::LEAST_SPLITS;
        else if (strcmp(splitPlaneStrategyStr, "balancedTree") == 0)
                sSplitPlaneStrategy = BspTree::BALANCED_TREE;
        else 
        {
                cerr << "Wrong BSP split plane strategy " << splitPlaneStrategyStr << endl;
                exit(1);
    }

        //-- parse BSP tree construction method
        char constructionMethodStr[64];
        
        environment->GetStringValue("BspTree.constructionMethod", constructionMethodStr);

        sConstructionMethod = BspTree::VIEW_CELLS;
        
        if (strcmp(constructionMethodStr, "viewCells") == 0)
                sConstructionMethod = BspTree::VIEW_CELLS;
        else if (strcmp(constructionMethodStr, "sceneGeometry") == 0)
                sConstructionMethod = BspTree::SCENE_GEOMETRY;
        else if (strcmp(constructionMethodStr, "rays") == 0)
                sConstructionMethod = BspTree::RAYS;
        else 
        {
                cerr << "Wrong bsp construction method " << constructionMethodStr << endl;
                exit(1);
    }

}

void BspTree::CollectLeaves(vector<BspLeaf *> &leaves)
{
        stack<BspNode *> nodeStack;
        nodeStack.push(mRoot);
 
        while (!nodeStack.empty()) 
        {
                BspNode *node = nodeStack.top();
    
                nodeStack.pop();
    
                if (node->IsLeaf()) 
                {
                        BspLeaf *leaf = (BspLeaf *)node;
                        
                        leaves.push_back(leaf);
                } else 
                {
                        BspInterior *interior = dynamic_cast<BspInterior *>(node);
                        nodeStack.push(interior->GetBack());
                        nodeStack.push(interior->GetFront());
                }
        }
}

int BspTree::CollectLeafPvs()
{
        int totalPvsSize = 0;
  
        stack<BspNode *> nodeStack;
  
        nodeStack.push(mRoot);
  
        while (!nodeStack.empty()) 
        {
                BspNode *node = nodeStack.top();
                
                nodeStack.pop();
                
                if (node->IsLeaf()) 
                {
                        BspLeaf *leaf = dynamic_cast<BspLeaf *>(node);

                        ViewCell *viewcell = leaf->GetViewCell();
                        
                        if (!viewcell->Mailed()) 
                        {
                                viewcell->Mail(); // what does mail mean?
                                        
                                // add this node to pvs of all nodes it can see
                                BspPvsMap::iterator ni; 
          
        /*                      for (ni = object->mBspPvs.mEntries.begin(); ni != object->mKdPvs.mEntries.end(); ni++) 
                                {
                                        BspNode *node = (*ni).first;
            
                                        // $$ JB TEMPORARY solution -> should add object PVS or explictly computed
                                        // BSP tree PVS
                                if (leaf->mBspPvs.AddNodeSample(node))
                                                totalPvsSize++;
                                }*/
                        }
                } else 
                {
                        // traverse tree
                        BspInterior *interior = (BspInterior *)node;
      
                        nodeStack.push(interior->GetFront());
                        nodeStack.push(interior->GetBack());
                }
        }

        return totalPvsSize;
}

AxisAlignedBox3 BspTree::GetBoundingBox() const
{
        return mBox;
}

BspNode *BspTree::GetRoot() const
{
        return mRoot;
}

bool BspTree::StorePolys() const
{
        return mStorePolys;
}

void BspTree::EvaluateLeafStats(const BspTraversalData &data)
{
        // the node became a leaf -> evaluate stats for leafs
        BspLeaf *leaf = dynamic_cast<BspLeaf *>(data.mNode);

        if (data.mDepth >= mTermMaxDepth)
        {
                ++ mStat.maxDepthNodes;
        }

        // store maximal depth
        if (data.mDepth > mStat.maxDepth)
                mStat.maxDepth = data.mDepth;

#ifdef _DEBUG
        Debug << "BSP Traversal data. Depth: " << data.mDepth << " (max: " << mTermMaxDepth<< "), #polygons: " << 
          data.mPolygons->size() << " (max: " << mTermMaxPolygons << ")" << endl;
#endif
}

int BspTree::CastRay(Ray &ray)
{
        int hits = 0;
  
        stack<BspRayTraversalData> tStack;
  
        float maxt = 1e6;
        float mint = 0;

        Intersectable::NewMail();

        // test with tree bounding box
        if (!mBox.GetMinMaxT(ray, &mint, &maxt))
                return 0;

        if (mint < 0)
                mint = 0;
  
        maxt += Limits::Threshold;
  
        Vector3 entp = ray.Extrap(mint);
        Vector3 extp = ray.Extrap(maxt);
  
        BspNode *node = mRoot;
        BspNode *farChild;
        
        while (1)
        {
                if (!node->IsLeaf()) 
                {
                        BspInterior *in = (BspInterior *) node;
                        
                        Plane3 *splitPlane = in->GetPlane();

                        float t = 0;
                        bool coplanar = false;
                
                        int entSide = splitPlane->Side(entp);
                        int extSide = splitPlane->Side(extp);

                        Vector3 intersection;

                        if (entSide < 0)
                        {
                                node = in->GetBack();

                                if(extSide <= 0) 
                                        continue;
                                        
                                farChild = in->GetFront(); // plane splits ray

                        } else if (entSide > 0)
                        {
                                node = in->GetFront();

                                if (extSide >= 0)
                                        continue;

                                farChild = in->GetBack();        // plane splits ray                    
                        }
                        else // ray and plane are coincident // WHAT TO DO IN THIS CASE ?
                        {
                                node = in->GetFront();
                                continue;
                        }

                        //-- split

                        // push data for far child
                        tStack.push(BspRayTraversalData(farChild, extp, maxt));

                        // find intersection with plane between ray origin and exit point
                        extp = splitPlane->FindIntersection(ray.GetLoc(), extp, &maxt);

                } else // compute intersections with objects in leaf
                {
                        BspLeaf *leaf = dynamic_cast<BspLeaf *>(node);
                        //ray.leaves.push_back(leaf);
      // TODO
                        /*ObjectContainer::const_iterator mi;
                        for (mi = leaf->mObjects.begin(); mi != leaf->mObjects.end(); ++mi) 
                        {
                                Intersectable *object = *mi;
                                if (!object->Mailed()) 
                                {
                                        object->Mail();
                                        //ray.meshes.push_back(mesh);
                                        hits += object->CastRay(ray);
                                }
                        }*/

                        if (hits && ray.GetType() == Ray::LOCAL_RAY)
                                if (ray.intersections[0].mT <= maxt)
                                        break;
      
                        // get the next node from the stack
                        if (tStack.empty())
                                break;
      
                        entp = extp;
                        mint = maxt;
                        BspRayTraversalData &s  = tStack.top();

                        node = s.mNode;
                        extp = s.mExitPoint;
                        maxt = s.mMaxT;

                        tStack.pop();
                }
        }

        return hits;
}

bool BspTree::Export(const string filename)
{
        Exporter *exporter = Exporter::GetExporter(filename);

        if (exporter) 
        {
                exporter->ExportBspTree(*this);
                delete exporter;

                return true;
        }       

        return false;
}
//} // GtpVisibilityPreprocessor