#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
}