//
// Tools_GlobalIllumination_EntitySamples.cpp
//
// Created by KJFL - 2004-06-25 17:18:46
//
// Copyright (C) 2004 Rebellion, All Rights Reserved.
//

#include "Core/Asura.h"

// This file's header.
#include "Lighting/Tools_GlobalIllumination_EntitySamples.h"

#include "Core/Asura_Timers.h"
#include "Mesh/Asura_Mesh.h"
#include "Rendering/Asura_Module.h"

#include "Tools_System.h"
#include "Lighting/Tools_LightSets.h"
#include "Lighting/Tools_EnvironmentalLightTransport.h"
#include "Lighting/Tools_PhotonMapping_System.h"
#include "Misc/Tools_Adjacency.h"
#include "Misc/Tools_Timed_Messages.h"
#include "Misc/Tools_HashTable.h"




Tools_GlobalIllumination_EntitySample*	Tools_GlobalIllumination_EntitySamples::s_pxSamples;

Tools_GlobalIllumination_EntitySample*	Tools_GlobalIllumination_EntitySamples::s_pxSortedSamples;

u_int									Tools_GlobalIllumination_EntitySamples::s_uNumberOfSamples;

u_int									Tools_GlobalIllumination_EntitySamples::s_uFrameStamp;
bool									Tools_GlobalIllumination_EntitySamples::s_bValid = false;


Tools_GlobalIllumination_EntitySample**	Tools_GlobalIllumination_EntitySamples::s_ppxProximalSamples;	
float*									Tools_GlobalIllumination_EntitySamples::s_fProximalSampleDistancesSquared;
float									Tools_GlobalIllumination_EntitySamples::s_fMaxDistanceSquared;
u_int									Tools_GlobalIllumination_EntitySamples::s_uMostDistantSample;

static const u_int uMAX_NUMBER_OF_PROXIMAL_SAMPLES = 6;

	
static u_int* g_puStack;

void Tools_GlobalIllumination_EntitySamples::Initialise( void )
{
	s_pxSamples = 0;
	s_uNumberOfSamples = 0;

	s_ppxProximalSamples = new Tools_GlobalIllumination_EntitySample*[uMAX_NUMBER_OF_PROXIMAL_SAMPLES];

	s_fProximalSampleDistancesSquared = new float[uMAX_NUMBER_OF_PROXIMAL_SAMPLES];

	s_uFrameStamp = Asura_Timers::GetFrameNumber();
	s_bValid = false;

	g_puStack = new u_int[32];

}

void Tools_GlobalIllumination_EntitySamples::Shutdown( void )
{
	// Everything must go.

	delete [] s_pxSamples;
	delete [] s_ppxProximalSamples;
	delete [] s_fProximalSampleDistancesSquared;

	s_pxSamples = 0;
	s_uNumberOfSamples = 0;

	delete [] g_puStack;
}

void Tools_GlobalIllumination_EntitySamples::Reset( void )
{
	// Let's keep the proximal samples list, since the size of that is constant,
	// but we'll throw away everything else.

	delete [] s_pxSamples;

	s_pxSamples = 0;
	s_uNumberOfSamples = 0;
	s_uFrameStamp = Asura_Timers::GetFrameNumber();
	s_bValid = false;

}

