*Added a tree structure with a variable number of childs per node, but with groupped...
[blender.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 #define RE_USE_HINT     (0)
30 static int tot_pushup   = 0;
31 static int tot_pushdown = 0;
32 static int tot_hints    = 0;
33
34
35 extern "C"
36 {
37 #include <assert.h>
38 #include "MEM_guardedalloc.h"
39 #include "BKE_utildefines.h"
40 #include "BLI_arithb.h"
41 #include "BLI_memarena.h"
42 #include "RE_raytrace.h"
43 #include "rayobject_rtbuild.h"
44 #include "rayobject.h"
45 };
46
47 #include "rayobject_hint.h"
48 #include "reorganize.h"
49 #include "bvh.h"
50 #include "svbvh.h"
51 #include <queue>
52
53
54 #define RE_DO_HINTS     (0)
55 #define RAY_BB_TEST_COST (0.2f)
56 #define DFS_STACK_SIZE  256
57 //#define DYNAMIC_ALLOC_BB
58
59
60 //#define rtbuild_split rtbuild_mean_split_largest_axis         /* objects mean split on the longest axis, childs BB are allowed to overlap */
61 //#define rtbuild_split rtbuild_median_split_largest_axis       /* space median split on the longest axis, childs BB are allowed to overlap */
62 #define rtbuild_split   rtbuild_heuristic_object_split          /* split objects using heuristic */
63
64 struct VBVHNode
65 {
66 #ifdef DYNAMIC_ALLOC_BB
67         float *bb;
68 #else
69         float   bb[6];
70 #endif
71
72         VBVHNode *child;
73         VBVHNode *sibling;
74 };
75
76 struct VBVHTree
77 {
78         RayObject rayobj;
79
80         SVBVHNode *root;
81
82         MemArena *node_arena;
83
84         float cost;
85         RTBuilder *builder;
86 };
87
88
89
90
91 template<class Tree,class OldNode>
92 struct Reorganize_VBVH
93 {
94         Tree *tree;
95         
96         Reorganize_VBVH(Tree *t)
97         {
98                 tree = t;
99         }
100         
101         VBVHNode *create_node()
102         {
103                 VBVHNode *node = (VBVHNode*)BLI_memarena_alloc(tree->node_arena, sizeof(VBVHNode));
104                 return node;
105         }
106         
107         void copy_bb(VBVHNode *node, OldNode *old)
108         {
109                 std::copy( old->bb, old->bb+6, node->bb );
110         }
111         
112         VBVHNode *transform(OldNode *old)
113         {
114                 if(is_leaf(old))
115                         return (VBVHNode*)old;
116
117                 VBVHNode *node = create_node();
118                 VBVHNode **child_ptr = &node->child;
119                 node->sibling = 0;
120
121                 copy_bb(node,old);
122
123                 for(OldNode *o_child = old->child; o_child; o_child = o_child->sibling)
124                 {
125                         VBVHNode *n_child = transform(o_child);
126                         *child_ptr = n_child;
127                         if(is_leaf(n_child)) return node;
128                         child_ptr = &n_child->sibling;
129                 }
130                 *child_ptr = 0;
131                 
132                 return node;
133         }       
134 };
135
136
137 /*
138  * Push nodes (used on dfs)
139  */
140 template<class Node>
141 inline static void bvh_node_push_childs(Node *node, Isect *isec, Node **stack, int &stack_pos)
142 {
143         Node *child = node->child;
144
145         if(is_leaf(child))
146         {
147                 stack[stack_pos++] = child;
148         }
149         else
150         {
151                 while(child)
152                 {
153                         //Skips BB tests on primitives
154 /*
155                         if(is_leaf(child->child))
156                                 stack[stack_pos++] = child->child;
157                         else
158 */
159                                 stack[stack_pos++] = child;
160                                 
161                         child = child->sibling;
162                 }
163         }
164 }
165
166 /*
167  * BVH done
168  */
169 static VBVHNode *bvh_new_node(VBVHTree *tree)
170 {
171         VBVHNode *node = (VBVHNode*)BLI_memarena_alloc(tree->node_arena, sizeof(VBVHNode));
172         
173         if( (((intptr_t)node) & (0x0f)) != 0 )
174         {
175                 puts("WRONG!");
176                 printf("%08x\n", (intptr_t)node);
177         }
178         node->sibling = NULL;
179         node->child   = NULL;
180
181 #ifdef DYNAMIC_ALLOC_BB
182         node->bb = (float*)BLI_memarena_alloc(tree->node_arena, 6*sizeof(float));
183 #endif
184         assert(RayObject_isAligned(node));
185         return node;
186 }
187
188
189
190 template<class Node>
191 int count_childs(Node *parent)
192 {
193         int n = 0;
194         for(Node *i = parent->child; i; i = i->sibling)
195         {
196                 n++;
197                 if(is_leaf(i))
198                         break;
199         }
200                 
201         return n;
202 }
203
204 template<class Node>
205 void append_sibling(Node *node, Node *sibling)
206 {
207         while(node->sibling)
208                 node = node->sibling;
209                 
210         node->sibling = sibling;
211 }
212
213
214 template<class Tree, class Node, class Builder>
215 Node *bvh_rearrange(Tree *tree, Builder *builder)
216 {
217         
218         int size = rtbuild_size(builder);
219         if(size == 1)
220         {
221                 Node *node = bvh_new_node(tree);
222                 INIT_MINMAX(node->bb, node->bb+3);
223                 rtbuild_merge_bb(builder, node->bb, node->bb+3);                
224                 node->child = (VBVHNode*) rtbuild_get_primitive( builder, 0 );
225                 return node;
226         }
227         else
228         {
229                 Node *node = bvh_new_node(tree);
230
231                 INIT_MINMAX(node->bb, node->bb+3);
232                 rtbuild_merge_bb(builder, node->bb, node->bb+3);
233                 
234                 Node **child = &node->child;
235
236                 int nc = rtbuild_split(builder, 2);
237                 assert(nc == 2);
238                 for(int i=0; i<nc; i++)
239                 {
240                         Builder tmp;
241                         rtbuild_get_child(builder, i, &tmp);
242                         
243                         *child = bvh_rearrange<Tree,Node,Builder>(tree, &tmp);
244                         child = &((*child)->sibling);
245                 }
246
247                 *child = 0;
248                 return node;
249         }
250 }
251
252 template<>
253 void bvh_done<VBVHTree>(VBVHTree *obj)
254 {
255         rtbuild_done(obj->builder);
256         
257         int needed_nodes = (rtbuild_size(obj->builder)+1)*2;
258         if(needed_nodes > BLI_MEMARENA_STD_BUFSIZE)
259                 needed_nodes = BLI_MEMARENA_STD_BUFSIZE;
260
261         MemArena *arena1 = BLI_memarena_new(needed_nodes);
262         BLI_memarena_use_malloc(arena1);
263         BLI_memarena_use_align(arena1, 16);
264         obj->node_arena = arena1;
265         
266         VBVHNode *root = bvh_rearrange<VBVHTree,VBVHNode,RTBuilder>( obj, obj->builder );
267         reorganize(root);
268         remove_useless(root, &root);
269         printf("refit: %f\n", bvh_refit(root) );
270         
271         pushup(root);
272         pushdown(root);
273
274         //Memory re-organize
275         if(0)
276         {
277                 MemArena *arena2 = BLI_memarena_new(needed_nodes);
278                 BLI_memarena_use_malloc(arena2);
279                 BLI_memarena_use_align(arena2, 16);
280                 obj->node_arena = arena2;
281                 root = Reorganize_VBVH<VBVHTree,VBVHNode>(obj).transform(root);
282         
283                 BLI_memarena_free(arena1);
284         }
285
286         if(1)
287         {
288                 MemArena *arena2 = BLI_memarena_new(needed_nodes);
289                 BLI_memarena_use_malloc(arena2);
290                 BLI_memarena_use_align(arena2, 16);
291                 obj->node_arena = arena2;
292                 obj->root = Reorganize_SVBVH<VBVHTree,VBVHNode>(obj).transform(root);
293         
294                 BLI_memarena_free(arena1);
295         }
296 /*
297         {
298                 obj->root = root;       
299         }
300 */
301
302         obj->cost = 1.0;
303         
304         rtbuild_free( obj->builder );
305         obj->builder = NULL;
306 }
307
308 template<int StackSize>
309 int intersect(VBVHTree *obj, Isect* isec)
310 {
311 /*
312         if(RE_DO_HINTS && isec->hint)
313         {
314                 LCTSHint *lcts = (LCTSHint*)isec->hint;
315                 isec->hint = 0;
316                 
317                 int hit = 0;
318                 for(int i=0; i<lcts->size; i++)
319                 {
320                         VBVHNode *node = (VBVHNode*)lcts->stack[i];
321                         if(RayObject_isAligned(node))
322                                 hit |= bvh_node_stack_raycast<VBVHNode,StackSize,true>(node, isec);
323                         else
324                                 hit |= RE_rayobject_intersect( (RayObject*)node, isec );
325                         
326                         if(hit && isec->mode == RE_RAY_SHADOW)
327                                 break;
328                 }
329                 isec->hint = (RayHint*)lcts;
330                 return hit;
331         }
332         else
333 */
334         {
335                 if(RayObject_isAligned(obj->root))
336                         return bvh_node_stack_raycast<SVBVHNode,StackSize,false>( obj->root, isec);
337                 else
338                         return RE_rayobject_intersect( (RayObject*) obj->root, isec );
339         }
340 }
341
342 template<class Node,class HintObject>
343 void bvh_dfs_make_hint(Node *node, LCTSHint *hint, int reserve_space, HintObject *hintObject);
344
345 template<class Node,class HintObject>
346 void bvh_dfs_make_hint_push_siblings(Node *node, LCTSHint *hint, int reserve_space, HintObject *hintObject)
347 {
348         if(!RayObject_isAligned(node))
349                 hint->stack[hint->size++] = (RayObject*)node;
350         else
351         {
352                 if(node->sibling)
353                         bvh_dfs_make_hint_push_siblings(node->sibling, hint, reserve_space+1, hintObject);
354
355                 bvh_dfs_make_hint(node, hint, reserve_space, hintObject);
356         }       
357 }
358
359 template<class Node,class HintObject>
360 void bvh_dfs_make_hint(Node *node, LCTSHint *hint, int reserve_space, HintObject *hintObject)
361 {
362         assert( hint->size + reserve_space + 1 <= RE_RAY_LCTS_MAX_SIZE );
363         
364         if(is_leaf(node))
365         {
366                 hint->stack[hint->size++] = (RayObject*)node;
367         }
368         else
369         {
370                 int childs = count_childs(node);
371                 if(hint->size + reserve_space + childs <= RE_RAY_LCTS_MAX_SIZE)
372                 {
373                         int result = hint_test_bb(hintObject, node->bb, node->bb+3);
374                         if(result == HINT_RECURSE)
375                         {
376                                 /* We are 100% sure the ray will be pass inside this node */
377                                 bvh_dfs_make_hint_push_siblings(node->child, hint, reserve_space, hintObject);
378                         }
379                         else if(result == HINT_ACCEPT)
380                         {
381                                 hint->stack[hint->size++] = (RayObject*)node;
382                         }
383                 }
384                 else
385                 {
386                         hint->stack[hint->size++] = (RayObject*)node;
387                 }
388         }
389 }
390
391 template<class Tree>
392 void bvh_hint_bb(Tree *tree, LCTSHint *hint, float *min, float *max)
393 {
394 /*
395         if(RE_USE_HINT)
396         {
397                 HintBB bb;
398                 VECCOPY(bb.bb, min);
399                 VECCOPY(bb.bb+3, max);
400
401                 hint->size = 0;
402                 bvh_dfs_make_hint( tree->root, hint, 0, &bb );
403                 tot_hints++;
404         }
405         else
406 */
407         {
408                 hint->size = 0;
409                 hint->stack[hint->size++] = (RayObject*)tree->root;
410         }
411 }
412
413 void bfree(VBVHTree *tree)
414 {
415         if(tot_pushup + tot_pushdown + tot_hints + tot_moves)
416         {
417                 printf("tot pushups: %d\n", tot_pushup);
418                 printf("tot pushdowns: %d\n", tot_pushdown);
419                 printf("tot moves: %d\n", tot_moves);
420                 printf("tot hints created: %d\n", tot_hints);
421                 tot_pushup = 0;
422                 tot_pushdown = 0;
423                 tot_hints = 0;
424                 tot_moves = 0;
425         }
426         bvh_free(tree);
427 }
428
429 /* the cast to pointer function is needed to workarround gcc bug: http://gcc.gnu.org/bugzilla/show_bug.cgi?id=11407 */
430 template<class Tree,int STACK_SIZE>
431 static RayObjectAPI make_api()
432 {
433         static RayObjectAPI api = 
434         {
435                 (RE_rayobject_raycast_callback) ((int(*)(Tree*,Isect*)) &intersect<STACK_SIZE>),
436                 (RE_rayobject_add_callback)     ((void(*)(Tree*,RayObject*)) &bvh_add<Tree>),
437                 (RE_rayobject_done_callback)    ((void(*)(Tree*))       &bvh_done<Tree>),
438 //              (RE_rayobject_free_callback)    ((void(*)(Tree*))       &bvh_free<Tree>),
439                 (RE_rayobject_free_callback)    ((void(*)(Tree*))       &bfree),
440                 (RE_rayobject_merge_bb_callback)((void(*)(Tree*,float*,float*)) &bvh_bb<Tree>),
441                 (RE_rayobject_cost_callback)    ((float(*)(Tree*))      &bvh_cost<Tree>),
442                 (RE_rayobject_hint_bb_callback) ((void(*)(Tree*,LCTSHint*,float*,float*)) &bvh_hint_bb<Tree>)
443         };
444         
445         return api;
446 }
447
448 template<class Tree>
449 static RayObjectAPI* get_api(int maxstacksize)
450 {
451         static RayObjectAPI bvh_api256 = make_api<Tree,1024>();
452         
453         if(maxstacksize <= 1024) return &bvh_api256;
454         assert(maxstacksize <= 256);
455         return 0;
456 }
457
458 RayObject *RE_rayobject_vbvh_create(int size)
459 {
460         VBVHTree *obj= (VBVHTree*)MEM_callocN(sizeof(VBVHTree), "VBVHTree");
461         assert( RayObject_isAligned(obj) ); /* RayObject API assumes real data to be 4-byte aligned */  
462         
463         obj->rayobj.api = get_api<VBVHTree>(DFS_STACK_SIZE);
464         obj->root = NULL;
465         
466         obj->node_arena = NULL;
467         obj->builder    = rtbuild_create( size );
468         
469         return RayObject_unalignRayAPI((RayObject*) obj);
470 }
471
472
473
474 /* SVBVH */
475 template<class HintObject>
476 void bvh_dfs_make_hint(VBVHNode *node, LCTSHint *hint, int reserve_space, HintObject *hintObject)
477 {
478         return;
479 }
480 /*
481 RayObject *RE_rayobject_svbvh_create(int size)
482 {
483         SVBVHTree *obj= (SVBVHTree*)MEM_callocN(sizeof(SVBVHTree), "SVBVHTree");
484         assert( RayObject_isAligned(obj) ); // RayObject API assumes real data to be 4-byte aligned
485         
486         obj->rayobj.api = get_api<SVBVHTree>(DFS_STACK_SIZE);
487         obj->root = NULL;
488         
489         obj->node_arena = NULL;
490         obj->builder    = rtbuild_create( size );
491         
492         return RayObject_unalignRayAPI((RayObject*) obj);
493 }
494 */