source: GTP/trunk/App/Demos/Vis/CHC_revisited/Bvh.h @ 2753

// This file has been written by Jiri Bittner, October 2006

#ifndef __BVH_H
#define __BVH_H

#include "Geometry.h"
//#include "FlexibleHeap.h"


namespace CHCDemo
{

////////
// Forward declarations

class SceneGeometry;
class Camera;


/** A node in the bv hierarchy.
*/
class BvhNode
{
        friend class Bvh;

public:

        /** visibility related options
        */
        struct VisibilityInfo
        {
                VisibilityInfo() { Reset(); }           
                /** Reset the visibility info.
                */
                void Reset();

                /// if the node is visible
                bool mIsVisible;
                /// #frames this node is assumed to stay visible
                int mAssumedVisibleFrames;
                /// the frame when this node was last touched during traversal
                int mLastVisitedFrame;
                /// #times this node was invisible (only valid if the node actually is invisible)
                int mTimesInvisible;
                /// if the node is view frustum culled
                bool mIsFrustumCulled;
                /// if the node is newly processed with no prior history available
                bool mIsNew;
        };

        /** Constructor taking the parent node.
        */
        BvhNode(BvhNode *parent);
        
        /** Returns true if this node is a leaf.
        */
        //virtual bool IsPseudoLeaf() = 0;
        /** Virtual destructor doing nothing.
        */
        virtual ~BvhNode();
        /** Returns unique id for this node.
        */
        //inline int GetId() {return mId;}
        /** Depth of this node in the tree.
        */
        inline int GetDepth() const {return mDepth;}
        /** Returns parent of this bvh node, NULL if it is root.
        */
        inline BvhNode *GetParent() {return mParent;}
        /** Number of leaves in the subtree induced by this node.
        */
        inline int GetNumLeaves() const {return mNumLeaves;}
        /** Reset the status of this node.
        */
        virtual void ResetVisibility();

        virtual int GetType() = 0; //{ return BVH_NODE; }


        /////////////////////
        //-- visibility culling related functions

        inline int GetLastVisitedFrame() const;

        inline void SetLastVisitedFrame(const int lastVisited);
        /** If this node is considered visible.
        */
        inline bool IsVisible() const;
        /** Set visibility flag of the node.
        */
        inline void SetVisible(const bool visible);
        /** The assumed visible time span of this node.
        */
        inline void SetAssumedVisibleFrames(const int t);
        /** See set.
        */
        inline int GetAssumedVisibleFrames() const;
        /** The time span this node remains visible.
        */
        inline void SetRemainingVisibleFrames(const int t);
        /** Decrease the time this node is considered visible.
        */
        inline void DecAssumedVisibleFrames();
        /** Increases the #times this node was
                successfully tested invisible.
        */
        inline void IncTimesInvisible();
        
        inline int GetTimesInvisible() const;
        inline void SetTimesInvisible(const int t);
        
        inline int GetTurnedVisibleFrame() const;
        inline void SetTurnedVisibleFrame(const int turnedVisibleFrame);

        inline int GetLastTestedFrame();
        inline void SetLastTestedFrame(const int lastTested);
        
        inline bool IsViewFrustumCulled() const;
        inline void SetViewFrustumCulled(const bool frustumCulled);

        inline bool IsNew() const;
        inline void SetIsNew(const bool isNew);


        //////////
        //-- rendering
        
        /** Returns the frame in which this node was last rendered.
        */
        inline int GetLastRenderedFrame() const;
        /** See get.
        */
        inline void SetLastRenderedFrame(int lastRenderedFrame);
        /** Does this node contain renderable geometry?
        */
        inline bool Empty() const;
        /** Counts #geometry stored in the subtree.
        */
        inline int CountPrimitives() const;


protected:

        /////////////
        
        /// some flags
        int mFlags;
        /// the depth of this node
        unsigned char mDepth;
        /// the split axis
        char mAxis;
        /// the parent node
        BvhNode *mParent;
        /// stores the visibility related parameters
        VisibilityInfo mVisibility;

