summaryrefslogtreecommitdiff
path: root/quadtree.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'quadtree.cpp')
-rw-r--r--quadtree.cpp217
1 files changed, 187 insertions, 30 deletions
diff --git a/quadtree.cpp b/quadtree.cpp
index 581f92e..f109f63 100644
--- a/quadtree.cpp
+++ b/quadtree.cpp
@@ -7,7 +7,6 @@
#define GL_GLEXT_PROTOTYPES
#include <GL/gl.h>
-#include <iostream>
#include <cmath>
#include <queue>
@@ -77,6 +76,11 @@ void Quadtree::QuadNode::fill() {
vertex_array[12] = x + width;
vertex_array[13] = tree->heights[(int)floorf((x + width)*tree->height + 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::subdivide(bool leaf) {
@@ -193,6 +197,39 @@ float Quadtree::QuadNode::get_height(float px, float py) {
return l1 * a.y + l2 * b.y + l3 * c.y;
}
+Vector3 Quadtree::QuadNode::get_normal(int index) {
+ Vector3 a(vertex_array[0], vertex_array[1], vertex_array[2]);
+ int bi, ci;
+ switch(index) {
+ // right
+ case 0:
+ bi = 1*3;
+ ci = 2*3;
+ break;
+ // up
+ case 1:
+ bi = 2*3;
+ ci = 3*3;
+ break;
+ // left
+ case 2:
+ bi = 3*3;
+ ci = 4*3;
+ break;
+ // down
+ case 3:
+ bi = 4*3;
+ ci = 1*3;
+ break;
+ }
+ Vector3 b = Vector3(vertex_array[bi], vertex_array[bi+1], vertex_array[bi+2]);
+ Vector3 c = Vector3(vertex_array[ci], vertex_array[ci+1], vertex_array[ci+2]);
+ Vector3 U = c - a;
+ Vector3 V = b - a;
+ Vector3 N(V.cross(U));
+ return N /= N.length();
+}
+
void Quadtree::create_nodes(int levels) {
if(root)
delete root;
@@ -255,30 +292,25 @@ void Quadtree::make_vbo() {
const size_t tex_coord_chunk_size = sizeof(float)*2*12;
const size_t tex_coords_size = tex_coord_chunk_size*nodes;
- if(vertices_size + normals_size + tex_coords_size > 100*1024*1024) {
- std::cerr << ">100 MB" << std::endl;
- }
-
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();
+ Quadtree::QuadNode* node = q.front();
q.pop();
- if(!n->vertex_array) {
+ if(!node->vertex_array) {
for(int j = 0; j < 4; j++)
- q.push(n->children[j]);
+ q.push(node->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 n[3*12];
+ v[0] = node->vertex_array[0];
+ v[1] = node->vertex_array[1];
+ v[2] = node->vertex_array[2];
float tex_coords[4][3][2] = {
{{.5, .5}, {0, 0}, {0, 1}},
{{.5, .5}, {0, 1}, {1, 1}},
@@ -287,32 +319,128 @@ void Quadtree::make_vbo() {
};
for(int i = 0; i < 4; i++) {
for(int j = 0; j < 3; j++) {
- tex_coords[i][j][0] *= n->width;
- tex_coords[i][j][1] *= n->height;
+ tex_coords[i][j][0] *= node->width;
+ tex_coords[i][j][1] *= node->height;
}
- 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[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] = 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)];
+ 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)];
glBufferSubData(GL_ARRAY_BUFFER, vertex_chunk_size*index + sizeof(float)*3*3*i, sizeof(float)*3*3, v);
+ }
+
+ /* interpolate normals per vertex between nodes */
- 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;
+ QuadNode *left = get_left(node);
+ QuadNode *right = get_right(node);
+ QuadNode *up = get_up(node);
+ QuadNode *down = get_down(node);
- glBufferSubData(GL_ARRAY_BUFFER, vertices_size + normal_chunk_size*index + sizeof(float)*3*3*i, sizeof(float)*3*3, n);
+ // midpoint
+ {
+ Vector3 v(node->get_normal(0) + node->get_normal(1) + node->get_normal(2) + node->get_normal(3));
+ 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;
}
+
+ // bottom-left
+ {
+ Vector3 v(node->get_normal(3) + node->get_normal(2));
+ if(left) {
+ v += left->get_normal(0);
+ v += left->get_normal(3);
+ }
+ if(down) {
+ v += down->get_normal(1);
+ v += down->get_normal(2);
+ }
+ if(left && down) {
+ QuadNode *n = get_left(down);
+ v += n->get_normal(0);
+ v += n->get_normal(1);
+ }
+ v /= v.length();
+ n[24] = n[30] = v.x;
+ n[25] = n[31] = v.y;
+ n[26] = n[32] = v.z;
+ }
+
+ // bottom-right
+ {
+ Vector3 v(node->get_normal(0) + node->get_normal(3));
+ if(right) {
+ v += right->get_normal(2);
+ v += right->get_normal(3);
+ }
+ if(down) {
+ v += down->get_normal(1);
+ v += down->get_normal(0);
+ }
+ if(down && right) {
+ QuadNode *n = get_down(right);
+ v += n->get_normal(1);
+ v += n->get_normal(2);
+ }
+ v /= v.length();
+ n[3] = n[33] = v.x;
+ n[4] = n[34] = v.y;
+ n[5] = n[35] = v.z;
+ }
+
+ // top-right
+ {
+ Vector3 v(node->get_normal(0) + node->get_normal(1));
+ if(right) {
+ v += right->get_normal(1);
+ v += right->get_normal(2);
+ }
+ if(up) {
+ v += up->get_normal(0);
+ v += up->get_normal(3);
+ }
+ if(up && right) {
+ QuadNode *n = get_right(up);
+ v += n->get_normal(2);
+ v += n->get_normal(3);
+ }
+ v /= v.length();
+ n[6] = n[12] = v.x;
+ n[7] = n[13] = v.y;
+ n[8] = n[14] = v.z;
+ }
+
+ // top-left
+ {
+ Vector3 v(node->get_normal(1) + node->get_normal(2));
+ if(up) {
+ v += up->get_normal(3);
+ v += up->get_normal(2);
+ }
+ if(left) {
+ v += left->get_normal(0);
+ v += left->get_normal(1);
+ }
+ if(left && up) {
+ QuadNode *n = get_left(up);
+ v += n->get_normal(0);
+ v += n->get_normal(3);
+ }
+ v /= v.length();
+ n[15] = n[21] = v.x;
+ n[16] = n[22] = v.y;
+ n[17] = n[23] = v.z;
+ }
+
+ glBufferSubData(GL_ARRAY_BUFFER, vertices_size + normal_chunk_size*index, normal_chunk_size, n);
+
glBufferSubData(GL_ARRAY_BUFFER, vertices_size + normals_size + tex_coord_chunk_size*index, tex_coord_chunk_size, tex_coords);
index++;
- offset += size;
}
}
@@ -333,3 +461,32 @@ Quadtree::QuadNode* Quadtree::find(float x, float y, int level) {
return node;
}
+
+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-05-20 02:31:24 +0200