Parameterized Splitting of Summed Volume Tables

C. Reinbold¹, R. Westermann¹

¹Computer Graphics & Visualization Group, Technische Universität München, Germany

Schematic operation principle of splitting SVTs. A 3D array is hierarchically split into multiple high to low precision arrays (decreasing color saturation indicates decreasing precision), to obtain a data structure from which sums over axis-aligned subarrays can be computed. For the 641 x 9601 x 9601 input volume obtained by a supercomputer simulation of a Rayleigh–Bénard convection, the SVT requires 247.6GB. Our algorithm generates SVT representations at 27.0GB or 71.2GB, requiring respectively 46 or 8 data fetch operations per prefix sum.

Abstract

Summed Volume Tables (SVTs) allow one to compute integrals over the data values in any cubical area of a three-dimensional orthogonal grid in constant time, and they are especially interesting for building spatial search structures for sparse volumes. However, SVTs become extremely memory consuming due to the large values they need to store; for a dataset of n values an SVT requires O(n log n) bits. The 3D Fenwick tree allows recovering the integral values in O(log^3 n) time, at a memory consumption of O(n) bits. We propose an algorithm that generates SVT representations that can flexibly trade speed for memory: From similar characteristics as SVTs, over equal memory consumption as 3D Fenwick trees at significantly lower computational complexity, to even further reduced memory consumption at the cost of raising computational complexity. For a 641 X 9601 X 9601 binary dataset the algorithm can generate an SVT representation that requires 27.0GB and 46*8 data fetch operations to retrieve an integral value, compared to 27.5GB and 1521*8 fetches by 3D Fenwick trees, a decrease in fetches of 97%. A full SVT requires 247.6GB and 8 fetches per integral value. We present a novel hierarchical approach to compute and store intermediate prefix sums of SVTs, so that any prescribed memory consumption between O(n) bits and O(n log n) bits is achieved. We evaluate the performance of the proposed algorithm in a number of examples considering large volume data, and we perform comparisons to existing alternatives.

Associated publications

Parameterized Splitting of Summed Volume Tables

C. Reinbold, R. Westermann

Eurographics Conference on Visualization (EuroVis) 2021 [DOI] [PDF] [SUPP] [VIDEO] [BIB]

This is the accepted version of the following article: "Parameterized Splitting of Summed Volume Tables (Reinbold & Westermann, 2021)", which has been published in final form at onlinelibrary.wiley.com. This article may be used for non-commercial purposes in accordance with the

Wiley Self-Archiving Policy.