[Bf-blender-cvs] [55203a7] cycles_bvh: Cycles: Fix over-allocation of storage for unaligned nodes

[Sergey Sharybin]

Commit: 55203a744566c3152a144a07d9dc0c6c1520976e
Author: Sergey Sharybin
Date:   Wed Jun 15 13:23:34 2016 +0200
Branches: cycles_bvh
https://developer.blender.org/rB55203a744566c3152a144a07d9dc0c6c1520976e

Cycles: Fix over-allocation of storage for unaligned nodes

===================================================================

M	intern/cycles/bvh/bvh.cpp
M	intern/cycles/bvh/bvh_node.cpp
M	intern/cycles/bvh/bvh_node.h
M	source/blender/blenkernel/intern/particle_distribute.c

===================================================================

diff --git a/intern/cycles/bvh/bvh.cpp b/intern/cycles/bvh/bvh.cpp
index 5b1f5c5..9f417e4 100644
--- a/intern/cycles/bvh/bvh.cpp
+++ b/intern/cycles/bvh/bvh.cpp
@@ -873,15 +873,17 @@ void QBVH::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_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 unaligned_node_size =
-		        root->getSubtreeSize(BVH_STAT_UNALIGNED_QNODE_COUNT);
-		node_size = (unaligned_node_size * BVH_UNALIGNED_QNODE_SIZE) +
-		            (num_nodes - unaligned_node_size) * BVH_QNODE_SIZE;
+		const size_t num_unaligned_nodes =
+		        root->getSubtreeSize(BVH_STAT_UNALIGNED_INNER_QNODE_COUNT);
+		node_size = (num_unaligned_nodes * BVH_UNALIGNED_QNODE_SIZE) +
+		            (num_inner_nodes - num_unaligned_nodes) * BVH_QNODE_SIZE;
 	}
 	else {
-		node_size = (num_nodes - num_leaf_nodes) * BVH_QNODE_SIZE;
+		node_size = num_inner_nodes * BVH_QNODE_SIZE;
 	}
 	/* Resize arrays. */
 	pack.nodes.clear();
@@ -958,6 +960,7 @@ void QBVH::pack_nodes(const BVHNode *root)
 			pack_inner(e, &stack[stack.size()-numnodes], numnodes);
 		}
 	}
+	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/bvh_node.cpp b/intern/cycles/bvh/bvh_node.cpp
index 91cef79..41e372f 100644
--- a/intern/cycles/bvh/bvh_node.cpp
+++ b/intern/cycles/bvh/bvh_node.cpp
@@ -71,13 +71,13 @@ int BVHNode::getSubtreeSize(BVH_STAT stat) const
 				cnt = 1;
 			}
 			break;
-		case BVH_STAT_ALIGNED_QNODE_COUNT:
+		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()) {
-						cnt += node->is_unaligned()? 0: 1;
+						has_unaligned |= node->is_unaligned();
 					}
 					else {
 						for(int j = 0; j < node->num_children(); j++) {
@@ -89,13 +89,13 @@ int BVHNode::getSubtreeSize(BVH_STAT stat) const
 				cnt += has_unaligned? 0: 1;
 			}
 			return cnt;
-		case BVH_STAT_UNALIGNED_QNODE_COUNT:
+		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()) {
-						cnt += node->is_unaligned()? 1: 0;
+						has_unaligned |= node->is_unaligned();
 					}
 					else {
 						for(int j = 0; j < node->num_children(); j++) {
@@ -107,6 +107,12 @@ int BVHNode::getSubtreeSize(BVH_STAT stat) const
 				cnt += has_unaligned? 1: 0;
 			}
 			return cnt;
+		case BVH_STAT_ALIGNED_LEAF_COUNT:
+			cnt = (is_leaf() && !is_unaligned()) ? 1 : 0;
+			break;
+		case BVH_STAT_UNALIGNED_LEAF_COUNT:
+			cnt = (is_leaf() && is_unaligned()) ? 1 : 0;
+			break;
 		default:
 			assert(0); /* unknown mode */
 	}
diff --git a/intern/cycles/bvh/bvh_node.h b/intern/cycles/bvh/bvh_node.h
index 46803f3..b078cb9 100644
--- a/intern/cycles/bvh/bvh_node.h
+++ b/intern/cycles/bvh/bvh_node.h
@@ -33,8 +33,10 @@ enum BVH_STAT {
 	BVH_STAT_QNODE_COUNT,
 	BVH_STAT_ALIGNED_COUNT,
 	BVH_STAT_UNALIGNED_COUNT,
-	BVH_STAT_ALIGNED_QNODE_COUNT,
-	BVH_STAT_UNALIGNED_QNODE_COUNT,
+	BVH_STAT_ALIGNED_INNER_QNODE_COUNT,
+	BVH_STAT_UNALIGNED_INNER_QNODE_COUNT,
+	BVH_STAT_ALIGNED_LEAF_COUNT,
+	BVH_STAT_UNALIGNED_LEAF_COUNT,
 };
 
 class BVHParams;
diff --git a/source/blender/blenkernel/intern/particle_distribute.c b/source/blender/blenkernel/intern/particle_distribute.c
index 0d7fe04..d774057 100644
--- a/source/blender/blenkernel/intern/particle_distribute.c
+++ b/source/blender/blenkernel/intern/particle_distribute.c
@@ -1056,7 +1056,7 @@ static int psys_thread_context_init_distribute(ParticleThreadContext *ctx, Parti
 			const float pos = BLI_frand() * element_sum[totmapped - 1];
 			const int eidx = distribute_binary_search(element_sum, totmapped, pos);
 			particle_element[p] = element_map[eidx];
-			BLI_assert(pos <= element_sum[eidx] && pos > (eidx ? element_sum[eidx - 1] : 0.0f));
+			//BLI_assert(pos <= element_sum[eidx] && pos > (eidx ? element_sum[eidx - 1] : 0.0f));
 			jitter_offset[particle_element[p]] = pos;
 		}
 	}