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

#include "Plane3.h"
#include "ViewCellBsp.h"
#include "Mesh.h"

#include "ViewCell.h"
#include <stack>

#define DEL_PTR(ptr) while (0) {if (ptr) {delete (ptr); (ptr) = NULL;}}

//namespace GtpVisibilityPreprocessor {
/****************************************************************/
/*                  class BspNode implementation                */
/****************************************************************/
bool BspNode::IsRoot() const 
{
        return mParent == NULL;
}

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


BspInterior::BspInterior(Plane3 plane): mPlane(plane) 
{}

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;
}

/****************************************************************/
/*                  class BspLeaf implementation                */
/****************************************************************/

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

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

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

/****************************************************************/
/*                  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());
                }

                delete node;
                node = NULL;
        }
}


void BspTree::InsertViewCell(ViewCell *viewCell)
{
        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::Copy2PolygonSoup(const ObjectContainer &objects, Mesh &mesh)
{
        ObjectContainer::const_iterator it, it_end = objects.end();

        for (it = objects.begin(); it != it_end; ++ it)
        {
                FaceContainer::const_iterator fi;
                Intersectable *object = *it;

                // extract the mesh instances
                if (object->Type() == Intersectable::MESH_INSTANCE)
                {
                        MeshInstance *inst = dynamic_cast<MeshInstance *>(object);

                        Mesh *polys = inst->GetMesh();

                        // copy the face data
                        for (fi = polys->mFaces.begin(); fi != polys->mFaces.end(); ++ fi)
                        {
                                Face *face = new Face((*fi)->mVertexIndices);
                                mesh.AddFace(face);
                        }
                }
        }
}

void BspTree::Subdivide(const ObjectContainer &objects)
{
        std::stack<BspTraversalData> tStack;
        Mesh 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();
    
                Mesh backPolys;
                Mesh frontPolys;

                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(Mesh *polys) 
{
        // TODO: more sophisticated criteria
        return polys->GetFacePlane(0);
}

BspNode *BspTree::SubdivideNode(BspLeaf *leaf, BspInterior *parent, 
                                                                Mesh *polys, const int depth, 
                                                                Mesh &frontPolys, Mesh &backPolys)
{
        // terminate traversal if no more faces in mesh
        if ((polys->mFaces.size() <= mMaxPolys) || (depth >= mMaxDepth))
        {
                // don't need to store polygon information
                polys->mFaces->clear(); // HACK: faces were deleted before
                DEL_PTR(polys); // we can savely delete mesh

                return leaf;
        }

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

        FaceContainer::const_iterator fi;

        for (fi = polys->mFaces.begin(); fi != polys->mFaces.end(); ++ fi)
        {
                Face *face = (*fi);

                int  result = 0;// = node->GetPlane()->Side(node->GetPlane());

                Face *front_piece, *back_piece;

                switch (result)
                {
                        case 1:
                                frontPolys.AddFace(face);
                                break;
                        case -1:
                                backPolys.AddFace(face);
                                break;
                        case 0:
                                //Split_Polygon (face, tree->partition, front_piece, back_piece);
                                backPolys.AddFace(back_piece);
                                frontPolys.AddFace(front_piece);

                                // face not needed anymore
                                DEL_PTR(face);

                                break;
                        default:
                                break;
                }
        }

        // backside of convex view cell polygon => outside
        BspLeaf *back = new BspLeaf();
        BspLeaf *front = new BspLeaf();

        // replace a link from node's parent
        if (parent)
        {
                parent->ReplaceChildLink(leaf, node);
        }

        // and setup child links
        node->SetupChildLinks(back, front);

        // don't need to store polygon information
        polys->mFaces->clear(); // HACK: faces were deleted before
        DEL_PTR(polys); // we can savely delete mesh

        DEL_PTR(leaf);

        return node;
}

//} // GtpVisibilityPreprocessor