3D variant for summed area table (SAT)

Question

As per Wikipedia:

A summed area table is a data structure and algorithm for quickly and efficiently generating the sum of values in a rectangular subset of a grid.

For a 2D space a summed area table can be generated by iterating x,y over the desired range,

I(x,y) = i(x,y) + I(x-1,y) + I(x,y-1) - I(x-1,y-1)

And the query function for a rectangle corners A(top-left), B(top-right), C(bottom-right), D can be given by:-

I(C) + I(A) - I(B) - I(D)

I want to convert the above to 3D. Also please tell if any other method/data structure available for calculating partial sums in 3D space.

Answer 1

I'm not sure but something like the following can be thought of. ( I haven't gone through the Wikipedia code )

For every coordinate (x,y,z) find the sum of all elements from (0,0,0) to this element.
Call it S(0,0,0 to x,y,z) or S0(x,y,z).
This can be easily built by traversing the 3D matrix once.

S0( x,y,z ) =  value[x,y,z] + S0(x-1,y-1,z-1) + 
               S0( x,y,z-1 ) + S0( x, y-1, z ) + S0( x-1, y, z ) 
               - S0( x-1, y-1, z ) - S0( x, y-1, z-1 ) - S0( x-1, y, z-1 )

(basically element value + S0(x-1,y-1,z-1) + 3 faces (xy,yz,zx) )

Now for every query (x1,y1,z1) to (x2,y2,z2), first convert the coordinates so that x1,y1,z1 is the corner of the cuboid closest to origin and x2,y2,z2 is the corner that is farthest from origin.

S( (x1,y1,z1) to (x2,y2,z2) ) = S0( x2,y2,z2 ) - S0( x2, y2, z1 ) 
                                - S0( x2, y1, z2 ) - S0( x1, y2, z2 )
                                + S0( x1, y1, z2 ) + S0( x1, y2, z1 ) + S0( x2, y1, z1 )
                                - S0( x1, y1, z1 )

(subject to corrections)

Answer 2

A bit late to the party, but anyway. There is a general formula for n-dimensional space in Wikipedia, presented in this paper. Following that notation, we assume that you are interested in the volume specified by a rectangular box with corners (x0,y0,z0) and (x1,y1,z1). Then, having an integral image (volume), the coefficients would be: S((x0,y0,z0) to(x1,y1,z1)) = S(x1,y1,z1) - S(x1,y1,z0) - S(x1,y0,z1) + S(x1,y0,z0) - S(x0,y1,z1) + S(x0,y1,z0) + S(x0,y0,z1) - S(x0,y0,z0)

Here is matlab code I used to calculate them (can specify dimensionality)

%number of dimensions
nDim = 3;
for i=1:2^nDim
        str=dec2bin(i-1,nDim);
        strout='index combo (';
        sum=0;
        for n=1:nDim
            strout = strcat(strout,str(n));
            sum=sum + str2num(str(n));
        end
        strout = strcat(strout,') sign: ',num2str((-1)^(nDim-sum)));
        disp(strout);
end

which outputs:

(000) sign:-1
(001) sign:1
(010) sign:1
(011) sign:-1
(100) sign:1
(101) sign:-1
(110) sign:-1
(111) sign:1