diff options
author | Lukas Stockner <lukas.stockner@freenet.de> | 2016-01-10 02:11:34 +0300 |
---|---|---|
committer | Lukas Stockner <lukas.stockner@freenet.de> | 2016-01-10 02:13:53 +0300 |
commit | 6995b4d8d96a14ea574f85658b73504fa0d8070a (patch) | |
tree | c0edd6359c7a29aaf29c32515f4aa4b9bc808798 /intern/cycles/render/tile.cpp | |
parent | ec20c4b558cc569e8a9d44923a2303fbc7d13523 (diff) |
Cycles: Adding Hilbert Spiral as a tile order for rendering
This patch adds the "Hilbert Spiral", a custom-designed continuous space-filling curve, as a tile order for rendering in Cycles.
It essentially works by dividing the tiles into tile blocks which are processed in a spiral outwards from the center. Inside each
block, the tiles are processed in a regular Hilbert curve pattern. By rotating that pattern according to the spiral direction,
a continuous curve is obtained, which helps with cache coherency and therefore rendering speed.
The curve is a compromise between the faster-rendering Bottom-to-Top etc. orders and the Center order, which is a bit slower,
but starts with the more important areas. The Hilbert Spiral also starts in the center (unless huge tiles are used) and is still
marginally slower than Bottom-to-Top, but noticeably faster than Center.
Reviewers: sergey, #cycles, dingto
Reviewed By: #cycles, dingto
Subscribers: iscream, gregzaal, sergey, mib2berlin
Differential Revision: https://developer.blender.org/D1166
Diffstat (limited to 'intern/cycles/render/tile.cpp')
-rw-r--r-- | intern/cycles/render/tile.cpp | 119 |
1 files changed, 119 insertions, 0 deletions
diff --git a/intern/cycles/render/tile.cpp b/intern/cycles/render/tile.cpp index 37b9647f84a..3fb60735b65 100644 --- a/intern/cycles/render/tile.cpp +++ b/intern/cycles/render/tile.cpp @@ -58,6 +58,31 @@ protected: int2 center_; }; +inline int2 hilbert_index_to_pos(int n, int d) +{ + int2 r, xy = make_int2(0, 0); + for(int s = 1; s < n; s *= 2) { + r.x = (d >> 1) & 1; + r.y = (d ^ r.x) & 1; + if(!r.y) { + if(r.x) { + xy = make_int2(s-1, s-1) - xy; + } + swap(xy.x, xy.y); + } + xy += r*make_int2(s, s); + d >>= 2; + } + return xy; +} + +enum SpiralDirection { + DIRECTION_UP, + DIRECTION_LEFT, + DIRECTION_DOWN, + DIRECTION_RIGHT, +}; + } /* namespace */ TileManager::TileManager(bool progressive_, int num_samples_, int2 tile_size_, int start_resolution_, @@ -132,6 +157,100 @@ int TileManager::gen_tiles(bool sliced) state.tiles.resize(num); vector<list<Tile> >::iterator tile_list = state.tiles.begin(); + if(tile_order == TILE_HILBERT_SPIRAL) { + assert(!sliced); + + /* Size of blocks in tiles, must be a power of 2 */ + const int hilbert_size = (max(tile_size.x, tile_size.y) <= 12)? 8: 4; + + int tile_w = (tile_size.x >= image_w)? 1: (image_w + tile_size.x - 1)/tile_size.x; + int tile_h = (tile_size.y >= image_h)? 1: (image_h + tile_size.y - 1)/tile_size.y; + int tiles_per_device = (tile_w * tile_h + num - 1) / num; + int cur_device = 0, cur_tiles = 0; + + int2 block_size = tile_size * make_int2(hilbert_size, hilbert_size); + /* Number of blocks to fill the image */ + int blocks_x = (block_size.x >= image_w)? 1: (image_w + block_size.x - 1)/block_size.x; + int blocks_y = (block_size.y >= image_h)? 1: (image_h + block_size.y - 1)/block_size.y; + int n = max(blocks_x, blocks_y) | 0x1; /* Side length of the spiral (must be odd) */ + /* Offset of spiral (to keep it centered) */ + int2 offset = make_int2((image_w - n*block_size.x)/2, (image_h - n*block_size.y)/2); + offset = (offset / tile_size) * tile_size; /* Round to tile border. */ + + int2 block = make_int2(0, 0); /* Current block */ + SpiralDirection prev_dir = DIRECTION_UP, dir = DIRECTION_UP; + for(int i = 0;;) { + /* Generate the tiles in the current block. */ + for(int hilbert_index = 0; hilbert_index < hilbert_size*hilbert_size; hilbert_index++) { + int2 tile, hilbert_pos = hilbert_index_to_pos(hilbert_size, hilbert_index); + /* Rotate block according to spiral direction. */ + if(prev_dir == DIRECTION_UP && dir == DIRECTION_UP) { + tile = make_int2(hilbert_pos.y, hilbert_pos.x); + } + else if(dir == DIRECTION_LEFT || prev_dir == DIRECTION_LEFT) { + tile = hilbert_pos; + } + else if(dir == DIRECTION_DOWN) { + tile = make_int2(hilbert_size-1-hilbert_pos.y, hilbert_size-1-hilbert_pos.x); + } + else { + tile = make_int2(hilbert_size-1-hilbert_pos.x, hilbert_size-1-hilbert_pos.y); + } + + int2 pos = block*block_size + tile*tile_size + offset; + /* Only add tiles which are in the image (tiles outside of the image can be generated since the spiral is always square). */ + if(pos.x >= 0 && pos.y >= 0 && pos.x < image_w && pos.y < image_h) { + int w = min(tile_size.x, image_w - pos.x); + int h = min(tile_size.y, image_h - pos.y); + tile_list->push_front(Tile(tile_index, pos.x, pos.y, w, h, cur_device)); + cur_tiles++; + tile_index++; + + if(cur_tiles == tiles_per_device) { + tile_list++; + cur_tiles = 0; + cur_device++; + } + } + } + + /* Stop as soon as the spiral has reached the center block. */ + if(block.x == (n-1)/2 && block.y == (n-1)/2) + break; + + /* Advance to next block. */ + prev_dir = dir; + switch(dir) { + case DIRECTION_UP: + block.y++; + if(block.y == (n-i-1)) { + dir = DIRECTION_LEFT; + } + break; + case DIRECTION_LEFT: + block.x++; + if(block.x == (n-i-1)) { + dir = DIRECTION_DOWN; + } + break; + case DIRECTION_DOWN: + block.y--; + if(block.y == i) { + dir = DIRECTION_RIGHT; + } + break; + case DIRECTION_RIGHT: + block.x--; + if(block.x == i+1) { + dir = DIRECTION_UP; + i++; + } + break; + } + } + return tile_index; + } + for(int slice = 0; slice < slice_num; slice++) { int slice_y = (image_h/slice_num)*slice; int slice_h = (slice == slice_num-1)? image_h - slice*(image_h/slice_num): image_h/slice_num; |