gbadev.org forum archive

This is a read-only mirror of the content originally found on forum.gbadev.org (now offline), salvaged from Wayback machine copies. A new forum can be found here.

DS development > A question about palettes and the .pcx loader

#59339 - SevenString - Mon Oct 31, 2005 6:51 pm

I don't want to report this as a bug because I'm betting that there is a very good reason for this, probably having to do with sprites and alpha or something similar.

However, for a while, it gave me some grief having dark holes in my pcx textures and images when I would load and display them.


In the file libnds\source\arm9\pcx.c, there are a couple of lines that read:

Code:
for(i = 0; i < 256; i++)
        image->palette[i] = RGB15((pal[i].r + 4) >> 3 ,(pal[i].g + 4) >> 3 , (pal[i].b + 4) >> 3) ;


The "+ 4" elements of the equation cause the palette RGB compnents to wrap around to dark values when that component is > 251.

If there IS a good reason for this, I can go back and clamp or remap my texture and image colors so that the values are never greater than 251 in RGB. However, for the short term, I simply changed the lines to read:

Code:
for(i = 0; i < 256; i++)
        image->palette[i] = RGB15(pal[i].r >> 3, pal[i].g >> 3, pal[i].b >> 3);


I've searched these forums, all the docs I can find, and the internet, and can't find anything on the subject. What am I missing?
_________________
"Artificial Intelligence is no match for natural stupidity."

#59340 - Mighty Max - Mon Oct 31, 2005 7:16 pm

There is a reason for it, yes :p

using only >>3 will round every value down. In the worst case it is producing a (value-7) >> 3

It would be much nearer to the color if you would round up when the upper gaussion of the division by 8 is nearer then the lower. Like rounding in decimal:

rounding 0.9 just by diving 10 is 0. rounding 0.9+0.5 (=1.4) is 1
rounding 0.4 just by diving 10 is 0. rounding 0.4+0.5 (=0.9) is 0

so that "+ half div value" is to increase accuracy. But yes, it should be clipped to vlaues 0-255.
_________________
GBAMP Multiboot

#59343 - SevenString - Mon Oct 31, 2005 7:30 pm

ach! <slaps self on the forehead> duh!

adding half of 8 because of the >> 3... I guess because I was obsessing over palettes and alphas, I was blind to the obvious.


Thanks, that makes total sense. I'll go ahead and change that line in my version of the library to read as something like:

Code:
image->palette[i] = RGB15((unsigned char)(min(((int)pal[i].r + 4), 255) >> 3), (unsigned char)(min(((int)pal[i].g + 4), 255) >> 3), (unsigned char)(min(((int)pal[i].b + 4), 255) >> 3))

_________________
"Artificial Intelligence is no match for natural stupidity."

#59356 - dovoto - Mon Oct 31, 2005 8:16 pm

SevenString wrote:
ach! <slaps self on the forehead> duh!



No need for that :) this is definatly a bug, I will correct when next I am at my PC. Thanks.

EDIT:

I dont suppose:

Code:
image->palette[i] = RGB15(((u16)pal[i].r + 4) >> 3 ,((u16)pal[i].g + 4) >> 3 , ((u16)pal[i].b + 4) >> 3) ;


Fixes it?
_________________
www.drunkencoders.com

#59597 - SevenString - Wed Nov 02, 2005 8:56 pm

I think that:

Code:
image->palette[i] = RGB15(((u16)pal[i].r + 4) >> 3 ,((u16)pal[i].g + 4) >> 3 , ((u16)pal[i].b + 4) >> 3) ;


fixes the wraparound, but would cause a different problem because you would still potentially have an extra bit at the top of one or more components.

For instance, if the red component were 255 (0x00ff), you would get:

0x00ff + 0x0004 = 0x0103 // EDITED TO AVOID FURTHER EMBARASSMENT
0x0103 >> 3 = 0x0020

if using RGB15 as currently defined in video.h ...

Code:
#define RGB15(r,g,b)  ((r)|((g)<<5)|((b)<<10))


you would get a corrupted lower bit of the green component, negating any advantage of the rounding technique in the first place.

One solution would be to use your new version of the palette constructor line, but modify the RGB15 macro definition to read something like:

Code:
#define RGB15(r, g, b)  (((r) & 0x001f) | (((g) & 0x001f) <<5 ) | (((b) & 0x001f) << 10))



