[Bf-blender-cvs] SVN commit: /data/svn/bf-blender [16377] trunk/blender/source/blender/ blenlib/intern/BLI_kdopbvh.c: bvh nodes got parent node reference again

Daniel Genrich daniel.genrich at gmx.net
Fri Sep 5 13:55:39 CEST 2008


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;





More information about the Bf-blender-cvs mailing list