Line data Source code
1 0 : /*
2 :
3 : OOMeshToOctreeConverter.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 "OOMeshToOctreeConverter.h"
26 :
27 :
28 : /*
29 : DESIGN NOTES
30 :
31 : OOMeshToOctreeConverter is responsible for analyzing a set of triangles
32 : from an OOMesh and turning them into an Octree using OOOctreeBuilder. This
33 : is a relatively heavyweight operation which is run on the main thread when
34 : loading a ship that isn't cached. Since ship set-up affects startup time
35 : and in-game stutter, this is performance-critical.
36 :
37 : The octree generation algorithm works as follows:
38 : Given a set of triangles within a bounding cube, and an iteration limit,
39 : do the following:
40 : * If the set of triangles is empty, produce an empty octree node.
41 : * Otherwise, if the iteration limit is reached, produce a solid node.
42 : * Otherwise, divide the set of triangles into eight equally-sized child
43 : cubes (splitting triangles if needed); create an inner node in the octree;
44 : and repeat the algorithm for each of the eight children.
45 :
46 : OOOctreeBuilder performs a simple structural optimization where an inner
47 : node whose child nodes are all solid is replaced with a solid node. This
48 : is effective recursively and very cheap. As such, there is no need for
49 : OOMeshToOctreeConverter to try to detect this situation.
50 :
51 : On a typical cold startup with no OXPs loaded, well over two million octree
52 : nodes are processed by OOMeshToOctreeConverter. The highest number of nodes
53 : in existence at once is 53. Our main performance concerns are to minimize
54 : the amount of memory managment per node and to avoid dynamic dispatch in
55 : critical areas, while minimizing the number of allocations per node is not
56 : very important.
57 :
58 : The current implementation uses a struct (defined in the header as
59 : OOMeshToOctreeConverterInternalData, and locally known as GeometryData)
60 : to store the triangle set. The root GeometryData is an instance variable
61 : of OOMeshToOctreeConverter, and children are created on the stack while
62 : iterating.
63 :
64 : Up to sixteen triangles can be stored directly in the GeometryData. If more
65 : than sixteen are needed, a heap-allocated array is used instead. At one
66 : point, I attempted to be cleverer about the storage using unions and implied
67 : capacity, but this was significantly slower with only small amounts of stack
68 : space saved.
69 :
70 : Profiling shows that over 93 % of nodes use sixteen or fewer triangles in
71 : vanilla Oolite. The proportion is lower when using OXPs with more complex
72 : models.
73 : */
74 :
75 : #import "OOMaths.h"
76 : #import "Octree.h"
77 : #import "OOLogging.h"
78 :
79 :
80 : // MARK: GeometryData operations.
81 :
82 : /*
83 : GeometryData
84 :
85 : Struct tracking a set of triangles. Must be initialized using
86 : InitGeometryData() before other operations.
87 :
88 : capacity is an estimate of the required size. If the number of triangles
89 : added exceeds kOOMeshToOctreeConverterSmallDataCapacity, the capacity will
90 : be used as the initial heap-allocated size, unless it's smaller than a
91 : minimum threshold.
92 :
93 :
94 : Triangle *triangles
95 : Pointer to the triangle array. Initially points at smallData.
96 :
97 : uint_fast32_t count
98 : The number of triangles currently in the GeometryData.
99 :
100 : uint_fast32_t capacity
101 : The number of slots in triangles. Invariant: count <= capacity.
102 :
103 : uint_fast32_t pendingCapacity
104 : The capacity hint passed to InitGeometryData(). Used by
105 : AddTriangle_slow().
106 :
107 : Triangle smallData[]
108 : Initial triangle storage. Should not be accessed directly; if it's
109 : relevant, triangles points to it.
110 : */
111 0 : typedef struct OOMeshToOctreeConverterInternalData GeometryData;
112 :
113 :
114 : /*
115 : InitGeometryData(data, capacity)
116 :
117 : Prepare a GeometryData struct for use.
118 : The data has to be by reference rather than a return value so that the
119 : triangles pointer can be pointed into the struct.
120 : */
121 : OOINLINE void InitGeometryData(GeometryData *data, uint_fast32_t capacity);
122 :
123 : /*
124 : DestroyGeometryData(data)
125 :
126 : Deallocates dynamic storage if necessary. Leaves the GeometryData in an
127 : invalid state.
128 : */
129 : OOINLINE void DestroyGeometryData(GeometryData *data);
130 :
131 : /*
132 : AddTriangle(data, tri)
133 :
134 : Add a triangle to a GeometryData. Will either succeed or abort.
135 : AddTriangle() is designed so that its fast case will be inlined (at least,
136 : if assertions are disabled as in Deployment builds) and its slow case will
137 : not.
138 :
139 :
140 : AddTriangle_slow(data, tri)
141 :
142 : Slow path for AddTriangle(), used when more space is needed. Should not
143 : be called directly. Invariant: may only be called when count == capacity.
144 : */
145 : OOINLINE void AddTriangle(GeometryData *data, Triangle tri);
146 : static NO_INLINE_FUNC void AddTriangle_slow(GeometryData *data, Triangle tri);
147 :
148 : /*
149 : MaxDimensionFromOrigin(data)
150 :
151 : Calculates the half-width of a bounding cube around data centered at the
152 : origin.
153 : */
154 : static OOScalar MaxDimensionFromOrigin(GeometryData *data);
155 :
156 : /*
157 : BuildSubOctree(data, builder, halfWidth, depth)
158 :
159 : Recursively apply the octree generation algorithm.
160 : data: input geometry data.
161 : builder: OOOctreeBuilder where results are accumulated. Each call will
162 : write one complete subtree, which may be a single leaf node.
163 : halfWidth: the half-width of the bounding cube of data.
164 : depth: recursion limit.
165 : */
166 : void BuildSubOctree(GeometryData *data, OOOctreeBuilder *builder, OOScalar halfWidth, NSUInteger depth);
167 :
168 : /*
169 : SplitGeometry{X|Y|Z}(data, dPlus, dMinus, offset)
170 :
171 : Divide data across its local zero plane perpendicular to the specified axis,
172 : putting triangles with coordinates >= 0 in dPlus and triangles with
173 : coordinates <= 0 in dMinus. Triangles will be split if necessary. Generated
174 : triangles will be offset by the specified amount (half of data's half-width)
175 : so that the split planes of dPlus and dMinus will be in the middle of their
176 : data sets.
177 : */
178 : static void SplitGeometryX(GeometryData *data, GeometryData *dPlus, GeometryData *dMinus, OOScalar x);
179 : static void SplitGeometryY(GeometryData *data, GeometryData *dPlus, GeometryData *dMinus, OOScalar y);
180 : static void SplitGeometryZ(GeometryData *data, GeometryData *dPlus, GeometryData *dMinus, OOScalar z);
181 :
182 :
183 : // MARK: Inline function bodies.
184 :
185 0 : void InitGeometryData(GeometryData *data, uint_fast32_t capacity)
186 : {
187 : NSCParameterAssert(data != NULL);
188 :
189 : data->count = 0;
190 : data->capacity = kOOMeshToOctreeConverterSmallDataCapacity;
191 : data->pendingCapacity = capacity;
192 : data->triangles = data->smallData;
193 : }
194 :
195 :
196 0 : OOINLINE void DestroyGeometryData(GeometryData *data)
197 : {
198 : NSCParameterAssert(data != 0 && data->capacity >= kOOMeshToOctreeConverterSmallDataCapacity);
199 :
200 : #if OO_DEBUG
201 : Triangle * const kScribbleValue = (Triangle *)-1L;
202 : NSCAssert(data->triangles != kScribbleValue, @"Attempt to destroy a GeometryData twice.");
203 : #endif
204 :
205 : if (data->capacity != kOOMeshToOctreeConverterSmallDataCapacity)
206 : {
207 : // If capacity is kOOMeshToOctreeConverterSmallDataCapacity, triangles points to smallData.
208 : free(data->triangles);
209 : }
210 :
211 : #if OO_DEBUG
212 : data->triangles = kScribbleValue;
213 : #endif
214 : }
215 :
216 :
217 0 : OOINLINE void AddTriangle(GeometryData *data, Triangle tri)
218 : {
219 : NSCParameterAssert(data != NULL);
220 :
221 : if (data->count < data->capacity)
222 : {
223 : data->triangles[data->count++] = tri;
224 : }
225 : else
226 : {
227 : AddTriangle_slow(data, tri);
228 : }
229 : }
230 :
231 :
232 : @implementation OOMeshToOctreeConverter
233 :
234 : - (id) initWithCapacity:(NSUInteger)capacity
235 : {
236 : NSParameterAssert(capacity < UINT32_MAX);
237 : if (capacity == 0) capacity = 1; // Happens for models with no faces.
238 :
239 : if ((self = [super init]))
240 : {
241 : InitGeometryData(&_data, (uint_fast32_t)capacity);
242 : }
243 :
244 : return self;
245 : }
246 :
247 :
248 0 : - (void) dealloc
249 : {
250 : DestroyGeometryData(&_data);
251 :
252 : [super dealloc];
253 : }
254 :
255 :
256 : + (instancetype) converterWithCapacity:(NSUInteger)capacity
257 : {
258 : return [[[self alloc] initWithCapacity:capacity] autorelease];
259 : }
260 :
261 :
262 0 : - (NSString *) descriptionComponents
263 : {
264 : return [NSString stringWithFormat:@"%u triangles", _data.count];
265 : }
266 :
267 :
268 : - (void) addTriangle:(Triangle)tri
269 : {
270 : if (!OOTriangleIsDegenerate(tri))
271 : {
272 : AddTriangle(&_data, tri);
273 : }
274 : }
275 :
276 :
277 : - (Octree *) findOctreeToDepth:(NSUInteger)depth
278 : {
279 : OOOctreeBuilder *builder = [[[OOOctreeBuilder alloc] init] autorelease];
280 : OOScalar halfWidth = 0.5f + MaxDimensionFromOrigin(&_data); // pad out from geometry by a half meter
281 :
282 : BuildSubOctree(&_data, builder, halfWidth, depth);
283 :
284 : return [builder buildOctreeWithRadius:halfWidth];
285 : }
286 :
287 : @end
288 :
289 :
290 0 : static OOScalar MaxDimensionFromOrigin(GeometryData *data)
291 : {
292 : NSCParameterAssert(data != NULL);
293 :
294 : OOScalar result = 0.0f;
295 : uint_fast32_t i, j;
296 : for (i = 0; i < data->count; i++) for (j = 0; j < 3; j++)
297 : {
298 : Vector v = data->triangles[i].v[j];
299 :
300 : result = fmax(result, fabs(v.x));
301 : result = fmax(result, fabs(v.y));
302 : result = fmax(result, fabs(v.z));
303 : }
304 : return result;
305 : }
306 :
307 :
308 0 : void BuildSubOctree(GeometryData *data, OOOctreeBuilder *builder, OOScalar halfWidth, NSUInteger depth)
309 : {
310 : NSCParameterAssert(data != NULL);
311 :
312 : OOScalar subHalfWidth = 0.5f * halfWidth;
313 :
314 : if (data->count == 0)
315 : {
316 : // No geometry here.
317 : [builder writeEmpty];
318 : return;
319 : }
320 :
321 : if (halfWidth <= OCTREE_MIN_HALF_WIDTH || depth <= 0)
322 : {
323 : // Maximum resolution reached and not full.
324 : [builder writeSolid];
325 : return;
326 : }
327 :
328 : /*
329 : To avoid reallocations, we want a reasonably pessimistic estimate of
330 : sub-data size.
331 :
332 : This table shows observed performance for several heuristics using
333 : vanilla Oolite r5352 (plus instrumentation). Values aren't precisely
334 : reproducible, but are reasonably stable.
335 :
336 : Heuristic: expression used to initialize subCapacity.
337 :
338 : PER: number of geometries per reallocation; in other words, a realloc
339 : is needed one time per PER geometries.
340 :
341 : MEM: high water mark for total memory consumption (triangles arrays
342 : only) across all live Geometries.
343 :
344 : Heuristic PER MEM
345 : n_triangles 3-4 71856
346 : n_triangles * 2 100 111384
347 : MAX(n_triangles * 2, 16) 300 111384
348 : MAX(n_triangles * 2, 21) 500 148512
349 : n_triangles * 3 500 165744
350 : MAX(n_triangles * 3, 16) 12000 165744
351 : MAX(n_triangles * 3, 21) 20000 165744
352 :
353 : The value 21 was chosen for reasons which, on reflection, were entirely
354 : wrong. Performance profiling shows no discernible difference between
355 : 2,16 and 3,21.
356 :
357 : As of r5374, up to 16 entries are stored on the stack and there is no
358 : benefit to specifying a minimum here any longer.
359 : */
360 : enum
361 : {
362 : kFactor = 2
363 : };
364 : uint_fast32_t subCapacity = data->count * kFactor;
365 :
366 0 : #define DECL_GEOMETRY(NAME, CAP) GeometryData NAME; InitGeometryData(&NAME, CAP);
367 :
368 : DECL_GEOMETRY(g_000, subCapacity);
369 : DECL_GEOMETRY(g_001, subCapacity);
370 : DECL_GEOMETRY(g_010, subCapacity);
371 : DECL_GEOMETRY(g_011, subCapacity);
372 : DECL_GEOMETRY(g_100, subCapacity);
373 : DECL_GEOMETRY(g_101, subCapacity);
374 : DECL_GEOMETRY(g_110, subCapacity);
375 : DECL_GEOMETRY(g_111, subCapacity);
376 :
377 : DECL_GEOMETRY(g_xx1, subCapacity);
378 : DECL_GEOMETRY(g_xx0, subCapacity);
379 :
380 : SplitGeometryZ(data, &g_xx1, &g_xx0, subHalfWidth);
381 : if (g_xx0.count != 0)
382 : {
383 : DECL_GEOMETRY(g_x00, subCapacity);
384 : DECL_GEOMETRY(g_x10, subCapacity);
385 :
386 : SplitGeometryY(&g_xx0, &g_x10, &g_x00, subHalfWidth);
387 : if (g_x00.count != 0)
388 : {
389 : SplitGeometryX(&g_x00, &g_100, &g_000, subHalfWidth);
390 : }
391 : if (g_x10.count != 0)
392 : {
393 : SplitGeometryX(&g_x10, &g_110, &g_010, subHalfWidth);
394 : }
395 : DestroyGeometryData(&g_x00);
396 : DestroyGeometryData(&g_x10);
397 : }
398 : if (g_xx1.count != 0)
399 : {
400 : DECL_GEOMETRY(g_x01, subCapacity);
401 : DECL_GEOMETRY(g_x11, subCapacity);
402 :
403 : SplitGeometryY(&g_xx1, &g_x11, &g_x01, subHalfWidth);
404 : if (g_x01.count != 0)
405 : {
406 : SplitGeometryX(&g_x01, &g_101, &g_001, subHalfWidth);
407 : }
408 : if (g_x11.count != 0)
409 : {
410 : SplitGeometryX(&g_x11, &g_111, &g_011, subHalfWidth);
411 : }
412 : DestroyGeometryData(&g_x01);
413 : DestroyGeometryData(&g_x11);
414 : }
415 : DestroyGeometryData(&g_xx0);
416 : DestroyGeometryData(&g_xx1);
417 :
418 : [builder beginInnerNode];
419 : depth--;
420 : BuildSubOctree(&g_000, builder, subHalfWidth, depth);
421 : BuildSubOctree(&g_001, builder, subHalfWidth, depth);
422 : BuildSubOctree(&g_010, builder, subHalfWidth, depth);
423 : BuildSubOctree(&g_011, builder, subHalfWidth, depth);
424 : BuildSubOctree(&g_100, builder, subHalfWidth, depth);
425 : BuildSubOctree(&g_101, builder, subHalfWidth, depth);
426 : BuildSubOctree(&g_110, builder, subHalfWidth, depth);
427 : BuildSubOctree(&g_111, builder, subHalfWidth, depth);
428 : [builder endInnerNode];
429 :
430 : DestroyGeometryData(&g_000);
431 : DestroyGeometryData(&g_001);
432 : DestroyGeometryData(&g_010);
433 : DestroyGeometryData(&g_011);
434 : DestroyGeometryData(&g_100);
435 : DestroyGeometryData(&g_101);
436 : DestroyGeometryData(&g_110);
437 : DestroyGeometryData(&g_111);
438 : }
439 :
440 :
441 0 : static void TranslateGeometryX(GeometryData *data, OOScalar offset)
442 : {
443 : NSCParameterAssert(data != NULL);
444 :
445 : // Optimization note: offset is never zero, so no early return.
446 :
447 : uint_fast32_t i, count = data->count;
448 : for (i = 0; i < count; i++)
449 : {
450 : data->triangles[i].v[0].x += offset;
451 : data->triangles[i].v[1].x += offset;
452 : data->triangles[i].v[2].x += offset;
453 : }
454 : }
455 :
456 :
457 0 : static void TranslateGeometryY(GeometryData *data, OOScalar offset)
458 : {
459 : NSCParameterAssert(data != NULL);
460 :
461 : // Optimization note: offset is never zero, so no early return.
462 :
463 : uint_fast32_t i, count = data->count;
464 : for (i = 0; i < count; i++)
465 : {
466 : data->triangles[i].v[0].y += offset;
467 : data->triangles[i].v[1].y += offset;
468 : data->triangles[i].v[2].y += offset;
469 : }
470 : }
471 :
472 :
473 0 : static void TranslateGeometryZ(GeometryData *data, OOScalar offset)
474 : {
475 : NSCParameterAssert(data != NULL);
476 :
477 : // Optimization note: offset is never zero, so no early return.
478 :
479 : uint_fast32_t i, count = data->count;
480 : for (i = 0; i < count; i++)
481 : {
482 : data->triangles[i].v[0].z += offset;
483 : data->triangles[i].v[1].z += offset;
484 : data->triangles[i].v[2].z += offset;
485 : }
486 : }
487 :
488 :
489 0 : static void SplitGeometryX(GeometryData *data, GeometryData *dPlus, GeometryData *dMinus, OOScalar x)
490 : {
491 : NSCParameterAssert(data != NULL && dPlus != NULL && dMinus != NULL);
492 :
493 : // test each triangle splitting against x == 0.0
494 : uint_fast32_t i, count = data->count;
495 : for (i = 0; i < count; i++)
496 : {
497 : bool done_tri = false;
498 : Vector v0 = data->triangles[i].v[0];
499 : Vector v1 = data->triangles[i].v[1];
500 : Vector v2 = data->triangles[i].v[2];
501 :
502 : if (v0.x >= 0.0f && v1.x >= 0.0f && v2.x >= 0.0f)
503 : {
504 : AddTriangle(dPlus, data->triangles[i]);
505 : done_tri = true;
506 : }
507 : else if (v0.x <= 0.0f && v1.x <= 0.0f && v2.x <= 0.0f)
508 : {
509 : AddTriangle(dMinus, data->triangles[i]);
510 : done_tri = true;
511 : }
512 : if (!done_tri) // triangle must cross x == 0.0
513 : {
514 : OOScalar i01, i12, i20;
515 : if (v0.x == v1.x)
516 : i01 = -1.0f;
517 : else
518 : i01 = v0.x / (v0.x - v1.x);
519 : if (v1.x == v2.x)
520 : i12 = -1.0f;
521 : else
522 : i12 = v1.x / (v1.x - v2.x);
523 : if (v2.x == v0.x)
524 : i20 = -1.0f;
525 : else
526 : i20 = v2.x / (v2.x - v0.x);
527 :
528 : Vector v01 = make_vector(0.0f, i01 * (v1.y - v0.y) + v0.y, i01 * (v1.z - v0.z) + v0.z);
529 : Vector v12 = make_vector(0.0f, i12 * (v2.y - v1.y) + v1.y, i12 * (v2.z - v1.z) + v1.z);
530 : Vector v20 = make_vector(0.0f, i20 * (v0.y - v2.y) + v2.y, i20 * (v0.z - v2.z) + v2.z);
531 :
532 : // cases where a vertex is on the split.
533 : if (v0.x == 0.0f)
534 : {
535 : if (v1.x > 0)
536 : {
537 : AddTriangle(dPlus, make_triangle(v0, v1, v12));
538 : AddTriangle(dMinus, make_triangle(v0, v12, v2));
539 : }
540 : else
541 : {
542 : AddTriangle(dMinus, make_triangle(v0, v1, v12));
543 : AddTriangle(dPlus, make_triangle(v0, v12, v2));
544 : }
545 : }
546 : if (v1.x == 0.0f)
547 : {
548 : if (v2.x > 0)
549 : {
550 : AddTriangle(dPlus, make_triangle(v1, v2, v20));
551 : AddTriangle(dMinus, make_triangle(v1, v20, v0));
552 : }
553 : else
554 : {
555 : AddTriangle(dMinus, make_triangle(v1, v2, v20));
556 : AddTriangle(dPlus, make_triangle(v1, v20, v0));
557 : }
558 : }
559 : if (v2.x == 0.0f)
560 : {
561 : if (v0.x > 0)
562 : {
563 : AddTriangle(dPlus, make_triangle(v2, v0, v01));
564 : AddTriangle(dMinus, make_triangle(v2, v01, v1));
565 : }
566 : else
567 : {
568 : AddTriangle(dMinus, make_triangle(v2, v0, v01));
569 : AddTriangle(dPlus, make_triangle(v2, v01, v1));
570 : }
571 : }
572 :
573 : if (v0.x > 0.0f && v1.x > 0.0f && v2.x < 0.0f)
574 : {
575 : AddTriangle(dPlus, make_triangle(v0, v12, v20));
576 : AddTriangle(dPlus, make_triangle(v0, v1, v12));
577 : AddTriangle(dMinus, make_triangle(v20, v12, v2));
578 : }
579 :
580 : if (v0.x > 0.0f && v1.x < 0.0f && v2.x > 0.0f)
581 : {
582 : AddTriangle(dPlus, make_triangle(v2, v01, v12));
583 : AddTriangle(dPlus, make_triangle(v2, v0, v01));
584 : AddTriangle(dMinus, make_triangle(v12, v01, v1));
585 : }
586 :
587 : if (v0.x > 0.0f && v1.x < 0.0f && v2.x < 0.0f)
588 : {
589 : AddTriangle(dPlus, make_triangle(v20, v0, v01));
590 : AddTriangle(dMinus, make_triangle(v2, v20, v1));
591 : AddTriangle(dMinus, make_triangle(v20, v01, v1));
592 : }
593 :
594 : if (v0.x < 0.0f && v1.x > 0.0f && v2.x > 0.0f)
595 : {
596 : AddTriangle(dMinus, make_triangle(v01, v20, v0));
597 : AddTriangle(dPlus, make_triangle(v1, v20, v01));
598 : AddTriangle(dPlus, make_triangle(v1, v2, v20));
599 : }
600 :
601 : if (v0.x < 0.0f && v1.x > 0.0f && v2.x < 0.0f)
602 : {
603 : AddTriangle(dPlus, make_triangle(v01, v1, v12));
604 : AddTriangle(dMinus, make_triangle(v0, v01, v2));
605 : AddTriangle(dMinus, make_triangle(v01, v12, v2));
606 : }
607 :
608 : if (v0.x < 0.0f && v1.x < 0.0f && v2.x > 0.0f)
609 : {
610 : AddTriangle(dPlus, make_triangle(v12, v2, v20));
611 : AddTriangle(dMinus, make_triangle(v1, v12, v0));
612 : AddTriangle(dMinus, make_triangle(v12, v20, v0));
613 : }
614 : }
615 : }
616 : TranslateGeometryX(dPlus, -x);
617 : TranslateGeometryX(dMinus, x);
618 : }
619 :
620 :
621 0 : static void SplitGeometryY(GeometryData *data, GeometryData *dPlus, GeometryData *dMinus, OOScalar y)
622 : {
623 : NSCParameterAssert(data != NULL && dPlus != NULL && dMinus != NULL);
624 :
625 : // test each triangle splitting against y == 0.0
626 : uint_fast32_t i, count = data->count;
627 : for (i = 0; i < count; i++)
628 : {
629 : bool done_tri = false;
630 : Vector v0 = data->triangles[i].v[0];
631 : Vector v1 = data->triangles[i].v[1];
632 : Vector v2 = data->triangles[i].v[2];
633 :
634 : if (v0.y >= 0.0f && v1.y >= 0.0f && v2.y >= 0.0f)
635 : {
636 : AddTriangle(dPlus, data->triangles[i]);
637 : done_tri = true;
638 : }
639 : if (v0.y <= 0.0f && v1.y <= 0.0f && v2.y <= 0.0f)
640 : {
641 : AddTriangle(dMinus, data->triangles[i]);
642 : done_tri = true;
643 : }
644 : if (!done_tri) // triangle must cross y == 0.0
645 : {
646 : OOScalar i01, i12, i20;
647 :
648 : if (v0.y == v1.y)
649 : i01 = -1.0f;
650 : else
651 : i01 = v0.y / (v0.y - v1.y);
652 : if (v1.y == v2.y)
653 : i12 = -1.0f;
654 : else
655 : i12 = v1.y / (v1.y - v2.y);
656 : if (v2.y == v0.y)
657 : i20 = -1.0f;
658 : else
659 : i20 = v2.y / (v2.y - v0.y);
660 :
661 : Vector v01 = make_vector(i01 * (v1.x - v0.x) + v0.x, 0.0f, i01 * (v1.z - v0.z) + v0.z);
662 : Vector v12 = make_vector(i12 * (v2.x - v1.x) + v1.x, 0.0f, i12 * (v2.z - v1.z) + v1.z);
663 : Vector v20 = make_vector(i20 * (v0.x - v2.x) + v2.x, 0.0f, i20 * (v0.z - v2.z) + v2.z);
664 :
665 : // cases where a vertex is on the split.
666 : if (v0.y == 0.0f)
667 : {
668 : if (v1.y > 0)
669 : {
670 : AddTriangle(dPlus, make_triangle(v0, v1, v12));
671 : AddTriangle(dMinus, make_triangle(v0, v12, v2));
672 : }
673 : else
674 : {
675 : AddTriangle(dMinus, make_triangle(v0, v1, v12));
676 : AddTriangle(dPlus, make_triangle(v0, v12, v2));
677 : }
678 : }
679 : if (v1.y == 0.0f)
680 : {
681 : if (v2.y > 0)
682 : {
683 : AddTriangle(dPlus, make_triangle(v1, v2, v20));
684 : AddTriangle(dMinus, make_triangle(v1, v20, v0));
685 : }
686 : else
687 : {
688 : AddTriangle(dMinus, make_triangle(v1, v2, v20));
689 : AddTriangle(dPlus, make_triangle(v1, v20, v0));
690 : }
691 : }
692 : if (v2.y == 0.0f)
693 : {
694 : if (v0.y > 0)
695 : {
696 : AddTriangle(dPlus, make_triangle(v2, v0, v01));
697 : AddTriangle(dMinus, make_triangle(v2, v01, v1));
698 : }
699 : else
700 : {
701 : AddTriangle(dMinus, make_triangle(v2, v0, v01));
702 : AddTriangle(dPlus, make_triangle(v2, v01, v1));
703 : }
704 : }
705 :
706 : if (v0.y > 0.0f && v1.y > 0.0f && v2.y < 0.0f)
707 : {
708 : AddTriangle(dPlus, make_triangle(v0, v12, v20));
709 : AddTriangle(dPlus, make_triangle(v0, v1, v12));
710 : AddTriangle(dMinus, make_triangle(v20, v12, v2));
711 : }
712 :
713 : if (v0.y > 0.0f && v1.y < 0.0f && v2.y > 0.0f)
714 : {
715 : AddTriangle(dPlus, make_triangle(v2, v01, v12));
716 : AddTriangle(dPlus, make_triangle(v2, v0, v01));
717 : AddTriangle(dMinus, make_triangle(v12, v01, v1));
718 : }
719 :
720 : if (v0.y > 0.0f && v1.y < 0.0f && v2.y < 0.0f)
721 : {
722 : AddTriangle(dPlus, make_triangle(v20, v0, v01));
723 : AddTriangle(dMinus, make_triangle(v2, v20, v1));
724 : AddTriangle(dMinus, make_triangle(v20, v01, v1));
725 : }
726 :
727 : if (v0.y < 0.0f && v1.y > 0.0f && v2.y > 0.0f)
728 : {
729 : AddTriangle(dMinus, make_triangle(v01, v20, v0));
730 : AddTriangle(dPlus, make_triangle(v1, v20, v01));
731 : AddTriangle(dPlus, make_triangle(v1, v2, v20));
732 : }
733 :
734 : if (v0.y < 0.0f && v1.y > 0.0f && v2.y < 0.0f)
735 : {
736 : AddTriangle(dPlus, make_triangle(v01, v1, v12));
737 : AddTriangle(dMinus, make_triangle(v0, v01, v2));
738 : AddTriangle(dMinus, make_triangle(v01, v12, v2));
739 : }
740 :
741 : if (v0.y < 0.0f && v1.y < 0.0f && v2.y > 0.0f)
742 : {
743 : AddTriangle(dPlus, make_triangle(v12, v2, v20));
744 : AddTriangle(dMinus, make_triangle(v1, v12, v0));
745 : AddTriangle(dMinus, make_triangle(v12, v20, v0));
746 : }
747 : }
748 : }
749 : TranslateGeometryY(dPlus, -y);
750 : TranslateGeometryY(dMinus, y);
751 : }
752 :
753 :
754 0 : static void SplitGeometryZ(GeometryData *data, GeometryData *dPlus, GeometryData *dMinus, OOScalar z)
755 : {
756 : NSCParameterAssert(data != NULL && dPlus != NULL && dMinus != NULL);
757 :
758 : // test each triangle splitting against z == 0.0
759 : uint_fast32_t i, count = data->count;
760 : for (i = 0; i < count; i++)
761 : {
762 : bool done_tri = false;
763 : Vector v0 = data->triangles[i].v[0];
764 : Vector v1 = data->triangles[i].v[1];
765 : Vector v2 = data->triangles[i].v[2];
766 :
767 : if (v0.z >= 0.0f && v1.z >= 0.0f && v2.z >= 0.0f)
768 : {
769 : AddTriangle(dPlus, data->triangles[i]);
770 : done_tri = true;
771 : }
772 : else if (v0.z <= 0.0f && v1.z <= 0.0f && v2.z <= 0.0f)
773 : {
774 : AddTriangle(dMinus, data->triangles[i]);
775 : done_tri = true;
776 : }
777 : if (!done_tri) // triangle must cross z == 0.0
778 : {
779 : OOScalar i01, i12, i20;
780 :
781 : if (v0.z == v1.z)
782 : i01 = -1.0f;
783 : else
784 : i01 = v0.z / (v0.z - v1.z);
785 : if (v1.z == v2.z)
786 : i12 = -1.0f;
787 : else
788 : i12 = v1.z / (v1.z - v2.z);
789 : if (v2.z == v0.z)
790 : i20 = -1.0f;
791 : else
792 : i20 = v2.z / (v2.z - v0.z);
793 :
794 : Vector v01 = make_vector(i01 * (v1.x - v0.x) + v0.x, i01 * (v1.y - v0.y) + v0.y, 0.0f);
795 : Vector v12 = make_vector(i12 * (v2.x - v1.x) + v1.x, i12 * (v2.y - v1.y) + v1.y, 0.0f);
796 : Vector v20 = make_vector(i20 * (v0.x - v2.x) + v2.x, i20 * (v0.y - v2.y) + v2.y, 0.0f);
797 :
798 : // cases where a vertex is on the split.
799 : if (v0.z == 0.0f)
800 : {
801 : if (v1.z > 0)
802 : {
803 : AddTriangle(dPlus, make_triangle(v0, v1, v12));
804 : AddTriangle(dMinus, make_triangle(v0, v12, v2));
805 : }
806 : else
807 : {
808 : AddTriangle(dMinus, make_triangle(v0, v1, v12));
809 : AddTriangle(dPlus, make_triangle(v0, v12, v2));
810 : }
811 : }
812 : if (v1.z == 0.0f)
813 : {
814 : if (v2.z > 0)
815 : {
816 : AddTriangle(dPlus, make_triangle(v1, v2, v20));
817 : AddTriangle(dMinus, make_triangle(v1, v20, v0));
818 : }
819 : else
820 : {
821 : AddTriangle(dMinus, make_triangle(v1, v2, v20));
822 : AddTriangle(dPlus, make_triangle(v1, v20, v0));
823 : }
824 : }
825 : if (v2.z == 0.0f)
826 : {
827 : if (v0.z > 0)
828 : {
829 : AddTriangle(dPlus, make_triangle(v2, v0, v01));
830 : AddTriangle(dMinus, make_triangle(v2, v01, v1));
831 : }
832 : else
833 : {
834 : AddTriangle(dMinus, make_triangle(v2, v0, v01));
835 : AddTriangle(dPlus, make_triangle(v2, v01, v1));
836 : }
837 : }
838 :
839 : if (v0.z > 0.0f && v1.z > 0.0f && v2.z < 0.0f)
840 : {
841 : AddTriangle(dPlus, make_triangle(v0, v12, v20));
842 : AddTriangle(dPlus, make_triangle(v0, v1, v12));
843 : AddTriangle(dMinus, make_triangle(v20, v12, v2));
844 : }
845 :
846 : if (v0.z > 0.0f && v1.z < 0.0f && v2.z > 0.0f)
847 : {
848 : AddTriangle(dPlus, make_triangle(v2, v01, v12));
849 : AddTriangle(dPlus, make_triangle(v2, v0, v01));
850 : AddTriangle(dMinus, make_triangle(v12, v01, v1));
851 : }
852 :
853 : if (v0.z > 0.0f && v1.z < 0.0f && v2.z < 0.0f)
854 : {
855 : AddTriangle(dPlus, make_triangle(v20, v0, v01));
856 : AddTriangle(dMinus, make_triangle(v2, v20, v1));
857 : AddTriangle(dMinus, make_triangle(v20, v01, v1));
858 : }
859 :
860 : if (v0.z < 0.0f && v1.z > 0.0f && v2.z > 0.0f)
861 : {
862 : AddTriangle(dMinus, make_triangle(v01, v20, v0));
863 : AddTriangle(dPlus, make_triangle(v1, v20, v01));
864 : AddTriangle(dPlus, make_triangle(v1, v2, v20));
865 : }
866 :
867 : if (v0.z < 0.0f && v1.z > 0.0f && v2.z < 0.0f)
868 : {
869 : AddTriangle(dPlus, make_triangle(v01, v1, v12));
870 : AddTriangle(dMinus, make_triangle(v0, v01, v2));
871 : AddTriangle(dMinus, make_triangle(v01, v12, v2));
872 : }
873 :
874 : if (v0.z < 0.0f && v1.z < 0.0f && v2.z > 0.0f)
875 : {
876 : AddTriangle(dPlus, make_triangle(v12, v2, v20));
877 : AddTriangle(dMinus, make_triangle(v1, v12, v0));
878 : AddTriangle(dMinus, make_triangle(v12, v20, v0));
879 : }
880 : }
881 : }
882 : TranslateGeometryZ(dPlus, -z);
883 : TranslateGeometryZ(dMinus, z);
884 : }
885 :
886 :
887 : /*
888 : void AddTriangle_slow(GeometryData *data, Triangle tri)
889 :
890 : Slow path for AddTriangle(). Ensure that there is enough space to add a
891 : triangle, then actually add it.
892 :
893 : If no memory has been allocated yet, capacity is
894 : kOOMeshToOctreeConverterSmallDataCapacity, triangles points at smallData
895 : and pendingCapacity is the capacity passed to InitGeometryData(). Otherwise,
896 : triangles is a malloced pointer.
897 :
898 : This is marked noinline so that the fast path in AddTriangle() can be
899 : inlined. Without the attribute, clang (and probably gcc too) will inline
900 : AddTriangles_slow() into AddTriangle() (because it only has one call site),
901 : making AddTriangle() too heavy to inline.
902 : */
903 0 : static NO_INLINE_FUNC void AddTriangle_slow(GeometryData *data, Triangle tri)
904 : {
905 : NSCParameterAssert(data != NULL);
906 : NSCParameterAssert(data->count == data->capacity);
907 :
908 : if (data->capacity == kOOMeshToOctreeConverterSmallDataCapacity)
909 : {
910 : data->capacity = MAX(data->pendingCapacity, (uint_fast32_t)kOOMeshToOctreeConverterSmallDataCapacity * 2);
911 : data->triangles = malloc(data->capacity * sizeof(Triangle));
912 : memcpy(data->triangles, data->smallData, sizeof data->smallData);
913 : }
914 : else
915 : {
916 : // create more space by doubling the capacity of this geometry.
917 : data->capacity = 1 + data->capacity * 2;
918 : data->triangles = realloc(data->triangles, data->capacity * sizeof(Triangle));
919 :
920 : // N.b.: we leak here if realloc() failed, but we're about to abort anyway.
921 : }
922 :
923 : if (EXPECT_NOT(data->triangles == NULL))
924 : {
925 : OOLog(kOOLogAllocationFailure, @"%@", @"!!!!! Ran out of memory to allocate more geometry!");
926 : exit(EXIT_FAILURE);
927 : }
928 :
929 : data->triangles[data->count++] = tri;
930 : }
|