or change the palette constructor to read:

Code:
image->palette[i] = RGB15((((u16)pal[i].r + 4) & 0x00ff) >> 3 ,(((u16)pal[i].g + 4) & 0x00ff) >> 3 , (((u16)pal[i].b + 4) & 0x00ff) >> 3);



However, IMO, changing the code at the RGB15 level may be preferable because it insures that ANY call to that lower-level macro is guaranteed to produce a result that can never have one RGB component "bleeding" into another.
_________________
"Artificial Intelligence is no match for natural stupidity."

Last edited by SevenString on Thu Nov 03, 2005 4:57 am; edited 2 times in total

#59654 - dovoto - Thu Nov 03, 2005 1:34 am

i am pretty sure 0x00ff + 4 = 0x0103
which when shifted by 3 is 0x0020
Or 32 in normal person numbers...this value would get masked to 0 or clamped to 31.

In all honesty the only way to do it properly (without roleover while maintaining rounding) is to clamp as you suggested in your first post...

Code:

u8 r = ((u16)pal[i].r + 4 < 256) ? pal[i].r += 4:255;
u8 g = ((u16)pal[i].g + 4 < 256) ? pal[i].g += 4:255;
u8 b = ((u16)pal[i].b + 4 < 256) ? pal[i].b += 4:255;

image->palette[i] = RGB15(r >> 3 , g >> 3 , b >> 3);


Changing RGB15() to mask values is something I considered doing when i wrote it.

While masking prevents bleedover, it does not prevent distortion of out of range values (32 becomes 0, 33 becomes 1, etc..). Since both cases (masking or not masking) result in unacceptable distortion of colors outside the 5 bit range I see no real advantage to either method.

Since masking incures a slight performance penelty I will leave it as is unless there is a convincing argument otherwise.

I will update the pcx loader to perform proper rounding with clamping, and thanks again for pointing out not only the bug but possible solutions.
_________________
www.drunkencoders.com

#59664 - SevenString - Thu Nov 03, 2005 4:54 am

yeah, 103 hex... must have had a post alchohol brain fart.

good point about the masking just bringing back the wraparound in that case.

as for the thanks, right back atcha for providing and supporting some cool tools!
_________________
"Artificial Intelligence is no match for natural stupidity."

#59681 - Mighty Max - Thu Nov 03, 2005 10:03 am

Code:

#define CLIP(x) ((x>255)?255:(x<0)?0:x)

image->palette[i] = RGB15(CLIP((u16)pal[i].r + 4) >> 3 ,CLIP((u16)pal[i].g + 4) >> 3 , CLIP((u16)pal[i].b + 4) >> 3) ;


Should do it
_________________
GBAMP Multiboot

#60345 - duencil - Wed Nov 09, 2005 12:01 pm

I'm pretty sure this rounding to nearest is a mistake. It might be useful to add half colours if we went the other way, promoting 15 bit colours up to 24 bit, so the end result doesn't look duller than the original.
Think about it a moment. We're mapping a 256 degree colour component down to 32 bands. If we use the "fractional add" we lose equal representation from the original set to the new set in all the bands.

I mean:
values 0-3 map to new band 0 (4 entries)
... intermediate values (8 entries/band)
values 244-255 map to new band 31 (12 entries)

Just do the shifts without an add, and rely on the hardware to make a good colour mapping in 15 bit.

#60348 - Mighty Max - Wed Nov 09, 2005 12:27 pm

Example against your theory:

RGB values at 0xEF

1. without that add:
corrected values = 0xEF >> 3 = 0x1D
Convert again to 8bit per channel: 0x1D << 8 = 0xE8
Thats 1 / 16 loss of precission

2. with the add:
corrected values = (0xEF + 4) >> 3 = 0xF3 >> 3 = 0x1E
Convert again to 8bit per channe: 0x1E << 8 = 0xF0
Thats only 1/256 loss of precission

On the other side, the colors that mapped correct in >> 3, they still do in +fractal >>3:

(color + fractal) >> 3
because of (color >> 3) << 3 maps correct (requirement) that is equal to
(color >> 3) + (fractal >> 3) = (color >>3) q.e.d.
=>
No color that mapped correct will map wrong on the round to nearest
_________________
GBAMP Multiboot

#60373 - duencil - Wed Nov 09, 2005 6:37 pm

