Implemented very ineffective dynamic terrain LOD.

4 files changed, 135 insertions, 19 deletions

diff --git a/main.cpp b/main.cpp
index ae1b471..5f089e8 100644
--- a/main.cpp
+++ b/main.cpp
@@ -72,13 +72,17 @@ int main(int argc, char **argv) {
 	SDL_Event event;
 	bool running = true;
 	bool grid = false;
+	bool terrain = true;
 	bool gravity = true;
 	SDL_WarpMouse(video::width/2, video::height/2);
 	unsigned int last_time = SDL_GetTicks();
+	unsigned int last_update = SDL_GetTicks();
 	/*boost::timer t;
 	double last_time = 0;*/
 	Vector3 selected;
 	Quadtree::QuadNode *node;
+	Quadtree::QuadNode *last_node = NULL;
+	scene.update();
 	while(running) {
 		unsigned int time = SDL_GetTicks();
 		//double time = t.elapsed();
@@ -86,6 +90,10 @@ int main(int argc, char **argv) {
 		unsigned int steps = time - last_time + 1;
 		//double steps = (time - last_time) * 1000;
 		last_time = time;
+		/*if(time - last_update > 5000) {
+			scene.update();
+			last_update = time;
+		}*/
 		bool do_select = 0;
 		int sx, sy;
 		while(SDL_PollEvent(&event)) {
@@ -101,6 +109,9 @@ int main(int argc, char **argv) {
 						case SDLK_g:
 							grid = !grid;
 							break;
+						case SDLK_t:
+							terrain = !terrain;
+							break;
 						case SDLK_KP_PLUS:
 						case SDLK_PLUS:
 							scene.qt->create_nodes(scene.qt->levels+1);
@@ -127,6 +138,12 @@ int main(int argc, char **argv) {
 						case SDLK_h:
 							gravity = !gravity;
 							break;
+						case SDLK_u:
+							scene.update();
+							break;
+						case SDLK_c:
+							scene.qt->fix_cracks();
+							break;
 						default:
 							break;
 					}
@@ -190,8 +207,9 @@ int main(int argc, char **argv) {
 			scene.pos.y -= 0.002*steps*(keystate[SDLK_LSHIFT]?10:1);
 		if(keystate[SDLK_e])
 			scene.pos.y += 0.002*steps*(keystate[SDLK_LSHIFT]?10:1);
-		if(moved && (forward || right))
+		if(moved && (forward || right)) {
 			scene.move(forward, right, steps*(keystate[SDLK_LSHIFT]?10:1));
+		}
 
 		std::string move_str;
 		Quadtree::QuadNode *node = scene.qt->find(scene.pos.x, scene.pos.z);
@@ -209,18 +227,21 @@ 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();
+			if(last_node != node) {
+				last_node = node;
+				scene.update();
+			}
+		}
 
 		scene.lookat();
 
-		glEnable(GL_LIGHTING);
+		//glEnable(GL_LIGHTING);
 		const float light_pos[4] = {50, 100, 50, 1};
 		//const float light_pos[4] = {0, 1, 0, 0};
-		glLightfv(GL_LIGHT0, GL_POSITION, light_pos);
+		//glLightfv(GL_LIGHT0, GL_POSITION, light_pos);
 
-		if(!grid) {
+		if(terrain) {
 			program.use();
 			glBindTexture(GL_TEXTURE_2D, grass_texture);
 			glEnable(GL_TEXTURE_2D);
@@ -237,7 +258,12 @@ int main(int argc, char **argv) {
 			glDisableClientState(GL_TEXTURE_COORD_ARRAY);
 			glDisable(GL_TEXTURE_2D);
 			glUseProgram(0);
-		} else {
+		}
+		if(grid) {
+			if(terrain)
+				glColor3f(0, 0, 0);
+			else
+				glColor3f(1, 1, 1);
 			std::queue<Quadtree::QuadNode*> q;
 			q.push(scene.qt->root);
 			while(!q.empty()) {
@@ -251,7 +277,7 @@ int main(int argc, char **argv) {
 			}
 		}
 
-		glDisable(GL_LIGHTING);
+		//glDisable(GL_LIGHTING);
 
 		float px, py, pz;
 		if(do_select && scene.select(sx, sy, px, py, pz)) {
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;
diff --git a/quadtree.h b/quadtree.h
index 53669d0..951a98e 100644
--- a/quadtree.h
+++ b/quadtree.h
@@ -19,6 +19,7 @@ class Quadtree {
 
 			float distance(float px, float pz);
 			void fill();
+			void fix_cracks();
 			void subdivide(bool leaf = true);
 			void merge();
 			void draw();
@@ -38,6 +39,7 @@ class Quadtree {
 		virtual ~Quadtree();
 
 		void update(float x, float z);
+		void fix_cracks();
 		void create_nodes(int levels);
 		unsigned int count_nodes();
 		void make_vbo();
diff --git a/video.cpp b/video.cpp
index 6ebe170..565a930 100644
--- a/video.cpp
+++ b/video.cpp
@@ -20,8 +20,8 @@ void video::init() {
 	glShadeModel(GL_SMOOTH);
 	glEnable(GL_POINT_SMOOTH);
 
-	glEnable(GL_LIGHTING);
-	glEnable(GL_LIGHT0);
+	//glEnable(GL_LIGHTING);
+	//glEnable(GL_LIGHT0);
 	//glEnable(GL_COLOR_MATERIAL);
 
 	const float light_ambient[4] = {.2, .2, .2, 1};