1public:
2// cull parameters is a convenient way of passing a bunch
3// of arguments through the culling functions without
4// writing loads of code. Not all members are used for some cull checks
5struct CullParams {
6 int result_count_overall; // both trees
7 int result_count; // this tree only
8 int result_max;
9 T **result_array;
10 int *subindex_array;
11
12 // We now process masks etc in a user template function,
13 // and these for simplicity assume even for cull tests there is a
14 // testing object (which has masks etc) for the user cull checks.
15 // This means for cull tests on their own, the client will usually
16 // want to create a dummy object, just in order to specify masks etc.
17 const T *tester;
18
19 // optional components for different tests
20 POINT point;
21 BVHABB_CLASS abb;
22 typename BVHABB_CLASS::ConvexHull hull;
23 typename BVHABB_CLASS::Segment segment;
24
25 // When collision testing, we can specify which tree ids
26 // to collide test against with the tree_collision_mask.
27 uint32_t tree_collision_mask;
28};
29
30private:
31void _cull_translate_hits(CullParams &p) {
32 int num_hits = _cull_hits.size();
33 int left = p.result_max - p.result_count_overall;
34
35 if (num_hits > left) {
36 num_hits = left;
37 }
38
39 int out_n = p.result_count_overall;
40
41 for (int n = 0; n < num_hits; n++) {
42 uint32_t ref_id = _cull_hits[n];
43
44 const ItemExtra &ex = _extra[ref_id];
45 p.result_array[out_n] = ex.userdata;
46
47 if (p.subindex_array) {
48 p.subindex_array[out_n] = ex.subindex;
49 }
50
51 out_n++;
52 }
53
54 p.result_count = num_hits;
55 p.result_count_overall += num_hits;
56}
57
58public:
59int cull_convex(CullParams &r_params, bool p_translate_hits = true) {
60 _cull_hits.clear();
61 r_params.result_count = 0;
62
63 uint32_t tree_test_mask = 0;
64
65 for (int n = 0; n < NUM_TREES; n++) {
66 tree_test_mask <<= 1;
67 if (!tree_test_mask) {
68 tree_test_mask = 1;
69 }
70
71 if (_root_node_id[n] == BVHCommon::INVALID) {
72 continue;
73 }
74
75 if (!(r_params.tree_collision_mask & tree_test_mask)) {
76 continue;
77 }
78
79 _cull_convex_iterative(_root_node_id[n], r_params);
80 }
81
82 if (p_translate_hits) {
83 _cull_translate_hits(r_params);
84 }
85
86 return r_params.result_count;
87}
88
89int cull_segment(CullParams &r_params, bool p_translate_hits = true) {
90 _cull_hits.clear();
91 r_params.result_count = 0;
92
93 uint32_t tree_test_mask = 0;
94
95 for (int n = 0; n < NUM_TREES; n++) {
96 tree_test_mask <<= 1;
97 if (!tree_test_mask) {
98 tree_test_mask = 1;
99 }
100
101 if (_root_node_id[n] == BVHCommon::INVALID) {
102 continue;
103 }
104
105 if (!(r_params.tree_collision_mask & tree_test_mask)) {
106 continue;
107 }
108
109 _cull_segment_iterative(_root_node_id[n], r_params);
110 }
111
112 if (p_translate_hits) {
113 _cull_translate_hits(r_params);
114 }
115
116 return r_params.result_count;
117}
118
119int cull_point(CullParams &r_params, bool p_translate_hits = true) {
120 _cull_hits.clear();
121 r_params.result_count = 0;
122
123 uint32_t tree_test_mask = 0;
124
125 for (int n = 0; n < NUM_TREES; n++) {
126 tree_test_mask <<= 1;
127 if (!tree_test_mask) {
128 tree_test_mask = 1;
129 }
130
131 if (_root_node_id[n] == BVHCommon::INVALID) {
132 continue;
133 }
134
135 if (!(r_params.tree_collision_mask & tree_test_mask)) {
136 continue;
137 }
138
139 _cull_point_iterative(_root_node_id[n], r_params);
140 }
141
142 if (p_translate_hits) {
143 _cull_translate_hits(r_params);
144 }
145
146 return r_params.result_count;
147}
148
149int cull_aabb(CullParams &r_params, bool p_translate_hits = true) {
150 _cull_hits.clear();
151 r_params.result_count = 0;
152
153 uint32_t tree_test_mask = 0;
154
155 for (int n = 0; n < NUM_TREES; n++) {
156 tree_test_mask <<= 1;
157 if (!tree_test_mask) {
158 tree_test_mask = 1;
159 }
160
161 if (_root_node_id[n] == BVHCommon::INVALID) {
162 continue;
163 }
164
165 // the tree collision mask determines which trees to collide test against
166 if (!(r_params.tree_collision_mask & tree_test_mask)) {
167 continue;
168 }
169
170 _cull_aabb_iterative(_root_node_id[n], r_params);
171 }
172
173 if (p_translate_hits) {
174 _cull_translate_hits(r_params);
175 }
176
177 return r_params.result_count;
178}
179
180bool _cull_hits_full(const CullParams &p) {
181 // instead of checking every hit, we can do a lazy check for this condition.
182 // it isn't a problem if we write too much _cull_hits because they only the
183 // result_max amount will be translated and outputted. But we might as
184 // well stop our cull checks after the maximum has been reached.
185 return (int)_cull_hits.size() >= p.result_max;
186}
187
188void _cull_hit(uint32_t p_ref_id, CullParams &p) {
189 // take into account masks etc
190 // this would be more efficient to do before plane checks,
191 // but done here for ease to get started
192 if (USE_PAIRS) {
193 const ItemExtra &ex = _extra[p_ref_id];
194
195 // user supplied function (for e.g. pairable types and pairable masks in the render tree)
196 if (!USER_CULL_TEST_FUNCTION::user_cull_check(p.tester, ex.userdata)) {
197 return;
198 }
199 }
200
201 _cull_hits.push_back(p_ref_id);
202}
203
204bool _cull_segment_iterative(uint32_t p_node_id, CullParams &r_params) {
205 // our function parameters to keep on a stack
206 struct CullSegParams {
207 uint32_t node_id;
208 };
209
210 // most of the iterative functionality is contained in this helper class
211 BVH_IterativeInfo<CullSegParams> ii;
212
213 // alloca must allocate the stack from this function, it cannot be allocated in the
214 // helper class
215 ii.stack = (CullSegParams *)alloca(ii.get_alloca_stacksize());
216
217 // seed the stack
218 ii.get_first()->node_id = p_node_id;
219
220 CullSegParams csp;
221
222 // while there are still more nodes on the stack
223 while (ii.pop(csp)) {
224 TNode &tnode = _nodes[csp.node_id];
225
226 if (tnode.is_leaf()) {
227 // lazy check for hits full up condition
228 if (_cull_hits_full(r_params)) {
229 return false;
230 }
231
232 TLeaf &leaf = _node_get_leaf(tnode);
233
234 // test children individually
235 for (int n = 0; n < leaf.num_items; n++) {
236 const BVHABB_CLASS &aabb = leaf.get_aabb(n);
237
238 if (aabb.intersects_segment(r_params.segment)) {
239 uint32_t child_id = leaf.get_item_ref_id(n);
240
241 // register hit
242 _cull_hit(child_id, r_params);
243 }
244 }
245 } else {
246 // test children individually
247 for (int n = 0; n < tnode.num_children; n++) {
248 uint32_t child_id = tnode.children[n];
249 const BVHABB_CLASS &child_abb = _nodes[child_id].aabb;
250
251 if (child_abb.intersects_segment(r_params.segment)) {
252 // add to the stack
253 CullSegParams *child = ii.request();
254 child->node_id = child_id;
255 }
256 }
257 }
258
259 } // while more nodes to pop
260
261 // true indicates results are not full
262 return true;
263}
264
265bool _cull_point_iterative(uint32_t p_node_id, CullParams &r_params) {
266 // our function parameters to keep on a stack
267 struct CullPointParams {
268 uint32_t node_id;
269 };
270
271 // most of the iterative functionality is contained in this helper class
272 BVH_IterativeInfo<CullPointParams> ii;
273
274 // alloca must allocate the stack from this function, it cannot be allocated in the
275 // helper class
276 ii.stack = (CullPointParams *)alloca(ii.get_alloca_stacksize());
277
278 // seed the stack
279 ii.get_first()->node_id = p_node_id;
280
281 CullPointParams cpp;
282
283 // while there are still more nodes on the stack
284 while (ii.pop(cpp)) {
285 TNode &tnode = _nodes[cpp.node_id];
286 // no hit with this node?
287 if (!tnode.aabb.intersects_point(r_params.point)) {
288 continue;
289 }
290
291 if (tnode.is_leaf()) {
292 // lazy check for hits full up condition
293 if (_cull_hits_full(r_params)) {
294 return false;
295 }
296
297 TLeaf &leaf = _node_get_leaf(tnode);
298
299 // test children individually
300 for (int n = 0; n < leaf.num_items; n++) {
301 if (leaf.get_aabb(n).intersects_point(r_params.point)) {
302 uint32_t child_id = leaf.get_item_ref_id(n);
303
304 // register hit
305 _cull_hit(child_id, r_params);
306 }
307 }
308 } else {
309 // test children individually
310 for (int n = 0; n < tnode.num_children; n++) {
311 uint32_t child_id = tnode.children[n];
312
313 // add to the stack
314 CullPointParams *child = ii.request();
315 child->node_id = child_id;
316 }
317 }
318
319 } // while more nodes to pop
320
321 // true indicates results are not full
322 return true;
323}
324
325// Note: This is a very hot loop profiling wise. Take care when changing this and profile.
326bool _cull_aabb_iterative(uint32_t p_node_id, CullParams &r_params, bool p_fully_within = false) {
327 // our function parameters to keep on a stack
328 struct CullAABBParams {
329 uint32_t node_id;
330 bool fully_within;
331 };
332
333 // most of the iterative functionality is contained in this helper class
334 BVH_IterativeInfo<CullAABBParams> ii;
335
336 // alloca must allocate the stack from this function, it cannot be allocated in the
337 // helper class
338 ii.stack = (CullAABBParams *)alloca(ii.get_alloca_stacksize());
339
340 // seed the stack
341 ii.get_first()->node_id = p_node_id;
342 ii.get_first()->fully_within = p_fully_within;
343
344 CullAABBParams cap;
345
346 // while there are still more nodes on the stack
347 while (ii.pop(cap)) {
348 TNode &tnode = _nodes[cap.node_id];
349
350 if (tnode.is_leaf()) {
351 // lazy check for hits full up condition
352 if (_cull_hits_full(r_params)) {
353 return false;
354 }
355
356 TLeaf &leaf = _node_get_leaf(tnode);
357
358 // if fully within we can just add all items
359 // as long as they pass mask checks
360 if (cap.fully_within) {
361 for (int n = 0; n < leaf.num_items; n++) {
362 uint32_t child_id = leaf.get_item_ref_id(n);
363
364 // register hit
365 _cull_hit(child_id, r_params);
366 }
367 } else {
368 // This section is the hottest area in profiling, so
369 // is optimized highly
370 // get this into a local register and preconverted to correct type
371 int leaf_num_items = leaf.num_items;
372
373 BVHABB_CLASS swizzled_tester;
374 swizzled_tester.min = -r_params.abb.neg_max;
375 swizzled_tester.neg_max = -r_params.abb.min;
376
377 for (int n = 0; n < leaf_num_items; n++) {
378 const BVHABB_CLASS &aabb = leaf.get_aabb(n);
379
380 if (swizzled_tester.intersects_swizzled(aabb)) {
381 uint32_t child_id = leaf.get_item_ref_id(n);
382
383 // register hit
384 _cull_hit(child_id, r_params);
385 }
386 }
387
388 } // not fully within
389 } else {
390 if (!cap.fully_within) {
391 // test children individually
392 for (int n = 0; n < tnode.num_children; n++) {
393 uint32_t child_id = tnode.children[n];
394 const BVHABB_CLASS &child_abb = _nodes[child_id].aabb;
395
396 if (child_abb.intersects(r_params.abb)) {
397 // is the node totally within the aabb?
398 bool fully_within = r_params.abb.is_other_within(child_abb);
399
400 // add to the stack
401 CullAABBParams *child = ii.request();
402
403 // should always return valid child
404 child->node_id = child_id;
405 child->fully_within = fully_within;
406 }
407 }
408 } else {
409 for (int n = 0; n < tnode.num_children; n++) {
410 uint32_t child_id = tnode.children[n];
411
412 // add to the stack
413 CullAABBParams *child = ii.request();
414
415 // should always return valid child
416 child->node_id = child_id;
417 child->fully_within = true;
418 }
419 }
420 }
421
422 } // while more nodes to pop
423
424 // true indicates results are not full
425 return true;
426}
427
428// returns full up with results
429bool _cull_convex_iterative(uint32_t p_node_id, CullParams &r_params, bool p_fully_within = false) {
430 // our function parameters to keep on a stack
431 struct CullConvexParams {
432 uint32_t node_id;
433 bool fully_within;
434 };
435
436 // most of the iterative functionality is contained in this helper class
437 BVH_IterativeInfo<CullConvexParams> ii;
438
439 // alloca must allocate the stack from this function, it cannot be allocated in the
440 // helper class
441 ii.stack = (CullConvexParams *)alloca(ii.get_alloca_stacksize());
442
443 // seed the stack
444 ii.get_first()->node_id = p_node_id;
445 ii.get_first()->fully_within = p_fully_within;
446
447 // preallocate these as a once off to be reused
448 uint32_t max_planes = r_params.hull.num_planes;
449 uint32_t *plane_ids = (uint32_t *)alloca(sizeof(uint32_t) * max_planes);
450
451 CullConvexParams ccp;
452
453 // while there are still more nodes on the stack
454 while (ii.pop(ccp)) {
455 const TNode &tnode = _nodes[ccp.node_id];
456
457 if (!ccp.fully_within) {
458 typename BVHABB_CLASS::IntersectResult res = tnode.aabb.intersects_convex(r_params.hull);
459
460 switch (res) {
461 default: {
462 continue; // miss, just move on to the next node in the stack
463 } break;
464 case BVHABB_CLASS::IR_PARTIAL: {
465 } break;
466 case BVHABB_CLASS::IR_FULL: {
467 ccp.fully_within = true;
468 } break;
469 }
470
471 } // if not fully within already
472
473 if (tnode.is_leaf()) {
474 // lazy check for hits full up condition
475 if (_cull_hits_full(r_params)) {
476 return false;
477 }
478
479 const TLeaf &leaf = _node_get_leaf(tnode);
480
481 // if fully within, simply add all items to the result
482 // (taking into account masks)
483 if (ccp.fully_within) {
484 for (int n = 0; n < leaf.num_items; n++) {
485 uint32_t child_id = leaf.get_item_ref_id(n);
486
487 // register hit
488 _cull_hit(child_id, r_params);
489 }
490
491 } else {
492 // we can either use a naive check of all the planes against the AABB,
493 // or an optimized check, which finds in advance which of the planes can possibly
494 // cut the AABB, and only tests those. This can be much faster.
495#define BVH_CONVEX_CULL_OPTIMIZED
496#ifdef BVH_CONVEX_CULL_OPTIMIZED
497 // first find which planes cut the aabb
498 uint32_t num_planes = tnode.aabb.find_cutting_planes(r_params.hull, plane_ids);
499 BVH_ASSERT(num_planes <= max_planes);
500
501//#define BVH_CONVEX_CULL_OPTIMIZED_RIGOR_CHECK
502#ifdef BVH_CONVEX_CULL_OPTIMIZED_RIGOR_CHECK
503 // rigorous check
504 uint32_t results[MAX_ITEMS];
505 uint32_t num_results = 0;
506#endif
507
508 // test children individually
509 for (int n = 0; n < leaf.num_items; n++) {
510 //const Item &item = leaf.get_item(n);
511 const BVHABB_CLASS &aabb = leaf.get_aabb(n);
512
513 if (aabb.intersects_convex_optimized(r_params.hull, plane_ids, num_planes)) {
514 uint32_t child_id = leaf.get_item_ref_id(n);
515
516#ifdef BVH_CONVEX_CULL_OPTIMIZED_RIGOR_CHECK
517 results[num_results++] = child_id;
518#endif
519
520 // register hit
521 _cull_hit(child_id, r_params);
522 }
523 }
524
525#ifdef BVH_CONVEX_CULL_OPTIMIZED_RIGOR_CHECK
526 uint32_t test_count = 0;
527
528 for (int n = 0; n < leaf.num_items; n++) {
529 const BVHABB_CLASS &aabb = leaf.get_aabb(n);
530
531 if (aabb.intersects_convex_partial(r_params.hull)) {
532 uint32_t child_id = leaf.get_item_ref_id(n);
533
534 CRASH_COND(child_id != results[test_count++]);
535 CRASH_COND(test_count > num_results);
536 }
537 }
538#endif
539
540#else
541 // not BVH_CONVEX_CULL_OPTIMIZED
542 // test children individually
543 for (int n = 0; n < leaf.num_items; n++) {
544 const BVHABB_CLASS &aabb = leaf.get_aabb(n);
545
546 if (aabb.intersects_convex_partial(r_params.hull)) {
547 uint32_t child_id = leaf.get_item_ref_id(n);
548
549 // full up with results? exit early, no point in further testing
550 if (!_cull_hit(child_id, r_params)) {
551 return false;
552 }
553 }
554 }
555#endif // BVH_CONVEX_CULL_OPTIMIZED
556 } // if not fully within
557 } else {
558 for (int n = 0; n < tnode.num_children; n++) {
559 uint32_t child_id = tnode.children[n];
560
561 // add to the stack
562 CullConvexParams *child = ii.request();
563
564 // should always return valid child
565 child->node_id = child_id;
566 child->fully_within = ccp.fully_within;
567 }
568 }
569
570 } // while more nodes to pop
571
572 // true indicates results are not full
573 return true;
574}
575