#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 (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();
	}
}


}