/**
*
* \file Tools_SubdividedMesh.cpp
*
* Created by Kevin Lea - 27/05/2002 10:09:36
*
* Copyright (C) 2002 Rebellion, All Rights Reserved.
*
* \brief
*
**/

#include "Core/Asura.h"

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

// Asura headers
#include "Debugging/Asura_Assert.h"
#include "Light/Asura_Light.h"
#include "Mesh/Asura_Mesh.h"
#include "Rendering/Asura_Surface.h"
#include "Rendering/Asura_Bicubic_Patch.h"
#include "Rendering/Asura_Module.h"
#include "Rendering/Asura_PatchSubdivision.h"

// Tools headers
#include "Load&Save/LevelExport/Tools_Level_Export.h"
#include "Materials/Tools_MaterialResponse_System.h"
#include "Misc/Tools_HashTable.h"
#include "Smoothing/Tools_ModuleSmoothing.h"

static Asura_Bicubic_Patch patch;
bool Tools_SubdividedMesh::s_bRecalculatePrelighting = false;

const u_int Tools_SubdividedMesh_Vertex::s_uDefaultColourTolerance = 2;
u_int Tools_SubdividedMesh_Vertex::s_uColourTolerance = 2;

//material response IDs for a single polygon
class Tools_MaterialResponseIDs
{
public :
	Asura_Hash_ID m_auID[TOOLS_NUM_MATERIALRESPONSE_PER_POLY];

	bool operator == (const Tools_MaterialResponseIDs& xOther) const
	{
		for(int i=0;i<TOOLS_NUM_MATERIALRESPONSE_PER_POLY;i++)
		{
			if(m_auID[i] != xOther.m_auID[i]) return false;
			return true;
		}
	}
	bool operator != (const Tools_MaterialResponseIDs& xOther) const
	{
		return !((*this) == xOther);
	}

};


Tools_SubdividedMesh::Tools_SubdividedMesh( Asura_Mesh* mesh, Asura_Vector_3& position, bool subdivide, bool bOnlyRenderablePolys, bool bMakeDoubleSidedPolys )
{
	m_pxMesh = mesh;
	m_xPosition = position;


	Asura_PatchSubdivision::FindPointsNearModule(mesh,position);
		
	if (!mesh->AreNormalsValid())
	{
		mesh->CreateNormals();
	}

	Asura_Surface_Mesh* surfaceMesh = Asura_Surface_Mesh_System::GetSurfaceMesh(mesh->Index);
	if (!surfaceMesh->SurfaceDataValid)
	{
		Asura_Surface_Mesh_System::ProcessMeshIntoSurfaces(*mesh,position);
		Asura_Assert(surfaceMesh->NumberOfSurfaces==mesh->NumberOfPolygons,"");
	}

	CreatePackets( mesh, subdivide, bOnlyRenderablePolys, bMakeDoubleSidedPolys );
}


Tools_SubdividedMesh::Tools_SubdividedMesh( int iModuleIndex, bool bOnlyRenderablePolys, bool bMakeDoubleSidedPolys, bool bSubdivide /* = true */, const u_int uPolygonFlagsToIgnor /*= AsuraPolygonFlag_Water|AsuraPolygonFlag_DontExport*/)
{
	Asura_Mesh* pxMesh = Asura_Module_System::GetMeshForModule(iModuleIndex);
	Asura_Assert(pxMesh,"");

	Asura_Vector_3 xPosition;
	Asura_Module_System::GetPositionOfModule(iModuleIndex,xPosition);

	Asura_PatchSubdivision::FindPointsNearModule(pxMesh,xPosition);

	m_pxMesh = pxMesh;
	m_xPosition = xPosition;


		
	if(!pxMesh->AreNormalsValid() || !pxMesh->m_bSmoothedAcrossModules)
	{
	 	Tools_ModuleSmoothing::CalculateNormals(iModuleIndex);
	}

	Asura_Surface_Mesh* surfaceMesh = Asura_Surface_Mesh_System::GetSurfaceMesh(pxMesh->Index);
	if (!surfaceMesh->SurfaceDataValid)
	{
		Asura_Surface_Mesh_System::ProcessModuleMeshIntoSurfaces(iModuleIndex);
	}

	CreatePackets( pxMesh, bSubdivide, bOnlyRenderablePolys, bMakeDoubleSidedPolys, uPolygonFlagsToIgnor);
}

