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. @@
_______________________________________________
Bf-blender-cvs mailing list
[email protected]
http://lists.blender.org/mailman/listinfo/bf-blender-cvs
