In order to keep the length of this document down, I'll just finish it here...
RLE Sprites come from the need for transparencies in sprites. Again, if you are doing a pinball
game, the ball would be a sprite. This is great, except that the background needs to show through
the corners of the sprite where there is no ball. Our previous DrawSprite routine could be extended for
this, although the results are not pretty:
PROCEDURE CDrawSprite(VAR Sprite : SpriteType; X, Y : INTEGER);
VAR
Index, XI, YI : INTEGER;
Color : BYTE;
BEGIN
Index := 0;
FOR YI := 0 TO Sprite.Height-1 DO
FOR XI := 0 TO Sprite.Width-1 DO
BEGIN
Color := Sprite.Data^[Index];
IF Color > 0 THEN
SetPixel(XI+X, YI+Y, Color);
INC(Index);
END;
END;
This requires an extra compare and jump for EVERY pixel in the sprite!!! There has to be a better
way than this! Transparancies are what make RLE sprites useful. RLE stands for Run Length Encoded,
and was historically used to compress data that had long runs of the same byte. For example:
0000001111124222222225555555
Would compress into:
6,0 5,1 1,2 1,4 8,2 7,5
Where each character is a byte. As you can see, this compressed from 28 bytes into 12 bytes.
Although this is a very good and simple algorithm, it has a terrible worst case. If there are no
two bytes of the same value next to each other, it would double the size. For RLE sprites, we
do not apply this to the actual data in the sprite, but we use it to compress the transparencies,
so that the sprite takes less space, and that the Draw routine does NOT have to do a compare for
every pixel. Here is an example: (0 means clear)
Original data: 000000000123456789000012345678900000000000000
Compressed data: 9,0 9,1,123456789 4,0 9,1,123456789 14,0
Thus, a run of transparencies is saved as one byte. The count(Number of zeros in a row) SHL 1,
with a zero as it's low bit. A run of data pixels is saved with a (Count SHL 1)+1 as it's
first byte. Following that, are Count bytes of the actual data. As we will see, this lets us
create very optimized code, and it stores all sprites well. The one worst case, where the size
of the sprite is increased by 150% is when the sprite data is a checkerboard pattern, and there are
only runs of 1 byte at the most.
The first thing that we need to use this new kind of sprite is a converter from the standard square
array of pixels to our new RLE format. This is accomplished by simply stepping along each pixel in
the sprite, and testing whether it is a clear pixel or not. If it is, simply increment a run counter
and go to the next pixel. Another performance oriented optimization is that we are not going to let
the runs wrap around onto more than one scanline. The following code illustrates this:
PROCEDURE ConvertSpriteToRLE(VAR Sprite : SpriteType);
VAR
SpriteSrc, SpriteDest : WORD;
NewSprite : SpriteType;
X, Y, I : INTEGER;
RunCount : INTEGER;
RunType : BOOLEAN;
BEGIN
NewSprite.Width := Sprite.Width;
NewSprite.Height := Sprite.Height;
NewSprite.DataLen := Sprite.Width*Sprite.Height*3 DIV 2; { * 1.5 }
NewSprite.SType := STRLE;
GETMEM(NewSprite.Data, NewSprite.DataLen);
SpriteSrc := 0; SpriteDest := 0;
FOR Y := 1 TO Sprite.Height DO
BEGIN
RunCount := 0;
RunType := Sprite.Data^[SpriteSrc] <> 0; { FALSE = Transparent }
FOR X := 1 TO Sprite.Width DO
BEGIN
IF RunType <> (Sprite.Data^[SpriteSrc] <> 0) THEN
BEGIN
NewSprite.Data^[SpriteDest] :=
(RunCount SHL 1) + (BYTE(RunType) AND 1);
INC(SpriteDest);
IF RunType = TRUE THEN
FOR I := SpriteSrc-RunCount TO SpriteSrc-1 DO
BEGIN
NewSprite.Data^[SpriteDest] := Sprite.Data^[I];
INC(SpriteDest);
END;
RunCount := 0;
RunType := Sprite.Data^[SpriteSrc] <> 0;
END;
INC(RunCount);
INC(SpriteSrc);
END;
IF RunCount > 0 THEN
BEGIN
NewSprite.Data^[SpriteDest] :=
(RunCount SHL 1) + (BYTE(RunType) AND 1);
INC(SpriteDest);
IF RunType = TRUE THEN
FOR I := SpriteSrc-RunCount TO SpriteSrc-1 DO
BEGIN
NewSprite.Data^[SpriteDest] := Sprite.Data^[I];
INC(SpriteDest);
END;
RunCount := 0;
RunType := Sprite.Data^[SpriteSrc] <> 0;
END;
END;
KillSprite(Sprite);
Sprite := NewSprite;
Sprite.DataLen := SpriteDest; { Resize the sprite data to the }
GETMEM(Sprite.Data, Sprite.DataLen); { exact amount needed }
Move(NewSprite.Data^, Sprite.Data^, Sprite.DataLen); { Copy the data }
KillSprite(NewSprite);
END;
As you can see, this is not a very exciting process, but it is very neccesary. It is also not
a very fast process, as it has to create sprite, resize them and delete them all in one call. But
it gives us an alternative much faster than testing every single pixel while drawing. This
introduces a trade-off between pre-computation and run time performance.
Now that we have these new kinds of sprites stored in memory, how are we going to draw them to the
screen? Why, the following routine would do the job nicely!
PROCEDURE DrawRLESprite(Sprite : SpriteType; X, Y : INTEGER);
VAR
I, J : INTEGER;
ScreenPtr,
SpritePtr : WORD;
Count : BYTE;
BEGIN
SpritePtr := 0;
FOR I := 0 TO Sprite.Height-1 DO
BEGIN
J := 0;
ScreenPtr := (Y+I)*Screen.Width+X;
WHILE J < Sprite.Width DO
BEGIN
Count := Sprite.Data^[SpritePtr];
INC(SpritePtr);
IF (Count AND 1) = 0 THEN { Transparant run }
BEGIN
ScreenPtr := ScreenPtr + (Count SHR 1);
J := J + (Count SHR 1);
END
ELSE { Block of pixels }
BEGIN
Count := Count SHR 1;
WHILE Count > 0 DO
BEGIN
Screen.Buffer^[ScreenPtr] := Sprite.Data^[SpritePtr];
INC(ScreenPtr); INC(J);
INC(SpritePtr); DEC(Count);
END;
END;
END;
END;
END;
This routine is just BEGGING to be converted to assembler! The loop where the block of pixels are
transfered could easily be converted into a movs instruction, and getting the run state in the
first bit of the count byte is as easy as a SHR instruction... Here we go!:
PROCEDURE DrawRLESprite(Sprite : SpriteType; X, Y : INTEGER);
VAR
I : INTEGER;
ScreenPtr,
SpritePtr : WORD;
BEGIN
SpritePtr := 0;
FOR I := 0 TO Sprite.Height-1 DO
BEGIN
ScreenPtr := (Y+I)*Screen.Width+X;
ASM
push DS
les DI, Screen.Buffer
add DI, ScreenPtr
mov DX, Sprite.Width
add DX, DI
lds SI, Sprite.Data
add SI, SpritePtr
mov AH, 0 { Clear the high byte of AX }
@XLoop:
cmp DI, DX
jae @OuttaXLoop { WHILE J < Sprite.Width DO }
mov AL, DS:[SI] { Count := Sprite.Data^[SpritePtr] }
inc SI { INC(SpritePtr) }
shr AL, 1
jnc @TransparentRun
@DataRun: { IF (Count AND 1) = 1 THEN }
mov CX, AX { WHILE Count > 0 DO }
rep movsb { Screen.Buffer^[ScreenPtr] := Sprite.Data^[SpritePtr] }
jmp @XLoop { END; }
@TransparentRun: { ELSE }
add DI, AX { ScreenPtr := ScreenPtr + (Count SHR 1) }
jmp @XLoop { END; }
@OuttaXLoop:
pop DS
sub SI, WORD [Sprite.Data]
mov SpritePtr, SI
END;
END;
END;
The main modification that I did, (besides converting it to assembler) is that I changed the XLoop
to check for when DI exceeded a value. Since DI was being updated automatically, it didn't make
sense to update J along with it... For being an inner loop, this is very fast!
PROCEDURE DrawRLESprite(Sprite : SpriteType; X, Y : INTEGER); ASSEMBLER;
VAR I, ScreenOffs : INTEGER;
ASM
push DS
les DI, Sprite
mov AX, [ES:DI+SpriteType.Height] { FOR I := 0 TO Sprite.Height-1 DO }
mov I, AX
mov BX, Y
add BX, BX
mov AX, [BX+OFFSET Screen.YTable]
add AX, X { ScreenPtr := (Y+I)*Screen.Width+X }
mov DX, [ES:DI+SpriteType.Width]
add DX, AX
mov BX, Screen.Width
les SI, ES:[DI+SpriteType.Data] { Need ES for Sprite... }
lds DI, Screen.Buffer { Need access to DS for Screen.Buffer }
add DX, DI
add DI, AX
mov AX, DS { Swap segment registers }
mov CX, ES
mov DS, CX
mov ES, AX
mov AX, DI
mov CH, 0 { Clear the high byte of AX }
@YLoop:
@XLoop:
cmp DI, DX
jae @OuttaXLoop { WHILE J < Sprite.Width DO }
mov CL, DS:[SI] { Count := Sprite.Data^[SpritePtr] }
inc SI { INC(SpritePtr) }
shr CL, 1 { Set the carry flag if Bit #0 is set }
jnc @TransparentRun
@DataRun: { IF (Count AND 1) = 1 THEN }
{ WHILE Count > 0 DO }
rep movsb { Screen.Buffer^[ScreenPtr] := Sprite.Data^[SpritePtr] }
jmp @XLoop { END; }
@TransparentRun: { ELSE }
add DI, CX { ScreenPtr := ScreenPtr + (Count SHR 1) }
jmp @XLoop { END; }
@OuttaXLoop:
add AX, BX { DI := DI + Screen.Width }
mov DI, AX
add DX, BX { End of next scanline }
dec I { Next YLoop }
jnz @YLoop
pop DS
END;
Instead of using AX in this example, I'm using CX... Only because I ran out of registers. The only
"Tricky" thing that I'm doing here is to swap the segment registers... I need to access Screen.Buffer
with the DS register, and Sprite.Data with the ES register... Loading one clobbers the other... -Sigh-
So we just have to swap the segment registers... And of course we can't just go: xchg ES, DS. What
everyone needs is a protected mode (386) Pascal compiler that lets you do anything that you want...
like use EAX and FS... Just a wishlist!
Gosh, you just have to have an example program! This, of course, needs the updated GraphPro and
Sprite libraries available here. This draws a sprite on the screen, then
moves it around, showing off it's transparency and it's speed...
PROGRAM RLESpriteTester;
USES GraphPro, Sprite;
PROCEDURE ConvertSpriteToRLE(VAR Sprite : SpriteType);
VAR
SpriteSrc, SpriteDest : WORD;
NewSprite : SpriteType;
X, Y, I : INTEGER;
RunCount : INTEGER;
RunType : BOOLEAN;
BEGIN
NewSprite.Width := Sprite.Width;
NewSprite.Height := Sprite.Height;
NewSprite.DataLen := Sprite.Width*Sprite.Height*3 DIV 2; { * 1.5 }
NewSprite.SType := STRLE;
GETMEM(NewSprite.Data, NewSprite.DataLen);
SpriteSrc := 0; SpriteDest := 0;
FOR Y := 1 TO Sprite.Height DO
BEGIN
RunCount := 0;
RunType := Sprite.Data^[SpriteSrc] <> 0; { FALSE = Transparent }
FOR X := 1 TO Sprite.Width DO
BEGIN
IF RunType <> (Sprite.Data^[SpriteSrc] <> 0) THEN
BEGIN
NewSprite.Data^[SpriteDest] :=
(RunCount SHL 1) + (BYTE(RunType) AND 1);
INC(SpriteDest);
IF RunType = TRUE THEN
FOR I := SpriteSrc-RunCount TO SpriteSrc-1 DO
BEGIN
NewSprite.Data^[SpriteDest] := Sprite.Data^[I];
INC(SpriteDest);
END;
RunCount := 0;
RunType := Sprite.Data^[SpriteSrc] <> 0;
END;
INC(RunCount);
INC(SpriteSrc);
END;
IF RunCount > 0 THEN
BEGIN
NewSprite.Data^[SpriteDest] :=
(RunCount SHL 1) + (BYTE(RunType) AND 1);
INC(SpriteDest);
IF RunType = TRUE THEN
FOR I := SpriteSrc-RunCount TO SpriteSrc-1 DO
BEGIN
NewSprite.Data^[SpriteDest] := Sprite.Data^[I];
INC(SpriteDest);
END;
RunCount := 0;
RunType := Sprite.Data^[SpriteSrc] <> 0;
END;
END;
KillSprite(Sprite);
Sprite := NewSprite;
Sprite.DataLen := SpriteDest; { Resize the sprite data to the }
GETMEM(Sprite.Data, Sprite.DataLen); { exact amount needed }
Move(NewSprite.Data^, Sprite.Data^, Sprite.DataLen); { Copy the data }
KillSprite(NewSprite);
END;
VAR
TestSprite : SpriteType;
I : INTEGER;
BEGIN
InitGraph;
Line(31, 16, 31, 47, 9);
Line(16, 31, 47, 31, 10);
Line(0, 0, 63, 63, 15);
Line(63, 0, 0, 63, 12); { Draw a pattern for the sprite }
GetSprite(TestSprite, 0, 0, 63, 63);
ConvertSpriteToRLE(TestSprite);
FOR I := 0 TO 319-64 DO
DrawRLESprite(TestSprite, I, 66);
KillSprite(TestSprite);
READLN;
Line( 0, 0, 31, 0, 15);
Line( 0, 31, 31, 31, 15);
Line( 0, 0, 0, 31, 15);
Line(31, 31, 31, 0, 15);
GetSprite(TestSprite, 0, 0, 31, 31); { Notice that it captures the cursor }
ConvertSpriteToRLE(TestSprite); { too... }
FOR I := 0 TO 319-32 DO
DrawRLESprite(TestSprite, I, 199-32);
READLN;
CloseGraph;
END.