diff options
| -rw-r--r-- | SConstruct | 2 | ||||
| -rw-r--r-- | main.cpp | 77 | ||||
| -rw-r--r-- | quadtree.cpp | 607 | ||||
| -rw-r--r-- | quadtree.h | 67 | ||||
| -rw-r--r-- | scene.cpp | 3 |
5 files changed, 245 insertions, 511 deletions
@@ -8,7 +8,7 @@ AddOption('--release', action = 'store_true') AddOption('--profiling', action = 'store_true') env.Append(CPPPATH = ['.']) -env.Append(LIBS = ['GL', 'GLU', 'boost_thread']) +env.Append(LIBS = ['GL', 'GLU']) env.ParseConfig('sdl-config --cflags --libs') env.ParseConfig('pkg-config --cflags --libs SDL_image') env.ParseConfig('pkg-config --cflags --libs ftgl') @@ -102,26 +102,6 @@ int main(int argc, char **argv) { case SDLK_t: terrain = !terrain; break; - case SDLK_KP_PLUS: - case SDLK_PLUS: - scene.qt->create_nodes(scene.qt->levels+1); - break; - case SDLK_KP_MINUS: - case SDLK_MINUS: - if(scene.qt->levels > 1) { - scene.qt->create_nodes(scene.qt->levels-1); - } - break; - case SDLK_KP_MULTIPLY: - node = scene.qt->find(scene.pos.x, scene.pos.z); - node->parent->merge(); - scene.qt->make_vbo(); - break; - case SDLK_KP_DIVIDE: - node = scene.qt->find(scene.pos.x, scene.pos.z); - node->subdivide(); - scene.qt->make_vbo(); - break; case SDLK_SPACE: scene.yvel = .05; break; @@ -131,9 +111,6 @@ int main(int argc, char **argv) { case SDLK_u: scene.update(); break; - case SDLK_c: - scene.qt->fix_cracks(); - break; default: break; } @@ -216,7 +193,7 @@ int main(int argc, char **argv) { scene.yvel = 0; } } - move_str = (boost::format("%s %.2f,%.2f %.2fx%.2f %d") % scene.pos.str() % node->x % node->y % node->width % node->height % node->level).str(); + move_str = (boost::format("%s %.2f,%.2f %.2fx%.2f") % scene.pos.str() % node->x % node->y % node->width % node->height).str(); if(last_node != node) { last_node = node; @@ -231,21 +208,42 @@ int main(int argc, char **argv) { //const float light_pos[4] = {0, 1, 0, 0}; //glLightfv(GL_LIGHT0, GL_POSITION, light_pos); + unsigned int chunks_rendered = 0; if(terrain) { program.use(); glBindTexture(GL_TEXTURE_2D, grass_texture); glEnable(GL_TEXTURE_2D); - glBindBuffer(GL_ARRAY_BUFFER, scene.qt->vbo_object); + //for(int i = 0; i < scene.qt->chunk_count; i++) { + std::queue<Quadtree::QuadChunk*> q; + q.push(scene.qt->root); + while(!q.empty()) { + Quadtree::QuadChunk *chunk = q.front(); + q.pop(); + if(!chunk->nodes) { + for(int i = 0; i < 4; i++) + q.push(chunk->children[i]); + continue; + } else if(!chunk->vbo_object) + continue; + chunks_rendered++; + //std::cout << (boost::format("vertices: %d nodes: %d") % scene.qt->chunks[i]->vertices % scene.qt->chunks[i]->node_count).str() << std::endl; + //glBindBuffer(GL_ARRAY_BUFFER, scene.qt->vbo_object); + //glBindBuffer(GL_ARRAY_BUFFER, scene.qt->chunks[i]->vbo_object); + glBindBuffer(GL_ARRAY_BUFFER, chunk->vbo_object); glVertexPointer(3, GL_FLOAT, 0, NULL); - glNormalPointer(GL_FLOAT, 0, (GLvoid*)(scene.qt->vertices*3*sizeof(float))); - glTexCoordPointer(2, GL_FLOAT, 0, (GLvoid*)(scene.qt->vertices*3*sizeof(float)*2)); + //glNormalPointer(GL_FLOAT, 0, (GLvoid*)(scene.qt->vertices*3*sizeof(float))); + glNormalPointer(GL_FLOAT, 0, (GLvoid*)(chunk->vertices*3*sizeof(float))); + //glTexCoordPointer(2, GL_FLOAT, 0, (GLvoid*)(scene.qt->vertices*3*sizeof(float)*2)); + glTexCoordPointer(2, GL_FLOAT, 0, (GLvoid*)(chunk->vertices*3*sizeof(float)*2)); glEnableClientState(GL_VERTEX_ARRAY); glEnableClientState(GL_NORMAL_ARRAY); glEnableClientState(GL_TEXTURE_COORD_ARRAY); - glDrawArrays(GL_TRIANGLES, 0, scene.qt->vertices); + //glDrawArrays(GL_TRIANGLES, 0, scene.qt->vertices); + glDrawArrays(GL_TRIANGLES, 0, chunk->vertices); glDisableClientState(GL_VERTEX_ARRAY); glDisableClientState(GL_NORMAL_ARRAY); glDisableClientState(GL_TEXTURE_COORD_ARRAY); + } glDisable(GL_TEXTURE_2D); glUseProgram(0); } @@ -254,16 +252,19 @@ int main(int argc, char **argv) { glColor3f(0, 0, 0); else glColor3f(1, 1, 1); - std::queue<Quadtree::QuadNode*> q; + std::queue<Quadtree::QuadChunk*> q; q.push(scene.qt->root); while(!q.empty()) { - Quadtree::QuadNode *node = q.front(); + Quadtree::QuadChunk *chunk = q.front(); q.pop(); - if(node->vertex_array) { - grid ? node->draw_grid() : node->draw(); - } else + if(!chunk->nodes) { for(int i = 0; i < 4; i++) - q.push(node->children[i]); + q.push(chunk->children[i]); + continue; + } else if(chunk->vbo_object) { + for(unsigned int i = 0; i < chunk->node_count; i++) + chunk->nodes[i]->draw_grid(); + } } } @@ -287,8 +288,10 @@ int main(int argc, char **argv) { float height = font->LineHeight(); glColor3f(1, 1, 1); glTranslatef(0, video::height-height, 0); - 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()); + font->Render((boost::format("%dx%d chunks: %d steps: %d") + % scene.qt->width % scene.qt->height % chunks_rendered % 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); //font->Render((boost::format("selected: %x") % selected).str().c_str()); glTranslatef(0, -height, 0); @@ -301,7 +304,7 @@ int main(int argc, char **argv) { SDL_GL_SwapBuffers(); - usleep(1000); + SDL_Delay(1); } video::free(); diff --git a/quadtree.cpp b/quadtree.cpp index 7fdf24f..8082ba7 100644 --- a/quadtree.cpp +++ b/quadtree.cpp @@ -13,49 +13,17 @@ using std::min; using std::max; -Quadtree::Quadtree(int width, int height, float *heightmap, int levels) { - this->width = width; - this->height = height; - vbo_object = 0; - root = NULL; - heights = heightmap; - thread_done = thread_running = false; - thread_buffer = NULL; - - create_nodes(levels); -} - -Quadtree::~Quadtree() { - if(vbo_object) - glDeleteBuffers(1, &vbo_object); - delete root; - delete[] heights; -} - -Quadtree::QuadNode::QuadNode(Quadtree *tree, QuadNode *parent, float x, float y, float width, float height, int level, bool leaf) { - this->tree = tree; - this->parent = parent; +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; - this->level = level; - children[0] = children[1] = children[2] = children[3] = NULL; - if(!leaf) { - elems = 0; - vertex_array = NULL; - return; - } fill(); } Quadtree::QuadNode::~QuadNode() { - if(vertex_array) - delete[] vertex_array; - for(int i = 0; i < 4; i++) - if(children[i]) - delete children[i]; } float Quadtree::QuadNode::distance(float px, float pz) { @@ -83,27 +51,24 @@ float Quadtree::QuadNode::distance(float px, float pz) { } void Quadtree::QuadNode::fill() { - elems = 3*5; - int size = sizeof(float)*elems; - vertex_array = new float[size]; vertex_array[0] = x + width / 2; - vertex_array[1] = tree->heights[(int)floorf((int)(x + width/2)*tree->height + (int)(y + height/2))]; + vertex_array[1] = chunk->tree->heights[(int)floorf((int)(x + width/2)*chunk->tree->height + (int)(y + height/2))]; vertex_array[2] = y + height / 2; vertex_array[3] = x; - vertex_array[4] = tree->heights[(int)floorf(x*tree->height+y)]; + vertex_array[4] = chunk->tree->heights[(int)floorf(x*chunk->tree->height+y)]; vertex_array[5] = y; vertex_array[6] = x; - vertex_array[7] = tree->heights[(int)floorf(x*tree->height + (y + height))]; + vertex_array[7] = chunk->tree->heights[(int)floorf(x*chunk->tree->height + (y + height))]; vertex_array[8] = y + height; vertex_array[9] = x + width; - vertex_array[10] = tree->heights[(int)floorf((x + width)*tree->height + (y + height))]; + vertex_array[10] = chunk->tree->heights[(int)floorf((x + width)*chunk->tree->height + (y + height))]; vertex_array[11] = y + height; vertex_array[12] = x + width; - vertex_array[13] = tree->heights[(int)floorf((x + width)*tree->height + y)]; + vertex_array[13] = chunk->tree->heights[(int)floorf((x + width)*chunk->tree->height + y)]; vertex_array[14] = y; /* midpoint is average of corner heights when width == 1 */ @@ -112,85 +77,7 @@ void Quadtree::QuadNode::fill() { } } -void Quadtree::QuadNode::fix_cracks() { - // y = y0 + (x - x0) * (y1 - y0) / (x1 - x0) - - QuadNode *down = tree->get_down(this); - if(down && level > down->level) { - vertex_array[4] = down->vertex_array[7] + - (vertex_array[3] - down->vertex_array[6]) * - (down->vertex_array[10] - down->vertex_array[7]) / - (down->vertex_array[9] - down->vertex_array[6]); - vertex_array[13] = down->vertex_array[7] + - (vertex_array[12] - down->vertex_array[6]) * - (down->vertex_array[10] - down->vertex_array[7]) / - (down->vertex_array[9] - down->vertex_array[6]); - } - - QuadNode *up = tree->get_up(this); - if(up && level > up->level) { - vertex_array[7] = up->vertex_array[4] + - (vertex_array[6] - up->vertex_array[3]) * - (up->vertex_array[13] - up->vertex_array[4]) / - (up->vertex_array[12] - up->vertex_array[3]); - vertex_array[10] = up->vertex_array[4] + - (vertex_array[9] - up->vertex_array[3]) * - (up->vertex_array[13] - up->vertex_array[4]) / - (up->vertex_array[12] - up->vertex_array[3]); - } - - QuadNode *left = tree->get_left(this); - if(left && level > left->level) { - vertex_array[10] = left->vertex_array[4] + - (vertex_array[11] - left->vertex_array[5]) * - (left->vertex_array[7] - left->vertex_array[4]) / - (left->vertex_array[8] - left->vertex_array[5]); - vertex_array[13] = left->vertex_array[4] + - (vertex_array[14] - left->vertex_array[5]) * - (left->vertex_array[7] - left->vertex_array[4]) / - (left->vertex_array[8] - left->vertex_array[5]); - } - - QuadNode *right = tree->get_right(this); - if(right && level > right->level) { - vertex_array[4] = right->vertex_array[13] + - (vertex_array[5] - right->vertex_array[14]) * - (right->vertex_array[10] - right->vertex_array[13]) / - (right->vertex_array[11] - right->vertex_array[14]); - vertex_array[7] = right->vertex_array[13] + - (vertex_array[8] - right->vertex_array[14]) * - (right->vertex_array[10] - right->vertex_array[13]) / - (right->vertex_array[11] - right->vertex_array[14]); - } -} - -void Quadtree::QuadNode::subdivide(bool leaf) { - if(vertex_array) { - elems = 0; - delete[] vertex_array; - vertex_array = NULL; - } - - 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 QuadNode(tree, this, nx, ny, width / 2, height / 2, level + 1, leaf); - } -} - -void Quadtree::QuadNode::merge() { - for(int i = 0; i < 4; i++) { - delete children[i]; - children[i] = NULL; - } - - fill(); -} - void Quadtree::QuadNode::draw() { - if(!vertex_array) - return; - float tex_coords[4][3][2] = { {{.5, .5}, {0, 0}, {0, 1}}, {{.5, .5}, {0, 1}, {1, 1}}, @@ -222,9 +109,6 @@ void Quadtree::QuadNode::draw() { } void Quadtree::QuadNode::draw_grid() { - if(!vertex_array) - return; - glNormal3f(0, 1, 0); glBegin(GL_LINES); for(int i = 0; i < 4; i++) { @@ -278,174 +162,86 @@ 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(); -} +/* QuadChunk */ -void Quadtree::update(float x, float z) { - if(!node_lock.try_lock()) { - return; - } - - /* - * Lock won't be held until this function calls make_vbo(), - * which creates the update thread. - */ - node_lock.unlock(); - - bool changed = false; +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; - std::queue<QuadNode*> q; - q.push(root); - while(!q.empty()) { - QuadNode *node = q.front(); - q.pop(); - float d = node->distance(x, z); - int l = floorf(sqrtf(100-d+20))+1; - if(d < 100 && node->vertex_array && node->level < l) { - node->subdivide(); - changed = true; - } else if(!node->vertex_array && node->level > max(l, 6)) { - node->merge(); - changed = true; - } - if(node->vertex_array) - continue; + if(width / chunk_size > 1) { + node_count = 0; + nodes = NULL; for(int i = 0; i < 4; i++) { - q.push(node->children[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; } - if(changed) { - fix_cracks(); - make_vbo(); - } -} - -void Quadtree::fix_cracks() { - std::queue<QuadNode*> q; - q.push(root); - while(!q.empty()) { - QuadNode *node = q.front(); - q.pop(); - if(node->vertex_array) { - if(node->vertex_array) delete[] node->vertex_array; - node->fill(); - node->fix_cracks(); - } else { - for(int i = 0; i < 4; i++) { - q.push(node->children[i]); - } + 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, x+j, y+i, 1, 1); } } } -void Quadtree::create_nodes(int levels) { - if(root) - delete root; - - int l = log2f(width); - if(levels > l) { - levels = l; - } - this->levels = levels; +Quadtree::QuadChunk::~QuadChunk() { + for(unsigned int i = 0; i < node_count; i++) + delete nodes[i]; + delete[] nodes; +} - boost::timer t; - root = new QuadNode(this, NULL, 0, 0, width-1, height-1, 1, levels == 0); - std::queue<Quadtree::QuadNode*> q; - if(levels > 0) - q.push(root); - while(!q.empty()) { - Quadtree::QuadNode *node = q.front(); - q.pop(); - node->subdivide(node->level == levels); - if(node->level < levels) { - for(int i = 0; i < 4; i++) - q.push(node->children[i]); - } - } +float Quadtree::QuadChunk::distance(float px, float pz) { + bool in_width = px > x && px < x+width; + bool in_height = pz > y && pz < y+height; - make_vbo(); + if(in_width && in_height) + return 0; - init_time = t.elapsed(); -} + Vector2 p(px, pz); -unsigned int Quadtree::count_nodes() { - std::queue<Quadtree::QuadNode*> q; - q.push(root); - unsigned int count = 0; - while(!q.empty()) { - Quadtree::QuadNode *node = q.front(); - q.pop(); + 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(); - if(!node->vertex_array) { - for(int i = 0; i < 4; i++) - q.push(node->children[i]); - } else { - count++; - } - } + float dist = min(min(min(a, b), c), d); - return count; -} + 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))); -Quadtree::UpdateThread::UpdateThread(Quadtree *t, float *b) { - tree = t; - buffer = b; + return dist; } -void Quadtree::UpdateThread::operator()() { - tree->vbo_lock.lock(); - tree->node_lock.lock(); +void Quadtree::QuadChunk::make_vbo() { + node_count = width*height; + vertices = node_count*12; + glGenBuffers(1, &vbo_object); + glBindBuffer(GL_ARRAY_BUFFER, vbo_object); - unsigned int nodes = tree->nodes; - const size_t vertex_chunk_size = 3*12; - const size_t vertices_size = vertex_chunk_size*nodes; + 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*nodes; - const size_t tex_coord_chunk_size = 2*12; - //const size_t tex_coords_size = tex_coord_chunk_size*nodes; + 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; - std::queue<Quadtree::QuadNode*> q; - q.push(tree->root); - unsigned int index = 0; - while(!q.empty()) { - Quadtree::QuadNode* node = q.front(); - q.pop(); - if(!node->vertex_array) { - for(int j = 0; j < 4; j++) - q.push(node->children[j]); - continue; - } + 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][3][2] = { {{.5, .5}, {0, 0}, {0, 1}}, {{.5, .5}, {0, 1}, {1, 1}}, @@ -475,196 +271,137 @@ void Quadtree::UpdateThread::operator()() { float *n = buffer + vertices_size + normal_chunk_size*index; - /* interpolate normals per vertex between nodes */ + Vector3 bl = tree->normals[(int)((node->x+1)*tree->height + node->y)]; + Vector3 br = tree->normals[(int)(node->x*tree->height + node->y)]; + Vector3 tr = tree->normals[(int)(node->x*tree->height + node->y+1)]; + Vector3 tl = tree->normals[(int)((node->x+1)*tree->height + node->y+1)]; + + n[24] = n[30] = bl.x; + n[25] = n[31] = bl.y; + n[26] = n[32] = bl.z; - QuadNode *left = tree->get_left(node); - QuadNode *right = tree->get_right(node); - QuadNode *up = tree->get_up(node); - QuadNode *down = tree->get_down(node); + n[3] = n[33] = br.x; + n[4] = n[34] = br.y; + n[5] = n[35] = br.z; - // midpoint - { - Vector3 v(node->get_normal(0) + node->get_normal(1) + node->get_normal(2) + node->get_normal(3)); + 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(tree->normals[(int)((node->x+node->width/2)*tree->height + 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; } + } - // 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 *temp = tree->get_left(down); - if(temp) { - v += temp->get_normal(0); - v += temp->get_normal(1); - } - } - v /= v.length(); - n[24] = n[30] = v.x; - n[25] = n[31] = v.y; - n[26] = n[32] = v.z; - } + glUnmapBuffer(GL_ARRAY_BUFFER); +} - // 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 *temp = tree->get_down(right); - if(temp) { - v += temp->get_normal(1); - v += temp->get_normal(2); - } - } - v /= v.length(); - n[3] = n[33] = v.x; - n[4] = n[34] = v.y; - n[5] = n[35] = v.z; - } +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)]; +} - // 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 *temp = tree->get_right(up); - if(temp) { - v += temp->get_normal(2); - v += temp->get_normal(3); - } - } - v /= v.length(); - n[6] = n[12] = v.x; - n[7] = n[13] = v.y; - n[8] = n[14] = v.z; - } +/* Quadtree */ - // 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); +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); + + boost::timer t; + normals = new Vector3[width*height]; + for(int x = 0; x < width; x++) { + for(int y = 0; y < height; 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); + } } - if(left && up) { - QuadNode *temp = tree->get_left(up); - if(temp) { - v += temp->get_normal(0); - v += temp->get_normal(3); + 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); + } + if(y < height-1) { + Vector3 V = Vector3(x, heights[x*height + y + 1], y+1) - p; + N += V.cross(U); } } - v /= v.length(); - n[15] = n[21] = v.x; - n[16] = n[22] = v.y; - n[17] = n[23] = v.z; + if(N.y < 0) + std::cout << N.str() << std::endl; + normals[x*height + y] = N / N.length(); } - - index++; } - - tree->thread_done = true; - tree->thread_running = false; - - tree->node_lock.unlock(); - tree->vbo_lock.unlock(); + std::cout << "normal time: " << t.elapsed() << std::endl; } -void Quadtree::make_vbo() { - if(thread_running || thread_done || thread_buffer) - return; - - nodes = count_nodes(); - glGenBuffers(1, &temp_vbo); - glBindBuffer(GL_ARRAY_BUFFER, temp_vbo); - - const size_t vertex_chunk_size = sizeof(float)*3*12; - const size_t vertices_size = vertex_chunk_size*nodes; - const size_t normal_chunk_size = vertex_chunk_size; - const size_t normals_size = normal_chunk_size*nodes; - const size_t tex_coord_chunk_size = sizeof(float)*2*12; - const size_t tex_coords_size = tex_coord_chunk_size*nodes; - - buf_size = sizeof(float)*(vertices_size + normals_size + tex_coords_size); - - glBufferData(GL_ARRAY_BUFFER, sizeof(float)*(vertices_size + normals_size + tex_coords_size), NULL, GL_STATIC_DRAW); - - thread_buffer = (float*)glMapBuffer(GL_ARRAY_BUFFER, GL_WRITE_ONLY); - - thread_running = true; - boost::thread(UpdateThread(this, thread_buffer)); +Quadtree::~Quadtree() { + delete root; + delete[] heights; + delete[] normals; } -void Quadtree::update_vbo() { - if(!vbo_lock.try_lock()) { - return; - } +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; + } - if(!thread_done || !thread_buffer || thread_running) { - vbo_lock.unlock(); - return; + 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; + } } - - thread_done = false; - - glBindBuffer(GL_ARRAY_BUFFER, temp_vbo); - glBufferData(GL_ARRAY_BUFFER, buf_size, thread_buffer, GL_STATIC_DRAW); - - thread_buffer = NULL; - - vertices = nodes*12; - - if(vbo_object) - glDeleteBuffers(1, &vbo_object); - vbo_object = temp_vbo; - temp_vbo = 0; - - vbo_lock.unlock(); } -Quadtree::QuadNode* Quadtree::find(float x, float y, int level) { - QuadNode *node = root; - while(node && !node->vertex_array) { - if(node->level == level) - return node; - float mx = node->x + node->width / 2; - float my = node->y + node->height / 2; - int i = 2*(y > my); - if(i < 2 && x > mx) - i = 1; - else if(i == 2 && x < mx) - i = 3; - node = node->children[i]; - } - - return node; +Quadtree::QuadNode *Quadtree::find(float x, float y) { + return root->find(x, y); } Quadtree::QuadNode *Quadtree::get_left(Quadtree::QuadNode *node) { @@ -3,64 +3,59 @@ #include "vector.h" -#include <boost/thread.hpp> +#include <list> class Quadtree { public: - - struct UpdateThread { - Quadtree *tree; - float *buffer; - UpdateThread(Quadtree *t, float *b); - void operator()(); - }; + struct QuadChunk; struct QuadNode { - Quadtree *tree; - QuadNode *parent; - QuadNode *children[4]; - int elems; + QuadChunk *chunk; float x, y, width, height; - int level; - float *vertex_array; + float vertex_array[15]; - QuadNode(Quadtree *tree, QuadNode *parent, float x, float y, float width, float height, int level, bool leaf); + QuadNode(QuadChunk *chunk, float x, float y, float width, float height); virtual ~QuadNode(); float distance(float px, float pz); void fill(); - void fix_cracks(); - void subdivide(bool leaf = true); - void merge(); void draw(); void draw_grid(); 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; + 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); + }; + + static const int chunk_size = 32; + + QuadChunk *root; float *heights; - float *thread_buffer; - size_t buf_size; - bool thread_done, thread_running; - boost::mutex vbo_lock; - boost::mutex node_lock; - int width, height, levels; + Vector3 *normals; + int width, height; float init_time; - QuadNode *root; - unsigned int temp_vbo; - unsigned int vbo_object; - unsigned int nodes; - unsigned int vertices; - Quadtree(int width, int height, float *heightmap, int levels); + Quadtree(int width, int height, float *heightmap); virtual ~Quadtree(); void update(float x, float z); - void fix_cracks(); - void create_nodes(int levels); - unsigned int count_nodes(); - void make_vbo(); - void update_vbo(); - QuadNode *find(float x, float y, int level = -1); + QuadNode *find(float x, float y); QuadNode *get_left(QuadNode *node); QuadNode *get_right(QuadNode *node); QuadNode *get_up(QuadNode *node); @@ -19,7 +19,7 @@ Scene::Scene() { int w = hm->w; int h = hm->h; SDL_FreeSurface(hm); - qt = new Quadtree(w, h, heightmap, 3); + qt = new Quadtree(w, h, heightmap); } Scene::~Scene() { @@ -92,5 +92,4 @@ bool Scene::select(int x, int y, float& px, float& py, float& pz) { void Scene::update() { qt->update(pos.x, pos.z); - qt->update_vbo(); } |