void Tools_GlobalIllumination_EntitySamples::GetNearestSample( const Asura_Vector_3& xPosition, Asura_SphericalHarmonics_Order2_RGB& xSH )
{

	// If the samples are invalid , and the Tools system is active (i.e. we haven't quit to game) then try to recalculate them.
	// RAR 08/01/2008
	if ( !s_bValid && Tools_System::IsActive() )
	{
		// if we haven't already tried it this frame, recalc the samples.
		static u_int uFrameLastTested = 0xffffffff;

		if (Asura_Timers::GetFrameNumber() != uFrameLastTested)
		{
			Tools_GlobalIllumination_EntitySamples::Reset();
			Tools_GlobalIllumination_EntitySamples::ConstructSamples();

			uFrameLastTested = Asura_Timers::GetFrameNumber();
		}
	}

	if ( s_uNumberOfSamples == 0 )
	{
		// fair enough, there really isn't any samples.
		// let's be nice and return an ambient white light from above so people can actually see things.

		xSH.m_afRedCoefficients[2] = xSH.m_afGreenCoefficients[2] = xSH.m_afBlueCoefficients[2] = -1.0f;
		return;
	}

	s_fMaxDistanceSquared = 0;
	
	u_int uNumberOfProximalSamples = 0;
	u_int uFurthestSample = 0;

	u_int* puStack = g_puStack;

	u_int uMaxDepth = 0;
	*puStack++ = 0;

	u_int uIndex = 1;

	u_int uSearches = 0;
	do
	{

		Asura_Assert( uIndex>0 && uIndex <= s_uNumberOfSamples, "aha");

		Tools_GlobalIllumination_EntitySample& xSample = s_pxSamples[uIndex];

	
		u_int uAxis = xSample.GetPlaneAxis();
	
		float fPlaneDist = xPosition[uAxis] - xSample.GetPosition()[uAxis];

		if (uIndex * 2 < s_uNumberOfSamples - 1)
		{
			if (uNumberOfProximalSamples < uMAX_NUMBER_OF_PROXIMAL_SAMPLES )
			{
				if (fPlaneDist>0)
				{
					*puStack++ = uIndex*2;
					*puStack++ = uIndex*2 + 1;
				}
				else
				{
					*puStack++ = uIndex*2 + 1;
					*puStack++ = uIndex*2;
				}
			}
			else if (fPlaneDist>0)
			{
			
				if (fPlaneDist*fPlaneDist<s_fMaxDistanceSquared)
				{
					*puStack++ = uIndex*2;
				}

				*puStack++ = uIndex*2 + 1;
			}
			else
			{
				if (fPlaneDist*fPlaneDist<s_fMaxDistanceSquared)
				{
					*puStack++ = uIndex*2 + 1;
				}
				*puStack++ = uIndex*2;
			}
		}

		u_int uDepth = puStack - g_puStack;

		if (uDepth > uMaxDepth)
		{
			uMaxDepth = uDepth;
		}
				
		uIndex = *(--puStack);
				

		if (uIndex == 0) break;

		{

			uSearches++;
			Asura_Vector_3 xDisp = xSample.GetPosition() - xPosition;
			float fDistanceSquared = xDisp.MagnitudeSquared();

			// if we haven't reached the maximum number of samples, just add it
			if (uNumberOfProximalSamples < uMAX_NUMBER_OF_PROXIMAL_SAMPLES)
			{
				// keep track of the max distance found, and which sample it was
				if (fDistanceSquared > s_fMaxDistanceSquared)
				{
					s_fMaxDistanceSquared = fDistanceSquared;
					uFurthestSample = uNumberOfProximalSamples;
				}

				// set the data to record the proximal sample
				s_ppxProximalSamples[uNumberOfProximalSamples] = &xSample;
				s_fProximalSampleDistancesSquared[uNumberOfProximalSamples] = fDistanceSquared;

				++uNumberOfProximalSamples;
			}
			// otherwise only add it if it's closer than the samples we already have
			else if (fDistanceSquared < s_fMaxDistanceSquared)
			{
				// replace the furthest out sample
				s_ppxProximalSamples[uFurthestSample] = &xSample;
				s_fProximalSampleDistancesSquared[uFurthestSample] = fDistanceSquared;

				// And find the new furthest out sample.
				// Since number of proximal samples is likely to always be small (<=5 say) we'll
				// just test the distances directly.
				uFurthestSample = 0;
				s_fMaxDistanceSquared = s_fProximalSampleDistancesSquared[0];

				for (u_int uSample=1; uSample<uMAX_NUMBER_OF_PROXIMAL_SAMPLES; uSample++)
				{
					if (s_fMaxDistanceSquared < s_fProximalSampleDistancesSquared[uSample])
					{
						s_fMaxDistanceSquared = s_fProximalSampleDistancesSquared[uSample];
						uFurthestSample = uSample;
					}
				}
			}
		}

		

	}
	while (uIndex!=0);

	//Tools_Timed_Message_System::AddMessage( 0xffffffff, "Number of samples: %d, Searched: %d, Max Depth: %d", s_uNumberOfSamples, uSearches, uMaxDepth );
//	Tools_Timed_Message_System::AddMessage( 0xffffffff, "Original: %f, changed: %f", f1,f2);

	

	// we now have a list of most proximal samples

	xSH.Zero();
#if 01
	if (uNumberOfProximalSamples>=1)
	{
		float fTotal = 0;

		for (u_int u=0; u<uNumberOfProximalSamples; u++)
		{
#if 0
			float fScale = 1.0f - s_fProximalSampleDistancesSquared[u] / s_fMaxDistanceSquared;
#else
			
			// nudge above zero to avoid singularities
			s_fProximalSampleDistancesSquared[u] += 0.001f;
			float fScale = 1.0f / s_fProximalSampleDistancesSquared[u];
#endif
			
			fTotal += fScale;

			if (s_uFrameStamp == s_ppxProximalSamples[u]->m_uFrameStamp)
			{
				xSH.ScaledAdd( s_ppxProximalSamples[u]->m_xSH, fScale );
			}
			else
			{

				Asura_SphericalHarmonics_Order2_RGB xResult;

#if defined ASURA_USE_HDR
				Tools_EnvironmentalLightTransport::GetDiffuseForVertex(xResult,
					s_ppxProximalSamples[u]->m_uVertex, s_ppxProximalSamples[u]->m_uModule);
#else
				Tools_PhotonMapping_System::GetSHsAtVertex(s_ppxProximalSamples[u]->m_uModule,
					s_ppxProximalSamples[u]->m_uVertex, xResult);
#endif

				xSH.ScaledAdd( xResult, fScale );

				s_ppxProximalSamples[u]->m_xSH = xResult;
				s_ppxProximalSamples[u]->m_uFrameStamp = s_uFrameStamp;
			}
		
		}

		xSH.Scale(1.0f / (float)fTotal);
	}
#endif
//Tools_Timed_Message_System::AddMessage(0xffffffff,"MaxDist: %f",s_fMaxDistanceSquared);

//	xSH = s_ppxProximalSamples[0]->m_xSH;

}


