]>
Dogcows Code - chaz/yoink/blob - src/Moof/Octree.hh
88dae7ac6492e587d1bb133516a27b4343d98735
2 /*******************************************************************************
4 Copyright (c) 2009, Charles McGarvey
7 Redistribution and use in source and binary forms, with or without
8 modification, are permitted provided that the following conditions are met:
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.
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.
27 *******************************************************************************/
29 #ifndef _MOOF_OCTREE_HH_
30 #define _MOOF_OCTREE_HH_
35 #include <boost/shared_ptr.hpp>
37 #include <stlplus/ntree.hpp>
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>
51 struct OctreeInsertable
53 virtual ~OctreeInsertable() {}
55 virtual bool isInsideAabb(const Aabb
& aabb
) const = 0;
56 virtual int getOctant(const Aabb
& aabb
) const = 0;
61 class Octree
: public Entity
63 typedef boost::shared_ptr
<T
> InsertableP
;
65 struct Node
: public Entity
67 std::list
<InsertableP
> objects
;
72 Node(const Aabb
& box
) :
75 sphere
.point
= aabb
.getCenter();
76 sphere
.radius
= (aabb
.min
- sphere
.point
).length();
79 void draw(Scalar alpha
) const
84 void drawIfVisible(Scalar alpha
, const Frustum
& frustum
) const
86 if (isVisible(frustum
))
94 logDebug("size of node %d", objects
.size());
97 void getAll(std::list
<InsertableP
>& insertables
) const
99 insertables
.insert(insertables
.end(), objects
.begin(),
103 void getIfVisible(std::list
<InsertableP
>& insertables
,
104 const Frustum
& frustum
) const
106 typename
std::list
<InsertableP
>::const_iterator it
;
108 for (it
= objects
.begin(); it
!= objects
.end(); ++it
)
110 if ((*it
)->isVisible(frustum
)) insertables
.push_back(*it
);
115 bool isVisible(const Frustum
& frustum
) const
117 if (sphere
.isVisible(frustum
))
119 return aabb
.isVisible(frustum
);
129 typedef boost::shared_ptr
<Octree
> Ptr
;
130 typedef typename
stlplus::ntree
<Node
>::iterator NodeP
;
135 NodeP
insert(InsertableP entity
, NodeP node
)
137 ASSERT(node
.valid() && "invalid node passed");
138 ASSERT(entity
&& "null entity passed");
140 if (entity
->isInsideAabb(node
->aabb
))
142 return insert_recurse(entity
, node
);
146 node
->objects
.push_back(entity
);
151 NodeP
insert_recurse(InsertableP entity
, NodeP node
)
153 ASSERT(node
.valid() && "invalid node passed");
154 ASSERT(entity
&& "null entity passed");
156 int octantNum
= entity
->getOctant(node
->aabb
);
159 node
->objects
.push_back(entity
);
164 if ((int)tree_
.children(node
) <= octantNum
)
166 addChild(node
, octantNum
);
169 NodeP child
= tree_
.child(node
, octantNum
);
170 ASSERT(child
.valid() && "expected valid child node");
172 return insert_recurse(entity
, child
);
176 void addChild(NodeP node
, int index
)
178 ASSERT(node
.valid() && "invalid node passed");
182 for (int i
= tree_
.children(node
); i
<= index
; ++i
)
184 node
->aabb
.getOctant(octant
, i
);
185 tree_
.append(node
, octant
);
190 void getNearbyObjects(std::list
<InsertableP
>& insertables
,
191 const OctreeInsertable
& entity
, NodeP node
) const
193 ASSERT(node
.valid() && "invalid node passed");
197 int octantNum
= entity
.getOctant(node
->aabb
);
200 node
->getAll(insertables
);
202 if (octantNum
< (int)tree_
.children(node
))
204 NodeP child
= tree_
.child(node
, octantNum
);
205 ASSERT(child
.valid() && "expected valid child node");
207 getNearbyObjects(insertables
, entity
, child
);
212 logDebug("getting all the rest...");
213 getAll(insertables
, node
);
218 void getAll(std::list
<InsertableP
>& insertables
, NodeP node
) const
220 ASSERT(node
.valid() && "invalid node passed");
222 node
->getAll(insertables
);
224 for (unsigned i
= 0; i
< tree_
.children(node
); ++i
)
226 NodeP child
= tree_
.child(node
, i
);
227 ASSERT(child
.valid() && "expected valid child node");
229 getAll(insertables
, child
);
233 void getIfVisible(std::list
<InsertableP
>& insertables
,
234 const Frustum
& frustum
, NodeP node
) const
236 ASSERT(node
.valid() && "invalid node passed");
238 // try to cull by sphere
239 Frustum::Collision collision
= frustum
.contains(node
->sphere
);
240 if (collision
== Frustum::OUTSIDE
) return;
242 // try to cull by aabb
243 collision
= frustum
.contains(node
->aabb
);
244 if (collision
== Frustum::OUTSIDE
) return;
247 if (collision
== Frustum::INSIDE
)
249 node
->getAll(insertables
);
251 else // collision == Frustum::INTERSECT
253 node
->getIfVisible(insertables
, frustum
);
256 if (tree_
.children(node
) > 0)
258 if (collision
== Frustum::INSIDE
)
260 for (unsigned i
= 0; i
< tree_
.children(node
); ++i
)
262 NodeP child
= tree_
.child(node
, i
);
263 ASSERT(child
.valid() && "expected valid child node");
265 getAll(insertables
, child
);
268 else // collision == Frustum::INTERSECT
270 for (unsigned i
= 0; i
< tree_
.children(node
); ++i
)
272 NodeP child
= tree_
.child(node
, i
);
273 ASSERT(child
.valid() && "expected valid child node");
275 getIfVisible(insertables
, frustum
, child
);
282 mutable stlplus::ntree
<Node
> tree_
;
287 void print(NodeP node
)
290 logInfo("depth to node: %d", tree_
.depth(node
));
291 logInfo("size of node: %d", tree_
.size(node
));
294 static Ptr
alloc(const Node
& rootNode
)
296 return Ptr(new Octree(rootNode
));
299 explicit Octree(const Node
& rootNode
)
301 tree_
.insert(rootNode
);
305 NodeP
insert(InsertableP entity
)
307 return insert(entity
, tree_
.root());
310 void remove(InsertableP entity
, NodeP node
)
312 ASSERT(entity
&& "null entity passed");
313 ASSERT(node
.valid() && "invalid node passed");
315 typename
std::list
<InsertableP
>::iterator it
;
316 it
= std::find(node
->objects
.begin(), node
->objects
.end(), entity
);
318 if (it
!= node
->objects
.end())
320 node
->objects
.erase(it
);
325 NodeP
reinsert(InsertableP entity
, NodeP node
)
327 remove(entity
, node
);
328 return insert(entity
);
332 void draw(Scalar alpha
) const
334 std::list
<InsertableP
> objects
;
337 typename
std::list
<InsertableP
>::const_iterator it
;
338 for (it
= objects
.begin(); it
!= objects
.end(); ++it
)
344 void drawIfVisible(Scalar alpha
, const Frustum
& frustum
) const
346 std::list
<InsertableP
> objects
;
347 //getIfVisible(objects, frustum);
348 getNearbyObjects(objects
, *savedObj
);
350 typename
std::list
<InsertableP
>::const_iterator it
;
351 for (it
= objects
.begin(); it
!= objects
.end(); ++it
)
358 void getAll(std::list
<InsertableP
>& insertables
) const
360 getAll(insertables
, tree_
.root());
363 void getIfVisible(std::list
<InsertableP
>& insertables
,
364 const Frustum
& frustum
) const
366 getIfVisible(insertables
, frustum
, tree_
.root());
369 mutable const OctreeInsertable
* savedObj
;
372 void getNearbyObjects(std::list
<InsertableP
>& insertables
,
373 const OctreeInsertable
& entity
) const
375 logDebug("--- GETTING NEARBY");
376 getNearbyObjects(insertables
, entity
, tree_
.root());
385 #endif // _MOOF_OCTREE_HH_
387 /** vim: set ts=4 sw=4 tw=80: *************************************************/
This page took 0.051366 seconds and 4 git commands to generate.