88dae7ac6492e587d1bb133516a27b4343d98735
[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 struct OctreeInsertable
52 {
53 virtual ~OctreeInsertable() {}
54
55 virtual bool isInsideAabb(const Aabb& aabb) const = 0;
56 virtual int getOctant(const Aabb& aabb) const = 0;
57 };
58
59
60 template <class T>
61 class Octree : public Entity
62 {
63 typedef boost::shared_ptr<T> InsertableP;
64
65 struct Node : public Entity
66 {
67 std::list<InsertableP> objects;
68
69 Aabb aabb;
70 Sphere sphere;
71
72 Node(const Aabb& box) :
73 aabb(box)
74 {
75 sphere.point = aabb.getCenter();
76 sphere.radius = (aabb.min - sphere.point).length();
77 }
78
79 void draw(Scalar alpha) const
80 {
81 aabb.draw(alpha);
82 }
83
84 void drawIfVisible(Scalar alpha, const Frustum& frustum) const
85 {
86 if (isVisible(frustum))
87 {
88 aabb.draw(alpha);
89 }
90 }
91
92 void printSize()
93 {
94 logDebug("size of node %d", objects.size());
95 }
96
97 void getAll(std::list<InsertableP>& insertables) const
98 {
99 insertables.insert(insertables.end(), objects.begin(),
100 objects.end());
101 }
102
103 void getIfVisible(std::list<InsertableP>& insertables,
104 const Frustum& frustum) const
105 {
106 typename std::list<InsertableP>::const_iterator it;
107
108 for (it = objects.begin(); it != objects.end(); ++it)
109 {
110 if ((*it)->isVisible(frustum)) insertables.push_back(*it);
111 }
112 }
113
114
115 bool isVisible(const Frustum& frustum) const
116 {
117 if (sphere.isVisible(frustum))
118 {
119 return aabb.isVisible(frustum);
120 }
121
122 return false;
123 }
124 };
125
126
127 public:
128
129 typedef boost::shared_ptr<Octree> Ptr;
130 typedef typename stlplus::ntree<Node>::iterator NodeP;
131
132 private:
133
134
135 NodeP insert(InsertableP entity, NodeP node)
136 {
137 ASSERT(node.valid() && "invalid node passed");
138 ASSERT(entity && "null entity passed");
139
140 if (entity->isInsideAabb(node->aabb))
141 {
142 return insert_recurse(entity, node);
143 }
144 else
145 {
146 node->objects.push_back(entity);
147 return node;
148 }
149 }
150
151 NodeP insert_recurse(InsertableP entity, NodeP node)
152 {
153 ASSERT(node.valid() && "invalid node passed");
154 ASSERT(entity && "null entity passed");
155
156 int octantNum = entity->getOctant(node->aabb);
157 if (octantNum == -1)
158 {
159 node->objects.push_back(entity);
160 return node;
161 }
162 else
163 {
164 if ((int)tree_.children(node) <= octantNum)
165 {
166 addChild(node, octantNum);
167 }
168
169 NodeP child = tree_.child(node, octantNum);
170 ASSERT(child.valid() && "expected valid child node");
171
172 return insert_recurse(entity, child);
173 }
174 }
175
176 void addChild(NodeP node, int index)
177 {
178 ASSERT(node.valid() && "invalid node passed");
179
180 Aabb octant;
181
182 for (int i = tree_.children(node); i <= index; ++i)
183 {
184 node->aabb.getOctant(octant, i);
185 tree_.append(node, octant);
186 }
187 }
188
189
190 void getNearbyObjects(std::list<InsertableP>& insertables,
191 const OctreeInsertable& entity, NodeP node) const
192 {
193 ASSERT(node.valid() && "invalid node passed");
194
195 node->printSize();
196
197 int octantNum = entity.getOctant(node->aabb);
198 if (octantNum != -1)
199 {
200 node->getAll(insertables);
201
202 if (octantNum < (int)tree_.children(node))
203 {
204 NodeP child = tree_.child(node, octantNum);
205 ASSERT(child.valid() && "expected valid child node");
206
207 getNearbyObjects(insertables, entity, child);
208 }
209 }
210 else
211 {
212 logDebug("getting all the rest...");
213 getAll(insertables, node);
214 }
215 }
216
217
218 void getAll(std::list<InsertableP>& insertables, NodeP node) const
219 {
220 ASSERT(node.valid() && "invalid node passed");
221
222 node->getAll(insertables);
223
224 for (unsigned i = 0; i < tree_.children(node); ++i)
225 {
226 NodeP child = tree_.child(node, i);
227 ASSERT(child.valid() && "expected valid child node");
228
229 getAll(insertables, child);
230 }
231 }
232
233 void getIfVisible(std::list<InsertableP>& insertables,
234 const Frustum& frustum, NodeP node) const
235 {
236 ASSERT(node.valid() && "invalid node passed");
237
238 // try to cull by sphere
239 Frustum::Collision collision = frustum.contains(node->sphere);
240 if (collision == Frustum::OUTSIDE) return;
241
242 // try to cull by aabb
243 collision = frustum.contains(node->aabb);
244 if (collision == Frustum::OUTSIDE) return;
245
246
247 if (collision == Frustum::INSIDE)
248 {
249 node->getAll(insertables);
250 }
251 else // collision == Frustum::INTERSECT
252 {
253 node->getIfVisible(insertables, frustum);
254 }
255
256 if (tree_.children(node) > 0)
257 {
258 if (collision == Frustum::INSIDE)
259 {
260 for (unsigned i = 0; i < tree_.children(node); ++i)
261 {
262 NodeP child = tree_.child(node, i);
263 ASSERT(child.valid() && "expected valid child node");
264
265 getAll(insertables, child);
266 }
267 }
268 else // collision == Frustum::INTERSECT
269 {
270 for (unsigned i = 0; i < tree_.children(node); ++i)
271 {
272 NodeP child = tree_.child(node, i);
273 ASSERT(child.valid() && "expected valid child node");
274
275 getIfVisible(insertables, frustum, child);
276 }
277 }
278 }
279 }
280
281
282 mutable stlplus::ntree<Node> tree_;
283
284
285 public:
286
287 void print(NodeP node)
288 {
289 logInfo("-----");
290 logInfo("depth to node: %d", tree_.depth(node));
291 logInfo("size of node: %d", tree_.size(node));
292 }
293
294 static Ptr alloc(const Node& rootNode)
295 {
296 return Ptr(new Octree(rootNode));
297 }
298
299 explicit Octree(const Node& rootNode)
300 {
301 tree_.insert(rootNode);
302 }
303
304
305 NodeP insert(InsertableP entity)
306 {
307 return insert(entity, tree_.root());
308 }
309
310 void remove(InsertableP entity, NodeP node)
311 {
312 ASSERT(entity && "null entity passed");
313 ASSERT(node.valid() && "invalid node passed");
314
315 typename std::list<InsertableP>::iterator it;
316 it = std::find(node->objects.begin(), node->objects.end(), entity);
317
318 if (it != node->objects.end())
319 {
320 node->objects.erase(it);
321 }
322 }
323
324
325 NodeP reinsert(InsertableP entity, NodeP node)
326 {
327 remove(entity, node);
328 return insert(entity);
329 }
330
331
332 void draw(Scalar alpha) const
333 {
334 std::list<InsertableP> objects;
335 getAll(objects);
336
337 typename std::list<InsertableP>::const_iterator it;
338 for (it = objects.begin(); it != objects.end(); ++it)
339 {
340 (*it)->draw(alpha);
341 }
342 }
343
344 void drawIfVisible(Scalar alpha, const Frustum& frustum) const
345 {
346 std::list<InsertableP> objects;
347 //getIfVisible(objects, frustum);
348 getNearbyObjects(objects, *savedObj);
349
350 typename std::list<InsertableP>::const_iterator it;
351 for (it = objects.begin(); it != objects.end(); ++it)
352 {
353 (*it)->draw(alpha);
354 }
355 }
356
357
358 void getAll(std::list<InsertableP>& insertables) const
359 {
360 getAll(insertables, tree_.root());
361 }
362
363 void getIfVisible(std::list<InsertableP>& insertables,
364 const Frustum& frustum) const
365 {
366 getIfVisible(insertables, frustum, tree_.root());
367 }
368
369 mutable const OctreeInsertable* savedObj;
370
371
372 void getNearbyObjects(std::list<InsertableP>& insertables,
373 const OctreeInsertable& entity) const
374 {
375 logDebug("--- GETTING NEARBY");
376 getNearbyObjects(insertables, entity, tree_.root());
377 logDebug("---");
378 savedObj = &entity;
379 }
380 };
381
382
383 } // namespace Mf
384
385 #endif // _MOOF_OCTREE_HH_
386
387 /** vim: set ts=4 sw=4 tw=80: *************************************************/
388
This page took 0.047006 seconds and 3 git commands to generate.