Fast Transparent Sprites

By Ashley Roll
1999

Introduction

I've been working on a sprite-based game for an arcade platform and I needed to display transparent sprites. Just to get things working, I implemented an algorithm that used a mask and image that were both layed down in sequence using bit masking to arrive at the final transparent sprite. I'm using a 16 Bit display depth, so this worked ok (it is difficult to get it to work correctly with a palletised display).

This worked by having a mask with white values (0xFFFF) where the image was to show and black values (0x0000) where the image was to be transparent. The image was formed with white pixels where it is to remain transparent.

To display the image, one would place the mask on the target surface as:

This will result in a pure white area where the image is to show and what ever was on the target where the image is to be transparent. Then one lays the image data over the top of this:

This will leave the transparent areas as they where and place the image data in the white area left by the mask. Note that this works in "true colour" modes because the values being worked on are the actual colour data. But for a palletised display the data being worked on is actually indexes into a colour table so when they are altered with the bit operations your are effectively selecting a different colour index. I suppose it would be possible to create a palette where this would work correctly - but you'd want to have a lot of spare time.

The problem with this approach is that it is SLOW. It takes a read and a write to the buffer for the mask and another for the image data. If this is going directly to video RAM it is going to be terribly slow. However it is possible to do anti-aliasing of the sprite to the background using a greyscale mask.

So did a bit of searching on the 'Net and found a quick explanation of a method to do transparent sprites that didn't rely on a mask and only ever wrote to the buffer once for each pixel that is actually shown. Unfortunately, one looses the ability to anti-aliasing, but you can't have it all.

The Technique

The technique is similar to Run Length Encoding, in that the image is processed and spans of transparent and visible pixels are calculated and encoded into a new image format.

What is done is that the mask and image are loaded into a conversion program which uses the same mask as before to determine which of the pixels in the image are actually visible and which are not. It then writes out a file containing only the visible pixels in order or drawing and a list of spans.

To draw the image, one would load the pixels and span information and start at the with the first span and draw it if it is visible or skip over it if it is not, then go on to the next span and so on.

The example code in the next section is my implementations (no guarantees about efficiency - I haven't tried to optimise it yet.) The rest of this section will be describing how I chose to implement it.

Image Format

For my target platform, I can't rely on files or external data so I have chosen to statically link all the data into the executable. I wouldn't recommend this to you unless you know what you're doing and have a really good reason for it. Therefore when I access an Image structure, assume it was loaded from a file previously.

I chose to store the pixel spans as signed 16-bit numbers and pixel data as unsigned 16-bit numbers (remember, all this code assumes 15/16 bits per pixel, but it shouldn't be too hard to make it work for other colour depths). I also chose to store the spans (also referred to as codes) separately from the image data. The original description I saw of this technique formed them into one stream.

I write in C++, but you should be able to follow the code and adapt it to C without much difficulty.

I created an Image class. This contains 2 pointers to arrays, one for the pixel data and the other for the codes (span data). I wanted to be able to support both transparent and normal images with the one structure so if the "codes" pointer is NULL, it is assumed that the image is just a standard bitmap.

I also have to take into account that some graphics cards use 15 bits per pixel (ignoring one bit at the end) and some use all 16 bits. Therefore I create all my images in 16 BPP and check at run-time if I need to convert them. If I do I convert then all once at startup. This doesn't affect the sprite drawing but I thought that I should explain what the BitsPerPixel() method is all about.

The Image class also contains basic information about the size of the sprite .

The Span Codes

I chose to use a signed 16-bit number to represent the spans. The magnitude of the number tells the number of pixels in the span, and the sign determines if the span is visible (positive) or transparent (negative). Zero is reserved as an "end of line" marker. Two consecutive zeros mean "end of the image".

Drawing the Sprite

To explain how to draw the sprite, I shall take the easy case where the entire of the sprite is to be drawn, that is it is not clipped by the edges of the target. Note that the example code takes clipping into account and draws only the pixels that will be visible on the target.

First we assign a pointer to the first code and first image data element. These are pCodes and pData respectively in the code. We also need a pointer to the target surface (pScreen). This is adjusted to point to the pixel where the top left corner of the sprite is placed. We will also need to keep track of where in the sprite we are.

Then we iterate through the codes, processing each in order until we find two consecutive zeros.

  1. If the code is zero, we have come to the end of a line, so move the target pointer to the beginning of the next row of the sprite by adding its "pitch".
  2. If the code is positive, then we have a visible span. Copy the number of pixels from the data pointer to the screen pointer, incrementing both as you go.
  3. If the code is negative, then we need to skip the number of pixels on the target so just increment the target pointer the number of pixels.
  4. Get the next code and repeat the loop.

That is simple, unfortunately, it gets more complicated when we have to consider clipping as the image data and codes are not in a format that easily allow us to skip the unused information. We have to keep track of the area of the sprite that really needs to be drawn and clip the individual spans to these borders. Luckily for you, I've done all the hard work getting this to work so you can just use my code. It is well commented for those that wish to understand exactly what is happening.

Creating the Image and Span Data

Creating the image and span data is relatively simple, start by generating the span codes by scanning the mask one line at a time from top to bottom. Count the number of consecutive black or white pixels and make a positive or negative number out of it (black = negative, white = positive).

When you reach the end of a line, end the current span and insert a zero into the codes then do the next line in the mask. When you reach the end of the mask, add an extra zero.

To generate the image data, we start at the first code and work through to the last one. If the code is positive, we add the pixel data from the image to the data stream, if it is negative we skip them.

I have included the program that I use to convert images to my data format. Note that it will output a C++ header and source file containing the data, you will have to change it to do what you want. It also is a handy demonstration of how to read monochrome and 24-bit Windows BMP files.

Example Code

I do my development with Microsoft Visual C++, but the code should be ok with any compiler. The code for drawing an Image is only a fragment so you'll have to do some work to get it going. The ConvImg program should compile fine with VC++.

The Code:

Notes on the DrawImage() Method

Refer to the Image.h file for the defination of the Image class. This could be made into a standard structure in C.

Arguments:

This function will accept both a transparent image and a "normal" one (no codes) and allows you to draw portions of the image so you don't have to draw it all. This is useful for Text - you can create a single image with all the letters and then draw only the one you need. The function will also take care of clipping the sprite to the target.

The function returns "true" on success (even if it clipped all the image) and "false" if an error occurred.

The following are the functions that DrawImage() calls.

Notes on the ConvImg Program

This is a standard C program, not C++.

The only difficulty you may have compiling this program with compilers other then Microsoft Visual C++ is getting the header files that define all the BITMAP related data structures.

This program was written to generate C++ source and header files that I compile with my game. You should convert it to write a file format that you can load at run-time, as there are many issues with statically linking large amounts of data into a program.

Basically the I use it by creating a scope (a structure) in C++ to contain the image data for a single level, then inside the definition of the scope structure (named by the <scope name> command line argument) I include the header file. I then compile and link the source file and everything is fine.

Copyright

Digital Nemesis Pty Ltd.(ACN: 085 995 213)
© Copyright Digital Nemesis Pty Ltd, 1999. All Rights Reserved.
Permission is granted to use and distribute this document and related source code free of charge
provided this and all similar messages and copyrights in the related files remains intact.