void Tools_GlobalIllumination_EntitySamples::ConstructSamples( void )
{
	Asura_Assert( s_pxSamples==0, "Samples already exist?" );
	Asura_Assert( s_uNumberOfSamples == 0, "Samples already exist?" );



	const u_int uNumberOfModules = Asura_Module_System::GetNumberOfModules();

	for (u_int uModule=0; uModule<uNumberOfModules; uModule++)
	{
		if(!Tools_LightSets::IsModuleInCurrentLightSet(uModule)) continue;

		const Asura_Mesh* pxMesh = Asura_Module_System::GetMeshForModule(uModule);

		const u_int uNumberOfVertices = pxMesh->NumberOfVertices;
	
		// scan through the vertices of each module
		for (u_int uVertex=0; uVertex<uNumberOfVertices; uVertex++)
		{
			// do we want to use this vertex as a sample point?
			if(ShouldMakeSampleAtVertex( uModule, uVertex ))
			{
				++s_uNumberOfSamples;
			}
		}
	}

	if (s_uNumberOfSamples == 0)
	{
		// there are no samples
		s_bValid = true;
		return;
	}

	s_pxSamples = new Tools_GlobalIllumination_EntitySample[s_uNumberOfSamples];

    Tools_HashTable<Tools_GlobalIllumination_EntitySample>* pxHashTable = new Tools_HashTable<Tools_GlobalIllumination_EntitySample>( 1 << Asura_Maths::GetFloorLog2(s_uNumberOfSamples >> 1) );
    

	u_int uSample = 0;
	for (u_int uModule=0; uModule<uNumberOfModules; uModule++)
	{
		if(!Tools_LightSets::IsModuleInCurrentLightSet(uModule)) continue;

		const Asura_Mesh* pxMesh = Asura_Module_System::GetMeshForModule(uModule);

		const Asura_Vector_3& xModulePosition = Asura_Module_System::GetPositionOfModule(uModule);
		const u_int uNumberOfVertices = pxMesh->NumberOfVertices;
	
		// scan through the vertices of each module
		for (u_int uVertex=0; uVertex<uNumberOfVertices; uVertex++)
		{
			// do we want to use this vertex as a sample point?
			if(ShouldMakeSampleAtVertex( uModule, uVertex ))
			{
				Asura_Vector_3 xPosition = pxMesh->VertexDataPtr[uVertex].Position + xModulePosition;

				s_pxSamples[uSample].SetPositionAndHash(xPosition);

				bool bFoundDuplicate = ( pxHashTable->Insert(&s_pxSamples[uSample]) != &s_pxSamples[uSample] );


				if (!bFoundDuplicate)
				{
					s_pxSamples[uSample].m_uModule = uModule;
					s_pxSamples[uSample].m_uVertex = uVertex;
					s_pxSamples[uSample].m_uFrameStamp = 0;
		
					++uSample;
				}
			}
		}
	}

	delete pxHashTable;
	
//	Tools_Timed_Message_System::AddMessage( 0xffffffff, "Number of samples: %d, duplicates removed: %d", uSample, s_uNumberOfSamples - uSample );

	s_uNumberOfSamples = uSample;

	ConstructLeftBalancedTree();

	s_bValid = true;
}

