Fix various warnings with clang build, and adjust cmake clang warnings flags
[blender.git] / source / blender / render / intern / raytrace / reorganize.h
1 /*
2  * ***** BEGIN GPL LICENSE BLOCK *****
3  *
4  * This program is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU General Public License
6  * as published by the Free Software Foundation; either version 2
7  * of the License, or (at your option) any later version. 
8  *
9  * This program is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program; if not, write to the Free Software Foundation,
16  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
17  *
18  * The Original Code is Copyright (C) 2009 Blender Foundation.
19  * All rights reserved.
20  *
21  * The Original Code is: all of this file.
22  *
23  * Contributor(s): AndrĂ© Pinto.
24  *
25  * ***** END GPL LICENSE BLOCK *****
26  */
27
28 /** \file blender/render/intern/raytrace/reorganize.h
29  *  \ingroup render
30  */
31
32
33 #include <float.h>
34 #include <math.h>
35 #include <stdio.h>
36
37 #include <algorithm>
38 #include <queue>
39 #include <vector>
40
41 #include "BKE_global.h"
42
43 #ifdef _WIN32
44 #  ifdef INFINITY
45 #    undef INFINITY
46 #  endif
47 #  define INFINITY FLT_MAX // in mingw math.h: (1.0F/0.0F). This generates compile error, though.
48 #endif
49
50 extern int tot_pushup;
51 extern int tot_pushdown;
52
53 #if !defined(INFINITY) && defined(HUGE_VAL)
54 #define INFINITY HUGE_VAL
55 #endif
56
57 template<class Node>
58 bool node_fits_inside(Node *a, Node *b)
59 {
60         return bb_fits_inside(b->bb, b->bb + 3, a->bb, a->bb + 3);
61 }
62
63 template<class Node>
64 void reorganize_find_fittest_parent(Node *tree, Node *node, std::pair<float, Node *> &cost)
65 {
66         std::queue<Node *> q;
67         q.push(tree);
68         
69         while (!q.empty()) {
70                 Node *parent = q.front();
71                 q.pop();
72                 
73                 if (parent == node) continue;
74                 if (node_fits_inside(node, parent) && RE_rayobject_isAligned(parent->child) ) {
75                         float pcost = bb_area(parent->bb, parent->bb + 3);
76                         cost = std::min(cost, std::make_pair(pcost, parent) );
77                         for (Node *child = parent->child; child; child = child->sibling)
78                                 q.push(child);
79                 }
80         }
81 }
82
83 template<class Node>
84 void reorganize(Node *root)
85 {
86         std::queue<Node *> q;
87
88         q.push(root);
89         while (!q.empty()) {
90                 Node *node = q.front();
91                 q.pop();
92                 
93                 if (RE_rayobject_isAligned(node->child)) {
94                         for (Node **prev = &node->child; *prev; ) {
95                                 assert(RE_rayobject_isAligned(*prev));
96                                 q.push(*prev);
97
98                                 std::pair<float, Node *> best(FLT_MAX, root);
99                                 reorganize_find_fittest_parent(root, *prev, best);
100
101                                 if (best.second == node) {
102                                         //Already inside the fitnest BB
103                                         prev = &(*prev)->sibling;
104                                 }
105                                 else {
106                                         Node *tmp = *prev;
107                                         *prev = (*prev)->sibling;
108                                         
109                                         tmp->sibling =  best.second->child;
110                                         best.second->child = tmp;
111                                 }
112                         
113                         
114                         }
115                 }
116                 if (node != root) {
117                 }
118         }
119 }
120
121 /*
122  * Prunes useless nodes from trees:
123  *  erases nodes with total amount of primitives = 0
124  *  prunes nodes with only one child (except if that child is a primitive)
125  */
126 template<class Node>
127 void remove_useless(Node *node, Node **new_node)
128 {
129         if (RE_rayobject_isAligned(node->child) ) {
130
131                 for (Node **prev = &node->child; *prev; ) {
132                         Node *next = (*prev)->sibling;
133                         remove_useless(*prev, prev);
134                         if (*prev == NULL)
135                                 *prev = next;
136                         else {
137                                 (*prev)->sibling = next;
138                                 prev = &((*prev)->sibling);
139                         }
140                 }
141         }
142         if (node->child) {
143                 if (RE_rayobject_isAligned(node->child) && node->child->sibling == 0)
144                         *new_node = node->child;
145         }
146         else if (node->child == NULL) {
147                 *new_node = NULL;
148         }
149 }
150
151 /*
152  * Minimizes expected number of BBtest by colapsing nodes
153  * it uses surface area heuristic for determining whether a node should be colapsed
154  */
155 template<class Node>
156 void pushup(Node *parent)
157 {
158         if (is_leaf(parent)) return;
159         
160         float p_area = bb_area(parent->bb, parent->bb + 3);
161         Node **prev = &parent->child;
162         for (Node *child = parent->child; RE_rayobject_isAligned(child) && child; ) {
163                 const float c_area = bb_area(child->bb, child->bb + 3);
164                 const int nchilds = count_childs(child);
165                 float original_cost = ((p_area != 0.0f) ? (c_area / p_area) * nchilds : 1.0f) + 1;
166                 float flatten_cost = nchilds;
167                 if (flatten_cost < original_cost && nchilds >= 2) {
168                         append_sibling(child, child->child);
169                         child = child->sibling;
170                         *prev = child;
171
172 //                      *prev = child->child;
173 //                      append_sibling( *prev, child->sibling );
174 //                      child = *prev;
175                         tot_pushup++;
176                 }
177                 else {
178                         *prev = child;
179                         prev = &(*prev)->sibling;
180                         child = *prev;
181                 }
182         }
183         
184         for (Node *child = parent->child; RE_rayobject_isAligned(child) && child; child = child->sibling)
185                 pushup(child);
186 }
187
188 /*
189  * try to optimize number of childs to be a multiple of SSize
190  */
191 template<class Node, int SSize>
192 void pushup_simd(Node *parent)
193 {
194         if (is_leaf(parent)) return;
195         
196         int n = count_childs(parent);
197                 
198         Node **prev = &parent->child;
199         for (Node *child = parent->child; RE_rayobject_isAligned(child) && child; ) {
200                 int cn = count_childs(child);
201                 if (cn - 1 <= (SSize - (n % SSize) ) % SSize && RE_rayobject_isAligned(child->child) ) {
202                         n += (cn - 1);
203                         append_sibling(child, child->child);
204                         child = child->sibling;
205                         *prev = child;
206                 }
207                 else {
208                         *prev = child;
209                         prev = &(*prev)->sibling;
210                         child = *prev;
211                 }
212         }
213                 
214         for (Node *child = parent->child; RE_rayobject_isAligned(child) && child; child = child->sibling)
215                 pushup_simd<Node, SSize>(child);
216 }
217
218
219 /*
220  * Pushdown
221  *      makes sure no child fits inside any of its sibling
222  */
223 template<class Node>
224 void pushdown(Node *parent)
225 {
226         Node **s_child = &parent->child;
227         Node *child = parent->child;
228         
229         while (child && RE_rayobject_isAligned(child)) {
230                 Node *next = child->sibling;
231                 Node **next_s_child = &child->sibling;
232                 
233                 //assert(bb_fits_inside(parent->bb, parent->bb+3, child->bb, child->bb+3));
234                 
235                 for (Node *i = parent->child; RE_rayobject_isAligned(i) && i; i = i->sibling)
236                         if (child != i && bb_fits_inside(i->bb, i->bb + 3, child->bb, child->bb + 3) && RE_rayobject_isAligned(i->child)) {
237 //                      todo optimize (should the one with the smallest area?)
238 //                      float ia = bb_area(i->bb, i->bb+3)
239 //                      if (child->i)
240                                 *s_child = child->sibling;
241                                 child->sibling = i->child;
242                                 i->child = child;
243                                 next_s_child = s_child;
244                         
245                                 tot_pushdown++;
246                                 break;
247                         }
248                 child = next;
249                 s_child = next_s_child;
250         }
251         
252         for (Node *i = parent->child; RE_rayobject_isAligned(i) && i; i = i->sibling) {
253                 pushdown(i);
254         }
255 }
256
257
258 /*
259  * BVH refit
260  * readjust nodes BB (useful if nodes childs where modified)
261  */
262 template<class Node>
263 float bvh_refit(Node *node)
264 {
265         if (is_leaf(node)) return 0;
266         if (is_leaf(node->child)) return 0;
267         
268         float total = 0;
269         
270         for (Node *child = node->child; child; child = child->sibling)
271                 total += bvh_refit(child);
272                 
273         float old_area = bb_area(node->bb, node->bb + 3);
274         INIT_MINMAX(node->bb, node->bb + 3);
275         for (Node *child = node->child; child; child = child->sibling) {
276                 DO_MIN(child->bb, node->bb);
277                 DO_MAX(child->bb + 3, node->bb + 3);
278         }
279         total += old_area - bb_area(node->bb, node->bb + 3);
280         return total;
281 }
282
283
284 /*
285  * this finds the best way to packing a tree according to a given test cost function
286  * with the purpose to reduce the expected cost (eg.: number of BB tests).
287  */
288 #include <vector>
289 #define MAX_CUT_SIZE         4               /* svbvh assumes max 4 children! */
290 #define MAX_OPTIMIZE_CHILDS  MAX_CUT_SIZE
291
292 struct OVBVHNode {
293         float bb[6];
294
295         OVBVHNode *child;
296         OVBVHNode *sibling;
297         
298         /*
299          * Returns min cost to represent the subtree starting at the given node,
300          * allowing it to have a given cutsize
301          */
302         float cut_cost[MAX_CUT_SIZE];
303         float get_cost(int cutsize)
304         {
305                 return cut_cost[cutsize - 1];
306         }
307         
308         /*
309          * This saves the cut size of this child, when parent is reaching
310          * its minimum cut with the given cut size
311          */
312         int cut_size[MAX_CUT_SIZE];
313         int get_cut_size(int parent_cut_size)
314         {
315                 return cut_size[parent_cut_size - 1];
316         }
317         
318         /*
319          * Reorganize the node based on calculated cut costs
320          */
321         int best_cutsize;
322         void set_cut(int cutsize, OVBVHNode ***cut)
323         {
324                 if (cutsize == 1) {
325                         **cut = this;
326                         *cut = &(**cut)->sibling;
327                 }
328                 else {
329                         if (cutsize > MAX_CUT_SIZE) {
330                                 for (OVBVHNode *child = this->child; child && RE_rayobject_isAligned(child); child = child->sibling) {
331                                         child->set_cut(1, cut);
332                                         cutsize--;
333                                 }
334                                 assert(cutsize == 0);
335                         }
336                         else {
337                                 for (OVBVHNode *child = this->child; child && RE_rayobject_isAligned(child); child = child->sibling) {
338                                         child->set_cut(child->get_cut_size(cutsize), cut);
339                                 }
340                         }
341                 }
342         }
343
344         void optimize()
345         {
346                 if (RE_rayobject_isAligned(this->child)) {
347                         //Calc new childs
348                         {
349                                 OVBVHNode **cut = &(this->child);
350                                 set_cut(best_cutsize, &cut);
351                                 *cut = NULL;
352                         }
353
354                         //Optimize new childs
355                         for (OVBVHNode *child = this->child; child && RE_rayobject_isAligned(child); child = child->sibling)
356                                 child->optimize();
357                 }
358         }
359 };
360
361 /*
362  * Calculates an optimal SIMD packing
363  *
364  */
365 template<class Node, class TestCost>
366 struct VBVH_optimalPackSIMD {
367         TestCost testcost;
368         
369         VBVH_optimalPackSIMD(TestCost testcost)
370         {
371                 this->testcost = testcost;
372         }
373         
374         /*
375          * calc best cut on a node
376          */
377         struct calc_best {
378                 Node *child[MAX_OPTIMIZE_CHILDS];
379                 float child_hit_prob[MAX_OPTIMIZE_CHILDS];
380                 
381                 calc_best(Node *node)
382                 {
383                         int nchilds = 0;
384                         //Fetch childs and needed data
385                         {
386                                 float parent_area = bb_area(node->bb, node->bb + 3);
387                                 for (Node *child = node->child; child && RE_rayobject_isAligned(child); child = child->sibling) {
388                                         this->child[nchilds] = child;
389                                         this->child_hit_prob[nchilds] = (parent_area != 0.0f) ? bb_area(child->bb, child->bb + 3) / parent_area : 1.0f;
390                                         nchilds++;
391                                 }
392
393                                 assert(nchilds >= 2 && nchilds <= MAX_OPTIMIZE_CHILDS);
394                         }
395                         
396                         
397                         //Build DP table to find minimum cost to represent this node with a given cutsize
398                         int     bt[MAX_OPTIMIZE_CHILDS + 1][MAX_CUT_SIZE + 1];     //backtrace table
399                         float cost[MAX_OPTIMIZE_CHILDS + 1][MAX_CUT_SIZE + 1]; //cost table (can be reduced to float[2][MAX_CUT_COST])
400                         
401                         for (int i = 0; i <= nchilds; i++) {
402                                 for (int j = 0; j <= MAX_CUT_SIZE; j++) {
403                                         cost[i][j] = INFINITY;
404                                 }
405                         }
406
407                         cost[0][0] = 0;
408                         
409                         for (int i = 1; i <= nchilds; i++) {
410                                 for (int size = i - 1; size /*+(nchilds-i)*/ <= MAX_CUT_SIZE; size++) {
411                                         for (int cut = 1; cut + size /*+(nchilds-i)*/ <= MAX_CUT_SIZE; cut++) {
412                                                 float new_cost = cost[i - 1][size] + child_hit_prob[i - 1] * child[i - 1]->get_cost(cut);
413                                                 if (new_cost < cost[i][size + cut]) {
414                                                         cost[i][size + cut] = new_cost;
415                                                         bt[i][size + cut] = cut;
416                                                 }
417                                         }
418                                 }
419                         }
420                         
421                         /* Save the ways to archive the minimum cost with a given cutsize */
422                         for (int i = nchilds; i <= MAX_CUT_SIZE; i++) {
423                                 node->cut_cost[i - 1] = cost[nchilds][i];
424                                 if (cost[nchilds][i] < INFINITY) {
425                                         int current_size = i;
426                                         for (int j = nchilds; j > 0; j--) {
427                                                 child[j - 1]->cut_size[i - 1] = bt[j][current_size];
428                                                 current_size -= bt[j][current_size];
429                                         }
430                                 }
431                         }
432                 }
433         };
434         
435         void calc_costs(Node *node)
436         {
437                 
438                 if (RE_rayobject_isAligned(node->child) ) {
439                         int nchilds = 0;
440                         for (Node *child = node->child; child && RE_rayobject_isAligned(child); child = child->sibling) {
441                                 calc_costs(child);
442                                 nchilds++;
443                         }
444
445                         for (int i = 0; i < MAX_CUT_SIZE; i++)
446                                 node->cut_cost[i] = INFINITY;
447
448                         //We are not allowed to look on nodes with with so many childs
449                         if (nchilds > MAX_CUT_SIZE) {
450                                 float cost = 0;
451
452                                 float parent_area = bb_area(node->bb, node->bb + 3);
453                                 for (Node *child = node->child; child && RE_rayobject_isAligned(child); child = child->sibling) {
454                                         cost += ((parent_area != 0.0f) ? (bb_area(child->bb, child->bb + 3) / parent_area) : 1.0f) * child->get_cost(1);
455                                 }
456                                 
457                                 cost += testcost(nchilds);
458                                 node->cut_cost[0] = cost;
459                                 node->best_cutsize = nchilds;
460                         }
461                         else {
462                                 calc_best calc(node);
463                 
464                                 //calc expected cost if we optimaly pack this node
465                                 for (int cutsize = nchilds; cutsize <= MAX_CUT_SIZE; cutsize++) {
466                                         float m = node->get_cost(cutsize) + testcost(cutsize);
467                                         if (m < node->cut_cost[0]) {
468                                                 node->cut_cost[0] = m;
469                                                 node->best_cutsize = cutsize;
470                                         }
471                                 }
472                         }
473                         assert(node->cut_cost[0] != INFINITY);
474                 }
475                 else {
476                         node->cut_cost[0] = 1.0f;
477                         for (int i = 1; i < MAX_CUT_SIZE; i++)
478                                 node->cut_cost[i] = INFINITY;
479                 }
480         }
481
482         Node *transform(Node *node)
483         {
484                 if (RE_rayobject_isAligned(node->child)) {
485                         static int num = 0;
486                         bool first = false;
487                         if (num == 0) { num++; first = true; }
488                         
489                         calc_costs(node);
490                         if ((G.debug & G_DEBUG) && first) printf("expected cost = %f (%d)\n", node->cut_cost[0], node->best_cutsize);
491                         node->optimize();
492                 }
493                 return node;
494         }
495 };