From 3b360c21777aad02394a643b32be2ab25362bba1 Mon Sep 17 00:00:00 2001 From: Jon Bergli Heier Date: Fri, 1 Apr 2011 15:53:14 +0200 Subject: Some cleanup in preparation for dynamic subdivision of the terrain quadtree. --- main.cpp | 34 +++++++++++----------- quadtree.cpp | 92 ++++++++++++++++++++++++++++++++++++++---------------------- quadtree.h | 5 +++- 3 files changed, 78 insertions(+), 53 deletions(-) diff --git a/main.cpp b/main.cpp index 36ddb10..9f3bf15 100644 --- a/main.cpp +++ b/main.cpp @@ -198,14 +198,14 @@ int main(int argc, char **argv) { grid = !grid; break; case SDLK_KP_PLUS: - delete qt; - qt = new Quadtree(hm->w, hm->h, heightmap, ++level); + case SDLK_PLUS: + qt->create_nodes(++level); level = qt->levels; break; case SDLK_KP_MINUS: + case SDLK_MINUS: if(level > 0) { - delete qt; - qt = new Quadtree(hm->w, hm->h, heightmap, --level); + qt->create_nodes(--level); } break; case SDLK_SPACE: @@ -278,21 +278,19 @@ int main(int argc, char **argv) { scene.move(forward, right, steps*(keystate[SDLK_LSHIFT]?10:1)); std::string move_str; - { - Quadtree::QuadNode *node = qt->find(scene.pos.x, scene.pos.z); - if(node) { - float y = node->get_height(scene.pos.x, scene.pos.z); - if(scene.pos.y > y && !keystate[SDLK_e]) - scene.yvel -= 9.81 * steps / 85000; - if(scene.yvel < -.5) - scene.yvel = -.5; - scene.pos.y += scene.yvel * steps; - if(scene.pos.y < y) { - scene.pos.y = y; - scene.yvel = 0; - } - move_str = (boost::format("%s %.2f,%.2f %dx%d") % scene.pos.str() % node->x % node->y % node->width % node->height).str(); + Quadtree::QuadNode *node = qt->find(scene.pos.x, scene.pos.z); + if(node) { + float y = node->get_height(scene.pos.x, scene.pos.z); + if(scene.pos.y > y && !keystate[SDLK_e]) + scene.yvel -= 9.81 * steps / 85000; + if(scene.yvel < -.5) + scene.yvel = -.5; + scene.pos.y += scene.yvel * steps; + if(scene.pos.y < y) { + scene.pos.y = y; + scene.yvel = 0; } + move_str = (boost::format("%s %.2f,%.2f %dx%d %d") % scene.pos.str() % node->x % node->y % node->width % node->height % node->level).str(); } scene.lookat(); diff --git a/quadtree.cpp b/quadtree.cpp index fc6b3cc..4b7eb52 100644 --- a/quadtree.cpp +++ b/quadtree.cpp @@ -15,39 +15,17 @@ Quadtree::Quadtree(int width, int height, float *heightmap, int levels) { this->width = width; this->height = height; vbo_object = 0; - - int l = log2f(width); - if(levels > l) { - levels = l; - } + root = NULL; heights = heightmap; - this->levels = levels; - - boost::timer t; - root = new QuadNode(this, NULL, 0, 0, width, height, 1, levels == 0); - std::queue q; - if(levels > 0) - q.push(root); - while(!q.empty()) { - Quadtree::QuadNode *node = q.front(); - q.pop(); - node->subdivide(node->level == levels); - if(node->level < levels) { - for(int i = 0; i < 4; i++) - q.push(node->children[i]); - } - } - make_vbo(); - - init_time = t.elapsed(); + create_nodes(levels); } Quadtree::~Quadtree() { if(vbo_object) glDeleteBuffers(1, &vbo_object); delete root; - //delete[] heights; + delete[] heights; } Quadtree::QuadNode::QuadNode(Quadtree *tree, QuadNode *parent, float x, float y, float width, float height, int level, bool leaf) { @@ -64,6 +42,19 @@ Quadtree::QuadNode::QuadNode(Quadtree *tree, QuadNode *parent, float x, float y, vertex_array = NULL; return; } + + fill(); +} + +Quadtree::QuadNode::~QuadNode() { + if(vertex_array) + delete[] vertex_array; + for(int i = 0; i < 4; i++) + if(children[i]) + delete children[i]; +} + +void Quadtree::QuadNode::fill() { elems = 3*5; int size = sizeof(float)*elems; vertex_array = new float[size]; @@ -88,14 +79,6 @@ Quadtree::QuadNode::QuadNode(Quadtree *tree, QuadNode *parent, float x, float y, vertex_array[14] = y; } -Quadtree::QuadNode::~QuadNode() { - if(vertex_array) - delete[] vertex_array; - for(int i = 0; i < 4; i++) - if(children[i]) - delete children[i]; -} - void Quadtree::QuadNode::subdivide(bool leaf) { if(vertex_array) { elems = 0; @@ -110,6 +93,15 @@ void Quadtree::QuadNode::subdivide(bool leaf) { } } +void Quadtree::QuadNode::merge() { + for(int i = 0; i < 4; i++) { + delete children[i]; + children[i] = NULL; + } + + fill(); +} + void Quadtree::QuadNode::draw() { if(!vertex_array) return; @@ -201,6 +193,36 @@ float Quadtree::QuadNode::get_height(float px, float py) { return l1 * a.y + l2 * b.y + l3 * c.y; } +void Quadtree::create_nodes(int levels) { + if(root) + delete root; + + int l = log2f(width); + if(levels > l) { + levels = l; + } + this->levels = levels; + + boost::timer t; + root = new QuadNode(this, NULL, 0, 0, width, height, 1, levels == 0); + std::queue q; + if(levels > 0) + q.push(root); + while(!q.empty()) { + Quadtree::QuadNode *node = q.front(); + q.pop(); + node->subdivide(node->level == levels); + if(node->level < levels) { + for(int i = 0; i < 4; i++) + q.push(node->children[i]); + } + } + + make_vbo(); + + init_time = t.elapsed(); +} + unsigned int Quadtree::count_nodes() { std::queue q; q.push(root); @@ -290,9 +312,11 @@ void Quadtree::make_vbo() { } } -Quadtree::QuadNode* Quadtree::find(float x, float y) { +Quadtree::QuadNode* Quadtree::find(float x, float y, int level) { QuadNode *node = root; while(!node->vertex_array) { + if(node->level == level) + return node; float mx = node->x + node->width / 2; float my = node->y + node->height / 2; int i = 2*(y > my); diff --git a/quadtree.h b/quadtree.h index 9a84e98..923a49f 100644 --- a/quadtree.h +++ b/quadtree.h @@ -15,7 +15,9 @@ class Quadtree { QuadNode(Quadtree *tree, QuadNode *parent, float x, float y, float width, float height, int level, bool leaf); virtual ~QuadNode(); + void fill(); void subdivide(bool leaf = true); + void merge(); void draw(); void draw_grid(); float get_height(float px, float py); @@ -31,9 +33,10 @@ class Quadtree { Quadtree(int width, int height, float *heightmap, int levels); virtual ~Quadtree(); + void create_nodes(int levels); unsigned int count_nodes(); void make_vbo(); - QuadNode *find(float x, float y); + QuadNode *find(float x, float y, int leve = -1l); }; #endif -- cgit v1.2.3