[Bf-blender-cvs] SVN commit: /data/svn/bf-blender [16000] branches/soc-2008-jaguarandi/ source/blender: Added several comments to BLI_kdopbvh

André Pinto andresusanopinto at gmail.com
Thu Aug 7 16:26:27 CEST 2008


Revision: 16000
          http://projects.blender.org/plugins/scmsvn/viewcvs.php?view=rev&root=bf-blender&revision=16000
Author:   jaguarandi
Date:     2008-08-07 16:26:27 +0200 (Thu, 07 Aug 2008)

Log Message:
-----------
Added several comments to BLI_kdopbvh
Changed BENCH to print both wall-clock/real time and cpu time

Modified Paths:
--------------
    branches/soc-2008-jaguarandi/source/blender/blenkernel/intern/shrinkwrap.c
    branches/soc-2008-jaguarandi/source/blender/blenlib/intern/BLI_kdopbvh.c

Modified: branches/soc-2008-jaguarandi/source/blender/blenkernel/intern/shrinkwrap.c
===================================================================
--- branches/soc-2008-jaguarandi/source/blender/blenkernel/intern/shrinkwrap.c	2008-08-07 14:21:43 UTC (rev 15999)
+++ branches/soc-2008-jaguarandi/source/blender/blenkernel/intern/shrinkwrap.c	2008-08-07 14:26:27 UTC (rev 16000)
@@ -63,44 +63,27 @@
 #if 1
 
 
