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 #ifndef QUADTREE_H 29 #define QUADTREE_H 30 31 #include <set> 32 #include <list> 33 34 #include "gl.h" 35 #include "bounds.h" 36 #include "frustum.h" 37 38 class QuadItem { 39 public: 40 Bounds2D quadItemBounds; 41 int node_count; ~QuadItem()42 virtual ~QuadItem() {}; updateQuadItemBounds()43 virtual void updateQuadItemBounds() {}; drawQuadItem()44 virtual void drawQuadItem() {}; 45 }; 46 47 template <class Data> 48 class VisitFunctor{ 49 public: 50 virtual void operator()(Data *)=0; 51 }; 52 53 class QuadTree; 54 55 class QuadNode { 56 GLuint listid; 57 58 Bounds2D bounds; 59 60 std::vector<QuadNode*> children; 61 std::list<QuadItem*> items; 62 63 QuadTree* tree; 64 65 int getChildIndex(const vec2 & pos) const; 66 void addToChild(QuadItem* item); 67 68 int depth; 69 70 QuadNode* parent; 71 public: 72 bool allowMoreItems(); 73 int usedChildren(); 74 75 QuadNode(QuadTree* tree, QuadNode* parent, Bounds2D itembounds, int parent_depth); 76 ~QuadNode(); 77 78 void addItem(QuadItem* item); //if not subdivided, subdivide, add to correct subdivided node. 79 80 int getItemsAt(std::set<QuadItem*>& itemset, vec2 pos); 81 void getLeavesInFrustum(std::set<QuadNode*>& nodeset, Frustum& frustum); 82 int getItemsInFrustum(std::set<QuadItem*>& itemset, Frustum& frustum); 83 int getItemsInBounds(std::set<QuadItem*>& itemset, Bounds2D& bounds) const; 84 85 void visitItemsInFrustum(const Frustum & frustum, VisitFunctor<QuadItem> & visit); 86 void visitItemsInBounds(const Bounds2D & bounds, VisitFunctor<QuadItem> & visit); 87 void visitItemsAt(const vec2 & pos, VisitFunctor<QuadItem> & visit); 88 void visitLeavesInFrustum(const Frustum & frustum, VisitFunctor<QuadNode> & visit); 89 90 bool empty(); 91 void generateLists(); 92 int draw(Frustum& frustum); 93 void outline(); 94 void outlineItems(); 95 }; 96 97 98 class QuadTree { 99 Bounds2D bounds; 100 QuadNode* root; 101 public: 102 int unique_item_count; 103 int item_count; 104 int node_count; 105 int max_node_depth; 106 int max_node_items; 107 108 int getItemsAt(std::set<QuadItem*>& itemset, vec2 pos); 109 void getLeavesInFrustum(std::set<QuadNode*>& nodeset, Frustum& frustum); 110 int getItemsInFrustum(std::set<QuadItem*>& itemset, Frustum& frustum); 111 int getItemsInBounds(std::set<QuadItem*>& itemset, Bounds2D& bounds) const; 112 113 void visitItemsAt(const vec2 & pos, VisitFunctor<QuadItem> & visit); 114 void visitLeavesInFrustum(const Frustum & frustum, VisitFunctor<QuadNode> & visit); 115 void visitItemsInFrustum(const Frustum & frustum, VisitFunctor<QuadItem> & visit); 116 void visitItemsInBounds(const Bounds2D & bounds, VisitFunctor<QuadItem> & visit); 117 void addItem(QuadItem* item); 118 void generateLists(); 119 int drawNodesInFrustum(Frustum& frustum); 120 QuadTree(Bounds2D bounds, int max_node_depth, int max_node_items); 121 ~QuadTree(); 122 void outline(); 123 void outlineItems(); 124 }; 125 126 #endif 127