256colour Translucency

[Khatoblepas]

Okay, so I'd be the first to admit I like doing things the hard way. In the game I am making, I am obsessive about file structuring, custom file formats for lower clockspeeds (Compression = Slow ), and making it run on the bare minimum.

Today I have been thinking about Translucency effects. I don't want to run on 16bit colour (Half the framerate? BAH), but I do want the delicious translucent sprites it has. I know how to do translucent shadows and white light glowing (It's all a case of managing your palette well.), but translucency stumped me. So, I wrote out some (hopefully readable) pseudocode for drawing a 50% transparent colour onto a pixel.

Any tips on how to optimise it are VERY welcome. It looks like a LOT for just writing a pixel. I bet it would run terribly, terribly slow with sprites that move =D

TYPEDEF struct Pixel {
char r;
char g;
char b;
} RGB;

void PlaceTranslucentPixel (targetx,targety,desiredr,desiredg,desiredb){

RGB pixel = GetPixelRGB (targetx,targety);
char i;
RGB result;
result.r = (pixel.r + desiredr) >> 1; //Halfway between each value. I hope I got the bit shifting right =x
result.g = (pixel.g + desiredr) >> 1;
result.b = (pixel.b + desiredr) >> 1;
char success;
while (i<255) 
{
  RGB temp = GetPalRGB(i); //Load up the current palette entry into an array.
 // If current palette entry is equal to the desired palette entry, with a tolerance of 4/63ths either way.
  if (temp.r > result.r -4 && temp.r < result.r +4 && 
      temp.g > result.g -4 && temp.g < result.g +4 &&
      temp.b > result.b -4 && temp.b < result.b +4) 
  {
  break; //You got an entry!
  success++;
  }
  else i++;
}
if (!success) { //If the last loop failed to bring results, repeat with a higher tolerance.
while (i<255) 
{
  RGB temp = GetPalRGB(i); 
  if (temp.r > result.r -8 && temp.r < result.r +8 && 
      temp.g > result.g -8 && temp.g < result.g +8 &&
      temp.b > result.b -8 && temp.b < result.b +8) 
  {
  break;
  success++;
  }
  else i++;
}
PlotPixel (targetx,targety,i); //Write the pixel with the halfway colour!
}

 

[shrubberyrobbery]

well, this might help, possibly...

in the past I have experimented with a fixed-256-colour 8 bit palette, and I came up with a very very useful scheme which was this:

2-bits red, 2-bits green, 2-bits blue, 2-bits 'luminance'

the 'luminance' worked like this (am going from memory here, but trust me, it worked well originally!): red, green and blue bits were worth a weight of '4' on the particular red/green/blue channel, and luminance bits were worth '1' on ALL channels
this is all scaled up so that a weight of '1' is equals to 16 on the 0-256 full colour scale.

here's the clever bit - we now have a 256-colour fully rgb palette, with 16 grey scales, and 'sort of' 16 shades of ANY colour/hue/saturation. magic!

for example, the first few grey-scale values would be:

#000000 is r=0, g=0, b=0, i=0
#101010 is r=0, g=0, b=0, i=1
#202020 is r=0, g=0, b=0, i=2
#303030 is r=0, g=0, b=0, i=3
#404040 is r=1, g=1, b=1, i=0

get it?

now what this means is that we have a proper RGB cube, which is optimised to make absolutely best use of the pitiful 8-bits available,

so getting the 'middle' colour between any two colours just means getting the 'middle' co-ords out of the rgb cube by averaging the rgb of the two colours to be merged. job done!

i don't have the time to go into much more detail at the moment, so i hope this made some kinda sense!

 

[Radek]

Okay, so I'd be the first to admit I like doing things the hard way. In the game I am making, I am obsessive about file structuring, custom file formats for lower clockspeeds (Compression = Slow ), and making it run on the bare minimum.

Today I have been thinking about Translucency effects. I don't want to run on 16bit colour (Half the framerate? BAH), but I do want the delicious translucent sprites it has. I know how to do translucent shadows and white light glowing (It's all a case of managing your palette well.), but translucency stumped me. So, I wrote out some (hopefully readable) pseudocode for drawing a 50% transparent colour onto a pixel.

Any tips on how to optimise it are VERY welcome. It looks like a LOT for just writing a pixel. I bet it would run terribly, terribly slow with sprites that move =D

If you are going to use 8bit palletized mode use it to your advantage. Someone already had give you one trick but there some others.

You can precalculate a transluency 2d table where indexes are source and value is final pixel.

If you can limit used colors you can have 16*16 (or 32*8, 64*4 and 128*2) table to mix your pixels with correct RGB results.

