Reduce sparse grid memory usage and minor fixes.

Sparse grids originally padded out an image to dimensions divisible by
TILE_SIZE, which resulted in many empty voxels in large volumes. Now,
border tiles are taken into account when calculating voxel indexes.

Aside from that, made some other minor fixes throughout the files.

7 files changed, 89 insertions, 104 deletions

diff --git a/intern/cycles/device/device_cpu.cpp b/intern/cycles/device/device_cpu.cpp
index a21884de6d6..4e1fa05e168 100644
--- a/intern/cycles/device/device_cpu.cpp
+++ b/intern/cycles/device/device_cpu.cpp
@@ -378,8 +378,9 @@ public:
 	{
 		size_t total_memory = mem.memory_size();
 		device_memory *offsets = mem.offsets;
-		if(offsets != NULL)
+		if(offsets) {
 			total_memory += offsets->memory_size();
+		}
 
 		VLOG(1) << "Texture allocate: " << mem.name << ", "
 		        << string_human_readable_number(total_memory) << " bytes. ("
@@ -414,21 +415,10 @@ public:
 			info.cl_buffer = 0;
 			info.interpolation = mem.interpolation;
 			info.extension = mem.extension;
-			if(offsets != NULL) {
-				/* If mem is a sparse volume, its real (tile)
-				 * dimensions are stored in the offsets texture.
-				 * Here, we store the pixel resolution. */
-				info.width = offsets->data_width * TILE_SIZE;
-				info.height = offsets->data_height * TILE_SIZE;
-				info.depth = offsets->data_depth * TILE_SIZE;
-				info.offsets = (uint64_t)offsets->host_pointer;
-			}
-			else {
-				info.width = mem.data_width;
-				info.height = mem.data_height;
-				info.depth = mem.data_depth;
-				info.offsets = (uint64_t)0;
-			}
+			info.width = mem.real_width;
+			info.height = mem.real_height;
+			info.depth = mem.real_depth;
+			info.offsets = (uint64_t)(offsets ? offsets->host_pointer : 0);
 			need_texture_info = true;
 		}
 
@@ -436,7 +426,7 @@ public:
 		mem.device_size = mem.memory_size();
 		stats.mem_alloc(mem.device_size);
 