-#if 0
-#define BENCH(a)	\
-	do {			\
-		clock_t _clock_init = clock();	\
-		(a);							\
-		printf("%s: %fms\n", #a, (float)(clock()-_clock_init)*1000/CLOCKS_PER_SEC);	\
-	} while(0)
-
-#define BENCH_VAR(name)		clock_t JOIN(_bench_step,name) = 0, JOIN(_bench_total,name) = 0
-#define BENCH_BEGIN(name)	JOIN(_bench_step, name) = clock()
-#define BENCH_END(name)		JOIN(_bench_total,name) += clock() - JOIN(_bench_step,name)
-#define BENCH_RESET(name)	JOIN(_bench_total, name) = 0
-#define BENCH_REPORT(name)	printf("%s: %fms\n", TO_STR(name), JOIN(_bench_total,name)*1000.0f/CLOCKS_PER_SEC)
-
-#else
 #include <sys/time.h>
 
 #define BENCH(a)	\
 	do {			\
 		double _t1, _t2;				\
 		struct timeval _tstart, _tend;	\
+		clock_t _clock_init = clock();	\
 		gettimeofday ( &_tstart, NULL);	\
 		(a);							\
 		gettimeofday ( &_tend, NULL);	\
 		_t1 = ( double ) _tstart.tv_sec + ( double ) _tstart.tv_usec/ ( 1000*1000 );	\
 		_t2 = ( double )   _tend.tv_sec + ( double )   _tend.tv_usec/ ( 1000*1000 );	\
-		printf("%s: %fms\n", #a, _t2-_t1);\
+		printf("%s: %fs (real) %fs (cpu)\n", #a, _t2-_t1, (float)(clock()-_clock_init)/CLOCKS_PER_SEC);\
 	} while(0)
 
 #define BENCH_VAR(name)		clock_t JOIN(_bench_step,name) = 0, JOIN(_bench_total,name) = 0
 #define BENCH_BEGIN(name)	JOIN(_bench_step, name) = clock()
 #define BENCH_END(name)		JOIN(_bench_total,name) += clock() - JOIN(_bench_step,name)
 #define BENCH_RESET(name)	JOIN(_bench_total, name) = 0
-#define BENCH_REPORT(name)	printf("%s: %fms\n", TO_STR(name), JOIN(_bench_total,name)*1000.0f/CLOCKS_PER_SEC)
+#define BENCH_REPORT(name)	printf("%s: %fms (cpu) \n", TO_STR(name), JOIN(_bench_total,name)*1000.0f/CLOCKS_PER_SEC)
 
-
-#endif
-
 #else
 
 #define BENCH(a)	(a)
@@ -1109,12 +1092,11 @@
 
 		if(index != -1)
 		{
-			float dist;
+			float dist = nearest.dist;
+			if(dist > 1e-5) weight *= (dist - calc->keptDist)/dist;
+
 			VECCOPY(tmp_co, nearest.co);
 			space_transform_invert(&calc->local2target, tmp_co);
-
-			dist = VecLenf(co, tmp_co);
-			if(dist > 1e-5) weight *= (dist - calc->keptDist)/dist;
 			VecLerpf(co, co, tmp_co, weight);	//linear interpolation
 		}
 	}
@@ -1349,7 +1331,7 @@
 			}
 			else
 			{
-				float dist = VecLenf(tmp_co, nearest.co);
+				float dist = sasqrt( nearest.dist );
 				VecLerpf(tmp_co, tmp_co, nearest.co, (dist - calc->keptDist)/dist);	//linear interpolation
 			}
 			space_transform_invert(&calc->local2target, tmp_co);

Modified: branches/soc-2008-jaguarandi/source/blender/blenlib/intern/BLI_kdopbvh.c
===================================================================
--- branches/soc-2008-jaguarandi/source/blender/blenlib/intern/BLI_kdopbvh.c	2008-08-07 14:21:43 UTC (rev 15999)
+++ branches/soc-2008-jaguarandi/source/blender/blenlib/intern/BLI_kdopbvh.c	2008-08-07 14:26:27 UTC (rev 16000)
@@ -45,11 +45,11 @@
 
 typedef struct BVHNode
 {
-	struct BVHNode **children;	// max 8 children
+	struct BVHNode **children;
 	float *bv;		// Bounding volume of all nodes, max 13 axis
 	int index;		// face, edge, vertex index
 	char totnode;	// how many nodes are used, used for speedup
-	char main_axis;
+	char main_axis;	// Axis used to split this node
 } BVHNode;
 
 struct BVHTree
@@ -281,139 +281,9 @@
 
 //////////////////////////////////////////////////////////////////////////////////////////////////////
 
-void BLI_bvhtree_free(BVHTree *tree)
-{	
-	if(tree)
-	{
-		MEM_freeN(tree->nodes);
-		MEM_freeN(tree->nodearray);
-		MEM_freeN(tree->nodebv);
-		MEM_freeN(tree->nodechild);
-		MEM_freeN(tree);
-	}
-}
-
-// calculate max number of branches
-int needed_branches(int tree_type, int leafs)
-{
-#if 1
-	//Worst case scenary  ( return max(0, leafs-tree_type)+1 )
-	if(leafs <= tree_type)
-		return 1;
-	else
-		return leafs-tree_type+1;
-
-#else
-	//If our bvh kdop is "almost perfect"
-	//TODO i dont trust the float arithmetic in here (and I am not sure this formula is according to our splitting method)
-	int i, numbranches = 0;
-	for(i = 1; i <= (int)ceil((float)((float)log(leafs)/(float)log(tree_type))); i++)
-		numbranches += (pow(tree_type, i) / tree_type);
-
-	return numbranches;
-#endif
-}
-		
-
-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;
-
-	tree = (BVHTree *)MEM_callocN(sizeof(BVHTree), "BVHTree");
-	
-	if(tree)
-	{
-		tree->epsilon = epsilon;
-		tree->tree_type = tree_type; 
-		tree->axis = axis;
-		
-		if(axis == 26)
-		{
-			tree->start_axis = 0;
-			tree->stop_axis = 13;
-		}
-		else if(axis == 18)
-		{
-			tree->start_axis = 7;
-			tree->stop_axis = 13;
-		}
-		else if(axis == 14)
-		{
-			tree->start_axis = 0;
-			tree->stop_axis = 7;
-		}
-		else if(axis == 8) // AABB
-		{
-			tree->start_axis = 0;
-			tree->stop_axis = 4;
-		}
-		else if(axis == 6) // OBB
-		{
-			tree->start_axis = 0;
-			tree->stop_axis = 3;
-		}
-		else
-		{
-			MEM_freeN(tree);
-			return NULL;
-		}
-
-
-		//Allocate arrays
-		numnodes = maxsize + 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)
-		{
-			MEM_freeN(tree->nodes);
-			MEM_freeN(tree);
-		}
-
-		tree->nodechild = (BVHNode**)MEM_callocN(sizeof(BVHNode*) * tree_type * numnodes, "BVHNodeBV");
-		if(!tree->nodechild)
-		{
-			MEM_freeN(tree->nodebv);
-			MEM_freeN(tree->nodes);
-			MEM_freeN(tree);
-		}
-
-		tree->nodearray = (BVHNode *)MEM_callocN(sizeof(BVHNode)* numnodes, "BVHNodeArray");
-		
-		if(!tree->nodearray)
-		{
-			MEM_freeN(tree->nodechild);
-			MEM_freeN(tree->nodebv);
-			MEM_freeN(tree->nodes);
-			MEM_freeN(tree);
-			return NULL;
-		}
-
-		//link the dynamic bv and child links
-		for(i=0; i< numnodes; i++)
-		{
-			tree->nodearray[i].bv = tree->nodebv + i * axis;
-			tree->nodearray[i].children = tree->nodechild + i * tree_type;
-		}
-		
-	}
-
-	return tree;
-}
-
-
+/*
+ * BVHTree bounding volumes functions
+ */
 static void create_kdop_hull(BVHTree *tree, BVHNode *node, float *co, int numpoints, int moving)
 {
 	float newminmax;
@@ -475,36 +345,6 @@
 
 }
 
