//
// Tools_VertexCacheOptimiser.cpp
//
// Created by KJFL - 30 March 2009
//
// Copyright (C) 2009 Rebellion, All Rights Reserved.
//

#include "Core/Asura.h"

// This file's header.
#include "MeshProcessing/Tools_VertexCacheOptimiser.h"

#include "Debugging/Asura_Assert.h"

// Enable this define to turn on the logfile and profiling.
// Note this will also run the TriStripper algorithm as well
// for comparisons of speed and vertex cache misses.
//#define TOOLS_VCO_PROFILE

#ifdef TOOLS_VCO_PROFILE
	
	#define TOOLS_VCO_LOGFILE "logfiles/VertexCacheOptimiser.txt"
	#include "Core/Asura_Timers.h"
	#include "Debugging/Asura_Logfile.h"
	#include "MeshProcessing/Asura_TriStripper.h"

#endif

// Lots of magic numbers used to formulate the scoring heuristics
// of cache position and valence. These comes from statistical 
// analysis and annealing. 
static const float fLAST_USED_TRIANGLE_SCORE = 0.75f;
static const float fCACHE_DECAY_POWER = 1.5f;
static const float fVALENCE_BOOST_SCALE = 2.0f;
static const float fVALENCE_BOOST_POWER = 0.5f;

// Multiplicative factor to change float scores into ints that
// can be tested and compared without FPU->CPU stalls.
static const float fSCORE_AS_INT_SCALE = 100000000.0f;

// Size of our LRU cache.
static const u_int uVERTEX_CACHE_SIZE = 32;

// Cut-off point at which we stop carrying about a vertex valence
// value - this is simply because we use fixed arrays for scoring. 
static const u_int uMAX_VALENCE_FOR_SCORING = 31;

// Arrays to hold the precalculated scores for a certain cache position
// and the valence of the vertex (i.e. the number of tris left for that
// vertex). These only need to be calculated once, so they are initialised
// as a global variable.
class Tools_VCO_Scores
{
	public:

		Tools_VCO_Scores()
		{
			// Assign scores for each cache position. The first three positions have an equal
			// set score, so that the order a triangle's vertices are added to the cache is 
			// not important. After that the scores start at a high value that decays to zero
			// as you go further down the cache rankings. 
			for (u_int uCachePosition=0; uCachePosition<uVERTEX_CACHE_SIZE; ++uCachePosition)
			{
				float fScore;
				if ( uCachePosition < 3 )
				{
					fScore = fLAST_USED_TRIANGLE_SCORE;
				}
				else
				{
					const float fScale = 1.0f / (float)(uVERTEX_CACHE_SIZE - 3 );
					fScore = 1.0f - (float)(uCachePosition-3)*fScale;
					fScore = Asura_Maths::Power( fScore, fCACHE_DECAY_POWER );
				}
			
				m_aiCacheScore[uCachePosition] = Asura_Maths::FloatToInt(fScore*fSCORE_AS_INT_SCALE);

			}

			// positions outside of the cache have no score
			m_aiCacheScore[uVERTEX_CACHE_SIZE] = 0;
			m_aiCacheScore[uVERTEX_CACHE_SIZE+1] = 0;
			m_aiCacheScore[uVERTEX_CACHE_SIZE+2] = 0;

			// zero valence (i.e no triangles left) means a huge negative score
			m_aiValenceScore[0] = Asura_Maths::FloatToInt( 10.0f * fSCORE_AS_INT_SCALE );
			// otherwise valence boost starts high and then is an ever decreasing amount
			for (u_int u=1; u<=uMAX_VALENCE_FOR_SCORING; ++u)
			{
				float fValenceBoost = Asura_Maths::Power( (float)u, -fVALENCE_BOOST_POWER );
				m_aiValenceScore[u] = Asura_Maths::FloatToInt(fSCORE_AS_INT_SCALE*fVALENCE_BOOST_SCALE * fValenceBoost);
			}
		}

		inline int GetCacheScore( u_int uCachePosition ) const
		{
			return m_aiCacheScore[uCachePosition];
		}

