#include "stdafx.h"
#include "SceneTree.h"

#include "Ray.h"
#include "SceneNode.h"

tPool<cSceneTreeNode> cSceneTreeNode::mPool( 2048, 256 );
cSceneCuller* cSceneTreeNode::mCuller = 0;

cSceneTreeNode::cSceneTreeNode( cSceneTree* tree, cSceneTreeNode* parent, const NiPoint3& center, float radius )
: cSphere( center, radius )
, mTree( tree )
, mParent( parent )
{
	mChild[0] = mChild[1] = mChild[2] = mChild[3] = 0;

	float d = ( radius / 1.4142135623731f ) * 0.5f;
	float r = radius * 0.55f;

	mTestSpheres[0].Set( center.x - d, center.y - d, 0.0f, r );
	mTestSpheres[1].Set( center.x + d, center.y - d, 0.0f, r );
	mTestSpheres[2].Set( center.x - d, center.y + d, 0.0f, r );
	mTestSpheres[3].Set( center.x + d, center.y + d, 0.0f, r );
}

cSceneTreeNode::cSceneTreeNode( cSceneTree* tree, cSceneTreeNode* parent, const cSphere& sphere )
: cSphere( sphere )
, mTree( tree )
, mParent( parent )
{
	mChild[0] = mChild[1] = mChild[2] = mChild[3] = 0;

	float d = ( mRadius / 1.4142135623731f ) * 0.5f;
	float r = mRadius * 0.55f;

	mTestSpheres[0].Set( mCenter.x - d, mCenter.y - d, 0.0f, r );
	mTestSpheres[1].Set( mCenter.x + d, mCenter.y - d, 0.0f, r );
	mTestSpheres[2].Set( mCenter.x - d, mCenter.y + d, 0.0f, r );
	mTestSpheres[3].Set( mCenter.x + d, mCenter.y + d, 0.0f, r );
}

cSceneTreeNode::~cSceneTreeNode()
{
	delete mChild[0];
	delete mChild[1];
	delete mChild[2];
	delete mChild[3];
}

void* cSceneTreeNode::operator new( size_t /*n*/ )
{ 
	return mPool.Alloc();
}

void cSceneTreeNode::operator delete( void* p )
{
	mPool.Free( (cSceneTreeNode*)p );
}

void cSceneTreeNode::Push( cSceneNode* node )
{
	assert( node );

	/// 말단 노드인 경우 장면 노드를 추가하고 바로 리턴
	if( mRadius <= mTree->GetMinRadius() )
	{
		node->mContainer = this;
		node->mIteratorValid = true;
		node->mIteratorByContainer = mObjectList.Insert( mObjectList.End(), node );
		return;
	}

	/// 장면 노드가 트리 노드보다 더 크면 상위 노드로 장면 노드를 전달
	if( node->GetRadius() > mRadius )
	{
		if( mParent )
		{
			mParent->Push( node );
		}
		else
		{
			node->mContainer = this;
			node->mIteratorValid = true;
			node->mIteratorByContainer = mObjectList.Insert( mObjectList.End(), node );
			//NiPoint3 p = node->GetCenter();
			//float r = node->GetRadius();

			//assert( 0 && "scene node radius is too big!" );
		}
		return;
	}

	/// 자식 노드들에 대해 장면 노드 포함 여부를 검사
	int i = 0;
	int count = 0;
	cSphere s( node->GetCenter(), node->GetRadius() );
	mTestSpheres[0].mResult = false;
	mTestSpheres[1].mResult = false;
	mTestSpheres[2].mResult = false;
	mTestSpheres[3].mResult = false;

	if( mTestSpheres[0].ContainSphere( s ) )
	{
		i = 0;
		mTestSpheres[0].mResult = true;
		++count;
	}
	if( mTestSpheres[1].ContainSphere( s ) )
	{
		i = 1;
		mTestSpheres[1].mResult = true;
		++count;
	}
	if( mTestSpheres[2].ContainSphere( s ) )
	{
		i = 2;
		mTestSpheres[2].mResult = true;
		++count;
	}
	if( mTestSpheres[3].ContainSphere( s ) )
	{
		i = 3;
		mTestSpheres[3].mResult = true;
		++count;
	}

	/// 장면 노드를 완전히 포함하는 자식 노드의 수를 검사
	switch( count )
	{
	case 0:
		{
			/// 현재 노드에 추가
			node->mContainer = this;
			node->mIteratorValid = true;
			node->mIteratorByContainer = mObjectList.Insert( mObjectList.End(), node );
		}
		break;
	case 1:
		{
			/// 해당 자식 노드에 장면 노드를 전달
			cSceneTreeNode* child = mChild[i];

			if( child == 0 )
			{
				child = mChild[i] = new cSceneTreeNode( mTree, this, mTestSpheres[i] );
			}
			child->Push( node );
		}
		break;
	case 2:
	case 3:
	case 4:
	default:
		{
			/// 가장 가까운 자식 노드에 장면 노드를 전달
			float minDistance = NI_INFINITY;
			int i = 0;
			const NiPoint3& c = node->GetCenter();
			float d;

			if( mTestSpheres[0].mResult )
			{
				d = mTestSpheres[0].GetDistance2( c );
				if( d < minDistance )
				{
					i = 0;
					minDistance = d;
				}
			}
			if( mTestSpheres[1].mResult )
			{
				d = mTestSpheres[1].GetDistance2( c );
				if( d < minDistance )
				{
					i = 1;
					minDistance = d;
				}
			}
			if( mTestSpheres[2].mResult )
			{
				d = mTestSpheres[2].GetDistance2( c );
				if( d < minDistance )
				{
					i = 2;
					minDistance = d;
				}
			}
			if( mTestSpheres[3].mResult )
			{
				d = mTestSpheres[3].GetDistance2( c );
				if( d < minDistance )
				{
					i = 3;
					minDistance = d;
				}
			}

			cSceneTreeNode* child = mChild[i];

			if( child == 0 )
			{
				child = mChild[i] = new cSceneTreeNode( mTree, this, mTestSpheres[i] );
			}
			child->Push( node );
		}
		break;
	}
}