        /////////
        // used for view frustum culling

        int mPlaneMask;
        int mPreferredPlane;


        ////////////
        //-- rendering related options
        
        /// when the node was last rendered
        int mLastRenderedFrame;
        /// #leaves under this node
        int mNumLeaves;
        
        // Indices to first and last triangle in the triangle array
        // assumes the triangle are placed in continuous chunk of memory
        // however this need not be a global array!
        
        /// the index of the first triangle
        int mFirst;
        /// the index of the last triangle
        int mLast;

        /// these nodes can be tested instead of the current node
        int mTestNodesIdx;
        int mNumTestNodes;
        int mIndicesPtr;
        /// Area of this node
        float mArea;
};


/////////////////
//-- public inline functions

int BvhNode::GetLastVisitedFrame() const 
{ 
        return mVisibility.mLastVisitedFrame; 
}


void BvhNode::SetLastVisitedFrame(const int lastVisited) 
{ 
        mVisibility.mLastVisitedFrame = lastVisited; 
}


bool BvhNode::IsVisible() const 
{ 
        return mVisibility.mIsVisible; 
}


void BvhNode::SetVisible(const bool visible) 
{ 
        mVisibility.mIsVisible = visible; 
}


void BvhNode::IncTimesInvisible() 
{ 
        ++ mVisibility.mTimesInvisible; 
}


int BvhNode::GetTimesInvisible() const 
{ 
        return mVisibility.mTimesInvisible; 
}


void BvhNode::SetTimesInvisible(const int t) 
{ 
        mVisibility.mTimesInvisible = t; 
}


bool BvhNode::IsViewFrustumCulled() const 
{ 
        return mVisibility.mIsFrustumCulled; 
}


void BvhNode::SetViewFrustumCulled(const bool frustumCulled) 
{ 
        mVisibility.mIsFrustumCulled = frustumCulled; 
}


bool BvhNode::IsNew() const 
{ 
        return mVisibility.mIsNew;
}


void BvhNode::SetIsNew(const bool isNew) 
{ 
        mVisibility.mIsNew = isNew; 
}


int BvhNode::GetLastRenderedFrame() const 
{ 
        return mLastRenderedFrame; 
}
        

void BvhNode::SetLastRenderedFrame(int lastRenderedFrame)
{
        mLastRenderedFrame = lastRenderedFrame;
}
        
        
bool BvhNode::Empty() const 
{ 
        return mFirst == -1; 
}


int BvhNode::CountPrimitives() const 
{
        return mLast - mFirst + 1; 
}


void BvhNode::SetAssumedVisibleFrames(const int t) 
{ 
        mVisibility.mAssumedVisibleFrames = t; 
}


int BvhNode::GetAssumedVisibleFrames() const 
{ 
        return mVisibility.mAssumedVisibleFrames;
}

void BvhNode::DecAssumedVisibleFrames() 
{
        -- mVisibility.mAssumedVisibleFrames; 
}


/** Internal node of the bv hierarchy.
*/
class BvhInterior: public BvhNode
{
friend class Bvh;

public:
        BvhInterior(BvhNode *parent): mBack(NULL), mFront(NULL), BvhNode(parent)
        {}
        virtual bool IsLeaf() {return false;}
        /** Back child.
        */
        inline BvhNode *GetBack() { return mBack;}
        /** Front child.
        */
        inline BvhNode *GetFront() { return mFront;}
        /** recursivly delete tree.
        */
        virtual ~BvhInterior() { if (mBack) delete mBack; if (mFront) delete mFront;}
        /** Returns split axis of this interior node.
        */
        inline int GetAxis() {return (int)mAxis;}
        /** Returns position of the split axis.
        */
        inline float GetPosition() {return (float)mPosition;}


protected:

        /// the position of the split plane
        float mPosition;
        
