_GRAPHICS PROGRAMMING COLUMN_ by Michael Abrash [LISTING ONE] /* Sample simple dirty-rectangle animation program, partially optimized and featuring internal animation, masked images (sprites), and nonoverlapping dirty rectangle copying. Tested with Borland C++ 3.0 in the small model. */ #include #include #include #include #include /* Comment out to disable overlap elimination in the dirty rectangle list. */ #define CHECK_OVERLAP 1 #define SCREEN_WIDTH 320 #define SCREEN_HEIGHT 200 #define SCREEN_SEGMENT 0xA000 /* Describes a dirty rectangle */ typedef struct { void *Next; /* pointer to next node in linked dirty rect list */ int Top; int Left; int Right; int Bottom; } DirtyRectangle; /* Describes an animated object */ typedef struct { int X; /* upper left corner in virtual bitmap */ int Y; int XDirection; /* direction and distance of movement */ int YDirection; int InternalAnimateCount; /* tracking internal animation state */ int InternalAnimateMax; /* maximum internal animation state */ } Entity; /* Storage used for dirty rectangles */ #define MAX_DIRTY_RECTANGLES 100 int NumDirtyRectangles; DirtyRectangle DirtyRectangles[MAX_DIRTY_RECTANGLES]; /* Head/tail of dirty rectangle list */ DirtyRectangle DirtyHead; /* If set to 1, ignore dirty rectangle list and copy the whole screen. */ int DrawWholeScreen = 0; /* Pixels and masks for the two internally animated versions of the image we'll animate */ #define IMAGE_WIDTH 13 #define IMAGE_HEIGHT 11 char ImagePixels0[] = { 0, 0, 0, 9, 9, 9, 9, 9, 0, 0, 0, 0, 0, 0, 0, 9, 9, 9, 9, 9, 9, 9, 0, 0, 0, 0, 0, 9, 9, 0, 0,14,14,14, 9, 9, 0, 0, 0, 9, 9, 0, 0, 0, 0,14,14,14, 9, 9, 0, 0, 9, 9, 0, 0, 0, 0,14,14,14, 9, 9, 0, 0, 9, 9,14, 0, 0,14,14,14,14, 9, 9, 0, 0, 9, 9,14,14,14,14,14,14,14, 9, 9, 0, 0, 9, 9,14,14,14,14,14,14,14, 9, 9, 0, 0, 0, 9, 9,14,14,14,14,14, 9, 9, 0, 0, 0, 0, 0, 9, 9, 9, 9, 9, 9, 9, 0, 0, 0, 0, 0, 0, 0, 9, 9, 9, 9, 9, 0, 0, 0, 0, 0, }; char ImageMask0[] = { 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, }; char ImagePixels1[] = { 0, 0, 0, 9, 9, 9, 9, 9, 0, 0, 0, 0, 9, 0, 0, 9, 9, 9, 9, 9, 9, 9, 0, 9, 9, 9, 0, 9, 9, 0, 0,14,14,14, 9, 9, 9, 9, 0, 9, 9, 0, 0, 0, 0,14,14,14, 0, 0, 0, 0, 9, 9, 0, 0, 0, 0,14,14, 0, 0, 0, 0, 0, 9, 9,14, 0, 0,14,14,14, 0, 0, 0, 0, 0, 9, 9,14,14,14,14,14,14, 0, 0, 0, 0, 0, 9, 9,14,14,14,14,14,14,14, 0, 0, 0, 0, 0, 9, 9,14,14,14,14,14, 9, 9, 9, 9, 0, 0, 0, 9, 9, 9, 9, 9, 9, 9, 0, 9, 9, 9, 0, 0, 0, 9, 9, 9, 9, 9, 0, 0, 0, 9, 9, }; char ImageMask1[] = { 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, }; /* Pointers to pixel and mask data for various internally animated versions of our animated image. */ char * ImagePixelArray[] = {ImagePixels0, ImagePixels1}; char * ImageMaskArray[] = {ImageMask0, ImageMask1}; /* Animated entities */ #define NUM_ENTITIES 15 Entity Entities[NUM_ENTITIES]; /* Pointer to system buffer into which we'll draw */ char far *SystemBufferPtr; /* Pointer to screen */ char far *ScreenPtr; void EraseEntities(void); void CopyDirtyRectanglesToScreen(void); void DrawEntities(void); void AddDirtyRect(Entity *, int, int); void DrawMasked(char far *, char *, char *, int, int, int); void FillRect(char far *, int, int, int, int); void CopyRect(char far *, char far *, int, int, int, int); void main() { int i, XTemp, YTemp; unsigned int TempCount; char far *TempPtr; union REGS regs; /* Allocate memory for the system buffer into which we'll draw */ if (!(SystemBufferPtr = farmalloc((unsigned int)SCREEN_WIDTH* SCREEN_HEIGHT))) { printf("Couldn't get memory\n"); exit(1); } /* Clear the system buffer */ TempPtr = SystemBufferPtr; for (TempCount = ((unsigned)SCREEN_WIDTH*SCREEN_HEIGHT); TempCount--; ) { *TempPtr++ = 0; } /* Point to the screen */ ScreenPtr = MK_FP(SCREEN_SEGMENT, 0); /* Set up the entities we'll animate, at random locations */ randomize(); for (i = 0; i < NUM_ENTITIES; i++) { Entities[i].X = random(SCREEN_WIDTH - IMAGE_WIDTH); Entities[i].Y = random(SCREEN_HEIGHT - IMAGE_HEIGHT); Entities[i].XDirection = 1; Entities[i].YDirection = -1; Entities[i].InternalAnimateCount = i & 1; Entities[i].InternalAnimateMax = 2; } /* Set the dirty rectangle list to empty, and set up the head/tail node as a sentinel */ NumDirtyRectangles = 0; DirtyHead.Next = &DirtyHead; DirtyHead.Top = 0x7FFF; DirtyHead.Left= 0x7FFF; DirtyHead.Bottom = 0x7FFF; DirtyHead.Right = 0x7FFF; /* Set 320x200 256-color graphics mode */ regs.x.ax = 0x0013; int86(0x10, ®s, ®s); /* Loop and draw until a key is pressed */ do { /* Draw the entities to the system buffer at their current locations, updating the dirty rectangle list */ DrawEntities(); /* Draw the dirty rectangles, or the whole system buffer if appropriate */ CopyDirtyRectanglesToScreen(); /* Reset the dirty rectangle list to empty */ NumDirtyRectangles = 0; DirtyHead.Next = &DirtyHead; /* Erase the entities in the system buffer at their old locations, updating the dirty rectangle list */ EraseEntities(); /* Move the entities, bouncing off the edges of the screen */ for (i = 0; i < NUM_ENTITIES; i++) { XTemp = Entities[i].X + Entities[i].XDirection; YTemp = Entities[i].Y + Entities[i].YDirection; if ((XTemp < 0) || ((XTemp + IMAGE_WIDTH) > SCREEN_WIDTH)) { Entities[i].XDirection = -Entities[i].XDirection; XTemp = Entities[i].X + Entities[i].XDirection; } if ((YTemp < 0) || ((YTemp + IMAGE_HEIGHT) > SCREEN_HEIGHT)) { Entities[i].YDirection = -Entities[i].YDirection; YTemp = Entities[i].Y + Entities[i].YDirection; } Entities[i].X = XTemp; Entities[i].Y = YTemp; } } while (!kbhit()); getch(); /* clear the keypress */ /* Back to text mode */ regs.x.ax = 0x0003; int86(0x10, ®s, ®s); } /* Draw entities at their current locations, updating dirty rectangle list. */ void DrawEntities() { int i; char far *RowPtrBuffer; char *TempPtrImage; char *TempPtrMask; Entity *EntityPtr; for (i = 0, EntityPtr = Entities; i < NUM_ENTITIES; i++, EntityPtr++) { /* Remember the dirty rectangle info for this entity */ AddDirtyRect(EntityPtr, IMAGE_HEIGHT, IMAGE_WIDTH); /* Point to the destination in the system buffer */ RowPtrBuffer = SystemBufferPtr + (EntityPtr->Y * SCREEN_WIDTH) + EntityPtr->X; /* Advance the image animation pointer */ if (++EntityPtr->InternalAnimateCount >= EntityPtr->InternalAnimateMax) { EntityPtr->InternalAnimateCount = 0; } /* Point to the image and mask to draw */ TempPtrImage = ImagePixelArray[EntityPtr->InternalAnimateCount]; TempPtrMask = ImageMaskArray[EntityPtr->InternalAnimateCount]; DrawMasked(RowPtrBuffer, TempPtrImage, TempPtrMask, IMAGE_HEIGHT, IMAGE_WIDTH, SCREEN_WIDTH); } } /* Copy the dirty rectangles, or the whole system buffer if appropriate, to the screen. */ void CopyDirtyRectanglesToScreen() { int i, RectWidth, RectHeight; unsigned int Offset; DirtyRectangle * DirtyPtr; if (DrawWholeScreen) { /* Just copy the whole buffer to the screen */ DrawWholeScreen = 0; CopyRect(ScreenPtr, SystemBufferPtr, SCREEN_HEIGHT, SCREEN_WIDTH, SCREEN_WIDTH, SCREEN_WIDTH); } else { /* Copy only the dirty rectangles, in the YX-sorted order in which they're linked */ DirtyPtr = DirtyHead.Next; for (i = 0; i < NumDirtyRectangles; i++) { /* Offset in both system buffer and screen of image */ Offset = (unsigned int) (DirtyPtr->Top * SCREEN_WIDTH) + DirtyPtr->Left; /* Dimensions of dirty rectangle */ RectWidth = DirtyPtr->Right - DirtyPtr->Left; RectHeight = DirtyPtr->Bottom - DirtyPtr->Top; /* Copy a dirty rectangle */ CopyRect(ScreenPtr + Offset, SystemBufferPtr + Offset, RectHeight, RectWidth, SCREEN_WIDTH, SCREEN_WIDTH); /* Point to the next dirty rectangle */ DirtyPtr = DirtyPtr->Next; } } } /* Erase the entities in the system buffer at their current locations, updating the dirty rectangle list. */ void EraseEntities() { int i; char far *RowPtr; for (i = 0; i < NUM_ENTITIES; i++) { /* Remember the dirty rectangle info for this entity */ AddDirtyRect(&Entities[i], IMAGE_HEIGHT, IMAGE_WIDTH); /* Point to the destination in the system buffer */ RowPtr = SystemBufferPtr + (Entities[i].Y * SCREEN_WIDTH) + Entities[i].X; /* Clear the rectangle */ FillRect(RowPtr, IMAGE_HEIGHT, IMAGE_WIDTH, SCREEN_WIDTH, 0); } } /* Add a dirty rectangle to the list. The list is maintained in top-to-bottom, left-to-right (YX sorted) order, with no pixel ever included twice, to minimize the number of display memory accesses and to avoid screen artifacts resulting from a large time interval between erasure and redraw for a given object or for adjacent objects. The technique used is to check for overlap between the rectangle and all rectangles already in the list. If no overlap is found, the rectangle is added to the list. If overlap is found, the rectangle is broken into nonoverlapping pieces, and the pieces are added to the list by recursive calls to this function. */ void AddDirtyRect(Entity * pEntity, int ImageHeight, int ImageWidth) { DirtyRectangle * DirtyPtr; DirtyRectangle * TempPtr; Entity TempEntity; int i; if (NumDirtyRectangles >= MAX_DIRTY_RECTANGLES) { /* Too many dirty rectangles; just redraw the whole screen */ DrawWholeScreen = 1; return; } /* Remember this dirty rectangle. Break up if necessary to avoid overlap with rectangles already in the list, then add whatever rectangles are left, in YX sorted order */ #ifdef CHECK_OVERLAP /* Check for overlap with existing rectangles */ TempPtr = DirtyHead.Next; for (i = 0; i < NumDirtyRectangles; i++, TempPtr = TempPtr->Next) { if ((TempPtr->Left < (pEntity->X + ImageWidth)) && (TempPtr->Right > pEntity->X) && (TempPtr->Top < (pEntity->Y + ImageHeight)) && (TempPtr->Bottom > pEntity->Y)) { /* We've found an overlapping rectangle. Calculate the rectangles, if any, remaining after subtracting out the overlapped areas, and add them to the dirty list */ /* Check for a nonoverlapped left portion */ if (TempPtr->Left > pEntity->X) { /* There's definitely a nonoverlapped portion at the left; add it, but only to at most the top and bottom of the overlapping rect; top and bottom strips are taken care of below */ TempEntity.X = pEntity->X; TempEntity.Y = max(pEntity->Y, TempPtr->Top); AddDirtyRect(&TempEntity, min(pEntity->Y + ImageHeight, TempPtr->Bottom) - TempEntity.Y, TempPtr->Left - pEntity->X); } /* Check for a nonoverlapped right portion */ if (TempPtr->Right < (pEntity->X + ImageWidth)) { /* There's definitely a nonoverlapped portion at the right; add it, but only to at most the top and bottom of the overlapping rect; top and bottom strips are taken care of below */ TempEntity.X = TempPtr->Right; TempEntity.Y = max(pEntity->Y, TempPtr->Top); AddDirtyRect(&TempEntity, min(pEntity->Y + ImageHeight, TempPtr->Bottom) - TempEntity.Y, (pEntity->X + ImageWidth) - TempPtr->Right); } /* Check for a nonoverlapped top portion */ if (TempPtr->Top > pEntity->Y) { /* There's a top portion that's not overlapped */ TempEntity.X = pEntity->X; TempEntity.Y = pEntity->Y; AddDirtyRect(&TempEntity, TempPtr->Top - pEntity->Y, ImageWidth); } /* Check for a nonoverlapped bottom portion */ if (TempPtr->Bottom < (pEntity->Y + ImageHeight)) { /* There's a bottom portion that's not overlapped */ TempEntity.X = pEntity->X; TempEntity.Y = TempPtr->Bottom; AddDirtyRect(&TempEntity, (pEntity->Y + ImageHeight) - TempPtr->Bottom, ImageWidth); } /* We've added all non-overlapped portions to the dirty list */ return; } } #endif /* CHECK_OVERLAP */ /* There's no overlap with any existing rectangle, so we can just add this rectangle as-is */ /* Find the YX-sorted insertion point. Searches will always terminate, because the head/tail rectangle is set to the maximum values */ TempPtr = &DirtyHead; while (((DirtyRectangle *)TempPtr->Next)->Top < pEntity->Y) { TempPtr = TempPtr->Next; } while ((((DirtyRectangle *)TempPtr->Next)->Top == pEntity->Y) && (((DirtyRectangle *)TempPtr->Next)->Left < pEntity->X)) { TempPtr = TempPtr->Next; } /* Set the rectangle and actually add it to the dirty list */ DirtyPtr = &DirtyRectangles[NumDirtyRectangles++]; DirtyPtr->Left = pEntity->X; DirtyPtr->Top = pEntity->Y; DirtyPtr->Right = pEntity->X + ImageWidth; DirtyPtr->Bottom = pEntity->Y + ImageHeight; DirtyPtr->Next = TempPtr->Next; TempPtr->Next = DirtyPtr; } [LISTING TWO] ; Assembly language helper routines for dirty rectangle animation. Tested with ; TASM 3.0. Fills a rectangle in the specified buffer. C-callable as: ; void FillRect(char far * BufferPtr, int RectHeight, int RectWidth, ; int BufferWidth, int Color); .model small .code parms struc dw ? ;pushed BP dw ? ;pushed return address BufferPtr dd ? ;far pointer to buffer in which to fill RectHeight dw ? ;height of rectangle to fill RectWidth dw ? ;width of rectangle to fill BufferWidth dw ? ;width of buffer in which to fill Color dw ? ;color with which to fill parms ends public _FillRect _FillRect proc near cld push bp mov bp,sp push di les di,[bp+BufferPtr] mov dx,[bp+RectHeight] mov bx,[bp+BufferWidth] sub bx,[bp+RectWidth] ;distance from end of one dest scan ; to start of next mov al,byte ptr [bp+Color] mov ah,al ;double the color for REP STOSW RowLoop: mov cx,[bp+RectWidth] shr cx,1 rep stosw adc cx,cx rep stosb add di,bx ;point to next scan to fill dec dx ;count down rows to fill jnz RowLoop pop di pop bp ret _FillRect endp ; Draws a masked image (a sprite) to the specified buffer. C-callable as: ; void DrawMasked(char far * BufferPtr, char * Pixels, char * Mask, ; int ImageHeight, int ImageWidth, int BufferWidth); parms2 struc dw ? ;pushed BP dw ? ;pushed return address BufferPtr2 dd ? ;far pointer to buffer in which to draw Pixels dw ? ;pointer to image pixels Mask dw ? ;pointer to image mask ImageHeight dw ? ;height of image to draw ImageWidth dw ? ;width of image to draw BufferWidth2 dw ? ;width of buffer in which to draw parms2 ends public _DrawMasked _DrawMasked proc near cld push bp mov bp,sp push si push di les di,[bp+BufferPtr2] mov si,[bp+Mask] mov bx,[bp+Pixels] mov dx,[bp+ImageHeight] mov ax,[bp+BufferWidth2] sub ax,[bp+ImageWidth] ;distance from end of one dest scan mov [bp+BufferWidth2],ax ; to start of next RowLoop2: mov cx,[bp+ImageWidth] ColumnLoop: lodsb ;get the next mask byte and al,al ;draw this pixel? jz SkipPixel ;no mov al,[bx] ;yes, draw the pixel mov es:[di],al SkipPixel: inc bx ;point to next source pixel inc di ;point to next dest pixel dec cx jnz ColumnLoop add di,[bp+BufferWidth2] ;point to next scan to fill dec dx ;count down rows to fill jnz RowLoop2 pop di pop si pop bp ret _DrawMasked endp ; Copies a rectangle from one buffer to another. C-callable as: ; void CopyRect(DestBufferPtr, SrcBufferPtr, CopyHeight, CopyWidth, ; DestBufferWidth, SrcBufferWidth); parms3 struc dw ? ;pushed BP dw ? ;pushed return address DestBufferPtr dd ? ;far pointer to buffer to which to copy SrcBufferPtr dd ? ;far pointer to buffer from which to copy CopyHeight dw ? ;height of rect to copy CopyWidth dw ? ;width of rect to copy DestBufferWidth dw ? ;width of buffer to which to copy SrcBufferWidth dw ? ;width of buffer from which to copy parms3 ends public _CopyRect _CopyRect proc near cld push bp mov bp,sp push si push di push ds les di,[bp+DestBufferPtr] lds si,[bp+SrcBufferPtr] mov dx,[bp+CopyHeight] mov bx,[bp+DestBufferWidth] ;distance from end of one dest scan sub bx,[bp+CopyWidth] ; of copy to the next mov ax,[bp+SrcBufferWidth] ;distance from end of one source scan sub ax,[bp+CopyWidth] ; of copy to the next RowLoop3: mov cx,[bp+CopyWidth] ;# of bytes to copy shr cx,1 rep movsw ;copy as many words as possible adc cx,cx rep movsb ;copy odd byte, if any add si,ax ;point to next source scan line add di,bx ;point to next dest scan line dec dx ;count down rows to fill jnz RowLoop3 pop ds pop di pop si pop bp ret _CopyRect endp end