Sign in to follow this  
forsandifs

Proper UINT32 colour arithmetic

Recommended Posts

forsandifs    154
I have many divisions and additions of UINT32s in my program, where UINT32 represents a colour.

My problem is that my implementation is very naive. If I want to halve the magnitude of all the colours represented by the UINT32 I simply do Colour / 2... And if I want to add two colours together I simply do Colour1 + Colour2...

This works up to a point, but not sufficiently well. In many cases where the scene is supposed to be greyscale throughout, I get undesired colours appearing like blues and greens, which suggests a colour shift due to the method of colour addition and subtraction I am using being inadequate.

How do I properly divide and add the colour values of UINT32s?

Share this post


Link to post
Share on other sites
D_Tr    362
Why don't you just use 4 bytes, one for each of R, G, B and A components? If you just divide the whole UINT32 with 2 then you shift all its bits one position to the right, so set bits can move to different channels and you don't want that. The same problem exists with addition and multiplication. If for whatever reason you cannot use 4 separate bytes, you can isolate each component with bitwise operations, perform arithmetic on each component separately, and then substitute the 8 bits of each component back to the UINT32 bit positions from where you extracted it. For example:


UINT32 color;
UINT32 c0 = color & 0x000000FF;
UINT32 c1 = (color & 0x0000FF00) >> 8;
UINT32 c2 = (color & 0x00FF0000) >> 16;
UINT32 c3 = (color & 0xFF000000) >> 24;

c0 = (c0 * 2) & 0x000000FF;
c1 = (c1 * 2) & 0x000000FF;
c2 = (c2 * 2) & 0x000000FF;
c3 = (c3 * 2) & 0x000000FF;

color = c0 | (c1 << 8) | (c2 << 16) | (c3 << 24);


You should wrap these bit-twiddling operations in functions though. This makes the calculations heavier though, so if you need more performance you can look at SSE instructions and their corresponding compiler instrinsics.

[Edited by - D_Tr on October 15, 2010 9:14:06 AM]

Share this post


Link to post
Share on other sites
forsandifs    154
Thank you very much.

I could probably use separate instances of a smaller data type to represent each colour component whilst performing the caluclations, however I would then need to convert those separate sata types into a UINT32.

If for example I were to use a float to describe the magnitude of each colour compenent, the arithmetic would become trivial, but how would I then convert those 3 floats, each represnting a colour component, into a UINT32?

Could I for instance use the D3DXColor structure and then simply cast it into UINT32 using (UINT32)Colour; ?

Share this post


Link to post
Share on other sites
D_Tr    362
Quote:
Original post by forsandifs
Could I for instance use the D3DXColor structure and then simply cast it into UINT32 using (UINT32)Colour; ?

Are you using C++? If yes, you can :)

Share this post


Link to post
Share on other sites
2square    129
If you want to do the calculations yourself, it's pretty easy too


float r, g, b, a;
unsigned int packedColor = 0;

packedColor = (packedColor | (unsigned int)r*255) << 8;
packedColor = (packedColor | (unsigned int)g*255) << 8;
packedColor = (packedColor | (unsigned int)b*255) << 8;
packedColor = (packedColor | (unsigned int)a*255);



