WGT Graphics Tutorial #4
		   Topic: Dirty Rectangle Animation
			  By Chris Egerter
			  January 23, 1995
	     Contact me at: chris.egerter@homebase.com
		Compuserve: 75242,2411


For this tutorial I chose to use WGT 4.0 for the basic image and
palette routines.  It was compiled and tested with Borland C++ 3.1.

First I should point out that I developed this technique on my own,
and have not read other texts about dirty rectangles.  In fact, I had been
using this technique for a couple of years before the term
"dirty rectangle" had even been mentioned to me.  If this code is
anything like Michael Abrash's article from Dr. Dobb's magazine, or any
other implementation, it is purely coincidental because I haven't read it!

Our goal here is to move several sprites around on the screen.  The
term "sprite" as I use it just refers to a moving figure.  PC's don't
have hardware sprites so we have to draw the images on the screen
ourselves.

The First Attempt
-----------------
Let's make a program which moves some sprites around the screen
without destroying the background.  We don't need anything fancy at first,
just something that will keep track of the sprite positions and update
the screen.

    A simple, brute force method of animation is outlined below:

    1. Make two virtual 320x200 pages in memory.
       Call one backgroundscreen, and the other workscreen.
       Backgroundscreen contains an image which remains behind all
       sprites.  Workscreen is used to construct each frame of the
       animation.

    2. Copy the backgroundscreen to the workscreen.

    3. Move the sprites to their new location.

    4. Put the sprite images on the workscreen.

    5. Copy the workscreen to the VGA's video memory.

    6. Repeat steps 2-5.


This method is slow because it copies 128k of memory for
each frame, without even drawing the sprites themselves.

This technique is shown in the animate1.c file.  Our main program
block looks like this:

void main (void)
{
 vga256 ();

 load_graphics ();

 initialize_sprites ();

 do {
  copypage (backgroundscreen, workscreen);
  /* Copy the background to our work screen, erasing the previous frame */

  draw_and_move_sprites ();
  /* Draw the sprites overtop the work screen */

  wretrace ();
  copypage (workscreen, NULL);
  /* Copy the work screen to the visual page */
 } while (!kbhit ());

 free_graphics ();
 wsetmode (3);
}


The copypage routine is something I built specifically for this
example. It quickly copies 16000 doublewords using the rep movsd command
in assembly.  You could also use wcopyscreen, but it won't be quite as
fast.  The copypage code is shown below:

void copypage (block source, block dest)
{
// wcopyscreen (0, 0, 319, 199, source, 0, 0, dest);

 if (dest == NULL)
   dest = MK_FP (0xA000, 0x0000);
 else
   dest+=4;

 if (source == NULL)
   source = MK_FP (0xA000, 0x0000);
 else
  source += 4;

 asm {
   .386
   push ds
   cld
   lds si, source
   les di, dest
   mov cx, 16000
   rep movsd
   pop ds
  }
}

You can see that if either the source or destination is NULL, it
creates a pointer to the VGA's memory.  Otherwise, it adds 4 to the
pointer to skip over the width and height integers stored in every WGT
block.  I assume each screen is 320x200 so I ignored these bytes.


Next we need some kind of sprite structure to store the position,
image number, speed, and direction of each object.

/* Our sprite structure */
typedef struct
 {
  int x, y;		/* Coordinate on the screen */
  int num;		/* Index into the sprite_image array of blocks */
  int dx, dy;		/* speed in the x and y direction */
  int width, height;	/* Width and height of the sprite's image */
 } sprite;

sprite objects[NUM_SPRITES];	/* an array of sprites */


As well, a routine is used to set up the initial values of this sprite
array.  It sets the coordinates to a random position on the screen, and
the direction of movement to down and right.

