Line data Source code
1 0 : /*
2 :
3 : Octree.m
4 :
5 : Oolite
6 : Copyright (C) 2004-2013 Giles C Williams and contributors
7 :
8 : This program is free software; you can redistribute it and/or
9 : modify it under the terms of the GNU General Public License
10 : as published by the Free Software Foundation; either version 2
11 : of the License, or (at your option) any later version.
12 :
13 : This program is distributed in the hope that it will be useful,
14 : but WITHOUT ANY WARRANTY; without even the implied warranty of
15 : MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 : GNU General Public License for more details.
17 :
18 : You should have received a copy of the GNU General Public License
19 : along with this program; if not, write to the Free Software
20 : Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
21 : MA 02110-1301, USA.
22 :
23 : */
24 :
25 : #import "Octree.h"
26 : #import "OOMaths.h"
27 : #import "Entity.h"
28 : #import "OOOpenGL.h"
29 : #import "OODebugGLDrawing.h"
30 : #import "OOMacroOpenGL.h"
31 : #import "OODebugFlags.h"
32 : #import "NSObjectOOExtensions.h"
33 : #import "OOCollectionExtractors.h"
34 :
35 :
36 : #ifndef NDEBUG
37 0 : #define OctreeDebugLog(format, ...) do { if (EXPECT_NOT(gDebugFlags & DEBUG_OCTREE_LOGGING)) OOLog(@"octree.debug", format, ## __VA_ARGS__); } while (0)
38 : #else
39 : #define OctreeDebugLog(...) do {} while (0)
40 : #endif
41 :
42 :
43 0 : typedef struct
44 : {
45 0 : GLfloat radius;
46 0 : const int *octree;
47 0 : unsigned char *octree_collision;
48 : } Octree_details;
49 :
50 :
51 : @interface Octree (Private)
52 :
53 : #ifndef OODEBUGLDRAWING_DISABLE
54 :
55 0 : - (void) drawOctreeFromLocation:(uint32_t)loc :(GLfloat)scale :(Vector)offset;
56 0 : - (void) drawOctreeCollisionFromLocation:(uint32_t)loc :(GLfloat)scale :(Vector)offset;
57 :
58 0 : - (BOOL) hasCollision;
59 0 : - (void) setHasCollision:(BOOL)value;
60 :
61 : #endif
62 :
63 0 : - (Octree_details) octreeDetails;
64 :
65 : @end
66 :
67 :
68 0 : static const int change_oct[] = { 0, 1, 2, 4, 3, 5, 6, 7 }; // used to move from nearest to furthest octant
69 :
70 :
71 0 : static BOOL isHitByLine(const int *octbuffer, unsigned char *collbuffer, int level, GLfloat rad, Vector v0, Vector v1, Vector off, int face_hit);
72 0 : static GLfloat volumeOfOctree(Octree_details octree_details, unsigned depthLimit);
73 0 : static Vector randomFullNodeFrom(Octree_details details, Vector offset);
74 :
75 0 : static BOOL isHitByOctree(Octree_details axialDetails, Octree_details otherDetails, Vector delta, Triangle other_ijk);
76 :
77 :
78 : @implementation Octree
79 :
80 0 : - (id) init
81 : {
82 : // -init makes no sense, since octrees are immutable.
83 : [self release];
84 : [NSException raise:NSInternalInconsistencyException format:@"Call of invalid initializer %s", __FUNCTION__];
85 : return nil;
86 : }
87 :
88 :
89 : // Designated initializer.
90 0 : - (id) initWithData:(NSData *)data
91 : radius:(GLfloat)radius
92 : {
93 : if ((self = [super init]))
94 : {
95 : _data = [data copy];
96 : _radius = radius;
97 :
98 : NSUInteger nodeCount = [_data length] / sizeof *_octree;
99 : NSParameterAssert(nodeCount < UINT32_MAX);
100 : _nodeCount = (uint32_t)nodeCount;
101 :
102 : _octree = [_data bytes];
103 :
104 : _collisionOctree = calloc(1, _nodeCount);
105 : if (_octree == NULL || _collisionOctree == NULL)
106 : {
107 : [self release];
108 : return nil;
109 : }
110 : }
111 :
112 : return self;
113 : }
114 :
115 :
116 : - (id) initWithDictionary:(NSDictionary *)dict
117 : {
118 : NSData *data = [dict objectForKey:@"octree"];
119 : if (![data isKindOfClass:[NSData class]] || ([data length] % sizeof (int)) != 0)
120 : {
121 : // Invalid representation.
122 : [self release];
123 : return nil;
124 : }
125 :
126 : return [self initWithData:data radius:[dict oo_floatForKey:@"radius"]];
127 : }
128 :
129 :
130 0 : - (void) dealloc
131 : {
132 : DESTROY(_data);
133 : free(_collisionOctree);
134 :
135 : [super dealloc];
136 : }
137 :
138 :
139 0 : - (BOOL) hasCollision
140 : {
141 : return _hasCollision;
142 : }
143 :
144 :
145 0 : - (void) setHasCollision:(BOOL)value
146 : {
147 : _hasCollision = !!value;
148 : }
149 :
150 :
151 0 : - (Octree_details) octreeDetails
152 : {
153 : Octree_details details =
154 : {
155 : .octree = _octree,
156 : .radius = _radius,
157 : .octree_collision = _collisionOctree
158 : };
159 : return details;
160 : }
161 :
162 :
163 : - (Octree *) octreeScaledBy:(GLfloat)factor
164 : {
165 : // Since octree data is immutable, we can share.
166 : return [[[Octree alloc] initWithData:_data radius:_radius * factor] autorelease];
167 : }
168 :
169 :
170 0 : static Vector offsetForOctant(int oct, GLfloat r)
171 : {
172 : return make_vector((0.5f - (GLfloat)((oct >> 2) & 1)) * r, (0.5f - (GLfloat)((oct >> 1) & 1)) * r, (0.5f - (GLfloat)(oct & 1)) * r);
173 : }
174 :
175 :
176 : #ifndef OODEBUGLDRAWING_DISABLE
177 :
178 : - (void) drawOctree
179 : {
180 : OODebugWFState state = OODebugBeginWireframe(NO);
181 :
182 : OO_ENTER_OPENGL();
183 : OOGL(glEnable(GL_BLEND));
184 : OOGLBEGIN(GL_LINES);
185 : glColor4f(0.4f, 0.4f, 0.4f, 0.5f);
186 :
187 : // it's a series of cubes
188 : [self drawOctreeFromLocation:0 :_radius : kZeroVector];
189 :
190 : OOGLEND();
191 :
192 : OODebugEndWireframe(state);
193 : OOCheckOpenGLErrors(@"Octree after drawing %@", self);
194 : }
195 :
196 :
197 : #if 0
198 : #define OCTREE_COLOR(r, g, b, a) glColor4f(r, g, b, a)
199 : #else
200 0 : #define OCTREE_COLOR(r, g, b, a) do {} while (0)
201 : #endif
202 :
203 :
204 0 : - (void) drawOctreeFromLocation:(uint32_t)loc :(GLfloat)scale :(Vector)offset
205 : {
206 : if (_octree[loc] == 0)
207 : {
208 : return;
209 : }
210 :
211 : OO_ENTER_OPENGL();
212 :
213 : if (_octree[loc] == -1) // full
214 : {
215 : // draw a cube
216 : glVertex3f(-scale + offset.x, -scale + offset.y, -scale + offset.z);
217 : glVertex3f(-scale + offset.x, scale + offset.y, -scale + offset.z);
218 : glVertex3f(-scale + offset.x, scale + offset.y, -scale + offset.z);
219 : glVertex3f(scale + offset.x, scale + offset.y, -scale + offset.z);
220 : glVertex3f(scale + offset.x, scale + offset.y, -scale + offset.z);
221 : glVertex3f(scale + offset.x, -scale + offset.y, -scale + offset.z);
222 : glVertex3f(scale + offset.x, -scale + offset.y, -scale + offset.z);
223 : glVertex3f(-scale + offset.x, -scale + offset.y, -scale + offset.z);
224 :
225 :
226 : glVertex3f(-scale + offset.x, -scale + offset.y, scale + offset.z);
227 : glVertex3f(-scale + offset.x, scale + offset.y, scale + offset.z);
228 : glVertex3f(-scale + offset.x, scale + offset.y, scale + offset.z);
229 : glVertex3f(scale + offset.x, scale + offset.y, scale + offset.z);
230 : glVertex3f(scale + offset.x, scale + offset.y, scale + offset.z);
231 : glVertex3f(scale + offset.x, -scale + offset.y, scale + offset.z);
232 : glVertex3f(scale + offset.x, -scale + offset.y, scale + offset.z);
233 : glVertex3f(-scale + offset.x, -scale + offset.y, scale + offset.z);
234 :
235 : glVertex3f(-scale + offset.x, -scale + offset.y, -scale + offset.z);
236 : glVertex3f(-scale + offset.x, -scale + offset.y, scale + offset.z);
237 :
238 : glVertex3f(-scale + offset.x, scale + offset.y, -scale + offset.z);
239 : glVertex3f(-scale + offset.x, scale + offset.y, scale + offset.z);
240 :
241 : glVertex3f(scale + offset.x, scale + offset.y, -scale + offset.z);
242 : glVertex3f(scale + offset.x, scale + offset.y, scale + offset.z);
243 :
244 : glVertex3f(scale + offset.x, -scale + offset.y, -scale + offset.z);
245 : glVertex3f(scale + offset.x, -scale + offset.y, scale + offset.z);
246 : }
247 : else if (_octree[loc] > 0)
248 : {
249 : GLfloat sc = 0.5f * scale;
250 : OCTREE_COLOR(0.4f, 0.4f, 0.4f, 0.5f);
251 : [self drawOctreeFromLocation:loc + _octree[loc] + 0 :sc :make_vector(offset.x - sc, offset.y - sc, offset.z - sc)];
252 : OCTREE_COLOR(0.0f, 0.0f, 1.0f, 0.5f);
253 : [self drawOctreeFromLocation:loc + _octree[loc] + 1 :sc :make_vector(offset.x - sc, offset.y - sc, offset.z + sc)];
254 : OCTREE_COLOR(0.0f, 1.0f, 0.0f, 0.5f);
255 : [self drawOctreeFromLocation:loc + _octree[loc] + 2 :sc :make_vector(offset.x - sc, offset.y + sc, offset.z - sc)];
256 : OCTREE_COLOR(0.0f, 1.0f, 1.0f, 0.5f);
257 : [self drawOctreeFromLocation:loc + _octree[loc] + 3 :sc :make_vector(offset.x - sc, offset.y + sc, offset.z + sc)];
258 : OCTREE_COLOR(1.0f, 0.0f, 0.0f, 0.5f);
259 : [self drawOctreeFromLocation:loc + _octree[loc] + 4 :sc :make_vector(offset.x + sc, offset.y - sc, offset.z - sc)];
260 : OCTREE_COLOR(1.0f, 0.0f, 1.0f, 0.5f);
261 : [self drawOctreeFromLocation:loc + _octree[loc] + 5 :sc :make_vector(offset.x + sc, offset.y - sc, offset.z + sc)];
262 : OCTREE_COLOR(1.0f, 1.0f, 0.0f, 0.5f);
263 : [self drawOctreeFromLocation:loc + _octree[loc] + 6 :sc :make_vector(offset.x + sc, offset.y + sc, offset.z - sc)];
264 : OCTREE_COLOR(1.0f, 1.0f, 1.0f, 0.5f);
265 : [self drawOctreeFromLocation:loc + _octree[loc] + 7 :sc :make_vector(offset.x + sc, offset.y + sc, offset.z + sc)];
266 : }
267 : }
268 :
269 :
270 0 : static BOOL drawTestForCollisions;
271 :
272 : - (void) drawOctreeCollisions
273 : {
274 : OODebugWFState state = OODebugBeginWireframe(NO);
275 :
276 : // it's a series of cubes
277 : drawTestForCollisions = NO;
278 : if (_hasCollision)
279 : {
280 : [self drawOctreeCollisionFromLocation:0 :_radius :kZeroVector];
281 : }
282 : _hasCollision = drawTestForCollisions;
283 :
284 : OODebugEndWireframe(state);
285 : OOCheckOpenGLErrors(@"Octree after drawing collisions for %@", self);
286 : }
287 :
288 :
289 0 : - (void) drawOctreeCollisionFromLocation:(uint32_t)loc :(GLfloat)scale :(Vector)offset
290 : {
291 : if (_octree[loc] == 0)
292 : {
293 : return;
294 : }
295 :
296 : if ((_octree[loc] != 0)&&(_collisionOctree[loc] != (unsigned char)0)) // full - draw
297 : {
298 : OO_ENTER_OPENGL();
299 :
300 : GLfloat red = (GLfloat)(_collisionOctree[loc])/255.0;
301 : glColor4f(1.0, 0.0, 0.0, red); // 50% translucent
302 :
303 : drawTestForCollisions = YES;
304 : _collisionOctree[loc]--;
305 :
306 : // draw a cube
307 : OOGL(glDisable(GL_CULL_FACE)); // face culling
308 :
309 : OOGL(glDisable(GL_TEXTURE_2D));
310 :
311 : OOGLBEGIN(GL_LINE_STRIP);
312 : glVertex3f(-scale + offset.x, -scale + offset.y, -scale + offset.z);
313 : glVertex3f(-scale + offset.x, scale + offset.y, -scale + offset.z);
314 : glVertex3f(scale + offset.x, scale + offset.y, -scale + offset.z);
315 : glVertex3f(scale + offset.x, -scale + offset.y, -scale + offset.z);
316 : glVertex3f(-scale + offset.x, -scale + offset.y, -scale + offset.z);
317 : OOGLEND();
318 :
319 : OOGLBEGIN(GL_LINE_STRIP);
320 : glVertex3f(-scale + offset.x, -scale + offset.y, scale + offset.z);
321 : glVertex3f(-scale + offset.x, scale + offset.y, scale + offset.z);
322 : glVertex3f(scale + offset.x, scale + offset.y, scale + offset.z);
323 : glVertex3f(scale + offset.x, -scale + offset.y, scale + offset.z);
324 : glVertex3f(-scale + offset.x, -scale + offset.y, scale + offset.z);
325 : OOGLEND();
326 :
327 : OOGLBEGIN(GL_LINES);
328 : glVertex3f(-scale + offset.x, -scale + offset.y, -scale + offset.z);
329 : glVertex3f(-scale + offset.x, -scale + offset.y, scale + offset.z);
330 :
331 : glVertex3f(-scale + offset.x, scale + offset.y, -scale + offset.z);
332 : glVertex3f(-scale + offset.x, scale + offset.y, scale + offset.z);
333 :
334 : glVertex3f(scale + offset.x, scale + offset.y, -scale + offset.z);
335 : glVertex3f(scale + offset.x, scale + offset.y, scale + offset.z);
336 :
337 : glVertex3f(scale + offset.x, -scale + offset.y, -scale + offset.z);
338 : glVertex3f(scale + offset.x, -scale + offset.y, scale + offset.z);
339 : OOGLEND();
340 :
341 : OOGL(glEnable(GL_CULL_FACE)); // face culling
342 : }
343 : if (_octree[loc] > 0)
344 : {
345 : GLfloat sc = 0.5f * scale;
346 : [self drawOctreeCollisionFromLocation:loc + _octree[loc] + 0 :sc :make_vector(offset.x - sc, offset.y - sc, offset.z - sc)];
347 : [self drawOctreeCollisionFromLocation:loc + _octree[loc] + 1 :sc :make_vector(offset.x - sc, offset.y - sc, offset.z + sc)];
348 : [self drawOctreeCollisionFromLocation:loc + _octree[loc] + 2 :sc :make_vector(offset.x - sc, offset.y + sc, offset.z - sc)];
349 : [self drawOctreeCollisionFromLocation:loc + _octree[loc] + 3 :sc :make_vector(offset.x - sc, offset.y + sc, offset.z + sc)];
350 : [self drawOctreeCollisionFromLocation:loc + _octree[loc] + 4 :sc :make_vector(offset.x + sc, offset.y - sc, offset.z - sc)];
351 : [self drawOctreeCollisionFromLocation:loc + _octree[loc] + 5 :sc :make_vector(offset.x + sc, offset.y - sc, offset.z + sc)];
352 : [self drawOctreeCollisionFromLocation:loc + _octree[loc] + 6 :sc :make_vector(offset.x + sc, offset.y + sc, offset.z - sc)];
353 : [self drawOctreeCollisionFromLocation:loc + _octree[loc] + 7 :sc :make_vector(offset.x + sc, offset.y + sc, offset.z + sc)];
354 : }
355 : }
356 : #endif // OODEBUGLDRAWING_DISABLE
357 :
358 :
359 0 : static BOOL isHitByLineSub(const int *octbuffer, unsigned char *collbuffer, int nextLevel, GLfloat rad, GLfloat rd2, Vector v0, Vector v1, int octantMask)
360 : {
361 : if (octbuffer[nextLevel + octantMask])
362 : {
363 : Vector moveLine = offsetForOctant(octantMask, rad);
364 : return isHitByLine(octbuffer, collbuffer, nextLevel + octantMask, rd2, v0, v1, moveLine, 0);
365 : }
366 : else return NO;
367 : }
368 :
369 :
370 0 : static BOOL hasCollided = NO;
371 0 : static GLfloat hit_dist = 0.0;
372 0 : static BOOL isHitByLine(const int *octbuffer, unsigned char *collbuffer, int level, GLfloat rad, Vector v0, Vector v1, Vector off, int face_hit)
373 : {
374 : // displace the line by the offset
375 : Vector u0 = make_vector(v0.x + off.x, v0.y + off.y, v0.z + off.z);
376 : Vector u1 = make_vector(v1.x + off.x, v1.y + off.y, v1.z + off.z);
377 :
378 : OctreeDebugLog(@"DEBUG octant: [%d] radius: %.2f vs. line: (%.2f, %.2f, %.2f) - (%.2f, %.2f, %.2f)",
379 : level, rad, u0.x, u0.y, u0.z, u1.x, u1.y, u1.z);
380 :
381 : if (octbuffer[level] == 0)
382 : {
383 : OctreeDebugLog(@"DEBUG Hit an empty octant: [%d]", level);
384 : return NO;
385 : }
386 :
387 : if (octbuffer[level] == -1)
388 : {
389 : OctreeDebugLog(@"DEBUG Hit a solid octant: [%d]", level);
390 : collbuffer[level] = 2; // green
391 : hit_dist = sqrt(u0.x * u0.x + u0.y * u0.y + u0.z * u0.z);
392 : return YES;
393 : }
394 :
395 : int faces = face_hit;
396 : if (faces == 0)
397 : faces = lineCubeIntersection(u0, u1, rad);
398 :
399 : if (faces == 0)
400 : {
401 : OctreeDebugLog(@"----> Line misses octant: [%d].", level);
402 : return NO;
403 : }
404 :
405 : int octantIntersected = 0;
406 :
407 : if (faces > 0)
408 : {
409 : Vector vi = lineIntersectionWithFace(u0, u1, faces, rad);
410 :
411 : if (CUBE_FACE_FRONT & faces)
412 : octantIntersected = ((vi.x < 0.0)? 1: 5) + ((vi.y < 0.0)? 0: 2);
413 : if (CUBE_FACE_BACK & faces)
414 : octantIntersected = ((vi.x < 0.0)? 0: 4) + ((vi.y < 0.0)? 0: 2);
415 :
416 : if (CUBE_FACE_RIGHT & faces)
417 : octantIntersected = ((vi.y < 0.0)? 4: 6) + ((vi.z < 0.0)? 0: 1);
418 : if (CUBE_FACE_LEFT & faces)
419 : octantIntersected = ((vi.y < 0.0)? 0: 2) + ((vi.z < 0.0)? 0: 1);
420 :
421 : if (CUBE_FACE_TOP & faces)
422 : octantIntersected = ((vi.x < 0.0)? 2: 6) + ((vi.z < 0.0)? 0: 1);
423 : if (CUBE_FACE_BOTTOM & faces)
424 : octantIntersected = ((vi.x < 0.0)? 0: 4) + ((vi.z < 0.0)? 0: 1);
425 :
426 : OctreeDebugLog(@"----> found intersection with face 0x%2x of cube of radius %.2f at (%.2f, %.2f, %.2f) octant:%d",
427 : faces, rad, vi.x, vi.y, vi.z, octantIntersected);
428 : }
429 : else
430 : {
431 : OctreeDebugLog(@"----> inside cube of radius %.2f octant:%d", rad, octantIntersected);
432 : }
433 :
434 : hasCollided = YES;
435 :
436 : collbuffer[level] = 1; // red
437 :
438 : OctreeDebugLog(@"%@", @"----> testing octants...");
439 :
440 : int nextLevel = level + octbuffer[level];
441 :
442 : GLfloat rd2 = 0.5f * rad;
443 :
444 : // first test the intersected octant, then the three adjacent, then the next three adjacent, the finally the diagonal octant
445 : int oct0, oct1, oct2, oct3; // test oct0 then oct1, oct2, oct3 then (7 - oct1), (7 - oct2), (7 - oct3) then (7 - oct0)
446 : oct0 = octantIntersected;
447 : oct1 = oct0 ^ 0x01; // adjacent x
448 : oct2 = oct0 ^ 0x02; // adjacent y
449 : oct3 = oct0 ^ 0x04; // adjacent z
450 :
451 : OctreeDebugLog(@"----> testing first octant hit [+%d]", oct0);
452 : if (isHitByLineSub(octbuffer, collbuffer, nextLevel, rad, rd2, u0, u1, oct0)) return YES; // first octant
453 :
454 : // test the three adjacent octants
455 :
456 : OctreeDebugLog(@"----> testing next three octants [+%d] [+%d] [+%d]", oct1, oct2, oct3);
457 : if (isHitByLineSub(octbuffer, collbuffer, nextLevel, rad, rd2, u0, u1, oct1)) return YES; // second octant
458 : if (isHitByLineSub(octbuffer, collbuffer, nextLevel, rad, rd2, u0, u1, oct2)) return YES; // third octant
459 : if (isHitByLineSub(octbuffer, collbuffer, nextLevel, rad, rd2, u0, u1, oct3)) return YES; // fourth octant
460 :
461 : // go to the next four octants
462 :
463 : oct0 ^= 0x07; oct1 ^= 0x07; oct2 ^= 0x07; oct3 ^= 0x07;
464 :
465 : OctreeDebugLog(@"----> testing back three octants [+%d] [+%d] [+%d]", oct1, oct2, oct3);
466 : if (isHitByLineSub(octbuffer, collbuffer, nextLevel, rad, rd2, u0, u1, oct1)) return YES; // fifth octant
467 : if (isHitByLineSub(octbuffer, collbuffer, nextLevel, rad, rd2, u0, u1, oct2)) return YES; // sixth octant
468 : if (isHitByLineSub(octbuffer, collbuffer, nextLevel, rad, rd2, u0, u1, oct3)) return YES; // seventh octant
469 :
470 : // and check the last octant
471 : OctreeDebugLog(@"----> testing final octant [+%d]", oct0);
472 : if (isHitByLineSub(octbuffer, collbuffer, nextLevel, rad, rd2, u0, u1, oct0)) return YES; // last octant
473 :
474 : return NO;
475 : }
476 :
477 : - (GLfloat) isHitByLine:(Vector)v0 :(Vector)v1
478 : {
479 : memset(_collisionOctree, 0, _nodeCount * sizeof *_collisionOctree);
480 : hasCollided = NO;
481 :
482 : if (isHitByLine(_octree, _collisionOctree, 0, _radius, v0, v1, kZeroVector, 0))
483 : {
484 : OctreeDebugLog(@"DEBUG Hit at distance %.2f", hit_dist);
485 : _hasCollision = hasCollided;
486 : return hit_dist;
487 : }
488 : else
489 : {
490 : OctreeDebugLog(@"%@", @"DEBUG Missed!");
491 : _hasCollision = hasCollided;
492 : return 0.0f;
493 : }
494 : }
495 :
496 :
497 0 : static BOOL isHitByOctree(Octree_details axialDetails,
498 : Octree_details otherDetails, Vector otherPosition, Triangle other_ijk)
499 : {
500 : const int *axialBuffer = axialDetails.octree;
501 : const int *otherBuffer = otherDetails.octree;
502 :
503 : if (axialBuffer[0] == 0)
504 : {
505 : OctreeDebugLog(@"%@", @"DEBUG Axial octree is empty.");
506 : return NO;
507 : }
508 :
509 : if (!otherBuffer)
510 : {
511 : OctreeDebugLog(@"%@", @"DEBUG Other octree is undefined.");
512 : return NO;
513 : }
514 :
515 : if (otherBuffer[0] == 0)
516 : {
517 : OctreeDebugLog(@"%@", @"DEBUG Other octree is empty.");
518 : return NO;
519 : }
520 :
521 : GLfloat axialRadius = axialDetails.radius;
522 : GLfloat otherRadius = otherDetails.radius;
523 :
524 : if (otherRadius < axialRadius) // test axial cube against other sphere
525 : {
526 : // 'crude and simple' - test sphere against cube...
527 : if ((otherPosition.x + otherRadius < -axialRadius)||(otherPosition.x - otherRadius > axialRadius)||
528 : (otherPosition.y + otherRadius < -axialRadius)||(otherPosition.y - otherRadius > axialRadius)||
529 : (otherPosition.z + otherRadius < -axialRadius)||(otherPosition.z - otherRadius > axialRadius))
530 : {
531 : OctreeDebugLog(@"%@", @"----> Other sphere does not intersect axial cube");
532 : return NO;
533 : }
534 : }
535 : else // test axial sphere against other cube
536 : {
537 : Vector d2 = vector_flip(otherPosition);
538 : Vector axialPosition = resolveVectorInIJK(d2, other_ijk);
539 : if ((axialPosition.x + axialRadius < -otherRadius)||(axialPosition.x - axialRadius > otherRadius)||
540 : (axialPosition.y + axialRadius < -otherRadius)||(axialPosition.y - axialRadius > otherRadius)||
541 : (axialPosition.z + axialRadius < -otherRadius)||(axialPosition.z - axialRadius > otherRadius))
542 : {
543 : OctreeDebugLog(@"%@", @"----> Axial sphere does not intersect other cube");
544 : return NO;
545 : }
546 : }
547 :
548 : // from here on, this Octree and the other Octree are considered to be intersecting
549 : unsigned char *axialCollisionBuffer = axialDetails.octree_collision;
550 : unsigned char *otherCollisionBuffer = otherDetails.octree_collision;
551 : if (axialBuffer[0] == -1)
552 : {
553 : // we are SOLID - is the other octree?
554 : if (otherBuffer[0] == -1)
555 : {
556 : // YES so octrees collide
557 : axialCollisionBuffer[0] = (unsigned char)255; // mark
558 : otherCollisionBuffer[0] = (unsigned char)255; // mark
559 :
560 : OctreeDebugLog(@"%@", @"DEBUG Octrees collide!");
561 : return YES;
562 : }
563 : // the other octree must be decomposed
564 : // and each of its octants tested against the axial octree
565 : // if any of them collides with this octant
566 : // then we have a solid collision
567 :
568 : OctreeDebugLog(@"%@", @"----> testing other octants...");
569 :
570 : // work out the nearest octant to the axial octree
571 : int nearest_oct = ((otherPosition.x > 0.0)? 0:4)|((otherPosition.y > 0.0)? 0:2)|((otherPosition.z > 0.0)? 0:1);
572 :
573 : int nextLevel = otherBuffer[0];
574 : const int *nextBuffer = &otherBuffer[nextLevel];
575 : unsigned char *nextCollisionBuffer = &otherCollisionBuffer[nextLevel];
576 : Octree_details nextDetails;
577 : Vector voff, nextPosition;
578 : unsigned i, oct;
579 :
580 : nextDetails.radius = 0.5f * otherRadius;
581 : for (i = 0; i < 8; i++)
582 : {
583 : oct = nearest_oct ^ change_oct[i]; // work from nearest to furthest
584 : if (nextBuffer[oct]) // don't test empty octants
585 : {
586 : nextDetails.octree = &nextBuffer[oct];
587 : nextDetails.octree_collision = &nextCollisionBuffer[oct];
588 :
589 : voff = resolveVectorInIJK(offsetForOctant(oct, otherRadius), other_ijk);
590 : nextPosition = vector_subtract(otherPosition, voff);
591 : if (isHitByOctree(axialDetails, nextDetails, nextPosition, other_ijk)) // test octant
592 : return YES;
593 : }
594 : }
595 :
596 : // otherwise
597 : return NO;
598 : }
599 : // we are not solid
600 : // we must test each of our octants against
601 : // the other octree, if any of them collide
602 : // we have a solid collision
603 :
604 : OctreeDebugLog(@"%@", @"----> testing axial octants...");
605 :
606 : // work out the nearest octant to the other octree
607 : int nearest_oct = ((otherPosition.x > 0.0)? 4:0)|((otherPosition.y > 0.0)? 2:0)|((otherPosition.z > 0.0)? 1:0);
608 :
609 : int nextLevel = axialBuffer[0];
610 : const int *nextBuffer = &axialBuffer[nextLevel];
611 : unsigned char *nextCollisionBuffer = &axialCollisionBuffer[nextLevel];
612 : Vector nextPosition;
613 : Octree_details nextDetails;
614 : unsigned i, oct;
615 :
616 : nextDetails.radius = 0.5f * axialRadius;
617 : for (i = 0; i < 8; i++)
618 : {
619 : oct = nearest_oct ^ change_oct[i]; // work from nearest to furthest
620 : if (nextBuffer[oct]) // don't test empty octants
621 : {
622 : nextDetails.octree = &nextBuffer[oct];
623 : nextDetails.octree_collision = &nextCollisionBuffer[oct];
624 :
625 : nextPosition = vector_add(otherPosition, offsetForOctant(oct, axialRadius));
626 : if (isHitByOctree(nextDetails, otherDetails, nextPosition, other_ijk))
627 : {
628 : return YES; // test octant
629 : }
630 : }
631 : }
632 : // otherwise we're done!
633 : return NO;
634 : }
635 :
636 :
637 : - (BOOL) isHitByOctree:(Octree *)other withOrigin:(Vector)v0 andIJK:(Triangle)ijk
638 : {
639 : if (other == nil) return NO;
640 :
641 : BOOL hit = isHitByOctree([self octreeDetails], [other octreeDetails], v0, ijk);
642 :
643 : _hasCollision = _hasCollision || hit;
644 : [other setHasCollision: [other hasCollision] || hit];
645 :
646 : return hit;
647 : }
648 :
649 :
650 : - (BOOL) isHitByOctree:(Octree *)other withOrigin:(Vector)v0 andIJK:(Triangle)ijk andScales:(GLfloat) s1 :(GLfloat)s2
651 : {
652 : Octree_details details1 = [self octreeDetails];
653 : Octree_details details2 = [other octreeDetails];
654 :
655 : details1.radius *= s1;
656 : details2.radius *= s2;
657 :
658 : BOOL hit = isHitByOctree(details1, details2, v0, ijk);
659 :
660 : _hasCollision = _hasCollision || hit;
661 : [other setHasCollision: [other hasCollision] || hit];
662 :
663 : return hit;
664 : }
665 :
666 :
667 : - (NSDictionary *) dictionaryRepresentation
668 : {
669 : return [NSDictionary dictionaryWithObjectsAndKeys:
670 : _data, @"octree",
671 : [NSNumber numberWithFloat:_radius], @"radius",
672 : nil];
673 : }
674 :
675 :
676 0 : static GLfloat volumeOfOctree(Octree_details octree_details, unsigned depthLimit)
677 : {
678 : const int *octBuffer = octree_details.octree;
679 : GLfloat octRadius = octree_details.radius;
680 :
681 : if (octBuffer[0] == 0)
682 : {
683 : return 0.0f;
684 : }
685 :
686 : if (octBuffer[0] == -1 || depthLimit == 0)
687 : {
688 : return octRadius * octRadius * octRadius;
689 : }
690 : depthLimit--;
691 :
692 : // We are not empty or solid.
693 : // We sum the volume of each of our octants.
694 : GLfloat sumVolume = 0.0f;
695 : Octree_details nextDetails;
696 : int nextLevel = octBuffer[0];
697 : const int *nextBuffer = &octBuffer[nextLevel];
698 : unsigned i;
699 :
700 : nextDetails.radius = 0.5f * octRadius;
701 : nextDetails.octree_collision = NULL; // Placate static analyzer
702 :
703 : for (i = 0; i < 8; i++)
704 : {
705 : if (nextBuffer[i]) // don't test empty octants
706 : {
707 : nextDetails.octree = &nextBuffer[i];
708 : sumVolume += volumeOfOctree(nextDetails, depthLimit);
709 : }
710 : }
711 : return sumVolume;
712 : }
713 :
714 :
715 : - (GLfloat) volume
716 : {
717 : /* For backwards compatibility, limit octree iteration for volume
718 : calculation to five levels. Raising the limit means lower calculated
719 : volumes for large ships.
720 :
721 : EMMSTRAN: consider raising the limit but fudging mass lock calculations
722 : to compensate. See http://aegidian.org/bb/viewtopic.php?f=3&t=9176 .
723 : Then again, five levels of iteration might be fine.
724 : -- Ahruman 2011-03-10
725 : */
726 : return volumeOfOctree([self octreeDetails], 5);
727 : }
728 :
729 :
730 0 : static Vector randomFullNodeFrom(Octree_details details, Vector offset)
731 : {
732 : const int *octBuffer = details.octree;
733 : GLfloat octRadius = details.radius;
734 :
735 : if (octBuffer[0] == 0) return offset;
736 : if (octBuffer[0] == -1) return offset;
737 :
738 : // We are not empty or solid.
739 : // Pick a location from a random octant.
740 : Octree_details nextDetails;
741 : int nextLevel = octBuffer[0];
742 : const int *nextBuffer = &octBuffer[nextLevel];
743 : unsigned i, oct;
744 :
745 : nextDetails.radius = 0.5f * octRadius;
746 : nextDetails.octree_collision = NULL;
747 : oct = Ranrot() & 7;
748 :
749 : for (i = 0; i < 8; i++)
750 : {
751 : int octant = oct ^ i;
752 : if (nextBuffer[octant]) // don't test empty octants
753 : {
754 : nextDetails.octree = &nextBuffer[octant];
755 : Vector voff = vector_add(offset, offsetForOctant(octant, octRadius));
756 : return randomFullNodeFrom(nextDetails, voff);
757 : }
758 : }
759 : return offset;
760 : }
761 :
762 :
763 : - (Vector) randomPoint
764 : {
765 : return randomFullNodeFrom([self octreeDetails], kZeroVector);
766 : }
767 :
768 :
769 : #ifndef NDEBUG
770 : - (size_t) totalSize
771 : {
772 : return [self oo_objectSize] + _nodeCount * [_data oo_objectSize] + [_data length] + _nodeCount * sizeof *_collisionOctree;
773 : }
774 : #endif
775 :
776 : @end
777 :
778 :
779 0 : enum
780 : {
781 : /*
782 : Initial capacity of OOOctreeBuilder. 16 KibiEntries is enough to handle
783 : all but 2 built-in models; I expect similar results for OXPs, since
784 : geometry detail has limited effect on the octree. Large models with
785 : higher depth are more likely to need growth.
786 : */
787 : kMinimumBuilderCapacity = 16 << 10
788 : };
789 :
790 :
791 : @implementation OOOctreeBuilder
792 :
793 : // Extract top of state stack.
794 0 : OOINLINE struct OOOctreeBuildState *State(OOOctreeBuilder *self)
795 : {
796 : return &self->_stateStack[self->_level];
797 : }
798 :
799 :
800 : // SetNode(): set the value of an entry in _octree, making space if needed.
801 0 : static void SetNode_slow(OOOctreeBuilder *self, uint32_t index, int value) NO_INLINE_FUNC;
802 0 : OOINLINE void SetNode(OOOctreeBuilder *self, uint32_t index, int value)
803 : {
804 : if (index < self->_capacity)
805 : {
806 : self->_octree[index] = value;
807 : }
808 : else
809 : {
810 : SetNode_slow(self, index, value);
811 : }
812 : }
813 :
814 :
815 : // InsertNode(): set the node at the current insertion point, and increment insertion point.
816 0 : OOINLINE void InsertNode(OOOctreeBuilder *self, int value)
817 : {
818 : NSCAssert(State(self)->remaining > 0, @"Attempt to add node to a full parent in octree builder.");
819 : State(self)->remaining--;
820 :
821 : SetNode(self, State(self)->insertionPoint++, value);
822 : }
823 :
824 :
825 0 : - (id) init
826 : {
827 : if ((self = [super init]))
828 : {
829 : _capacity = kMinimumBuilderCapacity;
830 : _octree = malloc(_capacity * sizeof *_octree);
831 : if (_octree == NULL)
832 : {
833 : [self release];
834 : return nil;
835 : }
836 :
837 : /*
838 : We're initially inserting into the root slot, which must exist and
839 : takes a single node.
840 : */
841 : _nodeCount = 1;
842 : State(self)->remaining = 1;
843 : }
844 : return self;
845 : }
846 :
847 :
848 0 : - (void) dealloc
849 : {
850 : free(_octree);
851 :
852 : [super dealloc];
853 : }
854 :
855 :
856 : - (Octree *) buildOctreeWithRadius:(GLfloat)radius
857 : {
858 : NSAssert(State(self)->remaining == 0 && _level == 0, @"Attempt to produce octree from an octree builder in an incomplete state.");
859 :
860 : size_t dataSize = _nodeCount * sizeof *_octree;
861 : int *resized = realloc(_octree, dataSize);
862 : if (resized == NULL) resized = _octree;
863 :
864 : /* Hand over the bytes to the data object, which will be used directly by
865 : the Octree.
866 : */
867 : NSData *data = [NSData dataWithBytesNoCopy:resized
868 : length:dataSize
869 : freeWhenDone:YES];
870 :
871 : _octree = NULL;
872 : _nodeCount = 0;
873 : _capacity = 0;
874 :
875 : return [[[Octree alloc] initWithData:data radius:radius] autorelease];
876 : }
877 :
878 :
879 : - (void) writeSolid
880 : {
881 : InsertNode(self, -1);
882 : }
883 :
884 :
885 : - (void) writeEmpty
886 : {
887 : InsertNode(self, 0);
888 : }
889 :
890 :
891 : - (void) beginInnerNode
892 : {
893 : NSAssert(_level < kMaxOctreeDepth, @"Attempt to build octree exceeding maximum depth.");
894 :
895 : // Insert relative offset to next free space.
896 : uint32_t newInsertionPoint = _nodeCount;
897 : InsertNode(self, (int)_nodeCount - State(self)->insertionPoint);
898 :
899 : /*
900 : Leave space for eight nodes.
901 :
902 : NOTE: this may leave memory uninitialized or leave _nodeCount pointing
903 : past the end of the buffer. A valid sequence of eight child insertions
904 : will fix both these problems by writing to all of the new slots.
905 : */
906 : _nodeCount += 8;
907 :
908 : // Push state and set up new "stack frame".
909 : _level++;
910 : State(self)->insertionPoint = newInsertionPoint;
911 : State(self)->remaining = 8;
912 : }
913 :
914 :
915 : - (void) endInnerNode
916 : {
917 : NSAssert(State(self)->remaining == 0, @"Attempt to end an inner octree node with fewer than eight children.");
918 : NSAssert1(_level > 0, @"Unbalanced call to %s", __FUNCTION__);
919 :
920 : _level--;
921 :
922 : /*
923 : Check if the last eight nodes are solid. If so, we just inserted an
924 : entirely solid subtree and can fold it into a single solid node. An
925 : entirely solid subtree will always use the last eight nodes (any solid
926 : subtrees within a child node will have been folded already), so this
927 : simple approach to folding will produce an optimal result.
928 :
929 : We could do the same for empty nodes, but OOMeshToOctreeConverter will
930 : never recurse into an empty subtree.
931 : */
932 :
933 : NSAssert(_nodeCount > 8, @"After ending an inner node, there must be at least eight nodes in buffer.");
934 : for (uint_fast32_t node = _nodeCount - 8; node < _nodeCount; node++)
935 : {
936 : if (_octree[node] != -1) return;
937 : }
938 :
939 : // If we got here, subtree is solid; fold it into a solid node.
940 : _octree[State(self)->insertionPoint - 1] = -1;
941 : _nodeCount -= 8;
942 : }
943 :
944 :
945 : // Slow path for SetNode() when writing beyond _capacity: expand, then perform set.
946 : static void SetNode_slow(OOOctreeBuilder *self, uint32_t index, int value)
947 : {
948 : uint32_t newCapacity = MAX(self->_capacity * 2, (uint32_t)kMinimumBuilderCapacity);
949 : newCapacity = MAX(newCapacity, index + 1);
950 :
951 : int *newBuffer = realloc(self->_octree, newCapacity * sizeof *newBuffer);
952 : if (EXPECT_NOT(newBuffer == NULL))
953 : {
954 : [NSException raise:NSMallocException format:@"Failed to allocate memory for octree."];
955 : }
956 :
957 : self->_octree = newBuffer;
958 : self->_capacity = newCapacity;
959 : self->_octree[index] = value;
960 : }
961 :
962 :
963 : #ifndef NDEBUG
964 : /* This method exists purely to suppress Clang static analyzer warnings that
965 : these ivars are unused (but may be used by categories, which they are).
966 : */
967 0 : - (BOOL) suppressClangStuff
968 : {
969 : return &_stateStack && 0;
970 : }
971 : #endif
972 :
973 : @end
|
