source: GTP/trunk/Lib/Vis/Preprocessing/src/VspTree.h @ 2539

#ifndef _VspTree_H__
#define _VspTree_H__

#include <stack>

#include "Mesh.h"
#include "Containers.h"
#include "Statistics.h"
#include "VssRay.h"
#include "RayInfo.h"
#include "gzstream.h"
#include "SubdivisionCandidate.h"
#include "HierarchyManager.h"
#include "Timer/PerfTimer.h"


#ifdef USE_SSE
#include <xmmintrin.h>
#endif


namespace GtpVisibilityPreprocessor {

class ViewCellLeaf;
class Plane3;
class AxisAlignedBox3;
class Ray;
class ViewCellsStatistics;
class ViewCellsManager;
class MergeCandidate;
class Beam;
class ViewCellsTree;
class Environment;
class VspInterior;
class VspLeaf;
class VspNode;
class KdNode;
class KdInterior;
class KdLeaf;
class HierarchyManager;
class KdIntersectable;
class KdTree;
class VspTree;
class KdTreeStatistics;



/** View space partition statistics.
*/
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;
        /// number of rays refs
        int rayRefs;
        /// overall pvs size
        int pvs;
        // accumulated depth (used to compute average)
        int accumDepth;
        // global cost ratio violations
        int mGlobalCostMisses;

        // 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 rayRefs / (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;
                rayRefs = 0;
                maxObjectRefs = 0;
                mGlobalCostMisses = 0;
        }

        void Print(std::ostream &app) const;

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


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

public:
        
        /// types of vsp nodes
        enum {Interior, Leaf};

        VspNode();
        virtual ~VspNode(){};
        VspNode(VspInterior *parent);

        /** Determines whether this node is a leaf or not
                @return true if leaf
        */
        virtual bool IsLeaf() const = 0;

        virtual int Type() 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 this node (which represents the whole subtree) is valid
        */
        bool TreeValid() const;
        /** Sets this node to valid.
        */
        void SetTreeValid(const bool v);
        /** Cost of mergin this node.
        */
        float GetMergeCost() {return (float)-mTimeStamp; }

        /// timestamp of this node
        int mTimeStamp;

        /////////
        //-- mailing options

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


        static int sMailId;
        int mMailbox;

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

public:

        /** Standard contructor taking split plane as argument.
        */
        VspInterior(const AxisAlignedPlane &plane);

        ~VspInterior();
        /** @return false since it is an interior node 
        */
        bool IsLeaf() const { return false; }

        int Type() const;
        /** Returns back child.
        */
        VspNode *GetBack() { return mBack; }
        /** Returns front child.
        */
        VspNode *GetFront() { return mFront; }
        /** Returns split plane.
        */
        AxisAlignedPlane GetPlane() const { return mPlane; }
        /** Returns position of split plane.
        */
        float GetPosition() const { return mPlane.mPosition; }
        /** Returns split axis.
        */
        int GetAxis() const { return mPlane.mAxis; }
        /** Replace front or back child with new child.
        */
        void ReplaceChildLink(VspNode *oldChild, VspNode *newChild);
        /** Replace front and back child.
        */
        void SetupChildLinks(VspNode *front, VspNode *back);
        /** Returns boundiŽng box of this node.
        */
        AxisAlignedBox3 GetBoundingBox() const;
        /** Sets boundiong box of this node.
        */
        void SetBoundingBox(const AxisAlignedBox3 &box);
        /** Computes intersection of this plane with the ray segment.
        */
        int ComputeRayIntersection(const RayInfo &rayData, float &t) const
        {
                return rayData.ComputeRayIntersection(mPlane.mAxis, mPlane.mPosition, t);
        }

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


protected:

        /// bounding box for this interior node: should we really store this?
        AxisAlignedBox3 mBoundingBox;
        /// Splitting plane corresponding to this node
        AxisAlignedPlane mPlane;
        /// back node
        VspNode *mBack;
        /// front node
        VspNode *mFront;
};


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

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 { return true; }
        
        int Type() const;

        /** Returns pointer of view cell.
        */
        ViewCellLeaf *GetViewCell() const { return mViewCell; }
        /** Sets pointer to view cell.
        */
        void SetViewCell(ViewCellLeaf *viewCell);

        SubdivisionCandidate *GetSubdivisionCandidate()
        { 
                return mSubdivisionCandidate; 
        }

        void SetSubdivisionCandidate(SubdivisionCandidate *candidate)
        { 
                mSubdivisionCandidate = candidate; 
        }


