Cycles: Make BVH wider prior to packing

This allows to do more non-trivial tree modifications to make
it more dense and more friendly for vectorization.

12 files changed, 331 insertions, 254 deletions

diff --git a/intern/cycles/bvh/bvh.cpp b/intern/cycles/bvh/bvh.cpp
index ac0614e3659..af012bbf3ac 100644
--- a/intern/cycles/bvh/bvh.cpp
+++ b/intern/cycles/bvh/bvh.cpp
@@ -127,10 +127,26 @@ void BVH::build(Progress& progress, Stats*)
 	                   pack.prim_time,
 	                   params,
 	                   progress);
-	BVHNode *root = bvh_build.run();
+	BVHNode *bvh2_root = bvh_build.run();
 
 	if(progress.get_cancel()) {
-		if(root) root->deleteSubtree();
+		if(bvh2_root != NULL) {
+			bvh2_root->deleteSubtree();
+		}
+		return;
+	}
+
+	/* BVH builder returns tree in a binary mode (with two children per inner
+	 * node. Need to adopt that for a wider BVH implementations. */
+	BVHNode *root = widen_children_nodes(bvh2_root);
+	if(root != bvh2_root) {
+		bvh2_root->deleteSubtree();
+	}
+
+	if(progress.get_cancel()) {
+		if(root != NULL) {
+			root->deleteSubtree();
+		}
 		return;
 	}
 
@@ -232,37 +248,6 @@ void BVH::refit_primitives(int start, int end, BoundBox& bbox, uint& visibility)
 	}
 }
 
-bool BVH::leaf_check(const BVHNode *node, BVH_TYPE bvh)
-{
-	if(node->is_leaf()) {
-		return node->is_unaligned;
-	}
-	else {
-		return node_is_unaligned(node, bvh);
-	}
-}
-
-bool BVH::node_is_unaligned(const BVHNode *node, BVH_TYPE bvh)
-{
-	const BVHNode *node0 = node->get_child(0);
-	const BVHNode *node1 = node->get_child(1);
-
-	switch(bvh) {
-		case bvh2:
-			return node0->is_unaligned || node1->is_unaligned;
-			break;
-		case bvh4:
-			return leaf_check(node0, bvh2) || leaf_check(node1, bvh2);
-			break;
-		case bvh8:
-			return leaf_check(node0, bvh4) || leaf_check(node1, bvh4);
-			break;
-		default:
-			assert(0);
-			return false;
-	}
-}
-
 /* Triangles */
 
 void BVH::pack_triangle(int idx, float4 tri_verts[3])
diff --git a/intern/cycles/bvh/bvh.h b/intern/cycles/bvh/bvh.h
index c8ad29004d7..33a069eeaf5 100644
--- a/intern/cycles/bvh/bvh.h
+++ b/intern/cycles/bvh/bvh.h
@@ -99,8 +99,6 @@ protected:
 
 	/* Refit range of primitives. */
 	void refit_primitives(int start, int end, BoundBox& bbox, uint& visibility);
-	static __forceinline bool leaf_check(const BVHNode *node, BVH_TYPE bvh);
-	static bool node_is_unaligned(const BVHNode *node, BVH_TYPE bvh);
 
 	/* triangles and strands */
 	void pack_primitives();
@@ -112,6 +110,8 @@ protected:
 	/* for subclasses to implement */
 	virtual void pack_nodes(const BVHNode *root) = 0;
 	virtual void refit_nodes() = 0;
+
+	virtual BVHNode *widen_children_nodes(const BVHNode *root) = 0;
 };
 
 /* Pack Utility */
diff --git a/intern/cycles/bvh/bvh2.cpp b/intern/cycles/bvh/bvh2.cpp
index 4a423c16559..e5dc4e6b1a8 100644
--- a/intern/cycles/bvh/bvh2.cpp
+++ b/intern/cycles/bvh/bvh2.cpp
@@ -30,6 +30,11 @@ BVH2::BVH2(const BVHParams& params_, const vector<Object*>& objects_)
 {
 }
 
