Moved from dynamic LOD to chunked loading.

5 files changed, 245 insertions, 511 deletions

diff --git a/SConstruct b/SConstruct
index ee8efa8..1e7d2e3 100644
--- a/SConstruct
+++ b/SConstruct
@@ -8,7 +8,7 @@ AddOption('--release', action = 'store_true')
 AddOption('--profiling', action = 'store_true')
 
 env.Append(CPPPATH = ['.'])
-env.Append(LIBS = ['GL', 'GLU', 'boost_thread'])
+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')
diff --git a/main.cpp b/main.cpp
index eee70dd..c0871a5 100644
--- a/main.cpp
+++ b/main.cpp
@@ -102,26 +102,6 @@ int main(int argc, char **argv) {
 						case SDLK_t:
 							terrain = !terrain;
 							break;
-						case SDLK_KP_PLUS:
-						case SDLK_PLUS:
-							scene.qt->create_nodes(scene.qt->levels+1);
-							break;
-						case SDLK_KP_MINUS:
-						case SDLK_MINUS:
-							if(scene.qt->levels > 1) {
-								scene.qt->create_nodes(scene.qt->levels-1);
-							}
-							break;
-						case SDLK_KP_MULTIPLY:
-							node = scene.qt->find(scene.pos.x, scene.pos.z);
-							node->parent->merge();
-							scene.qt->make_vbo();
-							break;
-						case SDLK_KP_DIVIDE:
-							node = scene.qt->find(scene.pos.x, scene.pos.z);
-							node->subdivide();
-							scene.qt->make_vbo();
-							break;
 						case SDLK_SPACE:
 							scene.yvel = .05;
 							break;
@@ -131,9 +111,6 @@ int main(int argc, char **argv) {
 						case SDLK_u:
 							scene.update();
 							break;
-						case SDLK_c:
-							scene.qt->fix_cracks();
-							break;
 						default:
 							break;
 					}
@@ -216,7 +193,7 @@ int main(int argc, char **argv) {
 					scene.yvel = 0;
 				}
 			}