Finally you can use 32bit surface (RGBA) and take advantage of 32bit ALU to mix RGB directly but at cost of 1 bit of precission:
- load RGBA pixel to 32 bit register
- clear the first bit of every channel
- bitshift logically to left by 1 bit
- do the same with second source
- add these registers
- write results to the surface

The same can be done for 16bit of course so you could process two RGB values at once!

 

[RiX0R]

...neat trick...

​

That's pretty clever, but what's the added value of the "luminance" field, as opposed to assigning the two spare bits to a color channel (R and B for example, like in 16-bit mode)?

 

[rokdcasbah]

assigning the bits to existing channels is possible of course...but imagine trying to compute a color when the color resolution is uneven...it'd be sloppy. you'd probably have to use percentages or something. meanwhile having an even 2 bits per channel makes pure grays a breeze and allows you to just type in color codes without pulling out a calculator. i'm just guessing though.

 

[Radek]

assigning the bits to existing channels is possible of course...but imagine trying to compute a color when the color resolution is uneven...it'd be sloppy. you'd probably have to use percentages or something. meanwhile having an even 2 bits per channel makes pure grays a breeze and allows you to just type in color codes without pulling out a calculator. i'm just guessing though.

​

Well...

Some Python code demonstrating what I had in a mind.

def MixRGB(s1, s2):
    # s1, s2 - tuples of (R, G, B) intenger values
    # Encode s1 and s2 into two binary values. This
    # WILL NOT be needed in an actual C or ASM code.
    s1bin = (s1[0] << 16) + (s1[1] << 8) + s1[2]
    s2bin = (s2[0] << 16) + (s2[1] << 8) + s2[2]
    # The algo starts here.
    s1bin &= 16711422   # 111111101111111011111110
    s2bin &= 16711422   # 111111101111111011111110
    s1bin >>= 1
    s2bin >>= 1
    RGBOut = s1bin + s2bin  # Final results of RGB  translucency
                            # just after 5 very plain opcodes.
    # Encode back to the tuple, again part not needed
    # in an actual code.
    R = (RGBOut & (255 << 16)) >> 16
    G = (RGBOut & (255 << 8)) >> 8
    B = (RGBOut & 255)
    return R, G, B

def Mix565RGB(s1, s2):
    # s1, s2 - tuples of (R, G, B) intenger values
    # Encode s1 and s2 into two binary values. This
    # WILL NOT be needed in an actual C or ASM code.
    # Pixel format: RRRRR GGGGGG BBBBB
    s1bin = (s1[0] << 11) + (s1[1] << 5) + s1[2]
    s2bin = (s2[0] << 11) + (s2[1] << 5) + s2[2]
    # The algo starts here.
    s1bin &= 63454  # 1111011111011110
    s2bin &= 63454  # 1111011111011110
    s1bin >>= 1
    s2bin >>= 1
    RGBOut = s1bin + s2bin  # Final results of 565 RGB  translucency
                            # just after 5 very plain opcodes.
    # Encode back to the tuple, again part not needed
    # in an actual code.
    R = (RGBOut & (31 << 11)) >> 11
    G = (RGBOut & (63 << 5)) >> 5
    B = (RGBOut & 31)
    return R, G, B

 

[rokdcasbah]

well done sir. what do the >> and << mean in python? is it some sort of fraction/decimal/range thing?

also, (offtopic) i was trying to code a breakout/arkanoid clone...
a. do you think using angles in radians or degrees for the ball movement is a good idea? and then convert the angle into components using cos and sin
b. how the hell do you use cos and sin in python?

haha thanks.

also, i was wondering...is transparency done simply by adding or averaging the rgb values? i was thinking about the way light mixes differently (additive) than paint (subtractive)...let's say your transparent object is subtractive...do you just subtract the rgb codes? and vice versa for additive sources?

in fact, how the hell does the snes even do it? the more i though about it, the more it seemed like there's more than one way to do this, depending on how you store the color information and what material it is you want to 'model'...

 

[Radek]

well done sir. what do the >> and << mean in python? is it some sort of fraction/decimal/range thing

Logical bitshifts to left (<<) and right (>>). Just like in the C and assembler.

also, (offtopic) i was trying to code a breakout/arkanoid clone...
a. do you think using angles in radians or degrees for the ball movement is a good idea? and then convert the angle into components using cos and sin

Try to use vector components directly. The less there are the sinus/cosinus the better.

b. how the hell do you use cos and sin in python?

Look at the "math" module.

haha thanks.

also, i was wondering...is transparency done simply by adding or averaging the rgb values? i was thinking about the way light mixes differently (additive) than paint (subtractive)...let's say your transparent object is subtractive...do you just subtract the rgb codes? and vice versa for additive sources?

There many types of transparency obviously. Source values can be averaged, multiplied, divided or whatever... And yes you must compute the individual RGB values. This is reason why it's so slow in software and why that trick I showed is very fast (thought not ideal - there is always loss of 1 bit in source scalars).

