summaryrefslogtreecommitdiff
path: root/quadtree.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'quadtree.cpp')
-rw-r--r--quadtree.cpp557
1 files changed, 0 insertions, 557 deletions
diff --git a/quadtree.cpp b/quadtree.cpp
deleted file mode 100644
index 2112016..0000000
--- a/quadtree.cpp
+++ /dev/null
@@ -1,557 +0,0 @@
-#include "quadtree.h"
-#include "vector.h"
-
-#include "gl.h"
-
-#include <cmath>
-#include <queue>
-#include <set>
-
-using std::min;
-using std::max;
-
-Quadtree::QuadNode::QuadNode(QuadChunk *chunk, float x, float y, float width, float height) {
- this->chunk = chunk;
- this->x = x;
- this->y = y;
- this->width = width;
- this->height = height;
-
- fill();
-}
-
-Quadtree::QuadNode::~QuadNode() {
-}
-
-float Quadtree::QuadNode::distance(float px, float pz) {
- 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);
-
- float a = (p - Vector2(x, y)).length();
- float b = (p - Vector2(x+width, y)).length();
- float c = (p - Vector2(x, y+height)).length();
- float d = (p - Vector2(x+width, y+height)).length();
-
- 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() {
- vertex_array[0] = x + width / 2;
- vertex_array[1] = chunk->heights[(int)floorf((int)(x + width/2)*(chunk->height+1) + (int)(y + height/2))];
- vertex_array[2] = y + height / 2;
-
- vertex_array[3] = x;
- vertex_array[4] = chunk->heights[(int)floorf((x)*(chunk->height+1)+y)];
- vertex_array[5] = y;
-
- vertex_array[6] = x;
- vertex_array[7] = chunk->heights[(int)floorf((x)*(chunk->height+1) + (y + height))];
- vertex_array[8] = y + height;
-
- vertex_array[9] = x + width;
- vertex_array[10] = chunk->heights[(int)floorf((x + width)*(chunk->height+1) + (y + height))];
- vertex_array[11] = y + height;
-
- vertex_array[12] = x + width;
- vertex_array[13] = chunk->heights[(int)floorf((x + width)*(chunk->height+1) + y)];
- vertex_array[14] = y;
-
- /* midpoint is average of corner heights when width == 1 */
- if(width == 1) {
- vertex_array[1] = (vertex_array[4] + vertex_array[7] + vertex_array[10] + vertex_array[13])/4;
- }
-}
-
-void Quadtree::QuadNode::draw() {
- 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() {
- 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(chunk->x + a.x, a.y, chunk->y + a.z);
- glVertex3f(chunk->x + b.x, b.y, chunk->y + b.z);
- }
- glEnd();
- glBegin(GL_LINE_LOOP);
- glVertex3f(chunk->x + vertex_array[3], vertex_array[4], chunk->y + vertex_array[5]);
- glVertex3f(chunk->x + vertex_array[6], vertex_array[7], chunk->y + vertex_array[8]);
- glVertex3f(chunk->x + vertex_array[9], vertex_array[10], chunk->y + vertex_array[11]);
- glVertex3f(chunk->x + vertex_array[12], vertex_array[13], chunk->y + vertex_array[14]);
- glEnd();
-}
-
-void Quadtree::QuadNode::draw_normal() {
- glNormal3f(0, 1, 0);
- glColor3f(1, 0, 0);
- int i = (int)(x*(chunk->height+1) + y);
- glBegin(GL_LINES);
- Vector3 N = chunk->normals[i];
- glVertex3f(chunk->x + x, chunk->heights[i], chunk->y + y);
- glVertex3f(chunk->x + x + N.x, chunk->heights[i] + N.y, chunk->y + y + N.z);
- glEnd();
-}
-
-float Quadtree::QuadNode::get_height(float px, float py) {
- px -= chunk->x;
- py -= chunk->y;
- 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;
-}
-
-/* QuadChunk */
-
-Quadtree::QuadChunk::QuadChunk(Quadtree *tree, float x, float y, float width, float height) {
- this->tree = tree;
- this->x = x;
- this->y = y;
- this->width = width;
- this->height = height;
- this->vbo_object = this->node_count = this->vertices = 0;
- this->nodes = NULL;
- heights = tree->terrain->generate_heights(x, y, width+1, height+1);
- normals = new Vector3[(int)((width+1)*(height+1))];
-
- calc_normals();
-
- node_count = width*height;
- nodes = new QuadNode*[node_count];
- for(int i = 0; i < height; i++) {
- for(int j = 0; j < width; j++) {
- nodes[j*(int)height + i] = new QuadNode(this, j, i, 1, 1);
- }
- }
- make_vbo();
-}
-
-Quadtree::QuadChunk::~QuadChunk() {
- for(unsigned int i = 0; i < node_count; i++)
- delete nodes[i];
- delete[] nodes;
- delete[] heights;
- delete[] normals;
-}
-
-float Quadtree::QuadChunk::distance(float px, float pz) {
- 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);
-
- float a = (p - Vector2(x, y)).length();
- float b = (p - Vector2(x+width, y)).length();
- float c = (p - Vector2(x, y+height)).length();
- float d = (p - Vector2(x+width, y+height)).length();
-
- 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::QuadChunk::make_vbo() {
- node_count = width*height;
- vertices = node_count*12;
- 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*node_count;
- const size_t normal_chunk_size = vertex_chunk_size;
- const size_t normals_size = normal_chunk_size*node_count;
- const size_t tex_coord_chunk_size = /*sizeof(float)*/2*12;
- const size_t tex_coords_size = tex_coord_chunk_size*node_count;
-
- buf_size = sizeof(float)*(vertices_size + normals_size + tex_coords_size);
-
- glBufferData(GL_ARRAY_BUFFER, buf_size, NULL, GL_STATIC_DRAW);
-
- float *buffer = (float*)glMapBuffer(GL_ARRAY_BUFFER, GL_WRITE_ONLY);
-
- for(unsigned int index = 0; index < node_count; index++) {
- Quadtree::QuadNode *node = nodes[index];
- float tex_coords[4][4][3][2] = {
- {{{.25, .25}, {0, 0}, {0, .5}},
- {{.25, .25}, {0, .5}, {.5, .5}},
- {{.25, .25}, {.5, .5}, {.5, 0}},
- {{.25, .25}, {.5, 0}, {0, 0}}},
-
- {{{.75, .25}, {.5, 0}, {.5, .5}},
- {{.75, .25}, {.5, .5}, {1, .5}},
- {{.75, .25}, {1, .5}, {1, 0}},
- {{.75, .25}, {1, 0}, {.5, 0}}},
-
- {{{.25, .75}, {0, .5}, {0, 1}},
- {{.25, .75}, {0, 1}, {.5, 1}},
- {{.25, .75}, {.5, 1}, {.5, .5}},
- {{.25, .75}, {.5, .5}, {0, .5}}},
-
- {{{.75, .75}, {.5, .5}, {.5, 1}},
- {{.75, .75}, {.5, 1}, {1, 1}},
- {{.75, .75}, {1, 1}, {1, .5}},
- {{.75, .75}, {1, .5}, {.5, .5}}}
- };
- for(int i = 0; i < 4; i++) {
- float *v = buffer + vertex_chunk_size*index + 3*3*i;
- for(int j = 0; j < 3; j++) {
- float *tc = buffer + vertices_size + normals_size + tex_coord_chunk_size*index + 6*i + 2*j;
- int k = (fmodf(node->x, 2) == 0 ? 1 : 0) + (fmodf(node->y, 2) == 0 ? 2 : 0);
- tc[0] = tex_coords[k][i][j][0]*node->width;
- tc[1] = tex_coords[k][i][j][1]*node->height;
- }
-
- v[0] = node->vertex_array[0];
- v[1] = node->vertex_array[1];
- v[2] = node->vertex_array[2];
-
- v[3] = node->vertex_array[i*3+3];
- v[4] = node->vertex_array[i*3+4];
- v[5] = node->vertex_array[i*3+5];
-
- v[6] = node->vertex_array[i == 3 ? 3 : (i*3+6)];
- v[7] = node->vertex_array[i == 3 ? 4 : (i*3+7)];
- v[8] = node->vertex_array[i == 3 ? 5 : (i*3+8)];
- }
-
- float *n = buffer + vertices_size + normal_chunk_size*index;
-
- Vector3 bl = normals[(int)((node->x+1)*(height+1) + node->y)];
- Vector3 br = normals[(int)((node->x)*(height+1) + node->y)];
- Vector3 tr = normals[(int)((node->x)*(height+1) + node->y+1)];
- Vector3 tl = normals[(int)((node->x+1)*(height+1) + node->y+1)];
-
- n[24] = n[30] = bl.x;
- n[25] = n[31] = bl.y;
- n[26] = n[32] = bl.z;
-
- n[3] = n[33] = br.x;
- n[4] = n[34] = br.y;
- n[5] = n[35] = br.z;
-
- n[6] = n[12] = tr.x;
- n[7] = n[13] = tr.y;
- n[8] = n[14] = tr.z;
-
- n[15] = n[21] = tl.x;
- n[16] = n[22] = tl.y;
- n[17] = n[23] = tl.z;
-
- if(node->width == 1) {
- Vector3 v(bl + br + tr + tl);
- v /= v.length();
- n[0] = n[9] = n[18] = n[27] = v.x;
- n[1] = n[10] = n[19] = n[28] = v.y;
- n[2] = n[11] = n[20] = n[29] = v.z;
- } else {
- Vector3 v(normals[(int)((node->x+node->width/2)*(height+1) + node->y+node->height/2)]);
- n[0] = n[9] = n[18] = n[27] = v.x;
- n[1] = n[10] = n[19] = n[28] = v.y;
- n[2] = n[11] = n[20] = n[29] = v.z;
- }
- }
-
- glUnmapBuffer(GL_ARRAY_BUFFER);
-}
-
-Quadtree::QuadNode* Quadtree::QuadChunk::find(float x, float y) {
- if(!(x >= this->x && x < this->x+width && y >= this->y && y < this->y+height)) {
- return NULL;
- }
- return nodes[(int)(x-this->x)*(int)height + (int)(y - this->y)];
-}
-
-void Quadtree::QuadChunk::calc_normals() {
- float *right, *left, *up, *down;
- right = left = up = down = NULL;
- if(tree->terrain->has_chunk(this->x - chunk_size, this->y))
- right = tree->terrain->get_chunk(this->x - chunk_size, this->y, width, height);
- if(tree->terrain->has_chunk(this->x + chunk_size, this->y))
- left = tree->terrain->get_chunk(this->x + chunk_size, this->y, width, height);
- if(tree->terrain->has_chunk(this->x, this->y + chunk_size))
- up = tree->terrain->get_chunk(this->x, this->y + chunk_size, width, height);
- if(tree->terrain->has_chunk(this->x, this->y - chunk_size))
- down = tree->terrain->get_chunk(this->x, this->y - chunk_size, width, height);
-
- for(int x = 0; x < width; x++) {
- for(int y = 0; y < height; y++) {
- Vector3 p(x, heights[x*(int)(height+1) + y], y);
- Vector3 N;
- Vector3 temp;
-
- // TODO: fix border bugginess
- float h;
- if(x > 0 || right) {
- if(x == 0)
- h = right[(chunk_size-1)*(int)(height) + y];
- else
- h = heights[(x-1)*(int)(height+1) + y];
- Vector3 U = Vector3(x-1, h, y) - p;
- if(y > 0 || down) {
- if(y == 0)
- h = down[x*(int)(height) + chunk_size - 1];
- else
- h = heights[x*(int)(height+1) + y - 1];
- Vector3 V = Vector3(x, h, y-1) - p;
- N += V.cross(U);
- }
- if(y < height-1 || up) {
- if(y == height-1)
- h = up[x*(int)(height)]; // y == 0
- else
- h = heights[x*(int)(height+1) + y + 1];
- Vector3 V = Vector3(x, h, y+1) - p;
- N += U.cross(V);
- }
- }
- if(x < width-1 || left) {
- if(x == width-1)
- h = left[y]; // x == 0
- else
- h = heights[(x+1)*(int)(height+1) + y];
- Vector3 U = Vector3(x+1, h, y) - p;
- if(y > 0 || down) {
- if(y == 0)
- h = down[x*(int)(height) + chunk_size - 1];
- else
- h = heights[x*(int)(height+1) + y - 1];
- Vector3 V = Vector3(x, h, y-1) - p;
- N += U.cross(V);
- }
- if(y < height-1 || up) {
- if(y == height-1)
- h = up[x*(int)(height)]; // y == 0
- else
- h = heights[x*(int)(height+1) + y + 1];
- Vector3 V = Vector3(x, h, y+1) - p;
- N += V.cross(U);
- }
- }
- N /= N.length();
- normals[x*(int)(height+1) + y] = N;
- }
- }
-
- if(right)
- delete[] right;
- if(left)
- delete[] left;
- if(up)
- delete[] up;
- if(down)
- delete[] down;
-}
-
-/* Quadtree */
-
-Quadtree::Quadtree() {
- terrain = new Terrain();
-}
-
-Quadtree::~Quadtree() {
- delete terrain;
- for(std::list<QuadChunk*>::iterator it = chunks.begin(); it != chunks.end(); it++) {
- delete *it;
- }
-}
-
-void Quadtree::raise(float x, float z, float radius, float focus, float strength, bool up) {
- // TODO: fix this
-/* if(x < 0 || x >= width-1 || z < 0 || z >= height-1)
- return;
-
- /* adjust heights */
- /*for(int i = x-radius; i < x+radius; i++) {
- if(i < 0 || i >= width-1)
- continue;
- for(int j = z-radius; j < z+radius; j++) {
- if(j < 0 || j >= height-1)
- continue;
- float v = powf((radius - min((Vector2(x, z) - Vector2(i, j)).length(), radius)) * strength, 1+focus);
-
- if(focus > 0)
- /* Scale v with radius based on focus.
- * Not 100% accurate, but close enough.
- */
- /*v /= radius * (focus/2);
-
- if(up)
- heights[i*height + j] += v;
- else
- heights[i*height + j] -= v;
- }
- }
-
- /* recalculate normals */
- /*for(int i = x-radius-1; i < x+radius; i++) {
- if(i < 0 || i >= width-1)
- continue;
- for(int j = z-radius-1; j < z+radius; j++) {
- if(j < 0 || j >= height-1)
- continue;
- calc_normal(i, j);
- }
- }
-
- /* refill nodes and remake VBOs */
- /*for(int nx = x-radius-1; nx < x+radius+chunk_size; nx+=chunk_size) {
- if(nx < 0 || nx >= width-1)
- continue;
- for(int nz = z-radius-1; nz < z+radius+chunk_size; nz+=chunk_size) {
- if(nz < 0 || nz >= height-1)
- continue;
- QuadNode *node = find(nx, nz);
- for(unsigned int i = 0; i < node->chunk->node_count; i++) {
- node->chunk->nodes[i]->fill();
- }
- node->chunk->make_vbo();
- }
- }*/
-}
-
-void Quadtree::update(float x, float z) {
- std::set<std::pair<int, int> > chunk_indices;
- int i = x - 100;
- i -= i % chunk_size;
- for(; i < x + 100; i += chunk_size) {
- int j = z - 100;
- j -= j % chunk_size;
- for(; j < z + 100; j += chunk_size) {
- float a = i - x;
- float b = j - z;
- if(sqrtf(a*a + b*b) < 100)
- chunk_indices.insert(std::pair<int, int>(i, j));
- }
- }
- for(std::list<QuadChunk*>::iterator it = chunks.begin(); it != chunks.end(); it++) {
- std::set<std::pair<int, int> >::iterator ind_it = chunk_indices.find(std::pair<int, int>((*it)->x, (*it)->y));
- if(ind_it != chunk_indices.end()) {
- chunk_indices.erase(ind_it);
- }
- if((*it)->distance(x, z) > 100) {
- it = chunks.erase(it);
- }
- }
- for(std::set<std::pair<int, int> >::iterator it = chunk_indices.begin(); it != chunk_indices.end(); it++) {
- QuadChunk *chunk = new QuadChunk(this, it->first, it->second, chunk_size, chunk_size);
- chunks.push_back(chunk);
- }
-}
-
-Quadtree::QuadNode *Quadtree::find(float x, float y) {
- for(std::list<QuadChunk*>::iterator it = chunks.begin(); it != chunks.end(); it++) {
- QuadNode *node = (*it)->find(x, y);
- if(node)
- return node;
- }
- return NULL;
-}
-
-Quadtree::QuadNode *Quadtree::get_left(Quadtree::QuadNode *node) {
- QuadNode *n = find(node->x + node->width*1.5, node->y + node->height / 2);
- if(n == node)
- return NULL;
- return n;
-}
-
-Quadtree::QuadNode *Quadtree::get_right(Quadtree::QuadNode *node) {
- QuadNode *n = find(node->x - node->width/2, node->y + node->height / 2);
- if(n == node)
- return NULL;
- return n;
-}
-
-Quadtree::QuadNode *Quadtree::get_up(Quadtree::QuadNode *node) {
- QuadNode *n = find(node->x + node->width/2, node->y + node->height*1.5);
- if(n == node)
- return NULL;
- return n;
-}
-
-Quadtree::QuadNode *Quadtree::get_down(Quadtree::QuadNode *node) {
- QuadNode *n = find(node->x + node->width/2, node->y);
- if(n == node)
- return NULL;
- return n;
-}
generated by cgit v1.2.3 (git 2.25.1) at 2024-07-01 13:12:59 +0200