-			move_str = (boost::format("%s %.2f,%.2f %.2fx%.2f %d") % scene.pos.str() % node->x % node->y % node->width % node->height % node->level).str();
+			move_str = (boost::format("%s %.2f,%.2f %.2fx%.2f") % scene.pos.str() % node->x % node->y % node->width % node->height).str();
 
 			if(last_node != node) {
 				last_node = node;
@@ -231,21 +208,42 @@ int main(int argc, char **argv) {
 		//const float light_pos[4] = {0, 1, 0, 0};
 		//glLightfv(GL_LIGHT0, GL_POSITION, light_pos);
 
+		unsigned int chunks_rendered = 0;
 		if(terrain) {
 			program.use();
 			glBindTexture(GL_TEXTURE_2D, grass_texture);
 			glEnable(GL_TEXTURE_2D);
-			glBindBuffer(GL_ARRAY_BUFFER, scene.qt->vbo_object);
+			//for(int i = 0; i < scene.qt->chunk_count; i++) {
+			std::queue<Quadtree::QuadChunk*> q;
+			q.push(scene.qt->root);
+			while(!q.empty()) {
+				Quadtree::QuadChunk *chunk = q.front();
+				q.pop();
+				if(!chunk->nodes) {
+					for(int i = 0; i < 4; i++)
+						q.push(chunk->children[i]);
+					continue;
+				} else if(!chunk->vbo_object)
+					continue;
+				chunks_rendered++;
+				//std::cout << (boost::format("vertices: %d  nodes: %d") % scene.qt->chunks[i]->vertices % scene.qt->chunks[i]->node_count).str() << std::endl;
+			//glBindBuffer(GL_ARRAY_BUFFER, scene.qt->vbo_object);
+			//glBindBuffer(GL_ARRAY_BUFFER, scene.qt->chunks[i]->vbo_object);
+			glBindBuffer(GL_ARRAY_BUFFER, chunk->vbo_object);
 			glVertexPointer(3, GL_FLOAT, 0, NULL);
-			glNormalPointer(GL_FLOAT, 0, (GLvoid*)(scene.qt->vertices*3*sizeof(float)));
-			glTexCoordPointer(2, GL_FLOAT, 0, (GLvoid*)(scene.qt->vertices*3*sizeof(float)*2));
+			//glNormalPointer(GL_FLOAT, 0, (GLvoid*)(scene.qt->vertices*3*sizeof(float)));
+			glNormalPointer(GL_FLOAT, 0, (GLvoid*)(chunk->vertices*3*sizeof(float)));
+			//glTexCoordPointer(2, GL_FLOAT, 0, (GLvoid*)(scene.qt->vertices*3*sizeof(float)*2));
+			glTexCoordPointer(2, GL_FLOAT, 0, (GLvoid*)(chunk->vertices*3*sizeof(float)*2));
 			glEnableClientState(GL_VERTEX_ARRAY);
 			glEnableClientState(GL_NORMAL_ARRAY);
 			glEnableClientState(GL_TEXTURE_COORD_ARRAY);
-			glDrawArrays(GL_TRIANGLES, 0, scene.qt->vertices);
+			//glDrawArrays(GL_TRIANGLES, 0, scene.qt->vertices);
+			glDrawArrays(GL_TRIANGLES, 0, chunk->vertices);
 			glDisableClientState(GL_VERTEX_ARRAY);
 			glDisableClientState(GL_NORMAL_ARRAY);
 			glDisableClientState(GL_TEXTURE_COORD_ARRAY);
+			}
 			glDisable(GL_TEXTURE_2D);
 			glUseProgram(0);
 		}
@@ -254,16 +252,19 @@ int main(int argc, char **argv) {
 				glColor3f(0, 0, 0);
 			else
 				glColor3f(1, 1, 1);
-			std::queue<Quadtree::QuadNode*> q;
+			std::queue<Quadtree::QuadChunk*> q;
 			q.push(scene.qt->root);
 			while(!q.empty()) {
-				Quadtree::QuadNode *node = q.front();
+				Quadtree::QuadChunk *chunk = q.front();
 				q.pop();
-				if(node->vertex_array) {
-					grid ? node->draw_grid() : node->draw();
-				} else
+				if(!chunk->nodes) {
 					for(int i = 0; i < 4; i++)
-						q.push(node->children[i]);
+						q.push(chunk->children[i]);
+					continue;
+				} else if(chunk->vbo_object) {
+					for(unsigned int i = 0; i < chunk->node_count; i++)
+						chunk->nodes[i]->draw_grid();
+				}
 			}
 		}
 
@@ -287,8 +288,10 @@ int main(int argc, char **argv) {
 		float height = font->LineHeight();
 		glColor3f(1, 1, 1);
 		glTranslatef(0, video::height-height, 0);
-		font->Render((boost::format("%dx%d  %d levels  %d nodes  tree creation time: %f  steps: %d  update: %d")
-					% scene.qt->width % scene.qt->height % scene.qt->levels % scene.qt->nodes % scene.qt->init_time % steps % scene.qt->thread_running).str().c_str());
+		font->Render((boost::format("%dx%d  chunks: %d  steps: %d")
+					% scene.qt->width % scene.qt->height % chunks_rendered % steps).str().c_str());
+		//font->Render((boost::format("%dx%d  %d levels  %d nodes  tree creation time: %f  steps: %d  update: %d")
+		//			% scene.qt->width % scene.qt->height % scene.qt->levels % scene.qt->nodes % scene.qt->init_time % steps % scene.qt->thread_running).str().c_str());
 		//glTranslatef(0, height, 0);
 		//font->Render((boost::format("selected: %x") % selected).str().c_str());
 		glTranslatef(0, -height, 0);
@@ -301,7 +304,7 @@ int main(int argc, char **argv) {
 
 		SDL_GL_SwapBuffers();
 
-		usleep(1000);
+		SDL_Delay(1);
 	}
 
 	video::free();
diff --git a/quadtree.cpp b/quadtree.cpp
index 7fdf24f..8082ba7 100644
--- a/quadtree.cpp
+++ b/quadtree.cpp
@@ -13,49 +13,17 @@
 using std::min;
 using std::max;
 
-Quadtree::Quadtree(int width, int height, float *heightmap, int levels) {
-	this->width = width;
-	this->height = height;
-	vbo_object = 0;
-	root = NULL;
-	heights = heightmap;
-	thread_done = thread_running = false;
-	thread_buffer = NULL;
-
-	create_nodes(levels);
-}
-
-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;
+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;
-	this->level = level;
-	children[0] = children[1] = children[2] = children[3] = NULL;
-	if(!leaf) {
-		elems = 0;
-		vertex_array = NULL;
-		return;
-	}
 
 	fill();
 }
 
 Quadtree::QuadNode::~QuadNode() {
-	if(vertex_array)
-		delete[] vertex_array;
-	for(int i = 0; i < 4; i++)
-		if(children[i])
-			delete children[i];
 }
 
 float Quadtree::QuadNode::distance(float px, float pz) {
@@ -83,27 +51,24 @@ float Quadtree::QuadNode::distance(float px, float pz) {
 }
 
 void Quadtree::QuadNode::fill() {
-	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[1] = chunk->tree->heights[(int)floorf((int)(x + width/2)*chunk->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[4] = chunk->tree->heights[(int)floorf(x*chunk->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[7] = chunk->tree->heights[(int)floorf(x*chunk->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[10] = chunk->tree->heights[(int)floorf((x + width)*chunk->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[13] = chunk->tree->heights[(int)floorf((x + width)*chunk->tree->height + y)];
 	vertex_array[14] = y;
 
 	/* midpoint is average of corner heights when width == 1 */
@@ -112,85 +77,7 @@ void Quadtree::QuadNode::fill() {
 	}
 }
 
-void Quadtree::QuadNode::fix_cracks() {
-	// y = y0 + (x - x0) * (y1 - y0) / (x1 - x0)
-
-	QuadNode *down = tree->get_down(this);
-	if(down && level > down->level) {
-		vertex_array[4] = down->vertex_array[7] +
-			(vertex_array[3] - down->vertex_array[6]) *
-			(down->vertex_array[10] - down->vertex_array[7]) /
-			(down->vertex_array[9] - down->vertex_array[6]);
-		vertex_array[13] = down->vertex_array[7] +
-			(vertex_array[12] - down->vertex_array[6]) *
-			(down->vertex_array[10] - down->vertex_array[7]) /
-			(down->vertex_array[9] - down->vertex_array[6]);
-	}
-
-	QuadNode *up = tree->get_up(this);
-	if(up && level > up->level) {
-		vertex_array[7] = up->vertex_array[4] +
-			(vertex_array[6] - up->vertex_array[3]) *
-			(up->vertex_array[13] - up->vertex_array[4]) /
-			(up->vertex_array[12] - up->vertex_array[3]);
-		vertex_array[10] = up->vertex_array[4] +
-			(vertex_array[9] - up->vertex_array[3]) *
-			(up->vertex_array[13] - up->vertex_array[4]) /
-			(up->vertex_array[12] - up->vertex_array[3]);
-	}
-
-	QuadNode *left = tree->get_left(this);
-	if(left && level > left->level) {
-		vertex_array[10] = left->vertex_array[4] +
-			(vertex_array[11] - left->vertex_array[5]) *
-			(left->vertex_array[7] - left->vertex_array[4]) /
-			(left->vertex_array[8] - left->vertex_array[5]);
-		vertex_array[13] = left->vertex_array[4] +
-			(vertex_array[14] - left->vertex_array[5]) *
-			(left->vertex_array[7] - left->vertex_array[4]) /
-			(left->vertex_array[8] - left->vertex_array[5]);
-	}
-
-	QuadNode *right = tree->get_right(this);
-	if(right && level > right->level) {
-		vertex_array[4] = right->vertex_array[13] +
-			(vertex_array[5] - right->vertex_array[14]) *
-			(right->vertex_array[10] - right->vertex_array[13]) /
-			(right->vertex_array[11] - right->vertex_array[14]);
-		vertex_array[7] = right->vertex_array[13] +
-			(vertex_array[8] - right->vertex_array[14]) *
-			(right->vertex_array[10] - right->vertex_array[13]) /
-			(right->vertex_array[11] - right->vertex_array[14]);
-	}
-}
-
-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::merge() {
-	for(int i = 0; i < 4; i++) {
-		delete children[i];
-		children[i] = NULL;
-	}
-
-	fill();
-}
-
 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}},
@@ -222,9 +109,6 @@ void Quadtree::QuadNode::draw() {
 }
 
 void Quadtree::QuadNode::draw_grid() {
-	if(!vertex_array)
-		return;
-
 	glNormal3f(0, 1, 0);
 	glBegin(GL_LINES);
 	for(int i = 0; i < 4; i++) {
@@ -278,174 +162,86 @@ float Quadtree::QuadNode::get_height(float px, float py) {
 	return l1 * a.y + l2 * b.y + l3 * c.y;
 }
 
-Vector3 Quadtree::QuadNode::get_normal(int index) {
-	Vector3 a(vertex_array[0], vertex_array[1], vertex_array[2]);
-	int bi, ci;
-	switch(index) {
-		// right
-		case 0:
-			bi = 1*3;
-			ci = 2*3;
-			break;
-		// up
-		case 1:
-			bi = 2*3;
-			ci = 3*3;
-			break;
-		// left
-		case 2:
-			bi = 3*3;
-			ci = 4*3;
-			break;
-		// down
-		case 3:
-			bi = 4*3;
-			ci = 1*3;
-			break;
-	}
-	Vector3 b = Vector3(vertex_array[bi], vertex_array[bi+1], vertex_array[bi+2]);
-	Vector3 c = Vector3(vertex_array[ci], vertex_array[ci+1], vertex_array[ci+2]);
-	Vector3 U = c - a;
-	Vector3 V = b - a;
-	Vector3 N(V.cross(U));
-	return N /= N.length();
-}
+/* QuadChunk */
 
-void Quadtree::update(float x, float z) {
-	if(!node_lock.try_lock()) {
-		return;
-	}
-
-	/*
-	 * Lock won't be held until this function calls make_vbo(),
-	 * which creates the update thread.
-	 */
-	node_lock.unlock();
-
-	bool changed = false;
+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;
 
-	std::queue<QuadNode*> q;
-	q.push(root);
-	while(!q.empty()) {
-		QuadNode *node = q.front();
-		q.pop();
-		float d = node->distance(x, z);
-		int l = floorf(sqrtf(100-d+20))+1;
-		if(d < 100 && node->vertex_array && node->level < l) {
-			node->subdivide();
-			changed = true;
-		} else if(!node->vertex_array && node->level > max(l, 6)) {
-			node->merge();
-			changed = true;
-		}
-		if(node->vertex_array)
-			continue;
+	if(width / chunk_size > 1) {
+		node_count = 0;
+		nodes = NULL;
 		for(int i = 0; i < 4; i++) {
-			q.push(node->children[i]);
+			float nx = x + ((i & 1) ^((i & 2) >> 1)) * width / 2;
+			float ny = y + ((i & 2) >> 1) * height / 2;
+			children[i] = new QuadChunk(tree, nx, ny, width / 2, height / 2);
 		}
+		return;
 	}
 
-	if(changed) {
-		fix_cracks();
-		make_vbo();
-	}
-}
-
-void Quadtree::fix_cracks() {
-	std::queue<QuadNode*> q;
-	q.push(root);
-	while(!q.empty()) {
-		QuadNode *node = q.front();
-		q.pop();
-		if(node->vertex_array) {
-			if(node->vertex_array) delete[] node->vertex_array;
-			node->fill();
-			node->fix_cracks();
-		} else {
-			for(int i = 0; i < 4; i++) {
-				q.push(node->children[i]);
-			}
+	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, x+j, y+i, 1, 1);
 		}
 	}
 }
 
-void Quadtree::create_nodes(int levels) {
-	if(root)
-		delete root;
-
-	int l = log2f(width);
-	if(levels > l) {
-		levels = l;
-	}
-	this->levels = levels;
+Quadtree::QuadChunk::~QuadChunk() {
+	for(unsigned int i = 0; i < node_count; i++)
+		delete nodes[i];
+	delete[] nodes;
+}
 
-	boost::timer t;
-	root = new QuadNode(this, NULL, 0, 0, width-1, height-1, 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]);
-		}
-	}
+float Quadtree::QuadChunk::distance(float px, float pz) {
+	bool in_width = px > x && px < x+width;
+	bool in_height = pz > y && pz < y+height;
 
-	make_vbo();
+	if(in_width && in_height)
+		return 0;
 
-	init_time = t.elapsed();
-}
+	Vector2 p(px, pz);
 
-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();
+	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();
 
-		if(!node->vertex_array) {
-			for(int i = 0; i < 4; i++)
-				q.push(node->children[i]);
-		} else {
-			count++;
-		}
-	}
+	float dist = min(min(min(a, b), c), d);
 
-	return count;
-}
+	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)));
 
-Quadtree::UpdateThread::UpdateThread(Quadtree *t, float *b) {
-	tree = t;
-	buffer = b;
+	return dist;
 }
 
-void Quadtree::UpdateThread::operator()() {
-	tree->vbo_lock.lock();
-	tree->node_lock.lock();
+void Quadtree::QuadChunk::make_vbo() {
+	node_count = width*height;
+	vertices = node_count*12;
+	glGenBuffers(1, &vbo_object);
+	glBindBuffer(GL_ARRAY_BUFFER, vbo_object);
 
-	unsigned int nodes = tree->nodes;
-	const size_t vertex_chunk_size = 3*12;
-	const size_t vertices_size = vertex_chunk_size*nodes;
+	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*nodes;
-	const size_t tex_coord_chunk_size = 2*12;
-	//const size_t tex_coords_size = tex_coord_chunk_size*nodes;
+	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;
 
-	std::queue<Quadtree::QuadNode*> q;
-	q.push(tree->root);
-	unsigned int index = 0;
-	while(!q.empty()) {
-		Quadtree::QuadNode* node = q.front();
-		q.pop();
-		if(!node->vertex_array) {
-			for(int j = 0; j < 4; j++)
-				q.push(node->children[j]);
-			continue;
-		}
+	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][3][2] = {
 			{{.5, .5}, {0, 0}, {0, 1}},
 			{{.5, .5}, {0, 1}, {1, 1}},
@@ -475,196 +271,137 @@ void Quadtree::UpdateThread::operator()() {
 
 		float *n = buffer + vertices_size + normal_chunk_size*index;
 
-		/* interpolate normals per vertex between nodes */
+		Vector3 bl = tree->normals[(int)((node->x+1)*tree->height + node->y)];
+		Vector3 br = tree->normals[(int)(node->x*tree->height + node->y)];
+		Vector3 tr = tree->normals[(int)(node->x*tree->height + node->y+1)];
+		Vector3 tl = tree->normals[(int)((node->x+1)*tree->height + node->y+1)];
+
+		n[24] = n[30] = bl.x;
+		n[25] = n[31] = bl.y;
+		n[26] = n[32] = bl.z;
 
-		QuadNode *left = tree->get_left(node);
-		QuadNode *right = tree->get_right(node);
-		QuadNode *up = tree->get_up(node);
-		QuadNode *down = tree->get_down(node);
+		n[3] = n[33] = br.x;
+		n[4] = n[34] = br.y;
+		n[5] = n[35] = br.z;
 
-		// midpoint
-		{
-			Vector3 v(node->get_normal(0) + node->get_normal(1) + node->get_normal(2) + node->get_normal(3));
+		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(tree->normals[(int)((node->x+node->width/2)*tree->height + 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;
 		}
+	}
 
-		// bottom-left
-		{
-			Vector3 v(node->get_normal(3) + node->get_normal(2));
-			if(left) {
-				v += left->get_normal(0);
-				v += left->get_normal(3);
-			}
-			if(down) {
-				v += down->get_normal(1);
-				v += down->get_normal(2);
-			}
-			if(left && down) {
-				QuadNode *temp = tree->get_left(down);
-				if(temp) {
-					v += temp->get_normal(0);
-					v += temp->get_normal(1);
-				}
-			}
-			v /= v.length();
-			n[24] = n[30] = v.x;
-			n[25] = n[31] = v.y;
-			n[26] = n[32] = v.z;
-		}
+	glUnmapBuffer(GL_ARRAY_BUFFER);
+}
 
-		// bottom-right
-		{
-			Vector3 v(node->get_normal(0) + node->get_normal(3));
-			if(right) {
-				v += right->get_normal(2);
-				v += right->get_normal(3);
-			}
-			if(down) {
-				v += down->get_normal(1);
-				v += down->get_normal(0);
-			}
-			if(down && right) {
-				QuadNode *temp = tree->get_down(right);
-				if(temp) {
-					v += temp->get_normal(1);
-					v += temp->get_normal(2);
-				}
-			}
-			v /= v.length();
-			n[3] = n[33] = v.x;
-			n[4] = n[34] = v.y;
-			n[5] = n[35] = v.z;
-		}
+Quadtree::QuadNode* Quadtree::QuadChunk::find(float x, float y) {
+	if(!nodes) {
+		float mx = this->x + width / 2;
+		float my = this->y + height / 2;
+		int i = 2*(y > my);
+		if(i < 2 && x > mx)
+			i = 1;
+		else if(i == 2 && x < mx)
+			i = 3;
+		return children[i]->find(x, 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)];
+}
 
-		// top-right
-		{
-			Vector3 v(node->get_normal(0) + node->get_normal(1));
-			if(right) {
-				v += right->get_normal(1);
-				v += right->get_normal(2);
-			}
-			if(up) {
-				v += up->get_normal(0);
-				v += up->get_normal(3);
-			}
-			if(up && right) {
-				QuadNode *temp = tree->get_right(up);
-				if(temp) {
-					v += temp->get_normal(2);
-					v += temp->get_normal(3);
-				}
-			}
-			v /= v.length();
-			n[6] = n[12] = v.x;
-			n[7] = n[13] = v.y;
-			n[8] = n[14] = v.z;
-		}
+/* Quadtree */
 
-		// top-left
-		{
-			Vector3 v(node->get_normal(1) + node->get_normal(2));
-			if(up) {
-				v += up->get_normal(3);
-				v += up->get_normal(2);
-			}
-			if(left) {
-				v += left->get_normal(0);
-				v += left->get_normal(1);
+Quadtree::Quadtree(int width, int height, float *heightmap) {
+	this->width = width;
+	this->height = height;
+	heights = heightmap;
+
+	root = new QuadChunk(this, 0, 0, width-1, height-1);
+
+	boost::timer t;
+	normals = new Vector3[width*height];
+	for(int x = 0; x < width; x++) {
+		for(int y = 0; y < height; y++) {
+			Vector3 p(x, heights[x*height + y], y);
+			Vector3 N;
+
+			if(x > 0) {
+				Vector3 U = Vector3(x-1, heights[(x-1)*height + y], y) - p;
+				if(y > 0) {
+					Vector3 V = Vector3(x, heights[x*height + y - 1], y-1) - p;
+					N += V.cross(U);
+				}
+				if(y < height-1) {
+					Vector3 V = Vector3(x, heights[x*height + y + 1], y+1) - p;
+					N += U.cross(V);
+				}
 			}
-			if(left && up) {
-				QuadNode *temp = tree->get_left(up);
-				if(temp) {
-					v += temp->get_normal(0);
-					v += temp->get_normal(3);
+			if(x < width-1) {
+				Vector3 U = Vector3(x+1, heights[(x+1)*height + y], y) - p;
+				if(y > 0) {
+					Vector3 V = Vector3(x, heights[x*height + y - 1], y-1) - p;
+					N += U.cross(V);
+				}
+				if(y < height-1) {
+					Vector3 V = Vector3(x, heights[x*height + y + 1], y+1) - p;
+					N += V.cross(U);
 				}
 			}
-			v /= v.length();
-			n[15] = n[21] = v.x;
-			n[16] = n[22] = v.y;
-			n[17] = n[23] = v.z;
+			if(N.y < 0)
+				std::cout << N.str() << std::endl;
+			normals[x*height + y] = N / N.length();
 		}
-
-		index++;
 	}
-
-	tree->thread_done = true;
-	tree->thread_running = false;
-
-	tree->node_lock.unlock();
-	tree->vbo_lock.unlock();
+	std::cout << "normal time: " << t.elapsed() << std::endl;
 }
 
-void Quadtree::make_vbo() {
-	if(thread_running || thread_done || thread_buffer)
-		return;
-
-	nodes = count_nodes();
-	glGenBuffers(1, &temp_vbo);
-	glBindBuffer(GL_ARRAY_BUFFER, temp_vbo);
-
-	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;
-
-	buf_size = sizeof(float)*(vertices_size + normals_size + tex_coords_size);
-
-	glBufferData(GL_ARRAY_BUFFER, sizeof(float)*(vertices_size + normals_size + tex_coords_size), NULL, GL_STATIC_DRAW);
-
-	thread_buffer = (float*)glMapBuffer(GL_ARRAY_BUFFER, GL_WRITE_ONLY);
-
-	thread_running = true;
-	boost::thread(UpdateThread(this, thread_buffer));
+Quadtree::~Quadtree() {
+	delete root;
+	delete[] heights;
+	delete[] normals;
 }
 
-void Quadtree::update_vbo() {
-	if(!vbo_lock.try_lock()) {
-		return;
-	}
+void Quadtree::update(float x, float z) {
+	std::queue<QuadChunk*> q;
+	q.push(root);
+	while(!q.empty()) {
+		QuadChunk *chunk = q.front();
+		q.pop();
+		if(!chunk->nodes) {
+			for(int i = 0; i < 4; i++)
+				q.push(chunk->children[i]);
+			continue;
+		}
 
-	if(!thread_done || !thread_buffer || thread_running) {
-		vbo_lock.unlock();
-		return;
+		float d = chunk->distance(x, z);
+		if(d < 100 && !chunk->vbo_object) {
+			chunk->make_vbo();
+		} else if(d > 100 && chunk->vbo_object) {
+			glDeleteBuffers(1, &chunk->vbo_object);
+			chunk->vbo_object = 0;
+			chunk->vertices = 0;
+		}
 	}
-
-	thread_done = false;
-
-	glBindBuffer(GL_ARRAY_BUFFER, temp_vbo);
-	glBufferData(GL_ARRAY_BUFFER, buf_size, thread_buffer, GL_STATIC_DRAW);
-
-	thread_buffer = NULL;
-
-	vertices = nodes*12;
-
-	if(vbo_object)
-		glDeleteBuffers(1, &vbo_object);
-	vbo_object = temp_vbo;
-	temp_vbo = 0;
-
-	vbo_lock.unlock();
 }
 
-Quadtree::QuadNode* Quadtree::find(float x, float y, int level) {
-	QuadNode *node = root;
-	while(node && !node->vertex_array) {
-		if(node->level == level)
-			return node;
-		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;
+Quadtree::QuadNode *Quadtree::find(float x, float y) {
+	return root->find(x, y);
 }
 
 Quadtree::QuadNode *Quadtree::get_left(Quadtree::QuadNode *node) {
diff --git a/quadtree.h b/quadtree.h
index b927dee..d6d1e8e 100644
--- a/quadtree.h
+++ b/quadtree.h
@@ -3,64 +3,59 @@
 
 #include "vector.h"
 
-#include <boost/thread.hpp>
+#include <list>
 
 class Quadtree {
 	public:
-
-		struct UpdateThread {
-			Quadtree *tree;
-			float *buffer;
-			UpdateThread(Quadtree *t, float *b);
-			void operator()();
-		};
+		struct QuadChunk;
 
 		struct QuadNode {
-			Quadtree *tree;
-			QuadNode *parent;
-			QuadNode *children[4];
-			int elems;
+			QuadChunk *chunk;
 			float x, y, width, height;
-			int level;
-			float *vertex_array;
+			float vertex_array[15];
 
-			QuadNode(Quadtree *tree, QuadNode *parent, float x, float y, float width, float height, int level, bool leaf);
+			QuadNode(QuadChunk *chunk, float x, float y, float width, float height);
 			virtual ~QuadNode();
 
 			float distance(float px, float pz);
 			void fill();
-			void fix_cracks();
-			void subdivide(bool leaf = true);
-			void merge();
 			void draw();
 			void draw_grid();
 			float get_height(float px, float py);
 			Vector3 get_normal(int index);
 		};
 
+		struct QuadChunk {
+			Quadtree *tree;
+			QuadChunk *children[4];
+			QuadNode **nodes;
+			float x, y, width, height;
+			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);
+		};
+
+		static const int chunk_size = 32;
+
+		QuadChunk *root;
 		float *heights;
-		float *thread_buffer;
-		size_t buf_size;
-		bool thread_done, thread_running;
-		boost::mutex vbo_lock;
-		boost::mutex node_lock;
-		int width, height, levels;
+		Vector3 *normals;
+		int width, height;
 		float init_time;
-		QuadNode *root;
-		unsigned int temp_vbo;
-		unsigned int vbo_object;
-		unsigned int nodes;
-		unsigned int vertices;
-		Quadtree(int width, int height, float *heightmap, int levels);
+		Quadtree(int width, int height, float *heightmap);
 		virtual ~Quadtree();
 
 		void update(float x, float z);
-		void fix_cracks();
-		void create_nodes(int levels);
-		unsigned int count_nodes();
-		void make_vbo();
-		void update_vbo();
-		QuadNode *find(float x, float y, int level = -1);
+		QuadNode *find(float x, float y);
 		QuadNode *get_left(QuadNode *node);
 		QuadNode *get_right(QuadNode *node);
 		QuadNode *get_up(QuadNode *node);
diff --git a/scene.cpp b/scene.cpp
index 5bbd1b2..9e606f1 100644
--- a/scene.cpp
+++ b/scene.cpp
@@ -19,7 +19,7 @@ Scene::Scene() {
 	int w = hm->w;
 	int h = hm->h;
 	SDL_FreeSurface(hm);
-	qt = new Quadtree(w, h, heightmap, 3);
+	qt = new Quadtree(w, h, heightmap);
 }
 
 Scene::~Scene() {
@@ -92,5 +92,4 @@ bool Scene::select(int x, int y, float& px, float& py, float& pz) {
 
 void Scene::update() {
 	qt->update(pos.x, pos.z);
-	qt->update_vbo();
 }