Started work on dynamic merging and subdivision.

1 files changed, 55 insertions, 8 deletions

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;