#include "dxstdafx.h"
#include ".\voronoigenerator.h"
#include <map>
//#include <gl/gl.h>
//#include <gl/glut.h>


VoronoiGenerator::VoronoiGenerator(void)
{
}

VoronoiGenerator::~VoronoiGenerator(void)
{
}

void VoronoiGenerator::addDir(const Vector& d)
{
	if(dirs.size()<3)
	{
		dirs.push_back(d);
		return;
	}
	if(dirs.size() == 3)
	{
		dirs.push_back(d);
		if(
			((dirs[0] - dirs[1]) && 
			(dirs[0] - dirs[2]))
			*
			dirs[3]
			>  0.0
			)
		{
			tris.push_back(Tri(this, 0, 1, 2));
			tris.push_back(Tri(this, 0, 3, 1));
			tris.push_back(Tri(this, 2, 1, 3));
			tris.push_back(Tri(this, 0, 2, 3));
		}
		else
		{
			tris.push_back(Tri(this, 0, 2, 1));
			tris.push_back(Tri(this, 0, 1, 3));
			tris.push_back(Tri(this, 0, 3, 2));
			tris.push_back(Tri(this, 1, 2, 3));
		}
		return;
	}
	dirs.push_back(d);
	std::multimap<int, int> edges;
	int stest;

	std::vector<Tri>::iterator a = tris.begin();
	std::vector<Tri>::iterator end = tris.end();
	while(a != end)
	{
		if(a->violates(d))
		{
			bool needsab = true, needsbc = true, needsca = true;
			std::multimap<int, int>::iterator fnd = edges.find(a->bi);
			while(fnd != edges.end() && fnd->first == a->bi)
			{
				if(fnd->second == a->ai)
				{
					edges.erase(fnd);
					needsab = false;
					break;
				}
				fnd++;
			}
			fnd = edges.find(a->ci);
			while(fnd != edges.end() && fnd->first == a->ci)
			{
				if(fnd->second == a->bi)
				{
					edges.erase(fnd);
					needsbc = false;
					break;
				}
				fnd++;
			}
			fnd = edges.find(a->ai);
			while(fnd != edges.end() && fnd->first == a->ai)
			{
				if(fnd->second == a->ci)
				{
					edges.erase(fnd);
					needsca = false;
					break;
				}
				fnd++;
			}

			if(needsab)
				edges.insert(std::pair<int, int>(a->ai, a->bi));
			if(needsbc)
				edges.insert(std::pair<int, int>(a->bi, a->ci));
			if(needsca)
				edges.insert(std::pair<int, int>(a->ci, a->ai));
			a = tris.erase(a);
			end = tris.end();
		}
		else
			a++;
	}
	std::multimap<int, int>::iterator l = edges.begin();
	std::multimap<int, int>::iterator lend = edges.end();
	int lastindex = dirs.size() - 1;
	stest = edges.size();
	while(l != lend)
	{
		tris.push_back(Tri(this, lastindex, l->first, l->second));
		l++;
	}
}

VoronoiGenerator::Tri::Tri(VoronoiGenerator* omesh, int ai, int bi, int ci)
{
	mesh = omesh;
	this->ai = ai;
	this->bi = bi;
	this->ci = ci;
	n = (mesh->dirs[ai] - mesh->dirs[bi]) &&
		(mesh->dirs[ai] - mesh->dirs[ci]);
	n.normalize();
	r = n * mesh->dirs[ai];
}

void VoronoiGenerator::Tri::refresh()
{
	n = (mesh->dirs[ai] - mesh->dirs[bi]) &&
		(mesh->dirs[ai] - mesh->dirs[ci]);
	n.normalize();
	r = n * mesh->dirs[ai];
}

bool VoronoiGenerator::Tri::violates(const Vector& p)
{
	return (p * n) > r;
}

bool VoronoiGenerator::Tri::contains(const Vector& p)
{
	if((p * n) < r)
		return false;
	Vector da = mesh->dirs[ai];
	Vector db = mesh->dirs[bi];
	Vector dc = mesh->dirs[ci];
	Vector cross = da && db;
	if(p * cross < 0.0)
		return false;
	cross = db && dc;
	if(p * cross < 0.0)
		return false;
	cross = dc && da;
	if(p * cross < 0.0)
		return false;
	return true;
}


void VoronoiGenerator::glDrawDelaunay(std::vector<Vector>& powers)
{
	/*
	glBegin(GL_TRIANGLES);
		std::vector<Tri>::iterator a = tris.begin();
		std::vector<Tri>::iterator end = tris.end();
		while(a != end)
		{
			glColor3d(powers[a->ai].r / 1000.0, powers[a->ai].g / 1000.0, powers[a->ai].b / 1000.0);
			glVertex3d(dirs[a->ai].x, dirs[a->ai].y, dirs[a->ai].z);
			glColor3d(powers[a->bi].r / 1000.0, powers[a->bi].g / 1000.0, powers[a->bi].b / 1000.0);
			glVertex3d(dirs[a->bi].x, dirs[a->bi].y, dirs[a->bi].z);
			glColor3d(powers[a->ci].r / 1000.0, powers[a->ci].g / 1000.0, powers[a->ci].b / 1000.0);
			glVertex3d(dirs[a->ci].x, dirs[a->ci].y, dirs[a->ci].z);
			a++;
		}
	glEnd();
	*/
}

