[Bf-blender-cvs] SVN commit: /data/svn/bf-blender [21391] branches/soc-2009-jaguarandi/ source/blender/render/intern: *Added BLI_memarena on bvh
André Pinto
andresusanopinto at gmail.com
Mon Jul 6 21:45:00 CEST 2009
Revision: 21391
http://projects.blender.org/plugins/scmsvn/viewcvs.php?view=rev&root=bf-blender&revision=21391
Author: jaguarandi
Date: 2009-07-06 21:45:00 +0200 (Mon, 06 Jul 2009)
Log Message:
-----------
*Added BLI_memarena on bvh
*Median split support on rtbuild
Modified Paths:
--------------
branches/soc-2009-jaguarandi/source/blender/render/intern/include/rayobject_rtbuild.h
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-06 17:29:32 UTC (rev 21390)
+++ branches/soc-2009-jaguarandi/source/blender/render/intern/include/rayobject_rtbuild.h 2009-07-06 19:45:00 UTC (rev 21391)
@@ -65,8 +65,12 @@
RTBuilder* rtbuild_get_child(RTBuilder *b, int child, RTBuilder *tmp);
/* Calculates child partitions and returns number of efectively needed partitions */
+int rtbuild_get_largest_axis(RTBuilder *b);
+
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);
+int rtbuild_median_split(RTBuilder *b, float *separators, int nchilds, int axis);
+int rtbuild_median_split_largest_axis(RTBuilder *b, int nchilds);
+
#endif
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-06 17:29:32 UTC (rev 21390)
+++ branches/soc-2009-jaguarandi/source/blender/render/intern/source/rayobject_bvh.c 2009-07-06 19:45:00 UTC (rev 21391)
@@ -32,10 +32,16 @@
#include "MEM_guardedalloc.h"
#include "BKE_utildefines.h"
#include "BLI_arithb.h"
+#include "BLI_memarena.h"
#include "RE_raytrace.h"
#include "rayobject_rtbuild.h"
#include "rayobject.h"
+#define DYNAMIC_ALLOC
+
+#define SPLIT_OVERLAP_MEAN_LONGEST_AXIS /* objects mean split on the longest axis, childs BB are allowed to overlap */
+//#define SPLIT_OVERLAP_MEDIAN_LONGEST_AXIS /* space median split on the longest axis, childs BB are allowed to overlap */
+
#define BVH_NCHILDS 4
typedef struct BVHTree BVHTree;
@@ -58,7 +64,11 @@
struct BVHNode
{
BVHNode *child[BVH_NCHILDS];
+#ifdef DYNAMIC_ALLOC
+ float bb[6];
+#else
float *bb; //[6]; //[2][3];
+#endif
int split_axis;
};
@@ -68,8 +78,12 @@
BVHNode *root;
+#ifdef DYNAMIC_ALLOC
+ MemArena *node_arena;
+#else
BVHNode *node_alloc, *node_next;
float *bb_alloc, *bb_next;
+#endif
RTBuilder *builder;
};
@@ -83,8 +97,12 @@
obj->rayobj.api = &bvh_api;
obj->root = NULL;
+#ifdef DYNAMIC_ALLOC
+ obj->node_arena = NULL;
+#else
obj->node_alloc = obj->node_next = NULL;
obj->bb_alloc = obj->bb_next = NULL;
+#endif
obj->builder = rtbuild_create( size );
return RayObject_unalignRayAPI((RayObject*) obj);
@@ -95,11 +113,16 @@
if(obj->builder)
rtbuild_free(obj->builder);
+#ifdef DYNAMIC_ALLOC
+ if(obj->node_arena)
+ BLI_memarena_free(obj->node_arena);
+#else
if(obj->node_alloc)
MEM_freeN(obj->node_alloc);
if(obj->bb_alloc)
MEM_freeN(obj->bb_alloc);
+#endif
MEM_freeN(obj);
}
@@ -190,6 +213,10 @@
static BVHNode *bvh_new_node(BVHTree *tree, int nid)
{
+#ifdef DYNAMIC_ALLOC
+ BVHNode *node = BLI_memarena_alloc(tree->node_arena, sizeof(BVHNode));
+ return node;
+#else
BVHNode *node = tree->node_alloc + nid - 1;
assert(RayObject_isAligned(node));
if(node+1 > tree->node_next)
@@ -199,6 +226,7 @@
tree->bb_next += 6;
return node;
+#endif
}
static int child_id(int pid, int nchild)
@@ -209,6 +237,9 @@
static BVHNode *bvh_rearrange(BVHTree *tree, RTBuilder *builder, int nid)
{
+ if(rtbuild_size(builder) == 0)
+ return 0;
+
if(rtbuild_size(builder) == 1)
{
RayObject *child = builder->begin[0];
@@ -242,11 +273,18 @@
else
{
int i;
- int nc = rtbuild_mean_split_largest_axis(builder, BVH_NCHILDS);
RTBuilder tmp;
-
BVHNode *parent = bvh_new_node(tree, nid);
+ int nc;
+#ifdef SPLIT_OVERLAP_MEAN_LONGEST_AXIS
+ nc = rtbuild_mean_split_largest_axis(builder, BVH_NCHILDS);
+#elif defined(SPLIT_OVERLAP_MEDIAN_LONGEST_AXIS)
+ nc = rtbuild_median_split_largest_axis(builder, BVH_NCHILDS);
+#else
+ assert(0);
+#endif
+
INIT_MINMAX(parent->bb, parent->bb+3);
parent->split_axis = builder->split_axis;
for(i=0; i<nc; i++)
@@ -261,31 +299,48 @@
}
}
+/*
static void bvh_info(BVHTree *obj)
{
printf("BVH: Used %d nodes\n", obj->node_next - obj->node_alloc);
}
+*/
static void bvh_done(BVHTree *obj)
{
+
+
+#ifdef DYNAMIC_ALLOC
+ int needed_nodes = (rtbuild_size(obj->builder)+1)*2;
+ if(needed_nodes > BLI_MEMARENA_STD_BUFSIZE)
+ needed_nodes = BLI_MEMARENA_STD_BUFSIZE;
+
+ obj->node_arena = BLI_memarena_new(needed_nodes);
+ BLI_memarena_use_malloc(obj->node_arena);
+
+#else
int needed_nodes;
- assert(obj->root == NULL && obj->node_alloc == NULL && obj->bb_alloc == NULL && obj->builder);
//TODO exact calculate needed nodes
needed_nodes = (rtbuild_size(obj->builder)+1)*2;
assert(needed_nodes > 0);
+ BVHNode *node = BLI_memarena_alloc(tree->node_arena, sizeof(BVHNode));
+ return node;
obj->node_alloc = (BVHNode*)MEM_mallocN( sizeof(BVHNode)*needed_nodes, "BVHTree.Nodes");
obj->node_next = obj->node_alloc;
obj->bb_alloc = (float*)MEM_mallocN( sizeof(float)*6*needed_nodes, "BVHTree.NodesBB");
obj->bb_next = obj->bb_alloc;
+#endif
obj->root = bvh_rearrange( obj, obj->builder, 1 );
+
+#ifndef DYNAMIC_ALLOC
+ assert(obj->node_alloc+needed_nodes >= obj->node_next);
+#endif
rtbuild_free( obj->builder );
obj->builder = NULL;
-
- assert(obj->node_alloc+needed_nodes >= obj->node_next);
}
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-06 17:29:32 UTC (rev 21390)
+++ branches/soc-2009-jaguarandi/source/blender/render/intern/source/rayobject_rtbuild.c 2009-07-06 19:45:00 UTC (rev 21391)
@@ -1,5 +1,6 @@
#include <assert.h>
#include <math.h>
+#include <stdlib.h>
#include "rayobject_rtbuild.h"
#include "MEM_guardedalloc.h"
@@ -8,6 +9,7 @@
static int partition_nth_element(RTBuilder *b, int _begin, int _end, int n);
static void split_leafs(RTBuilder *b, int *nth, int partitions, int split_axis);
+static int split_leafs_by_plane(RTBuilder *b, int begin, int end, float plane);
static void rtbuild_init(RTBuilder *b, RayObject **begin, RayObject **end)
@@ -61,12 +63,9 @@
RE_rayobject_merge_bb(*index, min, max);
}
-int rtbuild_get_largest_axis(RTBuilder *b)
+static int largest_axis(float *min, float *max)
{
- float min[3], max[3], sub[3];
-
- INIT_MINMAX(min, max);
- merge_bb( b, min, max);
+ float sub[3];
sub[0] = max[0]-min[0];
sub[1] = max[1]-min[1];
@@ -87,7 +86,22 @@
}
}
+int rtbuild_get_largest_axis(RTBuilder *b)
+{
+ float min[3], max[3];
+ INIT_MINMAX(min, max);
+ merge_bb( b, min, max);
+
+ return largest_axis(min,max);
+}
+
+
+/*
+int rtbuild_median_split(RTBuilder *b, int nchilds, int axis)
+{
+}
+*/
//Left balanced tree
int rtbuild_mean_split(RTBuilder *b, int nchilds, int axis)
{
@@ -146,8 +160,125 @@
return rtbuild_mean_split(b, nchilds, axis);
}
+/*
+ * "separators" is an array of dim NCHILDS-1
+ * and indicates where to cut the childs
+ */
+int rtbuild_median_split(RTBuilder *b, float *separators, int nchilds, int axis)
+{
+ int size = rtbuild_size(b);
+
+ assert(nchilds <= RTBUILD_MAX_CHILDS);
+ if(size <= nchilds)
+ {
+ return rtbuild_mean_split(b, nchilds, axis);
+ }
+ else
+ {
+ int i;
+ b->split_axis = axis;
+
+ //Calculate child offsets
+ b->child_offset[0] = 0;
+ for(i=0; i<nchilds-1; i++)
+ b->child_offset[i+1] = split_leafs_by_plane(b, b->child_offset[i], size, separators[i]);
+ b->child_offset[nchilds] = size;
+
+ for(i=0; i<nchilds; i++)
+ if(b->child_offset[i+1] - b->child_offset[i] == size)
+ return rtbuild_mean_split(b, nchilds, axis);
+
+ return nchilds;
+ }
+}
+
+int rtbuild_median_split_largest_axis(RTBuilder *b, int nchilds)
+{
+ int la, i;
+ float separators[RTBUILD_MAX_CHILDS];
+ float min[3], max[3];
+
+ INIT_MINMAX(min, max);
+ merge_bb( b, min, max);
+
+ la = largest_axis(min,max);
+ for(i=1; i<nchilds; i++)
+ separators[i-1] = (max[la]-min[la])*i / nchilds;
+
+ return rtbuild_median_split(b, separators, nchilds, la);
+}
+
+//Heuristics Splitter
+typedef struct CostEvent CostEvent;
+
+struct CostEvent
+{
+ float key;
+ float value;
+};
+
+int costevent_cmp(const CostEvent *a, const CostEvent *b)
+{
+ if(a->key < b->key) return -1;
+ if(a->key > b->key) return 1;
+ if(a->value < b->value) return -1;
+ if(a->value > b->value) return 1;
+ return 0;
+}
+
+void costevent_sort(CostEvent *begin, CostEvent *end)
+{
+ //TODO introsort
+ qsort(begin, sizeof(*begin), end-begin, (int(*)(const void *, const void *)) costevent_cmp);
+}
+
/*
+int rtbuild_heuristic_split(RTBuilder *b, int nchilds)
+{
+ int size = rtbuild_size(b);
+
+ if(size <= nchilds)
+ {
+ return rtbuild_mean_split_largest_axis(b, nchilds);
+ }
+ else
+ {
+ CostEvent *events[3], *ev[3];
+ RayObject *index;
+ int a = 0;
+
+ for(a = 0; a<3; a++)
+ ev[a] = events[a] = MEM_malloc( sizeof(CostEvent)*2*size, "RTBuilder.SweepSplitCostEvent" );
+
+ for(index = b->begin; b != b->end; b++)
+ {
+ float min[3], max[3];
+ INIT_MINMAX(min, max);
+ RE_rayobject_merge_bb(index, min, max);
+ for(a = 0; a<3; a++)
+ {
+ ev[a]->key = min[a];
+ ev[a]->value = 1;
+ ev[a]++;
+
+ ev[a]->key = max[a];
+ ev[a]->value = -1;
+ ev[a]++;
+ }
+ }
+ for(a = 0; a<3; a++)
+ costevent_sort(events[a], ev[a]);
+
+
+
+ for(a = 0; a<3; a++)
+ MEM_freeN(ev[a]);
+ }
+}
+*/
+
+/*
* Helper code
* PARTITION code / used on mean-split
* basicly this a std::nth_element (like on C++ STL algorithm)
@@ -268,3 +399,17 @@
partition_nth_element(b, nth[i], nth[i+1], nth[partitions] );
}
}
+
+static int split_leafs_by_plane(RTBuilder *b, int begin, int end, float plane)
+{
+ int i;
+ for(i = begin; i != end; i++)
+ {
+ if(sort_get_value(b, i) < plane)
+ {
+ sort_swap(b, i, begin);
+ begin++;
+ }
+ }
+ return begin;
+}
More information about the Bf-blender-cvs
mailing list