source: GTP/trunk/Lib/Vis/OnlineCullingCHC/OGRE/include/ViewCellBspTree.h @ 727

#ifndef _VspBspTree_H__
#define _VspBspTree_H__

#include "Mesh.h"
#include "Containers.h"
#include "Polygon3.h"
#include <stack>
#include "Statistics.h"
#include "VssRay.h"
#include "RayInfo.h"
#include "ViewCellBsp.h"

class ViewCell;
//class BspViewCell;
class Plane3;
class VspBspTree;  
class BspInterior;
class BspNode;
class AxisAlignedBox3;
class Ray;
class ViewCellsStatistics;
class ViewCellsManager;
class MergeCandidate;
class Beam;
class ViewCellsTree;


struct BspRay;


/**
    BspNode abstract class serving for interior and leaf node implementation
*/
class BspNode 
{
        friend class BspTree;

public:
        BspNode();
        virtual ~BspNode(){};
        BspNode(BspInterior *parent);

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

        /** Sets parent node.
        */
        void SetParent(BspInterior *parent);

        /** Returns true if this node is a sibling of node n.
        */
        bool IsSibling(BspNode *n) const;

        /** returns depth of the node.
        */
        int GetDepth() const;

        /** returns true if the whole subtree is valid
        */
        bool TreeValid() const;

        void SetTreeValid(const bool v);

        //-- mailing options

        void Mail() { mMailbox = sMailId; }
        static void NewMail() { ++ sMailId; }
        bool Mailed() const { return mMailbox == sMailId; }

        static int sMailId;
        int mMailbox;

        int mTimeStamp;

protected:

        /// if this sub tree is a completely valid view space region
        bool mTreeValid;
        /// parent of this node
        BspInterior *mParent;
};

/** BSP interior node implementation 
*/
class BspInterior: public BspNode 
{
        friend class BspTree;
public:
        /** Standard contructor taking split plane as argument.
        */
        BspInterior(const Plane3 &plane);
        ~BspInterior();
        /** @return false since it is an interior node 
        */
        bool IsLeaf() const;

        BspNode *GetBack();
        BspNode *GetFront();

        /** Returns split plane.
        */
        Plane3 GetPlane() const;

        /** Replace front or back child with new child.
        */
        void ReplaceChildLink(BspNode *oldChild, BspNode *newChild);
        /** Replace front and back child.
        */
        void SetupChildLinks(BspNode *b, BspNode *f);

        friend ostream &operator<<(ostream &s, const BspInterior &A)
        {
                return s << A.mPlane;
        }

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 
{
        friend class BspTree;

public:
        BspLeaf();
        BspLeaf(ViewCell *viewCell);
        BspLeaf(BspInterior *parent);
        BspLeaf(BspInterior *parent, ViewCell *viewCell);

        ~BspLeaf();

        /** @return true since it is an interior node 
        */
        bool IsLeaf() const;
        
        /** Returns pointer of view cell.
        */
        ViewCell *GetViewCell() const;

        /** Sets pointer to view cell.
        */
        void SetViewCell(ViewCell *viewCell);

        /// Rays piercing this leaf.
        VssRayContainer mVssRays;
        
        /// leaf pvs
        ObjectPvs *mPvs;

        /// Probability that the view point lies in this leaf
        float mProbability;

protected:
        
        /// if NULL this does not correspond to feasible viewcell
        ViewCell *mViewCell;
};

/**
        This bsp tree spatially organizes the view cells.  
*/
class ViewCellBspTree 
{
public:         
        /** Default constructor creating an empty tree.
        */ 
        VspBspTree();

        /** Default destructor.
        */
        ~VspBspTree();

        /** Returns list of BSP leaves with pvs smaller than
                a certain threshold.
                @param onlyUnmailed if only the unmailed leaves should be considered
                @param maxPvs the maximal pvs (-1 means unlimited)
        */
        void CollectLeaves(vector<BspLeaf *> &leaves, 
                                           const bool onlyUnmailed = false,
                                           const int maxPvs = -1) const;

        /** Returns box which bounds the whole tree.
        */
        AxisAlignedBox3 GetBoundingBox() const;

        /** Returns root of BSP tree.
        */
        BspNode *GetRoot() const;

        /** Collects the leaf view cells of the tree
                @param viewCells returns the view cells 
        */
        void CollectViewCells(ViewCellContainer &viewCells, bool onlyValid) const;

        /** A ray is cast possible intersecting the tree.
                @param the ray that is cast.
                @returns the number of intersections with objects stored in the tree.
        */
        int CastRay(Ray &ray);

        /** finds neighbouring leaves of this tree node.
        */
        int FindNeighbors(BspNode *n, 
                                          vector<BspLeaf *> &neighbors, 
                                          const bool onlyUnmailed) const;

        /** Constructs geometry associated with the half space intersections 
                leading to this node.
        */
        void ConstructGeometry(BspNode *n, BspNodeGeometry &geom) const;
        
        /** Construct geometry of view cell.
        */
        void ConstructGeometry(ViewCell *vc, BspNodeGeometry &geom) const;

        /** Returns random leaf of BSP tree.
                @param halfspace defines the halfspace from which the leaf is taken.
        */
        BspLeaf *GetRandomLeaf(const Plane3 &halfspace);

        /** Returns random leaf of BSP tree.
                @param onlyUnmailed if only unmailed leaves should be returned.
        */
        BspLeaf *GetRandomLeaf(const bool onlyUnmailed = false);

        /** Casts line segment into the tree.
                @param origin the origin of the line segment
                @param termination the end point of the line segment
                @returns view cells intersecting the line segment.
        */
    int CastLineSegment(const Vector3 &origin,
                                                const Vector3 &termination,
                                                ViewCellContainer &viewcells);

        /** Returns view cell the current point is located in.
        */
        ViewCell *GetViewCell(const Vector3 &point);


        /** Returns true if this view point is in a valid view space,
                false otherwise.
        */
        bool ViewPointValid(const Vector3 &viewPoint) const;

        /** Returns view cell corresponding to 
                the invalid view space.
        */
        BspViewCell *GetOutOfBoundsCell();



protected:

        
        
        /// Pointer to the root of the tree
        BspNode *mRoot;
                
};




#endif