Hello, I need help with the code to determine how I can grab (well call them chunks) 32x32 squares of data from a std::vector<float>


So say my array holds 128*128 amount of values

i want to grab the chunks from that array such as this

see crappy art link





I want the white and black squares to be say 32x32 chunks and I need to iterate over each 32x32 and grab those values....

I been beating my head into the wall and can't get the logic down correctly, so I am guessing there probably is some lib or algorithm that does this kind of thing already... I hope.

Thanks!

If you want the values in each "chunk" to be contiguous, treat your data like a 2D array of 2D arrays:
array[4][4][32][32]
(The first [4][4] is the outer array and [32][32] is the inner array.)

You can achieve this access pattern in a 1D vector like this:
vector[(((yOuter * 4) + xOuter) * 4 + yInner) * 32 + xInner]

Walking through the array of arrays then looks like this:

for (int yOuter = 0; yOuter < 4; ++yOuter)
{
for (int xOuter = 0; xOuter < 4; ++xOuter)
{
for (int yInner = 0; yInner < 32; ++yInner)
{
for (int xInner = 0; xInner < 32; ++xInner)
{
float value = vector[(((yOuter * 4) + xOuter) * 4 + yInner) * 32 + xInner];
...
}
}
}
}


You can (and should!) optimize this but it shows how things work.

Thanks for the reply, that may end up being used, to what I need, but I must not have explained myself to well.

I need to jump chunk by chunk 32x32 at a time, but the values need to be like such

4096 - 4223 //32nd row
...//nth row
128 - 255//second row
0 - 127//first row

those numbers are first white square on that previous image checkerboard....

now when we start at 0 we run 32x32 which should have values from index in the vector of

these are the y axis if you will in the 2D image above
0-32//first row
128-160//second row
256-288//third row
ect.... up to the 32nd row

now we shift over on X to the black square and re run but start at index 32 and rerun again to
32-64//first row
160-192//second row
ect... repeat until first row is done now move up to the first black square and repeat for that row again.... for a total of 16 chunks....

Not sure if this is a better idea of what I am trying to do...

An outer loop to iterate over chunks and an inner loop to actually grab the chunk data. Unless someone beats me to the punch, I'll post some code in the morning when I'm at a keyboard rather than pecking away on a phone.

An outer loop to iterate over chunks and an inner loop to actually grab the chunk data. Unless someone beats me to the punch, I'll post some code in the morning when I'm at a keyboard rather than pecking away on a phone.

Thanks!!! appreciate it

I suspected that's what you wanted but I wasn't sure.

To achieve that access pattern:

for (int yOuter = 0; yOuter < 4; ++yOuter)
{
for (int xOuter = 0; xOuter < 4; ++xOuter)
{
for (int yInner = 0; yInner < 32; ++yInner)
{
for (int xInner = 0; xInner < 32; ++xInner)
{
float value = vector[((yOuter * 4 + yInner) * 32 + xOuter) * 4 + xInner]; ...
}
}
}
}

The nested loop structure is exactly the same as before; only the index calculation changed.

A simple optimization:

for (int yOuter = 0; yOuter < 128; yOuter += 32)
{
for (int xOuter = 0; xOuter < 128; xOuter += 32)
{
for (int yInner = yOuter; yInner < yOuter + 32; ++yInner)
{
for (int xInner = xOuter; xInner < xOuter + 32; ++xInner)
{
float value = vector[yInner * 128 + xInner];
...
}
}
}
}


I suspected that's what you wanted but I wasn't sure.

To achieve that access pattern:

for (int yOuter = 0; yOuter < 4; ++yOuter)
{
for (int xOuter = 0; xOuter < 4; ++xOuter)
{
for (int yInner = 0; yInner < 32; ++yInner)
{
for (int xInner = 0; xInner < 32; ++xInner)
{
float value = vector[((yOuter * 4 + yInner) * 32 + xOuter) * 4 + xInner]; ...
}
}
}
}

The nested loop structure is exactly the same as before; only the index calculation changed.

A simple optimization:

