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