diff options
Diffstat (limited to 'quadtree.cpp')
| -rw-r--r-- | quadtree.cpp | 106 |
1 files changed, 97 insertions, 9 deletions
diff --git a/quadtree.cpp b/quadtree.cpp index b8aee16..782837c 100644 --- a/quadtree.cpp +++ b/quadtree.cpp @@ -11,6 +11,7 @@ #include <queue> using std::min; +using std::max; Quadtree::Quadtree(int width, int height, float *heightmap, int levels) { this->width = width; @@ -56,7 +57,10 @@ Quadtree::QuadNode::~QuadNode() { } float Quadtree::QuadNode::distance(float px, float pz) { - if(px > x && px < x+width && pz > y && pz < y+height) + 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); @@ -66,7 +70,14 @@ float Quadtree::QuadNode::distance(float px, float pz) { float c = (p - Vector2(x, y+height)).length(); float d = (p - Vector2(x+width, y+height)).length(); - return min(min(min(a, b), c), d); + 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() { @@ -99,6 +110,58 @@ 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; @@ -247,26 +310,51 @@ Vector3 Quadtree::QuadNode::get_normal(int index) { } void Quadtree::update(float x, float z) { - return; + bool changed = false; + std::queue<QuadNode*> q; q.push(root); while(!q.empty()) { QuadNode *node = q.front(); q.pop(); float d = node->distance(x, z); - std::cout << d << std::endl; - if(d < 20 && node->vertex_array) + int l = floorf(sqrtf(100-d+20))+1; + if(d < 100 && node->vertex_array && node->level < l) { node->subdivide(); - else if(d > 50 && !node->vertex_array) + changed = true; + } else if(!node->vertex_array && node->level > max(l, 6)) { node->merge(); + changed = true; + } if(node->vertex_array) - break; + continue; for(int i = 0; i < 4; i++) { q.push(node->children[i]); } } - make_vbo(); + 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]); + } + } + } } void Quadtree::create_nodes(int levels) { @@ -493,7 +581,7 @@ void Quadtree::make_vbo() { Quadtree::QuadNode* Quadtree::find(float x, float y, int level) { QuadNode *node = root; - while(!node->vertex_array) { + while(node && !node->vertex_array) { if(node->level == level) return node; float mx = node->x + node->width / 2; |