*Moved rtbuild to bf_render_raytrace
authorAndre Susano Pinto <andresusanopinto@gmail.com>
Sun, 12 Jul 2009 18:04:10 +0000 (18:04 +0000)
committerAndre Susano Pinto <andresusanopinto@gmail.com>
Sun, 12 Jul 2009 18:04:10 +0000 (18:04 +0000)
*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

source/blender/blenlib/BLI_memarena.h
source/blender/render/extern/include/RE_raytrace.h
source/blender/render/intern/include/rayobject.h
source/blender/render/intern/include/rayobject_rtbuild.h
source/blender/render/intern/raytrace/bvh.h
source/blender/render/intern/raytrace/rayobject_bvh.cpp
source/blender/render/intern/raytrace/rayobject_rtbuild.cpp [moved from source/blender/render/intern/source/rayobject_rtbuild.c with 98% similarity]
source/blender/render/intern/raytrace/rayobject_vbvh.cpp [new file with mode: 0644]
source/blender/render/intern/source/rayshade.c

index a2954f8fa0d51d3473fbe5b373d9f8fb17c349c5..4b955e9fa20a3c54c444a2deac0a66d7ae947fa2 100644 (file)
 #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_use_calloc (struct MemArena *ma);
 
 void*                          BLI_memarena_alloc      (struct MemArena *ma, int size);
 
+#ifdef __cplusplus
+}
+#endif
+
+
 #endif
 
index 7624cd09edba1448eebb32bf4e1bba29cd10e3eb..4d0c0b1a88c1862e27ee919c2b8cbbd2e8d3b92b 100644 (file)
 #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_octree_create(int ocres, int size);
 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 @@ struct Isect
 /* TODO use: FLT_MAX? */
 #define RE_RAYTRACE_MAXDIST    1e33
 
+#ifdef __cplusplus
+}
+#endif
+
 
 #endif /*__RE_RAYTRACE_H__*/
index de36a1e488877c39a19af965a645df90a48fa130..16ebc537ef972aad75d0be27456569acf6064178 100644 (file)
 #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 @@ float RE_rayobject_cost(RayObject *r);
 #endif
 
 
+
+#ifdef __cplusplus
+}
+#endif
+
+
 #endif
index a98ed38a5817c114e9fdc400d4bee778879879ee..b80e0868739f2a2febaaa57488bdbb7ec7e04812 100644 (file)
 #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_area(float *min, float *max);
 float bb_volume(float *min, float *max);
 int bb_largest_axis(float *min, float *max);
 
+#ifdef __cplusplus
+}
+#endif
+
 #endif
index 44f531faa9f9314f0736515555e263af3ff03191..d9277f9a5839deb5317ade3fd0991e934ad39228 100644 (file)
@@ -99,7 +99,12 @@ static int bvh_node_stack_raycast(Node *root, Isect *isec)
        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];
index 8a63e088a34375e299cfa82167d17111ac74fc91..2c2a260df982e76d7f5c776feff59dae4f0adda8 100644 (file)
  *
  * ***** 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
similarity index 98%
rename from source/blender/render/intern/source/rayobject_rtbuild.c
rename to source/blender/render/intern/raytrace/rayobject_rtbuild.cpp
index 3c301ce1f9fcc59835f0123298271ed4a9d14c17..dff0b02c00e4ab626eafd97e09bc372bd30346b2 100644 (file)
@@ -245,8 +245,8 @@ int rtbuild_heuristic_object_split(RTBuilder *b, int nchilds)
                float bcost = FLT_MAX;
                float childrens_cost = 0;
                int i, axis, baxis = -1, boffset = size/2, k, try_axis[3];
