/*!
	@file RuEntity_Particle_Grass.cpp

	Copyright (c) 2004-2005 All rights reserved
*/

#include "../../Scene/Particle/RuEntity_Particle_Grass.h"

#pragma unmanaged

// ************************************************************************************************************************************************************

ruRTTI_DEFINE_SUBCLASS(CRuGrassDatabase, IRuObject)
ruHEAP_DEFINE_SUBCLASS(CRuGrassDatabase, "CRuGrassDatabase", "IRuObject")
ruCLASSGUID_DEFINE(CRuGrassDatabase, 0xDEBE1A8D, 0x2E414516, 0xBF2BEDAD, 0xCBC87036)

ruRTTI_DEFINE_SUBCLASS(CRuEntity_Particle_Grass, IRuEntity_Renderable)
ruHEAP_DEFINE_SUBCLASS(CRuEntity_Particle_Grass, "CRuEntity_Particle_Grass", "IRuEntity_Renderable")
ruCLASSGUID_DEFINE(CRuEntity_Particle_Grass, 0x8ADBE19D, 0x7AFA47a2, 0xB55456DD, 0x32A83491)

ruRTTI_DEFINE_SUBCLASS(CRuEntity_Particle_Grass_Optimized, IRuEntity_Renderable)
ruHEAP_DEFINE_SUBCLASS(CRuEntity_Particle_Grass_Optimized, "CRuEntity_Particle_Grass_Optimized", "IRuEntity_Renderable")
ruCLASSGUID_DEFINE(CRuEntity_Particle_Grass_Optimized, 0x88DF0BDB, 0x1E214230, 0x9B64CB77, 0xABB6B8D3)

// ************************************************************************************************************************************************************

CRuGrassDatabase::CRuGrassDatabase()
:	m_isDirty(TRUE)
{
}

CRuGrassDatabase::~CRuGrassDatabase()
{
	for(INT32 i = 0; i < m_textureList.Count(); ++i)
	{
		delete[] m_textureList[i].m_textureName;
		ruSAFE_RELEASE(m_textureList[i].m_texture);
	}
}

BOOL CRuGrassDatabase::SerializeFrom(IRuStream *stream)
{
	CRuGUID classGUID;

	// Read class GUID
	if(RuReadGUID(stream, classGUID) == FALSE)
	{
		return FALSE;
	}

	// Read version
	INT32 version;
	stream->Read(&version, sizeof(INT32));

	// Read number of textures
	INT32 numTextures = m_textureList.Count();
	stream->Read(&numTextures, sizeof(INT32));

	for(INT32 i = 0; i < numTextures; ++i)
	{
		// Append new texture
		m_textureList.Add(TextureDesc());

		// Read length of texture name including NULL
		INT32 textureNameLength;
		stream->Read(&textureNameLength, sizeof(INT32));

		// Read texture name including NULL
		m_textureList[i].m_textureName = ruNEW char [textureNameLength];
		stream->Read(m_textureList[i].m_textureName, sizeof(char) * textureNameLength);

		// Read u subdivision
		stream->Read(&m_textureList[i].m_uSubdivision, sizeof(INT32));

		// Read v subdivision
		stream->Read(&m_textureList[i].m_vSubdivision, sizeof(INT32));

		// Set texture to NULL
		m_textureList[i].m_texture = NULL;
	}

	return TRUE;
}

BOOL CRuGrassDatabase::SerializeTo(IRuStream *stream)
{
	INT32 version = 1;

	// Write class GUID
	stream->Write(GetClassGUID().Data(), GetClassGUID().Size());

	// Write version
	stream->Write(&version, sizeof(INT32));

	// Write number of textures
	INT32 numTextures = m_textureList.Count();
	stream->Write(&numTextures, sizeof(INT32));

	for(INT32 i = 0; i < numTextures; ++i)
	{
		// Write length of texture name including NULL
		INT32 textureNameLength = strlen(m_textureList[i].m_textureName) + 1;
		stream->Write(&textureNameLength, sizeof(INT32));

		// Write texture name including NULL
		stream->Write(m_textureList[i].m_textureName, sizeof(char) * textureNameLength);

		// Write u subdivision
		stream->Write(&m_textureList[i].m_uSubdivision, sizeof(INT32));

		// Write v subdivision
		stream->Write(&m_textureList[i].m_vSubdivision, sizeof(INT32));
	}

	return TRUE;
}

INT32 CRuGrassDatabase::GetNumTextures()
{
	return m_textureList.Count();
}

INT32 CRuGrassDatabase::AppendTexture()
{
	INT32 index = m_textureList.Count();
	m_textureList.Add(TextureDesc());

	m_textureList[index].m_textureName = ruNEW char [1];
	m_textureList[index].m_textureName[0] = NULL;

	m_textureList[index].m_texture = NULL;

	// Mark DB as dirty
	m_isDirty = TRUE;

	return index;
}

