diff options
Diffstat (limited to 'source/blender/blenlib/intern/BLI_kdopbvh.c')
-rw-r--r-- | source/blender/blenlib/intern/BLI_kdopbvh.c | 40 |
1 files changed, 24 insertions, 16 deletions
diff --git a/source/blender/blenlib/intern/BLI_kdopbvh.c b/source/blender/blenlib/intern/BLI_kdopbvh.c index 19d9711922e..8438f3ddf72 100644 --- a/source/blender/blenlib/intern/BLI_kdopbvh.c +++ b/source/blender/blenlib/intern/BLI_kdopbvh.c @@ -129,7 +129,7 @@ typedef struct BVHOverlapData_Thread { } BVHOverlapData_Thread; typedef struct BVHNearestData { - BVHTree *tree; + const BVHTree *tree; const float *co; BVHTree_NearestPointCallback callback; void *userdata; @@ -139,7 +139,7 @@ typedef struct BVHNearestData { } BVHNearestData; typedef struct BVHRayCastData { - BVHTree *tree; + const BVHTree *tree; BVHTree_RayCastCallback callback; void *userdata; @@ -171,9 +171,9 @@ typedef struct BVHRayCastData { */ const float bvhtree_kdop_axes[13][3] = { - {1.0, 0, 0}, {0, 1.0, 0}, {0, 0, 1.0}, {1.0, 1.0, 1.0}, {1.0, -1.0, 1.0}, {1.0, 1.0, -1.0}, - {1.0, -1.0, -1.0}, {1.0, 1.0, 0}, {1.0, 0, 1.0}, {0, 1.0, 1.0}, {1.0, -1.0, 0}, {1.0, 0, -1.0}, - {0, 1.0, -1.0} + {1.0, 0, 0}, {0, 1.0, 0}, {0, 0, 1.0}, + {1.0, 1.0, 1.0}, {1.0, -1.0, 1.0}, {1.0, 1.0, -1.0}, {1.0, -1.0, -1.0}, + {1.0, 1.0, 0}, {1.0, 0, 1.0}, {0, 1.0, 1.0}, {1.0, -1.0, 0}, {1.0, 0, -1.0}, {0, 1.0, -1.0} }; @@ -593,10 +593,14 @@ static void bvhtree_print_tree(BVHTree *tree, BVHNode *node, int depth) static void bvhtree_info(BVHTree *tree) { printf("BVHTree info\n"); - printf("tree_type = %d, axis = %d, epsilon = %f\n", tree->tree_type, tree->axis, tree->epsilon); - printf("nodes = %d, branches = %d, leafs = %d\n", tree->totbranch + tree->totleaf, tree->totbranch, tree->totleaf); - printf("Memory per node = %ldbytes\n", sizeof(BVHNode) + sizeof(BVHNode *) * tree->tree_type + sizeof(float) * tree->axis); - printf("BV memory = %dbytes\n", (int)MEM_allocN_len(tree->nodebv)); + printf("tree_type = %d, axis = %d, epsilon = %f\n", + tree->tree_type, tree->axis, tree->epsilon); + printf("nodes = %d, branches = %d, leafs = %d\n", + tree->totbranch + tree->totleaf, tree->totbranch, tree->totleaf); + printf("Memory per node = %ldbytes\n", + sizeof(BVHNode) + sizeof(BVHNode *) * tree->tree_type + sizeof(float) * tree->axis); + printf("BV memory = %dbytes\n", + (int)MEM_allocN_len(tree->nodebv)); printf("Total memory = %ldbytes\n", sizeof(BVHTree) + MEM_allocN_len(tree->nodes) + @@ -649,12 +653,14 @@ static void verify_tree(BVHTree *tree) } } - printf("branches: %d, leafs: %d, total: %d\n", tree->totbranch, tree->totleaf, tree->totbranch + tree->totleaf); + printf("branches: %d, leafs: %d, total: %d\n", + tree->totbranch, tree->totleaf, tree->totbranch + tree->totleaf); } #endif /* Helper data and structures to build a min-leaf generalized implicit tree - * This code can be easily reduced (basicly this is only method to calculate pow(k, n) in O(1).. and stuff like that) */ + * This code can be easily reduced + * (basicly this is only method to calculate pow(k, n) in O(1).. and stuff like that) */ typedef struct BVHBuildHelper { int tree_type; /* */ int totleafs; /* */ @@ -711,8 +717,8 @@ static int implicit_leafs_index(BVHBuildHelper *data, int depth, int child_index * Generalized implicit tree build * * An implicit tree is a tree where its structure is implied, thus there is no need to store child pointers or indexs. - * Its possible to find the position of the child or the parent with simple maths (multiplication and adittion). This type - * of tree is for example used on heaps.. where node N has its childs at indexs N*2 and N*2+1. + * Its possible to find the position of the child or the parent with simple maths (multiplication and adittion). + * This type of tree is for example used on heaps.. where node N has its childs at indexs N*2 and N*2+1. * * Although in this case the tree type is general.. and not know until runtime. * tree_type stands for the maximum number of childs that a tree node can have. @@ -753,7 +759,7 @@ static int implicit_needed_branches(int tree_type, int leafs) * * TODO: This can be optimized a bit by doing a specialized nth_element instead of K nth_elements */ -static void split_leafs(BVHNode **leafs_array, int *nth, int partitions, int split_axis) +static void split_leafs(BVHNode **leafs_array, const int nth[], const int partitions, const int split_axis) { int i; for (i = 0; i < partitions - 1; i++) { @@ -1021,7 +1027,8 @@ void BLI_bvhtree_balance(BVHTree *tree) BVHNode *branches_array = tree->nodearray + tree->totleaf; BVHNode **leafs_array = tree->nodes; - /* This function should only be called once (some big bug goes here if its being called more than once per tree) */ + /* This function should only be called once + * (some big bug goes here if its being called more than once per tree) */ BLI_assert(tree->totbranch == 0); /* Build the implicit tree */ @@ -1470,7 +1477,8 @@ static void bfs_find_nearest(BVHNearestData *data, BVHNode *node) else { /* adjust heap size */ if ((heap_size >= max_heap_size) && - ADJUST_MEMORY(default_heap, (void **)&heap, heap_size + 1, &max_heap_size, sizeof(heap[0])) == false) + ADJUST_MEMORY(default_heap, (void **)&heap, + heap_size + 1, &max_heap_size, sizeof(heap[0])) == false) { printf("WARNING: bvh_find_nearest got out of memory\n"); |