#include "dxstdafx.h"
#include ".\pathmapeffect.h"
#include "Material.hpp"
#include "TexturedMaterial.h"
#include "WoodMaterial.hpp"
#include "TriangleMesh.h"
#include "Transformed.h"
#include "Entity.h"
#include "SubEntity.h"
#include "shlwapi.h"
#include <queue>
#include <fstream>


//! D3D vector-matrix multiplication
D3DVECTOR operator *(const D3DVECTOR& v, const D3DMATRIX& m)
{
	D3DVECTOR r;
	r.x = v.x * m._11 + v.y * m._21 + v.z * m._31 + m._41;
	r.y = v.x * m._12 + v.y * m._22 + v.z * m._32 + m._42;
	r.z = v.x * m._13 + v.y * m._23 + v.z * m._33 + m._43;
	float h = v.x * m._14 + v.y * m._24 + v.z * m._34 + m._44;
	if(h > 0.00001f || h < 0.00001f)
	{
		r.x /= h;
		r.y /= h;
		r.z /= h;
	}
	return r;
}

//! method name strings to be displayed on screen
const wchar_t* PathMapEffect::Method::methodNames[10] =
{
	L"PRM",
	L"PRM texture",
	L"_",
	L"_"
	, NULL, NULL, NULL, NULL, NULL, NULL
};

//! method constants
const PathMapEffect::Method PathMapEffect::Method::PRM(0);
const PathMapEffect::Method PathMapEffect::Method::SHOWTEX(1);
const PathMapEffect::Method PathMapEffect::Method::LAST(2);

//! constructor
PathMapEffect::PathMapEffect(LPDIRECT3DDEVICE9 device)
:method(Method::PRM)
{
	NRADIONS = (4096);
	NCLUSTERS = 64;
	DEPTHMAPRES	= 512;


	float* weights = new float[NCLUSTERS];			
	unsigned int* clusterLenghts = new unsigned int[NCLUSTERS];

	clusterSweepCurrentIndex = 0;

	rayId = 1;
	this->device = device;

	//first person camera allows more freedom of movement
	camera = new CFirstPersonCamera();
	lightCamera = new CFirstPersonCamera();

	HRESULT hr;
	DWORD effectCompileFlag=0;
	
	LPD3DXBUFFER compilationErrors;
	if(FAILED(
		hr = 
			D3DXCreateEffectFromFile(
				device,
				L"pathMap.fx",
				NULL,
				NULL,
				0,
				NULL,
				&effect,
				&compilationErrors) )){
		MessageBoxA( NULL, (LPSTR)compilationErrors->GetBufferPointer(), "Failed to load effect file!", MB_OK);
		exit(-1);
	}

	//store buffers so we can reset them after rendering to texture render targets
	device->GetRenderTarget(0, &frameColorBuffer);
	device->GetDepthStencilSurface(&frameDepthStencilBuffer);
	
	//load empty texture
	D3DXCreateTextureFromFile(device, L"media\\empty.bmp", &emptyTexture);

	//set up a scene

	loadScene("media\\space.txt");

	//load hangar mesh
//	loadMesh( L"media\\hangar.x" );
//	loadMesh( L"media\\fulltexchamber.x" );

/*	//create hangar entity
	Entity e1;
	e1.owner = this;
	e1.renderMesh = renderMeshes.at(0);
	D3DXMatrixIdentity(&e1.modelWorldTransform);
//	D3DXMatrixScaling(&e1.modelWorldTransform, 20.0f, 20.0f, 20.0f);
	D3DXMatrixScaling(&e1.modelWorldTransform, 0.5f, 1.0f, 0.5f);
	D3DXMatrixIdentity(&e1.inverseTransposedModelWorldTransform);
//	D3DXMatrixScaling(&e1.inverseTransposedModelWorldTransform, 1.0f/20.0f, 1.0f/20.0f, 1.0f/20.0f);
	D3DXMatrixScaling(&e1.inverseTransposedModelWorldTransform, 1.0f/0.5f, 1.0f, 1.0f/0.5f);

	e1.createRayTraceEntity();
	
	entities.push_back(e1);


	//load 'steps' mesh
	loadMesh( L"media\\steps.x" );

	//create step entities
	for(int eitor=0; eitor < 4; eitor++)
	{
		D3DXMATRIX urr;
		D3DXMATRIX rx;		D3DXMatrixRotationY(&rx, Vector::PI * 0.5f * eitor);
		Entity e2;
		e2.owner = this;
		e2.renderMesh = renderMeshes.at(1);

		D3DXMatrixTranslation(&urr, -15.0f, -14.0f, -7.0f);
		D3DXMatrixMultiply( &e2.modelWorldTransform, &urr, &rx);
		D3DXMatrixInverse(&e2.inverseTransposedModelWorldTransform, NULL, &e2.modelWorldTransform);

		e2.createRayTraceEntity();
		entities.push_back(e2);

		D3DXMATRIX trasi, roti;
		D3DXMatrixTranslation(&trasi, -15.0f + 7.0f, 14.0f, -7.0f -7.0f);		//7.25f, 13.5, -7.25); //rot 90 -90 90 trans 7.25 13.5 -7.25
		D3DXMatrixRotationYawPitchRoll(&roti, -Vector::PI * 0.5, Vector::PI, 0.0);
		D3DXMatrixMultiply(&urr, &roti, &trasi);

		D3DXMatrixMultiply( &e2.modelWorldTransform, &urr, &rx);

		D3DXMatrixInverse(&e2.inverseTransposedModelWorldTransform, NULL, &e2.modelWorldTransform);
		e2.createRayTraceEntity();
		entities.push_back(e2);
	}
*/

	loadMesh( L"media\\fighter.x", 0, "", 1);

	//compute the surface area of the complete geometry. useful for random sampling.
	sumSurfaceArea = 0.0;
	std::vector<Entity*>::iterator entityIterator = entities.begin();
	while(entityIterator != entities.end())
	{
		sumSurfaceArea += (*entityIterator)->getSurfaceArea();
		entityIterator++;
	}

	//initialize camera
	camera->SetViewParams( &D3DXVECTOR3(0.0f, 0.0f, 4.0f), &D3DXVECTOR3(0.0f, 0.0f, 0.0f));
	D3DSURFACE_DESC fbdesc;
	frameColorBuffer->GetDesc(&fbdesc);
	camera->SetProjParams( D3DX_PI/2, (float)fbdesc.Width / fbdesc.Height, 0.1f, 300.0f );

	//create resources for entities
	createPRMTextures();

	//set up spotlight
	lightCamera->SetViewParams( &D3DXVECTOR3(5.0f, 0.0f, 0.0f), &D3DXVECTOR3(0.0f, 0.0f, 0.0f));
	lightCamera->SetProjParams( D3DX_PI/1.9, 1.0f, 0.1f, 300.0f );

	//create ray tracing kd-tree containing ray-traceable versions of entities 
	Intersectable** objs = new Intersectable*[entities.size()];
	for(int u=0; u<entities.size(); u++)
		objs[u] = entities.at(u).rayTraceEntity;
	kdtree = new KDTree(objs, entities.size());
	delete [] objs;

	//create dummy render target texture for depth map rendering
	device->CreateTexture(DEPTHMAPRES, DEPTHMAPRES, 1, D3DUSAGE_RENDERTARGET, D3DFMT_R32F, D3DPOOL_DEFAULT, &fakeTexture, NULL);
	fakeTexture->GetSurfaceLevel(0, &fakeSurface);

	//create a depthstencil texture for depth map rendering
	device->CreateTexture(DEPTHMAPRES, DEPTHMAPRES, 1,
		D3DUSAGE_DEPTHSTENCIL, D3DFMT_D24X8, D3DPOOL_DEFAULT, &depthMapTexture, NULL);
	depthMapTexture->GetSurfaceLevel(0, &depthMapDepthStencilBuffer);

#ifdef GENERATE_PATH_MAPS
	precompute();
#else
	loadPathMaps();
#endif

	//create a texture for radion data (will be used for weight computations on the GPU)
	device->CreateTexture(2 * NRADIONS / 4096, 4096, 1, 0, D3DFMT_A32B32G32R32F, D3DPOOL_DEFAULT, &radionTexture, NULL);
	radionTexture->GetSurfaceLevel(0, &radionSurface);

	//fill texture with data
	uploadRadions();

	//create weights render target
	device->CreateTexture(4096, NRADIONS / 4096, 1, D3DUSAGE_RENDERTARGET, D3DFMT_R32F, D3DPOOL_DEFAULT, &weightsTexture, NULL);
	weightsTexture->GetSurfaceLevel(0, &weightsSurface);

	//create a sytem memory duplicate of the weights render target to be able to read back weights data
	device->CreateTexture(4096, NRADIONS / 4096, 1, 0, D3DFMT_R32F, D3DPOOL_SYSTEMMEM, &sysMemWeightsTexture, NULL);
	sysMemWeightsTexture->GetSurfaceLevel(0, &sysMemWeightsSurface);

	//create a vertex buffer to be able to visualize entry radion positions
	device->CreateVertexBuffer(NRADIONS * sizeof(float) * 6, D3DUSAGE_WRITEONLY, D3DFVF_XYZ | D3DFVF_NORMAL, D3DPOOL_DEFAULT, 
		&starterVertexBuffer, NULL);
	void* pData;
	starterVertexBuffer->Lock(0, 0, &pData, 0);
	fillRadionPosArray(pData);
	starterVertexBuffer->Unlock();


	exportEntityData();

#ifdef GENERATE_PATH_MAPS
	savePathMaps();
#endif
}