void Tools_GlobalIllumination_EntitySamples::LightingMayHaveChanged( void )
{
	s_uFrameStamp = Asura_Timers::GetFrameNumber();
}

bool Tools_GlobalIllumination_EntitySamples::ShouldMakeSampleAtVertex( u_int uModule, u_int uVertex )
{
	// is this vertex part of any polygons which have the 'UseForEntityGISamples' flag?

	const Tools_Polygon_Adjacency* pxVertAdj = Tools_Adjacency::GetVertexAdjacencies(uModule,uVertex);

	for(const Tools_Adjacent_Polygon* pxAdj = pxVertAdj->GetFirstAdjacency(); pxAdj; pxAdj = pxAdj->GetNext())
	{
		if(pxAdj->IsBetweenModules()) continue;

		int iModuleIndex = pxAdj->GetModuleIndex();
		int iPolygonIndex = pxAdj->GetPolygonIndex();

		const Asura_Mesh* pxPolysMesh = Asura_Module_System::GetMeshForModule(iModuleIndex);

		if (pxPolysMesh->PolygonFlagDataPtr && pxPolysMesh->PolygonFlagDataValid)
		{
			
			if (pxPolysMesh->PolygonFlagDataPtr[iPolygonIndex].Flags & AsuraPolygonFlag_UseForEntityGISamples)
			{
				// yep, let's have a sample here
				return true;
			}
		}
	}

	// apparently not
	return false;
}


const Tools_GlobalIllumination_EntitySample& Tools_GlobalIllumination_EntitySamples::GetSample( u_int uSample )
{
	// if sample is out of date, recalculate it
	if (s_uFrameStamp != s_pxSamples[uSample].m_uFrameStamp)
	{
#if defined ASURA_USE_HDR
		Tools_EnvironmentalLightTransport::GetDiffuseForVertex( s_pxSamples[uSample].m_xSH,
			s_pxSamples[uSample].m_uVertex, s_pxSamples[uSample].m_uModule );
#else
		Tools_PhotonMapping_System::GetSHsAtVertex( s_pxSamples[uSample].m_uModule,
			s_pxSamples[uSample].m_uVertex, s_pxSamples[uSample].m_xSH );
#endif

		s_pxSamples[uSample].m_uFrameStamp = s_uFrameStamp;
	}

	return s_pxSamples[uSample];
}





static Asura_Vector_3 g_xBBMin;
static Asura_Vector_3 g_xBBMax;

void Tools_GlobalIllumination_EntitySamples::ConstructLeftBalancedTree(void)
{
	// need to do something here
	if (s_uNumberOfSamples==0) return;

	Tools_GlobalIllumination_EntitySample* pxSortArray1 = new Tools_GlobalIllumination_EntitySample[s_uNumberOfSamples+1];
	Tools_GlobalIllumination_EntitySample** ppxSortArray2 = new Tools_GlobalIllumination_EntitySample*[s_uNumberOfSamples+1];

	Asura_Bounding_Box g_xBB;
	g_xBB.Reset();

	ppxSortArray2[0] = 0;
	for (u_int u=0; u<s_uNumberOfSamples; u++)
	{
		ppxSortArray2[u+1] = &s_pxSamples[u];
		g_xBB.Set(ppxSortArray2[u+1]->GetPosition());
		ppxSortArray2[u+1]->SetSplittingPlane(0);
	}

	g_xBBMax = Asura_Vector_3(g_xBB.MaxX,g_xBB.MaxY, g_xBB.MaxZ);
	g_xBBMin = Asura_Vector_3(g_xBB.MinX,g_xBB.MinY, g_xBB.MinZ);

	BalanceSegment(pxSortArray1, ppxSortArray2, 1, 1, s_uNumberOfSamples);

	delete [] ppxSortArray2;
	
	delete [] s_pxSamples;

	s_pxSamples = pxSortArray1;
	s_uNumberOfSamples++;
}