void initialize_sprites (void)
/* Set up the initial values in the sprite array */
{
int i;
sprite *spriteptr;

 spriteptr = objects;
 for (i = 0; i < NUM_SPRITES; i++)
  {
   spriteptr->num = 0;
   /* Image number 0 */

   spriteptr->width = wgetblockwidth (sprite_images[spriteptr->num]);
   spriteptr->height = wgetblockheight (sprite_images[spriteptr->num]);
   /* width and height are the size of the image # num */

   spriteptr->x = rand () % 320 - spriteptr->width;
   spriteptr->y = rand () % 200 - spriteptr->height;
   /* Pick a random coordinate */

   spriteptr->dx = SPEED;
   spriteptr->dy = SPEED;
   /* Moving down and right */

   spriteptr++; /* Next sprite */
  }
}


The sprites will move in a simple manner.  If they reach the edge of
the screen, they will switch directions, either horizontally or
vertically depending on which edge is hit.  To draw each sprite, we use
the wputblock routine with xray mode.



void draw_and_move_sprites (void)
/* Moves each sprite based on the speed and direction, and bounces them
  off the side of the screen if needed.  It then draws the sprite on the
  work screen.   Sprites are drawn from lowest to highest, meaning the
  higher numbered sprites will be above the rest. */
{
int i;
sprite *spriteptr;

  wsetscreen (workscreen);

  spriteptr = objects;

  for (i = 0; i < NUM_SPRITES; i++)
   {
    spriteptr->num++;		/* Animate the sprite through images 0-29 */
    if (spriteptr->num > 29)
       spriteptr->num = 0;

    /* Since we changed sprites, we need to get the new width and height
       of the image.  Only do this when you change spriteptr->num. */
    spriteptr->width = wgetblockwidth (sprite_images[spriteptr->num]);
    spriteptr->height = wgetblockheight (sprite_images[spriteptr->num]);

    spriteptr->x += spriteptr->dx;
    spriteptr->y += spriteptr->dy;
    /* Add the speed/direction to the current coordinate */

    if (spriteptr->x > 319 - spriteptr->width)
      spriteptr->dx = -SPEED;
    else if (spriteptr->x < 0)
      spriteptr->dx = SPEED;
    /* Change the direction horizontally if needed */

    if (spriteptr->y > 199 - spriteptr->height)
      spriteptr->dy = -SPEED;
    else if (spriteptr->y < 0)
      spriteptr->dy = SPEED;
    /* Change the direction vertically if needed */

    wputblock (spriteptr->x, spriteptr->y, sprite_images[spriteptr->num], 1);
    /* Draw the sprite with xray copy */

    spriteptr++;   /* Next sprite */
   }
}


That's the meat of our first animation engine.  Try running
animate1.exe to see what it does.  Notice the speed isn't very good.
For our next attempt, we will use a different method to update the screen
faster.


The Dirty Rectangle Technique
-----------------------------
The first attempt was slow because of the amount of memory we had
to move each frame.  To erase the sprites, we copied the whole background
screen to the workscreen.  We can improve this by copying only the
rectangles occupied by the sprites.

A sprite's bounding rectangle is based on the x,y coordinates, and the
width and height of the sprite image.

 x, y
  ÚÄÄÄÄÄÄÄÄ¿
  ³########³
  ³########³
  ³########³
  ÀÄÄÄÄÄÄÄÄÙ
	  x2, y2

Where: x2 = x + width  - 1
and    y2 = y + height - 1

I will use the # sign to indicate the sprite is drawn, and a . to indicate
the sprite was erased.

We know these values for each sprite, so to erase the sprites we can
copy each bounding rectangle from the backgroundscreen to the workscreen.
ie: wcopyscreen (x, y, x2, y2, backgroundscreen, x, y, workscreen);

Great.  We've eliminated one of the 64k memory transfers.  The biggest
bottleneck still remains however.  Copying 64k to the video memory
every frame isn't very efficient.  On faster computers with a local
bus video this may not be a problem anyway, but there are faster
ways of doing this kind of animation.

The dirty rectangle method works like this:

 1. Erase the old sprite by copying the background screen onto the
    work screen.  Only copy the rectangle bounded by each sprite.

 2. Move the sprites to their new location, and draw them on the
    work screen.

 3. Set the current dirty rectangle to the current position of the
    sprite.  That is, set x, y, x2 and y2.

 4. Expand the dirty rectangle to include the old position.  The
    rectangulur area is copied from the work screen to the visual
    screen.  By expanding the rectangle, we update the area where the
    sprite used to be.

 5. Set the old dirty rectangle to the current dirty rectangle.

 6. Repeat steps 1-5.



