Status: Tea and other thoughts

I haven't written here often, because it's stunningly difficult to write something worth reading; only more so when your thoughts are fleeting and your Internet access is sparse. However, just to affirm that I'm still alive and kicking, I'd like to share some stuff I've been up to and thinking about.

First is my new project: Tea. Tea is a simple 2D game development library for Ruby. It's made for the sort of grass-roots development that was popular with QBASIC back in its era. Tea is designed with simplicity in mind: 0 is better than 1, and 1 is better than 2, but at the same time, it won't avoid a valuable, convenient feature just because it can be built from other features. Graphics, input, sound and text are the pillars of Tea.

Tea is making slow but steady progress. Events have been blasted right through. Sound and text are waiting on graphics, and speaking of graphics, that has been a royal pain to deal with so far. Why? In the words of Joel Spolsky:

All non-trivial abstractions, to some degree, are leaky.

To demonstrate, I'll describe what I'm dealing with in the graphics subsystem of Tea. Tea is built largely on Ruby/SDL, which, surprise surprise, provides a Ruby-like flavouring to SDL.

Now, as all good, honest, hard-working API developers know, when you port an API from one language to another, C to Ruby in this case, you don't just translate the functions. Doing so means that you end up with something clunky, brittle and encourages programmers to write in the style of one language inside a completely different one. Thankfully, Ruby/SDL's author kept this in mind, adding niceties like automatic bounds checking for pixel plotting, arranging things into modules and classes and sticking with the OO-ness of Ruby.

Ruby/SDL also provides graphics primitives: what we know as basic shapes, like rectangles, lines, points and circles. It provides this by hooking into an SDL library called SGE, or SDL Graphics Extension. All is fine and good in the world. Ahh.

Except, it wasn't. SGE's graphics primitive functions offer alpha blending and anti-aliasing to boot. I wanted those in Tea's API, so I just translated the calls, and when I drew to the screen, it all looked okay. But when I used exactly the same calls on SDL surfaces I created, all was broken. Anything with an alpha less than 255 would not appear at all. Ever.

At first I thought I must have screwed up somewhere. Did I forget to set an alpha-related flag? Did I remember to give an alpha mask when I made the surface? Was I giving the surface pixel format the wrong endian byte ordering? I wracked my brain trying to see where I screwed up, and then I stumbled on this little bit of code in SGE's source:

           case 4: { /* Probably 32-bpp */
                if( alpha == 255 ){
                    *((Uint32 *)surface->pixels + y*surface->pitch/4 + x) = color;
                }else{
                    Uint32 *pixel = (Uint32 *)surface->pixels + y*surface->pitch/4 + x;
                    Uint32 dc = *pixel;
 
                    R = ((dc & Rmask) + (( (color & Rmask) - (dc & Rmask) ) * alpha >> 8)) & Rmask;
                    G = ((dc & Gmask) + (( (color & Gmask) - (dc & Gmask) ) * alpha >> 8)) & Gmask;
                    B = ((dc & Bmask) + (( (color & Bmask) - (dc & Bmask) ) * alpha >> 8)) & Bmask;
                    if( Amask )
                        A = ((dc & Amask) + (( (color & Amask) - (dc & Amask) ) * alpha >> 8)) & Amask;
 
                    *pixel = R | G | B | A;
                }
            }
            break;

To make sense of this, you need to know a bit about what alpha is and how it relates to drawing.

Your typical pixel consists of some mixture of red, green and blue light. When they're mixed you can get many different kinds of colours.

There's some history behind how pixels could be told what colour they were. Decades ago, the colours were hard-coded, none of that red/green/blue crap. After that came the paletted modes, where you could mix red/green/blue, but only have, say, 256 mixtures at once, and pixels said which mixture they were in the palette.