void Tools_GlobalIllumination_EntitySamples::BalanceSegment(Tools_GlobalIllumination_EntitySample* pxBalancedArray, Tools_GlobalIllumination_EntitySample** ppxOriginalArray, const u_int uIndex, const u_int uStart, const u_int uEnd)
{
	u_int uMedian = 1;

	while ((4*uMedian)<=(uEnd-uStart+1))
	{
		uMedian += uMedian;
	}

	if ((3*uMedian)<=(uEnd-uStart+1))
	{
		uMedian += uMedian;
		uMedian += uStart-1;
	}
	else
	{
		uMedian = uEnd - uMedian + 1;
	}

	float fLengthAlongX = g_xBBMax.x-g_xBBMin.x;
	float fLengthAlongY = g_xBBMax.y-g_xBBMin.y;
	float fLengthAlongZ = g_xBBMax.z-g_xBBMin.z;


	u_int uAxis;

	if (fLengthAlongX > fLengthAlongY)
	{
		if (fLengthAlongX > fLengthAlongZ)
		{
			uAxis = 0;
		}
		else
		{
			uAxis = 2;
		}
	}
	else if (fLengthAlongY > fLengthAlongZ)
	{
		uAxis = 1;
	}
	else
	{
		uAxis = 2;
	}
	

	MedianSplit(ppxOriginalArray, uStart, uEnd, uMedian, uAxis);

	pxBalancedArray[uIndex] = *ppxOriginalArray[uMedian];
	pxBalancedArray[uIndex].SetSplittingPlane(uAxis);

	if (uMedian>uStart)
	{
		if (uStart<uMedian-1)
		{
			const float tmp = g_xBBMax[uAxis];

			g_xBBMax[uAxis] = pxBalancedArray[uIndex].GetPosition()[uAxis];
			BalanceSegment(pxBalancedArray,ppxOriginalArray,2*uIndex,uStart, uMedian-1);
			g_xBBMax[uAxis] = tmp;
		}
		else
		{
			pxBalancedArray[2*uIndex] = *ppxOriginalArray[uStart];
		}
	}

	if (uMedian<uEnd)
	{
		if (uMedian+1 < uEnd)
		{
			const float tmp = g_xBBMin[uAxis];

			g_xBBMin[uAxis] = pxBalancedArray[uIndex].GetPosition()[uAxis];
			BalanceSegment(pxBalancedArray,ppxOriginalArray,2*uIndex+1,uMedian+1, uEnd);
			g_xBBMin[uAxis] = tmp;
		}
		else
		{
			pxBalancedArray[2*uIndex+1] = *ppxOriginalArray[uEnd];
		}
	}
}

void Tools_GlobalIllumination_EntitySamples::MedianSplit(Tools_GlobalIllumination_EntitySample** ppxArray, const u_int uStart, const u_int uEnd, const u_int uMedian, const u_int uAxis)
{
	u_int uLeft = uStart;
	u_int uRight = uEnd;

	while (uRight>uLeft)
	{
		const float f = ppxArray[uRight]->GetPosition()[uAxis];

		u_int i = uLeft-1;
		u_int j = uRight;

		for (;;)
		{
			while ( ppxArray[++i]->GetPosition()[uAxis] < f );
			while ( ppxArray[--j]->GetPosition()[uAxis] > f && j>uLeft);

			if (i>=j) break;

			Tools_GlobalIllumination_EntitySample* pxTemp = ppxArray[i];
			ppxArray[i] = ppxArray[j];
			ppxArray[j] = pxTemp;
		}

		Tools_GlobalIllumination_EntitySample* pxTemp = ppxArray[i];
		ppxArray[i] = ppxArray[uRight];
		ppxArray[uRight] = pxTemp;

		if (i>=uMedian)
		{
			uRight = i-1;
		}
		if (i<=uMedian)
		{
			uLeft =  i+1;
		}

	}
}