PathMapEffect::~PathMapEffect(void)
{
	delete weights;
	delete clusterLenghts;

	//release all resources allocated in the constructor
	starterVertexBuffer->Release();

	depthMapTexture->Release();
	depthMapDepthStencilBuffer->Release();
	fakeTexture->Release();
	fakeSurface->Release();

	sysMemWeightsTexture->Release();
	sysMemWeightsSurface->Release();
	weightsTexture->Release();
	weightsSurface->Release();
	radionTexture->Release();
	radionSurface->Release();

	delete kdtree;
	emptyTexture->Release();
	releaseTextures();
	releaseMeshes();
	releaseEntities();

	frameColorBuffer->Release();
	frameDepthStencilBuffer->Release();

	effect->Release();
	delete camera;
	delete lightCamera;
}

void PathMapEffect::loadMesh(LPCWSTR fileName, int prmAtlasSize, const char* name, int dividePcs, bool generateUV, bool generateTBN)
{
	Mesh* mesh = new Mesh(this, fileName, prmAtlasSize, name, dividePcs, generateUV, generateTBN);
	meshes.push_back(mesh);

/*	RenderMesh** slabs = new RenderMesh*[dividePcs];
	int* slabNTris = new int[dividePcs];
	int nTris = renderMesh->mesh->GetNumFaces();


	if(dividePcs == 1)
	{
		renderMesh->slabIndex = 0;
		slabs[0] = renderMesh;
		slabNTris[0] = nTris;
	}
	else
	{
		LPDIRECT3DVERTEXBUFFER9 vertexBuffer;
		renderMesh->mesh->GetVertexBuffer(&vertexBuffer);
		D3DVERTEX* vertexData;
		vertexBuffer->Lock(0,renderMesh->mesh->GetNumVertices()*renderMesh->mesh->GetNumBytesPerVertex(),(void**)&vertexData,0);
		LPDIRECT3DINDEXBUFFER9 indexBuffer;
		renderMesh->mesh->GetIndexBuffer(&indexBuffer);
		unsigned short* indexData;
		indexBuffer->Lock(0,nTris*3*sizeof(unsigned short),(void**)&indexData,0);

		Tri* tris = new Tri[nTris];
		//partition to small meshes
		for(int g=0; g<nTris; g++)
		{
			tris[g].origMeshIndex = g;
			tris[g].pos =	(vertexData[indexData[g * 3]].pos + 
							vertexData[indexData[g * 3 + 1]].pos + 
							vertexData[indexData[g * 3 + 2]].pos) * 0.33333333333333;
			tris[g].normal =	(vertexData[indexData[g * 3]].normal + 
							vertexData[indexData[g * 3 + 1]].normal + 
							vertexData[indexData[g * 3 + 2]].normal);
			tris[g].normal.normalize();
		}


		clusterTrisKMeans(tris, nTris, dividePcs, slabNTris);
		int triClusterStart = 0;

		for(int ict=0; ict<dividePcs; ict++)
		{
			slabs[ict] = new RenderMesh();
			slabs[ict]->prmAtlasSize = renderMesh->prmAtlasSize;
			strcpy(slabs[ict]->name, renderMesh->name);
			slabs[ict]->slabIndex = ict;
			slabs[ict]->rayTraceMaterial = renderMesh->rayTraceMaterial;
			slabs[ict]->nSubsets = renderMesh->nSubsets;
			slabs[ict]->textures = new LPDIRECT3DTEXTURE9[renderMesh->nSubsets];
			for(int qu=0; qu < renderMesh->nSubsets; qu++)
				slabs[ict]->textures[qu] = renderMesh->textures[qu];
			// count vertices
			unsigned short* ill = new unsigned short[renderMesh->mesh->GetNumVertices()];
			for(int zzz=0; zzz<renderMesh->mesh->GetNumVertices(); zzz++)
				ill[zzz] = 0;
			for(int rmi = triClusterStart; rmi<triClusterStart + slabNTris[ict]; rmi++)
			{
				ill[indexData[tris[rmi].origMeshIndex*3]] = 1;
				ill[indexData[tris[rmi].origMeshIndex*3+1]] = 1;
				ill[indexData[tris[rmi].origMeshIndex*3+2]] = 1;
			}

			int nVertices = 0;
			for(int ccc=0; ccc<renderMesh->mesh->GetNumVertices(); ccc++)
				if(ill[ccc])
					nVertices++;

			// create new mesh
			HRESULT dhre = D3DXCreateMeshFVF(
				slabNTris[ict],
				nVertices,
				0,
				D3DFVF_XYZ | D3DFVF_NORMAL | D3DFVF_TEX4 | D3DFVF_TEXCOORDSIZE2(0) | D3DFVF_TEXCOORDSIZE2(1) |
				D3DFVF_TEXCOORDSIZE3(2) | D3DFVF_TEXCOORDSIZE3(3),
				device,
				&slabs[ict]->mesh);
			// fill with tris
			LPDIRECT3DVERTEXBUFFER9 svertexBuffer;
			slabs[ict]->mesh->GetVertexBuffer(&svertexBuffer);
			D3DVERTEX* svertexData;
			svertexBuffer->Lock(0, nVertices*slabs[ict]->mesh->GetNumBytesPerVertex(),(void**)&svertexData,0);
			LPDIRECT3DINDEXBUFFER9 sindexBuffer;
			slabs[ict]->mesh->GetIndexBuffer(&sindexBuffer);
			unsigned short* sindexData;
			sindexBuffer->Lock(0,slabNTris[ict]*3*sizeof(unsigned short),(void**)&sindexData,0);

			int ufi = 0;
			for(int ifi=0; ifi<renderMesh->mesh->GetNumVertices(); ifi++)
				if(ill[ifi])
				{
					svertexData[ufi] = vertexData[ifi];
					ill[ifi] = ufi;
					ufi++;
				}
				else
					ill[ifi] = 0xffff;

			for(int trifi=0; trifi<slabNTris[ict]; trifi++)
			{
				sindexData[trifi*3] = ill[indexData[tris[trifi+triClusterStart].origMeshIndex*3]];
				sindexData[trifi*3+1] = ill[indexData[tris[trifi+triClusterStart].origMeshIndex*3+1]];
				sindexData[trifi*3+2] = ill[indexData[tris[trifi+triClusterStart].origMeshIndex*3+2]];
			}

			svertexBuffer->Unlock();
			sindexBuffer->Unlock();
			svertexBuffer->Release();
			sindexBuffer->Release();

			triClusterStart += slabNTris[ict];
		}

		vertexBuffer->Unlock();
		indexBuffer->Unlock();
		vertexBuffer->Release();
		indexBuffer->Release();

		renderMesh->mesh->Release();
		delete renderMesh;
	}

	for(unsigned int fi=0; fi < dividePcs; fi++)
	{
		RenderMesh*& renderMesh = slabs[fi];

		//lock the buffers and create ray tracing meshes from the data
		LPDIRECT3DVERTEXBUFFER9 vertexBuffer;
		renderMesh->mesh->GetVertexBuffer(&vertexBuffer);
		D3DVERTEX* vertexData;
		vertexBuffer->Lock(0,renderMesh->mesh->GetNumVertices()*renderMesh->mesh->GetNumBytesPerVertex(),(void**)&vertexData,0);
		LPDIRECT3DINDEXBUFFER9 indexBuffer;
		renderMesh->mesh->GetIndexBuffer(&indexBuffer);
		unsigned short* indexData;
		indexBuffer->Lock(0,renderMesh->mesh->GetNumFaces()*3*sizeof(unsigned short),(void**)&indexData,0);

		//create a TriangleMesh for ray-tracing
		renderMesh->rayTraceMesh = new TriangleMesh(renderMesh->rayTraceMaterial, indexData, renderMesh->mesh->GetNumFaces(),
			vertexData, renderMesh->mesh->GetNumVertices());

		vertexBuffer->Unlock();
		indexBuffer->Unlock();
		vertexBuffer->Release();
		indexBuffer->Release();

		renderMesh->slabIndex = fi;
		renderMesh->generateUVAtlas();
		renderMesh->buildEdgeVertexBuffer(device);
		renderMeshes.push_back(renderMesh);
	}
	delete [] slabs;*/
}