I did allow adding your +4 fraction when we promote a colour component back to 8bit, so the end result doesn't look duller than the original. So if we do want to judge methods based on error after passing our colour to 15 bit then shifting back to 24 bit (I don't know why as the ds is a 16 bit display, but we'll let that pass), lets take worst case error instead of some random example. With my method you'd be seeing a maximum 4 degrees discrepancy per channel.

example worst case: RGB values at 0
5 bits / channel = 0>>3 = 0
back to 8 bits / channel = (0<<3) +4 = 4
error: 4 degrees

Because of your plus before the >> shift down tro 5 bit, you're left with a lot of original values ending up in the top band, as I tried to explain before. When going back to 8bit, your highest colour discrepancies will be there.

So in your method the worst case is RGB values at 255
5 bits / channel = CLIP(255+4)>>3 = 31
back to 8 bits / channel = 31<<3 = 248
error: 7 degrees

#60375 - Mighty Max - Wed Nov 09, 2005 6:58 pm

first add, then shift.

0+4 >> 3 = 0
revers: no add at all (there is no reason at all to do add something)
0<<3 = 0

(i converted back to 8bit based colorparts to make them compareable, i cant compare a 5 bit value to a 8 bit values, because they repressent fractals of a full (1/256 against 1/32) And i dont want to compare ables with tomatoes)


Worst case situation:
255 >> 3 = 31 ..... <<3 = 248
yes 7 points beneath, but the modified:

CLIP(255 + 4)>>3 = 31 ..... <<3 = 248
still 7 points beneath, and now?

Does it make that worst then the original?
_________________
GBAMP Multiboot

Last edited by Mighty Max on Wed Nov 09, 2005 7:10 pm; edited 2 times in total

#60376 - Mighty Max - Wed Nov 09, 2005 7:06 pm

-delete-
_________________
GBAMP Multiboot

#60382 - duencil - Wed Nov 09, 2005 8:15 pm

Mighty Max wrote:
No color that mapped correct will map wrong on the round to nearest


That's contentious. Wouldn't it make make more sense if values 0-7 map to 0. That doesn't happen in round to nearest.

And 248-255 should map to 31. That does happen, but also 244-247 map to 31, which shouldn't.

Mighty Max wrote:
first add, then shift.

0+4 >> 3 = 0
revers: no add at all (there is no reason at all to do add something)
0<<3 = 0


Actually I wanted to say the opposite, that it only makes sense to use the fractional add when going in reverse (i.e back to 8 bit), because you suddenly have more representable precision. When you go down to 5 bits you just dont have the precision to miss what you think you're losing-

#60384 - SevenString - Wed Nov 09, 2005 8:31 pm

An example:

127.0 / 8.0 = 15.875

method 1: 127 >> 3 = 15
method 2: (127 + 4) >> 3 = 16

The latter method produces a result that, in 5bit space, more closely represents the original 8bit value. Simply put, 16 is closer than 15 to the value 15.875.


Also, in a 555 color space, precision is much MORE important than in 888 color space because color discrepancies are so much more visible. A bit or half bit one way or the other in 888 space is most often invisible. However, when the color (in particular, the hue) is off by up to an entire bit per RGB channel, it is usually fairly easy to see, considering that a single bit represents 1/32 of the entire range.
_________________
"Artificial Intelligence is no match for natural stupidity."

#60386 - Mighty Max - Wed Nov 09, 2005 8:48 pm

duencil wrote:

And 248-255 should map to 31. That does happen, but also 244-247 map to 31, which shouldn't.


Erm its correct
0x31 << 3 =248 is actually as near to 244 as 0x30 << 4 = 240.

Therefor 0x31 represents the values from 244-252 best.

For all other values its nearer = more accurate.

Don't see the error.
_________________
GBAMP Multiboot

#60399 - duencil - Thu Nov 10, 2005 12:41 am

SevenString wrote:

method 1: 127 >> 3 = 15
method 2: (127 + 4) >> 3 = 16

The latter method produces a result that, in 5bit space, more closely represents the original 8bit value. Simply put, 16 is closer than 15 to the value 15.875.


I think the issue of fractions is just confusing you guys. 127 is just short of half intensity right? The best place to represent that in a scale of 0-31 is 15. Pushing it up to 16 pushes it past halfway - a clear case of landing in the wrong band.