bool Tools_SubdividedMesh::CreatePackets( Asura_Mesh* pxMesh, bool bSubdivide, bool bOnlyRenderablePolys, bool bMakeDoubleSidedPolys, const u_int uPolygonFlagsToIgnor /*= AsuraPolygonFlag_Water|AsuraPolygonFlag_DontExport*/ )
{
	Asura_Surface_Mesh* surfaceMesh = Asura_Surface_Mesh_System::GetSurfaceMesh(pxMesh->Index);

	//CalculatePrelighting(pxMesh,position);
	this->Packets = NULL;
	NumberOfPackets = 0;
	TotalVertices = 0;
	TotalTris = 0;

	int totalVertices = 0;
	int totalIndices = 0;

	const int iMaxVertices = 65536;
	const int iMaxIndices = 65536*3;

	Tools_SubdividedMesh_Vertex*	tempVertexArray = new Tools_SubdividedMesh_Vertex[iMaxVertices];
	int*							tempIndexArray = new int[iMaxIndices];
	
	// DLH - If the system runs out of memory during export then fail.
	if( NULL == tempVertexArray || NULL == tempIndexArray)
	{
		delete[] tempVertexArray;
		delete[] tempIndexArray;
		
		return( false);
	}

	#if defined ASURA_USE_MATERIAL_RESPONSE_SYSTEM && !defined ASURA_MATERIAL_RESPONSE_CHARACTERS_ONLY
		Tools_MaterialResponseIDs* pxTempMaterialResponseHashIDArray = new Tools_MaterialResponseIDs[ iMaxIndices / 3 ];
		Tools_MaterialResponseIDs* pxMaterialResponseHashIDs = new Tools_MaterialResponseIDs[ surfaceMesh->NumberOfSurfaces ];
	#else
		int* piTempMaterialIndexArray = new int[iMaxIndices/3];
		int* piMaterialID = new int[surfaceMesh->NumberOfSurfaces]; // worse case scenario ;)
	#endif

	int* numberOfTrisInPacket = new int[surfaceMesh->NumberOfSurfaces];

	Asura_Assert(surfaceMesh->NumberOfSurfaces==pxMesh->NumberOfPolygons,"");

//    const int iFlagsToCheck = ( AsuraPolygonFlag_DontExport | AsuraPolygonFlag_Water | (bOnlyRenderablePolys ? AsuraPolygonFlag_DontRender : 0) );
    const int iFlagsToCheck = ( uPolygonFlagsToIgnor | (bOnlyRenderablePolys ? AsuraPolygonFlag_DontRender : 0) );

	bool bDone = false;
	int iMaxDetail = bSubdivide ? MAXIMUM_POSSIBLE_BICUBIC_ORDER : 0;
	for(int iDetail = iMaxDetail;iDetail>=0 && !bDone;iDetail--)
	{
		patch.SetMaxDetailLevel(iDetail);
		totalVertices = 0;
		totalIndices = 0;
		NumberOfPackets = 0;
		
		int s;
		for (s=0; s<surfaceMesh->NumberOfSurfaces; s++)
		{
			Asura_Surface* surfaceDataPtr = &surfaceMesh->Surfaces[s];

			int iPolygonFlags = 0;
			if(pxMesh->PolygonFlagDataValid)
			{
				iPolygonFlags = pxMesh->PolygonFlagDataPtr[s].Flags;
			}
			
			if( iPolygonFlags & iFlagsToCheck )
			{
				continue;
			}
			
			patch.Render(surfaceDataPtr,false);

			if((patch.nextAvailableVertex + totalVertices) >iMaxVertices)
			{
				//too many vertices , will need to turn down the max subdivision level. RAR 07/07/03
				break;
			}
			if((patch.noOfIndices + totalIndices) > iMaxIndices)
			{
				//too many indices , so will need to turn down max subdivision
				break;
			}

			for (int v=0; v<patch.nextAvailableVertex; v++, totalVertices)
			{
				tempVertexArray[totalVertices+v].Position= patch.Vertices[v].du0dv0;
				
				tempVertexArray[totalVertices+v].Normal = patch.Vertices[v].Normal;
	
				tempVertexArray[totalVertices+v].U = patch.Vertices[v].u;
				tempVertexArray[totalVertices+v].V = patch.Vertices[v].v;

				tempVertexArray[totalVertices+v].U2 = patch.Vertices[v].u2;
				tempVertexArray[totalVertices+v].V2 = patch.Vertices[v].v2;

				tempVertexArray[totalVertices+v].Colour = patch.Vertices[v].Diffuse;

				tempVertexArray[totalVertices+v].m_iPolygonIndex = s;
				tempVertexArray[totalVertices+v].m_iPolygonFlags = iPolygonFlags & (AsuraPolygonFlag_FullBright|AsuraPolygonFlag_IgnoreNormalForLighting|AsuraPolygonFlag_Darken);

				#if defined(ASURA_TARGET_SM3)
				tempVertexArray[totalVertices+v].m_xLightTransportHarmonic = patch.Vertices[v].m_xLightTransportHarmonic;
				tempVertexArray[totalVertices+v].m_xDiffuseSH = patch.Vertices[v].m_xDiffuseSH;

				// VGP 13Feb2006
				//tempVertexArray[totalVertices+v].m_xBrightestLightVector = patch.Vertices[v].m_xBrightestLightVector;

				tempVertexArray[totalVertices+v].m_xTangent = patch.Vertices[v].m_xTangent;
				tempVertexArray[totalVertices+v].m_xBinormal = patch.Vertices[v].m_xBinormal;
				tempVertexArray[totalVertices+v].m_xTangent2 = patch.Vertices[v].m_xTangent2;
				tempVertexArray[totalVertices+v].m_xBinormal2 = patch.Vertices[v].m_xBinormal2;
				#endif
				tempVertexArray[totalVertices+v].m_iIndexInPacket = -1;
			}

			for(int i=0; i<patch.noOfIndices; i++)
			{
				tempIndexArray[totalIndices+i] = (unsigned short)(patch.indexOrder[i]+totalVertices);

				#if defined ASURA_USE_MATERIAL_RESPONSE_SYSTEM && !defined ASURA_MATERIAL_RESPONSE_CHARACTERS_ONLY
				for(int iMatSlot=0; iMatSlot<= TOOLS_NUM_MATERIALRESPONSE_PER_POLY; iMatSlot++)
				{
					pxTempMaterialResponseHashIDArray[ (totalIndices + i) / 3 ].m_auID[iMatSlot] = surfaceDataPtr->m_auMaterialResponseHashID[iMatSlot];
				}
				#else
					piTempMaterialIndexArray[(totalIndices+i)/3] = surfaceDataPtr->m_iMaterialID;
				#endif
			}

			totalIndices+=patch.noOfIndices;
			totalVertices+=patch.nextAvailableVertex;

			u_int uNumberOfTris = patch.noOfIndices/3;

			if (iPolygonFlags & AsuraPolygonFlag_DoubleSided)
			{
				if(patch.nextAvailableVertex + totalVertices>iMaxVertices)
				{
					//too many vertices , will need to turn down the max subdivision level. RAR 07/07/03
					break;
				}
				if(patch.noOfIndices + totalIndices > iMaxIndices)
				{
					//too many indices , so will need to turn down max subdivision
					break;
				}

				
				
				for (int v=0; v<patch.nextAvailableVertex; v++, totalVertices)
				{
					tempVertexArray[totalVertices+v].Position= patch.Vertices[v].du0dv0;
					
					if(iPolygonFlags & AsuraPolygonFlag_SplayNormals)
					{
						//If using the splay normals flag ,it is slightly more correct to mirror the normal in the plane
						//of the polygon rather than negating it.
						//This is not entirely in cases where the polygon is smoothed with another that isn't coplanar
						//with it , but I'm not convinced the extra mess to get that cases correct is worth it. 
						//RAR 23/11/2006
						if(!pxMesh->m_bFaceNormalsValid) pxMesh->CreateFaceNormals();
						const Asura_Vector_3& xFaceNormal = pxMesh->NormalsDataPtr[s].FaceNormal;

						float fDot = patch.Vertices[v].Normal*xFaceNormal;

						tempVertexArray[totalVertices+v].Normal = patch.Vertices[v].Normal - xFaceNormal*(2*fDot);
					}
					else
					{
						tempVertexArray[totalVertices+v].Normal = -patch.Vertices[v].Normal;
					}
			
					tempVertexArray[totalVertices+v].U = patch.Vertices[v].u;
					tempVertexArray[totalVertices+v].V = patch.Vertices[v].v;

					tempVertexArray[totalVertices+v].U2 = patch.Vertices[v].u2;
					tempVertexArray[totalVertices+v].V2 = patch.Vertices[v].v2;

					tempVertexArray[totalVertices+v].Colour = patch.Vertices[v].Diffuse;

					tempVertexArray[totalVertices+v].m_iPolygonIndex = s;
					tempVertexArray[totalVertices+v].m_iPolygonFlags = iPolygonFlags & (AsuraPolygonFlag_FullBright|AsuraPolygonFlag_IgnoreNormalForLighting|AsuraPolygonFlag_Darken);

#if defined(ASURA_TARGET_SM3)
					tempVertexArray[totalVertices+v].m_xLightTransportHarmonic = patch.Vertices[v].m_xLightTransportHarmonic;
					tempVertexArray[totalVertices+v].m_xDiffuseSH = patch.Vertices[v].m_xDiffuseSH;

					// VGP 13Feb2006
					tempVertexArray[totalVertices+v].m_xBrightestLightVector = patch.Vertices[v].m_xBrightestLightVector;

					tempVertexArray[totalVertices+v].m_xTangent = patch.Vertices[v].m_xTangent;
					tempVertexArray[totalVertices+v].m_xBinormal = patch.Vertices[v].m_xBinormal;
#endif
					tempVertexArray[totalVertices+v].m_iIndexInPacket = -1;
				}

				for(int i=0; i<patch.noOfIndices; i++)
				{
					tempIndexArray[totalIndices+i] = (unsigned short)(patch.indexOrder[patch.noOfIndices-1-i]+totalVertices);

					#if defined ASURA_USE_MATERIAL_RESPONSE_SYSTEM && !defined ASURA_MATERIAL_RESPONSE_CHARACTERS_ONLY
					for(int iMatSlot=0; iMatSlot<TOOLS_NUM_MATERIALRESPONSE_PER_POLY; iMatSlot++)
					{
						pxTempMaterialResponseHashIDArray[ (totalIndices + i) / 3 ].m_auID[iMatSlot] = surfaceDataPtr->m_auMaterialResponseHashID[iMatSlot];
					}
					#else
						piTempMaterialIndexArray[(totalIndices+i)/3] = surfaceDataPtr->m_iMaterialID;
					#endif
				}

				totalIndices+=patch.noOfIndices;
				totalVertices+=patch.nextAvailableVertex;

				uNumberOfTris *= 2;
			}
			
			bool newTexture=true;

			for (int t=0; t<NumberOfPackets; t++)
			{
				bool bMaterialMatches;
				#if defined ASURA_USE_MATERIAL_RESPONSE_SYSTEM && !defined ASURA_MATERIAL_RESPONSE_CHARACTERS_ONLY
				bMaterialMatches = true;
				for(int iMatSlot=0; iMatSlot<TOOLS_NUM_MATERIALRESPONSE_PER_POLY; iMatSlot++)
				{
					if( pxMaterialResponseHashIDs[t].m_auID[iMatSlot] != surfaceDataPtr->m_auMaterialResponseHashID[iMatSlot] )
					{
						bMaterialMatches = false;
						break;
					}
				}
				#else
					bMaterialMatches = (piMaterialID[t] == surfaceDataPtr->m_iMaterialID);
				#endif
				if(bMaterialMatches)
				{
					// KJL - 26/05/2002 19:50:47 - we came across this texture before;
					// just increment the number of tris associated with the texture
					numberOfTrisInPacket[t]+=uNumberOfTris;
					newTexture = false;
					break;
				}
			}

			// KJL - 26/05/2002 19:51:16 - has new texture has been found?
			if (newTexture)
			{
				numberOfTrisInPacket[NumberOfPackets]=uNumberOfTris;

				#if defined ASURA_USE_MATERIAL_RESPONSE_SYSTEM && !defined ASURA_MATERIAL_RESPONSE_CHARACTERS_ONLY
				for(int iMatSlot=0; iMatSlot<TOOLS_NUM_MATERIALRESPONSE_PER_POLY; iMatSlot++)
				{
					pxMaterialResponseHashIDs[ NumberOfPackets ].m_auID[iMatSlot] = surfaceDataPtr->m_auMaterialResponseHashID[iMatSlot];
				}
				NumberOfPackets++;
				#else
					piMaterialID[NumberOfPackets++] = surfaceDataPtr->m_iMaterialID;
				#endif
			}
		}
		if(s==surfaceMesh->NumberOfSurfaces)
		{
			bDone = true;
			if(Tools_Level_Export::IsLevelExport() && iDetail!=iMaxDetail)
			{
				
				Tools_Level_Export::AddMessage(Tools_Level_Export::MT_WARNING,"Too many vertices in %s. Subdivision level reduced to %d",pxMesh->Name.GetString(),iDetail);
			}
		}

	}
	Asura_Assertf(bDone,("Too many vertices in mesh '%s'",pxMesh->Name.GetString()));

	// KJL - 26/05/2002 19:52:04 - allocate packets and initialise them based
	// on this information
	Packets = new Tools_SubdividedMesh_Packet[NumberOfPackets];
	
	int numberOfUniqueVertices;
	int* uniqueVertex = new int[totalIndices]; 

    Tools_HashTable< Tools_SubdividedMesh_Vertex>* pxVertexHashTable = new Tools_HashTable<Tools_SubdividedMesh_Vertex>( 1 << Asura_Maths::GetFloorLog2( iMaxVertices >> 1) );

	for (int p=0; p<NumberOfPackets; p++)
	{
		numberOfUniqueVertices = 0;
		
		pxVertexHashTable->Clear();
		
		Packets[p].NumberOfTris = numberOfTrisInPacket[p];

		#if defined ASURA_USE_MATERIAL_RESPONSE_SYSTEM && !defined ASURA_MATERIAL_RESPONSE_CHARACTERS_ONLY
		for(int iMatSlot=0; iMatSlot< TOOLS_NUM_MATERIALRESPONSE_PER_POLY; iMatSlot++)
		{
			Packets[p].m_auMaterialResponseHashID[iMatSlot] = pxMaterialResponseHashIDs[p].m_auID[iMatSlot];
		}
		#else
			Packets[p].m_iMaterialID = piMaterialID[p];
		#endif

		Packets[p].TriList = new int[numberOfTrisInPacket[p]*3];

		int t=0;

		for (int i=0; i<(totalIndices/3); i++)
		{
			#if defined ASURA_USE_MATERIAL_RESPONSE_SYSTEM && !defined ASURA_MATERIAL_RESPONSE_CHARACTERS_ONLY
			bool bMaterialMatch = true;
			for(int iMatSlot=0; iMatSlot < TOOLS_NUM_MATERIALRESPONSE_PER_POLY; iMatSlot++)
			{
				if( pxTempMaterialResponseHashIDArray[i].m_auID[iMatSlot] != Packets[p].m_auMaterialResponseHashID[iMatSlot] )
				{
					bMaterialMatch = false;
					break;
				}
			}
			if(!bMaterialMatch) continue;
			#else
				if (piTempMaterialIndexArray[i] != Packets[p].m_iMaterialID) continue;
			#endif

			for (int v=0; v<3; v++)
			{
				int iVertexID = tempIndexArray[(i*3)+v];
				int iNewVertexID = -1;
				bool bNewVertex = true;

				// DLH - 06 July 2006 15:42:38 - Use a HashTree to help find matching vertices much faster for large data cases
				const Tools_SubdividedMesh_Vertex* pxVertexFind = &tempVertexArray[iVertexID];
				// KOR - 04/10/2006 - this was breaking whenever a vertex was encountered more than once, as the same pointer
				// would be returned, but it was not a new vertex.
				if(pxVertexFind->m_iIndexInPacket < 0)
				{
					// We have not encountered this vertex before. Check whether the data in the vertex matches any previous one.
					const Tools_SubdividedMesh_Vertex* pxVertexMatchFound = pxVertexHashTable->Insert( pxVertexFind);
					
					Asura_Assert( tempVertexArray <= pxVertexMatchFound, "Pointer out of range");
					Asura_Assert( pxVertexMatchFound < (tempVertexArray + iMaxVertices), "Pointer out of range");
					Asura_Assert( pxVertexMatchFound < (tempVertexArray + totalVertices), "Pointer out of range");
					Asura_Assert( *pxVertexFind == *pxVertexMatchFound, "Vertices Do not match");
					if( pxVertexMatchFound != pxVertexFind)
					{
						// Found a match.
						iNewVertexID = pxVertexMatchFound->m_iIndexInPacket;
						bNewVertex = false;
					}
				}
				else
				{
					// Already encountered this one - no need to check against hash table, just use the ID we have.
					iNewVertexID = pxVertexFind->m_iIndexInPacket;
					bNewVertex = false;
				}

#if 0
				// KOR - 04/10/2006 - old brute force code. Enable this to check that the new hash table behaviour is correct.
				int newVertexID_BruteForce = -1;
				bool newVertex_BruteForce = true;
				/// Kevin Lea - 27/05/2002 15:31:36 - test to see if vertex is unique
				for (int n=0; n<numberOfUniqueVertices; n++)
				{
					if (tempVertexArray[iVertexID]==tempVertexArray[uniqueVertex[n]])
					{
						const Asura_Hash_ID uHashCurrent = tempVertexArray[iVertexID].GetHashID();
						const Asura_Hash_ID uHashFound = tempVertexArray[uniqueVertex[n]].GetHashID();
						Asura_Assert(uHashCurrent == uHashFound, "hashes do not match - fix the hash function")
						newVertexID_BruteForce = n;
						newVertex_BruteForce = false;
						break;
					}
				}
				Asura_Assert(newVertexID_BruteForce == iNewVertexID, "Brute force and hash gave different results");
				Asura_Assert(newVertex_BruteForce == bNewVertex, "Brute force and hash gave different results");
#endif

				if (bNewVertex)
				{
					iNewVertexID = numberOfUniqueVertices;
					tempVertexArray[iVertexID].m_iIndexInPacket = iNewVertexID;
					uniqueVertex[numberOfUniqueVertices++] = iVertexID;
				}
				
				Asura_Assertf( 0 <= iNewVertexID, ("iNewVertexID %d is out of range", iNewVertexID));
//				Asura_Assertf( iNewVertexID < totalVertices, ("iNewVertexID %d is out of range. Totoal %d", iNewVertexID, totalVertices));

				Packets[p].TriList[t*3+v] = iNewVertexID;
			}
			t++;
		}

		Packets[p].Vertices = new Tools_SubdividedMesh_Vertex[numberOfUniqueVertices];

		for (int v=0; v<numberOfUniqueVertices; v++)
		{
			Packets[p].Vertices[v] = tempVertexArray[uniqueVertex[v]];
		}
		Packets[p].NumberOfVertices = numberOfUniqueVertices;
		TotalVertices += numberOfUniqueVertices;
		TotalTris += Packets[p].NumberOfTris;
		
		#if defined( ASURA_ASSERT)
		{
			const Tools_SubdividedMesh_Packet& xPacket = Packets[ p];
			const u_int uIndexCount = 3 * xPacket.NumberOfTris;
			
			for( u_int uIndexIndex = 0; uIndexIndex < uIndexCount; uIndexIndex += 1)
			{
				const int iVertexIndex = xPacket.TriList[ uIndexIndex];
				Asura_Assertf( iVertexIndex < xPacket.NumberOfVertices, ("Vertex Index %d out of %d range. Mesh '%s'", iVertexIndex, xPacket.NumberOfVertices, pxMesh->Name.GetString()));
			}
		}
		#endif
	}
	
	delete pxVertexHashTable;

	delete [] uniqueVertex;
	// KJL - 26/05/2002 19:51:46 - delete temporary storage
	delete [] numberOfTrisInPacket;

	#if defined ASURA_USE_MATERIAL_RESPONSE_SYSTEM && !defined ASURA_MATERIAL_RESPONSE_CHARACTERS_ONLY
		delete [] pxMaterialResponseHashIDs;
		delete [] pxTempMaterialResponseHashIDArray;
	#else
		delete [] piMaterialID;
		delete [] piTempMaterialIndexArray;
	#endif

	delete [] tempIndexArray;
	delete [] tempVertexArray;

	if(s_bRecalculatePrelighting)
	{
		Asura_Lighting_System::CalculatePrelighting(this);
	}
	
	if(Tools_Level_Export::IsLevelExport())
	{
		//During level exports , the prelighting may be scaled. RAR 09/02/2004
		for(int i=0;i<NumberOfPackets;i++)
		{
			Tools_SubdividedMesh_Packet* pxPacket = &Packets[i];

			for(int j=0;j<pxPacket->NumberOfVertices;j++)
			{
				Tools_SubdividedMesh_Vertex* pxVertex = &pxPacket->Vertices[j];

				pxVertex->Colour = Tools_Level_Export::ScalePrelightValue(pxVertex->Colour);
			}
		}

	}

	if(pxMesh)
	{
		Tools_Level_Export::AddMessage( Tools_Level_Export::MT_LOGONLY,
			"Name: %s\t\tIn: %6i\tOut: %6i\tDiff: %6i\n", pxMesh->Name.GetString(), pxMesh->NumberOfTriangles, TotalTris, TotalTris - pxMesh->NumberOfTriangles);
	}
	
	return( true);
}

