1 //********************************************************************************************
2 //*
3 //* This file is part of Egoboo.
4 //*
5 //* Egoboo is free software: you can redistribute it and/or modify it
6 //* under the terms of the GNU General Public License as published by
7 //* the Free Software Foundation, either version 3 of the License, or
8 //* (at your option) any later version.
9 //*
10 //* Egoboo is distributed in the hope that it will be useful, but
11 //* WITHOUT ANY WARRANTY; without even the implied warranty of
12 //* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 //* General Public License for more details.
14 //*
15 //* You should have received a copy of the GNU General Public License
16 //* along with Egoboo. If not, see <http://www.gnu.org/licenses/>.
17 //*
18 //********************************************************************************************
19
20 /// @file bsp.c
21 /// @brief
22 /// @details
23
24 #include "bsp.inl"
25 #include "log.h"
26
27 #include "egoboo.h"
28 #include "egoboo_mem.h"
29
30 //--------------------------------------------------------------------------------------------
31 //--------------------------------------------------------------------------------------------
32 IMPLEMENT_DYNAMIC_ARY( BSP_leaf_ary, BSP_leaf_t );
33 IMPLEMENT_DYNAMIC_ARY( BSP_leaf_pary, BSP_leaf_t * );
34
35 IMPLEMENT_DYNAMIC_ARY( BSP_branch_ary, BSP_branch_t );
36 IMPLEMENT_DYNAMIC_ARY( BSP_branch_pary, BSP_branch_t * );
37
38 //--------------------------------------------------------------------------------------------
39 // private functions
40
41 static BSP_branch_t * BSP_tree_alloc_branch( BSP_tree_t * t );
42 static bool_t BSP_tree_free_branch( BSP_tree_t * t, BSP_branch_t * B );
43 static bool_t BSP_tree_remove_used( BSP_tree_t * t, BSP_branch_t * B );
44
45 static bool_t BSP_tree_insert_leaf_rec( BSP_tree_t * ptree, BSP_branch_t * pbranch, BSP_leaf_t * pleaf, int depth );
46 static bool_t BSP_tree_free_branches( BSP_tree_t * t );
47
48 //--------------------------------------------------------------------------------------------
49 //--------------------------------------------------------------------------------------------
BSP_aabb_ctor(BSP_aabb_t * pbb,size_t dim)50 BSP_aabb_t * BSP_aabb_ctor( BSP_aabb_t * pbb, size_t dim )
51 {
52 if ( NULL == pbb ) return NULL;
53
54 // initialize the memory
55 memset( pbb, 0, sizeof( *pbb ) );
56
57 // allocate memory and clear it
58 BSP_aabb_alloc( pbb, dim );
59
60 return pbb;
61 }
62
63 //--------------------------------------------------------------------------------------------
BSP_aabb_dtor(BSP_aabb_t * pbb)64 BSP_aabb_t * BSP_aabb_dtor( BSP_aabb_t * pbb )
65 {
66 if ( NULL == pbb ) return NULL;
67
68 // deallocate everything
69 pbb = BSP_aabb_dealloc( pbb );
70
71 // wipe it
72 memset( pbb, 0, sizeof( *pbb ) );
73
74 return pbb;
75 }
76
77 //--------------------------------------------------------------------------------------------
BSP_aabb_alloc(BSP_aabb_t * pbb,size_t dim)78 BSP_aabb_t * BSP_aabb_alloc( BSP_aabb_t * pbb, size_t dim )
79 {
80 if ( NULL == pbb ) return pbb;
81
82 pbb->dim = 0;
83
84 float_ary_ctor( &( pbb->mins ), dim );
85 float_ary_ctor( &( pbb->mids ), dim );
86 float_ary_ctor( &( pbb->maxs ), dim );
87
88 if ( dim != pbb->mins.alloc || dim != pbb->mids.alloc || dim != pbb->maxs.alloc )
89 {
90 BSP_aabb_dealloc( pbb );
91 }
92 else
93 {
94 pbb->dim = dim;
95 BSP_aabb_clear( pbb );
96 }
97
98 BSP_aabb_validate( pbb );
99
100 return pbb;
101 }
102
103 //--------------------------------------------------------------------------------------------
BSP_aabb_dealloc(BSP_aabb_t * pbb)104 BSP_aabb_t * BSP_aabb_dealloc( BSP_aabb_t * pbb )
105 {
106 if ( NULL == pbb ) return pbb;
107
108 // deallocate everything
109 float_ary_dtor( &( pbb->mins ) );
110 float_ary_dtor( &( pbb->mids ) );
111 float_ary_dtor( &( pbb->maxs ) );
112
113 pbb->dim = 0;
114 pbb->valid = bfalse;
115
116 return pbb;
117 }
118
119 //--------------------------------------------------------------------------------------------
BSP_aabb_empty(const BSP_aabb_t * psrc)120 bool_t BSP_aabb_empty( const BSP_aabb_t * psrc )
121 {
122 Uint32 cnt;
123
124 if ( NULL == psrc || 0 == psrc->dim || !psrc->valid ) return btrue;
125
126 for ( cnt = 0; cnt < psrc->dim; cnt++ )
127 {
128 if ( psrc->maxs.ary[cnt] <= psrc->mins.ary[cnt] )
129 return btrue;
130 }
131
132 return bfalse;
133 }
134
135 //--------------------------------------------------------------------------------------------
BSP_aabb_clear(BSP_aabb_t * psrc)136 bool_t BSP_aabb_clear( BSP_aabb_t * psrc )
137 {
138 /// @details BB@> Return this bounding box to an empty state.
139
140 Uint32 cnt;
141
142 if ( NULL == psrc ) return bfalse;
143
144 if ( psrc->dim <= 0 || NULL == psrc->mins.ary || NULL == psrc->mids.ary || NULL == psrc->maxs.ary )
145 {
146 BSP_aabb_invalidate( psrc );
147 return bfalse;
148 }
149
150 for ( cnt = 0; cnt < psrc->dim; cnt++ )
151 {
152 psrc->mins.ary[cnt] = psrc->mids.ary[cnt] = psrc->maxs.ary[cnt] = 0.0f;
153 }
154
155 return btrue;
156 }
157
158 //--------------------------------------------------------------------------------------------
BSP_aabb_from_oct_bb(BSP_aabb_t * pdst,const oct_bb_t * psrc)159 bool_t BSP_aabb_from_oct_bb( BSP_aabb_t * pdst, const oct_bb_t * psrc )
160 {
161 /// @details BB@> do an automatic conversion from an oct_bb_t to a BSP_aabb_t
162
163 Uint32 cnt;
164
165 if ( NULL == pdst || NULL == psrc ) return bfalse;
166
167 BSP_aabb_invalidate( pdst );
168
169 if ( pdst->dim <= 0 ) return bfalse;
170
171 // this process is a little bit complicated because the
172 // order to the OCT_* indices is optimized for a different test.
173 if ( 1 == pdst->dim )
174 {
175 pdst->mins.ary[kX] = psrc->mins[OCT_X];
176
177 pdst->maxs.ary[kX] = psrc->maxs[OCT_X];
178 }
179 else if ( 2 == pdst->dim )
180 {
181 pdst->mins.ary[kX] = psrc->mins[OCT_X];
182 pdst->mins.ary[kY] = psrc->mins[OCT_Y];
183
184 pdst->maxs.ary[kX] = psrc->maxs[OCT_X];
185 pdst->maxs.ary[kY] = psrc->maxs[OCT_Y];
186 }
187 else if ( pdst->dim >= 3 )
188 {
189 pdst->mins.ary[kX] = psrc->mins[OCT_X];
190 pdst->mins.ary[kY] = psrc->mins[OCT_Y];
191 pdst->mins.ary[kZ] = psrc->mins[OCT_Z];
192
193 pdst->maxs.ary[kX] = psrc->maxs[OCT_X];
194 pdst->maxs.ary[kY] = psrc->maxs[OCT_Y];
195 pdst->maxs.ary[kZ] = psrc->maxs[OCT_Z];
196
197 // blank any extended dimensions
198 for ( cnt = 3; cnt < pdst->dim; cnt++ )
199 {
200 pdst->mins.ary[cnt] = pdst->maxs.ary[cnt] = 0.0f;
201 }
202 }
203
204 // find the mid values
205 for ( cnt = 0; cnt < pdst->dim; cnt++ )
206 {
207 pdst->mids.ary[cnt] = 0.5f * ( pdst->mins.ary[cnt] + pdst->maxs.ary[cnt] );
208 }
209
210 BSP_aabb_validate( pdst );
211
212 return btrue;
213 }
214
215 //--------------------------------------------------------------------------------------------
BSP_aabb_validate(BSP_aabb_t * psrc)216 bool_t BSP_aabb_validate( BSP_aabb_t * psrc )
217 {
218 size_t cnt;
219
220 if ( NULL == psrc ) return bfalse;
221
222 // set it to valid
223 psrc->valid = btrue;
224
225 // check to see if any dimension is inverted
226 for ( cnt = 0; cnt < psrc->dim; cnt++ )
227 {
228 if ( psrc->maxs.ary[cnt] < psrc->mids.ary[cnt] )
229 {
230 psrc->valid = bfalse;
231 break;
232 }
233 if ( psrc->maxs.ary[cnt] < psrc->mins.ary[cnt] )
234 {
235 psrc->valid = bfalse;
236 break;
237 }
238 if ( psrc->mids.ary[cnt] < psrc->mins.ary[cnt] )
239 {
240 psrc->valid = bfalse;
241 break;
242 }
243 }
244
245 return psrc->valid;
246 }
247
248 //--------------------------------------------------------------------------------------------
BSP_aabb_invalidate(BSP_aabb_t * psrc)249 bool_t BSP_aabb_invalidate( BSP_aabb_t * psrc )
250 {
251 if ( NULL == psrc ) return bfalse;
252
253 // set it to valid
254 psrc->valid = bfalse;
255
256 return btrue;
257 }
258
259 //--------------------------------------------------------------------------------------------
BSP_aabb_copy(BSP_aabb_t * pdst,const BSP_aabb_t * psrc)260 bool_t BSP_aabb_copy( BSP_aabb_t * pdst, const BSP_aabb_t * psrc )
261 {
262 size_t cnt;
263
264 if ( NULL == pdst ) return bfalse;
265
266 if ( NULL == psrc )
267 {
268 BSP_aabb_dtor( pdst );
269 return bfalse;
270 }
271
272 // ensure that they have the same dimensions
273 if ( pdst->dim != psrc->dim )
274 {
275 BSP_aabb_dealloc( pdst );
276 BSP_aabb_alloc( pdst, psrc->dim );
277 }
278
279 for ( cnt = 0; cnt < psrc->dim; cnt++ )
280 {
281 pdst->mins.ary[cnt] = psrc->mins.ary[cnt];
282 pdst->mids.ary[cnt] = psrc->mids.ary[cnt];
283 pdst->maxs.ary[cnt] = psrc->maxs.ary[cnt];
284 }
285
286 BSP_aabb_validate( pdst );
287
288 return btrue;
289 }
290
291 //--------------------------------------------------------------------------------------------
BSP_aabb_self_union(BSP_aabb_t * pdst,BSP_aabb_t * psrc)292 bool_t BSP_aabb_self_union( BSP_aabb_t * pdst, BSP_aabb_t * psrc )
293 {
294 size_t min_dim, cnt;
295
296 if ( NULL == pdst ) return bfalse;
297
298 if ( NULL == psrc )
299 {
300 return BSP_aabb_validate( pdst );
301 }
302
303 min_dim = MIN( psrc->dim, pdst->dim );
304
305 for ( cnt = 0; cnt < min_dim; cnt++ )
306 {
307 pdst->mins.ary[cnt] = MIN( pdst->mins.ary[cnt], psrc->mins.ary[cnt] );
308 pdst->maxs.ary[cnt] = MAX( pdst->maxs.ary[cnt], psrc->maxs.ary[cnt] );
309
310 pdst->mids.ary[cnt] = 0.5f * ( pdst->mins.ary[cnt] + pdst->maxs.ary[cnt] );
311 }
312
313 return BSP_aabb_validate( pdst );
314 }
315
316 //--------------------------------------------------------------------------------------------
317 //--------------------------------------------------------------------------------------------
BSP_leaf_create(int dim,void * data,int type)318 BSP_leaf_t * BSP_leaf_create( int dim, void * data, int type )
319 {
320 BSP_leaf_t * rv;
321
322 rv = EGOBOO_NEW( BSP_leaf_t );
323 if ( NULL == rv ) return rv;
324
325 return BSP_leaf_ctor( rv, dim, data, type );
326 }
327
328 //--------------------------------------------------------------------------------------------
BSP_leaf_destroy(BSP_leaf_t ** ppleaf)329 bool_t BSP_leaf_destroy( BSP_leaf_t ** ppleaf )
330 {
331 if ( NULL == ppleaf || NULL == *ppleaf ) return bfalse;
332
333 BSP_leaf_dtor( *ppleaf );
334
335 EGOBOO_DELETE( *ppleaf );
336
337 return btrue;
338 }
339
340 //--------------------------------------------------------------------------------------------
BSP_leaf_ctor(BSP_leaf_t * L,int dim,void * data,int type)341 BSP_leaf_t * BSP_leaf_ctor( BSP_leaf_t * L, int dim, void * data, int type )
342 {
343 if ( NULL == L ) return L;
344
345 memset( L, 0, sizeof( *L ) );
346
347 BSP_aabb_ctor( &( L->bbox ), dim );
348
349 if ( NULL == data ) return L;
350
351 L->data_type = type;
352 L->data = data;
353
354 return L;
355 }
356
357 //--------------------------------------------------------------------------------------------
BSP_leaf_dtor(BSP_leaf_t * L)358 bool_t BSP_leaf_dtor( BSP_leaf_t * L )
359 {
360 if ( NULL == L ) return bfalse;
361
362 L->inserted = bfalse;
363 L->data_type = -1;
364 L->data = NULL;
365
366 BSP_aabb_dtor( &( L->bbox ) );
367
368 return btrue;
369 }
370
371 //--------------------------------------------------------------------------------------------
372 //--------------------------------------------------------------------------------------------
373 //BSP_branch_t * BSP_branch_create( size_t dim )
374 //{
375 // BSP_branch_t * rv;
376 //
377 // rv = EGOBOO_NEW( BSP_branch_t );
378 // if ( NULL == rv ) return rv;
379 //
380 // return BSP_branch_ctor( rv, dim );
381 //}
382 //
383 ////--------------------------------------------------------------------------------------------
384 //bool_t BSP_branch_destroy( BSP_branch_t ** ppbranch )
385 //{
386 // if ( NULL == ppbranch || NULL == *ppbranch ) return bfalse;
387 //
388 // BSP_branch_dtor( *ppbranch );
389 //
390 // EGOBOO_DELETE( *ppbranch );
391 //
392 // return btrue;
393 //}
394 //
395 ////--------------------------------------------------------------------------------------------
396 //BSP_branch_t * BSP_branch_create_ary( size_t ary_size, size_t dim )
397 //{
398 // size_t cnt;
399 // BSP_branch_t * lst;
400 //
401 // lst = EGOBOO_NEW_ARY( BSP_branch_t, ary_size );
402 // if ( NULL == lst ) return lst;
403 //
404 // for ( cnt = 0; cnt < ary_size; cnt++ )
405 // {
406 // BSP_branch_ctor( lst + cnt, dim );
407 // }
408 //
409 // return lst;
410 //}
411 //
412 ////--------------------------------------------------------------------------------------------
413 //bool_t BSP_branch_destroy_ary( size_t ary_size, BSP_branch_t ** lst )
414 //{
415 // size_t cnt;
416 //
417 // if ( NULL == lst || NULL == *lst || 0 == ary_size ) return bfalse;
418 //
419 // for ( cnt = 0; cnt < ary_size; cnt++ )
420 // {
421 // BSP_branch_dtor(( *lst ) + cnt );
422 // }
423 //
424 // EGOBOO_DELETE_ARY( *lst );
425 //
426 // return btrue;
427 //}
428
429 //--------------------------------------------------------------------------------------------
BSP_branch_ctor(BSP_branch_t * B,size_t dim)430 BSP_branch_t * BSP_branch_ctor( BSP_branch_t * B, size_t dim )
431 {
432 if ( NULL == B ) return B;
433
434 memset( B, 0, sizeof( *B ) );
435
436 BSP_branch_alloc( B, dim );
437
438 return B;
439 }
440
441 //--------------------------------------------------------------------------------------------
BSP_branch_dtor(BSP_branch_t * B)442 BSP_branch_t * BSP_branch_dtor( BSP_branch_t * B )
443 {
444 if ( NULL == B ) return B;
445
446 BSP_branch_dealloc( B );
447
448 memset( B, 0, sizeof( *B ) );
449
450 return B;
451 }
452
453 //--------------------------------------------------------------------------------------------
BSP_branch_alloc(BSP_branch_t * B,size_t dim)454 bool_t BSP_branch_alloc( BSP_branch_t * B, size_t dim )
455 {
456 bool_t child_rv, nodes_rv;
457
458 if ( NULL == B ) return bfalse;
459
460 // allocate the branch's children
461 child_rv = BSP_branch_list_alloc( &( B->children ), dim );
462
463 // allocate the branch's nodes
464 nodes_rv = BSP_leaf_list_alloc( &( B->nodes ), dim );
465
466 // allocate the branch's bounding box
467 BSP_aabb_alloc( &( B->bsp_bbox ), dim );
468
469 return child_rv && nodes_rv && ( dim == B->bsp_bbox.dim );
470 }
471
472 //--------------------------------------------------------------------------------------------
BSP_branch_dealloc(BSP_branch_t * B)473 bool_t BSP_branch_dealloc( BSP_branch_t * B )
474 {
475 if ( NULL == B ) return bfalse;
476
477 // deallocate the list of children
478 BSP_branch_list_dtor( &( B->children ) );
479
480 // deallocate the branch's nodes
481 BSP_leaf_list_dealloc( &( B->nodes ) );
482
483 // deallocate the list of nodes
484 BSP_leaf_list_dtor( &( B->nodes ) );
485
486 // deallocate the bounding box
487 BSP_aabb_dtor( &( B->bsp_bbox ) );
488
489 return btrue;
490 }
491
492 //--------------------------------------------------------------------------------------------
BSP_branch_unlink(BSP_branch_t * B)493 bool_t BSP_branch_unlink( BSP_branch_t * B )
494 {
495 bool_t found_self = bfalse;
496 size_t i;
497
498 // remove any links to other leaves
499 // assume the user knows what they are doing
500
501 if ( NULL == B ) return bfalse;
502
503 // unlink this branch from its parent
504 if ( NULL != B->parent )
505 {
506 for ( i = 0; i < B->parent->children.count; i++ )
507 {
508 if ( B == B->parent->children.lst[i] )
509 {
510 B->parent->children.lst[i] = NULL;
511 found_self = btrue;
512 }
513 }
514
515 B->parent = NULL;
516 }
517
518 // unlink the children
519 for ( i = 0; i < B->children.count; i++ )
520 {
521 if ( NULL != B->children.lst[i] )
522 {
523 B->children.lst[i]->parent = NULL;
524 }
525
526 B->children.lst[i] = NULL;
527 }
528
529 // Remove any nodes (from this branch only, NOT recursively).
530 // This resets the B->nodes list.
531 BSP_branch_free_nodes( B, bfalse );
532
533 return found_self;
534 }
535
536 //--------------------------------------------------------------------------------------------
BSP_branch_insert_leaf(BSP_branch_t * B,BSP_leaf_t * n)537 bool_t BSP_branch_insert_leaf( BSP_branch_t * B, BSP_leaf_t * n )
538 {
539 return BSP_leaf_list_insert( &( B->nodes ), n );
540 }
541
542 //--------------------------------------------------------------------------------------------
BSP_branch_insert_branch(BSP_branch_t * B,int index,BSP_branch_t * B2)543 bool_t BSP_branch_insert_branch( BSP_branch_t * B, int index, BSP_branch_t * B2 )
544 {
545 if ( NULL == B || index < 0 || ( size_t )index >= B->children.count ) return bfalse;
546
547 if ( NULL == B2 ) return bfalse;
548
549 if ( NULL != B->children.lst[ index ] )
550 {
551 return bfalse;
552 }
553
554 EGOBOO_ASSERT( B->depth + 1 == B2->depth );
555
556 B->children.lst[ index ] = B2;
557 B2->parent = B;
558
559 return btrue;
560 }
561
562 //--------------------------------------------------------------------------------------------
BSP_branch_clear(BSP_branch_t * B,bool_t recursive)563 bool_t BSP_branch_clear( BSP_branch_t * B, bool_t recursive )
564 {
565 size_t cnt;
566
567 if ( NULL == B ) return bfalse;
568
569 if ( recursive )
570 {
571 // recursively clear out any nodes in the children.lst
572 for ( cnt = 0; cnt < B->children.count; cnt++ )
573 {
574 if ( NULL == B->children.lst[cnt] ) continue;
575
576 BSP_branch_clear( B->children.lst[cnt], btrue );
577 };
578 }
579
580 // clear the node list
581 BSP_leaf_list_reset( &( B->nodes ) );
582
583 // reset the number of inserted children
584 B->children.inserted = 0;
585
586 return btrue;
587 }
588
589 //--------------------------------------------------------------------------------------------
BSP_branch_free_nodes(BSP_branch_t * B,bool_t recursive)590 bool_t BSP_branch_free_nodes( BSP_branch_t * B, bool_t recursive )
591 {
592 size_t cnt;
593
594 if ( NULL == B ) return bfalse;
595
596 if ( recursive )
597 {
598 // recursively clear out any nodes in the children.lst
599 for ( cnt = 0; cnt < B->children.count; cnt++ )
600 {
601 if ( NULL == B->children.lst[cnt] ) continue;
602
603 BSP_branch_free_nodes( B->children.lst[cnt], btrue );
604 };
605 }
606
607 // free all nodes of this branch
608 BSP_leaf_list_reset( &( B->nodes ) );
609
610 return btrue;
611 }
612
613 //--------------------------------------------------------------------------------------------
BSP_branch_prune(BSP_tree_t * t,BSP_branch_t * B,bool_t recursive)614 bool_t BSP_branch_prune( BSP_tree_t * t, BSP_branch_t * B, bool_t recursive )
615 {
616 /// @details BB@> remove all leaves with no children.lst. Do a depth first recursive search for efficiency
617
618 size_t i;
619 bool_t retval;
620
621 if ( NULL == B ) return bfalse;
622
623 // prune all of the children 1st
624 if ( recursive )
625 {
626 // prune all the children
627 for ( i = 0; i < B->children.count; i++ )
628 {
629 BSP_branch_prune( t, B->children.lst[i], btrue );
630 }
631 }
632
633 // do not remove the root node
634 if ( B == t->root ) return btrue;
635
636 retval = btrue;
637 if ( BSP_branch_empty( B ) )
638 {
639 if ( NULL != B->parent )
640 {
641 bool_t found = bfalse;
642
643 // unlink the parent and return the node to the free list
644 for ( i = 0; i < B->parent->children.count; i++ )
645 {
646 if ( B->parent->children.lst[i] == B )
647 {
648 B->parent->children.lst[i] = NULL;
649 found = btrue;
650 break;
651 }
652 }
653 EGOBOO_ASSERT( found );
654 }
655
656 retval = BSP_branch_pary_push_back( &( t->branch_free ), B );
657 }
658
659 return retval;
660 }
661
662 //--------------------------------------------------------------------------------------------
BSP_branch_add_all_nodes(BSP_branch_t * pbranch,BSP_leaf_pary_t * colst)663 bool_t BSP_branch_add_all_nodes( BSP_branch_t * pbranch, BSP_leaf_pary_t * colst )
664 {
665 size_t cnt, colst_size;
666 BSP_leaf_t * ptmp;
667
668 if ( NULL == pbranch || NULL == colst ) return bfalse;
669
670 colst_size = BSP_leaf_pary_get_size( colst );
671 if ( 0 == colst_size || BSP_leaf_pary_get_top( colst ) >= colst_size ) return bfalse;
672
673 // add any nodes in the nodes.lst
674 for ( cnt = 0, ptmp = pbranch->nodes.lst; NULL != ptmp && cnt < pbranch->nodes.count; ptmp = ptmp->next, cnt++ )
675 {
676 if ( !BSP_leaf_pary_push_back( colst, ptmp ) ) break;
677 }
678
679 // if there is no more room. stop
680 if ( BSP_leaf_pary_get_top( colst ) >= colst_size ) return bfalse;
681
682 // add all nodes from all children
683 for ( cnt = 0; cnt < pbranch->children.count; cnt++ )
684 {
685 BSP_branch_t * pchild = pbranch->children.lst[cnt];
686 if ( NULL == pchild ) continue;
687
688 BSP_branch_add_all_nodes( pchild, colst );
689
690 if ( BSP_leaf_pary_get_top( colst ) >= colst_size ) break;
691 }
692
693 return ( BSP_leaf_pary_get_top( colst ) < colst_size );
694 }
695
696 //--------------------------------------------------------------------------------------------
BSP_branch_empty(BSP_branch_t * pbranch)697 bool_t BSP_branch_empty( BSP_branch_t * pbranch )
698 {
699 size_t cnt;
700 bool_t empty;
701
702 if ( NULL == pbranch ) return bfalse;
703
704 // look to see if all children are free
705 empty = btrue;
706 for ( cnt = 0; cnt < pbranch->children.count; cnt++ )
707 {
708 if ( NULL != pbranch->children.lst[cnt] )
709 {
710 empty = bfalse;
711 break;
712 }
713 }
714
715 // check to see if there are any nodes in this branch's nodes.lst
716 if ( NULL != pbranch->nodes.lst )
717 {
718 empty = bfalse;
719 }
720
721 return empty;
722 }
723
724 //--------------------------------------------------------------------------------------------
BSP_branch_collide(BSP_branch_t * pbranch,BSP_aabb_t * paabb,BSP_leaf_pary_t * colst)725 bool_t BSP_branch_collide( BSP_branch_t * pbranch, BSP_aabb_t * paabb, BSP_leaf_pary_t * colst )
726 {
727 /// @details BB@> Recursively search the BSP tree for collisions with the paabb
728 // Return bfalse if we need to break out of the recursive search for any reason.
729
730 size_t cnt;
731
732 // if the collision list doesn't exist, stop
733 if ( NULL == colst || 0 == colst->alloc || colst->top >= colst->alloc ) return bfalse;
734
735 // if the branch doesn't exist, stop
736 if ( NULL == pbranch ) return bfalse;
737
738 // return if the object does not intersect the branch
739 if ( !BSP_aabb_overlap( paabb, &( pbranch->bsp_bbox ) ) )
740 {
741 // the branch and the object do not overlap at all.
742 // do nothing.
743 return bfalse;
744 }
745
746 // is the branch completely contained by the test aabb?
747 if ( BSP_aabb_lhs_contains_rhs( paabb, &( pbranch->nodes.bbox ) ) )
748 {
749 // add every single node under this branch
750 return BSP_branch_add_all_nodes( pbranch, colst );
751 }
752
753 // collide with the individual nodes
754 BSP_leaf_list_collide( &( pbranch->nodes ), paabb, colst );
755
756 // only check the children if there is overlap with the stored
757 // bounding box for the children
758 if ( BSP_aabb_overlap( paabb, &( pbranch->children.bbox ) ) )
759 {
760 // scan the child branches and collide with them recursively
761 for ( cnt = 0; cnt < pbranch->children.count; cnt++ )
762 {
763 BSP_branch_t * pchild = pbranch->children.lst[cnt];
764
765 // scan all the children.lst
766 if ( NULL == pchild ) continue;
767
768 BSP_branch_collide( pchild, paabb, colst );
769 }
770 }
771
772 return btrue;
773 }
774
775 //--------------------------------------------------------------------------------------------
776 //--------------------------------------------------------------------------------------------
777
778 //bool_t BSP_tree_init_0( BSP_tree_t * t )
779 //{
780 // /// @details BB@> reset the tree to the "empty" state. Assume we do not own the nodes.lst or children.lst.
781 //
782 // size_t i;
783 // BSP_branch_t * pbranch;
784 //
785 // // free any the nodes in the tree
786 // BSP_tree_free_nodes( t, bfalse );
787 //
788 // // initialize the leaves.
789 // t->branch_free.top = 0;
790 // t->branch_used.top = 0;
791 // for ( i = 0; i < t->branch_all.alloc; i++ )
792 // {
793 // // grab a branch off of the static list
794 // pbranch = t->branch_all.ary + i;
795 //
796 // if ( NULL == pbranch ) continue;
797 //
798 // // completely unlink the branch
799 // BSP_branch_unlink( pbranch );
800 //
801 // // push it onto the "stack"
802 // BSP_branch_pary_push_back( &( t->branch_free ), pbranch );
803 // };
804 //
805 // return btrue;
806 //}
807
808 //--------------------------------------------------------------------------------------------
BSP_tree_ctor(BSP_tree_t * t,Sint32 dim,Sint32 depth)809 BSP_tree_t * BSP_tree_ctor( BSP_tree_t * t, Sint32 dim, Sint32 depth )
810 {
811 int node_count;
812 size_t cnt;
813
814 if ( NULL == t ) return t;
815
816 memset( t, 0, sizeof( *t ) );
817
818 node_count = BSP_tree_count_nodes( dim, depth );
819 if ( node_count < 0 ) return t;
820
821 if ( !BSP_tree_alloc( t, node_count, dim ) ) return t;
822
823 t->depth = depth;
824
825 // initialize the free list
826 t->branch_free.top = 0;
827 t->branch_used.top = 0;
828 for ( cnt = 0; cnt < t->branch_all.alloc; cnt++ )
829 {
830 BSP_branch_pary_push_back( &( t->branch_free ), t->branch_all.ary + cnt );
831 }
832
833 return t;
834 }
835
836 //--------------------------------------------------------------------------------------------
BSP_tree_dtor(BSP_tree_t * t)837 BSP_tree_t * BSP_tree_dtor( BSP_tree_t * t )
838 {
839 if ( NULL == t ) return NULL;
840
841 BSP_tree_dealloc( t );
842
843 return t;
844 }
845
846 //--------------------------------------------------------------------------------------------
BSP_tree_alloc(BSP_tree_t * t,size_t count,size_t dim)847 bool_t BSP_tree_alloc( BSP_tree_t * t, size_t count, size_t dim )
848 {
849 size_t cnt;
850
851 if ( NULL == t ) return bfalse;
852
853 if ( NULL != t->branch_all.ary || t->branch_all.alloc > 0 ) return bfalse;
854
855 // re-initialize the variables
856 t->dimensions = 0;
857
858 // allocate the infinite node list
859 BSP_leaf_list_alloc( &( t->infinite ), dim );
860
861 // allocate the branches
862 BSP_branch_ary_ctor( &( t->branch_all ), count );
863 if ( NULL == t->branch_all.ary || 0 == t->branch_all.alloc ) return bfalse;
864
865 // initialize the array branches
866 for ( cnt = 0; cnt < count; cnt++ )
867 {
868 BSP_branch_ctor( t->branch_all.ary + cnt, dim );
869 }
870
871 // allocate the aux arrays
872 BSP_branch_pary_ctor( &( t->branch_used ), count );
873 BSP_branch_pary_ctor( &( t->branch_free ), count );
874
875 // initialize the root bounding box
876 BSP_aabb_ctor( &( t->bbox ), dim );
877
878 // set the variables
879 t->dimensions = dim;
880
881 return btrue;
882 }
883
884 //--------------------------------------------------------------------------------------------
BSP_tree_dealloc(BSP_tree_t * t)885 bool_t BSP_tree_dealloc( BSP_tree_t * t )
886 {
887 size_t i;
888
889 if ( NULL == t ) return bfalse;
890
891 if ( NULL == t->branch_all.ary || 0 == t->branch_all.alloc ) return btrue;
892
893 // allocate the infinite node list
894 BSP_leaf_list_dealloc( &( t->infinite ) );
895
896 // destruct the branches
897 for ( i = 0; i < t->branch_all.alloc; i++ )
898 {
899 BSP_branch_dtor( t->branch_all.ary + i );
900 }
901
902 // deallocate the branches
903 BSP_branch_ary_dtor( &( t->branch_all ) );
904
905 // deallocate the aux arrays
906 BSP_branch_pary_dtor( &( t->branch_used ) );
907 BSP_branch_pary_dtor( &( t->branch_free ) );
908
909 // deallocate the root bounding box
910 BSP_aabb_dtor( &( t->bbox ) );
911
912 return btrue;
913 }
914
915 //--------------------------------------------------------------------------------------------
BSP_tree_count_nodes(Sint32 dim,Sint32 depth)916 Sint32 BSP_tree_count_nodes( Sint32 dim, Sint32 depth )
917 {
918 int itmp;
919 Sint32 node_count;
920 Uint32 numer, denom;
921
922 itmp = dim * ( depth + 1 );
923 if ( itmp > 31 ) return -1;
924
925 numer = ( 1 << itmp ) - 1;
926 denom = ( 1 << dim ) - 1;
927 node_count = numer / denom;
928
929 return node_count;
930 }
931
932 //--------------------------------------------------------------------------------------------
BSP_tree_remove_used(BSP_tree_t * t,BSP_branch_t * B)933 bool_t BSP_tree_remove_used( BSP_tree_t * t, BSP_branch_t * B )
934 {
935 size_t cnt;
936
937 if ( NULL == t || 0 == t->branch_used.top ) return bfalse;
938
939 if ( NULL == B ) return bfalse;
940
941 // scan the used list for the branch
942 for ( cnt = 0; cnt < t->branch_used.top; cnt++ )
943 {
944 if ( B == t->branch_used.ary[cnt] ) break;
945 }
946
947 // did we find the branch in the used list?
948 if ( cnt == t->branch_used.top ) return bfalse;
949
950 // reduce the size of the list
951 t->branch_used.top--;
952
953 // move the branch that we found to the top of the list
954 SWAP( BSP_branch_t *, t->branch_used.ary[cnt], t->branch_used.ary[t->branch_used.top] );
955
956 return btrue;
957 }
958
959 //--------------------------------------------------------------------------------------------
BSP_tree_alloc_branch(BSP_tree_t * t)960 BSP_branch_t * BSP_tree_alloc_branch( BSP_tree_t * t )
961 {
962 BSP_branch_t ** pB = NULL, * B = NULL;
963
964 if ( NULL == t ) return NULL;
965
966 // grab the top branch
967 pB = BSP_branch_pary_pop_back( &( t->branch_free ) );
968 if ( NULL == pB ) return NULL;
969
970 B = *pB;
971 if ( NULL == B ) return NULL;
972
973 // add it to the used list
974 BSP_branch_pary_push_back( &( t->branch_used ), B );
975
976 return B;
977 }
978
979 //--------------------------------------------------------------------------------------------
BSP_tree_free_branch(BSP_tree_t * t,BSP_branch_t * B)980 bool_t BSP_tree_free_branch( BSP_tree_t * t, BSP_branch_t * B )
981 {
982 bool_t retval;
983
984 if ( NULL == t || NULL == B ) return bfalse;
985
986 retval = bfalse;
987 if ( BSP_tree_remove_used( t, B ) )
988 {
989 // add it to the used list
990 retval = BSP_branch_pary_push_back( &( t->branch_free ), B );
991 }
992
993 return retval;
994 }
995
996 //--------------------------------------------------------------------------------------------
BSP_tree_get_free(BSP_tree_t * t)997 BSP_branch_t * BSP_tree_get_free( BSP_tree_t * t )
998 {
999 BSP_branch_t * B;
1000
1001 // try to get a branch from our pre-allocated list. do all necessary book-keeping
1002 B = BSP_tree_alloc_branch( t );
1003 if ( NULL == B ) return NULL;
1004
1005 if ( NULL != B )
1006 {
1007 // make sure that this branch does not have data left over
1008 // from its last use
1009 EGOBOO_ASSERT( NULL == B->nodes.lst );
1010
1011 // make sure that the data is cleared out
1012 BSP_branch_unlink( B );
1013 }
1014
1015 return B;
1016 }
1017
1018 //--------------------------------------------------------------------------------------------
1019
1020 //bool_t BSP_tree_add_free( BSP_tree_t * t, BSP_branch_t * B )
1021 //{
1022 // if ( NULL == t || NULL == B ) return bfalse;
1023 //
1024 // // remove any links to other leaves
1025 // BSP_branch_unlink( B );
1026 //
1027 // return BSP_tree_free_branch( t, B );
1028 //}
1029
1030 //--------------------------------------------------------------------------------------------
1031
1032 //bool_t BSP_tree_free_all( BSP_tree_t * t )
1033 //{
1034 // if ( !BSP_tree_free_nodes( t, bfalse ) ) return bfalse;
1035 //
1036 // if ( !BSP_tree_free_branches( t ) ) return bfalse;
1037 //
1038 // return btrue;
1039 //}
1040
1041 //--------------------------------------------------------------------------------------------
BSP_tree_clear(BSP_tree_t * t,bool_t recursive)1042 bool_t BSP_tree_clear( BSP_tree_t * t, bool_t recursive )
1043 {
1044 if ( NULL == t ) return bfalse;
1045
1046 if ( recursive )
1047 {
1048 BSP_branch_clear( t->root, btrue );
1049 }
1050
1051 // free the infinite nodes of the tree
1052 BSP_leaf_list_reset( &( t->infinite ) );
1053
1054 return btrue;
1055 }
1056
1057 //--------------------------------------------------------------------------------------------
1058
1059 //bool_t BSP_tree_free_nodes( BSP_tree_t * t, bool_t recursive )
1060 //{
1061 // if ( NULL == t ) return bfalse;
1062 //
1063 // if ( recursive )
1064 // {
1065 // BSP_branch_free_nodes( t->root, btrue );
1066 // }
1067 //
1068 // // free the infinite nodes of the tree
1069 // BSP_leaf_list_reset( &( t->infinite ) );
1070 //
1071 // return btrue;
1072 //}
1073
1074 //--------------------------------------------------------------------------------------------
BSP_tree_free_branches(BSP_tree_t * t)1075 bool_t BSP_tree_free_branches( BSP_tree_t * t )
1076 {
1077 size_t cnt;
1078
1079 if ( NULL == t ) return bfalse;
1080
1081 // transfer all the "used" branches back to the "free" branches
1082 for ( cnt = 0; cnt < t->branch_used.top; cnt++ )
1083 {
1084 // grab a used branch
1085 BSP_branch_t * pbranch = t->branch_used.ary[cnt];
1086 if ( NULL == pbranch ) continue;
1087
1088 // completely unlink the branch
1089 BSP_branch_unlink( pbranch );
1090
1091 // return the branch to the free list
1092 BSP_branch_pary_push_back( &( t->branch_free ), pbranch );
1093 }
1094
1095 // reset the used list
1096 t->branch_used.top = 0;
1097
1098 // remove the tree root
1099 t->root = NULL;
1100
1101 return btrue;
1102 }
1103
1104 //--------------------------------------------------------------------------------------------
BSP_tree_prune(BSP_tree_t * t)1105 bool_t BSP_tree_prune( BSP_tree_t * t )
1106 {
1107 /// @details BB@> remove all leaves with no children.lst or nodes.lst.
1108
1109 size_t cnt;
1110
1111 if ( NULL == t || NULL == t->root ) return bfalse;
1112
1113 // search through all allocated branches. This will not catch all of the
1114 // empty branches every time, but it should catch quite a few
1115 for ( cnt = 0; cnt < t->branch_used.top; cnt++ )
1116 {
1117 BSP_tree_prune_branch( t, cnt );
1118 }
1119
1120 return btrue;
1121 }
1122
1123 //--------------------------------------------------------------------------------------------
BSP_tree_ensure_root(BSP_tree_t * t)1124 BSP_branch_t * BSP_tree_ensure_root( BSP_tree_t * t )
1125 {
1126 size_t cnt;
1127 BSP_branch_t * proot;
1128
1129 if ( NULL == t ) return NULL;
1130
1131 if ( NULL != t->root ) return t->root;
1132
1133 proot = BSP_tree_get_free( t );
1134 if ( NULL == proot ) return NULL;
1135
1136 // make sure that it is unlinked
1137 BSP_branch_unlink( proot );
1138
1139 // copy the tree bounding box to the root node
1140 for ( cnt = 0; cnt < t->dimensions; cnt++ )
1141 {
1142 proot->bsp_bbox.mins.ary[cnt] = t->bbox.mins.ary[cnt];
1143 proot->bsp_bbox.mids.ary[cnt] = t->bbox.mids.ary[cnt];
1144 proot->bsp_bbox.maxs.ary[cnt] = t->bbox.maxs.ary[cnt];
1145 }
1146
1147 // fix the depth
1148 proot->depth = 0;
1149
1150 // assign the root to the tree
1151 t->root = proot;
1152
1153 return proot;
1154 }
1155
1156 //--------------------------------------------------------------------------------------------
BSP_tree_ensure_branch(BSP_tree_t * t,BSP_branch_t * B,int index)1157 BSP_branch_t * BSP_tree_ensure_branch( BSP_tree_t * t, BSP_branch_t * B, int index )
1158 {
1159 BSP_branch_t * pbranch;
1160
1161 if (( NULL == t ) || ( NULL == B ) ) return NULL;
1162 if ( index < 0 || ( signed )index > ( signed )B->children.count ) return NULL;
1163
1164 // grab any existing value
1165 pbranch = B->children.lst[index];
1166
1167 // if this branch doesn't exist, create it and insert it properly.
1168 if ( NULL == pbranch )
1169 {
1170 // grab a free branch
1171 pbranch = BSP_tree_get_free( t );
1172
1173 if ( NULL != pbranch )
1174 {
1175 // make sure that it is unlinked
1176 BSP_branch_unlink( pbranch );
1177
1178 // generate its bounding box
1179 pbranch->depth = B->depth + 1;
1180 BSP_generate_aabb_child( &( B->bsp_bbox ), index, &( pbranch->bsp_bbox ) );
1181
1182 // insert it in the correct position
1183 BSP_branch_insert_branch( B, index, pbranch );
1184 }
1185 }
1186
1187 return pbranch;
1188 }
1189
1190 //--------------------------------------------------------------------------------------------
1191 //bool_t BSP_tree_insert( BSP_tree_t * t, BSP_branch_t * B, BSP_leaf_t * n, int index )
1192 //{
1193 // bool_t retval;
1194 //
1195 // if (( NULL == t ) || ( NULL == B ) || ( NULL == n ) ) return bfalse;
1196 // if (( signed )index > ( signed )B->children.count ) return bfalse;
1197 //
1198 // if ( index >= 0 && NULL != B->children.lst[index] )
1199 // {
1200 // // inserting a node into the child
1201 // retval = BSP_branch_insert_leaf( B->children.lst[index], n );
1202 // }
1203 // else if ( index < 0 || 0 == t->branch_free.top )
1204 // {
1205 // // inserting a node into this branch node
1206 // // this can either occur because someone requested it (index < 0)
1207 // // OR because there are no more free nodes
1208 // retval = BSP_branch_insert_leaf( B, n );
1209 // }
1210 // else
1211 // {
1212 // // the requested B->children.lst[index] slot is empty. grab a pre-allocated
1213 // // BSP_branch_t from the free list in the BSP_tree_t structure an insert it in
1214 // // this child node
1215 //
1216 // BSP_branch_t * pbranch = BSP_tree_ensure_branch( t, B, index );
1217 //
1218 // retval = BSP_branch_insert_leaf( pbranch, n );
1219 // }
1220 //
1221 // // do some book keeping
1222 // if( retval )
1223 // {
1224 // if( 0 == B->children.inserted )
1225 // {
1226 // BSP_aabb_copy( &(B->children.bbox), &(n->bbox) );
1227 // }
1228 // else
1229 // {
1230 // BSP_aabb_self_union( &(B->children.bbox), &(n->bbox) );
1231 // }
1232 //
1233 // B->children.inserted++;
1234 // }
1235 //
1236 // // something went wrong ?
1237 // return retval;
1238 //}
1239
1240 //--------------------------------------------------------------------------------------------
BSP_tree_insert_infinite(BSP_tree_t * ptree,BSP_leaf_t * pleaf)1241 bool_t BSP_tree_insert_infinite( BSP_tree_t * ptree, BSP_leaf_t * pleaf )
1242 {
1243 return BSP_leaf_list_insert( &( ptree->infinite ), pleaf );
1244 }
1245
1246 //--------------------------------------------------------------------------------------------
BSP_tree_insert_leaf(BSP_tree_t * ptree,BSP_leaf_t * pleaf)1247 bool_t BSP_tree_insert_leaf( BSP_tree_t * ptree, BSP_leaf_t * pleaf )
1248 {
1249 bool_t retval;
1250
1251 if ( NULL == ptree || NULL == pleaf ) return bfalse;
1252
1253 if ( !BSP_aabb_lhs_contains_rhs( &( ptree->bbox ), &( pleaf->bbox ) ) )
1254 {
1255 // put the leaf at the head of the infinite list
1256 retval = BSP_tree_insert_infinite( ptree, pleaf );
1257 }
1258 else
1259 {
1260 BSP_branch_t * proot = BSP_tree_ensure_root( ptree );
1261
1262 retval = BSP_tree_insert_leaf_rec( ptree, proot, pleaf, 0 );
1263 }
1264
1265 return retval;
1266 }
1267
1268 //--------------------------------------------------------------------------------------------
BSP_tree_insert_leaf_rec(BSP_tree_t * ptree,BSP_branch_t * pbranch,BSP_leaf_t * pleaf,int depth)1269 bool_t BSP_tree_insert_leaf_rec( BSP_tree_t * ptree, BSP_branch_t * pbranch, BSP_leaf_t * pleaf, int depth )
1270 {
1271 /// @details BB@> recursively insert a leaf in a tree of BSP_branch_t*. Get new branches using the
1272 /// BSP_tree_get_free() function to allocate any new branches that are needed.
1273
1274 size_t cnt;
1275 size_t index;
1276 bool_t fail;
1277 bool_t inserted_branch, inserted_leaf;
1278
1279 BSP_branch_t * pchild;
1280
1281 if ( NULL == ptree || NULL == pbranch || NULL == pleaf ) return bfalse;
1282
1283 // keep track of the tree depth
1284 depth++;
1285
1286 // keep track of where the leaf was inserted
1287 inserted_branch = bfalse;
1288 inserted_leaf = bfalse;
1289
1290 // don't go too deep
1291 if ( depth > ptree->depth )
1292 {
1293 // insert the node under this branch
1294 inserted_leaf = BSP_branch_insert_leaf( pbranch, pleaf );
1295 return inserted_leaf;
1296 }
1297
1298 //---- determine which child the leaf needs to go under
1299 /// @note This function is not optimal, since we encode the comparisons
1300 /// in the 32-bit integer indices, and then may have to decimate index to construct
1301 /// the child branch's bounding by calling BSP_generate_aabb_child().
1302 /// The reason that it is done this way is that we would have to be dynamically
1303 /// allocating and deallocating memory every time this function is called, otherwise. Big waste of time.
1304 fail = bfalse;
1305 index = 0;
1306 for ( cnt = 0; cnt < ptree->dimensions; cnt++ )
1307 {
1308 if ( pleaf->bbox.mins.ary[cnt] >= pbranch->bsp_bbox.mins.ary[cnt] && pleaf->bbox.maxs.ary[cnt] <= pbranch->bsp_bbox.mids.ary[cnt] )
1309 {
1310 index <<= 1;
1311 index |= 0;
1312 }
1313 else if ( pleaf->bbox.mins.ary[cnt] >= pbranch->bsp_bbox.mids.ary[cnt] && pleaf->bbox.maxs.ary[cnt] <= pbranch->bsp_bbox.maxs.ary[cnt] )
1314 {
1315 index <<= 1;
1316 index |= 1;
1317 }
1318 else if ( pleaf->bbox.mins.ary[cnt] >= pbranch->bsp_bbox.mins.ary[cnt] && pleaf->bbox.maxs.ary[cnt] <= pbranch->bsp_bbox.maxs.ary[cnt] )
1319 {
1320 // this leaf belongs at this node
1321 break;
1322 }
1323 else
1324 {
1325 // this leaf is actually bigger than this branch
1326 fail = btrue;
1327 break;
1328 }
1329 }
1330
1331 if ( fail )
1332 {
1333 // we cannot place this the node under this branch
1334 return bfalse;
1335 }
1336
1337 //---- insert the leaf in the right place
1338 if ( cnt < ptree->dimensions )
1339 {
1340 // place this node at this index
1341 inserted_leaf = BSP_branch_insert_leaf( pbranch, pleaf );
1342 }
1343 else if ( index < pbranch->children.count )
1344 {
1345 bool_t created;
1346
1347 pchild = pbranch->children.lst[index];
1348
1349 created = bfalse;
1350 if ( NULL == pchild )
1351 {
1352 pchild = BSP_tree_ensure_branch( ptree, pbranch, index );
1353 created = ( NULL != pchild );
1354 }
1355
1356 EGOBOO_ASSERT( pchild->depth == pbranch->depth + 1 );
1357
1358 if ( NULL != pchild )
1359 {
1360 // insert the leaf
1361 inserted_branch = BSP_tree_insert_leaf_rec( ptree, pchild, pleaf, depth );
1362 }
1363 }
1364
1365 // do some book keeping
1366 if ( inserted_branch )
1367 {
1368 if ( 0 == pbranch->children.inserted )
1369 {
1370 BSP_aabb_copy( &( pbranch->children.bbox ), &( pleaf->bbox ) );
1371 }
1372 else
1373 {
1374 BSP_aabb_self_union( &( pbranch->children.bbox ), &( pleaf->bbox ) );
1375 }
1376
1377 pbranch->children.inserted++;
1378 }
1379
1380 // not necessary, but best to be thorough
1381 depth--;
1382
1383 return inserted_branch || inserted_leaf;
1384 }
1385
1386 //--------------------------------------------------------------------------------------------
BSP_tree_prune_branch(BSP_tree_t * t,size_t cnt)1387 bool_t BSP_tree_prune_branch( BSP_tree_t * t, size_t cnt )
1388 {
1389 /// @details BB@> an optimized version of iterating through the t->branch_used list
1390 // and then calling BSP_branch_prune() on the empty branch. In the old method,
1391 // the t->branch_used list was searched twice to find each empty branch. This
1392 // function does it only once.
1393
1394 size_t i;
1395 bool_t remove;
1396
1397 BSP_branch_t * B;
1398
1399 if ( NULL == t || cnt < 0 || cnt >= t->branch_used.top ) return bfalse;
1400
1401 B = t->branch_used.ary[ cnt ];
1402 if ( NULL == B ) return bfalse;
1403
1404 // do not remove the root node
1405 if ( B == t->root ) return btrue;
1406
1407 remove = bfalse;
1408 if ( BSP_branch_empty( B ) )
1409 {
1410 bool_t found = BSP_branch_unlink( B );
1411
1412 // not finding yourself is an error
1413 EGOBOO_ASSERT( found );
1414
1415 remove = btrue;
1416 }
1417
1418 if ( remove )
1419 {
1420 // reduce the size of the list
1421 t->branch_used.top--;
1422
1423 // set B's data to "safe" values
1424 B->parent = NULL;
1425 for ( i = 0; i < B->children.count; i++ ) B->children.lst[i] = NULL;
1426 BSP_leaf_list_clear( &( B->nodes ) );
1427 B->depth = -1;
1428 BSP_aabb_clear( &( B->bsp_bbox ) );
1429
1430 // move the branch that we found to the top of the list
1431 SWAP( BSP_branch_t *, t->branch_used.ary[cnt], t->branch_used.ary[t->branch_used.top] );
1432
1433 // add the branch to the free list
1434 BSP_branch_pary_push_back( &( t->branch_free ), B );
1435 }
1436
1437 return remove;
1438 }
1439
1440 //--------------------------------------------------------------------------------------------
BSP_tree_collide(BSP_tree_t * tree,BSP_aabb_t * paabb,BSP_leaf_pary_t * colst)1441 int BSP_tree_collide( BSP_tree_t * tree, BSP_aabb_t * paabb, BSP_leaf_pary_t * colst )
1442 {
1443 /// @details BB@> fill the collision list with references to tiles that the object volume may overlap.
1444 // Return the number of collisions found.
1445
1446 if ( NULL == tree || NULL == paabb ) return 0;
1447
1448 if ( NULL == colst ) return 0;
1449 colst->top = 0;
1450 if ( 0 == colst->alloc ) return 0;
1451
1452 // collide with any "infinite" nodes
1453 BSP_leaf_list_collide( &( tree->infinite ), paabb, colst );
1454
1455 // collide with the rest of the tree
1456 BSP_branch_collide( tree->root, paabb, colst );
1457
1458 return colst->top;
1459 }
1460
1461 //--------------------------------------------------------------------------------------------
1462 //--------------------------------------------------------------------------------------------
BSP_leaf_list_ctor(BSP_leaf_list_t * LL,size_t dim)1463 BSP_leaf_list_t * BSP_leaf_list_ctor( BSP_leaf_list_t * LL, size_t dim )
1464 {
1465 if ( NULL == LL ) return LL;
1466
1467 memset( LL, 0, sizeof( *LL ) );
1468
1469 BSP_leaf_list_alloc( LL, dim );
1470
1471 return LL;
1472 }
1473
1474 //--------------------------------------------------------------------------------------------
BSP_leaf_list_dtor(BSP_leaf_list_t * LL)1475 BSP_leaf_list_t * BSP_leaf_list_dtor( BSP_leaf_list_t * LL )
1476 {
1477 if ( NULL == LL ) return LL;
1478
1479 BSP_leaf_list_dealloc( LL );
1480
1481 memset( LL, 0, sizeof( *LL ) );
1482
1483 return LL;
1484 }
1485
1486 //--------------------------------------------------------------------------------------------
BSP_leaf_list_alloc(BSP_leaf_list_t * LL,size_t dim)1487 bool_t BSP_leaf_list_alloc( BSP_leaf_list_t * LL, size_t dim )
1488 {
1489 if ( NULL == LL ) return bfalse;
1490
1491 BSP_leaf_list_dealloc( LL );
1492
1493 BSP_aabb_alloc( &( LL->bbox ), dim );
1494
1495 return 0 != LL->bbox.dim;
1496 }
1497
1498 //--------------------------------------------------------------------------------------------
BSP_leaf_list_dealloc(BSP_leaf_list_t * LL)1499 bool_t BSP_leaf_list_dealloc( BSP_leaf_list_t * LL )
1500 {
1501 if ( NULL == LL ) return bfalse;
1502
1503 BSP_aabb_dealloc( &( LL->bbox ) );
1504
1505 return btrue;
1506 }
1507
1508 //--------------------------------------------------------------------------------------------
BSP_leaf_list_clear(BSP_leaf_list_t * LL)1509 BSP_leaf_list_t * BSP_leaf_list_clear( BSP_leaf_list_t * LL )
1510 {
1511 // DYNAMIC ALLOCATION in LL->bbox, so do not use memset
1512
1513 if ( NULL == LL ) return LL;
1514
1515 BSP_aabb_clear( &( LL->bbox ) );
1516 LL->count = 0;
1517 LL->lst = NULL;
1518
1519 return LL;
1520 }
1521
1522 //--------------------------------------------------------------------------------------------
BSP_leaf_list_insert(BSP_leaf_list_t * LL,BSP_leaf_t * n)1523 bool_t BSP_leaf_list_insert( BSP_leaf_list_t * LL, BSP_leaf_t * n )
1524 {
1525 /// @details BB@> Insert a leaf in the list, making sure there are no duplicates.
1526 /// Duplicates will cause loops in the list and make it impossible to
1527 /// traverse properly.
1528
1529 bool_t retval;
1530 size_t cnt;
1531 BSP_leaf_t * pleaf;
1532
1533 if ( NULL == LL || NULL == n ) return bfalse;
1534
1535 if ( n->inserted )
1536 {
1537 // hmmm.... what to do?
1538 log_warning( "BSP_leaf_list_insert() - trying to insert a BSP_leaf that is claiming to be part of a list already\n" );
1539 }
1540
1541 retval = bfalse;
1542
1543 if ( NULL == LL->lst || 0 == LL->count )
1544 {
1545 // prepare the node
1546 n->next = NULL;
1547
1548 // insert the node
1549 LL->lst = n;
1550 LL->count = 1;
1551 BSP_aabb_copy( &( LL->bbox ), &( n->bbox ) );
1552
1553 n->inserted = btrue;
1554
1555 retval = btrue;
1556 }
1557 else
1558 {
1559 bool_t found = bfalse;
1560
1561 for ( cnt = 0, pleaf = LL->lst;
1562 NULL != pleaf->next && cnt < LL->count && !found;
1563 cnt++, pleaf = pleaf->next )
1564 {
1565 // do not insert duplicates, or we have a big problem
1566 if ( n == pleaf )
1567 {
1568 found = btrue;
1569 break;
1570 }
1571 }
1572
1573 if ( !found )
1574 {
1575 EGOBOO_ASSERT( NULL == pleaf->next );
1576
1577 // prepare the node
1578 n->next = NULL;
1579
1580 // insert the node at the end of the list
1581 pleaf->next = n;
1582 LL->count = LL->count + 1;
1583 BSP_aabb_self_union( &( LL->bbox ), &( n->bbox ) );
1584
1585 n->inserted = btrue;
1586
1587 retval = btrue;
1588 }
1589 }
1590
1591 return retval;
1592 }
1593
1594 //--------------------------------------------------------------------------------------------
BSP_leaf_list_reset(BSP_leaf_list_t * LL)1595 bool_t BSP_leaf_list_reset( BSP_leaf_list_t * LL )
1596 {
1597 /// @details BB@> Clear out the leaf list.
1598
1599 size_t cnt;
1600 BSP_leaf_t * ptmp;
1601
1602 if ( NULL == LL->lst )
1603 {
1604 BSP_leaf_list_clear( LL );
1605 return btrue;
1606 }
1607 if ( 0 == LL->count )
1608 {
1609 EGOBOO_ASSERT( NULL == LL->lst );
1610
1611 BSP_leaf_list_clear( LL );
1612 return btrue;
1613 }
1614
1615 for ( cnt = 0; NULL != LL->lst && cnt < LL->count; cnt++ )
1616 {
1617 // pop a node off the list
1618 ptmp = LL->lst;
1619 LL->lst = ptmp->next;
1620
1621 // clean up the node
1622 ptmp->inserted = bfalse;
1623 ptmp->next = NULL;
1624 };
1625
1626 // did we have a problem with the LL->count?
1627 EGOBOO_ASSERT( NULL == LL->lst );
1628
1629 // clear out the other data
1630 BSP_leaf_list_clear( LL );
1631
1632 return btrue;
1633 }
1634
1635 //--------------------------------------------------------------------------------------------
BSP_leaf_list_collide(BSP_leaf_list_t * LL,BSP_aabb_t * paabb,BSP_leaf_pary_t * colst)1636 bool_t BSP_leaf_list_collide( BSP_leaf_list_t * LL, BSP_aabb_t * paabb, BSP_leaf_pary_t * colst )
1637 {
1638 /// @details BB@> check for collisions with the given node list
1639
1640 size_t cnt;
1641 BSP_leaf_t * pleaf;
1642 bool_t retval;
1643 size_t colst_size;
1644
1645 // basic bounds checking
1646 if ( NULL == LL->lst || 0 == LL->count ) return bfalse;
1647 if ( NULL == paabb ) return bfalse;
1648
1649 // we have already the bounding box of all the leafs
1650 if ( !BSP_aabb_overlap( &( LL->bbox ), paabb ) ) return bfalse;
1651
1652 // if there is no more room in the colist, return bfalse
1653 colst_size = BSP_leaf_pary_get_size( colst );
1654 if ( 0 == colst_size || BSP_leaf_pary_get_top( colst ) >= colst_size )
1655 return bfalse;
1656
1657 // scan through every leaf
1658 for ( cnt = 0, pleaf = LL->lst;
1659 cnt < LL->count && NULL != pleaf;
1660 cnt++, pleaf = pleaf->next )
1661 {
1662 BSP_aabb_t * pleaf_bb = &( pleaf->bbox );
1663
1664 EGOBOO_ASSERT( pleaf->data_type > -1 );
1665
1666 if ( !pleaf->inserted )
1667 {
1668 // hmmm.... what to do?
1669 log_warning( "BSP_leaf_list_collide() - a node in a leaf list is claiming to not be inserted\n" );
1670 }
1671
1672 if ( BSP_aabb_overlap( paabb, pleaf_bb ) )
1673 {
1674 // we have a possible intersection
1675 if ( !BSP_leaf_pary_push_back( colst, pleaf ) ) break;
1676 }
1677 }
1678
1679 // return false if we maxed out the colist
1680 retval = ( BSP_leaf_pary_get_top( colst ) < colst_size );
1681
1682 return retval;
1683 }
1684
1685 //--------------------------------------------------------------------------------------------
1686 //--------------------------------------------------------------------------------------------
BSP_branch_list_ctor(BSP_branch_list_t * BL,size_t dim)1687 BSP_branch_list_t * BSP_branch_list_ctor( BSP_branch_list_t * BL, size_t dim )
1688 {
1689 if ( NULL == BL ) return BL;
1690
1691 memset( BL, 0, sizeof( *BL ) );
1692
1693 BSP_branch_list_alloc( BL, dim );
1694
1695 return BL;
1696 }
1697
1698 //--------------------------------------------------------------------------------------------
BSP_branch_list_dtor(BSP_branch_list_t * BL)1699 BSP_branch_list_t * BSP_branch_list_dtor( BSP_branch_list_t * BL )
1700 {
1701 if ( NULL == BL ) return BL;
1702
1703 BSP_branch_list_dealloc( BL );
1704
1705 memset( BL, 0, sizeof( *BL ) );
1706
1707 return BL;
1708 }
1709
1710 //--------------------------------------------------------------------------------------------
BSP_branch_list_alloc(BSP_branch_list_t * BL,size_t dim)1711 bool_t BSP_branch_list_alloc( BSP_branch_list_t * BL, size_t dim )
1712 {
1713 // determine the number of children from the number of dimensions
1714 size_t child_count = ( 0 == dim ) ? 0 : ( 2 << ( dim - 1 ) );
1715
1716 if ( NULL == BL ) return bfalse;
1717
1718 BSP_branch_list_dealloc( BL );
1719
1720 // allocate the child list
1721 BL->lst = EGOBOO_NEW_ARY( BSP_branch_t*, child_count );
1722 if ( NULL != BL->lst )
1723 {
1724 size_t cnt;
1725 for ( cnt = 0; cnt < child_count; cnt++ )
1726 {
1727 BL->lst[cnt] = NULL;
1728 }
1729 BL->count = child_count;
1730 }
1731
1732 BSP_aabb_alloc( &( BL->bbox ), dim );
1733
1734 return ( NULL != BL->lst ) && ( child_count == BL->count ) && ( dim == BL->bbox.dim );
1735 }
1736
1737 //--------------------------------------------------------------------------------------------
BSP_branch_list_dealloc(BSP_branch_list_t * BL)1738 bool_t BSP_branch_list_dealloc( BSP_branch_list_t * BL )
1739 {
1740 if ( NULL == BL ) return bfalse;
1741
1742 EGOBOO_DELETE_ARY( BL->lst );
1743 BL->count = 0;
1744
1745 BSP_aabb_dealloc( &( BL->bbox ) );
1746
1747 return btrue;
1748 }
1749
1750 //--------------------------------------------------------------------------------------------
1751 //--------------------------------------------------------------------------------------------
BSP_generate_aabb_child(BSP_aabb_t * psrc,int index,BSP_aabb_t * pdst)1752 bool_t BSP_generate_aabb_child( BSP_aabb_t * psrc, int index, BSP_aabb_t * pdst )
1753 {
1754 size_t cnt;
1755 int tnc, child_count;
1756
1757 // valid source?
1758 if ( NULL == psrc || psrc->dim <= 0 ) return bfalse;
1759
1760 // valid destination?
1761 if ( NULL == pdst ) return bfalse;
1762
1763 // valid index?
1764 child_count = 2 << ( psrc->dim - 1 );
1765 if ( index < 0 || index >= child_count ) return bfalse;
1766
1767 // make sure that the destination type matches the source type
1768 if ( pdst->dim != psrc->dim )
1769 {
1770 BSP_aabb_dtor( pdst );
1771 BSP_aabb_ctor( pdst, psrc->dim );
1772 }
1773
1774 // determine the bounds
1775 for ( cnt = 0; cnt < psrc->dim; cnt++ )
1776 {
1777 float maxval, minval;
1778
1779 tnc = (( signed )psrc->dim ) - 1 - cnt;
1780
1781 if ( 0 == ( index & ( 1 << tnc ) ) )
1782 {
1783 minval = psrc->mins.ary[cnt];
1784 maxval = psrc->mids.ary[cnt];
1785 }
1786 else
1787 {
1788 minval = psrc->mids.ary[cnt];
1789 maxval = psrc->maxs.ary[cnt];
1790 }
1791
1792 pdst->mins.ary[cnt] = minval;
1793 pdst->maxs.ary[cnt] = maxval;
1794 pdst->mids.ary[cnt] = 0.5f * ( minval + maxval );
1795 }
1796
1797 return btrue;
1798 }
1799