Forget the fraction issue: just trust the nintendo engineers to have developed a 15bit screen where each of the 32 bands represent an equal proportion of the intensity spectrum.

#60403 - SevenString - Thu Nov 10, 2005 1:01 am

I'm not confused, and I'll stick with method two.
_________________
"Artificial Intelligence is no match for natural stupidity."

#60406 - duencil - Thu Nov 10, 2005 1:24 am

I see I'm not convincing anyone here, and sorry to imply you were confused :) Well, one last try, and I'll call it a day as I have my own texture conversion routines anyway, and don't mind so much if its not fixed in libnds.

In an 8bits range you can't represent exactly the middle. You have 128 values on one side and 128 values on the other. In other words value 127 falls on one side, 128 on the other. Do we agree? With just 5 bits range we now get 16 values on each side, therefore on either side of the fictitious middle are intensity values 15 and 16. 127 maps to 15 (falling into the last band up to the centre ) and 128 to 16 (corresponding to the first band after the centre).

#60446 - Mighty Max - Thu Nov 10, 2005 1:38 pm

Max value of 5 bit is 31, right?

So 16 is 51.61% of 31
And 15 is 48.38% of 31

So actually 16 repesents the 50% as good as 15.
_________________
GBAMP Multiboot

#60466 - SevenString - Thu Nov 10, 2005 6:03 pm

Quote:
ach! <slaps self on the forehead> duh!


The reason for my initial embarrassment at asking the question in the first place is that this is a classic, standard technique for bit reduction called "thresholding", found in many textbooks on the subject, and one that I've been using it myself for decades.

I mentioned this issue to one of my co-workers, a mathematician and computer graphics researcher with a doctorate in CS from Princeton, and he just looked at me blankly and said, "Why would you want to do it any other way?"
_________________
"Artificial Intelligence is no match for natural stupidity."

#60476 - duencil - Thu Nov 10, 2005 9:02 pm

I really didn't want to get drawn back into this, but mistakes left unchallenged have a bad habit of propagating, apparently to many textbooks on the subject and as far as Princeton doctorates :)

So lets try a reductio al absurdam. Instead of doing an 8 bit -> 5 bit conversion, we'll take the case of an 8-bit -> 1 bit conversion (monochrome). Your principle still applies I suppose.

At least my strategy is the same, and simple. val >> 7.
Values up to mid intensity get mapped to 0, after mid intensity they get mapped to 1.

Now I think your "fractional reasoning" leads you to thinking that >> 7 is inaccurate, and you really want a /128.0 (or alternatively in this case a +64 then >>7). This leads us to the situation where all colours from 64-255 get mapped to 1, and onlo 0-63 get mapped to 0. Don't you see how absurd this is getting.

#60487 - Mighty Max - Thu Nov 10, 2005 11:01 pm

Does that make the maths in 8 to 5 bit conversation false?

Show me an actual example in 8 to 5 bit conversation, i have a greater fault then the pure shift.

Sure i can blow the fractal up against the clipping like you did. but that does not happen on that specific situation. Its not that it could suddenly occure i need to convert to 1bit values.
_________________
GBAMP Multiboot

#60489 - SevenString - Thu Nov 10, 2005 11:39 pm

8bit to 5bit? thresholding
8bit to 1bit? error diffusion
_________________
"Artificial Intelligence is no match for natural stupidity."

#60490 - Mighty Max - Fri Nov 11, 2005 12:08 am

I understand the point duencil brings up. But it doesn't go against my point. All i say is how the rounded divide works:


(int)x / y ist the lower gaussian of (anyfloatingpoint)x / y. Correct?
(int)(x+(y-1)) / y is the upper gaussian of (anyfloatingpoint)x / y. Still Correct?

Then

(int)(x+(y-1)/2) / y is the nearest gaussian number to (anyfloatingpoint)x / y


But yes, that shows the source of the error that jumps into the 8 to 1bit conversation:

I would actually need do /255 instead of /128. as i want to map 255 to 1 instead of 128 to 1.
_________________
GBAMP Multiboot

#60491 - SevenString - Fri Nov 11, 2005 12:13 am

I agree with you MM. But maybe I'm just being absurd. ;)

Side note: thx for the MultiBoot. so, so useful.
_________________
"Artificial Intelligence is no match for natural stupidity."

#60493 - duencil - Fri Nov 11, 2005 12:57 am

