TY - JOUR

T1 - Parameterized Splitting of Summed Volume Tables

AU - Reinbold, Christian

AU - Westermann, Rüdiger

N1 - Publisher Copyright:
© 2021 The Author(s) Computer Graphics Forum © 2021 The Eurographics Association and John Wiley & Sons Ltd. Published by John Wiley & Sons Ltd.

PY - 2021/6

Y1 - 2021/6

N2 - 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 (n log n) bits. The 3D Fenwick tree allows recovering the integral values in (log3 n) time, at a memory consumption of (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 × 9601 × 9601 binary dataset, the algorithm can generate an SVT representation that requires 27.0GB and 468 data fetch operations to retrieve an integral value, compared to 27.5GB and 15218 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 (n) bits and (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.

AB - 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 (n log n) bits. The 3D Fenwick tree allows recovering the integral values in (log3 n) time, at a memory consumption of (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 × 9601 × 9601 binary dataset, the algorithm can generate an SVT representation that requires 27.0GB and 468 data fetch operations to retrieve an integral value, compared to 27.5GB and 15218 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 (n) bits and (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.

KW - CCS Concepts

KW - • Human-centered computing → Scientific visualization

KW - • Information systems → Data structures

UR - http://www.scopus.com/inward/record.url?scp=85108862646&partnerID=8YFLogxK

U2 - 10.1111/cgf.14294

DO - 10.1111/cgf.14294

M3 - Article

AN - SCOPUS:85108862646

SN - 0167-7055

VL - 40

SP - 123

EP - 133

JO - Computer Graphics Forum

JF - Computer Graphics Forum

IS - 3

ER -