You basically need to convert from float to UINT32 by multiplying by 255 (Note: you'll lose some precision due to rounding). After that you pack it into a UINT32 using some bitwise arithmetic.

Share this post


Link to post
Share on other sites
deathkrush    350
Here is multi-byte addition (from the Hacker's Delight book)


unsigned int MultibyteAdd( unsigned int a, unsigned int b )
{
unsigned int s = ( x & 0x7f7f7f7f ) + ( y & 0x7f7f7f7f );
s = ( x + y ) & 0x80808080 + s;
return s;
}



Division and multiplication is more complicated but for the special cases of dividing or multiplying by a power of two you can use shift operators. The problem is that when bits overflow from one element to another you have a bug. The safest thing is to convert each component to float, do your math and convert it back to a packed integer. This will work safely for all arithmetic operations.

Share this post


Link to post
Share on other sites
forsandifs    154
Thank you very much guys. :)

I ended up getting it work by doing all the calculations with D3DXCOLOR but then converting appropriately to UINT32 by using the very useful D3DCOLOR_COLORVALUE macro provided by DirectX like D3DCOLOR_COLORVALUE( D3DXCOLOR1.r, D3DXCOLOR1.g, D3DXCOLOR1.b, D3DXCOLOR1.a ); This macro returns a correct UINT32 value of a colour defined by a float for each component.

Simply casting from D3DXCOLOR to UINT32 can sometimes introduce very significant error.

Share this post


Link to post
Share on other sites
popsoftheyear    2194
Quote:
Original post by deathkrush
Here is multi-byte addition (from the Hacker's Delight book)

*** Source Snippet Removed ***

Division and multiplication is more complicated but for the special cases of dividing or multiplying by a power of two you can use shift operators. The problem is that when bits overflow from one element to another you have a bug. The safest thing is to convert each component to float, do your math and convert it back to a packed integer. This will work safely for all arithmetic operations.


That doesn't work.
If 0x00000040 and 0x00000040 were added together, you'd get 0x00000100 with that function, I do believe (please correct me if I'm wrong!!)

I don't have Hacker's Delight unfortunately, but would this work?
unsigned int MultibyteAdd( unsigned int a, unsigned int b )
{
unsigned int s = ( x & 0x7f7f7f7f ) + ( y & 0x7f7f7f7f );
s = (( x + y ) & 0x80808080) | s;
return s;
}

Share this post


Link to post
Share on other sites
deathkrush    350
Whoops, I misinterpreted the funky notation in the book. This should work:


unsigned int MultibyteAdd( unsigned int x, unsigned int y )
{
unsigned int s = ( x & 0x7f7f7f7f ) + ( y & 0x7f7f7f7f );
s = ( ( x ^ y ) & 0x80808080 ) ^ s;
return s;
}


Share this post


Link to post
Share on other sites
unai    122
I implemented this loong time ago... may be of interest for you.

http://www.flipcode.com/archives/Color_Manipulation.shtml


Hoppe this helps,

Unai.

Share this post


Link to post
Share on other sites
JNT    148
Would it not be possible to store results in tables, such as multiplication, addition and subtraction tables? These could then be used to store precomputed, saturated results from color operations. They would be quite big (256*256 bytes each), but I suppose that should not be a problem.

Share this post


Link to post
Share on other sites
JNT    148
Quote:
Original post by Ohforf sake
Actually 128 TB is more than quite big. At least if you want to store all combinations.

For a simple software graphics engine I wrote a while back, I used 256*256 bytes to store a single type of table, but only 3 tables; one for +, one for -, one for *. That's about 200 kb.

I must ask, what combinations are you referring to that would occupy 128 TB?

Share this post


Link to post
Share on other sites
unai    122
If you want to go on the table way, you dont need so big tables, as;
a + b = b + a
a * b = b * a

You don`t need 256*256 values 512 entry table is enough an you index it always with (a+b)

Unai.

Share this post


Link to post
Share on other sites
JNT    148
Quote:
Original post by unai
If you want to go on the table way, you dont need so big tables, as;
a + b = b + a
a * b = b * a

Yes, good point. However, that would need a min/max calculation, no? That is, in part, what one would want to get away from by using the tables in the first place. Maybe there's some performance trade-off I'm not aware of when using larger tables?

Share this post


Link to post
Share on other sites
Ohforf sake    2052
Is a lookup really faster than a simple add and maybe an max?
I don't think the L1 can hold 200kB, especially with the actual bitmap data streaming through. And even with enough temporal coherence on the operands, you would still have the indirection addition (one add micro op there) and the L1 lookup which I suspect to be slower than a max operation.
Also note that if the table just covers byte operations you still need to do the mask/shift operations.

I thought you wanted to create a table for all color components (24 bits x 24 bits) which even with the mirror trick gets insanely huge.

Share this post


Link to post
Share on other sites
D_Tr    362
It really pays off to learn using the SSE intrinsics (or SSE inline assembly) in these cases. I am using a Core 2 Duo and I can alpha blend 16 pairs of bytes in 8 cycles, using the PAVGB instruction 8 times. The algorithm was easy to write and its speed was limited by the rate at which the CPU could read the two byte arrays and store the result array. Even older MMX instructions can provide great speed ups without disturbing the cache with look-up tables. There are MMX instructions to do 8 8-bit adds in parallel (signed or unsigned) and also MMX instructions to do 4 16 bit multiplies in parallel. You can also do saturated additions and subtractions (not sure about multiplications). MMX and SSE instrinsics are available in header files that are the same accross the 3 major C++ compilers (Intel, GCC, MS)

Share this post


Link to post
Share on other sites
JNT    148
Quote:
Original post by Ohforf sake
Is a lookup really faster than a simple add and maybe an max?
I don't think the L1 can hold 200kB, especially with the actual bitmap data streaming through. And even with enough temporal coherence on the operands, you would still have the indirection addition (one add micro op there) and the L1 lookup which I suspect to be slower than a max operation.


Yes, these are all valid concerns. And they may very well be true. But doing min/max against 0 and 255 for an unsigned char would also require converting the types to a larger format (such as a short) in order to avoid testing min/max against a wrapped value, so there would be some overhead to consider there as well. It could still be faster doing calculations without tables though.

At least, it would seem that, for some tests I have done, that the trade-off in performance is small.

Quote:
Original post by Danny02
why not use a union?

This is a quite elegant solution that I also would recommend.


union color32 {
unsigned int full;
struct {
unsigned char b, g, r, a; // depends on endianness though
} chan;
};

Share this post


Link to post
Share on other sites

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