-		if(offsets != NULL) {
+		if(offsets) {
 			offsets->device_pointer = (device_ptr)offsets->host_pointer;
 			offsets->device_size = offsets->memory_size();
 			stats.mem_alloc(offsets->device_size);
@@ -447,6 +437,9 @@ public:
 	void tex_free(device_memory& mem)
 	{
 		if(mem.device_pointer) {
+			if(mem.offsets) {
+				tex_free(*mem.offsets);
+			}
 			mem.device_pointer = 0;
 			stats.mem_free(mem.device_size);
 			mem.device_size = 0;
diff --git a/intern/cycles/device/device_memory.h b/intern/cycles/device/device_memory.h
index dd7f72ce102..a230d3928ca 100644
--- a/intern/cycles/device/device_memory.h
+++ b/intern/cycles/device/device_memory.h
@@ -187,6 +187,12 @@ public:
 	size_t data_width;
 	size_t data_height;
 	size_t data_depth;
+	/* For normal images, data_* = real_*. For sparse images,
+	 * real_* refers to the real voxel resolution of the image,
+	 * since sparse images are stored as a long 1D array. */
+	size_t real_width;
+	size_t real_height;
+	size_t real_depth;
 	MemoryType type;
 	const char *name;
 	InterpolationType interpolation;
@@ -318,9 +324,9 @@ public:
 		}
 
 		data_size = new_size;
-		data_width = width;
-		data_height = height;
-		data_depth = depth;
+		data_width = real_width = width;
+		data_height = real_height = height;
+		data_depth = real_depth = depth;
 
 		return data();
 	}
diff --git a/intern/cycles/kernel/kernels/cpu/kernel_cpu_image.h b/intern/cycles/kernel/kernels/cpu/kernel_cpu_image.h
index 93aa6117f58..7513efc6b15 100644
--- a/intern/cycles/kernel/kernels/cpu/kernel_cpu_image.h
+++ b/intern/cycles/kernel/kernels/cpu/kernel_cpu_image.h
@@ -77,16 +77,23 @@ template<typename T> struct TextureInterpolator  {
 
 	static ccl_always_inline float4 read(const T *data, const int *offsets,
 	                                     int x, int y, int z,
+	                                     int width, int height, int depth,
 	                                     int tiw, int tih, int tid)
 	{
-		int index = compute_index(offsets, x, y, z, tiw, tih, tid);
+		int index = compute_index(offsets, x, y, z,
+		                          width, height, depth, 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);
+		int3 c = compute_coordinates(idx, width, height, depth);
+		int index = compute_index(offsets, c.x, c.y, c.z,
+		                          width, height, depth,
+		                          get_tile_res(width),
+		                          get_tile_res(height),
+		                          get_tile_res(depth));
 		return index < 0 ? make_float4(0.0f) : read(data[index]);
 	}
 
@@ -300,8 +307,8 @@ template<typename T> struct TextureInterpolator  {
 		const int *ofs = (const int*)info.offsets;
 
 		if(ofs) {
-			return read(data, ofs, ix, iy, iz, get_tile_res(width),
-			            get_tile_res(height), get_tile_res(depth));
+			return read(data, ofs, ix, iy, iz, width, height, depth,
+			            get_tile_res(width), get_tile_res(height), get_tile_res(depth));
 		}
 		return read(data[compute_index(ix, iy, iz, width, height, depth)]);
 	}
@@ -361,14 +368,14 @@ template<typename T> struct TextureInterpolator  {
 			   !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(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);
+			r  = (1.0f - tz)*(1.0f - ty)*(1.0f - tx) * read(data, ofs, ix,  iy,  iz,  width, height, depth, tiw, tih, tid);
+			r += (1.0f - tz)*(1.0f - ty)*tx			 * read(data, ofs, nix, iy,  iz,  width, height, depth, tiw, tih, tid);
+			r += (1.0f - tz)*ty*(1.0f - tx)			 * read(data, ofs, ix,  niy, iz,  width, height, depth, tiw, tih, tid);
+			r += (1.0f - tz)*ty*tx					 * read(data, ofs, nix, niy, iz,  width, height, depth, tiw, tih, tid);
+			r += tz*(1.0f - ty)*(1.0f - tx)			 * read(data, ofs, ix,  iy,  niz, width, height, depth, tiw, tih, tid);
+			r += tz*(1.0f - ty)*tx					 * read(data, ofs, nix, iy,  niz, width, height, depth, tiw, tih, tid);
+			r += tz*ty*(1.0f - tx)					 * read(data, ofs, ix,  niy, niz, width, height, depth, tiw, tih, tid);
+			r += tz*ty*tx							 * read(data, ofs, nix, niy, niz, width, height, depth, tiw, tih, tid);
 		}
 		else {
 			r  = (1.0f - tz)*(1.0f - ty)*(1.0f - tx) * read(data[compute_index(ix,  iy,  iz,  width, height, depth)]);
diff --git a/intern/cycles/render/image.cpp b/intern/cycles/render/image.cpp
index 61394700886..8ce96a5810a 100644
--- a/intern/cycles/render/image.cpp
+++ b/intern/cycles/render/image.cpp
@@ -730,53 +730,52 @@ void ImageManager::file_load_failed(device_vector<DeviceType> *tex_img,
 }
 
 template<typename DeviceType>
-bool ImageManager::file_make_image_sparse(Device *device,
+void ImageManager::file_make_image_sparse(Device *device,
                                           Image *img,
                                           device_vector<DeviceType> *tex_img)
 {
-	device_vector<int> *tex_offsets
-	        = new device_vector<int>(device,
-	                                 (img->mem_name + "_offsets").c_str(),
-	                                 MEM_TEXTURE);
+	int real_width = tex_img->data_width;
+	int real_height = tex_img->data_height;
+	int real_depth = tex_img->data_depth;
 
 	vector<DeviceType> sparse_grid;
 	vector<int> offsets;
+
 	int voxel_count = create_sparse_grid<DeviceType>(tex_img->data(),
-	                                                 tex_img->data_width,
-	                                                 tex_img->data_height,
-	                                                 tex_img->data_depth,
+	                                                 real_width,
+	                                                 real_height,
+	                                                 real_depth,
 	                                                 img->isovalue,
 	                                                 &sparse_grid,
 	                                                 &offsets);
 
+	size_t memory_usage = offsets.size() * sizeof(int) +
+	                   voxel_count * sizeof(DeviceType);
+
 	if(voxel_count < 1) {
 		VLOG(1) << "Could not make sparse grid for "
 		        << path_filename(img->filename) << " (" << img->mem_name << ")"
 		        << ", no active tiles";
-		delete tex_offsets;
-		tex_offsets = NULL;
-		return false;
+		return;
 	}
 
-	VLOG(1) << "Original memory usage of '"
-	        << path_filename(img->filename) << "' (" << img->mem_name << "): "
-	        << string_human_readable_size(tex_img->memory_size());
+	VLOG(1) << "Memory usage of '"
+	        << path_filename(img->filename) << "' (" << img->mem_name
+	        << ") reduced from "
+	        << string_human_readable_size(tex_img->memory_size()) << " to "
+	        << string_human_readable_size(memory_usage);
 
 	DeviceType *texture_pixels;
 	int *texture_offsets;
-	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);
+	device_vector<int> *tex_offsets
+	        = new device_vector<int>(device,
+	                                 (img->mem_name + "_offsets").c_str(),
+	                                 MEM_TEXTURE);
 
 	{
-		/* 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 = (DeviceType*)tex_img->alloc(voxel_count);
-		texture_offsets = (int*)tex_offsets->alloc(tiw, tih, tid);
+		texture_offsets = (int*)tex_offsets->alloc(offsets.size());
 	}
 
 	memcpy(&texture_offsets[0],
@@ -787,7 +786,9 @@ bool ImageManager::file_make_image_sparse(Device *device,
 		   voxel_count * sizeof(DeviceType));
 
 	tex_img->offsets = tex_offsets;
-	return true;
+	tex_img->real_width = real_width;
+	tex_img->real_height = real_height;
+	tex_img->real_depth = real_depth;
 }
 
 template<TypeDesc::BASETYPE FileFormat,
@@ -811,11 +812,8 @@ void ImageManager::load_image(Device *device,
 		        << path_filename(img->filename) << " (" << img->mem_name << ")";
 		file_load_failed<StorageType, DeviceType>(tex_img, type);
 	}
-
-	if(img->make_sparse) {
-		if(!file_make_image_sparse<DeviceType>(device, img, tex_img)) {
-			file_load_failed<StorageType, DeviceType>(tex_img, type);
-		}
+	else if(img->make_sparse) {
+		file_make_image_sparse<DeviceType>(device, img, tex_img);
 	}
 
 	img->mem = tex_img;
diff --git a/intern/cycles/render/image.h b/intern/cycles/render/image.h
index 7f4810968b2..8739c8f7793 100644
--- a/intern/cycles/render/image.h
+++ b/intern/cycles/render/image.h
@@ -161,7 +161,7 @@ private:
 	                      ImageDataType type);
 
 	template<typename DeviceType>
-	bool file_make_image_sparse(Device *device,
+	void file_make_image_sparse(Device *device,
 	                            Image *img,
 	                            device_vector<DeviceType> *tex_dense);
 
diff --git a/intern/cycles/render/mesh_volume.cpp b/intern/cycles/render/mesh_volume.cpp
index db8b8797165..1730dbd95ac 100644
--- a/intern/cycles/render/mesh_volume.cpp
+++ b/intern/cycles/render/mesh_volume.cpp
@@ -404,17 +404,9 @@ void MeshManager::create_volume_mesh(Scene *scene,
 		VoxelAttribute *voxel = attr.data_voxel();
 		device_memory *image_memory = scene->image_manager->image_memory(voxel->slot);
 		device_memory *offsets = image_memory->offsets;
-		int3 resolution;
-		if(offsets) {
-			resolution = make_int3(offsets->data_width * TILE_SIZE,
-			                       offsets->data_height * TILE_SIZE,
-			                       offsets->data_depth * TILE_SIZE);
-		}
-		else {
-			resolution = make_int3(image_memory->data_width,
-                                   image_memory->data_height,
-		                           image_memory->data_depth);
-		}
+		int3 resolution = make_int3(image_memory->real_width,
+		                            image_memory->real_height,
+		                            image_memory->real_depth);
 
 		if(volume_params.resolution == make_int3(0, 0, 0)) {
 			volume_params.resolution = resolution;
@@ -491,15 +483,17 @@ void MeshManager::create_volume_mesh(Scene *scene,
 	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;
+					int voxel_index;
 
 					if(offsets) {
 						voxel_index = compute_index(offsets, x, y, z,
+						                            resolution.x,
+						                            resolution.y,
+						                            resolution.z,
 						                            tile_res.x,
 						                            tile_res.y,
 						                            tile_res.z);
@@ -507,6 +501,9 @@ void MeshManager::create_volume_mesh(Scene *scene,
 							continue;
 						}
 					}
+					else {
+						voxel_index = compute_index(x, y, z, resolution);
+					}
 
 					voxel_index *= channels;
 					for(int c = 0; c < channels; c++) {
diff --git a/intern/cycles/util/util_sparse_grid.h b/intern/cycles/util/util_sparse_grid.h
index d7d426363a9..d31b3df287f 100644
--- a/intern/cycles/util/util_sparse_grid.h
+++ b/intern/cycles/util/util_sparse_grid.h
@@ -99,6 +99,7 @@ const inline bool tile_is_active(const int *offsets,
 
 const inline int compute_index(const int *offsets,
                                int x, int y, int z,
+                               int width, int height, int depth,
                                int tiw, int tih, int tid)
 {
 	/* Get the 1D array index in the dense grid of the tile (x, y, z) is in. */
@@ -107,25 +108,20 @@ const inline int compute_index(const int *offsets,
 	if(dense_index < 0) {
 		return -1;
 	}
-	/* Get the index of the tile in the sparse grid. */
+	/* Get the index of the first voxel in the target tile. */
 	int sparse_index = offsets[dense_index];
 	if (sparse_index < 0) {
 		return -1;
 	}
+	/* If tile is a border tile, get its real dimensions. */
+	int itiw = tix+1 == tiw && width % TILE_SIZE != 0 ? width % TILE_SIZE : TILE_SIZE;
+	int itih = tiy+1 == tih && height % TILE_SIZE != 0 ? height % TILE_SIZE : TILE_SIZE;
+	int itid = tiz+1 == tid && depth % TILE_SIZE != 0 ? depth % TILE_SIZE : TILE_SIZE;
 	/* 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);
+	int in_tile_index = compute_index(x % itiw, y % itih, z % itid, itiw, itih, itid);
 	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,
@@ -137,9 +133,7 @@ int create_sparse_grid(const T *dense_grid,
 		return 0;
 	}
 
-	const T empty = cast_from_float<T>(0.0f);
 	const T threshold = cast_from_float<T>(isovalue);
-
 	/* Total number of active voxels (voxels in active tiles). */
 	int voxel_count = 0;
 	/* Total number of tiles in the grid (incl. inactive). */
@@ -155,27 +149,17 @@ int create_sparse_grid(const T *dense_grid,
 	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 tile_is_empty = true;
 				int c = 0;
 
 				/* Populate the tile. */
-				for(int k=z ; k < z+TILE_SIZE ; ++k) {
-					for(int j=y ; j < y+TILE_SIZE ; ++j) {
-						for(int i=x ; i < x+TILE_SIZE ; ++i) {
+				for(int k=z ; k < z+TILE_SIZE && k < depth ; ++k) {
+					for(int j=y ; j < y+TILE_SIZE && j < height; ++j) {
+						for(int i=x ; i < x+TILE_SIZE && i < width ; ++i) {
 							int index = compute_index(i, j, k, width, height, depth);
-							if(index < 0) {
-								/* Out of bounds of original image
-								 * store an empty voxel. */
-								sparse_grid->at(voxel_count + c) = empty;
-							}
-							else {
-								sparse_grid->at(voxel_count + c) = dense_grid[index];
-								if(tile_is_empty) {
-									if(gt(dense_grid[index], threshold)) {
-										tile_is_empty = false;
-									}
-								}
+							sparse_grid->at(voxel_count + c) = dense_grid[index];
+							if(tile_is_empty) {
+								tile_is_empty = !gt(dense_grid[index], threshold);
 							}
 							++c;
 						}