source: GTP/trunk/App/Demos/Vis/FriendlyCulling/src/Bvh.h @ 3282

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

#ifndef __BVH_H
#define __BVH_H

#include "common.h"
#include "Vector3.h"
#include "AxisAlignedBox3.h"



namespace CHCDemoEngine
{

// the number of visibility states
#define NUM_STATES 2

////////
//-- Forward declarations

class SceneEntity;
class Camera;
class RenderState;


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

public:

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

                /// if the node is visible
                bool mIsVisible;
                /// frame id until this node is assumed to stay visible
                int mAssumedVisibleFrameId;
                /// 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;
                /// the frame this node was last queried
                int mLastQueriedFrame;
        };

        /** Constructor taking the parent node.
        */
        BvhNode(BvhNode *parent);
        /** Virtual destructor doing nothing.
        */
        virtual ~BvhNode();
        /** Reset the status of this node.
        */
        virtual void ResetVisibility();
        /** Returns true if this node is a leaf.
        */
        virtual bool IsLeaf() const = 0;
        /** Depth of this node in the tree.
        */
        inline int GetDepth() const;
        /** Returns parent of this bvh node, NULL if it is root.
        */
        inline BvhNode *GetParent();
        /** Number of leaves in the subtree induced by this node.
        */
        inline int GetNumLeaves() const;
        /** Returns true if this node is a "virtual" leaf,
                i.e., the node is handled as a leaf during traversal.
        */
        inline bool IsVirtualLeaf() const;
        /** Returns the stored distance to the near plane.
        */
        inline float GetDistance() const;
        /** Returns id of the first scene entity in the node.
        */
        inline int GetFirstEntity() const;
        /** Returns id of the last scene entity in the node.
        */
        inline int GetLastEntity() const;


        ////////////////
        //-- 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 frame id until this node is assumed visible
        */
        inline void SetAssumedVisibleFrameId(int t);
        /** See set.
        */
        inline int GetAssumedVisibleFrameId() const;
        /** Increases the #times this node was
                successfully tested invisible.
        */
        inline void IncTimesTestedInvisible();
        
        inline int GetTimesTestedInvisible() const;
        inline void SetTimesTestedInvisible(int t);
        
        inline int GetTurnedVisibleFrame() const;
        inline void SetTurnedVisibleFrame(int turnedVisibleFrame);

        inline int GetLastQueriedFrame() const;
        inline void SetLastQueriedFrame(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() const;
        /** Return index of this node.
        */
        inline int GetId() const;
        /** See get
        */
        inline void SetId(int 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;
        /** This function is important in case you have more than one
                view position within a frame (e.g., camera view and shadow view for
                shadow mapping), because each camera needs its own state in
                order to not break temporal coherency.
        */
        inline static void SetCurrentState(int _state);


protected:

        /// the depth of this node
        unsigned char mDepth;
        /// the split axis
        char mAxis;
        /// the parent node
        BvhNode *mParent;


        //////////////
        //-- members definig the current visibility state (one state per camera)

        /// the currently used state
        static int sCurrentState;

        /// stores the visibility related info 
        VisibilityInfo mVisibility[NUM_STATES];
        /// when the node was last rendered
        int mLastRenderedFrame[NUM_STATES];


        ///////////////
        //-- members that help to speed up view frustum culling

        /// masks out planes of the frustum that do not have to be tested against
        int mPlaneMask[NUM_STATES];
        /// the plane that is usually responsible for culling this node. 
        /** if our educated guess was right, we save up to 5 comparisons.
        */
        int mPreferredPlane[NUM_STATES];


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


        /// #leaves under this node
        int mNumLeaves;
        /// Area of this node
        float mArea;
        /// distance to the camera
        float mDistance;
        /// the index of this node
        unsigned int mId;
        /// the bounding box
        AxisAlignedBox3 mBox;
        /// if this node is a virtual leaf
        bool mIsVirtualLeaf;
        /** This marks the maximal depth where a virtual leaf can be defined.
            From this point on it makes no sense to traverse down further, as all
                nodes below contain the same geometry, so no further refinement of visibility 
                can be archieved. All nodes below this point can merely used to define the 
                tighter bounds.
        */
        bool mIsMaxDepthForVirtualLeaf;


        ////////////
        //-- rendering related options
        
        // 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;


        ////////////////
        //-- rendering related options

        /// we  query the bounding boxes of the test nodes when testing this node
        int mTestNodesIdx;
        /// the number of these test nodes
        int mNumTestNodes;
        /// used for efficient element array rendering
        int mIndicesPtr;
};



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

public:

        BvhInterior(BvhNode *parent);
        
        virtual bool IsLeaf() const;
        /** Back child.
        */
        inline BvhNode *GetBack();
        /** Front child.
        */
        inline BvhNode *GetFront();
        /** Recursivly delete hierarchy.
        */
        virtual ~BvhInterior();


protected:

        BvhNode *mBack;
        BvhNode *mFront;
};



