#include "terrain.h"
#include "vector.h"

#include "gl.h"

#include <cmath>
#include <queue>
#include <set>

using std::min;
using std::max;

Terrain::Node::Node(Chunk *chunk, float x, float y) {
	this->chunk = chunk;
	this->x = x;
	this->y = y;

	fill();
}

Terrain::Node::~Node() {
}

float Terrain::Node::distance(float px, float pz) {
	bool in_width = px > x && px < x+1;
	bool in_height = pz > y && pz < y+1;

	if(in_width && in_height)
		return 0;

	Vector2 p(px, pz);

	float a = (p - Vector2(x, y)).length();
	float b = (p - Vector2(x+1, y)).length();
	float c = (p - Vector2(x, y+1)).length();
	float d = (p - Vector2(x+1, y+1)).length();

	float dist = min(min(min(a, b), c), d);

	if(in_width)
		dist = min(dist, (float)min(abs(y - pz), abs(y+1 - pz)));
	if(in_height)
		dist = min(dist, (float)min(abs(x - px), abs(x+1 - px)));

	return dist;
}

void Terrain::Node::fill() {
	vertex_array[0] = x;
	vertex_array[1] = chunk->heights[(int)floorf((x + 1)*(chunk->h_height) + (y + 1))];
	vertex_array[2] = y;

	vertex_array[3] = x;
	vertex_array[4] = chunk->heights[(int)floorf((x + 1)*(chunk->h_height) + (y + 2))];
	vertex_array[5] = y + 1;

	vertex_array[6] = x + 1;
	vertex_array[7] = chunk->heights[(int)floorf((x + 2)*(chunk->h_height) + (y + 2))];
	vertex_array[8] = y + 1;

	vertex_array[9] = x + 1;
	vertex_array[10] = chunk->heights[(int)floorf((x + 2)*(chunk->h_height) + (y + 1))];
	vertex_array[11] = y;
}

void Terrain::Node::draw() {
	glBegin(GL_TRIANGLES);
	for(int i = 0; i < 2; i++) {
		glTexCoord2f(0, 0);
		glVertex3f(vertex_array[0], vertex_array[1], vertex_array[2]);
		glTexCoord2f(i, 1);
		glVertex3f(vertex_array[i*3+3], vertex_array[i*3+4], vertex_array[i*3+5]);
		glTexCoord2f(1, 1-i);
		glVertex3f(vertex_array[i*3+6], vertex_array[i*3+7], vertex_array[i*3+8]);
	}
	glEnd();
}

void Terrain::Node::draw_grid() {
	glNormal3f(0, 1, 0);
	glBegin(GL_LINE_LOOP);
		glVertex3f(chunk->x + vertex_array[0], vertex_array[1], chunk->y + vertex_array[2]);
		glVertex3f(chunk->x + vertex_array[3], vertex_array[4], chunk->y + vertex_array[5]);
		glVertex3f(chunk->x + vertex_array[6], vertex_array[7], chunk->y + vertex_array[8]);
		glVertex3f(chunk->x + vertex_array[9], vertex_array[10], chunk->y + vertex_array[11]);

		glVertex3f(chunk->x + vertex_array[0], vertex_array[1], chunk->y + vertex_array[2]);
		glVertex3f(chunk->x + vertex_array[6], vertex_array[7], chunk->y + vertex_array[8]);
	glEnd();
}

void Terrain::Node::draw_normal() {
	glNormal3f(0, 1, 0);
	glColor3f(1, 0, 0);
	int i = (int)(x*(chunk->n_height) + y);
	int i2 = (int)((x + 1) * (chunk->h_height) + (y + 1));
	glBegin(GL_LINES);
		Vector3 N = chunk->normals[i];
		glVertex3f(chunk->x + x, chunk->heights[i2], chunk->y + y);
		glVertex3f(chunk->x + x + N.x, chunk->heights[i2] + N.y, chunk->y + y + N.z);
	glEnd();
}