void Tools_SubdividedMesh::ConvertToMesh(Asura_Mesh* pxOutputMesh, const bool bExpandVertices)
{
	const u_int uNewVertexCountMax = 0x10000;
	const u_int uNewVertexCount = (true == bExpandVertices) ? this->TotalTris * 3 : this->TotalVertices;
	
	Asura_Assert(pxOutputMesh, "Null output mesh provided");
	Asura_Assertf( uNewVertexCount <= uNewVertexCountMax, ("Too many vertices (%d) for mesh '%s'. Max is %d.", uNewVertexCount, this->m_pxMesh->Name.GetString(), uNewVertexCountMax));
	
	Asura_Mesh_Polygon* pxNewPolyData = new Asura_Mesh_Polygon[TotalTris];
	Asura_Mesh_Vertex* pxNewVertexData = new Asura_Mesh_Vertex[uNewVertexCount];
	Asura_Mesh_TextureInfo* pxNewTextureData = new Asura_Mesh_TextureInfo[TotalTris];
	Asura_Mesh_PolygonFlags* pxNewPolyFlagData = new Asura_Mesh_PolygonFlags[TotalTris];
	Asura_Mesh_Prelighting* pxNewPrelightingData = new Asura_Mesh_Prelighting[TotalTris];
	Asura_Mesh_PaintedColours* pxNewPaintedColourData = new Asura_Mesh_PaintedColours[ TotalTris ];

	u_short uVertexIndexWrite = 0;
	u_int uPolyIndexWrite = 0;

	for(int uPacketIndex = 0; uPacketIndex < NumberOfPackets; ++uPacketIndex)
	{
		Tools_SubdividedMesh_Packet* pxPacket = &Packets[uPacketIndex];

		for(int uPolyIndexRead = 0; uPolyIndexRead < pxPacket->NumberOfTris; ++uPolyIndexRead)
		{
			u_int auIndexVertex[3];
			
			if( true == bExpandVertices)
			{
				auIndexVertex[0] = uVertexIndexWrite+0;
				auIndexVertex[1] = uVertexIndexWrite+1;
				auIndexVertex[2] = uVertexIndexWrite+2;

				pxNewVertexData[uVertexIndexWrite++].Position = pxPacket->Vertices[pxPacket->TriList[uPolyIndexRead*3+0]].Position - m_xPosition;
				pxNewVertexData[uVertexIndexWrite++].Position = pxPacket->Vertices[pxPacket->TriList[uPolyIndexRead*3+1]].Position - m_xPosition;
				pxNewVertexData[uVertexIndexWrite++].Position = pxPacket->Vertices[pxPacket->TriList[uPolyIndexRead*3+2]].Position - m_xPosition;
			}
			else
			{
				auIndexVertex[0] = uVertexIndexWrite + pxPacket->TriList[(uPolyIndexRead*3)+0];
				auIndexVertex[1] = uVertexIndexWrite + pxPacket->TriList[(uPolyIndexRead*3)+1];
				auIndexVertex[2] = uVertexIndexWrite + pxPacket->TriList[(uPolyIndexRead*3)+2];
			}
			
			Asura_Assertf( auIndexVertex[0] < uNewVertexCount, ("Polygon Vertex Index (%d) is too for mesh '%s'. Max is %d.", auIndexVertex[0], this->m_pxMesh->Name.GetString(), uNewVertexCount));
			Asura_Assertf( auIndexVertex[0] < uNewVertexCountMax, ("Polygon Vertex Index (%d) is too for mesh '%s'. Max is %d.", auIndexVertex[0], this->m_pxMesh->Name.GetString(), uNewVertexCountMax));
			Asura_Assertf( auIndexVertex[1] < uNewVertexCount, ("Polygon Vertex Index (%d) is too for mesh '%s'. Max is %d.", auIndexVertex[1], this->m_pxMesh->Name.GetString(), uNewVertexCount));
			Asura_Assertf( auIndexVertex[1] < uNewVertexCountMax, ("Polygon Vertex Index (%d) is too for mesh '%s'. Max is %d.", auIndexVertex[1], this->m_pxMesh->Name.GetString(), uNewVertexCountMax));
			Asura_Assertf( auIndexVertex[2] < uNewVertexCount, ("Polygon Vertex Index (%d) is too for mesh '%s'. Max is %d.", auIndexVertex[2], this->m_pxMesh->Name.GetString(), uNewVertexCount));
			Asura_Assertf( auIndexVertex[2] < uNewVertexCountMax, ("Polygon Vertex Index (%d) is too for mesh '%s'. Max is %d.", auIndexVertex[2], this->m_pxMesh->Name.GetString(), uNewVertexCountMax));
			
			pxNewPolyData[uPolyIndexWrite] = Asura_Mesh_Polygon( static_cast<unsigned short>( auIndexVertex[0]), static_cast<unsigned short>( auIndexVertex[1]), static_cast<unsigned short>( auIndexVertex[2]));

			#if defined ASURA_USE_MATERIAL_RESPONSE_SYSTEM && !defined ASURA_MATERIAL_RESPONSE_CHARACTERS_ONLY
				for(int iMatSlot = 0; iMatSlot<TOOLS_NUM_MATERIALRESPONSE_PER_POLY; iMatSlot++)
				{
					pxNewTextureData[uPolyIndexWrite].m_auMaterialResponseHashID[iMatSlot] = pxPacket->m_auMaterialResponseHashID[iMatSlot];
				}

				// (AAM - 08.12.2006) Don't have this data available. This is only used for the old
				// water system anyway
				pxNewTextureData[uPolyIndexWrite].m_iMaterialID = ASURA_MATERIAL_NONE;
			#else
				pxNewTextureData[uPolyIndexWrite].m_iMaterialID = pxPacket->m_iMaterialID;
			#endif

			pxNewTextureData[uPolyIndexWrite].m_afAlpha[0] = 1.f;
			pxNewTextureData[uPolyIndexWrite].U[0][0] = pxPacket->Vertices[pxPacket->TriList[uPolyIndexRead*3+0]].U;
			pxNewTextureData[uPolyIndexWrite].U[0][1] = pxPacket->Vertices[pxPacket->TriList[uPolyIndexRead*3+1]].U;
			pxNewTextureData[uPolyIndexWrite].U[0][2] = pxPacket->Vertices[pxPacket->TriList[uPolyIndexRead*3+2]].U;
			pxNewTextureData[uPolyIndexWrite].U[1][0] = pxPacket->Vertices[pxPacket->TriList[uPolyIndexRead*3+0]].U2;
			pxNewTextureData[uPolyIndexWrite].U[1][1] = pxPacket->Vertices[pxPacket->TriList[uPolyIndexRead*3+1]].U2;
			pxNewTextureData[uPolyIndexWrite].U[1][2] = pxPacket->Vertices[pxPacket->TriList[uPolyIndexRead*3+2]].U2;
			pxNewTextureData[uPolyIndexWrite].V[0][0] = pxPacket->Vertices[pxPacket->TriList[uPolyIndexRead*3+0]].V;
			pxNewTextureData[uPolyIndexWrite].V[0][1] = pxPacket->Vertices[pxPacket->TriList[uPolyIndexRead*3+1]].V;
			pxNewTextureData[uPolyIndexWrite].V[0][2] = pxPacket->Vertices[pxPacket->TriList[uPolyIndexRead*3+2]].V;
			pxNewTextureData[uPolyIndexWrite].V[1][0] = pxPacket->Vertices[pxPacket->TriList[uPolyIndexRead*3+0]].V2;
			pxNewTextureData[uPolyIndexWrite].V[1][1] = pxPacket->Vertices[pxPacket->TriList[uPolyIndexRead*3+1]].V2;
			pxNewTextureData[uPolyIndexWrite].V[1][2] = pxPacket->Vertices[pxPacket->TriList[uPolyIndexRead*3+2]].V2;

			pxNewPolyFlagData[uPolyIndexWrite].Flags = pxPacket->Vertices[pxPacket->TriList[uPolyIndexRead*3+0]].m_iPolygonFlags;

			pxNewPrelightingData[uPolyIndexWrite].Colour[0] = pxPacket->Vertices[pxPacket->TriList[uPolyIndexRead*3+0]].Colour;
			pxNewPrelightingData[uPolyIndexWrite].Colour[1] = pxPacket->Vertices[pxPacket->TriList[uPolyIndexRead*3+1]].Colour;
			pxNewPrelightingData[uPolyIndexWrite].Colour[2] = pxPacket->Vertices[pxPacket->TriList[uPolyIndexRead*3+2]].Colour;

			// JGP - Generate base painted colours
			pxNewPaintedColourData[ uPolyIndexWrite ].Colour[ 0 ] = 0x808080;
			pxNewPaintedColourData[ uPolyIndexWrite ].Colour[ 1 ] = 0x808080;
			pxNewPaintedColourData[ uPolyIndexWrite ].Colour[ 2 ] = 0x808080;

			++uPolyIndexWrite;
		}
		
		if( false == bExpandVertices)
		{
			u_int uPacketVertexCount = pxPacket->NumberOfVertices;
			for( u_int uPacketVertexIndex = 0; uPacketVertexIndex < uPacketVertexCount; uPacketVertexIndex += 1, uVertexIndexWrite += 1)
			{
				pxNewVertexData[ uVertexIndexWrite].Position = pxPacket->Vertices[ uPacketVertexIndex].Position - m_xPosition;
			}
		}

	}
	
	Asura_Assert( uVertexIndexWrite == uNewVertexCount, "Vertex Mis calc");

	// JGP - Painted colours are valid
	if ( pxOutputMesh->m_pxPaintedColourDataPtr )		delete [] pxOutputMesh->m_pxPaintedColourDataPtr;
	pxOutputMesh->m_pxPaintedColourDataPtr = pxNewPaintedColourData;
	pxOutputMesh->m_bPaintedColourDataValid = true;

	if (pxOutputMesh->VertexDataPtr)					delete [] pxOutputMesh->VertexDataPtr;					pxOutputMesh->VertexDataPtr						= NULL;	pxOutputMesh->VertexDataValid			= false;
	if (pxOutputMesh->PolygonDataPtr)					delete [] pxOutputMesh->PolygonDataPtr;					pxOutputMesh->PolygonDataPtr					= NULL;	pxOutputMesh->PolygonDataValid			= false;
	if (pxOutputMesh->TextureDataPtr)					delete [] pxOutputMesh->TextureDataPtr;					pxOutputMesh->TextureDataPtr					= NULL;	pxOutputMesh->TextureDataValid			= false;
	if (pxOutputMesh->PrelightingDataPtr)				delete [] pxOutputMesh->PrelightingDataPtr;				pxOutputMesh->PrelightingDataPtr				= NULL;	pxOutputMesh->PrelightingDataValid		= false;
	if (pxOutputMesh->SmoothingGroupDataPtr)			delete [] pxOutputMesh->SmoothingGroupDataPtr;			pxOutputMesh->SmoothingGroupDataPtr				= NULL;	pxOutputMesh->SmoothingGroupDataValid	= false;
	if (pxOutputMesh->PolygonFlagDataPtr)				delete [] pxOutputMesh->PolygonFlagDataPtr;				pxOutputMesh->PolygonFlagDataPtr				= NULL;	pxOutputMesh->PolygonFlagDataValid		= false;
	if (pxOutputMesh->m_pxPolygonGuids)					delete [] pxOutputMesh->m_pxPolygonGuids;				pxOutputMesh->m_pxPolygonGuids					= NULL;	
	if (pxOutputMesh->m_pxPolygonLights)				delete [] pxOutputMesh->m_pxPolygonLights;				pxOutputMesh->m_pxPolygonLights					= NULL;	
	if (pxOutputMesh->m_puPolygonLightIDs)				delete [] pxOutputMesh->m_puPolygonLightIDs;			pxOutputMesh->m_puPolygonLightIDs				= NULL;	
	pxOutputMesh->m_iNumberOfPolygonLights = 0;

	pxOutputMesh->VertexDataPtr = pxNewVertexData;				pxOutputMesh->VertexDataValid = true;
	pxOutputMesh->PolygonDataPtr = pxNewPolyData;				pxOutputMesh->PolygonDataValid = true;
	pxOutputMesh->TextureDataPtr = pxNewTextureData;			pxOutputMesh->TextureDataValid = true;
	pxOutputMesh->PolygonFlagDataPtr = pxNewPolyFlagData;		pxOutputMesh->PolygonFlagDataValid = true;
	pxOutputMesh->PrelightingDataPtr = pxNewPrelightingData;	pxOutputMesh->PrelightingDataValid = true;

	pxOutputMesh->InvalidateNormals();
	pxOutputMesh->InvalidatePolygonIndices();

	pxOutputMesh->BoundingBoxDataValid = false;

	pxOutputMesh->NumberOfPolygons = pxOutputMesh->NumberOfTriangles = TotalTris;
	pxOutputMesh->NumberOfVertices = uNewVertexCount;
}

