summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--SConstruct2
-rw-r--r--main.cpp77
-rw-r--r--quadtree.cpp607
-rw-r--r--quadtree.h67
-rw-r--r--scene.cpp3
5 files changed, 245 insertions, 511 deletions
diff --git a/SConstruct b/SConstruct
index ee8efa8..1e7d2e3 100644
--- a/SConstruct
+++ b/SConstruct
@@ -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')
diff --git a/main.cpp b/main.cpp
index eee70dd..c0871a5 100644
--- a/main.cpp
+++ b/main.cpp
@@ -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) {
diff --git a/quadtree.h b/quadtree.h
index b927dee..d6d1e8e 100644
--- a/quadtree.h
+++ b/quadtree.h
@@ -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);
diff --git a/scene.cpp b/scene.cpp
index 5bbd1b2..9e606f1 100644
--- a/scene.cpp
+++ b/scene.cpp
@@ -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();
}