diff options
author | Andre Susano Pinto <andresusanopinto@gmail.com> | 2009-07-12 22:04:10 +0400 |
---|---|---|
committer | Andre Susano Pinto <andresusanopinto@gmail.com> | 2009-07-12 22:04:10 +0400 |
commit | a6b328b82577d3ec1429c02686ea1727e02140c0 (patch) | |
tree | f86eb2e35b316f3409ed503e5923e8fddc7d1841 | |
parent | e264087fad7a55be67d409fe1748d4fc647fba0c (diff) |
*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
-rw-r--r-- | source/blender/blenlib/BLI_memarena.h | 9 | ||||
-rw-r--r-- | source/blender/render/extern/include/RE_raytrace.h | 12 | ||||
-rw-r--r-- | source/blender/render/intern/include/rayobject.h | 11 | ||||
-rw-r--r-- | source/blender/render/intern/include/rayobject_rtbuild.h | 9 | ||||
-rw-r--r-- | source/blender/render/intern/raytrace/bvh.h | 7 | ||||
-rw-r--r-- | source/blender/render/intern/raytrace/rayobject_bvh.cpp | 11 | ||||
-rw-r--r-- | source/blender/render/intern/raytrace/rayobject_rtbuild.cpp (renamed from source/blender/render/intern/source/rayobject_rtbuild.c) | 4 | ||||
-rw-r--r-- | source/blender/render/intern/raytrace/rayobject_vbvh.cpp | 248 | ||||
-rw-r--r-- | source/blender/render/intern/source/rayshade.c | 8 |
9 files changed, 306 insertions, 13 deletions
diff --git a/source/blender/blenlib/BLI_memarena.h b/source/blender/blenlib/BLI_memarena.h index a2954f8fa0d..4b955e9fa20 100644 --- a/source/blender/blenlib/BLI_memarena.h +++ b/source/blender/blenlib/BLI_memarena.h @@ -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_use_calloc (struct MemArena *ma); void* BLI_memarena_alloc (struct MemArena *ma, int size); +#ifdef __cplusplus +} +#endif + + #endif diff --git a/source/blender/render/extern/include/RE_raytrace.h b/source/blender/render/extern/include/RE_raytrace.h index 7624cd09edb..4d0c0b1a88c 100644 --- a/source/blender/render/extern/include/RE_raytrace.h +++ b/source/blender/render/extern/include/RE_raytrace.h @@ -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_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__*/ diff --git a/source/blender/render/intern/include/rayobject.h b/source/blender/render/intern/include/rayobject.h index de36a1e4888..16ebc537ef9 100644 --- a/source/blender/render/intern/include/rayobject.h +++ b/source/blender/render/intern/include/rayobject.h @@ -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 @@ float RE_rayobject_cost(RayObject *r); #endif + +#ifdef __cplusplus +} +#endif + + #endif diff --git a/source/blender/render/intern/include/rayobject_rtbuild.h b/source/blender/render/intern/include/rayobject_rtbuild.h index a98ed38a581..b80e0868739 100644 --- a/source/blender/render/intern/include/rayobject_rtbuild.h +++ b/source/blender/render/intern/include/rayobject_rtbuild.h @@ -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_area(float *min, float *max); float bb_volume(float *min, float *max); int bb_largest_axis(float *min, float *max); +#ifdef __cplusplus +} +#endif + #endif diff --git a/source/blender/render/intern/raytrace/bvh.h b/source/blender/render/intern/raytrace/bvh.h index 44f531faa9f..d9277f9a583 100644 --- a/source/blender/render/intern/raytrace/bvh.h +++ b/source/blender/render/intern/raytrace/bvh.h @@ -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]; diff --git a/source/blender/render/intern/raytrace/rayobject_bvh.cpp b/source/blender/render/intern/raytrace/rayobject_bvh.cpp index 8a63e088a34..2c2a260df98 100644 --- a/source/blender/render/intern/raytrace/rayobject_bvh.cpp +++ b/source/blender/render/intern/raytrace/rayobject_bvh.cpp @@ -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 diff --git a/source/blender/render/intern/source/rayobject_rtbuild.c b/source/blender/render/intern/raytrace/rayobject_rtbuild.cpp index 3c301ce1f9f..dff0b02c00e 100644 --- a/source/blender/render/intern/source/rayobject_rtbuild.c +++ b/source/blender/render/intern/raytrace/rayobject_rtbuild.cpp @@ -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 index 00000000000..3f8f69a5abe --- /dev/null +++ b/source/blender/render/intern/raytrace/rayobject_vbvh.cpp @@ -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); +} diff --git a/source/blender/render/intern/source/rayshade.c b/source/blender/render/intern/source/rayshade.c index b967f2bd8ce..52edd7a7e27 100644 --- a/source/blender/render/intern/source/rayshade.c +++ b/source/blender/render/intern/source/rayshade.c @@ -70,8 +70,13 @@ 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 |