// Copyright (C) 2004-2009 Christoph Kubisch & Eike Decker
// This file is part of the "Luxinia Engine".
// For conditions of distribution and use, see copyright notice in luxiniapublicsdk.txt

#include "exmodeloptimize.h"

#include <luxcore/meshvcacheopt.h>


////////////////////////////////////////////////////////////////////////////////////////
// RemapIndices()
//
// Function to remap your indices to improve spatial locality in your vertex buffer.
//
// in_primGroups: array of PrimitiveGroups you want remapped
// numGroups: number of entries in in_primGroups
// numVerts: number of vertices in your vertex buffer, also can be thought of as the range
//  of acceptable values for indices in your primitive groups.
// remappedGroups: array of remapped PrimitiveGroups
//
// Note that, according to the remapping handed back to you, you must reorder your 
//  vertex buffer.
//
void RemapIndices(const PrimitiveGroup* in_primGroups, const unsigned short numGroups,
				  const unsigned int numVerts, PrimitiveGroup** remappedGroups)
{
	(*remappedGroups) = new PrimitiveGroup[numGroups];

	//caches oldIndex --> newIndex conversion
	int *indexCache;
	indexCache = new int[numVerts];
	memset(indexCache, -1, sizeof(int)*numVerts);

	//loop over primitive groups
	unsigned int indexCtr = 0;
	for(int i = 0; i < numGroups; i++)
	{
		unsigned int numIndices = in_primGroups[i].numIndices;

		//init remapped group
		(*remappedGroups)[i].numIndices = numIndices;
		(*remappedGroups)[i].indices    = new unsigned int[numIndices];

		for(size_t j = 0; j < numIndices; j++)
		{
			int cachedIndex = indexCache[in_primGroups[i].indices[j]];
			if(cachedIndex == -1) //we haven't seen this index before
			{
				//point to "last" vertex in VB
				(*remappedGroups)[i].indices[j] = indexCtr;

				//add to index cache, increment
				indexCache[in_primGroups[i].indices[j]] = indexCtr++;
			}
			else
			{
				//we've seen this index before
				(*remappedGroups)[i].indices[j] = cachedIndex;
			}
		}
	}

	delete[] indexCache;
}

//////////////////////////////////////////////////////////////////////////
// Model Optimization

void	EXModelMesh_optimize(EXModelPTR imodel,EXMeshPTR mesh, EXMeshOptimizer &optimizer)
{
	if (!optimizer.SupportsType(mesh->primitivetype))
		return;

	EXMesh	&imesh = *mesh;
	EXSkin *iskin = imesh.skin;

	std::vector<PrimOutSet>	collectedgroups;

	// we must pump all triangles (all groups, all instanced meshes)
	// else remapping the vertices will be wrong
	std::vector<EXMeshPTR>	indexmeshes;
	// self
	indexmeshes.push_back(mesh);

	for (size_t m = 0; m < imodel->meshes.size(); m++){
		EXMeshPTR othermesh = imodel->meshes[m];
		if (othermesh->instance == mesh && othermesh->primitivetype == mesh->primitivetype){
			indexmeshes.push_back(othermesh);
		}
	}

	uint		numTotalGrps = 0;
	for (size_t m = 0; m < indexmeshes.size(); m++){
		EXMeshPTR indexmesh = indexmeshes[m];
		for (size_t g = 0; g < indexmesh->primitivegroups.size(); g++){
			EXPrimitiveGroup &primgrp = indexmesh->primitivegroups[g];

			uint				numIndices = primgrp.indices.size();
			uint				*indicesData = new uint[primgrp.indices.size()];

			for (size_t i = 0; i < primgrp.indices.size(); i++){
				indicesData[i] = (uint)(primgrp.indices[i].vertexIDX);
			}

			// perform stripping for each prim group
			PrimOutSet strip = optimizer.MakePrimOutSet(indicesData,numIndices,(uint)imesh.vertices.size());
			delete[] indicesData;

			numTotalGrps += strip.numGrps;

			collectedgroups.push_back(strip);
		}
	}

	// batch collection to big primgroup and remap it
	// destroy old PrimGroups, but keep indices for collection
	PrimitiveGroup *pGrps = new PrimitiveGroup[numTotalGrps];
	uint runner = 0;
	for (size_t g = 0; g < collectedgroups.size(); g++){
		PrimOutSet &curstrip = collectedgroups[g];
		for (ushort s = 0; s < curstrip.numGrps; s++){
			PrimitiveGroup	&curgrp = pGrps[runner++];
			curgrp = curstrip.pGrps[s];
			curstrip.pGrps[s].indices = NULL;
		}

		delete[] curstrip.pGrps;
		curstrip.pGrps = NULL;
	}

	PrimitiveGroup *pFinalGrps;

	// remap and feed back indices & new vertex order
	RemapIndices(pGrps, numTotalGrps, EXMesh_getVertexCount(mesh), &pFinalGrps);

	uint origgrps = 0;
	runner = 0;
	for (size_t m = 0; m < indexmeshes.size(); m++){
		EXMeshPTR indexmesh = indexmeshes[m];
		EXMesh_setPrimitiveType(indexmesh,optimizer.OutType());

		// clear old prior copying as we rebuild them anyway
		for (size_t g = 0; g < indexmesh->primitivegroups.size(); g++){
			EXPrimitiveGroup &primgrp = indexmesh->primitivegroups[g];
			primgrp.indices.clear();
		}
		// copy old
		std::vector<EXPrimitiveGroup>	oldgrps = indexmesh->primitivegroups;
		indexmesh->primitivegroups.clear();
		// if we generated strips we must create new primgrps
		for (size_t g = 0; g < oldgrps.size(); g++){
			EXPrimitiveGroup &oldprimgrp = oldgrps[g];
			// old strip info
			PrimOutSet &curstrip = collectedgroups[origgrps++];

			// for evey new group by this old group generate
			// new grp

			for (ushort ng = 0; ng < curstrip.numGrps; ng++){
				PrimitiveGroup	&ogrp = pGrps[runner];
				PrimitiveGroup	&ngrp = pFinalGrps[runner];
				runner++;

				EXPrimitiveGroupPTR	newgrp = EXMesh_addPrimitiveGroup(indexmesh);

				EXPrimitiveGroup_provideIndex(newgrp,ngrp.numIndices-1);
				for (size_t i = 0; i < ngrp.numIndices; i++){
					uint oldIndex = ogrp.indices[i];
					uint newIndex = ngrp.indices[i];

					EXIndexPTR	index = EXPrimitiveGroup_getIndex(newgrp,i);
					EXVertexPTR	vertex = EXMesh_getVertex(mesh,oldIndex);
					index->vertex = vertex;
					index->vertexIDX = oldIndex;

					// remapping
					vertex->orderIDX = newIndex;
					imesh.vertexOrder[newIndex] = oldIndex;
				}
			}
		}
	}

	delete[] pFinalGrps;
	delete[] pGrps;
}