public:

        /// Rays piercing this leaf.
        VssRayContainer mVssRays;
        
        /// Probability that the view point lies in this leaf
        float mProbability;

protected:

        /// pointer to a split plane candidate splitting this leaf
        SubdivisionCandidate *mSubdivisionCandidate;
        
        /// if NULL this does not correspond to feasible viewcell
        ViewCellLeaf *mViewCell;
};


/** View Space Partitioning tree.
*/
class VspTree 
{
        friend class ViewCellsParseHandlers;
        friend class HierarchyManager;

public:
        
        ///////////
        //-- Helper structs / classes

        /** Additional data which is passed down the BSP tree during traversal.
        */
        struct VspTraversalData
        {  
        public:
                
                VspTraversalData();
                
                VspTraversalData(VspLeaf *node, 
                                                 const int depth, 
                                                 RayInfoContainer *rays,
                                                 const float pvs,
                                                 const float p,
                                                 const AxisAlignedBox3 &box);

        
                /** Returns cost of the traversal data.
                */
                inline float GetCost() const;
                /** Returns average ray contribution.
                */
                inline float GetAvgRayContribution() const;
                /** Returns average rays per object.
                */
                inline float GetAvgRaysPerObject() const;
                /** deletes contents and sets them to NULL.
                */
                void Clear();


                //////////////////////

                /// the current node
                VspLeaf *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;
                /// how often this branch has missed the max-cost ratio
                int mMaxCostMisses;
                // current priority
                float mPriority;
                /// pvs size
                float mPvs;
                /// the correction factor for this pvs
                float mCorrectedPvs;
                /// pvs size
                float mRenderCost;
                /// the correction factor for this pvs
                float mCorrectedRenderCost;

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

        /** Helper struct for data that comes with a split of a node.
        */
        struct SplitData 
        {
                SplitData(): 
        mFrontRenderCost(0), 
                mBackRenderCost(0), 
                mTotalRenderCost(0), 
                mFrontObjects(0),
        mBackObjects(0),
                mTotalObjects(0),
                mFrontTriangles(0),
                mBackTriangles(0),
                mTotalTriangles(0) 
                {}

                //////////////

                float mFrontRenderCost;
                float mBackRenderCost;
                float mTotalRenderCost;

                int mFrontObjects;
                int mBackObjects;
                int mTotalObjects;

                int mFrontTriangles;
                int mBackTriangles;
                int mTotalTriangles;
        };


        /** Candidate for a view space split.
        */
        class VspSubdivisionCandidate: public SubdivisionCandidate
        {  
        public:

                VspSubdivisionCandidate(const VspTraversalData &tData): mParentData(tData)
                {};

                ~VspSubdivisionCandidate() 
                {
                        mParentData.Clear(); 
                }

                int Type() const { return VIEW_SPACE; }

                void EvalCandidate(bool computeSplitplane = true)
                {
                        mDirty = false;
                        sVspTree->EvalSubdivisionCandidate(*this, computeSplitplane);
                }

                bool GlobalTerminationCriteriaMet() const
                {
                        return sVspTree->GlobalTerminationCriteriaMet(mParentData);
                }

                bool Apply(SplitQueue &splitQueue, 
                                   bool terminationCriteriaMet, 
                                   SubdivisionCandidateContainer &dirtyList)
                {
                        VspNode *n = sVspTree->Subdivide(splitQueue, this, terminationCriteriaMet);
                        
                        // local or global termination criteria failed
                        const bool success = !n->IsLeaf();      

                        if (success)
                                CollectDirtyCandidates(dirtyList, true);

                        return success;
                }

                void CollectDirtyCandidates(SubdivisionCandidateContainer &dirtyList,
                                                                        const bool onlyUnmailed)
                {
                        sVspTree->CollectDirtyCandidates(this, dirtyList, onlyUnmailed);
                }

                VspSubdivisionCandidate(const AxisAlignedPlane &plane, const VspTraversalData &tData): 
                        mSplitPlane(plane), mParentData(tData)
                {}

