*Added a tree structure with a variable number of childs per node, but with groupped...
[blender.git] / source / blender / render / intern / raytrace / reorganize.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 <algorithm>
30 #include <queue>
31
32 template<class Node>
33 bool node_fits_inside(Node *a, Node *b)
34 {
35         return bb_fits_inside(b->bb, b->bb+3, a->bb, a->bb+3);
36 }
37
38 template<class Node>
39 void reorganize_find_fittest_parent(Node *tree, Node *node, std::pair<float,Node*> &cost)
40 {
41         std::queue<Node*> q;
42         q.push(tree);
43         
44         while(!q.empty())
45         {
46                 Node *parent = q.front();
47                 q.pop();
48                 
49                 if(parent == node) continue;
50                 if(node_fits_inside(node, parent) && RayObject_isAligned(parent->child) )
51                 {
52                         float pcost = bb_area(parent->bb, parent->bb+3);
53                         cost = std::min( cost, std::make_pair(pcost,parent) );
54                         for(Node *child = parent->child; child; child = child->sibling)
55                                 q.push(child);                  
56                 }
57         }
58 }
59
60 static int tot_moves = 0;
61 template<class Node>
62 void reorganize(Node *root)
63 {
64         std::queue<Node*> q;
65
66         q.push(root);
67         while(!q.empty())
68         {
69                 Node * node = q.front();
70                 q.pop();
71                 
72                 if( RayObject_isAligned(node->child) )
73                 {
74                         for(Node **prev = &node->child; *prev; )
75                         {
76                                 assert( RayObject_isAligned(*prev) ); 
77                                 q.push(*prev);
78
79                                 std::pair<float,Node*> best(FLT_MAX, root);
80                                 reorganize_find_fittest_parent( root, *prev, best );
81
82                                 if(best.second == node)
83                                 {
84                                         //Already inside the fitnest BB
85                                         prev = &(*prev)->sibling;
86                                 }
87                                 else
88                                 {
89                                         Node *tmp = *prev;
90                                         *prev = (*prev)->sibling;
91                                         
92                                         tmp->sibling =  best.second->child;
93                                         best.second->child = tmp;
94                                         
95                                         tot_moves++;
96                                 }
97                         
98                         
99                         }
100                 }
101                 if(node != root)
102                 {
103                 }
104         }
105 }
106
107 /*
108  * Prunes useless nodes from trees:
109  *  erases nodes with total ammount of primitives = 0
110  *  prunes nodes with only one child (except if that child is a primitive)
111  */
112 template<class Node>
113 void remove_useless(Node *node, Node **new_node)
114 {
115         if( RayObject_isAligned(node->child) )
116         {
117
118                 for(Node **prev = &node->child; *prev; )
119                 {
120                         Node *next = (*prev)->sibling;
121                         remove_useless(*prev, prev);
122                         if(*prev == 0)
123                                 *prev = next;
124                         else
125                         {
126                                 (*prev)->sibling = next;
127                                 prev = &((*prev)->sibling);
128                         }
129                 }                       
130         }
131         if(node->child)
132         {
133                 if(RayObject_isAligned(node->child) && node->child->sibling == 0)
134                         *new_node = node->child;
135         }
136         else if(node->child == 0)
137                 *new_node = 0;  
138 }
139
140 /*
141  * Minimizes expected number of BBtest by colapsing nodes
142  * it uses surface area heuristic for determining whether a node should be colapsed
143  */
144 template<class Node>
145 void pushup(Node *parent)
146 {
147         float p_area = bb_area(parent->bb, parent->bb+3);
148         Node **prev = &parent->child;
149         for(Node *child = parent->child; RayObject_isAligned(child) && child; )
150         {
151                 float c_area = bb_area(child->bb, child->bb+3) ;
152                 int nchilds = count_childs(child);
153                 float original_cost = (c_area / p_area)*nchilds + 1;
154                 float flatten_cost = nchilds;
155                 if(flatten_cost < original_cost && nchilds >= 2)
156                 {
157                         append_sibling(child, child->child);
158                         child = child->sibling;
159                         *prev = child;
160
161 //                      *prev = child->child;
162 //                      append_sibling( *prev, child->sibling );
163 //                      child = *prev;
164                         tot_pushup++;
165                 }
166                 else
167                 {
168                         *prev = child;
169                         prev = &(*prev)->sibling;
170                         child = *prev;
171                 }               
172         }
173         
174         for(Node *child = parent->child; RayObject_isAligned(child) && child; child = child->sibling)
175                 pushup(child);
176 }
177
178
179
180 /*
181  * Pushdown
182  *      makes sure no child fits inside any of its sibling
183  */
184 template<class Node>
185 void pushdown(Node *parent)
186 {
187         Node **s_child = &parent->child;
188         Node * child = parent->child;
189         
190         while(child && RayObject_isAligned(child))
191         {
192                 Node *next = child->sibling;
193                 Node **next_s_child = &child->sibling;
194                 
195                 //assert(bb_fits_inside(parent->bb, parent->bb+3, child->bb, child->bb+3));
196                 
197                 for(Node *i = parent->child; RayObject_isAligned(i) && i; i = i->sibling)
198                 if(child != i && bb_fits_inside(i->bb, i->bb+3, child->bb, child->bb+3) && RayObject_isAligned(i->child))
199                 {
200 //                      todo optimize (should the one with the smallest area?)
201 //                      float ia = bb_area(i->bb, i->bb+3)
202 //                      if(child->i)
203                         *s_child = child->sibling;
204                         child->sibling = i->child;
205                         i->child = child;
206                         next_s_child = s_child;
207                         
208                         tot_pushdown++;
209                         break;
210                 }
211                 child = next;
212                 s_child = next_s_child;
213         }
214         
215         for(Node *i = parent->child; RayObject_isAligned(i) && i; i = i->sibling)
216                 pushdown( i );  
217 }
218
219
220 /*
221  * BVH refit
222  * reajust nodes BB (useful if nodes childs where modified)
223  */
224 template<class Node>
225 float bvh_refit(Node *node)
226 {
227         if(is_leaf(node)) return 0;     
228         if(is_leaf(node->child)) return 0;
229         
230         float total = 0;
231         
232         for(Node *child = node->child; child; child = child->sibling)
233                 total += bvh_refit(child);
234                 
235         float old_area = bb_area(node->bb, node->bb+3);
236         INIT_MINMAX(node->bb, node->bb+3);
237         for(Node *child = node->child; child; child = child->sibling)
238         {
239                 DO_MIN(child->bb, node->bb);
240                 DO_MAX(child->bb+3, node->bb+3);
241         }
242         total += old_area - bb_area(node->bb, node->bb+3);
243         return total;
244 }