Some cleanup in preparation for dynamic subdivision of the terrain quadtree.

3 files changed, 78 insertions, 53 deletions

diff --git a/main.cpp b/main.cpp
index 36ddb10..9f3bf15 100644
--- a/main.cpp
+++ b/main.cpp
@@ -198,14 +198,14 @@ int main(int argc, char **argv) {
 							grid = !grid;
 							break;
 						case SDLK_KP_PLUS:
-							delete qt;
-							qt = new Quadtree(hm->w, hm->h, heightmap, ++level);
+						case SDLK_PLUS:
+							qt->create_nodes(++level);
 							level = qt->levels;
 							break;
 						case SDLK_KP_MINUS:
+						case SDLK_MINUS:
 							if(level > 0) {
-								delete qt;
-								qt = new Quadtree(hm->w, hm->h, heightmap, --level);
+								qt->create_nodes(--level);
 							}
 							break;
 						case SDLK_SPACE:
@@ -278,21 +278,19 @@ int main(int argc, char **argv) {
 			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 * steps;
-				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();
+		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 * steps;
+			if(scene.pos.y < y) {
+				scene.pos.y = y;
+				scene.yvel = 0;
 			}
+			move_str = (boost::format("%s %.2f,%.2f %dx%d %d") % scene.pos.str() % node->x % node->y % node->width % node->height % node->level).str();
 		}
 
 		scene.lookat();
diff --git a/quadtree.cpp b/quadtree.cpp
index fc6b3cc..4b7eb52 100644
--- a/quadtree.cpp
+++ b/quadtree.cpp
@@ -15,39 +15,17 @@ 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;
-	}
+	root = NULL;
 	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();
+	create_nodes(levels);
 }
 
 Quadtree::~Quadtree() {
 	if(vbo_object)
 		glDeleteBuffers(1, &vbo_object);
 	delete root;
-	//delete[] heights;
+	delete[] heights;
 }
 
 Quadtree::QuadNode::QuadNode(Quadtree *tree, QuadNode *parent, float x, float y, float width, float height, int level, bool leaf) {
@@ -64,6 +42,19 @@ Quadtree::QuadNode::QuadNode(Quadtree *tree, QuadNode *parent, float x, float y,
 		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];
+}
+
+void Quadtree::QuadNode::fill() {
 	elems = 3*5;
 	int size = sizeof(float)*elems;
 	vertex_array = new float[size];
@@ -88,14 +79,6 @@ Quadtree::QuadNode::QuadNode(Quadtree *tree, QuadNode *parent, float x, float 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;
@@ -110,6 +93,15 @@ void Quadtree::QuadNode::subdivide(bool 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;
@@ -201,6 +193,36 @@ float Quadtree::QuadNode::get_height(float px, float py) {
 	return l1 * a.y + l2 * b.y + l3 * c.y;
 }
 
+void Quadtree::create_nodes(int levels) {
+	if(root)
+		delete root;
+
+	int l = log2f(width);
+	if(levels > l) {
+		levels = l;
+	}
+	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();
+}
+
 unsigned int Quadtree::count_nodes() {
 	std::queue<Quadtree::QuadNode*> q;
 	q.push(root);
@@ -290,9 +312,11 @@ void Quadtree::make_vbo() {
 	}
 }
 
-Quadtree::QuadNode* Quadtree::find(float x, float y) {
+Quadtree::QuadNode* Quadtree::find(float x, float y, int level) {
 	QuadNode *node = root;
 	while(!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);
diff --git a/quadtree.h b/quadtree.h
index 9a84e98..923a49f 100644
--- a/quadtree.h
+++ b/quadtree.h
@@ -15,7 +15,9 @@ class Quadtree {
 			QuadNode(Quadtree *tree, QuadNode *parent, float x, float y, float width, float height, int level, bool leaf);
 			virtual ~QuadNode();
 
+			void fill();
 			void subdivide(bool leaf = true);
+			void merge();
 			void draw();
 			void draw_grid();
 			float get_height(float px, float py);
@@ -31,9 +33,10 @@ class Quadtree {
 		Quadtree(int width, int height, float *heightmap, int levels);
 		virtual ~Quadtree();
 
+		void create_nodes(int levels);
 		unsigned int count_nodes();
 		void make_vbo();
-		QuadNode *find(float x, float y);
+		QuadNode *find(float x, float y, int leve = -1l);
 };
 
 #endif