const char *CRuGrassDatabase::GetTextureName(INT32 index) const
{
	if(index >= 0 && index < m_textureList.Count())
	{
		return m_textureList[index].m_textureName;
	}

	return "";
}

INT32 CRuGrassDatabase::GetUSubdivision(INT32 index) const
{
	if(index >= 0 && index < m_textureList.Count())
	{
		return m_textureList[index].m_uSubdivision;
	}

	return 1;
}

INT32 CRuGrassDatabase::GetVSubdivision(INT32 index) const
{
	if(index >= 0 && index < m_textureList.Count())
	{
		return m_textureList[index].m_vSubdivision;
	}

	return 1;
}

BOOL CRuGrassDatabase::SetTextureName(INT32 index, const char *textureName)
{
	if(index >= 0 && index < m_textureList.Count())
	{
		// Mark DB as dirty
		m_isDirty = TRUE;

		// Copy texture name
		delete[] m_textureList[index].m_textureName;
		m_textureList[index].m_textureName = ruNEW char [strlen(textureName) + 1];
		strcpy(m_textureList[index].m_textureName, textureName);

		// Release existing texture
		ruSAFE_RELEASE(m_textureList[index].m_texture);

		return TRUE;
	}

	return FALSE;
}

BOOL CRuGrassDatabase::SetUSubdivision(INT32 index, INT32 subdivision)
{
	if(index >= 0 && index < m_textureList.Count())
	{
		// Mark DB as dirty
		m_isDirty = TRUE;

		m_textureList[index].m_uSubdivision = subdivision;

		return TRUE;
	}

	return FALSE;
}

BOOL CRuGrassDatabase::SetVSubdivision(INT32 index, INT32 subdivision)
{
	if(index >= 0 && index < m_textureList.Count())
	{
		// Mark DB as dirty
		m_isDirty = TRUE;

		m_textureList[index].m_vSubdivision = subdivision;

		return TRUE;
	}

	return FALSE;
}

void CRuGrassDatabase::SetDirty(BOOL dirty)
{
	m_isDirty = dirty;
}

BOOL CRuGrassDatabase::IsDirty()
{
	return m_isDirty;
}

IRuTexture *CRuGrassDatabase::GetTexture(INT32 index)
{
	if(index >= 0 && index < m_textureList.Count())
	{
		if(m_textureList[index].m_texture == NULL)
		{
			m_textureList[index].m_texture = g_ruResourceManager->LoadTexture(m_textureList[index].m_textureName);
		}

		return m_textureList[index].m_texture;
	}

	return NULL;
}

// ************************************************************************************************************************************************************

