Initial working implementation of tiling for sparse grids.

11 files changed, 527 insertions, 44 deletions

diff --git a/intern/cycles/blender/blender_session.cpp b/intern/cycles/blender/blender_session.cpp
index 00d23b9095e..649d6edc679 100644
--- a/intern/cycles/blender/blender_session.cpp
+++ b/intern/cycles/blender/blender_session.cpp
@@ -1051,6 +1051,7 @@ void BlenderSession::builtin_image_info(const string &builtin_name,
 		BL::SmokeDomainSettings b_domain = object_smoke_domain_find(b_ob);
 
 		metadata.is_float = true;
+		metadata.is_volume = false;
 		metadata.depth = 1;
 		metadata.channels = 1;
 
@@ -1060,14 +1061,19 @@ void BlenderSession::builtin_image_info(const string &builtin_name,
 		if(builtin_name == Attribute::standard_name(ATTR_STD_VOLUME_DENSITY) ||
 		   builtin_name == Attribute::standard_name(ATTR_STD_VOLUME_FLAME) ||
 		   builtin_name == Attribute::standard_name(ATTR_STD_VOLUME_HEAT) ||
-		   builtin_name == Attribute::standard_name(ATTR_STD_VOLUME_TEMPERATURE))
+		   builtin_name == Attribute::standard_name(ATTR_STD_VOLUME_TEMPERATURE)) {
 			metadata.channels = 1;
-		else if(builtin_name == Attribute::standard_name(ATTR_STD_VOLUME_COLOR))
+		}
+		else if(builtin_name == Attribute::standard_name(ATTR_STD_VOLUME_COLOR)) {
 			metadata.channels = 4;
-		else if(builtin_name == Attribute::standard_name(ATTR_STD_VOLUME_VELOCITY))
+			metadata.is_volume = true;
+		}
+		else if(builtin_name == Attribute::standard_name(ATTR_STD_VOLUME_VELOCITY)) {
 			metadata.channels = 3;
-		else
+		}
+		else {
 			return;
+		}
 
 		int3 resolution = get_int3(b_domain.domain_resolution());
 		int amplify = (b_domain.use_high_resolution())? b_domain.amplify() + 1: 1;
diff --git a/intern/cycles/device/device_cpu.cpp b/intern/cycles/device/device_cpu.cpp
index 6be60f8bbb6..a21884de6d6 100644
--- a/intern/cycles/device/device_cpu.cpp
+++ b/intern/cycles/device/device_cpu.cpp
@@ -52,6 +52,7 @@
 #include "util/util_progress.h"
 #include "util/util_system.h"
 #include "util/util_thread.h"
+#include "util/util_sparse_grid.h"
 
 CCL_NAMESPACE_BEGIN
 
@@ -375,9 +376,14 @@ public:
 
 	void tex_alloc(device_memory& mem)
 	{
+		size_t total_memory = mem.memory_size();
+		device_memory *offsets = mem.offsets;
+		if(offsets != NULL)
+			total_memory += offsets->memory_size();
+
 		VLOG(1) << "Texture allocate: " << mem.name << ", "
-		        << string_human_readable_number(mem.memory_size()) << " bytes. ("
-		        << string_human_readable_size(mem.memory_size()) << ")";
+		        << string_human_readable_number(total_memory) << " bytes. ("
+		        << string_human_readable_size(total_memory) << ")";
 
 		if(mem.interpolation == INTERPOLATION_NONE) {
 			/* Data texture. */
@@ -390,7 +396,7 @@ public:
 			/* Image Texture. */
 			int flat_slot = 0;
 			if(string_startswith(mem.name, "__tex_image")) {
-				int pos =  string(mem.name).rfind("_");
+				int pos = string(mem.name).rfind("_");
 				flat_slot = atoi(mem.name + pos + 1);
 			}
 			else {
@@ -408,16 +414,34 @@ public:
 			info.cl_buffer = 0;
 			info.interpolation = mem.interpolation;
 			info.extension = mem.extension;
-			info.width = mem.data_width;
-			info.height = mem.data_height;
-			info.depth = mem.data_depth;
-
+			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;
+			}
 			need_texture_info = true;
 		}
 
 		mem.device_pointer = (device_ptr)mem.host_pointer;
 		mem.device_size = mem.memory_size();
 		stats.mem_alloc(mem.device_size);
+
+		if(offsets != NULL) {
+			offsets->device_pointer = (device_ptr)offsets->host_pointer;
+			offsets->device_size = offsets->memory_size();
+			stats.mem_alloc(offsets->device_size);
+		}
+
 	}
 
 	void tex_free(device_memory& mem)
diff --git a/intern/cycles/device/device_memory.h b/intern/cycles/device/device_memory.h
index d8fe41e78bb..dd7f72ce102 100644
--- a/intern/cycles/device/device_memory.h
+++ b/intern/cycles/device/device_memory.h
@@ -197,6 +197,7 @@ public:
 	device_ptr device_pointer;
 	void *host_pointer;
 	void *shared_pointer;
+	device_memory *offsets = NULL;
 
 	virtual ~device_memory();
 
diff --git a/intern/cycles/kernel/kernels/cpu/kernel_cpu_image.h b/intern/cycles/kernel/kernels/cpu/kernel_cpu_image.h
index 7bf833eadbc..3c18b08d5b8 100644
--- a/intern/cycles/kernel/kernels/cpu/kernel_cpu_image.h
+++ b/intern/cycles/kernel/kernels/cpu/kernel_cpu_image.h
@@ -17,9 +17,12 @@
 #ifndef __KERNEL_CPU_IMAGE_H__
 #define __KERNEL_CPU_IMAGE_H__
 
+#include "util/util_sparse_grid.h"
+
 CCL_NAMESPACE_BEGIN
 
-template<typename T> struct TextureInterpolator  {
+template<typename T, bool is_tile = false>
+struct TextureInterpolator  {
 #define SET_CUBIC_SPLINE_WEIGHTS(u, t) \
 	{ \
 		u[0] = (((-1.0f/6.0f)* t + 0.5f) * t - 0.5f) * t + (1.0f/6.0f); \
@@ -68,7 +71,7 @@ template<typename T> struct TextureInterpolator  {
 	                                     int width, int height)
 	{
 		if(x < 0 || y < 0 || x >= width || y >= height) {
-			return make_float4(0.0f, 0.0f, 0.0f, 0.0f);
+			return make_float4(0.0f);
 		}
 		return read(data[y * width + x]);
 	}
@@ -111,7 +114,7 @@ template<typename T> struct TextureInterpolator  {
 				break;
 			case EXTENSION_CLIP:
 				if(x < 0.0f || y < 0.0f || x > 1.0f || y > 1.0f) {
-					return make_float4(0.0f, 0.0f, 0.0f, 0.0f);
+					return make_float4(0.0f);
 				}
 				ATTR_FALLTHROUGH;
 			case EXTENSION_EXTEND:
@@ -120,7 +123,7 @@ template<typename T> struct TextureInterpolator  {
 				break;
 			default:
 				kernel_assert(0);
-				return make_float4(0.0f, 0.0f, 0.0f, 0.0f);
+				return make_float4(0.0f);
 		}
 		return read(data[ix + iy*width]);
 	}
@@ -153,7 +156,7 @@ template<typename T> struct TextureInterpolator  {
 				break;
 			default:
 				kernel_assert(0);
-				return make_float4(0.0f, 0.0f, 0.0f, 0.0f);
+				return make_float4(0.0f);
 		}
 		return (1.0f - ty) * (1.0f - tx) * read(data, ix, iy, width, height) +
 		       (1.0f - ty) * tx * read(data, nix, iy, width, height) +
@@ -202,7 +205,7 @@ template<typename T> struct TextureInterpolator  {
 				break;
 			default:
 				kernel_assert(0);
-				return make_float4(0.0f, 0.0f, 0.0f, 0.0f);
+				return make_float4(0.0f);
 		}
 		const int xc[4] = {pix, ix, nix, nnix};
 		const int yc[4] = {piy, iy, niy, nniy};
@@ -230,7 +233,7 @@ template<typename T> struct TextureInterpolator  {
 	                                       float x, float y)
 	{
 		if(UNLIKELY(!info.data)) {
-			return make_float4(0.0f, 0.0f, 0.0f, 0.0f);
+			return make_float4(0.0f);
 		}
 		switch(info.interpolation) {
 			case INTERPOLATION_CLOSEST:
@@ -266,7 +269,7 @@ template<typename T> struct TextureInterpolator  {
 				if(x < 0.0f || y < 0.0f || z < 0.0f ||
 				   x > 1.0f || y > 1.0f || z > 1.0f)
 				{
-					return make_float4(0.0f, 0.0f, 0.0f, 0.0f);
+					return make_float4(0.0f);
 				}
 				ATTR_FALLTHROUGH;
 			case EXTENSION_EXTEND:
@@ -276,11 +279,18 @@ template<typename T> struct TextureInterpolator  {
 				break;
 			default:
 				kernel_assert(0);
-				return make_float4(0.0f, 0.0f, 0.0f, 0.0f);
+				return make_float4(0.0f);
 		}
 
-		const T *data = (const T*)info.data;
-		return read(data[ix + iy*width + iz*width*height]);
+		if(is_tile) {
+			const SparseTile *data = (const SparseTile*)info.data;
+			const int *ofs = (const int*)info.offsets;
+			return read(get_value(data, ofs, ix, iy, iz, width, height, depth));
+		}
+		else {
+			const T *data = (const T*)info.data;
+			return read(data[compute_index(ix, iy, iz, width, height, depth)]);
+		}
 	}
 
 	static ccl_always_inline float4 interp_3d_linear(const TextureInfo& info,
@@ -310,7 +320,7 @@ template<typename T> struct TextureInterpolator  {
 				if(x < 0.0f || y < 0.0f || z < 0.0f ||
 				   x > 1.0f || y > 1.0f || z > 1.0f)
 				{
-					return make_float4(0.0f, 0.0f, 0.0f, 0.0f);
+					return make_float4(0.0f);
 				}
 				ATTR_FALLTHROUGH;
 			case EXTENSION_EXTEND:
@@ -324,21 +334,39 @@ template<typename T> struct TextureInterpolator  {
 				break;
 			default:
 				kernel_assert(0);
-				return make_float4(0.0f, 0.0f, 0.0f, 0.0f);
+				return make_float4(0.0f);
 		}
 
-		const T *data = (const T*)info.data;
 		float4 r;
 
-		r  = (1.0f - tz)*(1.0f - ty)*(1.0f - tx)*read(data[ix + iy*width + iz*width*height]);
-		r += (1.0f - tz)*(1.0f - ty)*tx*read(data[nix + iy*width + iz*width*height]);
-		r += (1.0f - tz)*ty*(1.0f - tx)*read(data[ix + niy*width + iz*width*height]);
-		r += (1.0f - tz)*ty*tx*read(data[nix + niy*width + iz*width*height]);
-
-		r += tz*(1.0f - ty)*(1.0f - tx)*read(data[ix + iy*width + niz*width*height]);
-		r += tz*(1.0f - ty)*tx*read(data[nix + iy*width + niz*width*height]);
-		r += tz*ty*(1.0f - tx)*read(data[ix + niy*width + niz*width*height]);
-		r += tz*ty*tx*read(data[nix + niy*width + niz*width*height]);
+		if(is_tile) {
+			const SparseTile *data = (const SparseTile*)info.data;
+			const int *ofs = (const int*)info.offsets;
+			/* Initial check if either voxel is in an active tile. */
+			if(!is_active(ofs, ix, iy, iz, width, height, depth) &&
+			   !is_active(ofs, nix, niy, niz, width, height, depth)) {
+				return make_float4(0.0f);
+			}
+			r  = (1.0f - tz)*(1.0f - ty)*(1.0f - tx) * read(get_value(data, ofs, ix,  iy,  iz,  width, height, depth));
+			r += (1.0f - tz)*(1.0f - ty)*tx			 * read(get_value(data, ofs, nix, iy,  iz,  width, height, depth));
+			r += (1.0f - tz)*ty*(1.0f - tx)			 * read(get_value(data, ofs, ix,  niy, iz,  width, height, depth));
+			r += (1.0f - tz)*ty*tx					 * read(get_value(data, ofs, nix, niy, iz,  width, height, depth));
+			r += tz*(1.0f - ty)*(1.0f - tx)			 * read(get_value(data, ofs, ix,  iy,  niz, width, height, depth));
+			r += tz*(1.0f - ty)*tx					 * read(get_value(data, ofs, nix, iy,  niz, width, height, depth));
+			r += tz*ty*(1.0f - tx)					 * read(get_value(data, ofs, ix,  niy, niz, width, height, depth));
+			r += tz*ty*tx							 * read(get_value(data, ofs, nix, niy, niz, width, height, depth));
+		}
+		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)]);
+			r += (1.0f - tz)*ty*tx					 * read(data[compute_index(nix, niy, iz,  width, height, depth)]);
+			r += tz*(1.0f - ty)*(1.0f - tx)			 * read(data[compute_index(ix,  iy,  niz, width, height, depth)]);
+			r += tz*(1.0f - ty)*tx					 * read(data[compute_index(nix, iy,  niz, width, height, depth)]);
+			r += tz*ty*(1.0f - tx)					 * read(data[compute_index(ix,  niy, niz, width, height, depth)]);
+			r += tz*ty*tx							 * read(data[compute_index(nix, niy, niz, width, height, depth)]);
+		}
 
 		return r;
 	}
@@ -356,6 +384,8 @@ template<typename T> struct TextureInterpolator  {
 #endif
 	float4 interp_3d_tricubic(const TextureInfo& info, float x, float y, float z)
 	{
+		/* todo (gchua): add tile support for this */
+		kernel_assert(!is_tile);
 		int width = info.width;
 		int height = info.height;
 		int depth = info.depth;
@@ -389,7 +419,7 @@ template<typename T> struct TextureInterpolator  {
 				if(x < 0.0f || y < 0.0f || z < 0.0f ||
 				   x > 1.0f || y > 1.0f || z > 1.0f)
 				{
-					return make_float4(0.0f, 0.0f, 0.0f, 0.0f);
+					return make_float4(0.0f);
 				}
 				ATTR_FALLTHROUGH;
 			case EXTENSION_EXTEND:
@@ -411,7 +441,7 @@ template<typename T> struct TextureInterpolator  {
 				break;
 			default:
 				kernel_assert(0);
-				return make_float4(0.0f, 0.0f, 0.0f, 0.0f);
+				return make_float4(0.0f);
 		}
 
 		const int xc[4] = {pix, ix, nix, nnix};
@@ -458,7 +488,7 @@ template<typename T> struct TextureInterpolator  {
 	                                          InterpolationType interp)
 	{
 		if(UNLIKELY(!info.data))
-			return make_float4(0.0f, 0.0f, 0.0f, 0.0f);
+			return make_float4(0.0f);
 
 		switch((interp == INTERPOLATION_NONE)? info.interpolation: interp) {
 			case INTERPOLATION_CLOSEST:
@@ -508,6 +538,8 @@ ccl_device float4 kernel_tex_image_interp_3d(KernelGlobals *kg, int id, float x,
 			return TextureInterpolator<half4>::interp_3d(info, x, y, z, interp);
 		case IMAGE_DATA_TYPE_BYTE4:
 			return TextureInterpolator<uchar4>::interp_3d(info, x, y, z, interp);
+		case IMAGE_DATA_TYPE_VOLUME:
+			return TextureInterpolator<float4, true>::interp_3d(info, x, y, z, interp);
 		case IMAGE_DATA_TYPE_FLOAT4:
 		default:
 			return TextureInterpolator<float4>::interp_3d(info, x, y, z, interp);
diff --git a/intern/cycles/render/image.cpp b/intern/cycles/render/image.cpp
index 9c5e32e8219..f7e2f6488a1 100644
--- a/intern/cycles/render/image.cpp
+++ b/intern/cycles/render/image.cpp
@@ -108,7 +108,10 @@ bool ImageManager::get_image_metadata(const string& filename,
 			return false;
 		}
 
-		if(metadata.is_float) {
+		if(metadata.is_volume) {
+			metadata.type = IMAGE_DATA_TYPE_VOLUME;
+		}
+		else if(metadata.is_float) {
 			metadata.is_linear = true;
 			metadata.type = (metadata.channels > 1) ? IMAGE_DATA_TYPE_FLOAT4 : IMAGE_DATA_TYPE_FLOAT;
 		}
@@ -183,7 +186,10 @@ bool ImageManager::get_image_metadata(const string& filename,
 	/* set type and channels */
 	metadata.channels = spec.nchannels;
 
-	if(metadata.is_half) {
+	if(metadata.is_volume) {
+		metadata.type = IMAGE_DATA_TYPE_VOLUME;
+	}
+	else if(metadata.is_half) {
 		metadata.type = (metadata.channels > 1) ? IMAGE_DATA_TYPE_HALF4 : IMAGE_DATA_TYPE_HALF;
 	}
 	else if(metadata.is_float) {
@@ -235,6 +241,8 @@ string ImageManager::name_from_type(int type)
 		return "half4";
 	else if(type == IMAGE_DATA_TYPE_HALF)
 		return "half";
+	else if(type == IMAGE_DATA_TYPE_VOLUME)
+		return "volume";
 	else
 		return "byte4";
 }
@@ -574,6 +582,7 @@ bool ImageManager::file_load_image(Image *img,
 	 * but device doesn't support single channel textures.
 	 */
 	bool is_rgba = (type == IMAGE_DATA_TYPE_FLOAT4 ||
+	                type == IMAGE_DATA_TYPE_VOLUME ||
 	                type == IMAGE_DATA_TYPE_HALF4 ||
 	                type == IMAGE_DATA_TYPE_BYTE4);
 	if(is_rgba) {
@@ -682,6 +691,87 @@ bool ImageManager::file_load_image(Image *img,
 	return true;
 }
 
+
+/* If volume, call this to convert to sparse grid. */
+template<TypeDesc::BASETYPE FileFormat,
+         typename StorageType,
+         typename DeviceType>
+bool ImageManager::file_load_image(Image *img,
+                                   ImageDataType type,
+                                   int texture_limit,
+                                   device_vector<SparseTile>& tex_img,
+                                   device_vector<int>& tex_offsets)
+{
+
+	device_vector<DeviceType> *tex_img_dense
+		= new device_vector<DeviceType>(NULL, img->mem_name.c_str(), MEM_TEXTURE);
+
+	if(!file_load_image<FileFormat, StorageType, DeviceType>(img,
+	                                                         type,
+	                                                         texture_limit,
+	                                                         *tex_img_dense))
+	{
+		/* Release temporary pointer. */
+		delete tex_img_dense;
+		tex_img_dense = NULL;
+		return false;
+	}
+
+	DeviceType *data = tex_img_dense->data();
+	size_t tile_width = compute_tile_resolution(tex_img_dense->data_width);
+	size_t tile_height = compute_tile_resolution(tex_img_dense->data_height);
+	size_t tile_depth = compute_tile_resolution(tex_img_dense->data_depth);
+
+	vector<SparseTile> sparse_grid;
+	vector<int> offsets;
+	/* Sample threshold value for now. */
+	float4 threshold = make_float4(0.0f);
+	int active_tile_count = create_sparse_grid(data, threshold,
+										       tex_img_dense->data_width,
+											   tex_img_dense->data_height,
+											   tex_img_dense->data_depth,
+											   &sparse_grid, &offsets);
+
+	if(active_tile_count < 1) {
+		/* to-do (gchua): handle this. */
+	}
+
+	SparseTile *texture_pixels;
+	int *texture_offsets;
+	{
+		/* 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*)tex_img.alloc(active_tile_count);
+		texture_offsets = (int*)tex_offsets.alloc(tile_width,
+												 tile_height,
+												 tile_depth);
+	}
+
+	memcpy(texture_offsets,
+		   &offsets[0],
+		   offsets.size() * sizeof(int));
+	memcpy(texture_pixels,
+		   &sparse_grid[0],
+		   active_tile_count * sizeof(SparseTile));
+
+	VLOG(1) << "Memory usage of dense grid '" << img->filename << "': "
+		    << string_human_readable_size(tex_img_dense->memory_size());
+	VLOG(1) << "Memory usage of sparse grid '" << img->filename << "': "
+	        << string_human_readable_size(tex_img.memory_size());
+	VLOG(1) << "Memory usage of auxiliary index: "
+	        << string_human_readable_size(tex_offsets.memory_size());
+
+	/* Release temporary pointer. */
+	delete tex_img_dense;
+	tex_img_dense = NULL;
+
+	return true;
+}
+
 void ImageManager::device_load_image(Device *device,
                                      Scene *scene,
                                      ImageDataType type,
@@ -696,7 +786,7 @@ void ImageManager::device_load_image(Device *device,
 	if(osl_texture_system && !img->builtin_data)
 		return;
 
-	string filename = path_filename(images[type][slot]->filename);
+	string filename = path_filename(img->filename);
 	progress->set_status("Updating Images", "Loading " + filename);
 
 	const int texture_limit = scene->params.texture_limit;
@@ -705,9 +795,13 @@ void ImageManager::device_load_image(Device *device,
 	int flat_slot = type_index_to_flattened_slot(slot, type);
 	img->mem_name = string_printf("__tex_image_%s_%03d", name_from_type(type).c_str(), flat_slot);
 
-	/* Free previous texture in slot. */
+	/* Free previous texture(s) in slot. */
 	if(img->mem) {
 		thread_scoped_lock device_lock(device_mutex);
+		if(img->mem->offsets) {
+			delete img->mem->offsets;
+			img->mem->offsets = NULL;
+		}
 		delete img->mem;
 		img->mem = NULL;
 	}
@@ -857,6 +951,55 @@ void ImageManager::device_load_image(Device *device,
 		thread_scoped_lock device_lock(device_mutex);
 		tex_img->copy_to_device();
 	}
+	else if(type == IMAGE_DATA_TYPE_VOLUME) {
+		device_vector<SparseTile> *tex_img
+			= new device_vector<SparseTile>(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);
+
+		if(!file_load_image<TypeDesc::FLOAT, float, float4>(img,
+															type,
+															texture_limit,
+															*tex_img,
+															*tex_offsets))
+		{
+			/* Clear pointers. */
+			delete tex_img;
+			delete tex_offsets;
+			tex_img = NULL;
+			tex_offsets = NULL;
+
+			/* on failure to load, we set a 1x1 pixels pink image (float4) */
+			device_vector<float4> *tex_fail
+				= new device_vector<float4>(device, img->mem_name.c_str(), MEM_TEXTURE);
+
+			thread_scoped_lock device_lock(device_mutex);
+			float *pixels = (float*)tex_fail->alloc(1, 1);
+
+			pixels[0] = TEX_IMAGE_MISSING_R;
+			pixels[1] = TEX_IMAGE_MISSING_G;
+			pixels[2] = TEX_IMAGE_MISSING_B;
+			pixels[3] = TEX_IMAGE_MISSING_A;
+
+			img->mem = tex_fail;
+			img->mem->interpolation = img->interpolation;
+			img->mem->extension = img->extension;
+			tex_fail->copy_to_device();
+		}
+		else {
+			img->mem = tex_img;
+			img->mem->interpolation = img->interpolation;
+			img->mem->extension = img->extension;
+			img->mem->offets = tex_offsets;
+			/* Need to set interpolation so that tex_alloc() will treat
+			 * tex_offsets as a image instead of data texture. */
+			tex_offsets->interpolation = img->interpolation;
+
+			thread_scoped_lock device_lock(device_mutex);
+			tex_img->copy_to_device();
+			tex_offsets->copy_to_device();
+		}
+	}
 
 	img->need_load = false;
 }
@@ -902,7 +1045,7 @@ void ImageManager::device_update(Device *device,
 				device_free_image(device, (ImageDataType)type, slot);
 			}
 			else if(images[type][slot]->need_load) {
-				if(!osl_texture_system || images[type][slot]->builtin_data)
+				if(!osl_texture_system || images[type][slot]->builtin_data) {
 					pool.push(function_bind(&ImageManager::device_load_image,
 					                        this,
 					                        device,
@@ -910,6 +1053,7 @@ void ImageManager::device_update(Device *device,
 					                        (ImageDataType)type,
 					                        slot,
 					                        &progress));
+				}
 			}
 		}
 	}
@@ -934,12 +1078,13 @@ void ImageManager::device_update_slot(Device *device,
 		device_free_image(device, type, slot);
 	}
 	else if(image->need_load) {
-		if(!osl_texture_system || image->builtin_data)
+		if(!osl_texture_system || image->builtin_data) {
 			device_load_image(device,
 			                  scene,
 			                  type,
 			                  slot,
 			                  progress);
+		}
 	}
 }
 
diff --git a/intern/cycles/render/image.h b/intern/cycles/render/image.h
index 5391490d993..0b493110076 100644
--- a/intern/cycles/render/image.h
+++ b/intern/cycles/render/image.h
@@ -24,6 +24,7 @@
 #include "util/util_string.h"
 #include "util/util_thread.h"
 #include "util/util_vector.h"
+#include "util/util_sparse_grid.h"
 
 CCL_NAMESPACE_BEGIN
 
@@ -34,7 +35,7 @@ class Scene;
 class ImageMetaData {
 public:
 	/* Must be set by image file or builtin callback. */
-	bool is_float, is_half;
+	bool is_float, is_half, is_volume;
 	int channels;
 	size_t width, height, depth;
 	bool builtin_free_cache;
@@ -151,6 +152,15 @@ private:
 	                     int texture_limit,
 	                     device_vector<DeviceType>& tex_img);
 
+	template<TypeDesc::BASETYPE FileFormat,
+	         typename StorageType,
+	         typename DeviceType>
+	bool file_load_image(Image *img,
+	                     ImageDataType type,
+	                     int texture_limit,
+	                     device_vector<SparseTile>& tex_img,
+	                     device_vector<int>& tex_offsets);
+
 	int max_flattened_slot(ImageDataType type);
 	int type_index_to_flattened_slot(int slot, ImageDataType type);
 	int flattened_slot_to_type_index(int flat_slot, ImageDataType *type);
diff --git a/intern/cycles/util/CMakeLists.txt b/intern/cycles/util/CMakeLists.txt
index 3b690860d53..940e9d0441e 100644
--- a/intern/cycles/util/CMakeLists.txt
+++ b/intern/cycles/util/CMakeLists.txt
@@ -18,6 +18,7 @@ set(SRC
 	util_path.cpp
 	util_string.cpp
 	util_simd.cpp
+	util_sparse_grid.cpp
 	util_system.cpp
 	util_task.cpp
 	util_thread.cpp
@@ -78,6 +79,7 @@ set(SRC_HEADERS
 	util_sky_model.h
 	util_sky_model_data.h
 	util_avxf.h
+	util_sparse_grid.cpp
 	util_sseb.h
 	util_ssef.h
 	util_ssei.h
diff --git a/intern/cycles/util/util_math_int4.h b/intern/cycles/util/util_math_int4.h
index 79a8c0841e7..502e77cee72 100644
--- a/intern/cycles/util/util_math_int4.h
+++ b/intern/cycles/util/util_math_int4.h
@@ -28,6 +28,9 @@ CCL_NAMESPACE_BEGIN
  */
 
 #ifndef __KERNEL_GPU__
+ccl_device_inline bool operator==(const int4& a, const int4& b);
+ccl_device_inline bool operator!=(const int4& a, const int4& b);
+ccl_device_inline bool operator<(const int4& a, const int4& b);
 ccl_device_inline int4 operator+(const int4& a, const int4& b);
 ccl_device_inline int4 operator+=(int4& a, const int4& b);
 ccl_device_inline int4 operator>>(const int4& a, int i);
@@ -42,6 +45,21 @@ ccl_device_inline int4 select(const int4& mask, const int4& a, const int4& b);
  */
 
 #ifndef __KERNEL_GPU__
+ccl_device_inline bool operator==(const int4& a, const int4& b)
+{
+	return a.x == b.x && a.y == b.y && a.z == b.z && a.w == b.w;
+}
+
+ccl_device_inline bool operator!=(const int4& a, const int4& b)
+{
+	return !(a == b);
+}
+
+ccl_device_inline bool operator<(const int4& a, const int4& b)
+{
+	return a.x < b.x && a.y < b.y && a.z < b.z && a.w < b.w;
+}
+
 ccl_device_inline int4 operator+(const int4& a, const int4& b)
 {
 #ifdef __KERNEL_SSE__
diff --git a/intern/cycles/util/util_sparse_grid.cpp b/intern/cycles/util/util_sparse_grid.cpp
new file mode 100644
index 00000000000..e5ae32b3f78
--- /dev/null
+++ b/intern/cycles/util/util_sparse_grid.cpp
@@ -0,0 +1,174 @@
+/*
+ * Copyright 2011-2018 Blender Foundation
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include "util/util_sparse_grid.h"
+#include "util/util_math.h"
+
+/* Functions to help generate and handle Sparse Grids. */
+
+CCL_NAMESPACE_BEGIN
+
+int compute_index(int x, int y, int z, int width, int height, int depth, int min)
+{
+    if(x < min || y < min || z < min || x >= width || y >= height || z >= depth) {
+		return min-1;
+    }
+	return x + width * (y + z * height);
+}
+
+int3 compute_coordinates(int index, int width, int height, int depth, int min)
+{
+    if(index < min || index >= width * height * depth) {
+		return make_int3(min-1, min-1, min-1);
+    }
+    int x = index % width;
+    int y = (index / width) % height;
+    int z = index / (width * height);
+    return make_int3(x, y, z);
+}
+
+int compute_tile_resolution(int res)
+{
+    if(res % TILE_SIZE == 0) {
+        return res / TILE_SIZE;
+    }
+    return res / TILE_SIZE + 1;
+}
+
+bool is_active(const int *offsets,
+               size_t x, size_t y, size_t z,
+               size_t width, size_t height, size_t depth)
+{
+    if(offsets == NULL)
+        return false;
+    int tile_width = compute_tile_resolution(width);
+    int tile_height = compute_tile_resolution(height);
+    int tile_depth = compute_tile_resolution(depth);
+    int tile_index = compute_index(x/TILE_SIZE, y/TILE_SIZE, z/TILE_SIZE,
+                                   tile_width, tile_height, tile_depth);
+    if(tile_index < 0 || tile_index > tile_width*tile_height*tile_depth)
+        return false;
+    int grid_index = offsets[tile_index];
+    return (grid_index >= 0 && grid_index < width*height*depth);
+}
+
+float4 get_value(const SparseTile *grid, const int *offsets,
+                 size_t x, size_t y, size_t z,
+                 size_t width, size_t height, size_t depth)
+{
+    if(offsets == NULL) {
+        return make_float4(0.0f);
+    }
+    int tile_width = compute_tile_resolution(width);
+    int tile_height = compute_tile_resolution(height);
+    int tile_depth = compute_tile_resolution(depth);
+    /* Get the 1D array tile index of the tile the voxel (x, y, z) is in. */
+    int tile_index = compute_index(x/TILE_SIZE, y/TILE_SIZE, z/TILE_SIZE,
+                                   tile_width, tile_height, tile_depth);
+    if(tile_index < 0 || tile_index > tile_width*tile_height*tile_depth) {
+        return make_float4(0.0f);
+    }
+    /* Get the index of the tile in the sparse grid. */
+    int grid_index = offsets[tile_index];
+    if (grid_index < 0 || grid_index > width*height*depth) {
+        return make_float4(0.0f);
+    }
+    /* Get tile and look up voxel in tile. */
+    int voxel_index = compute_index(x%TILE_SIZE, y%TILE_SIZE, z%TILE_SIZE);
+    return grid[grid_index].values[voxel_index];
+}
+
+float4 get_value(const SparseTile *grid, const int *offsets,
+                 size_t tile_index,
+                 size_t width, size_t height, size_t depth)
+{
+    int3 c = compute_coordinates(tile_index, width, height, depth);
+    return get_value(grid, offsets, c.x, c.y, c.z, width, height, depth);
+}
+
+int create_sparse_grid(float4 *dense_grid,
+                       const size_t width,
+                       const size_t height,
+                       const size_t depth,
+                       vector<SparseTile> *sparse_grid,
+                       vector<int> *offsets)
+{
+
+    /* Resize vectors to tiled resolution. */
+    int active_tile_count = 0;
+    int total_tile_count = compute_tile_resolution(width) *
+                           compute_tile_resolution(height) *
+                           compute_tile_resolution(depth);
+    /* Overalloc 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;
+
+    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 tile;
+                bool 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) {
+                            int index = compute_index(i, j, k, width, height, depth);
+                            if(index < 0) {
+                                /* Out of bounds of original image, store an empty voxel. */
+                                tile.values[c] = make_float4(0.0f);
+                            }
+                            else {
+                                tile.values[c] = dense_grid[index];
+                                if(is_empty) {
+                                    if(dense_grid[index].x > 0.0f ||
+                                       dense_grid[index].y > 0.0f ||
+                                       dense_grid[index].z > 0.0f ||
+                                       dense_grid[index].w > 0.0f) {
+                                        /* All values are greater than the threshold. */
+                                        is_empty = false;
+                                    }
+                                }
+                            }
+                            ++c;
+                        }
+                    }
+                }
+
+                /* Add tile if active. */
+                if(is_empty) {
+                    (*offsets)[total_tile_count] = -1;
+                }
+                else {
+                    (*sparse_grid)[active_tile_count] = tile;
+                    (*offsets)[total_tile_count] = active_tile_count;
+                    ++active_tile_count;
+                }
+                ++total_tile_count;
+            }
+        }
+    }
+
+    /* Return so that the parent function can resize
+     * sparse_grid appropriately. */
+    return active_tile_count;
+}
+
+CCL_NAMESPACE_END
diff --git a/intern/cycles/util/util_sparse_grid.h b/intern/cycles/util/util_sparse_grid.h
new file mode 100644
index 00000000000..cf94dcd62b1
--- /dev/null
+++ b/intern/cycles/util/util_sparse_grid.h
@@ -0,0 +1,66 @@
+/*
+ * Copyright 2011-2017 Blender Foundation
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#ifndef __UTIL_SPARSE_GRID_H__
+#define __UTIL_SPARSE_GRID_H__
+
+#include "util/util_types.h"
+#include "util/util_vector.h"
+
+CCL_NAMESPACE_BEGIN
+
+static const int TILE_SIZE = 8;
+
+struct SparseTile {
+    float4 values[TILE_SIZE * TILE_SIZE * TILE_SIZE];
+};
+
+int compute_index(int x, int y, int z,
+                  int width=TILE_SIZE,
+                  int height=TILE_SIZE,
+                  int depth=TILE_SIZE,
+                  int min=0);
+
+int3 compute_coordinates(int index,
+                         int width=TILE_SIZE,
+                         int height=TILE_SIZE,
+                         int depth=TILE_SIZE,
+                         int min=0);
+
+int compute_tile_resolution(int res);
+
+bool is_active(const int *offsets,
+               size_t x, size_t y, size_t z,
+               size_t width, size_t height, size_t depth);
+
+int create_sparse_grid(float4 *dense_grid,
+                       const size_t width,
+                       const size_t height,
+                       const size_t depth,
+                       vector<SparseTile> *sparse_grid,
+                       vector<int> *offsets);
+
+float4 get_value(const SparseTile *grid, const int *offsets,
+                 size_t x, size_t y, size_t z,
+                 size_t width, size_t height, size_t depth);
+
+float4 get_value(const SparseTile *grid, const int *offsets,
+                 size_t tile_index,
+                 size_t width, size_t height, size_t depth);
+
+CCL_NAMESPACE_END
+
+#endif /*__UTIL_SPARSE_GRID_H__*/
diff --git a/intern/cycles/util/util_texture.h b/intern/cycles/util/util_texture.h
index 4b5f630427d..a747d783009 100644
--- a/intern/cycles/util/util_texture.h
+++ b/intern/cycles/util/util_texture.h
@@ -53,6 +53,7 @@ typedef enum ImageDataType {
 	IMAGE_DATA_TYPE_FLOAT = 3,
 	IMAGE_DATA_TYPE_BYTE = 4,
 	IMAGE_DATA_TYPE_HALF = 5,
+	IMAGE_DATA_TYPE_VOLUME = 6,
 
 	IMAGE_DATA_NUM_TYPES
 } ImageDataType;
@@ -77,6 +78,10 @@ typedef enum ExtensionType {
 typedef struct TextureInfo {
 	/* Pointer, offset or texture depending on device. */
 	uint64_t data;
+	/* References the offsets for tiles in sparse volumes. */
+	uint64_t offsets;
+	/* Dummy member to keep sizeof(TextureInfo) divisible by 16. */
+	uint64_t pad;
 	/* Buffer number for OpenCL. */
 	uint cl_buffer;
 	/* Interpolation and extension type. */