source: GTP/trunk/Lib/Vis/Preprocessing/src/VspOspTree.h @ 1010

#ifndef _VspOspTree_H__
#define _VspOspTree_H__

#include <stack>

#include "Mesh.h"
#include "Containers.h"
#include "Statistics.h"
#include "VssRay.h"
#include "RayInfo.h"
#include "gzstream.h"


namespace GtpVisibilityPreprocessor {

class ViewCellLeaf;
//class VspViewCell;
class Plane3;
class AxisAlignedBox3;
class Ray;
class ViewCellsStatistics;
class ViewCellsManager;
class MergeCandidate;
class Beam;
class ViewCellsTree;
class Environment;
class VspInterior;
class VspLeaf;
class VspNode;


/** A definition for an axis aligned plane.
*/
struct AxisAlignedPlane
{
public:
        int mAxis;
        float mPosition;
};


class VspTreeStatistics: public StatisticsBase
{
public:
        // total number of nodes
        int nodes;
        // number of splits
        int splits[3];
        
        // totals number of rays
        int rays;
        // maximal reached depth
        int maxDepth;
        // minimal depth
        int minDepth;
        
        // max depth nodes
        int maxDepthNodes;
        // minimum depth nodes
        int minDepthNodes;
        // max depth nodes
        int minPvsNodes;
        // nodes with minimum PVS
        int minRaysNodes;
        // max ray contribution nodes
        int maxRayContribNodes;
        // minimum area nodes
        int minProbabilityNodes;
        /// nodes termination because of max cost ratio;
        int maxCostNodes;
        // max number of rays per node
        int maxObjectRefs;
        /// samples contributing to pvs
        int contributingSamples;
        /// sample contributions to pvs
        int sampleContributions;
        /// largest pvs
        int maxPvs;
        /// number of invalid leaves
        int invalidLeaves;
        /// accumulated number of rays refs
        int accumRays;
        int pvs;
        // accumulated depth (used to compute average)
        int accumDepth;

        // Constructor
        VspTreeStatistics() 
        {
                Reset();
        }

        int Nodes() const {return nodes;}
        int Interior() const { return nodes / 2; }
        int Leaves() const { return (nodes / 2) + 1; }
        
        // TODO: computation wrong
        double AvgDepth() const { return accumDepth / (double)Leaves();}; 
        double AvgRays() const { return accumRays / (double)Leaves();}; 

        void Reset() 
        {
                nodes = 0;
                for (int i = 0; i < 3; ++ i)
                        splits[i] = 0;
                
                maxDepth = 0;
                minDepth = 99999;
                accumDepth = 0;
        pvs = 0;
                maxDepthNodes = 0;
                minPvsNodes = 0;
                minRaysNodes = 0;
                maxRayContribNodes = 0;
                minProbabilityNodes = 0;
                maxCostNodes = 0;

                contributingSamples = 0;
                sampleContributions = 0;

                maxPvs = 0;
                invalidLeaves = 0;
                accumRays = 0;
        }

        void Print(ostream &app) const;

        friend ostream &operator<<(ostream &s, const VspTreeStatistics &stat) 
        {
                stat.Print(s);
                return s;
        } 
};

/**
    VspNode abstract class serving for interior and leaf node implementation
*/
class VspNode 
{

public:
        VspNode();
        virtual ~VspNode(){};
        VspNode(VspInterior *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.
        */
        VspInterior *GetParent();

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

        /** Returns true if this node is a sibling of node n.
        */
        bool IsSibling(VspNode *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
        VspInterior *mParent;
};


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

        VspNode *GetBack();
        VspNode *GetFront();

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

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

        friend ostream &operator<<(ostream &s, const VspInterior &A)
        {
                return s << A.mPlane.mAxis << " " << A.mPlane.mPosition;
        }

protected:

        /// Splitting plane corresponding to this node
        AxisAlignedPlane mPlane;

        /// back node
        VspNode *mBack;
        /// front node
        VspNode *mFront;
};


/** BSP leaf node implementation.
*/
class VspLeaf: public VspNode 
{

public:
        VspLeaf();
        VspLeaf(ViewCellLeaf *viewCell);
        VspLeaf(VspInterior *parent);
        VspLeaf(VspInterior *parent, ViewCellLeaf *viewCell);

