Revision: 21551
http://projects.blender.org/plugins/scmsvn/viewcvs.php?view=rev&root=bf-blender&revision=21551
Author: jaguarandi
Date: 2009-07-12 20:04:10 +0200 (Sun, 12 Jul 2009)
Log Message:
-----------
*Moved rtbuild to bf_render_raytrace
*Added vbvh - Just a experimental tree type :)
Variable Way BVH - there is no hardcoded number of childs per each Tree Node
- idea is to optimize a tree to reduced the expected number of BB tests even
after applying SAH (for that an hardcoded n-way is not enough)
- for now childs are stored on a linked list
Modified Paths:
--------------
branches/soc-2009-jaguarandi/source/blender/blenlib/BLI_memarena.h
branches/soc-2009-jaguarandi/source/blender/render/extern/include/RE_raytrace.h
branches/soc-2009-jaguarandi/source/blender/render/intern/include/rayobject.h
branches/soc-2009-jaguarandi/source/blender/render/intern/include/rayobject_rtbuild.h
branches/soc-2009-jaguarandi/source/blender/render/intern/raytrace/bvh.h
branches/soc-2009-jaguarandi/source/blender/render/intern/raytrace/rayobject_bvh.cpp
branches/soc-2009-jaguarandi/source/blender/render/intern/source/rayshade.c
Added Paths:
-----------
branches/soc-2009-jaguarandi/source/blender/render/intern/raytrace/rayobject_rtbuild.cpp
branches/soc-2009-jaguarandi/source/blender/render/intern/raytrace/rayobject_vbvh.cpp
Removed Paths:
-------------
branches/soc-2009-jaguarandi/source/blender/render/intern/source/rayobject_rtbuild.c
Modified: branches/soc-2009-jaguarandi/source/blender/blenlib/BLI_memarena.h
===================================================================
--- branches/soc-2009-jaguarandi/source/blender/blenlib/BLI_memarena.h
2009-07-12 13:06:52 UTC (rev 21550)
+++ branches/soc-2009-jaguarandi/source/blender/blenlib/BLI_memarena.h
2009-07-12 18:04:10 UTC (rev 21551)
@@ -37,6 +37,10 @@
#ifndef BLI_MEMARENA_H
#define BLI_MEMARENA_H
+#ifdef __cplusplus
+extern "C" {
+#endif
+
/* A reasonable standard buffer size, big
* enough to not cause much internal fragmentation,
* small enough not to waste resources
@@ -55,5 +59,10 @@
void* BLI_memarena_alloc (struct MemArena *ma,
int size);
+#ifdef __cplusplus
+}
#endif
+
+#endif
+
Modified:
branches/soc-2009-jaguarandi/source/blender/render/extern/include/RE_raytrace.h
===================================================================
---
branches/soc-2009-jaguarandi/source/blender/render/extern/include/RE_raytrace.h
2009-07-12 13:06:52 UTC (rev 21550)
+++
branches/soc-2009-jaguarandi/source/blender/render/extern/include/RE_raytrace.h
2009-07-12 18:04:10 UTC (rev 21551)
@@ -31,6 +31,11 @@
#ifndef RE_RAYTRACE_H
#define RE_RAYTRACE_H
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+
#define RT_USE_LAST_HIT /* last shadow hit is reused before raycasting
on whole tree */
//#define RT_USE_HINT /* last hit object is reused before
raycasting on whole tree */
@@ -88,7 +93,8 @@
RayObject* RE_rayobject_instance_create(RayObject *target, float
transform[][4], void *ob, void *target_ob);
RayObject* RE_rayobject_blibvh_create(int size); /* BLI_kdopbvh.c */
-RayObject* RE_rayobject_bvh_create(int size); /* rayobject_bvh.c */
+RayObject* RE_rayobject_bvh_create(int size); /*
raytrace/rayobject_bvh.c */
+RayObject* RE_rayobject_vbvh_create(int size); /*
raytrace/rayobject_vbvh.c */
RayObject* RE_rayobject_bih_create(int size); /* rayobject_bih.c */
@@ -151,5 +157,9 @@
/* TODO use: FLT_MAX? */
#define RE_RAYTRACE_MAXDIST 1e33
+#ifdef __cplusplus
+}
+#endif
+
#endif /*__RE_RAYTRACE_H__*/
Modified:
branches/soc-2009-jaguarandi/source/blender/render/intern/include/rayobject.h
===================================================================
---
branches/soc-2009-jaguarandi/source/blender/render/intern/include/rayobject.h
2009-07-12 13:06:52 UTC (rev 21550)
+++
branches/soc-2009-jaguarandi/source/blender/render/intern/include/rayobject.h
2009-07-12 18:04:10 UTC (rev 21551)
@@ -29,9 +29,14 @@
#ifndef RE_RAYOBJECT_H
#define RE_RAYOBJECT_H
+#ifdef __cplusplus
+extern "C" {
+#endif
+
#include "RE_raytrace.h"
#include <float.h>
+
/* RayObject
A ray object is everything where we can cast rays like:
@@ -166,4 +171,10 @@
#endif
+
+#ifdef __cplusplus
+}
#endif
+
+
+#endif
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-12 13:06:52 UTC (rev 21550)
+++
branches/soc-2009-jaguarandi/source/blender/render/intern/include/rayobject_rtbuild.h
2009-07-12 18:04:10 UTC (rev 21551)
@@ -29,8 +29,13 @@
#ifndef RE_RAYOBJECT_RTBUILD_H
#define RE_RAYOBJECT_RTBUILD_H
+#ifdef __cplusplus
+extern "C" {
+#endif
+
#include "rayobject.h"
+
/*
* Ray Tree Builder
* this structs helps building any type of tree
@@ -88,4 +93,8 @@
float bb_volume(float *min, float *max);
int bb_largest_axis(float *min, float *max);
+#ifdef __cplusplus
+}
#endif
+
+#endif
Modified:
branches/soc-2009-jaguarandi/source/blender/render/intern/raytrace/bvh.h
===================================================================
--- branches/soc-2009-jaguarandi/source/blender/render/intern/raytrace/bvh.h
2009-07-12 13:06:52 UTC (rev 21550)
+++ branches/soc-2009-jaguarandi/source/blender/render/intern/raytrace/bvh.h
2009-07-12 18:04:10 UTC (rev 21551)
@@ -99,7 +99,12 @@
Node *stack[MAX_STACK_SIZE];
int hit = 0, stack_pos = 0;
- stack[stack_pos++] = root;
+ //Assume the BB of root always succeed
+ if(1)
+ bvh_node_push_childs(root, isec, stack, stack_pos);
+ else
+ stack[stack_pos++] = root;
+
while(stack_pos)
{
Node *node = stack[--stack_pos];
Modified:
branches/soc-2009-jaguarandi/source/blender/render/intern/raytrace/rayobject_bvh.cpp
===================================================================
---
branches/soc-2009-jaguarandi/source/blender/render/intern/raytrace/rayobject_bvh.cpp
2009-07-12 13:06:52 UTC (rev 21550)
+++
branches/soc-2009-jaguarandi/source/blender/render/intern/raytrace/rayobject_bvh.cpp
2009-07-12 18:04:10 UTC (rev 21551)
@@ -26,18 +26,15 @@
*
* ***** END GPL LICENSE BLOCK *****
*/
-extern "C"
-{
#include <assert.h>
+
+#include "RE_raytrace.h"
+#include "rayobject_rtbuild.h"
+#include "rayobject.h"
#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"
-};
-
#include "bvh.h"
#define BVH_NCHILDS 2
Copied:
branches/soc-2009-jaguarandi/source/blender/render/intern/raytrace/rayobject_rtbuild.cpp
(from rev 21538,
branches/soc-2009-jaguarandi/source/blender/render/intern/source/rayobject_rtbuild.c)
===================================================================
---
branches/soc-2009-jaguarandi/source/blender/render/intern/raytrace/rayobject_rtbuild.cpp
(rev 0)
+++
branches/soc-2009-jaguarandi/source/blender/render/intern/raytrace/rayobject_rtbuild.cpp
2009-07-12 18:04:10 UTC (rev 21551)
@@ -0,0 +1,531 @@
+#include <assert.h>
+#include <math.h>
+#include <stdlib.h>
+
+#include "rayobject_rtbuild.h"
+#include "MEM_guardedalloc.h"
+#include "BLI_arithb.h"
+#include "BKE_utildefines.h"
+
+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)
+{
+ int i;
+
+ b->begin = begin;
+ b->end = end;
+ b->split_axis = 0;
+ b->child_sorted_axis = -1;
+
+ for(i=0; i<RTBUILD_MAX_CHILDS; i++)
+ b->child_offset[i] = 0;
+
+ INIT_MINMAX(b->bb, b->bb+3);
+}
+
+RTBuilder* rtbuild_create(int size)
+{
+ RTBuilder *builder = (RTBuilder*) MEM_mallocN( sizeof(RTBuilder),
"RTBuilder" );
+ RayObject **memblock= (RayObject**)MEM_mallocN(
sizeof(RayObject*)*size,"RTBuilder.objects");
+ rtbuild_init(builder, memblock, memblock);
+ return builder;
+}
+
+void rtbuild_free(RTBuilder *b)
+{
+ MEM_freeN(b->begin);
+ MEM_freeN(b);
+}
+
+void rtbuild_add(RTBuilder *b, RayObject *o)
+{
+ *(b->end++) = o;
+}
+
+void rtbuild_calc_bb(RTBuilder *b)
+{
+ if(b->bb[0] == 1.0e30f)
+ {
+ RayObject **index = b->begin;
+ for(; index != b->end; index++)
+ RE_rayobject_merge_bb(*index, b->bb, b->bb+3);
+ }
+}
+
+void rtbuild_merge_bb(RTBuilder *b, float *min, float *max)
+{
+ rtbuild_calc_bb(b);
+ DO_MIN(b->bb, min);
+ DO_MAX(b->bb+3, max);
+}
+
+int rtbuild_get_largest_axis(RTBuilder *b)
+{
+ rtbuild_calc_bb(b);
+ return bb_largest_axis(b->bb, b->bb+3);
+}
+
+
+int rtbuild_size(RTBuilder *b)
+{
+ return b->end - b->begin;
+}
+
+
+RTBuilder* rtbuild_get_child(RTBuilder *b, int child, RTBuilder *tmp)
+{
+ rtbuild_init( tmp, b->begin + b->child_offset[child], b->begin +
b->child_offset[child+1] );
+ tmp->child_sorted_axis = b->child_sorted_axis;
+ return tmp;
+}
+
+
+
+//Left balanced tree
+int rtbuild_mean_split(RTBuilder *b, int nchilds, int axis)
+{
+ int i;
+ int mleafs_per_child, Mleafs_per_child;
+ int tot_leafs = rtbuild_size(b);
+ int missing_leafs;
+
+ long long s;
+
+ assert(nchilds <= RTBUILD_MAX_CHILDS);
+
+ //TODO optimize calc of leafs_per_child
+ for(s=nchilds; s<tot_leafs; s*=nchilds);
+ Mleafs_per_child = s/nchilds;
+ mleafs_per_child = Mleafs_per_child/nchilds;
+
+ //split min leafs per child
+ b->child_offset[0] = 0;
+ for(i=1; i<=nchilds; i++)
+ b->child_offset[i] = mleafs_per_child;
+
+ //split remaining leafs
+ missing_leafs = tot_leafs - mleafs_per_child*nchilds;
+ for(i=1; i<=nchilds; i++)
+ {
+ if(missing_leafs > Mleafs_per_child - mleafs_per_child)
+ {
+ 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;
+}
+
+
+int rtbuild_mean_split_largest_axis(RTBuilder *b, int nchilds)
+{
+ int axis = rtbuild_get_largest_axis(b);
+ 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];
+
+ rtbuild_calc_bb(b);
+
+ la = bb_largest_axis(b->bb,b->bb+3);
+ for(i=1; i<nchilds; i++)
+ separators[i-1] = (b->bb[la+3]-b->bb[la])*i / nchilds;
+
+ return rtbuild_median_split(b, separators, nchilds, la);
+}
+
+//Heuristics Object Splitter
+typedef struct CostObject CostObject;
+struct CostObject
+{
+ RayObject *obj;
+ float cost;
+ float bb[6];
+};
+
+//Ugly.. but using qsort and no globals its the cleaner I can get
+#define costobject_cmp(axis) costobject_cmp##axis
+#define define_costobject_cmp(axis)
\
+int costobject_cmp(axis)(const CostObject *a, const CostObject *b) \
+{
\
+ if(a->bb[axis] < b->bb[axis]) return -1;
\
@@ Diff output truncated at 10240 characters. @@
_______________________________________________
Bf-blender-cvs mailing list
Bf-blender-cvs@blender.org
http://lists.blender.org/mailman/listinfo/bf-blender-cvs
