diff options
author | Campbell Barton <ideasman42@gmail.com> | 2015-08-20 08:56:33 +0300 |
---|---|---|
committer | Campbell Barton <ideasman42@gmail.com> | 2015-08-20 09:31:05 +0300 |
commit | e9f432f73c164f1698381111255523ae99879b5f (patch) | |
tree | 0d99b18f2bf0f4373aa82349c087e691e607735a /source/blender | |
parent | 6b53b4afb9cb2f334ca4503f05b02e7acc5f68e5 (diff) |
BVH-overlap: use stack for overlap data array
This is known to be <32, so no need to malloc every item.
Diffstat (limited to 'source/blender')
-rw-r--r-- | source/blender/blenlib/intern/BLI_kdopbvh.c | 75 |
1 files changed, 33 insertions, 42 deletions
diff --git a/source/blender/blenlib/intern/BLI_kdopbvh.c b/source/blender/blenlib/intern/BLI_kdopbvh.c index 295879f4f5e..790a7879403 100644 --- a/source/blender/blenlib/intern/BLI_kdopbvh.c +++ b/source/blender/blenlib/intern/BLI_kdopbvh.c @@ -44,6 +44,7 @@ #include "MEM_guardedalloc.h" #include "BLI_utildefines.h" +#include "BLI_alloca.h" #include "BLI_stack.h" #include "BLI_kdopbvh.h" #include "BLI_math.h" @@ -1042,30 +1043,27 @@ float BLI_bvhtree_getepsilon(const BVHTree *tree) /** * overlap - is it possible for 2 bv's to collide ? */ -static int tree_overlap(BVHNode *node1, BVHNode *node2, axis_t start_axis, axis_t stop_axis) +static bool tree_overlap_test(const BVHNode *node1, const BVHNode *node2, axis_t start_axis, axis_t stop_axis) { - const float *bv1 = node1->bv; - const float *bv2 = node2->bv; - - const float *bv1_end = bv1 + (stop_axis << 1); - - bv1 += start_axis << 1; - bv2 += start_axis << 1; + const float *bv1 = node1->bv + (start_axis << 1); + const float *bv2 = node2->bv + (start_axis << 1); + const float *bv1_end = node1->bv + (stop_axis << 1); /* test all axis if min + max overlap */ for (; bv1 != bv1_end; bv1 += 2, bv2 += 2) { - if ((*(bv1) > *(bv2 + 1)) || (*(bv2) > *(bv1 + 1))) + if ((bv1[0] > bv2[1]) || (bv2[0] > bv1[1])) { return 0; + } } return 1; } -static void traverse(BVHOverlapData *data, BVHNode *node1, BVHNode *node2) +static void tree_overlap_traverse(BVHOverlapData *data, const BVHNode *node1, const BVHNode *node2) { int j; - if (tree_overlap(node1, node2, data->start_axis, data->stop_axis)) { + if (tree_overlap_test(node1, node2, data->start_axis, data->stop_axis)) { /* check if node1 is a leaf */ if (!node1->totnode) { /* check if node2 is a leaf */ @@ -1084,14 +1082,14 @@ static void traverse(BVHOverlapData *data, BVHNode *node1, BVHNode *node2) else { for (j = 0; j < data->tree2->tree_type; j++) { if (node2->children[j]) - traverse(data, node1, node2->children[j]); + tree_overlap_traverse(data, node1, node2->children[j]); } } } else { for (j = 0; j < data->tree2->tree_type; j++) { if (node1->children[j]) - traverse(data, node1->children[j], node2); + tree_overlap_traverse(data, node1->children[j], node2); } } } @@ -1100,10 +1098,12 @@ static void traverse(BVHOverlapData *data, BVHNode *node1, BVHNode *node2) BVHTreeOverlap *BLI_bvhtree_overlap(BVHTree *tree1, BVHTree *tree2, unsigned int *r_overlap_tot) { - int j; + const unsigned int tree_type = (unsigned int)tree1->tree_type; + unsigned int j; size_t total = 0; BVHTreeOverlap *overlap = NULL, *to = NULL; - BVHOverlapData **data; + BVHOverlapData *data = BLI_array_alloca(data, tree_type); + axis_t start_axis, stop_axis; /* check for compatibility of both trees (can't compare 14-DOP with 18-DOP) */ if (UNLIKELY((tree1->axis != tree2->axis) && @@ -1113,50 +1113,41 @@ BVHTreeOverlap *BLI_bvhtree_overlap(BVHTree *tree1, BVHTree *tree2, unsigned int BLI_assert(0); return NULL; } + + start_axis = min_axis(tree1->start_axis, tree2->start_axis); + stop_axis = min_axis(tree1->stop_axis, tree2->stop_axis); /* fast check root nodes for collision before doing big splitting + traversal */ - if (!tree_overlap(tree1->nodes[tree1->totleaf], tree2->nodes[tree2->totleaf], - min_axis(tree1->start_axis, tree2->start_axis), - min_axis(tree1->stop_axis, tree2->stop_axis))) - { + if (!tree_overlap_test(tree1->nodes[tree1->totleaf], tree2->nodes[tree2->totleaf], start_axis, stop_axis)) { return NULL; } - data = MEM_mallocN(sizeof(BVHOverlapData *) * tree1->tree_type, "BVHOverlapData_star"); - - for (j = 0; j < tree1->tree_type; j++) { - data[j] = MEM_mallocN(sizeof(BVHOverlapData), "BVHOverlapData"); - + for (j = 0; j < tree_type; j++) { /* init BVHOverlapData */ - data[j]->overlap = BLI_stack_new(sizeof(BVHTreeOverlap), __func__); - data[j]->tree1 = tree1; - data[j]->tree2 = tree2; - data[j]->start_axis = min_axis(tree1->start_axis, tree2->start_axis); - data[j]->stop_axis = min_axis(tree1->stop_axis, tree2->stop_axis); + data[j].tree1 = tree1; + data[j].tree2 = tree2; + data[j].overlap = BLI_stack_new(sizeof(BVHTreeOverlap), __func__); + data[j].start_axis = start_axis; + data[j].stop_axis = stop_axis; } #pragma omp parallel for private(j) schedule(static) if (tree1->totleaf > KDOPBVH_OMP_LIMIT) for (j = 0; j < MIN2(tree1->tree_type, tree1->nodes[tree1->totleaf]->totnode); j++) { - traverse(data[j], tree1->nodes[tree1->totleaf]->children[j], tree2->nodes[tree2->totleaf]); + tree_overlap_traverse(&data[j], tree1->nodes[tree1->totleaf]->children[j], tree2->nodes[tree2->totleaf]); } - for (j = 0; j < tree1->tree_type; j++) - total += BLI_stack_count(data[j]->overlap); + for (j = 0; j < tree_type; j++) + total += BLI_stack_count(data[j].overlap); to = overlap = MEM_mallocN(sizeof(BVHTreeOverlap) * total, "BVHTreeOverlap"); - for (j = 0; j < tree1->tree_type; j++) { - unsigned int count = (unsigned int)BLI_stack_count(data[j]->overlap); - BLI_stack_pop_n(data[j]->overlap, to, count); - BLI_stack_free(data[j]->overlap); + for (j = 0; j < tree_type; j++) { + unsigned int count = (unsigned int)BLI_stack_count(data[j].overlap); + BLI_stack_pop_n(data[j].overlap, to, count); + BLI_stack_free(data[j].overlap); to += count; } - - for (j = 0; j < tree1->tree_type; j++) { - MEM_freeN(data[j]); - } - MEM_freeN(data); - + *r_overlap_tot = (unsigned int)total; return overlap; } |