+BVHNode *BVH2::widen_children_nodes(const BVHNode *root)
+{
+	return const_cast<BVHNode *>(root);
+}
+
 void BVH2::pack_leaf(const BVHStackEntry& e,
                      const LeafNode *leaf)
 {
@@ -188,9 +193,8 @@ void BVH2::pack_nodes(const BVHNode *root)
 	}
 	else {
 		stack.push_back(BVHStackEntry(root, nextNodeIdx));
-		nextNodeIdx += node_is_unaligned(root, bvh2)
-		                       ? BVH_UNALIGNED_NODE_SIZE
-		                       : BVH_NODE_SIZE;
+		nextNodeIdx += root->has_unaligned() ? BVH_UNALIGNED_NODE_SIZE
+		                                     : BVH_NODE_SIZE;
 	}
 
 	while(stack.size()) {
@@ -203,7 +207,7 @@ void BVH2::pack_nodes(const BVHNode *root)
 			pack_leaf(e, leaf);
 		}
 		else {
-			/* innner node */
+			/* inner node */
 			int idx[2];
 			for(int i = 0; i < 2; ++i) {
 				if(e.node->get_child(i)->is_leaf()) {
@@ -211,7 +215,7 @@ void BVH2::pack_nodes(const BVHNode *root)
 				}
 				else {
 					idx[i] = nextNodeIdx;
-					nextNodeIdx += node_is_unaligned(e.node->get_child(i), bvh2)
+					nextNodeIdx += e.node->get_child(i)->has_unaligned()
 					                       ? BVH_UNALIGNED_NODE_SIZE
 					                       : BVH_NODE_SIZE;
 				}
diff --git a/intern/cycles/bvh/bvh2.h b/intern/cycles/bvh/bvh2.h
index ecc697567bb..f38cdf5aca9 100644
--- a/intern/cycles/bvh/bvh2.h
+++ b/intern/cycles/bvh/bvh2.h
@@ -48,6 +48,9 @@ protected:
 	friend class BVH;
 	BVH2(const BVHParams& params, const vector<Object*>& objects);
 
+	/* Building process. */
+	virtual BVHNode *widen_children_nodes(const BVHNode *root) override;
+
 	/* pack */
 	void pack_nodes(const BVHNode *root);
 
diff --git a/intern/cycles/bvh/bvh4.cpp b/intern/cycles/bvh/bvh4.cpp
index a449587e607..a7c4cea85ce 100644
--- a/intern/cycles/bvh/bvh4.cpp
+++ b/intern/cycles/bvh/bvh4.cpp
@@ -37,6 +37,68 @@ BVH4::BVH4(const BVHParams& params_, const vector<Object*>& objects_)
 	params.bvh_layout = BVH_LAYOUT_BVH4;
 }
 
+namespace {
+
+BVHNode *bvh_node_merge_children_recursively(const BVHNode *node)
+{
+	if(node->is_leaf()) {
+		return new LeafNode(*reinterpret_cast<const LeafNode *>(node));
+	}
+	/* Collect nodes of one layer deeper, allowing us to have more childrem in
+	 * an inner layer. */
+	assert(node->num_children() <= 2);
+	const BVHNode *children[4];
+	const BVHNode *child0 = node->get_child(0);
+	const BVHNode *child1 = node->get_child(1);
+	int num_children = 0;
+	if(child0->is_leaf()) {
+		children[num_children++] = child0;
+	}
+	else {
+		children[num_children++] = child0->get_child(0);
+		children[num_children++] = child0->get_child(1);
+	}
+	if(child1->is_leaf()) {
+		children[num_children++] = child1;
+	}
+	else {
+		children[num_children++] = child1->get_child(0);
+		children[num_children++] = child1->get_child(1);
+	}
+	/* Merge children in subtrees. */
+	BVHNode *children4[4];
+	for(int i = 0; i < num_children; ++i) {
+		children4[i] = bvh_node_merge_children_recursively(children[i]);
+	}
+	/* Allocate new node. */
+	BVHNode *node4 = new InnerNode(node->bounds, children4, num_children);
+	/* TODO(sergey): Consider doing this from the InnerNode() constructor.
+	 * But in order to do this nicely need to think of how to pass all the
+	 * parameters there. */
+	if(node->is_unaligned) {
+		node4->is_unaligned = true;
+		node4->aligned_space = new Transform();
+		*node4->aligned_space = *node->aligned_space;
+	}
+	return node4;
+}
+
+}  // namespace
+
+BVHNode *BVH4::widen_children_nodes(const BVHNode *root)
+{
+	if(root == NULL) {
+		return NULL;
+	}
+	if(root->is_leaf()) {
+		return const_cast<BVHNode *>(root);
+	}
+	BVHNode *root4 = bvh_node_merge_children_recursively(root);
+	/* TODO(sergey): Pack children nodes to parents which has less that 4
+	 * children. */
+	return root4;
+}
+
 void BVH4::pack_leaf(const BVHStackEntry& e, const LeafNode *leaf)
 {
 	float4 data[BVH_QNODE_LEAF_SIZE];
@@ -248,14 +310,14 @@ void BVH4::pack_unaligned_node(int idx,
 void BVH4::pack_nodes(const BVHNode *root)
 {
 	/* Calculate size of the arrays required. */
-	const size_t num_nodes = root->getSubtreeSize(BVH_STAT_QNODE_COUNT);
+	const size_t num_nodes = root->getSubtreeSize(BVH_STAT_NODE_COUNT);
 	const size_t num_leaf_nodes = root->getSubtreeSize(BVH_STAT_LEAF_COUNT);
 	assert(num_leaf_nodes <= num_nodes);
 	const size_t num_inner_nodes = num_nodes - num_leaf_nodes;
 	size_t node_size;
 	if(params.use_unaligned_nodes) {
 		const size_t num_unaligned_nodes =
-		        root->getSubtreeSize(BVH_STAT_UNALIGNED_INNER_QNODE_COUNT);
+		        root->getSubtreeSize(BVH_STAT_UNALIGNED_INNER_COUNT);
 		node_size = (num_unaligned_nodes * BVH_UNALIGNED_QNODE_SIZE) +
 		            (num_inner_nodes - num_unaligned_nodes) * BVH_QNODE_SIZE;
 	}
@@ -283,9 +345,8 @@ void BVH4::pack_nodes(const BVHNode *root)
 	}
 	else {
 		stack.push_back(BVHStackEntry(root, nextNodeIdx));
-		nextNodeIdx += node_is_unaligned(root, bvh4)
-		                       ? BVH_UNALIGNED_QNODE_SIZE
-		                       : BVH_QNODE_SIZE;
+		nextNodeIdx += root->has_unaligned() ? BVH_UNALIGNED_QNODE_SIZE
+		                                     : BVH_QNODE_SIZE;
 	}
 
 	while(stack.size()) {
@@ -299,44 +360,30 @@ void BVH4::pack_nodes(const BVHNode *root)
 		}
 		else {
 			/* Inner node. */
-			const BVHNode *node = e.node;
-			const BVHNode *node0 = node->get_child(0);
-			const BVHNode *node1 = node->get_child(1);
 			/* Collect nodes. */
-			const BVHNode *nodes[4];
-			int numnodes = 0;
-			if(node0->is_leaf()) {
-				nodes[numnodes++] = node0;
-			}
-			else {
-				nodes[numnodes++] = node0->get_child(0);
-				nodes[numnodes++] = node0->get_child(1);
-			}
-			if(node1->is_leaf()) {
-				nodes[numnodes++] = node1;
-			}
-			else {
-				nodes[numnodes++] = node1->get_child(0);
-				nodes[numnodes++] = node1->get_child(1);
-			}
+			const BVHNode *children[4];
+			const int num_children = e.node->num_children();
 			/* Push entries on the stack. */
-			for(int i = 0; i < numnodes; ++i) {
+			for(int i = 0; i < num_children; ++i) {
 				int idx;
-				if(nodes[i]->is_leaf()) {
+				children[i] = e.node->get_child(i);
+				assert(children[i] != NULL);
+				if(children[i]->is_leaf()) {
 					idx = nextLeafNodeIdx++;
 				}
 				else {
 					idx = nextNodeIdx;
-					nextNodeIdx += node_is_unaligned(nodes[i], bvh4)
+					nextNodeIdx += children[i]->has_unaligned()
 					                       ? BVH_UNALIGNED_QNODE_SIZE
 					                       : BVH_QNODE_SIZE;
 				}
-				stack.push_back(BVHStackEntry(nodes[i], idx));
+				stack.push_back(BVHStackEntry(children[i], idx));
 			}
 			/* Set node. */
-			pack_inner(e, &stack[stack.size()-numnodes], numnodes);
+			pack_inner(e, &stack[stack.size() - num_children], num_children);
 		}
 	}
+
 	assert(node_size == nextNodeIdx);
 	/* Root index to start traversal at, to handle case of single leaf node. */
 	pack.root_index = (root->is_leaf())? -1: 0;
diff --git a/intern/cycles/bvh/bvh4.h b/intern/cycles/bvh/bvh4.h
index 28bab2fe327..2a2a466c767 100644
--- a/intern/cycles/bvh/bvh4.h
+++ b/intern/cycles/bvh/bvh4.h
@@ -48,6 +48,9 @@ protected:
 	friend class BVH;
 	BVH4(const BVHParams& params, const vector<Object*>& objects);
 
+	/* Building process. */
+	virtual BVHNode *widen_children_nodes(const BVHNode *root) override;
+
 	/* pack */
 	void pack_nodes(const BVHNode *root);
 
diff --git a/intern/cycles/bvh/bvh8.cpp b/intern/cycles/bvh/bvh8.cpp
index b95fe572e27..af930b2f2df 100644
--- a/intern/cycles/bvh/bvh8.cpp
+++ b/intern/cycles/bvh/bvh8.cpp
@@ -41,6 +41,96 @@ BVH8::BVH8(const BVHParams& params_, const vector<Object*>& objects_)
 {
 }
 
+namespace {
+
+BVHNode *bvh_node_merge_children_recursively(const BVHNode *node)
+{
+	if(node->is_leaf()) {
+		return new LeafNode(*reinterpret_cast<const LeafNode *>(node));
+	}
+	/* Collect nodes of two layer deeper, allowing us to have more childrem in
+	 * an inner layer. */
+	assert(node->num_children() <= 2);
+	const BVHNode *children[8];
+	const BVHNode *child0 = node->get_child(0);
+	const BVHNode *child1 = node->get_child(1);
+	int num_children = 0;
+	if(child0->is_leaf()) {
+		children[num_children++] = child0;
+	}
+	else {
+		const BVHNode *child00 = child0->get_child(0),
+		              *child01 = child0->get_child(1);
+		if(child00->is_leaf()) {
+			children[num_children++] = child00;
+		}
+		else {
+			children[num_children++] = child00->get_child(0);
+			children[num_children++] = child00->get_child(1);
+		}
+		if(child01->is_leaf()) {
+			children[num_children++] = child01;
+		}
+		else {
+			children[num_children++] = child01->get_child(0);
+			children[num_children++] = child01->get_child(1);
+		}
+	}
+	if(child1->is_leaf()) {
+		children[num_children++] = child1;
+	}
+	else {
+		const BVHNode *child10 = child1->get_child(0),
+		              *child11 = child1->get_child(1);
+		if(child10->is_leaf()) {
+			children[num_children++] = child10;
+		}
+		else {
+			children[num_children++] = child10->get_child(0);
+			children[num_children++] = child10->get_child(1);
+		}
+		if(child11->is_leaf()) {
+			children[num_children++] = child11;
+		}
+		else {
+			children[num_children++] = child11->get_child(0);
+			children[num_children++] = child11->get_child(1);
+		}
+	}
+	/* Merge children in subtrees. */
+	BVHNode *children4[8];
+	for(int i = 0; i < num_children; ++i) {
+		children4[i] = bvh_node_merge_children_recursively(children[i]);
+	}
+	/* Allocate new node. */
+	BVHNode *node8 = new InnerNode(node->bounds, children4, num_children);
+	/* TODO(sergey): Consider doing this from the InnerNode() constructor.
+	 * But in order to do this nicely need to think of how to pass all the
+	 * parameters there. */
+	if(node->is_unaligned) {
+		node8->is_unaligned = true;
+		node8->aligned_space = new Transform();
+		*node8->aligned_space = *node->aligned_space;
+	}
+	return node8;
+}
+
+}  // namespace
+
+BVHNode *BVH8::widen_children_nodes(const BVHNode *root)
+{
+	if(root == NULL) {
+		return NULL;
+	}
+	if(root->is_leaf()) {
+		return const_cast<BVHNode *>(root);
+	}
+	BVHNode *root8 = bvh_node_merge_children_recursively(root);
+	/* TODO(sergey): Pack children nodes to parents which has less that 4
+	 * children. */
+	return root8;
+}
+
 void BVH8::pack_leaf(const BVHStackEntry& e, const LeafNode *leaf)
 {
 	float4 data[BVH_ONODE_LEAF_SIZE];
@@ -252,14 +342,14 @@ void BVH8::pack_unaligned_node(int idx,
 void BVH8::pack_nodes(const BVHNode *root)
 {
 	/* Calculate size of the arrays required. */
-	const size_t num_nodes = root->getSubtreeSize(BVH_STAT_ONODE_COUNT);
+	const size_t num_nodes = root->getSubtreeSize(BVH_STAT_NODE_COUNT);
 	const size_t num_leaf_nodes = root->getSubtreeSize(BVH_STAT_LEAF_COUNT);
 	assert(num_leaf_nodes <= num_nodes);
 	const size_t num_inner_nodes = num_nodes - num_leaf_nodes;
 	size_t node_size;
 	if(params.use_unaligned_nodes) {
 		const size_t num_unaligned_nodes =
-		        root->getSubtreeSize(BVH_STAT_UNALIGNED_INNER_ONODE_COUNT);
+		        root->getSubtreeSize(BVH_STAT_UNALIGNED_INNER_COUNT);
 		node_size = (num_unaligned_nodes * BVH_UNALIGNED_ONODE_SIZE) +
 		        (num_inner_nodes - num_unaligned_nodes) * BVH_ONODE_SIZE;
 	}
@@ -287,9 +377,8 @@ void BVH8::pack_nodes(const BVHNode *root)
 	}
 	else {
 		stack.push_back(BVHStackEntry(root, nextNodeIdx));
-		nextNodeIdx += node_is_unaligned(root, bvh8)
-		                   ? BVH_UNALIGNED_ONODE_SIZE
-		                   : BVH_ONODE_SIZE;
+		nextNodeIdx += root->has_unaligned() ? BVH_UNALIGNED_ONODE_SIZE
+		                                     : BVH_ONODE_SIZE;
 	}
 
 	while(stack.size()) {
@@ -303,72 +392,29 @@ void BVH8::pack_nodes(const BVHNode *root)
 		}
 		else {
 			/* Inner node. */
-			const BVHNode *node = e.node;
-			const BVHNode *node0 = node->get_child(0);
-			const BVHNode *node1 = node->get_child(1);
 			/* Collect nodes. */
-			const BVHNode *nodes[8];
-			int numnodes = 0;
-			if(node0->is_leaf()) {
-				nodes[numnodes++] = node0;
-			}
-			else {
-				const BVHNode *node00 = node0->get_child(0),
-				              *node01 = node0->get_child(1);
-				if(node00->is_leaf()) {
-					nodes[numnodes++] = node00;
-				}
-				else {
-					nodes[numnodes++] = node00->get_child(0);
-					nodes[numnodes++] = node00->get_child(1);
-				}
-				if(node01->is_leaf()) {
-					nodes[numnodes++] = node01;
-				}
-				else {
-					nodes[numnodes++] = node01->get_child(0);
-					nodes[numnodes++] = node01->get_child(1);
-				}
-			}
-			if(node1->is_leaf()) {
-				nodes[numnodes++] = node1;
-			}
-			else {
-				const BVHNode *node10 = node1->get_child(0),
-				              *node11 = node1->get_child(1);
-				if(node10->is_leaf()) {
-					nodes[numnodes++] = node10;
-				}
-				else {
-					nodes[numnodes++] = node10->get_child(0);
-					nodes[numnodes++] = node10->get_child(1);
-				}
-				if(node11->is_leaf()) {
-					nodes[numnodes++] = node11;
-				}
-				else {
-					nodes[numnodes++] = node11->get_child(0);
-					nodes[numnodes++] = node11->get_child(1);
-				}
-			}
+			const BVHNode *children[8];
+			int num_children = e.node->num_children();
 			/* Push entries on the stack. */
-			for(int i = 0; i < numnodes; ++i) {
+			for(int i = 0; i < num_children; ++i) {
 				int idx;
-				if(nodes[i]->is_leaf()) {
+				children[i] = e.node->get_child(i);
+				if(children[i]->is_leaf()) {
 					idx = nextLeafNodeIdx++;
 				}
 				else {
 					idx = nextNodeIdx;
-					nextNodeIdx += node_is_unaligned(nodes[i], bvh8)
-						? BVH_UNALIGNED_ONODE_SIZE
-						: BVH_ONODE_SIZE;
+					nextNodeIdx += children[i]->has_unaligned()
+					                       ? BVH_UNALIGNED_ONODE_SIZE
+					                       : BVH_ONODE_SIZE;
 				}
-				stack.push_back(BVHStackEntry(nodes[i], idx));
+				stack.push_back(BVHStackEntry(children[i], idx));
 			}
 			/* Set node. */
-			pack_inner(e, &stack[stack.size() - numnodes], numnodes);
+			pack_inner(e, &stack[stack.size() - num_children], num_children);
 		}
 	}
+
 	assert(node_size == nextNodeIdx);
 	/* Root index to start traversal at, to handle case of single leaf node. */
 	pack.root_index = (root->is_leaf()) ? -1 : 0;
diff --git a/intern/cycles/bvh/bvh8.h b/intern/cycles/bvh/bvh8.h
index 834daf3abce..84f82538c0f 100644
--- a/intern/cycles/bvh/bvh8.h
+++ b/intern/cycles/bvh/bvh8.h
@@ -59,6 +59,9 @@ protected:
 	friend class BVH;
 	BVH8(const BVHParams& params, const vector<Object*>& objects);
 
+	/* Building process. */
+	virtual BVHNode *widen_children_nodes(const BVHNode *root) override;
+
 	/* pack */
 	void pack_nodes(const BVHNode *root);
 
diff --git a/intern/cycles/bvh/bvh_embree.cpp b/intern/cycles/bvh/bvh_embree.cpp
index 2d6efe8dad5..8415d80c4a8 100644
--- a/intern/cycles/bvh/bvh_embree.cpp
+++ b/intern/cycles/bvh/bvh_embree.cpp
@@ -436,6 +436,12 @@ void BVHEmbree::build(Progress& progress, Stats *stats_)
 	stats = NULL;
 }
 
+BVHNode *BVHEmbree::widen_children_nodes(const BVHNode * /*root*/)
+{
+	assert(!"Must not be called.");
+	return NULL;
+}
+
 void BVHEmbree::add_object(Object *ob, int i)
 {
 	Mesh *mesh = ob->mesh;
diff --git a/intern/cycles/bvh/bvh_embree.h b/intern/cycles/bvh/bvh_embree.h
index 9990826ba98..983b6dc07da 100644
--- a/intern/cycles/bvh/bvh_embree.h
+++ b/intern/cycles/bvh/bvh_embree.h
@@ -40,6 +40,10 @@ public:
 	virtual ~BVHEmbree();
 	RTCScene scene;
 	static void destroy(RTCScene);
+
+	/* Building process. */
+	virtual BVHNode *widen_children_nodes(const BVHNode *root) override;
+
 protected:
 	friend class BVH;
 	BVHEmbree(const BVHParams& params, const vector<Object*>& objects);
diff --git a/intern/cycles/bvh/bvh_node.cpp b/intern/cycles/bvh/bvh_node.cpp
index fd8b4977699..dc0255c4039 100644
--- a/intern/cycles/bvh/bvh_node.cpp
+++ b/intern/cycles/bvh/bvh_node.cpp
@@ -47,69 +47,6 @@ int BVHNode::getSubtreeSize(BVH_STAT stat) const
 		case BVH_STAT_CHILDNODE_COUNT:
 			cnt = num_children();
 			break;
-		case BVH_STAT_QNODE_COUNT:
-			cnt = 1;
-			for(int i = 0; i < num_children(); i++) {
-				BVHNode *node = get_child(i);
-				if(node->is_leaf()) {
-					cnt += 1;
-				}
-				else {
-					for(int j = 0; j < node->num_children(); j++) {
-						cnt += node->get_child(j)->getSubtreeSize(stat);
-					}
-				}
-			}
-			return cnt;
-		case BVH_STAT_ONODE_COUNT:
-			cnt = 1;
-			for(int i = 0; i < num_children(); i++) {
-				BVHNode *node = get_child(i);
-				if(node->is_leaf()) {
-					cnt += 1;
-				}
-				else {
-					for(int j = 0; j < node->num_children(); j++)
-					{
-						BVHNode *node_next = node->get_child(j);
-						if(node_next->is_leaf()) {
-							cnt += 1;
-						}
-						else {
-							for(int k = 0; k < node_next->num_children(); k++) {
-								cnt += node_next->get_child(k)->getSubtreeSize(stat);
-							}
-						}
-					}
-				}
-			}
-			return cnt;
-		case BVH_STAT_UNALIGNED_INNER_ONODE_COUNT:
-			{
-				bool has_unaligned = false;
-				for(int i = 0; i < num_children(); i++) {
-					BVHNode *node = get_child(i);
-					if(node->is_leaf()) {
-						has_unaligned |= node->is_unaligned;
-					}
-					else {
-						for(int j = 0; j < node->num_children(); j++) {
-							BVHNode *node_next = node->get_child(j);
-							if(node_next->is_leaf()) {
-								has_unaligned |= node_next->is_unaligned;
-							}
-							else {
-								for(int k = 0; k < node_next->num_children(); k++) {
-									cnt += node_next->get_child(k)->getSubtreeSize(stat);
-									has_unaligned |= node_next->get_child(k)->is_unaligned;
-								}
-							}
-						}
-					}
-				}
-				cnt += has_unaligned? 1: 0;
-			}
-			return cnt;
 		case BVH_STAT_ALIGNED_COUNT:
 			if(!is_unaligned) {
 				cnt = 1;
@@ -138,42 +75,6 @@ int BVHNode::getSubtreeSize(BVH_STAT stat) const
 				cnt += has_unaligned? 1: 0;
 			}
 			break;
-		case BVH_STAT_ALIGNED_INNER_QNODE_COUNT:
-			{
-				bool has_unaligned = false;
-				for(int i = 0; i < num_children(); i++) {
-					BVHNode *node = get_child(i);
-					if(node->is_leaf()) {
-						has_unaligned |= node->is_unaligned;
-					}
-					else {
-						for(int j = 0; j < node->num_children(); j++) {
-							cnt += node->get_child(j)->getSubtreeSize(stat);
-							has_unaligned |= node->get_child(j)->is_unaligned;
-						}
-					}
-				}
-				cnt += has_unaligned? 0: 1;
-			}
-			return cnt;
-		case BVH_STAT_UNALIGNED_INNER_QNODE_COUNT:
-			{
-				bool has_unaligned = false;
-				for(int i = 0; i < num_children(); i++) {
-					BVHNode *node = get_child(i);
-					if(node->is_leaf()) {
-						has_unaligned |= node->is_unaligned;
-					}
-					else {
-						for(int j = 0; j < node->num_children(); j++) {
-							cnt += node->get_child(j)->getSubtreeSize(stat);
-							has_unaligned |= node->get_child(j)->is_unaligned;
-						}
-					}
-				}
-				cnt += has_unaligned? 1: 0;
-			}
-			return cnt;
 		case BVH_STAT_ALIGNED_LEAF_COUNT:
 			cnt = (is_leaf() && !is_unaligned) ? 1 : 0;
 			break;
diff --git a/intern/cycles/bvh/bvh_node.h b/intern/cycles/bvh/bvh_node.h
index 65d5df01158..8a2cffeb056 100644
--- a/intern/cycles/bvh/bvh_node.h
+++ b/intern/cycles/bvh/bvh_node.h
@@ -29,18 +29,13 @@ enum BVH_STAT {
 	BVH_STAT_LEAF_COUNT,
 	BVH_STAT_TRIANGLE_COUNT,
 	BVH_STAT_CHILDNODE_COUNT,
-	BVH_STAT_QNODE_COUNT,
 	BVH_STAT_ALIGNED_COUNT,
 	BVH_STAT_UNALIGNED_COUNT,
 	BVH_STAT_ALIGNED_INNER_COUNT,
 	BVH_STAT_UNALIGNED_INNER_COUNT,
-	BVH_STAT_ALIGNED_INNER_QNODE_COUNT,
-	BVH_STAT_UNALIGNED_INNER_QNODE_COUNT,
 	BVH_STAT_ALIGNED_LEAF_COUNT,
 	BVH_STAT_UNALIGNED_LEAF_COUNT,
 	BVH_STAT_DEPTH,
-	BVH_STAT_ONODE_COUNT,
-	BVH_STAT_UNALIGNED_INNER_ONODE_COUNT,
 };
 
 class BVHParams;
@@ -48,13 +43,6 @@ class BVHParams;
 class BVHNode
 {
 public:
-	BVHNode() : is_unaligned(false),
-	            aligned_space(NULL),
-	            time_from(0.0f),
-	            time_to(1.0f)
-	{
-	}
-
 	virtual ~BVHNode()
 	{
 		delete aligned_space;
@@ -85,6 +73,19 @@ public:
 		return *aligned_space;
 	}
 
+	inline bool has_unaligned() const
+	{
+		if(is_leaf()) {
+			return false;
+		}
+		for(int i = 0; i < num_children(); ++i) {
+			if(get_child(i)->is_unaligned) {
+				return true;
+			}
+		}
+		return false;
+	}
+
 	// Subtree functions
 	int getSubtreeSize(BVH_STAT stat=BVH_STAT_NODE_COUNT) const;
 	float computeSubtreeSAHCost(const BVHParams& p, float probability = 1.0f) const;
@@ -105,56 +106,130 @@ public:
 	Transform *aligned_space;
 
 	float time_from, time_to;
+
+protected:
+	explicit BVHNode(const BoundBox& bounds)
+	: bounds(bounds),
+	  visibility(0),
+	  is_unaligned(false),
+	  aligned_space(NULL),
+	  time_from(0.0f),
+	  time_to(1.0f)
+	{
+	}
+
+	explicit BVHNode(const BVHNode& other)
+	: bounds(other.bounds),
+	  visibility(other.visibility),
+	  is_unaligned(other.is_unaligned),
+	  aligned_space(NULL),
+	  time_from(other.time_from),
+	  time_to(other.time_to)
+	{
+		if(other.aligned_space != NULL) {
+			assert(other.is_unaligned);
+			aligned_space = new Transform();
+			*aligned_space = *other.aligned_space;
+		}
+		else {
+			assert(!other.is_unaligned);
+		}
+	}
 };
 
 class InnerNode : public BVHNode
 {
 public:
+	static constexpr int kNumMaxChildren = 8;
+
 	InnerNode(const BoundBox& bounds,
 	          BVHNode* child0,
 	          BVHNode* child1)
+	: BVHNode(bounds),
+	  num_children_(2)
 	{
-		this->bounds = bounds;
 		children[0] = child0;
 		children[1] = child1;
+		reset_unused_children();
 
-		if(child0 && child1)
-			visibility = child0->visibility|child1->visibility;
-		else
-			visibility = 0; /* happens on build cancel */
+		if(child0 && child1) {
+			visibility = child0->visibility | child1->visibility;
+		}
+		else {
+			/* Happens on build cancel. */
+			visibility = 0;
+		}
 	}
 
+	InnerNode(const BoundBox& bounds,
+	          BVHNode** children,
+	          const int num_children)
+	: BVHNode(bounds),
+	  num_children_(num_children)
+	{
+		visibility = 0;
+		time_from = FLT_MAX;
+		time_to = -FLT_MAX;
+		for(int i = 0; i < num_children; ++i) {
+			assert(children[i] != NULL);
+			visibility |= children[i]->visibility;
+			this->children[i] = children[i];
+			time_from = min(time_from, children[i]->time_from);
+			time_to = max(time_to, children[i]->time_to);
+		}
+		reset_unused_children();
+	}
+
+	/* NOTE: This function is only used during binary BVH builder, and it
+	 * supposed to be configured to have 2 children which will be filled in in a
+	 * bit. But this is important to have children reset to NULL. */
 	explicit InnerNode(const BoundBox& bounds)
+	: BVHNode(bounds),
+	  num_children_(0)
 	{
-		this->bounds = bounds;
+		reset_unused_children();
 		visibility = 0;
-		children[0] = NULL;
-		children[1] = NULL;
+		num_children_ = 2;
 	}
 
 	bool is_leaf() const { return false; }
-	int num_children() const { return 2; }
-	BVHNode *get_child(int i) const{ assert(i>=0 && i<2); return children[i]; }
+	int num_children() const { return num_children_; }
+	BVHNode *get_child(int i) const
+	{
+		assert(i >= 0 && i < num_children_);
+		return children[i];
+	}
 	void print(int depth) const;
 
-	BVHNode *children[2];
+	int num_children_;
+	BVHNode *children[kNumMaxChildren];
+
+protected:
+	void reset_unused_children()
+	{
+		for(int i = num_children_; i < kNumMaxChildren; ++i) {
+			children[i] = NULL;
+		}
+	}
 };
 
 class LeafNode : public BVHNode
 {
 public:
 	LeafNode(const BoundBox& bounds, uint visibility, int lo, int hi)
-	: lo(lo),
+	: BVHNode(bounds),
+	  lo(lo),
 	  hi(hi)
 	{
 		this->bounds = bounds;
 		this->visibility = visibility;
 	}
 
-	LeafNode(const LeafNode& s)
-	: BVHNode()
+	LeafNode(const LeafNode& other)
+	: BVHNode(other),
+	  lo(other.lo),
+	  hi(other.hi)
 	{
-		*this = s;
 	}
 
 	bool is_leaf() const { return true; }