Remove SparseTile; support CPU tricubic interp.

Sparse grids now use their normal types instead of a specific struct.
Also added support for tricubic interpolation of sparse grids for CPU
rendering.

4 files changed, 127 insertions, 151 deletions

diff --git a/intern/cycles/kernel/kernels/cpu/kernel_cpu_image.h b/intern/cycles/kernel/kernels/cpu/kernel_cpu_image.h
index 3435bcab70a..93aa6117f58 100644
--- a/intern/cycles/kernel/kernels/cpu/kernel_cpu_image.h
+++ b/intern/cycles/kernel/kernels/cpu/kernel_cpu_image.h
@@ -75,6 +75,21 @@ template<typename T> struct TextureInterpolator  {
 		return read(data[y * width + x]);
 	}
 
+	static ccl_always_inline float4 read(const T *data, const int *offsets,
+	                                     int x, int y, int z,
+	                                     int tiw, int tih, int tid)
+	{
+		int index = compute_index(offsets, x, y, z, tiw, tih, tid);
+		return index < 0 ? make_float4(0.0f) : read(data[index]);
+	}
+
+	static ccl_always_inline float4 read(const T *data, const int *offsets,
+	                                     int idx, int width, int height, int depth)
+	{
+		int index = compute_index(offsets, idx, width, height, depth);
+		return index < 0 ? make_float4(0.0f) : read(data[index]);
+	}
+
 	static ccl_always_inline int wrap_periodic(int x, int width)
 	{
 		x %= width;
@@ -281,18 +296,14 @@ template<typename T> struct TextureInterpolator  {
 				return make_float4(0.0f);
 		}
 
+		const T *data = (const T*)info.data;
 		const int *ofs = (const int*)info.offsets;
+
 		if(ofs) {
-			const SparseTile<T> *data = (const SparseTile<T>*)info.data;
-			return read(get_value<T>(data, ofs, ix, iy, iz,
-			                         compute_tile_resolution(width),
-			                         compute_tile_resolution(height),
-			                         compute_tile_resolution(depth)));
-		}
-		else {
-			const T *data = (const T*)info.data;
-			return read(data[compute_index(ix, iy, iz, width, height, depth)]);
+			return read(data, ofs, ix, iy, iz, get_tile_res(width),
+			            get_tile_res(height), get_tile_res(depth));
 		}
+		return read(data[compute_index(ix, iy, iz, width, height, depth)]);
 	}
 
 	static ccl_always_inline float4 interp_3d_linear(const TextureInfo& info,
@@ -340,29 +351,26 @@ template<typename T> struct TextureInterpolator  {
 		}
 
 		float4 r;
+		const T *data = (const T*)info.data;
 		const int *ofs = (const int*)info.offsets;
 
 		if(ofs) {
-			const SparseTile<T> *data = (const SparseTile<T>*)info.data;
-			int tiw = compute_tile_resolution(width);
-			int tih = compute_tile_resolution(height);
-			int tid = compute_tile_resolution(depth);
+			int tiw = get_tile_res(width), tih = get_tile_res(height), tid = get_tile_res(depth);
 			/* Initial check if either voxel is in an active tile. */
 			if(!tile_is_active(ofs, ix, iy, iz, tiw, tih, tid) &&
 			   !tile_is_active(ofs, nix, niy, niz, tiw, tih, tid)) {
 				return make_float4(0.0f);
 			}
-			r  = (1.0f - tz)*(1.0f - ty)*(1.0f - tx) * read(get_value<T>(data, ofs, ix,  iy,  iz,  tiw, tih, tid));
-			r += (1.0f - tz)*(1.0f - ty)*tx			 * read(get_value<T>(data, ofs, nix, iy,  iz,  tiw, tih, tid));
-			r += (1.0f - tz)*ty*(1.0f - tx)			 * read(get_value<T>(data, ofs, ix,  niy, iz,  tiw, tih, tid));
-			r += (1.0f - tz)*ty*tx					 * read(get_value<T>(data, ofs, nix, niy, iz,  tiw, tih, tid));
-			r += tz*(1.0f - ty)*(1.0f - tx)			 * read(get_value<T>(data, ofs, ix,  iy,  niz, tiw, tih, tid));
-			r += tz*(1.0f - ty)*tx					 * read(get_value<T>(data, ofs, nix, iy,  niz, tiw, tih, tid));
-			r += tz*ty*(1.0f - tx)					 * read(get_value<T>(data, ofs, ix,  niy, niz, tiw, tih, tid));
-			r += tz*ty*tx							 * read(get_value<T>(data, ofs, nix, niy, niz, tiw, tih, tid));
+			r  = (1.0f - tz)*(1.0f - ty)*(1.0f - tx) * read(data, ofs, ix,  iy,  iz,  tiw, tih, tid);
+			r += (1.0f - tz)*(1.0f - ty)*tx			 * read(data, ofs, nix, iy,  iz,  tiw, tih, tid);
+			r += (1.0f - tz)*ty*(1.0f - tx)			 * read(data, ofs, ix,  niy, iz,  tiw, tih, tid);
+			r += (1.0f - tz)*ty*tx					 * read(data, ofs, nix, niy, iz,  tiw, tih, tid);
+			r += tz*(1.0f - ty)*(1.0f - tx)			 * read(data, ofs, ix,  iy,  niz, tiw, tih, tid);
+			r += tz*(1.0f - ty)*tx					 * read(data, ofs, nix, iy,  niz, tiw, tih, tid);
+			r += tz*ty*(1.0f - tx)					 * read(data, ofs, ix,  niy, niz, tiw, tih, tid);
+			r += tz*ty*tx							 * read(data, ofs, nix, niy, niz, tiw, tih, tid);
 		}
 		else {
-			const T *data = (const T*)info.data;
 			r  = (1.0f - tz)*(1.0f - ty)*(1.0f - tx) * read(data[compute_index(ix,  iy,  iz,  width, height, depth)]);
 			r += (1.0f - tz)*(1.0f - ty)*tx			 * read(data[compute_index(nix, iy,  iz,  width, height, depth)]);
 			r += (1.0f - tz)*ty*(1.0f - tx)			 * read(data[compute_index(ix,  niy, iz,  width, height, depth)]);
@@ -461,7 +469,9 @@ template<typename T> struct TextureInterpolator  {
 		/* Some helper macro to keep code reasonable size,
 		 * let compiler to inline all the matrix multiplications.
 		 */
-#define DATA(x, y, z) (read(data[xc[x] + yc[y] + zc[z]]))
+#define DATA(x, y, z) (ofs ? \
+	    read(data, ofs, xc[x] + yc[y] + zc[z], width, height, depth) : \
+	    read(data[xc[x] + yc[y] + zc[z]]))
 #define COL_TERM(col, row) \
 		(v[col] * (u[0] * DATA(0, col, row) + \
 		           u[1] * DATA(1, col, row) + \
@@ -479,6 +489,7 @@ template<typename T> struct TextureInterpolator  {
 
 		/* Actual interpolation. */
 		const T *data = (const T*)info.data;
+		const int *ofs = (const int*)info.offsets;
 		return ROW_TERM(0) + ROW_TERM(1) + ROW_TERM(2) + ROW_TERM(3);
 
 #undef COL_TERM
diff --git a/intern/cycles/render/image.cpp b/intern/cycles/render/image.cpp
index c1caea34619..bef1419d178 100644
--- a/intern/cycles/render/image.cpp
+++ b/intern/cycles/render/image.cpp
@@ -730,52 +730,49 @@ void ImageManager::file_load_failed(device_vector<DeviceType> *tex_img,
 template<typename DeviceType>
 bool ImageManager::file_make_image_sparse(Device *device,
                                           Image *img,
-                                          device_vector<DeviceType> *tex_dense)
+                                          device_vector<DeviceType> *tex_img)
 {
-	device_vector<SparseTile<DeviceType>> *tex_sparse
-	        = new device_vector<SparseTile<DeviceType>>(device,
-	                                                    (img->mem_name).c_str(),
-	                                                    MEM_TEXTURE);
 	device_vector<int> *tex_offsets
 	        = new device_vector<int>(device,
 	                                 (img->mem_name + "_offsets").c_str(),
 	                                 MEM_TEXTURE);
 
-	vector<SparseTile<DeviceType>> sparse_grid;
+	vector<DeviceType> sparse_grid;
 	vector<int> offsets;
-	int active_tile_count = create_sparse_grid<DeviceType>(
-	                            tex_dense->data(),
-	                            tex_dense->data_width,
-	                            tex_dense->data_height,
-	                            tex_dense->data_depth,
-	                            &sparse_grid,
-	                            &offsets);
-
-	if(active_tile_count < 1) {
+	int voxel_count = create_sparse_grid<DeviceType>(tex_img->data(),
+	                                                 tex_img->data_width,
+	                                                 tex_img->data_height,
+	                                                 tex_img->data_depth,
+	                                                 &sparse_grid,
+	                                                 &offsets);
+
+	if(voxel_count < 1) {
 		VLOG(1) << "Could not make sparse grid for "
 		        << path_filename(img->filename) << " (" << img->mem_name << ")"
 		        << ", no active tiles";
-		delete tex_sparse;
 		delete tex_offsets;
-		tex_sparse = NULL;
 		tex_offsets = NULL;
 		return false;
 	}
 
-	SparseTile<DeviceType> *texture_pixels;
+	VLOG(1) << "Original memory usage of '"
+	        << path_filename(img->filename) << "' (" << img->mem_name << "): "
+	        << string_human_readable_size(tex_img->memory_size());
+
+	DeviceType *texture_pixels;
 	int *texture_offsets;
-	int tiw = compute_tile_resolution(tex_dense->data_width);
-	int tih = compute_tile_resolution(tex_dense->data_height);
-	int tid = compute_tile_resolution(tex_dense->data_depth);
+	int tiw = get_tile_res(tex_img->data_width);
+	int tih = get_tile_res(tex_img->data_height);
+	int tid = get_tile_res(tex_img->data_depth);
 
 	{
-		/* Since only active tiles are stored in tex_sparse, its
+		/* Since only active tiles are stored in tex_img, its
 		 * allocated memory will be <= the actual resolution
 		 * of the volume. We store the true resolution (in tiles) in the
 		 * tex_offsets instead, since it needs to be allocated enough
 		 * space to track all tiles anyway. */
 		thread_scoped_lock device_lock(device_mutex);
-		texture_pixels = (SparseTile<DeviceType>*)tex_sparse->alloc(active_tile_count);
+		texture_pixels = (DeviceType*)tex_img->alloc(voxel_count);
 		texture_offsets = (int*)tex_offsets->alloc(tiw, tih, tid);
 	}
 
@@ -784,20 +781,9 @@ bool ImageManager::file_make_image_sparse(Device *device,
 		   offsets.size() * sizeof(int));
 	memcpy(&texture_pixels[0],
 		   &sparse_grid[0],
-		   active_tile_count * sizeof(SparseTile<DeviceType>));
-
-	img->mem = tex_sparse;
-	img->mem->interpolation = img->interpolation;
-	img->mem->extension = img->extension;
-	img->mem->offsets = tex_offsets;
-
-	thread_scoped_lock device_lock(device_mutex);
-	tex_sparse->copy_to_device();
-
-	VLOG(1) << "Original memory usage of '"
-	        << path_filename(img->filename) << "' (" << img->mem_name << "): "
-	        << string_human_readable_size(tex_dense->memory_size());
+		   voxel_count * sizeof(DeviceType));
 
+	tex_img->offsets = tex_offsets;
 	return true;
 }
 
@@ -824,19 +810,17 @@ void ImageManager::load_image(Device *device,
 	}
 
 	if(img->make_sparse) {
-		if(file_make_image_sparse<DeviceType>(device, img, tex_img)) {
-			delete tex_img;
-			tex_img = NULL;
+		if(!file_make_image_sparse<DeviceType>(device, img, tex_img)) {
+			file_load_failed<StorageType, DeviceType>(tex_img, type);
 		}
 	}
 
-	if(tex_img) {
-		img->mem = tex_img;
-		img->mem->interpolation = img->interpolation;
-		img->mem->extension = img->extension;
-		thread_scoped_lock device_lock(device_mutex);
-		tex_img->copy_to_device();
-	}
+	img->mem = tex_img;
+	img->mem->interpolation = img->interpolation;
+	img->mem->extension = img->extension;
+
+	thread_scoped_lock device_lock(device_mutex);
+	tex_img->copy_to_device();
 }
 
 void ImageManager::device_load_image(Device *device,
diff --git a/intern/cycles/render/mesh_volume.cpp b/intern/cycles/render/mesh_volume.cpp
index 8a55b89abcc..db8b8797165 100644
--- a/intern/cycles/render/mesh_volume.cpp
+++ b/intern/cycles/render/mesh_volume.cpp
@@ -378,7 +378,7 @@ void VolumeMeshBuilder::convert_quads_to_tris(const vector<QuadData> &quads,
 /* ************************************************************************** */
 
 struct VoxelAttributeGrid {
-	void *data;
+	float *data;
 	int *offsets = NULL;
 	int channels;
 };
@@ -410,7 +410,7 @@ void MeshManager::create_volume_mesh(Scene *scene,
 			                       offsets->data_height * TILE_SIZE,
 			                       offsets->data_depth * TILE_SIZE);
 		}
-		else{
+		else {
 			resolution = make_int3(image_memory->data_width,
                                    image_memory->data_height,
 		                           image_memory->data_depth);
@@ -425,7 +425,7 @@ void MeshManager::create_volume_mesh(Scene *scene,
 		}
 
 		VoxelAttributeGrid voxel_grid;
-		voxel_grid.data = image_memory->host_pointer;
+		voxel_grid.data = static_cast<float*>(image_memory->host_pointer);
 		voxel_grid.channels = image_memory->data_elements;
 		if(offsets) {
 			voxel_grid.offsets = static_cast<int*>(offsets->host_pointer);
@@ -469,9 +469,9 @@ 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 int3 tile_res = make_int3(compute_tile_resolution(resolution.x),
-	                                compute_tile_resolution(resolution.y),
-	                                compute_tile_resolution(resolution.z));
+	const int3 tile_res = make_int3(get_tile_res(resolution.x),
+	                                get_tile_res(resolution.y),
+	                                get_tile_res(resolution.z));
 
 	if(attr) {
 		const Transform *tfm = attr->data_transform();
@@ -488,57 +488,31 @@ void MeshManager::create_volume_mesh(Scene *scene,
 	VolumeMeshBuilder builder(&volume_params);
 	const float isovalue = mesh->volume_isovalue;
 
-	for(size_t i = 0; i < voxel_grids.size(); ++i) {
-		const VoxelAttributeGrid &voxel_grid = voxel_grids[i];
-		const int channels = voxel_grid.channels;
-
-		if(channels > 1 && voxel_grid.offsets) {
-			SparseTile<float4> *data = (SparseTile<float4>*)voxel_grid.data;
-			for(int z = 0; z < resolution.z; ++z) {
-				for(int y = 0; y < resolution.y; ++y) {
-					for(int x = 0; x < resolution.x; ++x) {
-						float4 val = get_value<float4>(data,
-						                               voxel_grid.offsets,
-						                               x, y, z,
-						                               tile_res.x,
-						                               tile_res.y,
-						                               tile_res.z);
-						if(any(isovalue < val)) {
-							builder.add_node_with_padding(x, y, z);
+	for(int z = 0; z < resolution.z; ++z) {
+		for(int y = 0; y < resolution.y; ++y) {
+			for(int x = 0; x < resolution.x; ++x) {
+				int voxel_index = compute_index(x, y, z, resolution);
+
+				for(size_t i = 0; i < voxel_grids.size(); ++i) {
+					const VoxelAttributeGrid &voxel_grid = voxel_grids[i];
+					const int channels = voxel_grid.channels;
+					const int *offsets = voxel_grid.offsets;
+
+					if(offsets) {
+						voxel_index = compute_index(offsets, x, y, z,
+						                            tile_res.x,
+						                            tile_res.y,
+						                            tile_res.z);
+						if(voxel_index < 0) {
+							continue;
 						}
 					}
-				}
-			}
-		}
-		else if(voxel_grid.offsets) {
-			SparseTile<float> *data = (SparseTile<float>*)voxel_grid.data;
-			for(int z = 0; z < resolution.z; ++z) {
-				for(int y = 0; y < resolution.y; ++y) {
-					for(int x = 0; x < resolution.x; ++x) {
-						float val = get_value<float>(data,
-						                             voxel_grid.offsets,
-						                             x, y, z,
-						                             tile_res.x,
-						                             tile_res.y,
-						                             tile_res.z);
-						if(val >= isovalue) {
+
+					voxel_index *= channels;
+					for(int c = 0; c < channels; c++) {
+						if(voxel_grid.data[voxel_index + c] >= isovalue) {
 							builder.add_node_with_padding(x, y, z);
-						}
-					}
-				}
-			}
-		}
-		else {
-			float *data = (float*)(voxel_grid.data);
-			for(int z = 0; z < resolution.z; ++z) {
-				for(int y = 0; y < resolution.y; ++y) {
-					for(int x = 0; x < resolution.x; ++x) {
-						size_t voxel_index = compute_index(x, y, z, resolution) * channels;
-						for(int c = 0 ; c < channels; ++c) {
-							if(data[voxel_index + c] >= isovalue) {
-								builder.add_node_with_padding(x, y, z);
-								break;
-							}
+							break;
 						}
 					}
 				}
diff --git a/intern/cycles/util/util_sparse_grid.h b/intern/cycles/util/util_sparse_grid.h
index 91ed75e23f8..5e47316ddff 100644
--- a/intern/cycles/util/util_sparse_grid.h
+++ b/intern/cycles/util/util_sparse_grid.h
@@ -50,10 +50,6 @@ namespace {
 static const int TILE_SIZE = 8;
 static const float THRESHOLD = 0.001f;
 
-template<typename T> struct SparseTile {
-	T values[TILE_SIZE * TILE_SIZE * TILE_SIZE];
-};
-
 const inline int compute_index(const size_t x, const size_t y, const size_t z,
                                const size_t width, const size_t height, const size_t depth)
 {
@@ -81,7 +77,7 @@ const inline int3 compute_coordinates(const size_t index, const size_t width,
 	return make_int3(x, y, z);
 }
 
-const inline size_t compute_tile_resolution(const size_t res)
+const inline size_t get_tile_res(const size_t res)
 {
 	return (res / TILE_SIZE) + !(res % TILE_SIZE == 0);
 }
@@ -102,31 +98,39 @@ const inline bool tile_is_active(const int *offsets,
 	return dense_index < 0 ? false : offsets[dense_index] >= 0;
 }
 
-template<typename T>
-const T get_value(const SparseTile<T> *grid, const int *offsets,
-                  int x, int y, int z, int tiw, int tih, int tid)
+const inline int compute_index(const int *offsets,
+                               int x, int y, int z,
+                               int tiw, int tih, int tid)
 {
 	/* Get the 1D array index in the dense grid of the tile (x, y, z) is in. */
 	int tix = x/TILE_SIZE, tiy = y/TILE_SIZE, tiz = z/TILE_SIZE;
 	int dense_index = compute_index(tix, tiy, tiz, tiw, tih, tid);
 	if(dense_index < 0) {
-		return cast_from_float<T>(0.0f);
+		return -1;
 	}
 	/* Get the index of the tile in the sparse grid. */
 	int sparse_index = offsets[dense_index];
 	if (sparse_index < 0) {
-		return cast_from_float<T>(0.0f);
+		return -1;
 	}
 	/* Look up voxel in the tile. */
 	int in_tile_index = compute_index(x%TILE_SIZE, y%TILE_SIZE, z%TILE_SIZE,
 	                                  TILE_SIZE, TILE_SIZE, TILE_SIZE);
-	return grid[sparse_index].values[in_tile_index];
+	return sparse_index + in_tile_index;
+}
+
+const inline int compute_index(const int *offsets, int index,
+                               int width, int height, int depth)
+{
+	int3 c = compute_coordinates(index, width, height, depth);
+	return compute_index(offsets, c.x, c.y, c.z, get_tile_res(width),
+	                     get_tile_res(height), get_tile_res(depth));
 }
 
 template<typename T>
 int create_sparse_grid(const T *dense_grid,
                        int width, int height, int depth,
-                       vector<SparseTile<T>> *sparse_grid,
+                       vector<T> *sparse_grid,
                        vector<int> *offsets)
 {
 	if(!dense_grid) {
@@ -135,23 +139,24 @@ int create_sparse_grid(const T *dense_grid,
 
 	const T empty = cast_from_float<T>(0.0f);
 	const T threshold = cast_from_float<T>(THRESHOLD);
-	int active_tile_count = 0;
-	int total_tile_count = compute_tile_resolution(width) *
-	                       compute_tile_resolution(height) *
-	                       compute_tile_resolution(depth);
+	T tile[TILE_SIZE * TILE_SIZE * TILE_SIZE];
+
+	/* Total number of active voxels (voxels in active tiles). */
+	int voxel_count = 0;
+	/* Total number of tiles in the grid (incl. inactive). */
+	int tile_count = get_tile_res(width) * get_tile_res(height) * get_tile_res(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(total_tile_count);
-	offsets->resize(total_tile_count);
-	total_tile_count = 0;
+	sparse_grid->resize(width * height * depth);
+	offsets->resize(tile_count);
+	tile_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) {
 
-				SparseTile<T> tile;
 				bool tile_is_empty = true;
 				int c = 0;
 
@@ -163,10 +168,10 @@ int create_sparse_grid(const T *dense_grid,
 							if(index < 0) {
 								/* Out of bounds of original image
 								 * store an empty voxel. */
-								tile.values[c] = empty;
+								tile[c] = empty;
 							}
 							else {
-								tile.values[c] = dense_grid[index];
+								tile[c] = dense_grid[index];
 								if(tile_is_empty) {
 									if(gt(dense_grid[index], threshold)) {
 										tile_is_empty = false;
@@ -180,21 +185,23 @@ int create_sparse_grid(const T *dense_grid,
 
 				/* Add tile if active. */
 				if(tile_is_empty) {
-					(*offsets)[total_tile_count] = -1;
+					(*offsets)[tile_count] = -1;
 				}
 				else {
-					(*sparse_grid)[active_tile_count] = tile;
-					(*offsets)[total_tile_count] = active_tile_count;
-					++active_tile_count;
+					(*offsets)[tile_count] = voxel_count;
+					for(int i=0 ; i < c ; ++i) {
+						sparse_grid->at(voxel_count + i) = tile[i];
+					}
+					voxel_count += c;
 				}
-				++total_tile_count;
+				++tile_count;
 			}
 		}
 	}
 
 	/* Return so that the parent function can resize
 	 * sparse_grid appropriately. */
-	return active_tile_count;
+	return voxel_count;
 }
 
 CCL_NAMESPACE_END