                float GetPriority() const {     return mPriority; }


                ////////////////////

                static VspTree* sVspTree;
                /// the current split plane
                AxisAlignedPlane mSplitPlane;
                /// parent node traversal data
                VspTraversalData mParentData;
        
                float mCorrectedFrontPvs;
                float mCorrectedBackPvs;

                float mFrontPvs;
                float mBackPvs;

                float mFrontTriangles;
                float mBackTriangles;
                
                float mCorrectedFrontRenderCost;
                float mCorrectedBackRenderCost;
                
                float mFrontRenderCost;
                float mBackRenderCost;
        };

        /** Struct for traversing line segment.
        */
        struct LineTraversalData 
        {
                VspNode *mNode;
                Vector3 mExitPoint;
                float mMaxT;
    
                LineTraversalData () {}
                LineTraversalData (VspNode *n, const Vector3 &p, const float maxt):
                mNode(n), mExitPoint(p), mMaxT(maxt) {}
        };


        //////////////////////


        /** Default constructor creating an empty tree.
        */ 
        VspTree();
        /** Default destructor.
        */
        ~VspTree();
        /** Returns BSP Tree statistics.
        */
        const VspTreeStatistics &GetStatistics() const; 
        /** Returns bounding box of the specified node.
        */
        AxisAlignedBox3 GetBoundingBox(VspNode *node) const;
        /** 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 of a leaf to be added (-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(VspLeaf *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,
                                                const bool useMailboxing = true);
        /** Sets pointer to view cells manager.
        */
        void SetViewCellsManager(ViewCellsManager *vcm);
        /** 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();
        /** 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();
        /** 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;
        /** Returns view cells of this ray, either taking precomputed cells
                or by recomputation.
        */
        void GetViewCells(const VssRay &ray, ViewCellContainer &viewCells);
        /** Returns view cells tree.
        */
        ViewCellsTree *GetViewCellsTree() const { return mViewCellsTree; }
        /** Sets the view cells tree.
        */
        void SetViewCellsTree(ViewCellsTree *vt) { mViewCellsTree = vt; }
        /** Writes vsp tree to output stream
        */
        bool Export(OUT_STREAM &stream);
        /** Writes vsp tree to binary output stream.
        */
        bool ExportBinary(OUT_STREAM &stream);
        /** Imports tree from binary format.
        */
        bool ImportBinary(IN_STREAM &stream, ObjectContainer &pvsObjects);


        ////////////

        PerfTimer mSortTimer;
        PerfTimer mSplitTimer;
        PerfTimer mNodeTimer;
        PerfTimer mSubdivTimer;
        PerfTimer mEvalTimer;
        PerfTimer mPlaneTimer;
        PerfTimer mViewCellsTimer;

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 inline bool operator<(const SortableEntry &a, const SortableEntry &b)
                {       // prefer max event
                        //if (EpsilonEqual(a.value, b.value, 0.0001f))
                        //      return (a.type == ERayMax);

                        return (a.value < b.value);
                }
        };

        /** faster evaluation of split plane cost for kd axis aligned cells.
        */
        float EvalLocalSplitCost(const VspTraversalData &data,
                                                         const AxisAlignedBox3 &box,
                                                         const int axis,
                                                         const float &position,
                                                         float &pFront,
                                                         float &pBack) const;
        /** If != NULL, sets the bounding box to the forced  bounding box.
                Else computes the bounding box of the view space using the
                hit points gathered from the ray-object intersections.
        */
        void ComputeBoundingBox(const VssRayContainer &rays,
                                                        AxisAlignedBox3 *forcedBoundingBox);
        /** Evaluates candidate for splitting.
        */
        void EvalSubdivisionCandidate(VspSubdivisionCandidate &candidate, 
                                                                  bool computeSplitPlane = true);
        /** Evaluates render cost decrease of next split.
        */
        float EvalRenderCostDecrease(VspSubdivisionCandidate &candidate, 
                                                                 float &normalizedOldRenderCost,
                                                                 const SplitData &data) const;
        /** 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 VspTraversalData &data);

        /** Subdivides node using a best split priority queue.
            @param tQueue the best split priority queue
                @param splitCandidate the candidate for the next split
                @param globalCriteriaMet if the global termination criteria were already met
                @returns new root of the subtree
        */
        VspNode *Subdivide(SplitQueue &tQueue,
                                           SubdivisionCandidate *splitCandidate,
                                           const bool globalCriteriaMet);
        /** Adds stats to subdivision log file.
        */
        void AddSubdivisionStats(const int viewCells,
                                                         const float renderCostDecr,
                                                         const float totalRenderCost,
                                                         const float avgRenderCost);
        /** Subdivides leaf.
                @param tData data object holding, e.g., a pointer to the leaf
                @param frontData returns the data (e.g., pointer to the leaf) in front of the split plane
                @param backData returns the data (e.g., pointer to the leaf) in the back of the split plane
        
                @returns the root of the subdivision
        */
        VspInterior *SubdivideNode(const VspSubdivisionCandidate &sc,
                                                           VspTraversalData &frontData,
                               VspTraversalData &backData);

