]>
Dogcows Code - chaz/yoink/blob - src/Moof/Octree.hh
cdac62a29071f4eeaeb51c48c055e84db1a029dc
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>
52 //typedef boost::shared_ptr<Octree> OctreeP;
55 //typedef stlplus::ntree<Octree::Node>::iterator OctreeNodeP;
58 struct OctreeInsertable
60 virtual ~OctreeInsertable() {}
62 virtual bool isInsideAabb(const Aabb
& aabb
) const = 0;
63 virtual int getOctant(const Aabb
& aabb
) const = 0;
68 class Octree
: public Entity
70 typedef boost::shared_ptr
<T
> InsertableP
;
72 struct Node
: public Entity
74 std::list
<InsertableP
> objects
;
79 Node(const Aabb
& box
) :
82 sphere
.point
= aabb
.getCenter();
83 sphere
.radius
= (aabb
.min
- sphere
.point
).length();
86 void draw(Scalar alpha
) const
88 typename
std::list
<InsertableP
>::const_iterator it
;
90 for (it
= objects
.begin(); it
!= objects
.end(); ++it
)
96 aabb
.draw(); // temporary
99 void drawIfVisible(Scalar alpha
, const Frustum
& frustum
) const
101 typename
std::list
<InsertableP
>::const_iterator it
;
103 for (it
= objects
.begin(); it
!= objects
.end(); ++it
)
105 (*it
)->drawIfVisible(alpha
, frustum
);
108 if (!objects
.empty())
116 bool isVisible(const Frustum
& frustum
) const
118 if (sphere
.isVisible(frustum
))
120 return aabb
.isVisible(frustum
);
130 typedef boost::shared_ptr
<Octree
> Ptr
;
131 typedef typename
stlplus::ntree
<Node
>::iterator NodeP
;
136 NodeP
insert(InsertableP entity
, NodeP node
)
138 ASSERT(node
.valid() && "invalid node passed");
139 ASSERT(entity
&& "null entity passed");
141 if (entity
->isInsideAabb(node
->aabb
))
143 return insert_recurse(entity
, node
);
147 node
->objects
.push_back(entity
);
152 NodeP
insert_recurse(InsertableP entity
, NodeP node
)
154 ASSERT(node
.valid() && "invalid node passed");
155 ASSERT(entity
&& "null entity passed");
157 int octantNum
= entity
->getOctant(node
->aabb
);
160 node
->objects
.push_back(entity
);
165 if ((int)tree_
.children(node
) <= octantNum
)
167 addChild(node
, octantNum
);
170 NodeP child
= tree_
.child(node
, octantNum
);
171 ASSERT(child
.valid() && "expected valid child node");
173 return insert(entity
, child
);
177 void addChild(NodeP node
, int index
)
179 ASSERT(node
.valid() && "invalid node passed");
183 for (int i
= tree_
.children(node
); i
<= index
; ++i
)
185 node
->aabb
.getOctant(octant
, i
);
186 tree_
.append(node
, octant
);
191 void draw(Scalar alpha
, NodeP node
) const
193 ASSERT(node
.valid() && "invalid node passed");
197 for (unsigned i
= 0; i
< tree_
.children(node
); ++i
)
199 NodeP child
= tree_
.child(node
, i
);
200 ASSERT(child
.valid() && "expected valid child node");
206 void drawIfVisible(Scalar alpha
, const Frustum
& frustum
, NodeP node
) const
208 ASSERT(node
.valid() && "invalid node passed");
210 // try to cull by sphere
211 Frustum::Collision collision
= frustum
.contains(node
->sphere
);
212 if (collision
== Frustum::OUTSIDE
) return;
214 // try to cull by aabb
215 collision
= frustum
.contains(node
->aabb
);
216 if (collision
== Frustum::OUTSIDE
) return;
219 if (collision
== Frustum::INSIDE
)
223 else // collision == Frustum::INTERSECT
225 node
->drawIfVisible(alpha
, frustum
);
228 if (tree_
.children(node
) > 0)
230 if (collision
== Frustum::INSIDE
)
232 for (unsigned i
= 0; i
< tree_
.children(node
); ++i
)
234 NodeP child
= tree_
.child(node
, i
);
235 ASSERT(child
.valid() && "expected valid child node");
240 else // collision == Frustum::INTERSECT
242 for (unsigned i
= 0; i
< tree_
.children(node
); ++i
)
244 NodeP child
= tree_
.child(node
, i
);
245 ASSERT(child
.valid() && "expected valid child node");
247 drawIfVisible(alpha
, frustum
, child
);
253 mutable stlplus::ntree
<Node
> tree_
;
258 void print(NodeP node
)
261 //logDebug("depth to node: %d", tree_.depth(node));
262 //logDebug("size of node: %d", tree_.size(node));
265 static Ptr
alloc(const Node
& rootNode
)
267 return Ptr(new Octree(rootNode
));
270 explicit Octree(const Node
& rootNode
)
272 tree_
.insert(rootNode
);
275 NodeP
insert(InsertableP entity
)
277 return insert(entity
, tree_
.root());
280 NodeP
reinsert(InsertableP entity
, NodeP node
)
282 ASSERT(entity
&& "null entity passed");
283 ASSERT(node
.valid() && "invalid node passed");
285 typename
std::list
<InsertableP
>::iterator it
;
286 it
= std::find(node
->objects
.begin(), node
->objects
.end(), entity
);
288 if (it
!= node
->objects
.end())
290 node
->objects
.erase(it
);
293 return insert(entity
);
296 void draw(Scalar alpha
) const
298 draw(alpha
, tree_
.root());
301 void drawIfVisible(Scalar alpha
, const Frustum
& frustum
) const
303 drawIfVisible(alpha
, frustum
, tree_
.root());
310 #endif // _MOOF_OCTREE_HH_
312 /** vim: set ts=4 sw=4 tw=80: *************************************************/
This page took 0.046104 seconds and 4 git commands to generate.