Revision: 16377
http://projects.blender.org/plugins/scmsvn/viewcvs.php?view=rev&root=bf-blender&revision=16377
Author: genscher
Date: 2008-09-05 13:55:39 +0200 (Fri, 05 Sep 2008)
Log Message:
-----------
bvh nodes got parent node reference again
Modified Paths:
--------------
trunk/blender/source/blender/blenlib/intern/BLI_kdopbvh.c
Modified: trunk/blender/source/blender/blenlib/intern/BLI_kdopbvh.c
===================================================================
--- trunk/blender/source/blender/blenlib/intern/BLI_kdopbvh.c 2008-09-05
07:12:04 UTC (rev 16376)
+++ trunk/blender/source/blender/blenlib/intern/BLI_kdopbvh.c 2008-09-05
11:55:39 UTC (rev 16377)
@@ -51,6 +51,7 @@
typedef struct BVHNode
{
struct BVHNode **children;
+ struct BVHNode *parent; // some user defined traversed need that
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
@@ -700,6 +701,10 @@
BVHBuildHelper data;
int depth;
+
+ // set parent from root node to NULL
+ BVHNode *tmp = branches_array+0;
+ tmp->parent = NULL;
//Most of bvhtree code relies on 1-leaf trees having at least one branch
//We handle that special case here
@@ -709,7 +714,8 @@
refit_kdop_hull(tree, root, 0, num_leafs);
root->main_axis = get_largest_axis(root->bv) / 2;
root->totnode = 1;
- root->children[0] = leafs_array[0];
+ root->children[0] = leafs_array[0];
+ root->children[0]->parent = root;
return;
}
@@ -772,9 +778,15 @@
int child_leafs_end =
implicit_leafs_index(&data, depth+1, child_level_index+1);
if(child_leafs_end - child_leafs_begin > 1)
+ {
parent->children[k] = branches_array +
child_index;
+ parent->children[k]->parent = parent;
+ }
else if(child_leafs_end - child_leafs_begin ==
1)
+ {
parent->children[k] = leafs_array[
child_leafs_begin ];
+ parent->children[k]->parent = parent;
+ }
else
break;
@@ -1089,6 +1101,66 @@
return;
}
+// general function for traversing the tree
+void BLI_bvhtree_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
+ if(!node1->totnode)
+ {
+ // 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");
+ return;
+ }
+ data->max_overlap *= 2;
+ }
+
+ // both leafs, insert overlap!
+ data->overlap[data->i].indexA = node1->index;
+ data->overlap[data->i].indexB = node2->index;
+
+ data->i++;
+ }
+ else
+ {
+ for(j = 0; j < data->tree2->tree_type; j++)
+ {
+ if(node2->children[j])
+ traverse(data, node1,
node2->children[j]);
+ }
+ }
+ }
+ else
+ {
+
+ for(j = 0; j < data->tree2->tree_type; j++)
+ {
+ if(node1->children[j])
+ traverse(data, node1->children[j],
node2);
+ }
+ }
+ }
+ return;
+}
+
BVHTreeOverlap *BLI_bvhtree_overlap(BVHTree *tree1, BVHTree *tree2, int
*result)
{
int j, total = 0;
_______________________________________________
Bf-blender-cvs mailing list
[email protected]
http://lists.blender.org/mailman/listinfo/bf-blender-cvs