In case you didn't quite understand that, here is a step by step
example.

--------------------------------Frame 0-----------------------------------
 x, y
  ÚÄÄÄÄÄÄÄÄ¿
  ³########³
  ³########³
  ³########³
  ÀÄÄÄÄÄÄÄÄÙ
	  x2, y2

The sprite is drawn on the screen initially at x,y.



--------------------------------Frame 1-----------------------------------
 x, y
  ÚÄÄÄÄÄÄÄÄ¿
  ³........³
  ³........³
  ³........³
  ÀÄÄÄÄÄÄÄÄÙ
	  x2, y2

The rectangle bounding the sprite is copied from the background screen,
which erases the sprite.


--------------------------------Frame 2-----------------------------------
 x, y
  ÚÄÄÄÄÄÄÄÄ¿
  ³........³
  ³........³
  ³........³
  ÀÄÄÄÄÄÄÄÄÙ
	  x2, y2

		 x + dx, y + dy
		       ÚÄÄÄÄÄÄÄÄ¿
		       ³########³
		       ³########³
		       ³########³
		       ÀÄÄÄÄÄÄÄÄÙ
			   x2 + dx, y2 + dy


The sprite is moved based on the dx and dy values.  The sprite is then
drawn at the new location.


--------------------------------Frame 3-----------------------------------
 x, y
  ÚÄÄÄÄÄÄÄÄ¿
  ³........³
  ³........³
  ³........³
  ÀÄÄÄÄÄÄÄÄÙ
	  x2, y2

		 x + dx, y + dy
		       ++++++++++
		       +########+
		       +########+
		       +########+
		       ++++++++++
			   x2 + dx, y2 + dy


The dirty rectangle is set to the current sprite location.  In this case,
the dirty rectangle is at (x + dx, y + dy) to (x2 + dx, y2 + dy).  The
plus signs show the rectangle.





--------------------------------Frame 4-----------------------------------
 x, y
  +++++++++++++++++++++++++++++++
  +........³                    +
  +........³                    +
  +........³                    +
  +ÄÄÄÄÄÄÄÄÙ                    +
  +  	  x2, y2                +
  +				+
  +	 	 x + dx, y + dy +
  +	       	       ÚÄÄÄÄÄÄÄÄ+
  +	       	       ³########+
  +	       	       ³########+
  +	       	       ³########+
  +++++++++++++++++++++++++++++++
			   x2 + dx, y2 + dy


The rectangle is expanded to include the old position which was erased.
This whole rectangle is then copied from the work screen to the visual
screen.  You can see that this will draw the new sprite, and erase the old
one at the same time.


We will need to include the rectangle boundaries in our sprite structure.
The old dirty rectangle from the previous frame is stored in
ox, oy, ox2, oy2 for each sprite.

typedef struct
 {
  int x, y;		/* Coordinate on the screen */
  int num;		/* Index into the sprite_image array of blocks */
  int dx, dy;		/* speed in the x and y direction */
  int width, height;	/* Width and height of the sprite's image */

  int ox, oy, ox2, oy2;
 } sprite;


We also require the current dirty rectangle.  These variables will be
reused for each sprite.

int rx, ry, rx2, ry2;


Our new initialize_sprites routine needs to set the old dirty rectangle for
each sprite.  It looks like this:

void initialize_sprites (void)
/* Set up the initial values in the sprite array */
{
int i;
sprite *spriteptr;

 spriteptr = objects;
 for (i = 0; i < NUM_SPRITES; i++)
  {
   spriteptr->num = 0;
   /* Image number 0 */

   spriteptr->width = wgetblockwidth (sprite_images[spriteptr->num]);
   spriteptr->height = wgetblockheight (sprite_images[spriteptr->num]);
   /* width and height are the size of the image # num */

   spriteptr->x = rand () % 320 - spriteptr->width;
   spriteptr->y = rand () % 200 - spriteptr->height;
   /* Pick a random coordinate */

   spriteptr->dx = SPEED;
   spriteptr->dy = SPEED;
   /* Moving down and right */

   spriteptr->ox = spriteptr->x;
   spriteptr->oy = spriteptr->y;
   spriteptr->ox2 = spriteptr->x + spriteptr->width - 1;
   spriteptr->oy2 = spriteptr->y + spriteptr->height - 1;

   spriteptr++; /* Next sprite */
  }
}



