From 61fe986e9ad6d1f26275e2ffd72cae0c2542256c Mon Sep 17 00:00:00 2001
From: Jon Bergli Heier <snakebite@jvnv.net>
Date: Sun, 3 Apr 2011 15:09:13 +0200
Subject: Implemented very ineffective dynamic terrain LOD.

---
 quadtree.cpp | 106 ++++++++++++++++++++++++++++++++++++++++++++++++++++++-----
 1 file changed, 97 insertions(+), 9 deletions(-)

(limited to 'quadtree.cpp')

diff --git a/quadtree.cpp b/quadtree.cpp
index b8aee16..782837c 100644
--- a/quadtree.cpp
+++ b/quadtree.cpp
@@ -11,6 +11,7 @@
 #include <queue>
 
 using std::min;
+using std::max;
 
 Quadtree::Quadtree(int width, int height, float *heightmap, int levels) {
 	this->width = width;
@@ -56,7 +57,10 @@ Quadtree::QuadNode::~QuadNode() {
 }
 
 float Quadtree::QuadNode::distance(float px, float pz) {
-	if(px > x && px < x+width && pz > y && pz < y+height)
+	bool in_width = px > x && px < x+width;
+	bool in_height = pz > y && pz < y+height;
+
+	if(in_width && in_height)
 		return 0;
 
 	Vector2 p(px, pz);
@@ -66,7 +70,14 @@ float Quadtree::QuadNode::distance(float px, float pz) {
 	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);
+	float dist = min(min(min(a, b), c), d);
+
+	if(in_width)
+		dist = min(dist, (float)min(abs(y - pz), abs(y+height - pz)));
+	if(in_height)
+		dist = min(dist, (float)min(abs(x - px), abs(x+width - px)));
+
+	return dist;
 }
 
 void Quadtree::QuadNode::fill() {
@@ -99,6 +110,58 @@ void Quadtree::QuadNode::fill() {
 	}
 }
 
+void Quadtree::QuadNode::fix_cracks() {
+	// y = y0 + (x - x0) * (y1 - y0) / (x1 - x0)
+
+	QuadNode *down = tree->get_down(this);
+	if(down && level > down->level) {
+		vertex_array[4] = down->vertex_array[7] +
+			(vertex_array[3] - down->vertex_array[6]) *
+			(down->vertex_array[10] - down->vertex_array[7]) /
+			(down->vertex_array[9] - down->vertex_array[6]);
+		vertex_array[13] = down->vertex_array[7] +
+			(vertex_array[12] - down->vertex_array[6]) *
+			(down->vertex_array[10] - down->vertex_array[7]) /
+			(down->vertex_array[9] - down->vertex_array[6]);
+	}
+
+	QuadNode *up = tree->get_up(this);
+	if(up && level > up->level) {
+		vertex_array[7] = up->vertex_array[4] +
+			(vertex_array[6] - up->vertex_array[3]) *
+			(up->vertex_array[13] - up->vertex_array[4]) /
+			(up->vertex_array[12] - up->vertex_array[3]);
+		vertex_array[10] = up->vertex_array[4] +
+			(vertex_array[9] - up->vertex_array[3]) *
+			(up->vertex_array[13] - up->vertex_array[4]) /
+			(up->vertex_array[12] - up->vertex_array[3]);
+	}
+
+	QuadNode *left = tree->get_left(this);
+	if(left && level > left->level) {
+		vertex_array[10] = left->vertex_array[4] +
+			(vertex_array[11] - left->vertex_array[5]) *
+			(left->vertex_array[7] - left->vertex_array[4]) /
+			(left->vertex_array[8] - left->vertex_array[5]);
+		vertex_array[13] = left->vertex_array[4] +
+			(vertex_array[14] - left->vertex_array[5]) *
+			(left->vertex_array[7] - left->vertex_array[4]) /
+			(left->vertex_array[8] - left->vertex_array[5]);
+	}
+
+	QuadNode *right = tree->get_right(this);
+	if(right && level > right->level) {
+		vertex_array[4] = right->vertex_array[13] +
+			(vertex_array[5] - right->vertex_array[14]) *
+			(right->vertex_array[10] - right->vertex_array[13]) /
+			(right->vertex_array[11] - right->vertex_array[14]);
+		vertex_array[7] = right->vertex_array[13] +
+			(vertex_array[8] - right->vertex_array[14]) *
+			(right->vertex_array[10] - right->vertex_array[13]) /
+			(right->vertex_array[11] - right->vertex_array[14]);
+	}
+}
+
 void Quadtree::QuadNode::subdivide(bool leaf) {
 	if(vertex_array) {
 		elems = 0;
@@ -247,26 +310,51 @@ Vector3 Quadtree::QuadNode::get_normal(int index) {
 }
 
 void Quadtree::update(float x, float z) {
-	return;
+	bool changed = false;
+
 	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)
+		int l = floorf(sqrtf(100-d+20))+1;
+		if(d < 100 && node->vertex_array && node->level < l) {
 			node->subdivide();
-		else if(d > 50 && !node->vertex_array)
+			changed = true;
+		} else if(!node->vertex_array && node->level > max(l, 6)) {
 			node->merge();
+			changed = true;
+		}
 		if(node->vertex_array)
-			break;
+			continue;
 		for(int i = 0; i < 4; i++) {
 			q.push(node->children[i]);
 		}
 	}
 
-	make_vbo();
+	if(changed) {
+		fix_cracks();
+		make_vbo();
+	}
+}
+
+void Quadtree::fix_cracks() {
+	std::queue<QuadNode*> q;
+	q.push(root);
+	while(!q.empty()) {
+		QuadNode *node = q.front();
+		q.pop();
+		if(node->vertex_array) {
+			if(node->vertex_array) delete[] node->vertex_array;
+			node->fill();
+			node->fix_cracks();
+		} else {
+			for(int i = 0; i < 4; i++) {
+				q.push(node->children[i]);
+			}
+		}
+	}
 }
 
 void Quadtree::create_nodes(int levels) {
@@ -493,7 +581,7 @@ void Quadtree::make_vbo() {
 
 Quadtree::QuadNode* Quadtree::find(float x, float y, int level) {
 	QuadNode *node = root;
-	while(!node->vertex_array) {
+	while(node && !node->vertex_array) {
 		if(node->level == level)
 			return node;
 		float mx = node->x + node->width / 2;
-- 
cgit v1.2.3