        /** Selects an axis aligned for the next split.
                @returns cost for this split
        */
        float SelectSplitPlane(const VspTraversalData &tData,
                                                   AxisAlignedPlane &plane,
                                                   float &pFront,
                                                   float &pBack);
        /** Sorts split candidates along the specified axis.
                The split candidates are generated on possible visibility
                events (i.e., where ray segments intersect the ray boundaries).
                The sorted candidates are needed to compute the heuristics.

                @param polys the input for choosing split candidates
                @param axis the current split axis
                @param splitCandidates returns sorted list of split candidates
        */
        void SortSubdivisionCandidates(const RayInfoContainer &rays, 
                                                                   const int axis, 
                                                                   float minBand, 
                                                                   float maxBand);
        /** Evaluate render cost of this pvs.
        */
        float EvalPvsCost(const RayInfoContainer &rays) const;

        int EvalPvsEntriesIncr(VspSubdivisionCandidate &splitCandidate,
                                                   const SplitData &sData) const;
        /** Returns number of effective entries in the pvs.
        */
        int EvalPvsEntriesSize(const RayInfoContainer &rays) const;

        int EvalPvsEntriesContribution(const VssRay &ray, const bool isTermination) const;
        /** Computes best cost for axis aligned planes.
        */
        float EvalLocalCostHeuristics(const VspTraversalData &tData,
                                                                  const AxisAlignedBox3 &box,
                                                                  const int axis,
                                                                  float &position,
                                                                  const RayInfoContainer &usedRays);


        ///////////////////////
        //-- Helper function for computing heuristics

        /** Evaluates the contribution to left and right pvs at a visibility event ve.
                @param ve the visibility event
                @param pvsLeft updates the left pvs
                @param rightPvs updates the right pvs
        */
        inline void EvalHeuristics(const SortableEntry &ve, float &pvsLeft, float &pvsRight) const;
        /** Evaluates contribution of min event to pvs
        */
        inline float EvalMinEventContribution(const VssRay &ray, const bool isTermination) const;
        /** Evaluates contribution of max event to pvs
        */
        inline float EvalMaxEventContribution(const VssRay &ray, const bool isTermination) const;
        /** Evaluates contribution of kd leaf when encountering a min event
        */
        inline float EvalMinEventContribution(KdLeaf *leaf) const;
        /**  Evaluates contribution of kd leaf when encountering a max event
        */
        inline float EvalMaxEventContribution(KdLeaf *leaf) const;
        /** Prepares objects for the heuristics.
                @returns pvs size as seen by the rays.
        */
        float PrepareHeuristics(const RayInfoContainer &rays);
        /** Prepare a single ray for heuristics.
        */
        float PrepareHeuristics(const VssRay &ray, const bool isTermination);
        /** Prepare a single kd leaf for heuristics.
        */
        float PrepareHeuristics(KdLeaf *leaf);
        /** Evaluates minimal and maximal depth in the tree.
        */
        void EvalMinMaxDepth(int &minDepth, int &maxDepth);
        /** Writes the node to disk
                @note: should be implemented as visitor.
        */
        void ExportNode(VspNode *node, OUT_STREAM &stream);
        

        ////////////////

        void ExportBinInterior(OUT_STREAM &stream, VspInterior *interior);
        void ExportBinLeaf(OUT_STREAM &stream, VspLeaf *leaf);

