source: GTP/trunk/Lib/Vis/Preprocessing/src/FromPointVisibilityTree.h @ 1006

#ifndef _FromPointVisibilityTree_H__
#define _FromPointVisibilityTree_H__

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

namespace GtpVisibilityPreprocessor {

class ViewCell;
class Plane3;
class FromPointVisibilityTree;  
class BspInterior;
class BspNode;
class AxisAlignedBox3;
class Ray;
class ViewCellsStatistics;
class ViewCellsManager;
class MergeCandidate;
class Beam;
class ViewCellsTree;



/** A location in space representing from point-visibility.
*/
struct VisibilityPoint
{
        Vector3 mPosition;

        /// from point visibility => visible objects, not potentially
        ObjectPvs mVisibleObjects;
};


/**
        This is a tree which partitions from point queries in a greedy optimal fashion.
*/
class FromPointVisibilityTree 
{
        friend class ViewCellsParseHandlers;
        friend class VspBspViewCellsManager;

public:
        
        /** Additional data which is passed down the BSP tree during traversal.
        */
        class VspBspTraversalData
        {  
        public:
                /// the current node
                BspNode *mNode;
                /// polygonal data for splitting
                PolygonContainer *mPolygons;
                /// current depth
                int mDepth;
                /// rays piercing this node
                RayInfoContainer *mRays;
                /// the probability that this node contains view point
                float mProbability;
                /// geometry of node as induced by planes
                BspNodeGeometry *mGeometry;
                /// pvs size
                int mPvs;
                /// how often this branch has missed the max-cost ratio
                int mMaxCostMisses;
                /// if this node is a kd-node (i.e., boundaries are axis aligned
                bool mIsKdNode;
                // current axis
                int mAxis;
                // current priority
                float mPriority;

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


                VspBspTraversalData():
                mNode(NULL),
                mPolygons(NULL),
                mDepth(0),
                mRays(NULL),
                mPvs(0),
                mProbability(0.0),
                mGeometry(NULL),
                mMaxCostMisses(0), 
                mIsKdNode(false),
                mPriority(0),
                mAxis(0)
                {}
                
                VspBspTraversalData(BspNode *node, 
                                                        PolygonContainer *polys, 
                                                        const int depth, 
                                                        RayInfoContainer *rays,
                                                        const int pvs,
                                                        const float p,
                                                        BspNodeGeometry *geom): 
                mNode(node), 
                mPolygons(polys), 
                mDepth(depth), 
                mRays(rays),
                mPvs(pvs),
                mProbability(p),
                mGeometry(geom),
                mMaxCostMisses(0),
                mIsKdNode(false),
                mPriority(0),
                mAxis(0)
                {}

                VspBspTraversalData(PolygonContainer *polys, 
                                                        const int depth, 
                                                        RayInfoContainer *rays,
                                                        BspNodeGeometry *geom): 
                mNode(NULL), 
                mPolygons(polys), 
                mDepth(depth), 
                mRays(rays),
                mPvs(0),
                mProbability(0),
                mGeometry(geom),
                mMaxCostMisses(0),
                mIsKdNode(false),
                mAxis(0)
                {}

                /** 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(mPolygons);
                        DEL_PTR(mRays);
                        DEL_PTR(mGeometry);
                }

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

        typedef std::priority_queue<VspBspTraversalData> VspBspTraversalQueue;
        
        
        struct VspBspSplitCandidate
        {  
                /// the current node
                Plane3 mSplitPlane;
                /// split axis of this plane (0, 1, 2, or 3 if non-axis-aligned)
                int mSplitAxis;
                /// the number of misses of max cost ratio until this split
                int mMaxCostMisses;

                // parent data
                VspBspTraversalData mParentData;
                // cost of applying this split
                float mRenderCost;

                VspBspSplitCandidate(): mRenderCost(0) 
                {};

                VspBspSplitCandidate(const Plane3 &plane, const VspBspTraversalData &tData): 
                mSplitPlane(plane), mParentData(tData), mRenderCost(0)
                {}

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

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

        typedef std::priority_queue<VspBspSplitCandidate> VspBspSplitQueue;

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

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

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

        /** Constructs the tree from a given set of rays.
                @param sampleRays the set of sample rays the construction is based on
        */
        void Construct(const VssRayContainer &sampleRays,
                                   AxisAlignedBox3 *forcedBoundingBox);

        
        /** Constructs the tree from a given set of visibility points
                @param visibiltiyPointe visibility points the construction is based on
        */
        void Construct(const VisibilityPointsContainer &visibilityPoints, 
                                   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<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);

        /// bsp tree construction types
        enum {FROM_INPUT_VIEW_CELLS, FROM_SCENE_GEOMETRY, FROM_SAMPLES};

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

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

        /** Returns distance from node 1 to node 2.
        */
        int TreeDistance(BspNode *n1, BspNode *n2) const;

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

        /** Writes tree to output stream
        */
        bool Export(ofstream &stream);

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

