From 61fe986e9ad6d1f26275e2ffd72cae0c2542256c Mon Sep 17 00:00:00 2001 From: Jon Bergli Heier Date: Sun, 3 Apr 2011 15:09:13 +0200 Subject: Implemented very ineffective dynamic terrain LOD. --- main.cpp | 42 ++++++++++++++++++----- quadtree.cpp | 106 ++++++++++++++++++++++++++++++++++++++++++++++++++++++----- quadtree.h | 2 ++ video.cpp | 4 +-- 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 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 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 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 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}; -- cgit v1.2.3