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

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

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);
        /** Returns true if this node is a leaf.
        */
        //virtual bool IsPseudoLeaf() = 0;
        /** Virtual destructor doing nothing.
        */
        virtual ~BvhNode();
        /** 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() const = 0;

        bool IsVirtualLeaf() const { return mIsVirtualLeaf; }

        /** Returns the stored distance to the near plane.
        */
        float GetDistance() const  { return mDistance; }


        ////////////////
        //-- 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() { 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;
        /** This is an imporantent function once you have one or more
                view point changes 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.
        */
        static void SetCurrentState(int _state) { sCurrentState = _state; }


protected:

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


        //////////////
        //-- members that define the current state. There is one state for each camera

        /// the currently used state
        static int sCurrentState;

        /// stores the visibility related info 
        VisibilityInfo mVisibility[NUM_STATES];
        
        // members used 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];
        /// when the node was last rendered
        int mLastRenderedFrame[NUM_STATES];

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


        /// #leaves under this node
        int mNumLeaves;


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

        /// the bounding boxes of these nodes are queries instead of the current node
        int mTestNodesIdx;
        /// the number of tighter bounding volumes used for this node
        int mNumTestNodes;
        /// used for efficient element array rendering
        int mIndicesPtr;

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



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


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


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


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


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


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


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


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


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


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


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


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


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


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


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


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


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

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


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





/** 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() const { return false; }
        /** Back child.
        */
        inline BvhNode *GetBack() { return mBack; }
        /** Front child.
        */
        inline BvhNode *GetFront() { return mFront; }
        /** Recursivly delete hierarchy.
        */
        virtual ~BvhInterior();

protected:

        BvhNode *mBack;
        BvhNode *mFront;
};


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

public:

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

        ~BvhLeaf();

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


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

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


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

        /** Bvh properties
        */
        struct BvhStats
        {
                BvhStats(): 
                mInteriorSA(0),
                mLeafSA(0),
                mInteriorVol(0),
                mLeafVol(0),
                mTriangles(0),
                mTriangleRatio(0),
                mGeometryRatio(0),
                mMaxGeometry(0),
                mMaxTriangles(0)
                {}
                
                float mInteriorSA;
                float mLeafSA;
                float mInteriorVol;
                float mLeafVol; 
                
                int mTriangles;

                float mTriangleRatio;
                float mGeometryRatio;

                int mMaxGeometry;
                int mMaxTriangles;
        };

public:

        /** Destructor.
        */
        ~Bvh();
        /** 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 number of 'virtual' nodes in the hierarchy, i.e.
                the number of nodes actually used for traversal.
        */
        int GetNumVirtualNodes() const  { return mNumVirtualNodes; }
        /** Returns number of bvh leaves.
        */
        inline int GetNumVirtualLeaves() const { return mNumVirtualNodes / 2 + 1;}
        /** Returns root node of the bvh.
        */
        BvhNode *GetRoot() { return mRoot; }
        /** Sets the scene camera
        */
        //void SetCamera(Camera * camera) { mCamera = camera; }

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

        void CollectNodes(BvhNode *node, BvhNodeContainer &nodes, int depth);
        void CollectNodes(BvhNode *node, BvhNodeContainer &nodes);
        void CollectLeaves(BvhNode *node, BvhLeafContainer &leaves);
        /** Collect only the virtual leaves.
        */
        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);
        /** Returns the bounding box of this bvh.
        */
        inline const AxisAlignedBox3 &GetBox() { return mBox; }


        //////////////
        //-- 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);
        /** 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();
        /** 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 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.
        */
        void SetVirtualLeaves(int numTriangles);
        

        ////////
        //-- 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; }
        /** 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
        */
        const Bvh(const SceneEntityContainer &entities);
        /** Called by the constructor. Initializes important members.
        */
        void Init();

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

        void ComputeBvhStats();
        void PrintBvhStats() const;


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

        int PrepareBoundsWithDrawArrays(const BvhNodeContainer &nodes);
        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);


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

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

        int SortTrianglesSpatialMedian(BvhLeaf *leaf, 
                                           int axis,
                                                                   SceneEntityContainer &entities);

        BvhNode *SubdivideLeaf(BvhLeaf *leaf, 
                                   int parentAxis, 
                                                   SceneEntityContainer &entities);

        /** Recompute the dynamic branch of the hierarchy.
        */
        void UpdateDynamicBranch();

        inline bool TerminationCriteriaMet(BvhLeaf *leaf) const;


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


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

}

#endif // __BVH_H