[Bf-blender-cvs] [6995b4d] master: Cycles: Adding Hilbert Spiral as a tile order for rendering
Lukas Stockner
noreply at git.blender.org
Sun Jan 10 00:16:31 CET 2016
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__
More information about the Bf-blender-cvs
mailing list