ok Mighty Max, to generalise that, for the 8->5 bit reduction case, you could do (val<<5)/255

That's a much better proposal: gives you half bands at the top and bottom of the scale (only 4 entries each), equal sized bands in between(8 entries), no clipping, and allows proper round to nearest. But its costly with three divides per pixel.

edit: forget that - it doesn't even get you round to nearest.

I still would insist straight shifts are the correct solution.

#60568 - dovoto - Fri Nov 11, 2005 8:55 pm

< uneducated rant >

Yes more intensities will map into a value of 31 with rounding and clamping than they will into any of the other 31 intensities and less will round into the intensity 0 to make up the difference

---only intensities 0-3 will map to 0, while 244-255 will map to 31 with all the rest having just 8 values each.

This disparity results in banding at both ends of the intensity spectrum (an effect that becomes much more apparent the lower the bit depth you must convert to).

Truncating also has draw backs. Low intensity colors are lost completely (intensities 0-7) while rounding allows intensities 4-7 to be preserved.

An argument can be made that rounding causes colors to map closer to their original intensities; at first this argument seems valid:

7 / 8 = 0.875

If you were to truncate this would become 0 and if you were to round it would become 1. Since 0.875 is closer to 1 than 0 it seems that rounding gives a better result.

But, there is a very poor assumption being made...

in 256 color space 255 is max intensity.
255/8 = 31.875.

on the DS max intensity is 31. This implies that
255 in 8 bit color space should map to 31 in DS color space. Or, after the result of the division 31.875 should map to 31 on the DS.

If we take the intensity values to be linear (which they are) then it holds that 30.875 should map to 30 on the DS, 29.875 to 29, and so on to the point that .875 should in fact map to 0. This is the mapping that results from simply truncating the value.

Truncating causes a more even distribution of color intensities than rounding and clamping and preserves true relative intensity for the entire range (in so far as the new bit depth allows).

Do to the fact that the image is created on a different platform than the DS the actual accuracy of the conversion (rounded or truncated) is indeterminate. It may be the case that your art platform has a much brighter display than the DS and that an 8 bit value of 128 should map closer to 30 than 16 to retain the same intensity (something many of us have experienced on the GBA and its very dim screen). Since accurate intensity conversion can not be determined (and is in fact arbitrary) the only real choice is to go with the method that produces the even distribution.

The proper way to do color conversion (in my uneducated opinion) is to apply a non-linear alpha correction based on the physical systems in question (source and destination) and then truncate.

Since my pcx color conversion can not make the assumption of pre-processed images, nor can it possibly apply alpha correction itself it must choose whether loosing very low intensity colors is more painfull than the slight banding of colors at the maximum end of the intensity spectrum. I am pretty much undecided on which gives better looking images...perhaps someone should do a few textures and see how they look using both methods.

What do real graphics applications do? (photoshop, gimp, painshop..etc)
_________________
www.drunkencoders.com

#60585 - duencil - Sat Nov 12, 2005 2:47 am

Really helpful explanation dovoto. You explained this a lot better than I was capable of and made me realise a few things too.

Like you made clear truncating suffers from low intensity colours (like 0,0,0 to 7,7,7 in 8 bit) getting mapped to complete 0,0,0 which will be the displays representation of complete black.. But equally colours 248,248,248 to 255,255,255 get mapped to the display's representation of complete white, producing simliarly bad pixel discrepancies for colors close to both extremes of the spectrum (+-7). On the other hand, you could expect the least error occurring around the centre ( where pixels can be expected to be off by at most +-4)

Like you say the physical properties of the display (like the gamma ramp)complicates things. One thing we could do if we care enough about this issue is make a software gamma table of 256 entries, mapping our 8 bit to 5 bit values to compensate for this intensity error curve. Even if we don't know about the actual characteristics of the display, a 5 bit to 8bit conversion trick I've seen a few times which produces such a nonlinear mapping is x' = (x<<3)|(x>>2). I don't see such a simple way to reverse this, but building a table using this to find for each entry in the table the closest 8 bit value and its 5 bit equivalent would be trivial.

#60601 - tepples - Sat Nov 12, 2005 4:06 pm

What you really need to do is run each pixel through a gamma correction lookup table for each RGB component and then use some sort of error-diffusion.
_________________
-- Where is he?
-- Who?
-- You know, the human.
-- I think he moved to Tilwick.