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

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

#ifndef __BVH_H
#define __BVH_H

#if TOIMPLEMENT

#include "Bounds.h"
#include "PerfTimer.h"
#include "NV_RenderPredictorRenderAction.h"
#include "VisibilityPredictor.h"
#include "HierarchyNode.h"
#include "FlexibleHeap.h"


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

class Scene;
class Node;
class Camera;
class Box;
class BvhLeaf;
class BvhNode;
class TriangleBvh;



/** A node in the bv hierarchy.
*/
class BvhNode: public RenderableHierarchyNode, public Heapable
{
        friend class Bvh;

public:

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


                /// if the node is visible
                bool mIsVisible;
                /// if all the leaves are visible
                bool mIsFullyVisible;
                
                /// #pixels this node was visible for the last test
                int mVisiblePixels;             
                /// #frames this node is assumed to stay visible
                int mAssumedVisibleFrames;
                /// #frames this node is assumed to stay visible
                int mRemainingVisibleFrames;
                
                /// the frame in which the node was last tested visible
                int mLastTestedVisibleFrame;
                /// the frame when this node was last touched during traversal
                int mLastVisitedFrame;
                /// frame id when the node turned visible
                int mTurnedVisibleFrame;
                /// when was the node last tested
                int mLastTestedFrame;

                /// #times this node was invisible (only valid if the node actually is invisible)
                int mTimesInvisible;
                /// #times this node was tested
                int mTimesTested;
                /// #times this node was tested
                int mTimesChangedClassification;
                /// The ratio of classification changes / tests
                float mAvgChangedClassification;
                
                /// if the node is view frustum culled
                bool mIsFrustumCulled;

                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 (int)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;}
        /** Box used for visualization.
        */
        Box *GetOrCreateVizBox();
        /** Reset the status of this node.
        */
        virtual void ResetVisibility();

        virtual int GetType() { 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);
        /** See set.
        */
        inline int GetRemainingVisibleFrames() const;
        /** Decrease the time this node is considered visible.
        */
        inline void DecRemainingVisibleFrames();
        /** Returns the frame id when this node was tested
                visible.
        */
        inline void SetLastTestedVisibleFrame(const int t);
        /** See set.
        */
        inline int GetLastTestedVisibleFrame() const;
        /** Increases the #times this node was
                successfully tested invisible.
        */
        inline void IncTimesInvisible();
        /** If the subtree induced by this node
                is fully visible.
        */
        inline bool IsFullyVisible();

        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 void SetVisiblePixels(const int pixels);
        inline int GetVisiblePixels();

        inline void IncTimesTested();
        inline void IncTimesChangedClassficiation();

        inline int GetTimesTested();
        inline int GetTimesChangedClassification();
        
        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;


        ///////////////
        //-- public stuff

        /// Visibility measurements for the period this node was visible
        VisibilityMeasurementBuffer mMeasurements;
        /// some flags
        int mFlags;

        //int mNumFailedTests;

protected:

        /** Marks the subtree induced by this node
                as fully visible.
        */
        inline void SetFullyVisible(const bool visible);


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

        /// 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 traingle 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::SetLastTestedVisibleFrame(const int t) 
{ 
        mVisibility.mLastTestedVisibleFrame = t; 
}


int BvhNode::GetLastTestedVisibleFrame() const 
{ 
        return mVisibility.mLastTestedVisibleFrame; 
}


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


bool BvhNode::IsFullyVisible() 
{ 
        return mVisibility.mIsFullyVisible; 
}


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


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


int BvhNode::GetTurnedVisibleFrame() const 
{ 
        return mVisibility.mTurnedVisibleFrame; 
}


void BvhNode::SetTurnedVisibleFrame(const int turnedVisibleFrame) 
{ 
        mVisibility.mTurnedVisibleFrame = turnedVisibleFrame; 
}


int BvhNode::GetLastTestedFrame() 
{ 
        return mVisibility.mLastTestedFrame; 
}


void BvhNode::SetLastTestedFrame(const int lastTested)
{ 
        mVisibility.mLastTestedFrame = lastTested; 
}


void BvhNode::SetVisiblePixels(const int pixels)
{ 
        mVisibility.mVisiblePixels = pixels; 
}


int BvhNode::GetVisiblePixels() 
{
        return mVisibility.mVisiblePixels;
}


void BvhNode::IncTimesTested() 
{ 
        ++ mVisibility.mTimesTested; 
}


void BvhNode::IncTimesChangedClassficiation() 
{ 
        ++ mVisibility.mTimesChangedClassification; 
}


int BvhNode::GetTimesTested() 
{ 
        return mVisibility.mTimesTested; 
}


int BvhNode::GetTimesChangedClassification() 
{ 
        return mVisibility.mTimesChangedClassification; 
}


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::SetRemainingVisibleFrames(const int t) 
{ 
        mVisibility.mRemainingVisibleFrames = t; 
}


int BvhNode::GetRemainingVisibleFrames() const 
{ 
        return mVisibility.mRemainingVisibleFrames;
}


void BvhNode::DecRemainingVisibleFrames() 
{
        -- mVisibility.mRemainingVisibleFrames; 
}



