Merged Quadtree and friends into Terrain.

8 files changed, 609 insertions, 654 deletions

diff --git a/quadtree.cpp b/quadtree.cpp
deleted file mode 100644
index 2112016..0000000
--- a/quadtree.cpp
+++ /dev/null
@@ -1,557 +0,0 @@
-#include "quadtree.h"
-#include "vector.h"
-
-#include "gl.h"
-
-#include <cmath>
-#include <queue>
-#include <set>
-
-using std::min;
-using std::max;
-
-Quadtree::QuadNode::QuadNode(QuadChunk *chunk, float x, float y, float width, float height) {
-	this->chunk = chunk;
-	this->x = x;
-	this->y = y;
-	this->width = width;
-	this->height = height;
-
-	fill();
-}
-
-Quadtree::QuadNode::~QuadNode() {
-}
-
-float Quadtree::QuadNode::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 Quadtree::QuadNode::fill() {
-	vertex_array[0] = x + width / 2;
-	vertex_array[1] = chunk->heights[(int)floorf((int)(x + width/2)*(chunk->height+1) + (int)(y + height/2))];
-	vertex_array[2] = y + height / 2;
-
-	vertex_array[3] = x;
-	vertex_array[4] = chunk->heights[(int)floorf((x)*(chunk->height+1)+y)];
-	vertex_array[5] = y;
-
-	vertex_array[6] = x;
-	vertex_array[7] = chunk->heights[(int)floorf((x)*(chunk->height+1) + (y + height))];
-	vertex_array[8] = y + height;
-
-	vertex_array[9] = x + width;
-	vertex_array[10] = chunk->heights[(int)floorf((x + width)*(chunk->height+1) + (y + height))];
-	vertex_array[11] = y + height;
-
-	vertex_array[12] = x + width;
-	vertex_array[13] = chunk->heights[(int)floorf((x + width)*(chunk->height+1) + y)];
-	vertex_array[14] = y;
-
-	/* midpoint is average of corner heights when width == 1 */
-	if(width == 1) {
-		vertex_array[1] = (vertex_array[4] + vertex_array[7] + vertex_array[10] + vertex_array[13])/4;
-	}
-}
-
-void Quadtree::QuadNode::draw() {
-	float tex_coords[4][3][2] = {
-		{{.5, .5}, {0, 0}, {0, 1}},
-		{{.5, .5}, {0, 1}, {1, 1}},
-		{{.5, .5}, {1, 1}, {1, 0}},
-		{{.5, .5}, {1, 0}, {0, 0}}
-	};
-
-	glBegin(GL_TRIANGLES);
-	for(int i = 0; i < 4; i++) {
-		Vector3 a(vertex_array[0], vertex_array[1], vertex_array[2]);
-		Vector3 b(vertex_array[i*3+3], vertex_array[i*3+4], vertex_array[i*3+5]);
-		Vector3 c(vertex_array[i == 3 ? 3 : (i*3+6)], vertex_array[i == 3 ? 4 : (i*3+7)], vertex_array[i == 3 ? 5 : (i*3+8)]);
-
-		Vector3 U(c.x-a.x, c.y-a.y, c.z-a.z);
-		Vector3 V(b.x-a.x, b.y-a.y, b.z-a.z);
-		Vector3 N(V.cross(U));
-		glNormal3f(N.x, N.y, N.z);
-
-		glTexCoord2f(tex_coords[i][0][0], tex_coords[i][0][1]);
-		glVertex3f(a.x, a.y, a.z);
-
-		glTexCoord2f(tex_coords[i][1][0], tex_coords[i][1][1]);
-		glVertex3f(b.x, b.y, b.z);
-
-		glTexCoord2f(tex_coords[i][2][0], tex_coords[i][2][1]);
-		glVertex3f(c.x, c.y, c.z);
-	}
-	glEnd();
-}
-
-void Quadtree::QuadNode::draw_grid() {
-	glNormal3f(0, 1, 0);
-	glBegin(GL_LINES);
-	for(int i = 0; i < 4; i++) {
-		Vector3 a(vertex_array[0], vertex_array[1], vertex_array[2]);
-		Vector3 b(vertex_array[i*3+3], vertex_array[i*3+4], vertex_array[i*3+5]);
-
-		glVertex3f(chunk->x + a.x, a.y, chunk->y + a.z);
-		glVertex3f(chunk->x + b.x, b.y, chunk->y + b.z);
-	}
-	glEnd();
-	glBegin(GL_LINE_LOOP);
-		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[12], vertex_array[13], chunk->y + vertex_array[14]);
-	glEnd();
-}
-
-void Quadtree::QuadNode::draw_normal() {
-	glNormal3f(0, 1, 0);
-	glColor3f(1, 0, 0);
-	int i = (int)(x*(chunk->height+1) + y);
-	glBegin(GL_LINES);
-		Vector3 N = chunk->normals[i];
-		glVertex3f(chunk->x + x, chunk->heights[i], chunk->y + y);
-		glVertex3f(chunk->x + x + N.x, chunk->heights[i] + N.y, chunk->y + y + N.z);
-	glEnd();
-}
-
-float Quadtree::QuadNode::get_height(float px, float py) {
-	px -= chunk->x;
-	py -= chunk->y;
-	bool left;
-	bool top;
-	top = px - x >= height - (py - y);
-	left = px - x >= py - y;
-	Vector3 a(vertex_array[0], vertex_array[1], vertex_array[2]);
-	Vector3 b, c;
-	int bi, ci;
-	if(left) {
-		if(top) {
-			bi = 3*3;
-			ci = 4*3;
-		} else {
-			bi = 4*3;
-			ci = 1*3;
-		}
-	} else {
-		if(top) {
-			bi = 2*3;
-			ci = 3*3;
-		} else {
-			bi = 1*3;
-			ci = 2*3;
-		}
-	}
-	b = Vector3(vertex_array[bi], vertex_array[bi+1], vertex_array[bi+2]);
-	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;
-}
-
-/* QuadChunk */
-
-Quadtree::QuadChunk::QuadChunk(Quadtree *tree, float x, float y, float width, float height) {
-	this->tree = tree;
-	this->x = x;
-	this->y = y;
-	this->width = width;
-	this->height = height;
-	this->vbo_object = this->node_count = this->vertices = 0;
-	this->nodes = NULL;
-	heights = tree->terrain->generate_heights(x, y, width+1, height+1);
-	normals = new Vector3[(int)((width+1)*(height+1))];
-
-	calc_normals();
-
-	node_count = width*height;
-	nodes = new QuadNode*[node_count];
-	for(int i = 0; i < height; i++) {
-		for(int j = 0; j < width; j++) {
-			nodes[j*(int)height + i] = new QuadNode(this, j, i, 1, 1);
-		}
-	}
-	make_vbo();
-}
-
-Quadtree::QuadChunk::~QuadChunk() {
-	for(unsigned int i = 0; i < node_count; i++)
-		delete nodes[i];
-	delete[] nodes;
-	delete[] heights;
-	delete[] normals;
-}
-
-float Quadtree::QuadChunk::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 Quadtree::QuadChunk::make_vbo() {
-	node_count = width*height;
-	vertices = node_count*12;
-	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*12;
-	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*12;
-	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++) {
-		Quadtree::QuadNode *node = nodes[index];
-		float tex_coords[4][4][3][2] = {
-			{{{.25, .25}, {0, 0}, {0, .5}},
-			{{.25, .25}, {0, .5}, {.5, .5}},
-			{{.25, .25}, {.5, .5}, {.5, 0}},
-			{{.25, .25}, {.5, 0}, {0, 0}}},
-
-			{{{.75, .25}, {.5, 0}, {.5, .5}},
-			{{.75, .25}, {.5, .5}, {1, .5}},
-			{{.75, .25}, {1, .5}, {1, 0}},
-			{{.75, .25}, {1, 0}, {.5, 0}}},
-
-			{{{.25, .75}, {0, .5}, {0, 1}},
-			{{.25, .75}, {0, 1}, {.5, 1}},
-			{{.25, .75}, {.5, 1}, {.5, .5}},
-			{{.25, .75}, {.5, .5}, {0, .5}}},
-
-			{{{.75, .75}, {.5, .5}, {.5, 1}},
-			{{.75, .75}, {.5, 1}, {1, 1}},
-			{{.75, .75}, {1, 1}, {1, .5}},
-			{{.75, .75}, {1, .5}, {.5, .5}}}
-		};
-		for(int i = 0; i < 4; 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 ? 1 : 0) + (fmodf(node->y, 2) == 0 ? 2 : 0);
-				tc[0] = tex_coords[k][i][j][0]*node->width;
-				tc[1] = tex_coords[k][i][j][1]*node->height;
-			}
-
-			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 ? 3 : (i*3+6)];
-			v[7] = node->vertex_array[i == 3 ? 4 : (i*3+7)];
-			v[8] = node->vertex_array[i == 3 ? 5 : (i*3+8)];
-		}
-
-		float *n = buffer + vertices_size + normal_chunk_size*index;
-
-		Vector3 bl = normals[(int)((node->x+1)*(height+1) + node->y)];
-		Vector3 br = normals[(int)((node->x)*(height+1) + node->y)];
-		Vector3 tr = normals[(int)((node->x)*(height+1) + node->y+1)];
-		Vector3 tl = normals[(int)((node->x+1)*(height+1) + node->y+1)];
-
-		n[24] = n[30] = bl.x;
-		n[25] = n[31] = bl.y;
-		n[26] = n[32] = bl.z;
-
-		n[3] = n[33] = br.x;
-		n[4] = n[34] = br.y;
-		n[5] = n[35] = br.z;
-
-		n[6] = n[12] = tr.x;
-		n[7] = n[13] = tr.y;
-		n[8] = n[14] = tr.z;
-
-		n[15] = n[21] = tl.x;
-		n[16] = n[22] = tl.y;
-		n[17] = n[23] = tl.z;
-
-		if(node->width == 1) {
-			Vector3 v(bl + br + tr + tl);
-			v /= v.length();
-			n[0] = n[9] = n[18] = n[27] = v.x;
-			n[1] = n[10] = n[19] = n[28] = v.y;
-			n[2] = n[11] = n[20] = n[29] = v.z;
-		} else {
-			Vector3 v(normals[(int)((node->x+node->width/2)*(height+1) + node->y+node->height/2)]);
-			n[0] = n[9] = n[18] = n[27] = v.x;
-			n[1] = n[10] = n[19] = n[28] = v.y;
-			n[2] = n[11] = n[20] = n[29] = v.z;
-		}
-	}
-
-	glUnmapBuffer(GL_ARRAY_BUFFER);
-}
-
-Quadtree::QuadNode* Quadtree::QuadChunk::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 Quadtree::QuadChunk::calc_normals() {
-	float *right, *left, *up, *down;
-	right = left = up = down = NULL;
-	if(tree->terrain->has_chunk(this->x - chunk_size, this->y))
-		right = tree->terrain->get_chunk(this->x - chunk_size, this->y, width, height);
-	if(tree->terrain->has_chunk(this->x + chunk_size, this->y))
-		left = tree->terrain->get_chunk(this->x + chunk_size, this->y, width, height);
-	if(tree->terrain->has_chunk(this->x, this->y + chunk_size))
-		up = tree->terrain->get_chunk(this->x, this->y + chunk_size, width, height);
-	if(tree->terrain->has_chunk(this->x, this->y - chunk_size))
-		down = tree->terrain->get_chunk(this->x, this->y - chunk_size, width, height);
-
-	for(int x = 0; x < width; x++) {
-		for(int y = 0; y < height; y++) {
-			Vector3 p(x, heights[x*(int)(height+1) + y], y);
-			Vector3 N;
-			Vector3 temp;
-
-			// TODO: fix border bugginess
-			float h;
-			if(x > 0 || right) {
-				if(x == 0)
-					h = right[(chunk_size-1)*(int)(height) + y];
-				else
-					h = heights[(x-1)*(int)(height+1) + y];
-				Vector3 U = Vector3(x-1, h, y) - p;
-				if(y > 0 || down) {
-					if(y == 0)
-						h = down[x*(int)(height) + chunk_size - 1];
-					else
-						h = heights[x*(int)(height+1) + y - 1];
-					Vector3 V = Vector3(x, h, y-1) - p;
-					N += V.cross(U);
-				}
-				if(y < height-1 || up) {
-					if(y == height-1)
-						h = up[x*(int)(height)]; // y == 0
-					else
-						h = heights[x*(int)(height+1) + y + 1];
-					Vector3 V = Vector3(x, h, y+1) - p;
-					N += U.cross(V);
-				}
-			}
-			if(x < width-1 || left) {
-				if(x == width-1)
-					h = left[y]; // x == 0
-				else
-					h = heights[(x+1)*(int)(height+1) + y];
-				Vector3 U = Vector3(x+1, h, y) - p;
-				if(y > 0 || down) {
-					if(y == 0)
-						h = down[x*(int)(height) + chunk_size - 1];
-					else
-						h = heights[x*(int)(height+1) + y - 1];
-					Vector3 V = Vector3(x, h, y-1) - p;
-					N += U.cross(V);
-				}
-				if(y < height-1 || up) {
-					if(y == height-1)
-						h = up[x*(int)(height)]; // y == 0
-					else
-						h = heights[x*(int)(height+1) + y + 1];
-					Vector3 V = Vector3(x, h, y+1) - p;
-					N += V.cross(U);
-				}
-			}
-			N /= N.length();
-			normals[x*(int)(height+1) + y] = N;
-		}
-	}
-
-	if(right)
-		delete[] right;
-	if(left)
-		delete[] left;
-	if(up)
-		delete[] up;
-	if(down)
-		delete[] down;
-}
-
-/* Quadtree */
-
-Quadtree::Quadtree() {
-	terrain = new Terrain();
-}
-
-Quadtree::~Quadtree() {
-	delete terrain;
-	for(std::list<QuadChunk*>::iterator it = chunks.begin(); it != chunks.end(); it++) {
-		delete *it;
-	}
-}
-
-void Quadtree::raise(float x, float z, float radius, float focus, float strength, bool up) {
-	// TODO: fix this
-/*	if(x < 0 || x >= width-1 || z < 0 || z >= height-1)
-		return;
-
-	/* adjust heights */
-	/*for(int i = x-radius; i < x+radius; i++) {
-		if(i < 0 || i >= width-1)
-			continue;
-		for(int j = z-radius; j < z+radius; j++) {
-			if(j < 0 || j >= height-1)
-				continue;
-			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);
-
-			if(up)
-				heights[i*height + j] += v;
-			else
-				heights[i*height + j] -= v;
-		}
-	}
-
-	/* recalculate normals */
-	/*for(int i = x-radius-1; i < x+radius; i++) {
-		if(i < 0 || i >= width-1)
-			continue;
-		for(int j = z-radius-1; j < z+radius; j++) {
-			if(j < 0 || j >= height-1)
-				continue;
-			calc_normal(i, j);
-		}
-	}
-
-	/* refill nodes and remake VBOs */
-	/*for(int nx = x-radius-1; nx < x+radius+chunk_size; nx+=chunk_size) {
-		if(nx < 0 || nx >= width-1)
-			continue;
-		for(int nz = z-radius-1; nz < z+radius+chunk_size; nz+=chunk_size) {
-			if(nz < 0 || nz >= height-1)
-				continue;
-			QuadNode *node = find(nx, nz);
-			for(unsigned int i = 0; i < node->chunk->node_count; i++) {
-				node->chunk->nodes[i]->fill();
-			}
-			node->chunk->make_vbo();
-		}
-	}*/
-}
-
-void Quadtree::update(float x, float z) {
-	std::set<std::pair<int, int> > chunk_indices;
-	int i = x - 100;
-	i -= i % chunk_size;
-	for(; i < x + 100; i += chunk_size) {
-		int j = z - 100;
-		j -= j % chunk_size;
-		for(; j < z + 100; j += chunk_size) {
-			float a = i - x;
-			float b = j - z;
-			if(sqrtf(a*a + b*b) < 100)
-				chunk_indices.insert(std::pair<int, int>(i, j));
-		}
-	}
-	for(std::list<QuadChunk*>::iterator it = chunks.begin(); it != chunks.end(); it++) {
-		std::set<std::pair<int, int> >::iterator ind_it = chunk_indices.find(std::pair<int, int>((*it)->x, (*it)->y));
-		if(ind_it != chunk_indices.end()) {
-			chunk_indices.erase(ind_it);
-		}
-		if((*it)->distance(x, z) > 100) {
-			it = chunks.erase(it);
-		}
-	}
-	for(std::set<std::pair<int, int> >::iterator it = chunk_indices.begin(); it != chunk_indices.end(); it++) {
-		QuadChunk *chunk = new QuadChunk(this, it->first, it->second, chunk_size, chunk_size);
-		chunks.push_back(chunk);
-	}
-}
-
-Quadtree::QuadNode *Quadtree::find(float x, float y) {
-	for(std::list<QuadChunk*>::iterator it = chunks.begin(); it != chunks.end(); it++) {
-		QuadNode *node = (*it)->find(x, y);
-		if(node)
-			return node;
-	}
-	return NULL;
-}
-
-Quadtree::QuadNode *Quadtree::get_left(Quadtree::QuadNode *node) {
-	QuadNode *n = find(node->x + node->width*1.5, node->y + node->height / 2);
-	if(n == node)
-		return NULL;
-	return n;
-}
-
-Quadtree::QuadNode *Quadtree::get_right(Quadtree::QuadNode *node) {
-	QuadNode *n = find(node->x - node->width/2, node->y + node->height / 2);
-	if(n == node)
-		return NULL;
-	return n;
-}
-
-Quadtree::QuadNode *Quadtree::get_up(Quadtree::QuadNode *node) {
-	QuadNode *n = find(node->x + node->width/2, node->y + node->height*1.5);
-	if(n == node)
-		return NULL;
-	return n;
-}
-
-Quadtree::QuadNode *Quadtree::get_down(Quadtree::QuadNode *node) {
-	QuadNode *n = find(node->x + node->width/2, node->y);
-	if(n == node)
-		return NULL;
-	return n;
-}
diff --git a/quadtree.h b/quadtree.h
deleted file mode 100644
index 84125d2..0000000
--- a/quadtree.h
+++ /dev/null
@@ -1,68 +0,0 @@
-#ifndef QUADTREE_H
-#define QUADTREE_H
-
-#include "vector.h"
-#include "terrain.h"
-
-#include <list>
-
-class Quadtree {
-	public:
-		struct QuadChunk;
-
-		struct QuadNode {
-			QuadChunk *chunk;
-			float x, y, width, height;
-			float vertex_array[15];
-
-			QuadNode(QuadChunk *chunk, float x, float y, float width, float height);
-			virtual ~QuadNode();
-
-			float distance(float px, float pz);
-			void fill();
-			void draw();
-			void draw_grid();
-			void draw_normal();
-			float get_height(float px, float py);
-			Vector3 get_normal(int index);
-		};
-
-		struct QuadChunk {
-			Quadtree *tree;
-			QuadNode **nodes;
-			float x, y, width, height;
-			float *heights;
-			Vector3 *normals;
-			size_t buf_size;
-			unsigned int vbo_object;
-			unsigned int node_count;
-			unsigned int vertices;
-			float init_time;
-
-			QuadChunk(Quadtree *tree, float x, float y, float width, float height);
-			~QuadChunk();
-
-			float distance(float px, float pz);
-			void make_vbo();
-			QuadNode *find(float x, float y);
-			void calc_normals();
-		};
-
-		static const int chunk_size = 32;
-
-		std::list<QuadChunk*> chunks;
-		Terrain *terrain;
-		Quadtree();
-		virtual ~Quadtree();
-
-		void raise(float x, float z, float radius, float focus, float strength, bool up = true);
-
-		void update(float x, float z);
-		QuadNode *find(float x, float y);
-		QuadNode *get_left(QuadNode *node);
-		QuadNode *get_right(QuadNode *node);
-		QuadNode *get_up(QuadNode *node);
-		QuadNode *get_down(QuadNode *node);
-};
-
-#endif
diff --git a/scene.cpp b/scene.cpp
index 8d7301d..e749347 100644
--- a/scene.cpp
+++ b/scene.cpp
@@ -16,7 +16,7 @@ Scene::Scene() {
 	running = true;
 	grid = false;
 	normals = false;
-	terrain = true;
+	render_terrain = true;
 	gravity = true;
 
 	last_node = NULL;
@@ -48,8 +48,8 @@ Scene::Scene() {
 	soil_texture = load_texture("textures/zooboing-469-sand-modified.jpg");
 	marker_texture = load_texture("textures/cross.png");
 
-	/* init quadtree */
-	qt = new Quadtree();
+	/* init terrain */
+	terrain = new Terrain();
 
 	/* load font */
 	font = new FTTextureFont("fonts/VeraMono.ttf");
@@ -61,8 +61,8 @@ Scene::Scene() {
 Scene::~Scene() {
 	if(tool)
 		delete tool;
-	if(qt)
-		delete qt;
+	if(terrain)
+		delete terrain;
 	delete font;
 }
 
@@ -129,7 +129,7 @@ bool Scene::select(int x, int y, float& px, float& py, float& pz) {
 }
 
 void Scene::update() {
-	qt->update(pos.x, pos.z);
+	terrain->update(pos.x, pos.z);
 }
 
 void Scene::events() {
@@ -158,7 +158,7 @@ void Scene::events() {
 						normals = !normals;
 						break;
 					case SDLK_t:
-						terrain = !terrain;
+						render_terrain = !render_terrain;
 						break;
 					case SDLK_SPACE:
 						yvel = .05;
@@ -174,7 +174,7 @@ void Scene::events() {
 						break;
 					case SDLK_1:
 						if(tool) delete tool;
-						tool = new RaiseTool(qt);
+						tool = new RaiseTool(terrain);
 						break;
 					default:
 						break;
@@ -284,7 +284,7 @@ void Scene::render() {
 	}
 
 	std::string move_str;
-	Quadtree::QuadNode *node = qt->find(pos.x, pos.z);
+	Terrain::Node *node = terrain->find(pos.x, pos.z);
 	if(node) {
 		if(gravity) {
 			float y = node->get_height(pos.x, pos.z);
@@ -316,7 +316,7 @@ void Scene::render() {
 	//glLightfv(GL_LIGHT0, GL_POSITION, light_pos);
 
 	unsigned int chunks_rendered = 0;
-	if(terrain) {
+	if(render_terrain) {
 		terrain_program.use();
 		GLint show_sel = glGetUniformLocation(terrain_program.get_program(), "show_sel");
 		glUniform1i(show_sel, show_selection ? 1 : 0);
@@ -346,8 +346,8 @@ void Scene::render() {
 		while(!q.empty()) {
 			Quadtree::QuadChunk *chunk = q.front();
 			q.pop();*/
-		for(std::list<Quadtree::QuadChunk*>::iterator it = qt->chunks.begin(); it != qt->chunks.end(); it++) {
-			Quadtree::QuadChunk *chunk = *it;
+		for(std::list<Terrain::Chunk*>::iterator it = terrain->chunks.begin(); it != terrain->chunks.end(); it++) {
+			Terrain::Chunk *chunk = *it;
 			/*if(!chunk->nodes) {
 				for(int i = 0; i < 4; i++)
 					q.push(chunk->children[i]);
@@ -390,8 +390,8 @@ void Scene::render() {
 		while(!q.empty()) {
 			Quadtree::QuadChunk *chunk = q.front();
 			q.pop();*/
-		for(std::list<Quadtree::QuadChunk*>::iterator it = qt->chunks.begin(); it != qt->chunks.end(); it++) {
-			Quadtree::QuadChunk *chunk = *it;
+		for(std::list<Terrain::Chunk*>::iterator it = terrain->chunks.begin(); it != terrain->chunks.end(); it++) {
+			Terrain::Chunk *chunk = *it;
 			glPushMatrix();
 			glTranslatef(-pos.x, -pos.y, -pos.z);
 			/*if(!chunk->nodes) {
@@ -406,8 +406,8 @@ void Scene::render() {
 		}
 	}
 	if(normals) {
-		for(std::list<Quadtree::QuadChunk*>::iterator it = qt->chunks.begin(); it != qt->chunks.end(); it++) {
-			Quadtree::QuadChunk *chunk = *it;
+		for(std::list<Terrain::Chunk*>::iterator it = terrain->chunks.begin(); it != terrain->chunks.end(); it++) {
+			Terrain::Chunk *chunk = *it;
 			glPushMatrix();
 			glTranslatef(-pos.x, -pos.y, -pos.z);
 			for(unsigned int i = 0; i < chunk->node_count; i++)
diff --git a/scene.h b/scene.h
index af4f96f..82c1100 100644
--- a/scene.h
+++ b/scene.h
@@ -2,7 +2,7 @@
 #define SCENE_H
 
 #include "vector.h"
-#include "quadtree.h"
+#include "terrain.h"
 #include "gl.h"
 #include "shader.h"
 #include "gui.h"
@@ -15,7 +15,7 @@ class Scene {
 		float pitch, yaw;
 		Vector3 pos;
 		float yvel;
-		Quadtree *qt;
+		Terrain *terrain;
 		FTFont *font;
 		GUI *gui;
 		Tool *tool;
@@ -23,11 +23,11 @@ class Scene {
 		bool running;
 		bool grid;
 		bool normals;
-		bool terrain;
+		bool render_terrain;
 		bool gravity;
 		bool dialog;
 
-		Quadtree::QuadNode *last_node;
+		Terrain::Node *last_node;
 
 		unsigned int last_time;
 		Vector3 selected;
diff --git a/terrain.cpp b/terrain.cpp
index e0cd291..a6f1e66 100644
--- a/terrain.cpp
+++ b/terrain.cpp
@@ -1,12 +1,445 @@
 #include "terrain.h"
+#include "vector.h"
+
+#include "gl.h"
 
 #include <noise/noise.h>
 #include "noiseutils/noiseutils.h"
 
 #include <iostream>
+#include <cmath>
+#include <queue>
+#include <set>
 
 using namespace noise;
 
+using std::min;
+using std::max;
+
+Terrain::Node::Node(Chunk *chunk, float x, float y, float width, float height) {
+	this->chunk = chunk;
+	this->x = x;
+	this->y = y;
+	this->width = width;
+	this->height = height;
+
+	fill();
+}
+
+Terrain::Node::~Node() {
+}
+
+float Terrain::Node::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::Node::fill() {
+	vertex_array[0] = x + width / 2;
+	vertex_array[1] = chunk->heights[(int)floorf((int)(x + width/2)*(chunk->height+1) + (int)(y + height/2))];
+	vertex_array[2] = y + height / 2;
+
+	vertex_array[3] = x;
+	vertex_array[4] = chunk->heights[(int)floorf((x)*(chunk->height+1)+y)];
+	vertex_array[5] = y;
+
+	vertex_array[6] = x;
+	vertex_array[7] = chunk->heights[(int)floorf((x)*(chunk->height+1) + (y + height))];
+	vertex_array[8] = y + height;
+
+	vertex_array[9] = x + width;
+	vertex_array[10] = chunk->heights[(int)floorf((x + width)*(chunk->height+1) + (y + height))];
+	vertex_array[11] = y + height;
+
+	vertex_array[12] = x + width;
+	vertex_array[13] = chunk->heights[(int)floorf((x + width)*(chunk->height+1) + y)];
+	vertex_array[14] = y;
+
+	/* midpoint is average of corner heights when width == 1 */
+	if(width == 1) {
+		vertex_array[1] = (vertex_array[4] + vertex_array[7] + vertex_array[10] + vertex_array[13])/4;
+	}
+}
+
+void Terrain::Node::draw() {
+	float tex_coords[4][3][2] = {
+		{{.5, .5}, {0, 0}, {0, 1}},
+		{{.5, .5}, {0, 1}, {1, 1}},
+		{{.5, .5}, {1, 1}, {1, 0}},
+		{{.5, .5}, {1, 0}, {0, 0}}
+	};
+
+	glBegin(GL_TRIANGLES);
+	for(int i = 0; i < 4; i++) {
+		Vector3 a(vertex_array[0], vertex_array[1], vertex_array[2]);
+		Vector3 b(vertex_array[i*3+3], vertex_array[i*3+4], vertex_array[i*3+5]);
+		Vector3 c(vertex_array[i == 3 ? 3 : (i*3+6)], vertex_array[i == 3 ? 4 : (i*3+7)], vertex_array[i == 3 ? 5 : (i*3+8)]);
+
+		Vector3 U(c.x-a.x, c.y-a.y, c.z-a.z);
+		Vector3 V(b.x-a.x, b.y-a.y, b.z-a.z);
+		Vector3 N(V.cross(U));
+		glNormal3f(N.x, N.y, N.z);
+
+		glTexCoord2f(tex_coords[i][0][0], tex_coords[i][0][1]);
+		glVertex3f(a.x, a.y, a.z);
+
+		glTexCoord2f(tex_coords[i][1][0], tex_coords[i][1][1]);
+		glVertex3f(b.x, b.y, b.z);
+
+		glTexCoord2f(tex_coords[i][2][0], tex_coords[i][2][1]);
+		glVertex3f(c.x, c.y, c.z);
+	}
+	glEnd();
+}
+
+void Terrain::Node::draw_grid() {
+	glNormal3f(0, 1, 0);
+	glBegin(GL_LINES);
+	for(int i = 0; i < 4; i++) {
+		Vector3 a(vertex_array[0], vertex_array[1], vertex_array[2]);
+		Vector3 b(vertex_array[i*3+3], vertex_array[i*3+4], vertex_array[i*3+5]);
+
+		glVertex3f(chunk->x + a.x, a.y, chunk->y + a.z);
+		glVertex3f(chunk->x + b.x, b.y, chunk->y + b.z);
+	}
+	glEnd();
+	glBegin(GL_LINE_LOOP);
+		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[12], vertex_array[13], chunk->y + vertex_array[14]);
+	glEnd();
+}
+
+void Terrain::Node::draw_normal() {
+	glNormal3f(0, 1, 0);
+	glColor3f(1, 0, 0);
+	int i = (int)(x*(chunk->height+1) + y);
+	glBegin(GL_LINES);
+		Vector3 N = chunk->normals[i];
+		glVertex3f(chunk->x + x, chunk->heights[i], chunk->y + y);
+		glVertex3f(chunk->x + x + N.x, chunk->heights[i] + 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;
+	bool top;
+	top = px - x >= height - (py - y);
+	left = px - x >= py - y;
+	Vector3 a(vertex_array[0], vertex_array[1], vertex_array[2]);
+	Vector3 b, c;
+	int bi, ci;
+	if(left) {
+		if(top) {
+			bi = 3*3;
+			ci = 4*3;
+		} else {
+			bi = 4*3;
+			ci = 1*3;
+		}
+	} else {
+		if(top) {
+			bi = 2*3;
+			ci = 3*3;
+		} else {
+			bi = 1*3;
+			ci = 2*3;
+		}
+	}
+	b = Vector3(vertex_array[bi], vertex_array[bi+1], vertex_array[bi+2]);
+	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, float width, float height) {
+	this->terrain = terrain;
+	this->x = x;
+	this->y = y;
+	this->width = width;
+	this->height = height;
+	this->vbo_object = this->node_count = this->vertices = 0;
+	this->nodes = NULL;
+	heights = terrain->generate_heights(x, y, width+1, height+1);
+	normals = new Vector3[(int)((width+1)*(height+1))];
+
+	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, 1, 1);
+		}
+	}
+	make_vbo();
+}
+
+Terrain::Chunk::~Chunk() {
+	for(unsigned int i = 0; i < node_count; i++)
+		delete nodes[i];
+	delete[] nodes;
+	delete[] heights;
+	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*12;
+	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*12;
+	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*12;
+	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];
+		float tex_coords[4][4][3][2] = {
+			{{{.25, .25}, {0, 0}, {0, .5}},
+			{{.25, .25}, {0, .5}, {.5, .5}},
+			{{.25, .25}, {.5, .5}, {.5, 0}},
+			{{.25, .25}, {.5, 0}, {0, 0}}},
+
+			{{{.75, .25}, {.5, 0}, {.5, .5}},
+			{{.75, .25}, {.5, .5}, {1, .5}},
+			{{.75, .25}, {1, .5}, {1, 0}},
+			{{.75, .25}, {1, 0}, {.5, 0}}},
+
+			{{{.25, .75}, {0, .5}, {0, 1}},
+			{{.25, .75}, {0, 1}, {.5, 1}},
+			{{.25, .75}, {.5, 1}, {.5, .5}},
+			{{.25, .75}, {.5, .5}, {0, .5}}},
+
+			{{{.75, .75}, {.5, .5}, {.5, 1}},
+			{{.75, .75}, {.5, 1}, {1, 1}},
+			{{.75, .75}, {1, 1}, {1, .5}},
+			{{.75, .75}, {1, .5}, {.5, .5}}}
+		};
+		for(int i = 0; i < 4; 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 ? 1 : 0) + (fmodf(node->y, 2) == 0 ? 2 : 0);
+				tc[0] = tex_coords[k][i][j][0]*node->width;
+				tc[1] = tex_coords[k][i][j][1]*node->height;
+			}
+
+			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 ? 3 : (i*3+6)];
+			v[7] = node->vertex_array[i == 3 ? 4 : (i*3+7)];
+			v[8] = node->vertex_array[i == 3 ? 5 : (i*3+8)];
+		}
+
+		float *n = buffer + vertices_size + normal_chunk_size*index;
+
+		Vector3 bl = normals[(int)((node->x+1)*(height+1) + node->y)];
+		Vector3 br = normals[(int)((node->x)*(height+1) + node->y)];
+		Vector3 tr = normals[(int)((node->x)*(height+1) + node->y+1)];
+		Vector3 tl = normals[(int)((node->x+1)*(height+1) + node->y+1)];
+
+		n[24] = n[30] = bl.