doxygen: prevent GPL license block from being parsed as doxygen comment.
[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., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, 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
30 int tot_pushup   = 0;
31 int tot_pushdown = 0;
32 int tot_hints    = 0;
33
34 #include <assert.h>
35
36 #include "MEM_guardedalloc.h"
37
38 #include "BKE_global.h"
39
40 #include "BLI_math.h"
41 #include "BLI_memarena.h"
42 #include "BLI_utildefines.h"
43
44 #include "rayintersection.h"
45 #include "rayobject.h"
46 #include "rayobject_rtbuild.h"
47
48 #include "reorganize.h"
49 #include "bvh.h"
50 #include "vbvh.h"
51
52 #include <queue>
53 #include <algorithm>
54
55 #define DFS_STACK_SIZE  256
56
57 struct VBVHTree
58 {
59         RayObject rayobj;
60         VBVHNode *root;
61         MemArena *node_arena;
62         float cost;
63         RTBuilder *builder;
64 };
65
66 /*
67  * Cost to test N childs
68  */
69 struct PackCost
70 {
71         float operator()(int n)
72         {
73                 return n;
74         }
75 };
76
77 template<>
78 void bvh_done<VBVHTree>(VBVHTree *obj)
79 {
80         rtbuild_done(obj->builder, &obj->rayobj.control);
81         
82         //TODO find a away to exactly calculate the needed memory
83         MemArena *arena1 = BLI_memarena_new(BLI_MEMARENA_STD_BUFSIZE, "vbvh arena");
84                                            BLI_memarena_use_malloc(arena1);
85         
86         //Build and optimize the tree
87         if(1)
88         {
89                 VBVHNode *root = BuildBinaryVBVH<VBVHNode>(arena1,&obj->rayobj.control).transform(obj->builder);
90                 if(RE_rayobjectcontrol_test_break(&obj->rayobj.control))
91                 {
92                         BLI_memarena_free(arena1);
93                         return;
94                 }
95
96                 reorganize(root);
97                 remove_useless(root, &root);
98                 bvh_refit(root);
99         
100                 pushup(root);
101                 pushdown(root);
102                 obj->root = root;
103         }
104         else
105         {
106 /*
107         TODO
108                 MemArena *arena2 = BLI_memarena_new(BLI_MEMARENA_STD_BUFSIZE, "vbvh arena2");
109                                                    BLI_memarena_use_malloc(arena2);
110                                                    
111                 //Finds the optimal packing of this tree using a given cost model
112                 //TODO this uses quite a lot of memory, find ways to reduce memory usage during building
113                 OVBVHNode *root = BuildBinaryVBVH<OVBVHNode>(arena2).transform(obj->builder);                   
114                 VBVH_optimalPackSIMD<OVBVHNode,PackCost>(PackCost()).transform(root);
115                 obj->root = Reorganize_VBVH<OVBVHNode>(arena1).transform(root);
116                 
117                 BLI_memarena_free(arena2);
118  */
119         }
120
121         //Cleanup
122         rtbuild_free( obj->builder );
123         obj->builder = NULL;
124
125         obj->node_arena = arena1;
126         obj->cost = 1.0;        
127 }
128
129 template<int StackSize>
130 int intersect(VBVHTree *obj, Isect* isec)
131 {
132         //TODO renable hint support
133         if(RE_rayobject_isAligned(obj->root)) {
134                 if(isec->mode == RE_RAY_SHADOW)
135                         return bvh_node_stack_raycast<VBVHNode,StackSize,false,true>( obj->root, isec);
136                 else
137                         return bvh_node_stack_raycast<VBVHNode,StackSize,false,false>( obj->root, isec);
138         }
139         else
140                 return RE_rayobject_intersect( (RayObject*) obj->root, isec );
141 }
142
143 template<class Tree>
144 void bvh_hint_bb(Tree *tree, LCTSHint *hint, float *min, float *max)
145 {
146         //TODO renable hint support
147         {
148                 hint->size = 0;
149                 hint->stack[hint->size++] = (RayObject*)tree->root;
150         }
151 }
152
153 void bfree(VBVHTree *tree)
154 {
155         if(tot_pushup + tot_pushdown + tot_hints + tot_moves)
156         {
157                 if(G.f & G_DEBUG) {
158                         printf("tot pushups: %d\n", tot_pushup);
159                         printf("tot pushdowns: %d\n", tot_pushdown);
160                         printf("tot moves: %d\n", tot_moves);
161                         printf("tot hints created: %d\n", tot_hints);
162                 }
163
164                 tot_pushup = 0;
165                 tot_pushdown = 0;
166                 tot_hints = 0;
167                 tot_moves = 0;
168         }
169         bvh_free(tree);
170 }
171
172 /* the cast to pointer function is needed to workarround gcc bug: http://gcc.gnu.org/bugzilla/show_bug.cgi?id=11407 */
173 template<class Tree, int STACK_SIZE>
174 RayObjectAPI make_api()
175 {
176         static RayObjectAPI api = 
177         {
178                 (RE_rayobject_raycast_callback) ((int(*)(Tree*,Isect*)) &intersect<STACK_SIZE>),
179                 (RE_rayobject_add_callback)     ((void(*)(Tree*,RayObject*)) &bvh_add<Tree>),
180                 (RE_rayobject_done_callback)    ((void(*)(Tree*))       &bvh_done<Tree>),
181                 (RE_rayobject_free_callback)    ((void(*)(Tree*))       &bvh_free<Tree>),
182                 (RE_rayobject_merge_bb_callback)((void(*)(Tree*,float*,float*)) &bvh_bb<Tree>),
183                 (RE_rayobject_cost_callback)    ((float(*)(Tree*))      &bvh_cost<Tree>),
184                 (RE_rayobject_hint_bb_callback) ((void(*)(Tree*,LCTSHint*,float*,float*)) &bvh_hint_bb<Tree>)
185         };
186         
187         return api;
188 }
189
190 template<class Tree>
191 RayObjectAPI* bvh_get_api(int maxstacksize)
192 {
193         static RayObjectAPI bvh_api256 = make_api<Tree,1024>();
194         
195         if(maxstacksize <= 1024) return &bvh_api256;
196         assert(maxstacksize <= 256);
197         return 0;
198 }
199
200 RayObject *RE_rayobject_vbvh_create(int size)
201 {
202         return bvh_create_tree<VBVHTree,DFS_STACK_SIZE>(size);
203 }