Revert "Morton ordering for sparse grids."

This reverts commit a93a9fb09bcfd6211f063255ccb11cfc15e013d1.

5 files changed, 41 insertions, 68 deletions

diff --git a/intern/cycles/device/device_cpu.cpp b/intern/cycles/device/device_cpu.cpp
index 36904951df6..04578eec954 100644
--- a/intern/cycles/device/device_cpu.cpp
+++ b/intern/cycles/device/device_cpu.cpp
@@ -421,9 +421,8 @@ public:
 			info.grid_info = 0;
 			if(grid_info) {
 				info.grid_info = (uint64_t)grid_info->host_pointer;
-				info.bit_count = compute_bit_count(info.width,
-				                                   info.height,
-				                                   info.depth);
+				info.tiled_width = get_tile_res(info.width);
+				info.tiled_height = get_tile_res(info.height);
 				info.last_tile_width = info.width % TILE_SIZE;
 				info.last_tile_height = info.height % TILE_SIZE;
 			}
diff --git a/intern/cycles/kernel/kernels/cpu/kernel_cpu_image.h b/intern/cycles/kernel/kernels/cpu/kernel_cpu_image.h
index 64367b7fb84..a0d6b54245b 100644
--- a/intern/cycles/kernel/kernels/cpu/kernel_cpu_image.h
+++ b/intern/cycles/kernel/kernels/cpu/kernel_cpu_image.h
@@ -82,12 +82,12 @@ template<typename T> struct TextureInterpolator  {
 
 	static ccl_always_inline float4 read(const T *data, const int *grid_info,
 	                                     int x, int y, int z,
-	                                     int bit_count, int ltw, int lth)
+	                                     int tiw, int tih, int ltw, int lth)
 	{
 		int tix = x / TILE_SIZE, itix = x % TILE_SIZE,
 		    tiy = y / TILE_SIZE, itiy = y % TILE_SIZE,
 		    tiz = z / TILE_SIZE, itiz = z % TILE_SIZE;
-		int dense_index = compute_morton(tix, tiy, tiz, bit_count) * 2;
+		int dense_index = flatten(tix, tiy, tiz, tiw, tih) * 2;
 		int sparse_index = grid_info[dense_index];
 		int dims = grid_info[dense_index + 1];
 		if(sparse_index < 0) {
@@ -101,12 +101,12 @@ template<typename T> struct TextureInterpolator  {
 
 	static ccl_always_inline float4 read(const T *data, const int *grid_info,
 	                                     int index, int width, int height, int /*depth*/,
-	                                     int bit_count, int ltw, int lth)
+	                                     int tiw, int tih, int ltw, int lth)
 	{
 		int x = index % width;
 		int y = (index / width) % height;
 		int z = index / (width * height);
-		return read(data, grid_info, x, y, z, bit_count, ltw, lth);
+		return read(data, grid_info, x, y, z, tiw, tih, ltw, lth);
 	}
 
 	static ccl_always_inline int wrap_periodic(int x, int width)
@@ -319,7 +319,8 @@ template<typename T> struct TextureInterpolator  {
 		const int *grid_info = (const int*)info.grid_info;
 
 		if(grid_info) {
-			return read(data, grid_info, ix, iy, iz, info.bit_count,
+			return read(data, grid_info, ix, iy, iz,
+			            info.tiled_width, info.tiled_height,
 			            info.last_tile_width, info.last_tile_height);
 		}
 		return read(data[flatten(ix, iy, iz, width, height)]);
@@ -374,17 +375,18 @@ template<typename T> struct TextureInterpolator  {
 		const int *gi = (const int*)info.grid_info;
 
 		if(gi) {
-			int bc = info.bit_count;
+			int tiw = info.tiled_width;
+			int tih = info.tiled_height;
 			int ltw = info.last_tile_width;
 			int lth = info.last_tile_height;
-			r  = (1.0f - tz)*(1.0f - ty)*(1.0f - tx) * read(data, gi, ix,  iy,  iz,  bc, ltw, lth);
-			r += (1.0f - tz)*(1.0f - ty)*tx          * read(data, gi, nix, iy,  iz,  bc, ltw, lth);
-			r += (1.0f - tz)*ty*(1.0f - tx)          * read(data, gi, ix,  niy, iz,  bc, ltw, lth);
-			r += (1.0f - tz)*ty*tx                   * read(data, gi, nix, niy, iz,  bc, ltw, lth);
-			r += tz*(1.0f - ty)*(1.0f - tx)          * read(data, gi, ix,  iy,  niz, bc, ltw, lth);
-			r += tz*(1.0f - ty)*tx                   * read(data, gi, nix, iy,  niz, bc, ltw, lth);
-			r += tz*ty*(1.0f - tx)                   * read(data, gi, ix,  niy, niz, bc, ltw, lth);
-			r += tz*ty*tx                            * read(data, gi, nix, niy, niz, bc, ltw, lth);
+			r  = (1.0f - tz)*(1.0f - ty)*(1.0f - tx) * read(data, gi, ix,  iy,  iz,  tiw, tih, ltw, lth);
+			r += (1.0f - tz)*(1.0f - ty)*tx          * read(data, gi, nix, iy,  iz,  tiw, tih, ltw, lth);
+			r += (1.0f - tz)*ty*(1.0f - tx)          * read(data, gi, ix,  niy, iz,  tiw, tih, ltw, lth);
+			r += (1.0f - tz)*ty*tx                   * read(data, gi, nix, niy, iz,  tiw, tih, ltw, lth);
+			r += tz*(1.0f - ty)*(1.0f - tx)          * read(data, gi, ix,  iy,  niz, tiw, tih, ltw, lth);
+			r += tz*(1.0f - ty)*tx                   * read(data, gi, nix, iy,  niz, tiw, tih, ltw, lth);
+			r += tz*ty*(1.0f - tx)                   * read(data, gi, ix,  niy, niz, tiw, tih, ltw, lth);
+			r += tz*ty*tx                            * read(data, gi, nix, niy, niz, tiw, tih, ltw, lth);
 		}
 		else {
 			r  = (1.0f - tz)*(1.0f - ty)*(1.0f - tx) * read(data[flatten(ix,  iy,  iz,  width, height)]);
@@ -416,7 +418,8 @@ template<typename T> struct TextureInterpolator  {
 		int width = info.width;
 		int height = info.height;
 		int depth = info.depth;
-		int bc = info.bit_count;
+		int tiw = info.tiled_width;
+		int tih = info.tiled_height;
 		int ltw = info.last_tile_width;
 		int lth = info.last_tile_height;
 		int ix, iy, iz;
@@ -489,7 +492,7 @@ template<typename T> struct TextureInterpolator  {
 		 * let compiler to inline all the matrix multiplications.
 		 */
 #define DATA(x, y, z) (gi ? \
-		read(data, gi, xc[x] + yc[y] + zc[z], width, height, depth, bc, ltw, lth) : \
+		read(data, gi, xc[x] + yc[y] + zc[z], width, height, depth, tiw, tih, ltw, lth) : \
 		read(data[xc[x] + yc[y] + zc[z]]))
 #define COL_TERM(col, row) \
 		(v[col] * (u[0] * DATA(0, col, row) + \
diff --git a/intern/cycles/render/mesh_volume.cpp b/intern/cycles/render/mesh_volume.cpp
index d70d465d543..5ce8198b9d6 100644
--- a/intern/cycles/render/mesh_volume.cpp
+++ b/intern/cycles/render/mesh_volume.cpp
@@ -461,9 +461,6 @@ void MeshManager::create_volume_mesh(Scene *scene,
 	float3 cell_size = make_float3(1.0f/resolution.x,
 	                               1.0f/resolution.y,
 	                               1.0f/resolution.z);
-	const size_t bit_count = compute_bit_count(resolution.x,
-	                                           resolution.y,
-	                                           resolution.z);
 	const int3 tiled_res = make_int3(get_tile_res(resolution.x),
 	                                 get_tile_res(resolution.y),
 	                                 get_tile_res(resolution.z));
@@ -499,7 +496,9 @@ void MeshManager::create_volume_mesh(Scene *scene,
 					if(grid_info) {
 						if(!using_cuda) {
 							voxel_index = compute_index(grid_info, x, y, z,
-														bit_count,
+														tiled_res.x,
+														tiled_res.y,
+														tiled_res.z,
 														last_tile_res.x,
 														last_tile_res.y);
 						}
diff --git a/intern/cycles/util/util_sparse_grid.h b/intern/cycles/util/util_sparse_grid.h
index 81f6c6abcf5..d63cee25fda 100644
--- a/intern/cycles/util/util_sparse_grid.h
+++ b/intern/cycles/util/util_sparse_grid.h
@@ -86,34 +86,11 @@ const inline size_t get_tile_res(const size_t res)
 	return (res / TILE_SIZE) + (res % TILE_SIZE != 0);
 }
 
-/* Finds the number of bits used by the largest
- * dimension of an image. Used for Morton order. */
-const inline size_t compute_bit_count(size_t width, size_t height, size_t depth)
-{
-	size_t largest_dim = max(max(width, height), depth);
-	size_t bit_count = 0, n = 1;
-	while(largest_dim >= n) {
-		n *= 2;
-		++bit_count;
-	}
-	return bit_count;
-}
-
-const inline size_t compute_morton(size_t x, size_t y, size_t z, size_t bit_count)
-{
-	size_t morton_index = 0;
-	for (size_t i = 0 ; i < bit_count ; ++i) {
-		morton_index |= ((x >> i) & 1) << (i * 3 + 0);
-		morton_index |= ((y >> i) & 1) << (i * 3 + 1);
-		morton_index |= ((z >> i) & 1) << (i * 3 + 2);
-	}
-	return morton_index;
-}
-
 /* Do not call this function in the kernel. */
 const inline int compute_index(const int *grid_info,
                                int x, int y, int z,
-                               int bit_count, int ltw, int lth)
+                               int tiw, int tih, int tid,
+                               int ltw, int lth)
 {
 	/* Coordinates of (x, y, z)'s tile and
 	 * coordinates of (x, y, z) with origin at tile start. */
@@ -121,7 +98,7 @@ const inline int compute_index(const int *grid_info,
 	    tiy = y / TILE_SIZE, itiy = y % TILE_SIZE,
 	    tiz = z / TILE_SIZE, itiz = z % TILE_SIZE;
 	/* Get the 1D array index in the dense grid of the tile (x, y, z) is in. */
-	int dense_index = compute_morton(tix, tiy, tiz, bit_count) * 2;
+	int dense_index = compute_index(tix, tiy, tiz, tiw, tih, tid) * 2;
 	if(dense_index < 0) {
 		return -1;
 	}
@@ -178,21 +155,19 @@ int create_sparse_grid(const T *dense_grid,
 	}
 
 	const T threshold = cast_from_float<T>(isovalue);
-	/* Get the minumum number of bits needed to represent each dimension. */
-	size_t bit_count = compute_bit_count(width, height, depth);
+
 	/* Resize vectors to tiled resolution. Have to overalloc
 	 * sparse_grid because we don't know the number of
 	 * active tiles yet. */
 	sparse_grid->resize(width * height * depth);
-	/* Overalloc of grid_info for morton order. */
-	const size_t max_dim = max(max(width, height), depth);
-	grid_info->resize(max_dim * max_dim * max_dim * 2);
+	grid_info->resize(get_tile_res(width) *
+	                  get_tile_res(height) *
+	                  get_tile_res(depth) * 2);
+	int info_count = 0, voxel_count = 0;
 
-	int voxel_count = 0;
 	for(int z=0 ; z < depth ; z += TILE_SIZE) {
 		for(int y=0 ; y < height ; y += TILE_SIZE) {
 			for(int x=0 ; x < width ; x += TILE_SIZE) {
-
 				bool is_active = false;
 				int voxel = 0;
 
@@ -210,10 +185,6 @@ int create_sparse_grid(const T *dense_grid,
 					}
 				}
 
-				/* Compute tile index. */
-				size_t tile = compute_morton(x/TILE_SIZE, y/TILE_SIZE,
-				                             z/TILE_SIZE, bit_count) * 2;
-
 				/* If tile is active, store tile's offset and dimension info. */
 				if(is_active) {
 					/* Store if the tile is the last tile in the X/Y direction
@@ -221,14 +192,15 @@ int create_sparse_grid(const T *dense_grid,
 					int dimensions = 0;
 					dimensions |= ((x + TILE_SIZE > width) << ST_SHIFT_TRUNCATE_WIDTH);
 					dimensions |= ((y + TILE_SIZE > height) << ST_SHIFT_TRUNCATE_HEIGHT);
-					grid_info->at(tile) = voxel_count;
-					grid_info->at(tile + 1) = dimensions;
+					grid_info->at(info_count) = voxel_count;
+					grid_info->at(info_count + 1) = dimensions;
 					voxel_count += voxel;
 				}
 				else {
-					grid_info->at(tile) = -1;
-					grid_info->at(tile + 1) = 0;
+					grid_info->at(info_count) = -1;
+					grid_info->at(info_count + 1) = 0;
 				}
+				info_count += 2;
 			}
 		}
 	}
diff --git a/intern/cycles/util/util_texture.h b/intern/cycles/util/util_texture.h
index 1fb070c1273..7f86ccca658 100644
--- a/intern/cycles/util/util_texture.h
+++ b/intern/cycles/util/util_texture.h
@@ -85,11 +85,11 @@ typedef struct TextureInfo {
 	uint interpolation, extension;
 	/* Dimensions. */
 	uint width, height, depth;
-	/* For sparse grid index calculations: tiled dimensions, last tile's
-	 * dimensions, and bit count of the dimensions. */
-	uint tiled_width, tiled_height, last_tile_width, last_tile_height, bit_count;
+	/* Tiled dimensions for sparse grid index calculations,
+	 * and length of the last tile's dimensions. */
+	uint tiled_width, tiled_height, last_tile_width, last_tile_height;
 	/* Dummy variable to keep TextureInfo the correct size. */
-	uint dummy;
+	uint64_t dummy;
 } TextureInfo;
 
 CCL_NAMESPACE_END