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 | |
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')
-rw-r--r-- | intern/cycles/blender/addon/properties.py | 1 | ||||
-rw-r--r-- | intern/cycles/render/tile.cpp | 119 | ||||
-rw-r--r-- | intern/cycles/render/tile.h | 3 | ||||
-rw-r--r-- | intern/cycles/util/util_math.h | 31 |
4 files changed, 153 insertions, 1 deletions
diff --git a/intern/cycles/blender/addon/properties.py b/intern/cycles/blender/addon/properties.py index f48bc93cabf..a64a033591a 100644 --- a/intern/cycles/blender/addon/properties.py +++ b/intern/cycles/blender/addon/properties.py @@ -92,6 +92,7 @@ enum_tile_order = ( ('LEFT_TO_RIGHT', "Left to Right", "Render from left to right"), ('TOP_TO_BOTTOM', "Top to Bottom", "Render from top to bottom"), ('BOTTOM_TO_TOP', "Bottom to Top", "Render from bottom to top"), + ('HILBERT_SPIRAL', "Hilbert Spiral", "Render in a Hilbert Spiral"), ) enum_use_layer_samples = ( 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; diff --git a/intern/cycles/render/tile.h b/intern/cycles/render/tile.h index 09e1b25dda7..700e00c9e0a 100644 --- a/intern/cycles/render/tile.h +++ b/intern/cycles/render/tile.h @@ -47,7 +47,8 @@ enum TileOrder { TILE_RIGHT_TO_LEFT = 1, TILE_LEFT_TO_RIGHT = 2, TILE_TOP_TO_BOTTOM = 3, - TILE_BOTTOM_TO_TOP = 4 + TILE_BOTTOM_TO_TOP = 4, + TILE_HILBERT_SPIRAL = 5, }; /* Tile Manager */ diff --git a/intern/cycles/util/util_math.h b/intern/cycles/util/util_math.h index 4a676d0d7b5..f3fd1b31e31 100644 --- a/intern/cycles/util/util_math.h +++ b/intern/cycles/util/util_math.h @@ -939,6 +939,37 @@ ccl_device_inline void print_float4(const char *label, const float4& a) #endif +/* Int2 */ + +#ifndef __KERNEL_OPENCL__ + +ccl_device_inline int2 operator+(const int2 &a, const int2 &b) +{ + return make_int2(a.x + b.x, a.y + b.y); +} + +ccl_device_inline int2 operator+=(int2 &a, const int2 &b) +{ + return a = a + b; +} + +ccl_device_inline int2 operator-(const int2 &a, const int2 &b) +{ + return make_int2(a.x - b.x, a.y - b.y); +} + +ccl_device_inline int2 operator*(const int2 &a, const int2 &b) +{ + return make_int2(a.x * b.x, a.y * b.y); +} + +ccl_device_inline int2 operator/(const int2 &a, const int2 &b) +{ + return make_int2(a.x / b.x, a.y / b.y); +} + +#endif + /* Int3 */ #ifndef __KERNEL_OPENCL__ |