Now we have what's known as packed pixels. A packed pixel contains its own red/green/blue bits, stored as individual numbers in the pixel itself. With 15-bit colour, red/green/blue got 5 bits each. Of course, in a system where the fundamental unit is 8 bits, i.e. bytes, that's pretty damn slow due to alignment issues. 16-bit colour gave red and blue 5 bits, and the extra one went to green, so it got 6 bits.

Today's packed pixels aren't 15 or 16 bit. Moore's Law has let our gluttonous selves get away with a whole 8 bits each for red, green and blue! Wowzers! Now the space for a single packed pixel is 24 bits.

Some people may have already picked up on something: most stuff runs on 32 bits, so what happens when each pixel is 24 bits? Yep, alignment issues. A 24-bit pixel is as alien to the world of 32 bits as 15-bit pixels were to the world of 16 bits. At least 24 is a multiple of 8, but when you're dealing with 4 chunks of 8 bits, it doesn't help a lick. Not much of a choice here: waste that extra 8 bits for an even 32, or be damned to bad performance.

Today's packed pixels are often 32-bits. Many video systems will even emulate 24-bit video modes with 32-bits because it looks the same, and it looks the same because the red/green/blue parts of a 32-bit pixel look like this:

rrrrrrrr gggggggg bbbbbbbb ????????

Turns out that neither the red, the green, nor the blue pixels steal any bits from the extra space. Then who gets those 8 bits?

On a screen, there's not much to do with it, so it's just left blank. But when you're dealing with graphical memory that will eventually be shown on a screen, those 8 bits can be put to good use.

Say you want to draw a spaceship. You have a spaceship in a rectangular block of graphics memory, and you want to draw it against a background of a nebulous space cloud. However, just bit-block transferring (or "blitting") the spaceship graphics memory will cause the nice background to be tarnished with an ugly black box. How do we draw the spaceship, but not the box?

Alpha to the rescue! Alpha is a numeric value that provides opacity information: how opaque is something? Full alpha means completely opaque, while no alpha means completely invisible. You probably know where I'm going with this: alpha could be assigned to each pixel, in those last 8 bits of our 32-bit pixels!

rrrrrrrr gggggggg bbbbbbbb AAAAAAAA

Now we can tell each pixel to be drawn (full alpha), or not drawn (zero alpha). Great.

But wait, we're missing something: what's meant to happen when alpha is somewhere between full and zero? If alpha is half for a spaceship pixel, how does it get "sort of" drawn? This is what alpha blending describes: "How do I blend what I'm drawing and what I'm drawing to based on alpha?"

Linear interpolation is one choice: if 0 alpha says not to draw a spaceship pixel, and 255 alpha means to completely draw the spaceship pixel, then anything in between will be some linear mix of the red/green/blue parts of the spaceship pixel, and the nebulous cloud background:

