[Bf-blender-cvs] SVN commit: /data/svn/bf-blender [15955] branches/soc-2008-jaguarandi/ source/blender/blenlib/intern/BLI_kdopbvh.c: Shrink BVHNode by 16bits

[André Pinto]

Revision: 15955
          http://projects.blender.org/plugins/scmsvn/viewcvs.php?view=rev&root=bf-blender&revision=15955
Author:   jaguarandi
Date:     2008-08-04 22:30:57 +0200 (Mon, 04 Aug 2008)

Log Message:
-----------
Shrink BVHNode by 16bits

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 19:12:42 UTC (rev 15954)
+++ branches/soc-2008-jaguarandi/source/blender/blenlib/intern/BLI_kdopbvh.c	2008-08-04 20:30:57 UTC (rev 15955)
@@ -45,12 +45,10 @@
 
 typedef struct BVHNode
 {
-	struct BVHNode **children; // max 8 children
-	struct BVHNode *parent; // needed for bottom - top update
-	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?
+	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;
 
@@ -554,13 +552,10 @@
 		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]);
-//			printf("Used %d (%d)\n", free_node_index, tend-start);
-			tnode->parent = node;
 			
 			if(tend != end)
 				partition_nth_element(tree->nodes, start, end, tend, laxis);
@@ -608,7 +603,6 @@
 		if(tend-start == 1)
 		{
 			node->children[i] = tree->nodes[start];
-			node->children[i]->parent = node;
 		}
 		else
 		{
@@ -905,23 +899,13 @@
 // call BLI_bvhtree_update_node() first for every node/point/triangle
 void BLI_bvhtree_update_tree(BVHTree *tree)
 {
-	BVHNode *leaf, *parent;
-	
-	// reset tree traversing flag
-	for (leaf = tree->nodearray + tree->totleaf; leaf != tree->nodearray + tree->totleaf + tree->totbranch; leaf++)
-		leaf->traversed = 0;
-	
-	for (leaf = tree->nodearray; leaf != tree->nodearray + tree->totleaf; leaf++)
-	{
-		for (parent = leaf->parent; parent; parent = parent->parent)
-		{
-			parent->traversed++;	// we tried to go up in hierarchy 
-			if (parent->traversed < parent->totnode) 
-				break;	// we do not need to check further 
-			else 
-				node_join(tree, parent);
-		}
-	}
+	BVHNode** root  = tree->nodes + tree->totleaf;
+	BVHNode** index = tree->nodes + tree->totleaf + tree->totbranch-1;
+
+	//Update bottom=>top
+	//TRICKY: the way we build the tree the parent of a child has an index < then the child index
+	for (; index != root; index--)
+		node_join(tree, *index);
 }
 
 float BLI_bvhtree_getepsilon(BVHTree *tree)