Cycles: BVH params option to split leaf node by primitive types

The idea of this change is make it possible to split leaf nodes by primitive
type, making leaf containing primitives of the same type.

This would become handy when working on a single ray to multiple triangles
intersection code, plus with careful implementation it might give some extra
benefits on BVH traversal code by avoiding primitive type fetch and check for
each primitive in the node. But that's a bit tricky to have benefits on this
change only because depth of BVH increases.

This option is not exposed to the interface at all and not used even secretly,
the commit is only needed to help working further in this direction without
messing around with local patches and worrying of them running out of date.

4 files changed, 145 insertions, 12 deletions

diff --git a/intern/cycles/bvh/bvh.cpp b/intern/cycles/bvh/bvh.cpp
index ac2762b80bd..38773bfbc4e 100644
--- a/intern/cycles/bvh/bvh.cpp
+++ b/intern/cycles/bvh/bvh.cpp
@@ -504,12 +504,19 @@ RegularBVH::RegularBVH(const BVHParams& params_, const vector<Object*>& objects_
 
 void RegularBVH::pack_leaf(const BVHStackEntry& e, const LeafNode *leaf)
 {
-	if(leaf->num_triangles() == 1 && pack.prim_index[leaf->m_lo] == -1)
+	if(leaf->num_triangles() == 1 && pack.prim_index[leaf->m_lo] == -1) {
 		/* object */
-		pack_node(e.idx, leaf->m_bounds, leaf->m_bounds, ~(leaf->m_lo), 0, leaf->m_visibility, leaf->m_visibility);
-	else
-		/* triangle */
-		pack_node(e.idx, leaf->m_bounds, leaf->m_bounds, leaf->m_lo, leaf->m_hi, leaf->m_visibility, leaf->m_visibility);
+		pack_node(e.idx, leaf->m_bounds, leaf->m_bounds, ~(leaf->m_lo), 0,
+		          leaf->m_visibility, leaf->m_visibility);
+	}
+	else {
+		/* Triangle/curve primitive leaf.  */
+		pack_node(e.idx, leaf->m_bounds, leaf->m_bounds,
+		          leaf->m_lo, leaf->m_hi,
+		          leaf->m_visibility,
+		          pack.prim_type[leaf->m_lo]);
+	}
+
 }
 
 void RegularBVH::pack_inner(const BVHStackEntry& e, const BVHStackEntry& e0, const BVHStackEntry& e1)
@@ -657,7 +664,7 @@ void RegularBVH::refit_node(int idx, bool leaf, BoundBox& bbox, uint& visibility
 			visibility |= ob->visibility;
 		}
 
-		pack_node(idx, bbox, bbox, c0, c1, visibility, visibility);
+		pack_node(idx, bbox, bbox, c0, c1, visibility, data[3].w);
 	}
 	else {
 		/* refit inner node, set bbox from children */
@@ -700,6 +707,7 @@ void QBVH::pack_leaf(const BVHStackEntry& e, const LeafNode *leaf)
 		data[6].y = __int_as_float(leaf->m_hi);
 	}
 	data[6].z = __uint_as_float(leaf->m_visibility);
+	data[6].w = __uint_as_float(pack.prim_type[leaf->m_lo]);
 
 	memcpy(&pack.nodes[e.idx * BVH_QNODE_SIZE], data, sizeof(float4)*BVH_QNODE_SIZE);
 }
diff --git a/intern/cycles/bvh/bvh_build.cpp b/intern/cycles/bvh/bvh_build.cpp
index 5547229a910..f4368a84482 100644
--- a/intern/cycles/bvh/bvh_build.cpp
+++ b/intern/cycles/bvh/bvh_build.cpp
@@ -449,8 +449,123 @@ BVHNode *BVHBuild::create_object_leaf_nodes(const BVHReference *ref, int start,
 	}
 }
 