void Asura_Lighting_System::CalculatePrelighting(class Tools_SubdividedMesh* pxSubdividedMesh)
{
	Asura_Assert(pxSubdividedMesh,"");
	Asura_Mesh* pxMesh = pxSubdividedMesh->m_pxMesh;
	Asura_Assert(pxMesh->AreNormalsValid(),"");

	//build the list of nearby lights
	if (!pxMesh->BoundingBoxDataValid) pxMesh->CalculateBoundingBox();

	Asura_Bounding_Box bb;
	bb = pxMesh->BoundingBox;
	bb.Displace(pxSubdividedMesh->m_xPosition);

	Asura_Lighting_System::MakeLightListForObject(bb);

	//calculate prelighting for each vertex in each packet
	for(int i=0;i<pxSubdividedMesh->NumberOfPackets;i++)
	{
		Tools_SubdividedMesh_Packet* pxPacket = &pxSubdividedMesh->Packets[i];

		for(int j=0;j<pxPacket->NumberOfVertices;j++)
		{
			Tools_SubdividedMesh_Vertex* pxVertex = &pxPacket->Vertices[j];

			//For the LOS test need to project the vertex onto the original polygon , so it doesn't get blocked
			//by the unsubdivided mesh.
			//If the original polygon was a quad ,then use the greatest distance from the oth and 3rd vertex , 
			//to avoid problems with polygons that aren't quite planar

			const Asura_Mesh_Polygon* pxPoly = &pxMesh->PolygonDataPtr[pxVertex->m_iPolygonIndex];
			const Asura_Vector_3& xFaceNormal = pxMesh->NormalsDataPtr[pxVertex->m_iPolygonIndex].FaceNormal;
			float fDistance = -Asura_Maths::LargeFloat;
			for(int k=0;k<pxPoly->NumberOfVertices();k+=3)
			{
				const Asura_Vector_3& xOriginalVertex = pxSubdividedMesh->m_xPosition+pxMesh->VertexDataPtr[pxMesh->PolygonDataPtr[pxVertex->m_iPolygonIndex].VertexID[k]].Position;

				Asura_Vector_3 xOffset = xOriginalVertex - pxVertex->Position;
				float fTempDistance = xOffset*xFaceNormal + 0.002f;
				if(fTempDistance>fDistance) fDistance = fTempDistance;
					
			}
			Asura_Vector_3 xPointOnPoly = pxVertex->Position + xFaceNormal*fDistance;

			unsigned int uColour;
			CalculatePreLightValue(pxVertex->Position, xPointOnPoly, pxVertex->Normal, uColour, -1, -1, pxVertex->m_iPolygonFlags);
			pxVertex->Colour = ((uColour & 0xFFFFFF) | (pxVertex->Colour & 0xFF000000));
		}
	}
	
}


