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

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__