-               CostObject *cost   = MEM_mallocN( sizeof(CostObject)*size, "RTBuilder.HeuristicObjectSplitter" );
-               float      *acc_bb = MEM_mallocN( sizeof(float)*6*size, "RTBuilder.HeuristicObjectSplitterBB" );
+               CostObject *cost   = (CostObject*)MEM_mallocN( sizeof(CostObject)*size, "RTBuilder.HeuristicObjectSplitter" );
+               float      *acc_bb = (float*)MEM_mallocN( sizeof(float)*6*size, "RTBuilder.HeuristicObjectSplitterBB" );
 
                for(i=0; i<size; i++)
                {
diff --git a/source/blender/render/intern/raytrace/rayobject_vbvh.cpp b/source/blender/render/intern/raytrace/rayobject_vbvh.cpp
new file mode 100644 (file)
index 0000000..3f8f69a
--- /dev/null
@@ -0,0 +1,248 @@
+/**
+ * $Id$
+ *
+ * ***** BEGIN GPL LICENSE BLOCK *****
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version. 
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
+ *
+ * The Original Code is Copyright (C) 2009 Blender Foundation.
+ * All rights reserved.
+ *
+ * The Original Code is: all of this file.
+ *
+ * Contributor(s): AndrĂ© Pinto.
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ */
+extern "C"
+{
+#include <assert.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"
+#include <queue>
+
+#define BVHNode VBVHNode
+#define BVHTree VBVHTree
+
+#define RAY_BB_TEST_COST (0.2f)
+#define DFS_STACK_SIZE 128
+#define DYNAMIC_ALLOC
+
+//#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
+{
+       BVHNode *child;
+       BVHNode *sibling;
+
+       float   bb[6];
+};
+
+struct BVHTree
+{
+       RayObject rayobj;
+
+       BVHNode *root;
+
+       MemArena *node_arena;
+
+       float cost;
+       RTBuilder *builder;
+};
+
+
+/*
+ * Push nodes (used on dfs)
+ */
+template<class Node>
+inline static void bvh_node_push_childs(Node *node, Isect *isec, Node **stack, int &stack_pos)
+{
+       Node *child = node->child;
+       while(child)
+       {
+               stack[stack_pos++] = child;
+               if(RayObject_isAligned(child))
+                       child = child->sibling;
+               else break;
+       }
+}
+
+/*
+ * BVH done
+ */
+static BVHNode *bvh_new_node(BVHTree *tree)
+{
+       BVHNode *node = (BVHNode*)BLI_memarena_alloc(tree->node_arena, sizeof(BVHNode));
+       node->sibling = NULL;
+       node->child   = NULL;
+
+       assert(RayObject_isAligned(node));
+       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;
+       }
+}
+
+
+template<class Tree, class Node, class Builder>
+Node *bvh_rearrange(Tree *tree, Builder *builder, float *cost)
+{
+       
+       int size = rtbuild_size(builder);
+       if(size == 1)
+       {
+               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*)builder->begin[0];
+
+               *cost = RE_rayobject_cost((RayObject*)node->child)+RAY_BB_TEST_COST;
+               return node;
+       }
+       else
+       {
+               Node *node = bvh_new_node(tree);
+               float parent_area;
+               
+               INIT_MINMAX(node->bb, node->bb+3);
+               rtbuild_merge_bb(builder, node->bb, node->bb+3);
+               
+               parent_area = bb_area( node->bb, node->bb+3 );
+               Node **child = &node->child;
+               
+               std::queue<Builder> childs;
+               childs.push(*builder);
+               
+               *cost = 0;
+               
+               while(!childs.empty())
+               {
+                       Builder b = childs.front();
+                                               childs.pop();
+                       
+                       float hit_prob = rtbuild_area(&b) / parent_area;
+                       if(hit_prob > 1.0f / 2.0f && rtbuild_size(&b) > 1)
+                       {
+                               //The expected number of BB test is smaller if we directly add the 2 childs of this node
+                               int nc = rtbuild_split(&b, 2);
+                               assert(nc == 2);
+                               for(int i=0; i<nc; i++)
+                               {
+                                       Builder tmp;
+                                       rtbuild_get_child(&b, i, &tmp);
+                                       childs.push(tmp);
+                               }
+                               
+                       }
+                       else
+                       {
+                               float tcost;
+                               *child = bvh_rearrange<Tree,Node,Builder>(tree, &b, &tcost);
+                               child = &((*child)->sibling);
+                               
+                               *cost += tcost*hit_prob + RAY_BB_TEST_COST;
+                       }
+               }
+               assert(child != &node->child);
+               *child = 0;
+
+               return node;
+       }
+}
+
+template<>
+void bvh_done<BVHTree>(BVHTree *obj)
+{
+       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);
+
+       
+       obj->root = bvh_rearrange<BVHTree,BVHNode,RTBuilder>( obj, obj->builder, &obj->cost );
+       obj->cost = 1.0;
+       
+       rtbuild_free( obj->builder );
+       obj->builder = NULL;
+}
+
+template<>
+int bvh_intersect<BVHTree>(BVHTree *obj, Isect* isec)
+{
+       if(RayObject_isAligned(obj->root))
+               return bvh_node_stack_raycast<BVHNode,DFS_STACK_SIZE>(obj->root, isec);
+       else
+               return RE_rayobject_intersect( (RayObject*) obj->root, isec );
+}
+
+/* the cast to pointer function is needed to workarround gcc bug: http://gcc.gnu.org/bugzilla/show_bug.cgi?id=11407 */
+static RayObjectAPI bvh_api =
+{
+       (RE_rayobject_raycast_callback) ((int(*)(BVHTree*,Isect*)) &bvh_intersect<BVHTree>),
+       (RE_rayobject_add_callback)     ((void(*)(BVHTree*,RayObject*)) &bvh_add<BVHTree>),
+       (RE_rayobject_done_callback)    ((void(*)(BVHTree*))       &bvh_done<BVHTree>),
+       (RE_rayobject_free_callback)    ((void(*)(BVHTree*))       &bvh_free<BVHTree>),
+       (RE_rayobject_merge_bb_callback)((void(*)(BVHTree*,float*,float*)) &bvh_bb<BVHTree>),
+       (RE_rayobject_cost_callback)    ((float(*)(BVHTree*))      &bvh_cost<BVHTree>)
+};
+
+RayObject *RE_rayobject_vbvh_create(int size)
+{
+       BVHTree *obj= (BVHTree*)MEM_callocN(sizeof(BVHTree), "BVHTree");
+       assert( RayObject_isAligned(obj) ); /* RayObject API assumes real data to be 4-byte aligned */  
+       
+       obj->rayobj.api = &bvh_api;
+       obj->root = NULL;
+       
+       obj->node_arena = NULL;
+       obj->builder    = rtbuild_create( size );
+       
+       return RayObject_unalignRayAPI((RayObject*) obj);
+}
index b967f2bd8ced689b340bb0537a79f87110561509..52edd7a7e276226eb01a5739f35b64c93508929b 100644 (file)
 extern struct Render R;
 /* ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ */
 
-RayObject *RE_rayobject_tree_create(int type, int size)
+RayObject *  RE_rayobject_tree_create(int type, int size) __attribute__((noinline));
+
+RayObject *  RE_rayobject_tree_create(int type, int size)
 {
+//     if(type == R_RAYTRACE_TREE_BIH)
+       return RE_rayobject_vbvh_create(size);
+
        if(type == R_RAYTRACE_TREE_BVH)
                return RE_rayobject_bvh_create(size);
        if(type == R_RAYTRACE_TREE_BIH)
@@ -79,7 +84,6 @@ RayObject *RE_rayobject_tree_create(int type, int size)
        if(type == R_RAYTRACE_TREE_BLIBVH)
                return RE_rayobject_blibvh_create(size);
 
-       return RE_rayobject_bvh_create(size);   
 }
 
 #ifdef RE_RAYCOUNTER