summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--main.cpp34
-rw-r--r--quadtree.cpp92
-rw-r--r--quadtree.h5
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<Quadtree::QuadNode*> 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<Quadtree::QuadNode*> 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<Quadtree::QuadNode*> 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
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-21 17:15:01 +0100