/** 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), mTriangleBvh(NULL)
        {}

        ~BvhLeaf();

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


struct NodeGeometry
{
        virtual AxisAlignedBox3 GetBoundingBox() = 0;
};


struct ObjectGeometry
{
        virtual AxisAlignedBox3 GetBoundingBox() = 0;
};


struct TriangleGeometry
{
        virtual AxisAlignedBox3 GetBoundingBox() = 0;
};


/** 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).
        */
        NodeGeometry **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, Viewer *viewer);
        /** this gives the orthogonal distance from the viewpoint to the nearest BBox-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);
        /** Resize the visibility buffers of the bvh nodes.
        */
        void ResizeVisibilityBuffers(const int size);

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

        void SetVolRatioThresholdForTestingChildren(const float ratio);
        /** Returns depth of bvh hierarchy.
        */
        float GetAvgDepth() const;


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

        void SetCollectTighterBoundsWithMaxLevel(bool t);


        /////////////
        //-- timers

        mutable PerfTimer timeSetup;
        mutable PerfTimer timeIssueDrawElements;
        mutable PerfTimer timeViewFrustumCulling;
        mutable PerfTimer timeDistance;

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

        static unsigned int sCurrentVboId;
        

protected:

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


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

        /** Constructor taking the geometry and a pointer to the current render action.
        */
        Bvh(const GeometryVector &geometry, 
                DistanceSortedRenderAction *const renderer);
        /** protected constructor: do nothing.
        */
        Bvh(): mCamera(NULL), mFrameId(-1), mVertices(NULL), mRenderer(NULL) {}
        /** Destructor.
        */
        ~Bvh();



        //-- sorting functions

        /** The method of subdividing objects into halves in some axis using spatial median
        */
        int     SortTrianglesSpatialMedian(BvhLeaf *leaf, const int axis);
        /** The method of subdividing objects into halves in some axis
                using object median.
        */
        int     SortTrianglesObjectMedian(BvhLeaf *leaf, const int axis, float &pos);
        /** sort triangles along the axis with respect to the splitting plane 
                given by axis/position return index of the first tiangles belong 
                to the front of the splitting plane.
        */
        int     SortTriangles(BvhLeaf *leaf, const int axis, const float position);
        /** sort triangles by their area.
        */
        int SortTrianglesSurfaceArea(BvhLeaf *leaf, const float sa);


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


        /** Subdivides the current leaf.
        */
        BvhNode *SubdivideLeaf(BvhLeaf *leaf, const int parentAxis);    
        /** select splitting plane using SAH - returns the position of the splitting plane.
        */
        float SelectPlaneSah(BvhLeaf *leaf, int &axis, float &minCost);
        /** evaluate the SAH cost of a particulkar splitting plane
        */
        float EvaluateSahCost(BvhLeaf *leaf, const int axis, const float position);

        void ComputeBvhStats();
        void PrintBvhStats() const;

        /** Update children nodes recursively.
        */
        void UpdateBoxes(BvhNode *node);
        /** Update box for a leaf node
        */
        void UpdateLeafBox(BvhLeaf *leaf);
        /** Returns true if termination criteria met.
        */
        bool TerminationCriteriaMet(BvhLeaf *leaf) const;
        /** Compute unique ids for the bvh nodes.
        */
        void ComputeIds();
        /** Helper method that updates the number of leaves in the subtree under
                this node.
        */
        void UpdateNumLeaves(BvhNode *node) const;


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

        int PrepareBoundingBoxesWithDrawArrays(const BvhNodeContainer &nodes);
        void RenderBoundingBoxesWithDrawArrays(const 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 BoundingBox &box, const 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);

        bool CreateTighterBoundsForLeaf(BvhLeaf *leaf, Point3f *triangles, const int triangleCount);

        Point3f *CollectTriangles(BvhLeaf *leaf, int &triangleCount);

        int     IsWithinViewFrustumLocal(BvhNode *node);

        int     IsWithinViewFrustum(const BoundingBox &box, const int planeMask, const int preferredPlane);
        /** Compute screen space projection of a bounding box.
        */
        float ComputeScreenSpaceProjection(const BoundingBox &box) const;

        float GetMinSquareDistance(const BoundingBox &box) const;
        /** Computes the area of the triangles in a leaf.
        */
        float ComputeGeometryArea(BvhLeaf *leaf, Point3f *triangles, const int triangleCount) const;


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

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


        /////////
        //-- termination criteria

        int mMaxGeometry;
        int mMaxTriangles;
        int mSplitType;
        int mNumNodes;
        int mMaxDepth;
        float mMinArea;

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


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

        /// pointer to the renderaction
        DistanceSortedRenderAction *const mRenderer;

        BvhStats mBvhStats;

        HierarchyNodeContainer mTestNodes;
        
        unsigned int *mTestIndices;

        /// a pointer to the end of the indices array
        int mCurrentIndicesPtr;

        float mScale;

        float mAvgDepth;

        Vector3f mNearPlane;
        float mNearPlaneD;
};

#endif
#endif // __BVH_H