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

#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 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));

        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());

                Polygon *front_piece = NULL;
                Polygon *back_piece = NULL;

                switch (result)
                {
                        case Polygon::COINCIDENT:
                        case Polygon::FRONT_SIDE:
                                frontPolys->push(poly);
                                break;
                        case Polygon::BACK_SIDE:
                                backPolys->push(poly);
                                break;
                        case Polygon::SPLIT:
                                front_piece = new Polygon();
                                back_piece = new Polygon();

                                //-- split polygon
                poly->Split(node->GetPlane(), front_piece, back_piece);


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

                                // don't need polygon anymore
                                DEL_PTR(poly);
                                break;
                        default:
                                frontPolys->push(poly);
                                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);

        DEL_PTR(leaf);

        return node;
}

//} // GtpVisibilityPreprocessor