final_red = background_red + (spaceship_red - background_red) * (alpha / 255)
final_green = background_green + (spaceship_green - background_green * (alpha / 255)
final_blue = background_blue + (spaceship_blue - background_blue) * (alpha / 255)

If alpha is zero, it's easy to see that the final colour will be unaffected. If alpha is 255, on the other hand, the final colour will be exactly the spaceship's colour. Anything in between is some negotiation between spaceship pixel and nebulous cloud pixel.

This, in fact, is precisely what SGE does with its alpha blending, and it works fine on the screen. But things get tricky when you move to graphics memory other than the screen. For one thing, the screen doesn't have any alpha: those bits were left blank and are ignored.

But graphics memory buffers really do use the alpha, and they need it, and things start to get ugly. First, you need to consider how to use the alpha. Do I want to do the same sort of blending as before, or do I want the alpha to just be "drawn in" so that the graphics buffer can use it? Both approaches have legitimate uses, and somebody may want to use both in different situations, so it can't be ignored.

Why can't the same linear interpolation work for graphics memory buffers? Consider a buffer that's completely transparent, i.e. all pixels have an alpha of zero. When drawn as-is, this will show absolutely nothing. So far, so good. Now, what happens when we draw a white rectangle over this buffer with an alpha that's not quite full?

Using the linear formulas above, whatever random red/green/blue values that are in those zero alpha pixels are suddenly going to be blended with our clean white rectangle. Result: ugly noise for something that should have been drawn clean. Somehow, we need to account for the transparency of the graphics buffer's pixels when blending those red/green/blue values.

Here's what I've got so far with Tea's code (effectively, but not exactly):

if buffer_alpha > 0
  ratio = min(draw_alpha / buffer_alpha, 1.0)  // Watch out for division by 0!
else
  ratio = 1.0
end
final_red = buffer_red + (draw_red - buffer_red) * ratio
final_green = buffer_green + (draw_green - buffer_green) * ratio
final_blue = buffer_blue + (draw_blue - buffer_blue) * ratio
final_alpha = ????

That scales the influence of the drawn colour against the graphics buffer's alpha, so that random colours for pixels with zero alpha have zero effect.

That's good, but what do we set for the alpha? Since alpha matters for graphics memory buffers, we'll need to set it to something predictable. Going back to SGE's code, there's a section that reads like this:

                   R = ((dc & Rmask) + (( (color & Rmask) - (dc & Rmask) ) * alpha >> 8)) & Rmask;
                    G = ((dc & Gmask) + (( (color & Gmask) - (dc & Gmask) ) * alpha >> 8)) & Gmask;
                    B = ((dc & Bmask) + (( (color & Bmask) - (dc & Bmask) ) * alpha >> 8)) & Bmask;
                    if( Amask )
                        A = ((dc & Amask) + (( (color & Amask) - (dc & Amask) ) * alpha >> 8)) & Amask;

The first 3 lines do the linear interpolation that I described earlier. But that last line is problematic! Think it through: if you draw a 255 alpha pixel onto a 0 alpha pixel, what should you get? If you said 128, you made the same mistake that SGE's author made when he wrote this code. If you put an opaque object in front of a piece of glass, you shouldn't see a translucent object: the whole thing should still be opaque!

Here's the formula I use in Tea:

final_alpha = min(buffer_alpha + draw_alpha, 255)

This will add the alphas together, maxing out at 255. I'm not sure how correct it is, but it acts okay for what I want, and it has the added bonus of correctly setting the ratios of the old and new red/green/blue parts right, according to the final alpha, e.g. a 90 alpha pixel drawn to something with 10 alpha will contribute 9 times as much colour as the buffer's colour would.

Anyway, SGE got it wrong for everything but the screen. Plus there's no way to tell it to replace the alpha, bypassing the blending entirely. That's much simpler, but SGE doesn't do that for me either. Boo.

So those drawing functions that Ruby/SDL provided, that work by hooking into SGE, turn out to be insufficient for my needs. I should have known that those handy-dandy pre-written methods were too good to be true. Score one for the leaky abstraction.

On top of that, since I have to redo the alpha blending that SGE should have given me, I have to re-implement the actual graphics primitive functions as well. Rectangle was easy. Efficient line drawing wasn't as easy, but doable. Efficient circles, which is what I'm up to, aren't trivial at all, which was what I was meant to be working on today, except instead of writing code, I decided to write this blog entry. Aren't you grateful?

Anyway, there's no immediately obvious code on the Internet for drawing a filled, anti-aliased circle. My game plan is to adapt Xiaolin Wu's anti-aliased circle algorithm, get that to work, extend it to operate in all 8 octants, and extend it again to fill in the inside of the circle. I'm writing this in pure Ruby, which is why I'm so obsessed with the performance: even drawing a blended rectangle has proven to be painfully slow. I'd write this all in C, but when I do that, I may as well kiss goodbye to any dreams of cross-platform compatibility that I wanted for Tea.

This blog entry is getting too damn big for its own good, so I'll only touch on the idea I wanted to see today: a blog with a Git back-end. That way, I could write whenever I wanted, and when I get Internet access, I could just sync my writing with the online storage. One can dream.