9e7075438cb9d7e53f57931fad92391b6160b1d4
[blender.git] / source / blender / render / intern / raytrace / rayobject_vbvh.cpp
1 /*
2  * ***** BEGIN GPL LICENSE BLOCK *****
3  *
4  * This program is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU General Public License
6  * as published by the Free Software Foundation; either version 2
7  * of the License, or (at your option) any later version. 
8  *
9  * This program is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program; if not, write to the Free Software Foundation,
16  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
17  *
18  * The Original Code is Copyright (C) 2009 Blender Foundation.
19  * All rights reserved.
20  *
21  * The Original Code is: all of this file.
22  *
23  * Contributor(s): AndrĂ© Pinto.
24  *
25  * ***** END GPL LICENSE BLOCK *****
26  */
27
28 /** \file blender/render/intern/raytrace/rayobject_vbvh.cpp
29  *  \ingroup render
30  */
31
32
33 int tot_pushup   = 0;
34 int tot_pushdown = 0;
35 int tot_hints    = 0;
36
37 #include <assert.h>
38
39 #include "MEM_guardedalloc.h"
40
41 #include "BKE_global.h"
42
43 #include "BLI_math.h"
44 #include "BLI_memarena.h"
45 #include "BLI_utildefines.h"
46
47 #include "rayintersection.h"
48 #include "rayobject.h"
49 #include "rayobject_rtbuild.h"
50
51 #include "reorganize.h"
52 #include "bvh.h"
53 #include "vbvh.h"
54
55 #include <queue>
56 #include <algorithm>
57
58 #define DFS_STACK_SIZE  256
59
60 struct VBVHTree {
61         RayObject rayobj;
62         VBVHNode *root;
63         MemArena *node_arena;
64         float cost;
65         RTBuilder *builder;
66 };
67
68 /*
69  * Cost to test N childs
70  */
71 struct PackCost {
72         float operator()(int n)
73         {
74                 return n;
75         }
76 };
77
78 template<>
79 void bvh_done<VBVHTree>(VBVHTree *obj)
80 {
81         rtbuild_done(obj->builder, &obj->rayobj.control);
82         
83         //TODO find a away to exactly calculate the needed memory
84         MemArena *arena1 = BLI_memarena_new(BLI_MEMARENA_STD_BUFSIZE, "vbvh arena");
85         BLI_memarena_use_malloc(arena1);
86         
87         //Build and optimize the tree
88         if (1) {
89                 VBVHNode *root = BuildBinaryVBVH<VBVHNode>(arena1, &obj->rayobj.control).transform(obj->builder);
90                 if (RE_rayobjectcontrol_test_break(&obj->rayobj.control)) {
91                         BLI_memarena_free(arena1);
92                         return;
93                 }
94
95                 if (root) {
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                         obj->root = NULL;
106         }
107         else {
108                 /* TODO */
109 #if 0
110                 MemArena *arena2 = BLI_memarena_new(BLI_MEMARENA_STD_BUFSIZE, "vbvh arena2");
111                 BLI_memarena_use_malloc(arena2);
112                                                    
113                 //Finds the optimal packing of this tree using a given cost model
114                 //TODO this uses quite a lot of memory, find ways to reduce memory usage during building
115                 OVBVHNode *root = BuildBinaryVBVH<OVBVHNode>(arena2).transform(obj->builder);                   
116                 VBVH_optimalPackSIMD<OVBVHNode, PackCost>(PackCost()).transform(root);
117                 obj->root = Reorganize_VBVH<OVBVHNode>(arena1).transform(root);
118                 
119                 BLI_memarena_free(arena2);
120 #endif
121         }
122
123         //Cleanup
124         rtbuild_free(obj->builder);
125         obj->builder = NULL;
126
127         obj->node_arena = arena1;
128         obj->cost = 1.0;        
129 }
130
131 template<int StackSize>
132 int intersect(VBVHTree *obj, Isect *isec)
133 {
134         //TODO renable hint support
135         if (RE_rayobject_isAligned(obj->root)) {
136                 if (isec->mode == RE_RAY_SHADOW)
137                         return bvh_node_stack_raycast<VBVHNode, StackSize, false, true>(obj->root, isec);
138                 else
139                         return bvh_node_stack_raycast<VBVHNode, StackSize, false, false>(obj->root, isec);
140         }
141         else
142                 return RE_rayobject_intersect( (RayObject *) obj->root, isec);
143 }
144
145 template<class Tree>
146 void bvh_hint_bb(Tree *tree, LCTSHint *hint, float *UNUSED(min), float *UNUSED(max))
147 {
148         //TODO renable hint support
149         {
150                 hint->size = 0;
151                 hint->stack[hint->size++] = (RayObject *)tree->root;
152         }
153 }
154
155 void bfree(VBVHTree *tree)
156 {
157         if (tot_pushup + tot_pushdown + tot_hints + tot_moves) {
158                 if (G.debug & G_DEBUG) {
159                         printf("tot pushups: %d\n", tot_pushup);
160                         printf("tot pushdowns: %d\n", tot_pushdown);
161                         printf("tot moves: %d\n", tot_moves);
162                         printf("tot hints created: %d\n", tot_hints);
163                 }
164
165                 tot_pushup = 0;
166                 tot_pushdown = 0;
167                 tot_hints = 0;
168                 tot_moves = 0;
169         }
170         bvh_free(tree);
171 }
172
173 /* the cast to pointer function is needed to workarround gcc bug: http://gcc.gnu.org/bugzilla/show_bug.cgi?id=11407 */
174 template<class Tree, int STACK_SIZE>
175 RayObjectAPI make_api()
176 {
177         static RayObjectAPI api = 
178         {
179                 (RE_rayobject_raycast_callback) ((int   (*)(Tree *, Isect *)) & intersect<STACK_SIZE>),
180                 (RE_rayobject_add_callback)     ((void  (*)(Tree *, RayObject *)) & bvh_add<Tree>),
181                 (RE_rayobject_done_callback)    ((void  (*)(Tree *))       & bvh_done<Tree>),
182                 (RE_rayobject_free_callback)    ((void  (*)(Tree *))       & bvh_free<Tree>),
183                 (RE_rayobject_merge_bb_callback)((void  (*)(Tree *, float *, float *)) & bvh_bb<Tree>),
184                 (RE_rayobject_cost_callback)    ((float (*)(Tree *))      & bvh_cost<Tree>),
185                 (RE_rayobject_hint_bb_callback) ((void  (*)(Tree *, LCTSHint *, float *, float *)) & bvh_hint_bb<Tree>)
186         };
187         
188         return api;
189 }
190
191 template<class Tree>
192 RayObjectAPI *bvh_get_api(int maxstacksize)
193 {
194         static RayObjectAPI bvh_api256 = make_api<Tree, 1024>();
195         
196         if (maxstacksize <= 1024) return &bvh_api256;
197         assert(maxstacksize <= 256);
198         return 0;
199 }
200
201 RayObject *RE_rayobject_vbvh_create(int size)
202 {
203         return bvh_create_tree<VBVHTree, DFS_STACK_SIZE>(size);
204 }