LPDIRECT3DTEXTURE9 PathMapEffect::loadTexture(LPCWSTR fileName, Material** rayTraceMaterial)
{
	if(fileName == NULL || wcscmp(fileName, L"") == 0)
		return NULL;
	wchar_t* mediaFileName = new wchar_t[wcslen(fileName) + 64];
	//we assume the x file was in folder .\media
	wcscpy(mediaFileName, L"media\\");
	wcscat(mediaFileName, fileName);
	LPDIRECT3DTEXTURE9 tex;

	D3DXIMAGE_INFO bobo;
	if(S_OK != 
		D3DXCreateTextureFromFileEx(device, mediaFileName, D3DX_DEFAULT, D3DX_DEFAULT, 1, 0,
		D3DFMT_FROM_FILE, D3DPOOL_MANAGED, D3DX_DEFAULT, D3DX_DEFAULT, 0, &bobo, NULL, &tex
		))
	{
		 MessageBox(NULL, mediaFileName, L"Could not load texture file!", MB_OK);
		 return NULL;
	}
	
	materialTextures.push_back(tex);

	if(rayTraceMaterial != NULL)
	{
		D3DLOCKED_RECT lrect;
		HRESULT hr = tex->LockRect(0, &lrect, NULL, D3DLOCK_READONLY);
		LPDIRECT3DSURFACE9 texsurf; 
		tex->GetSurfaceLevel(0, &texsurf);
		D3DSURFACE_DESC desc;
		texsurf->GetDesc(&desc);
		*rayTraceMaterial = new TexturedMaterial(lrect.pBits, lrect.Pitch, desc.Width);
		texsurf->Release();
		tex->UnlockRect(0);
	}
	return tex;
}

void PathMapEffect::releaseTextures()
{
	std::vector<LPDIRECT3DTEXTURE9>::iterator i = materialTextures.begin();
	while(i != materialTextures.end())
	{
		(*i)->Release();
		i++;
	}

	std::vector<Material*>::iterator z = rayTraceMaterials.begin();
	while(z != rayTraceMaterials.end())
	{
		delete (*z);
		z++;
	}
}

void PathMapEffect::releaseMeshes()
{
	std::vector<PathMapEffect::RenderMesh*>::iterator i = renderMeshes.begin();
	while(i != renderMeshes.end())
	{
//		if((*i)->bumpTexture)
//			(*i)->bumpTexture->Release();
		if((*i)->normalTexture)
			(*i)->normalTexture->Release();
		(*i)->mesh->Release();
		delete (*i)->rayTraceMesh;
		if((*i)->edgeVertexBuffer)
			(*i)->edgeVertexBuffer->Release();
		delete *i;
		i++;
	}
}

void PathMapEffect::renderWithPRM()
{
	// first pass: render depth

	device->SetRenderTarget(0, fakeSurface);
	device->SetDepthStencilSurface(depthMapDepthStencilBuffer);
	device->Clear( 0, NULL, D3DCLEAR_ZBUFFER, D3DCOLOR_ARGB(255, 0, 0, 0), 1.0f, 0 );
	//no color writes
	device->SetRenderState(D3DRS_COLORWRITEENABLE, 0);
	//render back faces (avoids Z-fighting, no need for comparison bias)
	device->SetRenderState(D3DRS_CULLMODE, D3DCULL_CW);
	
	if( SUCCEEDED( device->BeginScene() ) )
	{
		effect->SetTechnique("Depth");
		UINT nPasses;
		effect->Begin(&nPasses, 0);
		effect->BeginPass(0);
		//loop through all entities, all mesh subsets, set proper transformations

		std::vector<Entity*>::iterator entityIterator = entities.begin();
		while(entityIterator != entities.end())
		{
			effect->SetMatrix("modelToProjMatrix", 
				&( entityIterator->modelWorldTransform * *lightCamera->GetViewMatrix() * *lightCamera->GetProjMatrix() ) );
			effect->CommitChanges();
			unsigned int nSubsets = entityIterator->renderMesh->nSubsets;
			for(int i = 0; i< nSubsets; i++)
			{
				entityIterator->renderMesh->mesh->DrawSubset(i);
			}
			entityIterator++;
		}

		effect->EndPass();
		effect->End();
		device->EndScene();
	}

	//reset front face rendering, color writes
	device->SetRenderState(D3DRS_CULLMODE, D3DCULL_CCW);
	HRESULT hr = S_OK;
	hr = device->SetRenderState(D3DRS_COLORWRITEENABLE, D3DCOLORWRITEENABLE_ALPHA| D3DCOLORWRITEENABLE_BLUE| D3DCOLORWRITEENABLE_GREEN | D3DCOLORWRITEENABLE_RED);

	// 2. pass: compute weights

	// simple parallel computation for all pixels: no 3D, depth, shadows, only a full-texture quad
	hr = device->SetRenderState(D3DRS_ZENABLE, D3DZB_FALSE);
	hr = device->SetRenderState(D3DRS_STENCILENABLE, false);
	hr = device->SetRenderTarget(0,weightsSurface);
	hr = device->SetDepthStencilSurface(NULL);
	D3DXVECTOR3 lightPos = *lightCamera->GetEyePt();
	D3DXVECTOR3 lightDir = *lightCamera->GetWorldAhead();
	lightDir /= D3DXVec3Length( &lightDir );
	float ffl = parameters->Get(fLightScale) * 10.0f;
	D3DXVECTOR3 lightPower(ffl, ffl, ffl);

	device->Clear( 0, NULL, D3DCLEAR_TARGET,	D3DCOLOR_XRGB(0,0,0), 1.0f, 0 );

	if( SUCCEEDED( device->BeginScene() ) ){
		if( effect != NULL ){
			D3DXHANDLE hTechnique = NULL;
			hTechnique = effect->GetTechniqueByName((LPSTR)"ComputeWeights");
			if(hTechnique==NULL){
				return;
			}
			effect->SetTechnique( hTechnique );

			UINT nPasses = 0;
			effect->Begin( &nPasses, 0 );
			for(UINT j=0;j<nPasses;j++){ 
				effect->BeginPass(j);
				hr = effect->SetTexture("radions", radionTexture);
				static float opttme[9] = {0.5f, 0.0f, 0.0f,
										0.0f, -0.5f, 0.0f,
										0.5f + (0.5f / DEPTHMAPRES), 0.5f + (0.5f / DEPTHMAPRES), 1.0f};

				//set global params
				effect->SetFloatArray("occProjToTexMatrix", opttme, 9);
				effect->SetMatrix("occWorldToProjMatrix", &(*lightCamera->GetViewMatrix() * *lightCamera->GetProjMatrix()));

				effect->SetTexture("depthMap", depthMapTexture);
				hr = effect->SetInt("nRadionColumns", NRADIONS / 4096);
				hr = effect->SetFloatArray("lightPower", (float*)&lightPower, 3);
				hr = effect->SetFloatArray("lightPos", (float*)&lightPos, 3);
				hr = effect->SetFloatArray("lightDir", (float*)&lightDir, 3);
				effect->CommitChanges();
				renderFullScreen();
				effect->EndPass();
			}
			effect->End();
		}
		device->EndScene();
	}

	// read the weights back

	D3DLOCKED_RECT rData;
	hr = device->GetRenderTargetData(weightsSurface, sysMemWeightsSurface);
	hr =  sysMemWeightsSurface->LockRect(&rData, NULL, D3DLOCK_READONLY);
	float* allEntryWeights = (float*)rData.pBits;

	// average weights per cluster
	float sumWeightsAll = 0.0;
	unsigned int iRadion = 0;
	for(int iCluster=0; iCluster < NCLUSTERS; iCluster++)
	{
		weights[iCluster] = 0.0;
		float clusterrad = 0.0;
		for(int clusterSummer=0; clusterSummer < clusterLenghts[iCluster]; clusterSummer++, iRadion++)
		{
			float radrad = bushStarters[iRadion].radiance.sum();
			weights[iCluster] += allEntryWeights[iRadion] * radrad;
			clusterrad += radrad;
		}
		if(clusterrad > 0.01)
			weights[iCluster] /= clusterrad; //(double)clusterLenghts[iCluster];
		else
			weights[iCluster] = 0.0f;
//		if(iCluster != TEST_CLUST)
//			weights[iCluster] = 0.0;
//		if(weights[iCluster] > 0.005)
//			weights[iCluster] = 0.005;
		sumWeightsAll += weights[iCluster];
	}
	sysMemWeightsSurface->UnlockRect();

	// 3. pass: render scene using weights to combine PRM texture atlases

	
	device->SetRenderTarget(0, frameColorBuffer);
	device->SetDepthStencilSurface(frameDepthStencilBuffer);
	// use backface culling, depth test
	hr = device->SetRenderState(D3DRS_CULLMODE, D3DCULL_CCW);
	hr = device->SetRenderState(D3DRS_ZENABLE, D3DZB_TRUE);

	device->Clear( 0, NULL, D3DCLEAR_TARGET | D3DCLEAR_ZBUFFER,	D3DCOLOR_XRGB(0,0,0), 1.0f, 0 );
	
	if( SUCCEEDED( device->BeginScene() ) )
	{
		effect->SetTechnique("walk");
		UINT nPasses;
		effect->Begin(&nPasses, 0);
		effect->BeginPass(0);

		static float opttme[9] = {0.5f, 0.0f, 0.0f,
								0.0f, -0.5f, 0.0f,
								0.5f + (0.5f / DEPTHMAPRES), 0.5f + (0.5f / DEPTHMAPRES), 1.0f};

		//set global params
		effect->SetFloatArray("occProjToTexMatrix", opttme, 9);
		effect->SetMatrix("occWorldToProjMatrix", &(*lightCamera->GetViewMatrix() * *lightCamera->GetProjMatrix()));

		effect->SetTexture("depthMap", depthMapTexture);

		//loop through entities
		std::vector<PathMapEffect::Entity>::iterator entityIterator = entities.begin();
		while(entityIterator != entities.end())
		{
			//set entity params
			// nearestIdx -> bushId
			float* weightsa = new float[entityIterator->nNearClusters];
			for(unsigned int y=0; y<entityIterator->nNearClusters; y++)
			{
//				Entity e = *entityIterator;
				weightsa[y] = weights[entityIterator->nearClusterIndices[y]];
			}
			hr = effect->SetFloatArray("weightsa", weightsa, entityIterator->nNearClusters);
			effect->SetMatrix("modelToWorldMatrix", &entityIterator->modelWorldTransform);
			effect->SetMatrix("inverseTransposedModelToWorldMatrix", &entityIterator->inverseTransposedModelWorldTransform);
			D3DXMATRIX t = entityIterator->modelWorldTransform;
			if(parameters->Get(bLookFromLight))
				effect->SetMatrix("modelToProjMatrix", &(entityIterator->modelWorldTransform * *lightCamera->GetViewMatrix()  * *lightCamera->GetProjMatrix()  ));
			else
			{
				D3DXVECTOR3 wa = *camera->GetWorldAhead();
				wa = wa * (1.0 / D3DXVec3Length(&wa));
				D3DXVECTOR3 eye = *camera->GetEyePt();
				D3DXVECTOR3 shup = -eye * (1.0 / D3DXVec3Length(&eye));
				float angle = acos(D3DXVec3Dot(&wa, &shup));
				D3DXMATRIX maro;
				D3DXVECTOR3 rotax;
				D3DXVec3Cross(&rotax, &wa, &shup);
				D3DXMatrixRotationAxis(&maro, &rotax, angle);
				effect->SetMatrix("modelToProjMatrix", &(entityIterator->modelWorldTransform * maro * *camera->GetViewMatrix() * *camera->GetProjMatrix()  ));
			}

			effect->SetTexture("filteredAtlas", entityIterator->prmTexture);
			effect->SetTexture("bumpMap", entityIterator->renderMesh->bumpTexture);
			effect->SetTexture("normalMap", entityIterator->renderMesh->normalTexture);
			hr = effect->SetFloatArray("lightPower", (float*)&lightPower, 3);
			hr = effect->SetFloatArray("lightPos", (float*)&lightPos, 3);
			hr = effect->SetFloatArray("lightDir", (float*)&lightDir, 3);
			
			int prmnt[2] = {entityIterator->renderMesh->prmxres / entityIterator->renderMesh->prmAtlasSize, 
				entityIterator->renderMesh->prmyres / entityIterator->renderMesh->prmAtlasSize};
			hr = effect->SetIntArray("prmAtlasTiles", prmnt, 2);
			hr = effect->SetFloatArray("atlasHalfPixel", (float*)&Vector(
				0.5 / entityIterator->renderMesh->prmxres, 0.5 / entityIterator->renderMesh->prmyres, 0.0), 2);

			unsigned int nSubsets = entityIterator->renderMesh->nSubsets;
			for(int i = 0; i< nSubsets; i++)
			{
				//set subset material texture
				if(entityIterator->renderMesh->textures[i])
					effect->SetTexture("brdfMap", entityIterator->renderMesh->textures[i]);
				else
					effect->SetTexture("brdfMap", emptyTexture);
				effect->CommitChanges();
				entityIterator->renderMesh->mesh->DrawSubset(i);
			}
			entityIterator++;

			delete weightsa;
		}
		effect->EndPass();
		effect->End();
		device->EndScene();
	}

	if(!parameters->Get(bLookFromLight))
	if( SUCCEEDED( device->BeginScene() ) )
	{
		effect->SetTechnique("torch");
		UINT nPasses;
		effect->Begin(&nPasses, 0);
		effect->BeginPass(0);

		D3DXMATRIX scaleShip;
		D3DXMatrixScaling(&scaleShip, 0.05f, 0.05f, 0.05f);

		effect->SetTexture("brdfMap", renderMeshes[renderMeshes.size()-1]->textures[0]);
		effect->SetMatrix("modelToProjMatrix", &(scaleShip * *lightCamera->GetWorldMatrix() * *camera->GetViewMatrix()  * *camera->GetProjMatrix()  ));

		effect->CommitChanges();
		renderMeshes[renderMeshes.size()-1]->mesh->DrawSubset(0);

		effect->EndPass();
		effect->End();
		device->EndScene();
	}

}