struct D3DVERTEX{
	D3DXVECTOR3 pos;
	D3DXVECTOR3 normal;
	D3DXVECTOR2 tex0;
	D3DXVECTOR2 tex1;
	D3DXVECTOR3 tex2;
};

void VoronoiGenerator::d3dDrawDelaunay(LPDIRECT3DDEVICE9 device)
{
	std::vector<Tri>::iterator a = tris.begin();
	std::vector<Tri>::iterator end = tris.end();
	while(a != end)
	{
		D3DVERTEX tr[3];
	    tr[0].pos=D3DXVECTOR3(dirs[a->ai].x, dirs[a->ai].y, dirs[a->ai].z);
		tr[1].pos=D3DXVECTOR3(dirs[a->bi].x, dirs[a->bi].y, dirs[a->bi].z);
		tr[2].pos=D3DXVECTOR3(dirs[a->ci].x, dirs[a->ci].y, dirs[a->ci].z);

		device->DrawPrimitiveUP(D3DPT_TRIANGLELIST, 1, tr, sizeof(D3DVERTEX));
		a++;
	}


}

void VoronoiGenerator::relaxLloyd()
{
	double* voroAreas = new double[dirs.size()];
	std::vector<Vector> relaxedDirs;
	relaxedDirs.insert(relaxedDirs.begin(), dirs.size(), Vector::RGBBLACK);
/*	for(int r=0; r<dirs.size(); r++)
	{
		voroAreas[r] = 0.0;
	}*/

	std::vector<Tri>::iterator a = tris.begin();
	std::vector<Tri>::iterator end = tris.end();
	while(a != end)
	{
		Vector la = (dirs[a->bi] - dirs[a->ai]);
		Vector lb = (dirs[a->ci] - dirs[a->ai]);
		double lcos = la * lb;
		if(lcos >= 1.0)
			lcos = 1.0;
		double triArea = 
			sqrt(la.norm2() * la.norm2() * (1.0 - lcos * lcos)) / 4.0;
//		double lsin = sqrt(1.0 - lcos * lcos);
//		relaxedDirs[a->ai] += a->n * lsin;
//		relaxedDirs[a->bi] += a->n * lsin;
//		relaxedDirs[a->ci] += a->n * lsin;
		relaxedDirs[a->ai] += (dirs[a->ai] * 4.0 + dirs[a->bi] + dirs[a->ci]) * 0.166666666666 * triArea;
		relaxedDirs[a->bi] += (dirs[a->ai] + dirs[a->bi] * 4.0 + dirs[a->ci]) * 0.166666666666 * triArea;
		relaxedDirs[a->ci] += (dirs[a->ai] + dirs[a->bi] + dirs[a->ci] * 4.0) * 0.166666666666 * triArea;
//		voroAreas[a->ai] += triArea;
//		voroAreas[a->bi] += triArea;
//		voroAreas[a->ci] += triArea;
		a++;
	}
	std::vector<Vector>::iterator d = relaxedDirs.begin();
	std::vector<Vector>::iterator dend = relaxedDirs.end();
	int idx = 0;
	while(d != dend)
	{
/*		if(voroAreas[idx] == 0.0)
		{
			char mess[200];
			sprintf(mess, "HEY: %d", idx);
			AfxMessageBox(mess);
			voroAreas[idx] = 1.0;
		}
		(*d) *= 1.0 / voroAreas[idx];*/
		d->normalize();
		d++;
		idx++;
	}
	dirs = relaxedDirs;
	delete voroAreas;
	std::vector<Tri>::iterator rfa = tris.begin();
	std::vector<Tri>::iterator rfend = tris.end();
	while(rfa != rfend)
	{
		rfa->refresh();
		rfa++;
	}
}

int VoronoiGenerator::lastNearestTriIndex = 0;

int VoronoiGenerator::getNearestDirIndex(const Vector& pd)
{
	std::vector<Tri>::iterator a = tris.begin() + lastNearestTriIndex;
	std::vector<Tri>::iterator end = tris.end();
	std::vector<Tri>::iterator finitor = end;
	if(lastNearestTriIndex)
		finitor = tris.begin() + (lastNearestTriIndex - 1);
	while(a != finitor)
	{
		if(a == end)
		{
			a = tris.begin();
			if(a == finitor)
				break;
		}
		if(a->contains(pd))
		{
			lastNearestTriIndex = a - tris.begin();
			double adist = dirs[a->ai] * pd;
			double bdist = dirs[a->bi] * pd;
			double cdist = dirs[a->ci] * pd;
			if(adist > bdist && adist > cdist)
				return a->ai;
			if(bdist > adist && bdist > cdist)
				return a->bi;
			if(cdist > adist && cdist > bdist)
				return a->ci;
		}
		a++;
	}
	return 0;
}