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