        ~VspLeaf();

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

        /** Sets pointer to view cell.
        */
        void SetViewCell(ViewCellLeaf *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
        ViewCellLeaf *mViewCell;
};


/**
        This class implements a structure holding two different hierarchies,
        one for object space partitioning and one for view space partitioning.

        The object space and the view space are subdivided using a cost heuristics.
        If an object space split or a view space split is chosen is also evaluated
        based on the heuristics. 
        
        The view space heuristics is evaluated by weighting and adding the pvss of the back and
        front node of each specific split. unlike for the standalone method vspbsp tree,
        the pvs of an object would not be the pvs of single object but that of all objects
        which are contained in the same leaf of the object subdivision. This could be done
        by storing the pointer to the object space partition parent, which would allow access to all children.
        Another possibility is to include traced kd-cells in the ray casing process.

        Accordingly, the object space heuristics is evaluated by storing a pvs of view cells with each object.
        the contribution to an object to the pvs is the number of view cells it can be seen from.


        There is a potential efficiency problem involved in a sense that once a certain type
        of split is chosen for view space / object space, the candidates for the next split of 
        object space / view space must be reevaluated.
        
*/
class VspOspTree 
{
        friend class ViewCellsParseHandlers;
        friend class VspVspViewCellsManager;

public:
        
        /** Additional data which is passed down the BSP tree during traversal.
        */
        class VspOspTraversalData
        {  
        public:
                /// the current node
                VspNode *mNode;
                /// current depth
                int mDepth;
                /// rays piercing this node
                RayInfoContainer *mRays;
                /// the probability that this node contains view point
                float mProbability;
                /// the bounding box of the node
                AxisAlignedBox3 mBoundingBox;
                /// pvs size
                int mPvs;
                /// how often this branch has missed the max-cost ratio
                int mMaxCostMisses;
                // current axis
                int mAxis;
                // current priority
                float mPriority;

                
                /** Returns average ray contribution.
                */
                float GetAvgRayContribution() const
                {
                        return (float)mPvs / ((float)mRays->size() + Limits::Small);
                }


                VspOspTraversalData():
                mNode(NULL),
                mDepth(0),
                mRays(NULL),
                mPvs(0),
                mProbability(0.0),
                mMaxCostMisses(0), 
                mPriority(0),
                mAxis(0)
                {}
                
                VspOspTraversalData(VspNode *node, 
                                                        const int depth, 
                                                        RayInfoContainer *rays,
                                                        const int pvs,
                                                        const float p,
                                                        const AxisAlignedBox3 &box): 
                mNode(node), 
                mDepth(depth), 
                mRays(rays),
                mPvs(pvs),
                mProbability(p),
                mBoundingBox(box),
                mMaxCostMisses(0),
                mPriority(0),
                mAxis(0)
                {}

                VspOspTraversalData(PolygonContainer *polys, 
                                                        const int depth, 
                                                        RayInfoContainer *rays,
                                                        const AxisAlignedBox3 &box): 
                mNode(NULL), 
                mDepth(depth), 
                mRays(rays),
                mPvs(0),
                mProbability(0),
                mMaxCostMisses(0),
                mAxis(0),
                mBoundingBox(box)
                {}

                /** Returns cost of the traversal data.
                */
                float GetCost() const
                {
                        //cout << mPriority << endl;
                        return mPriority;
                }

                // deletes contents and sets them to NULL
                void Clear()
                {
                        DEL_PTR(mRays);
                }

                friend bool operator<(const VspOspTraversalData &a, const VspOspTraversalData &b)
                {
                        return a.GetCost() < b.GetCost();
                }
    };
        

        typedef std::priority_queue<VspOspTraversalData> VspOspTraversalQueue;
        
        
        struct VspOspSplitCandidate
        {  
                /// the current plane
                AxisAlignedPlane mSplitPlane;
                /// the number of misses of max cost ratio until this split
                int mMaxCostMisses;
                /// parent data
                VspOspTraversalData mParentData;
                /// cost of applying this split
                float mRenderCost;

