]> Dogcows Code - chaz/yoink/blob - src/Moof/Octree.cc
bd1b410a6faa17cbc837df55527646b54c5232fb
[chaz/yoink] / src / Moof / Octree.cc
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 #include "Camera.hh"
30 #include "Log.hh"
31 #include "Octree.hh"
32
33
34 namespace Mf {
35
36
37 void Octree::sort()
38 {
39 stlplus::ntree<OctreeNode>::prefix_iterator it;
40
41 for (it = tree_.prefix_begin(); it != tree_.prefix_end(); ++it)
42 {
43 it->sort();
44 }
45 }
46
47
48 OctreeNodeP Octree::insert(EntityP entity, OctreeNodeP node)
49 {
50 ASSERT(node.valid() && "invalid node passed");
51 ASSERT(entity && "null entity passed");
52
53 int octantNum = -1;
54
55 Plane::Halfspace halfspace;
56
57 // TODO this method needs a lot of work
58 Plane xy = node->getAabb().getPlaneXY();
59
60
61 // make sure the entity is fully inside the volume
62 if (!(entity->getAabb().max[0] < node->getAabb().max[0] &&
63 entity->getAabb().min[0] > node->getAabb().min[0] &&
64 entity->getAabb().max[1] < node->getAabb().max[1] &&
65 entity->getAabb().min[1] > node->getAabb().min[1] &&
66 entity->getAabb().max[2] < node->getAabb().max[2] &&
67 entity->getAabb().min[2] > node->getAabb().min[2]))
68 {
69 // TODO this check is only needed for the root node, if we're inside the
70 // volume of the root node, we'll be fully inside the child as
71 // determined by trying to insert the parent node
72 goto done;
73 }
74
75 halfspace = xy.intersectsSphere(entity->getSphere());
76 if (halfspace == Plane::INTERSECT)
77 {
78 halfspace = xy.intersectsAabb(entity->getAabb());
79 }
80
81 if (halfspace == Plane::POSITIVE)
82 {
83 Plane xz = node->getAabb().getPlaneXZ();
84 halfspace = xz.intersectsSphere(entity->getSphere());
85 if (halfspace == Plane::INTERSECT)
86 {
87 halfspace = xz.intersectsAabb(entity->getAabb());
88 }
89
90 if (halfspace == Plane::POSITIVE)
91 {
92 Plane yz = node->getAabb().getPlaneYZ();
93 halfspace = yz.intersectsSphere(entity->getSphere());
94 if (halfspace == Plane::INTERSECT)
95 {
96 halfspace = yz.intersectsAabb(entity->getAabb());
97 }
98
99 if (halfspace == Plane::POSITIVE)
100 {
101 octantNum = 2;
102 }
103 else if (halfspace == Plane::NEGATIVE)
104 {
105 octantNum = 3;
106 }
107 }
108 else if (halfspace == Plane::NEGATIVE)
109 {
110 Plane yz = node->getAabb().getPlaneYZ();
111 halfspace = yz.intersectsSphere(entity->getSphere());
112 if (halfspace == Plane::INTERSECT)
113 {
114 halfspace = yz.intersectsAabb(entity->getAabb());
115 }
116
117 if (halfspace == Plane::POSITIVE)
118 {
119 octantNum = 1;
120 }
121 else if (halfspace == Plane::NEGATIVE)
122 {
123 octantNum = 0;
124 }
125 }
126 }
127 else if (halfspace == Plane::NEGATIVE)
128 {
129 Plane xz = node->getAabb().getPlaneXZ();
130 halfspace = xz.intersectsSphere(entity->getSphere());
131 if (halfspace == Plane::INTERSECT)
132 {
133 halfspace = xz.intersectsAabb(entity->getAabb());
134 }
135
136 if (halfspace == Plane::POSITIVE)
137 {
138 Plane yz = node->getAabb().getPlaneYZ();
139 halfspace = yz.intersectsSphere(entity->getSphere());
140 if (halfspace == Plane::INTERSECT)
141 {
142 halfspace = yz.intersectsAabb(entity->getAabb());
143 }
144
145 if (halfspace == Plane::POSITIVE)
146 {
147 octantNum = 6;
148 }
149 else if (halfspace == Plane::NEGATIVE)
150 {
151 octantNum = 7;
152 }
153 }
154 else if (halfspace == Plane::NEGATIVE)
155 {
156 Plane yz = node->getAabb().getPlaneYZ();
157 halfspace = yz.intersectsSphere(entity->getSphere());
158 if (halfspace == Plane::INTERSECT)
159 {
160 halfspace = yz.intersectsAabb(entity->getAabb());
161 }
162
163 if (halfspace == Plane::POSITIVE)
164 {
165 octantNum = 5;
166 }
167 else if (halfspace == Plane::NEGATIVE)
168 {
169 octantNum = 4;
170 }
171 }
172 }
173
174 done:
175
176 if (octantNum == -1)
177 {
178 node->objects.push_front(entity);
179 return node;
180 }
181 else
182 {
183 if ((int)tree_.children(node) <= octantNum)
184 {
185 addChild(node, octantNum);
186 }
187
188 OctreeNodeP child = tree_.child(node, octantNum);
189 ASSERT(child.valid() && "expected valid child node");
190
191 return insert(entity, child);
192 }
193 }
194
195 OctreeNodeP Octree::reinsert(EntityP entity, OctreeNodeP node)
196 {
197 ASSERT(entity && "null entity passed");
198 ASSERT(node.valid() && "invalid node passed");
199
200 std::list<EntityP>::iterator it;
201 it = std::find(node->objects.begin(), node->objects.end(), entity);
202
203 if (it != node->objects.end())
204 {
205 node->objects.erase(it);
206 }
207
208 return insert(entity);
209 }
210
211
212 void Octree::addChild(OctreeNodeP node, int index)
213 {
214 ASSERT(node.valid() && "invalid node passed");
215
216 Aabb octant;
217
218 for (int i = tree_.children(node); i <= index; ++i)
219 {
220 node->getAabb().getOctant(octant, i);
221 tree_.append(node, octant);
222 }
223 }
224
225
226 void Octree::draw(Scalar alpha, OctreeNodeP node)
227 {
228 ASSERT(node.valid() && "invalid node passed");
229
230 node->draw(alpha);
231
232 for (unsigned i = 0; i < tree_.children(node); ++i)
233 {
234 OctreeNodeP child = tree_.child(node, i);
235 ASSERT(child.valid() && "expected valid child node");
236
237 draw(alpha, child);
238 }
239 }
240
241 void Octree::drawIfVisible(Scalar alpha, const Camera& cam, OctreeNodeP node)
242 {
243 ASSERT(node.valid() && "invalid node passed");
244
245 // try to cull by sphere
246 Frustum::Collision collision =
247 cam.getFrustum().containsSphere(node->getSphere());
248 if (collision == Frustum::OUTSIDE) return;
249
250 // try to cull by aabb
251 collision = cam.getFrustum().containsAabb(node->getAabb());
252 if (collision == Frustum::OUTSIDE) return;
253
254
255 if (collision == Frustum::INSIDE)
256 {
257 node->draw(alpha);
258 }
259 else // collision == Frustum::INTERSECT
260 {
261 node->drawIfVisible(alpha, cam);
262 }
263
264 if (tree_.children(node) > 0)
265 {
266 if (collision == Frustum::INSIDE)
267 {
268 for (unsigned i = 0; i < tree_.children(node); ++i)
269 {
270 OctreeNodeP child = tree_.child(node, i);
271 ASSERT(child.valid() && "expected valid child node");
272
273 draw(alpha, child);
274 }
275 }
276 else // collision == Frustum::INTERSECT
277 {
278 for (unsigned i = 0; i < tree_.children(node); ++i)
279 {
280 OctreeNodeP child = tree_.child(node, i);
281 ASSERT(child.valid() && "expected valid child node");
282
283 drawIfVisible(alpha, cam, child);
284 }
285 }
286 }
287 }
288
289
290 } // namespace Mf
291
292 /** vim: set ts=4 sw=4 tw=80: *************************************************/
293
This page took 0.044874 seconds and 3 git commands to generate.