HRESULT PathMapEffect::RenderMesh::setVertexFormat(DWORD fvf, LPDIRECT3DDEVICE9 device)
{
	LPD3DXMESH tempMesh;

	//clone the mesh to the appropriate format
    HRESULT hr = mesh->CloneMeshFVF( mesh->GetOptions(), 
                                  fvf , 
                                  device, &tempMesh );
	if(hr == S_OK)
	{
		DWORD* padj = new DWORD[mesh->GetNumFaces() * 3];
		mesh->GenerateAdjacency(0.00001f, padj);
		delete padj;
		//forget he old mesh
		mesh->Release();
		//use the cloned mesh
		mesh = tempMesh;
	}
	return hr;
}

HRESULT PathMapEffect::RenderMesh::generateUVAtlas()
{
	LPD3DXMESH tempMesh;

	float maxStretchApplied;
	unsigned int nCharts;

	HRESULT hr =
		D3DXUVAtlasCreate(
			mesh,		//	LPD3DXMESH pMesh,
			0,			//	UINT dwMaxChartNumber,
			1.0f,		//	FLOAT fMaxStretch,
			prmAtlasSize - 4,		//	UINT dwWidth,
			prmAtlasSize - 4,		//	UINT dwHeight,
			2.0f,		//	FLOAT fGutter,
			1,			//	DWORD dwTextureIndex,
			NULL,		//	CONST DWORD * pdwAdjacency,
			NULL,		//	CONST CHAR * pcFalseEdges,
			NULL,		//	FLOAT * pfIMTArray,
			NULL,		//	LPD3DXUVATLASCB pCallback,
			0.001f,		//	FLOAT fCallbackFrequency,
            NULL,		//	LPVOID pUserContent,
			&tempMesh,	//	LPD3DXMESH * ppMeshOut,
			NULL,		//	LPD3DXBUFFER * ppFacePartitioning,
			NULL,		//	LPD3DXBUFFER * ppVertexRemapArray,
			&maxStretchApplied,	//	FLOAT * pfMaxStretchOut,
			&nCharts			//	UINT * pdwNumChartsOut
		);

	if(hr == S_OK)
	{
		//forget he old mesh
		mesh->Release();
	}

	hr = 
		D3DXComputeTangentFrameEx(
			tempMesh,					//  ID3DXMesh * pMesh,
			D3DDECLUSAGE_TEXCOORD,	// DWORD dwTextureInSemantic,
			0,						//  DWORD dwTextureInIndex,
			D3DDECLUSAGE_TEXCOORD,	// DWORD dwUPartialOutSemantic,
			2,						// DWORD dwUPartialOutIndex,
			D3DDECLUSAGE_TEXCOORD,	// DWORD dwVPartialOutSemantic,
			3,						// DWORD dwVPartialOutIndex,
			D3DDECLUSAGE_NORMAL,	// DWORD dwNormalOutSemantic,
			0,						// DWORD dwNormalOutIndex,
			(D3DXTANGENT_WRAP_UV
//			| D3DXTANGENT_DONT_ORTHOGONALIZE | D3DXTANGENT_DONT_NORMALIZE_PARTIALS)
			)& !( D3DXTANGENT_CALCULATE_NORMALS ), // DWORD dwOptions,
			NULL,					// CONST DWORD * pdwAdjacency,
			0.2,					// FLOAT fPartialEdgeThreshold,
			0.0,					// FLOAT fSingularPointThreshold,
			0.2,					// FLOAT fNormalEdgeThreshold,
			&mesh,					// ID3DXMesh ** ppMeshOut,
			NULL					// ID3DXBuffer ** ppVertexMapping
		);

	if(hr == S_OK)
	{
		//forget he old mesh
		tempMesh->Release();
	}

	LPDIRECT3DVERTEXBUFFER9 vertexBuffer;
	mesh->GetVertexBuffer(&vertexBuffer);
	D3DVERTEX* vertexData;
	vertexBuffer->Lock(0,mesh->GetNumVertices()*mesh->GetNumBytesPerVertex(),(void**)&vertexData,0);

	for(unsigned int u=0; u < mesh->GetNumVertices(); u++ )
		vertexData[u].tex1 = (vertexData[u].tex1 * (prmAtlasSize - 4) + D3DXVECTOR2(2.0,2.0)) / (float)prmAtlasSize;

	vertexBuffer->Unlock();
	SAFE_RELEASE(vertexBuffer);

	
//	D3DXSaveMeshToX(L"media/om.x", mesh, NULL, NULL, 0, 0, 1 /*DXFILEFORMAT_TEXT*/);

	return hr;
}