                VspOspSplitCandidate(): mRenderCost(0) 
                {};

                VspOspSplitCandidate(const AxisAlignedPlane &plane, const VspOspTraversalData &tData): 
                mSplitPlane(plane), mParentData(tData), mRenderCost(0)
                {}

                /** Returns cost of the traversal data.
                */
                float GetCost() const
                {
#if 1
                        return mRenderCost;
#else
                        return (float) (-mDepth); // for kd tree
#endif
                }

                friend bool operator<(const VspOspSplitCandidate &a, const VspOspSplitCandidate &b)
                {
                        return a.GetCost() < b.GetCost();
                }
    };

        typedef std::priority_queue<VspOspSplitCandidate> VspOspSplitQueue;

        /** Default constructor creating an empty tree.
        */ 
        VspOspTree();

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

        /** Returns BSP Tree statistics.
        */
        const VspTreeStatistics &GetStatistics() const; 
  

        /** Constructs the tree from a given set of rays.
                @param sampleRays the set of sample rays the construction is based on
                @param viewCells if not NULL, new view cells are 
                created in the leafs and stored in the container
        */
        void Construct(const VssRayContainer &sampleRays,
                                   AxisAlignedBox3 *forcedBoundingBox);

        /** 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<VspLeaf *> &leaves, 
                                           const bool onlyUnmailed = false,
                                           const int maxPvs = -1) const;

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

        /** Returns root of the view space partitioning tree.
        */
        VspNode *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(VspNode *n, 
                                          vector<VspLeaf *> &neighbors, 
                                          const bool onlyUnmailed) const;

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

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

        /** Returns epsilon of this tree.
        */
        float GetEpsilon() const;

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

                
        /** Sets pointer to view cells manager.
        */
        void SetViewCellsManager(ViewCellsManager *vcm);


        /** Collapses the tree with respect to the view cell partition.
                @returns number of collapsed nodes
        */
        int CollapseTree();

        /** Returns view cell the current point is located in.
                @param point the current view point
                @param active if currently active view cells should be returned or
                elementary view cell
        */
        ViewCell *GetViewCell(const Vector3 &point, const bool active = false);


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

        /** Writes tree to output stream
        */
#if ZIPPED_VIEWCELLS
        bool Export(ogzstream &stream);
#else
        bool Export(ofstream &stream);
#endif

        /** Casts beam, i.e. a 5D frustum of rays, into tree.
                Tests conservative using the bounding box of the nodes.
                @returns number of view cells it intersected
        */
        int CastBeam(Beam &beam);


        /** Checks if tree validity-flags are right 
                with respect to view cell valitiy.
                If not, marks subtree as invalid.
        */
        void ValidateTree();

        /** Invalid view cells are added to the unbounded space
        */
        void CollapseViewCells();

        /** Collects rays stored in the leaves.
        */
        void CollectRays(VssRayContainer &rays);

        /** Intersects box with the tree and returns the number of intersected boxes.
                @returns number of view cells found
        */
        int ComputeBoxIntersections(const AxisAlignedBox3 &box, ViewCellContainer &viewCells) const;

        // pointer to the hierarchy of view cells
        ViewCellsTree *mViewCellsTree;


protected:

        // --------------------------------------------------------------
        // For sorting objects
        // --------------------------------------------------------------
        struct SortableEntry
        {
                enum EType 
                {
                        ERayMin,
                        ERayMax
                };

                int type;
                float value;
                VssRay *ray;
  
                SortableEntry() {}
                SortableEntry(const int t, const float v, VssRay *r):type(t),
                                          value(v), ray(r) 
                {
                }
                
                friend bool operator<(const SortableEntry &a, const SortableEntry &b) 
                {
                        return a.value < b.value;
                }
        };

        /** faster evaluation of split plane cost for kd axis aligned cells.
        */
        float EvalSplitCost(const VspOspTraversalData &data,
                                                const AxisAlignedBox3 &box,
                                                const int axis,
                                                const float &position,
                                                float &pFront,
                                                float &pBack) const;

