*Added support to "BB hints" (which works like a BB version of LCTS - longest common...
[blender-staging.git] / source / blender / render / intern / raytrace / rayobject_vbvh.cpp
1 /**
2  * $Id$
3  *
4  * ***** BEGIN GPL LICENSE BLOCK *****
5  *
6  * This program is free software; you can redistribute it and/or
7  * modify it under the terms of the GNU General Public License
8  * as published by the Free Software Foundation; either version 2
9  * of the License, or (at your option) any later version. 
10  *
11  * This program is distributed in the hope that it will be useful,
12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14  * GNU General Public License for more details.
15  *
16  * You should have received a copy of the GNU General Public License
17  * along with this program; if not, write to the Free Software Foundation,
18  * Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
19  *
20  * The Original Code is Copyright (C) 2009 Blender Foundation.
21  * All rights reserved.
22  *
23  * The Original Code is: all of this file.
24  *
25  * Contributor(s): AndrĂ© Pinto.
26  *
27  * ***** END GPL LICENSE BLOCK *****
28  */
29 extern "C"
30 {
31 #include <assert.h>
32 #include "MEM_guardedalloc.h"
33 #include "BKE_utildefines.h"
34 #include "BLI_arithb.h"
35 #include "BLI_memarena.h"
36 #include "RE_raytrace.h"
37 #include "rayobject_rtbuild.h"
38 #include "rayobject.h"
39 };
40
41 #include "bvh.h"
42 #include <queue>
43
44 #define BVHNode VBVHNode
45 #define BVHTree VBVHTree
46
47 #define RAY_BB_TEST_COST (0.2f)
48 #define DFS_STACK_SIZE  128
49 #define DYNAMIC_ALLOC
50
51 //#define rtbuild_split rtbuild_mean_split_largest_axis         /* objects mean split on the longest axis, childs BB are allowed to overlap */
52 //#define rtbuild_split rtbuild_median_split_largest_axis       /* space median split on the longest axis, childs BB are allowed to overlap */
53 #define rtbuild_split   rtbuild_heuristic_object_split          /* split objects using heuristic */
54
55 struct BVHNode
56 {
57         BVHNode *child;
58         BVHNode *sibling;
59
60         float   bb[6];
61 };
62
63 struct BVHTree
64 {
65         RayObject rayobj;
66
67         BVHNode *root;
68
69         MemArena *node_arena;
70
71         float cost;
72         RTBuilder *builder;
73 };
74
75
76 /*
77  * Push nodes (used on dfs)
78  */
79 template<class Node>
80 inline static void bvh_node_push_childs(Node *node, Isect *isec, Node **stack, int &stack_pos)
81 {
82         Node *child = node->child;
83         while(child)
84         {
85                 stack[stack_pos++] = child;
86                 if(RayObject_isAligned(child))
87                         child = child->sibling;
88                 else break;
89         }
90 }
91
92 /*
93  * BVH done
94  */
95 static BVHNode *bvh_new_node(BVHTree *tree)
96 {
97         BVHNode *node = (BVHNode*)BLI_memarena_alloc(tree->node_arena, sizeof(BVHNode));
98         node->sibling = NULL;
99         node->child   = NULL;
100
101         assert(RayObject_isAligned(node));
102         return node;
103 }
104
105 template<class Builder>
106 float rtbuild_area(Builder *builder)
107 {
108         float min[3], max[3];
109         INIT_MINMAX(min, max);
110         rtbuild_merge_bb(builder, min, max);
111         return bb_area(min, max);       
112 }
113
114 template<class Node>
115 void bvh_update_bb(Node *node)
116 {
117         INIT_MINMAX(node->bb, node->bb+3);
118         Node *child = node->child;
119         
120         while(child)
121         {
122                 bvh_node_merge_bb(child, node->bb, node->bb+3);
123                 if(RayObject_isAligned(child))
124                         child = child->sibling;
125                 else
126                         child = 0;
127         }
128 }
129
130
131 static int tot_pushup   = 0;
132 static int tot_pushdown = 0;
133 static int tot_hints    = 0;
134
135 template<class Node>
136 void pushdown(Node *parent)
137 {
138         Node **s_child = &parent->child;
139         Node * child = parent->child;
140         
141         while(child && RayObject_isAligned(child))
142         {
143                 Node *next = child->sibling;
144                 Node **next_s_child = &child->sibling;
145                 
146                 //assert(bb_fits_inside(parent->bb, parent->bb+3, child->bb, child->bb+3));
147                 
148                 for(Node *i = parent->child; RayObject_isAligned(i) && i; i = i->sibling)
149                 if(child != i && bb_fits_inside(i->bb, i->bb+3, child->bb, child->bb+3))
150                 {
151 //                      todo optimize (hsould the one with the smallest area
152 //                      float ia = bb_area(i->bb, i->bb+3)
153 //                      if(child->i)
154                         *s_child = child->sibling;
155                         child->sibling = i->child;
156                         i->child = child;
157                         next_s_child = s_child;
158                         
159                         tot_pushdown++;
160                         break;
161                 }
162                 child = next;
163                 s_child = next_s_child;
164         }
165         
166         for(Node *i = parent->child; RayObject_isAligned(i) && i; i = i->sibling)
167                 pushdown( i );  
168 }
169
170 template<class Tree, class Node, class Builder>
171 Node *bvh_rearrange(Tree *tree, Builder *builder, float *cost)
172 {
173         
174         int size = rtbuild_size(builder);
175         if(size == 1)
176         {
177                 Node *node = bvh_new_node(tree);
178                 INIT_MINMAX(node->bb, node->bb+3);
179                 rtbuild_merge_bb(builder, node->bb, node->bb+3);
180                 
181                 node->child = (BVHNode*)builder->begin[0];
182
183                 *cost = RE_rayobject_cost((RayObject*)node->child)+RAY_BB_TEST_COST;
184                 return node;
185         }
186         else
187         {
188                 Node *node = bvh_new_node(tree);
189                 float parent_area;
190                 
191                 INIT_MINMAX(node->bb, node->bb+3);
192                 rtbuild_merge_bb(builder, node->bb, node->bb+3);
193                 
194                 parent_area = bb_area( node->bb, node->bb+3 );
195                 Node **child = &node->child;
196                 
197                 std::queue<Builder> childs;
198                 childs.push(*builder);
199                 
200                 *cost = 0;
201                 
202                 while(!childs.empty())
203                 {
204                         Builder b = childs.front();
205                                                 childs.pop();
206                         
207                         float hit_prob = rtbuild_area(&b) / parent_area;
208                         if(hit_prob > 1.0f / 2.0f && rtbuild_size(&b) > 1)
209                         {
210                                 //The expected number of BB test is smaller if we directly add the 2 childs of this node
211                                 int nc = rtbuild_split(&b, 2);
212                                 assert(nc == 2);
213                                 for(int i=0; i<nc; i++)
214                                 {
215                                         Builder tmp;
216                                         rtbuild_get_child(&b, i, &tmp);
217                                         childs.push(tmp);
218                                 }
219                                 tot_pushup++;
220                                 
221                         }
222                         else
223                         {
224                                 float tcost;
225                                 *child = bvh_rearrange<Tree,Node,Builder>(tree, &b, &tcost);
226                                 child = &((*child)->sibling);
227                                 
228                                 *cost += tcost*hit_prob + RAY_BB_TEST_COST;
229                         }
230                 }
231                 assert(child != &node->child);
232                 *child = 0;
233
234                 return node;
235         }
236 }
237
238 template<>
239 void bvh_done<BVHTree>(BVHTree *obj)
240 {
241         int needed_nodes = (rtbuild_size(obj->builder)+1)*2;
242         if(needed_nodes > BLI_MEMARENA_STD_BUFSIZE)
243                 needed_nodes = BLI_MEMARENA_STD_BUFSIZE;
244
245         obj->node_arena = BLI_memarena_new(needed_nodes);
246         BLI_memarena_use_malloc(obj->node_arena);
247
248         
249         obj->root = bvh_rearrange<BVHTree,BVHNode,RTBuilder>( obj, obj->builder, &obj->cost );
250         pushdown(obj->root);
251         obj->cost = 1.0;
252         
253         rtbuild_free( obj->builder );
254         obj->builder = NULL;
255 }
256
257 template<int StackSize>
258 int intersect(BVHTree *obj, Isect* isec)
259 {
260         if(isec->hint)
261         {
262                 LCTSHint *lcts = (LCTSHint*)isec->hint;
263                 isec->hint = 0;
264                 
265                 int hit = 0;
266                 for(int i=0; i<lcts->size; i++)
267                 {
268                         BVHNode *node = (BVHNode*)lcts->stack[i];
269                         if(RayObject_isAligned(node))
270                                 hit |= bvh_node_stack_raycast<BVHNode,StackSize,true>(node, isec);
271                         else
272                                 hit |= RE_rayobject_intersect( (RayObject*)node, isec );
273                         
274                         if(hit && isec->mode == RE_RAY_SHADOW)
275                                 break;
276                 }
277                 isec->hint = (RayHint*)lcts;
278                 return hit;
279         }
280         else
281         {
282                 if(RayObject_isAligned(obj->root))
283                         return bvh_node_stack_raycast<BVHNode,StackSize,false>(obj->root, isec);
284                 else
285                         return RE_rayobject_intersect( (RayObject*) obj->root, isec );
286         }
287 }
288
289 template<class Node>
290 void bvh_dfs_make_hint(Node *node, LCTSHint *hint, int reserve_space, float *min, float *max);
291
292 template<class Node>
293 void bvh_dfs_make_hint_push_siblings(Node *node, LCTSHint *hint, int reserve_space, float *min, float *max)
294 {
295         if(!RayObject_isAligned(node))
296                 hint->stack[hint->size++] = (RayObject*)node;
297         else
298         {
299                 if(node->sibling)
300                         bvh_dfs_make_hint_push_siblings(node->sibling, hint, reserve_space+1, min, max);
301
302                 bvh_dfs_make_hint(node, hint, reserve_space, min, max);
303         }
304                 
305         
306 }
307
308 template<class Node>
309 void bvh_dfs_make_hint(Node *node, LCTSHint *hint, int reserve_space, float *min, float *max)
310 {
311         assert( hint->size - reserve_space + 1 <= RE_RAY_LCTS_MAX_SIZE );
312         
313         if(hint->size - reserve_space + 1 == RE_RAY_LCTS_MAX_SIZE || !RayObject_isAligned(node))
314                 hint->stack[hint->size++] = (RayObject*)node;
315         else
316         {
317                 /* We are 100% sure the ray will be pass inside this node */
318                 if(bb_fits_inside(node->bb, node->bb+3, min, max) )
319                 {
320                         bvh_dfs_make_hint_push_siblings(node->child, hint, reserve_space, min, max);
321                 }
322                 else
323                 {
324                         hint->stack[hint->size++] = (RayObject*)node;
325                 }
326         }
327 }
328
329 template<class Tree>
330 void bvh_hint_bb(Tree *tree, LCTSHint *hint, float *min, float *max)
331 {
332         hint->size = 0;
333         bvh_dfs_make_hint( tree->root, hint, 0, min, max );
334         tot_hints++;
335 }
336
337 void bfree(BVHTree *tree)
338 {
339         if(tot_pushup + tot_pushdown + tot_hints)
340         {
341                 printf("tot pushups: %d\n", tot_pushup);
342                 printf("tot pushdowns: %d\n", tot_pushdown);
343                 printf("tot hints created: %d\n", tot_hints);
344                 tot_pushup = 0;
345                 tot_pushdown = 0;
346                 tot_hints = 0;
347         }
348         bvh_free(tree);
349 }
350
351 /* the cast to pointer function is needed to workarround gcc bug: http://gcc.gnu.org/bugzilla/show_bug.cgi?id=11407 */
352 template<int STACK_SIZE>
353 static RayObjectAPI make_api()
354 {
355         static RayObjectAPI api = 
356         {
357                 (RE_rayobject_raycast_callback) ((int(*)(BVHTree*,Isect*)) &intersect<STACK_SIZE>),
358                 (RE_rayobject_add_callback)     ((void(*)(BVHTree*,RayObject*)) &bvh_add<BVHTree>),
359                 (RE_rayobject_done_callback)    ((void(*)(BVHTree*))       &bvh_done<BVHTree>),
360 //              (RE_rayobject_free_callback)    ((void(*)(BVHTree*))       &bvh_free<BVHTree>),
361                 (RE_rayobject_free_callback)    ((void(*)(BVHTree*))       &bfree),
362                 (RE_rayobject_merge_bb_callback)((void(*)(BVHTree*,float*,float*)) &bvh_bb<BVHTree>),
363                 (RE_rayobject_cost_callback)    ((float(*)(BVHTree*))      &bvh_cost<BVHTree>),
364                 (RE_rayobject_hint_bb_callback) ((void(*)(BVHTree*,LCTSHint*,float*,float*)) &bvh_hint_bb<BVHTree>)
365         };
366         
367         return api;
368 }
369
370 static RayObjectAPI* get_api(int maxstacksize)
371 {
372 //      static RayObjectAPI bvh_api16  = make_api<16>();
373 //      static RayObjectAPI bvh_api32  = make_api<32>();
374 //      static RayObjectAPI bvh_api64  = make_api<64>();
375         static RayObjectAPI bvh_api128 = make_api<128>();
376         static RayObjectAPI bvh_api256 = make_api<256>();
377         
378 //      if(maxstacksize <= 16 ) return &bvh_api16;
379 //      if(maxstacksize <= 32 ) return &bvh_api32;
380 //      if(maxstacksize <= 64 ) return &bvh_api64;
381         if(maxstacksize <= 128) return &bvh_api128;
382         if(maxstacksize <= 256) return &bvh_api256;
383         assert(maxstacksize <= 256);
384         return 0;
385 }
386
387 RayObject *RE_rayobject_vbvh_create(int size)
388 {
389         BVHTree *obj= (BVHTree*)MEM_callocN(sizeof(BVHTree), "BVHTree");
390         assert( RayObject_isAligned(obj) ); /* RayObject API assumes real data to be 4-byte aligned */  
391         
392         obj->rayobj.api = get_api(DFS_STACK_SIZE);
393         obj->root = NULL;
394         
395         obj->node_arena = NULL;
396         obj->builder    = rtbuild_create( size );
397         
398         return RayObject_unalignRayAPI((RayObject*) obj);
399 }