		inline int GetValenceScore( u_int uValence ) const 
		{
			return m_aiValenceScore[uValence];
		}
	
	private:

		int m_aiCacheScore[uVERTEX_CACHE_SIZE+3];
		int m_aiValenceScore[uMAX_VALENCE_FOR_SCORING+1];
};

static const Tools_VCO_Scores g_xScores;

#ifdef TOOLS_VCO_PROFILE
// Helper routine to find the vertex-cache-miss-to-triangle ratio,
// designed to mimic a hardware-based FIFO cache.
static float Tools_VCO_Test( u_int uNumberOfIndices, u_int uNumberOfTriangles, const u_short* pusIndexList )
{
	u_int uCacheMisses = 0;

	const u_int uMaxCacheSize = 20;
	u_short ausCache[uMaxCacheSize];
	u_int uNumberOfVerticesInCache = 0;

	for ( u_int u=0; u<uNumberOfIndices; ++u )
	{
		const u_short usIndex = pusIndexList[u];

		bool bInCache = false;
		for ( u_int v=0; v<uNumberOfVerticesInCache; ++v )
		{
			if ( ausCache[v] == usIndex )
			{
				bInCache = true;
				break;
			}
		}

		if (bInCache) continue;

		++uCacheMisses;

		if ( uNumberOfVerticesInCache < uMaxCacheSize )
		{
			ausCache[uNumberOfVerticesInCache++] = usIndex;
		}
		else
		{
			for (u_int v=1; v<uMaxCacheSize; ++v)
			{
				ausCache[v-1] = ausCache[v];
			}
			ausCache[uMaxCacheSize-1] = usIndex;
		}

	}

	return (float)(uCacheMisses)/((float)uNumberOfTriangles);
}
#endif

