BF2.5: First commit of smoke code.

Not working: 
a) rendering (since volumterics branch is not merged yet)
b) moving collision objects of any kind
c) saving of collision objects (because that's what I am working on)
d) pointcache
e) A bunch of other things I already know of 

So please do not report any bugs on this one yet :-)

2 files changed, 109 insertions, 76 deletions

diff --git a/source/blender/blenlib/BLI_kdopbvh.h b/source/blender/blenlib/BLI_kdopbvh.h
index e3591a84e98..50462d531ef 100644
--- a/source/blender/blenlib/BLI_kdopbvh.h
+++ b/source/blender/blenlib/BLI_kdopbvh.h
@@ -93,5 +93,7 @@ int BLI_bvhtree_find_nearest(BVHTree *tree, const float *co, BVHTreeNearest *nea
 
 int BLI_bvhtree_ray_cast(BVHTree *tree, const float *co, const float *dir, float radius, BVHTreeRayHit *hit, BVHTree_RayCastCallback callback, void *userdata);
 
+float BLI_bvhtree_bb_raycast(float *bv, float *light_start, float *light_end, float *pos);
+
 #endif // BLI_KDOPBVH_H
 
diff --git a/source/blender/blenlib/intern/BLI_kdopbvh.c b/source/blender/blenlib/intern/BLI_kdopbvh.c
index 0f8194362c9..84de9f9d862 100644
--- a/source/blender/blenlib/intern/BLI_kdopbvh.c
+++ b/source/blender/blenlib/intern/BLI_kdopbvh.c
@@ -72,10 +72,10 @@ struct BVHTree
 	char 	start_axis, stop_axis; // KDOP_AXES array indices according to axis
 };
 
