Initial commit.

11 files changed, 1046 insertions, 0 deletions

diff --git a/.gitignore b/.gitignore
new file mode 100644
index 0000000..16c9d65
--- /dev/null
+++ b/.gitignore
@@ -0,0 +1,7 @@
+.sconsign.dblite
+/foo
+*.o
+*.ttf
+*.png
+*.jpg
+.*.swp
diff --git a/SConstruct b/SConstruct
new file mode 100644
index 0000000..1e7d2e3
--- /dev/null
+++ b/SConstruct
@@ -0,0 +1,27 @@
+import os
+
+env = Environment(
+	ENV = os.environ,
+)
+
+AddOption('--release', action = 'store_true')
+AddOption('--profiling', action = 'store_true')
+
+env.Append(CPPPATH = ['.'])
+env.Append(LIBS = ['GL', 'GLU'])
+env.ParseConfig('sdl-config --cflags --libs')
+env.ParseConfig('pkg-config --cflags --libs SDL_image')
+env.ParseConfig('pkg-config --cflags --libs ftgl')
+
+if not GetOption('release'):
+	env.Append(CPPFLAGS = ['-Wall', '-g'])
+
+if GetOption('profiling'):
+	env.Append(CPPFLAGS = ['-pg'])
+	env.Append(LINKFLAGS = ['-pg'])
+
+Export('env')
+
+env.Program('foo', Glob('*.cpp'))
+
+# vim: syn=python
diff --git a/main.cpp b/main.cpp
new file mode 100644
index 0000000..b653427
--- /dev/null
+++ b/main.cpp
@@ -0,0 +1,331 @@
+#include "video.h"
+#include "scene.h"
+#include "vector.h"
+#include "quadtree.h"
+
+#include <SDL_image.h>
+#include <FTGL/ftgl.h>
+#include <boost/format.hpp>
+#include <boost/shared_ptr.hpp>
+
+#define GL_GLEXT_PROTOTYPES
+#include <SDL_opengl.h>
+//#include <GL/gl.h>
+#include <GL/gl.h>
+//#include <GL/glu.h>
+
+#include <iostream>
+#include <cmath>
+#include <list>
+#include <vector>
+#include <map>
+#include <queue>
+
+FTFont *font;
+
+Scene scene;
+
+struct hit_record {
+	uint32_t hits;
+	int32_t min_z;
+	int32_t max_z;
+	uint32_t name;
+};
+
+// TODO: reimplement
+int select(Quadtree& qt, int x, int y) {
+	y = 600-y;
+	glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT);
+
+	GLuint buf[64] = {0};
+	GLint hits, view[4] = {0};
+	uint32_t id = 0;
+	glSelectBuffer(64, buf);
+	glGetIntegerv(GL_VIEWPORT, view);
+	glRenderMode(GL_SELECT);
+	glInitNames();
+
+	//glPushName(0);
+	glMatrixMode(GL_PROJECTION);
+	glPushMatrix();
+		glLoadIdentity();
+		gluPickMatrix(x, y, 1, 1, view);
+		gluPerspective(45, (float)view[2] / (float)view[3], 1, 10000);
+		glMatrixMode(GL_MODELVIEW);
+		glLoadIdentity();
+		scene.lookat();
+
+		std::vector<Quadtree::QuadNode*> nodes;
+		uint32_t index = 0;
+		std::queue<Quadtree::QuadNode*> q;
+		q.push(qt.root);
+		while(!q.empty()) {
+			Quadtree::QuadNode *node = q.front();
+			q.pop();
+			if(node->vertex_array) {
+				glPushName(++index);
+				/*glBegin(GL_QUADS);
+					glVertex3f(node->x - node->width/2,
+				glEnd();*/
+				glPopName();
+				node->draw();
+			} else
+				for(int i = 0; i < 4; i++)
+					q.push(node->children[i]);
+		}
+		glMatrixMode(GL_PROJECTION);
+	glPopMatrix();
+	//glMatrixMode(GL_MODELVIEW);
+	//glFlush();
+	hits = glRenderMode(GL_RENDER);
+	//std::cout << "hits: " << hits << std::endl;
+	for(int i = 0; i < hits; i++) {
+		struct hit_record *hit = (struct hit_record*)(buf + i*sizeof(hit_record));
+		//std::cout << "  hits: " << hit->hits << "  min_z: " << hit->min_z << "  max_z: " << hit->max_z << std::endl;
+		if(hit->hits == 1 && hit->name > 0)
+			id = hit->name;
+	}
+	glMatrixMode(GL_MODELVIEW);
+	//std::cout << "id: " << id << std::endl;
+	if(id > 0) {
+		//return map[vectors[id-1]];
+	}
+	//return Vector3::p();
+	//return id;
+	return 0;
+}
+
+int main(int argc, char **argv) {
+	video::width = 800;
+	video::height = 600;
+	video::init();
+
+	font = new FTTextureFont("font.ttf");
+	font->FaceSize(10);
+
+	SDL_Surface *hm = IMG_Load("heightmap6.png");
+	unsigned char *pixels = (unsigned char*)hm->pixels;
+	float *heightmap = new float[hm->w * hm->h];
+	for(int x = 0; x < hm->w; x++) {
+		for(int y = 0; y < hm->h; y++) {
+			heightmap[y*hm->w + x] = ((float)(pixels[y*hm->w + x]) / 256) * 20;
+		}
+	}
+	int level = 3;
+	Quadtree *qt = new Quadtree(hm->w, hm->h, heightmap, level);
+	//Quadtree qt(qt_size, qt_size, (int)ceil(sqrt(qt_size)));
+
+	GLuint grass_texture;
+	{
+		SDL_Surface *surface = IMG_Load("Grass0073_3_S.jpg");
+		SDL_Surface *image = SDL_CreateRGBSurface(SDL_SWSURFACE, surface->w, surface->h, 32,
+				0x000000ff, 0x0000ff00, 0x00ff0000, 0xff000000);
+		SDL_Rect area;
+		area.x = area.y = 0;
+		area.w = surface->w;
+		area.h = surface->h;
+		SDL_BlitSurface(surface, &area, image, &area);
+		//glPixelStorei(GL_UNPACK_ALIGNMENT, 4);
+		glGenTextures(1, &grass_texture);
+		glBindTexture(GL_TEXTURE_2D, grass_texture);
+		glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_MIN_FILTER, GL_LINEAR_MIPMAP_LINEAR);
+		glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_MAG_FILTER, GL_LINEAR_MIPMAP_LINEAR);
+		if(image->format->Amask) {
+			//glTexImage2D(GL_TEXTURE_2D, 0, GL_RGBA, image->w, image->h, 0, GL_RGBA, GL_UNSIGNED_BYTE, image->pixels);
+			gluBuild2DMipmaps(GL_TEXTURE_2D, 4, image->w, image->h, GL_RGBA, GL_UNSIGNED_BYTE, image->pixels);
+		} else {
+			//glTexImage2D(GL_TEXTURE_2D, 0, GL_RGB, image->w, image->h, 0, GL_RGB, GL_UNSIGNED_BYTE, image->pixels);
+			gluBuild2DMipmaps(GL_TEXTURE_2D, 3, image->w, image->h, GL_RGB, GL_UNSIGNED_BYTE, image->pixels);
+		}
+		SDL_FreeSurface(surface);
+		SDL_FreeSurface(image);
+	}
+
+	//SDL_WM_GrabInput(SDL_GRAB_ON);
+
+	SDL_Event event;
+	bool running = true;
+	bool grid = false;
+	SDL_WarpMouse(video::width/2, video::height/2);
+	unsigned int last_time = SDL_GetTicks();
+	/*boost::timer t;
+	double last_time = 0;*/
+	while(running) {
+		unsigned int time = SDL_GetTicks();
+		//double time = t.elapsed();
+		//t.restart();
+		unsigned int steps = time - last_time + 1;
+		//double steps = (time - last_time) * 1000;
+		last_time = time;
+		while(SDL_PollEvent(&event)) {
+			switch(event.type) {
+				case SDL_QUIT:
+					running = false;
+					break;
+				case SDL_KEYDOWN:
+					switch(event.key.keysym.sym) {
+						case SDLK_ESCAPE:
+							running = false;
+							break;
+						case SDLK_g:
+							grid = !grid;
+							break;
+						case SDLK_KP_PLUS:
+							delete qt;
+							qt = new Quadtree(hm->w, hm->h, heightmap, ++level);
+							break;
+						case SDLK_KP_MINUS:
+							if(level > 0) {
+								delete qt;
+								qt = new Quadtree(hm->w, hm->h, heightmap, --level);
+							}
+							break;
+						case SDLK_SPACE:
+							scene.yvel = .05;
+							break;
+						default:
+							break;
+					}
+					break;
+				case SDL_MOUSEBUTTONUP:
+					switch(event.button.button) {
+						case SDL_BUTTON_LEFT:
+							// TODO: reimplement selection
+							break;
+						case SDL_BUTTON_WHEELUP:
+						case SDL_BUTTON_WHEELDOWN:
+							// TODO: reimplement?
+							break;
+					}
+				case SDL_MOUSEMOTION:
+					if(event.motion.x == video::width/2 && event.motion.y == video::height/2)
+						break;
+					scene.yaw += (float)event.motion.xrel / 500;
+					scene.pitch += (float)event.motion.yrel / 500;
+					if(scene.yaw > 2*M_PI)
+						scene.yaw -= 2*M_PI;
+					else if(scene.yaw < 0)
+						scene.yaw += 2*M_PI;
+					if(scene.pitch > M_PI)
+						scene.pitch = M_PI;
+					else if(scene.pitch < 0)
+						scene.pitch = 0;
+					SDL_WarpMouse(video::width/2, video::height/2);
+					break;
+			}
+		}
+
+		glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT);
+		glLoadIdentity();
+		video::persp();
+
+		unsigned char *keystate = SDL_GetKeyState(NULL);
+		float forward = 0;
+		float right = 0;
+		bool moved = false;
+		if(keystate[SDLK_w]) {
+			moved = true;
+			forward++;
+		}
+		if(keystate[SDLK_s]) {
+			moved = true;
+			forward--;
+		}
+		if(keystate[SDLK_a]) {
+			moved = true;
+			right--;
+		}
+		if(keystate[SDLK_d]) {
+			moved = true;
+			right++;
+		}
+		if(keystate[SDLK_q])
+			scene.pos.y -= 0.002*steps;
+		if(keystate[SDLK_e])
+			scene.pos.y += 0.002*steps*(keystate[SDLK_LSHIFT]?10:1);
+		if(moved && (forward || right))
+			scene.move(forward, right, steps*(keystate[SDLK_LSHIFT]?10:1));
+
+		std::string move_str;
+		{
+			Quadtree::QuadNode *node = qt->find(scene.pos.x, scene.pos.z);
+			if(node) {
+				float y = node->get_height(scene.pos.x, scene.pos.z);
+				if(scene.pos.y > y && !keystate[SDLK_e])
+					scene.yvel -= 9.81 * steps / 85000;
+				if(scene.yvel < -.5)
+					scene.yvel = -.5;
+				scene.pos.y += scene.yvel;
+				if(scene.pos.y < y) {
+					scene.pos.y = y;
+					scene.yvel = 0;
+				}
+				move_str = (boost::format("%s %.2f,%.2f %dx%d") % scene.pos.str() % node->x % node->y % node->width % node->height).str();
+			}
+		}
+
+		scene.lookat();
+
+		glEnable(GL_LIGHTING);
+		//const float light_pos[4] = {50, 20, 50, 1};
+		const float light_pos[4] = {0, 1, 0, 0};
+		glLightfv(GL_LIGHT0, GL_POSITION, light_pos);
+
+		if(!grid) {
+			glBindTexture(GL_TEXTURE_2D, grass_texture);
+			glEnable(GL_TEXTURE_2D);
+			glBindBuffer(GL_ARRAY_BUFFER, qt->vbo_object);
+			glVertexPointer(3, GL_FLOAT, 0, NULL);
+			glNormalPointer(GL_FLOAT, 0, (GLvoid*)(qt->vertices*3*sizeof(float)));
+			glTexCoordPointer(2, GL_FLOAT, 0, (GLvoid*)(qt->vertices*3*sizeof(float)*2));
+			glEnableClientState(GL_VERTEX_ARRAY);
+			glEnableClientState(GL_NORMAL_ARRAY);
+			glEnableClientState(GL_TEXTURE_COORD_ARRAY);
+			glDrawArrays(GL_TRIANGLES, 0, qt->vertices);
+			glDisableClientState(GL_VERTEX_ARRAY);
+			glDisableClientState(GL_NORMAL_ARRAY);
+			glDisableClientState(GL_TEXTURE_COORD_ARRAY);
+		} else {
+			std::queue<Quadtree::QuadNode*> q;
+			q.push(qt->root);
+			glBindTexture(GL_TEXTURE_2D, grass_texture);
+			glEnable(GL_TEXTURE_2D);
+			while(!q.empty()) {
+				Quadtree::QuadNode *node = q.front();
+				q.pop();
+				if(node->vertex_array) {
+					grid ? node->draw_grid() : node->draw();
+				} else
+					for(int i = 0; i < 4; i++)
+						q.push(node->children[i]);
+			}
+		}
+
+		glDisable(GL_TEXTURE_2D);
+		glDisable(GL_LIGHTING);
+
+		video::ortho();
+		float height = font->LineHeight();
+		glColor3f(1, 1, 1);
+		glTranslatef(0, 600-height, 0);
+		font->Render((boost::format("%dx%d  %d levels  %d nodes  tree creation time: %f  steps: %d")
+					% qt->width % qt->height % qt->levels % qt->nodes % qt->init_time % steps).str().c_str());
+		//glTranslatef(0, height, 0);
+		//font->Render((boost::format("selected: %x") % selected).str().c_str());
+		glTranslatef(0, -height, 0);
+		font->Render(move_str.c_str());
+		/*if(selected) {
+			glTranslatef(0, height, 0);
+			//font->Render((boost::format("(%s %s %s %s)") % selected->a->str() % selected->b->str() % selected->c->str() % selected->d->str()).str().c_str());
+			font->Render(selected->str().c_str());
+		}*/
+
+		SDL_GL_SwapBuffers();
+
+		usleep(1000);
+	}
+
+	video::free();
+
+	return 0;
+}
diff --git a/quadtree.cpp b/quadtree.cpp
new file mode 100644
index 0000000..33011d5
--- /dev/null
+++ b/quadtree.cpp
@@ -0,0 +1,302 @@
+#include "quadtree.h"
+#include "vector.h"
+
+#include <boost/format.hpp>
+#include <boost/timer.hpp>
+
+#define GL_GLEXT_PROTOTYPES
+#include <GL/gl.h>
+
+#include <iostream>
+#include <cmath>
+#include <queue>
+
+Quadtree::Quadtree(int width, int height, float *heightmap, int levels) {
+	this->width = width;
+	this->height = height;
+	vbo_object = 0;
+
+	int l = log2f(width);
+	if(levels > l) {
+		levels = l;
+	}
+	heights = heightmap;
+	this->levels = levels;
+
+	boost::timer t;
+	root = new QuadNode(this, NULL, 0, 0, width, height, 1, levels == 0);
+	std::queue<Quadtree::QuadNode*> q;
+	if(levels > 0)
+		q.push(root);
+	while(!q.empty()) {
+		Quadtree::QuadNode *node = q.front();
+		q.pop();
+		node->subdivide(node->level == levels);
+		if(node->level < levels) {
+			for(int i = 0; i < 4; i++)
+				q.push(node->children[i]);
+		}
+	}
+
+	make_vbo();
+
+	init_time = t.elapsed();
+}
+
+Quadtree::~Quadtree() {
+	if(vbo_object)
+		glDeleteBuffers(1, &vbo_object);
+	delete root;
+	//delete[] heights;
+}
+
+Quadtree::QuadNode::QuadNode(Quadtree *tree, QuadNode *parent, float x, float y, float width, float height, int level, bool leaf) {
+	this->tree = tree;
+	this->parent = parent;
+	this->x = x;
+	this->y = y;
+	this->width = width;
+	this->height = height;
+	this->level = level;
+	children[0] = children[1] = children[2] = children[3] = NULL;
+	if(!leaf) {
+		elems = 0;
+		vertex_array = NULL;
+		return;
+	}
+	elems = 3*5;
+	int size = sizeof(float)*elems;
+	vertex_array = new float[size];
+	vertex_array[0] = x + width / 2;
+	vertex_array[1] = tree->heights[(int)floorf((int)(x + width/2)*tree->height + (int)(y + height/2))];
+	vertex_array[2] = y + height / 2;
+
+	vertex_array[3] = x;
+	vertex_array[4] = tree->heights[(int)floorf(x*tree->height+y)];
+	vertex_array[5] = y;
+
+	vertex_array[6] = x;
+	vertex_array[7] = tree->heights[(int)floorf(x*tree->height + (y + height))];
+	vertex_array[8] = y + height;
+
+	vertex_array[9] = x + width;
+	vertex_array[10] = tree->heights[(int)floorf((x + width)*tree->height + (y + height))];
+	vertex_array[11] = y + height;
+
+	vertex_array[12] = x + width;
+	vertex_array[13] = tree->heights[(int)floorf((x + width)*tree->height + y)];
+	vertex_array[14] = y;
+}
+
+Quadtree::QuadNode::~QuadNode() {
+	if(vertex_array)
+		delete[] vertex_array;
+	for(int i = 0; i < 4; i++)
+		if(children[i])
+			delete children[i];
+}
+
+void Quadtree::QuadNode::subdivide(bool leaf) {
+	if(vertex_array) {
+		elems = 0;
+		delete[] vertex_array;
+		vertex_array = NULL;
+	}
+
+	for(int i = 0; i < 4; i++) {
+		float nx = x + ((i & 1) ^ ((i & 2) >> 1)) * width / 2;
+		float ny = y + ((i & 2) >> 1) * height / 2;
+		children[i] = new QuadNode(tree, this, nx, ny, width / 2, height / 2, level + 1, leaf);
+	}
+}
+
+void Quadtree::QuadNode::draw() {
+	if(!vertex_array)
+		return;
+
+	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() {
+	if(!vertex_array)
+		return;
+
+	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(a.x, a.y, a.z);
+		glVertex3f(b.x, b.y, b.z);
+	}
+	glEnd();
+	glBegin(GL_LINE_LOOP);
+		glVertex3f(vertex_array[3], vertex_array[4], vertex_array[5]);
+		glVertex3f(vertex_array[6], vertex_array[7], vertex_array[8]);
+		glVertex3f(vertex_array[9], vertex_array[10], vertex_array[11]);
+		glVertex3f(vertex_array[12], vertex_array[13], vertex_array[14]);
+	glEnd();
+}
+
+float Quadtree::QuadNode::get_height(float px, float py) {
+	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;
+}
+
+unsigned int Quadtree::count_nodes() {
+	std::queue<Quadtree::QuadNode*> q;
+	q.push(root);
+	unsigned int count = 0;
+	while(!q.empty()) {
+		Quadtree::QuadNode *node = q.front();
+		q.pop();
+
+		if(!node->vertex_array) {
+			for(int i = 0; i < 4; i++)
+				q.push(node->children[i]);
+		} else {
+			count++;
+		}
+	}
+
+	return count;
+}
+
+void Quadtree::make_vbo() {
+	nodes = count_nodes();
+	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*nodes;
+	const size_t normal_chunk_size = vertex_chunk_size;
+	const size_t normals_size = normal_chunk_size*nodes;
+	const size_t tex_coord_chunk_size = sizeof(float)*2*12;
+	const size_t tex_coords_size = tex_coord_chunk_size*nodes;
+
+	glBufferData(GL_ARRAY_BUFFER, vertices_size + normals_size + tex_coords_size, NULL, GL_DYNAMIC_DRAW);
+
+	std::queue<Quadtree::QuadNode*> q;
+	q.push(root);
+	unsigned int offset = 0;
+	vertices = nodes*12;
+	unsigned int index = 0;
+	while(!q.empty()) {
+		Quadtree::QuadNode* n = q.front();
+		q.pop();
+		if(!n->vertex_array) {
+			for(int j = 0; j < 4; j++)
+				q.push(n->children[j]);
+			continue;
+		}
+		int size = 12*3*sizeof(float);
+		float v[3*12];
+		v[0] = n->vertex_array[0];
+		v[1] = n->vertex_array[1];
+		v[2] = n->vertex_array[2];
+		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}}
+		};
+		for(int i = 0; i < 4; i++) {
+			v[3] = n->vertex_array[i*3+3];
+			v[4] = n->vertex_array[i*3+4];
+			v[5] = n->vertex_array[i*3+5];
+
+			v[6] = n->vertex_array[i == 3 ? 3 : (i*3+6)];
+			v[7] = n->vertex_array[i == 3 ? 4 : (i*3+7)];
+			v[8] = n->vertex_array[i == 3 ? 5 : (i*3+8)];
+			glBufferSubData(GL_ARRAY_BUFFER, vertex_chunk_size*index + sizeof(float)*3*3*i, sizeof(float)*3*3, v);
+
+			Vector3 U(v[6]-v[0], v[7]-v[1], v[8]-v[2]);
+			Vector3 V(v[3]-v[0], v[4]-v[1], v[5]-v[2]);
+			Vector3 N(V.cross(U));
+			float n[3*3];
+			n[0] = n[3] = n[6] = N.x;
+			n[1] = n[4] = n[7] = N.y;
+			n[2] = n[5] = n[8] = N.z;
+
+			glBufferSubData(GL_ARRAY_BUFFER, vertices_size + normal_chunk_size*index + sizeof(float)*3*3*i, sizeof(float)*3*3, n);
+		}
+		glBufferSubData(GL_ARRAY_BUFFER, vertices_size + normals_size + tex_coord_chunk_size*index, tex_coord_chunk_size, tex_coords);
+		index++;
+		offset += size;
+	}
+}
+
+Quadtree::QuadNode* Quadtree::find(float x, float y) {
+	QuadNode *node = root;
+	while(!node->vertex_array) {
+		float mx = node->x + node->width / 2;
+		float my = node->y + node->height / 2;
+		int i = 2*(y > my);
+		if(i < 2 && x > mx)
+			i = 1;
+		else if(i == 2 && x < mx)
+			i = 3;
+		node = node->children[i];
+	}
+
+	return node;
+}
diff --git a/quadtree.h b/quadtree.h
new file mode 100644
index 0000000..9a84e98
--- /dev/null
+++ b/quadtree.h
@@ -0,0 +1,39 @@
+#ifndef QUADTREE_H
+#define QUADTREE_H
+
+class Quadtree {
+	public:
+		struct QuadNode {
+			Quadtree *tree;
+			QuadNode *parent;
+			QuadNode *children[4];
+			int elems;
+			float x, y, width, height;
+			int level;
+			float *vertex_array;
+
+			QuadNode(Quadtree *tree, QuadNode *parent, float x, float y, float width, float height, int level, bool leaf);
+			virtual ~QuadNode();
+
+			void subdivide(bool leaf = true);
+			void draw();
+			void draw_grid();
+			float get_height(float px, float py);
+		};
+
+		float *heights;
+		int width, height, levels;
+		float init_time;
+		QuadNode *root;
+		unsigned int vbo_object;
+		unsigned int nodes;
+		unsigned int vertices;
+		Quadtree(int width, int height, float *heightmap, int levels);
+		virtual ~Quadtree();
+
+		unsigned int count_nodes();
+		void make_vbo();
+		QuadNode *find(float x, float y);
+};
+
+#endif
diff --git a/scene.cpp b/scene.cpp
new file mode 100644
index 0000000..47b76bf
--- /dev/null
+++ b/scene.cpp
@@ -0,0 +1,46 @@
+#include "scene.h"
+
+#include <SDL_opengl.h>
+
+#include <cmath>
+
+#define inrange(a, b, c) ((a) >= (b) && (a) <= (c))
+
+void Scene::lookat() {
+	/* calculate cartesian coordinates for the center vector where yaw is Φ and pitch is θ
+	 * x = cos Φ sin θ
+	 * y = cos θ
+	 * z = sin Φ sin θ
+	 */
+	Vector3 center(sinf(pitch) * cosf(yaw), cosf(pitch), sinf(pitch) * sinf(yaw));
+	center += pos;
+	center.y += 1;
+	//Vector3 up(cosf(yaw) * cosf(pitch), sinf(pitch), sinf(yaw) * cosf(pitch));
+	Vector3 up(-cosf(pitch) * cosf(yaw), sinf(pitch), -cosf(pitch) * sinf(yaw));
+	gluLookAt(pos.x, pos.y+1, pos.z,
+			center.x, center.y, center.z,
+			up.x, up.y, up.z);
+}
+
+void Scene::move(float forward, float right, int steps) {
+	Vector2 dir;
+	dir.x += forward*cosf(yaw);
+	dir.y += forward*sinf(yaw);
+
+	dir.x += right*cosf(yaw+M_PI_2);
+	dir.y += right*sinf(yaw+M_PI_2);
+
+	// ensure that the vector length is 1.0
+	dir /= dir.length();
+	dir *= 0.005;
+	dir *= steps;
+
+	float x = pos.x + dir.x;
+	//if(inrange(x, -2, 2))
+		pos.x = x;
+	float z = pos.z + dir.y;
+	//if(inrange(z, -2, 2))
+		pos.z = z;
+	//pos.x += dir.x;
+	//pos.z += dir.y;
+}
diff --git a/scene.h b/scene.h
new file mode 100644
index 0000000..7ae50b8
--- /dev/null
+++ b/scene.h
@@ -0,0 +1,16 @@
+#ifndef SCENE_H
+#define SCENE_H
+
+#include "vector.h"
+
+class Scene {
+	public:
+		float pitch, yaw;
+		Vector3 pos;
+		float yvel;
+
+		void lookat();
+		void move(float forward, float right, int steps);
+};
+
+#endif
diff --git a/vector.cpp b/vector.cpp
new file mode 100644
index 0000000..2da8c99
--- /dev/null
+++ b/vector.cpp
@@ -0,0 +1,146 @@
+#include "vector.h"
+
+#include <boost/format.hpp>
+
+#include <cmath>
+#include <string>
+
+Vector2::Vector2() {
+	x = y = 0;
+}
+
+Vector2::Vector2(const Vector2& v) {
+	x = v.x;
+	y = v.y;
+}
+
+Vector2::Vector2(float x, float y) {
+	this->x = x;
+	this->y = y;
+}
+
+bool Vector2::operator==(const Vector2& v) const {
+	return x == v.x && y == v.y;
+}
+
+Vector2& Vector2::operator+=(const Vector2& v) {
+	x += v.x;
+	y += v.y;
+	return *this;
+}
+
+Vector2& Vector2::operator-=(const Vector2& v) {
+	x -= v.x;
+	y -= v.y;
+	return *this;
+}
+
+Vector2 Vector2::operator-(const Vector2& v) {
+	return Vector2(*this) -= v;
+}
+
+Vector2& Vector2::operator*=(const float f) {
+	x *= f;
+	y *= f;
+	return *this;
+}
+
+Vector2& Vector2::operator/=(const float f) {
+	x /= f;
+	y /= f;
+	return *this;
+}
+
+float Vector2::length() {
+	return sqrtf(x*x + y*y);
+}
+
+std::string Vector2::str() {
+	return (boost::format("[%.2f %.2f]") % x % y).str();
+}
+
+/**
+ * Vector3
+ */
+
+Vector3::Vector3() {
+	x = y = z = 0;
+}
+
+Vector3::Vector3(const Vector3& v) : Vector2(v) {
+	z = v.z;
+}
+
+Vector3::Vector3(float x, float y, float z) : Vector2(x, y) {
+	this->z = z;
+}
+
+bool Vector3::operator==(const Vector3& v) {
+	return x == v.x && y == v.y && z == v.z;
+}
+
+Vector3& Vector3::operator+=(const Vector3& v) {
+	x += v.x;
+	y += v.y;
+	z += v.z;
+	return *this;
+}
+
+Vector3 Vector3::operator+(const Vector3& v) {
+	return Vector3(*this) += v;
+}
+
+Vector3& Vector3::operator-=(const Vector3& v) {
+	x -= v.x;
+	y -= v.y;
+	z -= v.z;
+	return *this;
+}
+
+Vector3 Vector3::operator-(const Vector3& v) {
+	return Vector3(*this) -= v;
+}
+
+Vector3& Vector3::operator*=(const float f) {
+	x *= f;
+	y *= f;
+	z *= f;
+	return *this;
+}
+
+Vector3 Vector3::operator*(const float f) {
+	return Vector3(*this) *= f;
+}
+
+Vector3& Vector3::operator/=(const float f) {
+	x /= f;
+	y /= f;
+	z /= f;
+	return *this;
+}
+
+Vector3 Vector3::operator/(const float f) {
+	return Vector3(*this) /= f;
+}
+
+Vector3 Vector3::cross(const Vector3& v) {
+	return Vector3(y*v.z - z*v.y,
+			z*v.x - x*v.z,
+			x*v.y - y*v.x);
+}
+
+float Vector3::dot(const Vector3& v) {
+	return x*v.x + y*v.y + z*v.z;
+}
+
+Vector2 Vector3::xz() {
+	return Vector2(x, z);
+}
+
+float Vector3::length() {
+	return sqrtf(x*x + y*y + z*z);
+}
+
+std::string Vector3::str() {
+	return (boost::format("[%.2f %.2f %.2f]") % x % y % z).str();
+}
diff --git a/vector.h b/vector.h
new file mode 100644
index 0000000..48deb87
--- /dev/null
+++ b/vector.h
@@ -0,0 +1,49 @@
+#ifndef VECTOR_H
+#define VECTOR_H
+
+#include <boost/shared_ptr.hpp>
+
+#include <string>
+
+class Vector2 {
+	public:
+		float x, y;
+
+		Vector2();
+		Vector2(const Vector2& v);
+		Vector2(float x, float y);
+		bool operator==(const Vector2& v) const;
+		Vector2& operator+=(const Vector2& v);
+		Vector2& operator-=(const Vector2& v);
+		Vector2 operator-(const Vector2& v);
+		Vector2& operator*=(const float f);
+		Vector2& operator/=(const float f);
+		float length();
+		std::string str();
+};
+
+class Vector3 : public Vector2 {
+	public:
+		typedef boost::shared_ptr<Vector3> p;
+		float z;
+
+		Vector3();
+		Vector3(const Vector3& v);
+		Vector3(float x, float y, float z);
+		bool operator==(const Vector3& v);
+		Vector3& operator+=(const Vector3& v);
+		Vector3 operator+(const Vector3& v);
+		Vector3& operator-=(const Vector3& v);
+		Vector3 operator-(const Vector3& v);
+		Vector3& operator*=(const float f);
+		Vector3 operator*(const float f);
+		Vector3& operator/=(const float f);
+		Vector3 operator/(const float f);
+		Vector3 cross(const Vector3& v);
+		float dot(const Vector3& v);
+		Vector2 xz();
+		float length();
+		std::string str();
+};
+
+#endif
diff --git a/video.cpp b/video.cpp
new file mode 100644
index 0000000..6ebe170
--- /dev/null
+++ b/video.cpp
@@ -0,0 +1,65 @@
+#include "video.h"
+
+#include <GL/gl.h>
+#include <GL/glu.h>
+
+SDL_Surface *video::surface = NULL;
+int video::width = 800;
+int video::height = 600;
+
+void video::init() {
+	SDL_Init(SDL_INIT_VIDEO);
+
+	surface = SDL_SetVideoMode(width, height, 32, SDL_OPENGL);
+
+	glClearColor(0, 0, 0, 0);
+	glClearDepth(1);
+	glDepthFunc(GL_LESS);
+	glEnable(GL_DEPTH_TEST);
+
+	glShadeModel(GL_SMOOTH);
+	glEnable(GL_POINT_SMOOTH);
+
+	glEnable(GL_LIGHTING);
+	glEnable(GL_LIGHT0);
+	//glEnable(GL_COLOR_MATERIAL);
+
+	const float light_ambient[4] = {.2, .2, .2, 1};
+	const float light_diffuse[4] = {1, 1, 1, 1};
+	const float light_specular[4] = {1, 1, 1, 1};
+	glLightfv(GL_LIGHT0, GL_AMBIENT, light_ambient);
+	glLightfv(GL_LIGHT0, GL_DIFFUSE, light_diffuse);
+	glLightfv(GL_LIGHT0, GL_SPECULAR, light_specular);
+
+	//glLightModeli(GL_LIGHT_MODEL_LOCAL_VIEWER, GL_TRUE);
+	//glMaterialf(GL_FRONT_AND_BACK, GL_SHININESS, 0);
+	//glColorMaterial(GL_FRONT_AND_BACK, GL_AMBIENT_AND_DIFFUSE);
+
+	glHint(GL_PERSPECTIVE_CORRECTION_HINT, GL_NICEST);
+
+	persp();
+}
+
+void video::free() {
+	SDL_Quit();
+}
+
+void video::persp() {
+	glMatrixMode(GL_PROJECTION);
+	glLoadIdentity();
+
+	gluPerspective(45, (float)width/(float)height, .1, 1000);
+
+	glMatrixMode(GL_MODELVIEW);
+	glLoadIdentity();
+}
+
+void video::ortho() {
+	glMatrixMode(GL_PROJECTION);
+	glLoadIdentity();
+
+	glOrtho(0, width, 0, height, 0, 1);
+
+	glMatrixMode(GL_MODELVIEW);
+	glLoadIdentity();
+}
diff --git a/video.h b/video.h
new file mode 100644
index 0000000..5bb694b
--- /dev/null
+++ b/video.h
@@ -0,0 +1,18 @@
+#ifndef VIDEO_H
+#define VIDEO_H
+
+#include <SDL.h>
+
+namespace video {
+	extern int width;
+	extern int height;
+
+	void init();
+	void free();
+	void persp();
+	void ortho();
+
+	extern SDL_Surface *surface;
+} /* video */
+
+#endif