+BVHNode *BVHBuild::create_primitive_leaf_node(const vector<int>& p_type,
+                                              const vector<int>& p_index,
+                                              const vector<int>& p_object,
+                                              const BoundBox& bounds,
+                                              uint visibility,
+                                              int start)
+{
+	assert(p_type.size() == p_index.size());
+	assert(p_index.size() == p_object.size());
+	for(int i = 0; i < p_type.size(); ++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];
+		}
+	}
+	return new LeafNode(bounds, visibility, start, start + p_type.size());
+}
+
+BVHNode* BVHBuild::create_leaf_node_split(const BVHRange& range)
+{
+	/* TODO(sergey): Reserve some elementsin arrays by default. */
+	vector<int> p_type[PRIMITIVE_NUM_TOTAL];
+	vector<int> p_index[PRIMITIVE_NUM_TOTAL];
+	vector<int> p_object[PRIMITIVE_NUM_TOTAL];
+	BoundBox bounds[PRIMITIVE_NUM_TOTAL] = {BoundBox::empty,
+	                                        BoundBox::empty,
+	                                        BoundBox::empty,
+	                                        BoundBox::empty};
+	int ob_num = 0;
+	uint visibility[PRIMITIVE_NUM_TOTAL] = {0};
+
+	/* Fill in per-type type/index array. */
+	for(int i = 0; i < range.size(); i++) {
+		BVHReference& ref = references[range.start() + i];
+		if(ref.prim_index() != -1) {
+			int type_index = bitscan(ref.prim_type() & PRIMITIVE_ALL);
+			p_type[type_index].push_back(ref.prim_type());
+			p_index[type_index].push_back(ref.prim_index());
+			p_object[type_index].push_back(ref.prim_object());
+
+			bounds[type_index].grow(ref.bounds());
+			visibility[type_index] |= objects[ref.prim_object()]->visibility;
+		}
+		else {
+			if(ob_num < i) {
+				references[range.start() + ob_num] = ref;
+			}
+			ob_num++;
+		}
+	}
+
+	/* Create leaf nodes for every existing primitive. */
+	BVHNode *leaves[PRIMITIVE_NUM_TOTAL + 1] = {NULL};
+	int num_leaves = 0;
+	int start = range.start();
+	for(int i = 0; i < PRIMITIVE_NUM_TOTAL; ++i) {
+		if(p_type[i].size()) {
+			leaves[num_leaves] = create_primitive_leaf_node(p_type[i],
+			                                                p_index[i],
+			                                                p_object[i],
+			                                                bounds[i],
+			                                                visibility[i],
+			                                                start);
+			++num_leaves;
+			start += p_type[i].size();
+		}
+	}
+
+	/* Create leaf node for object. */
+	if(num_leaves == 0 || ob_num) {
+		/* Only create object leaf nodes if there are objects or no other
+		 * nodes created.
+		 */
+		const BVHReference *ref = (ob_num)? &references[range.start()]: NULL;
+		leaves[num_leaves] = create_object_leaf_nodes(ref, start, ob_num);
+		++num_leaves;
+	}
+
+	if(num_leaves == 1) {
+		/* Simplest case: single leaf, just return it.
+		 * In all the rest cases we'll be creating intermediate inner node with
+		 * an appropriate bounding box.
+		 */
+		return leaves[0];
+	}
+	else if(num_leaves == 2) {
+		return new InnerNode(range.bounds(), leaves[0], leaves[1]);
+	}
+	else if(num_leaves == 3) {
+		BoundBox inner_bounds = merge(bounds[1], bounds[2]);
+		BVHNode *inner = new InnerNode(inner_bounds, leaves[1], leaves[2]);
+		return new InnerNode(range.bounds(), leaves[0], inner);
+	} else /*if(num_leaves == 4)*/ {
+		/* 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]);
+		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);
+	}
+}
+
 BVHNode* BVHBuild::create_leaf_node(const BVHRange& range)
 {
+	if(params.use_split_leaf_types) {
+		/* Need to ensure leaf nodes has single primitive type only. */
+		return create_leaf_node_split(range);
+	}
+
 	vector<int>& p_type = prim_type;
 	vector<int>& p_index = prim_index;
 	vector<int>& p_object = prim_object;
@@ -487,7 +602,7 @@ BVHNode* BVHBuild::create_leaf_node(const BVHRange& range)
 	}
 
 	BVHNode *leaf = NULL;
-	
+  
 	if(num > 0) {
 		leaf = new LeafNode(bounds, visibility, range.start(), range.start() + num);
 
@@ -499,7 +614,7 @@ BVHNode* BVHBuild::create_leaf_node(const BVHRange& range)
 	 * we want there to be the only one, so we keep splitting */
 	const BVHReference *ref = (ob_num)? &references[range.start()]: NULL;
 	BVHNode *oleaf = create_object_leaf_nodes(ref, range.start() + num, ob_num);
-	
+  
 	if(leaf)
 		return new InnerNode(range.bounds(), leaf, oleaf);
 	else
@@ -588,4 +703,3 @@ void BVHBuild::rotate(BVHNode *node, int max_depth)
 }
 
 CCL_NAMESPACE_END
-
diff --git a/intern/cycles/bvh/bvh_build.h b/intern/cycles/bvh/bvh_build.h
index a6b9916de9b..75c64be6eab 100644
--- a/intern/cycles/bvh/bvh_build.h
+++ b/intern/cycles/bvh/bvh_build.h
@@ -70,6 +70,15 @@ protected:
 	BVHNode *create_leaf_node(const BVHRange& range);
 	BVHNode *create_object_leaf_nodes(const BVHReference *ref, int start, int num);
 
+	/* Leaf node type splitting. */
+	BVHNode *create_leaf_node_split(const BVHRange& range);
+	BVHNode *create_primitive_leaf_node(const vector<int>& p_type,
+	                                    const vector<int>& p_index,
+	                                    const vector<int>& p_object,
+	                                    const BoundBox& bounds,
+	                                    uint visibility,
+	                                    int start);
+
 	bool range_within_max_leaf_size(const BVHRange& range);
 
 	/* threads */
@@ -116,4 +125,3 @@ protected:
 CCL_NAMESPACE_END
 
 #endif /* __BVH_BUILD_H__ */
-
diff --git a/intern/cycles/bvh/bvh_params.h b/intern/cycles/bvh/bvh_params.h
index 43c2d9b2683..c4dc14710e3 100644
--- a/intern/cycles/bvh/bvh_params.h
+++ b/intern/cycles/bvh/bvh_params.h
@@ -49,7 +49,10 @@ public:
 	/* QBVH */
 	int use_qbvh;
 
-	int pad;
+	/* Split leaf nodes by primitive types,
+	 * leaving node containing primitives of single type only.
+	 */
+	int use_split_leaf_types;
 
 	/* fixed parameters */
 	enum {
@@ -75,7 +78,7 @@ public:
 		top_level = false;
 		use_cache = false;
 		use_qbvh = false;
-		pad = false;
+		use_split_leaf_types = false;
 	}
 
 	/* SAH costs */