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

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

#ifndef __BVH_H
#define __BVH_H

#include "Geometry.h"


namespace CHCDemo
{

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

class SceneEntity;
class Camera;


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

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 bool IsLeaf() = 0; //{ return BVH_NODE; }


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

        inline int GetLastVisitedFrame() const;

        inline void SetLastVisitedFrame(int lastVisited);
        /** If this node is considered visible.
        */
        inline bool IsVisible() const;
        /** Set visibility flag of the node.
        */
        inline void SetVisible(bool visible);
        /** The assumed visible time span of this node.
        */
        inline void SetAssumedVisibleFrames(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(int t);
        
        inline int GetTurnedVisibleFrame() const;
        inline void SetTurnedVisibleFrame(int turnedVisibleFrame);

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

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


        /** Returns the bounding box of this node.
        */
        inline const AxisAlignedBox3 &GetBox() { return mBox; }
        /** Return index of this node.
        */
        inline int GetId() const { return mId; }
        /** See get
        */
        inline void SetId(int id) { mId = id; }


        //////////
        //-- 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 info
        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;
        /// distance to the camera
        float mDistance;
        /// the index of this node
        unsigned int mId;
        /// indices used for draw array rendering
        unsigned int *mIndices;
        /// the bounding box
        AxisAlignedBox3 mBox;

};


/////////////////
//-- 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;
        friend class BvhLoader;

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;
        friend class BvhLoader;

public:

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

        ~BvhLeaf();

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


/**     This class implements the compare operator for the priority queue.
        a lower distance has a higher value in the queue
*/
class myless
{
public:
        bool operator() (BvhNode *v1, BvhNode *v2) const
    {
                return (v1->mDistance > v2->mDistance);
    }
};


/** Class representing a bounding volume hierarchy.
*/
class Bvh
{
        friend class BvhLoader;

        /** 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;}
        /** Returns root node of the bvh.
        */
        BvhNode *GetRoot() { return mRoot; }
        /** Counts the triangle in this leaf.
        */
        int CountTriangles(BvhLeaf *leaf) const;


        void CollectNodes(BvhNode *node, BvhNodeContainer &nodes, int depth);
        void CollectNodes(BvhNode *node, BvhNodeContainer &nodes);
        void CollectLeaves(BvhNode *node, BvhLeafContainer &leaves);


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

        /** Returns geometry by reference (faster).
        */
        SceneEntity **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, 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;
        /** Pulls up the last visited classification in the bvh.
        */
        void PullUpLastVisited(BvhNode *node, 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(int mode);
        /** 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 influencing tighter bounds


        /** Sets maximal depth for taking the bounding boxes to test the
                visibility of a node. 
                Deeper => the bounds adapt more to the geometry.
        */
        void SetMaxDepthForTestingChildren(int maxDepth);

        void SetAreaRatioThresholdForTestingChildren(float ratio);

        /** Returns stats.
        */
        const BvhStats &GetBvhStats() const {return mBvhStats;}
        

protected:

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

        /** protected constructor: do nothing.
        */
        Bvh();
        /** 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);

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

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


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

        /// the current camera
        Camera *mCamera;
        // current frame id
        int mFrameId;
        /// a vertex array used if working with indexed arrays (without vbo)
        Vector3 *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;


        BvhStats mBvhStats;

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

        int mNumNodes;


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

        static unsigned int sCurrentVboId;
};

}

#endif // __BVH_H