ClangFormat: apply to source, most of intern
[blender.git] / intern / cycles / render / tile.cpp
1 /*
2  * Copyright 2011-2013 Blender Foundation
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  * http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16
17 #include "render/tile.h"
18
19 #include "util/util_algorithm.h"
20 #include "util/util_foreach.h"
21 #include "util/util_types.h"
22
23 CCL_NAMESPACE_BEGIN
24
25 namespace {
26
27 class TileComparator {
28  public:
29   TileComparator(TileOrder order_, int2 center_, Tile *tiles_)
30       : order(order_), center(center_), tiles(tiles_)
31   {
32   }
33
34   bool operator()(int a, int b)
35   {
36     switch (order) {
37       case TILE_CENTER: {
38         float2 dist_a = make_float2(center.x - (tiles[a].x + tiles[a].w / 2),
39                                     center.y - (tiles[a].y + tiles[a].h / 2));
40         float2 dist_b = make_float2(center.x - (tiles[b].x + tiles[b].w / 2),
41                                     center.y - (tiles[b].y + tiles[b].h / 2));
42         return dot(dist_a, dist_a) < dot(dist_b, dist_b);
43       }
44       case TILE_LEFT_TO_RIGHT:
45         return (tiles[a].x == tiles[b].x) ? (tiles[a].y < tiles[b].y) : (tiles[a].x < tiles[b].x);
46       case TILE_RIGHT_TO_LEFT:
47         return (tiles[a].x == tiles[b].x) ? (tiles[a].y < tiles[b].y) : (tiles[a].x > tiles[b].x);
48       case TILE_TOP_TO_BOTTOM:
49         return (tiles[a].y == tiles[b].y) ? (tiles[a].x < tiles[b].x) : (tiles[a].y > tiles[b].y);
50       case TILE_BOTTOM_TO_TOP:
51       default:
52         return (tiles[a].y == tiles[b].y) ? (tiles[a].x < tiles[b].x) : (tiles[a].y < tiles[b].y);
53     }
54   }
55
56  protected:
57   TileOrder order;
58   int2 center;
59   Tile *tiles;
60 };
61
62 inline int2 hilbert_index_to_pos(int n, int d)
63 {
64   int2 r, xy = make_int2(0, 0);
65   for (int s = 1; s < n; s *= 2) {
66     r.x = (d >> 1) & 1;
67     r.y = (d ^ r.x) & 1;
68     if (!r.y) {
69       if (r.x) {
70         xy = make_int2(s - 1, s - 1) - xy;
71       }
72       swap(xy.x, xy.y);
73     }
74     xy += r * make_int2(s, s);
75     d >>= 2;
76   }
77   return xy;
78 }
79
80 enum SpiralDirection {
81   DIRECTION_UP,
82   DIRECTION_LEFT,
83   DIRECTION_DOWN,
84   DIRECTION_RIGHT,
85 };
86
87 } /* namespace */
88
89 TileManager::TileManager(bool progressive_,
90                          int num_samples_,
91                          int2 tile_size_,
92                          int start_resolution_,
93                          bool preserve_tile_device_,
94                          bool background_,
95                          TileOrder tile_order_,
96                          int num_devices_,
97                          int pixel_size_)
98 {
99   progressive = progressive_;
100   tile_size = tile_size_;
101   tile_order = tile_order_;
102   start_resolution = start_resolution_;
103   pixel_size = pixel_size_;
104   num_samples = num_samples_;
105   num_devices = num_devices_;
106   preserve_tile_device = preserve_tile_device_;
107   background = background_;
108   schedule_denoising = false;
109
110   range_start_sample = 0;
111   range_num_samples = -1;
112
113   BufferParams buffer_params;
114   reset(buffer_params, 0);
115 }
116
117 TileManager::~TileManager()
118 {
119 }
120
121 void TileManager::device_free()
122 {
123   if (schedule_denoising || progressive) {
124     for (int i = 0; i < state.tiles.size(); i++) {
125       delete state.tiles[i].buffers;
126       state.tiles[i].buffers = NULL;
127     }
128   }
129
130   state.tiles.clear();
131 }
132
133 static int get_divider(int w, int h, int start_resolution)
134 {
135   int divider = 1;
136   if (start_resolution != INT_MAX) {
137     while (w * h > start_resolution * start_resolution) {
138       w = max(1, w / 2);
139       h = max(1, h / 2);
140
141       divider <<= 1;
142     }
143   }
144   return divider;
145 }
146
147 void TileManager::reset(BufferParams &params_, int num_samples_)
148 {
149   params = params_;
150
151   set_samples(num_samples_);
152
153   state.buffer = BufferParams();
154   state.sample = range_start_sample - 1;
155   state.num_tiles = 0;
156   state.num_samples = 0;
157   state.resolution_divider = get_divider(params.width, params.height, start_resolution);
158   state.render_tiles.clear();
159   state.denoising_tiles.clear();
160   device_free();
161 }
162
163 void TileManager::set_samples(int num_samples_)
164 {
165   num_samples = num_samples_;
166
167   /* No real progress indication is possible when using unlimited samples. */
168   if (num_samples == INT_MAX) {
169     state.total_pixel_samples = 0;
170   }
171   else {
172     uint64_t pixel_samples = 0;
173     /* While rendering in the viewport, the initial preview resolution is increased to the native resolution
174      * before the actual rendering begins. Therefore, additional pixel samples will be rendered. */
175     int divider = max(get_divider(params.width, params.height, start_resolution) / 2, pixel_size);
176     while (divider > pixel_size) {
177       int image_w = max(1, params.width / divider);
178       int image_h = max(1, params.height / divider);
179       pixel_samples += image_w * image_h;
180       divider >>= 1;
181     }
182
183     int image_w = max(1, params.width / divider);
184     int image_h = max(1, params.height / divider);
185     state.total_pixel_samples = pixel_samples +
186                                 (uint64_t)get_num_effective_samples() * image_w * image_h;
187     if (schedule_denoising) {
188       state.total_pixel_samples += params.width * params.height;
189     }
190   }
191 }
192
193 /* If sliced is false, splits image into tiles and assigns equal amount of tiles to every render device.
194  * If sliced is true, slice image into as much pieces as how many devices are rendering this image. */
195 int TileManager::gen_tiles(bool sliced)
196 {
197   int resolution = state.resolution_divider;
198   int image_w = max(1, params.width / resolution);
199   int image_h = max(1, params.height / resolution);
200   int2 center = make_int2(image_w / 2, image_h / 2);
201
202   int num_logical_devices = preserve_tile_device ? num_devices : 1;
203   int num = min(image_h, num_logical_devices);
204   int slice_num = sliced ? num : 1;
205   int tile_w = (tile_size.x >= image_w) ? 1 : divide_up(image_w, tile_size.x);
206
207   device_free();
208   state.render_tiles.clear();
209   state.denoising_tiles.clear();
210   state.render_tiles.resize(num);
211   state.denoising_tiles.resize(num);
212   state.tile_stride = tile_w;
213   vector<list<int>>::iterator tile_list;
214   tile_list = state.render_tiles.begin();
215
216   if (tile_order == TILE_HILBERT_SPIRAL) {
217     assert(!sliced);
218
219     int tile_h = (tile_size.y >= image_h) ? 1 : divide_up(image_h, tile_size.y);
220     state.tiles.resize(tile_w * tile_h);
221
222     /* Size of blocks in tiles, must be a power of 2 */
223     const int hilbert_size = (max(tile_size.x, tile_size.y) <= 12) ? 8 : 4;
224
225     int tiles_per_device = divide_up(tile_w * tile_h, num);
226     int cur_device = 0, cur_tiles = 0;
227
228     int2 block_size = tile_size * make_int2(hilbert_size, hilbert_size);
229     /* Number of blocks to fill the image */
230     int blocks_x = (block_size.x >= image_w) ? 1 : divide_up(image_w, block_size.x);
231     int blocks_y = (block_size.y >= image_h) ? 1 : divide_up(image_h, block_size.y);
232     int n = max(blocks_x, blocks_y) | 0x1; /* Side length of the spiral (must be odd) */
233     /* Offset of spiral (to keep it centered) */
234     int2 offset = make_int2((image_w - n * block_size.x) / 2, (image_h - n * block_size.y) / 2);
235     offset = (offset / tile_size) * tile_size; /* Round to tile border. */
236
237     int2 block = make_int2(0, 0); /* Current block */
238     SpiralDirection prev_dir = DIRECTION_UP, dir = DIRECTION_UP;
239     for (int i = 0;;) {
240       /* Generate the tiles in the current block. */
241       for (int hilbert_index = 0; hilbert_index < hilbert_size * hilbert_size; hilbert_index++) {
242         int2 tile, hilbert_pos = hilbert_index_to_pos(hilbert_size, hilbert_index);
243         /* Rotate block according to spiral direction. */
244         if (prev_dir == DIRECTION_UP && dir == DIRECTION_UP) {
245           tile = make_int2(hilbert_pos.y, hilbert_pos.x);
246         }
247         else if (dir == DIRECTION_LEFT || prev_dir == DIRECTION_LEFT) {
248           tile = hilbert_pos;
249         }
250         else if (dir == DIRECTION_DOWN) {
251           tile = make_int2(hilbert_size - 1 - hilbert_pos.y, hilbert_size - 1 - hilbert_pos.x);
252         }
253         else {
254           tile = make_int2(hilbert_size - 1 - hilbert_pos.x, hilbert_size - 1 - hilbert_pos.y);
255         }
256
257         int2 pos = block * block_size + tile * tile_size + offset;
258         /* Only add tiles which are in the image (tiles outside of the image can be generated since the spiral is always square). */
259         if (pos.x >= 0 && pos.y >= 0 && pos.x < image_w && pos.y < image_h) {
260           int w = min(tile_size.x, image_w - pos.x);
261           int h = min(tile_size.y, image_h - pos.y);
262           int2 ipos = pos / tile_size;
263           int idx = ipos.y * tile_w + ipos.x;
264           state.tiles[idx] = Tile(idx, pos.x, pos.y, w, h, cur_device, Tile::RENDER);
265           tile_list->push_front(idx);
266           cur_tiles++;
267
268           if (cur_tiles == tiles_per_device) {
269             tile_list++;
270             cur_tiles = 0;
271             cur_device++;
272           }
273         }
274       }
275
276       /* Stop as soon as the spiral has reached the center block. */
277       if (block.x == (n - 1) / 2 && block.y == (n - 1) / 2)
278         break;
279
280       /* Advance to next block. */
281       prev_dir = dir;
282       switch (dir) {
283         case DIRECTION_UP:
284           block.y++;
285           if (block.y == (n - i - 1)) {
286             dir = DIRECTION_LEFT;
287           }
288           break;
289         case DIRECTION_LEFT:
290           block.x++;
291           if (block.x == (n - i - 1)) {
292             dir = DIRECTION_DOWN;
293           }
294           break;
295         case DIRECTION_DOWN:
296           block.y--;
297           if (block.y == i) {
298             dir = DIRECTION_RIGHT;
299           }
300           break;
301         case DIRECTION_RIGHT:
302           block.x--;
303           if (block.x == i + 1) {
304             dir = DIRECTION_UP;
305             i++;
306           }
307           break;
308       }
309     }
310     return tile_w * tile_h;
311   }
312
313   int idx = 0;
314   for (int slice = 0; slice < slice_num; slice++) {
315     int slice_y = (image_h / slice_num) * slice;
316     int slice_h = (slice == slice_num - 1) ? image_h - slice * (image_h / slice_num) :
317                                              image_h / slice_num;
318
319     int tile_h = (tile_size.y >= slice_h) ? 1 : divide_up(slice_h, tile_size.y);
320
321     int tiles_per_device = divide_up(tile_w * tile_h, num);
322     int cur_device = 0, cur_tiles = 0;
323
324     for (int tile_y = 0; tile_y < tile_h; tile_y++) {
325       for (int tile_x = 0; tile_x < tile_w; tile_x++, idx++) {
326         int x = tile_x * tile_size.x;
327         int y = tile_y * tile_size.y;
328         int w = (tile_x == tile_w - 1) ? image_w - x : tile_size.x;
329         int h = (tile_y == tile_h - 1) ? slice_h - y : tile_size.y;
330
331         state.tiles.push_back(
332             Tile(idx, x, y + slice_y, w, h, sliced ? slice : cur_device, Tile::RENDER));
333         tile_list->push_back(idx);
334
335         if (!sliced) {
336           cur_tiles++;
337
338           if (cur_tiles == tiles_per_device) {
339             /* Tiles are already generated in Bottom-to-Top order, so no sort is necessary in that case. */
340             if (tile_order != TILE_BOTTOM_TO_TOP) {
341               tile_list->sort(TileComparator(tile_order, center, &state.tiles[0]));
342             }
343             tile_list++;
344             cur_tiles = 0;
345             cur_device++;
346           }
347         }
348       }
349     }
350     if (sliced) {
351       tile_list++;
352     }
353   }
354
355   return idx;
356 }
357
358 void TileManager::gen_render_tiles()
359 {
360   /* Regenerate just the render tiles for progressive render. */
361   foreach (Tile &tile, state.tiles) {
362     state.render_tiles[tile.device].push_back(tile.index);
363   }
364 }
365
366 void TileManager::set_tiles()
367 {
368   int resolution = state.resolution_divider;
369   int image_w = max(1, params.width / resolution);
370   int image_h = max(1, params.height / resolution);
371
372   state.num_tiles = gen_tiles(!background);
373
374   state.buffer.width = image_w;
375   state.buffer.height = image_h;
376
377   state.buffer.full_x = params.full_x / resolution;
378   state.buffer.full_y = params.full_y / resolution;
379   state.buffer.full_width = max(1, params.full_width / resolution);
380   state.buffer.full_height = max(1, params.full_height / resolution);
381 }
382
383 int TileManager::get_neighbor_index(int index, int neighbor)
384 {
385   static const int dx[] = {-1, 0, 1, -1, 1, -1, 0, 1, 0}, dy[] = {-1, -1, -1, 0, 0, 1, 1, 1, 0};
386
387   int resolution = state.resolution_divider;
388   int image_w = max(1, params.width / resolution);
389   int image_h = max(1, params.height / resolution);
390   int tile_w = (tile_size.x >= image_w) ? 1 : divide_up(image_w, tile_size.x);
391   int tile_h = (tile_size.y >= image_h) ? 1 : divide_up(image_h, tile_size.y);
392
393   int nx = state.tiles[index].x / tile_size.x + dx[neighbor],
394       ny = state.tiles[index].y / tile_size.y + dy[neighbor];
395   if (nx < 0 || ny < 0 || nx >= tile_w || ny >= tile_h)
396     return -1;
397
398   return ny * state.tile_stride + nx;
399 }
400
401 /* Checks whether all neighbors of a tile (as well as the tile itself) are at least at state min_state. */
402 bool TileManager::check_neighbor_state(int index, Tile::State min_state)
403 {
404   if (index < 0 || state.tiles[index].state < min_state) {
405     return false;
406   }
407   for (int neighbor = 0; neighbor < 9; neighbor++) {
408     int nindex = get_neighbor_index(index, neighbor);
409     /* Out-of-bounds tiles don't matter. */
410     if (nindex >= 0 && state.tiles[nindex].state < min_state) {
411       return false;
412     }
413   }
414
415   return true;
416 }
417
418 /* Returns whether the tile should be written (and freed if no denoising is used) instead of updating. */
419 bool TileManager::finish_tile(int index, bool &delete_tile)
420 {
421   delete_tile = false;
422
423   if (progressive) {
424     return true;
425   }
426
427   switch (state.tiles[index].state) {
428     case Tile::RENDER: {
429       if (!schedule_denoising) {
430         state.tiles[index].state = Tile::DONE;
431         delete_tile = true;
432         return true;
433       }
434       state.tiles[index].state = Tile::RENDERED;
435       /* For each neighbor and the tile itself, check whether all of its neighbors have been rendered. If yes, it can be denoised. */
436       for (int neighbor = 0; neighbor < 9; neighbor++) {
437         int nindex = get_neighbor_index(index, neighbor);
438         if (check_neighbor_state(nindex, Tile::RENDERED)) {
439           state.tiles[nindex].state = Tile::DENOISE;
440           state.denoising_tiles[state.tiles[nindex].device].push_back(nindex);
441         }
442       }
443       return false;
444     }
445     case Tile::DENOISE: {
446       state.tiles[index].state = Tile::DENOISED;
447       /* For each neighbor and the tile itself, check whether all of its neighbors have been denoised. If yes, it can be freed. */
448       for (int neighbor = 0; neighbor < 9; neighbor++) {
449         int nindex = get_neighbor_index(index, neighbor);
450         if (check_neighbor_state(nindex, Tile::DENOISED)) {
451           state.tiles[nindex].state = Tile::DONE;
452           /* It can happen that the tile just finished denoising and already can be freed here.
453            * However, in that case it still has to be written before deleting, so we can't delete it yet. */
454           if (neighbor == 8) {
455             delete_tile = true;
456           }
457           else {
458             delete state.tiles[nindex].buffers;
459             state.tiles[nindex].buffers = NULL;
460           }
461         }
462       }
463       return true;
464     }
465     default:
466       assert(false);
467       return true;
468   }
469 }
470
471 bool TileManager::next_tile(Tile *&tile, int device)
472 {
473   int logical_device = preserve_tile_device ? device : 0;
474
475   if (logical_device >= state.render_tiles.size())
476     return false;
477
478   if (!state.denoising_tiles[logical_device].empty()) {
479     int idx = state.denoising_tiles[logical_device].front();
480     state.denoising_tiles[logical_device].pop_front();
481     tile = &state.tiles[idx];
482     return true;
483   }
484
485   if (state.render_tiles[logical_device].empty())
486     return false;
487
488   int idx = state.render_tiles[logical_device].front();
489   state.render_tiles[logical_device].pop_front();
490   tile = &state.tiles[idx];
491   return true;
492 }
493
494 bool TileManager::done()
495 {
496   int end_sample = (range_num_samples == -1) ? num_samples :
497                                                range_start_sample + range_num_samples;
498   return (state.resolution_divider == pixel_size) &&
499          (state.sample + state.num_samples >= end_sample);
500 }
501
502 bool TileManager::next()
503 {
504   if (done())
505     return false;
506
507   if (progressive && state.resolution_divider > pixel_size) {
508     state.sample = 0;
509     state.resolution_divider = max(state.resolution_divider / 2, pixel_size);
510     state.num_samples = 1;
511     set_tiles();
512   }
513   else {
514     state.sample++;
515
516     if (progressive)
517       state.num_samples = 1;
518     else if (range_num_samples == -1)
519       state.num_samples = num_samples;
520     else
521       state.num_samples = range_num_samples;
522
523     state.resolution_divider = pixel_size;
524
525     if (state.sample == range_start_sample) {
526       set_tiles();
527     }
528     else {
529       gen_render_tiles();
530     }
531   }
532
533   return true;
534 }
535
536 int TileManager::get_num_effective_samples()
537 {
538   return (range_num_samples == -1) ? num_samples : range_num_samples;
539 }
540
541 CCL_NAMESPACE_END