        void CollectViewCells(BspNode *root, 
                                                  bool onlyValid, 
                                                  ViewCellContainer &viewCells,
                                                  bool onlyUnmailed = false) const;

        
        int FindApproximateNeighbors(BspNode *n, 
                                                             vector<BspLeaf *> &neighbors,
                                                                 const bool onlyUnmailed) const;

        /** 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 EvalAxisAlignedSplitCost(const VspBspTraversalData &data,
                                                                   const AxisAlignedBox3 &box,
                                                                   const int axis,
                                                                   const float &position,
                                                                   float &pFront,
                                                                   float &pBack) const;

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

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

        float EvalRenderCostDecrease(const Plane3 &candidatePlane,
                                                                 const VspBspTraversalData &data) const;

        void ConstructWithSplitQueue(const PolygonContainer &polys, RayInfoContainer *rays);


        /** Returns view cell corresponding to 
                the invalid view space. If it does not exist, it is created.
        */
        BspViewCell *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
        */
        BspNode *CollapseTree(BspNode *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 VspBspTraversalData &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
        */
        BspNode *Subdivide(VspBspTraversalQueue &tStack, 
                                           VspBspTraversalData &tData);

        BspNode *Subdivide(VspBspSplitQueue &tQueue,
                                           VspBspSplitCandidate &splitCandidate);

        /** Constructs the tree from the given traversal data.
                @param polys stores set of polygons on which subdivision may be based
                @param rays storesset of rays on which subdivision may be based
        */
        void Construct(const PolygonContainer &polys, RayInfoContainer *rays);

        /** Selects the best possible splitting plane. 
                @param plane returns the split plane
                @param leaf the leaf to be split
                @param polys the polygon list on which the split decition is based
                @param rays ray container on which selection may be based
                @note the polygons can be reordered in the process
                @returns true if the cost of the split is under maxCostRatio

        */
        bool SelectPlane(Plane3 &plane, 
                                         BspLeaf *leaf, 
                                         VspBspTraversalData &data,
                                         VspBspTraversalData &frontData,
                                         VspBspTraversalData &backData,
                                         int &splitAxis);
        
        /** Strategies where the effect of the split plane is tested
            on all input rays.

                @returns the cost of the candidate split plane
        */
        float EvalSplitPlaneCost(const Plane3 &candidatePlane, 
                                                         const VspBspTraversalData &data,
                                                         BspNodeGeometry &geomFront,
                                                         BspNodeGeometry &geomBack,
                                                         float &pFront,
                                                         float &pBack) const;

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

        BspInterior *SubdivideNode(const Plane3 &splitPlane,
                                                           VspBspTraversalData &tData,
                                                           VspBspTraversalData &frontData,
                               VspBspTraversalData &backData,
                                                           PolygonContainer &coincident);

        /** Extracts the meshes of the objects and adds them to polygons. 
                Adds object aabb to the aabb of the tree.
                @param maxPolys the maximal number of objects to be stored as polygons
                @returns the number of polygons
        */
        int AddToPolygonSoup(const ObjectContainer &objects, 
                                                 PolygonContainer &polys, 
                                                 int maxObjects = 0);

        /** Extracts the meshes of the view cells and and adds them to polygons.
                Adds view cell aabb to the aabb of the tree.
                @param maxPolys the maximal number of objects to be stored as polygons
                @returns the number of polygons
        */
        int AddToPolygonSoup(const ViewCellContainer &viewCells, 
                                                 PolygonContainer &polys, 
                                                 int maxObjects = 0);

        /** Extract polygons of this mesh and add to polygon container.
                @param mesh the mesh that drives the polygon construction
                @param parent the parent intersectable this polygon is constructed from
                @returns number of polygons
        */
        int AddMeshToPolygons(Mesh *mesh, PolygonContainer &polys, MeshInstance *parent);

        /** Selects an axis aligned for the next split.
                @returns cost for this split
        */
        float SelectAxisAlignedPlane(Plane3 &plane, 
                                                                 const VspBspTraversalData &tData,
                                                                 int &axis,
                                                                 BspNodeGeometry **frontGeom,
                                                                 BspNodeGeometry **backGeom,
                                                                 float &pFront,
                                                                 float &pBack,
                                                                 const bool useKdSplit);

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

        /** Selects an axis aligned split plane.
                @Returns true if split is valied
        */
        bool SelectAxisAlignedPlane(Plane3 &plane, const PolygonContainer &polys) const;

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


        /** Extracts the split planes representing the space bounded by node n.
        */
        void ExtractHalfSpaces(BspNode *n, vector<Plane3> &halfSpaces) 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 VspBspTraversalData &data) const;

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

        /** Computes accumulated ray lenght of this rays.
        */
        float AccumulatedRayLength(const RayInfoContainer &rays) const;