void PathMapEffect::renderFullScreen(float depth)
{
	float fLeftU = 0.0f, fTopV = 0.0f, fRightU = 1.0f, fBottomV = 1.0f;

    D3DSURFACE_DESC dtdsdRT;
    PDIRECT3DSURFACE9 pSurfRT;

    // Acquire render target width and height
    device->GetRenderTarget(0, &pSurfRT);
    pSurfRT->GetDesc(&dtdsdRT);
    pSurfRT->Release();

    // Ensure that we're directly mapping texels to pixels by offset by 0.5
    // For more info see the doc page titled "Directly Mapping Texels to Pixels"
    FLOAT fWidth5 = (FLOAT)dtdsdRT.Width - 0.5f;
    FLOAT fHeight5 = (FLOAT)dtdsdRT.Height - 0.5f;

    // Draw the quad
	struct D3DVERTEX{
		D3DXVECTOR3 pos;
		D3DXVECTOR2 tex0;
	};

    D3DVERTEX svQuad[4];

    svQuad[0].pos=D3DXVECTOR3(-1, 1, depth);
    svQuad[0].tex0 = D3DXVECTOR2(fLeftU, fTopV);

    svQuad[1].pos = D3DXVECTOR3(1, 1, depth);
    svQuad[1].tex0 = D3DXVECTOR2(fRightU, fTopV);

    svQuad[2].pos = D3DXVECTOR3(-1, -1, depth);
    svQuad[2].tex0 = D3DXVECTOR2(fLeftU, fBottomV);

    svQuad[3].pos = D3DXVECTOR3(1, -1, depth);
    svQuad[3].tex0 = D3DXVECTOR2(fRightU, fBottomV);
	
	device->SetRenderState(D3DRS_CULLMODE,D3DCULL_NONE);
	device->SetFVF(D3DFVF_XYZ | D3DFVF_TEX1 | D3DFVF_TEXCOORDSIZE2(0));
    device->DrawPrimitiveUP(D3DPT_TRIANGLESTRIP, 2, svQuad, sizeof(D3DVERTEX));
}

void PathMapEffect::move(float fElapsedTime)
{
	clusterSweepCurrentIndex += fElapsedTime * 2.0f;
	if(clusterSweepCurrentIndex > NCLUSTERS)
		clusterSweepCurrentIndex -= NCLUSTERS;
	//apply some rotation to one of the entities
	if(parameters->Get(bTurbo))
	{
		camera->FrameMove(fElapsedTime * 10.0f);
		lightCamera->FrameMove(fElapsedTime * 10.0f);
	}
	else
	{
		camera->FrameMove(fElapsedTime);
		lightCamera->FrameMove(fElapsedTime);
	}
/*	D3DXMATRIX rot;
	D3DXMatrixRotationY(&rot, fElapsedTime * 0.1f);
	D3DXMatrixMultiply( &entities.at(0).modelWorldTransform, 
						&rot,
						&entities.at(0).modelWorldTransform);
	D3DXMatrixInverse(  &entities.at(0).inverseTransposedModelWorldTransform, NULL, 
						&entities.at(0).modelWorldTransform);
	D3DXMatrixTranspose( &entities.at(0).inverseTransposedModelWorldTransform, &entities.at(0).inverseTransposedModelWorldTransform);

	if(entities.size() > 1)
	{
		D3DXMatrixTranslation(&entities.at(1).modelWorldTransform, 0.0f, parameters->Get(fSecondModelHeight) * 5.0f , 0.0f);
		D3DXMatrixTranslation(&entities.at(1).inverseTransposedModelWorldTransform, 0.0f, -parameters->Get(fSecondModelHeight) * 5.0f , 0.0f);
	}*/
}

LRESULT PathMapEffect::handleMessage( HWND hWnd, UINT uMsg, WPARAM wParam, LPARAM lParam)

{
	if(parameters->Get(bMoveLight))
		return lightCamera->HandleMessages(hWnd, uMsg, wParam, lParam);
	else
		return camera->HandleMessages(hWnd, uMsg, wParam, lParam);
}

void PathMapEffect::addUiParameters(Parameters* parameters)
{
	PathMapEffect::parameters = parameters;
	parameters->Add( bLookFromLight, "Look from light", 1);
	parameters->Add( bMoveLight, "Move light", 1);
	parameters->Add( bDots, "Entry points", 1);
	parameters->Add( bTurbo, "Turbo", 1);
	parameters->Add( fLightScale, "Tone scale", 100, 'V', 'B', convert100);
}

void PathMapEffect::setUiParameterDefaults(Parameters* parameters)
{
}

Parameters*	PathMapEffect::parameters = NULL;

void PathMapEffect::render()
{
	if(method == Method::PRM)
		renderWithPRM();
	else
		showPRMTexture();
	if(parameters->Get(bDots))
	{
		float psf = 8.0f;
		HRESULT hr = device->SetRenderState(D3DRS_POINTSIZE, *((DWORD*)&psf));
		hr = device->SetRenderState(D3DRS_ZENABLE, D3DZB_TRUE);
		if( SUCCEEDED( device->BeginScene() ) )
		{
			D3DXHANDLE hTechnique = NULL;
			hTechnique = effect->GetTechniqueByName((LPSTR)"Dots");
			effect->SetTechnique( hTechnique );
			UINT nPasses = 0;
			effect->Begin( &nPasses, 0 );
			for(UINT j=0;j<nPasses;j++){
				effect->BeginPass(j);
					hr = effect->SetTexture("depthMap",depthMapTexture);
					if(parameters->Get(bLookFromLight))
						effect->SetMatrix("worldToProjMatrix", &(*lightCamera->GetViewMatrix()  * *lightCamera->GetProjMatrix()  ));
					else
						effect->SetMatrix("worldToProjMatrix", &(*camera->GetViewMatrix()  * *camera->GetProjMatrix()  ));

							static float opttme[9] = {0.5f, 0.0f, 0.0f,
								0.0f, -0.5f, 0.0f,
								0.5f + (0.5f / DEPTHMAPRES), 0.5f + (0.5f / DEPTHMAPRES), 1.0f};

					effect->SetFloatArray("occProjToTexMatrix", opttme, 9);
					D3DXVECTOR3 lightPos = *lightCamera->GetEyePt();
					hr = effect->SetFloatArray("lightPos", (float*)&lightPos, 3);
					effect->CommitChanges();
					hr = device->SetFVF(D3DFVF_XYZ |  D3DFVF_NORMAL);
					hr = device->SetStreamSource(0, starterVertexBuffer, 0, sizeof(float) * 6);
					UINT offset = 0;
					for(int iClusterDraw=0; iClusterDraw < NCLUSTERS; iClusterDraw++)
					{
//						hr = effect->SetFloat("aClusterWeight", weights[iClusterDraw] * 10.0);
						hr = effect->SetFloat("aClusterWeight", (float)iClusterDraw);
						effect->CommitChanges();
//						if(iClusterDraw - clusterSweepCurrentIndex > -1.0 && 
//							iClusterDraw - clusterSweepCurrentIndex < 0.0	)
							device->DrawPrimitive(D3DPT_POINTLIST, offset, clusterLenghts[iClusterDraw]);
						offset += clusterLenghts[iClusterDraw];
					}
				effect->EndPass();
			}
			effect->End();
		}
		device->EndScene();
	}
}

void PathMapEffect::releaseEntities()
{
	std::vector<PathMapEffect::Entity>::iterator entityIterator = entities.begin();
	while(entityIterator != entities.end())
	{
		delete entityIterator->rayTraceEntity;
		entityIterator->prmSurface->Release();
		entityIterator->prmTexture->Release();
		entityIterator++;
	}	
}

void PathMapEffect::sampleSphereDirection(Vector& outDir)
{
	do{
	outDir = Vector(-1.0 + 2.0 * (float)rand() / RAND_MAX, -1.0 + 2.0 * (float)rand() / RAND_MAX, -1.0 + 2.0 * (float)rand() / RAND_MAX);
	}while(outDir.norm2() > 1.0);
	outDir.normalize();
}

void PathMapEffect::sampleShootingDiffuseDirection(int depth, const Vector& normal, Vector& outDir)
{
	Vector u, v;
	if(fabsf(normal[0]) < 0.9f)
	{
		u.set(0.0f, -normal[2], normal[1]);
		u *= 1.0f / sqrtf(normal[2] * normal[2] + normal[1] * normal[1]);
	}
	else
	{
		u.set(normal[2], 0.0f, -normal[0]);
		u *= 1.0f / sqrtf(normal[2] * normal[2] + normal[0] * normal[0]);
	}
	v.setCrossProduct(normal, u);

	float phi = 2.0f * 3.14159265358979323846f * (float)rand() / RAND_MAX;
	float xi2 = (float)rand() / RAND_MAX;
	float cosPhi = cos(phi);
	float sinPhi = sin(phi);
	float cosTheta = sqrtf(xi2);
	float sinTheta = sqrtf(1.0f - xi2);

	outDir.setScaled(sinTheta * cosPhi, v);
	outDir.addScaled(sinTheta * sinPhi, u);
	outDir.addScaled(cosTheta, normal);
}

