Sign in to follow this  

Bitmasks

This topic is 4242 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hello! What would be the best way to implement a bitmask in C++? How should I store the data? I was thinking that I should use a dynamic array of a simple data type and then provide methods that make it easy to get/set the bits. One idea I had was to first make a Byte object that would provide bit setting functionality. A Bitmask could store an array of Bytes of the appropriate size. Does this sound reasonable? I want to be able to have my Sprite objects generate a Bitmask whenever they're modified in a meaningful way, i.e. stretched or rotated, so that I can perform quick pixel-by-pixel collision detection. Bitmask objects could provide a method for checking for a collision, provided another Bitmask and some coordinates. Does this make sense? Any help, code, or suggestions are appreciated! Thanks!

Share this post


Link to post
Share on other sites

bool IsBitSet(unsigned long value, int bitIndex)
{
return (value & (1 << bitIndex)) != 0; // bitIndex [0,31].
}


Don't make a byte object, make a dword object, four times a byte so it's basically four times faster :). Bitmasking is common on 2D pixelperfect collision checks, but if your images are very large (like, dunno, 300x300 pixels or bigger), the check might be awfully slow even with SIMD instructions.(of course depending on the shape of the objects itself) In that case, you might want to create a vector shape of the object (which as an added bonus is easy to rotate and scale).

Share this post


Link to post
Share on other sites
Eep... That function'll be really inefficient if you're going to use it in per-pixel collision detection (with overhead and such). Use inlines or macros if it's going to be in a large loop.

Wait, are you going to use individual bits? If so, I wouldn't suggest it. It'll probably cost you more in run-time when you have to execute multiple bit-wise shifts for each pixel. Just store them as a pixel-per-byte (or dword, whichever alignment allows for faster operations). It makes everything a lot more simple.
And to check if they are set:
if (srcA[index] & srcB[index]) ... //Automatically checks if greater than 0


I've posted my algoritm here, but it's not going to be the fastest.
Plus, it goes into the nitty gritty (well, the gritty-ness) of calculating a box to find the 'critical area' in the collision.

Share this post


Link to post
Share on other sites
Thanks for the replies. :-)

So, if I understand this correctly, I shouldn't bother with manipulating individual bits? I thought this may be a good idea because it would simply save space in memory, i.e. one bit per pixel rather than one/two/four byte(s) per pixel. I guess it really wouldn't matter given that machines today have plenty 'o memory.

Would bitmasks be too slow for images larger than ~300x300 pixels? A vectorized mask would be great to work with, but creating an algorithm to vectorize images when they're loaded seems... daunting. :-P Maybe a file could be included that stores vector information.

Share this post


Link to post
Share on other sites
Quote:
So, if I understand this correctly, I shouldn't bother with manipulating individual bits? I thought this may be a good idea because it would simply save space in memory, i.e. one bit per pixel rather than one/two/four byte(s) per pixel. I guess it really wouldn't matter given that machines today have plenty 'o memory.

Yep. I had tried this before, and then decided that 8x the number of bytes of memory is trivial compared to the calculations that had to take place in order to check one bit.

Quote:
Would bitmasks be too slow for images larger than ~300x300 pixels? A vectorized mask would be great to work with, but creating an algorithm to vectorize images when they're loaded seems... daunting. :-P Maybe a file could be included that stores vector information.

Simply depends on the efficiency of your engine... Now, what you would need a 300x300 pixel-precise collision check for, I don't know. If you're going to use it as landscape, I'd suggest using tiling.
If it it is for a large enemy or what not, you can try the vectorized mask (something I still need to try) or you can 'cheat' and create large 'general' blocks to break the image down into to fewer amounts of sections, say 10x10 blocks. When loading, you can average the number of pixels on in that area, and then decide whether that area should be solid or not. Of course, collisions with this could look mighty odd... And calculating the bounds for collisions with more precise objects might be a little expensive too.

Share this post


Link to post
Share on other sites

This topic is 4242 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this