diff options
| -rw-r--r-- | quadtree.cpp | 557 | ||||
| -rw-r--r-- | quadtree.h | 68 | ||||
| -rw-r--r-- | scene.cpp | 32 | ||||
| -rw-r--r-- | scene.h | 8 | ||||
| -rw-r--r-- | terrain.cpp | 525 | ||||
| -rw-r--r-- | terrain.h | 55 | ||||
| -rw-r--r-- | tool.cpp | 10 | ||||
| -rw-r--r-- | tool.h | 8 |
8 files changed, 609 insertions, 654 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; -} diff --git a/quadtree.h b/quadtree.h deleted file mode 100644 index 84125d2..0000000 --- a/quadtree.h +++ /dev/null @@ -1,68 +0,0 @@ -#ifndef QUADTREE_H -#define QUADTREE_H - -#include "vector.h" -#include "terrain.h" - -#include <list> - -class Quadtree { - public: - struct QuadChunk; - - struct QuadNode { - QuadChunk *chunk; - float x, y, width, height; - float vertex_array[15]; - - QuadNode(QuadChunk *chunk, float x, float y, float width, float height); - virtual ~QuadNode(); - - float distance(float px, float pz); - 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; - QuadNode **nodes; - float x, y, width, height; - float *heights; - Vector3 *normals; - size_t buf_size; - unsigned int vbo_object; - unsigned int node_count; - unsigned int vertices; - float init_time; - - QuadChunk(Quadtree *tree, float x, float y, float width, float height); - ~QuadChunk(); - - float distance(float px, float pz); - void make_vbo(); - QuadNode *find(float x, float y); - void calc_normals(); - }; - - static const int chunk_size = 32; - - std::list<QuadChunk*> chunks; - Terrain *terrain; - Quadtree(); - virtual ~Quadtree(); - - void raise(float x, float z, float radius, float focus, float strength, bool up = true); - - void update(float x, float z); - QuadNode *find(float x, float y); - QuadNode *get_left(QuadNode *node); - QuadNode *get_right(QuadNode *node); - QuadNode *get_up(QuadNode *node); - QuadNode *get_down(QuadNode *node); -}; - -#endif @@ -16,7 +16,7 @@ Scene::Scene() { running = true; grid = false; normals = false; - terrain = true; + render_terrain = true; gravity = true; last_node = NULL; @@ -48,8 +48,8 @@ Scene::Scene() { soil_texture = load_texture("textures/zooboing-469-sand-modified.jpg"); marker_texture = load_texture("textures/cross.png"); - /* init quadtree */ - qt = new Quadtree(); + /* init terrain */ + terrain = new Terrain(); /* load font */ font = new FTTextureFont("fonts/VeraMono.ttf"); @@ -61,8 +61,8 @@ Scene::Scene() { Scene::~Scene() { if(tool) delete tool; - if(qt) - delete qt; + if(terrain) + delete terrain; delete font; } @@ -129,7 +129,7 @@ bool Scene::select(int x, int y, float& px, float& py, float& pz) { } void Scene::update() { - qt->update(pos.x, pos.z); + terrain->update(pos.x, pos.z); } void Scene::events() { @@ -158,7 +158,7 @@ void Scene::events() { normals = !normals; break; case SDLK_t: - terrain = !terrain; + render_terrain = !render_terrain; break; case SDLK_SPACE: yvel = .05; @@ -174,7 +174,7 @@ void Scene::events() { break; case SDLK_1: if(tool) delete tool; - tool = new RaiseTool(qt); + tool = new RaiseTool(terrain); break; default: break; @@ -284,7 +284,7 @@ void Scene::render() { } std::string move_str; - Quadtree::QuadNode *node = qt->find(pos.x, pos.z); + Terrain::Node *node = terrain->find(pos.x, pos.z); if(node) { if(gravity) { float y = node->get_height(pos.x, pos.z); @@ -316,7 +316,7 @@ void Scene::render() { //glLightfv(GL_LIGHT0, GL_POSITION, light_pos); unsigned int chunks_rendered = 0; - if(terrain) { + if(render_terrain) { terrain_program.use(); GLint show_sel = glGetUniformLocation(terrain_program.get_program(), "show_sel"); glUniform1i(show_sel, show_selection ? 1 : 0); @@ -346,8 +346,8 @@ void Scene::render() { while(!q.empty()) { Quadtree::QuadChunk *chunk = q.front(); q.pop();*/ - for(std::list<Quadtree::QuadChunk*>::iterator it = qt->chunks.begin(); it != qt->chunks.end(); it++) { - Quadtree::QuadChunk *chunk = *it; + for(std::list<Terrain::Chunk*>::iterator it = terrain->chunks.begin(); it != terrain->chunks.end(); it++) { + Terrain::Chunk *chunk = *it; /*if(!chunk->nodes) { for(int i = 0; i < 4; i++) q.push(chunk->children[i]); @@ -390,8 +390,8 @@ void Scene::render() { while(!q.empty()) { Quadtree::QuadChunk *chunk = q.front(); q.pop();*/ - for(std::list<Quadtree::QuadChunk*>::iterator it = qt->chunks.begin(); it != qt->chunks.end(); it++) { - Quadtree::QuadChunk *chunk = *it; + for(std::list<Terrain::Chunk*>::iterator it = terrain->chunks.begin(); it != terrain->chunks.end(); it++) { + Terrain::Chunk *chunk = *it; glPushMatrix(); glTranslatef(-pos.x, -pos.y, -pos.z); /*if(!chunk->nodes) { @@ -406,8 +406,8 @@ void Scene::render() { } } if(normals) { - for(std::list<Quadtree::QuadChunk*>::iterator it = qt->chunks.begin(); it != qt->chunks.end(); it++) { - Quadtree::QuadChunk *chunk = *it; + for(std::list<Terrain::Chunk*>::iterator it = terrain->chunks.begin(); it != terrain->chunks.end(); it++) { + Terrain::Chunk *chunk = *it; glPushMatrix(); glTranslatef(-pos.x, -pos.y, -pos.z); for(unsigned int i = 0; i < chunk->node_count; i++) @@ -2,7 +2,7 @@ #define SCENE_H #include "vector.h" -#include "quadtree.h" +#include "terrain.h" #include "gl.h" #include "shader.h" #include "gui.h" @@ -15,7 +15,7 @@ class Scene { float pitch, yaw; Vector3 pos; float yvel; - Quadtree *qt; + Terrain *terrain; FTFont *font; GUI *gui; Tool *tool; @@ -23,11 +23,11 @@ class Scene { bool running; bool grid; bool normals; - bool terrain; + bool render_terrain; bool gravity; bool dialog; - Quadtree::QuadNode *last_node; + Terrain::Node *last_node; unsigned int last_time; Vector3 selected; diff --git a/terrain.cpp b/terrain.cpp index e0cd291..a6f1e66 100644 --- a/terrain.cpp +++ b/terrain.cpp @@ -1,12 +1,445 @@ #include "terrain.h" +#include "vector.h" + +#include "gl.h" #include <noise/noise.h> #include "noiseutils/noiseutils.h" #include <iostream> +#include <cmath> +#include <queue> +#include <set> using namespace noise; +using std::min; +using std::max; + +Terrain::Node::Node(Chunk *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(); +} + +Terrain::Node::~Node() { +} + +float Terrain::Node::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 Terrain::Node::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 Terrain::Node::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 Terrain::Node::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 Terrain::Node::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 Terrain::Node::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; +} + +/* Chunk */ + +Terrain::Chunk::Chunk(Terrain *terrain, float x, float y, float width, float height) { + this->terrain = terrain; + 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 = 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 Node*[node_count]; + for(int i = 0; i < height; i++) { + for(int j = 0; j < width; j++) { + nodes[j*(int)height + i] = new Node(this, j, i, 1, 1); + } + } + make_vbo(); +} + +Terrain::Chunk::~Chunk() { + for(unsigned int i = 0; i < node_count; i++) + delete nodes[i]; + delete[] nodes; + delete[] heights; + delete[] normals; +} + +float Terrain::Chunk::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 Terrain::Chunk::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++) { + Terrain::Node *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] = |