float Terrain::Node::get_height(float px, float py) {
	px -= chunk->x;
	py -= chunk->y;
	bool left;
	left = px - x >= py - y;
	int ci = left ? 9 : 3;
	Vector3 a(vertex_array[0], vertex_array[1], vertex_array[2]);
	Vector3 b = Vector3(vertex_array[6], vertex_array[7], vertex_array[8]);
	Vector3 c = Vector3(vertex_array[ci], vertex_array[ci+1], vertex_array[ci+2]);
	float det1 = (b.z - c.z) * (a.x - c.x) + (c.x - b.x) * (a.z - c.z);
	float det2 = (c.z - a.z) * (b.x - c.x) + (a.x - c.x) * (b.z - c.z);
	float l1 = ((b.z - c.z) * (px - c.x) + (c.x - b.x) * (py - c.z)) / det1;
	float l2 = ((c.z - a.z) * (px - c.x) + (a.x - c.x) * (py - c.z)) / det2;
	float l3 = 1 - l1 - l2;
	return l1 * a.y + l2 * b.y + l3 * c.y;
}

/* Chunk */

Terrain::Chunk::Chunk(Terrain *terrain, float x, float y) : cache_obj(terrain->tc->get_chunk(x, y, Terrain::chunk_size_total, Terrain::chunk_size_total)) {
	this->terrain = terrain;
	this->x = x;
	this->y = y;
	this->width = Terrain::chunk_size;
	this->height = Terrain::chunk_size;
	this->h_width = Terrain::chunk_size_total;
	this->h_height = Terrain::chunk_size_total;
	this->n_width = width+1;
	this->n_height = height+1;
	this->vbo_object = this->node_count = this->vertices = 0;
	this->nodes = NULL;
	heights = cache_obj->heights;

	for(std::list<Vector3>::iterator it = cache_obj->objects.begin(); it != cache_obj->objects.end(); it++) {
		models::Model::p tree = models::ModelManager::get_instance().get_model("tree");
		objects.push_back(ObjectPair(tree, *it));
	}

	normals = new Vector3[(int)((n_width)*(n_height))];

	calc_normals();

	node_count = width*height;
	nodes = new Node*[node_count];
	for(int i = 0; i < height; i++) {
		for(int j = 0; j < width; j++) {
			nodes[j*(int)height + i] = new Node(this, j, i);
		}
	}

	make_vbo();
}

Terrain::Chunk::~Chunk() {
	for(unsigned int i = 0; i < node_count; i++)
		delete nodes[i];
	delete[] nodes;
	delete[] normals;
}

float Terrain::Chunk::distance(float px, float pz) {
	bool in_width = px > x && px < x+width;
	bool in_height = pz > y && pz < y+height;

	if(in_width && in_height)
		return 0;

	Vector2 p(px, pz);

	float a = (p - Vector2(x, y)).length();
	float b = (p - Vector2(x+width, y)).length();
	float c = (p - Vector2(x, y+height)).length();
	float d = (p - Vector2(x+width, y+height)).length();

	float dist = min(min(min(a, b), c), d);

	if(in_width)
		dist = min(dist, (float)min(abs(y - pz), abs(y+height - pz)));
	if(in_height)
		dist = min(dist, (float)min(abs(x - px), abs(x+width - px)));

	return dist;
}

