256colour Translucency

Discussion in 'General Discussions' started by Khatoblepas, Jan 23, 2006.

  1. Khatoblepas

    Khatoblepas Still Fresh

    Joined:
    Dec 28, 2005
    Messages:
    94
    Location:
    England
    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

    Code:
    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!
    }
     
    Tags:
  2. shrubberyrobbery

    shrubberyrobbery Member

    Joined:
    Dec 1, 2005
    Messages:
    174
    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!
     
  3. Radek

    Radek Certified Guru

    Joined:
    Oct 13, 2005
    Messages:
    871
    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!
     
    Last edited by a moderator: Dec 17, 2015
  4. RiX0R

    RiX0R Idler-Inside

    Joined:
    Sep 20, 2005
    Messages:
    294
    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)?
     
    Last edited by a moderator: Dec 19, 2015
  5. rokdcasbah

    rokdcasbah got me a date with botticelli's niece

    Joined:
    Jan 5, 2006
    Messages:
    1,517
    Location:
    up on cripple creek
    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.
     
  6. Radek

    Radek Certified Guru

    Joined:
    Oct 13, 2005
    Messages:
    871
    Well...

    Some Python code demonstrating what I had in a mind.

    Code:
    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
    
     
    Last edited by a moderator: Dec 19, 2015
  7. rokdcasbah

    rokdcasbah got me a date with botticelli's niece

    Joined:
    Jan 5, 2006
    Messages:
    1,517
    Location:
    up on cripple creek
    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'...
     
  8. Radek

    Radek Certified Guru

    Joined:
    Oct 13, 2005
    Messages:
    871
    Logical bitshifts to left (<<) and right (>>). Just like in the C and assembler.

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

    Look at the "math" module.

    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).

    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.
     
    Last edited by a moderator: Dec 19, 2015
  9. rokdcasbah

    rokdcasbah got me a date with botticelli's niece

    Joined:
    Jan 5, 2006
    Messages:
    1,517
    Location:
    up on cripple creek
    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.
     
  10. shrubberyrobbery

    shrubberyrobbery Member

    Joined:
    Dec 1, 2005
    Messages:
    174
    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.
     
    Last edited by a moderator: Dec 19, 2015
  11. rokdcasbah

    rokdcasbah got me a date with botticelli's niece

    Joined:
    Jan 5, 2006
    Messages:
    1,517
    Location:
    up on cripple creek
    our eyes are definitely less sensitive to blue. a lot of the jpeg compression happens on the blue channel.
     
  12. Khatoblepas

    Khatoblepas Still Fresh

    Joined:
    Dec 28, 2005
    Messages:
    94
    Location:
    England
    Ah. You see, in order for Delta Masking to work with this (see footnote), the palette has to be ordered in a certain way.

    [​IMG]

    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.
     
  13. Radek

    Radek Certified Guru

    Joined:
    Oct 13, 2005
    Messages:
    871
    And most sensitive to green - this is why we have 5-6-5 RGB for 16bit modes.

    Anyway... some more digging in Arm assembler:

    Code:
    ;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...
     
    Last edited by a moderator: Dec 19, 2015
  14. Khatoblepas

    Khatoblepas Still Fresh

    Joined:
    Dec 28, 2005
    Messages:
    94
    Location:
    England
    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...
     
  15. RiX0R

    RiX0R Idler-Inside

    Joined:
    Sep 20, 2005
    Messages:
    294
    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.
     
  16. Khatoblepas

    Khatoblepas Still Fresh

    Joined:
    Dec 28, 2005
    Messages:
    94
    Location:
    England
    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 >>
     
  17. Radek

    Radek Certified Guru

    Joined:
    Oct 13, 2005
    Messages:
    871
    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)
     
    Last edited by a moderator: Dec 17, 2015
  18. Khatoblepas

    Khatoblepas Still Fresh

    Joined:
    Dec 28, 2005
    Messages:
    94
    Location:
    England
    So you're saying use a different part of the palette for the characters than the backgrounds? Say you have 256 colours:

    Code:
    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?
     
  19. Radek

    Radek Certified Guru

    Joined:
    Oct 13, 2005
    Messages:
    871
    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.
     
    Last edited by a moderator: Dec 17, 2015
  20. gfoot

    gfoot Member

    Joined:
    Nov 15, 2005
    Messages:
    218
    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.
     

Share This Page

Loading...