void PathMapEffect::precompute()
{
	// generate entry points
	for(unsigned int cRad=0; cRad < NRADIONS; cRad++)
	{
		Radion starter;
		sampleSurfaceRadion(starter);
		//sampleSurfaceRadionUniform(starter);
		bushStarters.push_back(starter);
	}

	// sort entry radions into clusters
	Radion* entryArray = (Radion*)&*bushStarters.begin();
	clusterRadions(entryArray, bushStarters.size(), 0);
	clusterRadionsKMeans();

	// for every entity, find the most relevant clusters
	std::vector<PathMapEffect::Entity>::iterator entityIterator = entities.begin();
	while(entityIterator != entities.end())
	{
		entityIterator->findNearClusters(bushStarters, NCLUSTERS);
		entityIterator++;
	}

	// for every entry radion, shoot a bush of radions, and add their
	// contributions to all PRMs of all entities
	unsigned int iCluster = 0;
	std::vector<Radion> bushRadions;
	for(int iStarter = 0; iStarter < NRADIONS; )
	{
		bushRadions.clear();
		for(int iric=0; iric < clusterLenghts[iCluster]; iric++, iStarter++)
			shootRadionBush(bushStarters[iStarter], bushRadions);
		std::vector<PathMapEffect::Entity>::iterator entityIterator = entities.begin();
		while(entityIterator != entities.end())
		{
			entityIterator->renderPRM(bushRadions, iCluster);
			entityIterator++;
		}
		iCluster++;
	}

	//scale down multiple pixel writes
	entityIterator = entities.begin();
	while(entityIterator != entities.end())
	{
		entityIterator->normalizePRM();
		entityIterator++;
	}
}

int compareX(const void* a, const void* b)
{
	if( ((const Radion*)a)->position.x < ((const Radion*)b)->position.x )
		return -1;
	else
		return 1;
}

int compareY(const void* a, const void* b)
{
	if( ((const Radion*)a)->position.y < ((const Radion*)b)->position.y )
		return -1;
	else
		return 1;
}

int compareZ(const void* a, const void* b)
{
	if( ((const Radion*)a)->position.z < ((const Radion*)b)->position.z )
		return -1;
	else
		return 1;
}

int compareDirX(const void* a, const void* b)
{
	if( ((const Radion*)a)->normal.x < ((const Radion*)b)->normal.x )
		return -1;
	else
		return 1;
}

int compareDirY(const void* a, const void* b)
{
	if( ((const Radion*)a)->normal.y < ((const Radion*)b)->normal.y )
		return -1;
	else
		return 1;
}

int compareDirZ(const void* a, const void* b)
{
	if( ((const Radion*)a)->normal.z < ((const Radion*)b)->normal.z )
		return -1;
	else
		return 1;
}


void PathMapEffect::clusterRadionsKMeans()
{
	Radion centroids[NCLUSTERS];
	std::vector<Radion> clusters[NCLUSTERS];
	//initial clusters: uniform length
	for(unsigned int i=0; i<NCLUSTERS; i++)
		clusterLenghts[i] = NRADIONS / NCLUSTERS;
	for(unsigned int iKMeans = 0; iKMeans < 128; iKMeans++)
	{
		//find centroids
		unsigned int iRadion = 0;
		for(unsigned int i=0; i<NCLUSTERS; i++)
		{
			centroids[i].position = Vector::RGBBLACK;
			centroids[i].normal = Vector::RGBBLACK;
			for(unsigned int iRadionInCluster=0; iRadionInCluster < clusterLenghts[i]; iRadionInCluster++, iRadion++)
			{
				centroids[i].position += bushStarters.at(iRadion).position;
				centroids[i].normal += bushStarters.at(iRadion).normal;
			}
			centroids[i].position *= 1.0f / (float)clusterLenghts[i];
			centroids[i].normal.normalize();
		}
		
		for(unsigned int i=0; i<NCLUSTERS; i++)
			clusters[i].clear();

		//sort radions to centroids
		iRadion = 0;
		for(unsigned int i=0; i<NCLUSTERS; i++)
		{
			for(unsigned int iRadionInCluster=0; iRadionInCluster < clusterLenghts[i]; iRadionInCluster++, iRadion++)
			{
				unsigned int minimumDistanceClusterIndex = 0;
				float minimumDistance = FLT_MAX;
				for(unsigned int u=0; u<NCLUSTERS; u++)
				{
					float dirDist = (bushStarters.at(iRadion).normal * centroids[u].normal);
					float dist = (bushStarters.at(iRadion).position - centroids[u].position).norm() * pow(6.0, 1.0 - (double)dirDist);
					if(dist < minimumDistance)
					{
						minimumDistanceClusterIndex = u;
						minimumDistance = dist;
					}
				}
				clusters[minimumDistanceClusterIndex].push_back( bushStarters.at(iRadion) );
			}
		}
		//refill bushStarters, set cluster lengths
		iRadion = 0;
		for(unsigned int i=0; i<NCLUSTERS; i++)
		{
			clusterLenghts[i] = clusters[i].size();
			for(unsigned int iRadionInCluster=0; iRadionInCluster < clusterLenghts[i]; iRadionInCluster++, iRadion++)
			{
				bushStarters.at(iRadion) = clusters[i].at(iRadionInCluster);
			}
		}
		//eliminate empty clusters
		for(unsigned int i=1; i<NCLUSTERS; i++)
		{
			if(clusterLenghts[i] == 0)
			{
				clusterLenghts[i] = clusterLenghts[i-1] >> 1;
				clusterLenghts[i-1] -= clusterLenghts[i-1] >> 1;
			}
		}
		for(int i=NCLUSTERS - 1; i >= 0; i--)
		{
			if(clusterLenghts[i] == 0)
			{
				clusterLenghts[i] = clusterLenghts[i+1] >> 1;
				clusterLenghts[i+1] -= clusterLenghts[i+1] >> 1;
			}
		}
	}
}

/*void PathMapEffect::clusterTrisKMeans(Tri* triArray, int nTris, int nClusters, int* clusterLenghts)
{
	Tri* centroids = new Tri[nClusters];
	std::vector<Tri>* result = new std::vector<Tri>[nClusters];

	//initial clusters: uniform length
	for(unsigned int i=0; i<nClusters; i++)
		clusterLenghts[i] = nTris / nClusters;
	for(unsigned int iKMeans = 0; iKMeans < 128; iKMeans++)
	{
		//find centroids
		unsigned int iTri = 0;
		for(unsigned int i=0; i<nClusters; i++)
		{
			centroids[i].pos = Vector::RGBBLACK;
			centroids[i].normal = Vector::RGBBLACK;
			for(unsigned int iTriInCluster=0; iTriInCluster < clusterLenghts[i]; iTriInCluster++, iTri++)
			{
				centroids[i].pos += triArray[iTri].pos;
				centroids[i].normal += triArray[iTri].normal;
			}
			centroids[i].pos *= 1.0f / (float)clusterLenghts[i];
			centroids[i].normal.normalize();
		}
		
		for(unsigned int i=0; i<nClusters; i++)
			result[i].clear();

		//sort radions to centroids
		iTri = 0;
		for(unsigned int i=0; i<nClusters; i++)
		{
			for(unsigned int iTriInCluster=0; iTriInCluster < clusterLenghts[i]; iTriInCluster++, iTri++)
			{
				unsigned int minimumDistanceClusterIndex = 0;
				float minimumDistance = FLT_MAX;
				for(unsigned int u=0; u<nClusters; u++)
				{
					float dirDist = (triArray[iTri].normal * centroids[u].normal);
					float dist = (triArray[iTri].pos - centroids[u].pos).norm() * pow(6.0, 1.0 - (double)dirDist);
					if(dist < minimumDistance)
					{
						minimumDistanceClusterIndex = u;
						minimumDistance = dist;
					}
				}
				result[minimumDistanceClusterIndex].push_back( triArray[iTri] );
			}
		}
		//refill bushStarters, set cluster lengths
		iTri = 0;
		for(unsigned int i=0; i<nClusters; i++)
		{
			clusterLenghts[i] = result[i].size();
			for(unsigned int iTriInCluster=0; iTriInCluster < clusterLenghts[i]; iTriInCluster++, iTri++)
			{
				triArray[iTri] = result[i].at(iTriInCluster);
			}
		}
		//eliminate empty clusters
		for(unsigned int i=1; i<nClusters; i++)
		{
			if(clusterLenghts[i] == 0)
			{
				clusterLenghts[i] = clusterLenghts[i-1] >> 1;
				clusterLenghts[i-1] -= clusterLenghts[i-1] >> 1;
			}
		}
		for(int i=nClusters - 1; i >= 0; i--)
		{
			if(clusterLenghts[i] == 0)
			{
				clusterLenghts[i] = clusterLenghts[i+1] >> 1;
				clusterLenghts[i+1] -= clusterLenghts[i+1] >> 1;
			}
		}
	}
	delete [] centroids;
	delete [] result;
}
*/

int PathMapEffect::clusterRadions(Radion* partition, int psize, char axis)
{
/*	if(psize < 2)
		return 1;
	if(axis == 0)
		qsort(partition, psize, sizeof(Radion), compareDirX);
	else if(axis == 1)
		qsort(partition, psize, sizeof(Radion), compareDirY);
	else if(axis == 2)
		qsort(partition, psize, sizeof(Radion), compareDirZ);
	else if(axis == 3)
		qsort(partition, psize, sizeof(Radion), compareX);
	else if(axis == 4)
		qsort(partition, psize, sizeof(Radion), compareY);
	else if(axis == 5)
		qsort(partition, psize, sizeof(Radion), compareZ);
	clusterRadions(partition, psize >> 1, (axis+1)%6);
	clusterRadions(partition + (psize >> 1), psize - (psize >> 1), (axis+1)%6);
	return 1;
/*/	if(psize < 2)
		return 1;
	if(axis == 0)
		qsort(partition, psize, sizeof(Radion), compareX);
	else if(axis == 1)
		qsort(partition, psize, sizeof(Radion), compareY);
	else if(axis == 2)
		qsort(partition, psize, sizeof(Radion), compareZ);
	clusterRadions(partition, psize >> 1, (axis+1)%3);
	clusterRadions(partition + (psize >> 1), psize - (psize >> 1), (axis+1)%3);
	return 1;//*/
}