CRuEntity_Particle_Grass::CRuEntity_Particle_Grass()
{
	m_maxParticlesPerBatch = 100;

	m_periodInterval = 2.0f;
	m_t = 0.0f;

	m_grassDB = NULL;

	m_mesh = ruNEW CRuMesh();
	m_mesh->Initialize(ruPRIMTYPE_TRIANGLELIST, 12 * m_maxParticlesPerBatch, 6 * m_maxParticlesPerBatch, ruVERTEXFORMAT_POSITION | ruVERTEXFORMAT_DIFFUSE, 1);

	CRuVector3 *position = static_cast<CRuMorphTarget *>(m_mesh->GetMorphTarget(0))->GetPosition();
	DWORD *diffuse = static_cast<CRuMorphTarget *>(m_mesh->GetMorphTarget(0))->GetDiffuse();
	UINT16 *indices = m_mesh->GetIndices();

	CRuVector3 v(0.0f, 0.0f, -1.0f);
	CRuQuaternion e0Quat, e1Quat;
	e0Quat.FromAngleAxis(CRuVector3(0.0f, 1.0f, 0.0f), 0.523599f);
	e1Quat.FromAngleAxis(CRuVector3(0.0f, 1.0f, 0.0f), -0.523599f);

	CRuVector3 e0 = v * e0Quat.GetMatrix();
	CRuVector3 e1 = v * e1Quat.GetMatrix();

	REAL edgeLength = 1.0f;
	REAL hingeRatio = 0.2f;
	REAL halfHingeRatio = hingeRatio / 2.0f;
	REAL triEdgeLength = edgeLength * (1.0f - hingeRatio);
	REAL triHeight = sqrt(triEdgeLength * triEdgeLength - (triEdgeLength / 2.0f) * (triEdgeLength / 2.0f));
	REAL triCentroidOffset = triEdgeLength / sqrt(3.0f);

	CRuVector3 origin_y0(0.0f, 0.0f, triCentroidOffset);

/*
	Triangle Arrangement
	--------------------

	         v0    v2
	           \  /
	            \/
	            /\
	  face 1 < /  \ > face 0
        v4 ___/____\___ v5
	         /      \
			/        \
		  v3    ^     v1
	          face 2
*/

	for(INT32 i = 0, vIdx = 0, fIdx = 0; i < m_maxParticlesPerBatch; ++i)
	{
		// v0_y0
		diffuse[vIdx] = (i << 24) | (0xFF << 16) | (0xFF << 8);
		position[vIdx] = origin_y0 + e0 * -(edgeLength * halfHingeRatio);
		++vIdx;

		// v0_y1
		diffuse[vIdx] = (i << 24) | (0xFF << 16) | (0x00 << 8) | 0xFF;
		position[vIdx].Set(position[vIdx - 1].x, edgeLength, position[vIdx - 1].z);
		++vIdx;

		// v1_y0
		diffuse[vIdx] = (i << 24) | (0x00 << 16) | (0xFF << 8);
		position[vIdx] = position[vIdx - 2] + e0 * edgeLength;
		++vIdx;

		// v1_y1
		diffuse[vIdx] = (i << 24) | (0x00 << 16) | (0x00 << 8) | 0xFF;
		position[vIdx].Set(position[vIdx - 1].x, edgeLength, position[vIdx - 1].z);
		++vIdx;

		// v2_y0
		diffuse[vIdx] = (i << 24) | (0x00 << 16) | (0xFF << 8);
		position[vIdx] = origin_y0 + e1 * -(edgeLength * halfHingeRatio);
		++vIdx;

		// v2_y1
		diffuse[vIdx] = (i << 24) | (0x00 << 16) | (0x00 << 8) | 0xFF;
		position[vIdx].Set(position[vIdx - 1].x, edgeLength, position[vIdx - 1].z);
		++vIdx;

		// v3_y0
		diffuse[vIdx] = (i << 24) | (0xFF << 16) | (0xFF << 8);
		position[vIdx] = position[vIdx - 2] + e1 * edgeLength;
		++vIdx;

		// v3_y1
		diffuse[vIdx] = (i << 24) | (0xFF << 16) | (0x00 << 8) | 0xFF;
		position[vIdx].Set(position[vIdx - 1].x, edgeLength, position[vIdx - 1].z);
		++vIdx;

		// v4_y0
		diffuse[vIdx] = (i << 24) | (0x00 << 16) | (0xFF << 8);
		position[vIdx].Set(-edgeLength / 2.0f, 0.0f, -(triHeight - triCentroidOffset));
		++vIdx;

		// v4_y1
		diffuse[vIdx] = (i << 24) | (0x00 << 16) | (0x00 << 8) | 0xFF;
		position[vIdx].Set(position[vIdx - 1].x, edgeLength, position[vIdx - 1].z);
		++vIdx;

		// v5_y0
		diffuse[vIdx] = (i << 24) | (0xFF << 16) | (0xFF << 8);
		position[vIdx].Set(edgeLength / 2.0f, 0.0f, -(triHeight - triCentroidOffset));
		++vIdx;

		// v5_y1
		diffuse[vIdx] = (i << 24) | (0xFF << 16) | (0x00 << 8) | 0xFF;
		position[vIdx].Set(position[vIdx - 1].x, edgeLength, position[vIdx - 1].z);
		++vIdx;

		INT32 vertexOffset = i * 12;

		indices[fIdx++] = vertexOffset + 0;
		indices[fIdx++] = vertexOffset + 2;
		indices[fIdx++] = vertexOffset + 3;

		indices[fIdx++] = vertexOffset + 0;
		indices[fIdx++] = vertexOffset + 3;
		indices[fIdx++] = vertexOffset + 1;

		indices[fIdx++] = vertexOffset + 0 + 4;
		indices[fIdx++] = vertexOffset + 1 + 4;
		indices[fIdx++] = vertexOffset + 2 + 4;

		indices[fIdx++] = vertexOffset + 1 + 4;
		indices[fIdx++] = vertexOffset + 3 + 4;
		indices[fIdx++] = vertexOffset + 2 + 4;

		indices[fIdx++] = vertexOffset + 0 + 8;
		indices[fIdx++] = vertexOffset + 1 + 8;
		indices[fIdx++] = vertexOffset + 2 + 8;

		indices[fIdx++] = vertexOffset + 1 + 8;
		indices[fIdx++] = vertexOffset + 3 + 8;
		indices[fIdx++] = vertexOffset + 2 + 8;
	}
}

CRuEntity_Particle_Grass::~CRuEntity_Particle_Grass()
{
	// Clear all batches
	ClearBatches();

	ruSAFE_RELEASE(m_grassDB);
	ruSAFE_RELEASE(m_mesh);

	// Release resources used by batch structures
	while(m_freeBatchDescStack.IsEmpty() == FALSE)
	{
		delete m_freeBatchDescStack.Pop();
	}
}

CRuEntity *CRuEntity_Particle_Grass::Clone(CRuEntity *clonedEntity)
{
	// This system cannot be cloned
	return NULL;
}

BOOL CRuEntity_Particle_Grass::ResetStates()
{
	return TRUE;
}

