source: GTP/trunk/Lib/Vis/OnlineCullingCHC/src/CoherentHierarchicalCullingPlusPlusManager.cpp @ 2561

#include "CoherentHierarchicalCullingPlusPlusManager.h"
#include "CullingLogManager.h"

#include <time.h>
#include <sstream>



namespace GtpVisibility {


static const bool CULL_INVALID_NODES = true;
//static const bool CULL_INVALID_NODES = false;
static const int MAX_INVISIBLE_NODES_SIZE = 20;

//-----------------------------------------------------------------------
CoherentHierarchicalCullingPlusPlusManager::CoherentHierarchicalCullingPlusPlusManager():
mAssumedVisibility(0), mMaxInvisibleNodesSize(MAX_INVISIBLE_NODES_SIZE)
{
}
//-----------------------------------------------------------------------
CoherentHierarchicalCullingPlusPlusManager::CoherentHierarchicalCullingPlusPlusManager(
                                                                                                                const unsigned int assumedVisibility):
mAssumedVisibility(assumedVisibility), mMaxInvisibleNodesSize(MAX_INVISIBLE_NODES_SIZE)
{
}
//-----------------------------------------------------------------------
void CoherentHierarchicalCullingPlusPlusManager::AssignAssumedVisibility(GtpVisibility::HierarchyNode *node)
{
        if (!mHierarchyInterface->IsNodeVisible(node))
                // previously invisible nodes: give random offset just for the first test after
                // becoming visible to avoid that all nodes are tested in the same frame
                mHierarchyInterface->SetNodeAssumedVisible(node, rand() * mAssumedVisibility / RAND_MAX);
        else
                mHierarchyInterface->SetNodeAssumedVisible(node, mAssumedVisibility);
}
//-----------------------------------------------------------------------
void CoherentHierarchicalCullingPlusPlusManager::RenderScene()
{
        if (0) CullingLogManager::GetSingleton()->LogMessage("chc++");
        
        unsigned int visiblePixels = 0;

        /////////////
        //-- PART 1: process finished occlusion queries

        while (!mHierarchyInterface->GetQueue()->empty() || !mQueryQueue.empty()
                   || !mInvisibleNodes.empty() 
                   //|| !mVisibleNodes.empty()
                   )
        {
                //////////
                //-- only wait for result if there are no nodes to process
                bool resultAvailable = false;

                while (
                           !mQueryQueue.empty() && 
                           (NodeInvalid(mQueryQueue.front().first) ||
                           mHierarchyInterface->GetQueue()->empty() ||
                           (resultAvailable = mQueryQueue.front().second->GetQueryResult(visiblePixels, false)))
                           )
                {
                        HierarchyNode *node = mQueryQueue.front().first;

                        // parent was tested invisible => remove children from queue
                        // "invalid nodes" happen for hierarchies where interiors store geometry
                        if (NodeInvalid(node)) {mQueryQueue.pop(); continue;}

                        // during the wait time we issue nodes from visible queue
                        while (!mVisibleNodes.empty() && !resultAvailable)
                        {
                                HierarchyNode *vn = mVisibleNodes.front();
                                mVisibleNodes.pop();
                                IssueQuery(vn, false);

                                // check if result is already availalbe
                                resultAvailable = mQueryQueue.front().second->GetQueryResult(visiblePixels, false);
                        }

                        if (!resultAvailable)
                                mQueryQueue.front().second->GetQueryResult(visiblePixels, true);

                        resultAvailable = false;
                mQueryQueue.pop();

                        // tested visible
                        if (visiblePixels > mVisibilityThreshold)
                        {
                                // assing the #frames the node is assumed to stay visible
                                AssignAssumedVisibility(node);

                                // traverse node if not already traversed in this frame 
                                // (i.e., the visible flag is not set)
                                // note: it is necessary to do this test because we query
                                // previously visible interior node containing geometry without
                                // waiting for the result
                                if (!mHierarchyInterface->IsNodeVisible(node))
                                        mHierarchyInterface->TraverseNode2(node);

                                mHierarchyInterface->PullUpVisibility(node);
                        }
                        else
                        {       
                                mHierarchyInterface->SetNodeVisible(node, false);

                                ++ mNumQueryCulledNodes;
                                
                                if (mVisualizeCulledNodes)
                                        mHierarchyInterface->VisualizeCulledNode(node, QUERY_CULLED);
                        }
                        
                        // update node's visited flag
                        mHierarchyInterface->SetLastVisited(node, mHierarchyInterface->GetFrameId());   
                }
                
                ////////////////
                //-- PART 2: hierarchical traversal

                if (!mHierarchyInterface->GetQueue()->empty())
                {
                        HierarchyNode *node = mHierarchyInterface->GetQueue()->top();
                        mHierarchyInterface->GetQueue()->pop();
                                
                        // parent was tested invisible => remove children from queue
                        if (NodeInvalid(node)) continue;

                        bool intersects = false;

                        if (!mHierarchyInterface->CheckFrustumVisible(node, intersects))
                        {
                                ++ mNumFrustumCulledNodes;
                                
                                if (mVisualizeCulledNodes)
                                        mHierarchyInterface->VisualizeCulledNode(node, FRUSTUM_CULLED);
                        }
                        else if (intersects)
                        {
                                //-- if node intersects near plane, skip query because wrong results possible
                                SkipQuery(node);
                        }
                        else
                        {
                                // identify previously visible nodes
                                bool wasVisible = mHierarchyInterface->IsNodeVisible(node) && 
                                        (mHierarchyInterface->LastVisited(node) == mHierarchyInterface->GetFrameId() - 1);
                                
                                // if we assume node to be visible in this frame => skip query 
                                const bool skipQuery = wasVisible &&
                                                                           DecideVisible(node) && 
                                                                           mHierarchyInterface->HasGeometry(node);

                                if (skipQuery)
                                {
                                        SkipQuery(node);
                                        continue;
                                }

                // identify nodes that we cannot skip queries for
                                // geometry not only in leaves => test for renderable geometry
                                const bool issueQuery = !wasVisible || mHierarchyInterface->HasGeometry(node);
                                                        
                                // set node's visibility classification
                                // we identify previously visible / invisible nodes in the query queue
                                mHierarchyInterface->SetNodeVisible(node, wasVisible && issueQuery);

                                if (issueQuery)
                                {
                                        ++ mNumQueriesIssued;

                                        if (!wasVisible)
                                        {
                                                mInvisibleNodes.push_back(node);

                                                if ((int)mInvisibleNodes.size() >= mMaxInvisibleNodesSize)
                                                {
                                                        mHierarchyInterface->RenderQueue();
                                                        // issue the batched queries
                                                        IssueBatchedQuery(mInvisibleNodes);
                                                }
                                        }
                                        else
                                        {
                                                // mVisibleNodes.push(node);
                                                IssueQuery(node, false);
                                        }
                                }
                                else
                                {
                                        // skip testing previously visible nodes without geometry
                    // just update node's visited flag
                                        mHierarchyInterface->SetLastVisited(node, mHierarchyInterface->GetFrameId());
                                }
                                
                                // always traverse a node if it was visible
                                if (wasVisible)
                                {
                                        mHierarchyInterface->TraverseNode2(node);
                                }
                        }
                }

                  // issue rest of nodes from nodes from invisible queue
                if (mHierarchyInterface->GetQueue()->empty() && !mInvisibleNodes.empty())
                {
                        if (0)
                        {
                                std::stringstream d;
                                d << "inv nodes: " << (int)mInvisibleNodes.size();
                                CullingLogManager::GetSingleton()->LogMessage(d.str());
                        }
                        
                        mHierarchyInterface->RenderQueue();
                        IssueBatchedQuery(mInvisibleNodes);
                }

        // issue rest of nodes from nodes from visible queue
                if (0 && 
                        mHierarchyInterface->GetQueue()->empty() && mQueryQueue.empty() && !mVisibleNodes.empty())
                {
                        while (!mVisibleNodes.empty())
                        {
                                IssueQuery(mVisibleNodes.front(), false);
                                mVisibleNodes.pop();
                        }
                }
        }
        
    // render what is left in the render queue
        mHierarchyInterface->RenderQueue();

        // issue rest of nodes from nodes from visible queue
        while (!mVisibleNodes.empty())
        {
                IssueQuery(mVisibleNodes.front(), false);
                mVisibleNodes.pop();
        }

        int i = 0;

        while (!mQueryQueue.empty() && 
                    mQueryQueue.front().second->GetQueryResult(visiblePixels, true))
        {
                ++ i;

                HierarchyNode *node = mQueryQueue.front().first;
                mQueryQueue.pop();

                // tested visible
                if (visiblePixels > mVisibilityThreshold)
                {
                        // assing the #frames the node is assumed to stay visible
                        AssignAssumedVisibility(node);
                        mHierarchyInterface->PullUpVisibility(node);
                }
                else
                {       
                        mHierarchyInterface->SetNodeVisible(node, false);

                        ++ mNumQueryCulledNodes;

                        if (mVisualizeCulledNodes)
                                mHierarchyInterface->VisualizeCulledNode(node, QUERY_CULLED);
                }

                // update node's visited flag
                mHierarchyInterface->SetLastVisited(node, mHierarchyInterface->GetFrameId());   
        }
}
//-----------------------------------------------------------------------
void CoherentHierarchicalCullingPlusPlusManager::SetAssumedVisibility(const unsigned int assumedVisibility)
{
        mAssumedVisibility = assumedVisibility;
}
//-----------------------------------------------------------------------
inline bool CoherentHierarchicalCullingPlusPlusManager::DecideVisible(HierarchyNode *node) const
{
        mHierarchyInterface->DecNodeAssumedVisible(node);
        //std::stringstream d; d << "node visible: " << mHierarchyInterface->GetNodeAssumedVisible(node);
        //CullingLogManager::GetSingleton()->LogMessage(d.str());
        return mHierarchyInterface->GetNodeAssumedVisible(node) > 0;
}
//-----------------------------------------------------------------------
inline void CoherentHierarchicalCullingPlusPlusManager::SkipQuery(HierarchyNode *node) const
{
        //-- set node to be visible in this frame, then traverse it
        mHierarchyInterface->SetLastVisited(node, mHierarchyInterface->GetFrameId());

        mHierarchyInterface->PullUpVisibility(node);                    
        mHierarchyInterface->TraverseNode2(node);
}
//-----------------------------------------------------------------------
inline bool CoherentHierarchicalCullingPlusPlusManager::NodeInvalid(HierarchyNode *node) const
{
        if (!CULL_INVALID_NODES) return false;

        // parent was tested invisible in this frame
    const bool nodeInvalid = ( 
                 mHierarchyInterface->GetParent(node) && 
                 (mHierarchyInterface->LastVisited(node) == mHierarchyInterface->GetFrameId()) && 
                 !mHierarchyInterface->IsNodeVisible(mHierarchyInterface->GetParent(node))
         );

        return nodeInvalid;
}
//-----------------------------------------------------------------------
void CoherentHierarchicalCullingPlusPlusManager::SetTestGeometryForVisibleLeaves(const bool testGeometry)
{
        mTestGeometryForVisibleLeaves = testGeometry;
}
//-----------------------------------------------------------------------
bool CoherentHierarchicalCullingPlusPlusManager::GetTestGeometryForVisibleLeaves()
{
        return mTestGeometryForVisibleLeaves;
}
//-----------------------------------------------------------------------
inline void CoherentHierarchicalCullingPlusPlusManager::IssueQuery(HierarchyNode *node, 
                                                                                                                                   const bool queryGeometry)
{
        mQueryQueue.push(QueryPair(node, mHierarchyInterface->
                IssueNodeOcclusionQuery(node, queryGeometry)));
}
//-----------------------------------------------------------------------
void CoherentHierarchicalCullingPlusPlusManager::IssueBatchedQuery(HierarchyNodeContainer &nodes)
{
        HierarchyNodeContainer::const_iterator nit, nit_end = nodes.end();

        for (nit = nodes.begin(); nit != nit_end; ++ nit)
                IssueQuery(*nit, false);

        //for (int i = (int)nodes.size() - 1; i >= 0; -- i)
        //      IssueQuery(nodes[i], false);

        nodes.clear();
}
//-----------------------------------------------------------------------
#if 0
void CoherentHierarchicalCullingPlusPlusManager::IssueOptimalBatches(QueryHeap &nodes)
{
        while (!nodes.Empty())
        {       
                QueryQueueEntry *entry = GetNextQueryQueueEntry();
                entry->mIsVisibleQuery = false;
        
                float pFail = 1.0f; 
                float maxBatchVal = 0.0f;
                float newPBatch = 1.0f;
                float newBatchVal;
                
                // issue next query
                while (!nodes.Empty())
                {
                        HierarchyNode *node = nodes.Top();
        
                        newPBatch *= mNodePredictor.GetProbability(node);

                        if (entry->mNodes.empty())
                                newBatchVal = 1.0f;
                        else
                        {
                                const float newSize = float(entry->mNodes.size() + 1);
                                newBatchVal = newSize / (1.0f + (1.0f - newPBatch) * newSize);
                        }

                        if (newBatchVal <= maxBatchVal)
                                break;

                        pFail = entry->mNodes.empty() ? 0.0f : (1.0f - newPBatch);

                        nodes.Pop();
                        entry->AddNode(node);

                        maxBatchVal = newBatchVal;
                }

                entry->mPFail = pFail;

                IssueQuery(*entry, false);
                mQueries.push(entry);
        }
}
#endif
}