[Bf-blender-cvs] SVN commit: /data/svn/bf-blender [15956] branches/soc-2008-jaguarandi/ source/blender/blenlib/intern/BLI_kdopbvh.c: Another 8bit diet
André Pinto
andresusanopinto at gmail.com
Mon Aug 4 22:54:00 CEST 2008
Revision: 15956
http://projects.blender.org/plugins/scmsvn/viewcvs.php?view=rev&root=bf-blender&revision=15956
Author: jaguarandi
Date: 2008-08-04 22:53:52 +0200 (Mon, 04 Aug 2008)
Log Message:
-----------
Another 8bit diet
Modified Paths:
--------------
branches/soc-2008-jaguarandi/source/blender/blenlib/intern/BLI_kdopbvh.c
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-04 20:30:57 UTC (rev 15955)
+++ branches/soc-2008-jaguarandi/source/blender/blenlib/intern/BLI_kdopbvh.c 2008-08-04 20:53:52 UTC (rev 15956)
@@ -48,8 +48,8 @@
struct BVHNode **children; // max 8 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;
+
} BVHNode;
struct BVHTree
@@ -495,6 +495,8 @@
create_kdop_hull(tree, node, co, numpoints, 0);
node->index= index;
+ node->children = NULL;
+
// inflate the bv with some epsilon
for (i = tree->start_axis; i < tree->stop_axis; i++)
{
@@ -538,12 +540,12 @@
const int slice = (end-start)/tree->tree_type; //division rounded down
const int rest = (end-start)%tree->tree_type; //remainder of division
- assert( node->totnode == 0 );
+ assert( node->children[0] == NULL);
node->main_axis = laxis/2;
// split nodes along longest axis
- for (i=0; start < end; node->totnode = ++i) //i counts the current child
+ for (i=0; start < end; i++) //i counts the current child
{
int tend = start + slice + (i < rest ? 1 : 0);
@@ -582,13 +584,14 @@
int omp_data_start[tree->tree_type];
int omp_data_end [tree->tree_type];
int omp_data_index[tree->tree_type];
+ int totnode = 0;
- assert( node->totnode == 0 );
+ assert( node->children[0] == NULL );
node->main_axis = laxis/2;
// split nodes along longest axis
- for (i=0; start < end; node->totnode = ++i) //i counts the current child
+ for (i=0; start < end; ++i, ++totnode) //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);
@@ -618,7 +621,7 @@
}
#pragma omp parallel for private(i) schedule(static)
- for( i = 0; i < node->totnode; i++)
+ for( i = 0; i < totnode; i++)
{
if(omp_data_end[i]-omp_data_start[i] > 1)
{
@@ -728,10 +731,10 @@
if(tree_overlap(node1, node2, MIN2(data->tree1->start_axis, data->tree2->start_axis), MIN2(data->tree1->stop_axis, data->tree2->stop_axis)))
{
// check if node1 is a leaf
- if(!node1->totnode)
+ if(node1->children == NULL)
{
// check if node2 is a leaf
- if(!node2->totnode)
+ if(node2->children == NULL)
{
if(node1 == node2)
@@ -785,6 +788,7 @@
int j, total = 0;
BVHTreeOverlap *overlap = NULL, *to = NULL;
BVHOverlapData **data;
+ BVHNode *root;
// 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))
@@ -808,11 +812,12 @@
data[j]->i = 0;
}
+ root = tree1->nodes[tree1->totleaf];
+
#pragma omp parallel for private(j) schedule(static)
- for(j = 0; j < MIN2(tree1->tree_type, tree1->nodes[tree1->totleaf]->totnode); j++)
- {
- traverse(data[j], tree1->nodes[tree1->totleaf]->children[j], tree2->nodes[tree2->totleaf]);
- }
+ for(j = 0; j < tree1->tree_type; j++)
+ if(root->children[j])
+ traverse(data[j], root->children[j], tree2->nodes[tree2->totleaf]);
for(j = 0; j < tree1->tree_type; j++)
total += data[j]->i;
@@ -973,7 +978,7 @@
sdist = calc_nearest_point(data, node, nearest);
if(sdist >= data->nearest.dist) return;
- if(node->totnode == 0)
+ if(node->children == NULL)
{
if(data->callback)
data->callback(data->userdata , node->index, data->co, &data->nearest);
@@ -986,8 +991,11 @@
}
else
{
- for(i=0; i != node->totnode; i++)
- dfs_find_nearest(data, node->children[i]);
+ for(i=0; i != data->tree->tree_type; i++)
+ if(node->children[i])
+ dfs_find_nearest(data, node->children[i]);
+ else
+ break;
}
}
@@ -1084,7 +1092,7 @@
float dist = ray_nearest_hit(data, node);
if(dist >= data->hit.dist) return;
- if(node->totnode == 0)
+ if(node->children == NULL)
{
if(data->callback)
data->callback(data->userdata, node->index, &data->ray, &data->hit);
@@ -1100,17 +1108,18 @@
//pick loop direction to dive into the tree (based on ray direction and split axis)
if(data->ray_dot_axis[ node->main_axis ] > 0)
{
- for(i=0; i != node->totnode; i++)
- {
- dfs_raycast(data, node->children[i]);
- }
+ for(i=0; i != data->tree->tree_type; i++)
+ if(node->children[i])
+ dfs_raycast(data, node->children[i]);
+ else
+ break;
}
else
{
- for(i=node->totnode-1; i >= 0; i--)
- {
- dfs_raycast(data, node->children[i]);
- }
+ for(i=data->tree->tree_type; i >= 0; i--)
+ if(node->children[i])
+ dfs_raycast(data, node->children[i]);
+
}
}
}
More information about the Bf-blender-cvs
mailing list