]>
Dogcows Code - chaz/yoink/blob - src/Moof/Octree.hh
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 int getOctant(const Aabb
& aabb
) const = 0;
60 class Octree
: public Entity
62 typedef boost::shared_ptr
<T
> InsertableP
;
64 struct Node
: public Entity
66 std::list
<InsertableP
> objects
;
68 Node(const Aabb
& aabb
)
71 mSphere
.point
= mAabb
.getCenter();
72 mSphere
.radius
= (mAabb
.min
- mSphere
.point
).length();
75 void draw(Scalar alpha
) const
82 logDebug("size of node %d", objects
.size());
85 void getAll(std::list
<InsertableP
>& insertables
) const
87 insertables
.insert(insertables
.end(), objects
.begin(),
91 void getIfVisible(std::list
<InsertableP
>& insertables
,
92 const Frustum
& frustum
) const
94 typename
std::list
<InsertableP
>::const_iterator it
;
96 for (it
= objects
.begin(); it
!= objects
.end(); ++it
)
98 if ((*it
)->isVisible(frustum
)) insertables
.push_back(*it
);
106 typedef boost::shared_ptr
<Octree
> Ptr
;
107 typedef typename
stlplus::ntree
<Node
>::iterator NodeP
;
112 NodeP
insert(InsertableP entity
, NodeP node
)
114 ASSERT(node
.valid() && "invalid node passed");
115 ASSERT(entity
&& "null entity passed");
117 Aabb entityAabb
= entity
->getAabb();
118 Aabb nodeAabb
= node
->getAabb();
120 if (!(entityAabb
.max
[0] < nodeAabb
.max
[0] &&
121 entityAabb
.min
[0] > nodeAabb
.min
[0] &&
122 entityAabb
.max
[1] < nodeAabb
.max
[1] &&
123 entityAabb
.min
[1] > nodeAabb
.min
[1] &&
124 entityAabb
.max
[2] < nodeAabb
.max
[2] &&
125 entityAabb
.min
[2] > nodeAabb
.min
[2]))
127 node
->objects
.push_back(entity
);
132 return insert_recurse(entity
, node
);
136 NodeP
insert_recurse(InsertableP entity
, NodeP node
)
138 ASSERT(node
.valid() && "invalid node passed");
139 ASSERT(entity
&& "null entity passed");
141 int octantNum
= entity
->getOctant(node
->getAabb());
144 node
->objects
.push_back(entity
);
149 if ((int)mTree
.children(node
) <= octantNum
)
151 addChild(node
, octantNum
);
154 NodeP child
= mTree
.child(node
, octantNum
);
155 ASSERT(child
.valid() && "expected valid child node");
157 return insert_recurse(entity
, child
);
161 void addChild(NodeP node
, int index
)
163 ASSERT(node
.valid() && "invalid node passed");
167 for (int i
= mTree
.children(node
); i
<= index
; ++i
)
169 node
->getAabb().getOctant(octant
, i
);
170 mTree
.append(node
, octant
);
175 void getNearbyObjects(std::list
<InsertableP
>& insertables
,
176 const OctreeInsertable
& entity
, NodeP node
) const
178 ASSERT(node
.valid() && "invalid node passed");
182 int octantNum
= entity
.getOctant(node
->getAabb());
185 node
->getAll(insertables
);
187 if (octantNum
< (int)mTree
.children(node
))
189 NodeP child
= mTree
.child(node
, octantNum
);
190 ASSERT(child
.valid() && "expected valid child node");
192 getNearbyObjects(insertables
, entity
, child
);
197 logDebug("getting all the rest...");
198 getAll(insertables
, node
);
203 void getAll(std::list
<InsertableP
>& insertables
, NodeP node
) const
205 ASSERT(node
.valid() && "invalid node passed");
207 node
->getAll(insertables
);
209 for (unsigned i
= 0; i
< mTree
.children(node
); ++i
)
211 NodeP child
= mTree
.child(node
, i
);
212 ASSERT(child
.valid() && "expected valid child node");
214 getAll(insertables
, child
);
218 void getIfVisible(std::list
<InsertableP
>& insertables
,
219 const Frustum
& frustum
, NodeP node
) const
221 ASSERT(node
.valid() && "invalid node passed");
223 // try to cull by sphere
224 Frustum::Collision collision
= frustum
.contains(node
->getSphere());
225 if (collision
== Frustum::OUTSIDE
) return;
227 // try to cull by aabb
228 collision
= frustum
.contains(node
->getAabb());
229 if (collision
== Frustum::OUTSIDE
) return;
232 if (collision
== Frustum::INSIDE
)
234 node
->getAll(insertables
);
236 else // collision == Frustum::INTERSECT
238 node
->getIfVisible(insertables
, frustum
);
241 if (mTree
.children(node
) > 0)
243 if (collision
== Frustum::INSIDE
)
245 for (unsigned i
= 0; i
< mTree
.children(node
); ++i
)
247 NodeP child
= mTree
.child(node
, i
);
248 ASSERT(child
.valid() && "expected valid child node");
250 getAll(insertables
, child
);
253 else // collision == Frustum::INTERSECT
255 for (unsigned i
= 0; i
< mTree
.children(node
); ++i
)
257 NodeP child
= mTree
.child(node
, i
);
258 ASSERT(child
.valid() && "expected valid child node");
260 getIfVisible(insertables
, frustum
, child
);
267 mutable stlplus::ntree
<Node
> mTree
;
272 void print(NodeP node
)
275 logInfo("depth to node: %d", mTree
.depth(node
));
276 logInfo("size of node: %d", mTree
.size(node
));
279 static Ptr
alloc(const Node
& rootNode
)
281 return Ptr(new Octree(rootNode
));
284 explicit Octree(const Node
& rootNode
)
286 mTree
.insert(rootNode
);
290 NodeP
insert(InsertableP entity
)
292 return insert(entity
, mTree
.root());
295 void remove(InsertableP entity
, NodeP node
)
297 ASSERT(entity
&& "null entity passed");
298 ASSERT(node
.valid() && "invalid node passed");
300 typename
std::list
<InsertableP
>::iterator it
;
301 it
= std::find(node
->objects
.begin(), node
->objects
.end(), entity
);
303 if (it
!= node
->objects
.end())
305 node
->objects
.erase(it
);
310 NodeP
reinsert(InsertableP entity
, NodeP node
)
312 remove(entity
, node
);
313 return insert(entity
);
317 void draw(Scalar alpha
) const
319 std::list
<InsertableP
> objects
;
322 typename
std::list
<InsertableP
>::const_iterator it
;
323 for (it
= objects
.begin(); it
!= objects
.end(); ++it
)
329 void drawIfVisible(Scalar alpha
, const Frustum
& frustum
) const
331 std::list
<InsertableP
> objects
;
332 getIfVisible(objects
, frustum
);
333 //getNearbyObjects(objects, *savedObj);
335 typename
std::list
<InsertableP
>::const_iterator it
;
336 for (it
= objects
.begin(); it
!= objects
.end(); ++it
)
343 void getAll(std::list
<InsertableP
>& insertables
) const
345 getAll(insertables
, mTree
.root());
348 void getIfVisible(std::list
<InsertableP
>& insertables
,
349 const Frustum
& frustum
) const
351 getIfVisible(insertables
, frustum
, mTree
.root());
354 mutable const OctreeInsertable
* savedObj
;
357 void getNearbyObjects(std::list
<InsertableP
>& insertables
,
358 const OctreeInsertable
& entity
) const
360 logDebug("--- GETTING NEARBY");
361 getNearbyObjects(insertables
, entity
, mTree
.root());
370 #endif // _MOOF_OCTREE_HH_
372 /** vim: set ts=4 sw=4 tw=80: *************************************************/
This page took 0.048836 seconds and 4 git commands to generate.