void Terrain::Chunk::make_vbo() {
	node_count = width*height;
	vertices = node_count*6;
	if(vbo_object)
		glDeleteBuffers(1, &vbo_object);
	glGenBuffers(1, &vbo_object);
	glBindBuffer(GL_ARRAY_BUFFER, vbo_object);

	const size_t vertex_chunk_size = /*sizeof(float)*/3*6;
	const size_t vertices_size = vertex_chunk_size*node_count;
	const size_t normal_chunk_size = vertex_chunk_size;
	const size_t normals_size = normal_chunk_size*node_count;
	const size_t tex_coord_chunk_size = /*sizeof(float)*/2*6;
	const size_t tex_coords_size = tex_coord_chunk_size*node_count;

	buf_size = sizeof(float)*(vertices_size + normals_size + tex_coords_size);

	glBufferData(GL_ARRAY_BUFFER, buf_size, NULL, GL_STATIC_DRAW);

	float *buffer = (float*)glMapBuffer(GL_ARRAY_BUFFER, GL_WRITE_ONLY);

	for(unsigned int index = 0; index < node_count; index++) {
		Terrain::Node *node = nodes[index];
		// quad-node, triangle, vertex, texcoord
		float tex_coords[4][2][3][2] = {
			{{{0, 0}, {0, .5}, {.5, .5}},
			{{0, 0}, {.5, .5}, {.5, 0}}},

			{{{.5, 0}, {.5, .5}, {1, .5}},
			{{.5, 0}, {1, .5}, {1, 0}}},

			{{{0, .5}, {0, 1}, {.5, 1}},
			{{0, .5}, {.5, 1}, {.5, .5}}},

			{{{.5, .5}, {.5, 1}, {1, 1}},
			{{.5, .5}, {1, 1}, {1, .5}}}
		};
		for(int i = 0; i < 2; i++) {
			float *v = buffer + vertex_chunk_size*index + 3*3*i;
			for(int j = 0; j < 3; j++) {
				float *tc = buffer + vertices_size + normals_size + tex_coord_chunk_size*index + 6*i + 2*j;
				int k = (fmodf(node->x, 2) == 0 ? 0 : 1) + (fmodf(node->y, 2) == 0 ? 0 : 2);
				tc[0] = tex_coords[k][i][j][0];
				tc[1] = tex_coords[k][i][j][1];
			}

			v[0] = node->vertex_array[0];
			v[1] = node->vertex_array[1];
			v[2] = node->vertex_array[2];

			v[3] = node->vertex_array[i*3+3];
			v[4] = node->vertex_array[i*3+4];
			v[5] = node->vertex_array[i*3+5];

			v[6] = node->vertex_array[i*3+6];
			v[7] = node->vertex_array[i*3+7];
			v[8] = node->vertex_array[i*3+8];
		}

		float *n = buffer + vertices_size + normal_chunk_size*index;

		Vector3 bl = normals[(int)((node->x+1)*(n_height) + node->y)];
		Vector3 br = normals[(int)((node->x)*(n_height) + node->y)];
		Vector3 tr = normals[(int)((node->x)*(n_height) + node->y+1)];
		Vector3 tl = normals[(int)((node->x+1)*(n_height) + node->y+1)];

		n[0] = n[9] = br.x;
		n[1] = n[10] = br.y;
		n[2] = n[11] = br.z;

		n[3] = tr.x;
		n[4] = tr.y;
		n[5] = tr.z;

		n[6] = n[12] = tl.x;
		n[7] = n[13] = tl.y;
		n[8] = n[14] = tl.z;

		n[15] = bl.x;
		n[16] = bl.y;
		n[17] = bl.z;
	}

	glUnmapBuffer(GL_ARRAY_BUFFER);
}

Terrain::Node* Terrain::Chunk::find(float x, float y) {
	if(!(x >= this->x && x < this->x+width && y >= this->y && y < this->y+height)) {
		return NULL;
	}
	return nodes[(int)(x-this->x)*(int)height + (int)(y - this->y)];
}

void Terrain::Chunk::calc_normals() {
	for(int x = 1; x < h_width-1; x++) {
		for(int y = 1; y < h_height-1; y++) {
			Vector3 p(x, heights[x*h_height + y], y);
			Vector3 N, U, V;
			float h;

			// right
			h = heights[(x-1)*h_height + y];
			U = Vector3(x-1, h, y) - p;

			// down
			h = heights[x*h_height + y - 1];
			V = Vector3(x, h, y-1) - p;
			N += V.cross(U);

			// up
			h = heights[x*h_height + y + 1];
			V = Vector3(x, h, y+1) - p;
			N += U.cross(V);

			// left
			h = heights[(x+1)*h_height + y];
			U = Vector3(x+1, h, y) - p;

			//down
			h = heights[x*h_height + y - 1];
			V = Vector3(x, h, y-1) - p;
			N += U.cross(V);

			// up
			h = heights[x*h_height + y + 1];
			V = Vector3(x, h, y+1) - p;
			N += V.cross(U);

			N /= N.length();
			normals[(x-1)*n_height + y - 1] = N;
		}
	}
}

Terrain::Terrain() {
	tc = new TerrainCache("map", 120);
}

Terrain::~Terrain() {
	for(std::list<Chunk*>::iterator it = chunks.begin(); it != chunks.end(); it++) {
		delete *it;
	}
	delete tc;
}

