Revision: 21320
http://projects.blender.org/plugins/scmsvn/viewcvs.php?view=rev&root=bf-blender&revision=21320
Author: jaguarandi
Date: 2009-07-02 17:45:15 +0200 (Thu, 02 Jul 2009)
Log Message:
-----------
*RTBuilder now supports splitting leafs in N leafs
something is wrong on rayobject_bvh as it looks slower than BLI_bvh and code is
based on it
Modified Paths:
--------------
branches/soc-2009-jaguarandi/source/blender/render/intern/include/rayobject_rtbuild.h
branches/soc-2009-jaguarandi/source/blender/render/intern/source/rayobject.c
branches/soc-2009-jaguarandi/source/blender/render/intern/source/rayobject_bvh.c
branches/soc-2009-jaguarandi/source/blender/render/intern/source/rayobject_rtbuild.c
Modified:
branches/soc-2009-jaguarandi/source/blender/render/intern/include/rayobject_rtbuild.h
===================================================================
---
branches/soc-2009-jaguarandi/source/blender/render/intern/include/rayobject_rtbuild.h
2009-07-02 15:05:46 UTC (rev 21319)
+++
branches/soc-2009-jaguarandi/source/blender/render/intern/include/rayobject_rtbuild.h
2009-07-02 15:45:15 UTC (rev 21320)
@@ -41,7 +41,7 @@
* generate with simple calls, and then convert to the theirs
* specific structure on the fly.
*/
-#define MAX_CHILDS 32
+#define RTBUILD_MAX_CHILDS 32
typedef struct RTBuilder
{
/* list to all primitives in this tree */
@@ -51,7 +51,7 @@
int split_axis;
/* child partitions calculated during splitting */
- int child_offset[MAX_CHILDS+1];
+ int child_offset[RTBUILD_MAX_CHILDS+1];
} RTBuilder;
@@ -67,5 +67,6 @@
/* Calculates child partitions and returns number of efectively needed
partitions */
int rtbuild_mean_split(RTBuilder *b, int nchilds, int axis);
int rtbuild_mean_split_largest_axis(RTBuilder *b, int nchilds);
+int rtbuild_get_largest_axis(RTBuilder *b);
#endif
Modified:
branches/soc-2009-jaguarandi/source/blender/render/intern/source/rayobject.c
===================================================================
---
branches/soc-2009-jaguarandi/source/blender/render/intern/source/rayobject.c
2009-07-02 15:05:46 UTC (rev 21319)
+++
branches/soc-2009-jaguarandi/source/blender/render/intern/source/rayobject.c
2009-07-02 15:45:15 UTC (rev 21320)
@@ -296,6 +296,7 @@
RE_RC_COUNT(isec->count->raycast.test);
/* Setup vars used on raycast */
+ isec->labda *= Normalize(isec->vec);
isec->dist = VecLength(isec->vec);
for(i=0; i<3; i++)
Modified:
branches/soc-2009-jaguarandi/source/blender/render/intern/source/rayobject_bvh.c
===================================================================
---
branches/soc-2009-jaguarandi/source/blender/render/intern/source/rayobject_bvh.c
2009-07-02 15:05:46 UTC (rev 21319)
+++
branches/soc-2009-jaguarandi/source/blender/render/intern/source/rayobject_bvh.c
2009-07-02 15:45:15 UTC (rev 21320)
@@ -35,7 +35,7 @@
#include "rayobject_rtbuild.h"
#include "rayobject.h"
-#define BVH_NCHILDS 2
+#define BVH_NCHILDS 4
typedef struct BVHTree BVHTree;
static int bvh_intersect(BVHTree *obj, Isect *isec);
@@ -57,7 +57,7 @@
struct BVHNode
{
BVHNode *child[BVH_NCHILDS];
- float bb[2][3];
+ float *bb; //[6]; //[2][3];
};
struct BVHTree
@@ -65,6 +65,7 @@
RayObject rayobj;
BVHNode *alloc, *next_node, *root;
+ float *bb_alloc, *bb_next;
RTBuilder *builder;
};
@@ -90,6 +91,9 @@
if(obj->alloc)
MEM_freeN(obj->alloc);
+ if(obj->bb_alloc)
+ MEM_freeN(obj->bb_alloc);
+
MEM_freeN(obj);
}
@@ -99,8 +103,8 @@
if(RayObject_isAligned(node))
{
//TODO only half operations needed
- DO_MINMAX(node->bb[0], min, max);
- DO_MINMAX(node->bb[1], min, max);
+ DO_MINMAX(node->bb , min, max);
+ DO_MINMAX(node->bb+3, min, max);
}
else
{
@@ -121,18 +125,40 @@
int hit = 0;
if(RE_rayobject_bb_intersect(isec, (const float*)node->bb) != FLT_MAX)
{
- int i;
- for(i=0; i<BVH_NCHILDS; i++)
- if(RayObject_isAligned(node->child[i]))
- {
- hit |= dfs_raycast(node->child[i], isec);
- if(hit && isec->mode == RE_RAY_SHADOW) return
hit;
- }
- else
- {
- hit |= RE_rayobject_intersect(
(RayObject*)node->child[i], isec);
- if(hit && isec->mode == RE_RAY_SHADOW) return
hit;
- }
+// if(isec->idot_axis[node->split_axis] > 0.0f)
+ {
+ int i;
+ for(i=0; i<BVH_NCHILDS; i++)
+ if(RayObject_isAligned(node->child[i]))
+ {
+ if(node->child[i] == 0) break;
+
+ hit |= dfs_raycast(node->child[i],
isec);
+ if(hit && isec->mode == RE_RAY_SHADOW)
return hit;
+ }
+ else
+ {
+ hit |= RE_rayobject_intersect(
(RayObject*)node->child[i], isec);
+ if(hit && isec->mode == RE_RAY_SHADOW)
return hit;
+ }
+ }
+/*
+ else
+ {
+ int i;
+ for(i=BVH_NCHILDS-1; i>=0; i--)
+ if(RayObject_isAligned(node->child[i]))
+ {
+ hit |= dfs_raycast(node->child[i],
isec);
+ if(hit && isec->mode == RE_RAY_SHADOW)
return hit;
+ }
+ else
+ {
+ hit |= RE_rayobject_intersect(
(RayObject*)node->child[i], isec);
+ if(hit && isec->mode == RE_RAY_SHADOW)
return hit;
+ }
+ }
+*/
}
return hit;
}
@@ -154,11 +180,36 @@
rtbuild_add( obj->builder, ob );
}
+static BVHNode *bvh_new_node(BVHTree *tree)
+{
+ BVHNode *node = tree->next_node++;
+ node->bb = tree->bb_next;
+ tree->bb_next += 6;
+
+ return node;
+}
+
static BVHNode *bvh_rearrange(BVHTree *tree, RTBuilder *builder)
{
if(rtbuild_size(builder) == 1)
{
- return (BVHNode*)builder->begin[0];
+// return (BVHNode*)builder->begin[0];
+//
+//
+ int i;
+ BVHNode *parent = bvh_new_node(tree);
+
+ INIT_MINMAX(parent->bb, parent->bb+3);
+
+ for(i=0; i<1; i++)
+ {
+ parent->child[i] = (BVHNode*)builder->begin[i];
+ bvh_merge_bb(parent->child[i], parent->bb,
parent->bb+3);
+ }
+ for(; i<BVH_NCHILDS; i++)
+ parent->child[i] = 0;
+
+ return parent;
}
else
{
@@ -166,15 +217,17 @@
int nc = rtbuild_mean_split_largest_axis(builder, BVH_NCHILDS);
RTBuilder tmp;
- BVHNode *parent = tree->next_node++;
+ BVHNode *parent = bvh_new_node(tree);
- INIT_MINMAX(parent->bb[0], parent->bb[1]);
+ INIT_MINMAX(parent->bb, parent->bb+3);
// bvh->split_axis = tmp->split_axis;
for(i=0; i<nc; i++)
{
parent->child[i] = bvh_rearrange( tree,
rtbuild_get_child(builder, i, &tmp) );
- bvh_merge_bb(parent->child[i], parent->bb[0],
parent->bb[1]);
+ bvh_merge_bb(parent->child[i], parent->bb,
parent->bb+3);
}
+ for(; i<BVH_NCHILDS; i++)
+ parent->child[i] = 0;
return parent;
}
@@ -189,6 +242,10 @@
assert(needed_nodes > 0);
obj->alloc = (BVHNode*)MEM_mallocN( sizeof(BVHNode)*needed_nodes,
"BVHTree.Nodes");
obj->next_node = obj->alloc;
+
+ obj->bb_alloc = (float*)MEM_mallocN( sizeof(float)*6*needed_nodes,
"BVHTree.Nodes");
+ obj->bb_next = obj->bb_alloc;
+
obj->root = bvh_rearrange( obj, obj->builder );
assert(obj->alloc+needed_nodes >= obj->next_node);
Modified:
branches/soc-2009-jaguarandi/source/blender/render/intern/source/rayobject_rtbuild.c
===================================================================
---
branches/soc-2009-jaguarandi/source/blender/render/intern/source/rayobject_rtbuild.c
2009-07-02 15:05:46 UTC (rev 21319)
+++
branches/soc-2009-jaguarandi/source/blender/render/intern/source/rayobject_rtbuild.c
2009-07-02 15:45:15 UTC (rev 21320)
@@ -1,3 +1,6 @@
+#include <assert.h>
+#include <math.h>
+
#include "rayobject_rtbuild.h"
#include "MEM_guardedalloc.h"
#include "BLI_arithb.h"
@@ -2,3 +5,2 @@
#include "BKE_utildefines.h"
-#include <assert.h>
@@ -16,7 +18,7 @@
b->end = end;
b->split_axis = 0;
- for(i=0; i<MAX_CHILDS; i++)
+ for(i=0; i<RTBUILD_MAX_CHILDS; i++)
b->child_offset[i] = 0;
}
@@ -59,7 +61,7 @@
RE_rayobject_merge_bb(*index, min, max);
}
-static int calc_largest_axis(RTBuilder *b)
+int rtbuild_get_largest_axis(RTBuilder *b)
{
float min[3], max[3], sub[3];
@@ -84,25 +86,44 @@
}
-//Unballanced mean
-//TODO better balance nodes
-//TODO suport for variable number of partitions (its hardcoded in 2)
+//Left balanced tree
int rtbuild_mean_split(RTBuilder *b, int nchilds, int axis)
{
+ int i;
+ int leafs_per_child;
+ int tot_leafs = rtbuild_size(b);
+
+ long long s;
+
+ assert(nchilds <= RTBUILD_MAX_CHILDS);
+
+ //TODO optimize calc of leafs_per_child
+ for(s=nchilds; s<tot_leafs; s*=nchilds);
+ leafs_per_child = s/nchilds;
+
+ assert(leafs_per_child*nchilds >= tot_leafs);
+
b->child_offset[0] = 0;
- b->child_offset[1] = (b->end - b->begin) / 2;
- b->child_offset[2] = (b->end - b->begin);
-
- assert( b->child_offset[0] != b->child_offset[1] && b->child_offset[1]
!= b->child_offset[2]);
-
- split_leafs(b, b->child_offset, 2, axis);
- return 2;
+ for(i=1; ; i++)
+ {
+ assert(i <= nchilds);
+
+ b->child_offset[i] = b->child_offset[i-1] + leafs_per_child;
+ if(b->child_offset[i] >= tot_leafs)
+ {
+ b->child_offset[i] = tot_leafs;
+ split_leafs(b, b->child_offset, i, axis);
+
+ assert(i > 1);
+ return i;
+ }
+ }
}
int rtbuild_mean_split_largest_axis(RTBuilder *b, int nchilds)
{
- int axis = calc_largest_axis(b);
+ int axis = rtbuild_get_largest_axis(b);
return rtbuild_mean_split(b, nchilds, axis);
}
_______________________________________________
Bf-blender-cvs mailing list
[email protected]
http://lists.blender.org/mailman/listinfo/bf-blender-cvs