        /** Evaluates candidate for splitting.
        */
        void EvalSplitCandidate(VspOspTraversalData &tData, VspOspSplitCandidate &splitData);

        /** Computes priority of the traversal data and stores it in tData.
        */
        void EvalPriority(VspOspTraversalData &tData) const;

        /** Evaluates render cost decrease of next split.
        */
        float EvalRenderCostDecrease(const AxisAlignedPlane &candidatePlane,
                                                                 const VspOspTraversalData &data) const;

        /** Constructs tree using the split priority queue.
        */
        void Construct(RayInfoContainer *rays);

        /** Collects view cells in the subtree under root.
        */
        void CollectViewCells(VspNode *root, 
                                                  bool onlyValid, 
                                                  ViewCellContainer &viewCells,
                                                  bool onlyUnmailed = false) const;

        /** Returns view cell corresponding to 
                the invalid view space. If it does not exist, it is created.
        */
        VspViewCell *GetOrCreateOutOfBoundsCell();

        /** Collapses the tree with respect to the view cell partition,
                i.e. leaves having the same view cell are collapsed.
                @param node the root of the subtree to be collapsed
                @param collapsed returns the number of collapsed nodes
                @returns node of type leaf if the node could be collapsed, 
                this node otherwise
        */
        VspNode *CollapseTree(VspNode *node, int &collapsed);

        /** Helper function revalidating the view cell leaf list after merge.
        */
        void RepairViewCellsLeafLists();

        /** Evaluates tree stats in the BSP tree leafs.
        */
        void EvaluateLeafStats(const VspOspTraversalData &data);

        /** Subdivides node with respect to the traversal data.
            @param tStack current traversal stack
                @param tData traversal data also holding node to be subdivided
                @returns new root of the subtree
        */
        VspNode *Subdivide(VspOspSplitQueue &tQueue,
                                           VspOspSplitCandidate &splitCandidate);

        
        /** Subdivides leaf.
                @param leaf the leaf to be subdivided
                
                @param polys the polygons to be split
                @param frontPolys returns the polygons in front of the split plane
                @param backPolys returns the polygons in the back of the split plane
                
                @param rays the polygons to be filtered
                @param frontRays returns the polygons in front of the split plane
                @param backRays returns the polygons in the back of the split plane

                @returns the root of the subdivision
        */

        VspInterior *SubdivideNode(const AxisAlignedPlane &splitPlane,
                                                           VspOspTraversalData &tData,
                                                           VspOspTraversalData &frontData,
                               VspOspTraversalData &backData);

        /** Selects an axis aligned for the next split.
                @returns cost for this split
        */
        float SelectPlane(const VspOspTraversalData &tData,
                                          AxisAlignedPlane &plane,
                                          float &pFront,
                                          float &pBack);

        /** Sorts split candidates for surface area heuristics for axis aligned splits.
                @param polys the input for choosing split candidates
                @param axis the current split axis
                @param splitCandidates returns sorted list of split candidates
        */
        void SortSplitCandidates(const RayInfoContainer &rays, 
                                                         const int axis, 
                                                         float minBand, 
                                                         float maxBand);

        /** Computes best cost for axis aligned planes.
        */
        float BestCostRatioHeuristics(const RayInfoContainer &rays,
                                                                  const AxisAlignedBox3 &box,
                                                                  const int pvsSize,
                                                                  const int axis,
                                                                  float &position);

        /** Subdivides the rays into front and back rays according to the split plane.
                
                @param plane the split plane
                @param rays contains the rays to be split. The rays are 
                           distributed into front and back rays.
                @param frontRays returns rays on the front side of the plane
                @param backRays returns rays on the back side of the plane
                
                @returns the number of splits
        */
        int SplitRays(const Plane3 &plane,
                                  RayInfoContainer &rays, 
                              RayInfoContainer &frontRays, 
                                  RayInfoContainer &backRays) const;

