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