void Terrain::raise(float x, float z, float radius, float focus, float strength, bool up) {
	// TODO: fix
	// TODO: fix setting heights on unloaded chunks

	std::set<Chunk*> changed_chunks;

	/* adjust heights */
	for(int i = x-radius; i < x+radius; i++) {
		for(int j = z-radius; j < z+radius; j++) {
			float v = powf((radius - min((Vector2(x, z) - Vector2(i, j)).length(), radius)) * strength, 1+focus);

			if(focus > 0)
				/* Scale v with radius based on focus.
				 * Not 100% accurate, but close enough.
				 */
				v /= radius * (focus/2);

			Chunk *chunk = find_chunk(i, j);
			changed_chunks.insert(chunk);
			int index = (i-chunk->x)*(chunk->h_height) + j-chunk->y;
			if(up)
				chunk->heights[index] += v;
			else
				chunk->heights[index] -= v;

			/* fill the "outer border" */
			if(i % chunk_size == 0) {
				Chunk *chunk = find_chunk(i-chunk_size, j);
				if(chunk) {
					changed_chunks.insert(chunk);
					index = (chunk_size)*(chunk->h_height) + j-chunk->y;
					if(up)
						chunk->heights[index] += v;
					else
						chunk->heights[index] -= v;
				}
			}
			if(j % chunk_size == 0) {
				Chunk *chunk = find_chunk(i, j-chunk_size);
				if(chunk) {
					changed_chunks.insert(chunk);
					index = (i-chunk->x)*(chunk->h_height) + chunk_size;
					if(up)
						chunk->heights[index] += v;
					else
						chunk->heights[index] -= v;
				}
			}
			if(i % chunk_size == 0 && j % chunk_size == 0) {
				Chunk *chunk = find_chunk(i-chunk_size, j-chunk_size);
				if(chunk) {
					changed_chunks.insert(chunk);
					index = (chunk_size)*(chunk->h_height) + chunk_size;
					if(up)
						chunk->heights[index] += v;
					else
						chunk->heights[index] -= v;
				}
			}
		}
	}

	/* recalculate normals */
	for(std::set<Chunk*>::iterator it = changed_chunks.begin(); it != changed_chunks.end(); it++) {
		(*it)->calc_normals();
	}

	/* refill nodes and remake VBOs */
	for(std::set<Chunk*>::iterator it = changed_chunks.begin(); it != changed_chunks.end(); it++) {
		Chunk *chunk = *it;
		for(unsigned int i = 0; i < chunk->node_count; i++) {
			chunk->nodes[i]->fill();
		}
		chunk->make_vbo();
	}
}

void Terrain::update(float x, float z) {
	const int chunk_dist_threshold = chunk_size*4;
	std::set<std::pair<int, int> > chunk_indices;
	int i = x - chunk_dist_threshold;
	i -= i % chunk_size;
	for(; i < x + chunk_dist_threshold; i += chunk_size) {
		int j = z - chunk_dist_threshold;
		j -= j % chunk_size;
		for(; j < z + chunk_dist_threshold; j += chunk_size) {
			float a = i - x + chunk_size/2;
			float b = j - z + chunk_size/2;
			if(sqrtf(a*a + b*b) < chunk_dist_threshold)
				chunk_indices.insert(std::pair<int, int>(i, j));
		}
	}

	for(std::list<Chunk*>::iterator it = chunks.begin(); it != chunks.end(); it++) {
		Chunk *chunk = *it;
		std::set<std::pair<int, int> >::iterator ind_it = chunk_indices.find(std::pair<int, int>(chunk->x, chunk->y));
		if(ind_it != chunk_indices.end()) {
			chunk_indices.erase(ind_it);
		}
		if(chunk->distance(x, z) > chunk_dist_threshold) {
			delete *it;
			it = chunks.erase(it);
		}
	}

	for(std::set<std::pair<int, int> >::iterator it = chunk_indices.begin(); it != chunk_indices.end(); it++) {
		if(tc->tl->has_chunk(it->first, it->second)) {
			Chunk *chunk = NULL;
			try {
				chunk = new Chunk(this, it->first, it->second);
			} catch(...) {
			}
			if(chunk)
				chunks.push_back(chunk);
		}
	}
}

Terrain::Chunk *Terrain::find_chunk(float x, float y) {
	Node *node = find(x, y);
	return node ? node->chunk : NULL;
}

Terrain::Node *Terrain::find(float x, float y) {
	for(std::list<Chunk*>::iterator it = chunks.begin(); it != chunks.end(); it++) {
		Node *node = (*it)->find(x, y);
		if(node)
			return node;
	}
	return NULL;
}