copying a vector<vector<vector<bool> > > container

[TheDestroyer]

Hello programmers,

I'm working on discretising continuous shapes into a 3D image, and for this I'm using some math to transform mathematical planes into black and white pixels, so every pixel takes the value 0 or 1 in a 3D map (3D image) according to some mathematical criterion.

The problem is the following: in a specific method, I need to copy a small vector<vector<vector<bool> > > map (size:50x50x50) to a bigger one (size:1000x1000x1000), and the copying should be done with the OR gate, so the copy process may look like this:

for(i=0;i<small_map.size;i++)
for(j=0;j<small_map[i].size;j++)
for(k=0;k<small_map[i][j].size;k++)
{
    big_map[x+i][y+j][z+k] = big_map[x+i][y+j][z+k] || small_map[i][j][k];
}

where x,y,z are variables that determine the position of the new shape to be inserted in the big image.
This process is successful, but it's very slow that it becomes totally inefficient.

The question is: is there a way to do this copying more efficiently?

Any efforts are highly appreciated.
Thank you

[imi]

I remember I read somewhere that vector<bool> was evil and a big failure and that if the C++ comitee could turn back the time they would never haved defined it as it is defined now. IIRC, it boils down to the fact that vector<bool>::value_type is not a bool and so vector<bool> is actually not a valid STL container.

Use std::bitset (if you know at compile time how big it will be) or boost::dynamic_bitset.


Ciao, Imi.

[TheDestroyer]

Thank you for your answer :).

Actually I know this issue of vector<bool>, but so far I'm not involved in the iterators of those vectors, and therefore there's not problem with them.

But the question is still there. Is there a way, or let's say another type, that could help me making this copy process faster and more efficient?

Thank you!

[jsmith]

The problem is that you have a gazillion memory accesses and computations to do.

bitset does not seem to be flexible enough to allow you to easily reduce the number of memory
accesses. (It allows you, for example, to OR together two bitsets, but both bitsets have to be
the same size).

What you might consider doing is flattening your 3D data structure into a 1D data structure and
using, say, vector<uint32_t>, which would allow you to process 32 bits at a time.

[TheDestroyer]

I thought about this, but how will this benefit me?
Imagine that you have an image that has a boundary start in the middle of my 32-bit integer relative to my big image, this means I'll have to shift every integer in the small image 16 bits in order to fit my big image in the correct position besides that I have to copy the shifted bits to the next integer, I guess this would take some very good amount if time, right?

Is there a smart way to do this shift?

and will it be possible to apply the OR gate on those integers? I guess this isn't a big problem, is it?

Thank you :)

[imi]

Actually I know this issue of vector<bool>, but so far I'm not involved in the iterators of those vectors, and therefore there's not problem with them.

I wouldn't bet on that. The STL could use iterators internally at some point.

With your construct, it definetely can't do any bitwise OR operations on whole bytes (let alone whole integers, which would be fastest). Instead, it constructs an awefull lot of proxy classes - one for each *bit*.


Ciao, Imi.

[TheDestroyer]

Thank you Imi for your answer.

But as I mentioned before, using an integer will hinder setting the correct position of the small image on the big one, imagine that the position of the small image in the big one is not a multiple of the bits-size of my integer, this means I'll have to shift my small image by some bits at every boundary integer before copying it, a process that'll take a long time, right?

Is what I said clear? I'm afraid not... please tell me if it's not.

Is there a solution for this?

Thank you :)

[jsmith]

What it sounds to me like you are trying to do is essentially a blit. If so, I would search
the 'net for code that does blits.