void cSceneTreeNode::Remove( cSceneNode* node )
{
	assert( node );

	if( node->mIteratorValid )
	{
		node->mIteratorValid = false;
		mObjectList.Erase( node->mIteratorByContainer );
	}
}

void cSceneTreeNode::Update( cSceneNode* node )
{
	assert( node );

	/// 장면 노드가 속한 트리 노드에 대해 포함 여부를 검사
	cSphere s( node->GetCenter(), node->GetRadius() );

	if( ContainSphere( s ) == false )
	{
		/// 장면 노드를 트리 노드에서 제거하고 상위 트리 노드에 대해 포함 유무를 검사
		Remove( node );

		if( mParent )
		{
			if( mParent->ContainSphere( s ) )
				mParent->Push( node );
			else
				mTree->Push( node );
		}
		else
		{
			mTree->Push( node );
		}
	}
}

void cSceneTreeNode::Cull( NiVisibleArray* solidArray, NiVisibleArray* skinedArray, NiVisibleArray* alphaArray, NiFrustumPlanes& frustum )
{
	unsigned int saveActive = frustum.GetActivePlaneState();
	unsigned int i = 0;

	for( ; i < NiFrustumPlanes::MAX_PLANES; ++i )
	{
		if( frustum.IsPlaneActive(i) )
		{
			unsigned int side = WhichSide( frustum.GetPlane(i) );

			if( side == NiPlane::NEGATIVE_SIDE )
			{
				// The object is not visible since it is on the negative
				// side of the plane.
				frustum.SetActivePlaneState(saveActive);
				return;
			}

			if( side == NiPlane::POSITIVE_SIDE )
			{
				// The object is fully on the positive side of the plane,
				// so there is no need to compare child objects to this plane.
				frustum.DisablePlane(i);
			}
		}
	}

	if( frustum.IsAnyPlaneActive() == false )
	{
		/// 완전 포함 -> 자손들을 모두 추가
		AddToVisibleArray( solidArray, skinedArray, alphaArray );
	}
	else if( i == NiFrustumPlanes::MAX_PLANES )
	{
		/// 교차 -> 컬링 검사를 계속
		/// 포함된 개체들에 대해 검사
		cObjectList::cIterator i = mObjectList.Begin();
		cObjectList::cIterator end = mObjectList.End();

		for( ; i != end; ++i )
		{
			cSceneNode* n = (cSceneNode*)*i;
			unsigned int c = 0;

			for( ; c < NiFrustumPlanes::MAX_PLANES; ++c )
			{
				if( frustum.IsPlaneActive(c) )
				{
					if( n->WhichSide( frustum.GetPlane(c) ) == NiPlane::NEGATIVE_SIDE )
						break;
				}
			}

			if( c == NiFrustumPlanes::MAX_PLANES )
			{
				if( n->OnVisible( *mCuller ) )
					n->AddToVisibleArray( solidArray, skinedArray, alphaArray );
			}
		}

		/// 자손들에 대해 컬링
		if( mChild[0] )
			mChild[0]->Cull( solidArray, skinedArray, alphaArray, frustum );
		if( mChild[1] )
			mChild[1]->Cull( solidArray, skinedArray, alphaArray, frustum );
		if( mChild[2] )
			mChild[2]->Cull( solidArray, skinedArray, alphaArray, frustum );
		if( mChild[3] )
			mChild[3]->Cull( solidArray, skinedArray, alphaArray, frustum );
	}

	frustum.SetActivePlaneState(saveActive);
}

