Bitmasks
Author
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!
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).
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:
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.
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 0I'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.
Author
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.
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.
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