        BvhNode *mBack;
        BvhNode *mFront;
};


class BvhLeaf: public BvhNode
{
friend class Bvh;

public:

        BvhLeaf(BvhNode *parent): BvhNode(parent)
        {}

        ~BvhLeaf();

        virtual bool IsLeaf() { return true; }
};


/** Class representing a bounding volume hierarchy.
*/
class Bvh
{
        /** Bvh properties
        */
        struct BvhStats
        {
                BvhStats(): 
                mInteriorSA(0),
                mLeafSA(0),
                mInteriorVol(0),
                mLeafVol(0),
                mBoundsInteriorSA(0),
                mBoundsLeafSA(0),
                mBoundsInteriorVol(0),
                mBoundsLeafVol(0),
                mBoundsLeavesCount(0),
                mTriangles(0),
                mTriangleRatio(0),
                mGeometryRatio(0),
                mMaxGeometry(0),
                mMaxTriangles(0)
                {}
                
                float mInteriorSA;
                float mLeafSA;
                float mInteriorVol;
                float mLeafVol; 
                float mBoundsInteriorSA;
                float mBoundsLeafSA;
                float mBoundsInteriorVol;
                float mBoundsLeafVol;
                int mBoundsLeavesCount;
                int mTriangles;

                float mTriangleRatio;
                float mGeometryRatio;

                int mMaxGeometry;
                int mMaxTriangles;
        };

public:

        /** Returns number of bvh nodes.
        */
        inline int GetNumNodes() const {return mNumNodes;}
        /** Returns number of bvh leaves.
        */
        inline int GetNumLeaves() const {return mNumNodes / 2 + 1;}
        /** Constructs the bounding volume hierarchy.
        */
        void Construct();
        /** Returns root node of the bvh.
        */
        BvhNode *GetRoot() {return mRoot;}
        /** Counts the triangle in this leaf.
        */
        int CountTriangles(BvhLeaf *leaf) const;


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

        /** Returns geometry by reference (faster).
        */
        SceneGeometry **GetGeometry(BvhNode *node, int &size);


        /////////////
        //-- Rendering related options

        /** Renders the bounding box of this node (Or the tigher bounding boxes of some subnodes).
        */
        void RenderBoundingBox(BvhNode *node);
        /** Renders bounding boxes of the collection of nodes.
                @returns #rendered boxes
        */
        int RenderBoundingBoxes(const BvhNodeContainer &nodes);



        //////////////
        //-- Traversal related options

        /** Pulls up visible classification.
        */
        void MakeParentsVisible(BvhNode *node);
        /** Does the view frustum culling for this node with respect to the previous culls
                @returns: 0 if completely outside, 1 if completely inside, -1 if intersecting (partly inside),
        */
        int     IsWithinViewFrustum(BvhNode *node);
        /** sets frame dependent values.
        */
        void InitFrame(Camera *camera, const int currentFrameId);
        /** this gives the orthogonal distance from the viewpoint to the nearest bounding box vertex
                note that negative values can appear because culling is done only afterwards
        */
        float CalcDistance(BvhNode *node) const;
        /** Sets maximal depth for taking the bounding boxes to test the
                visibility of a node. The deeper the more the box fits to the geometry.
        */
        void SetMaxDepthForTestingChildren(const int maxDepth);
        /** Pulls up the fully visible classification in the bvh.
        */
        void UpdateFullVisibility(BvhNode *node) const;
        /** Pulls up the last visited classification in the bvh.
        */
        void PullUpLastVisited(BvhNode *node, const int frameId) const;
        /** Resets the node classifications in the tree.
        */
        void ResetNodeClassifications();
        /** Helper function that renders the bounding boxes of the leaves as
                wireframes for visualization purpose.
        */
        void RenderBoundingBoxesForViz(const int mode);
        /** Returns squared min distance to the view point.
        */
        float GetSquareDistance(BvhNode *node) const;
        /** Count triangles the node contains.
        */
        int CountTriangles(BvhNode *node) const;
        /** Returns area of the geometry contained in the node.
        */
        float GetGeometryArea(BvhNode *node) const;