-typedef struct BVHOverlapData 
-{  
-	BVHTree *tree1, *tree2; 
-	BVHTreeOverlap *overlap; 
+typedef struct BVHOverlapData
+{
+	BVHTree *tree1, *tree2;
+	BVHTreeOverlap *overlap;
 	int i, max_overlap; /* i is number of overlaps */
 	int start_axis, stop_axis;
 } BVHOverlapData;
@@ -109,7 +109,7 @@ typedef struct BVHRayCastData
 
 ////////////////////////////////////////////////////////////////////////
 // Bounding Volume Hierarchy Definition
-// 
+//
 // Notes: From OBB until 26-DOP --> all bounding volumes possible, just choose type below
 // Notes: You have to choose the type at compile time ITM
 // Notes: You can choose the tree type --> binary, quad, octree, choose below
@@ -188,10 +188,10 @@ int ADJUST_MEMORY(void *local_memblock, void **memblock, int new_size, int *max_
 
 
 //////////////////////////////////////////////////////////////////////////////////////////////////////
-// Introsort 
+// Introsort
 // with permission deriven from the following Java code:
 // http://ralphunden.net/content/tutorials/a-guide-to-introsort/
-// and he derived it from the SUN STL 
+// and he derived it from the SUN STL
 //////////////////////////////////////////////////////////////////////////////////////////////////////
 static int size_threshold = 16;
 /*
@@ -362,7 +362,7 @@ static void create_kdop_hull(BVHTree *tree, BVHNode *node, float *co, int numpoi
 	float newminmax;
 	float *bv = node->bv;
 	int i, k;
-	
+
 	// don't init boudings for the moving case
 	if(!moving)
 	{
@@ -372,7 +372,7 @@ static void create_kdop_hull(BVHTree *tree, BVHNode *node, float *co, int numpoi
 			bv[2*i + 1] = -FLT_MAX;
 		}
 	}
-	
+
 	for(k = 0; k < numpoints; k++)
 	{
 		// for all Axes.
@@ -394,7 +394,7 @@ static void refit_kdop_hull(BVHTree *tree, BVHNode *node, int start, int end)
 	int i, j;
 	float *bv = node->bv;
 
-	
+
 	for (i = tree->start_axis; i < tree->stop_axis; i++)
 	{
 		bv[2*i] = FLT_MAX;
@@ -406,10 +406,10 @@ static void refit_kdop_hull(BVHTree *tree, BVHNode *node, int start, int end)
 // for all Axes.
 		for (i = tree->start_axis; i < tree->stop_axis; i++)
 		{
-			newmin = tree->nodes[j]->bv[(2 * i)];   
+			newmin = tree->nodes[j]->bv[(2 * i)];
 			if ((newmin < bv[(2 * i)]))
 				bv[(2 * i)] = newmin;
- 
+
 			newmax = tree->nodes[j]->bv[(2 * i) + 1];
 			if ((newmax > bv[(2 * i) + 1]))
 				bv[(2 * i) + 1] = newmax;
@@ -427,14 +427,14 @@ static char get_largest_axis(float *bv)
 	middle_point[0] = (bv[1]) - (bv[0]); // x axis
 	middle_point[1] = (bv[3]) - (bv[2]); // y axis
 	middle_point[2] = (bv[5]) - (bv[4]); // z axis
-	if (middle_point[0] > middle_point[1]) 
+	if (middle_point[0] > middle_point[1])
 	{
 		if (middle_point[0] > middle_point[2])
 			return 1; // max x axis
 		else
 			return 5; // max z axis
 	}
-	else 
+	else
 	{
 		if (middle_point[1] > middle_point[2])
 			return 3; // max y axis
@@ -448,24 +448,24 @@ static char get_largest_axis(float *bv)
 static void node_join(BVHTree *tree, BVHNode *node)
 {
 	int i, j;
-	
+
 	for (i = tree->start_axis; i < tree->stop_axis; i++)
 	{
 		node->bv[2*i] = FLT_MAX;
 		node->bv[2*i + 1] = -FLT_MAX;
 	}
-	
+
 	for (i = 0; i < tree->tree_type; i++)
 	{
-		if (node->children[i]) 
+		if (node->children[i])
 		{
 			for (j = tree->start_axis; j < tree->stop_axis; j++)
 			{
-				// update minimum 
-				if (node->children[i]->bv[(2 * j)] < node->bv[(2 * j)]) 
+				// update minimum
+				if (node->children[i]->bv[(2 * j)] < node->bv[(2 * j)])
 					node->bv[(2 * j)] = node->children[i]->bv[(2 * j)];
-				
-				// update maximum 
+
+				// update maximum
 				if (node->children[i]->bv[(2 * j) + 1] > node->bv[(2 * j) + 1])
 					node->bv[(2 * j) + 1] = node->children[i]->bv[(2 * j) + 1];
 			}
@@ -518,7 +518,7 @@ static void bvhtree_info(BVHTree *tree)
 static void verify_tree(BVHTree *tree)
 {
 	int i, j, check = 0;
-	
+
 	// check the pointer list
 	for(i = 0; i < tree->totleaf; i++)
 	{
@@ -538,7 +538,7 @@ static void verify_tree(BVHTree *tree)
 			check = 0;
 		}
 	}
-	
+
 	// check the leaf list
 	for(i = 0; i < tree->totleaf; i++)
 	{
@@ -558,7 +558,7 @@ static void verify_tree(BVHTree *tree)
 			check = 0;
 		}
 	}
-	
+
 	printf("branches: %d, leafs: %d, total: %d\n", tree->totbranch, tree->totleaf, tree->totbranch + tree->totleaf);
 }
 #endif
@@ -703,7 +703,7 @@ static void non_recursive_bvh_div_nodes(BVHTree *tree, BVHNode *branches_array,
 
 	BVHBuildHelper data;
 	int depth;
-	
+
 	// set parent from root node to NULL
 	BVHNode *tmp = branches_array+0;
 	tmp->parent = NULL;
@@ -722,7 +722,7 @@ static void non_recursive_bvh_div_nodes(BVHTree *tree, BVHNode *branches_array,
 	}
 
 	branches_array--;	//Implicit trees use 1-based indexs
-	
+
 	build_implicit_tree_helper(tree, &data);
 
 	//Loop tree levels (log N) loops
@@ -806,11 +806,11 @@ BVHTree *BLI_bvhtree_new(int maxsize, float epsilon, char tree_type, char axis)
 {
 	BVHTree *tree;
 	int numnodes, i;
-	
+
 	// theres not support for trees below binary-trees :P
 	if(tree_type < 2)
 		return NULL;
-	
+
 	if(tree_type > MAX_TREETYPE)
 		return NULL;
 
@@ -820,13 +820,13 @@ BVHTree *BLI_bvhtree_new(int maxsize, float epsilon, char tree_type, char axis)
 	//so that tangent rays can still hit a bounding volume..
 	//this bug would show up when casting a ray aligned with a kdop-axis and with an edge of 2 faces
 	epsilon = MAX2(FLT_EPSILON, epsilon);
-	
+
 	if(tree)
 	{
 		tree->epsilon = epsilon;
-		tree->tree_type = tree_type; 
+		tree->tree_type = tree_type;
 		tree->axis = axis;
-		
+
 		if(axis == 26)
 		{
 			tree->start_axis = 0;
@@ -863,13 +863,13 @@ BVHTree *BLI_bvhtree_new(int maxsize, float epsilon, char tree_type, char axis)
 		numnodes = maxsize + implicit_needed_branches(tree_type, maxsize) + tree_type;
 
 		tree->nodes = (BVHNode **)MEM_callocN(sizeof(BVHNode *)*numnodes, "BVHNodes");
-		
+
 		if(!tree->nodes)
 		{
 			MEM_freeN(tree);
 			return NULL;
 		}
-		
+
 		tree->nodebv = (float*)MEM_callocN(sizeof(float)* axis * numnodes, "BVHNodeBV");
 		if(!tree->nodebv)
 		{
@@ -886,7 +886,7 @@ BVHTree *BLI_bvhtree_new(int maxsize, float epsilon, char tree_type, char axis)
 		}
 
 		tree->nodearray = (BVHNode *)MEM_callocN(sizeof(BVHNode)* numnodes, "BVHNodeArray");
-		
+
 		if(!tree->nodearray)
 		{
 			MEM_freeN(tree->nodechild);
@@ -902,14 +902,14 @@ BVHTree *BLI_bvhtree_new(int maxsize, float epsilon, char tree_type, char axis)
 			tree->nodearray[i].bv = tree->nodebv + i * axis;
 			tree->nodearray[i].children = tree->nodechild + i * tree_type;
 		}
-		
+
 	}
 
 	return tree;
 }
 
 void BLI_bvhtree_free(BVHTree *tree)
-{	
+{
 	if(tree)
 	{
 		MEM_freeN(tree->nodes);
@@ -946,27 +946,27 @@ int BLI_bvhtree_insert(BVHTree *tree, int index, float *co, int numpoints)
 {
 	int i;
 	BVHNode *node = NULL;
-	
+
 	// insert should only possible as long as tree->totbranch is 0
 	if(tree->totbranch > 0)
 		return 0;
-	
+
 	if(tree->totleaf+1 >= MEM_allocN_len(tree->nodes)/sizeof(*(tree->nodes)))
 		return 0;
-	
+
 	// TODO check if have enough nodes in array
-	
+
 	node = tree->nodes[tree->totleaf] = &(tree->nodearray[tree->totleaf]);
 	tree->totleaf++;
-	
+
 	create_kdop_hull(tree, node, co, numpoints, 0);
 	node->index= index;
-	
+
 	// inflate the bv with some epsilon
 	for (i = tree->start_axis; i < tree->stop_axis; i++)
 	{
-		node->bv[(2 * i)] -= tree->epsilon; // minimum 
-		node->bv[(2 * i) + 1] += tree->epsilon; // maximum 
+		node->bv[(2 * i)] -= tree->epsilon; // minimum
+		node->bv[(2 * i) + 1] += tree->epsilon; // maximum
 	}
 
 	return 1;
@@ -978,23 +978,23 @@ int BLI_bvhtree_update_node(BVHTree *tree, int index, float *co, float *co_movin
 {
 	int i;
 	BVHNode *node= NULL;
-	
+
 	// check if index exists
 	if(index > tree->totleaf)
 		return 0;
-	
+
 	node = tree->nodearray + index;
-	
+
 	create_kdop_hull(tree, node, co, numpoints, 0);
-	
+
 	if(co_moving)
 		create_kdop_hull(tree, node, co_moving, numpoints, 1);
-	
+
 	// inflate the bv with some epsilon
 	for (i = tree->start_axis; i < tree->stop_axis; i++)
 	{
-		node->bv[(2 * i)] -= tree->epsilon; // minimum 
-		node->bv[(2 * i) + 1] += tree->epsilon; // maximum 
+		node->bv[(2 * i)] -= tree->epsilon; // minimum
+		node->bv[(2 * i) + 1] += tree->epsilon; // maximum
 	}
 
 	return 1;
@@ -1030,24 +1030,24 @@ static int tree_overlap(BVHNode *node1, BVHNode *node2, int start_axis, int stop
 	float *bv2 = node2->bv;
 
 	float *bv1_end = bv1 + (stop_axis<<1);
-		
+
 	bv1 += start_axis<<1;
 	bv2 += start_axis<<1;
-	
+
 	// test all axis if min + max overlap
 	for (; bv1 != bv1_end; bv1+=2, bv2+=2)
 	{
-		if ((*(bv1) > *(bv2 + 1)) || (*(bv2) > *(bv1 + 1))) 
+		if ((*(bv1) > *(bv2 + 1)) || (*(bv2) > *(bv1 + 1)))
 			return 0;
 	}
-	
+
 	return 1;
 }
 
 static void traverse(BVHOverlapData *data, BVHNode *node1, BVHNode *node2)
 {
 	int j;
-	
+
 	if(tree_overlap(node1, node2, data->start_axis, data->stop_axis))
 	{
 		// check if node1 is a leaf
@@ -1056,17 +1056,17 @@ static void traverse(BVHOverlapData *data, BVHNode *node1, BVHNode *node2)
 			// check if node2 is a leaf
 			if(!node2->totnode)
 			{
-				
+
 				if(node1 == node2)
 				{
 					return;
 				}
-					
+
 				if(data->i >= data->max_overlap)
-				{	
+				{
 					// try to make alloc'ed memory bigger
 					data->overlap = realloc(data->overlap, sizeof(BVHTreeOverlap)*data->max_overlap*2);
-					
+
 					if(!data->overlap)
 					{
 						printf("Out of Memory in traverse\n");
@@ -1074,7 +1074,7 @@ static void traverse(BVHOverlapData *data, BVHNode *node1, BVHNode *node2)
 					}
 					data->max_overlap *= 2;
 				}
-				
+
 				// both leafs, insert overlap!
 				data->overlap[data->i].indexA = node1->index;
 				data->overlap[data->i].indexB = node2->index;
@@ -1092,7 +1092,7 @@ static void traverse(BVHOverlapData *data, BVHNode *node1, BVHNode *node2)
 		}
 		else
 		{
-			
+
 			for(j = 0; j < data->tree2->tree_type; j++)
 			{
 				if(node1->children[j])
@@ -1108,21 +1108,21 @@ BVHTreeOverlap *BLI_bvhtree_overlap(BVHTree *tree1, BVHTree *tree2, int *result)
 	int j, total = 0;
 	BVHTreeOverlap *overlap = NULL, *to = NULL;
 	BVHOverlapData **data;
-	
+
 	// check for compatibility of both trees (can't compare 14-DOP with 18-DOP)
 	if((tree1->axis != tree2->axis) && (tree1->axis == 14 || tree2->axis == 14) && (tree1->axis == 18 || tree2->axis == 18))
 		return 0;
-	
+
 	// fast check root nodes for collision before doing big splitting + traversal
 	if(!tree_overlap(tree1->nodes[tree1->totleaf], tree2->nodes[tree2->totleaf], MIN2(tree1->start_axis, tree2->start_axis), MIN2(tree1->stop_axis, tree2->stop_axis)))
 		return 0;
 
 	data = MEM_callocN(sizeof(BVHOverlapData *)* tree1->tree_type, "BVHOverlapData_star");
-	
+
 	for(j = 0; j < tree1->tree_type; j++)
 	{
 		data[j] = (BVHOverlapData *)MEM_callocN(sizeof(BVHOverlapData), "BVHOverlapData");
-		
+
 		// init BVHOverlapData
 		data[j]->overlap = (BVHTreeOverlap *)malloc(sizeof(BVHTreeOverlap)*MAX2(tree1->totleaf, tree2->totleaf));
 		data[j]->tree1 = tree1;
@@ -1138,25 +1138,25 @@ BVHTreeOverlap *BLI_bvhtree_overlap(BVHTree *tree1, BVHTree *tree2, int *result)
 	{
 		traverse(data[j], tree1->nodes[tree1->totleaf]->children[j], tree2->nodes[tree2->totleaf]);
 	}
-	
+
 	for(j = 0; j < tree1->tree_type; j++)
 		total += data[j]->i;
-	
+
 	to = overlap = (BVHTreeOverlap *)MEM_callocN(sizeof(BVHTreeOverlap)*total, "BVHTreeOverlap");
-	
+
 	for(j = 0; j < tree1->tree_type; j++)
 	{
 		memcpy(to, data[j]->overlap, data[j]->i*sizeof(BVHTreeOverlap));
 		to+=data[j]->i;
 	}
-	
+
 	for(j = 0; j < tree1->tree_type; j++)
 	{
 		free(data[j]->overlap);
 		MEM_freeN(data[j]);
 	}
 	MEM_freeN(data);
-	
+
 	(*result) = total;
 	return overlap;
 }
@@ -1339,7 +1339,7 @@ static void bfs_find_nearest(BVHNearestData *data, BVHNode *node)
 				push_heaps++;
 			}
 		}
-		
+
 		if(heap_size == 0) break;
 
 		current = heap[0];
@@ -1405,10 +1405,9 @@ int BLI_bvhtree_find_nearest(BVHTree *tree, const float *co, BVHTreeNearest *nea
  */
 
 //Determines the distance that the ray must travel to hit the bounding volume of the given node
-static float ray_nearest_hit(BVHRayCastData *data, BVHNode *node)
+static float ray_nearest_hit(BVHRayCastData *data, float *bv)
 {
 	int i;
-	const float *bv = node->bv;
 
 	float low = 0, upper = data->hit.dist;
 
@@ -1436,7 +1435,7 @@ static float ray_nearest_hit(BVHRayCastData *data, BVHNode *node)
 				if(lu > low)   low = lu;
 				if(ll < upper) upper = ll;
 			}
-	
+
 			if(low > upper) return FLT_MAX;
 		}
 	}
