Working dynamic generation of terrain.

6 files changed, 207 insertions, 118 deletions

diff --git a/quadtree.cpp b/quadtree.cpp
index 15759d9..2112016 100644
--- a/quadtree.cpp
+++ b/quadtree.cpp
@@ -5,6 +5,7 @@
 
 #include <cmath>
 #include <queue>
+#include <set>
 
 using std::min;
 using std::max;
@@ -48,23 +49,23 @@ float Quadtree::QuadNode::distance(float px, float pz) {
 
 void Quadtree::QuadNode::fill() {
 	vertex_array[0] = x + width / 2;
-	vertex_array[1] = chunk->tree->heights[(int)floorf((int)(chunk->x + x + width/2)*chunk->tree->height + (int)(chunk->y + y + height/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->tree->heights[(int)floorf((chunk->x + x)*chunk->tree->height+chunk->y + y)];
+	vertex_array[4] = chunk->heights[(int)floorf((x)*(chunk->height+1)+y)];
 	vertex_array[5] = y;
 
 	vertex_array[6] = x;
-	vertex_array[7] = chunk->tree->heights[(int)floorf((chunk->x + x)*chunk->tree->height + (chunk->y + y + height))];
+	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->tree->heights[(int)floorf((chunk->x + x + width)*chunk->tree->height + (chunk->y + y + height))];
+	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->tree->heights[(int)floorf((chunk->x + x + width)*chunk->tree->height + chunk->y + y)];
+	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 */
@@ -123,6 +124,17 @@ void Quadtree::QuadNode::draw_grid() {
 	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;
@@ -170,15 +182,10 @@ Quadtree::QuadChunk::QuadChunk(Quadtree *tree, float x, float y, float width, fl
 	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))];
 
-	if(width / chunk_size > 1) {
-		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 QuadChunk(tree, nx, ny, width / 2, height / 2);
-		}
-		return;
-	}
+	calc_normals();
 
 	node_count = width*height;
 	nodes = new QuadNode*[node_count];
@@ -187,12 +194,15 @@ Quadtree::QuadChunk::QuadChunk(Quadtree *tree, float x, float y, float width, fl
 			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) {
@@ -287,10 +297,10 @@ void Quadtree::QuadChunk::make_vbo() {
 
 		float *n = buffer + vertices_size + normal_chunk_size*index;
 
-		Vector3 bl = tree->normals[(int)((this->x+node->x+1)*tree->height + this->y+node->y)];
-		Vector3 br = tree->normals[(int)((this->x+node->x)*tree->height + this->y+node->y)];
-		Vector3 tr = tree->normals[(int)((this->x+node->x)*tree->height + this->y+node->y+1)];
-		Vector3 tl = tree->normals[(int)((this->x+node->x+1)*tree->height + this->y+node->y+1)];
+		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;
@@ -315,7 +325,7 @@ void Quadtree::QuadChunk::make_vbo() {
 			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)]);
+			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;
@@ -326,51 +336,113 @@ void Quadtree::QuadChunk::make_vbo() {
 }
 
 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)];
 }
 
-/* Quadtree */
-
-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);
+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);
 
-	normals = new Vector3[width*height];
 	for(int x = 0; x < width; x++) {
 		for(int y = 0; y < height; y++) {
-			calc_normal(x, 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 root;
-	delete[] heights;
-	delete[] normals;
+	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) {
-	if(x < 0 || x >= width-1 || z < 0 || z >= height-1)
+	// 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++) {
+	/*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++) {
@@ -382,7 +454,7 @@ void Quadtree::raise(float x, float z, float radius, float focus, float strength
 				/* Scale v with radius based on focus.
 				 * Not 100% accurate, but close enough.
 				 */
-				v /= radius * (focus/2);
+				/*v /= radius * (focus/2);
 
 			if(up)
 				heights[i*height + j] += v;
@@ -392,7 +464,7 @@ void Quadtree::raise(float x, float z, float radius, float focus, float strength
 	}
 
 	/* recalculate normals */
-	for(int i = x-radius-1; i < x+radius; i++) {
+	/*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++) {
@@ -403,7 +475,7 @@ void Quadtree::raise(float x, float z, float radius, float focus, float strength
 	}
 
 	/* refill nodes and remake VBOs */
-	for(int nx = x-radius-1; nx < x+radius+chunk_size; nx+=chunk_size) {
+	/*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) {
@@ -415,65 +487,45 @@ void Quadtree::raise(float x, float z, float radius, float focus, float strength
 			}
 			node->chunk->make_vbo();
 		}
-	}
+	}*/
 }
 
-Vector3 Quadtree::calc_normal(int x, int 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);
+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));
 		}
 	}
