]>
Dogcows Code - chaz/yoink/blob - src/Moof/Octree.hh
2 /*] Copyright (c) 2009-2010, Charles McGarvey [**************************
3 **] All rights reserved.
7 * Distributable under the terms and conditions of the 2-clause BSD license;
8 * see the file COPYING for a complete text of the license.
10 **************************************************************************/
12 #ifndef _MOOF_OCTREE_HH_
13 #define _MOOF_OCTREE_HH_
18 #include <boost/shared_ptr.hpp>
19 #include <stlplus/ntree.hpp>
21 #include <Moof/Aabb.hh>
22 #include <Moof/Drawable.hh>
23 #include <Moof/Entity.hh>
24 #include <Moof/Frustum.hh>
25 #include <Moof/Log.hh>
26 #include <Moof/Math.hh>
27 #include <Moof/Sphere.hh>
33 struct OctreeInsertable
35 virtual ~OctreeInsertable() {}
37 virtual int getOctant(const Aabb
<3>& aabb
) const = 0;
42 class Octree
: public Entity
44 typedef boost::shared_ptr
<T
> InsertableP
;
46 struct Node
: public Entity
48 std::list
<InsertableP
> objects
;
50 Node(const Aabb
<3>& aabb
)
53 mSphere
.point
= mAabb
.getCenter();
54 mSphere
.radius
= (mAabb
.min
- mSphere
.point
).length();
57 void draw(Scalar alpha
) const
64 logInfo
<< "size of node " << objects
.size() << std::endl
;
67 void getAll(std::list
<InsertableP
>& insertables
) const
69 insertables
.insert(insertables
.end(), objects
.begin(),
73 void getIfVisible(std::list
<InsertableP
>& insertables
,
74 const Frustum
& frustum
) const
76 typename
std::list
<InsertableP
>::const_iterator it
;
78 for (it
= objects
.begin(); it
!= objects
.end(); ++it
)
80 if ((*it
)->isVisible(frustum
)) insertables
.push_back(*it
);
88 typedef boost::shared_ptr
<Octree
> Ptr
;
89 typedef typename
stlplus::ntree
<Node
>::iterator NodeP
;
94 NodeP
insert(InsertableP entity
, NodeP node
)
96 ASSERT(node
.valid() && "invalid node passed");
97 ASSERT(entity
&& "null entity passed");
99 Aabb
<3> entityAabb
= entity
->getAabb();
100 Aabb
<3> nodeAabb
= node
->getAabb();
102 if (!(entityAabb
.max
[0] < nodeAabb
.max
[0] &&
103 entityAabb
.min
[0] > nodeAabb
.min
[0] &&
104 entityAabb
.max
[1] < nodeAabb
.max
[1] &&
105 entityAabb
.min
[1] > nodeAabb
.min
[1] &&
106 entityAabb
.max
[2] < nodeAabb
.max
[2] &&
107 entityAabb
.min
[2] > nodeAabb
.min
[2]))
109 node
->objects
.push_back(entity
);
114 return insert_recurse(entity
, node
);
118 NodeP
insert_recurse(InsertableP entity
, NodeP node
)
120 ASSERT(node
.valid() && "invalid node passed");
121 ASSERT(entity
&& "null entity passed");
123 int octantNum
= entity
->getOctant(node
->getAabb());
126 node
->objects
.push_back(entity
);
131 if ((int)mTree
.children(node
) <= octantNum
)
133 addChild(node
, octantNum
);
136 NodeP child
= mTree
.child(node
, octantNum
);
137 ASSERT(child
.valid() && "expected valid child node");
139 return insert_recurse(entity
, child
);
143 void addChild(NodeP node
, int index
)
145 ASSERT(node
.valid() && "invalid node passed");
149 for (int i
= mTree
.children(node
); i
<= index
; ++i
)
151 node
->getAabb().getOctant(octant
, i
);
152 mTree
.append(node
, octant
);
157 void getNearbyObjects(std::list
<InsertableP
>& insertables
,
158 const OctreeInsertable
& entity
, NodeP node
) const
160 ASSERT(node
.valid() && "invalid node passed");
164 int octantNum
= entity
.getOctant(node
->getAabb());
167 node
->getAll(insertables
);
169 if (octantNum
< (int)mTree
.children(node
))
171 NodeP child
= mTree
.child(node
, octantNum
);
172 ASSERT(child
.valid() && "expected valid child node");
174 getNearbyObjects(insertables
, entity
, child
);
179 logInfo("getting all the rest...");
180 getAll(insertables
, node
);
185 void getAll(std::list
<InsertableP
>& insertables
, NodeP node
) const
187 ASSERT(node
.valid() && "invalid node passed");
189 node
->getAll(insertables
);
191 for (unsigned i
= 0; i
< mTree
.children(node
); ++i
)
193 NodeP child
= mTree
.child(node
, i
);
194 ASSERT(child
.valid() && "expected valid child node");
196 getAll(insertables
, child
);
200 void getIfVisible(std::list
<InsertableP
>& insertables
,
201 const Frustum
& frustum
, NodeP node
) const
203 ASSERT(node
.valid() && "invalid node passed");
205 // try to cull by sphere
206 Frustum::Collision collision
= frustum
.contains(node
->getSphere());
207 if (collision
== Frustum::OUTSIDE
) return;
209 // try to cull by aabb
210 collision
= frustum
.contains(node
->getAabb());
211 if (collision
== Frustum::OUTSIDE
) return;
214 if (collision
== Frustum::INSIDE
)
216 node
->getAll(insertables
);
218 else // collision == Frustum::INTERSECT
220 node
->getIfVisible(insertables
, frustum
);
223 if (mTree
.children(node
) > 0)
225 if (collision
== Frustum::INSIDE
)
227 for (unsigned i
= 0; i
< mTree
.children(node
); ++i
)
229 NodeP child
= mTree
.child(node
, i
);
230 ASSERT(child
.valid() && "expected valid child node");
232 getAll(insertables
, child
);
235 else // collision == Frustum::INTERSECT
237 for (unsigned i
= 0; i
< mTree
.children(node
); ++i
)
239 NodeP child
= mTree
.child(node
, i
);
240 ASSERT(child
.valid() && "expected valid child node");
242 getIfVisible(insertables
, frustum
, child
);
249 mutable stlplus::ntree
<Node
> mTree
;
254 void print(NodeP node
)
257 logInfo
<< "depth to node: " << mTree
.depth(node
) << std::endl
;
258 logInfo
<< "size of node: " << mTree
.size(node
) << std::endl
;
261 static Ptr
alloc(const Node
& rootNode
)
263 return Ptr(new Octree(rootNode
));
266 explicit Octree(const Node
& rootNode
)
268 mTree
.insert(rootNode
);
272 NodeP
insert(InsertableP entity
)
274 return insert(entity
, mTree
.root());
277 void remove(InsertableP entity
, NodeP node
)
279 ASSERT(entity
&& "null entity passed");
280 ASSERT(node
.valid() && "invalid node passed");
282 typename
std::list
<InsertableP
>::iterator it
;
283 it
= std::find(node
->objects
.begin(), node
->objects
.end(), entity
);
285 if (it
!= node
->objects
.end())
287 node
->objects
.erase(it
);
292 NodeP
reinsert(InsertableP entity
, NodeP node
)
294 remove(entity
, node
);
295 return insert(entity
);
299 void draw(Scalar alpha
) const
301 std::list
<InsertableP
> objects
;
304 typename
std::list
<InsertableP
>::const_iterator it
;
305 for (it
= objects
.begin(); it
!= objects
.end(); ++it
)
311 void drawIfVisible(Scalar alpha
, const Frustum
& frustum
) const
313 std::list
<InsertableP
> objects
;
314 getIfVisible(objects
, frustum
);
315 //getNearbyObjects(objects, *savedObj);
317 typename
std::list
<InsertableP
>::const_iterator it
;
318 for (it
= objects
.begin(); it
!= objects
.end(); ++it
)
325 void getAll(std::list
<InsertableP
>& insertables
) const
327 getAll(insertables
, mTree
.root());
330 void getIfVisible(std::list
<InsertableP
>& insertables
,
331 const Frustum
& frustum
) const
333 getIfVisible(insertables
, frustum
, mTree
.root());
336 mutable const OctreeInsertable
* savedObj
;
339 void getNearbyObjects(std::list
<InsertableP
>& insertables
,
340 const OctreeInsertable
& entity
) const
342 logInfo("--- GETTING NEARBY");
343 getNearbyObjects(insertables
, entity
, mTree
.root());
352 #endif // _MOOF_OCTREE_HH_
This page took 0.046788 seconds and 4 git commands to generate.