void cSceneTreeNode::AddToVisibleArray( NiVisibleArray* solidArray, NiVisibleArray* skinedArray, NiVisibleArray* alphaArray ) const
{
	/// 포함된 개체들을 추가
	cObjectList::cConstIterator i = mObjectList.Begin();
	cObjectList::cConstIterator end = mObjectList.End();

	for( ; i != end; ++i )
	{
		cSceneNode* n = (cSceneNode*)*i;

		if( n->OnVisible( *mCuller ) )
			n->AddToVisibleArray( solidArray, skinedArray, alphaArray );
	}

	// 자식 노드들에 대해 재귀 호출
	if( mChild[0] )
		mChild[0]->AddToVisibleArray( solidArray, skinedArray, alphaArray );
	if( mChild[1] )
		mChild[1]->AddToVisibleArray( solidArray, skinedArray, alphaArray );
	if( mChild[2] )
		mChild[2]->AddToVisibleArray( solidArray, skinedArray, alphaArray );
	if( mChild[3] )
		mChild[3]->AddToVisibleArray( solidArray, skinedArray, alphaArray );
}

bool cSceneTreeNode::CollideRay( tArray<void*>* collidableArray, const cRay& ray, float maxDistance )
{
	bool ret = false;

	if( IntersectRay( ray, maxDistance ) )
	{
		/// 포함된 장면 노드들에 대해 교차 검사
		if( mObjectList.IsEmpty() == false )
		{
			cObjectList::cIterator i = mObjectList.Begin();
			cObjectList::cIterator end = mObjectList.End();

			for( ; i != end; ++i )
			{
				cSceneNode* n = (cSceneNode*)*i;

				if( n->Pick( ray.GetOrigin(), ray.GetDirection() ) && n->GetPickDistance() < maxDistance )
				{
					collidableArray->PushBack( n );
					ret = true;
				}
			}
		}

		/// 자식들에 대해 교차 검사
		if( mChild[0] )
			ret |= mChild[0]->CollideRay( collidableArray, ray, maxDistance );
		if( mChild[1] )
			ret |= mChild[1]->CollideRay( collidableArray, ray, maxDistance );
		if( mChild[2] )
			ret |= mChild[2]->CollideRay( collidableArray, ray, maxDistance );
		if( mChild[3] )
			ret |= mChild[3]->CollideRay( collidableArray, ray, maxDistance );
	}
	return ret;
}

bool cSceneTreeNode::CollideSphere( tArray<void*>* collidableArray, const cSphere& sphere )
{
	bool ret = false;

	if( IntersectSphere( sphere ) )
	{
		/// 포함된 장면 노드들에 대해 교차 검사
		if( mObjectList.IsEmpty() == false )
		{
			cObjectList::cIterator i = mObjectList.Begin();
			cObjectList::cIterator end = mObjectList.End();

			for( ; i != end; ++i )
			{
				cSceneNode* n = (cSceneNode*)*i;

				if( cSphere( n->GetCenter(), n->GetRadius() ).IntersectSphere( sphere ) )
				{
					collidableArray->PushBack( n );
					ret = true;
				}
			}
		}

		/// 자식들에 대해 교차 검사
		if( mChild[0] )
			ret |= mChild[0]->CollideSphere( collidableArray, sphere );
		if( mChild[1] )
			ret |= mChild[1]->CollideSphere( collidableArray, sphere );
		if( mChild[2] )
			ret |= mChild[2]->CollideSphere( collidableArray, sphere );
		if( mChild[3] )
			ret |= mChild[3]->CollideSphere( collidableArray, sphere );
	}
	return ret;
}

cSceneTree::cSceneTree()
: mRootNode( 0 )
, mCenter( NiPoint3::ZERO )
, mMinRadius( 0.0f )
, mMaxRadius( 0.0f )
{
}

cSceneTree::~cSceneTree()
{
	delete mRootNode;
}

void cSceneTree::Clear()
{
	delete mRootNode;
	mRootNode = 0;
}

void cSceneTree::Init( const NiPoint3& center, float minRadius, float maxRadius )
{
	mCenter = center;
	mMinRadius = minRadius;
	mMaxRadius = maxRadius;

	delete mRootNode;
	mRootNode = new cSceneTreeNode( this, 0, center, maxRadius );
}

void cSceneTree::Push( cSceneNode* node )
{
	assert( node );
	assert( mRootNode );

	mRootNode->Push( node );
}

void cSceneTree::Cull( NiVisibleArray* solidArray, NiVisibleArray* skinedArray, NiVisibleArray* alphaArray, NiFrustumPlanes& frustum, cSceneCuller& culler )
{
	assert( solidArray );
	assert( skinedArray );
	assert( alphaArray );
	assert( mRootNode );

	cSceneTreeNode::mCuller = &culler;
	mRootNode->Cull( solidArray, skinedArray, alphaArray, frustum );
}

bool cSceneTree::CollideRay( tArray<void*>* collidableArray, const cRay& ray, float maxDistance, bool sortByDistance )
{
	assert( collidableArray );
	assert( mRootNode );

	bool ret = mRootNode->CollideRay( collidableArray, ray, maxDistance );

	if( ret && sortByDistance && collidableArray->IsEmpty() == false )
	{
		::Sort( collidableArray->Begin(), collidableArray->End(), cSceneNodeCompareByPickDistance() );
	}
	return ret;
}

bool cSceneTree::CollideSphere( tArray<void*>* collidableArray, const cSphere& sphere )
{
	assert( collidableArray );
	assert( mRootNode );

	return mRootNode->CollideSphere( collidableArray, sphere );
}
