1c57ff2d3317fe83d10aa6972093683cb634556f
[chaz/yoink] / src / Moof / Octree.hh
1
2 /*******************************************************************************
3
4 Copyright (c) 2009, Charles McGarvey
5 All rights reserved.
6
7 Redistribution and use in source and binary forms, with or without
8 modification, are permitted provided that the following conditions are met:
9
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.
15
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.
26
27 *******************************************************************************/
28
29 #ifndef _MOOF_OCTREE_HH_
30 #define _MOOF_OCTREE_HH_
31
32 #include <list>
33
34 #include <boost/shared_ptr.hpp>
35
36 #include <stlplus/ntree.hpp>
37
38 #include <Moof/Aabb.hh>
39 #include <Moof/Drawable.hh>
40 #include <Moof/Entity.hh>
41 #include <Moof/Math.hh>
42 #include <Moof/Sphere.hh>
43
44
45 namespace Mf {
46
47
48 struct OctreeNode : public Entity
49 {
50 std::list<EntityPtr> objects;
51
52 OctreeNode()
53 {
54 aabb_.min = Vector3(-1.0, -1.0, -1.0);
55 aabb_.max = Vector3(1.0, 1.0, 1.0);
56 sphere_.init(Vector3(0.0, 0.0, 0.0), 1.41421);
57 }
58
59 OctreeNode(const Aabb& aabb)
60 {
61 aabb_ = aabb;
62 sphere_.point = aabb.getCenter();
63 sphere_.radius = (aabb.min - sphere_.point).length();
64 }
65
66 void draw(Scalar alpha) const
67 {
68 std::list<EntityPtr>::const_iterator it;
69
70 for (it = objects.begin(); it != objects.end(); ++it)
71 {
72 (*it)->draw(alpha);
73 }
74 if (!objects.empty())
75 aabb_.draw(); // temporary
76 }
77
78 void drawIfVisible(Scalar alpha, const Camera& cam) const
79 {
80 std::list<EntityPtr>::const_iterator it;
81
82 for (it = objects.begin(); it != objects.end(); ++it)
83 {
84 (*it)->drawIfVisible(alpha, cam);
85 }
86 if (!objects.empty())
87 aabb_.draw();
88 }
89
90
91 bool isVisible(const Camera& cam) const
92 {
93 if (sphere_.isVisible(cam))
94 {
95 return aabb_.isVisible(cam);
96 }
97
98 return false;
99 }
100 };
101
102
103 class Octree;
104 typedef boost::shared_ptr<Octree> OctreePtr;
105
106 class Octree
107 {
108
109 stlplus::ntree<OctreeNode> root_;
110
111 public:
112
113 explicit Octree(const OctreeNode& rootNode)
114 {
115 root_.insert(rootNode);
116 }
117
118 void insert(EntityPtr entity)
119 {
120 insert(root_.root(), entity);
121 }
122
123 void insert(stlplus::ntree<OctreeNode>::iterator node, EntityPtr entity)
124 {
125 Plane::Halfspace halfspace;
126 int octantNum = -1;
127
128 if (!node.valid())
129 {
130 std::cerr << "cannot insert into invalid node" << std::endl;
131 return;
132 }
133
134 Plane xy = node->getAabb().getPlaneXY();
135 halfspace = xy.intersectsSphere(entity->getSphere());
136
137 if (halfspace == Plane::POSITIVE)
138 {
139 Plane xz = node->getAabb().getPlaneXZ();
140 halfspace = xz.intersectsSphere(entity->getSphere());
141
142 if (halfspace == Plane::POSITIVE)
143 {
144 Plane yz = node->getAabb().getPlaneYZ();
145 halfspace = yz.intersectsSphere(entity->getSphere());
146
147 if (halfspace == Plane::POSITIVE)
148 {
149 octantNum = 2;
150 }
151 else if (halfspace == Plane::NEGATIVE)
152 {
153 octantNum = 3;
154 }
155 }
156 else if (halfspace == Plane::NEGATIVE)
157 {
158 Plane yz = node->getAabb().getPlaneYZ();
159 halfspace = yz.intersectsSphere(entity->getSphere());
160
161 if (halfspace == Plane::POSITIVE)
162 {
163 octantNum = 1;
164 }
165 else if (halfspace == Plane::NEGATIVE)
166 {
167 octantNum = 0;
168 }
169 }
170 }
171 else if (halfspace == Plane::NEGATIVE)
172 {
173 Plane xz = node->getAabb().getPlaneXZ();
174 halfspace = xz.intersectsSphere(entity->getSphere());
175
176 if (halfspace == Plane::POSITIVE)
177 {
178 Plane yz = node->getAabb().getPlaneYZ();
179 halfspace = yz.intersectsSphere(entity->getSphere());
180
181 if (halfspace == Plane::POSITIVE)
182 {
183 octantNum = 6;
184 }
185 else if (halfspace == Plane::NEGATIVE)
186 {
187 octantNum = 7;
188 }
189 }
190 else if (halfspace == Plane::NEGATIVE)
191 {
192 Plane yz = node->getAabb().getPlaneYZ();
193 halfspace = yz.intersectsSphere(entity->getSphere());
194
195 if (halfspace == Plane::POSITIVE)
196 {
197 octantNum = 5;
198 }
199 else if (halfspace == Plane::NEGATIVE)
200 {
201 octantNum = 4;
202 }
203 }
204 }
205
206 if (octantNum == -1)
207 {
208 node->objects.push_front(entity);
209 //return node;
210 }
211 else
212 {
213 if (root_.children(node) == 0)
214 {
215 addChildren(node);
216 }
217
218 stlplus::ntree<OctreeNode>::iterator child = root_.child(node, octantNum);
219
220 if (child.valid())
221 {
222 return insert(child, entity);
223 }
224 else
225 {
226 std::cerr << "expected but found no child at index " << octantNum << std::endl;
227 //return stlplus::ntree<OctreeNode>::iterator();
228 }
229 //return WeakPtr();
230 }
231 }
232
233 void addChildren(stlplus::ntree<OctreeNode>::iterator node)
234 {
235 Aabb octant;
236
237 if (!node.valid())
238 {
239 std::cerr << "cannot add children to invalid node" << std::endl;
240 return;
241 }
242
243 for (int i = 0; i < 8; ++i)
244 {
245 node->getAabb().getOctant(octant, i);
246 //OctreeNode octantNode(octant);
247
248 root_.append(node, octant);
249 }
250 }
251
252 void draw(stlplus::ntree<OctreeNode>::iterator node, Scalar alpha)
253 {
254 if (!node.valid())
255 {
256 std::cerr << "cannot draw null child node :-(" << std::endl;
257 return;
258 }
259
260 node->draw(alpha);
261
262 for (unsigned i = 0; i < root_.children(node); ++i)
263 {
264 stlplus::ntree<OctreeNode>::iterator child = root_.child(node, i);
265
266 if (child.valid())
267 {
268 draw(child, alpha);
269 }
270 else
271 {
272 std::cerr << "node is not a leaf, but has an invalid child" << std::endl;
273 }
274
275 }
276 }
277
278 void drawIfVisible(stlplus::ntree<OctreeNode>::iterator node,
279 Scalar alpha, const Camera& cam)
280 {
281 //node.drawIfVisible(alpha, cam);
282
283 if (!node.valid())
284 {
285 std::cerr << "invalid child while drawing :-(" << std::endl;
286 return;
287 }
288
289 Frustum::Collision collision =
290 cam.getFrustum().containsSphere(node->getSphere());
291 if (collision == Frustum::OUTSIDE) return;
292
293 collision = cam.getFrustum().containsAabb(node->getAabb());
294 if (collision == Frustum::OUTSIDE) return;
295
296
297 if (collision == Frustum::INSIDE)
298 {
299 node->draw(alpha);
300 }
301 else // collision == Frustum::INTERSECT
302 {
303 node->drawIfVisible(alpha, cam);
304 }
305
306 if (root_.children(node) > 0)
307 {
308 if (collision == Frustum::INSIDE)
309 {
310 for (unsigned i = 0; i < root_.children(node); ++i)
311 {
312 stlplus::ntree<OctreeNode>::iterator child = root_.child(node, i);
313
314 if (child.valid())
315 {
316 draw(child, alpha);
317 }
318 else
319 {
320 std::cerr << "node is not a leaf, but has an invalid child" << std::endl;
321 }
322
323 }
324 }
325 else // collision == Frustum::INTERSECT
326 {
327 for (unsigned i = 0; i < root_.children(node); ++i)
328 {
329 stlplus::ntree<OctreeNode>::iterator child = root_.child(node, i);
330
331 if (child.valid())
332 {
333 drawIfVisible(child, alpha, cam);
334 }
335 else
336 {
337 std::cerr << "node is not a leaf, but has an invalid child" << std::endl;
338 }
339 }
340 }
341 }
342 }
343
344 void drawIfVisible(Scalar alpha, const Camera& cam)
345 {
346 drawIfVisible(root_.root(), alpha, cam);
347 }
348
349 };
350
351
352
353 } // namespace Mf
354
355 #endif // _MOOF_OCTREE_HH_
356
357 /** vim: set ts=4 sw=4 tw=80: *************************************************/
358
This page took 0.04375 seconds and 3 git commands to generate.