Recursive splitting of 3D binary array to create bitstream for every entry that equals 1

Question

I'm trying to split a binary (only elements are 0 and 1) dynamically-allocated 3D array into seperate and smaller 3D arrays. The following figure makes it a bit clearer to understand:

http://img521.imageshack.us/img521/4296/splittingsteps.png

It's a sparse 3D array of 10.000 elements. For each 1 that is an element of my array, I want to create a unique bitstream. The obtained subdomains return me a number of 1s that are in the corresponding block. That number is then converted to binary and added to the bitstream.

Since this splitting operation is the same every time, first splitting in the i direction, then in the j direction and then in the k direction (3 levels) I want to do this recursively. Also, since I'm working in ANSI C, working non recursively would result in a huge amount of duplicate code.

The splitting should terminate at subdomains that are empty, so only containing 0 (number_x =0) or when the size is [0..1] x [0..1] x [0]. These subdomains are handled by a Huffman code.

More specifically, it's a 3D array with starting dimensions:

I = [0 .. 511] x [0 .. 511] x [0 .. 31] 

My current code for the first three levels can be found at http://codepad.org/zGbAhKrC

Split level #1 results in two 3D arrays of dimensions:

I_w = [0 .. 255] x [0 .. 511] x [0 .. 31]
I_e = [256 .. 511] x [0 .. 511] x [0 .. 31]

number_w = 6505 and number_e = 3495 represent the number of 1's in both parts.

Split level #2 results in four 3D arrays of dimensions:

I_sw = [0 .. 255] x [0 .. 255] x [0 .. 31]
I_nw = [0 .. 255] x [256 .. 511] x [0 .. 31]
I_se = [256 .. 511] x [0 .. 255] x [0 .. 31]
I_ne = [256 .. 511] x [256 .. 511] x [0 .. 31]

number_sw = 2141 and number_nw = 4364 represent the number of 1's in the corresponding block. number_se = 1745 and number_ne = 1750 represent the number of 1's in the corresponding block.

Split level #3 results in eight 3D arrays of dimensions:

I_swm = [0 .. 255] x [0 .. 255] x [0 .. 15]
I_nwm = [0 .. 255] x [256 .. 511] x [0 .. 15]
I_swp = [0 .. 255] x [0 .. 255] x [16 .. 31]
I_nwp = [0 .. 255] x [256 .. 511] x [16 .. 31]
I_sem = [256 .. 511] x [0 .. 255] x [0 .. 15]
I_nem = [256 .. 511] x [256 .. 511] x [0 .. 15]
I_sep = [256 .. 511] x [0 .. 255] x [16 .. 31]
I_nep = [256 .. 511] x [256 .. 511] x [16 .. 31]

number_swm = 2141 and number_swp = 0 represent the number of 1s in the corresponding block. number_nwm = 4364 and number_nwp = 0 represent the number of 1s in the corresponding block. number_sem = 1745 and number_sep = 0 represent the number of 1s in the corresponding block. number_nem = 1750 and number_nep = 0 represent the number of 1s in the corresponding block.

Anyone who can help me with some pseudo code based on my current code?

Thanks in advance!

Answer 1

Have a look at the kd-tree examples in wikipedia.