void PathMapEffect::shootRadionBush(Radion& starter, std::vector<Radion>& bushRadions)
{
	bushRadions.push_back(starter);

	int nPhotonsShotForLight = 1;	//branching factor
	for(int iPhoton = 0; iPhoton < nPhotonsShotForLight; iPhoton++)
	{
		unsigned int depth = 0;
		ray.id = rayId++;
		ray.isShadowRay = false;
		ray.origin = starter.position;
		Vector power = starter.radiance;
		float prob = starter.probability;
		prob *= nPhotonsShotForLight;
		power *= 1.0f / nPhotonsShotForLight;
		sampleShootingDiffuseDirection(depth, starter.normal, ray.dir);

		for(;;depth++)
		{
			kdtree->traverse(ray, hitRec, 0.0f, FLT_MAX);
			if(hitRec.isIntersect)
			{
				Radion nr;
				nr.position = hitRec.point;
				nr.normal = hitRec.normal;
				nr.radiance = power;
				nr.radiance %= hitRec.material->getTextureDiffuseBrdf(hitRec.texUV);
				nr.probability = prob;
				bushRadions.push_back(nr);
			}
			else
				break;
			if(depth >= 3)
				break;
			float rrRandom = (float)rand() / RAND_MAX;
			float diffuseAlbedo = hitRec.material->getTextureDiffuseAlbedo(hitRec.texUV);
			float idealAlbedo = hitRec.material->getTextureIdealAlbedo(hitRec.texUV);
			float refractiveAlbedo = hitRec.material->getRefractiveAlbedo();
			if(rrRandom < diffuseAlbedo)
			{
				ray.id = rayId++;
				ray.isShadowRay = false;
				ray.origin = hitRec.point;
				power %= hitRec.material->getTextureDiffuseBrdf(hitRec.texUV);
				power *= 1.0f / diffuseAlbedo;
				prob *= diffuseAlbedo;
				sampleShootingDiffuseDirection(depth, hitRec.normal, ray.dir);
			}
			else
			{
				rrRandom -= diffuseAlbedo;
				if(rrRandom < idealAlbedo)
				{
					ray.dir.setIdealReflectedDirection(ray.dir, hitRec.normal);
					ray.id = rayId++;
					ray.isShadowRay = false;
					ray.origin = hitRec.point;
					power %= hitRec.material->getIdealBrdf();
					power *= 1.0f / idealAlbedo;
					prob *= idealAlbedo;
				}
				else
					break;
			}
		}
	}
}

void PathMapEffect::sampleSurfaceRadion(Radion& starter)
{
	float randa = ((double)rand() / RAND_MAX) * entities.size();
//&	float randa = ((double)rand() / RAND_MAX) * sumSurfaceArea;
	float uptonowSurfaceArea = 0.0;
	Entity* e = NULL;
	std::vector<Entity*>::iterator entityIterator = entities.begin();
	while(entityIterator != entities.end())
	{
		uptonowSurfaceArea += 1.0f;
//&		uptonowSurfaceArea += (*entityIterator)->getSurfaceArea();
		if(uptonowSurfaceArea >= randa)
		{
			e = *entityIterator;
			break;
		}
		entityIterator++;
	}

	SubEntity* se = e->sampleSurface(starter);

	float surfa = starter.radiance.z;

	Vector rtexc = starter.radiance;
	starter.radiance = se->getRayTraceEntity()->getMaterial()->getTextureDiffuseBrdf(rtexc);
	starter.radiance *= (surfa / NRADIONS) * entities.size();
//&	starter.radiance *= sumSurfaceArea / NRADIONS;
	starter.probability = (float)NRADIONS / (entities.size() * surfa );
}

void PathMapEffect::sampleSurfaceRadionUniform(Radion& starter)
{
	float randa = ((double)rand() / RAND_MAX) * sumSurfaceArea;
	float uptonowSurfaceArea = 0.0;
	Entity* e = NULL;
	std::vector<Entity*>::iterator entityIterator = entities.begin();
	while(entityIterator != entities.end())
	{
		uptonowSurfaceArea += (*entityIterator)->getSurfaceArea();
		if(uptonowSurfaceArea >= randa)
		{
			e = *entityIterator;
			break;
		}
		entityIterator++;
	}

	SubEntity* se = e->sampleSurface(starter);

	float surfa = starter.radiance.z;

	Vector rtexc = starter.radiance;
	starter.radiance = se->getRayTraceEntity()->getMaterial()->getTextureDiffuseBrdf(rtexc);
	starter.radiance *= sumSurfaceArea / NRADIONS;
	starter.probability = (float)NRADIONS / (entities.size() * surfa );
}


/*
void PathMapEffect::showPRMTexture()
{
	device->SetRenderTarget(0, frameColorBuffer);
	device->SetDepthStencilSurface(frameDepthStencilBuffer);

	device->Clear( 0, NULL, D3DCLEAR_TARGET | D3DCLEAR_ZBUFFER,	D3DCOLOR_XRGB(0,0,0), 1.0f, 0 );

	if( SUCCEEDED( device->BeginScene() ) ){
		if( effect != NULL ){
			D3DXHANDLE hTechnique = effect->GetTechniqueByName((LPSTR)"ShowTex");
			if(hTechnique==NULL){
				return;
			}
			effect->SetTechnique( hTechnique );
			UINT nPasses = 0;
			effect->Begin( &nPasses, 0 );
			for(UINT j=0;j<nPasses;j++){
				effect->BeginPass(j);
		
				//loop through entities
				std::vector<PathMapEffect::Entity>::iterator entityIterator = entities.begin();
				//while(entityIterator != entities.end())
				{
					//set entity params
					effect->SetMatrix("modelToWorldMatrix", &entityIterator->modelWorldTransform);
					effect->SetMatrix("inverseTransposedModelToWorldMatrix", &entityIterator->inverseTransposedModelWorldTransform);
					D3DXMATRIX t = entityIterator->modelWorldTransform;
					if(parameters->Get(bLookFromLight))
						effect->SetMatrix("modelToProjMatrix", &(entityIterator->modelWorldTransform * *lightCamera->GetViewMatrix()  * *lightCamera->GetProjMatrix()  ));
					else
						effect->SetMatrix("modelToProjMatrix", &(entityIterator->modelWorldTransform * *camera->GetViewMatrix()  * *camera->GetProjMatrix()  ));

					effect->SetTexture("filteredAtlas", entityIterator->prmTexture);

					unsigned int nSubsets = entityIterator->renderMesh->nSubsets;
					for(int i = 0; i< nSubsets; i++)
					{
						//set subset material texture
						effect->SetTexture("texToShow", entityIterator->prmTexture);
						effect->CommitChanges();
						renderFullScreen();
//						effect->CommitChanges();
//						entityIterator->renderMesh->mesh->DrawSubset(i);
					}
					entityIterator++;
				}
				effect->EndPass();
			}
			effect->End();
		}
		device->EndScene();
	}

}
*/

void PathMapEffect::uploadRadions()
{
	int nRadions = bushStarters.size();
	struct TMR{
		float pos[4];
		float dir[4];
//		float pow[4];
	};
	TMR* tm = new TMR[nRadions];
	for(int i=0; i<nRadions; i++)
	{
//*
		tm[i].pos[0] = bushStarters[i].position[0];
		tm[i].pos[1] = bushStarters[i].position[1];
		tm[i].pos[2] = bushStarters[i].position[2];
		tm[i].pos[3] = 1.0;
		tm[i].dir[0] = bushStarters[i].normal[0];
		tm[i].dir[1] = bushStarters[i].normal[1];
		tm[i].dir[2] = bushStarters[i].normal[2];
		tm[i].dir[3] = 1.0;
//		tm[i].pow[0] = bushStarters[i].radiance[0];
//		tm[i].pow[1] = bushStarters[i].radiance[1];
//		tm[i].pow[2] = bushStarters[i].radiance[2];
//		tm[i].pow[3] = 1.0;
/*/
		tm[i].pos[0] = 0.9;
		tm[i].pos[1] = 0.2;
		tm[i].pos[2] = 0.2;
		tm[i].pos[3] = 1.0;
		tm[i].dir[0] = 0.2;
		tm[i].dir[1] = 0.9;
		tm[i].dir[2] = 0.2;
		tm[i].dir[3] = 1.0;
		tm[i].pow[0] = 0.2;
		tm[i].pow[1] = 0.2;
		tm[i].pow[2] = 0.9;	//blue
		tm[i].pow[3] = 0.99;
//*/
	}

	RECT imgSize;
	imgSize.top = imgSize.left = 0;
	imgSize.bottom =  nRadions;
	imgSize.right = 2 * nRadions / 4096;
	D3DXLoadSurfaceFromMemory(radionSurface, NULL, NULL, tm, D3DFMT_A32B32G32R32F, 
		imgSize.right * 4 * sizeof(float), NULL, &imgSize, D3DX_FILTER_NONE, 0);

	delete [] tm;
}