in fact, how the hell does the snes even do it? the more i though about it, the more it seemed like there's more than one way to do this, depending on how you store the color information and what material it is you want to 'model'...

​

When you are using simple average (the "( a + b ) / 2") you can use bitshift instead of divide. This is very cheap to do. But I don't know exactly what is snes using so it might have a full alphablending of surfaces thought it's unlikely.

 

[rokdcasbah]

thanks for the clarification, radek.

http://www.gamedev.net/reference/articles/article883.asp

the author of that article says the snes used color addition. he doesn't provide any references, though, but i'm not sure why he'd lie anyway.

edit: later on he says that chronotrigger and possibly mario rpg used color subtraction.

 

[shrubberyrobbery]

assigning the bits to existing channels is possible of course...but imagine trying to compute a color when the color resolution is uneven...it'd be sloppy. you'd probably have to use percentages or something. meanwhile having an even 2 bits per channel makes pure grays a breeze and allows you to just type in color codes without pulling out a calculator. i'm just guessing though.

​

yep. that was my reasoning, exactly.

If you're going to have plain rgb channels in 8 bits, then the best compromise is 3-bits red, 3-bits-green and 2-bits blue (as our eyes are less sensitive to blue levels, i think?), but that is so sub-optimal and screws up so much other stuff, that its not really worth it.

I find the 2-bits luminance is SO useful. It also works out very well if you use this scheme when doing dithering to simulate higher colour depths. I used this when i did a 8-bit 3d engine thingy ages ago - it meant I could have 'pretend' 24-bit colour.

 

[rokdcasbah]

our eyes are definitely less sensitive to blue. a lot of the jpeg compression happens on the blue channel.

 

[Khatoblepas]

Ah. You see, in order for Delta Masking to work with this (see footnote), the palette has to be ordered in a certain way.

An example of how I make the palette. So, I'm going to have to be careful what kind of method I use, or my simple functions'll go out the window. That's why I tried to do one that would work independantly of the palette, since it's gonna be changing with the scenery. =x

A lookup table might be nice to use, but having 768b+64k for each palette would take up a lot of space. Thooough... loading palettes one at a time would save RAM, so... YEAH! Lookup table it is! Much easier than manually doing it everytime.


* Delta Mask: A flat 1bit bitmap image followed by a delta value, telling the intravenous blitter to lighten or darken the currently blitted layer (a signed char. +3 or -2 or something.). It is, literally, a mask from which things can be make to shadow, or glow. It's something of my own invention =3. I use it mainly for shadows underneath characters, and dialogue box backgrounds. The way I blit is like this:

Layer 1 Maptiles
Deltamask1[shadows of characters]
Characters
Deltamask2[wallshadows and glow that affects characters]
Layer 2 Maptiles
[Deltamask3 - Rarely used, only for overhead fog and dialogue boxes]

I've yet to optimise everything, and it's still not in alpha.

 

[Radek]

our eyes are definitely less sensitive to blue. a lot of the jpeg compression happens on the blue channel.

​

And most sensitive to green - this is why we have 5-6-5 RGB for 16bit modes.

Anyway... some more digging in Arm assembler:

;In R1 and R2 are 2x2 source pixel in 5-6-5 RGB format.
;R3 contains a bit mask:    "11110111110111101111011111011110"
;              RGB bits:     RRRRRGGGGGGBBBBBRRRRRGGGGGGBBBBB
;first/second 16bit pixel:   11111111111111112222222222222222
;R0 will have a final output of mixing.

AND R1, R3; zero first bit of every R, G, B scalar
AND R2, R3; the same as above but for second source pack
MOV R0, R1, LSR #1; divide by 2 first pixel pack
ADD R0, R0, R2, LSR #1; the same as above but for second pack and add results

; That's all - in R0 are results of averaging two packs of two 16bit RGB pixels!
; (effectivelly processing 6 scalars in one go)
; This code should (not counting load/store) execute in just 4 cycles on Arm9.
; This means one transparent pixel per 2 machine cycles. The problem is reduced
; accuracy as every scalar has zeroed first bit. But it's fast...

Didn't test it yet but... worked just fine prototyped in Python.

edit: the "code" marker doesn't use a fixedwidth font...

 

[Khatoblepas]

Okay! Another question.

I'm using the 50% Transparent Alpha Table method (cause it's the only one I understand ;_; ) and I'm wondering... would it be better if I pre-calculated the 256*256 CLUT, or did it on the fly? Would you prefer slow loading times, or a bigger game? And for that matter, is reading 64k into an array faster than doign it on the fly yourself? Or should I use compression on the table, and decompress it when it is read in? Would this be slow?