-	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);
+	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(y < height-1) {
-			Vector3 V = Vector3(x, heights[x*height + y + 1], y+1) - p;
-			N += V.cross(U);
+		if((*it)->distance(x, z) > 100) {
+			it = chunks.erase(it);
 		}
 	}
-	N /= N.length();
-	normals[x*height + y] = N;
-	return N;
-}
-
-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;
-		}
-
-		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;
-		}
+	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) {
-	return root->find(x, 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) {
diff --git a/quadtree.h b/quadtree.h
index 62ac8bb..84125d2 100644
--- a/quadtree.h
+++ b/quadtree.h
@@ -2,6 +2,9 @@
 #define QUADTREE_H
 
 #include "vector.h"
+#include "terrain.h"
+
+#include <list>
 
 class Quadtree {
 	public:
@@ -19,15 +22,17 @@ class Quadtree {
 			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;
-			QuadChunk *children[4];
 			QuadNode **nodes;
 			float x, y, width, height;
+			float *heights;
+			Vector3 *normals;
 			size_t buf_size;
 			unsigned int vbo_object;
 			unsigned int node_count;
@@ -40,21 +45,18 @@ class Quadtree {
 			float distance(float px, float pz);
 			void make_vbo();
 			QuadNode *find(float x, float y);
+			void calc_normals();
 		};
 
 		static const int chunk_size = 32;
 
-		QuadChunk *root;
-		float *heights;
-		Vector3 *normals;
-		int width, height;
-		float init_time;
-		Quadtree(int width, int height, float *heightmap);
+		std::list<QuadChunk*> chunks;
+		Terrain *terrain;
+		Quadtree();
 		virtual ~Quadtree();
 
 		void raise(float x, float z, float radius, float focus, float strength, bool up = true);
 
-		Vector3 calc_normal(int x, int y);
 		void update(float x, float z);
 		QuadNode *find(float x, float y);
 		QuadNode *get_left(QuadNode *node);
diff --git a/scene.cpp b/scene.cpp
index b67468b..8d7301d 100644
--- a/scene.cpp
+++ b/scene.cpp
@@ -15,6 +15,7 @@
 Scene::Scene() {
 	running = true;
 	grid = false;
+	normals = false;
 	terrain = true;
 	gravity = true;
 
@@ -48,10 +49,7 @@ Scene::Scene() {
 	marker_texture = load_texture("textures/cross.png");
 
 	/* init quadtree */
-	int w = 1025;
-	int h = 1025;
-	float *heightmap = Terrain::generate_heights(0, 0, w, h);
-	qt = new Quadtree(w, h, heightmap);
+	qt = new Quadtree();
 
 	/* load font */
 	font = new FTTextureFont("fonts/VeraMono.ttf");
@@ -156,6 +154,9 @@ void Scene::events() {
 					case SDLK_g:
 						grid = !grid;
 						break;
+					case SDLK_n:
+						normals = !normals;
+						break;
 					case SDLK_t:
 						terrain = !terrain;
 						break;
@@ -340,17 +341,19 @@ void Scene::render() {
 		glActiveTexture(GL_TEXTURE3);
 		glBindTexture(GL_TEXTURE_2D, marker_texture);
 
-		std::queue<Quadtree::QuadChunk*> q;
+		/*std::queue<Quadtree::QuadChunk*> q;
 		q.push(qt->root);
 		while(!q.empty()) {
 			Quadtree::QuadChunk *chunk = q.front();
-			q.pop();
-			if(!chunk->nodes) {
+			q.pop();*/
+		for(std::list<Quadtree::QuadChunk*>::iterator it = qt->chunks.begin(); it != qt->chunks.end(); it++) {
+			Quadtree::QuadChunk *chunk = *it;
+			/*if(!chunk->nodes) {
 				for(int i = 0; i < 4; i++)
 					q.push(chunk->children[i]);
 				continue;
 			} else if(!chunk->vbo_object)
-				continue;
+				continue;*/
 			chunks_rendered++;
 			glPushMatrix();
 			glTranslatef(-pos.x + chunk->x, -pos.y, -pos.z + chunk->y);
@@ -382,19 +385,34 @@ void Scene::render() {
 			glColor3f(0, 0, 0);
 		else
 			glColor3f(1, 1, 1);
-		std::queue<Quadtree::QuadChunk*> q;
+		/*std::queue<Quadtree::QuadChunk*> q;
 		q.push(qt->root);
 		while(!q.empty()) {
 			Quadtree::QuadChunk *chunk = q.front();
-			q.pop();
-			if(!chunk->nodes) {
+			q.pop();*/
+		for(std::list<Quadtree::QuadChunk*>::iterator it = qt->chunks.begin(); it != qt->chunks.end(); it++) {
+			Quadtree::QuadChunk *chunk = *it;
+			glPushMatrix();
+			glTranslatef(-pos.x, -pos.y, -pos.z);
+			/*if(!chunk->nodes) {
 				for(int i = 0; i < 4; i++)
 					q.push(chunk->children[i]);
 				continue;
-			} else if(chunk->vbo_object) {
+			} else*/ if(chunk->vbo_object) {
 				for(unsigned int i = 0; i < chunk->node_count; i++)
 					chunk->nodes[i]->draw_grid();
 			}
+			glPopMatrix();
+		}
+	}
+	if(normals) {
+		for(std::list<Quadtree::QuadChunk*>::iterator it = qt->chunks.begin(); it != qt->chunks.end(); it++) {
+			Quadtree::QuadChunk *chunk = *it;
+			glPushMatrix();
+			glTranslatef(-pos.x, -pos.y, -pos.z);
+			for(unsigned int i = 0; i < chunk->node_count; i++)
+				chunk->nodes[i]->draw_normal();
+			glPopMatrix();
 		}
 	}
 
@@ -411,8 +429,8 @@ void Scene::render() {
 	float height = font->LineHeight();
 	glColor3f(1, 1, 1);
 	glTranslatef(0, video::height-height, 0);
-	font->Render((boost::format("%dx%d  chunks: %d  gravity: %d  steps: %d")
-				% qt->width % qt->height % chunks_rendered % gravity % steps).str().c_str());
+	font->Render((boost::format("chunks: %d  gravity: %d  steps: %d")
+				% chunks_rendered % gravity % 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);
diff --git a/scene.h b/scene.h
index 59f0c79..af4f96f 100644
--- a/scene.h
+++ b/scene.h
@@ -22,6 +22,7 @@ class Scene {
 
 		bool running;
 		bool grid;
+		bool normals;
 		bool terrain;
 		bool gravity;
 		bool dialog;
diff --git a/terrain.cpp b/terrain.cpp
index a44d0d3..e0cd291 100644
--- a/terrain.cpp
+++ b/terrain.cpp
@@ -18,7 +18,7 @@ float *Terrain::generate_heights(int x, int y, int width, int height) {
 	heightmap_builder.SetDestNoiseMap(heightmap);
 
 	heightmap_builder.SetDestSize(width, height);
-	heightmap_builder.SetBounds(x / 100, (x+width) / 100, y / 100, (y+height) / 100);
+	heightmap_builder.SetBounds((double)x / 100, (double)(x+width) / 100, (double)y / 100, (double)(y+height) / 100);
 	heightmap_builder.Build();
 
 	float *heights = new float[width*height];
@@ -28,5 +28,15 @@ float *Terrain::generate_heights(int x, int y, int width, int height) {
 		}
 	}
 
+	chunk_indices.insert(std::pair<int, int>(x, y));
+
 	return heights;
 }
+
+float *Terrain::get_chunk(int x, int y, int width, int height) {
+	return generate_heights(x, y, width, height);
+}
+
+bool Terrain::has_chunk(int x, int y) {
+	return chunk_indices.find(std::pair<int, int>(x, y)) != chunk_indices.end();
+}
diff --git a/terrain.h b/terrain.h
index 88b2277..3ce4402 100644
--- a/terrain.h
+++ b/terrain.h
@@ -1,9 +1,15 @@
 #ifndef TERRAIN_H
 #define TERRAIN_H
 
+#include <set>
+
 class Terrain {
+	private:
+		std::set<std::pair<int, int> > chunk_indices;
 	public:
-		static float *generate_heights(int x, int y, int width, int height);
+		float *generate_heights(int x, int y, int width, int height);
+		float *get_chunk(int x, int y, int width, int height);
+		bool has_chunk(int x, int y);
 };
 
 #endif