void PathMapEffect::fillRadionPosArray(void* pData)
{
	int nRadions = NRADIONS;
	struct TMR{
		float pos[3];
		float rad[3];
	};
	TMR* tm = (TMR*)pData;
	for(int i=0; i<nRadions; i++)
	{
		tm[i].pos[0] = bushStarters[i].position[0];
		tm[i].pos[1] = bushStarters[i].position[1];
		tm[i].pos[2] = bushStarters[i].position[2];
		tm[i].rad[0] = bushStarters[i].radiance[0];
		tm[i].rad[1] = bushStarters[i].radiance[1];
		tm[i].rad[2] = bushStarters[i].radiance[2];
	}
}

const wchar_t* PathMapEffect::getWeightsString()
{
	static wchar_t ws[512];
	ws[0] = 0;
	char wan[64];
	float sumw = 0.0f;
	for(int i=0; i<33; i++)
	{
//		StrCpy(wan, L"%f ");
		if(i == 32)
			sprintf(wan, "%.3f ", (double)sumw);
		else
		{
			sumw += weights[i];
			sprintf(wan, "%.3f ", (double)weights[i]);
		}
		wchar_t* wideValue = new wchar_t[MultiByteToWideChar(CP_ACP, 0, wan, -1, NULL, 0)];
		MultiByteToWideChar(CP_ACP, 0, wan, -1, wideValue, 511);
		StrCatW(ws, wideValue);
		delete wideValue;
	}
	return ws;
}


void PathMapEffect::savePathMaps()
{
	std::fstream entryPointFile("prm\\prmEntryPoints.dat", std::ios::out | std::ios::binary);

	for(unsigned int u=0; u < NRADIONS; u++)
	{
		entryPointFile << bushStarters.at(u);
	}
	
	for(unsigned int c=0; c < NCLUSTERS; c++)
	{
		entryPointFile.write((char*)&clusterLenghts[c], sizeof(unsigned int));
	}

	entryPointFile.flush();
	entryPointFile.close();

	unsigned int iEntity = 0;
	std::vector<Entity*>::iterator entityIterator = entities.begin();
	while(entityIterator != entities.end())
	{
		(*entityIterator)->savePRMs();

		entityIterator++;
		iEntity++;
	}

}

void PathMapEffect::loadPathMaps()
{
	std::fstream entryPointFile("prm\\prmEntryPoints.dat", std::ios::in | std::ios::binary);

	bushStarters.clear();

	for(unsigned int u=0; u < NRADIONS; u++)
	{
		Radion ri;
		entryPointFile >> ri;
		bushStarters.push_back(ri);
	}
	
	for(unsigned int c=0; c < NCLUSTERS; c++)
	{
		entryPointFile.read((char*)&clusterLenghts[c], sizeof(unsigned int));		
	}

	entryPointFile.close();

	unsigned int iEntity = 0;
	std::vector<Entity*>::iterator entityIterator = entities.begin();
	while(entityIterator != entities.end())
	{
		entityIterator->findNearClusters(bushStarters, NCLUSTERS);

		wchar_t prmFileName[256];
//		wsprintf(prmFileName, L"prm\\prm_%08d.hdr", iEntity);
		MultiByteToWideChar(CP_ACP, 0, entityIterator->prmfilename, -1, prmFileName, 255);
		D3DXLoadSurfaceFromFile(entityIterator->prmSurface, NULL, NULL, prmFileName, NULL, D3DX_DEFAULT, 0, NULL);
		entityIterator++;
		iEntity++;
	}
}

void PathMapEffect::exportEntityData()
{
	std::fstream entryPointFile("media\\entityPathMapData.txt", std::ios::out);

	unsigned int iEntity = 0;
	std::vector<PathMapEffect::Entity>::iterator entityIterator = entities.begin();
	while(entityIterator != entities.end())
	{
		entryPointFile << "entity " << entityIterator->name << '\n';
		entryPointFile << "{" << '\n';
		entryPointFile << " pathmapfile " << entityIterator->prmfilename << '\n';
		entryPointFile << " clusters ";
		for(int i=0; i<entityIterator->nNearClusters; i++)
			entryPointFile << entityIterator->nearClusterIndices[i] << " ";
		entryPointFile << '\n';
		entryPointFile << "}" << '\n';
		entryPointFile << '\n';

//		for(int i=0; i<16; i++)
//			entryPointFile << entityIterator->modelWorldTransform.m[i%4][i/4] << " ";
		entryPointFile << '\n';
		entityIterator++;
		iEntity++;
	}

	entryPointFile.flush();
	entryPointFile.close();

}

void PathMapEffect::loadScene(const char* sceneFileName)
{
	std::fstream sceneFile(sceneFileName, std::ios::in);

	char keyword[256];
	while(!sceneFile.eof())
	{
		sceneFile >> keyword;
		if(strcmp(keyword, "mesh") == 0)
		{
			int meshAtlasSize = 128;
			bool needsUV = true;
			bool needsTBN = false;
			int dividePcs = 1;
			double bumpScale = 1.0;
			char meshname[256];
			wchar_t* wide = NULL;
			wchar_t* wBump = NULL;
			Vector color = Vector::RGBWHITE;

			sceneFile >> meshname;
			if(strcmp(meshname, "{") == 0)
				strcpy(meshname, "mesh");
			while(strcmp(keyword, "}") != 0 && !sceneFile.eof())
			{
				sceneFile >> keyword;
				if(strcmp(keyword, "xfile") == 0)
				{
					sceneFile >> keyword;
					if(keyword)
					{
						wide = L::l+keyword;
					}

				}
				if(strcmp(keyword, "pathmapresolution") == 0)
				{
					sceneFile >> meshAtlasSize;
				}
				if(strcmp(keyword, "divide") == 0)
				{
					sceneFile >> dividePcs;
				}
			}
			if(wide)
			{
				loadMesh(wide, meshAtlasSize, meshname, dividePcs, needsUV, needsTBN);
				delete wide;
			}

		}

		if(strcmp(keyword, "entity") == 0)
		{
			Entity e;
			e.owner = this;

			char entityname[256];
			sceneFile >> entityname;
			if(strcmp(entityname, "{") == 0)
				strcpy(entityname, "noname");

			strcpy(e.name, entityname);

			while(strcmp(keyword, "}") != 0 && !sceneFile.eof())
			{
				sceneFile >> keyword;
				if(strcmp(keyword, "pathmapfile") == 0)
				{
					sceneFile >> keyword;
					strcpy(e.prmfilename, keyword);
				}
				if(strcmp(keyword, "mesh") == 0)
				{
					sceneFile >> keyword;

					std::vector<PathMapEffect::RenderMesh*>::iterator i = renderMeshes.begin();
					while(i != renderMeshes.end())
					{
						if(strcmp((*i)->name, keyword) == 0)
						{
							e.renderMesh = *i;
							break;
						}
						i++;
					}
				}
				if(strcmp(keyword, "transformation") == 0)
				{
					for(int i=0; i<16; i++)
						sceneFile >> e.modelWorldTransform.m[i%4][i/4];
					D3DXMatrixInverse(&e.inverseTransposedModelWorldTransform, NULL, &e.modelWorldTransform);
				}
				if(strcmp(keyword, "pathmapclusters") == 0)
				{
					sceneFile >> e.nNearClusters;
				}
			}
			std::vector<PathMapEffect::RenderMesh*>::iterator i = renderMeshes.begin();
			while(i != renderMeshes.end())
			{
				if(strcmp((*i)->name, e.renderMesh->name) == 0)
				{
					Entity eslab;
					eslab.renderMesh = *i;
					sprintf(eslab.prmfilename, "%s_s%d.hdr", e.prmfilename, eslab.renderMesh->slabIndex);
					eslab.modelWorldTransform = e.modelWorldTransform;
					eslab.inverseTransposedModelWorldTransform = e.inverseTransposedModelWorldTransform;
					eslab.owner = this;
					eslab.nNearClusters = e.nNearClusters;

					eslab.createRayTraceEntity();
					entities.push_back(eslab);
				}
				i++;
			}
		}
	}
	sceneFile.close();
}


LPDIRECT3DSURFACE9 renderScene(const RenderStrategy& renderStrategy)
{
	renderStrategy.applyTargets(this);

	renderStrategy.applyRenderState();

	if( SUCCEEDED( device->BeginScene() ) )
	{
		renderStrategy.applyTechnique();
		UINT nPasses;
		effect->Begin( &nPasses, 0 );
		for(UINT j=0;j<nPasses;j++)
		{
			effect->BeginPass(j);

			//loop through all entities
			std::vector<Entity>::iterator entityIterator = pathMapEffect->entities.begin();
			while(entityIterator != pathMapEffect->entities.end())
			{

				(*entityIterator)->drawAllSubEntities(renderStrategy);
				entityIterator++;
			}

			effect->EndPass();
		}
		effect->End();
		device->EndScene();
	}

	renderStrategy.resetRenderState();

}