BOOL CRuEntity_Particle_Grass::Update(REAL elapsedTime)
{
	// Update t
	m_t += (elapsedTime / m_periodInterval) * ruPI;

	// Cycle t in [0, 2PI]
	if(m_t > ruPI * 2.0f)
	{
		m_t = fmod(m_t, ruPI * 2.0f);
	}

	// Update t in all batches
	for(INT32 i = 0; i < m_batches.Count(); ++i)
	{
		m_batches[i]->m_vsConstants[2] = m_t;
	}

	return TRUE;
}

INT32 CRuEntity_Particle_Grass::GetNumMeshes() const
{
	return m_batches.Count();
}

BOOL CRuEntity_Particle_Grass::GetMesh(INT32 meshIndex, IRuMesh **meshOut, IRuMaterial **materialOut)
{
	if(meshIndex >= 0 && meshIndex < m_batches.Count())
	{
		*meshOut = m_batches[meshIndex]->m_mesh;
		*materialOut = m_batches[meshIndex]->m_material;

		return TRUE;
	}

	return FALSE;
}

void CRuEntity_Particle_Grass::SetGrassDatabase(CRuGrassDatabase *grassDB)
{
	grassDB->AddRef();
	ruSAFE_RELEASE(m_grassDB);
	m_grassDB = grassDB;
}

void CRuEntity_Particle_Grass::SetParticleList(const CRuArrayList<CRuParticle_Grass> &particleList, BOOL calculateEntityBounds)
{
	// Clear existing batches
	ClearBatches();

	// If requested, calculate the entity bounds for this grass particle system
	if(calculateEntityBounds)
	{
		// TODO: Finish me
	}

	// Sort particles by model style, then by texture ID
	for(INT32 i = 0; i < particleList.Count(); ++i)
	{
		m_sortCriterias[0].Add(particleList[i].m_modelStyle);
		m_sortCriterias[1].Add(particleList[i].m_textureIndex);
	}

	m_radixSorter.Sort((UINT32 *) m_sortCriterias[1].GetArray(), m_sortCriterias[1].Count(), FALSE, FALSE);
	m_radixSorter.Sort((UINT32 *) m_sortCriterias[0].GetArray(), m_sortCriterias[0].Count(), FALSE, TRUE);

	// Iterate through all particles and build batches
	BatchDesc *batch = NULL;
	UINT8 currentModelStyle = 0xFF;
	UINT16 currentTextureIndex = 0xFFFF;
	UINT32 *sortedIndices = m_radixSorter.GetSortedIndices();
	INT32 particlesThisBatch = 0;
	INT32 currentTextureWidth = 0;
	INT32 currentTextureHeight = 0;
	for(INT32 i = 0, j = 24; i < particleList.Count(); ++i, ++particlesThisBatch)
	{
		// Store reference to the particle
		const CRuParticle_Grass &particle = particleList[sortedIndices[i]];

		// Detect if there is a need for a new batch
		if(particle.m_modelStyle != currentModelStyle || particle.m_textureIndex != currentTextureIndex || particlesThisBatch >= m_maxParticlesPerBatch)
		{
			// Set number of particles for the previous batch if applicable
			if(batch)
			{
				batch->m_material->GetParameterBlock()->SetParameter(ruPARAMTYPE_GEOINSTANCE_S_COUNT, particlesThisBatch);

				// Setup rendering batch
				batch->m_mesh->SetProxiedMesh(m_mesh, m_mesh->AddBatch(0, particlesThisBatch * 6));
			}

			// Get a free batch descriptor
			if(m_freeBatchDescStack.IsEmpty())
			{
				batch = ruNEW BatchDesc(m_maxParticlesPerBatch);
			}
			else
			{
				batch = m_freeBatchDescStack.Pop();
			}

			// Select model

			// Select texture
			IRuTexture *texture = m_grassDB->GetTexture(particle.m_textureIndex);

			if(texture)
			{
				batch->m_material->SetTexture(ruTEXCHANNEL_DIFFUSEMAP, texture);

				currentTextureWidth = texture->GetLevelWidth(0);
				currentTextureHeight = texture->GetLevelHeight(0);

				// Setup header constants
				batch->m_vsConstants[0] = (REAL) m_grassDB->GetUSubdivision(particle.m_textureIndex) / texture->GetLevelWidth(0);
				batch->m_vsConstants[1] = (REAL) m_grassDB->GetVSubdivision(particle.m_textureIndex) / texture->GetLevelHeight(0);
				batch->m_vsConstants[2] = m_t;
				batch->m_vsConstants[3] = 0.0f;
			}
			else
			{
				batch->m_material->SetTexture(ruTEXCHANNEL_DIFFUSEMAP, NULL);

				// Setup header constants
				batch->m_vsConstants[0] = 0.0f;
				batch->m_vsConstants[1] = 0.0f;
				batch->m_vsConstants[2] = 0.0f;
				batch->m_vsConstants[3] = 0.0f;
			}

			batch->m_vsConstants[4] = 256.0f;						// diffuse color scale factor - so we can get a proper integer index
			batch->m_vsConstants[5] = 2.0f;							// 2 constant rows per instance dataset
			batch->m_vsConstants[6] = 33.0f;						// Instance dataset begins at c33
//			batch->m_vsConstants[7] = 1.0f / 480.0f;				// reciprocal fade distance
			batch->m_vsConstants[7] = 1.0f / 900.0f;				// reciprocal fade distance

			batch->m_vsConstants[8] = 0.0f;							// normal x
			batch->m_vsConstants[9] = 1.0f;							// normal y
			batch->m_vsConstants[10] = 0.0f;						// normal z
			batch->m_vsConstants[11] = 0.0f;						// unused

			batch->m_vsConstants[12] =  3.14159265f;				// sin/cos range
			batch->m_vsConstants[13] =  0.50000000f;
			batch->m_vsConstants[14] =  6.28318531f;
			batch->m_vsConstants[15] =  0.15915494f;

			batch->m_vsConstants[16] =  1.00000000f;
			batch->m_vsConstants[17] = -0.50000000f;
			batch->m_vsConstants[18] =  0.04166667f;
			batch->m_vsConstants[19] = -0.00138889f;

			batch->m_vsConstants[20] =  1.00000000f;
			batch->m_vsConstants[21] = -0.16666667f;
			batch->m_vsConstants[22] =  0.00833333f;
			batch->m_vsConstants[23] = -0.00019841f;

			currentModelStyle = particle.m_modelStyle;
			currentTextureIndex = particle.m_textureIndex;

			// Reset constant index
			particlesThisBatch = 0;
			j = 24;

			// Add batch to batch list
			m_batches.Add(batch);
		}

		INT32 subTexPerRow = max(1, currentTextureWidth / m_grassDB->GetUSubdivision(particle.m_textureIndex));

		// Setup constant data for this particle
		batch->m_vsConstants[j++] = particle.m_position.x;												// position x
		batch->m_vsConstants[j++] = particle.m_position.y;												// position y
		batch->m_vsConstants[j++] = particle.m_position.z;												// position z
		batch->m_vsConstants[j++] = particle.m_scale;													// scale

		batch->m_vsConstants[j++] = static_cast<REAL>(particle.m_subTextureIndex % subTexPerRow);		// u index
		batch->m_vsConstants[j++] = static_cast<REAL>(particle.m_subTextureIndex / subTexPerRow);		// v index
		batch->m_vsConstants[j++] = (g_mtRand.GenerateFloat() - 0.5f) * particle.m_swayMagnitude;		// x max displacement
		batch->m_vsConstants[j++] = (g_mtRand.GenerateFloat() - 0.5f) * particle.m_swayMagnitude;		// z max displacement
	}

	if(batch)
	{
		batch->m_material->GetParameterBlock()->SetParameter(ruPARAMTYPE_GEOINSTANCE_S_COUNT, particlesThisBatch);

		// Setup rendering batch
		batch->m_mesh->SetProxiedMesh(m_mesh, m_mesh->AddBatch(0, particlesThisBatch * 6));
	}
}

