1 #include "bbox_tree.h"
2 #include "draw_scene.h"
3 #include "lights.h"
4 #ifdef EXTRA_DEBUG
5 #include "errors.h"
6 #endif
7
8 #ifdef OSX
9 #include <sys/malloc.h>
10 #else
11 #ifndef BSD
12 #ifndef alloca // newer versions of SDL have their own alloca!
13 #include <malloc.h>
14 #endif //alloca
15 #endif //BSD
16 #endif //OSX
17
18 #ifdef CLUSTER_INSIDES
19 #include "cluster.h"
20 #endif // CLUSTER_INSIDES
21
22 BBOX_TREE* main_bbox_tree = NULL;
23 BBOX_ITEMS* main_bbox_tree_items = NULL;
24
25 #ifdef EXTRA_DEBUG
26 #define BBOX_TREE_LOG_INFO(item) { log_debug_verbose(__FILE__, __LINE__, item); }
27 #else //DEBUG
28 #define BBOX_TREE_LOG_INFO(item) { /*!< NOP */ }
29 #endif //DEBUG
30
31 #define NO_INDEX 0xFFFFFFFF
32
is_extra_first_sub_node(Uint32 extra)33 static __inline__ Uint32 is_extra_first_sub_node(Uint32 extra)
34 {
35 return ((extra & EXTRA_FIRST_SUB_NODE) != 0);
36 }
37
set_all_intersect_update_needed(BBOX_TREE * bbox_tree)38 void set_all_intersect_update_needed(BBOX_TREE* bbox_tree)
39 {
40 Uint32 i;
41
42 if (bbox_tree != NULL)
43 {
44 for (i = 0; i < MAX_INTERSECTION_TYPES; i++)
45 bbox_tree->intersect[i].intersect_update_needed = 1;
46 }
47 else BBOX_TREE_LOG_INFO("bbox_tree");
48 }
49
adapt_intersect_list_size(BBOX_TREE * bbox_tree,Uint32 count)50 static __inline__ void adapt_intersect_list_size(BBOX_TREE* bbox_tree, Uint32 count)
51 {
52 Uint32 size, idx;
53
54 if (count == 0) count = 1;
55 idx = bbox_tree->cur_intersect_type;
56 size = bbox_tree->intersect[idx].size;
57
58 if ((bbox_tree->intersect[idx].count+count) >= size)
59 {
60 size += max2i(count, size/2);
61 bbox_tree->intersect[idx].items = (BBOX_ITEM*)realloc(bbox_tree->intersect[idx].items, size*sizeof(BBOX_ITEM));
62 bbox_tree->intersect[idx].size = size;
63 }
64 }
65
add_intersect_item_to_list(BBOX_TREE * bbox_tree,BBOX_ITEM * item,Uint32 idx)66 static __inline__ void add_intersect_item_to_list(BBOX_TREE* bbox_tree, BBOX_ITEM* item, Uint32 idx)
67 {
68 #ifdef CLUSTER_INSIDES
69 if (item->cluster && item->cluster != current_cluster) return;
70 #endif // CLUSTER_INSIDES
71 adapt_intersect_list_size(bbox_tree, 1);
72 memcpy(&bbox_tree->intersect[idx].items[bbox_tree->intersect[idx].count], item, sizeof(BBOX_ITEM));
73 bbox_tree->intersect[idx].count++;
74 }
75
add_intersect_item(BBOX_TREE * bbox_tree,Uint32 index,Uint32 idx)76 static __inline__ void add_intersect_item(BBOX_TREE* bbox_tree, Uint32 index, Uint32 idx)
77 {
78 add_intersect_item_to_list(bbox_tree, &bbox_tree->items[index], idx);
79 }
80
add_intersect_items(BBOX_TREE * bbox_tree,Uint32 index,Uint32 count)81 static __inline__ void add_intersect_items(BBOX_TREE* bbox_tree, Uint32 index, Uint32 count)
82 {
83 Uint32 i;
84
85 adapt_intersect_list_size(bbox_tree, count);
86 for (i = 0; i < count; i++) add_intersect_item(bbox_tree, index+i, bbox_tree->cur_intersect_type);
87 }
88
add_dyn_intersect_item(BBOX_TREE * bbox_tree,Uint32 node,Uint32 index,Uint32 idx)89 static __inline__ void add_dyn_intersect_item(BBOX_TREE* bbox_tree, Uint32 node, Uint32 index, Uint32 idx)
90 {
91 add_intersect_item_to_list(bbox_tree, &bbox_tree->nodes[node].dynamic_objects.items[index], idx);
92 }
93
add_dyn_intersect_items(BBOX_TREE * bbox_tree,Uint32 node,Uint32 count)94 static __inline__ void add_dyn_intersect_items(BBOX_TREE* bbox_tree, Uint32 node, Uint32 count)
95 {
96 Uint32 i;
97
98 adapt_intersect_list_size(bbox_tree, count);
99 for (i = 0; i < count; i++) add_dyn_intersect_item(bbox_tree, node, i, bbox_tree->cur_intersect_type);
100 }
101
check_aabb_in_frustum(const AABBOX bbox,const FRUSTUM frustum,Uint32 in_mask,Uint32 * out_mask)102 static __inline__ int check_aabb_in_frustum(const AABBOX bbox, const FRUSTUM frustum, Uint32 in_mask, Uint32 *out_mask)
103 {
104 VECTOR4 n, p;
105 VECTOR3 _n, _p;
106 float v;
107 Uint32 i, k, result;
108
109 result = INSIDE;
110 *out_mask = 0;
111
112 for (i = 0, k = 1; k <= in_mask; i++, k += k)
113 {
114 if (k & in_mask)
115 {
116 VInvertSelect(_n, bbox.bbmin, bbox.bbmax, frustum[i].mask);
117 VAssign4(n, _n, 1.0f);
118 v = VDot4(n, frustum[i].plane);
119 if (v < 0.0f)
120 {
121 return OUTSIDE;
122 }
123
124 VSelect(_p, bbox.bbmin, bbox.bbmax, frustum[i].mask);
125 VAssign4(p, _p, 1.0f);
126 v = VDot4(p, frustum[i].plane);
127 if (v < 0.0f)
128 {
129 *out_mask |= k;
130 result = INTERSECT;
131 }
132 }
133 }
134
135 return result;
136 }
137
check_aabb_in_frustum_no_out_mask(const AABBOX bbox,const FRUSTUM frustum,Uint32 in_mask)138 static __inline__ int check_aabb_in_frustum_no_out_mask(const AABBOX bbox, const FRUSTUM frustum, Uint32 in_mask)
139 {
140 VECTOR4 n, p;
141 VECTOR3 _n, _p;
142 float v;
143 Uint32 i, k;
144
145 for (i = 0, k = 1; k <= in_mask; i++, k += k)
146 {
147 if (k & in_mask)
148 {
149 VInvertSelect(_n, bbox.bbmin, bbox.bbmax, frustum[i].mask);
150 VAssign4(n, _n, 1.0f);
151 v = VDot4(n, frustum[i].plane);
152 if (v < 0.0f)
153 {
154 return OUTSIDE;
155 }
156
157 VSelect(_p, bbox.bbmin, bbox.bbmax, frustum[i].mask);
158 VAssign4(p, _p, 1.0f);
159 v = VDot4(p, frustum[i].plane);
160 if (v < 0.0f)
161 {
162 return INTERSECT;
163 }
164 }
165 }
166
167 return INSIDE;
168 }
169
check_aabb_outside_frustum(const AABBOX bbox,const FRUSTUM frustum,Uint32 in_mask)170 static __inline__ int check_aabb_outside_frustum(const AABBOX bbox, const FRUSTUM frustum, Uint32 in_mask)
171 {
172 VECTOR4 n;
173 VECTOR3 _n;
174 float v;
175 Uint32 i, k;
176
177 for (i = 0, k = 1; k <= in_mask; i++, k += k)
178 {
179 if (k & in_mask)
180 {
181 VInvertSelect(_n, bbox.bbmin, bbox.bbmax, frustum[i].mask);
182 VAssign4(n, _n, 1.0f);
183 v = VDot4(n, frustum[i].plane);
184 if (v < 0.0f)
185 {
186 return OUTSIDE;
187 }
188 }
189 }
190
191 return INTERSECT;
192 }
193
check_aabb_inside_portals(const AABBOX bbox,const PLANE * portals,Uint32 count)194 static __inline__ int check_aabb_inside_portals(const AABBOX bbox, const PLANE* portals, Uint32 count)
195 {
196 VECTOR4 n;
197 VECTOR3 _n;
198 float v;
199 Uint32 i, j, ret;
200
201 for (i = 0; i < count; i++)
202 {
203 ret = 1;
204 for (j = 0; j < 4; j++)
205 {
206 VInvertSelect(_n, bbox.bbmin, bbox.bbmax, portals[i * 4 + j].mask);
207 VAssign4(n, _n, 1.0f);
208 v = VDot4(n, portals[i * 4 + j].plane);
209 if (v < 0.0f)
210 {
211 ret = 0;
212 break;
213 }
214 }
215 if (ret == 1)
216 {
217 return 1;
218 }
219 }
220
221 return 0;
222 }
223
add_items(BBOX_TREE * bbox_tree,Uint32 sub_node,Uint32 in_mask)224 static __inline__ void add_items(BBOX_TREE* bbox_tree, Uint32 sub_node, Uint32 in_mask)
225 {
226 Uint32 idx1, idx2, size, i;
227
228 idx1 = bbox_tree->cur_intersect_type;
229 idx2 = bbox_tree->nodes[sub_node].items_index;
230 size = bbox_tree->nodes[sub_node].items_count;
231
232 for (i = 0; i < size; i++)
233 {
234 if (check_aabb_outside_frustum(bbox_tree->items[idx2+i].bbox, bbox_tree->intersect[idx1].frustum, in_mask) != OUTSIDE)
235 add_intersect_item(bbox_tree, idx2+i, idx1);
236 }
237 }
238
add_dyn_items(BBOX_TREE * bbox_tree,Uint32 sub_node,Uint32 in_mask)239 static __inline__ void add_dyn_items(BBOX_TREE* bbox_tree, Uint32 sub_node, Uint32 in_mask)
240 {
241 Uint32 idx, size, i;
242
243 idx = bbox_tree->cur_intersect_type;
244 size = bbox_tree->nodes[sub_node].dynamic_objects.index;
245
246 for (i = 0; i < size; i++)
247 {
248 if (check_aabb_outside_frustum(bbox_tree->nodes[sub_node].dynamic_objects.items[i].bbox, bbox_tree->intersect[idx].frustum, in_mask) != OUTSIDE)
249 add_dyn_intersect_item(bbox_tree, sub_node, i, idx);
250 }
251 }
252
merge_items(BBOX_TREE * bbox_tree,Uint32 sub_node,Uint32 in_mask,AABBOX * bbox)253 static __inline__ void merge_items(BBOX_TREE* bbox_tree, Uint32 sub_node, Uint32 in_mask, AABBOX* bbox)
254 {
255 Uint32 idx1, idx2, size, i;
256
257 idx1 = bbox_tree->cur_intersect_type;
258 idx2 = bbox_tree->nodes[sub_node].items_index;
259 size = bbox_tree->nodes[sub_node].items_count;
260
261 for (i = 0; i < size; i++)
262 {
263 if (check_aabb_outside_frustum(bbox_tree->items[idx2+i].bbox, bbox_tree->intersect[idx1].frustum, in_mask) != OUTSIDE)
264 {
265 VMin(bbox->bbmin, bbox->bbmin, bbox_tree->items[idx2+i].bbox.bbmin);
266 VMax(bbox->bbmax, bbox->bbmax, bbox_tree->items[idx2+i].bbox.bbmax);
267 }
268 }
269 }
270
merge_dyn_items(BBOX_TREE * bbox_tree,Uint32 sub_node,Uint32 in_mask,AABBOX * bbox)271 static __inline__ void merge_dyn_items(BBOX_TREE* bbox_tree, Uint32 sub_node, Uint32 in_mask, AABBOX* bbox)
272 {
273 Uint32 idx, size, i;
274
275 idx = bbox_tree->cur_intersect_type;
276 size = bbox_tree->nodes[sub_node].dynamic_objects.index;
277
278 for (i = 0; i < size; i++)
279 {
280 if (check_aabb_outside_frustum(bbox_tree->nodes[sub_node].dynamic_objects.items[i].bbox,
281 bbox_tree->intersect[idx].frustum, in_mask) != OUTSIDE)
282 {
283 VMin(bbox->bbmin, bbox->bbmin, bbox_tree->nodes[sub_node].dynamic_objects.items[i].bbox.bbmin);
284 VMax(bbox->bbmax, bbox->bbmax, bbox_tree->nodes[sub_node].dynamic_objects.items[i].bbox.bbmax);
285 }
286 }
287 }
288
check_sub_nodes(BBOX_TREE * bbox_tree,Uint32 sub_node,Uint32 in_mask)289 static __inline__ void check_sub_nodes(BBOX_TREE* bbox_tree, Uint32 sub_node, Uint32 in_mask)
290 {
291 Uint32 out_mask, result, idx;
292
293 if (sub_node != NO_INDEX)
294 {
295 idx = bbox_tree->cur_intersect_type;
296 result = check_aabb_in_frustum(bbox_tree->nodes[sub_node].bbox, bbox_tree->intersect[idx].frustum, in_mask, &out_mask);
297 if (result == INSIDE)
298 {
299 add_intersect_items(bbox_tree, bbox_tree->nodes[sub_node].items_index, bbox_tree->nodes[sub_node].items_count);
300 add_dyn_intersect_items(bbox_tree, sub_node, bbox_tree->nodes[sub_node].dynamic_objects.index);
301 }
302 else
303 {
304 if (result == INTERSECT)
305 {
306 add_dyn_items(bbox_tree, sub_node, out_mask);
307 if ( (bbox_tree->nodes[sub_node].nodes[0] == NO_INDEX) &&
308 (bbox_tree->nodes[sub_node].nodes[1] == NO_INDEX)) add_items(bbox_tree, sub_node, out_mask);
309 else
310 {
311 check_sub_nodes(bbox_tree, bbox_tree->nodes[sub_node].nodes[0], out_mask);
312 check_sub_nodes(bbox_tree, bbox_tree->nodes[sub_node].nodes[1], out_mask);
313 }
314 }
315 }
316 }
317 }
318
calc_bbox_sub_nodes(BBOX_TREE * bbox_tree,Uint32 sub_node,Uint32 in_mask,AABBOX * bbox)319 static __inline__ void calc_bbox_sub_nodes(BBOX_TREE* bbox_tree, Uint32 sub_node, Uint32 in_mask, AABBOX* bbox)
320 {
321 Uint32 out_mask, result, idx;
322
323 if (sub_node != NO_INDEX)
324 {
325 idx = bbox_tree->cur_intersect_type;
326 result = check_aabb_in_frustum(bbox_tree->nodes[sub_node].bbox, bbox_tree->intersect[idx].frustum, in_mask, &out_mask);
327 if (result == INSIDE)
328 {
329 VMin(bbox->bbmin, bbox->bbmin, bbox_tree->nodes[sub_node].bbox.bbmin);
330 VMax(bbox->bbmax, bbox->bbmax, bbox_tree->nodes[sub_node].bbox.bbmax);
331 }
332 else
333 {
334 if (result == INTERSECT)
335 {
336 merge_dyn_items(bbox_tree, sub_node, out_mask, bbox);
337 if ( (bbox_tree->nodes[sub_node].nodes[0] == NO_INDEX) &&
338 (bbox_tree->nodes[sub_node].nodes[1] == NO_INDEX)) merge_items(bbox_tree, sub_node, out_mask, bbox);
339 else
340 {
341 calc_bbox_sub_nodes(bbox_tree, bbox_tree->nodes[sub_node].nodes[0], out_mask, bbox);
342 calc_bbox_sub_nodes(bbox_tree, bbox_tree->nodes[sub_node].nodes[1], out_mask, bbox);
343 }
344 }
345 }
346 }
347 }
348
light_depht_comp(BBOX_ITEM * a,BBOX_ITEM * b)349 static __inline__ int light_depht_comp(BBOX_ITEM* a, BBOX_ITEM* b)
350 {
351 Uint32 ai, bi;
352 float ax, ay, az, bx, by, bz, ad, bd;
353
354 ai = a->ID;
355 bi = b->ID;
356
357 if ((lights_list[ai] == NULL) || (lights_list[bi] == NULL)) return 0;
358
359 ax = lights_list[ai]->pos_x + camera_x;
360 ay = lights_list[ai]->pos_y + camera_y;
361 az = lights_list[ai]->pos_z;
362 bx = lights_list[bi]->pos_x + camera_x;
363 by = lights_list[bi]->pos_y + camera_y;
364 bz = lights_list[bi]->pos_z;
365 ad = ax*ax+ay*ay+az*az;
366 bd = bx*bx+by*by+bz*bz;
367
368 if (ad < bd) return -1;
369 else
370 {
371 if (ad == bd) return 0;
372 else return 1;
373 }
374 }
375
comp_items(const void * in_a,const void * in_b)376 static int comp_items(const void *in_a, const void *in_b)
377 {
378 BBOX_ITEM *a, *b;
379 Uint32 am, bm;
380
381 a = (BBOX_ITEM *)in_a;
382 b = (BBOX_ITEM *)in_b;
383
384 am = a->type;
385 bm = b->type;
386
387 if (am < bm) return -1;
388 else
389 {
390 if (am == bm)
391 {
392 if (am == TYPE_LIGHT) return light_depht_comp(a, b);
393 else
394 {
395 am = a->texture_id;
396 bm = b->texture_id;
397 if (am < bm) return -1;
398 else
399 {
400 if (am == bm)
401 {
402 return 0;
403 }
404 else
405 {
406 return 1;
407 }
408 }
409 }
410 }
411 else return 1;
412 }
413 }
414
build_start_stop(BBOX_TREE * bbox_tree)415 static __inline__ void build_start_stop(BBOX_TREE* bbox_tree)
416 {
417 Uint32 idx, i, cur_type, type;
418
419 idx = bbox_tree->cur_intersect_type;
420 memset(bbox_tree->intersect[idx].start, 0, TYPES_COUNT*sizeof(Uint32));
421 memset(bbox_tree->intersect[idx].stop, 0, TYPES_COUNT*sizeof(Uint32));
422
423 if (bbox_tree->intersect[idx].count > 0)
424 {
425 i = 0;
426 cur_type = bbox_tree->intersect[idx].items[i].type;
427 if (cur_type == TYPE_DELETED) return;
428
429 set_bbox_intersect_flag(bbox_tree, cur_type, ide_changed);
430 bbox_tree->intersect[idx].start[cur_type] = i;
431 for (i = 1; i < bbox_tree->intersect[idx].count; i++)
432 {
433 type = bbox_tree->intersect[idx].items[i].type;
434 if (type != cur_type)
435 {
436 if (type == TYPE_DELETED) break;
437 bbox_tree->intersect[idx].start[type] = i;
438 bbox_tree->intersect[idx].stop[cur_type] = i;
439 cur_type = type;
440 set_bbox_intersect_flag(bbox_tree, cur_type, ide_changed);
441 }
442 }
443 bbox_tree->intersect[idx].stop[cur_type] = i;
444 }
445 }
446
delete_item_from_intersect_list(BBOX_TREE * bbox_tree,Uint32 ID,Uint32 type_mask)447 static __inline__ void delete_item_from_intersect_list(BBOX_TREE* bbox_tree, Uint32 ID, Uint32 type_mask)
448 {
449 Uint32 i, j, k, size;
450 int start, stop;
451 Uint32 id;
452
453 for (i = 0; i < MAX_INTERSECTION_TYPES; i++)
454 {
455 for (j = 0; j < TYPES_COUNT; j++)
456 {
457 if (type_mask != get_type_mask_from_type(j)) continue;
458 start = bbox_tree->intersect[i].start[j];
459 stop = bbox_tree->intersect[i].stop[j];
460 for (k = start; k < stop; k++)
461 {
462 if ((type_mask == TYPE_MASK_3D_BLEND_SELF_LIT_OBJECT) ||
463 (type_mask == TYPE_MASK_3D_BLEND_NO_SELF_LIT_OBJECT) ||
464 (type_mask == TYPE_MASK_3D_NO_BLEND_SELF_LIT_OBJECT) ||
465 (type_mask == TYPE_MASK_3D_NO_BLEND_NO_SELF_LIT_OBJECT))
466 id = get_3dobject_index(bbox_tree->intersect[i].items[k].ID);
467 else id = bbox_tree->intersect[i].items[k].ID;
468
469 if (id == ID)
470 {
471 size = stop - k -1;
472 if (size > 0)
473 memmove(&bbox_tree->intersect[i].items[k], &bbox_tree->intersect[i].items[k+1], size*sizeof(BBOX_ITEM));
474 bbox_tree->intersect[i].stop[j]--;
475 stop--;
476 k--;
477 }
478 }
479 }
480 }
481 }
482
check_bbox_tree(BBOX_TREE * bbox_tree)483 void check_bbox_tree(BBOX_TREE* bbox_tree)
484 {
485 Uint32 idx;
486
487 if (bbox_tree != NULL)
488 {
489 idx = bbox_tree->cur_intersect_type;
490 if (bbox_tree->intersect[idx].intersect_update_needed > 0)
491 {
492 bbox_tree->intersect[idx].count = 0;
493 check_sub_nodes(bbox_tree, 0, bbox_tree->intersect[idx].frustum_mask);
494 qsort((void *)(bbox_tree->intersect[idx].items), bbox_tree->intersect[idx].count, sizeof(BBOX_ITEM), comp_items);
495 build_start_stop(bbox_tree);
496 bbox_tree->intersect[idx].intersect_update_needed = 0;
497 }
498 }
499 else BBOX_TREE_LOG_INFO("bbox_tree");
500 }
501
calc_scene_bbox(BBOX_TREE * bbox_tree,AABBOX * bbox)502 void calc_scene_bbox(BBOX_TREE* bbox_tree, AABBOX* bbox)
503 {
504 Uint32 idx;
505
506 if (bbox_tree != NULL)
507 {
508 idx = bbox_tree->cur_intersect_type;
509 VFill(bbox->bbmax, -BOUND_HUGE);
510 VFill(bbox->bbmin, BOUND_HUGE);
511 calc_bbox_sub_nodes(bbox_tree, 0, bbox_tree->intersect[idx].frustum_mask, bbox);
512 }
513 else BBOX_TREE_LOG_INFO("bbox_tree");
514 }
515
free_bbox_tree_data(BBOX_TREE * bbox_tree)516 static __inline__ void free_bbox_tree_data(BBOX_TREE* bbox_tree)
517 {
518 Uint32 i;
519
520 if (bbox_tree->items != NULL)
521 {
522 free(bbox_tree->items);
523 bbox_tree->items = NULL;
524 }
525 else BBOX_TREE_LOG_INFO("bbox_tree->items");
526
527 bbox_tree->items_count = 0;
528
529 for (i = 0; i < bbox_tree->nodes_count; i++)
530 {
531 if (bbox_tree->nodes[i].dynamic_objects.items != NULL)
532 {
533 free(bbox_tree->nodes[i].dynamic_objects.items);
534 bbox_tree->nodes[i].dynamic_objects.items = NULL;
535 }
536 }
537 if (bbox_tree->nodes != NULL)
538 {
539 free(bbox_tree->nodes);
540 bbox_tree->nodes = NULL;
541 }
542 else BBOX_TREE_LOG_INFO("bbox_tree->nodes");
543
544 bbox_tree->nodes_count = 0;
545 }
546
clear_bbox_tree(BBOX_TREE * bbox_tree)547 void clear_bbox_tree(BBOX_TREE* bbox_tree)
548 {
549 Uint32 i;
550
551 if (bbox_tree != NULL)
552 {
553 for (i = 0; i < MAX_INTERSECTION_TYPES; i++)
554 {
555 memset(bbox_tree->intersect[i].start, 0, TYPES_COUNT*sizeof(Uint32));
556 memset(bbox_tree->intersect[i].stop, 0, TYPES_COUNT*sizeof(Uint32));
557 bbox_tree->intersect[i].size = 0;
558 bbox_tree->intersect[i].count = 0;
559 bbox_tree->intersect[i].intersect_update_needed = 0;
560 if (bbox_tree->intersect[i].items != NULL)
561 {
562 free(bbox_tree->intersect[i].items);
563 bbox_tree->intersect[i].items = NULL;
564 }
565 }
566 free_bbox_tree_data(bbox_tree);
567 }
568 else BBOX_TREE_LOG_INFO("bbox_tree");
569 }
570
free_bbox_tree(BBOX_TREE * bbox_tree)571 void free_bbox_tree(BBOX_TREE* bbox_tree)
572 {
573 if (bbox_tree != NULL)
574 {
575 clear_bbox_tree(bbox_tree);
576 free(bbox_tree);
577 bbox_tree = NULL;
578 }
579 else BBOX_TREE_LOG_INFO("bbox_tree");
580 }
581
582 static int Axis = 0;
583
compboxes(const void * in_a,const void * in_b)584 static int compboxes(const void *in_a, const void *in_b)
585 {
586 const BBOX_ITEM *a = in_a, *b = in_b;
587 float am, bm;
588
589 am = a->bbox.bbmin[Axis];
590 bm = b->bbox.bbmin[Axis];
591
592 if (am < bm)
593 return -1;
594 else if (bm < am)
595 return 1;
596 else
597 return 0;
598 }
599
600 #ifdef FASTER_MAP_LOAD
build_area_table(const BBOX_TREE * bbox_tree,Uint32 a,Uint32 b,float * areas)601 static __inline__ void build_area_table(const BBOX_TREE *bbox_tree,
602 Uint32 a, Uint32 b, float *areas)
603 {
604 VECTOR3 bmin, bmax, len;
605 int i, j;
606
607 VFill(bmin, BOUND_HUGE);
608 VFill(bmax, -BOUND_HUGE);
609
610 if (a < b)
611 {
612 for (i = a, j = 0; i <= b; i++, j++)
613 {
614 VMin(bmin, bmin, bbox_tree->items[i].bbox.bbmin);
615 VMax(bmax, bmax, bbox_tree->items[i].bbox.bbmax);
616 VSub(len, bmax, bmin);
617
618 areas[j] = len[X] * len[Y] * len[Z];
619 }
620 }
621 else
622 {
623 for (i = a, j = a-b; i >= (int)b; i--, j--)
624 {
625 VMin(bmin, bmin, bbox_tree->items[i].bbox.bbmin);
626 VMax(bmax, bmax, bbox_tree->items[i].bbox.bbmax);
627 VSub(len, bmax, bmin);
628
629 areas[j] = len[X] * len[Y] * len[Z];
630 }
631 }
632 }
633
find_axis_and_bbox(const BBOX_TREE * bbox_tree,Uint32 first,Uint32 last,Uint32 * ret,AABBOX * bbox)634 static __inline__ void find_axis_and_bbox(const BBOX_TREE *bbox_tree,
635 Uint32 first, Uint32 last, Uint32 *ret, AABBOX *bbox)
636 {
637 Uint32 i, a1, a2, a3;
638 VECTOR3 bmin, bmax;
639 float d, e;
640
641 VFill(bmin, BOUND_HUGE);
642 VFill(bmax, -BOUND_HUGE);
643
644 for (i = first; i < last; i++)
645 {
646 VMin(bmin, bmin, bbox_tree->items[i].bbox.bbmin);
647 VMax(bmax, bmax, bbox_tree->items[i].bbox.bbmax);
648 }
649
650 VAssign(bbox->bbmin, bmin);
651 VAssign(bbox->bbmax, bmax);
652
653 a1 = 0;
654 a2 = 1;
655 a3 = 2;
656
657 d = bmax[a1] - bmin[a1];
658 e = bmax[a2] - bmin[a2];
659 if (d < e)
660 {
661 i = a2;
662 a2 = a1;
663 a1 = i;
664 }
665
666 d = bmax[a1] - bmin[a1];
667 e = bmax[a3] - bmin[a3];
668 if (d < e)
669 {
670 // i = a2;
671 // a2 = a1;
672 i = a3;
673 a3 = a1;
674 a1 = i;
675 }
676
677 d = bmax[a2] - bmin[a2];
678 e = bmax[a3] - bmin[a3];
679 if (d < e)
680 {
681 i = a3;
682 a3 = a2;
683 a2 = i;
684 }
685
686 ret[0] = a1;
687 ret[1] = a2;
688 ret[2] = a3;
689 }
690 #else // FASTER_MAP_LOAD
build_area_table(BBOX_TREE * bbox_tree,Uint32 a,Uint32 b,float * areas)691 static __inline__ void build_area_table(BBOX_TREE *bbox_tree, Uint32 a, Uint32 b, float *areas)
692 {
693 int i, imin, dir;
694 VECTOR3 bmin, bmax, len;
695
696 if (a < b)
697 {
698 imin = a;
699 dir = 1;
700 }
701 else
702 {
703 imin = b;
704 dir = -1;
705 }
706
707 VFill(bmin, BOUND_HUGE);
708 VFill(bmax, -BOUND_HUGE);
709
710 for (i = a; i != (b + dir); i += dir)
711 {
712 VMin(bmin, bmin, bbox_tree->items[i].bbox.bbmin);
713 VMax(bmax, bmax, bbox_tree->items[i].bbox.bbmax);
714 VSub(len, bmax, bmin);
715
716 areas[i - imin] = len[X] * len[Y] * len[Z];
717 }
718 }
719
find_axis(BBOX_TREE * bbox_tree,Uint32 first,Uint32 last,Uint32 * ret)720 static __inline__ void find_axis(BBOX_TREE *bbox_tree, Uint32 first, Uint32 last, Uint32 *ret)
721 {
722 Uint32 i, a1, a2, a3;
723 VECTOR3 bmin, bmax;
724 float d, e;
725
726 VFill(bmin, BOUND_HUGE);
727 VFill(bmax, -BOUND_HUGE);
728
729 for (i = first; i < last; i++)
730 {
731 VMin(bmin, bmin, bbox_tree->items[i].bbox.bbmin);
732 VMax(bmax, bmax, bbox_tree->items[i].bbox.bbmax);
733 }
734
735 a1 = 0;
736 a2 = 1;
737 a3 = 2;
738
739 d = bmax[a1] - bmin[a1];
740 e = bmax[a2] - bmin[a2];
741
742 if (d < e)
743 {
744 i = a2;
745 a2 = a1;
746 a1 = i;
747 }
748
749 d = bmax[a1] - bmin[a1];
750 e = bmax[a3] - bmin[a3];
751
752 if (d < e)
753 {
754 i = a2;
755 a2 = a1;
756 a1 = i;
757 }
758
759 d = bmax[a2] - bmin[a2];
760 e = bmax[a3] - bmin[a3];
761
762 if (d < e)
763 {
764 i = a3;
765 a3 = a2;
766 a2 = i;
767 }
768
769 ret[0] = a1;
770 ret[1] = a2;
771 ret[2] = a3;
772 }
773
calc_bbox(AABBOX * bbox,BBOX_TREE * bbox_tree,Uint32 first,Uint32 last)774 static __inline__ void calc_bbox(AABBOX *bbox, BBOX_TREE *bbox_tree, Uint32 first, Uint32 last)
775 {
776 int i;
777 VECTOR3 bmin, bmax;
778
779 VFill(bmin, BOUND_HUGE);
780 VFill(bmax, -BOUND_HUGE);
781
782 for (i = first; i < last; i++)
783 {
784 VMin(bmin, bmin, bbox_tree->items[i].bbox.bbmin);
785 VMax(bmax, bmax, bbox_tree->items[i].bbox.bbmax);
786 }
787
788 VAssign(bbox->bbmin, bmin);
789 VAssign(bbox->bbmax, bmax);
790 }
791 #endif // FASTER_MAP_LOAD
792
sort_and_split(BBOX_TREE * bbox_tree,Uint32 node,Uint32 * index,Uint32 first,Uint32 last)793 static __inline__ Uint32 sort_and_split(BBOX_TREE* bbox_tree, Uint32 node, Uint32* index, Uint32 first, Uint32 last)
794 {
795 Uint32 size, i, j, axis[3];
796 int best_loc;
797 float *area_left, *area_right;
798 float best_index, new_index;
799 #ifdef FASTER_MAP_LOAD
800 AABBOX bbox;
801 #endif
802
803 size = last - first;
804
805 if (size < 1) return -1;
806
807 #ifdef FASTER_MAP_LOAD
808 find_axis_and_bbox(bbox_tree, first, last, axis, &bbox);
809 #else
810 find_axis(bbox_tree, first, last, axis);
811 #endif
812
813 best_loc = -1;
814
815 if (size > 8)
816 {
817 area_left = malloc(size * sizeof(float));
818 area_right = malloc(size * sizeof(float));
819
820 for (j = 0; j < 3; j++)
821 {
822 Axis = axis[j];
823
824 qsort(bbox_tree->items + first, size, sizeof(BBOX_ITEM), compboxes);
825 build_area_table(bbox_tree, first, last - 1, area_left);
826 build_area_table(bbox_tree, last - 1, first, area_right);
827
828 best_index = area_right[0] * (size - 3.0);
829
830 /*
831 * Find the most effective point to split. The best location will be
832 * the one that minimizes the function N1*A1 + N2*A2 where N1 and N2
833 * are the number of objects in the two groups and A1 and A2 are the
834 * surface areas of the bounding boxes of the two groups.
835 */
836 for (i = 0; i < size - 1; i++)
837 {
838 new_index = (i + 1) * area_left[i] + (size - 1 - i) * area_right[i + 1];
839
840 if (new_index < best_index)
841 {
842 best_index = new_index;
843 best_loc = i + first;
844 }
845 }
846 if (best_loc >= 0) break;
847 }
848
849 free(area_left);
850 free(area_right);
851 }
852
853 #ifdef FASTER_MAP_LOAD
854 VAssign(bbox_tree->nodes[node].bbox.bbmin, bbox.bbmin);
855 VAssign(bbox_tree->nodes[node].bbox.bbmax, bbox.bbmax);
856 VAssign(bbox_tree->nodes[node].orig_bbox.bbmin, bbox.bbmin);
857 VAssign(bbox_tree->nodes[node].orig_bbox.bbmax, bbox.bbmax);
858 #else
859 calc_bbox(&bbox_tree->nodes[node].bbox, bbox_tree, first, last);
860 VAssign(bbox_tree->nodes[node].orig_bbox.bbmin, bbox_tree->nodes[node].bbox.bbmin);
861 VAssign(bbox_tree->nodes[node].orig_bbox.bbmax, bbox_tree->nodes[node].bbox.bbmax);
862 #endif
863 bbox_tree->nodes[node].items_index = first;
864 bbox_tree->nodes[node].items_count = size;
865
866 bbox_tree->nodes[node].dynamic_objects.size = 0;
867 bbox_tree->nodes[node].dynamic_objects.index = 0;
868 bbox_tree->nodes[node].dynamic_objects.items = NULL;
869
870 if (best_loc < 0)
871 {
872 bbox_tree->nodes[node].nodes[0] = NO_INDEX;
873 bbox_tree->nodes[node].nodes[1] = NO_INDEX;
874 return 1;
875 }
876 else
877 {
878 if (*index+2 >= bbox_tree->nodes_count)
879 {
880 bbox_tree->nodes_count *= 2;
881 bbox_tree->nodes = (BBOX_TREE_NODE*)realloc(bbox_tree->nodes, bbox_tree->nodes_count*sizeof(BBOX_TREE_NODE));
882 }
883 bbox_tree->nodes[node].nodes[0] = (*index)+0;
884 bbox_tree->nodes[node].nodes[1] = (*index)+1;
885 *index += 2;
886 sort_and_split(bbox_tree, bbox_tree->nodes[node].nodes[0], index, first, best_loc + 1);
887 sort_and_split(bbox_tree, bbox_tree->nodes[node].nodes[1], index, best_loc + 1, last);
888 return 0;
889 }
890 }
891
init_bbox_tree(BBOX_TREE * bbox_tree,const BBOX_ITEMS * bbox_items)892 void init_bbox_tree(BBOX_TREE* bbox_tree, const BBOX_ITEMS *bbox_items)
893 {
894 Uint32 size, index;
895
896 if (bbox_items != NULL)
897 {
898 if (bbox_items->index > 0)
899 {
900 size = bbox_items->index;
901 index = 1;
902 bbox_tree->nodes_count = 2*size;
903 bbox_tree->nodes = (BBOX_TREE_NODE*)malloc(size*2*sizeof(BBOX_TREE_NODE));
904 bbox_tree->items_count = size;
905 bbox_tree->items = (BBOX_ITEM*)malloc(size*sizeof(BBOX_ITEM));
906 memcpy(bbox_tree->items, bbox_items->items, size*sizeof(BBOX_ITEM));
907 sort_and_split(bbox_tree, 0, &index, 0, size);
908 bbox_tree->nodes_count = index;
909 bbox_tree->nodes = (BBOX_TREE_NODE*)realloc(bbox_tree->nodes, index*sizeof(BBOX_TREE_NODE));
910 set_all_intersect_update_needed(bbox_tree);
911 }
912 }
913 else BBOX_TREE_LOG_INFO("bbox_items");
914 }
915
add_aabb_to_list(BBOX_ITEMS * bbox_items,const AABBOX bbox,Uint32 ID,Uint32 type,Uint32 texture_id)916 static __inline__ void add_aabb_to_list(BBOX_ITEMS *bbox_items, const AABBOX bbox, Uint32 ID, Uint32 type, Uint32 texture_id)
917 {
918 Uint32 index, size;
919
920 index = bbox_items->index;
921 size = bbox_items->size;
922
923 if (size <= index)
924 {
925 size *= 2;
926 bbox_items->items = (BBOX_ITEM*)realloc(bbox_items->items, size*sizeof(BBOX_ITEM));
927 bbox_items->size = size;
928 }
929 VAssign(bbox_items->items[index].bbox.bbmin, bbox.bbmin);
930 VAssign(bbox_items->items[index].bbox.bbmax, bbox.bbmax);
931 bbox_items->items[index].type = type;
932 bbox_items->items[index].extra = 0;
933 bbox_items->items[index].texture_id = texture_id;
934 bbox_items->items[index].ID = ID;
935 #ifdef CLUSTER_INSIDES
936 bbox_items->items[index].cluster = current_cluster;
937 #endif // CLUSTER_INSIDES
938 bbox_items->index = index + 1;
939 }
940
add_light_to_list(BBOX_ITEMS * bbox_items,Uint32 ID,const AABBOX bbox)941 void add_light_to_list(BBOX_ITEMS *bbox_items, Uint32 ID, const AABBOX bbox)
942 {
943 add_aabb_to_list(bbox_items, bbox, ID, TYPE_LIGHT, 0);
944 }
945
get_3D_type(Uint32 blend,Uint32 ground,Uint32 alpha,Uint32 self_lit)946 static __inline__ Uint32 get_3D_type(Uint32 blend, Uint32 ground, Uint32 alpha, Uint32 self_lit)
947 {
948 Uint32 type;
949
950 type = 0;
951 if (!blend) type += 8;
952 if (!ground) type += 4;
953 if (!alpha) type += 2;
954 if (!self_lit) type += 1;
955
956 switch (type)
957 {
958 case 0: return TYPE_3D_BLEND_GROUND_ALPHA_SELF_LIT_OBJECT;
959 case 1: return TYPE_3D_BLEND_GROUND_ALPHA_NO_SELF_LIT_OBJECT;
960 case 2: return TYPE_3D_BLEND_GROUND_NO_ALPHA_SELF_LIT_OBJECT;
961 case 3: return TYPE_3D_BLEND_GROUND_NO_ALPHA_NO_SELF_LIT_OBJECT;
962 case 4: return TYPE_3D_BLEND_NO_GROUND_ALPHA_SELF_LIT_OBJECT;
963 case 5: return TYPE_3D_BLEND_NO_GROUND_ALPHA_NO_SELF_LIT_OBJECT;
964 case 6: return TYPE_3D_BLEND_NO_GROUND_NO_ALPHA_SELF_LIT_OBJECT;
965 case 7: return TYPE_3D_BLEND_NO_GROUND_NO_ALPHA_NO_SELF_LIT_OBJECT;
966 case 8: return TYPE_3D_NO_BLEND_GROUND_ALPHA_SELF_LIT_OBJECT;
967 case 9: return TYPE_3D_NO_BLEND_GROUND_ALPHA_NO_SELF_LIT_OBJECT;
968 case 10: return TYPE_3D_NO_BLEND_GROUND_NO_ALPHA_SELF_LIT_OBJECT;
969 case 11: return TYPE_3D_NO_BLEND_GROUND_NO_ALPHA_NO_SELF_LIT_OBJECT;
970 case 12: return TYPE_3D_NO_BLEND_NO_GROUND_ALPHA_SELF_LIT_OBJECT;
971 case 13: return TYPE_3D_NO_BLEND_NO_GROUND_ALPHA_NO_SELF_LIT_OBJECT;
972 case 14: return TYPE_3D_NO_BLEND_NO_GROUND_NO_ALPHA_SELF_LIT_OBJECT;
973 case 15: return TYPE_3D_NO_BLEND_NO_GROUND_NO_ALPHA_NO_SELF_LIT_OBJECT;
974 default: return 0xFF;
975 }
976 }
977
get_3D_type_mask(Uint32 blend,Uint32 self_lit)978 static __inline__ Uint32 get_3D_type_mask(Uint32 blend, Uint32 self_lit)
979 {
980 Uint32 type;
981
982 type = 0;
983 if (!blend) type += 2;
984 if (!self_lit) type += 1;
985
986 switch (type)
987 {
988 case 0: return TYPE_MASK_3D_BLEND_SELF_LIT_OBJECT;
989 case 1: return TYPE_MASK_3D_BLEND_NO_SELF_LIT_OBJECT;
990 case 2: return TYPE_MASK_3D_NO_BLEND_SELF_LIT_OBJECT;
991 case 3: return TYPE_MASK_3D_NO_BLEND_NO_SELF_LIT_OBJECT;
992 default: return 0xFF;
993 }
994 }
995
add_3dobject_to_list(BBOX_ITEMS * bbox_items,Uint32 ID,const AABBOX bbox,Uint32 blend,Uint32 ground,Uint32 alpha,Uint32 self_lit,Uint32 texture_id)996 void add_3dobject_to_list(BBOX_ITEMS *bbox_items, Uint32 ID, const AABBOX bbox, Uint32 blend, Uint32 ground, Uint32 alpha, Uint32 self_lit, Uint32 texture_id)
997 {
998 add_aabb_to_list(bbox_items, bbox, ID, get_3D_type(blend, ground, alpha, self_lit), texture_id);
999 }
1000
get_2D_type(Uint32 alpha)1001 static __inline__ Uint32 get_2D_type(Uint32 alpha)
1002 {
1003 if (alpha == 0) return TYPE_2D_NO_ALPHA_OBJECT;
1004 else return TYPE_2D_ALPHA_OBJECT;
1005 }
1006
get_2D_type_mask(Uint32 alpha)1007 static __inline__ Uint32 get_2D_type_mask(Uint32 alpha)
1008 {
1009 if (alpha == 0) return TYPE_MASK_2D_ALPHA_OBJECT;
1010 else return TYPE_MASK_2D_NO_ALPHA_OBJECT;
1011 }
1012
add_2dobject_to_list(BBOX_ITEMS * bbox_items,Uint32 ID,const AABBOX bbox,Uint32 alpha,Uint32 texture_id)1013 void add_2dobject_to_list(BBOX_ITEMS *bbox_items, Uint32 ID, const AABBOX bbox, Uint32 alpha, Uint32 texture_id)
1014 {
1015 add_aabb_to_list(bbox_items, bbox, ID, get_2D_type(alpha), texture_id);
1016 }
1017
get_blend_type(Uint32 blend)1018 static __inline__ Uint32 get_blend_type(Uint32 blend)
1019 {
1020 switch (blend)
1021 {
1022 case GL_ZERO: return 0;
1023 case GL_ONE: return 1;
1024 case GL_SRC_COLOR: return 2;
1025 case GL_ONE_MINUS_SRC_COLOR: return 3;
1026 case GL_DST_COLOR: return 4;
1027 case GL_ONE_MINUS_DST_COLOR: return 5;
1028 case GL_SRC_ALPHA: return 6;
1029 case GL_ONE_MINUS_SRC_ALPHA: return 7;
1030 case GL_DST_ALPHA: return 8;
1031 case GL_ONE_MINUS_DST_ALPHA: return 9;
1032 case GL_SRC_ALPHA_SATURATE: return 10;
1033 default: return 0xFF;
1034 }
1035 }
1036
get_particle_type(Uint32 sblend,Uint32 dblend)1037 static __inline__ Uint32 get_particle_type(Uint32 sblend, Uint32 dblend)
1038 {
1039 return ((get_blend_type(sblend) << 4) + get_blend_type(dblend));
1040 }
1041
add_particle_sys_to_list(BBOX_ITEMS * bbox_items,Uint32 ID,const AABBOX bbox,Uint32 sblend,Uint32 dblend)1042 void add_particle_sys_to_list(BBOX_ITEMS *bbox_items, Uint32 ID, const AABBOX bbox, Uint32 sblend, Uint32 dblend)
1043 {
1044 add_aabb_to_list(bbox_items, bbox, ID, TYPE_PARTICLE_SYSTEM, get_particle_type(sblend, dblend));
1045 }
1046
add_terrain_to_list(BBOX_ITEMS * bbox_items,Uint32 ID,const AABBOX bbox,Uint32 texture_id)1047 void add_terrain_to_list(BBOX_ITEMS *bbox_items, Uint32 ID, const AABBOX bbox, Uint32 texture_id)
1048 {
1049 add_aabb_to_list(bbox_items, bbox, ID, TYPE_TERRAIN, texture_id);
1050 }
1051
get_water_type(Uint32 reflectiv)1052 static __inline__ Uint32 get_water_type(Uint32 reflectiv)
1053 {
1054 if (reflectiv) return TYPE_REFLECTIV_WATER;
1055 else return TYPE_NO_REFLECTIV_WATER;
1056 }
1057
get_water_type_mask(Uint32 reflectiv)1058 static __inline__ Uint32 get_water_type_mask(Uint32 reflectiv)
1059 {
1060 if (reflectiv) return TYPE_MASK_REFLECTIV_WATER;
1061 else return TYPE_MASK_NO_REFLECTIV_WATER;
1062 }
1063
add_water_to_list(BBOX_ITEMS * bbox_items,Uint32 ID,const AABBOX bbox,Uint32 texture_id,Uint32 reflectiv)1064 void add_water_to_list(BBOX_ITEMS *bbox_items, Uint32 ID, const AABBOX bbox, Uint32 texture_id, Uint32 reflectiv)
1065 {
1066 add_aabb_to_list(bbox_items, bbox, ID, get_water_type(reflectiv), texture_id);
1067 }
1068
check_aabb_aabb(const AABBOX bbox,const AABBOX dyn_bbox,float grow)1069 static __inline__ Uint32 check_aabb_aabb(const AABBOX bbox, const AABBOX dyn_bbox, float grow)
1070 {
1071 AABBOX new_bbox;
1072 VECTOR3 len;
1073 float old_v, new_v;
1074
1075 VMin(new_bbox.bbmin, bbox.bbmin, dyn_bbox.bbmin);
1076 VMax(new_bbox.bbmax, bbox.bbmax, dyn_bbox.bbmax);
1077
1078 VSub(len, bbox.bbmax, bbox.bbmin);
1079 old_v = len[X] * len[Y] * len[Z];
1080 VSub(len, new_bbox.bbmax, new_bbox.bbmin);
1081 new_v = len[X] * len[Y] * len[Z];
1082
1083 if ((new_v / old_v) > grow) return 0;
1084 else return 1;
1085 }
1086
add_dynamic_item_to_node(BBOX_TREE * bbox_tree,Uint32 node,const AABBOX bbox,Uint32 ID,Uint32 type,Uint32 texture_id,Uint32 extra)1087 static __inline__ void add_dynamic_item_to_node(BBOX_TREE *bbox_tree, Uint32 node, const AABBOX bbox, Uint32 ID, Uint32 type, Uint32 texture_id, Uint32 extra)
1088 {
1089 Uint32 index, size;
1090
1091 if (node != NO_INDEX)
1092 {
1093 index = bbox_tree->nodes[node].dynamic_objects.index;
1094 size = bbox_tree->nodes[node].dynamic_objects.size;
1095
1096 if (size <= index)
1097 {
1098 if (size < 4) size = 4;
1099 size *= 2;
1100 bbox_tree->nodes[node].dynamic_objects.items = (BBOX_ITEM*)realloc(bbox_tree->nodes[node].dynamic_objects.items, size*sizeof(BBOX_ITEM));
1101 bbox_tree->nodes[node].dynamic_objects.size = size;
1102 }
1103
1104 bbox_tree->nodes[node].dynamic_objects.items[index].ID = ID;
1105 bbox_tree->nodes[node].dynamic_objects.items[index].extra = extra;
1106 bbox_tree->nodes[node].dynamic_objects.items[index].texture_id = texture_id;
1107 bbox_tree->nodes[node].dynamic_objects.items[index].type = type;
1108 #ifdef CLUSTER_INSIDES
1109 bbox_tree->nodes[node].dynamic_objects.items[index].cluster = current_cluster;
1110 #endif // CLUSTER_INSIDES
1111 VAssign(bbox_tree->nodes[node].dynamic_objects.items[index].bbox.bbmin, bbox.bbmin);
1112 VAssign(bbox_tree->nodes[node].dynamic_objects.items[index].bbox.bbmax, bbox.bbmax);
1113 bbox_tree->nodes[node].dynamic_objects.index = index + 1;
1114 VMin(bbox_tree->nodes[node].bbox.bbmin, bbox_tree->nodes[node].bbox.bbmin, bbox.bbmin);
1115 VMax(bbox_tree->nodes[node].bbox.bbmax, bbox_tree->nodes[node].bbox.bbmax, bbox.bbmax);
1116 }
1117 }
1118
add_dynamic_aabb_to_abt_node(BBOX_TREE * bbox_tree,Uint32 node,const AABBOX bbox,Uint32 ID,Uint32 type,Uint32 texture_id)1119 static __inline__ int add_dynamic_aabb_to_abt_node(BBOX_TREE *bbox_tree, Uint32 node, const AABBOX bbox, Uint32 ID, Uint32 type, Uint32 texture_id)
1120 {
1121 Uint32 result, extra;
1122
1123 if (node != NO_INDEX)
1124 {
1125 if (check_aabb_aabb(bbox_tree->nodes[node].orig_bbox, bbox, 1.1f))
1126 {
1127 extra = EXTRA_FIRST_SUB_NODE;
1128 result = add_dynamic_aabb_to_abt_node(bbox_tree, bbox_tree->nodes[node].nodes[0], bbox, ID, type, texture_id);
1129 if (result == 0)
1130 {
1131 result = add_dynamic_aabb_to_abt_node(bbox_tree, bbox_tree->nodes[node].nodes[1], bbox, ID, type, texture_id);
1132 extra = 0;
1133 }
1134 add_dynamic_item_to_node(bbox_tree, node, bbox, ID, type, texture_id, extra);
1135 return 1;
1136 }
1137 else return 0;
1138 }
1139 else return 0;
1140 }
1141
add_aabb_to_abt(BBOX_TREE * bbox_tree,const AABBOX bbox,Uint32 ID,Uint32 type,Uint32 texture_id,Uint32 dynamic)1142 static __inline__ void add_aabb_to_abt(BBOX_TREE *bbox_tree, const AABBOX bbox, Uint32 ID, Uint32 type, Uint32 texture_id, Uint32 dynamic)
1143 {
1144 Uint32 result;
1145
1146 if (bbox_tree != NULL)
1147 {
1148 result = add_dynamic_aabb_to_abt_node(bbox_tree, 0, bbox, ID, type, texture_id);
1149 if (result == 0) add_dynamic_item_to_node(bbox_tree, 0, bbox, ID, type, texture_id, 0);
1150 set_all_intersect_update_needed(bbox_tree);
1151 }
1152 else BBOX_TREE_LOG_INFO("bbox_tree");
1153 }
1154
add_light_to_abt(BBOX_TREE * bbox_tree,Uint32 ID,const AABBOX bbox,Uint32 dynamic)1155 void add_light_to_abt(BBOX_TREE *bbox_tree, Uint32 ID, const AABBOX bbox, Uint32 dynamic)
1156 {
1157 add_aabb_to_abt(bbox_tree, bbox, ID, TYPE_LIGHT, 0, dynamic);
1158 }
1159
add_3dobject_to_abt(BBOX_TREE * bbox_tree,Uint32 ID,const AABBOX bbox,Uint32 blend,Uint32 ground,Uint32 alpha,Uint32 self_lit,Uint32 texture_id,Uint32 dynamic)1160 void add_3dobject_to_abt(BBOX_TREE *bbox_tree, Uint32 ID, const AABBOX bbox, Uint32 blend, Uint32 ground, Uint32 alpha, Uint32 self_lit, Uint32 texture_id, Uint32 dynamic)
1161 {
1162 add_aabb_to_abt(bbox_tree, bbox, ID, get_3D_type(blend, ground, alpha, self_lit), texture_id, dynamic);
1163 }
1164
add_2dobject_to_abt(BBOX_TREE * bbox_tree,Uint32 ID,const AABBOX bbox,Uint32 alpha,Uint32 texture_id,Uint32 dynamic)1165 void add_2dobject_to_abt(BBOX_TREE *bbox_tree, Uint32 ID, const AABBOX bbox, Uint32 alpha, Uint32 texture_id, Uint32 dynamic)
1166 {
1167 add_aabb_to_abt(bbox_tree, bbox, ID, get_2D_type(alpha), texture_id, dynamic);
1168 }
1169
add_particle_to_abt(BBOX_TREE * bbox_tree,Uint32 ID,const AABBOX bbox,Uint32 sblend,Uint32 dblend,Uint32 dynamic)1170 void add_particle_to_abt(BBOX_TREE *bbox_tree, Uint32 ID, const AABBOX bbox, Uint32 sblend, Uint32 dblend, Uint32 dynamic)
1171 {
1172 add_aabb_to_abt(bbox_tree, bbox, ID, TYPE_PARTICLE_SYSTEM, get_particle_type(sblend, dblend), dynamic);
1173 }
1174
add_terrain_to_abt(BBOX_TREE * bbox_tree,Uint32 ID,const AABBOX bbox,Uint32 texture_id,Uint32 dynamic)1175 void add_terrain_to_abt(BBOX_TREE *bbox_tree, Uint32 ID, const AABBOX bbox, Uint32 texture_id, Uint32 dynamic)
1176 {
1177 add_aabb_to_abt(bbox_tree, bbox, ID, TYPE_TERRAIN, texture_id, dynamic);
1178 }
1179
add_water_to_abt(BBOX_TREE * bbox_tree,Uint32 ID,const AABBOX bbox,Uint32 texture_id,Uint32 reflectiv,Uint32 dynamic)1180 void add_water_to_abt(BBOX_TREE *bbox_tree, Uint32 ID, const AABBOX bbox, Uint32 texture_id, Uint32 reflectiv, Uint32 dynamic)
1181 {
1182 add_aabb_to_abt(bbox_tree, bbox, ID, get_water_type(reflectiv), texture_id, dynamic);
1183 }
1184
1185 static __inline__ Uint32 delete_dynamic_aabb_from_node(BBOX_TREE *bbox_tree, Uint32 node, Uint32 ID, Uint32 type_mask);
1186
delete_dynamic_item_from_node(BBOX_TREE * bbox_tree,Uint32 node,Uint32 idx,Uint32 ID,Uint32 type_mask)1187 static __inline__ void delete_dynamic_item_from_node(BBOX_TREE *bbox_tree, Uint32 node, Uint32 idx, Uint32 ID, Uint32 type_mask)
1188 {
1189 int index, size, count;
1190
1191 index = bbox_tree->nodes[node].dynamic_objects.index;
1192 size = bbox_tree->nodes[node].dynamic_objects.size;
1193
1194 if (is_extra_first_sub_node(bbox_tree->nodes[node].dynamic_objects.items[idx].extra))
1195 delete_dynamic_aabb_from_node(bbox_tree, bbox_tree->nodes[node].nodes[0], ID, type_mask);
1196 else delete_dynamic_aabb_from_node(bbox_tree, bbox_tree->nodes[node].nodes[1], ID, type_mask);
1197
1198 if (index <= 1)
1199 {
1200 size = 0;
1201 index = 0;
1202 if (bbox_tree->nodes[node].dynamic_objects.items != NULL)
1203 {
1204 free(bbox_tree->nodes[node].dynamic_objects.items);
1205 bbox_tree->nodes[node].dynamic_objects.items = NULL;
1206 }
1207 }
1208 else
1209 {
1210 if (index < (size/2))
1211 {
1212 size /= 2;
1213 bbox_tree->nodes[node].dynamic_objects.items = (BBOX_ITEM*)realloc(bbox_tree->nodes[node].dynamic_objects.items, size*sizeof(BBOX_ITEM));
1214 }
1215
1216 count = index-idx-1;
1217 if (count > 0) memmove(&bbox_tree->nodes[node].dynamic_objects.items[idx], &bbox_tree->nodes[node].dynamic_objects.items[idx+1], count*sizeof(BBOX_ITEM));
1218 index--;
1219 }
1220 bbox_tree->nodes[node].dynamic_objects.index = index;
1221 bbox_tree->nodes[node].dynamic_objects.size = size;
1222 }
1223
dynamic_aabb_is_in_node(BBOX_TREE * bbox_tree,Uint32 node,Uint32 ID,Uint32 type_mask)1224 static __inline__ Uint32 dynamic_aabb_is_in_node(BBOX_TREE *bbox_tree, Uint32 node, Uint32 ID, Uint32 type_mask)
1225 {
1226 Uint32 i, result;
1227 Uint32 id;
1228
1229 result = 0;
1230
1231 for (i = 0; i < bbox_tree->nodes[node].dynamic_objects.index; i++)
1232 {
1233 if ((type_mask == TYPE_MASK_3D_BLEND_SELF_LIT_OBJECT) ||
1234 (type_mask == TYPE_MASK_3D_BLEND_NO_SELF_LIT_OBJECT) ||
1235 (type_mask == TYPE_MASK_3D_NO_BLEND_SELF_LIT_OBJECT) ||
1236 (type_mask == TYPE_MASK_3D_NO_BLEND_NO_SELF_LIT_OBJECT))
1237 id = get_3dobject_index(bbox_tree->nodes[node].dynamic_objects.items[i].ID);
1238 else id = bbox_tree->nodes[node].dynamic_objects.items[i].ID;
1239
1240 if ((id == ID) &&
1241 (get_type_mask_from_type(bbox_tree->nodes[node].dynamic_objects.items[i].type) == type_mask))
1242 {
1243 delete_dynamic_item_from_node(bbox_tree, node, i, ID, type_mask);
1244 result = 1;
1245 }
1246 }
1247
1248 return result;
1249 }
1250
delete_dynamic_aabb_from_node(BBOX_TREE * bbox_tree,Uint32 node,Uint32 ID,Uint32 type_mask)1251 static __inline__ Uint32 delete_dynamic_aabb_from_node(BBOX_TREE *bbox_tree, Uint32 node, Uint32 ID, Uint32 type_mask)
1252 {
1253 Uint32 i, result, idx1, idx2;
1254 AABBOX new_bbox;
1255
1256 if (node != NO_INDEX && bbox_tree->nodes_count > 0)
1257 {
1258 result = dynamic_aabb_is_in_node(bbox_tree, node, ID, type_mask);
1259 if (result != 0)
1260 {
1261 if ((bbox_tree->nodes[node].nodes[0] != NO_INDEX) && (bbox_tree->nodes[node].nodes[1] != NO_INDEX))
1262 {
1263 idx1 = bbox_tree->nodes[node].nodes[0];
1264 idx2 = bbox_tree->nodes[node].nodes[1];
1265 VMin(new_bbox.bbmin, bbox_tree->nodes[idx1].bbox.bbmin, bbox_tree->nodes[idx2].bbox.bbmin);
1266 VMax(new_bbox.bbmax, bbox_tree->nodes[idx1].bbox.bbmax, bbox_tree->nodes[idx2].bbox.bbmax);
1267 }
1268 else
1269 {
1270 VAssign(new_bbox.bbmin, bbox_tree->nodes[node].orig_bbox.bbmin);
1271 VAssign(new_bbox.bbmax, bbox_tree->nodes[node].orig_bbox.bbmax);
1272 }
1273
1274 for (i = 0; i < bbox_tree->nodes[node].dynamic_objects.index; i++)
1275 {
1276 VMin(new_bbox.bbmin, new_bbox.bbmin, bbox_tree->nodes[node].dynamic_objects.items[i].bbox.bbmin);
1277 VMax(new_bbox.bbmax, new_bbox.bbmax, bbox_tree->nodes[node].dynamic_objects.items[i].bbox.bbmax);
1278 }
1279
1280 VAssign(bbox_tree->nodes[node].bbox.bbmin, new_bbox.bbmin);
1281 VAssign(bbox_tree->nodes[node].bbox.bbmax, new_bbox.bbmax);
1282
1283 return 1;
1284 }
1285 }
1286 return 0;
1287 }
1288
delete_aabb_from_abt(BBOX_TREE * bbox_tree,Uint32 ID,Uint32 type_mask)1289 static __inline__ void delete_aabb_from_abt(BBOX_TREE *bbox_tree, Uint32 ID, Uint32 type_mask)
1290 {
1291 if (bbox_tree != NULL)
1292 {
1293 delete_item_from_intersect_list(bbox_tree, ID, type_mask);
1294 delete_dynamic_aabb_from_node(bbox_tree, 0, ID, type_mask);
1295 }
1296 else BBOX_TREE_LOG_INFO("bbox_tree");
1297 }
1298
delete_3dobject_from_abt(BBOX_TREE * bbox_tree,Uint32 ID,Uint32 blend,Uint32 self_lit)1299 void delete_3dobject_from_abt(BBOX_TREE *bbox_tree, Uint32 ID, Uint32 blend, Uint32 self_lit)
1300 {
1301 delete_aabb_from_abt(bbox_tree, ID, get_3D_type_mask(blend, self_lit));
1302 }
1303
delete_2dobject_from_abt(BBOX_TREE * bbox_tree,Uint32 ID,Uint32 alpha)1304 void delete_2dobject_from_abt(BBOX_TREE *bbox_tree, Uint32 ID, Uint32 alpha)
1305 {
1306 delete_aabb_from_abt(bbox_tree, ID, get_2D_type_mask(alpha));
1307 }
1308
delete_particle_from_abt(BBOX_TREE * bbox_tree,Uint32 ID)1309 void delete_particle_from_abt(BBOX_TREE *bbox_tree, Uint32 ID)
1310 {
1311 delete_aabb_from_abt(bbox_tree, ID, TYPE_MASK_PARTICLE_SYSTEM);
1312 }
1313
delete_light_from_abt(BBOX_TREE * bbox_tree,Uint32 ID)1314 void delete_light_from_abt(BBOX_TREE *bbox_tree, Uint32 ID)
1315 {
1316 delete_aabb_from_abt(bbox_tree, ID, TYPE_MASK_LIGHT);
1317 }
1318
delete_terrain_from_abt(BBOX_TREE * bbox_tree,Uint32 ID)1319 void delete_terrain_from_abt(BBOX_TREE *bbox_tree, Uint32 ID)
1320 {
1321 delete_aabb_from_abt(bbox_tree, ID, TYPE_MASK_TERRAIN);
1322 }
1323
delete_water_from_abt(BBOX_TREE * bbox_tree,Uint32 ID,Uint32 reflectiv)1324 void delete_water_from_abt(BBOX_TREE *bbox_tree, Uint32 ID, Uint32 reflectiv)
1325 {
1326 delete_aabb_from_abt(bbox_tree, ID, get_water_type_mask(reflectiv));
1327 }
1328
create_bbox_items(Uint32 size)1329 BBOX_ITEMS* create_bbox_items(Uint32 size)
1330 {
1331 BBOX_ITEMS* bbox_items;
1332
1333 bbox_items = (BBOX_ITEMS*)malloc(sizeof(BBOX_ITEMS));
1334 size = max2u(8, size);
1335 bbox_items->size = size;
1336 bbox_items->index = 0;
1337 bbox_items->items = (BBOX_ITEM*)malloc(size*sizeof(BBOX_ITEM));
1338
1339 return bbox_items;
1340 }
1341
free_bbox_items(BBOX_ITEMS * bbox_items)1342 void free_bbox_items(BBOX_ITEMS* bbox_items)
1343 {
1344 if (bbox_items != NULL)
1345 {
1346 if (bbox_items->items != NULL)
1347 {
1348 free(bbox_items->items);
1349 bbox_items->items = NULL;
1350 }
1351 else BBOX_TREE_LOG_INFO("bbox_items->items");
1352 free(bbox_items);
1353 bbox_items = NULL;
1354 }
1355 else BBOX_TREE_LOG_INFO("bbox_items");
1356 }
1357
build_bbox_tree()1358 BBOX_TREE* build_bbox_tree()
1359 {
1360 BBOX_TREE* bbox_tree;
1361 Uint32 i;
1362
1363 bbox_tree = (BBOX_TREE*)malloc(sizeof(BBOX_TREE));
1364
1365 bbox_tree->cur_intersect_type = INTERSECTION_TYPE_DEFAULT;
1366 for (i = 0; i < MAX_INTERSECTION_TYPES; i++)
1367 {
1368 bbox_tree->intersect[i].size = 8;
1369 bbox_tree->intersect[i].count = 0;
1370 bbox_tree->intersect[i].items = (BBOX_ITEM*)malloc(8*sizeof(BBOX_ITEM));
1371 memset(&bbox_tree->intersect[i].flags, 0, sizeof(bbox_tree->intersect[i].flags));
1372 }
1373 bbox_tree->nodes_count = 0;
1374 bbox_tree->nodes = NULL;
1375 bbox_tree->items_count = 0;
1376 bbox_tree->items = NULL;
1377 return bbox_tree;
1378 }
1379
get_point_from_aabbox(VECTOR3 point,const AABBOX bbox,Uint32 number)1380 static __inline__ void get_point_from_aabbox(VECTOR3 point, const AABBOX bbox, Uint32 number)
1381 {
1382 VECTOR3I mask;
1383
1384 switch (number)
1385 {
1386 case 0:
1387 VMakeI(mask, 0x00000000, 0x00000000, 0x00000000);
1388 break;
1389 case 1:
1390 VMakeI(mask, 0x00000000, 0x00000000, 0xFFFFFFFF);
1391 break;
1392 case 2:
1393 VMakeI(mask, 0x00000000, 0xFFFFFFFF, 0x00000000);
1394 break;
1395 case 3:
1396 VMakeI(mask, 0x00000000, 0xFFFFFFFF, 0xFFFFFFFF);
1397 break;
1398 case 4:
1399 VMakeI(mask, 0xFFFFFFFF, 0x00000000, 0x00000000);
1400 break;
1401 case 5:
1402 VMakeI(mask, 0xFFFFFFFF, 0x00000000, 0xFFFFFFFF);
1403 break;
1404 case 6:
1405 VMakeI(mask, 0xFFFFFFFF, 0xFFFFFFFF, 0x00000000);
1406 break;
1407 case 7:
1408 VMakeI(mask, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF);
1409 break;
1410 default:
1411 VMakeI(mask, 0x00000000, 0x00000000, 0x00000000);
1412 #ifdef DEBUG
1413 LOG_ERROR("Wrong number (%d) for get_point_from_aabbox!", number);
1414 #endif
1415 break;
1416 }
1417 VSelect(point, bbox.bbmin, bbox.bbmax, mask);
1418 }
1419
calculate_frustum_data(FRUSTUM_DATA data,const FRUSTUM frustum,const VECTOR3 light_dir,Uint32 mask)1420 static __inline__ void calculate_frustum_data(FRUSTUM_DATA data, const FRUSTUM frustum, const VECTOR3 light_dir, Uint32 mask)
1421 {
1422 VECTOR3 n;
1423 VECTOR4 t;
1424 float v;
1425 int i, k;
1426
1427 VAssign(n, light_dir);
1428 Normalize(n, n);
1429 VAssign4(t, n, 0.0f);
1430
1431 for (i = 0, k = 1; k <= mask; i++, k += k)
1432 {
1433 if (k & mask)
1434 {
1435 v = VDot4(t, frustum[i].plane);
1436 if (max2f(v, -v) < 0.0001f)
1437 {
1438 data[i].zero = 1;
1439 data[i].scale = 1.0f;
1440 data[i].mask = 0;
1441 }
1442 else
1443 {
1444 data[i].zero = 0;
1445 data[i].scale = v;
1446 if (v < 0.0f) data[i].mask = 1;
1447 else data[i].mask = 0;
1448 }
1449 }
1450 }
1451 }
1452
check_shadow_line_walk(const AABBOX bbox,const FRUSTUM frustum,const VECTOR3 light_dir,Uint32 mask,const float * hit)1453 static __inline__ int check_shadow_line_walk(const AABBOX bbox, const FRUSTUM frustum, const VECTOR3 light_dir, Uint32 mask, const float* hit)
1454 {
1455 AABBOX tmp_bbox;
1456 VECTOR3 walk;
1457 int i, k, result, intersect;
1458
1459 intersect = 0;
1460
1461 result = check_aabb_in_frustum_no_out_mask(bbox, frustum, mask);
1462
1463 if (result == INSIDE) return result;
1464 else if (result == INTERSECT) intersect = 1;
1465
1466 for (i = 0, k = 1; k <= mask; i++, k += k)
1467 {
1468 if ((k & mask) && (hit[i] > 0.0f))
1469 {
1470 VScale(walk, light_dir, hit[i]);
1471 VAdd(tmp_bbox.bbmin, bbox.bbmin, walk);
1472 VAdd(tmp_bbox.bbmax, bbox.bbmax, walk);
1473 result = check_aabb_in_frustum_no_out_mask(tmp_bbox, frustum, mask);
1474 if (result == INSIDE) return result;
1475 else if (result == INTERSECT) intersect = 1;
1476 }
1477 }
1478 if (intersect != 0) return INTERSECT;
1479 else return OUTSIDE;
1480 }
1481
check_shadow_lines(const AABBOX bbox,const FRUSTUM frustum,const FRUSTUM_DATA data,const VECTOR3 light_dir,Uint32 mask,Uint32 point_mask)1482 static __inline__ int check_shadow_lines(const AABBOX bbox, const FRUSTUM frustum, const FRUSTUM_DATA data, const VECTOR3 light_dir, Uint32 mask, Uint32 point_mask)
1483 {
1484 VECTOR3 _p;
1485 VECTOR4 p;
1486 float tmp, vmin, vmax, step, hit[16];
1487 int i, j, k, l, intersect, intersects, points;
1488
1489 intersects = 0;
1490 points = 0;
1491
1492 memset(hit, 0, sizeof(hit));
1493
1494 for (i = 0, k = 1; k <= point_mask; i++, k += k)
1495 {
1496 if (k & point_mask)
1497 {
1498 get_point_from_aabbox(_p, bbox, i);
1499 VAssign4(p, _p, 1.0f);
1500 vmin = 0.0f;
1501 vmax = BOUND_HUGE;
1502 points++;
1503 intersect = 1;
1504
1505 for (j = 0, l = 1; l <= mask; j++, l += l)
1506 {
1507 if (l & mask)
1508 {
1509 tmp = VDot4(p, frustum[j].plane);
1510
1511 if (data[j].zero == 0)
1512 {
1513 step = tmp/data[j].scale;
1514 if (step < 0.0f)
1515 {
1516 if (tmp < 0.0f)
1517 {
1518 intersect = 0;
1519 }
1520 }
1521 else
1522 {
1523 hit[j] = max2f(hit[j], step);
1524 if (intersect != 0)
1525 {
1526 if (data[j].mask)
1527 {
1528 vmin = max2f(vmin, step);
1529 }
1530 else
1531 {
1532 vmax = min2f(vmax, step);
1533 }
1534 if (vmin > vmax)
1535 {
1536 intersect = 0;
1537 }
1538 }
1539 }
1540 }
1541 else
1542 {
1543 if (tmp < 0.0f)
1544 {
1545 intersect = 0;
1546 }
1547 }
1548 }
1549 }
1550 intersects += intersect;
1551 }
1552 }
1553 if (intersects == 0)
1554 {
1555 return check_shadow_line_walk(bbox, frustum, light_dir, mask, hit);
1556 }
1557 else if (intersects == points) return INSIDE;
1558 else return INTERSECT;
1559 }
1560
check_shadow_line_walk_outside(const AABBOX bbox,const FRUSTUM frustum,const VECTOR3 light_dir,Uint32 mask,const float * hit)1561 static __inline__ int check_shadow_line_walk_outside(const AABBOX bbox, const FRUSTUM frustum, const VECTOR3 light_dir, Uint32 mask, const float* hit)
1562 {
1563 AABBOX tmp_bbox;
1564 VECTOR3 walk;
1565 int i, k;
1566
1567 if (check_aabb_outside_frustum(bbox, frustum, mask) != OUTSIDE) return INTERSECT;
1568
1569 for (i = 0, k = 1; k <= mask; i++, k += k)
1570 {
1571 if ((k & mask) && (hit[i] > 0.0f))
1572 {
1573 VScale(walk, light_dir, hit[i]);
1574 VAdd(tmp_bbox.bbmin, bbox.bbmin, walk);
1575 VAdd(tmp_bbox.bbmax, bbox.bbmax, walk);
1576 if (check_aabb_outside_frustum(tmp_bbox, frustum, mask) != OUTSIDE) return INTERSECT;
1577 }
1578 }
1579 return OUTSIDE;
1580 }
1581
check_shadow_lines_outside(const AABBOX bbox,const FRUSTUM frustum,const FRUSTUM_DATA data,const VECTOR3 light_dir,Uint32 mask,Uint32 point_mask)1582 static __inline__ int check_shadow_lines_outside(const AABBOX bbox, const FRUSTUM frustum, const FRUSTUM_DATA data, const VECTOR3 light_dir, Uint32 mask, Uint32 point_mask)
1583 {
1584 VECTOR3 _p;
1585 VECTOR4 p;
1586 float tmp, vmin, vmax, step, hit[16];
1587 int i, j, k, l, intersect;
1588
1589 memset(hit, 0, sizeof(hit));
1590
1591 for (i = 0, k = 1; k <= point_mask; i++, k += k)
1592 {
1593 if (k & point_mask)
1594 {
1595 get_point_from_aabbox(_p, bbox, i);
1596 VAssign4(p, _p, 1.0f);
1597 vmin = 0.0f;
1598 vmax = BOUND_HUGE;
1599 intersect = 1;
1600
1601 for (j = 0, l = 1; l <= mask; j++, l += l)
1602 {
1603 if (l & mask)
1604 {
1605 tmp = VDot4(p, frustum[j].plane);
1606
1607 if (data[j].zero == 0)
1608 {
1609 step = tmp/data[j].scale;
1610 if (step < 0.0f)
1611 {
1612 if (tmp < 0.0f)
1613 {
1614 intersect = 0;
1615 }
1616 }
1617 else
1618 {
1619 hit[j] = max2f(hit[j], step);
1620 if (intersect != 0)
1621 {
1622 if (data[j].mask)
1623 {
1624 vmin = max2f(vmin, step);
1625 }
1626 else
1627 {
1628 vmax = min2f(vmax, step);
1629 }
1630 if (vmin > vmax)
1631 {
1632 intersect = 0;
1633 }
1634 }
1635 }
1636 }
1637 else
1638 {
1639 if (tmp < 0.0f)
1640 {
1641 intersect = 0;
1642 }
1643 }
1644 }
1645 }
1646 if (intersect != 0) return INTERSECT;
1647 }
1648 }
1649 return check_shadow_line_walk_outside(bbox, frustum, light_dir, mask, hit);
1650 }
1651
add_dyn_items_shadow(BBOX_TREE * bbox_tree,Uint32 sub_node,const FRUSTUM frustum,Uint32 in_mask,const FRUSTUM view_frustum,const FRUSTUM_DATA data,const VECTOR3 light_dir,Uint32 mask,Uint32 point_mask)1652 static __inline__ void add_dyn_items_shadow(BBOX_TREE* bbox_tree, Uint32 sub_node, const FRUSTUM frustum, Uint32 in_mask,
1653 const FRUSTUM view_frustum, const FRUSTUM_DATA data, const VECTOR3 light_dir, Uint32 mask, Uint32 point_mask)
1654 {
1655 Uint32 idx, size, i;
1656
1657 idx = bbox_tree->cur_intersect_type;
1658 size = bbox_tree->nodes[sub_node].dynamic_objects.index;
1659
1660 for (i = 0; i < size; i++)
1661 {
1662 if (check_aabb_outside_frustum(bbox_tree->nodes[sub_node].dynamic_objects.items[i].bbox, frustum, in_mask) != OUTSIDE)
1663 {
1664 if (check_shadow_lines_outside(bbox_tree->nodes[sub_node].dynamic_objects.items[i].bbox, view_frustum, data, light_dir,
1665 mask, point_mask) != OUTSIDE)
1666 add_dyn_intersect_item(bbox_tree, sub_node, i, idx);
1667 }
1668 }
1669 }
1670
add_items_shadow(BBOX_TREE * bbox_tree,Uint32 sub_node,const FRUSTUM frustum,Uint32 in_mask,const FRUSTUM view_frustum,const FRUSTUM_DATA data,const VECTOR3 light_dir,Uint32 mask,Uint32 point_mask)1671 static __inline__ void add_items_shadow(BBOX_TREE* bbox_tree, Uint32 sub_node, const FRUSTUM frustum, Uint32 in_mask,
1672 const FRUSTUM view_frustum, const FRUSTUM_DATA data, const VECTOR3 light_dir, Uint32 mask, Uint32 point_mask)
1673 {
1674 Uint32 idx1, idx2, size, i;
1675
1676 idx1 = bbox_tree->cur_intersect_type;
1677 idx2 = bbox_tree->nodes[sub_node].items_index;
1678 size = bbox_tree->nodes[sub_node].items_count;
1679
1680 for (i = 0; i < size; i++)
1681 {
1682 if (check_aabb_outside_frustum(bbox_tree->items[idx2+i].bbox, frustum, in_mask) != OUTSIDE)
1683 {
1684 if (check_shadow_lines_outside(bbox_tree->items[idx2+i].bbox, view_frustum, data, light_dir, mask, point_mask) != OUTSIDE)
1685 add_intersect_item(bbox_tree, idx2+i, idx1);
1686 }
1687 }
1688 }
1689
check_sub_nodes_shadow(BBOX_TREE * bbox_tree,Uint32 sub_node,const FRUSTUM frustum,Uint32 in_mask,const FRUSTUM view_frustum,const FRUSTUM_DATA data,const VECTOR3 light_dir,Uint32 mask,Uint32 point_mask)1690 static __inline__ void check_sub_nodes_shadow(BBOX_TREE* bbox_tree, Uint32 sub_node, const FRUSTUM frustum, Uint32 in_mask,
1691 const FRUSTUM view_frustum, const FRUSTUM_DATA data, const VECTOR3 light_dir, Uint32 mask, Uint32 point_mask)
1692 {
1693 Uint32 out_mask, result;
1694
1695 if (sub_node != NO_INDEX)
1696 {
1697 result = check_aabb_in_frustum(bbox_tree->nodes[sub_node].bbox, frustum, in_mask, &out_mask);
1698
1699 if (result == OUTSIDE) return;
1700 result = check_shadow_lines(bbox_tree->nodes[sub_node].bbox, view_frustum, data, light_dir, mask, point_mask);
1701
1702 if (result == INSIDE)
1703 {
1704 add_intersect_items(bbox_tree, bbox_tree->nodes[sub_node].items_index, bbox_tree->nodes[sub_node].items_count);
1705 add_dyn_intersect_items(bbox_tree, sub_node, bbox_tree->nodes[sub_node].dynamic_objects.index);
1706 }
1707 else
1708 {
1709 if (result == INTERSECT)
1710 {
1711 add_dyn_items_shadow(bbox_tree, sub_node, frustum, out_mask, view_frustum, data, light_dir, mask, point_mask);
1712 if ( (bbox_tree->nodes[sub_node].nodes[0] == NO_INDEX) &&
1713 (bbox_tree->nodes[sub_node].nodes[1] == NO_INDEX))
1714 add_items_shadow(bbox_tree, sub_node, frustum, out_mask, view_frustum, data, light_dir, mask, point_mask);
1715 else
1716 {
1717 check_sub_nodes_shadow(bbox_tree, bbox_tree->nodes[sub_node].nodes[0], frustum, out_mask,
1718 view_frustum, data, light_dir, mask, point_mask);
1719 check_sub_nodes_shadow(bbox_tree, bbox_tree->nodes[sub_node].nodes[1], frustum, out_mask,
1720 view_frustum, data, light_dir, mask, point_mask);
1721 }
1722 }
1723 }
1724 }
1725 }
1726
calculate_point_mask(const VECTOR3 light_dir)1727 static __inline__ int calculate_point_mask(const VECTOR3 light_dir)
1728 {
1729 int mask, idx, i, k;
1730
1731 idx = 0;
1732
1733 if (VExtract(light_dir, X) >= 0.0f) idx += 1;
1734 if (VExtract(light_dir, Y) >= 0.0f) idx += 2;
1735 if (VExtract(light_dir, Z) >= 0.0f) idx += 4;
1736
1737 mask = 0;
1738
1739 for (i = 0, k = 1; i < 8; i++, k += k)
1740 {
1741 if ((i != idx) && (i != (7-idx))) mask |= k;
1742 }
1743
1744 return mask;
1745 }
1746
check_bbox_tree_shadow(BBOX_TREE * bbox_tree,const FRUSTUM frustum,Uint32 mask,const FRUSTUM view_frustum,Uint32 view_mask,const VECTOR3 light_dir)1747 void check_bbox_tree_shadow(BBOX_TREE* bbox_tree, const FRUSTUM frustum, Uint32 mask, const FRUSTUM view_frustum,
1748 Uint32 view_mask, const VECTOR3 light_dir)
1749 {
1750 Uint32 idx, point_mask;
1751 FRUSTUM_DATA data;
1752
1753 if (bbox_tree != NULL)
1754 {
1755 idx = bbox_tree->cur_intersect_type;
1756 if (idx != INTERSECTION_TYPE_SHADOW) return;
1757 if (bbox_tree->intersect[idx].intersect_update_needed > 0)
1758 {
1759 point_mask = calculate_point_mask(light_dir);
1760 calculate_frustum_data(data, view_frustum, light_dir, view_mask);
1761 bbox_tree->intersect[idx].count = 0;
1762 check_sub_nodes_shadow(bbox_tree, 0, frustum, mask, view_frustum, data, light_dir, view_mask, point_mask);
1763 qsort((void *)(bbox_tree->intersect[idx].items), bbox_tree->intersect[idx].count, sizeof(BBOX_ITEM), comp_items);
1764 build_start_stop(bbox_tree);
1765 bbox_tree->intersect[idx].intersect_update_needed = 0;
1766 }
1767 }
1768 else BBOX_TREE_LOG_INFO("bbox_tree");
1769 }
1770
set_frustum(BBOX_TREE * bbox_tree,const FRUSTUM frustum,Uint32 mask)1771 void set_frustum(BBOX_TREE* bbox_tree, const FRUSTUM frustum, Uint32 mask)
1772 {
1773 Uint32 idx;
1774
1775 if (bbox_tree != NULL)
1776 {
1777 idx = bbox_tree->cur_intersect_type;
1778 memcpy(bbox_tree->intersect[idx].frustum, frustum, sizeof(FRUSTUM));
1779 bbox_tree->intersect[idx].frustum_mask = mask;
1780 }
1781 else BBOX_TREE_LOG_INFO("bbox_tree");
1782 }
1783
reflection_portal_checks(BBOX_TREE * bbox_tree,const PLANE * portals,Uint32 count)1784 static __inline__ void reflection_portal_checks(BBOX_TREE* bbox_tree, const PLANE* portals, Uint32 count)
1785 {
1786 Uint32 i, j, idx;
1787 int start, stop;
1788
1789 idx = bbox_tree->cur_intersect_type;
1790
1791 for (i = 0; i < TYPES_COUNT; i++)
1792 {
1793 start = bbox_tree->intersect[idx].start[i];
1794 stop = bbox_tree->intersect[idx].stop[i];
1795 for (j = start; j < stop; j++)
1796 {
1797 if (check_aabb_inside_portals(bbox_tree->intersect[idx].items[j].bbox, portals, count) == 0)
1798 {
1799 bbox_tree->intersect[idx].items[j].type = TYPE_DELETED;
1800 }
1801 }
1802 }
1803 }
1804
reflection_portal_check(BBOX_TREE * bbox_tree,const PLANE * portals,Uint32 count)1805 void reflection_portal_check(BBOX_TREE* bbox_tree, const PLANE* portals, Uint32 count)
1806 {
1807 Uint32 idx;
1808
1809 if (bbox_tree != NULL)
1810 {
1811 idx = bbox_tree->cur_intersect_type;
1812 if (bbox_tree->intersect[idx].intersect_update_needed == 0)
1813 {
1814 reflection_portal_checks(bbox_tree, portals, count);
1815 qsort((void *)(bbox_tree->intersect[idx].items), bbox_tree->intersect[idx].count, sizeof(BBOX_ITEM), comp_items);
1816 build_start_stop(bbox_tree);
1817 bbox_tree->intersect[idx].intersect_update_needed = 0;
1818 }
1819 }
1820 else BBOX_TREE_LOG_INFO("bbox_tree");
1821 }
1822
1823