        /** Splits polygons with respect to the split plane.

                @param plane the split plane
                @param polys the polygons to be split. the polygons are consumed and
                           distributed to the containers frontPolys, backPolys, coincident.
                @param frontPolys returns the polygons in the front of the split plane
                @param backPolys returns the polygons in the back of the split plane
                @param coincident returns the polygons coincident to the split plane

                @returns the number of splits   
        */
        int SplitPolygons(const Plane3 &plane,
                                          PolygonContainer &polys, 
                                          PolygonContainer &frontPolys, 
                                          PolygonContainer &backPolys, 
                                          PolygonContainer &coincident) 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(BspLeaf *leaf,
                                  const RayInfoContainer &rays, 
                                  float &sampleContributions,
                                  int &contributingSamples);





        
        /** Take 3 ray endpoints, where two are minimum and one a maximum
                point or the other way round.
        */
        Plane3 ChooseCandidatePlane(const RayInfoContainer &rays) const;

        /** Take plane normal as plane normal and the midpoint of the ray.
                PROBLEM: does not resemble any point where visibility is 
                likely to change
        */
        Plane3 ChooseCandidatePlane2(const RayInfoContainer &rays) const;

        /** Fit the plane between the two lines so that the plane 
                has equal shortest distance to both lines.
        */
        Plane3 ChooseCandidatePlane3(const RayInfoContainer &rays) const;
  
        /** Collects candidates for merging.
                @param leaves the leaves to be merged
                @returns number of leaves in queue
        */
        int CollectMergeCandidates(const vector<BspLeaf *> leaves, vector<MergeCandidate> &candidates);

        /** Collects candidates for the merge in the merge queue.
                @returns number of leaves in queue
        */
        int CollectMergeCandidates(const VssRayContainer &rays, vector<MergeCandidate> &candidates);
        
        /** Preprocesses polygons and throws out all polygons which are coincident to
                the view space box faces (they can be problematic).
        */
        void PreprocessPolygons(PolygonContainer &polys);
        
        /** Propagates valid flag up the tree.
        */
        void PropagateUpValidity(BspNode *node);

        /** Writes the node to disk
                @note: should be implemented as visitor
        */
        void ExportNode(BspNode *node, ofstream &stream);

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



        /// Pointer to the root of the tree
        BspNode *mRoot;
                
        BspTreeStatistics mBspStats;

        /// Strategies for choosing next split plane.
        enum {NO_STRATEGY = 0,
                  RANDOM_POLYGON = 1, 
                  AXIS_ALIGNED = 2,
                  LEAST_RAY_SPLITS = 256,
                  BALANCED_RAYS = 512,
                  PVS = 1024
                };

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

        bool mUseCostHeuristics;

        /// 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;
        /// minimal accumulated ray length
        float mTermMinAccRayLength;

        //HACK
        int mTermMinPolygons;

        float mTermMinGlobalCostRatio;
        int mTermGlobalCostMissTolerance;

        int mGlobalCostMisses;

        bool mUseSplitCostQueue;
        //-- termination criteria for axis aligned split

        /// minimal number of rays for axis aligned split
        int mTermMinRaysForAxisAligned;
        // max ray contribution
        float mTermMaxRayContriForAxisAligned;

        /// strategy to get the best split plane
        int mSplitPlaneStrategy;
        /// number of candidates evaluated for the next split plane
        int mMaxPolyCandidates;
        /// number of candidates for split planes evaluated using the rays
        int mMaxRayCandidates;
        /// balancing factor for PVS criterium
        float mCtDivCi;

        //-- axis aligned split criteria
        float mAxisAlignedCtDivCi;
        /// spezifies the split border of the axis aligned split
        float mAxisAlignedSplitBorder;

        /// maximal acceptable cost ratio
        float mTermMaxCostRatio;
        /// tolerance value indicating how often the max cost ratio can be failed
        int mTermMissTolerance;

        //-- factors guiding the split plane heuristics
        float mLeastRaySplitsFactor;
        float mBalancedRaysFactor;
        float mPvsFactor;

        /// if area or volume should be used for PVS heuristics
        bool mUseAreaForPvs;
        /// tolerance for polygon split
        float mEpsilon;
        /// maximal number of test rays used to evaluate candidate split plane
        int mMaxTests;
        /// normalizes different bsp split plane criteria
        float mCostNormalizer;
        /// maximal number of view cells
        int mMaxViewCells;
        
        ofstream  mSubdivisionStats;

        // if rays should be stored in leaves
        bool mStoreRays;
        
        /// if only driving axis should be used for split
        bool mOnlyDrivingAxis;

        ViewCellsManager *mViewCellsManager;

        vector<SortableEntry> *mSplitCandidates;

        
        float mRenderCostWeight;
        /// View cell corresponding to the space outside the valid view space
        BspViewCell *mOutOfBoundsCell;

        /// maximal tree memory
        float mMaxMemory;
        /// the tree is out of memory
        bool mOutOfMemory;
        
        float mTotalCost;
        int mTotalPvsSize;

        float mMinBand;
        float mMaxBand;

        //int mSplits;
        /// subdivision stats output file
        ofstream mSubdivsionStats;
        /// if random split axis should be used
        bool mUseRandomAxis;
        /// use polygon split whenever there are polys left
        bool mUsePolygonSplitIfAvailable;
        /// current time stamp (used for keeping split history)
        int mTimeStamp;
        /// number of currenly generated view cells
        int mCreatedViewCells;
        /// if vsp bsp tree should simulate octree
        bool mCirculatingAxis;

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

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


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