class BvhLeaf: public BvhNode
{
        friend class Bvh;
        friend class BvhFactory;

public:

        BvhLeaf(BvhNode *parent);

        ~BvhLeaf();

        virtual bool IsLeaf() const;
};


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


typedef std::priority_queue<BvhNode *, std::vector<BvhNode *>, GtDistance> TraversalQueue;


/** Class representing a bounding volume hierarchy.
*/
class Bvh
{
        friend class BvhFactory;
        friend class BvhConstructor;
        friend class BvhExporter;

        /** Bvh properties
        */
        struct BvhStats
        {
                BvhStats() { Reset(); }

                void Reset() 
                {
                        mInteriorSA = .0f;
                        mLeafSA = .0f;
                        mInteriorVol = .0f;
                        mLeafVol = .0f;
                        mTriangleRatio = .0f;
                        mGeometryRatio = .0f;

                        mTriangles = 0;
                        mLeaves = 0;
                }

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

                float mInteriorSA;
                float mLeafSA;
                float mInteriorVol;
                float mLeafVol; 
                
                float mTriangleRatio;
                float mGeometryRatio;

                int mTriangles;
                int mLeaves;
        };

public:

        /** Destructor.
        */
        ~Bvh();
        /** Returns number of bvh nodes.
        */
        inline int GetNumNodes() const;
        /** Counts the number of nodes in this subtree
        */
        int CountNumNodes(BvhNode *node) const;
        /** Counts the number of virtual nodes in this subtree
        */
        int CountNumVirtualNodes(BvhNode *node) const;

        /** Returns number of bvh leaves.
        */
        inline int GetNumLeaves() const;
        /** Returns number of 'virtual' nodes in the hierarchy, i.e.
                the number of nodes actually used for traversal.
        */
        inline int GetNumVirtualNodes() const;
        /** Returns number of bvh leaves.
        */
        inline int GetNumVirtualLeaves() const;
        /** Returns root node of the bvh.
        */
        inline BvhNode *GetRoot();
        /** Returns the static root node of the bvh.
        */
        inline BvhNode *GetStaticRoot();
        /** Returns the dynamic root node of the bvh.
        */
        inline BvhNode *GetDynamicRoot();
        /** Returns the bounding box of this bvh.
        */
        inline const AxisAlignedBox3 &GetBox() const;
        /** Returns true if the current bvh node intersects the near plane.
        */
        bool IntersectsNearPlane(BvhNode *node) const; 


        ///////////////
        //-- functions collecting nodes based on some criteria

        /** Collect all child nodes in a given depth from the specified node.
        */
        void CollectNodes(BvhNode *node, BvhNodeContainer &nodes, int depth);
        /** Collect all child nodes.
        */
        void CollectNodes(BvhNode *node, BvhNodeContainer &nodes);
        /** Collect the "physical" leaves of the hierarchy
        */
        void CollectLeaves(BvhNode *node, BvhLeafContainer &leaves);
        /** Collect only the virtual leaves (can be anywhere in the hierarchy).
        */
        void CollectVirtualLeaves(BvhNode *node, BvhNodeContainer &leaves);


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

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


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

        /** Renders the bounds of this node 
            (the box of the node or the tigher bounds of some subnodes).
        */
        void RenderBounds(BvhNode *node, RenderState *state, bool useTightBounds);
        /** Renders bounding boxes of the collection of nodes.
                @returns #rendered boxes
        */
        int RenderBounds(const BvhNodeContainer &nodes, RenderState *state, bool useTightBounds);
        


