From 7d5c1adf8e581599848b3fec54e0af88eb469046 Mon Sep 17 00:00:00 2001 From: Jon Bergli Heier Date: Sun, 8 May 2011 15:02:30 +0200 Subject: Working dynamic generation of terrain. --- quadtree.cpp | 240 ++++++++++++++++++++++++++++++++++++----------------------- quadtree.h | 18 +++-- scene.cpp | 46 ++++++++---- scene.h | 1 + terrain.cpp | 12 ++- terrain.h | 8 +- 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 #include +#include 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::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 > 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(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::iterator it = chunks.begin(); it != chunks.end(); it++) { + std::set >::iterator ind_it = chunk_indices.find(std::pair((*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 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 >::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::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 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 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 q; + /*std::queue q; q.push(qt->root); while(!q.empty()) { Quadtree::QuadChunk *chunk = q.front(); - q.pop(); - if(!chunk->nodes) { + q.pop();*/ + for(std::list::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 q; + /*std::queue q; q.push(qt->root); while(!q.empty()) { Quadtree::QuadChunk *chunk = q.front(); - q.pop(); - if(!chunk->nodes) { + q.pop();*/ + for(std::list::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::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(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(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 + class Terrain { + private: + std::set > 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 -- cgit v1.2.3