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 bbox.c
21 /// @brief
22 /// @details
23
24 #include "bbox.inl"
25
26 #include "egoboo_math.inl"
27
28 #include "egoboo_mem.h"
29
30 //--------------------------------------------------------------------------------------------
31 // struct s_cv_point_data
32 //--------------------------------------------------------------------------------------------
33 struct s_cv_point_data
34 {
35 bool_t inside;
36 fvec3_t pos;
37 float rads;
38 };
39 typedef struct s_cv_point_data cv_point_data_t;
40
41 static int cv_point_data_cmp( const void * pleft, const void * pright );
42
43 //--------------------------------------------------------------------------------------------
44 //--------------------------------------------------------------------------------------------
45
46 static oct_bb_t * oct_bb_ctor_index( oct_bb_t * pobb, int index );
47 static egoboo_rv oct_bb_copy_index( oct_bb_t * pdst, const oct_bb_t * psrc, int index );
48 static egoboo_rv oct_bb_validate_index( oct_bb_t * pobb, int index );
49 static bool_t oct_bb_empty_index( const oct_bb_t * pbb, int index );
50
51 static bool_t oct_bb_empty_raw( const oct_bb_t * pbb );
52 static bool_t oct_bb_empty_index_raw( const oct_bb_t * pbb, int index );
53
54 //--------------------------------------------------------------------------------------------
55 //--------------------------------------------------------------------------------------------
56
57 static Uint32 cv_list_count = 0;
58 static OVolume_t cv_list[1000];
59
60 //--------------------------------------------------------------------------------------------
61 //--------------------------------------------------------------------------------------------
aabb_lst_ctor(aabb_lst_t * lst)62 EGO_CONST aabb_lst_t * aabb_lst_ctor( aabb_lst_t * lst )
63 {
64 if ( NULL == lst ) return NULL;
65
66 memset( lst, 0, sizeof( *lst ) );
67
68 return lst;
69 }
70
71 //--------------------------------------------------------------------------------------------
aabb_lst_dtor(aabb_lst_t * lst)72 EGO_CONST aabb_lst_t * aabb_lst_dtor( aabb_lst_t * lst )
73 {
74 if ( NULL == lst ) return NULL;
75
76 if ( lst->count > 0 )
77 {
78 EGOBOO_DELETE( lst->list );
79 }
80
81 lst->count = 0;
82 lst->list = NULL;
83
84 return lst;
85 }
86
87 //--------------------------------------------------------------------------------------------
aabb_lst_renew(aabb_lst_t * lst)88 EGO_CONST aabb_lst_t * aabb_lst_renew( aabb_lst_t * lst )
89 {
90 if ( NULL == lst ) return NULL;
91
92 aabb_lst_dtor( lst );
93 return aabb_lst_ctor( lst );
94 }
95
96 //--------------------------------------------------------------------------------------------
aabb_lst_alloc(aabb_lst_t * lst,int count)97 EGO_CONST aabb_lst_t * aabb_lst_alloc( aabb_lst_t * lst, int count )
98 {
99 if ( NULL == lst ) return NULL;
100
101 aabb_lst_dtor( lst );
102
103 if ( count > 0 )
104 {
105 lst->list = EGOBOO_NEW_ARY( ego_aabb_t, count );
106 if ( NULL != lst->list )
107 {
108 lst->count = count;
109 }
110 }
111
112 return lst;
113 }
114
115 //--------------------------------------------------------------------------------------------
116 //--------------------------------------------------------------------------------------------
bbox_ary_ctor(aabb_ary_t * ary)117 EGO_CONST aabb_ary_t * bbox_ary_ctor( aabb_ary_t * ary )
118 {
119 if ( NULL == ary ) return NULL;
120
121 memset( ary, 0, sizeof( *ary ) );
122
123 return ary;
124 }
125
126 //--------------------------------------------------------------------------------------------
bbox_ary_dtor(aabb_ary_t * ary)127 EGO_CONST aabb_ary_t * bbox_ary_dtor( aabb_ary_t * ary )
128 {
129 int i;
130
131 if ( NULL == ary ) return NULL;
132
133 if ( NULL != ary->list )
134 {
135 for ( i = 0; i < ary->count; i++ )
136 {
137 aabb_lst_dtor( ary->list + i );
138 }
139
140 EGOBOO_DELETE( ary->list );
141 }
142
143 ary->count = 0;
144 ary->list = NULL;
145
146 return ary;
147 }
148
149 //--------------------------------------------------------------------------------------------
bbox_ary_renew(aabb_ary_t * ary)150 EGO_CONST aabb_ary_t * bbox_ary_renew( aabb_ary_t * ary )
151 {
152 if ( NULL == ary ) return NULL;
153 bbox_ary_dtor( ary );
154 return bbox_ary_ctor( ary );
155 }
156
157 //--------------------------------------------------------------------------------------------
bbox_ary_alloc(aabb_ary_t * ary,int count)158 EGO_CONST aabb_ary_t * bbox_ary_alloc( aabb_ary_t * ary, int count )
159 {
160 if ( NULL == ary ) return NULL;
161
162 bbox_ary_dtor( ary );
163
164 if ( count > 0 )
165 {
166 ary->list = EGOBOO_NEW_ARY( aabb_lst_t, count );
167 if ( NULL != ary->list )
168 {
169 ary->count = count;
170 }
171 }
172
173 return ary;
174 }
175
176 //--------------------------------------------------------------------------------------------
177 //--------------------------------------------------------------------------------------------
OVolume_merge(const OVolume_t * pv1,const OVolume_t * pv2)178 OVolume_t OVolume_merge( const OVolume_t * pv1, const OVolume_t * pv2 )
179 {
180 OVolume_t rv;
181
182 // construct the OVolume
183 memset( &rv, 0, sizeof( rv ) );
184 rv.lod = -1;
185
186 if ( NULL == pv1 && NULL == pv2 )
187 {
188 return rv;
189 }
190 else if ( NULL == pv2 )
191 {
192 return *pv1;
193 }
194 else if ( NULL == pv1 )
195 {
196 return *pv2;
197 }
198 else
199 {
200 // check for uninitialized volumes
201 if ( -1 == pv1->lod && -1 == pv2->lod )
202 {
203 return rv;
204 }
205 else if ( -1 == pv1->lod )
206 {
207 return *pv2;
208 }
209 else if ( -1 == pv2->lod )
210 {
211 return *pv1;
212 };
213
214 // merge the volumes
215 oct_bb_union( &( pv1->oct ), &( pv2->oct ), &( rv.oct ) );
216
217 // check for an invalid volume
218 rv.lod = rv.oct.empty ? -1 : 1;
219 }
220
221 return rv;
222 }
223
224 //--------------------------------------------------------------------------------------------
OVolume_intersect(const OVolume_t * pv1,const OVolume_t * pv2)225 OVolume_t OVolume_intersect( const OVolume_t * pv1, const OVolume_t * pv2 )
226 {
227 OVolume_t rv;
228
229 // construct the OVolume
230 memset( &rv, 0, sizeof( rv ) );
231 rv.lod = -1;
232
233 if ( NULL == pv1 || NULL == pv2 )
234 {
235 return rv;
236 }
237 else
238 {
239 // check for uninitialized volumes
240 if ( -1 == pv1->lod && -1 == pv2->lod )
241 {
242 return rv;
243 }
244 else if ( -1 == pv1->lod )
245 {
246 return *pv2;
247 }
248 else if ( -1 == pv2->lod )
249 {
250 return *pv1;
251 }
252
253 // intersect the volumes
254 oct_bb_intersection_index( &( pv1->oct ), &( pv1->oct ), &( rv.oct ), OCT_X );
255 if ( rv.oct.mins[OCT_X] >= rv.oct.maxs[OCT_X] ) return rv;
256
257 oct_bb_intersection_index( &( pv1->oct ), &( pv1->oct ), &( rv.oct ), OCT_Y );
258 if ( rv.oct.mins[OCT_Y] >= rv.oct.maxs[OCT_Y] ) return rv;
259
260 oct_bb_intersection_index( &( pv1->oct ), &( pv1->oct ), &( rv.oct ), OCT_Z );
261 if ( rv.oct.mins[OCT_Z] >= rv.oct.maxs[OCT_Z] ) return rv;
262
263 if ( pv1->lod >= 0 && pv2->lod >= 0 )
264 {
265 oct_bb_intersection_index( &( pv1->oct ), &( pv1->oct ), &( rv.oct ), OCT_XY );
266 if ( rv.oct.mins[OCT_XY] >= rv.oct.maxs[OCT_XY] ) return rv;
267
268 oct_bb_intersection_index( &( pv1->oct ), &( pv1->oct ), &( rv.oct ), OCT_YX );
269 if ( rv.oct.mins[OCT_YX] >= rv.oct.maxs[OCT_YX] ) return rv;
270 }
271 else if ( pv1->lod >= 0 )
272 {
273 rv.oct.mins[OCT_XY] = MAX( pv1->oct.mins[OCT_XY], pv2->oct.mins[OCT_X] + pv2->oct.mins[OCT_Y] );
274 rv.oct.maxs[OCT_XY] = MIN( pv1->oct.maxs[OCT_XY], pv2->oct.maxs[OCT_X] + pv2->oct.maxs[OCT_Y] );
275 if ( rv.oct.mins[OCT_XY] >= rv.oct.maxs[OCT_XY] ) return rv;
276
277 rv.oct.mins[OCT_YX] = MAX( pv1->oct.mins[OCT_YX], -pv2->oct.maxs[OCT_X] + pv2->oct.mins[OCT_Y] );
278 rv.oct.maxs[OCT_YX] = MIN( pv1->oct.maxs[OCT_YX], -pv2->oct.mins[OCT_X] + pv2->oct.maxs[OCT_Y] );
279 if ( rv.oct.mins[OCT_YX] >= rv.oct.maxs[OCT_YX] ) return rv;
280 }
281 else if ( pv2->lod >= 0 )
282 {
283 rv.oct.mins[OCT_XY] = MAX( pv1->oct.mins[OCT_X] + pv1->oct.mins[OCT_Y], pv2->oct.mins[OCT_XY] );
284 rv.oct.maxs[OCT_XY] = MIN( pv1->oct.maxs[OCT_X] + pv1->oct.maxs[OCT_Y], pv2->oct.maxs[OCT_XY] );
285 if ( rv.oct.mins[OCT_XY] >= rv.oct.maxs[OCT_XY] ) return rv;
286
287 rv.oct.mins[OCT_YX] = MAX( -pv1->oct.maxs[OCT_X] + pv1->oct.mins[OCT_Y], pv2->oct.mins[OCT_YX] );
288 rv.oct.maxs[OCT_YX] = MIN( -pv1->oct.mins[OCT_X] + pv1->oct.maxs[OCT_Y], pv2->oct.maxs[OCT_YX] );
289 if ( rv.oct.mins[OCT_YX] >= rv.oct.maxs[OCT_YX] ) return rv;
290 }
291 else
292 {
293 rv.oct.mins[OCT_XY] = MAX( pv1->oct.mins[OCT_X] + pv1->oct.mins[OCT_Y], pv2->oct.mins[OCT_X] + pv2->oct.mins[OCT_Y] );
294 rv.oct.maxs[OCT_XY] = MIN( pv1->oct.maxs[OCT_X] + pv1->oct.maxs[OCT_Y], pv2->oct.maxs[OCT_X] + pv2->oct.maxs[OCT_Y] );
295 if ( rv.oct.mins[OCT_XY] >= rv.oct.maxs[OCT_XY] ) return rv;
296
297 rv.oct.mins[OCT_YX] = MAX( -pv1->oct.maxs[OCT_X] + pv1->oct.mins[OCT_Y], -pv2->oct.maxs[OCT_X] + pv2->oct.mins[OCT_Y] );
298 rv.oct.maxs[OCT_YX] = MIN( -pv1->oct.mins[OCT_X] + pv1->oct.maxs[OCT_Y], -pv2->oct.mins[OCT_X] + pv2->oct.maxs[OCT_Y] );
299 if ( rv.oct.mins[OCT_YX] >= rv.oct.maxs[OCT_YX] ) return rv;
300 }
301
302 if ( 0 == pv1->lod && 0 == pv2->lod )
303 {
304 rv.lod = 0;
305 }
306 else
307 {
308 rv.lod = MIN( pv1->lod, pv2->lod );
309 }
310 }
311
312 return rv;
313 }
314
315 //--------------------------------------------------------------------------------------------
OVolume_refine(OVolume_t * pov,fvec3_t * pcenter,float * pvolume)316 bool_t OVolume_refine( OVolume_t * pov, fvec3_t * pcenter, float * pvolume )
317 {
318 /// @details BB@> determine which of the 16 possible intersection points are within both
319 // square and diamond bounding volumes
320
321 bool_t invalid;
322 int cnt, tnc, count;
323 float area, darea, volume;
324
325 fvec3_t center, centroid;
326 cv_point_data_t pd[16];
327
328 if ( NULL == pov ) return bfalse;
329
330 invalid = bfalse;
331 if ( pov->oct.mins[OCT_X] >= pov->oct.maxs[OCT_X] ) invalid = btrue;
332 else if ( pov->oct.mins[OCT_Y] >= pov->oct.maxs[OCT_Y] ) invalid = btrue;
333 else if ( pov->oct.mins[OCT_Z] >= pov->oct.maxs[OCT_Z] ) invalid = btrue;
334 else if ( pov->oct.mins[OCT_XY] >= pov->oct.maxs[OCT_XY] ) invalid = btrue;
335 else if ( pov->oct.mins[OCT_YX] >= pov->oct.maxs[OCT_YX] ) invalid = btrue;
336
337 if ( invalid )
338 {
339 pov->lod = -1;
340 if ( NULL != pvolume )( *pvolume ) = 0;
341 return bfalse;
342 }
343
344 // square points
345 cnt = 0;
346 pd[cnt].pos.x = pov->oct.maxs[OCT_X];
347 pd[cnt].pos.y = pov->oct.maxs[OCT_Y];
348
349 cnt++;
350 pd[cnt].pos.x = pov->oct.maxs[OCT_X];
351 pd[cnt].pos.y = pov->oct.mins[OCT_Y];
352
353 cnt++;
354 pd[cnt].pos.x = pov->oct.mins[OCT_X];
355 pd[cnt].pos.y = pov->oct.mins[OCT_Y];
356
357 cnt++;
358 pd[cnt].pos.x = pov->oct.mins[OCT_X];
359 pd[cnt].pos.y = pov->oct.maxs[OCT_Y];
360
361 // diamond points
362 cnt++;
363 pd[cnt].pos.x = ( pov->oct.maxs[OCT_XY] - pov->oct.mins[OCT_YX] ) * 0.5f;
364 pd[cnt].pos.y = ( pov->oct.maxs[OCT_XY] + pov->oct.mins[OCT_YX] ) * 0.5f;
365
366 cnt++;
367 pd[cnt].pos.x = ( pov->oct.mins[OCT_XY] - pov->oct.mins[OCT_YX] ) * 0.5f;
368 pd[cnt].pos.y = ( pov->oct.mins[OCT_XY] + pov->oct.mins[OCT_YX] ) * 0.5f;
369
370 cnt++;
371 pd[cnt].pos.x = ( pov->oct.mins[OCT_XY] - pov->oct.maxs[OCT_YX] ) * 0.5f;
372 pd[cnt].pos.y = ( pov->oct.mins[OCT_XY] + pov->oct.maxs[OCT_YX] ) * 0.5f;
373
374 cnt++;
375 pd[cnt].pos.x = ( pov->oct.maxs[OCT_XY] - pov->oct.maxs[OCT_YX] ) * 0.5f;
376 pd[cnt].pos.y = ( pov->oct.maxs[OCT_XY] + pov->oct.maxs[OCT_YX] ) * 0.5f;
377
378 // intersection points
379 cnt++;
380 pd[cnt].pos.x = pov->oct.maxs[OCT_X];
381 pd[cnt].pos.y = pov->oct.maxs[OCT_X] + pov->oct.mins[OCT_YX];
382
383 cnt++;
384 pd[cnt].pos.x = pov->oct.mins[OCT_Y] - pov->oct.mins[OCT_YX];
385 pd[cnt].pos.y = pov->oct.mins[OCT_Y];
386
387 cnt++;
388 pd[cnt].pos.x = -pov->oct.mins[OCT_Y] + pov->oct.mins[OCT_XY];
389 pd[cnt].pos.y = pov->oct.mins[OCT_Y];
390
391 cnt++;
392 pd[cnt].pos.x = pov->oct.mins[OCT_X];
393 pd[cnt].pos.y = -pov->oct.mins[OCT_X] + pov->oct.mins[OCT_XY];
394
395 cnt++;
396 pd[cnt].pos.x = pov->oct.mins[OCT_X];
397 pd[cnt].pos.y = pov->oct.mins[OCT_X] + pov->oct.maxs[OCT_YX];
398
399 cnt++;
400 pd[cnt].pos.x = pov->oct.maxs[OCT_Y] - pov->oct.maxs[OCT_YX];
401 pd[cnt].pos.y = pov->oct.maxs[OCT_Y];
402
403 cnt++;
404 pd[cnt].pos.x = -pov->oct.maxs[OCT_Y] + pov->oct.maxs[OCT_XY];
405 pd[cnt].pos.y = pov->oct.maxs[OCT_Y];
406
407 cnt++;
408 pd[cnt].pos.x = pov->oct.maxs[OCT_X];
409 pd[cnt].pos.y = -pov->oct.maxs[OCT_X] + pov->oct.maxs[OCT_XY];
410
411 // which points are outside both volumes
412 fvec3_self_clear( center.v );
413 count = 0;
414 for ( cnt = 0; cnt < 16; cnt++ )
415 {
416 float ftmp;
417
418 pd[cnt].inside = bfalse;
419
420 // check the box
421 if ( pd[cnt].pos.x < pov->oct.mins[OCT_X] || pd[cnt].pos.x > pov->oct.maxs[OCT_X] ) continue;
422 if ( pd[cnt].pos.y < pov->oct.mins[OCT_Y] || pd[cnt].pos.y > pov->oct.maxs[OCT_Y] ) continue;
423
424 // check the diamond
425 ftmp = pd[cnt].pos.x + pd[cnt].pos.y;
426 if ( ftmp < pov->oct.mins[OCT_XY] || ftmp > pov->oct.maxs[OCT_XY] ) continue;
427
428 ftmp = -pd[cnt].pos.x + pd[cnt].pos.y;
429 if ( ftmp < pov->oct.mins[OCT_YX] || ftmp > pov->oct.maxs[OCT_YX] ) continue;
430
431 // found a point
432 center.x += pd[cnt].pos.x;
433 center.y += pd[cnt].pos.y;
434 count++;
435 pd[cnt].inside = btrue;
436 };
437
438 if ( count < 3 ) return bfalse;
439
440 // find the centroid
441 center.x *= 1.0f / ( float )count;
442 center.y *= 1.0f / ( float )count;
443 center.z *= 1.0f / ( float )count;
444
445 // move the valid points to the beginning of the list
446 for ( cnt = 0, tnc = 0; cnt < 16 && tnc < count; cnt++ )
447 {
448 if ( !pd[cnt].inside ) continue;
449
450 // insert a valid point into the next available slot
451 if ( tnc != cnt )
452 {
453 pd[tnc] = pd[cnt];
454 }
455
456 // record the Cartesian rotation angle relative to center
457 pd[tnc].rads = ATAN2( pd[cnt].pos.y - center.y, pd[cnt].pos.x - center.x );
458 tnc++;
459 }
460
461 // use qsort to order the points according to their rotation angle
462 // relative to the centroid
463 qsort(( void * )pd, count, sizeof( cv_point_data_t ), cv_point_data_cmp );
464
465 // now we can use geometry to find the area of the planar collision area
466 fvec3_self_clear( centroid.v );
467 {
468 fvec3_t diff1, diff2;
469 oct_vec_t opd;
470
471 oct_vec_ctor( opd, pd[0].pos.v );
472 oct_bb_set_ovec( &( pov->oct ), opd );
473
474 area = 0;
475 for ( cnt = 1; cnt < count - 1; cnt++ )
476 {
477 tnc = cnt + 1;
478
479 // optimize the bounding volume
480 oct_vec_ctor( opd, pd[tnc].pos.v );
481 oct_bb_self_sum_ovec( &( pov->oct ), opd );
482
483 // determine the area for this element
484 diff1.x = pd[cnt].pos.x - center.x;
485 diff1.y = pd[cnt].pos.y - center.y;
486
487 diff2.x = pd[tnc].pos.x - pd[cnt].pos.x;
488 diff2.y = pd[tnc].pos.y - pd[cnt].pos.y;
489
490 darea = diff1.x * diff2.y - diff1.y * diff2.x;
491
492 // estimate the centroid
493 area += darea;
494 centroid.x += ( pd[cnt].pos.x + pd[tnc].pos.x + center.x ) / 3.0f * darea;
495 centroid.y += ( pd[cnt].pos.y + pd[tnc].pos.y + center.y ) / 3.0f * darea;
496 }
497
498 diff1.x = pd[cnt].pos.x - center.x;
499 diff1.y = pd[cnt].pos.y - center.y;
500
501 diff2.x = pd[1].pos.x - pd[cnt].pos.x;
502 diff2.y = pd[1].pos.y - pd[cnt].pos.y;
503
504 darea = diff1.x * diff2.y - diff1.y * diff2.x;
505
506 area += darea;
507 centroid.x += ( pd[cnt].pos.x + pd[1].pos.x + center.x ) / 3.0f * darea;
508 centroid.y += ( pd[cnt].pos.y + pd[1].pos.y + center.y ) / 3.0f * darea;
509 }
510
511 // is the volume valid?
512 invalid = bfalse;
513 if ( pov->oct.mins[OCT_X] >= pov->oct.maxs[OCT_X] ) invalid = btrue;
514 else if ( pov->oct.mins[OCT_Y] >= pov->oct.maxs[OCT_Y] ) invalid = btrue;
515 else if ( pov->oct.mins[OCT_Z] >= pov->oct.maxs[OCT_Z] ) invalid = btrue;
516 else if ( pov->oct.mins[OCT_XY] >= pov->oct.maxs[OCT_XY] ) invalid = btrue;
517 else if ( pov->oct.mins[OCT_YX] >= pov->oct.maxs[OCT_YX] ) invalid = btrue;
518
519 if ( invalid )
520 {
521 pov->lod = -1;
522 if ( NULL != pvolume )( *pvolume ) = 0;
523 return bfalse;
524 }
525
526 // determine the volume center
527 if ( NULL != pcenter && ABS( area ) > 0 )
528 {
529 ( *pcenter ).x = centroid.x / area;
530 ( *pcenter ).y = centroid.y / area;
531 ( *pcenter ).z = ( pov->oct.maxs[OCT_Z] + pov->oct.mins[OCT_Z] ) * 0.5f;
532 }
533
534 // determine the volume
535 volume = ABS( area ) * ( pov->oct.maxs[OCT_Z] - pov->oct.mins[OCT_Z] );
536 if ( NULL != pvolume )
537 {
538 ( *pvolume ) = volume;
539 };
540
541 return volume > 0.0f;
542 }
543
544 //--------------------------------------------------------------------------------------------
545 //--------------------------------------------------------------------------------------------
CVolume_ctor(CVolume_t * pcv,const OVolume_t * pva,const OVolume_t * pvb)546 bool_t CVolume_ctor( CVolume_t * pcv, const OVolume_t * pva, const OVolume_t * pvb )
547 {
548 bool_t retval;
549 CVolume_t cv;
550
551 if ( pva->lod < 0 || pvb->lod < 0 ) return bfalse;
552
553 //---- do the preliminary collision test ----
554
555 cv.ov = OVolume_intersect( pva, pvb );
556 if ( cv.ov.lod < 0 )
557 {
558 return bfalse;
559 };
560
561 //---- refine the collision volume ----
562
563 cv.ov.lod = MIN( pva->lod, pvb->lod );
564 retval = CVolume_refine( &cv );
565
566 if ( NULL != pcv )
567 {
568 *pcv = cv;
569 }
570
571 return retval;
572 }
573
574 //--------------------------------------------------------------------------------------------
CVolume_refine(CVolume_t * pcv)575 bool_t CVolume_refine( CVolume_t * pcv )
576 {
577 /// @details BB@> determine which of the 16 possible intersection points are within both
578 // square and diamond bounding volumes
579
580 if ( NULL == pcv ) return bfalse;
581
582 if ( pcv->ov.oct.maxs[OCT_Z] <= pcv->ov.oct.mins[OCT_Z] )
583 {
584 pcv->ov.lod = -1;
585 pcv->volume = 0;
586 return bfalse;
587 }
588
589 return OVolume_refine( &( pcv->ov ), &( pcv->center ), &( pcv->volume ) );
590 }
591
592 //--------------------------------------------------------------------------------------------
593 //--------------------------------------------------------------------------------------------
cv_point_data_cmp(const void * pleft,const void * pright)594 static int cv_point_data_cmp( const void * pleft, const void * pright )
595 {
596 int rv = 0;
597
598 cv_point_data_t * pcv_left = ( cv_point_data_t * )pleft;
599 cv_point_data_t * pcv_right = ( cv_point_data_t * )pright;
600
601 if ( pcv_left->rads < pcv_right->rads ) rv = -1;
602 else if ( pcv_left->rads > pcv_right->rads ) rv = 1;
603
604 return rv;
605 }
606
607 //--------------------------------------------------------------------------------------------
608 //--------------------------------------------------------------------------------------------
oct_bb_to_points(const oct_bb_t * pbmp,fvec4_t pos[],size_t pos_count)609 int oct_bb_to_points( const oct_bb_t * pbmp, fvec4_t pos[], size_t pos_count )
610 {
611 /// @details BB@> convert the corners of the level 1 bounding box to a point cloud
612 /// set pos[].w to zero for now, that the transform does not
613 /// shift the points while transforming them
614 ///
615 /// @note Make sure to set pos[].w to zero so that the bounding box will not be translated
616 /// then the transformation matrix is applied.
617 ///
618 /// @note The math for finding the corners of this bumper is not hard, but it is easy to make a mistake.
619 /// be careful if you modify anything.
620
621 float ftmp;
622 float val_x, val_y;
623
624 int vcount = 0;
625
626 if ( NULL == pbmp || NULL == pos || 0 == pos_count ) return 0;
627
628 //---- the points along the y_max edge
629 ftmp = 0.5f * ( pbmp->maxs[OCT_XY] + pbmp->maxs[OCT_YX] ); // the top point of the diamond
630 if ( ftmp <= pbmp->maxs[OCT_Y] )
631 {
632 val_x = 0.5f * ( pbmp->maxs[OCT_XY] - pbmp->maxs[OCT_YX] );
633 val_y = ftmp;
634
635 pos[vcount].x = val_x;
636 pos[vcount].y = val_y;
637 pos[vcount].z = pbmp->maxs[OCT_Z];
638 pos[vcount].w = 0.0f;
639 vcount++;
640
641 pos[vcount].x = val_x;
642 pos[vcount].y = val_y;
643 pos[vcount].z = pbmp->mins[OCT_Z];
644 pos[vcount].w = 0.0f;
645 vcount++;
646 }
647 else
648 {
649 val_y = pbmp->maxs[OCT_Y];
650
651 val_x = pbmp->maxs[OCT_Y] - pbmp->maxs[OCT_YX];
652 if ( val_x < pbmp->mins[OCT_X] )
653 {
654 val_x = pbmp->mins[OCT_X];
655 }
656
657 pos[vcount].x = val_x;
658 pos[vcount].y = val_y;
659 pos[vcount].z = pbmp->maxs[OCT_Z];
660 pos[vcount].w = 0.0f;
661 vcount++;
662
663 pos[vcount].x = val_x;
664 pos[vcount].y = val_y;
665 pos[vcount].z = pbmp->mins[OCT_Z];
666 pos[vcount].w = 0.0f;
667 vcount++;
668
669 val_x = pbmp->maxs[OCT_XY] - pbmp->maxs[OCT_Y];
670 if ( val_x > pbmp->maxs[OCT_X] )
671 {
672 val_x = pbmp->maxs[OCT_X];
673 }
674
675 pos[vcount].x = val_x;
676 pos[vcount].y = val_y;
677 pos[vcount].z = pbmp->maxs[OCT_Z];
678 pos[vcount].w = 0.0f;
679 vcount++;
680
681 pos[vcount].x = val_x;
682 pos[vcount].y = val_y;
683 pos[vcount].z = pbmp->mins[OCT_Z];
684 pos[vcount].w = 0.0f;
685 vcount++;
686 }
687
688 //---- the points along the y_min edge
689 ftmp = 0.5f * ( pbmp->mins[OCT_XY] + pbmp->mins[OCT_YX] ); // the top point of the diamond
690 if ( ftmp >= pbmp->mins[OCT_Y] )
691 {
692 val_x = 0.5f * ( pbmp->mins[OCT_XY] - pbmp->mins[OCT_YX] );
693 val_y = ftmp;
694
695 pos[vcount].x = val_x;
696 pos[vcount].y = val_y;
697 pos[vcount].z = pbmp->maxs[OCT_Z];
698 pos[vcount].w = 0.0f;
699 vcount++;
700
701 pos[vcount].x = val_x;
702 pos[vcount].y = val_y;
703 pos[vcount].z = pbmp->mins[OCT_Z];
704 pos[vcount].w = 0.0f;
705 vcount++;
706 }
707 else
708 {
709 val_y = pbmp->mins[OCT_Y];
710
711 val_x = pbmp->mins[OCT_XY] - pbmp->mins[OCT_Y];
712 if ( val_x < pbmp->mins[OCT_X] )
713 {
714 val_x = pbmp->mins[OCT_X];
715 }
716
717 pos[vcount].x = val_x;
718 pos[vcount].y = val_y;
719 pos[vcount].z = pbmp->maxs[OCT_Z];
720 pos[vcount].w = 0.0f;
721 vcount++;
722
723 pos[vcount].x = val_x;
724 pos[vcount].y = val_y;
725 pos[vcount].z = pbmp->mins[OCT_Z];
726 pos[vcount].w = 0.0f;
727 vcount++;
728
729 val_x = pbmp->mins[OCT_Y] - pbmp->mins[OCT_YX];
730 if ( val_x > pbmp->maxs[OCT_X] )
731 {
732 val_x = pbmp->maxs[OCT_X];
733 }
734 pos[vcount].x = val_x;
735 pos[vcount].y = val_y;
736 pos[vcount].z = pbmp->maxs[OCT_Z];
737 pos[vcount].w = 0.0f;
738 vcount++;
739
740 pos[vcount].x = val_x;
741 pos[vcount].y = val_y;
742 pos[vcount].z = pbmp->mins[OCT_Z];
743 pos[vcount].w = 0.0f;
744 vcount++;
745 }
746
747 //---- the points along the x_max edge
748 ftmp = 0.5f * ( pbmp->maxs[OCT_XY] - pbmp->mins[OCT_YX] ); // the top point of the diamond
749 if ( ftmp <= pbmp->maxs[OCT_X] )
750 {
751 val_y = 0.5f * ( pbmp->maxs[OCT_XY] + pbmp->mins[OCT_YX] );
752 val_x = ftmp;
753
754 pos[vcount].x = val_x;
755 pos[vcount].y = val_y;
756 pos[vcount].z = pbmp->maxs[OCT_Z];
757 pos[vcount].w = 0.0f;
758 vcount++;
759
760 pos[vcount].x = val_x;
761 pos[vcount].y = val_y;
762 pos[vcount].z = pbmp->mins[OCT_Z];
763 pos[vcount].w = 0.0f;
764 vcount++;
765 }
766 else
767 {
768 val_x = pbmp->maxs[OCT_X];
769
770 val_y = pbmp->maxs[OCT_X] + pbmp->mins[OCT_YX];
771 if ( val_y < pbmp->mins[OCT_Y] )
772 {
773 val_y = pbmp->mins[OCT_Y];
774 }
775
776 pos[vcount].x = val_x;
777 pos[vcount].y = val_y;
778 pos[vcount].z = pbmp->maxs[OCT_Z];
779 pos[vcount].w = 0.0f;
780 vcount++;
781
782 pos[vcount].x = val_x;
783 pos[vcount].y = val_y;
784 pos[vcount].z = pbmp->mins[OCT_Z];
785 pos[vcount].w = 0.0f;
786 vcount++;
787
788 val_y = pbmp->maxs[OCT_XY] - pbmp->maxs[OCT_X];
789 if ( val_y > pbmp->maxs[OCT_Y] )
790 {
791 val_y = pbmp->maxs[OCT_Y];
792 }
793 pos[vcount].x = val_x;
794 pos[vcount].y = val_y;
795 pos[vcount].z = pbmp->maxs[OCT_Z];
796 pos[vcount].w = 0.0f;
797 vcount++;
798
799 pos[vcount].x = val_x;
800 pos[vcount].y = val_y;
801 pos[vcount].z = pbmp->mins[OCT_Z];
802 pos[vcount].w = 0.0f;
803 vcount++;
804 }
805
806 //---- the points along the x_min edge
807 ftmp = 0.5f * ( pbmp->mins[OCT_XY] - pbmp->maxs[OCT_YX] ); // the left point of the diamond
808 if ( ftmp >= pbmp->mins[OCT_X] )
809 {
810 val_y = 0.5f * ( pbmp->mins[OCT_XY] + pbmp->maxs[OCT_YX] );
811 val_x = ftmp;
812
813 pos[vcount].x = val_x;
814 pos[vcount].y = val_y;
815 pos[vcount].z = pbmp->maxs[OCT_Z];
816 pos[vcount].w = 0.0f;
817 vcount++;
818
819 pos[vcount].x = val_x;
820 pos[vcount].y = val_y;
821 pos[vcount].z = pbmp->mins[OCT_Z];
822 pos[vcount].w = 0.0f;
823 vcount++;
824 }
825 else
826 {
827 val_x = pbmp->mins[OCT_X];
828
829 val_y = pbmp->mins[OCT_XY] - pbmp->mins[OCT_X];
830 if ( val_y < pbmp->mins[OCT_Y] )
831 {
832 val_y = pbmp->mins[OCT_Y];
833 }
834
835 pos[vcount].x = val_x;
836 pos[vcount].y = val_y;
837 pos[vcount].z = pbmp->maxs[OCT_Z];
838 pos[vcount].w = 0.0f;
839 vcount++;
840
841 pos[vcount].x = val_x;
842 pos[vcount].y = val_y;
843 pos[vcount].z = pbmp->mins[OCT_Z];
844 pos[vcount].w = 0.0f;
845 vcount++;
846
847 val_y = pbmp->maxs[OCT_YX] + pbmp->mins[OCT_X];
848 if ( val_y > pbmp->maxs[OCT_Y] )
849 {
850 val_y = pbmp->maxs[OCT_Y];
851 }
852
853 pos[vcount].x = val_x;
854 pos[vcount].y = val_y;
855 pos[vcount].z = pbmp->maxs[OCT_Z];
856 pos[vcount].w = 0.0f;
857 vcount++;
858
859 pos[vcount].x = val_x;
860 pos[vcount].y = val_y;
861 pos[vcount].z = pbmp->mins[OCT_Z];
862 pos[vcount].w = 0.0f;
863 vcount++;
864 }
865
866 return vcount;
867 }
868
869 //--------------------------------------------------------------------------------------------
points_to_oct_bb(oct_bb_t * pbmp,const fvec4_t pos[],const size_t pos_count)870 void points_to_oct_bb( oct_bb_t * pbmp, const fvec4_t pos[], const size_t pos_count )
871 {
872 /// @details BB@> convert the new point cloud into a level 1 bounding box using a fvec4_t
873 /// array as the source
874
875 Uint32 cnt, tnc;
876 oct_vec_t otmp;
877 oct_vec_base_t pmins, pmaxs;
878
879 if ( NULL == pbmp || NULL == pos || 0 == pos_count ) return;
880
881 // resolve the pointers
882 pmins = pbmp->mins;
883 pmaxs = pbmp->maxs;
884
885 // initialize using the first point
886 oct_vec_ctor( otmp, pos[0].v );
887 for ( cnt = 0; cnt < OCT_COUNT; cnt++ )
888 {
889 pmins[cnt] = pmaxs[cnt] = otmp[cnt];
890 }
891
892 // cycle through all other points
893 for ( cnt = 1; cnt < pos_count; cnt++ )
894 {
895 oct_vec_ctor( otmp, pos[cnt].v );
896
897 for ( tnc = 0; tnc < OCT_COUNT; tnc++ )
898 {
899 pmins[tnc] = MIN( pmins[tnc], otmp[tnc] );
900 pmaxs[tnc] = MAX( pmaxs[tnc], otmp[tnc] );
901 }
902 }
903
904 oct_bb_validate( pbmp );
905 }
906
907 //--------------------------------------------------------------------------------------------
908 //--------------------------------------------------------------------------------------------
oct_bb_downgrade(const oct_bb_t * psrc_bb,const bumper_t bump_stt,const bumper_t bump_base,bumper_t * pdst_bump,oct_bb_t * pdst_bb)909 egoboo_rv oct_bb_downgrade( const oct_bb_t * psrc_bb, const bumper_t bump_stt, const bumper_t bump_base, bumper_t * pdst_bump, oct_bb_t * pdst_bb )
910 {
911 /// @details BB@> convert a level 1 bumper to an "equivalent" level 0 bumper
912
913 float val1, val2, val3, val4;
914
915 // return if there is no source
916 if ( NULL == psrc_bb ) return rv_error;
917
918 //---- handle all of the pdst_bump data first
919 if ( NULL != pdst_bump )
920 {
921 if ( 0.0f == bump_stt.height )
922 {
923 pdst_bump->height = 0.0f;
924 }
925 else
926 {
927 // have to use MAX here because the height can be distorted due
928 // to make object-particle interactions easier (i.e. it allows you to
929 // hit a grub bug with your hands)
930
931 pdst_bump->height = MAX( bump_base.height, psrc_bb->maxs[OCT_Z] );
932 }
933
934 if ( 0.0f == bump_stt.size )
935 {
936 pdst_bump->size = 0.0f;
937 }
938 else
939 {
940 val1 = ABS( psrc_bb->mins[OCT_X] );
941 val2 = ABS( psrc_bb->maxs[OCT_Y] );
942 val3 = ABS( psrc_bb->mins[OCT_Y] );
943 val4 = ABS( psrc_bb->maxs[OCT_Y] );
944 pdst_bump->size = MAX( MAX( val1, val2 ), MAX( val3, val4 ) );
945 }
946
947 if ( 0.0f == bump_stt.size_big )
948 {
949 pdst_bump->size_big = 0;
950 }
951 else
952 {
953 val1 = ABS( psrc_bb->maxs[OCT_YX] );
954 val2 = ABS( psrc_bb->mins[OCT_YX] );
955 val3 = ABS( psrc_bb->maxs[OCT_XY] );
956 val4 = ABS( psrc_bb->mins[OCT_XY] );
957 pdst_bump->size_big = MAX( MAX( val1, val2 ), MAX( val3, val4 ) );
958 }
959 }
960
961 //---- handle all of the pdst_bb data second
962 if ( NULL != pdst_bb )
963 {
964 // memcpy() can fail horribly if the domains overlap, so use memmove()
965 if ( pdst_bb != psrc_bb )
966 {
967 memmove( pdst_bb, psrc_bb, sizeof( *pdst_bb ) );
968 }
969
970 if ( 0.0f == bump_stt.height )
971 {
972 pdst_bb->mins[OCT_Z] = pdst_bb->maxs[OCT_Z] = 0.0f;
973 }
974 else
975 {
976 // handle the vertical distortion the same as above
977 pdst_bb->maxs[OCT_Z] = MAX( bump_base.height, psrc_bb->maxs[OCT_Z] );
978 }
979
980 // 0.0f == bump_stt.size is supposed to be shorthand for "this object doesn't interact
981 // with anything", so we have to set all of the horizontal pdst_bb data to zero
982 if ( 0.0f == bump_stt.size )
983 {
984 pdst_bb->mins[OCT_X ] = pdst_bb->maxs[OCT_X ] = 0.0f;
985 pdst_bb->mins[OCT_Y ] = pdst_bb->maxs[OCT_Y ] = 0.0f;
986 pdst_bb->mins[OCT_XY] = pdst_bb->maxs[OCT_XY] = 0.0f;
987 pdst_bb->mins[OCT_YX] = pdst_bb->maxs[OCT_YX] = 0.0f;
988 }
989 }
990
991 oct_bb_validate( pdst_bb );
992
993 return rv_success;
994 }
995
996 //--------------------------------------------------------------------------------------------
oct_bb_interpolate(const oct_bb_t * psrc1,const oct_bb_t * psrc2,oct_bb_t * pdst,float flip)997 egoboo_rv oct_bb_interpolate( const oct_bb_t * psrc1, const oct_bb_t * psrc2, oct_bb_t * pdst, float flip )
998 {
999 int cnt;
1000
1001 bool_t src1_empty, src2_empty;
1002 if ( NULL == pdst ) return rv_error;
1003
1004 src1_empty = ( NULL == psrc1 || psrc1->empty );
1005 src2_empty = ( NULL == psrc2 || psrc2->empty );
1006
1007 if ( src1_empty && src2_empty )
1008 {
1009 oct_bb_ctor( pdst );
1010 return rv_fail;
1011 }
1012 else if ( !src1_empty && 0.0f == flip )
1013 {
1014 return oct_bb_copy( pdst, psrc1 );
1015 }
1016 else if ( !src2_empty && 1.0f == flip )
1017 {
1018 return oct_bb_copy( pdst, psrc2 );
1019 }
1020 else if ( src1_empty || src2_empty )
1021 {
1022 oct_bb_ctor( pdst );
1023 return rv_fail;
1024 }
1025
1026 for ( cnt = 0; cnt < OCT_COUNT; cnt++ )
1027 {
1028 pdst->mins[cnt] = psrc1->mins[cnt] + ( psrc2->mins[cnt] - psrc1->mins[cnt] ) * flip;
1029 pdst->maxs[cnt] = psrc1->maxs[cnt] + ( psrc2->maxs[cnt] - psrc1->maxs[cnt] ) * flip;
1030 }
1031
1032 return oct_bb_validate( pdst );
1033 }
1034
1035