[Bf-blender-cvs] SVN commit: /data/svn/bf-blender [22360] branches/soc-2009-jaguarandi/ source/blender/render/intern/raytrace: *Added a tree structure with a variable number of childs per node, but with groupped childs (for SIMD)
André Pinto
andresusanopinto at gmail.com
Tue Aug 11 02:33:51 CEST 2009
Revision: 22360
http://projects.blender.org/plugins/scmsvn/viewcvs.php?view=rev&root=bf-blender&revision=22360
Author: jaguarandi
Date: 2009-08-11 02:33:51 +0200 (Tue, 11 Aug 2009)
Log Message:
-----------
*Added a tree structure with a variable number of childs per node, but with groupped childs (for SIMD)
*SIMD support for the first 4*N childs of each node
*Some bvh code organized
Modified Paths:
--------------
branches/soc-2009-jaguarandi/source/blender/render/intern/raytrace/bvh.h
branches/soc-2009-jaguarandi/source/blender/render/intern/raytrace/rayobject_vbvh.cpp
branches/soc-2009-jaguarandi/source/blender/render/intern/raytrace/reorganize.h
Added Paths:
-----------
branches/soc-2009-jaguarandi/source/blender/render/intern/raytrace/svbvh.h
Modified: branches/soc-2009-jaguarandi/source/blender/render/intern/raytrace/bvh.h
===================================================================
--- branches/soc-2009-jaguarandi/source/blender/render/intern/raytrace/bvh.h 2009-08-10 21:53:19 UTC (rev 22359)
+++ branches/soc-2009-jaguarandi/source/blender/render/intern/raytrace/bvh.h 2009-08-11 00:33:51 UTC (rev 22360)
@@ -28,6 +28,9 @@
*/
#include <xmmintrin.h>
+#ifndef RE_RAYTRACE_BVH_H
+#define RE_RAYTRACE_BVH_H
+
inline int test_bb_group4(__m128 *bb_group, const Isect *isec)
{
@@ -53,6 +56,12 @@
rtbuild_add( obj->builder, ob );
}
+template<class Node>
+inline bool is_leaf(Node *node)
+{
+ return !RayObject_isAligned(node);
+}
+
template<class Tree> static void bvh_done(Tree *obj);
template<class Tree>
@@ -93,14 +102,14 @@
template<class Node>
static void bvh_node_merge_bb(Node *node, float *min, float *max)
{
- if(RayObject_isAligned(node))
+ if(is_leaf(node))
{
- DO_MIN(node->bb , min);
- DO_MAX(node->bb+3, max);
+ RE_rayobject_merge_bb( (RayObject*)node, min, max);
}
else
{
- RE_rayobject_merge_bb( (RayObject*)node, min, max);
+ DO_MIN(node->bb , min);
+ DO_MAX(node->bb+3, max);
}
}
@@ -117,7 +126,7 @@
Node *stack[MAX_STACK_SIZE];
int hit = 0, stack_pos = 0;
- if(!TEST_ROOT && RayObject_isAligned(root))
+ if(!TEST_ROOT && !is_leaf(root))
bvh_node_push_childs(root, isec, stack, stack_pos);
else
stack[stack_pos++] = root;
@@ -125,7 +134,7 @@
while(stack_pos)
{
Node *node = stack[--stack_pos];
- if(RayObject_isAligned(node))
+ if(!is_leaf(node))
{
if(bvh_node_hit_test(node,isec))
{
@@ -157,9 +166,9 @@
if(!TEST_ROOT)
{
- if(RayObject_isAligned(root))
+ if(!is_leaf(root))
{
- if(RayObject_isAligned(root->child))
+ if(!is_leaf(root->child))
bvh_node_push_childs(root, isec, stack, stack_pos);
else
return RE_rayobject_intersect( (RayObject*)root->child, isec);
@@ -169,7 +178,7 @@
}
else
{
- if(RayObject_isAligned(root))
+ if(!is_leaf(root))
stack[stack_pos++] = root;
else
return RE_rayobject_intersect( (RayObject*)root, isec);
@@ -214,7 +223,7 @@
for(int i=0; i<4; i++)
{
Node *t = stack[stack_pos+i];
- assert(RayObject_isAligned(t));
+ assert(!is_leaf(t));
float *bb = ((float*)t_bb)+i;
bb[4*0] = t->bb[0];
@@ -237,7 +246,7 @@
if(res & (1<<i))
{
RE_RC_COUNT(isec->raycounter->bb.hit);
- if(RayObject_isAligned(t_node[i]))
+ if(!is_leaf(t_node[i]))
{
for(Node *t=t_node[i]; t; t=t->sibling)
{
@@ -255,11 +264,11 @@
else if(stack_pos > 0)
{
Node *node = stack[--stack_pos];
- assert(RayObject_isAligned(node));
+ assert(!is_leaf(node));
if(bvh_node_hit_test(node,isec))
{
- if(RayObject_isAligned(node->child))
+ if(!is_leaf(node->child))
{
bvh_node_push_childs(node, isec, stack, stack_pos);
assert(stack_pos <= MAX_STACK_SIZE);
@@ -291,7 +300,7 @@
{
int i;
for(i=0; i<BVH_NCHILDS; i++)
- if(RayObject_isAligned(node->child[i]))
+ if(!is_leaf(node->child[i]))
{
if(node->child[i] == 0) break;
@@ -308,7 +317,7 @@
{
int i;
for(i=BVH_NCHILDS-1; i>=0; i--)
- if(RayObject_isAligned(node->child[i]))
+ if(!is_leaf(node->child[i]))
{
if(node->child[i])
{
@@ -326,3 +335,5 @@
return hit;
}
*/
+
+#endif
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-10 21:53:19 UTC (rev 22359)
+++ branches/soc-2009-jaguarandi/source/blender/render/intern/raytrace/rayobject_vbvh.cpp 2009-08-11 00:33:51 UTC (rev 22360)
@@ -26,6 +26,12 @@
*
* ***** END GPL LICENSE BLOCK *****
*/
+#define RE_USE_HINT (0)
+static int tot_pushup = 0;
+static int tot_pushdown = 0;
+static int tot_hints = 0;
+
+
extern "C"
{
#include <assert.h>
@@ -41,22 +47,21 @@
#include "rayobject_hint.h"
#include "reorganize.h"
#include "bvh.h"
+#include "svbvh.h"
#include <queue>
-#define BVHNode VBVHNode
-#define BVHTree VBVHTree
-
#define RE_DO_HINTS (0)
#define RAY_BB_TEST_COST (0.2f)
#define DFS_STACK_SIZE 256
//#define DYNAMIC_ALLOC_BB
+
//#define rtbuild_split rtbuild_mean_split_largest_axis /* objects mean split on the longest axis, childs BB are allowed to overlap */
//#define rtbuild_split rtbuild_median_split_largest_axis /* space median split on the longest axis, childs BB are allowed to overlap */
#define rtbuild_split rtbuild_heuristic_object_split /* split objects using heuristic */
-struct BVHNode
+struct VBVHNode
{
#ifdef DYNAMIC_ALLOC_BB
float *bb;
@@ -64,15 +69,15 @@
float bb[6];
#endif
- BVHNode *child;
- BVHNode *sibling;
+ VBVHNode *child;
+ VBVHNode *sibling;
};
-struct BVHTree
+struct VBVHTree
{
RayObject rayobj;
- BVHNode *root;
+ SVBVHNode *root;
MemArena *node_arena;
@@ -81,6 +86,54 @@
};
+
+
+template<class Tree,class OldNode>
+struct Reorganize_VBVH
+{
+ Tree *tree;
+
+ Reorganize_VBVH(Tree *t)
+ {
+ tree = t;
+ }
+
+ VBVHNode *create_node()
+ {
+ VBVHNode *node = (VBVHNode*)BLI_memarena_alloc(tree->node_arena, sizeof(VBVHNode));
+ return node;
+ }
+
+ void copy_bb(VBVHNode *node, OldNode *old)
+ {
+ std::copy( old->bb, old->bb+6, node->bb );
+ }
+
+ VBVHNode *transform(OldNode *old)
+ {
+ if(is_leaf(old))
+ return (VBVHNode*)old;
+
+ VBVHNode *node = create_node();
+ VBVHNode **child_ptr = &node->child;
+ node->sibling = 0;
+
+ copy_bb(node,old);
+
+ for(OldNode *o_child = old->child; o_child; o_child = o_child->sibling)
+ {
+ VBVHNode *n_child = transform(o_child);
+ *child_ptr = n_child;
+ if(is_leaf(n_child)) return node;
+ child_ptr = &n_child->sibling;
+ }
+ *child_ptr = 0;
+
+ return node;
+ }
+};
+
+
/*
* Push nodes (used on dfs)
*/
@@ -89,7 +142,7 @@
{
Node *child = node->child;
- if(!RayObject_isAligned(child))
+ if(is_leaf(child))
{
stack[stack_pos++] = child;
}
@@ -99,7 +152,7 @@
{
//Skips BB tests on primitives
/*
- if(!RayObject_isAligned(child->child))
+ if(is_leaf(child->child))
stack[stack_pos++] = child->child;
else
*/
@@ -113,9 +166,9 @@
/*
* BVH done
*/
-static BVHNode *bvh_new_node(BVHTree *tree)
+static VBVHNode *bvh_new_node(VBVHTree *tree)
{
- BVHNode *node = (BVHNode*)BLI_memarena_alloc(tree->node_arena, sizeof(BVHNode));
+ VBVHNode *node = (VBVHNode*)BLI_memarena_alloc(tree->node_arena, sizeof(VBVHNode));
if( (((intptr_t)node) & (0x0f)) != 0 )
{
@@ -132,79 +185,16 @@
return node;
}
-template<class Builder>
-float rtbuild_area(Builder *builder)
-{
- float min[3], max[3];
- INIT_MINMAX(min, max);
- rtbuild_merge_bb(builder, min, max);
- return bb_area(min, max);
-}
-template<class Node>
-void bvh_update_bb(Node *node)
-{
- INIT_MINMAX(node->bb, node->bb+3);
- Node *child = node->child;
-
- while(child)
- {
- bvh_node_merge_bb(child, node->bb, node->bb+3);
- if(RayObject_isAligned(child))
- child = child->sibling;
- else
- child = 0;
- }
-}
-
-static int tot_pushup = 0;
-static int tot_pushdown = 0;
-static int tot_hints = 0;
-
template<class Node>
-void pushdown(Node *parent)
-{
- Node **s_child = &parent->child;
- Node * child = parent->child;
-
- while(child && RayObject_isAligned(child))
- {
- Node *next = child->sibling;
- Node **next_s_child = &child->sibling;
-
- //assert(bb_fits_inside(parent->bb, parent->bb+3, child->bb, child->bb+3));
-
- for(Node *i = parent->child; RayObject_isAligned(i) && i; i = i->sibling)
- if(child != i && bb_fits_inside(i->bb, i->bb+3, child->bb, child->bb+3) && RayObject_isAligned(i->child))
- {
-// todo optimize (should the one with the smallest area?)
-// float ia = bb_area(i->bb, i->bb+3)
-// if(child->i)
- *s_child = child->sibling;
- child->sibling = i->child;
- i->child = child;
- next_s_child = s_child;
-
- tot_pushdown++;
- break;
- }
- child = next;
- s_child = next_s_child;
- }
-
- for(Node *i = parent->child; RayObject_isAligned(i) && i; i = i->sibling)
- pushdown( i );
-}
-
-template<class Node>
int count_childs(Node *parent)
{
int n = 0;
for(Node *i = parent->child; i; i = i->sibling)
{
n++;
- if(!RayObject_isAligned(i))
+ if(is_leaf(i))
break;
}
@@ -220,40 +210,7 @@
node->sibling = sibling;
}
-template<class Node>
-void pushup(Node *parent)
-{
- float p_area = bb_area(parent->bb, parent->bb+3);
- Node **prev = &parent->child;
- for(Node *child = parent->child; RayObject_isAligned(child) && child; )
- {
- float c_area = bb_area(child->bb, child->bb+3) ;
- int nchilds = count_childs(child);
- float original_cost = (c_area / p_area)*nchilds + 1;
- float flatten_cost = nchilds;
- if(flatten_cost < original_cost && nchilds >= 2)
- {
- append_sibling(child, child->child);
- child = child->sibling;
- *prev = child;
-// *prev = child->child;
-// append_sibling( *prev, child->sibling );
-// child = *prev;
- tot_pushup++;
- }
- else
- {
- *prev = child;
- prev = &(*prev)->sibling;
- child = *prev;
- }
- }
-
- for(Node *child = parent->child; RayObject_isAligned(child) && child; child = child->sibling)
- pushup(child);
-}
-
template<class Tree, class Node, class Builder>
Node *bvh_rearrange(Tree *tree, Builder *builder)
{
@@ -264,7 +221,7 @@
Node *node = bvh_new_node(tree);
INIT_MINMAX(node->bb, node->bb+3);
rtbuild_merge_bb(builder, node->bb, node->bb+3);
- node->child = (BVHNode*) rtbuild_get_primitive( builder, 0 );
+ node->child = (VBVHNode*) rtbuild_get_primitive( builder, 0 );
return node;
}
else
@@ -292,30 +249,8 @@
}
}
-template<class Node>
-float bvh_refit(Node *node)
-{
- if(!RayObject_isAligned(node)) return 0;
- if(!RayObject_isAligned(node->child)) return 0;
-
- float total = 0;
-
- for(Node *child = node->child; child; child = child->sibling)
- total += bvh_refit(child);
-
- float old_area = bb_area(node->bb, node->bb+3);
- INIT_MINMAX(node->bb, node->bb+3);
- for(Node *child = node->child; child; child = child->sibling)
- {
- DO_MIN(child->bb, node->bb);
- DO_MAX(child->bb+3, node->bb+3);
- }
- total += old_area - bb_area(node->bb, node->bb+3);
- return total;
-}
-
template<>
-void bvh_done<BVHTree>(BVHTree *obj)
+void bvh_done<VBVHTree>(VBVHTree *obj)
{
rtbuild_done(obj->builder);
@@ -323,18 +258,47 @@
if(needed_nodes > BLI_MEMARENA_STD_BUFSIZE)
needed_nodes = BLI_MEMARENA_STD_BUFSIZE;
- obj->node_arena = BLI_memarena_new(needed_nodes);
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list