void EXModel_optimize(EXModel *imodel, EXMeshOptimizer &optimizer)
{
	for (size_t i = 0; i < imodel->meshes.size(); i++){
		EXMeshPTR imesh = imodel->meshes[i];
		if (EXMesh_getType(imesh)==EXMESH_MESH)
		{
			EXModelMesh_optimize(imodel,imesh,optimizer);
		}
	}
}

//////////////////////////////////////////////////////////////////////////
// Optimizer classes

class ReOrderOptimizer : public EXMeshOptimizer
{
public:
	virtual PrimOutSet MakePrimOutSet(const uint *indices, uint numIndices, uint numVertices){
		PrimOutSet	strip;
		strip.pGrps = new PrimitiveGroup();
		strip.numGrps = 1;

		uint *indicescpy = new uint[numIndices];
		memcpy(indicescpy,indices,sizeof(uint)*numIndices);

		strip.pGrps->indices =  indicescpy;
		strip.pGrps->numIndices = numIndices;

		return strip;
	}

	virtual booln SupportsType(EXPrimitiveType type){
		return type == EXPRIM_TRIANGLE_LIST;
	}

	virtual EXPrimitiveType OutType() {
		return EXPRIM_TRIANGLE_LIST;
	}

};

class TipsifyOptimizer : public EXMeshOptimizer
{
public:
	virtual PrimOutSet MakePrimOutSet(const uint *indices, uint numIndices, uint numVertices){
		PrimOutSet	strip;
		strip.pGrps = new PrimitiveGroup();
		strip.numGrps = 1;

		uint *indicescpy = new uint[numIndices];
		memcpy(indicescpy,indices,sizeof(uint)*numIndices);

		strip.pGrps->indices =  (uint*)vcacheopt_tipsify((void*)indicescpy,numIndices/3,numVertices,m_cachesize,VERTEX_INDEX_TYPE_UINT32);
		strip.pGrps->numIndices = numIndices;

		return strip;
	}

	virtual booln SupportsType(EXPrimitiveType type){
		return type == EXPRIM_TRIANGLE_LIST;
	}

	virtual EXPrimitiveType OutType() {
		return EXPRIM_TRIANGLE_LIST;
	}

	TipsifyOptimizer(uint cachesize) {
		m_cachesize	= cachesize;
	}
private:
	uint		m_cachesize;
};


class ForsythOptimizer : public EXMeshOptimizer
{
public:
	virtual PrimOutSet MakePrimOutSet(const uint *indices, uint numIndices, uint numVertices){
		PrimOutSet	strip;
		strip.pGrps = new PrimitiveGroup[1];
		strip.numGrps = 1;

		uint *indicescpy = new uint[numIndices];
		memcpy(indicescpy,indices,sizeof(uint)*numIndices);

		strip.pGrps->indices =  (uint*)vcacheopt_forsyth((void*)indicescpy,numIndices/3,numVertices,m_cachesize,VERTEX_INDEX_TYPE_UINT32);
		strip.pGrps->numIndices = numIndices;

		return strip;
	}

	virtual booln SupportsType(EXPrimitiveType type){
		return type == EXPRIM_TRIANGLE_LIST;
	}

	virtual EXPrimitiveType OutType() {
		return EXPRIM_TRIANGLE_LIST;
	}

	ForsythOptimizer(uint cachesize) {
		m_cachesize	= cachesize;
	}
private:
	uint		m_cachesize;
};

void EXModel_optimizeONLYREORDER(EXModel *imodel){
	ReOrderOptimizer opt;
	EXModel_optimize(imodel,opt);
}

void EXModel_optimizeTIPSIFY(EXModel *imodel,uint cachesize){
	TipsifyOptimizer opt(cachesize);
	EXModel_optimize(imodel,opt);
}

void EXModel_optimizeFORSYTH(EXModel *imodel,uint cachesize){
	ForsythOptimizer opt(cachesize);
	EXModel_optimize(imodel,opt);
}