An adaptive, hybrid data structure for sparse volume data on the GPU

Abstract

Dealing with large, sparse, volume data on the GPU is a necessity in many applications such as volume rendering, processing or simulation. The limited memory budget of modern GPUs restricts users from uploading large volume data sets entirely. Fortunately, sparse data, i.e. data containing large empty regions, can be represented more efficiently compared to a common dense array. Our approach makes it possible to upload a full data set even if the original volume does not fit on the GPU. In previous work, a variety of sparse data structures have been utilized on the GPU, each with different properties. Tree representations, such as the octree, kd tree or N3 tree, provide a hierarchical solution for data sets of relatively low sparsity. For data sets of medium sparsity, spatial hashing makes more efficient access and storage possible. Extremely sparse data can be efficiently represented and accessed via binary search in sorted voxel lists. Our observation is, that data sets often contain regions of different sparsity. Depending on the sparsity of a region, a specific data structure (e.g., an octree, a voxel list) requires the least memory to store the data. We formulate an algorithm that is able to automatically find this memory optimal representation. By using such a combination of different data structures, we achieve an even better representation than any single data structure for real world data sets. We call such a data structure a hybrid data structure. Any sparse data structure introduces an access overhead. For example, the access to an octree requires one additional indirection per height level of the tree. A voxel list has to be searched to retrieve a specific element. By using a hybrid data structure, we also introduce an access overhead on top of the overhead that comes from using a sparse data structure. In our work we introduce JiTTree, which utilizes a data aware just-in-time compilation step to improve the access performance of our hybrid data structure. We show that the implementation of our hybrid data structure effectively reduces the memory requirement of sparse data sets. JiTTree can improve the performance of hybrid bricking for certain access patterns such as stencil access.