summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--quadtree.cpp240
-rw-r--r--quadtree.h18
-rw-r--r--scene.cpp46
-rw-r--r--scene.h1
-rw-r--r--terrain.cpp12
-rw-r--r--terrain.h8
6 files changed, 207 insertions, 118 deletions
diff --git a/quadtree.cpp b/quadtree.cpp
index 15759d9..2112016 100644
--- a/quadtree.cpp
+++ b/quadtree.cpp
@@ -5,6 +5,7 @@
#include <cmath>
#include <queue>
+#include <set>
using std::min;
using std::max;
@@ -48,23 +49,23 @@ float Quadtree::QuadNode::distance(float px, float pz) {
void Quadtree::QuadNode::fill() {
vertex_array[0] = x + width / 2;
- vertex_array[1] = chunk->tree->heights[(int)floorf((int)(chunk->x + x + width/2)*chunk->tree->height + (int)(chunk->y + y + height/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->tree->heights[(int)floorf((chunk->x + x)*chunk->tree->height+chunk->y + y)];
+ vertex_array[4] = chunk->heights[(int)floorf((x)*(chunk->height+1)+y)];
vertex_array[5] = y;
vertex_array[6] = x;
- vertex_array[7] = chunk->tree->heights[(int)floorf((chunk->x + x)*chunk->tree->height + (chunk->y + y + height))];
+ 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->tree->heights[(int)floorf((chunk->x + x + width)*chunk->tree->height + (chunk->y + y + height))];
+ 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->tree->heights[(int)floorf((chunk->x + x + width)*chunk->tree->height + chunk->y + y)];
+ 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 */
@@ -123,6 +124,17 @@ void Quadtree::QuadNode::draw_grid() {
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;
@@ -170,15 +182,10 @@ Quadtree::QuadChunk::QuadChunk(Quadtree *tree, float x, float y, float width, fl
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))];
- if(width / chunk_size > 1) {
- 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 QuadChunk(tree, nx, ny, width / 2, height / 2);
- }
- return;
- }
+ calc_normals();
node_count = width*height;
nodes = new QuadNode*[node_count];
@@ -187,12 +194,15 @@ Quadtree::QuadChunk::QuadChunk(Quadtree *tree, float x, float y, float width, fl
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) {
@@ -287,10 +297,10 @@ void Quadtree::QuadChunk::make_vbo() {
float *n = buffer + vertices_size + normal_chunk_size*index;
- Vector3 bl = tree->normals[(int)((this->x+node->x+1)*tree->height + this->y+node->y)];
- Vector3 br = tree->normals[(int)((this->x+node->x)*tree->height + this->y+node->y)];
- Vector3 tr = tree->normals[(int)((this->x+node->x)*tree->height + this->y+node->y+1)];
- Vector3 tl = tree->normals[(int)((this->x+node->x+1)*tree->height + this->y+node->y+1)];
+ 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;
@@ -315,7 +325,7 @@ void Quadtree::QuadChunk::make_vbo() {
n[1] = n[10] = n[19] = n[28] = v.y;
n[2] = n[11] = n[20] = n[29] = v.z;
} else {
- Vector3 v(tree->normals[(int)((node->x+node->width/2)*tree->height + node->y+node->height/2)]);
+ 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;
@@ -326,51 +336,113 @@ void Quadtree::QuadChunk::make_vbo() {
}
Quadtree::QuadNode* Quadtree::QuadChunk::find(float x, float y) {
- if(!nodes) {
- float mx = this->x + width / 2;
- float my = this->y + height / 2;
- int i = 2*(y >= my);
- if(i < 2 && x >= mx)
- i = 1;
- else if(i == 2 && x < mx)
- i = 3;
- return children[i]->find(x, 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)];
}
-/* Quadtree */
-
-Quadtree::Quadtree(int width, int height, float *heightmap) {
- this->width = width;
- this->height = height;
- heights = heightmap;
-
- root = new QuadChunk(this, 0, 0, width-1, height-1);
+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);
- normals = new Vector3[width*height];
for(int x = 0; x < width; x++) {
for(int y = 0; y < height; y++) {
- calc_normal(x, 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 root;
- delete[] heights;
- delete[] normals;
+ 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) {
- if(x < 0 || x >= width-1 || z < 0 || z >= height-1)
+ // 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++) {
+ /*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++) {
@@ -382,7 +454,7 @@ void Quadtree::raise(float x, float z, float radius, float focus, float strength
/* Scale v with radius based on focus.
* Not 100% accurate, but close enough.
*/
- v /= radius * (focus/2);
+ /*v /= radius * (focus/2);
if(up)
heights[i*height + j] += v;
@@ -392,7 +464,7 @@ void Quadtree::raise(float x, float z, float radius, float focus, float strength
}
/* recalculate normals */
- for(int i = x-radius-1; i < x+radius; i++) {
+ /*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++) {
@@ -403,7 +475,7 @@ void Quadtree::raise(float x, float z, float radius, float focus, float strength
}
/* refill nodes and remake VBOs */
- for(int nx = x-radius-1; nx < x+radius+chunk_size; nx+=chunk_size) {
+ /*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) {
@@ -415,65 +487,45 @@ void Quadtree::raise(float x, float z, float radius, float focus, float strength
}
node->chunk->make_vbo();
}
- }
+ }*/
}
-Vector3 Quadtree::calc_normal(int x, int y) {
- Vector3 p(x, heights[x*height + y], y);
- Vector3 N;
-
- if(x > 0) {
- Vector3 U = Vector3(x-1, heights[(x-1)*height + y], y) - p;
- if(y > 0) {
- Vector3 V = Vector3(x, heights[x*height + y - 1], y-1) - p;
- N += V.cross(U);
- }
- if(y < height-1) {
- Vector3 V = Vector3(x, heights[x*height + y + 1], y+1) - p;
- N += U.cross(V);
+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));
}
}
- if(x < width-1) {
- Vector3 U = Vector3(x+1, heights[(x+1)*height + y], y) - p;
- if(y > 0) {
- Vector3 V = Vector3(x, heights[x*height + y - 1], y-1) - p;
- N += U.cross(V);
+ 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(y < height-1) {
- Vector3 V = Vector3(x, heights[x*height + y + 1], y+1) - p;
- N += V.cross(U);
+ if((*it)->distance(x, z) > 100) {
+ it = chunks.erase(it);
}
}
- N /= N.length();
- normals[x*height + y] = N;
- return N;
-}
-
-void Quadtree::update(float x, float z) {
- std::queue<QuadChunk*> q;
- q.push(root);
- while(!q.empty()) {
- QuadChunk *chunk = q.front();
- q.pop();
- if(!chunk->nodes) {
- for(int i = 0; i < 4; i++)
- q.push(chunk->children[i]);
- continue;
- }
-
- float d = chunk->distance(x, z);
- if(d < 100 && !chunk->vbo_object) {
- chunk->make_vbo();
- } else if(d > 100 && chunk->vbo_object) {
- glDeleteBuffers(1, &chunk->vbo_object);
- chunk->vbo_object = 0;
- chunk->vertices = 0;
- }
+ 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) {
- return root->find(x, 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) {
diff --git a/quadtree.h b/quadtree.h
index 62ac8bb..84125d2 100644
--- a/quadtree.h
+++ b/quadtree.h
@@ -2,6 +2,9 @@
#define QUADTREE_H
#include "vector.h"
+#include "terrain.h"
+
+#include <list>
class Quadtree {
public:
@@ -19,15 +22,17 @@ class Quadtree {
void fill();
void draw();
void draw_grid();
+ void draw_normal();
float get_height(float px, float py);
Vector3 get_normal(int index);
};
struct QuadChunk {
Quadtree *tree;
- QuadChunk *children[4];
QuadNode **nodes;
float x, y, width, height;
+ float *heights;
+ Vector3 *normals;
size_t buf_size;
unsigned int vbo_object;
unsigned int node_count;
@@ -40,21 +45,18 @@ class Quadtree {
float distance(float px, float pz);
void make_vbo();
QuadNode *find(float x, float y);
+ void calc_normals();
};
static const int chunk_size = 32;
- QuadChunk *root;
- float *heights;
- Vector3 *normals;
- int width, height;
- float init_time;
- Quadtree(int width, int height, float *heightmap);
+ std::list<QuadChunk*> chunks;
+ Terrain *terrain;
+ Quadtree();
virtual ~Quadtree();
void raise(float x, float z, float radius, float focus, float strength, bool up = true);
- Vector3 calc_normal(int x, int y);
void update(float x, float z);
QuadNode *find(float x, float y);
QuadNode *get_left(QuadNode *node);
diff --git a/scene.cpp b/scene.cpp
index b67468b..8d7301d 100644
--- a/scene.cpp
+++ b/scene.cpp
@@ -15,6 +15,7 @@
Scene::Scene() {
running = true;
grid = false;
+ normals = false;
terrain = true;
gravity = true;
@@ -48,10 +49,7 @@ Scene::Scene() {
marker_texture = load_texture("textures/cross.png");
/* init quadtree */
- int w = 1025;
- int h = 1025;
- float *heightmap = Terrain::generate_heights(0, 0, w, h);
- qt = new Quadtree(w, h, heightmap);
+ qt = new Quadtree();
/* load font */
font = new FTTextureFont("fonts/VeraMono.ttf");
@@ -156,6 +154,9 @@ void Scene::events() {
case SDLK_g:
grid = !grid;
break;
+ case SDLK_n:
+ normals = !normals;
+ break;
case SDLK_t:
terrain = !terrain;
break;
@@ -340,17 +341,19 @@ void Scene::render() {
glActiveTexture(GL_TEXTURE3);
glBindTexture(GL_TEXTURE_2D, marker_texture);
- std::queue<Quadtree::QuadChunk*> q;
+ /*std::queue<Quadtree::QuadChunk*> q;
q.push(qt->root);
while(!q.empty()) {
Quadtree::QuadChunk *chunk = q.front();
- q.pop();
- if(!chunk->nodes) {
+ q.pop();*/
+ for(std::list<Quadtree::QuadChunk*>::iterator it = qt->chunks.begin(); it != qt->chunks.end(); it++) {
+ Quadtree::QuadChunk *chunk = *it;
+ /*if(!chunk->nodes) {
for(int i = 0; i < 4; i++)
q.push(chunk->children[i]);
continue;
} else if(!chunk->vbo_object)
- continue;
+ continue;*/
chunks_rendered++;
glPushMatrix();
glTranslatef(-pos.x + chunk->x, -pos.y, -pos.z + chunk->y);
@@ -382,19 +385,34 @@ void Scene::render() {
glColor3f(0, 0, 0);
else
glColor3f(1, 1, 1);
- std::queue<Quadtree::QuadChunk*> q;
+ /*std::queue<Quadtree::QuadChunk*> q;
q.push(qt->root);
while(!q.empty()) {
Quadtree::QuadChunk *chunk = q.front();
- q.pop();
- if(!chunk->nodes) {
+ q.pop();*/
+ for(std::list<Quadtree::QuadChunk*>::iterator it = qt->chunks.begin(); it != qt->chunks.end(); it++) {
+ Quadtree::QuadChunk *chunk = *it;
+ glPushMatrix();
+ glTranslatef(-pos.x, -pos.y, -pos.z);
+ /*if(!chunk->nodes) {
for(int i = 0; i < 4; i++)
q.push(chunk->children[i]);
continue;
- } else if(chunk->vbo_object) {
+ } else*/ if(chunk->vbo_object) {
for(unsigned int i = 0; i < chunk->node_count; i++)
chunk->nodes[i]->draw_grid();
}
+ glPopMatrix();
+ }
+ }
+ if(normals) {
+ for(std::list<Quadtree::QuadChunk*>::iterator it = qt->chunks.begin(); it != qt->chunks.end(); it++) {
+ Quadtree::QuadChunk *chunk = *it;
+ glPushMatrix();
+ glTranslatef(-pos.x, -pos.y, -pos.z);
+ for(unsigned int i = 0; i < chunk->node_count; i++)
+ chunk->nodes[i]->draw_normal();
+ glPopMatrix();
}
}
@@ -411,8 +429,8 @@ void Scene::render() {
float height = font->LineHeight();
glColor3f(1, 1, 1);
glTranslatef(0, video::height-height, 0);
- font->Render((boost::format("%dx%d chunks: %d gravity: %d steps: %d")
- % qt->width % qt->height % chunks_rendered % gravity % steps).str().c_str());
+ font->Render((boost::format("chunks: %d gravity: %d steps: %d")
+ % chunks_rendered % gravity % steps).str().c_str());
//font->Render((boost::format("%dx%d %d levels %d nodes tree creation time: %f steps: %d update: %d")
// % scene.qt->width % scene.qt->height % scene.qt->levels % scene.qt->nodes % scene.qt->init_time % steps % scene.qt->thread_running).str().c_str());
//glTranslatef(0, height, 0);
diff --git a/scene.h b/scene.h
index 59f0c79..af4f96f 100644
--- a/scene.h
+++ b/scene.h
@@ -22,6 +22,7 @@ class Scene {
bool running;
bool grid;
+ bool normals;
bool terrain;
bool gravity;
bool dialog;
diff --git a/terrain.cpp b/terrain.cpp
index a44d0d3..e0cd291 100644
--- a/terrain.cpp
+++ b/terrain.cpp
@@ -18,7 +18,7 @@ float *Terrain::generate_heights(int x, int y, int width, int height) {
heightmap_builder.SetDestNoiseMap(heightmap);
heightmap_builder.SetDestSize(width, height);
- heightmap_builder.SetBounds(x / 100, (x+width) / 100, y / 100, (y+height) / 100);
+ heightmap_builder.SetBounds((double)x / 100, (double)(x+width) / 100, (double)y / 100, (double)(y+height) / 100);
heightmap_builder.Build();
float *heights = new float[width*height];
@@ -28,5 +28,15 @@ float *Terrain::generate_heights(int x, int y, int width, int height) {
}
}
+ chunk_indices.insert(std::pair<int, int>(x, y));
+
return heights;
}
+
+float *Terrain::get_chunk(int x, int y, int width, int height) {
+ return generate_heights(x, y, width, height);
+}
+
+bool Terrain::has_chunk(int x, int y) {
+ return chunk_indices.find(std::pair<int, int>(x, y)) != chunk_indices.end();
+}
diff --git a/terrain.h b/terrain.h
index 88b2277..3ce4402 100644
--- a/terrain.h
+++ b/terrain.h
@@ -1,9 +1,15 @@
#ifndef TERRAIN_H
#define TERRAIN_H
+#include <set>
+
class Terrain {
+ private:
+ std::set<std::pair<int, int> > chunk_indices;
public:
- static float *generate_heights(int x, int y, int width, int height);
+ float *generate_heights(int x, int y, int width, int height);
+ float *get_chunk(int x, int y, int width, int height);
+ bool has_chunk(int x, int y);
};
#endif
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-22 06:19:28 +0100