Revision: 16010
http://projects.blender.org/plugins/scmsvn/viewcvs.php?view=rev&root=bf-blender&revision=16010
Author: jaguarandi
Date: 2008-08-07 22:12:56 +0200 (Thu, 07 Aug 2008)
Log Message:
-----------
Fixed compiling warnings of bvhutils.c
Commited the right version of BLI_kdopbvh.c
Modified Paths:
--------------
trunk/blender/source/blender/blenkernel/intern/bvhutils.c
trunk/blender/source/blender/blenlib/intern/BLI_kdopbvh.c
Modified: trunk/blender/source/blender/blenkernel/intern/bvhutils.c
===================================================================
--- trunk/blender/source/blender/blenkernel/intern/bvhutils.c 2008-08-07
20:00:58 UTC (rev 16009)
+++ trunk/blender/source/blender/blenkernel/intern/bvhutils.c 2008-08-07
20:12:56 UTC (rev 16010)
@@ -55,7 +55,7 @@
{
float dist;
- if(RayIntersectsTriangle(ray->origin, ray->direction, v0, v1, v2,
&dist, NULL))
+ if(RayIntersectsTriangle((float*)ray->origin, (float*)ray->direction,
(float*)v0, (float*)v1, (float*)v2, &dist, NULL))
return dist;
return FLT_MAX;
@@ -71,7 +71,7 @@
CalcNormFloat((float*)v0, (float*)v1, (float*)v2, plane_normal);
VECADDFAC( p1, ray->origin, ray->direction, m_dist);
- if(SweepingSphereIntersectsTriangleUV(ray->origin, p1, radius, v0, v1,
v2, &idist, &hit_point))
+ if(SweepingSphereIntersectsTriangleUV((float*)ray->origin, p1, radius,
(float*)v0, (float*)v1, (float*)v2, &idist, hit_point))
{
return idist * m_dist;
}
Modified: trunk/blender/source/blender/blenlib/intern/BLI_kdopbvh.c
===================================================================
--- trunk/blender/source/blender/blenlib/intern/BLI_kdopbvh.c 2008-08-07
20:00:58 UTC (rev 16009)
+++ trunk/blender/source/blender/blenlib/intern/BLI_kdopbvh.c 2008-08-07
20:12:56 UTC (rev 16010)
@@ -1,7 +1,5 @@
/**
*
- * $Id$
- *
* ***** BEGIN GPL LICENSE BLOCK *****
*
* This program is free software; you can redistribute it and/or
@@ -47,13 +45,11 @@
typedef struct BVHNode
{
- struct BVHNode **children; // max 8 children
- struct BVHNode *parent; // needed for bottom - top update
+ 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 traversed; // how many nodes already traversed until this level?
- char main_axis;
+ char main_axis; // Axis used to split this node
} BVHNode;
struct BVHTree
@@ -75,6 +71,7 @@
BVHTree *tree1, *tree2;
BVHTreeOverlap *overlap;
int i, max_overlap; /* i is number of overlaps */
+ int start_axis, stop_axis;
} BVHOverlapData;
typedef struct BVHNearestData
@@ -285,139 +282,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;
@@ -479,36 +346,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)
@@ -534,113 +371,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];
- node->children[i]->parent = node;
- }
- else
- {
- BVHNode *tnode = node->children[i] =
tree->nodes[free_node_index] = &(tree->nodearray[free_node_index]);
- tnode->parent = node;
-
- 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];
- node->children[i]->parent = node;
+ 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
- {
- node->children[i] = tree->nodes[free_node_index] =
&(tree->nodearray[free_node_index]);
- node->children[i]->parent = node;
-
- if(tend != end)
- partition_nth_element(tree->nodes, start, end,
tend, laxis);
-
- free_node_index += needed_branches(tree->tree_type,
tend-start);
- }
-
- start = tend;
+ break;
}
-
-#pragma omp parallel for private(i) schedule(static)
- for( i = 0; i < node->totnode; i++)
- {
- if(omp_data_end[i]-omp_data_start[i] > 1)
- {
- BVHNode *tnode = node->children[i];
- refit_kdop_hull(tree, tnode, omp_data_start[i],
omp_data_end[i]);
- bvh_div_nodes (tree, tnode, omp_data_start[i],
omp_data_end[i], omp_data_index[i]+1);
- }
- }
-
- return;
}
-
-static void print_tree(BVHTree *tree, BVHNode *node, int depth)
+/*
+ * Debug and information functions
+ */
+static void bvhtree_print_tree(BVHTree *tree, BVHNode *node, int depth)
{
int i;
for(i=0; i<depth; i++) printf(" ");
@@ -651,70 +417,89 @@
for(i=0; i<tree->tree_type; i++)
if(node->children[i])
- print_tree(tree, node->children[i], depth+1);
+ bvhtree_print_tree(tree, node->children[i], depth+1);
}
+static void bvhtree_info(BVHTree *tree)
+{
+ printf("BVHTree info\n");
+ printf("tree_type = %d, axis = %d, epsilon = %f\n", tree->tree_type,
tree->axis, tree->epsilon);
@@ Diff output truncated at 10240 characters. @@
_______________________________________________
Bf-blender-cvs mailing list
[email protected]
http://lists.blender.org/mailman/listinfo/bf-blender-cvs