        /** Adds the object to the pvs of the front and back leaf with a given classification.

                @param obj the object to be added
                @param cf the ray classification regarding the split plane
                @param frontPvs returns the PVS of the front partition
                @param backPvs returns the PVS of the back partition
        
        */
        void AddObjToPvs(Intersectable *obj, 
                                         const int cf, 
                                         float &frontPvs, 
                                         float &backPvs, 
                                         float &totalPvs) const;
        
        /** Computes PVS size induced by the rays.
        */
        int ComputePvsSize(const RayInfoContainer &rays) const;

        /** Returns true if tree can be terminated.
        */
        inline bool LocalTerminationCriteriaMet(const VspOspTraversalData &data) const;

        /** Returns true if global tree can be terminated.
        */
        inline bool GlobalTerminationCriteriaMet(const VspOspTraversalData &data) const;

        /** Adds ray sample contributions to the PVS.
                @param sampleContributions the number contributions of the samples
                @param contributingSampels the number of contributing rays
                
        */
        void AddToPvs(VspLeaf *leaf,
                                  const RayInfoContainer &rays, 
                                  float &sampleContributions,
                                  int &contributingSamples);

        /** Propagates valid flag up the tree.
        */
        void PropagateUpValidity(VspNode *node);

        /** Writes the node to disk
                @note: should be implemented as visitor.
        */
#if ZIPPED_VIEWCELLS
        void ExportNode(VspNode *node, ogzstream &stream);
#else
        void ExportNode(VspNode *node, ofstream &stream);
#endif

        /** Returns estimated memory usage of tree.
        */
        float GetMemUsage() const;


protected:

        ViewCellsManager *mViewCellsManager;
        vector<SortableEntry> *mSplitCandidates;

        /// Pointer to the root of the tree
        VspNode *mRoot;
                
        VspTreeStatistics mVspStats;
        
        /// View cell corresponding to the space outside the valid view space
        VspViewCell *mOutOfBoundsCell;

        /// box around the whole view domain
        AxisAlignedBox3 mBox;



        //-- local termination

        /// minimal number of rays before subdivision termination
        int mTermMinRays;
        /// maximal possible depth
        int mTermMaxDepth;
        /// mininum probability
        float mTermMinProbability;
        /// mininum PVS
        int mTermMinPvs;
        /// maximal contribution per ray
        float mTermMaxRayContribution;
        /// maximal acceptable cost ratio
        float mTermMaxCostRatio;
        /// tolerance value indicating how often the max cost ratio can be failed
        int mTermMissTolerance;


        //-- global criteria
        float mTermMinGlobalCostRatio;
        int mTermGlobalCostMissTolerance;
        int mGlobalCostMisses;

        /// maximal number of view cells
        int mMaxViewCells;
        /// maximal tree memory
        float mMaxMemory;
        /// the tree is out of memory
        bool mOutOfMemory;



        //-- split heuristics based parameters
        
        bool mUseCostHeuristics;
        /// balancing factor for PVS criterium
        float mCtDivCi; 
        /// if only driving axis should be used for split
        bool mOnlyDrivingAxis;
        /// if random split axis should be used
        bool mUseRandomAxis;
        /// if vsp bsp tree should simulate octree
        bool mCirculatingAxis;
        /// minimal relative position where the split axis can be placed
        float mMinBand;
        /// maximal relative position where the split axis can be placed
        float mMaxBand;


        /// current time stamp (used for keeping split history)
        int mTimeStamp;
        // if rays should be stored in leaves
        bool mStoreRays;

        /// epsilon for geometric comparisons
        float mEpsilon;

        /// if we should use breath first priority for the splits
        int mNodePriorityQueueType;

        // priority queue strategy
        enum {BREATH_FIRST, DEPTH_FIRST, COST_BASED};


        /// subdivision stats output file
        ofstream  mSubdivisionStats;
        /// keeps track of cost during subdivision
        float mTotalCost;
        /// keeps track of overall pvs size during subdivision
        int mTotalPvsSize;
        /// number of currenly generated view cells
        int mCreatedViewCells;

private:

        /// Generates unique ids for PVS criterium
        static void GenerateUniqueIdsForPvs();

        //-- unique ids for PVS criterium
        static int sFrontId; 
        static int sBackId;
        static int sFrontAndBackId;
};

}


#endif