static bool IsColourApproximatelyEqual( u_int uRGBA1, u_int uRGBA2, u_int uTol )
{
    if( uRGBA1 != uRGBA2 )
    {
        // Compare channels individually.
        for( u_int u = 4; u--; )
        {
            int iChannel1 = uRGBA1 & 0xFFu;
            int iChannel2 = uRGBA2 & 0xFFu;

            if( Asura_Maths::Abs(iChannel1 - iChannel2) > static_cast<int>(uTol) )
            {
                return false;
            }
        
            uRGBA1 >>= 8u;
            uRGBA2 >>= 8u;
        }
    }

    return true;
}


// (SB - 26/07/07) Allow projects to alter the parameters used for comparing vertices - by default test everything
Tools_SubdividedMesh_Vertex::VertexComparisonParameters Tools_SubdividedMesh_Vertex::s_xVertexComparisonParameters = { 0xffffffff, 0xffffffff };

#if defined ASURA_USE_MATERIAL_RESPONSE_SYSTEM && !defined ASURA_MATERIAL_RESPONSE_CHARACTERS_ONLY
	bool Tools_SubdividedMesh_Vertex::ApproximatelyEquals(const Tools_SubdividedMesh_Vertex* pxVert1,const Tools_SubdividedMesh_Vertex* pxVert2,bool bHasSecondMaterial,bool bCheckPosition)