void CRuEntity_Particle_Grass::ClearBatches()
{
	// Push all used batches onto stack
	for(INT32 i = 0; i < m_batches.Count(); ++i)
	{
		m_freeBatchDescStack.Push(m_batches[i]);
	}

	// Clear batches
	m_batches.Clear();

	// Clear batches
	m_mesh->ClearBatches();
}

// ************************************************************************************************************************************************************

CRuEntity_Particle_Grass_Optimized::CRuEntity_Particle_Grass_Optimized()
{
	m_maxParticlesPerBatch = 2000;

	m_periodInterval = 2.0f;
	m_t = 0.0f;

	m_grassDB = NULL;
}

CRuEntity_Particle_Grass_Optimized::~CRuEntity_Particle_Grass_Optimized()
{
	// Clear all batches
	ClearBatches();

	ruSAFE_RELEASE(m_grassDB);
}

CRuEntity *CRuEntity_Particle_Grass_Optimized::Clone(CRuEntity *clonedEntity)
{
	// This system cannot be cloned
	return NULL;
}

BOOL CRuEntity_Particle_Grass_Optimized::ResetStates()
{
	return TRUE;
}

BOOL CRuEntity_Particle_Grass_Optimized::Update(REAL elapsedTime)
{
	// Update t
	m_t += (elapsedTime / m_periodInterval) * ruPI;

	// Cycle t in [0, 2PI]
	if(m_t > ruPI * 2.0f)
	{
		m_t = fmod(m_t, ruPI * 2.0f);
	}

	for(INT32 i = 0; i < m_vsConstants.Count(); ++i)
	{
		m_vsConstants[i][2] = m_t;
	}

	return TRUE;
}

