summaryrefslogtreecommitdiff
path: root/quadtree.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'quadtree.cpp')
-rw-r--r--quadtree.cpp302
1 files changed, 302 insertions, 0 deletions
diff --git a/quadtree.cpp b/quadtree.cpp
new file mode 100644
index 0000000..33011d5
--- /dev/null
+++ b/quadtree.cpp
@@ -0,0 +1,302 @@
+#include "quadtree.h"
+#include "vector.h"
+
+#include <boost/format.hpp>
+#include <boost/timer.hpp>
+
+#define GL_GLEXT_PROTOTYPES
+#include <GL/gl.h>
+
+#include <iostream>
+#include <cmath>
+#include <queue>
+
+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;
+ }
+ 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();
+}
+
+Quadtree::~Quadtree() {
+ if(vbo_object)
+ glDeleteBuffers(1, &vbo_object);
+ delete root;
+ //delete[] heights;
+}
+
+Quadtree::QuadNode::QuadNode(Quadtree *tree, QuadNode *parent, float x, float y, float width, float height, int level, bool leaf) {
+ this->tree = tree;
+ this->parent = parent;
+ this->x = x;
+ this->y = y;
+ this->width = width;
+ this->height = height;
+ this->level = level;
+ children[0] = children[1] = children[2] = children[3] = NULL;
+ if(!leaf) {
+ elems = 0;
+ vertex_array = NULL;
+ return;
+ }
+ elems = 3*5;
+ int size = sizeof(float)*elems;
+ vertex_array = new float[size];
+ vertex_array[0] = x + width / 2;
+ vertex_array[1] = tree->heights[(int)floorf((int)(x + width/2)*tree->height + (int)(y + height/2))];
+ vertex_array[2] = y + height / 2;
+
+ vertex_array[3] = x;
+ vertex_array[4] = tree->heights[(int)floorf(x*tree->height+y)];
+ vertex_array[5] = y;
+
+ vertex_array[6] = x;
+ vertex_array[7] = tree->heights[(int)floorf(x*tree->height + (y + height))];
+ vertex_array[8] = y + height;
+
+ vertex_array[9] = x + width;
+ vertex_array[10] = tree->heights[(int)floorf((x + width)*tree->height + (y + height))];
+ vertex_array[11] = y + height;
+
+ vertex_array[12] = x + width;
+ vertex_array[13] = tree->heights[(int)floorf((x + width)*tree->height + 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;
+ delete[] vertex_array;
+ vertex_array = NULL;
+ }
+
+ for(int i = 0; i < 4; i++) {
+ float nx = x + ((i & 1) ^ ((i & 2) >> 1)) * width / 2;
+ float ny = y + ((i & 2) >> 1) * height / 2;
+ children[i] = new QuadNode(tree, this, nx, ny, width / 2, height / 2, level + 1, leaf);
+ }
+}
+
+void Quadtree::QuadNode::draw() {
+ if(!vertex_array)
+ return;
+
+ float tex_coords[4][3][2] = {
+ {{.5, .5}, {0, 0}, {0, 1}},
+ {{.5, .5}, {0, 1}, {1, 1}},
+ {{.5, .5}, {1, 1}, {1, 0}},
+ {{.5, .5}, {1, 0}, {0, 0}}
+ };
+
+ glBegin(GL_TRIANGLES);
+ for(int i = 0; i < 4; i++) {
+ Vector3 a(vertex_array[0], vertex_array[1], vertex_array[2]);
+ Vector3 b(vertex_array[i*3+3], vertex_array[i*3+4], vertex_array[i*3+5]);
+ Vector3 c(vertex_array[i == 3 ? 3 : (i*3+6)], vertex_array[i == 3 ? 4 : (i*3+7)], vertex_array[i == 3 ? 5 : (i*3+8)]);
+
+ Vector3 U(c.x-a.x, c.y-a.y, c.z-a.z);
+ Vector3 V(b.x-a.x, b.y-a.y, b.z-a.z);
+ Vector3 N(V.cross(U));
+ glNormal3f(N.x, N.y, N.z);
+
+ glTexCoord2f(tex_coords[i][0][0], tex_coords[i][0][1]);
+ glVertex3f(a.x, a.y, a.z);
+
+ glTexCoord2f(tex_coords[i][1][0], tex_coords[i][1][1]);
+ glVertex3f(b.x, b.y, b.z);
+
+ glTexCoord2f(tex_coords[i][2][0], tex_coords[i][2][1]);
+ glVertex3f(c.x, c.y, c.z);
+ }
+ glEnd();
+}
+
+void Quadtree::QuadNode::draw_grid() {
+ if(!vertex_array)
+ return;
+
+ glNormal3f(0, 1, 0);
+ glBegin(GL_LINES);
+ for(int i = 0; i < 4; i++) {
+ Vector3 a(vertex_array[0], vertex_array[1], vertex_array[2]);
+ Vector3 b(vertex_array[i*3+3], vertex_array[i*3+4], vertex_array[i*3+5]);
+
+ glVertex3f(a.x, a.y, a.z);
+ glVertex3f(b.x, b.y, b.z);
+ }
+ glEnd();
+ glBegin(GL_LINE_LOOP);
+ glVertex3f(vertex_array[3], vertex_array[4], vertex_array[5]);
+ glVertex3f(vertex_array[6], vertex_array[7], vertex_array[8]);
+ glVertex3f(vertex_array[9], vertex_array[10], vertex_array[11]);
+ glVertex3f(vertex_array[12], vertex_array[13], vertex_array[14]);
+ glEnd();
+}
+
+float Quadtree::QuadNode::get_height(float px, float py) {
+ bool left;
+ bool top;
+ top = px - x >= height - (py - y);
+ left = px - x >= py - y;
+ Vector3 a(vertex_array[0], vertex_array[1], vertex_array[2]);
+ Vector3 b, c;
+ int bi, ci;
+ if(left) {
+ if(top) {
+ bi = 3*3;
+ ci = 4*3;
+ } else {
+ bi = 4*3;
+ ci = 1*3;
+ }
+ } else {
+ if(top) {
+ bi = 2*3;
+ ci = 3*3;
+ } else {
+ bi = 1*3;
+ ci = 2*3;
+ }
+ }
+ b = Vector3(vertex_array[bi], vertex_array[bi+1], vertex_array[bi+2]);
+ c = Vector3(vertex_array[ci], vertex_array[ci+1], vertex_array[ci+2]);
+ float det1 = (b.z - c.z) * (a.x - c.x) + (c.x - b.x) * (a.z - c.z);
+ float det2 = (c.z - a.z) * (b.x - c.x) + (a.x - c.x) * (b.z - c.z);
+ float l1 = ((b.z - c.z) * (px - c.x) + (c.x - b.x) * (py - c.z)) / det1;
+ float l2 = ((c.z - a.z) * (px - c.x) + (a.x - c.x) * (py - c.z)) / det2;
+ float l3 = 1 - l1 - l2;
+ return l1 * a.y + l2 * b.y + l3 * c.y;
+}
+
+unsigned int Quadtree::count_nodes() {
+ std::queue<Quadtree::QuadNode*> q;
+ q.push(root);
+ unsigned int count = 0;
+ while(!q.empty()) {
+ Quadtree::QuadNode *node = q.front();
+ q.pop();
+
+ if(!node->vertex_array) {
+ for(int i = 0; i < 4; i++)
+ q.push(node->children[i]);
+ } else {
+ count++;
+ }
+ }
+
+ return count;
+}
+
+void Quadtree::make_vbo() {
+ nodes = count_nodes();
+ if(vbo_object)
+ glDeleteBuffers(1, &vbo_object);
+ glGenBuffers(1, &vbo_object);
+ glBindBuffer(GL_ARRAY_BUFFER, vbo_object);
+ const size_t vertex_chunk_size = sizeof(float)*3*12;
+ const size_t vertices_size = vertex_chunk_size*nodes;
+ const size_t normal_chunk_size = vertex_chunk_size;
+ const size_t normals_size = normal_chunk_size*nodes;
+ const size_t tex_coord_chunk_size = sizeof(float)*2*12;
+ const size_t tex_coords_size = tex_coord_chunk_size*nodes;
+
+ glBufferData(GL_ARRAY_BUFFER, vertices_size + normals_size + tex_coords_size, NULL, GL_DYNAMIC_DRAW);
+
+ std::queue<Quadtree::QuadNode*> q;
+ q.push(root);
+ unsigned int offset = 0;
+ vertices = nodes*12;
+ unsigned int index = 0;
+ while(!q.empty()) {
+ Quadtree::QuadNode* n = q.front();
+ q.pop();
+ if(!n->vertex_array) {
+ for(int j = 0; j < 4; j++)
+ q.push(n->children[j]);
+ continue;
+ }
+ int size = 12*3*sizeof(float);
+ float v[3*12];
+ v[0] = n->vertex_array[0];
+ v[1] = n->vertex_array[1];
+ v[2] = n->vertex_array[2];
+ float tex_coords[4][3][2] = {
+ {{.5, .5}, {0, 0}, {0, 1}},
+ {{.5, .5}, {0, 1}, {1, 1}},
+ {{.5, .5}, {1, 1}, {1, 0}},
+ {{.5, .5}, {1, 0}, {0, 0}}
+ };
+ for(int i = 0; i < 4; i++) {
+ v[3] = n->vertex_array[i*3+3];
+ v[4] = n->vertex_array[i*3+4];
+ v[5] = n->vertex_array[i*3+5];
+
+ v[6] = n->vertex_array[i == 3 ? 3 : (i*3+6)];
+ v[7] = n->vertex_array[i == 3 ? 4 : (i*3+7)];
+ v[8] = n->vertex_array[i == 3 ? 5 : (i*3+8)];
+ glBufferSubData(GL_ARRAY_BUFFER, vertex_chunk_size*index + sizeof(float)*3*3*i, sizeof(float)*3*3, v);
+
+ Vector3 U(v[6]-v[0], v[7]-v[1], v[8]-v[2]);
+ Vector3 V(v[3]-v[0], v[4]-v[1], v[5]-v[2]);
+ Vector3 N(V.cross(U));
+ float n[3*3];
+ n[0] = n[3] = n[6] = N.x;
+ n[1] = n[4] = n[7] = N.y;
+ n[2] = n[5] = n[8] = N.z;
+
+ glBufferSubData(GL_ARRAY_BUFFER, vertices_size + normal_chunk_size*index + sizeof(float)*3*3*i, sizeof(float)*3*3, n);
+ }
+ glBufferSubData(GL_ARRAY_BUFFER, vertices_size + normals_size + tex_coord_chunk_size*index, tex_coord_chunk_size, tex_coords);
+ index++;
+ offset += size;
+ }
+}
+
+Quadtree::QuadNode* Quadtree::find(float x, float y) {
+ QuadNode *node = root;
+ while(!node->vertex_array) {
+ float mx = node->x + node->width / 2;
+ float my = node->y + node->height / 2;
+ int i = 2*(y > my);
+ if(i < 2 && x > mx)
+ i = 1;
+ else if(i == 2 && x < mx)
+ i = 3;
+ node = node->children[i];
+ }
+
+ return node;
+}
generated by cgit v1.2.3 (git 2.25.1) at 2024-05-20 04:08:37 +0200