Merge branch 'master' into temp-ghash-experimentstemp-ghash-experiments

Note that 'store hash' feature was removed for now - to complex to maintain (conflicts)
and relatively easy to re-add if we ever really want this one day.

Conflicts:
	source/blender/blenlib/BLI_ghash.h
	source/blender/blenlib/intern/BLI_ghash.c
	source/blender/blenlib/intern/hash_mm2a.c
	source/blender/bmesh/tools/bmesh_region_match.c
	tests/gtests/blenlib/BLI_ghash_performance_test.cc
	tests/gtests/blenlib/BLI_ghash_test.cc
	tests/gtests/blenlib/CMakeLists.txt

1 files changed, 45 insertions, 40 deletions

diff --git a/intern/cycles/bvh/bvh_build.cpp b/intern/cycles/bvh/bvh_build.cpp
index 4ce8f787169..a44ad656316 100644
--- a/intern/cycles/bvh/bvh_build.cpp
+++ b/intern/cycles/bvh/bvh_build.cpp
@@ -42,7 +42,7 @@ ccl_device_inline int bitscan(int value)
 {
 	assert(value != 0);
 	int bit = 0;
-	while (value >>= 1) {
+	while(value >>= 1) {
 		++bit;
 	}
 	return bit;
@@ -65,15 +65,18 @@ public:
 /* Constructor / Destructor */
 
 BVHBuild::BVHBuild(const vector<Object*>& objects_,
-	vector<int>& prim_type_, vector<int>& prim_index_, vector<int>& prim_object_,
-	const BVHParams& params_, Progress& progress_)
-: objects(objects_),
-  prim_type(prim_type_),
-  prim_index(prim_index_),
-  prim_object(prim_object_),
-  params(params_),
-  progress(progress_),
-  progress_start_time(0.0)
+                   array<int>& prim_type_,
+                   array<int>& prim_index_,
+                   array<int>& prim_object_,
+                   const BVHParams& params_,
+                   Progress& progress_)
+ : objects(objects_),
+   prim_type(prim_type_),
+   prim_index(prim_index_),
+   prim_object(prim_object_),
+   params(params_),
+   progress(progress_),
+   progress_start_time(0.0)
 {
 	spatial_min_overlap = 0.0f;
 }
@@ -136,7 +139,7 @@ void BVHBuild::add_reference_mesh(BoundBox& root, BoundBox& center, Mesh *mesh,
 				size_t steps = mesh->motion_steps - 1;
 				float4 *key_steps = curve_attr_mP->data_float4();
 
-				for (size_t i = 0; i < steps; i++)
+				for(size_t i = 0; i < steps; i++)
 					curve.bounds_grow(k, key_steps + i*mesh_size, bounds);
 
 				type = PRIMITIVE_MOTION_CURVE;
@@ -446,18 +449,10 @@ BVHNode *BVHBuild::create_object_leaf_nodes(const BVHReference *ref, int start,
 		return new LeafNode(bounds, 0, 0, 0);
 	}
 	else if(num == 1) {
-		if(start == prim_index.size()) {
-			assert(params.use_spatial_split);
-
-			prim_type.push_back(ref->prim_type());
-			prim_index.push_back(ref->prim_index());
-			prim_object.push_back(ref->prim_object());
-		}
-		else {
-			prim_type[start] = ref->prim_type();
-			prim_index[start] = ref->prim_index();
-			prim_object[start] = ref->prim_object();
-		}
+		assert(start < prim_type.size());
+		prim_type[start] = ref->prim_type();
+		prim_index[start] = ref->prim_index();
+		prim_object[start] = ref->prim_object();
 
 		uint visibility = objects[ref->prim_object()]->visibility;
 		return new LeafNode(ref->bounds(), visibility, start, start+1);
@@ -484,17 +479,9 @@ BVHNode *BVHBuild::create_primitive_leaf_node(const int *p_type,
                                               int num)
 {
 	for(int i = 0; i < num; ++i) {
-		if(start + i == prim_index.size()) {
-			assert(params.use_spatial_split);
-			prim_type.push_back(p_type[i]);
-			prim_index.push_back(p_index[i]);
-			prim_object.push_back(p_object[i]);
-		}
-		else {
-			prim_type[start + i] = p_type[i];
-			prim_index[start + i] = p_index[i];
-			prim_object[start + i] = p_object[i];
-		}
+		prim_type[start + i] = p_type[i];
+		prim_index[start + i] = p_index[i];
+		prim_object[start + i] = p_object[i];
 	}
 	return new LeafNode(bounds, visibility, start, start + num);
 }
@@ -535,6 +522,19 @@ BVHNode* BVHBuild::create_leaf_node(const BVHRange& range)
 		}
 	}
 
+	/* Extend an array when needed. */
+	if(prim_type.size() < range.end()) {
+		assert(params.use_spatial_split);
+		/* TODO(sergey): We might want to look into different policies of
+		 * re-allocation here, so on the one hand we would not do as much
+		 * re-allocations and on the other hand will have small memory
+		 * overhead.
+		 */
+		prim_type.resize(range.end());
+		prim_index.resize(range.end());
+		prim_object.resize(range.end());
+	}
+
 	/* Create leaf nodes for every existing primitive. */
 	BVHNode *leaves[PRIMITIVE_NUM_TOTAL + 1] = {NULL};
 	int num_leaves = 0;
@@ -577,17 +577,22 @@ BVHNode* BVHBuild::create_leaf_node(const BVHRange& range)
 		return new InnerNode(range.bounds(), leaves[0], leaves[1]);
 	}
 	else if(num_leaves == 3) {
-		BoundBox inner_bounds = merge(bounds[1], bounds[2]);
+		BoundBox inner_bounds = merge(leaves[1]->m_bounds, leaves[2]->m_bounds);
 		BVHNode *inner = new InnerNode(inner_bounds, leaves[1], leaves[2]);
 		return new InnerNode(range.bounds(), leaves[0], inner);
-	} else /*if(num_leaves == 4)*/ {
+	} else {
 		/* Shpuld be doing more branches if more primitive types added. */
-		assert(num_leaves == 4);
-		BoundBox inner_bounds_a = merge(bounds[0], bounds[1]);
-		BoundBox inner_bounds_b = merge(bounds[2], bounds[3]);
+		assert(num_leaves <= 5);
+		BoundBox inner_bounds_a = merge(leaves[0]->m_bounds, leaves[1]->m_bounds);
+		BoundBox inner_bounds_b = merge(leaves[2]->m_bounds, leaves[3]->m_bounds);
 		BVHNode *inner_a = new InnerNode(inner_bounds_a, leaves[0], leaves[1]);
 		BVHNode *inner_b = new InnerNode(inner_bounds_b, leaves[2], leaves[3]);
-		return new InnerNode(range.bounds(), inner_a, inner_b);
+		BoundBox inner_bounds_c = merge(inner_a->m_bounds, inner_b->m_bounds);
+		BVHNode *inner_c = new InnerNode(inner_bounds_c, inner_a, inner_b);
+		if(num_leaves == 5) {
+			return new InnerNode(range.bounds(), inner_c, leaves[4]);
+		}
+		return inner_c;
 	}
 }