doxygen: prevent GPL license block from being parsed as doxygen comment.
[blender.git] / source / blender / render / intern / raytrace / vbvh.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 <assert.h>
31 #include <algorithm>
32
33 #include "BLI_memarena.h"
34
35 #include "rayobject_rtbuild.h"
36
37 /*
38  * VBVHNode represents a BVHNode with support for a variable number of childrens
39  */
40 struct VBVHNode
41 {
42         float   bb[6];
43
44         VBVHNode *child;
45         VBVHNode *sibling;
46 };
47
48
49 /*
50  * Push nodes (used on dfs)
51  */
52 template<class Node>
53 inline static void bvh_node_push_childs(Node *node, Isect *isec, Node **stack, int &stack_pos)
54 {
55         Node *child = node->child;
56
57         if(is_leaf(child))
58         {
59                 stack[stack_pos++] = child;
60         }
61         else
62         {
63                 while(child)
64                 {
65                         //Skips BB tests on primitives
66 /*
67                         if(is_leaf(child->child))
68                                 stack[stack_pos++] = child->child;
69                         else
70 */
71                                 stack[stack_pos++] = child;
72                                 
73                         child = child->sibling;
74                 }
75         }
76 }
77
78
79 template<class Node>
80 int count_childs(Node *parent)
81 {
82         int n = 0;
83         for(Node *i = parent->child; i; i = i->sibling)
84         {
85                 n++;
86                 if(is_leaf(i))
87                         break;
88         }
89                 
90         return n;
91 }
92
93
94 template<class Node>
95 void append_sibling(Node *node, Node *sibling)
96 {
97         while(node->sibling)
98                 node = node->sibling;
99                 
100         node->sibling = sibling;
101 }
102
103
104 /*
105  * Builds a binary VBVH from a rtbuild
106  */
107 template<class Node>
108 struct BuildBinaryVBVH
109 {
110         MemArena *arena;
111         RayObjectControl *control;
112
113         void test_break()
114         {
115                 if(RE_rayobjectcontrol_test_break(control))
116                         throw "Stop";
117         }
118
119         BuildBinaryVBVH(MemArena *a, RayObjectControl *c)
120         {
121                 arena = a;
122                 control = c;
123         }
124
125         Node *create_node()
126         {
127                 Node *node = (Node*)BLI_memarena_alloc( arena, sizeof(Node) );
128                 assert( RE_rayobject_isAligned(node) );
129
130                 node->sibling = NULL;
131                 node->child   = NULL;
132
133                 return node;
134         }
135         
136         int rtbuild_split(RTBuilder *builder)
137         {
138                 return ::rtbuild_heuristic_object_split(builder, 2);
139         }
140         
141         Node *transform(RTBuilder *builder)
142         {
143                 try
144                 {
145                         return _transform(builder);
146                         
147                 } catch(...)
148                 {
149                 }
150                 return NULL;
151         }
152         
153         Node *_transform(RTBuilder *builder)
154         {
155                 
156                 int size = rtbuild_size(builder);
157                 if(size == 1)
158                 {
159                         Node *node = create_node();
160                         INIT_MINMAX(node->bb, node->bb+3);
161                         rtbuild_merge_bb(builder, node->bb, node->bb+3);                
162                         node->child = (Node*) rtbuild_get_primitive( builder, 0 );
163                         return node;
164                 }
165                 else
166                 {
167                         test_break();
168                         
169                         Node *node = create_node();
170
171                         Node **child = &node->child;
172
173                         int nc = rtbuild_split(builder);
174                         INIT_MINMAX(node->bb, node->bb+3);
175
176                         assert(nc == 2);
177                         for(int i=0; i<nc; i++)
178                         {
179                                 RTBuilder tmp;
180                                 rtbuild_get_child(builder, i, &tmp);
181                                 
182                                 *child = _transform(&tmp);
183                                 DO_MIN((*child)->bb, node->bb);
184                                 DO_MAX((*child)->bb+3, node->bb+3);
185                                 child = &((*child)->sibling);
186                         }
187
188                         *child = 0;
189                         return node;
190                 }
191         }
192 };
193
194 /*
195 template<class Tree,class OldNode>
196 struct Reorganize_VBVH
197 {
198         Tree *tree;
199         
200         Reorganize_VBVH(Tree *t)
201         {
202                 tree = t;
203         }
204         
205         VBVHNode *create_node()
206         {
207                 VBVHNode *node = (VBVHNode*)BLI_memarena_alloc(tree->node_arena, sizeof(VBVHNode));
208                 return node;
209         }
210         
211         void copy_bb(VBVHNode *node, OldNode *old)
212         {
213                 std::copy( old->bb, old->bb+6, node->bb );
214         }
215         
216         VBVHNode *transform(OldNode *old)
217         {
218                 if(is_leaf(old))
219                         return (VBVHNode*)old;
220
221                 VBVHNode *node = create_node();
222                 VBVHNode **child_ptr = &node->child;
223                 node->sibling = 0;
224
225                 copy_bb(node,old);
226
227                 for(OldNode *o_child = old->child; o_child; o_child = o_child->sibling)
228                 {
229                         VBVHNode *n_child = transform(o_child);
230                         *child_ptr = n_child;
231                         if(is_leaf(n_child)) return node;
232                         child_ptr = &n_child->sibling;
233                 }
234                 *child_ptr = 0;
235                 
236                 return node;
237         }       
238 };
239 */