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 ++++++++++++++++++++++++++++++++++++----------------------- 1 file changed, 146 insertions(+), 94 deletions(-) (limited to 'quadtree.cpp') 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) { -- cgit v1.2.3