Cycles: Adding Hilbert Spiral as a tile order for rendering
authorLukas Stockner <lukas.stockner@freenet.de>
Sat, 9 Jan 2016 23:11:34 +0000 (00:11 +0100)
committerLukas Stockner <lukas.stockner@freenet.de>
Sat, 9 Jan 2016 23:13:53 +0000 (00:13 +0100)
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

intern/cycles/blender/addon/properties.py
intern/cycles/render/tile.cpp
intern/cycles/render/tile.h
intern/cycles/util/util_math.h

index f48bc93cabf1b0955c805cdd4d15250a08ab077e..a64a033591a2a4ce520970af5aed6e7fa529e80a 100644 (file)
@@ -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 = (
index 37b9647f84a0d00ad6abab4d87de3f60cd9825fa..3fb60735b65a8fde0cd0cf45281dc84d0f142039 100644 (file)
@@ -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;
index 09e1b25dda73bf43c5b1e46c46438a9f41675cf3..700e00c9e0ad3ef0daa4bd0ee0444ac46f4347fe 100644 (file)
@@ -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 */
index 4a676d0d7b53b4a257e5390d455cacf10d6bd08a..f3fd1b31e31bba25e70a4b5b671d51803eb14c6d 100644 (file)
@@ -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__