        VspInterior *ImportBinInterior(IN_STREAM  &stream, VspInterior *parent);
        VspLeaf *ImportBinLeaf(IN_STREAM &stream, VspInterior *parent, const ObjectContainer &pvsObjects);

        VspNode *ImportNextNode(IN_STREAM &stream, 
                                                        VspInterior *parent,
                                                        const ObjectContainer &pvsObjects);


        //////////////////////////////////////////////////

        /** 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 AxisAlignedPlane &plane,
                                  RayInfoContainer &rays, 
                              RayInfoContainer &frontRays, 
                                  RayInfoContainer &backRays) const;
        /** Add contributions of this ray to fron, back, and overall pvs of the parent.
        */
        inline void UpdatePvsEntriesContribution(const VssRay &ray,
                                                                                         const bool isTermination,
                                                                                         const int cf,
                                                                                         float &frontPvs,
                                                                                         float &backPvs,
                                                                                         float &totalPvs) const;
        /** Classfifies the object with respect to the 
                pvs of the front and back leaf and updates pvs size
                accordingly.

                @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
        
        */
        inline void UpdateContributionsToPvs(const VssRay &ray,
                                                                                 const bool isTermination,
                                                                                 const int cf,
                                                                                 float &frontPvs,
                                                                                 float &backPvs,
                                                                                 float &totalPvs) const;
        /** Evaluates the contribution for objects.
        */
        inline void UpdateContributionsToPvs(Intersectable *obj, 
                                                                                 const int cf, 
                                                                                 float &frontPvs, 
                                                                                 float &backPvs, 
                                                                                 float &totalPvs) const;
        /** Evaluates the contribution for bounding volume leaves.
        */
        inline void UpdateContributionsToPvs(BvhLeaf *leaf,
                                                                                 const int cf,
                                                                                 float &frontPvs,
                                                                                 float &backPvs,
                                                                                 float &totalPvs,
                                                                                 const bool countEntries) const;
        /** Updates contribution to pvs caused by this bvh leaf.
        */
        inline void UpdateContributionsToPvs(BvhLeaf *leaf,
                                                                                 const int cf,
                                                                                 SplitData &sdata) const;
        /** Evaluates the contribution for kd leaves.
        */
        inline void UpdateContributionsToPvs(KdLeaf *leaf,
                                                                                 const int cf,
                                                                                 float &frontPvs,
                                                                                 float &backPvs,
                                                                                 float &totalPvs) const;
        /** Returns true if tree can be terminated.
        */
        inline bool LocalTerminationCriteriaMet(const VspTraversalData &data) const;
        /** Returns true if global tree can be terminated.
        */
        bool GlobalTerminationCriteriaMet(const VspTraversalData &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 AddSamplesToPvs(VspLeaf *leaf,
                                                 const RayInfoContainer &rays, 
                                                 float &sampleContributions,
                                                 int &contributingSamples);
        /** Propagates valid flag up the tree.
        */
        void PropagateUpValidity(VspNode *node);
        /** Returns estimated memory usage of tree.
        */
        float GetMemUsage() const;
        /** Updates view cell pvs of objects.
        */
        void ProcessViewCellObjects(ViewCell *parent, 
                                                                ViewCell *front, 
                                                                ViewCell *back) const;
        /** Creates a new view cell from the traversal data.
        */
        void CreateViewCell(VspTraversalData &tData, 
                                                const bool updatePvs,
                                                const float renderCost,
                                                const int pvs);
        /** Collect split candidates which are affected by the last split
                and must be reevaluated.
        */
        void CollectDirtyCandidates(VspSubdivisionCandidate *sc, 
                                                                vector<SubdivisionCandidate *> &dirtyList,
                                                                const bool onlyUnmailed);
        /** Adds the split candidate associated with this ray to the dirty list.
        */
        void AddCandidateToDirtyList(const VssRay &ray, 
                                                           const bool isTermination,
                                                           vector<SubdivisionCandidate *> &dirtyList,
                                                           const bool onlyUnmailed) const;
        /** Rays will be clipped to the bounding box.
        */
        void PreprocessRays(const VssRayContainer &sampleRays, RayInfoContainer &rays);
        /** Evaluate subdivision statistics.
        */
        void EvalSubdivisionStats(const SubdivisionCandidate &tData);
        /** Prepares the construction of the vsp tree.
        */
        void PrepareConstruction(SplitQueue &tQueue,
                                                         const VssRayContainer &sampleRays,
                                                         RayInfoContainer &rays);
        /** Evaluates pvs contribution of this ray.
        */
        float EvalContributionToPvs(const VssRay &ray, const bool isTermination) const;
        /** Evaluates pvs contribution of a kd node.
        */
        float EvalContributionToPvs(KdLeaf *leaf) const;
        /** Creates new root of hierarchy and computes bounding box.
                Has to be called before the preparation of the subdivision.
        */
        void Initialise(const VssRayContainer &rays,
                                        AxisAlignedBox3 *forcedBoundingBox,
                                        const ObjectContainer &objects);

        int CompressObjects();

        int CompressObjects(VspLeaf *leaf);

        int TraverseRayPacket(RayPacket &rp, const bool useMailboxing);

#ifdef USE_SSE
        struct PacketTraversalData
        {
                PacketTraversalData () {}
        
                PacketTraversalData (VspNode *n, 
                                         const __m128 &px, const __m128 &py, const __m128 &pz, 
                                                         const __m128 &maxt,
                                                         const __m128 &mask):
                mNode(n), 
                mExitPointX4(px), mExitPointY4(py), mExitPointZ4(pz),
                mMaxT4(maxt),
                mMask4(mask)
                {}

                VspNode *mNode;

                union { __m128 mExitPointX4; float mExitPointX[4]; };
                union { __m128 mExitPointY4; float mExitPointY[4]; };
                union { __m128 mExitPointZ4; float mExitPointZ[4]; };

                union { __m128 mMaxT4; float mMaxT[4]; };
                union { __m128 mMask4; float mMask[4]; };
        };


        struct __declspec(align(16)) PacketTraversalStack
        {
                // for performance
                friend class VspTree;

        public:
                PacketTraversalStack(const int depth):
                mStackPtr(0), 
                //mDepth(depth)
                mDepth(1000)
                {
                        //mData = new PacketTraversalData[mDepth];
                }

                ~PacketTraversalStack()
                {
                        //delete [] mData;
                }
                
                //PacketTraversalStack() {}

                void Pop() {-- mStackPtr;}
                const PacketTraversalData &Top() const { return mData[mStackPtr - 1];}
                
                void Push(const PacketTraversalData &tData) 
                {
                        // note: faster with direct assignments
                        mData[mStackPtr ++] = tData;
                        //if (mStackPtr == mDepth) std::cerr << "this can never happen!!" << std::endl;
                }

                bool Empty() const {return mStackPtr <= 0;}

        protected:

                // static array to avoid using operator new
                //PacketTraversalData *mData;
                PacketTraversalData mData[1000];

                int mStackPtr;
                int mDepth;
        };

#endif


protected:

        /// pointer to the hierarchy of view cells
        ViewCellsTree *mViewCellsTree;
        /// Pointer to the hierarchy manager which is responsible for both 
        /// view and object space
        HierarchyManager *mHierarchyManager;
        /// Pointer to the bv hierarchy
        BvHierarchy *mBvHierarchy;
        /// Pointer to the view cells manager
        ViewCellsManager *mViewCellsManager;
        /// Buffer for subdivision candidates used for split heuristics evaluation
        vector<SortableEntry> *mLocalSubdivisionCandidates;
        /// Pointer to the root of the tree
        VspNode *mRoot;
        /// The statistics
        VspTreeStatistics mVspStats;
        /// View cell corresponding to the space outside the valid view space
        VspViewCell *mOutOfBoundsCell;
        /// box around the whole view domain
        AxisAlignedBox3 mBoundingBox;


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

        /// 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;
        /// subdivision stats output file
        std::ofstream mSubdivisionStats;
        /// keeps track of cost during subdivision
        float mTotalCost;
        /// keeps track of #pvs entries during subdivison
        int mPvsEntries;
        /// keeps track of overall pvs size during subdivision
        int mTotalPvsSize;
        /// number of currenly generated view cells
        int mCreatedViewCells;

        /// weight between render cost decrease and node render cost
        float mRenderCostDecreaseWeight;
        /// maximal #of rays used for heuristics evalution
        int mMaxTests;
        /// constant value for driving the heuristics
        float mMemoryConst;
};


}

#endif