@@ -1449,7 +1448,7 @@ static void dfs_raycast(BVHRayCastData *data, BVHNode *node)
 
 	//ray-bv is really fast.. and simple tests revealed its worth to test it
 	//before calling the ray-primitive functions
-	float dist = ray_nearest_hit(data, node);
+	float dist = ray_nearest_hit(data, node->bv);
 	if(dist >= data->hit.dist) return;
 
 	if(node->totnode == 0)
@@ -1527,3 +1526,35 @@ int BLI_bvhtree_ray_cast(BVHTree *tree, const float *co, const float *dir, float
 	return data.hit.index;
 }
 
+float BLI_bvhtree_bb_raycast(float *bv, float *light_start, float *light_end, float *pos)
+{
+	BVHRayCastData data;
+	float dist = 0.0;
+	int i;
+
+	data.hit.dist = FLT_MAX;
+
+	// get light direction
+	data.ray.direction[0] = light_end[0] - light_start[0];
+	data.ray.direction[1] = light_end[1] - light_start[1];
+	data.ray.direction[2] = light_end[2] - light_start[2];
+
+	data.ray.radius = 0.0;
+
+	data.ray.origin[0] = light_start[0];
+	data.ray.origin[1] = light_start[1];
+	data.ray.origin[2] = light_start[2];
+
+	Normalize(data.ray.direction);
+	VECCOPY(data.ray_dot_axis, data.ray.direction);
+
+	dist = ray_nearest_hit(&data, bv);
+
+	if(dist > 0.0)
+	{
+		VECADDFAC(pos, light_start, data.ray.direction, dist);
+	}
+	return dist;
+
+}
+