INT32 CRuEntity_Particle_Grass_Optimized::GetNumMeshes() const
{
	return m_meshes.Count();
}

BOOL CRuEntity_Particle_Grass_Optimized::GetMesh(INT32 meshIndex, IRuMesh **meshOut, IRuMaterial **materialOut)
{
	if(meshIndex >= 0 && meshIndex < m_meshes.Count())
	{
		*meshOut = m_meshes[meshIndex];
		*materialOut = m_materials[meshIndex];

		return TRUE;
	}

	return FALSE;
}

void CRuEntity_Particle_Grass_Optimized::SetGrassDatabase(CRuGrassDatabase *grassDB)
{
	grassDB->AddRef();
	ruSAFE_RELEASE(m_grassDB);
	m_grassDB = grassDB;
}

void CRuEntity_Particle_Grass_Optimized::SetParticleList(const CRuArrayList<CRuParticle_Grass> &particleList, BOOL calculateEntityBounds)
{
	// Clear existing batches
	ClearBatches();

	// If requested, calculate the entity bounds for this grass particle system
	if(calculateEntityBounds)
	{
		// TODO: Finish me
	}

	// Sort particles by model style, then by texture ID
	for(INT32 i = 0; i < particleList.Count(); ++i)
	{
		m_sortCriterias[0].Add(particleList[i].m_modelStyle);
		m_sortCriterias[1].Add(particleList[i].m_textureIndex);
	}

	m_radixSorter.Sort((UINT32 *) m_sortCriterias[1].GetArray(), m_sortCriterias[1].Count(), FALSE, FALSE);
	m_radixSorter.Sort((UINT32 *) m_sortCriterias[0].GetArray(), m_sortCriterias[0].Count(), FALSE, TRUE);

	// Iterate through all particles and build batches
	UINT32 *sortedIndices = m_radixSorter.GetSortedIndices();
	INT32 particlesThisBatch = 0;
	INT32 currentTextureWidth = 0;
	INT32 currentTextureHeight = 0;
	for(INT32 i = 0; i < particleList.Count(); )
	{
		// Store reference to start particle
		INT32 startIndex = i, endIndex = i;
		const CRuParticle_Grass &startParticle = particleList[sortedIndices[startIndex]];

		UINT8 currentModelStyle = particleList[sortedIndices[startIndex]].m_modelStyle;
		UINT16 currentTextureIndex = particleList[sortedIndices[startIndex]].m_textureIndex;

		// Find the end of the current batch
		while(particleList[sortedIndices[endIndex]].m_modelStyle == currentModelStyle && particleList[sortedIndices[endIndex]].m_textureIndex == currentTextureIndex && (endIndex - startIndex) <= m_maxParticlesPerBatch)
		{
			++endIndex;

			if(endIndex >= particleList.Count())
				break;
		}

		// Select model

		// Build basic material and mesh objects
		CRuMesh *mesh = ruNEW CRuMesh();
		CRuMaterial *material = ruNEW CRuMaterial();
		REAL *vsConstants = ruNEW REAL [24];

		material->SetShader(g_ruResourceManager->GetShader("ruSHADER_PARTICLE_GRASS_OPTIMIZED"));
		material->GetParameterBlock()->SetParameter(ruPARAMTYPE_GEOINSTANCE_S_COUNT, 0);
		material->GetParameterBlock()->SetParameter(ruPARAMTYPE_GEOINSTANCE_S_DATA, (DWORD) vsConstants);

		INT32 numParticlesThisBatch = endIndex - startIndex;
		mesh->Initialize(ruPRIMTYPE_TRIANGLELIST, 12 * numParticlesThisBatch, 6 * numParticlesThisBatch, ruVERTEXFORMAT_POSITION | ruVERTEXFORMAT_DIFFUSE | ruVERTEXFORMAT_BLENDWEIGHT, 1);

		// Select texture
		IRuTexture *texture = m_grassDB->GetTexture(startParticle.m_textureIndex);

		if(texture)
		{
			material->SetTexture(ruTEXCHANNEL_DIFFUSEMAP, texture);

			currentTextureWidth = texture->GetLevelWidth(0);
			currentTextureHeight = texture->GetLevelHeight(0);

			// Setup header constants
			vsConstants[0] = (REAL) m_grassDB->GetUSubdivision(startParticle.m_textureIndex) / texture->GetLevelWidth(0);
			vsConstants[1] = (REAL) m_grassDB->GetVSubdivision(startParticle.m_textureIndex) / texture->GetLevelHeight(0);
			vsConstants[2] = m_t;
			vsConstants[3] = 0.0f;
		}
		else
		{
			material->SetTexture(ruTEXCHANNEL_DIFFUSEMAP, NULL);

			// Setup header constants
			vsConstants[0] = 0.0f;
			vsConstants[1] = 0.0f;
			vsConstants[2] = 0.0f;
			vsConstants[3] = 0.0f;
		}

		vsConstants[4] = 256.0f;						// diffuse color scale factor - so we can get a proper integer index
		vsConstants[5] = 2.0f;						// 2 constant rows per instance dataset
		vsConstants[6] = 33.0f;						// Instance dataset begins at c33
		vsConstants[7] = 1.0f / 480.0f;				// reciprocal fade distance

		vsConstants[8] = 0.0f;						// normal x
		vsConstants[9] = 1.0f;						// normal y
		vsConstants[10] = 0.0f;						// normal z
		vsConstants[11] = 0.0f;						// unused

		vsConstants[12] =  3.14159265f;				// sin/cos range
		vsConstants[13] =  0.50000000f;
		vsConstants[14] =  6.28318531f;
		vsConstants[15] =  0.15915494f;

		vsConstants[16] =  1.00000000f;
		vsConstants[17] = -0.50000000f;
		vsConstants[18] =  0.04166667f;
		vsConstants[19] = -0.00138889f;

		vsConstants[20] =  1.00000000f;
		vsConstants[21] = -0.16666667f;
		vsConstants[22] =  0.00833333f;
		vsConstants[23] = -0.00019841f;

		FillVertexData(mesh, numParticlesThisBatch);

		CRuVector3 *position = static_cast<CRuMorphTarget *>(mesh->GetMorphTarget(0))->GetPosition();
		REAL *grassProperties = static_cast<CRuMorphTarget *>(mesh->GetMorphTarget(0))->GetBlendWeight();

		CRuMatrix4x4 scaleTransform;
		CRuMatrix4x4 translateTransform;
		INT32 subTexPerRow = max(1, currentTextureWidth / m_grassDB->GetUSubdivision(startParticle.m_textureIndex));
		for(INT32 j = 0, k = startIndex, l = 0, m = 0; j < numParticlesThisBatch; ++j, ++k)
		{
			// Store reference to the particle
			const CRuParticle_Grass &particle = particleList[sortedIndices[k]];

			scaleTransform.SetToScaling(particle.m_scale, particle.m_scale, particle.m_scale);
			translateTransform.SetToTranslation(particle.m_position.x, particle.m_position.y, particle.m_position.z);

			for(INT32 n = 0; n < 12; ++m, ++n)
			{
				// Scale and translate the vertex
				scaleTransform.TransformPoint(position[m]);
				translateTransform.TransformPoint(position[m]);

				// Set grass properties for the vertex
				grassProperties[l++] = static_cast<REAL>(particle.m_subTextureIndex % subTexPerRow);		// u index
				grassProperties[l++] = static_cast<REAL>(particle.m_subTextureIndex / subTexPerRow);		// v index
				grassProperties[l++] = (g_mtRand.GenerateFloat() - 0.5f) * particle.m_swayMagnitude;		// x max displacement
				grassProperties[l++] = (g_mtRand.GenerateFloat() - 0.5f) * particle.m_swayMagnitude;		// z max displacement
			}
		}

		m_meshes.Add(mesh);
		m_materials.Add(material);
		m_vsConstants.Add(vsConstants);

		i += numParticlesThisBatch;
	}
}

