doxygen: prevent GPL license block from being parsed as doxygen comment.
[blender.git] / source / blender / render / intern / raytrace / bvh.h
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 #include "MEM_guardedalloc.h"
31
32 #include "BLI_math.h"
33
34 #include "raycounter.h"
35 #include "rayintersection.h"
36 #include "rayobject.h"
37 #include "rayobject_hint.h"
38 #include "rayobject_rtbuild.h"
39
40 #include <assert.h>
41
42 #ifdef __SSE__
43 #include <xmmintrin.h>
44 #endif
45
46 #ifndef RE_RAYTRACE_BVH_H
47 #define RE_RAYTRACE_BVH_H
48
49 #ifdef __SSE__
50 inline int test_bb_group4(__m128 *bb_group, const Isect *isec)
51 {
52         const __m128 tmin0 = _mm_setzero_ps();
53         const __m128 tmax0 = _mm_set_ps1(isec->dist);
54
55         float start[3], idot_axis[3];
56         copy_v3_v3(start, isec->start);
57         copy_v3_v3(idot_axis, isec->idot_axis);
58
59         const __m128 tmin1 = _mm_max_ps(tmin0, _mm_mul_ps( _mm_sub_ps( bb_group[isec->bv_index[0]], _mm_set_ps1(start[0]) ), _mm_set_ps1(idot_axis[0])) );
60         const __m128 tmax1 = _mm_min_ps(tmax0, _mm_mul_ps( _mm_sub_ps( bb_group[isec->bv_index[1]], _mm_set_ps1(start[0]) ), _mm_set_ps1(idot_axis[0])) );
61         const __m128 tmin2 = _mm_max_ps(tmin1, _mm_mul_ps( _mm_sub_ps( bb_group[isec->bv_index[2]], _mm_set_ps1(start[1]) ), _mm_set_ps1(idot_axis[1])) );
62         const __m128 tmax2 = _mm_min_ps(tmax1, _mm_mul_ps( _mm_sub_ps( bb_group[isec->bv_index[3]], _mm_set_ps1(start[1]) ), _mm_set_ps1(idot_axis[1])) );
63         const __m128 tmin3 = _mm_max_ps(tmin2, _mm_mul_ps( _mm_sub_ps( bb_group[isec->bv_index[4]], _mm_set_ps1(start[2]) ), _mm_set_ps1(idot_axis[2])) );
64         const __m128 tmax3 = _mm_min_ps(tmax2, _mm_mul_ps( _mm_sub_ps( bb_group[isec->bv_index[5]], _mm_set_ps1(start[2]) ), _mm_set_ps1(idot_axis[2])) );
65         
66         return _mm_movemask_ps(_mm_cmpge_ps(tmax3, tmin3));
67 }
68 #endif
69
70 /*
71  * Determines the distance that the ray must travel to hit the bounding volume of the given node
72  * Based on Tactical Optimization of Ray/Box Intersection, by Graham Fyffe
73  *  [http://tog.acm.org/resources/RTNews/html/rtnv21n1.html#art9]
74  */
75 static int rayobject_bb_intersect_test(const Isect *isec, const float *_bb)
76 {
77         const float *bb = _bb;
78         
79         float t1x = (bb[isec->bv_index[0]] - isec->start[0]) * isec->idot_axis[0];
80         float t2x = (bb[isec->bv_index[1]] - isec->start[0]) * isec->idot_axis[0];
81         float t1y = (bb[isec->bv_index[2]] - isec->start[1]) * isec->idot_axis[1];
82         float t2y = (bb[isec->bv_index[3]] - isec->start[1]) * isec->idot_axis[1];
83         float t1z = (bb[isec->bv_index[4]] - isec->start[2]) * isec->idot_axis[2];
84         float t2z = (bb[isec->bv_index[5]] - isec->start[2]) * isec->idot_axis[2];
85
86         RE_RC_COUNT(isec->raycounter->bb.test);
87         
88         if(t1x > t2y || t2x < t1y || t1x > t2z || t2x < t1z || t1y > t2z || t2y < t1z) return 0;
89         if(t2x < 0.0 || t2y < 0.0 || t2z < 0.0) return 0;
90         if(t1x > isec->dist || t1y > isec->dist || t1z > isec->dist) return 0;
91         RE_RC_COUNT(isec->raycounter->bb.hit);  
92
93         return 1;
94 }
95
96 /* bvh tree generics */
97 template<class Tree> static int bvh_intersect(Tree *obj, Isect *isec);
98
99 template<class Tree> static void bvh_add(Tree *obj, RayObject *ob)
100 {
101         rtbuild_add( obj->builder, ob );
102 }
103
104 template<class Node>
105 inline bool is_leaf(Node *node)
106 {
107         return !RE_rayobject_isAligned(node);
108 }
109
110 template<class Tree> static void bvh_done(Tree *obj);
111
112 template<class Tree>
113 static void bvh_free(Tree *obj)
114 {
115         if(obj->builder)
116                 rtbuild_free(obj->builder);
117
118         if(obj->node_arena)
119                 BLI_memarena_free(obj->node_arena);
120
121         MEM_freeN(obj);
122 }
123
124 template<class Tree>
125 static void bvh_bb(Tree *obj, float *min, float *max)
126 {
127         bvh_node_merge_bb(obj->root, min, max);
128 }
129
130
131 template<class Tree>
132 static float bvh_cost(Tree *obj)
133 {
134         assert(obj->cost >= 0.0);
135         return obj->cost;
136 }
137
138
139
140 /* bvh tree nodes generics */
141 template<class Node> static inline int bvh_node_hit_test(Node *node, Isect *isec)
142 {
143         return rayobject_bb_intersect_test(isec, (const float*)node->bb);
144 }
145
146
147 template<class Node>
148 static inline void bvh_node_merge_bb(Node *node, float *min, float *max)
149 {
150         if(is_leaf(node))
151         {
152                 RE_rayobject_merge_bb( (RayObject*)node, min, max);
153         }
154         else
155         {
156                 DO_MIN(node->bb  , min);
157                 DO_MAX(node->bb+3, max);
158         }
159 }
160
161
162
163 /*
164  * recursivly transverse a BVH looking for a rayhit using a local stack
165  */
166 template<class Node> static inline void bvh_node_push_childs(Node *node, Isect *isec, Node **stack, int &stack_pos);
167
168 template<class Node,int MAX_STACK_SIZE,bool TEST_ROOT,bool SHADOW>
169 static int bvh_node_stack_raycast(Node *root, Isect *isec)
170 {
171         Node *stack[MAX_STACK_SIZE];
172         int hit = 0, stack_pos = 0;
173                 
174         if(!TEST_ROOT && !is_leaf(root))
175                 bvh_node_push_childs(root, isec, stack, stack_pos);
176         else
177                 stack[stack_pos++] = root;
178
179         while(stack_pos)
180         {
181                 Node *node = stack[--stack_pos];
182                 if(!is_leaf(node))
183                 {
184                         if(bvh_node_hit_test(node,isec))
185                         {
186                                 bvh_node_push_childs(node, isec, stack, stack_pos);
187                                 assert(stack_pos <= MAX_STACK_SIZE);
188                         }
189                 }
190                 else
191                 {
192                         hit |= RE_rayobject_intersect( (RayObject*)node, isec);
193                         if(SHADOW && hit) return hit;
194                 }
195         }
196         return hit;
197 }
198
199
200 #ifdef __SSE__
201 /*
202  * Generic SIMD bvh recursion
203  * this was created to be able to use any simd (with the cost of some memmoves)
204  * it can take advantage of any SIMD width and doens't needs any special tree care
205  */
206 template<class Node,int MAX_STACK_SIZE,bool TEST_ROOT>
207 static int bvh_node_stack_raycast_simd(Node *root, Isect *isec)
208 {
209         Node *stack[MAX_STACK_SIZE];
210
211         int hit = 0, stack_pos = 0;
212                 
213         if(!TEST_ROOT)
214         {
215                 if(!is_leaf(root))
216                 {
217                         if(!is_leaf(root->child))
218                                 bvh_node_push_childs(root, isec, stack, stack_pos);
219                         else
220                                 return RE_rayobject_intersect( (RayObject*)root->child, isec);
221                 }
222                 else
223                         return RE_rayobject_intersect( (RayObject*)root, isec);
224         }
225         else
226         {
227                 if(!is_leaf(root))
228                         stack[stack_pos++] = root;
229                 else
230                         return RE_rayobject_intersect( (RayObject*)root, isec);
231         }
232
233         while(true)
234         {
235                 //Use SIMD 4
236                 if(stack_pos >= 4)
237                 {
238                         __m128 t_bb[6];
239                         Node * t_node[4];
240                         
241                         stack_pos -= 4;
242
243                         /* prepare the 4BB for SIMD */
244                         t_node[0] = stack[stack_pos+0]->child;
245                         t_node[1] = stack[stack_pos+1]->child;
246                         t_node[2] = stack[stack_pos+2]->child;
247                         t_node[3] = stack[stack_pos+3]->child;
248                         
249                         const float *bb0 = stack[stack_pos+0]->bb;
250                         const float *bb1 = stack[stack_pos+1]->bb;
251                         const float *bb2 = stack[stack_pos+2]->bb;
252                         const float *bb3 = stack[stack_pos+3]->bb;
253                         
254                         const __m128 x0y0x1y1 = _mm_shuffle_ps( _mm_load_ps(bb0), _mm_load_ps(bb1), _MM_SHUFFLE(1,0,1,0) );
255                         const __m128 x2y2x3y3 = _mm_shuffle_ps( _mm_load_ps(bb2), _mm_load_ps(bb3), _MM_SHUFFLE(1,0,1,0) );
256                         t_bb[0] = _mm_shuffle_ps( x0y0x1y1, x2y2x3y3, _MM_SHUFFLE(2,0,2,0) );
257                         t_bb[1] = _mm_shuffle_ps( x0y0x1y1, x2y2x3y3, _MM_SHUFFLE(3,1,3,1) );
258
259                         const __m128 z0X0z1X1 = _mm_shuffle_ps( _mm_load_ps(bb0), _mm_load_ps(bb1), _MM_SHUFFLE(3,2,3,2) );
260                         const __m128 z2X2z3X3 = _mm_shuffle_ps( _mm_load_ps(bb2), _mm_load_ps(bb3), _MM_SHUFFLE(3,2,3,2) );
261                         t_bb[2] = _mm_shuffle_ps( z0X0z1X1, z2X2z3X3, _MM_SHUFFLE(2,0,2,0) );
262                         t_bb[3] = _mm_shuffle_ps( z0X0z1X1, z2X2z3X3, _MM_SHUFFLE(3,1,3,1) );
263
264                         const __m128 Y0Z0Y1Z1 = _mm_shuffle_ps( _mm_load_ps(bb0+4), _mm_load_ps(bb1+4), _MM_SHUFFLE(1,0,1,0) );
265                         const __m128 Y2Z2Y3Z3 = _mm_shuffle_ps( _mm_load_ps(bb2+4), _mm_load_ps(bb3+4), _MM_SHUFFLE(1,0,1,0) );
266                         t_bb[4] = _mm_shuffle_ps( Y0Z0Y1Z1, Y2Z2Y3Z3, _MM_SHUFFLE(2,0,2,0) );
267                         t_bb[5] = _mm_shuffle_ps( Y0Z0Y1Z1, Y2Z2Y3Z3, _MM_SHUFFLE(3,1,3,1) );
268 /*                      
269                         for(int i=0; i<4; i++)
270                         {
271                                 Node *t = stack[stack_pos+i];
272                                 assert(!is_leaf(t));
273                                 
274                                 float *bb = ((float*)t_bb)+i;
275                                 bb[4*0] = t->bb[0];
276                                 bb[4*1] = t->bb[1];
277                                 bb[4*2] = t->bb[2];
278                                 bb[4*3] = t->bb[3];
279                                 bb[4*4] = t->bb[4];
280                                 bb[4*5] = t->bb[5];
281                                 t_node[i] = t->child;
282                         }
283 */
284                         RE_RC_COUNT(isec->raycounter->simd_bb.test);
285                         int res = test_bb_group4( t_bb, isec );
286
287                         for(int i=0; i<4; i++)
288                         if(res & (1<<i))
289                         {
290                                 RE_RC_COUNT(isec->raycounter->simd_bb.hit);
291                                 if(!is_leaf(t_node[i]))
292                                 {
293                                         for(Node *t=t_node[i]; t; t=t->sibling)
294                                         {
295                                                 assert(stack_pos < MAX_STACK_SIZE);
296                                                 stack[stack_pos++] = t;
297                                         }
298                                 }
299                                 else
300                                 {
301                                         hit |= RE_rayobject_intersect( (RayObject*)t_node[i], isec);
302                                         if(hit && isec->mode == RE_RAY_SHADOW) return hit;                              
303                                 }       
304                         }
305                 }
306                 else if(stack_pos > 0)
307                 {       
308                         Node *node = stack[--stack_pos];
309                         assert(!is_leaf(node));
310                         
311                         if(bvh_node_hit_test(node,isec))
312                         {
313                                 if(!is_leaf(node->child))
314                                 {
315                                         bvh_node_push_childs(node, isec, stack, stack_pos);
316                                         assert(stack_pos <= MAX_STACK_SIZE);
317                                 }
318                                 else
319                                 {
320                                         hit |= RE_rayobject_intersect( (RayObject*)node->child, isec);
321                                         if(hit && isec->mode == RE_RAY_SHADOW) return hit;
322                                 }
323                         }
324                 }
325                 else break;
326         }
327         return hit;
328 }
329 #endif
330
331 /*
332  * recursively transverse a BVH looking for a rayhit using system stack
333  */
334 /*
335 template<class Node>
336 static int bvh_node_raycast(Node *node, Isect *isec)
337 {
338         int hit = 0;
339         if(bvh_test_node(node, isec))
340         {
341                 if(isec->idot_axis[node->split_axis] > 0.0f)
342                 {
343                         int i;
344                         for(i=0; i<BVH_NCHILDS; i++)
345                                 if(!is_leaf(node->child[i]))
346                                 {
347                                         if(node->child[i] == 0) break;
348                                         
349                                         hit |= bvh_node_raycast(node->child[i], isec);
350                                         if(hit && isec->mode == RE_RAY_SHADOW) return hit;
351                                 }
352                                 else
353                                 {
354                                         hit |= RE_rayobject_intersect( (RayObject*)node->child[i], isec);
355                                         if(hit && isec->mode == RE_RAY_SHADOW) return hit;
356                                 }
357                 }
358                 else
359                 {
360                         int i;
361                         for(i=BVH_NCHILDS-1; i>=0; i--)
362                                 if(!is_leaf(node->child[i]))
363                                 {
364                                         if(node->child[i])
365                                         {
366                                                 hit |= dfs_raycast(node->child[i], isec);
367                                                 if(hit && isec->mode == RE_RAY_SHADOW) return hit;
368                                         }
369                                 }
370                                 else
371                                 {
372                                         hit |= RE_rayobject_intersect( (RayObject*)node->child[i], isec);
373                                         if(hit && isec->mode == RE_RAY_SHADOW) return hit;
374                                 }
375                 }
376         }
377         return hit;
378 }
379 */
380
381 template<class Node,class HintObject>
382 void bvh_dfs_make_hint(Node *node, LCTSHint *hint, int reserve_space, HintObject *hintObject)
383 {
384         assert( hint->size + reserve_space + 1 <= RE_RAY_LCTS_MAX_SIZE );
385         
386         if(is_leaf(node))
387         {
388                 hint->stack[hint->size++] = (RayObject*)node;
389         }
390         else
391         {
392                 int childs = count_childs(node);
393                 if(hint->size + reserve_space + childs <= RE_RAY_LCTS_MAX_SIZE)
394                 {
395                         int result = hint_test_bb(hintObject, node->bb, node->bb+3);
396                         if(result == HINT_RECURSE)
397                         {
398                                 /* We are 100% sure the ray will be pass inside this node */
399                                 bvh_dfs_make_hint_push_siblings(node->child, hint, reserve_space, hintObject);
400                         }
401                         else if(result == HINT_ACCEPT)
402                         {
403                                 hint->stack[hint->size++] = (RayObject*)node;
404                         }
405                 }
406                 else
407                 {
408                         hint->stack[hint->size++] = (RayObject*)node;
409                 }
410         }
411 }
412
413
414 template<class Tree>
415 static RayObjectAPI* bvh_get_api(int maxstacksize);
416
417
418 template<class Tree, int DFS_STACK_SIZE>
419 static inline RayObject *bvh_create_tree(int size)
420 {
421         Tree *obj= (Tree*)MEM_callocN(sizeof(Tree), "BVHTree" );
422         assert( RE_rayobject_isAligned(obj) ); /* RayObject API assumes real data to be 4-byte aligned */       
423         
424         obj->rayobj.api = bvh_get_api<Tree>(DFS_STACK_SIZE);
425         obj->root = NULL;
426         
427         obj->node_arena = NULL;
428         obj->builder    = rtbuild_create( size );
429         
430         return RE_rayobject_unalignRayAPI((RayObject*) obj);
431 }
432
433 #endif