From 3b360c21777aad02394a643b32be2ab25362bba1 Mon Sep 17 00:00:00 2001
From: Jon Bergli Heier <snakebite@jvnv.net>
Date: Fri, 1 Apr 2011 15:53:14 +0200
Subject: Some cleanup in preparation for dynamic subdivision of the terrain
 quadtree.

---
 quadtree.cpp | 92 ++++++++++++++++++++++++++++++++++++++----------------------
 1 file changed, 58 insertions(+), 34 deletions(-)

(limited to 'quadtree.cpp')

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);
-- 
cgit v1.2.3