From e9d6ab657235ebbf3eb9fcb35537c9b2181a1360 Mon Sep 17 00:00:00 2001 From: Jon Bergli Heier Date: Sat, 9 Apr 2011 14:31:18 +0200 Subject: Moved from dynamic LOD to chunked loading. --- quadtree.cpp | 607 +++++++++++++++++------------------------------------------ 1 file changed, 172 insertions(+), 435 deletions(-) (limited to 'quadtree.cpp') 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 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 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 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 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 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 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) { -- cgit v1.2.3