An Efficient Flood Visit Algorithm

Listing 6 A point examination function optimized for speed

/*****************************************************
 * EGAPIXEL.C -- this is a hardware--specific function
 * to examine and fill EGA/VGA pixels.
 * 
 * for TurboC V2.0
 * 
 * by Anton Treuenfels
 * last revision:  04/11/94
 *
 * references:
 * Stevens, Roger T., "Graphics Programming in C",
 *  M&T Books, 1988
 * Wilton, Richard, "PC & PS/2 Video Systems",
 *  Microsoft Press, 1987
 ****************************************************/

#include "usrdef.h"

/*******************************
 * Header Section -- EGAPIXEL.H *
 ******************************/

#ifndef SEEN_EGAPIX
#define SEEN_EGAPIX

/* function prototype */

void egaflood(int, int, Boolean);

#endif

/*****************************
 * Code Section -- EGAPIXEL.C *
 ****************************/

#include <stddef.h>
#include <dos.h>
#include <graphics.h>

#include "bgigrh.h"
#include "flood.h"
#include "uflood.h"

#define BRDRPIX WHITE
#define BACKPIX LIGHTBLUE
#define FOREPIX BLUE

/* screen dimension */

#define XMAX    639    /* highest supported by BGI */

/* video memory */

#define VBASE   0xa0000000L     /* base address */
#define ROWSIZE 80              /* bytes per row */
#define COLMASK 0xfff8          /* column mask */
#define COLSHFT 3               /* column shift */
#define PIXMASK 0x07            /* pixel select */

/* graphics controller */

#define SETGRH(R, V)    {outportb(0x3ce, (R)); \
                     outportb(0x3cf, (V));}

#define COMP    2       /* color compare register */
#define DFLTCMP 0x00

#define MODE    5       /* mode register */
#define DFLTMOD 0x00
#define R1W2    0x06    /* read mode 1, write mode 2 */

#define MASK    8       /* bitmask register */
#define DFLTMSK 0xff

/* pixel masks and pattern */

static Byte pixMask[] = {0x80, 0x40, 0x20, 0x10,
                     0x08, 0x04, 0x02, 0x01};
static Byte patMask[] = {0xcc, 0xcc, 0x33, 0x33,
                     0xcc, 0xcc, 0x33, 0x33};

#define PATMASK 0x07        /* pattern select */

/* screen variables */

static int currCol;         /* current column */
static int currRow;         /* current row */
static int colOffset;       /* column offset*/
static Byte far *rowPtr;    /* row offset */
static Byte far *screenPtr; /* current screen byte */
static Byte rowPattern;     /* row fill pattern */

/****************************************************/

/* initialize current column and row */

static void initcurr(int ypos) {

   currCol = ~COLMASK;
   currRow = ypos -- 1;
}

/* examine one pixel */

static int egapixel(int xpos, int ypos) {

   Byte bitmask;
   
   if (ypos != currRow) {
      if ((ypos < 0 || (ypos > MaxYpos))
          return(FALSE);
      currRow = ypos;
      rowPtr = (Byte far *)(VBASE + ypos * ROWSIZE);
      screenPtr = rowPtr + colOffset;
      rowPattern = patMask[ypos & PATMASK];
   }
   
   if ((xpos & COLMASK) != currCol) {
      if ((xpos < 0) || (xpos> XMAX))
          return(FALSE);
      currCol = xpos & COLMASK;
      colOffset = xpos >> COLSHFT;
      screenPtr = rowPtr + colOffset;
   }
   
   bitmask = pixMask[xpos & PIXMASK];
   if ((*screenPtr & bitmask) != 0)
      return(FALSE);

   SETGRH(MASK, bitmask);
   *screenPtr = (rowPattern & bitmask) ? FOREPIX : BACKPIX;
   return(TRUE);
}

/* execute fill */

void egaflood(int xpos, int ypos, Boolean fastfill) {

   abspoint(&xpos, &ypos);
   initcurr(ypos);
   SETGRH(COMP, BRDRPIX);
   SETGRH(MODE, R1W2);
   if (fastfill)
      (void)flood(xpos, ypos, egapixel);
   else
      (void)uflood(xpos, ypos, egapixel);
   SETGRH(MASK, DFLTMSK);
   SETGRH(MODE, DFLTMOD);
   SETGRH(COMP, DFLTCMP);
}

/* End of File */