#else
	bool Tools_SubdividedMesh_Vertex::ApproximatelyEquals(const Tools_SubdividedMesh_Vertex* pxVert1,const Tools_SubdividedMesh_Vertex* pxVert2,int iMaterial,bool bCheckPosition)
#endif
{
	// Tolerance values
	// These are used to decide if the properties of two vertices are close enough that they can be merged
	// Position tolerance is the squared maximum distance between positions
	// Normal tolerance is the maximum angle between normals
	// UV tolerance is the maximum difference between U coords or V coords
	// Colour colerance is the maximum difference in value between each channel of two colours
	// SH tolerance is max difference in coefficients for SHs
	const float fPosTol = 0.0025f * 0.0025f; // +/- 0.25cm.
    const float fNrmTol = 0.996194698092f;   // +/- 5º (where this value is cos 5º)
    const float fUVTol  = 0.01f;             // +/- 0.01 in any channel.
	const u_int uColTol = s_uColourTolerance;// +/- 2 in any channel (default)
	#if defined(ASURA_TARGET_SM3)
	const float fSHTol = 0.01f;				 // +/- 0.01 in any coefficient. RAR 04/05/2006
	#endif

	//Position
	if(bCheckPosition)
	{
		if(!pxVert1->Position.ApproximatelyEquals(pxVert2->Position,fPosTol)) return false;
	}

	//Normal
	if(pxVert1->Normal * pxVert2->Normal < fNrmTol && s_xVertexComparisonParameters.m_bTestNormals)
	{
		//Failed first test (which assumes that they are both unit length vectors)
		//Allow equality however if the normals are both zero
		if(!(pxVert1->Normal.ApproximatelyEquals(Asura_Maths::ZeroVector3) && pxVert2->Normal.ApproximatelyEquals(Asura_Maths::ZeroVector3)))
		{
			return false;
		}
	}

	//UVs
	#if defined ASURA_USE_MATERIAL_RESPONSE_SYSTEM && !defined ASURA_MATERIAL_RESPONSE_CHARACTERS_ONLY
		const bool bDualTexture = bHasSecondMaterial;
	#else
		const bool bDualTexture = Asura_Material_System::IsMaterialDualTexture(iMaterial);
	#endif
    
	if( Asura_Maths::Abs(pxVert1->U - pxVert2->U) > fUVTol && s_xVertexComparisonParameters.m_bTestPrimaryUV ) { return false; }
	if( Asura_Maths::Abs(pxVert1->V - pxVert2->V) > fUVTol && s_xVertexComparisonParameters.m_bTestPrimaryUV ) { return false; }

	// Only bother comparing secondary texture coordinates if it's
	// a dual texture material. Note that we know at this point that
	// the materials match.
	if( bDualTexture )
	{
		if( Asura_Maths::Abs(pxVert1->U2 - pxVert2->U2) > fUVTol && s_xVertexComparisonParameters.m_bTestSecondaryUV ) { return false; }
		if( Asura_Maths::Abs(pxVert1->V2 - pxVert2->V2) > fUVTol && s_xVertexComparisonParameters.m_bTestSecondaryUV ) { return false; }
	}

	//Colour
	if( !IsColourApproximatelyEqual(pxVert1->Colour, pxVert2->Colour, uColTol) && s_xVertexComparisonParameters.m_bTestColour )
	{
		return false;
	}

	//Polygon flags (may be no point in checking these...)
	if((pxVert1->m_iPolygonFlags & s_xVertexComparisonParameters.m_iFlagTestMask) != (pxVert2->m_iPolygonFlags & s_xVertexComparisonParameters.m_iFlagTestMask)) return false;

	#if defined(ASURA_TARGET_SM3)
	//Light transport harmonic
	for(int i=0;i<Asura_SphericalHarmonics_Order3::NUMBER_OF_TERMS;i++)
	{
		const float fDiff = pxVert1->m_xLightTransportHarmonic[i] - pxVert2->m_xLightTransportHarmonic[i];
		if(Asura_Maths::Abs(fDiff) > fSHTol) return false;
	}

	//diffuse SH
	for(int i=0;i<Asura_SphericalHarmonics_Order2_RGB::NUMBER_OF_COEFFICIENTS;i++)
	{
		const float fDiff = pxVert1->m_xDiffuseSH[i] - pxVert2->m_xDiffuseSH[i];
		if(Asura_Maths::Abs(fDiff) > fSHTol) return false;
	}

	//brightest light vector
	if(pxVert1->m_xBrightestLightVector * pxVert2->m_xBrightestLightVector < fNrmTol)
	{
		//Failed first test (which assumes that they are both unit length vectors)
		//Allow equality however if the normals are both zero
		if(!(pxVert1->m_xBrightestLightVector.ApproximatelyEquals(Asura_Maths::ZeroVector3) && pxVert2->m_xBrightestLightVector.ApproximatelyEquals(Asura_Maths::ZeroVector3)))
		{
			return false;
		}
	}

	//tangent
	if(pxVert1->m_xTangent * pxVert2->m_xTangent < fNrmTol)
	{
		//Failed first test (which assumes that they are both unit length vectors)
		//Allow equality however if the normals are both zero
		if(!(pxVert1->m_xTangent.ApproximatelyEquals(Asura_Maths::ZeroVector3) && pxVert2->m_xTangent.ApproximatelyEquals(Asura_Maths::ZeroVector3)))
		{
			return false;
		}
	}

	//binormal
	if(pxVert1->m_xBinormal * pxVert2->m_xBinormal < fNrmTol)
	{
		//Failed first test (which assumes that they are both unit length vectors)
		//Allow equality however if the normals are both zero
		if(!(pxVert1->m_xBinormal.ApproximatelyEquals(Asura_Maths::ZeroVector3) && pxVert2->m_xBinormal.ApproximatelyEquals(Asura_Maths::ZeroVector3)))
		{
			return false;
		}
	}
	if(pxVert1->m_xTangent2 * pxVert2->m_xTangent2 < fNrmTol)
	{
		//Failed first test (which assumes that they are both unit length vectors)
		//Allow equality however if the normals are both zero
		if(!(pxVert1->m_xTangent2.ApproximatelyEquals(Asura_Maths::ZeroVector3) && pxVert2->m_xTangent2.ApproximatelyEquals(Asura_Maths::ZeroVector3)))
		{
			return false;
		}
	}

	//binormal
	if(pxVert1->m_xBinormal2 * pxVert2->m_xBinormal2 < fNrmTol)
	{
		//Failed first test (which assumes that they are both unit length vectors)
		//Allow equality however if the normals are both zero
		if(!(pxVert1->m_xBinormal2.ApproximatelyEquals(Asura_Maths::ZeroVector3) && pxVert2->m_xBinormal2.ApproximatelyEquals(Asura_Maths::ZeroVector3)))
		{
			return false;
		}
	}


#endif //defined(ASURA_TARGET_SM3)

	return true;
		
}

// By default compare everything
void Tools_SubdividedMesh_Vertex::SetDefaultVertexComparisonMode()
{
	s_xVertexComparisonParameters.m_uComparisonFlags = 0xffffffff;
	s_xVertexComparisonParameters.m_iFlagTestMask = 0xffffffff;
}

void Tools_SubdividedMesh_Vertex::SetVertexComparisonMode(VertexComparisonParameters& xParams)
{
	s_xVertexComparisonParameters = xParams;
}