        //////////////
        //-- 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, RenderState *state);
        /** Stores the orthogonal distance from the viewpoint to a point on the node.
                We choose the the nearest bounding box vertex . 
                Note that negative values can appear because culling is done only afterwards
        */
        void UpdateDistance(BvhNode *node) const;
        /** Returns the maximum distance from the near plane to this node.
        */
        float CalcMaxDistance(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();
        /** Counts the number of triangles contained in this node.
        */
        int CountTriangles(BvhNode *node) const;
        /** Returns area of the the node.
        */
        float GetArea(BvhNode *node) const;
        /** Compute unique ids for the nodes.
        */
        void ComputeIds();
        /** Assign virtual leaves based on specified number of triangles per leaf.
                That means that we try to set the leaves at a point where we
                have less than numTriangles triangles within this leaf and beyond.

                Virtual leaves are nodes that are determined to be the leaves
                of the hierarchy during render traversal. These nodes are not necessarily 
                the same as the real leaves of the hierarchy and can be anywhere
                in the hierarchy. 
                Please refer to the article for more info about virtual leaves
        */
        void SetVirtualLeaves(int numTriangles);
        

        ////////////
        //-- these functions determine the 'tightness' of the bounds that are used for querying


        /** Sets maximal depth for taking the bounding boxes to test the
                visibility of a node. 
                Deeper level means that the bounds adapt more to the geometry but
                also that more boxes are rendered
        */
        void SetMaxDepthForTestingChildren(int maxDepth);
        /** The ratio of area between node and subnodes where 
                testing the subnodes as proxy is still considered feasable
        */
        void SetAreaRatioThresholdForTestingChildren(float ratio);


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

        /** Returns statistics.
        */
        const BvhStats &GetBvhStats() const { return mBvhStats; }
        /** Render wireframe bvh for visualization purpose.
        */
        void RenderBoundsForViz(BvhNode *node, RenderState *state, bool useTightBounds);

        
protected:

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

        /** protected constructor: do nothing.
        */
        Bvh();
        /** Protected constructor taking scene geometry into account
                Sets the static and dynamic objects for the hierarchy.
        */
        Bvh(const SceneEntityContainer &staticEntities, 
            const SceneEntityContainer &dynamicEntities);
        /** Protected constructor taking scene geometry into account
                Sets the static and dynamic objects for the hierarchy.
        */
        Bvh(const SceneEntityContainer &staticEntities, 
            const SceneEntityContainer &dynamicEntities,
            int maxDepthForTestingChildren);
        /** Called by the constructor. Initializes important members.
        */
        void Init();


        /////////////
        /** Traverse hierarchy and compute stats.
        */
        void ComputeBvhStats(BvhNode *root, BvhStats &bvhStats);
        /** Output the bvh statistics.
        */
        void PrintBvhStats(const BvhStats &bvhStats, BvhNode *root) const;


        //////////
        //-- Helper methods for bounding box rendering in immediate and vbo mode.
        
        void PrepareVertices();
        /** Prepare nodes for vbo rendering.
        */
        int PrepareBoundsWithDrawArrays(const BvhNodeContainer &nodes);
        /** Render the nodes from the vbo prepared previously.
        */
        void RenderBoundsWithDrawArrays(int numNodes, RenderState *state);

        /** 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 nodes.
        */
        void PostProcess();
        /** Helper method that updates the number of leaves in the subtree under
                this node.
        */
        void UpdateNumLeaves(BvhNode *node) const;
        /** Frustum tests the ith plane.
        */
        inline bool TestPlane(BvhNode *node, int i, bool &bIntersect);
        /** Renders a bounding box in immediate mode.
        */
        void RenderBoundingBoxImmediate(const AxisAlignedBox3 &box);


        /////////////////////////////
        //-- functions used to construct the dynamic part of the hierarchy

        int SortTriangles(BvhLeaf *leaf, 
                              int axis, 
                                          float position);

        int SortTrianglesSpatialMedian(BvhLeaf *leaf, 
                                           int axis);

        BvhNode *SubdivideLeaf(BvhLeaf *leaf, 
                                   int parentAxis);
        /** Recompute the dynamic branch of the hierarchy.
        */
        void CreateDynamicBranch();

        void UpdateBoundingBoxes(BvhNode *node);

        inline bool TerminationCriteriaMet(BvhLeaf *leaf) const;

        void ComputeMaxDepthForVirtualLeaves();

        void CreateRoot();

        void UpdateDynamicBounds(RenderState *state);


        ////////////////////////
        
        /// the bounding box of the bvh
        AxisAlignedBox3 mBox;
        /// the root of the hierarchy
        BvhInterior *mRoot;
        /// the root of static part of the the hierarchy
        BvhNode *mStaticRoot;
        /// the root of dynamic part of the the hierarchy
        BvhNode *mDynamicRoot;
        /// pointers to the geometry associated with this node
        SceneEntity **mGeometry;
        /// #of entities
        size_t mGeometrySize;
        /// #of static entities
        size_t mStaticGeometrySize;
        /// #of dynamic entities
        size_t mDynamicGeometrySize;


        ////////////////
        //-- tigher bounds termination criteria

        /** maximal depth from which children are fetched for 
                testing instead of the current node
        */
        int mMaxDepthForTestingChildren;
        /// threshold for computing tighter bounds
        float mAreaRatioThreshold;
        
        
        ////////////////
        //-- statistics

        BvhStats mBvhStats;
        /// the overall number of nodes
        int mNumNodes;
        /// the number of "virtual" (=actually used) nodes
        int mNumVirtualNodes;


        ////////////
        //-- rendering stuff

        /// these proxy nodes are tested instead of the current node
        BvhNodeContainer mTestNodes;
        /// the indices used for vbo index buffering
        unsigned int *mTestIndices;
        /// a pointer to the end of the indices array
        int mCurrentIndicesPtr;
        /// the vbo id
        unsigned int mVboId;
        /// a vertex array used if working with indexed arrays (without vbo)
        Vector3 *mVertices;
        /// indices used for draw array rendering
        unsigned int *mIndices;


        ///////////
        //-- termination criteria for dynamic branch

        int mMaxDepthForDynamicBranch;

        //SceneEntityContainer mDynamicEntities;
};



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


inline int BvhNode::GetLastVisitedFrame() const 
{ 
        return mVisibility[sCurrentState].mLastVisitedFrame; 
}


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


inline bool BvhNode::IsVisible() const 
{ 
        return mVisibility[sCurrentState].mIsVisible; 
}


inline void BvhNode::SetVisible(bool visible) 
{ 
        mVisibility[sCurrentState].mIsVisible = visible; 
}


inline void BvhNode::IncTimesTestedInvisible() 
{ 
        ++ mVisibility[sCurrentState].mTimesInvisible; 
}


inline int BvhNode::GetTimesTestedInvisible() const 
{ 
        return mVisibility[sCurrentState].mTimesInvisible; 
}


inline void BvhNode::SetTimesTestedInvisible(int t) 
{ 
        mVisibility[sCurrentState].mTimesInvisible = t; 
}


inline bool BvhNode::IsViewFrustumCulled() const 
{ 
        return mVisibility[sCurrentState].mIsFrustumCulled; 
}


inline void BvhNode::SetViewFrustumCulled(bool frustumCulled) 
{ 
        mVisibility[sCurrentState].mIsFrustumCulled = frustumCulled; 
}


inline bool BvhNode::IsNew() const 
{ 
        return mVisibility[sCurrentState].mIsNew;
}


inline void BvhNode::SetIsNew(bool isNew) 
{ 
        mVisibility[sCurrentState].mIsNew = isNew; 
}


inline void BvhNode::SetAssumedVisibleFrameId(int t) 
{ 
        mVisibility[sCurrentState].mAssumedVisibleFrameId = t; 
}


inline int BvhNode::GetAssumedVisibleFrameId() const 
{ 
        return mVisibility[sCurrentState].mAssumedVisibleFrameId;
}


inline int BvhNode::GetLastQueriedFrame() const
{
        return mVisibility[sCurrentState].mLastQueriedFrame;
}


inline void BvhNode::SetLastQueriedFrame(int lastTested)
{
        mVisibility[sCurrentState].mLastQueriedFrame = lastTested;
}


inline int BvhNode::GetLastRenderedFrame() const 
{ 
        return mLastRenderedFrame[sCurrentState]; 
}
        

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


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

inline int BvhNode::GetDepth() const 
{ 
        return mDepth; 
}


inline BvhNode *BvhNode::GetParent() 
{ 
        return mParent; 
}


inline int BvhNode::GetNumLeaves() const
{
        return mNumLeaves;
}


inline bool BvhNode::IsVirtualLeaf() const
{ 
        return mIsVirtualLeaf; 
}


inline float BvhNode::GetDistance() const
{
        return mDistance; 
}

        
inline const AxisAlignedBox3 &BvhNode::GetBox() const
{
        return mBox; 
}


inline int BvhNode::GetId() const 
{
        return mId; 
}


inline void BvhNode::SetId(int id) 
{
        mId = id; 
}


inline void BvhNode::SetCurrentState(int _state) 
{
        sCurrentState = _state; 
}


inline int BvhNode::GetFirstEntity() const
{
        return mFirst;
}


inline int BvhNode::GetLastEntity() const
{
        return mLast;
}


inline BvhNode *BvhInterior::GetBack()
{
        return mBack; 
}


inline BvhNode *BvhInterior::GetFront() 
{ 
        return mFront; 
}



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

        
inline int Bvh::GetNumNodes() const
{
        return mNumNodes; 
}


inline int Bvh::GetNumLeaves() const 
{ 
        return mNumNodes / 2 + 1;
}


inline int Bvh::GetNumVirtualNodes() const  
{ 
        return mNumVirtualNodes; 
}


inline int Bvh::GetNumVirtualLeaves() const
{
        return mNumVirtualNodes / 2 + 1;
}


inline BvhNode *Bvh::GetRoot()
{ 
        return mRoot; 
}


inline BvhNode *Bvh::GetDynamicRoot()
{ 
        return mDynamicRoot; 
}


inline BvhNode *Bvh::GetStaticRoot()
{ 
        return mStaticRoot; 
}


inline const AxisAlignedBox3 &Bvh::GetBox() const 
{ 
        return mBox; 
}


}

#endif // __BVH_H