Tools_VertexCacheOptimiser::Tools_VertexCacheOptimiser( u_int uNumberOfTriangles, u_int uNumberOfVertices, const u_short* pusIndexList, bool bReorderVertices )
{
#ifdef TOOLS_VCO_PROFILE
	Asura_TickCount xStartTime = Asura_Timers::GetCurTicks();
#endif
	m_uCurrentCache = 0;
	m_apuLRUCache[0] = new u_int[uVERTEX_CACHE_SIZE+3];
	m_apuLRUCache[1] = new u_int[uVERTEX_CACHE_SIZE+3];
	m_uNumberOfVerticesInCache = 0;

	m_pusIndexList = new u_short[ uNumberOfTriangles * 3 ];
	m_pusVertexOrder = 0;
	m_uNumberOfUsedVertices = 0;

	u_int uNewIndex = 0;

	m_pxTriangles = new Tools_VCO_Triangle[ uNumberOfTriangles ];
	m_pxVertices = new Tools_VCO_Vertex[ uNumberOfVertices ];

	// Do the basic initialisation for each triangle, and also count
	// up the number of triangles each vertex is used in.
	u_int uTriBufferSize = 0;
	for ( u_int u=0, uIndex=0; u<uNumberOfTriangles; ++u )
	{
		m_pxTriangles[u].m_iScore = 0;
		m_pxTriangles[u].m_bAddedToDrawList = false;

		// TODO - a good candidate for unrolling
		for ( u_int v=0; v<3; ++v )
		{
			u_short usVertex =  pusIndexList[uIndex++];

			Asura_Assert( usVertex < uNumberOfVertices, "Data Error: higher vertex index than expected" );

			// Mark this triangle as using this vertex
			m_pxTriangles[u].m_usVertices[v] = usVertex;

			// Increment the number of triangles using this vertex
			++m_pxVertices[usVertex].m_uTotalNumberOfTris;
			++uTriBufferSize;
		}
	}

	// Used to allocate a little buffer per vertex, but the speed
	// overhead was too much - better to allocate one big buffer.
	u_int* puTriBuffer = new u_int[uTriBufferSize];
	
	{
		u_int  uTriBufferOffset = 0;

		// Now we now the number of triangles that use each vertex, 
		// allocate arrays and initialise score
		for ( u_int u=0; u<uNumberOfVertices; ++u )
		{
			u_int uTotalTris = m_pxVertices[u].m_uTotalNumberOfTris;
			
			m_pxVertices[u].m_puTriangles = &(puTriBuffer[uTriBufferOffset]);
			uTriBufferOffset += uTotalTris;
		
			// initial score is down to number of triangles using vertex
			const u_int uValence = Asura_Maths::Min( uTotalTris, uMAX_VALENCE_FOR_SCORING );
			m_pxVertices[u].m_iScore += g_xScores.GetValenceScore( uValence );
		}
	}

	u_int uHighestScoringTriangle = 0;
	int iHighestTriangleScore = -1;

	// Then do another scan to fill in the triangle usage arrays,
	// as well as the initial triangle scores
	// TODO - can we avoid these three separate loops?
	// I did think of lazy allocating the tri arrays rather than 
	// having the vertex loop above, but that brings in conditionals
	// and branches.
	for ( u_int u=0; u<uNumberOfTriangles; ++u )
	{
		int iScore = 0;

		// TODO - a good candidate for unrolling?
		for ( u_int v=0; v<3; ++v )
		{
			// Mark this vertex as being used by this triangle
			u_int uVertex = m_pxTriangles[u].m_usVertices[v];
			m_pxVertices[uVertex].m_puTriangles[m_pxVertices[uVertex].m_uNumberOfTrisOutstanding++] = u;
	
			// Triangle score is just sum of its vertices scores
			iScore += m_pxVertices[uVertex].m_iScore;
		}

		m_pxTriangles[u].m_iScore = iScore;
	
		if ( iScore > iHighestTriangleScore )
		{
			iHighestTriangleScore = iScore;
			uHighestScoringTriangle = u;
		}
	}

	// keep adding the best triangle until we've done them all
	for ( u_int uMainLoop=0; uMainLoop<uNumberOfTriangles; ++uMainLoop )
	{
		// If we don't know the best triangle, scan through all triangles updating their scores
		// and pick the best. In general this happens when all the remaining triangles use none
		// of the vertices in the cache. 
		// NOTE: this is our one o(N*N) loop, so we really want to avoid this happening too
		// often!
		if ( iHighestTriangleScore < 0 )
		{
			// TODO - better cache access if we have a separate array of tri scores?
			// Should we rearrange the array so it shrinks?
			for ( u_int u=0; u<uNumberOfTriangles; ++u )
			{
				// TODO - must be able to blend this into the score and 
				// remove a branch.
				if ( !m_pxTriangles[u].m_bAddedToDrawList )
				{
					// TODO - check the cached score is definitely valid,
					// if we're only reading at least that's not too bad.
					const int iScore = m_pxTriangles[u].m_iScore;
			
					if ( iScore > iHighestTriangleScore )
					{
						iHighestTriangleScore = iScore;
						uHighestScoringTriangle = u;
					}
				}
			}
		}

		const u_int uTriToAdd = uHighestScoringTriangle;
		Tools_VCO_Triangle& xBestTri = m_pxTriangles[uTriToAdd];

		Asura_Assert( xBestTri.m_bAddedToDrawList == false, "Already added this tri" );

		// reset the high score so we can look again
		uHighestScoringTriangle = 0;
		iHighestTriangleScore = -1;

		// Add this tri to our new draw list
		xBestTri.m_bAddedToDrawList = true;
		m_pusIndexList[uNewIndex++] = xBestTri.m_usVertices[0];
		m_pusIndexList[uNewIndex++] = xBestTri.m_usVertices[1];
		m_pusIndexList[uNewIndex++] = xBestTri.m_usVertices[2];

		// Fill in the new cache, adding the best tri vertices
		// to the very front, and then filling in the rest
		// of the cache from the old one until we run out of 
		// space. Then recalc the vertex scores.
		{
			u_int* puOldCache = m_apuLRUCache[m_uCurrentCache];
			m_uCurrentCache = 1 - m_uCurrentCache;
			u_int* puNewCache = m_apuLRUCache[m_uCurrentCache];
			
			u_int uNewCachePosition=0;	
		
			// 1) Reduce number of outstanding tris for each vertex of this best tri,
			// 2) Add the vertices to the front of the new cache
			// 3) Update the vertex scores accordingly.
			for ( u_int v=0; v<3; ++v )
			{
				const u_int uVertex = xBestTri.m_usVertices[v];
				Tools_VCO_Vertex& xVertex = m_pxVertices[uVertex];

				--xVertex.m_uNumberOfTrisOutstanding;

				puNewCache[uNewCachePosition] = uVertex;
		
				int iScore = g_xScores.GetCacheScore( uNewCachePosition );
	
				u_int uValence = Asura_Maths::Min( xVertex.m_uNumberOfTrisOutstanding, uMAX_VALENCE_FOR_SCORING );
				iScore += g_xScores.GetValenceScore( uValence );
				
				xVertex.m_iScore = iScore;

				++uNewCachePosition;
			}
				
			// Now copy in the old vertex cache into the new one, skipping
			// any vertices already added by the best tri. Update the vertex
			// scores with the new cache position.
			for (u_int u=0; u<m_uNumberOfVerticesInCache; ++u)
			{
				const u_int uVertex = puOldCache[u];

				// If this vertex is one of the ones we've put at the front, skip it
				if ( uVertex == xBestTri.m_usVertices[0] || uVertex == xBestTri.m_usVertices[1] || uVertex == xBestTri.m_usVertices[2] )
				{
					continue;
				}
				
				// otherwise add it to the new cache 
				puNewCache[uNewCachePosition] = uVertex;
				
				// and update the score to represent this new cache position
				int iScore = g_xScores.GetCacheScore( uNewCachePosition );
				
				u_int uValence = Asura_Maths::Min( m_pxVertices[ uVertex ].m_uNumberOfTrisOutstanding, uMAX_VALENCE_FOR_SCORING );
				iScore += g_xScores.GetValenceScore( uValence );

				m_pxVertices[ uVertex ].m_iScore = iScore;
				++uNewCachePosition;
			}

			// find the new size of the vertex cache, which temporarily
			// may be up to 3 vertices bigger than the max allowed.
			m_uNumberOfVerticesInCache = uNewCachePosition;
		}


		// Update the triangle scores for all triangles using
		// vertices in the cache, and keep track of the best one.
		// This includes triangles for the vertices which are falling
		// out of the cache - otherwise their scores would be inaccurate.
		{
			u_int* puCache = m_apuLRUCache[m_uCurrentCache];
			for ( u_int u=0; u<m_uNumberOfVerticesInCache; ++u )
			{
				Tools_VCO_Vertex& xVertex = m_pxVertices[ puCache[u] ];

				const u_int uNumberOfRemainingTris = xVertex.m_uNumberOfTrisOutstanding;
		
				// Scan through the active tris for each vertex - this is not the same
				// as the full triangle list! If you find the tri we're adding, swap
				// it to the end of the buffer. If you don't find it, well it's at the
				// end of the buffer anyway. This reduces work for future passes.
				for (u_int uTri=0; uTri<uNumberOfRemainingTris; )
				{
					u_int uTriIndex = xVertex.m_puTriangles[ uTri ];

					if ( uTriIndex == uTriToAdd )
					{
						uTriIndex = xVertex.m_puTriangles[ uNumberOfRemainingTris ];
						xVertex.m_puTriangles[uTri] = uTriIndex;
					}
					
					Tools_VCO_Triangle& xTri = m_pxTriangles[uTriIndex];
			
					int iScore;
					iScore  = m_pxVertices[ xTri.m_usVertices[0] ].m_iScore;
					iScore += m_pxVertices[ xTri.m_usVertices[1] ].m_iScore;
					iScore += m_pxVertices[ xTri.m_usVertices[2] ].m_iScore;
					xTri.m_iScore = iScore;

					if ( iScore > iHighestTriangleScore )
					{
						iHighestTriangleScore = iScore;
						uHighestScoringTriangle = uTriIndex;
					}
					
					++uTri;
				}
			}
		}

		// Shrink the cache size down to the max allowed if necessary
		m_uNumberOfVerticesInCache = Asura_Maths::Min( m_uNumberOfVerticesInCache, uVERTEX_CACHE_SIZE );
	}
	delete [] puTriBuffer;
	delete [] m_pxTriangles;
	delete [] m_pxVertices;
	delete [] m_apuLRUCache[0];
	delete [] m_apuLRUCache[1];

#ifdef TOOLS_VCO_PROFILE
	float fTimeTaken = Asura_Timers::TicksToSeconds( Asura_Timers::GetCurTicks() - xStartTime );

	// That's the triangle reordering done. Now reorder the vertices if required
	xStartTime = Asura_Timers::GetCurTicks();
#endif 

	if ( bReorderVertices )
	{
		m_pusVertexOrder = new u_short[ uNumberOfVertices ];
		u_int* puVertexUsage = new u_int[ uNumberOfVertices ];
		const u_int uNOT_USED = 0xffffffff;

		for ( u_int u=0; u<uNumberOfVertices; ++u )
		{
			puVertexUsage[u] = uNOT_USED;
		}

		
		for ( u_int u=0; u<uNumberOfTriangles*3; ++u )
		{
			const u_short uVertex = m_pusIndexList[u];

			if ( puVertexUsage[ uVertex ] == uNOT_USED )
			{
				// New vertex, add it to the list
				puVertexUsage[ uVertex ] = m_uNumberOfUsedVertices;
				m_pusVertexOrder[ m_uNumberOfUsedVertices ] = uVertex;
				++m_uNumberOfUsedVertices;
			}

			m_pusIndexList[u] = static_cast<u_short>(puVertexUsage[ uVertex ]);
		}

		delete [] puVertexUsage;
	}

#ifdef TOOLS_VCO_PROFILE

	float fReorderVertexTimeTaken = Asura_Timers::TicksToSeconds( Asura_Timers::GetCurTicks() - xStartTime );

	// test vs stripifier
	xStartTime = Asura_Timers::GetCurTicks();
	Tools_TriStripper::Initialise();
	u_short* pusStripIndices;
	u_int uNumStripIndices = Tools_TriStripper::CreateStrips( uNumberOfTriangles, pusIndexList, &pusStripIndices );
   	Tools_TriStripper::Shutdown();
	float fStripifyTimeTaken = Asura_Timers::TicksToSeconds( Asura_Timers::GetCurTicks() - xStartTime );
	float fStripifierScore = Tools_VCO_Test( uNumStripIndices, uNumberOfTriangles, pusStripIndices );
	delete [] pusStripIndices;

	Asura_Logfile_Retail(( TOOLS_VCO_LOGFILE,	"****Data****\n"
												"Number of Tris %d\n"
												"Number of Verts %d\n"
												"Cache miss ratio before %f\n"											
												"\n*VCO*\n"
												"Time taken %f s\n"
												"Cache miss ratio after %f\n"
												"Time taken to reorder vertices %f\n"
												"NumberOfVerticesUsed %d\n"
												"\n"
												"*Stripifier*\n"
												"Time taken %f s\n"
												"Cache miss ratio after %f\n"
												"\n",
												uNumberOfTriangles,
												uNumberOfVertices,
												Tools_VCO_Test( uNumberOfTriangles*3, uNumberOfTriangles, pusIndexList ),
												fTimeTaken,
												Tools_VCO_Test( uNumberOfTriangles*3, uNumberOfTriangles, m_pusIndexList ),
												fReorderVertexTimeTaken,
												m_uNumberOfUsedVertices,
												fStripifyTimeTaken,
												fStripifierScore
												));
#endif // #ifdef TOOLS_VCO_PROFILE

}


Tools_VertexCacheOptimiser::~Tools_VertexCacheOptimiser()
{
	delete [] m_pusIndexList;
	delete [] m_pusVertexOrder;
}