I know this wouldn't be a problem with consoles with a fixed medium (if I were devving my game for the Dreamcast, for example, it would definately be a precalculated thing, as the medium the Dreamcast (homebrew) uses is CDs, and you could easily just put the game on multiple CDs).

But I just need your opinion. Space or speed?
So many questions...

 

[RiX0R]

Speed definitely.

Precalculating and compiling in is a pain, imho, because you need a second program to do the precalculation and write out a source file, and you need to do that every time something changes.

But Startup speed doesn't matter as much, so I would go with precalculating at startup. Just show a "loading" screen -- it will only take a few seconds anyway.

 

[Khatoblepas]

Well, if I'm going to be using multiple palettes for different areas (So I can have richer colours - Grass/Emerald Green dominant colours for forest areas, sea green and blue for underwater, reds and browns for mountains and autumn scenes - no use using a global palette and compromising when I have the ability to do all this!), there would be loading times between each map that doesn't use the same palette. Something similar was done in Albion.

A hassle, yes, but as I'm trying to make something REALLY awesome for the GP2x I gotta make it look pretty and not have redundant palette entries! Push 8bit to (my) limit!

I CAN write out an alphatable file for every palette that needs it, and when I make the editor for the program, it would just be a simple matter of calculating it when I save the source files =P. So there's gonna be no mistakes and stuff, and people can easily make games with it too. I HATE doing everything by command lines and manual stuff >>

 

[Radek]

Well, if I'm going to be using multiple palettes for different areas (So I can have richer colours - Grass/Emerald Green dominant colours for forest areas, sea green and blue for underwater, reds and browns for mountains and autumn scenes - no use using a global palette and compromising when I have the ability to do all this!), there would be loading times between each map that doesn't use the same palette. Something similar was done in Albion.

A hassle, yes, but as I'm trying to make something REALLY awesome for the GP2x I gotta make it look pretty and not have redundant palette entries! Push 8bit to (my) limit!

I have an another suggestion - the lockup table is a nice but with 256*256 size it will eat 64KB of memory. This isn't a problem itself but it might trash data cache on the ARM cpu as it has only 16KB. If you could use less colors for transparent surfaces you could make a smaller lockup table. After all the most colors will be used by background and when you will mix them (even by a table) the output will have bigger variation of them anyway.

So 32x256 is only 8192bytes and will fit in a cache nicely therefore it'll be faster. But it could complicate preparing the graphics somewhat...
(so your best bet it's to do with full 256*256 tables and only resort to such optimization when really necessary)

 

[Khatoblepas]

So you're saying use a different part of the palette for the characters than the backgrounds? Say you have 256 colours:

IIIIIIIIIIIIIIII
CCCCCCCCCCCCCCCC
CCCCCCCCCCCCCCCC
CCCCCCCCCCCCCCCC
BBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBB

Where I is Interface colours, C is character colours, and B is background colours?

I suppose then you could have a dedicated palette for the interface/font (it never changes and can't be used anywhere else), a dedicated palette for the sprites (48 colours should be enough for anybody! The Amiga had less!) and the rest for the background. Sounds fair.

But then you have the conundrum of semi transparent maptiles (like windows and waterfalls). I could make it so that pixels in the maptile mapped to <49 makes the pixel translucent, and make sure nothing is mapped to the first 16.

12k would work, right?

 

[Radek]

So you're saying use a different part of the palette for the characters than the backgrounds? Say you have 256 colours:

Not, not at all.

You can use all 256 colors for background (and everything else) just...

Ok, it starting to be complicated so imagine the "standard" 256x256 table first.

Lets adress it in this way: [y][x] - y is first source value, x the second.

Then assume we have only 32 colors for transparent surfaces. It will be list of 32 8bit (0-255) values what can be selected freely. This is the index "y" and the let make it to 1 dimensional table with size of 32 (call it "PREINDEX).

Then make a second table by just copying every [y][0-255] slice of the 256x256 lockup table (y are values from "PREINDEX" table) so we have in the end the table of 32x256 elements.

Now reencode sprites (the ones what have to be transparent) to 5bit values using PREINDEX table:

A - original 8bit value

find where the A is the PREINDEX table

the position of the A (0-31) in that table will be new reencoded value of A

Make all needed sprites' data this way.

Now you duplicated some sprites in the memory but you can use all 256 colors for everything and still have a small lockup table for transparencies. Even better you can have many such tables for any 32 color combination from 256.

If you could put all colors of transparent sprites into first 32 positions of 256 palette then reencoding will be not needed.

 

[gfoot]

Without reencoding, you don't need to use the first 32 colors for translucent sprites - you could use any 32-color block per sprite and still get good cache performance within each sprite.

Something else that might be worth mentioning is if you can arrange that blending a sprite is simply ORing its pixel values with that of its background, you can do it very fast indeed using the hardware blitter. Might be too restrictive on palette content though.