Commit: 6995b4d8d96a14ea574f85658b73504fa0d8070a Author: Lukas Stockner Date: Sun Jan 10 00:11:34 2016 +0100 Branches: master https://developer.blender.org/rB6995b4d8d96a14ea574f85658b73504fa0d8070a
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 =================================================================== M intern/cycles/blender/addon/properties.py M intern/cycles/render/tile.cpp M intern/cycles/render/tile.h M intern/cycles/util/util_math.h =================================================================== diff --git a/intern/cycles/blender/addon/properties.py b/intern/cycles/blender/addon/properties.py index f48bc93..a64a033 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 37b9647..3fb6073 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 09e1b25..700e00c 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 4a676d0..f3fd1b3 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__ _______________________________________________ Bf-blender-cvs mailing list Bf-blender-cvs@blender.org http://lists.blender.org/mailman/listinfo/bf-blender-cvs