void CRuEntity_Particle_Grass_Optimized::FillVertexData(CRuMesh *mesh, INT32 numParticles)
{
	CRuVector3 *position = static_cast<CRuMorphTarget *>(mesh->GetMorphTarget(0))->GetPosition();
	DWORD *diffuse = static_cast<CRuMorphTarget *>(mesh->GetMorphTarget(0))->GetDiffuse();
	UINT16 *indices = mesh->GetIndices();

	CRuVector3 v(0.0f, 0.0f, -1.0f);
	CRuQuaternion e0Quat, e1Quat;
	e0Quat.FromAngleAxis(CRuVector3(0.0f, 1.0f, 0.0f), 0.523599f);
	e1Quat.FromAngleAxis(CRuVector3(0.0f, 1.0f, 0.0f), -0.523599f);

	CRuVector3 e0 = v * e0Quat.GetMatrix();
	CRuVector3 e1 = v * e1Quat.GetMatrix();

	REAL edgeLength = 1.0f;
	REAL hingeRatio = 0.2f;
	REAL halfHingeRatio = hingeRatio / 2.0f;
	REAL triEdgeLength = edgeLength * (1.0f - hingeRatio);
	REAL triHeight = sqrt(triEdgeLength * triEdgeLength - (triEdgeLength / 2.0f) * (triEdgeLength / 2.0f));
	REAL triCentroidOffset = triEdgeLength / sqrt(3.0f);

	CRuVector3 origin_y0(0.0f, 0.0f, triCentroidOffset);

/*
	Triangle Arrangement
	--------------------

	         v0    v2
	           \  /
	            \/
	            /\
	  face 1 < /  \ > face 0
        v4 ___/____\___ v5
	         /      \
			/        \
		  v3    ^     v1
	          face 2
*/

	for(INT32 i = 0, vIdx = 0, fIdx = 0; i < numParticles; ++i)
	{
		// v0_y0
		diffuse[vIdx] = (i << 24) | (0xFF << 16) | (0xFF << 8);
		position[vIdx] = origin_y0 + e0 * -(edgeLength * halfHingeRatio);
		++vIdx;

		// v0_y1
		diffuse[vIdx] = (i << 24) | (0xFF << 16) | (0x00 << 8) | 0xFF;
		position[vIdx].Set(position[vIdx - 1].x, edgeLength, position[vIdx - 1].z);
		++vIdx;

		// v1_y0
		diffuse[vIdx] = (i << 24) | (0x00 << 16) | (0xFF << 8);
		position[vIdx] = position[vIdx - 2] + e0 * edgeLength;
		++vIdx;

		// v1_y1
		diffuse[vIdx] = (i << 24) | (0x00 << 16) | (0x00 << 8) | 0xFF;
		position[vIdx].Set(position[vIdx - 1].x, edgeLength, position[vIdx - 1].z);
		++vIdx;

		// v2_y0
		diffuse[vIdx] = (i << 24) | (0x00 << 16) | (0xFF << 8);
		position[vIdx] = origin_y0 + e1 * -(edgeLength * halfHingeRatio);
		++vIdx;

		// v2_y1
		diffuse[vIdx] = (i << 24) | (0x00 << 16) | (0x00 << 8) | 0xFF;
		position[vIdx].Set(position[vIdx - 1].x, edgeLength, position[vIdx - 1].z);
		++vIdx;

		// v3_y0
		diffuse[vIdx] = (i << 24) | (0xFF << 16) | (0xFF << 8);
		position[vIdx] = position[vIdx - 2] + e1 * edgeLength;
		++vIdx;

		// v3_y1
		diffuse[vIdx] = (i << 24) | (0xFF << 16) | (0x00 << 8) | 0xFF;
		position[vIdx].Set(position[vIdx - 1].x, edgeLength, position[vIdx - 1].z);
		++vIdx;

		// v4_y0
		diffuse[vIdx] = (i << 24) | (0x00 << 16) | (0xFF << 8);
		position[vIdx].Set(-edgeLength / 2.0f, 0.0f, -(triHeight - triCentroidOffset));
		++vIdx;

		// v4_y1
		diffuse[vIdx] = (i << 24) | (0x00 << 16) | (0x00 << 8) | 0xFF;
		position[vIdx].Set(position[vIdx - 1].x, edgeLength, position[vIdx - 1].z);
		++vIdx;

		// v5_y0
		diffuse[vIdx] = (i << 24) | (0xFF << 16) | (0xFF << 8);
		position[vIdx].Set(edgeLength / 2.0f, 0.0f, -(triHeight - triCentroidOffset));
		++vIdx;

		// v5_y1
		diffuse[vIdx] = (i << 24) | (0xFF << 16) | (0x00 << 8) | 0xFF;
		position[vIdx].Set(position[vIdx - 1].x, edgeLength, position[vIdx - 1].z);
		++vIdx;

		INT32 vertexOffset = i * 12;

		indices[fIdx++] = vertexOffset + 0;
		indices[fIdx++] = vertexOffset + 2;
		indices[fIdx++] = vertexOffset + 3;

		indices[fIdx++] = vertexOffset + 0;
		indices[fIdx++] = vertexOffset + 3;
		indices[fIdx++] = vertexOffset + 1;

		indices[fIdx++] = vertexOffset + 0 + 4;
		indices[fIdx++] = vertexOffset + 1 + 4;
		indices[fIdx++] = vertexOffset + 2 + 4;

		indices[fIdx++] = vertexOffset + 1 + 4;
		indices[fIdx++] = vertexOffset + 3 + 4;
		indices[fIdx++] = vertexOffset + 2 + 4;

		indices[fIdx++] = vertexOffset + 0 + 8;
		indices[fIdx++] = vertexOffset + 1 + 8;
		indices[fIdx++] = vertexOffset + 2 + 8;

		indices[fIdx++] = vertexOffset + 1 + 8;
		indices[fIdx++] = vertexOffset + 3 + 8;
		indices[fIdx++] = vertexOffset + 2 + 8;
	}
}

void CRuEntity_Particle_Grass_Optimized::ClearBatches()
{
	for(INT32 i = 0; i < m_meshes.Count(); ++i)
	{
		ruSAFE_RELEASE(m_meshes[i]);
	}
	m_meshes.Clear();

	for(INT32 i = 0; i < m_materials.Count(); ++i)
	{
		ruSAFE_RELEASE(m_materials[i]);
	}
	m_materials.Clear();

	for(INT32 i = 0; i < m_vsConstants.Count(); ++i)
	{
		delete[] m_vsConstants[i];
	}
	m_vsConstants.Clear();
}

// ************************************************************************************************************************************************************

#pragma managed
