Revision: 21324
http://projects.blender.org/plugins/scmsvn/viewcvs.php?view=rev&root=bf-blender&revision=21324
Author: jaguarandi
Date: 2009-07-02 23:57:50 +0200 (Thu, 02 Jul 2009)
Log Message:
-----------
*fixed rtbuild (there was a sorting bug introduced while adapting code from
BLI_bvh)
This bvh should be at least as fast as BLI_kdopbvh now
Modified Paths:
--------------
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/source/rayobject.c
===================================================================
---
branches/soc-2009-jaguarandi/source/blender/render/intern/source/rayobject.c
2009-07-02 20:46:35 UTC (rev 21323)
+++
branches/soc-2009-jaguarandi/source/blender/render/intern/source/rayobject.c
2009-07-02 21:57:50 UTC (rev 21324)
@@ -42,8 +42,9 @@
* Based on Tactical Optimization of Ray/Box Intersection, by Graham Fyffe
* [http://tog.acm.org/resources/RTNews/html/rtnv21n1.html#art9]
*/
-float RE_rayobject_bb_intersect(const Isect *isec, const float *bb)
+float RE_rayobject_bb_intersect(const Isect *isec, const float *_bb)
{
+ const float *bb = _bb;
float dist;
float t1x = (bb[isec->bv_index[0]] - isec->start[0]) *
isec->idot_axis[0];
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 20:46:35 UTC (rev 21323)
+++
branches/soc-2009-jaguarandi/source/blender/render/intern/source/rayobject_bvh.c
2009-07-02 21:57:50 UTC (rev 21324)
@@ -27,6 +27,7 @@
* ***** END GPL LICENSE BLOCK *****
*/
#include <assert.h>
+#include <stdio.h>
#include "MEM_guardedalloc.h"
#include "BKE_utildefines.h"
@@ -58,6 +59,7 @@
{
BVHNode *child[BVH_NCHILDS];
float *bb; //[6]; //[2][3];
+ char split_axis;
};
struct BVHTree
@@ -125,7 +127,7 @@
int hit = 0;
if(RE_rayobject_bb_intersect(isec, (const float*)node->bb) != FLT_MAX)
{
-// if(isec->idot_axis[node->split_axis] > 0.0f)
+ if(isec->idot_axis[node->split_axis] > 0.0f)
{
int i;
for(i=0; i<BVH_NCHILDS; i++)
@@ -142,7 +144,6 @@
if(hit && isec->mode == RE_RAY_SHADOW)
return hit;
}
}
-/*
else
{
int i;
@@ -158,7 +159,6 @@
if(hit && isec->mode == RE_RAY_SHADOW)
return hit;
}
}
-*/
}
return hit;
}
@@ -180,24 +180,33 @@
rtbuild_add( obj->builder, ob );
}
-static BVHNode *bvh_new_node(BVHTree *tree)
+static BVHNode *bvh_new_node(BVHTree *tree, int nid)
{
- BVHNode *node = tree->next_node++;
+ BVHNode *node = tree->alloc + nid - 1;
+ if(node+1 > tree->next_node)
+ tree->next_node = node+1;
+
node->bb = tree->bb_next;
tree->bb_next += 6;
return node;
}
-static BVHNode *bvh_rearrange(BVHTree *tree, RTBuilder *builder)
+static int child_id(int pid, int nchild)
{
+ //N child of node A = A * K + (2 - K) + N, (0 <= N < K)
+ return pid*BVH_NCHILDS+(2-BVH_NCHILDS)+nchild;
+}
+
+static BVHNode *bvh_rearrange(BVHTree *tree, RTBuilder *builder, int nid)
+{
if(rtbuild_size(builder) == 1)
{
// return (BVHNode*)builder->begin[0];
//
//
int i;
- BVHNode *parent = bvh_new_node(tree);
+ BVHNode *parent = bvh_new_node(tree, nid);
INIT_MINMAX(parent->bb, parent->bb+3);
@@ -217,13 +226,13 @@
int nc = rtbuild_mean_split_largest_axis(builder, BVH_NCHILDS);
RTBuilder tmp;
- BVHNode *parent = bvh_new_node(tree);
+ BVHNode *parent = bvh_new_node(tree, nid);
INIT_MINMAX(parent->bb, parent->bb+3);
-// bvh->split_axis = tmp->split_axis;
+ parent->split_axis = builder->split_axis;
for(i=0; i<nc; i++)
{
- parent->child[i] = bvh_rearrange( tree,
rtbuild_get_child(builder, i, &tmp) );
+ parent->child[i] = bvh_rearrange( tree,
rtbuild_get_child(builder, i, &tmp), child_id(nid,i) );
bvh_merge_bb(parent->child[i], parent->bb,
parent->bb+3);
}
for(; i<BVH_NCHILDS; i++)
@@ -243,13 +252,15 @@
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_alloc = (float*)MEM_mallocN( sizeof(float)*6*needed_nodes,
"BVHTree.NodesBB");
obj->bb_next = obj->bb_alloc;
- obj->root = bvh_rearrange( obj, obj->builder );
+ obj->root = bvh_rearrange( obj, obj->builder, 1 );
assert(obj->alloc+needed_nodes >= obj->next_node);
+ printf("BVH: Used %d nodes\n", obj->next_node-obj->alloc);
+
rtbuild_free( obj->builder );
obj->builder = NULL;
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 20:46:35 UTC (rev 21323)
+++
branches/soc-2009-jaguarandi/source/blender/render/intern/source/rayobject_rtbuild.c
2009-07-02 21:57:50 UTC (rev 21324)
@@ -67,8 +67,10 @@
INIT_MINMAX(min, max);
merge_bb( b, min, max);
-
- VECSUB(sub, max, min);
+
+ sub[0] = max[0]-min[0];
+ sub[1] = max[1]-min[1];
+ sub[2] = max[2]-min[2];
if(sub[0] > sub[1])
{
if(sub[0] > sub[2])
@@ -90,8 +92,9 @@
int rtbuild_mean_split(RTBuilder *b, int nchilds, int axis)
{
int i;
- int leafs_per_child;
+ int mleafs_per_child, Mleafs_per_child;
int tot_leafs = rtbuild_size(b);
+ int missing_leafs;
long long s;
@@ -99,25 +102,41 @@
//TODO optimize calc of leafs_per_child
for(s=nchilds; s<tot_leafs; s*=nchilds);
- leafs_per_child = s/nchilds;
+ Mleafs_per_child = s/nchilds;
+ mleafs_per_child = Mleafs_per_child/nchilds;
- assert(leafs_per_child*nchilds >= tot_leafs);
+ //split min leafs per child
+ b->child_offset[0] = 0;
+ for(i=1; i<=nchilds; i++)
+ b->child_offset[i] = mleafs_per_child;
- b->child_offset[0] = 0;
- for(i=1; ; i++)
+ //split remaining leafs
+ missing_leafs = tot_leafs - mleafs_per_child*nchilds;
+ for(i=1; i<=nchilds; i++)
{
- assert(i <= nchilds);
-
- b->child_offset[i] = b->child_offset[i-1] + leafs_per_child;
- if(b->child_offset[i] >= tot_leafs)
+ if(missing_leafs > Mleafs_per_child - mleafs_per_child)
{
- b->child_offset[i] = tot_leafs;
- split_leafs(b, b->child_offset, i, axis);
-
- assert(i > 1);
- return i;
+ b->child_offset[i] += Mleafs_per_child -
mleafs_per_child;
+ missing_leafs -= Mleafs_per_child - mleafs_per_child;
}
+ else
+ {
+ b->child_offset[i] += missing_leafs;
+ missing_leafs = 0;
+ break;
+ }
}
+
+ //adjust for accumulative offsets
+ for(i=1; i<=nchilds; i++)
+ b->child_offset[i] += b->child_offset[i-1];
+
+ //Count created childs
+ for(i=nchilds; b->child_offset[i] == b->child_offset[i-1]; i--);
+ split_leafs(b, b->child_offset, i, axis);
+
+ assert( b->child_offset[0] == 0 && b->child_offset[i] == tot_leafs );
+ return i;
}
@@ -166,15 +185,15 @@
}
else
{
- if(fc > fb)
- return b;
- else
+ if(fc < fb)
{
- if(fc > fa)
+ if(fc < fa)
+ return a;
+ else
return c;
- else
- return a;
}
+ else
+ return b;
}
}
@@ -203,14 +222,9 @@
int i=lo, j=hi;
while (1)
{
- while(sort_get_value(b,i) < x)
- i++;
-
+ while(sort_get_value(b,i) < x) i++;
j--;
-
- while(x < sort_get_value(b,j))
- j--;
-
+ while(x < sort_get_value(b,j)) j--;
if(!(i < j))
return i;
@@ -226,7 +240,7 @@
// after a call to this function you can expect one of:
// every node to left of a[n] are smaller or equal to it
// every node to the right of a[n] are greater or equal to it
-static int partition_nth_element(RTBuilder *b, int _begin, int _end, int n)
+static int partition_nth_element(RTBuilder *b, int _begin, int n, int _end)
{
int begin = _begin, end = _end, cut;
while(end-begin > 3)
@@ -246,10 +260,10 @@
{
int i;
b->split_axis = split_axis;
+
for(i=0; i < partitions-1; i++)
{
- if(nth[i] >= nth[partitions])
- break;
+ assert(nth[i] < nth[i+1] && nth[i+1] < nth[partitions]);
partition_nth_element(b, nth[i], nth[i+1], nth[partitions] );
}
_______________________________________________
Bf-blender-cvs mailing list
Bf-blender-cvs@blender.org
http://lists.blender.org/mailman/listinfo/bf-blender-cvs
