]>
Dogcows Code - chaz/yoink/blob - src/Moof/Octree.hh
78d3aa875706cd61f4558740c7b90a8cf4f82cd3
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_
34 #include <boost/shared_ptr.hpp>
36 #include <Moof/Aabb.hh>
37 #include <Moof/Drawable.hh>
38 #include <Moof/Entity.hh>
39 #include <Moof/Math.hh>
40 #include <Moof/Sphere.hh>
41 #include <Moof/Tree.hh>
47 struct OctreeNode
: public Entity
49 std::list
<EntityPtr
> objects
;
53 aabb_
.min
= Vector3(-1.0, -1.0, -1.0);
54 aabb_
.max
= Vector3(1.0, 1.0, 1.0);
55 sphere_
.init(Vector3(0.0, 0.0, 0.0), 1.41421);
58 OctreeNode(const Aabb
& aabb
)
61 sphere_
.point
= aabb
.getCenter();
62 sphere_
.radius
= (aabb
.min
- sphere_
.point
).length();
65 void draw(Scalar alpha
) const
67 std::list
<EntityPtr
>::const_iterator it
;
69 for (it
= objects
.begin(); it
!= objects
.end(); ++it
)
74 aabb_
.draw(); // temporary
77 void drawIfVisible(Scalar alpha
, const Camera
& cam
) const
79 std::list
<EntityPtr
>::const_iterator it
;
81 for (it
= objects
.begin(); it
!= objects
.end(); ++it
)
83 (*it
)->drawIfVisible(alpha
, cam
);
90 bool isVisible(const Camera
& cam
) const
92 if (sphere_
.isVisible(cam
))
94 return aabb_
.isVisible(cam
);
103 typedef boost::shared_ptr
<Octree
> OctreePtr
;
105 class Octree
: public Tree
<OctreeNode
>
110 explicit Octree(const OctreeNode
& initNode
) :
111 Tree
<OctreeNode
>(initNode
) {}
115 inline static OctreePtr
createNewNode(const OctreeNode
& item
)
117 OctreePtr newNode
= OctreePtr(new Octree(item
));
123 static Tree
<OctreeNode
>::WeakPtr
add(Ptr node
, EntityPtr entity
)
125 Plane::Halfspace halfspace
;
128 Plane xy
= node
->node
.getAabb().getPlaneXY();
129 halfspace
= xy
.intersectsSphere(entity
->getSphere());
131 if (halfspace
== Plane::POSITIVE
)
133 Plane xz
= node
->node
.getAabb().getPlaneXZ();
134 halfspace
= xz
.intersectsSphere(entity
->getSphere());
136 if (halfspace
== Plane::POSITIVE
)
138 Plane yz
= node
->node
.getAabb().getPlaneYZ();
139 halfspace
= yz
.intersectsSphere(entity
->getSphere());
141 if (halfspace
== Plane::POSITIVE
)
145 else if (halfspace
== Plane::NEGATIVE
)
150 else if (halfspace
== Plane::NEGATIVE
)
152 Plane yz
= node
->node
.getAabb().getPlaneYZ();
153 halfspace
= yz
.intersectsSphere(entity
->getSphere());
155 if (halfspace
== Plane::POSITIVE
)
159 else if (halfspace
== Plane::NEGATIVE
)
165 else if (halfspace
== Plane::NEGATIVE
)
167 Plane xz
= node
->node
.getAabb().getPlaneXZ();
168 halfspace
= xz
.intersectsSphere(entity
->getSphere());
170 if (halfspace
== Plane::POSITIVE
)
172 Plane yz
= node
->node
.getAabb().getPlaneYZ();
173 halfspace
= yz
.intersectsSphere(entity
->getSphere());
175 if (halfspace
== Plane::POSITIVE
)
179 else if (halfspace
== Plane::NEGATIVE
)
184 else if (halfspace
== Plane::NEGATIVE
)
186 Plane yz
= node
->node
.getAabb().getPlaneYZ();
187 halfspace
= yz
.intersectsSphere(entity
->getSphere());
189 if (halfspace
== Plane::POSITIVE
)
193 else if (halfspace
== Plane::NEGATIVE
)
202 node
->node
.objects
.push_front(entity
);
212 Ptr child
= node
->getChild(octantNum
);
215 return add(child
, entity
);
219 std::cerr
<< "no child at index " << octantNum
<< std::endl
;
226 static void addChildren(Ptr node
)
230 for (int i
= 0; i
< 8; ++i
)
232 node
->node
.getAabb().getOctant(octant
, i
);
233 //OctreeNode octantNode(octant);
235 Ptr newChild
= createNewNode(octant
);
236 node
->addChild(newChild
);
240 void draw(Ptr node
, Scalar alpha
)
244 std::cerr
<< "null child :-(" << std::endl
;
248 node
->node
.draw(alpha
);
252 Ptr firstChild
= node
->getFirstChild();
253 Ptr temp
= firstChild
;
257 std::cerr
<< "node is not a leaf, but has no first child :-(" << std::endl
;
264 temp
= temp
->getNextSibling();
266 while (temp
&& temp
!= firstChild
);
270 void drawIfVisible(Ptr node
, Scalar alpha
, const Camera
& cam
)
272 //node.drawIfVisible(alpha, cam);
276 std::cerr
<< "null child :-(" << std::endl
;
280 Frustum::Collision collision
=
281 cam
.getFrustum().containsSphere(node
->node
.getSphere());
282 if (collision
== Frustum::OUTSIDE
) return;
284 collision
= cam
.getFrustum().containsAabb(node
->node
.getAabb());
285 if (collision
== Frustum::OUTSIDE
) return;
288 if (collision
== Frustum::INSIDE
)
290 node
->node
.draw(alpha
);
292 else // collision == Frustum::INTERSECT
294 node
->node
.drawIfVisible(alpha
, cam
);
299 Ptr firstChild
= node
->getFirstChild();
300 Ptr temp
= firstChild
;
304 std::cerr
<< "node is not a leaf, but has no first child :-(" << std::endl
;
308 if (collision
== Frustum::INSIDE
)
313 temp
= temp
->getNextSibling();
315 while (temp
&& temp
!= firstChild
);
317 else // collision == Frustum::INTERSECT
321 drawIfVisible(temp
, alpha
, cam
);
322 temp
= temp
->getNextSibling();
324 while (temp
&& temp
!= firstChild
);
329 void drawIfVisible(Scalar alpha
, const Camera
& cam
)
331 drawIfVisible(getThis(), alpha
, cam
);
340 #endif // _MOOF_OCTREE_HH_
342 /** vim: set ts=4 sw=4 tw=80: *************************************************/
This page took 0.055508 seconds and 4 git commands to generate.