Next we need a routine to erase the sprites.  This simply takes each
dirty rectangle and copies that portion from the background screen to
the work screen.


void erase_sprites (void)
/* Erases each sprite by copying the section from the background screen. */
{
int i;
sprite *spriteptr;

int x, y, x2, y2;


  wsetscreen (workscreen);

  spriteptr = objects;

  for (i = 0; i < NUM_SPRITES; i++)
   {
    x = spriteptr->ox;		/* Get the old dirty rectangle coordinates */
    y = spriteptr->oy;
    x2 = spriteptr->ox2;
    y2 = spriteptr->oy2;

    if (x < 0)			/* Clip them, but don't change the original */
	x = 0;			/* values, because we need them later */
    else if (x > 319)
	x = 319;
    if (y < 0)
	y = 0;
    else if (y > 199)
	y = 199;

    wcopyscreen (x, y, x2, y2, backgroundscreen, x, y, workscreen);

    spriteptr++;   /* Next sprite */
   }
}



Our routine to expand the dirty rectangle to a new size consists of a
series of if statements which compare the minimum and maximum values.
If the new coordinate is lower or higher than the current value, the
current value becomes the new value.  We also clip the rectangle to the
screen edges.

void expand_dirty_rectangle (int sprite_num, int x, int y, int x2, int y2)
/* Find boundaries of the old and new sprite rectangle */
{
sprite *spriteptr;

 spriteptr = &objects[sprite_num];

 if (x < rx)
     rx = x;
 if (x2 > rx2)
     rx2 = x2;
 if (y < ry)
     ry = y;
 if (y2 > ry2)
     ry2 = y2;


  if (rx < 0)
      rx = 0;

  if (rx2 > 319)
      rx2 = 319;

  if (ry < 0)
      ry = 0;

  if (ry2 > 199)
      ry2 = 199;
}


The draw and move routine remains the same as it was in the first method.
The final code required is the copy_sprites routine.  It goes through each
sprite and sets the current dirty rectangle to the image's boundaries.
It then expands the rectangle to include the previous frame, and copies
the this area to the visual page.  The current rectangle (not expanded)
is then copied to the old rectangle values in the sprite structure.


void copy_sprites (void)
{
int i;
sprite *spriteptr;
int x, y, x2, y2;

  spriteptr = objects;
  for (i = 0; i < NUM_SPRITES; i++)
   {
    /* Store these values because they are used more than once */
    x  = spriteptr->x;
    y  = spriteptr->y;
    x2 = spriteptr->x + spriteptr->width - 1;
    y2 = spriteptr->y + spriteptr->height - 1;

    /* Set the dirty rectangle to the current position of the sprite */
    rx  = x;
    ry  = y;
    rx2 = x2;
    ry2 = y2;

    expand_dirty_rectangle (i, spriteptr->ox, spriteptr->oy,
			       spriteptr->ox2, spriteptr->oy2);

    wcopyscreen (rx, ry, rx2, ry2, workscreen, rx, ry, NULL);

    spriteptr->ox = x;
    spriteptr->oy = y;
    spriteptr->ox2 = x2;
    spriteptr->oy2 = y2;

    spriteptr++;

   }
}



Our main block now looks like this.  There is very little different in the
main routine, but the speed increase is dramatic.

void main (void)
{
 vga256 ();

 load_graphics ();

 initialize_sprites ();

 do {

  erase_sprites ();
  /* Erase the previous frame from the work screen */

  draw_and_move_sprites ();
  /* Draw the sprites overtop the work screen */

  wretrace ();
  copy_sprites ();

 } while (!kbhit ());


 free_graphics ();
 wsetmode (3);
}