d9277f9a5839deb5317ade3fd0991e934ad39228
[blender-staging.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., 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
30 /* bvh tree generics */
31 template<class Tree> static int bvh_intersect(Tree *obj, Isect *isec);
32
33 template<class Tree> static void bvh_add(Tree *obj, RayObject *ob)
34 {
35         rtbuild_add( obj->builder, ob );
36 }
37
38 template<class Tree> static void bvh_done(Tree *obj);
39
40 template<class Tree>
41 static void bvh_free(Tree *obj)
42 {
43         if(obj->builder)
44                 rtbuild_free(obj->builder);
45
46         if(obj->node_arena)
47                 BLI_memarena_free(obj->node_arena);
48
49         MEM_freeN(obj);
50 }
51
52 template<class Tree>
53 static void bvh_bb(Tree *obj, float *min, float *max)
54 {
55         bvh_node_merge_bb(obj->root, min, max);
56 }
57
58
59 template<class Tree>
60 static float bvh_cost(Tree *obj)
61 {
62         assert(obj->cost >= 0.0);
63         return obj->cost;
64 }
65
66
67
68 /* bvh tree nodes generics */
69 template<class Node> static inline int bvh_node_hit_test(Node *node, Isect *isec)
70 {
71         return RE_rayobject_bb_intersect(isec, (const float*)node->bb) != FLT_MAX;
72 }
73
74
75 template<class Node>
76 static void bvh_node_merge_bb(Node *node, float *min, float *max)
77 {
78         if(RayObject_isAligned(node))
79         {
80                 DO_MIN(node->bb  , min);
81                 DO_MAX(node->bb+3, max);
82         }
83         else
84         {
85                 RE_rayobject_merge_bb( (RayObject*)node, min, max);
86         }
87 }
88
89
90
91 /*
92  * recursivly transverse a BVH looking for a rayhit using a local stack
93  */
94 template<class Node> static inline void bvh_node_push_childs(Node *node, Isect *isec, Node **stack, int &stack_pos);
95
96 template<class Node,int MAX_STACK_SIZE>
97 static int bvh_node_stack_raycast(Node *root, Isect *isec)
98 {
99         Node *stack[MAX_STACK_SIZE];
100         int hit = 0, stack_pos = 0;
101                 
102         //Assume the BB of root always succeed
103         if(1)
104                 bvh_node_push_childs(root, isec, stack, stack_pos);
105         else
106                 stack[stack_pos++] = root;
107
108         while(stack_pos)
109         {
110                 Node *node = stack[--stack_pos];
111                 if(RayObject_isAligned(node))
112                 {
113                         if(bvh_node_hit_test(node,isec))
114                         {
115                                 bvh_node_push_childs(node, isec, stack, stack_pos);
116                                 assert(stack_pos <= MAX_STACK_SIZE);
117                         }
118                 }
119                 else
120                 {
121                         hit |= RE_rayobject_intersect( (RayObject*)node, isec);
122                         if(hit && isec->mode == RE_RAY_SHADOW) return hit;
123                 }
124         }
125         return hit;
126
127 }
128
129 /*
130  * recursively transverse a BVH looking for a rayhit using system stack
131  */
132 /*
133 template<class Node>
134 static int bvh_node_raycast(Node *node, Isect *isec)
135 {
136         int hit = 0;
137         if(bvh_test_node(node, isec))
138         {
139                 if(isec->idot_axis[node->split_axis] > 0.0f)
140                 {
141                         int i;
142                         for(i=0; i<BVH_NCHILDS; i++)
143                                 if(RayObject_isAligned(node->child[i]))
144                                 {
145                                         if(node->child[i] == 0) break;
146                                         
147                                         hit |= bvh_node_raycast(node->child[i], isec);
148                                         if(hit && isec->mode == RE_RAY_SHADOW) return hit;
149                                 }
150                                 else
151                                 {
152                                         hit |= RE_rayobject_intersect( (RayObject*)node->child[i], isec);
153                                         if(hit && isec->mode == RE_RAY_SHADOW) return hit;
154                                 }
155                 }
156                 else
157                 {
158                         int i;
159                         for(i=BVH_NCHILDS-1; i>=0; i--)
160                                 if(RayObject_isAligned(node->child[i]))
161                                 {
162                                         if(node->child[i])
163                                         {
164                                                 hit |= dfs_raycast(node->child[i], isec);
165                                                 if(hit && isec->mode == RE_RAY_SHADOW) return hit;
166                                         }
167                                 }
168                                 else
169                                 {
170                                         hit |= RE_rayobject_intersect( (RayObject*)node->child[i], isec);
171                                         if(hit && isec->mode == RE_RAY_SHADOW) return hit;
172                                 }
173                 }
174         }
175         return hit;
176 }
177 */