-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 
-	}
-
-	return 1;
-}
-
 // only supports x,y,z axis in the moment
 // but we should use a plain and simple function here for speed sake
 static char get_largest_axis(float *bv)
@@ -530,109 +370,42 @@
 	}
 }
 
-static void bvh_div_nodes(BVHTree *tree, BVHNode *node, int start, int end, int free_node_index)
+// bottom-up update of bvh node BV
+// join the children on the parent BV
+static void node_join(BVHTree *tree, BVHNode *node)
 {
-	int i;
-
-	const char laxis = get_largest_axis(node->bv); 	//determine longest axis to split along
-	const int  slice = (end-start)/tree->tree_type;	//division rounded down
-	const int  rest  = (end-start)%tree->tree_type;	//remainder of division
+	int i, j;
 	
-	assert( node->totnode == 0 );
-
-	node->main_axis = laxis/2;
-	
-	// split nodes along longest axis
-	for (i=0; start < end; node->totnode = ++i) //i counts the current child
-	{	
-		int tend = start + slice + (i < rest ? 1 : 0);
-		
-		assert( tend <= end);
-		
-		if(tend-start == 1)	// ok, we have 1 left for this node
-		{
-			node->children[i] = tree->nodes[start];
-		}
-		else
-		{
-			BVHNode *tnode = node->children[i] = tree->nodes[free_node_index] = &(tree->nodearray[free_node_index]);
-			
-			if(tend != end)
-				partition_nth_element(tree->nodes, start, end, tend, laxis);
-
-			refit_kdop_hull(tree, tnode, start, tend);
-
-			bvh_div_nodes(tree, tnode, start, tend, free_node_index+1);
-			free_node_index += needed_branches(tree->tree_type, tend-start);
-		}
-		start = tend;
+	for (i = tree->start_axis; i < tree->stop_axis; i++)
+	{
+		node->bv[2*i] = FLT_MAX;
+		node->bv[2*i + 1] = -FLT_MAX;
 	}
 	
-	return;
-}
-
-static void omp_bvh_div_nodes(BVHTree *tree, BVHNode *node, int start, int end, int free_node_index)
-{
-	int i;
-
-	const char laxis = get_largest_axis(node->bv); 	//determine longest axis to split along
-	const int  slice = (end-start)/tree->tree_type;	//division rounded down
-	const int  rest  = (end-start)%tree->tree_type;	//remainder of division
-
-	int omp_data_start[tree->tree_type];
-	int omp_data_end  [tree->tree_type];
-	int omp_data_index[tree->tree_type];
-	
-	assert( node->totnode == 0 );
-
-	node->main_axis = laxis/2;	
-
-	// split nodes along longest axis
-	for (i=0; start < end; node->totnode = ++i) //i counts the current child
-	{	
-		//Split the rest from left to right (TODO: this doenst makes an optimal tree)
-		int tend = start + slice + (i < rest ? 1 : 0);
-		
-		assert( tend <= end);
-		
-		//save data for later OMP
-		omp_data_start[i] = start;
-		omp_data_end  [i] = tend;
-		omp_data_index[i] = free_node_index;
-
-		if(tend-start == 1)
+	for (i = 0; i < tree->tree_type; i++)
+	{
+		if (node->children[i]) 
 		{
-			node->children[i] = tree->nodes[start];
+			for (j = tree->start_axis; j < tree->stop_axis; 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 
+				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];
+			}
 		}
 		else
-		{

@@ Diff output truncated at 10240 characters. @@




More information about the Bf-blender-cvs mailing list