for (int yOuter = 0; yOuter < 128; yOuter += 32)
{
for (int xOuter = 0; xOuter < 128; xOuter += 32)
{
for (int yInner = yOuter; yInner < yOuter + 32; ++yInner)
{
for (int xInner = xOuter; xInner < xOuter + 32; ++xInner)
{
float value = vector[yInner * 128 + xInner];
...
}
}
}
}


I think we are on the right track, so thanks for sticking with me

I think the order of my chunks is wrong with that indexing formula? My patches aren't aligning correctly? Or it looks like the first 32x32 patch is the only one that is grabbed. I watch the two inner loops and the second time yInner is iterated the index value = 4 for the first point? Shouldn't that be 32 since my patchsize is 32... Any ideas?

Thanks!

Update:
Here is a link to the output

http://pastebin.com/gh0c91Q7

You can do it without the dual x and y loops by traversing the array linearly and using the modulus operator to get the y value of your 2d to linear address. So sorry, haven't had a chance to get at the computer so still pecking away on the phone but break the problem down like this: for each cell in your checker pattern (representing the chunks), jot down the indices needed for each cell (the chunk start index is the index of the first element of the chunk, conceptually in the top right corner, although of course such a notion doesn't exist in a linear array). This should give you an idea of the formula needed to calculate the start address of each chunk. With this known, you can derive a similar formula to iterate over the individual elements of a given chunk. Start with a 16x16 block of chunks where each chunk is a 4x4 set of elements (64x64 elements in total) and try to figure it out on paper. If you're still struggling by the time I get at my computer, I'll give you a hand and post up some source (I can't see the above source as it goes off my screen).

You can do it without the dual x and y loops by traversing the array linearly and using the modulus operator to get the y value of your 2d to linear address. So sorry, haven't had a chance to get at the computer so still pecking away on the phone but break the problem down like this: for each cell in your checker pattern (representing the chunks), jot down the indices needed for each cell (the chunk start index is the index of the first element of the chunk, conceptually in the top right corner, although of course such a notion doesn't exist in a linear array). This should give you an idea of the formula needed to calculate the start address of each chunk. With this known, you can derive a similar formula to iterate over the individual elements of a given chunk. Start with a 16x16 block of chunks where each chunk is a 4x4 set of elements (64x64 elements in total) and try to figure it out on paper. If you're still struggling by the time I get at my computer, I'll give you a hand and post up some source (I can't see the above source as it goes off my screen).

Ok, I posted a update to a link to see the data that is coming out of the loops. The first patch is fine, but I need to move over on X axis if you will, and start the 32x32 run again, but the value starts at 4 and not 32.... I think that is the problem but unsure but in my mind its not correct...

I haven't tested this code as I've just knocked it out now I'm on my desktop but it should work. I've done this sort of thing on a few occasions so I'm pretty sure it should work straight out of the box. This method has 4 loops, you can do it with 2 but for the sake of clarity stick with 4 for now. Let me know if you want me to elaborate on my code but bear in mind I'm heading out in a bit so it may be a few hours before I can get back to you. The 1st two loops (c_y and c_x) iterate over chunks whilst the inner two loops (e_x and e_y) iterate over the elements of a given chunk. Not that we start the e_y and e_x iterations at the chunk's 1st element (c_y and c_x). We then use the usual 2D to linear array formula to get the index of each element of a given chunk. This formula is y * width + x.


// Example metrics:
// Chunk width and height = 32 (32x32 collection of elements)
// Array width and height = 128 (128x128 collection of elements OR 4x4 collection of chunks)

// Iterate over the chunks. For the time being, we'll have an independent x and y loop
for(int c_y = 0; c_y < array_height; c_y += chunk_height)
{
for(int c_x = 0; c_x < array_width; c_x += chunk_width)
{
// Now we have the index of the 1st element of a given chunk, we can iterate over each element of the chunk
for(int e_y = c_y; e_y < c_y + chunk_height; e_y++)
{
for(int e_x = c_x; e_x < c_x + chunk_width; e_x++)
{
// The index of this element is as follows:
int element_index = e_y * array_width + e_x;
}
}
}
}


This code assumes that your elements are arranged in linear memory. The concept of chunks is purely conceptual, so as long as your elements are ordered like this: 0,1,2,3,4,5,6,7,8,9,10,11,12,13,etc. you should be fine. Ask if you want this clarified so we know we're reading off the same page