1 /*
2 Copyright (c) 2009 Andrew Caudwell (acaudwell@gmail.com)
3 All rights reserved.
4
5 Redistribution and use in source and binary forms, with or without
6 modification, are permitted provided that the following conditions
7 are met:
8 1. Redistributions of source code must retain the above copyright
9 notice, this list of conditions and the following disclaimer.
10 2. Redistributions in binary form must reproduce the above copyright
11 notice, this list of conditions and the following disclaimer in the
12 documentation and/or other materials provided with the distribution.
13 3. The name of the author may not be used to endorse or promote products
14 derived from this software without specific prior written permission.
15
16 THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
17 IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
18 OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
19 IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
20 INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
21 NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
22 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
23 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
24 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
25 THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
26 */
27
28 #include "quadtree.h"
29
30 // QUAD NODE
31
32 // allow more items in node if
33 // - has no children and one of any of:
34 // * maximum depth reached
35 // * item count is less than desired capacity
36
37
allowMoreItems()38 bool QuadNode::allowMoreItems() {
39 return (children.empty() && (depth >= tree->max_node_depth || items.size() < tree->max_node_items ) );
40 }
41
42
addItem(QuadItem * item)43 void QuadNode::addItem(QuadItem* item) {
44
45 if(allowMoreItems()) {
46 tree->item_count++;
47 item->node_count++;
48 items.push_back(item);
49 return;
50 }
51
52 if(!children.empty()) {
53 addToChild(item);
54 return;
55 }
56
57 vec2 average = bounds.centre();
58
59 vec2 middle = average - bounds.min;
60
61 vec2 relmax = bounds.max-bounds.min;
62
63 Bounds2D newbounds;
64
65 children.reserve(4);
66
67 //top left
68 newbounds = Bounds2D( bounds.min + vec2(0.0, 0.0), bounds.min + middle );
69 children.push_back(new QuadNode(tree, this, newbounds, depth));
70
71 //top right
72 newbounds = Bounds2D( bounds.min + vec2(middle.x, 0.0), bounds.min + vec2(relmax.x,middle.y) );
73 children.push_back(new QuadNode(tree, this, newbounds, depth));
74
75 //bottom left
76 newbounds = Bounds2D( bounds.min + vec2(0.0, middle.y), bounds.min + vec2(middle.x,relmax.y) );
77 children.push_back(new QuadNode(tree, this, newbounds, depth));
78
79 //bottom right
80 newbounds = Bounds2D( bounds.min + middle, bounds.max );
81 children.push_back(new QuadNode(tree, this, newbounds, depth));
82
83 for(std::list<QuadItem*>::iterator it = items.begin(); it != items.end(); it++) {
84 QuadItem* oi = *it;
85 tree->item_count--;
86 oi->node_count--;
87 addToChild(oi);
88 }
89
90 items.clear();
91
92 addToChild(item);
93 }
94
95
addToChild(QuadItem * item)96 void QuadNode::addToChild(QuadItem* item) {
97 if(children.empty()) return;
98
99 for(int i=0;i<4;i++) {
100 if(children[i]->bounds.overlaps(item->quadItemBounds)) {
101 children[i]->addItem(item);
102 }
103 }
104 }
105
106
getLeavesInFrustum(std::set<QuadNode * > & nodeset,Frustum & frustum)107 void QuadNode::getLeavesInFrustum(std::set<QuadNode*>& nodeset, Frustum& frustum) {
108
109 if(!items.empty()) {
110 nodeset.insert(this);
111 return;
112 }
113
114 if(children.empty()) return;
115
116 //for each 4 corners
117 for(int i=0;i<4;i++) {
118 if(!children[i]->empty() && frustum.intersects(children[i]->bounds)) {
119 children[i]->getLeavesInFrustum(nodeset, frustum);
120 }
121 }
122
123 return;
124 }
125
126
getItemsInFrustum(std::set<QuadItem * > & itemset,Frustum & frustum)127 int QuadNode::getItemsInFrustum(std::set<QuadItem*>& itemset, Frustum& frustum) {
128
129 if(!items.empty()) {
130 int items_added = 0;
131 for(std::list<QuadItem*>::iterator it = items.begin(); it != items.end(); it++) {
132 QuadItem* oi = (*it);
133
134 if(oi!=0) {
135 itemset.insert(oi);
136 items_added++;
137 }
138 }
139 return items_added;
140 }
141
142 if(children.empty()) return 0;
143
144 int count = 0;
145
146 //for each 4 corners
147 for(int i=0;i<4;i++) {
148 if(!children[i]->empty() && frustum.intersects(children[i]->bounds)) {
149 count += children[i]->getItemsInFrustum(itemset, frustum);
150 }
151 }
152
153 return count;
154 }
155
156
getItemsInBounds(std::set<QuadItem * > & itemset,Bounds2D & bounds) const157 int QuadNode::getItemsInBounds(std::set<QuadItem*>& itemset, Bounds2D& bounds) const{
158
159 if(!items.empty()) {
160 int items_added = 0;
161
162 for(std::list<QuadItem*>::const_iterator it = items.begin(); it != items.end(); it++) {
163 QuadItem* oi = (*it);
164 itemset.insert(oi);
165 items_added++;
166 }
167
168 return items_added;
169 }
170
171 if(children.empty()) return 0;
172
173 int count = 0;
174
175 //for each 4 corners
176 for(int i=0;i<4;i++) {
177 if(!children[i]->empty() && bounds.overlaps(children[i]->bounds)) {
178 count += children[i]->getItemsInBounds(itemset, bounds);
179 }
180 }
181
182 return count;
183 }
184
185
186
187
getItemsAt(std::set<QuadItem * > & itemset,vec2 pos)188 int QuadNode::getItemsAt(std::set<QuadItem*>& itemset, vec2 pos) {
189
190 if(!items.empty()) {
191 int items_added = 0;
192 for(std::list<QuadItem*>::iterator it = items.begin(); it != items.end(); it++) {
193 QuadItem* oi = (*it);
194 if(oi!=0) {
195 itemset.insert(oi);
196 items_added++;
197 }
198 }
199 return items_added;
200 }
201
202 if(children.empty()) return 0;
203
204 int index = getChildIndex(pos);
205
206 if(index == -1) return 0;
207
208 return children[index]->getItemsAt(itemset, pos);
209 }
210
visitLeavesInFrustum(const Frustum & frustum,VisitFunctor<QuadNode> & visit)211 void QuadNode::visitLeavesInFrustum(const Frustum& frustum, VisitFunctor<QuadNode> & visit){
212
213 if(!items.empty()) {
214
215 visit(this);
216
217 }else if(!children.empty()){
218
219 //visit each corner
220 for(int i=0;i<4;i++)
221 if(!children[i]->empty() && frustum.intersects(children[i]->bounds))
222 children[i]->visitLeavesInFrustum(frustum, visit);
223
224 }
225
226 }
227
228
visitItemsInFrustum(const Frustum & frustum,VisitFunctor<QuadItem> & visit)229 void QuadNode::visitItemsInFrustum(const Frustum & frustum, VisitFunctor<QuadItem> & visit){
230
231 if(!items.empty()) {
232
233 for(std::list<QuadItem*>::const_iterator it = items.begin(); it != items.end(); it++)
234 visit(*it);
235
236 }else if(!children.empty()){
237
238 //visit each corner
239 for(int i=0;i<4;i++)
240 if(!children[i]->empty() && frustum.intersects(children[i]->bounds))
241 children[i]->visitItemsInFrustum(frustum, visit);
242
243 }
244
245 }
246
247
visitItemsInBounds(const Bounds2D & bounds,VisitFunctor<QuadItem> & visit)248 void QuadNode::visitItemsInBounds(const Bounds2D & bounds, VisitFunctor<QuadItem> & visit){
249
250 if(!items.empty()) {
251
252 for(std::list<QuadItem*>::const_iterator it = items.begin(); it != items.end(); it++)
253 visit(*it);
254
255 }else if(!children.empty()){
256
257 //visit each corner
258 for(int i=0;i<4;i++)
259 if(!children[i]->empty() && bounds.overlaps(children[i]->bounds))
260 children[i]->visitItemsInBounds(bounds, visit);
261
262 }
263
264 }
265
visitItemsAt(const vec2 & pos,VisitFunctor<QuadItem> & visit)266 void QuadNode::visitItemsAt(const vec2 & pos, VisitFunctor<QuadItem> & visit){
267
268 if(!items.empty()){
269
270 for(std::list<QuadItem*>::const_iterator it = items.begin(); it != items.end(); it++)
271 if(*it) visit(*it);
272
273 }else if(!children.empty()){
274
275 int index = getChildIndex(pos);
276 if(index != -1) children[index]->visitItemsAt(pos, visit);
277
278 }
279
280 }
281
empty()282 bool QuadNode::empty() {
283 return (items.empty() && children.empty());
284 }
285
286
getChildIndex(const vec2 & pos) const287 int QuadNode::getChildIndex(const vec2 & pos) const{
288
289 if(children.empty()) return -1;
290
291 for(int i=0;i<4;i++) {
292 if(children[i]->bounds.contains(pos)) {
293 return i;
294 }
295 }
296
297 return -1;
298 }
299
300
301
QuadNode(QuadTree * tree,QuadNode * parent,Bounds2D bounds,int parent_depth)302 QuadNode::QuadNode(QuadTree* tree, QuadNode* parent, Bounds2D bounds, int parent_depth) {
303
304 this->parent = parent;
305 this->tree = tree;
306 this->bounds = bounds;
307 this->depth = parent_depth + 1;
308
309 listid = 0;
310
311 tree->node_count++;
312 }
313
314
~QuadNode()315 QuadNode::~QuadNode() {
316
317 if(listid) glDeleteLists(listid, 1);
318
319 if(!children.empty()) {
320 for(int i=0;i<4;i++) {
321 delete children[i];
322 }
323 }
324
325 tree->item_count -= items.size();
326
327 items.clear();
328
329 tree->node_count--;
330 }
331
332
usedChildren()333 int QuadNode::usedChildren() {
334 int populated = 0;
335
336 if(!children.empty()) {
337 for(int i=0;i<4;i++) {
338 if(!children[i]->empty()) populated++;
339 }
340 }
341
342 return populated;
343 }
344
345
draw(Frustum & frustum)346 int QuadNode::draw(Frustum& frustum) {
347
348 if(listid && !items.empty()) {
349 glPushMatrix();
350 glCallList(listid);
351 glPopMatrix();
352 return 1;
353 }
354
355 int drawn = 0;
356
357 if(!children.empty()) {
358 for(int i=0;i<4;i++) {
359 QuadNode* c = children[i];
360 if(!c->empty() && frustum.intersects(c->bounds)) {
361 drawn += c->draw(frustum);
362 }
363 }
364 }
365
366 return drawn;
367 }
368
369
generateLists()370 void QuadNode::generateLists() {
371
372 if(!items.empty()) {
373 if(!listid) listid = glGenLists(1);
374
375 glNewList(listid, GL_COMPILE);
376
377 for(std::list<QuadItem*>::iterator it = items.begin(); it != items.end(); it++) {
378 QuadItem* oi = (*it);
379 oi->drawQuadItem();
380 }
381
382 glEndList();
383 return;
384 }
385
386 if(!children.empty()) {
387 for(int i=0;i<4;i++) {
388 QuadNode* c = children[i];
389 if(!c->empty()) {
390 c->generateLists();
391 }
392 }
393 }
394 }
395
396
outline()397 void QuadNode::outline() {
398 //bounds.draw();
399
400 if(!items.empty()) {
401 bounds.draw();
402 /*glBegin(GL_LINES);
403 glVertex2fv(bounds.min);
404 glVertex2fv(bounds.max);
405 glEnd();*/
406 }
407
408 if(children.empty()) return;
409
410 for(int i=0;i<4;i++) {
411 QuadNode* c = children[i];
412 if(c!=0) {
413 c->outline();
414 }
415 }
416 }
417
outlineItems()418 void QuadNode::outlineItems() {
419 if(items.empty() && children.empty()) return;
420
421 for(std::list<QuadItem*>::iterator it = items.begin(); it != items.end(); it++) {
422 QuadItem* oi = (*it);
423 oi->quadItemBounds.draw();
424 }
425
426 if(children.empty()) return;
427
428 for(int i=0;i<4;i++) {
429 QuadNode* c = children[i];
430 if(c!=0) {
431 c->outlineItems();
432 }
433 }
434 }
435 //Quad TREE
436
437
QuadTree(Bounds2D bounds,int max_node_depth,int max_node_items)438 QuadTree::QuadTree(Bounds2D bounds, int max_node_depth, int max_node_items) {
439 item_count = 0;
440 node_count = 0;
441 unique_item_count = 0;
442
443 this->max_node_depth = max_node_depth;
444 this->max_node_items = max_node_items;
445
446 root = new QuadNode(this, 0, bounds, 0);
447 }
448
449
~QuadTree()450 QuadTree::~QuadTree() {
451 delete root;
452 }
453
454
getItemsAt(std::set<QuadItem * > & itemset,vec2 pos)455 int QuadTree::getItemsAt(std::set<QuadItem*>& itemset, vec2 pos) {
456 int return_count = root->getItemsAt(itemset, pos);
457
458 return return_count;
459 }
460
getItemsInFrustum(std::set<QuadItem * > & itemset,Frustum & frustum)461 int QuadTree::getItemsInFrustum(std::set<QuadItem*>& itemset, Frustum& frustum) {
462 return root->getItemsInFrustum(itemset, frustum);
463 }
464
465
getItemsInBounds(std::set<QuadItem * > & itemset,Bounds2D & bounds) const466 int QuadTree::getItemsInBounds(std::set<QuadItem*>& itemset, Bounds2D& bounds) const{
467 return root->getItemsInBounds(itemset, bounds);
468 }
469
470
getLeavesInFrustum(std::set<QuadNode * > & nodeset,Frustum & frustum)471 void QuadTree::getLeavesInFrustum(std::set<QuadNode*>& nodeset, Frustum& frustum) {
472 return root->getLeavesInFrustum(nodeset, frustum);
473 }
474
475
visitItemsAt(const vec2 & pos,VisitFunctor<QuadItem> & visit)476 void QuadTree::visitItemsAt(const vec2 & pos, VisitFunctor<QuadItem> & visit){
477 return root->visitItemsAt(pos, visit);
478 }
479
480
visitItemsInFrustum(const Frustum & frustum,VisitFunctor<QuadItem> & visit)481 void QuadTree::visitItemsInFrustum(const Frustum & frustum, VisitFunctor<QuadItem> & visit){
482 root->visitItemsInFrustum(frustum, visit);
483 }
484
485
visitItemsInBounds(const Bounds2D & bounds,VisitFunctor<QuadItem> & visit)486 void QuadTree::visitItemsInBounds(const Bounds2D & bounds, VisitFunctor<QuadItem> & visit){
487 root->visitItemsInBounds(bounds, visit);
488 }
489
490
visitLeavesInFrustum(const Frustum & frustum,VisitFunctor<QuadNode> & visit)491 void QuadTree::visitLeavesInFrustum(const Frustum& frustum, VisitFunctor<QuadNode> & visit){
492 root->visitLeavesInFrustum(frustum, visit);
493 }
494
495
addItem(QuadItem * item)496 void QuadTree::addItem(QuadItem* item) {
497 item->node_count = 0;
498 root->addItem(item);
499 unique_item_count++;
500 }
501
502
drawNodesInFrustum(Frustum & frustum)503 int QuadTree::drawNodesInFrustum(Frustum& frustum) {
504 return root->draw(frustum);
505 }
506
507
generateLists()508 void QuadTree::generateLists() {
509 root->generateLists();
510 }
511
512
outline()513 void QuadTree::outline() {
514 root->outline();
515 }
516
outlineItems()517 void QuadTree::outlineItems() {
518 root->outlineItems();
519 }
520