        ////////////
        //-- functions that change the boundaries of the nodes

        void SetUseTighterBoundsForTests(bool tighterBoundsForTests);

        void SetAreaRatioThresholdForTestingChildren(const float ratio);


        const BvhStats &GetBvhStats() const {return mBvhStats;}

        void SetCollectTighterBoundsWithMaxLevel(bool t);


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

        static unsigned int sCurrentVboId;
        

protected:

        /** Small struct representing a frustum.
        */
        struct Frustum
        {
                /// the 6 clip planes
                float mClipPlane[6][4];
        };
        


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

        /** Constructor loading the bvh from disc
        */
        Bvh(const std::string &filename);
        /** protected constructor: do nothing.
        */
        //Bvh(): mCamera(NULL), mFrameId(-1), mVertices(NULL), mRenderer(NULL) {}
        /** Destructor.
        */
        ~Bvh();


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

        void ComputeBvhStats();
        void PrintBvhStats() const;


        //////////
        //-- Helper methods for bounding box rendering in immediate and vbo mode.
        
        void PrepareVertices();

        int PrepareBoundingBoxesWithDrawArrays(const BvhNodeContainer &nodes);
        void RenderBoundingBoxesWithDrawArrays(int numNodes);

        int RenderBoundingBoxesImmediate(const BvhNodeContainer &nodes);
        /** Renders a bounding box in immediate mode using index restart
                and restarts the strip only if wished.
        */
        void RenderBoundingBoxImmediate(const AxisAlignedBox3 &box, bool restartStrip);
        /** Create the indices that each node needs to use vbo rendering.
        */
        void CreateIndices();
        /** Create the list of nodes whose bounding boxes are tested instead of the
                bounding box of the node itself.
        */
        bool CreateNodeRenderList(BvhNode *node);
        /** Recursivly updates indices so we can 
                render also interior nodes without traversing hierarchy
        */
        void UpdateInteriors(BvhNode *node);
        /** Recomputes the boundaries of the nodes. This function is always called if
                some boundary options are changed.
        */
        void RecomputeBounds();
        /** Does some postprocessing on the leaves.
                @returns #leaves that were chosen for tighter bounds.
        */
        int PostProcessLeaves(BvhLeafContainer &leaves);


        int     IsWithinViewFrustumLocal(BvhNode *node);

        int     IsWithinViewFrustum(const AxisAlignedBox3 &box, int planeMask, int preferredPlane);
        
        float GetMinSquareDistance(const AxisAlignedBox3 &box) const;
        
        
        ////////////////////////

        /// the root of the hierarchy
        BvhNode *mRoot;
        /// pointers to the geometry associated with this node
        SceneGeometry **mGeometry;
        /// #of entities
        size_t mGeometrySize;


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


        /// these values are valid for all nodes
        char mClipPlaneAABBVertexIndices[6][2];
        /// the current view frustum
        Frustum mFrustum;
        /// the current camera
        Camera *mCamera;
        // current frame id
        int mFrameId;
        /// a vertex array used if working with indexed arrays (without vbo)
        //Point3f *mVertices;
        /// indices used for draw array rendering
        unsigned int *mIndices;

        /** maximal depth from which children are fetched for 
                testing instead of the current node
        */
        int mMaxDepthForTestingChildren;

        float mAreaRatioThreshold;
        float mVolRatioThreshold;

        BvhStats mBvhStats;

        //HierarchyNodeContainer mTestNodes;
        
        unsigned int *mTestIndices;
        /// a pointer to the end of the indices array
        int mCurrentIndicesPtr;

        float mScale;

        Vector3 mNearPlane;
        float mNearPlaneD;
        int mNumNodes;
};

}

#endif // __BVH_H