cdac62a29071f4eeaeb51c48c055e84db1a029dc
[chaz/yoink] / src / Moof / Octree.hh
1
2 /*******************************************************************************
3
4 Copyright (c) 2009, Charles McGarvey
5 All rights reserved.
6
7 Redistribution and use in source and binary forms, with or without
8 modification, are permitted provided that the following conditions are met:
9
10 * Redistributions of source code must retain the above copyright notice,
11 this list of conditions and the following disclaimer.
12 * Redistributions in binary form must reproduce the above copyright notice,
13 this list of conditions and the following disclaimer in the documentation
14 and/or other materials provided with the distribution.
15
16 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
17 AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
18 IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
19 DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
20 FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
21 DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
22 SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
23 CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
24 OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
25 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
26
27 *******************************************************************************/
28
29 #ifndef _MOOF_OCTREE_HH_
30 #define _MOOF_OCTREE_HH_
31
32 #include <algorithm>
33 #include <list>
34
35 #include <boost/shared_ptr.hpp>
36
37 #include <stlplus/ntree.hpp>
38
39 #include <Moof/Aabb.hh>
40 #include <Moof/Drawable.hh>
41 #include <Moof/Entity.hh>
42 #include <Moof/Frustum.hh>
43 #include <Moof/Log.hh>
44 #include <Moof/Math.hh>
45 #include <Moof/Sphere.hh>
46
47
48 namespace Mf {
49
50
51 //class Octree;
52 //typedef boost::shared_ptr<Octree> OctreeP;
53
54 //class Octree::Node;
55 //typedef stlplus::ntree<Octree::Node>::iterator OctreeNodeP;
56
57
58 struct OctreeInsertable
59 {
60 virtual ~OctreeInsertable() {}
61
62 virtual bool isInsideAabb(const Aabb& aabb) const = 0;
63 virtual int getOctant(const Aabb& aabb) const = 0;
64 };
65
66
67 template <class T>
68 class Octree : public Entity
69 {
70 typedef boost::shared_ptr<T> InsertableP;
71
72 struct Node : public Entity
73 {
74 std::list<InsertableP> objects;
75
76 Aabb aabb;
77 Sphere sphere;
78
79 Node(const Aabb& box) :
80 aabb(box)
81 {
82 sphere.point = aabb.getCenter();
83 sphere.radius = (aabb.min - sphere.point).length();
84 }
85
86 void draw(Scalar alpha) const
87 {
88 typename std::list<InsertableP>::const_iterator it;
89
90 for (it = objects.begin(); it != objects.end(); ++it)
91 {
92 (*it)->draw(alpha);
93 }
94
95 if (!objects.empty())
96 aabb.draw(); // temporary
97 }
98
99 void drawIfVisible(Scalar alpha, const Frustum& frustum) const
100 {
101 typename std::list<InsertableP>::const_iterator it;
102
103 for (it = objects.begin(); it != objects.end(); ++it)
104 {
105 (*it)->drawIfVisible(alpha, frustum);
106 }
107
108 if (!objects.empty())
109 {
110 //aabb.draw();
111 //sphere.draw();
112 }
113 }
114
115
116 bool isVisible(const Frustum& frustum) const
117 {
118 if (sphere.isVisible(frustum))
119 {
120 return aabb.isVisible(frustum);
121 }
122
123 return false;
124 }
125 };
126
127
128 public:
129
130 typedef boost::shared_ptr<Octree> Ptr;
131 typedef typename stlplus::ntree<Node>::iterator NodeP;
132
133 private:
134
135
136 NodeP insert(InsertableP entity, NodeP node)
137 {
138 ASSERT(node.valid() && "invalid node passed");
139 ASSERT(entity && "null entity passed");
140
141 if (entity->isInsideAabb(node->aabb))
142 {
143 return insert_recurse(entity, node);
144 }
145 else
146 {
147 node->objects.push_back(entity);
148 return node;
149 }
150 }
151
152 NodeP insert_recurse(InsertableP entity, NodeP node)
153 {
154 ASSERT(node.valid() && "invalid node passed");
155 ASSERT(entity && "null entity passed");
156
157 int octantNum = entity->getOctant(node->aabb);
158 if (octantNum == -1)
159 {
160 node->objects.push_back(entity);
161 return node;
162 }
163 else
164 {
165 if ((int)tree_.children(node) <= octantNum)
166 {
167 addChild(node, octantNum);
168 }
169
170 NodeP child = tree_.child(node, octantNum);
171 ASSERT(child.valid() && "expected valid child node");
172
173 return insert(entity, child);
174 }
175 }
176
177 void addChild(NodeP node, int index)
178 {
179 ASSERT(node.valid() && "invalid node passed");
180
181 Aabb octant;
182
183 for (int i = tree_.children(node); i <= index; ++i)
184 {
185 node->aabb.getOctant(octant, i);
186 tree_.append(node, octant);
187 }
188 }
189
190
191 void draw(Scalar alpha, NodeP node) const
192 {
193 ASSERT(node.valid() && "invalid node passed");
194
195 node->draw(alpha);
196
197 for (unsigned i = 0; i < tree_.children(node); ++i)
198 {
199 NodeP child = tree_.child(node, i);
200 ASSERT(child.valid() && "expected valid child node");
201
202 draw(alpha, child);
203 }
204 }
205
206 void drawIfVisible(Scalar alpha, const Frustum& frustum, NodeP node) const
207 {
208 ASSERT(node.valid() && "invalid node passed");
209
210 // try to cull by sphere
211 Frustum::Collision collision = frustum.contains(node->sphere);
212 if (collision == Frustum::OUTSIDE) return;
213
214 // try to cull by aabb
215 collision = frustum.contains(node->aabb);
216 if (collision == Frustum::OUTSIDE) return;
217
218
219 if (collision == Frustum::INSIDE)
220 {
221 node->draw(alpha);
222 }
223 else // collision == Frustum::INTERSECT
224 {
225 node->drawIfVisible(alpha, frustum);
226 }
227
228 if (tree_.children(node) > 0)
229 {
230 if (collision == Frustum::INSIDE)
231 {
232 for (unsigned i = 0; i < tree_.children(node); ++i)
233 {
234 NodeP child = tree_.child(node, i);
235 ASSERT(child.valid() && "expected valid child node");
236
237 draw(alpha, child);
238 }
239 }
240 else // collision == Frustum::INTERSECT
241 {
242 for (unsigned i = 0; i < tree_.children(node); ++i)
243 {
244 NodeP child = tree_.child(node, i);
245 ASSERT(child.valid() && "expected valid child node");
246
247 drawIfVisible(alpha, frustum, child);
248 }
249 }
250 }
251 }
252
253 mutable stlplus::ntree<Node> tree_;
254
255
256 public:
257
258 void print(NodeP node)
259 {
260 //logDebug("-----");
261 //logDebug("depth to node: %d", tree_.depth(node));
262 //logDebug("size of node: %d", tree_.size(node));
263 }
264
265 static Ptr alloc(const Node& rootNode)
266 {
267 return Ptr(new Octree(rootNode));
268 }
269
270 explicit Octree(const Node& rootNode)
271 {
272 tree_.insert(rootNode);
273 }
274
275 NodeP insert(InsertableP entity)
276 {
277 return insert(entity, tree_.root());
278 }
279
280 NodeP reinsert(InsertableP entity, NodeP node)
281 {
282 ASSERT(entity && "null entity passed");
283 ASSERT(node.valid() && "invalid node passed");
284
285 typename std::list<InsertableP>::iterator it;
286 it = std::find(node->objects.begin(), node->objects.end(), entity);
287
288 if (it != node->objects.end())
289 {
290 node->objects.erase(it);
291 }
292
293 return insert(entity);
294 }
295
296 void draw(Scalar alpha) const
297 {
298 draw(alpha, tree_.root());
299 }
300
301 void drawIfVisible(Scalar alpha, const Frustum& frustum) const
302 {
303 drawIfVisible(alpha, frustum, tree_.root());
304 }
305 };
306
307
308 } // namespace Mf
309
310 #endif // _MOOF_OCTREE_HH_
311
312 /** vim: set ts=4 sw=4 tw=80: *************************************************/
313
This page took 0.042031 seconds and 3 git commands to generate.