From 156683c7cbcd697f09f5101fd14c01051928edb8 Mon Sep 17 00:00:00 2001
From: Jon Bergli Heier <snakebite@jvnv.net>
Date: Sat, 2 Apr 2011 20:14:35 +0200
Subject: Started work on dynamic merging and subdivision.

---
 main.cpp     | 13 +++++++++++++
 quadtree.cpp | 63 ++++++++++++++++++++++++++++++++++++++++++++++++++++--------
 quadtree.h   |  2 ++
 scene.cpp    |  4 ++++
 scene.h      |  1 +
 5 files changed, 75 insertions(+), 8 deletions(-)

diff --git a/main.cpp b/main.cpp
index f836cf3..ae1b471 100644
--- a/main.cpp
+++ b/main.cpp
@@ -78,6 +78,7 @@ int main(int argc, char **argv) {
 	/*boost::timer t;
 	double last_time = 0;*/
 	Vector3 selected;
+	Quadtree::QuadNode *node;
 	while(running) {
 		unsigned int time = SDL_GetTicks();
 		//double time = t.elapsed();
@@ -110,6 +111,16 @@ int main(int argc, char **argv) {
 								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;
@@ -200,6 +211,8 @@ int main(int argc, char **argv) {
 			move_str = (boost::format("%s %.2f,%.2f %.2fx%.2f %d") % scene.pos.str() % node->x % node->y % node->width % node->height % node->level).str();
 		}
 
+		scene.update();
+
 		scene.lookat();
 
 		glEnable(GL_LIGHTING);
diff --git a/quadtree.cpp b/quadtree.cpp
index ab08e3e..b8aee16 100644
--- a/quadtree.cpp
+++ b/quadtree.cpp
@@ -10,6 +10,8 @@
 #include <cmath>
 #include <queue>
 
+using std::min;
+
 Quadtree::Quadtree(int width, int height, float *heightmap, int levels) {
 	this->width = width;
 	this->height = height;
@@ -53,6 +55,20 @@ Quadtree::QuadNode::~QuadNode() {
 			delete children[i];
 }
 
+float Quadtree::QuadNode::distance(float px, float pz) {
+	if(px > x && px < x+width && pz > y && pz < y+height)
+		return 0;
+
+	Vector2 p(px, pz);
+
+	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();
+
+	return min(min(min(a, b), c), d);
+}
+
 void Quadtree::QuadNode::fill() {
 	elems = 3*5;
 	int size = sizeof(float)*elems;
@@ -230,6 +246,29 @@ Vector3 Quadtree::QuadNode::get_normal(int index) {
 	return N /= N.length();
 }
 
+void Quadtree::update(float x, float z) {
+	return;
+	std::queue<QuadNode*> q;
+	q.push(root);
+	while(!q.empty()) {
+		QuadNode *node = q.front();
+		q.pop();
+		float d = node->distance(x, z);
+		std::cout << d << std::endl;
+		if(d < 20 && node->vertex_array)
+			node->subdivide();
+		else if(d > 50 && !node->vertex_array)
+			node->merge();
+		if(node->vertex_array)
+			break;
+		for(int i = 0; i < 4; i++) {
+			q.push(node->children[i]);
+		}
+	}
+
+	make_vbo();
+}
+
 void Quadtree::create_nodes(int levels) {
 	if(root)
 		delete root;
@@ -362,8 +401,10 @@ void Quadtree::make_vbo() {
 			}
 			if(left && down) {
 				QuadNode *n = get_left(down);
-				v += n->get_normal(0);
-				v += n->get_normal(1);
+				if(n) {
+					v += n->get_normal(0);
+					v += n->get_normal(1);
+				}
 			}
 			v /= v.length();
 			n[24] = n[30] = v.x;
@@ -384,8 +425,10 @@ void Quadtree::make_vbo() {
 			}
 			if(down && right) {
 				QuadNode *n = get_down(right);
-				v += n->get_normal(1);
-				v += n->get_normal(2);
+				if(n) {
+					v += n->get_normal(1);
+					v += n->get_normal(2);
+				}
 			}
 			v /= v.length();
 			n[3] = n[33] = v.x;
@@ -406,8 +449,10 @@ void Quadtree::make_vbo() {
 			}
 			if(up && right) {
 				QuadNode *n = get_right(up);
-				v += n->get_normal(2);
-				v += n->get_normal(3);
+				if(n) {
+					v += n->get_normal(2);
+					v += n->get_normal(3);
+				}
 			}
 			v /= v.length();
 			n[6] = n[12] = v.x;
@@ -428,8 +473,10 @@ void Quadtree::make_vbo() {
 			}
 			if(left && up) {
 				QuadNode *n = get_left(up);
-				v += n->get_normal(0);
-				v += n->get_normal(3);
+				if(n) {
+					v += n->get_normal(0);
+					v += n->get_normal(3);
+				}
 			}
 			v /= v.length();
 			n[15] = n[21] = v.x;
diff --git a/quadtree.h b/quadtree.h
index a0e5254..53669d0 100644
--- a/quadtree.h
+++ b/quadtree.h
@@ -17,6 +17,7 @@ class Quadtree {
 			QuadNode(Quadtree *tree, QuadNode *parent, float x, float y, float width, float height, int level, bool leaf);
 			virtual ~QuadNode();
 
+			float distance(float px, float pz);
 			void fill();
 			void subdivide(bool leaf = true);
 			void merge();
@@ -36,6 +37,7 @@ class Quadtree {
 		Quadtree(int width, int height, float *heightmap, int levels);
 		virtual ~Quadtree();
 
+		void update(float x, float z);
 		void create_nodes(int levels);
 		unsigned int count_nodes();
 		void make_vbo();
diff --git a/scene.cpp b/scene.cpp
index c477345..4b96595 100644
--- a/scene.cpp
+++ b/scene.cpp
@@ -89,3 +89,7 @@ bool Scene::select(int x, int y, float& px, float& py, float& pz) {
 
 	return false;
 }
+
+void Scene::update() {
+	qt->update(pos.x, pos.z);
+}
diff --git a/scene.h b/scene.h
index 9e34e56..2429fcc 100644
--- a/scene.h
+++ b/scene.h
@@ -17,6 +17,7 @@ class Scene {
 		void lookat();
 		void move(float forward, float right, int steps);
 		bool select(int x, int y, float& px, float& py, float& pz);
+		void update();
 };
 
 #endif
-- 
cgit v1.2.3