Merge branch 'master' into blender2.8

1 files changed, 38 insertions, 26 deletions

diff --git a/source/blender/blenlib/intern/BLI_kdopbvh.c b/source/blender/blenlib/intern/BLI_kdopbvh.c
index 19d9711922e..084ae4c222e 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}
 };
 
 
@@ -321,11 +321,16 @@ static int bvh_partition(BVHNode **a, int lo, int hi, BVHNode *x, int axis)
 {
 	int i = lo, j = hi;
 	while (1) {
-		while ((a[i])->bv[axis] < x->bv[axis]) i++;
+		while (a[i]->bv[axis] < x->bv[axis]) {
+			i++;
+		}
 		j--;
-		while (x->bv[axis] < (a[j])->bv[axis]) j--;
-		if (!(i < j))
+		while (x->bv[axis] < a[j]->bv[axis]) {
+			j--;
+		}
+		if (!(i < j)) {
 			return i;
+		}
 		SWAP(BVHNode *, a[i], a[j]);
 		i++;
 	}
@@ -427,19 +432,18 @@ static void sort_along_axis(BVHTree *tree, int start, int end, int axis)
  * \note after a call to this function you can expect one of:
  * - every node to left of a[n] are smaller or equal to it
  * - every node to the right of a[n] are greater or equal to it */
-static int partition_nth_element(BVHNode **a, int _begin, int _end, int n, int axis)
+static void partition_nth_element(BVHNode **a, int begin, int end, const int n, const int axis)
 {
-	int begin = _begin, end = _end, cut;
 	while (end - begin > 3) {
-		cut = bvh_partition(a, begin, end, bvh_medianof3(a, begin, (begin + end) / 2, end - 1, axis), axis);
-		if (cut <= n)
+		const int cut = bvh_partition(a, begin, end, bvh_medianof3(a, begin, (begin + end) / 2, end - 1, axis), axis);
+		if (cut <= n) {
 			begin = cut;
-		else
+		}
+		else {
 			end = cut;
+		}
 	}
 	bvh_insertionsort(a, begin, end, axis);
-
-	return n;
 }
 
 #ifdef USE_SKIP_LINKS
@@ -593,10 +597,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 +657,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 +721,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 +763,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 +1031,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 +1481,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");