[Bf-blender-cvs] SVN commit: /data/svn/bf-blender [22433] branches/soc-2009-jaguarandi/ source/blender/render/intern/raytrace: Another tree pass during build to increase the number of nodes that have multipe of 4childs

[Andre Susano Pinto]

Revision: 22433
          http://projects.blender.org/plugins/scmsvn/viewcvs.php?view=rev&root=bf-blender&revision=22433
Author:   jaguarandi
Date:     2009-08-13 17:56:24 +0200 (Thu, 13 Aug 2009)

Log Message:
-----------
Another tree pass during build to increase the number of nodes that have multipe of 4childs

Modified Paths:
--------------
    branches/soc-2009-jaguarandi/source/blender/render/intern/raytrace/rayobject_vbvh.cpp
    branches/soc-2009-jaguarandi/source/blender/render/intern/raytrace/reorganize.h

Modified: branches/soc-2009-jaguarandi/source/blender/render/intern/raytrace/rayobject_vbvh.cpp
===================================================================
--- branches/soc-2009-jaguarandi/source/blender/render/intern/raytrace/rayobject_vbvh.cpp	2009-08-13 15:13:44 UTC (rev 22432)
+++ branches/soc-2009-jaguarandi/source/blender/render/intern/raytrace/rayobject_vbvh.cpp	2009-08-13 15:56:24 UTC (rev 22433)
@@ -270,6 +270,7 @@
 	
 	pushup(root);
 	pushdown(root);
+	pushup_simd<VBVHNode,4>(root);
 
 	//Memory re-organize
 	if(0)

Modified: branches/soc-2009-jaguarandi/source/blender/render/intern/raytrace/reorganize.h
===================================================================
--- branches/soc-2009-jaguarandi/source/blender/render/intern/raytrace/reorganize.h	2009-08-13 15:13:44 UTC (rev 22432)
+++ branches/soc-2009-jaguarandi/source/blender/render/intern/raytrace/reorganize.h	2009-08-13 15:56:24 UTC (rev 22433)
@@ -144,6 +144,8 @@
 template<class Node>
 void pushup(Node *parent)
 {
+	if(is_leaf(parent)) return;
+	
 	float p_area = bb_area(parent->bb, parent->bb+3);
 	Node **prev = &parent->child;
 	for(Node *child = parent->child; RayObject_isAligned(child) && child; )
@@ -175,6 +177,38 @@
 		pushup(child);
 }
 
+/*
+ * try to optimize number of childs to be a multiple of SSize
+ */
+template<class Node, int SSize>
+void pushup_simd(Node *parent)
+{
+	if(is_leaf(parent)) return;
+	
+	int n = count_childs(parent);
+		
+	Node **prev = &parent->child;
+	for(Node *child = parent->child; RayObject_isAligned(child) && child; )
+	{
+		int cn = count_childs(child);
+		if(cn-1 <= (SSize - (n%SSize) ) % SSize && RayObject_isAligned(child->child) )
+		{
+			n += (cn - 1);
+			append_sibling(child, child->child);
+			child = child->sibling;
+			*prev = child;	
+		}
+		else
+		{
+			*prev = child;
+			prev = &(*prev)->sibling;
+			child = *prev;
+		}		
+	}
+		
+	for(Node *child = parent->child; RayObject_isAligned(child) && child; child = child->sibling)
+		pushup_simd<Node,SSize>(child);
+}
 
 
 /*