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.

1 files changed, 117 insertions, 3 deletions

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
-