source: GTP/trunk/App/Demos/Vis/FriendlyCulling/src/CHCPlusPlusTraverser.cpp @ 3065

#include "CHCPlusPlusTraverser.h"
#include "RenderState.h"

using namespace std;

namespace CHCDemoEngine
{


CHCPlusPlusTraverser::CHCPlusPlusTraverser()
{
}


void CHCPlusPlusTraverser::HandleQueryResult(OcclusionQuery *query)
{
        // wait until result available
        const int visible = query->GetQueryResult() > mVisibilityThreshold;

        // multiquery
        if (query->GetSize() > 1)
        {
                // failed query: query individual nodes
                if (visible)
                {
                        for (size_t i = 0; i < query->GetSize(); ++ i)
                        {
                                BvhNode *node = query->GetNodes()[i];

                                mIQueue.push_back(node);
                                node->SetLastQueriedFrame(mFrameId);
                        }
                }
                else // query successful: update classifications
                {
                        for (size_t i = 0; i < query->GetSize(); ++ i)
                        {
                                BvhNode *node = query->GetNodes()[i];
                                node->IncTimesTestedInvisible();
                                node->SetVisible(false);
                                node->SetLastQueriedFrame(mFrameId);
                        }

                        mStats.mNumQueryCulledNodes += query->GetSize();
                }
        }
        else // single query
        {
                BvhNode *node = query->GetFrontNode();

                node->SetLastQueriedFrame(mFrameId);

                // failed query: query individual nodes
                if (visible)
                {
                        // node was previously invisible
                        if (!node->IsVisible())
                        {
                                // reset flag
                                node->SetTimesTestedInvisible(0);
                                node->SetAssumedVisibleFrameId(mFrameId + mAssumedVisibleFrames);
                        }
                        else
                        {       // randomize first invokation
                                node->SetAssumedVisibleFrameId(mFrameId + Random(mAssumedVisibleFrames + 1));
                        }

                        mBvh->MakeParentsVisible(node);
                        TraverseNode(node);
                }
                else
                {
                        node->IncTimesTestedInvisible();
                        ++ mStats.mNumQueryCulledNodes;
                }

                node->SetVisible(visible);
        }
}


void CHCPlusPlusTraverser::Traverse()
{
        int waitedForQueries = 0;
        int returnedQueries = 0;

        //-- PART 1: process finished occlusion queries
        while (!mDistanceQueue.empty() || !mQueryQueue.empty())
        {
                bool resultAvailable = false;

                while (!mQueryQueue.empty() && 
                           (mDistanceQueue.empty() || (resultAvailable = mQueryQueue.front()->ResultAvailable())))
                {
                        while (!resultAvailable && !mVQueue.empty())
                        {
                                BvhNode *node = mVQueue.front();
                                mVQueue.pop();
                                
                                OcclusionQuery *query = IssueOcclusionQuery(node);

                                mQueryQueue.push(query);
                                resultAvailable = mQueryQueue.front()->ResultAvailable();
                        }
                        
                        //++ returnedQueries; if (!resultAvailable) ++ waitedForQueries;
                        
                        OcclusionQuery *query = mQueryQueue.front();
                        mQueryQueue.pop();

                        // waiting for query result
                        HandleQueryResult(query);
                }       

                //-- PART 2: hierarchical traversal
                if (!mDistanceQueue.empty())
                {
                        BvhNode *node = mDistanceQueue.top();
                        mDistanceQueue.pop();
        
                        if (mBvh->IsWithinViewFrustum(node))
                        {
                                // for near plane intersecting bounding box possible 
                                // wrong results => skip occlusion query
                                if (mBvh->IntersectsNearPlane(node))
                                {
                                        // update node's visited flag
                                        node->SetLastVisitedFrame(mFrameId);
                                        node->SetVisible(true);
                                        mBvh->MakeParentsVisible(node);

                                        TraverseNode(node);
                                }
                                else
                                {               
                                        // identify previously visible nodes
                                        const bool wasVisible = node->IsVisible() && (node->GetLastVisitedFrame() == mFrameId - 1);
                                        
                                        // identify nodes that we cannot skip queries for
                                        const bool queryFeasible = (!wasVisible || (node->IsVirtualLeaf() && 
                                                (node->GetAssumedVisibleFrameId() <= mFrameId)));

                                        // node was not recently tested => reset flag 
                                        if (node->GetLastVisitedFrame() != mFrameId - 1)
                                                node->SetTimesTestedInvisible(0);

                                        // update node's visited flag
                                        node->SetLastVisitedFrame(mFrameId);
                                        
                                        // skip testing previously visible interior nodes
                                        if (queryFeasible)
                                        {
                                                if (!wasVisible)
                                                {
                                                        QueryPreviouslyInvisibleNodes(node);
                                                }
                                                else
                                                {
                                                        mVQueue.push(node);
                                                }
                                        }
                                        else
                                        {
                                                if (node->IsVirtualLeaf())
                                                {
                                                        node->SetVisible(true);
                                                        mBvh->MakeParentsVisible(node);
                                                } 
                                                else // reset visibility classification
                                                {
                                                        node->SetVisible(false);
                                                }
                                        }
                                        
                                        // always traverse a node if it was previously visible
                                        if (wasVisible)
                                                TraverseNode(node);
                                }
                        }
                        else
                        {
                                // for stats
                                ++ mStats.mNumFrustumCulledNodes;
                        }
                }

                // distance queue empty: feed the remaining multiqueries to
                // be able to proceed traversal
                if (mDistanceQueue.empty())
                {
                        IssueMultiQueries();
                }
        }

        // render the rest of the objects
        if (mUseRenderQueue) ApplyRenderQueue();


        //////////////
        //-- issue remaining previously visible node queries

        while (!mVQueue.empty())
        {
                BvhNode *node = mVQueue.front();
                mVQueue.pop();

                OcclusionQuery *query = IssueOcclusionQuery(node);
                mQueryQueue.push(query);
        }

        while (!mQueryQueue.empty())
        {
                OcclusionQuery *query = mQueryQueue.front();
                mQueryQueue.pop();

                HandleQueryResult(query);
        }

        //cout << "returned queries: " << returnedQueries << " waited for queries: " << waitedForQueries << " (=" << 100.0f * waitedForQueries / returnedQueries << "%)" << endl;
}


void CHCPlusPlusTraverser::QueryPreviouslyInvisibleNodes(BvhNode *node)
{
        mIQueue.push_back(node);

        if (mIQueue.size() > mMaxBatchSize)
        {
                IssueMultiQueries();
        }
}


OcclusionQuery * CHCPlusPlusTraverser::GetNextMultiQuery(BvhNodeContainer &iqueue)
{
        OcclusionQuery *query = mQueryHandler.RequestQuery();

        float pFail = 1.0f; 
        float maxBatchVal = 0.0f;
        float newPBatch = 1.0f;
        float newBatchVal;

        // issue next query
        while (!iqueue.empty())
        {
                BvhNode *node = iqueue.back();

                // node was already part of a mulitquery => avoid recursion
                if (node->GetLastQueriedFrame() == mFrameId)
                        newPBatch = 0;
                else
                newPBatch *= mVisibilityPredictor.GetProbability(node);

                if (query->GetNodes().empty())
                {
                        // single node will never cause a wasted query
                        newBatchVal = 1.0f;
                }
                else
                {
                        int newSize = query->GetSize() + 1;
                        newBatchVal = newSize / (1.0f + (1.0f - newPBatch) * newSize);
                }

                if (newBatchVal <= maxBatchVal)
                        break;

                iqueue.pop_back();
                query->AddNode(node);

                maxBatchVal = newBatchVal;
        }

        //cout <<"size: " << query->GetSize() << endl;
        IssueOcclusionQuery(*query);

        return query;
}


static inline bool lt(BvhNode *a, BvhNode *b)
{
        return a->GetTimesTestedInvisible() < b->GetTimesTestedInvisible();
}


void CHCPlusPlusTraverser::IssueMultiQueries()
{
        if (mUseMultiQueries)
        {
                // sort queries by #times invisible
                sort(mIQueue.begin(), mIQueue.end(), lt);

                while (!mIQueue.empty())
                        mQueryQueue.push(GetNextMultiQuery(mIQueue));
        }
        else
        {
                BvhNodeContainer::const_iterator it, it_end = mIQueue.end();

                for (it = mIQueue.begin(); it != it_end; ++ it)
                        mQueryQueue.push(IssueOcclusionQuery(*it));

                mIQueue.clear();
        }
}


}