* Point Density texture

Replaced the previous KD-tree (for caching points) with a 
BVH-tree (thanks to Andre 'jaguarandi' Pinto for help here!).

The bvh is quite a bit faster and doesn't suffer some of the
artifacts that were apparent with the kd-tree.

I've also added a choice of falloff types: Standard, Smooth, and 
Sharp. Standard gives a harder edge, easier to see individual 
particles, and when used with a larger radius, Smooth and Sharp 
falloffs make a much cloudier appearance possible. See the image 
below (note the settings and render times too)

http://mke3.net/blender/devel/rendering/volumetrics/pointdensity_bvh.jpg

1 files changed, 98 insertions, 11 deletions

diff --git a/source/blender/blenlib/intern/BLI_kdopbvh.c b/source/blender/blenlib/intern/BLI_kdopbvh.c
index 30472beb3e6..f82b6b7f162 100644
--- a/source/blender/blenlib/intern/BLI_kdopbvh.c
+++ b/source/blender/blenlib/intern/BLI_kdopbvh.c
@@ -1171,7 +1171,7 @@ static float squared_dist(const float *a, const float *b)
 }
 
 //Determines the nearest point of the given node BV. Returns the squared distance to that point.
-static float calc_nearest_point(BVHNearestData *data, BVHNode *node, float *nearest)
+static float calc_nearest_point(const float *proj, BVHNode *node, float *nearest)
 {
 	int i;
 	const float *bv = node->bv;
@@ -1179,12 +1179,12 @@ static float calc_nearest_point(BVHNearestData *data, BVHNode *node, float *near
 	//nearest on AABB hull
 	for(i=0; i != 3; i++, bv += 2)
 	{
-		if(bv[0] > data->proj[i])
+		if(bv[0] > proj[i])
 			nearest[i] = bv[0];
-		else if(bv[1] < data->proj[i])
+		else if(bv[1] < proj[i])
 			nearest[i] = bv[1];
 		else
-			nearest[i] = data->proj[i];
+			nearest[i] = proj[i];
 	}
 
 /*
@@ -1206,7 +1206,7 @@ static float calc_nearest_point(BVHNearestData *data, BVHNode *node, float *near
 		}
 	}
 */
-	return squared_dist(data->co, nearest);
+	return squared_dist(proj, nearest);
 }
 
 
@@ -1229,7 +1229,7 @@ static void dfs_find_nearest_dfs(BVHNearestData *data, BVHNode *node)
 		else
 		{
 			data->nearest.index	= node->index;
-			data->nearest.dist	= calc_nearest_point(data, node, data->nearest.co);
+			data->nearest.dist	= calc_nearest_point(data->proj, node, data->nearest.co);
 		}
 	}
 	else
@@ -1243,7 +1243,7 @@ static void dfs_find_nearest_dfs(BVHNearestData *data, BVHNode *node)
 
 			for(i=0; i != node->totnode; i++)
 			{
-				if( calc_nearest_point(data, node->children[i], nearest) >= data->nearest.dist) continue;
+				if( calc_nearest_point(data->proj, node->children[i], nearest) >= data->nearest.dist) continue;
 				dfs_find_nearest_dfs(data, node->children[i]);
 			}
 		}
@@ -1251,7 +1251,7 @@ static void dfs_find_nearest_dfs(BVHNearestData *data, BVHNode *node)
 		{
 			for(i=node->totnode-1; i >= 0 ; i--)
 			{
-				if( calc_nearest_point(data, node->children[i], nearest) >= data->nearest.dist) continue;
+				if( calc_nearest_point(data->proj, node->children[i], nearest) >= data->nearest.dist) continue;
 				dfs_find_nearest_dfs(data, node->children[i]);
 			}
 		}
@@ -1261,7 +1261,7 @@ static void dfs_find_nearest_dfs(BVHNearestData *data, BVHNode *node)
 static void dfs_find_nearest_begin(BVHNearestData *data, BVHNode *node)
 {
 	float nearest[3], sdist;
-	sdist = calc_nearest_point(data, node, nearest);
+	sdist = calc_nearest_point(data->proj, node, nearest);
 	if(sdist >= data->nearest.dist) return;
 	dfs_find_nearest_dfs(data, node);
 }
@@ -1298,7 +1298,7 @@ static void bfs_find_nearest(BVHNearestData *data, BVHNode *node)
 	}
 
 	current.node = node;
-	current.dist = calc_nearest_point(data, node, nearest);
+	current.dist = calc_nearest_point(data->proj, node, nearest);
 
 	while(current.dist < data->nearest.dist)
 	{
@@ -1326,7 +1326,7 @@ static void bfs_find_nearest(BVHNearestData *data, BVHNode *node)
 				}
 
 				heap[heap_size].node = current.node->children[i];
-				heap[heap_size].dist = calc_nearest_point(data, current.node->children[i], nearest);
+				heap[heap_size].dist = calc_nearest_point(data->proj, current.node->children[i], nearest);
 
 				if(heap[heap_size].dist >= data->nearest.dist) continue;
 				heap_size++;
@@ -1524,3 +1524,90 @@ int BLI_bvhtree_ray_cast(BVHTree *tree, const float *co, const float *dir, float
 	return data.hit.index;
 }
 
+/*
+ * Range Query - as request by broken :P
+ *
+ * Allocs and fills an array with the indexs of node that are on the given spherical range (center, radius) 
+ * Returns the size of the array.
+ */
+typedef struct RangeQueryData
+{
+	BVHTree *tree;
+	const float *center;
+	float radius;			//squared radius
+
+	int hits;
+
+	BVHTree_RangeQuery callback;
+	void *userdata;
+
+
+} RangeQueryData;
+
+
+static void dfs_range_query(RangeQueryData *data, BVHNode *node)
+{
+	if(node->totnode == 0)
+	{
+
+		//Calculate the node min-coords (if the node was a point then this is the point coordinates)
+		float co[3];
+		co[0] = node->bv[0];
+		co[1] = node->bv[2];
+		co[2] = node->bv[4];
+
+	}
+	else
+	{
+		int i;
+		for(i=0; i != node->totnode; i++)
+		{
+			float nearest[3];
+			float dist = calc_nearest_point(data->center, node->children[i], nearest);
+			if(dist < data->radius)
+			{
+				//Its a leaf.. call the callback
+				if(node->children[i]->totnode == 0)
+				{
+					data->hits++;
+					data->callback( data->userdata, node->children[i]->index, dist, data->radius );
+				}
+				else
+					dfs_range_query( data, node->children[i] );
+			}
+		}
+	}
+}
+
+int BLI_bvhtree_range_query(BVHTree *tree, const float *co, float radius, BVHTree_RangeQuery callback, void *userdata)
+{
+	BVHNode * root = tree->nodes[tree->totleaf];
+
+	RangeQueryData data;
+	data.tree = tree;
+	data.center = co;
+	data.radius = radius*radius;
+	data.hits = 0;
+
+	data.callback = callback;
+	data.userdata = userdata;
+
+	if(root != NULL)
+	{
+		float nearest[3];
+		float dist = calc_nearest_point(data.center, root, nearest);
+		if(dist < data.radius)
+		{
+			//Its a leaf.. call the callback
+			if(root->totnode == 0)
+			{
+				data.hits++;
+				data.callback( data.userdata, root->index, dist, data.radius );
+			}
+			else
+				dfs_range_query( &data, root );
+		}
+	}
+
+	return data.hits;
+}