An Efficient Flood Visit Algorithm



August 01, 1994
URL:http://drdobbs.com/an-efficient-flood-visit-algorithm/184402916

August 1994/An Efficient Flood Visit Algorithm/Listing 1

Listing 1 An algorithm which prevents a child's shadow from falling on its parent line

/*****************************************************
 * UFLOOD.C - unoptimized flood visit
 *
 * for ANSI C
 *
 * by Anton Treuenfels
 * last revision:  04/12/94
 ****************************************************/

/*****************************
 * HEADER SECTION - UFLOOD.H *
 ****************************/

#ifndef SEEN_UFLOOD
#define SEEN_UFLOOD

/* function prototype */

int uflood(int, int, int (*)(int. int));

#endif

/***************************
 * CODE SECTION - UFLOOD.C *
 **************************/

#include <stdlib.h>

#include "usrdef.h"

/* line shadow */

typedef struct shdw {
   struct shdw *next;  /* forward link */
   int lft, rgt;       /* endpoints */
   int row, par;       /* row and parent row */
   Boolean ok;         /* valid flag */
} shadow;

/* shadow variables */

static shadow *seedShadow;  /* current shadow */
static shadow *shadowHead;  /* other pending shadows */

/* visit coordinate function */

static int (*isInterior)(int, int);

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

/* make new shadow */

static void newshadow(int slft, int srgt, int srow, int prow) {

   shadow *new;

   if ((new = malloc(sizeof(shadow))) == NULL)
      exit(EXIT_FAILURE);

   new->lft = slft;    new->rgt = srgt;
   new->row = srow;    new->par = prow;
   new->ok = TRUE;
   new->next = shadowHead;
   shadowHead = new;
}

/* clip off ends of overlapped shadow */

static void clipshadow(shadow *s, shadow *clip) {

   if (s->lft < (clip->lft - 1))
      newshadow(s->lft, clip->lft - 2, s->row, s->par);
   if (s->rgt > (clip->rgt + 1))
      newshadow(clip->rgt + 2, s->rgt, s->row, s->par);
}

/* remove overlapped segment from shadow pair */

static void removeoverlap(shadow *o) {

   shadow *s;

   for (s = shadowHead; s; s = s->next) {
      if ((s->row == o->par) && (s->ok) &&
         (s->lft <= o->rgt) && (s->rgt >= o->lft)) {
            clipshadow(s, o);
            if (o != seedShadow)
               clipshadow(o, s);
            s->ok= o->ok = FALSE;
            return;
      }
   }
}

/* make shadows of one child line */

static void makeshadows(int lft, int rgt, int row) {

   shadow *p;

   newshadow(lft, rgt, row + 1, row);
   newshadow(lft, rgt, row - 1, row);

   removeoverlap(seedShadow);

   for (p = shadowHead; p; p = p->next) {
      if ((p->row == row) && (p->ok) &&
            !((p->lft > rgt) || (p->rgt < lft)))
         removeoverlap(p);
   }
}

/* fill all child lines found within one shadow */

static void fillshadow(void) {

   int col, row, lft;

    row = seedShadow->row;

   for (col = seedShadow->lft; col <= seedShadow->rgt;
          col++) {
      if ((*isInterior)(col, row)) {
         if ((lft = col) == seedShadow->lft) {
            while ((*isInterior)(--lft, row))
               ;
            lft++;
         }
         while ((*isInterior)(++col, row))
            ;

         makeshadows(lft, col - 1, row);
      }
   }
}

/* flood visit */

int uflood(int seedx, int seedy, int (*visit)(int, int)) {

   isInterior = visit;
   shadowHead = NULL;
   newshadow(seedx, seedx, seedy. seedy);
   while (shadowHead) {
      seedShadow = shadowHead;
      shadowHead = shadowHead-->next;
      if (seedShadow-->ok)
         fillshadow();
      free(seedShadow);
   }
}

/* End of File
August 1994/An Efficient Flood Visit Algorithm/Listing 2

Listing 2 An algorithm that improves on uflood.c

/*********************************************************
 * FLOOD.C -- optimized flood visit
 *
 * This algorithm visits once each all 4--way connected
 * interior points on a finite plane which share a common
 * property, given a starting point which has the property
 * and a function which can determine whether any given
 * point also has it. The common points need not form a
 * convex region, that is, islands and peninsulas bounded
 * by points which do not share the common property may
 * exist within the region of points which do.
 *
 * for ANSI C
 *
 * by Anton Treuenfels
 * last revision:  04/12/94
 *
 * references:
 * Lieberman, Henry, "How To Color In A Coloring Book",
 *   in Computer Graphics. Vol. 12, No. 3, Aug 1978
 * Polik, William F., "Area Filling Algorithms",
 *   in Computer Language, Vol. 3, No. 5, May 1986
 * Wilton, Richard, "PC & PS/2 Video Systems",
 *   Microsoft Press, 1987
 *********************************************************/

/***************************
 *HEADER SECTION -- FLOOD.H *
 **************************/

#ifndef SEEN_FLOOD
#define SEEN_FL00D

/* function prototype */

int flood(int, int, int (*)(int, int));

#endif

/**************************
 * CODE SECTION -- FLOOD.C *
 *************************/

#include <stdlib.h>
#include <setjmp.h>

#include "usrdef.h"

/* line shadow */

typedef struct shdw {
   struct shdw *next;      /* forward link */
   int lft, rgt;           /* endpoints */
   int row, par;           /* row and parent row */
   Boolean ok;             /* valid flag */
} shadow;

/* shadow variables */

static int currRow;         /* current row */
static shadow *seedShadow;  /* current shadow */
static shadow *rowHead;     /* current row shadows */
static shadow *pendHead;    /* other pending shadows */
static shadow *freeHead;    /* unused shadow nodes */

/* visit coordinate function */

static int (*isInterior)(int, int);

/* error recovery buffer */

static jmp_buf errBuf;

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

/* release shadow nodes */

static void freeshadows(shadow *s) {

   shadow *t;

   while (s) {
      t = s-->next;
      free(s);
      s = t;
   }
}

/* make new shadow */

static void newshadow(int slft, int srgt, int srow, int prow) {

   shadow *new;

   if ((new = freeHead) != NULL)
      freeHead = freeHead-->next;
   else if ((new = malloc(sizeof(shadow))) == NULL) {
      freeshadows(rowHead);
      freeshadows(pendHead);
      longjmp(errBuf, !0);
   }

   new-->lft = slft;  new-->rgt = srgt;
   new-->row = srow;  new-->par = prow;
   new-->ok = TRUE;
   new-->next = pendNead;
   pendHead = new;
}

/* make list of all shadows on one row */

static void makerow(void) {

   shadow *s, *t, *u;
   
   t = pendHead;
   pendHead = NULL;
   while ((s = t) != NULL) {
      t = t-->next;
      if (s-->ok) {
         if (rowHead == NULL) {
            currRow = s-->row;
            s-->next = NULL;
            rowHead = s;
         }
         else if (s-->row == currRow) {
            if (s-->lft <= rowHead-->lft) {
               s-->next = rowHead;
               rowHead = s;
            }
            else {
               for (u = rowHead; u-->next; u = u-->next)
                  if (s-->lft <= u-->next-->lft)
                     break;
               s-->next = u-->next;
               u-->next = s;
            }
         }
         else {
            s-->next = pendHead;
            pendHead = s;
         }
      }
      else {
         s-->next = freeHead;
         freeHead = s;
      }
   }
}

/* make new shadow(s) that don't overlap lines */

static void clipshadow(int lft, int rgt, int row, shadow *line) {

   if (lft < (line-->lft -- 1))
      newshadow(lft, line-->lft -- 2, row, line-->row);
   if (rgt > (line-->rgt + 1))
      newshadow(line-->rgt + 2, rgt, row, line-->row);
}

/* discard shadow segments which overlap lines */

static void removeoverlap(shadow *rw) {

   shadow *chld;

   for (chld = pendHead; chld-->row != rw-->par; chld = chld-->next)
      ;
   clipshadow(chld-->lft, chld-->rgt, chld-->row, rw);

   if (rw-->rgt > (chld-->rgt + 1))
      rw-->lft = chld-->rgt + 2;
   else
      rw-->ok = FALSE;
   chld-->ok = FALSE;
}

/* make shadows of one child line */

static void makeshadows(int lft, int rgt) {

   shadow *p;
   
   if (currRow > seedShadow-->par) {
      newshadow(1ft; rgt, currRow + 1, currRow);
      clipshadow(lft, rgt, currRow -- 1, seedShadow);
   }
   else if (currRow < seedShadow-->par) {
      newshadow(lft, rgt, currRow -- 1, currRow);
      clipshadow(lft, rgt, currRow + 1, seedShadow);
   }
   else {
      newshadow(1ft, rgt, currRow + 1, currRow);
      newshadow(1ft, rgt, curtRow -- 1, currRow);
   }
   
   for (p = rowHead; p && (p-->lft <= rgt); p = p-->next)
      if (p-->ok)
         removeoverlap(p);
}

/* visit all child lines found within one shadow */

static void visitshadow(void) {
   
   int col, lft;
   
   for (col = seedShadow-->lft; col <= seedShadow-->rgt; col++) {
      if ((*isInterior)(col, currRow)) {
         if ((lft = cold == seedShadow-->lft) {
            while ((*islnterior)(--lft, currRow))
               ;
            lft++;
         }
         while ((*isInterior)(++col, currRow))
            ;
            
         makeshadows(lft, col -- 1);
      }
   }
}

/* flood visit */

static void doflood(int seedx, int seedy, int (*visit)(int, int)) {

   isInterior = visit;
   pendHead = rowHead = freeHead = NULL;
   newshadow(seedx, seedx, seedy, seedy);
   while (pendHead) {
      makerow();
      while (rowHead) {
         seedShadow = rowHead;
         rowHead = rowHead-->next;
         if (seedShadow-->ok)
            visitshadow();
         seedShadow-->next = freeHead;
         freeHead = seedShadow;
      }
   }
   freeshadows(freeHead);
}

/* execute flood visit through guard function */

int flood(int seedx, int seedy, int (*visit)(int, int)) {

   if (setjmp(errBuf) != 0)
      return(FAIL);
   doflood(seedx, seedy, visit);
   return(OK);
}

/* End of File */
August 1994/An Efficient Flood Visit Algorithm/Listing 3

Listing 3 An algorithm that tests uflood.c and flood.c

/*******************************************************
 * FLOODTST.C -- exercise the flood visit algorithm.
 *
 * This module assumes a 100 by 100 coordinate space.
 * Called routines in other modules are responsible
 * for mapping these virtual coordinates to whatever
 * coordinate space is actually supported by the video
 * hardware before performing requested operations.
 *
 * for ANSI C
 *
 * by Anton Treuenfels
 * last revision:  04/11/94
 ******************************************************/

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <time.h>

#include "usrdef.h"
#include "bgigrh.h"
#include "bgipixel.h"
#include "egapixel.h"

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

/* fill empty screen */

static void set_test0(int *seedx, int *seedy) {

   *seedx = *seedy = 50;
}

/* fill empty box */

static void set_test1(int *seedx, int *seedy) {

   grhrect(10, 10, 90, 90);
   *seedx = *seedy = 50;
}

/* fill space between concentric boxes */

static void set_test2(int *seedx, int *seedy) {

   grhrect(10, 10, 90, 90);
   grhrect(30, 30, 70, 70);
   *seedx = 15; *seedy = 50;
}

/* fill large open non--convex figure */

static void set_test3(int *seedx, int *seedy) {

   grhrect(10, 10, 90, 90);
   grhfpair(20, 20, 80, 80);
   *seedx = 15; *seedy = 50;
}

/* draw staggered arrangement */

static void drawstaggered(int *seedx, int *seedy, int dx, int dy,
                      void (*figure)(int, int, int, int)) {

   int ix, iy, i, j;
   
   ix = 3 * dx; iy = 3 * dy / 2;
   
   for (i = dx/2; i < 100 -- dx; i += ix) {
      for (j = dy/2; j < 100 -- dy; j += iy) 
         (*figure)(i, j, i+dx, j+dy);
   }
   
   for (i = 2*dx; i < 100 -- dx; i += ix) {
      for (j = dy; j < 100 -- dy; j += iy)
         (*figure)(i, j, i+dx, j+dy);
   }
   
   *seedx = 2 * dx; *seedy = dy / 2;
}

/* fill staggered boxes */

static void set_test4(int *sx, int *sy) {

   drawstaggered(sx, sy, 2, 3, grhrect);
}

/* fill staggered circles */

static void set_test6(int *sx, int *sy) {

   drawstaggered(sx, sy, 2, 3, grhcircle);
}

/* fill staggered open non--convex figures */

static void set_test8(int *sx, int *sy) {

   drawstaggered(sx, sy, 8, 9, grhfpair);
}

/* draw regularly spaced arrangement */

static void drawregular(int *seedx, int *seedy, int dx, int dy,
                    void (*figure)(int, int, int, int)) {

   int ix, iy, i, j;
   
   ix = 3 * dx / 2;  iy = 3 * dy / 2;
   
   for (i = dx/2; i < 100 -- dx; i += ix) {
      for (j = dy/2; j < 100 -- dy; j += iy)
         (*figure)(i, j, i+dx, j+dy);
   }
   
   *seedx = 0; *seedy = 50;
}

/* fill regular boxes */

static void set_test5(int *sx, int *sy) {

   drawregular(sx, sy, 2, 3, grhrect);
}

/* fill regular circles */

static void set_test7(int *sx, int *sy) {

   drawregular(sx, sy, 2, 3, grhcircle);
}

/* fill random figures */

static void set_test9(int *seedx, int *seedy) {

   void (*draw[])(int, int, int, int) = {
      grhrect, grhcircle, grhfpair
      };

   int i, j, dx, dy, rx, ry;
   int lft, top, bot, rgt;
   
   dx = 10; dy = 10;
   
   rx = dx/2; ry = dy/2;
   
   randomize();
   
   for (i = 2; i < 100 -- 2* dx; i += dx) {
      for (j = 0; j < 100 -- 2 * dx; j += dy) {
         lft = i + random(rx);
         top = j + random(ry);
         rgt = lft + random(dx) + rx;
         bot = top + random(ry) + dy;
         (*draw[random(3)])(lft, top, rgt, bot);
      }
   }
   
   *seedx = 1; *seedy = 50;
}

/* wait for and return one char from keyboard */

static int onechar(void) {
   fflush(stdin);
   return(toupper(getchar()));
}

/* execute test */

static void xtest(int num, Boolean fastfill, Boolean fastvisit) {

   void (*settest[])(int *, int *) = {
      set_test0, set_test1, set_test2,
      set_test3, set_test4, set_test5,
      set_test6, set_test7, set_test8,
      set_test9
      };

   int x, y;
   
   grhopen();
   (*settest[num])(&x, &y);
   if (fastvisit)
      egaflood(x, y, fastfill);
   else
      checkflood(x, y, fastfill);
   (void)onechar();
   grhclose();
}

/* da supervisor */

int main(void) {

   int c;
   Boolean keepgoing, fastfill, fastvisit;
   
   fastfill = fastvisit = FALSE;
   keepgoing = TRUE;
   while (keepgoing) {
      printf("\n\n%s fill algorithm enabled.",
            fastfill ? "Optimized" : "Unoptimized");
      printf("\n%s visit function enabled.",
            fastvisit ? "Fast" : "Checking");
      printf("\n\nCommands: 0-->9= test,");
      printf(" F)iller, V)isitor, Q)uit");
      printf("\nWhat next?  ");
      c = onechar();
      if (isdigit(c))
         xtest(c -- '0', fastfill, fastvisit);
      else {
         switch (c) {
         case 'F':
            fastfill = !fastfill;
            break;
         case 'V':
            fastvisit = !fastvisit;
            break;
         case 'Q': case EOF:
            keepgoing = FALSE;
            break;
         default:
            printf("\nDon't know that choice");
         }
      }
   }
   return(EXIT_SUCCESS);
}

/* End of File
August 1994/An Efficient Flood Visit Algorithm/Listing 4

Listing 4 Supporting graphics functions

/*******************************************************
 * BGIGRH.C -- required graphics functions
 *  using Borland Graphic Interface
 *
 * The routines in this module adapt themselves to
 * whatever video hardware a driver is available for.
 *
 * for TurboC V2.0
 *
 * by Anton Treuenfels
 *
 * first created:  01/01/93
 * last revision:  04/11/94
 ******************************************************/

/******************************
 * Header Section -- BGIGRH.H  *
 *****************************/

#ifndef SEEN_BGIGRH
#define SEEN_BGIGRH

/* exported variables */

extern long MaxXPos. MaxYPos;
extern int MaxColor;

/* function prototypes */

void abspoint(int *, int *);
void grhopen(void);
void grhclose(void);
void grhfpair(int, int, int, int);
void grhrect(int, int, int, int);

void grhcircle(int, int, int, int);

#endif

/***************************
 * Code Section -- BGIGRH.C *
 **************************/

#include <stdio.h>
#include <stdlib.h>
#include <graphics.h>

#include "usrdef.h"

/* change the following definition if the driver
  files are not there or in the current directory */

#define DRIVERPATH "C:\\TURBOC\\BGI"

long MaxXPos, MaxYPos;  /* physical screen size */
int MaxColor;           /* maximum color index */

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

/* convert relative point to absolute */

void abspoint(int *xpos, int *ypos) {

   if (*xpos <= 0)
      *xpos = 0;
   else if (*xpos >= 100)
      *xpos = (int)MaxXPos;
   else
      *xpos = (int)(*xpos * MaxXPos / 100);

   if (*ypos <= 0)
      *ypos = 0;
   else if (*ypos >= 100)
      *ypos = (int)MaxYPos;
   else
      *ypos = (int)(*ypos * MaxYPos / 100);
}

/* convert relative rectangle to absolute */

static void absrect(int *lft, int *top, int *rgt, int *bot) {


   int tmp;
   
   if (*lft > *rgt) {
      tmp = *lft; *lft = *rgt; *rgt = tmp;
   }
   if (*top > *bot) {
      tmp = *top; *top = *bot; *bot = tmp;
   }
   abspoint(lft, top);
   abspoint(rgt, bot);
}

/* init bitmapped graphics operations */

void grhopen(void) {

   int gdriver, gmode, gerror;
   
   gdriver = DETECT;
   initgraph(&gdriver, &gmode, DRIVERPATH);
   gerror = graphresult();
   if (gerror < 0) {
      printf("\ngraphics error: %s.\n", grapherrormsg(gerror));
      exit(EXIT_FAILURE);
   }
   
   MaxXPos = getmaxx();
   MaxYPos = getmaxy();
   MaxColor = getmaxcolor();
   
   setcolor(MaxColor);
   setbkcolor(0);
}

/* end bitmapped graphics operations */

void grhclose(void) {

   closegraph();
}

/* draw sideways 'F' pair */

void grhfpair(int lft, int top, int rgt, int bot) {

   int dx, dy, dx2, dx3, dy3;
   setlinestyle(SOLID_LINE, 0x0000, NORM_WIDTH);
   absrect(&lft, &top, &rgt, &bot);
   dx = (rgt -- lft + 1) / 7;
   dy = (bot -- top + 1) / 5;
   dx2 = 2* dx; dx3 = 3 * dx; dy3 = 3 * dy;
   rectangle(lft, top, rgt, top + dy);
   rectangle(lft, bot -- dy, rgt, bot);
   rectangle(rgt -- dx, top + dy, rgt, top + dy3);
   rectangle(lft, bot -- dy3, lft + dx. bot -- dy);
   rectangle(lft + dx2, top + dy, lft + dx3, top + dy3);
   rectangle(rgt -- dx3, bot -- dy3, rgt -- dx2, bot -- dy);
}

/* draw rectangle */

void grhrect(int lft, int top, int rgt, int bot) {

   setlinestyle(SOLID_LINE, 0x0000, NORM_WIDTH);
   absrect(&lft, &top, &rgt, &bot);
   rectangle(lft, top, rgt, bot);
}

/* draw circle */

void grhcircle(int lft, int top, int rgt, int bot) {

   int radius;
   
   setlinestyle(SOLID_LINE, 0x0000, NORM_WIDTH);
   absrect(&lft, &top, &rgt, &bot);
   radius = min((rgt -- lft)/2, (bot -- top)/2);
   circle((lft + rgt)/2, (top + bot)/2, radius);
}
/* End of File */
August 1994/An Efficient Flood Visit Algorithm/Listing 5

Listing 5 A point examination function

/*****************************************************
 * BGIPIXEL.C -- this is a compiler--specific function
 * to examine and fill pixels.
 *
 * for TurboC V 2.0
 *
 * by Anton Treuenfels
 * last revision:  04/11/94
 ****************************************************/

#include "usrdef.h"

/*******************************
 * Header Section -- BGIPIXEL.H *
 ******************************/

#ifndef SEEN_BGIPIX
#define SEEN_BGIPIX

/* function prototype */

void checkflood(int, int, Boolean);

#endif

/*****************************
 * Code Section -- BGIPIXEL.C *
 ****************************/

#include <stdio.h>
#include <stdlib.h>
#include <graphics.h>

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

/* efficiency counts */

static long readcnt, writecnt;

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

/* check and fill pixel */

static int bgipixel(int xpos, int ypos) {

   int pixval;
   
   readcnt++;
   if ((ypos >= 0) && (ypos <= MaxYPos)
      && (xpos >= 0) && (xpos <= MaxXPos)) {
         pixval = getpixel(xpos, ypos);
         if (pixval == 0) {
            writecnt++;
            if (xpos & 1) putpixel(xpos, ypos, MaxColor);
            return(TRUE);
         }
            pixval = max(0, pixval -- 1);
            putpixel(xpos, ypos, pixval);
   }
   return(FALSE);
}

/* checking fill using Borland Graphics Interface */

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

   char txtbuf[80];
   
   readcnt = writecnt = 0;
   abspoint(&xpos, &ypos);
   if (fastfill)
      flood(xpos, ypos, bgipixel);
   else
      uflood(xpos, ypos, bgipixel);
   sprintf(txtbuf, "Pixels read=    %ld", readcnt);
   outtextxy(1, 1, txtbuf);
   sprint(txtbuf, "Pixels written= %ld", writecnt);
   outtextxy(1, 10, txtbuf);
   sprintf(txtbuf, "Write/Read= %.2f",
          (float)writecnt / (float)readcnt);
    outtextxy(1, 21, txtbuf);
}
/* End of File */
August 1994/An Efficient Flood Visit Algorithm/Listing 6

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 */
August 1994/An Efficient Flood Visit Algorithm/Listing 7

Listing 7 Definitions for graphics routines

/*************************************************
 * USRDEF.H -- additions to <stddef.h>
 *
 * last revised:   02/28/93
 ************************************************/

#define SEEN_USRDEF
#define SEEN_USRDEF

/* condition codes */

#define FALSE   0
#define TRUE    !FALSE

#define OK      0
#define FAIL   --1

/* synonym types */

typedef unsigned char Byte;
typedef int Boolean;
#endif

August 1994/An Efficient Flood Visit Algorithm/Sidebar

Patterns of Visitation


The unoptimized visit function uflood tends to require more storage than the optimized version flood. Using the Turbo C small memory model and an EGA display, during test 4 uflood actually runs out of storage space and terminates abruptly. The lower storage requirements of flood clearly have something to do with the fact that entire rows are processed at once, but there is more going on here than meets the eye. The manner in which flood chooses rows to visit also has a great influence.

Shadows get onto the pending list when child lines cast shadows. If child lines cast shadows on both sides of a row, then which row is visited next depends on the last shadow cast. If shadows are cast on only one side, that row will be visited next. If no shadows are cast, visiting has reached a dead end and will jump to the row of whatever shadow is at the head of the pending list.

When shadows are cast on both sides of a row, after the next row is chosen shadows on the other row remain on the pending list. They stay there until visiting either reaches a dead end or sweeps by their row while proceeding around an island in another part of the region. Which shadow will be at the head of the list when a dead end is reached?

flood makes this answer essentially unpredictable by reversing the relative order of shadows remaining in the pending list each time a row is selected. It is this characteristic that makes it possible for a child to have parent lines on both sides, because visiting can jump from one side of a pending shadow to the other without passing through its row.

Say, instead, that the relative order of shadows remaining in the pending list is maintained instead of reversed. After reaching a dead end, visiting will revert to the most recent row remaining in the pending list (more precisely, to the row that was not selected after the last time shadows were cast on both sides of a row). This prevents visiting from jumping from one side of a pending shadow to the other.

This leads to code simplification because overlapped shadows would then be found only at the head of the row and pending lists. Immediately upon detection overlapped shadows could be placed on the free list — the validity flags would no longer be necessary. These effects can be achieved in other ways, of course, but the possibility that the overlapped shadow is not at the head of its list makes the process somewhat messy. (The time savings are not great, but the quick placement of nodes on the free list leads to significant reductions in storage requirements for some complex regions.)

It turns out that maintaining relative order in the pending list is not a good thing to do. While with simple regions involving only a few islands there is little or no difference, as regions grow more complex the number of shadows in the pending list can increase enormously.

In test 4, for example, rows on the far side of islands cast shadows on both sides. The shadows cast onto islands (on the same side as the parents of the child lines) are all dead ends. If the last child on the row casts a shadow on an island, it will be detected immediately and the next row selected will contain all of the shadows cast away from the islands (on the side opposite the parents of the child lines). But if the last child casts only a shadow away from the islands, the shadows falling on islands remain in the pending list until visiting reaches the dead end at the bottom of the screen. With an EGA display, eventually over 400 shadows are in the pending list. Not only space but also time spent manipulating the pending list is increased.

The difference caused by reversing instead of maintaining the relative order of shadows in the pending list shows up whenever shadows cast on islands are discovered to be dead ends. List rearrangement means that the next row selected might not be the most recent one added to the list, but instead one from an earlier point. Because the shadows on such a row are usually dead ends themselves, they are removed from the pending list but not replaced. The net overall effect is to keep the pending list shorter than when maintaining relative order.

When maintaining relative order, test 6 also experiences a dramatic increase in the number of shadows required, to over 400. Test 8 has a moderate increase, to over 100. The random patterns of test 9 require about 50 shadows on average.

These results indicate that the code simplifications possible by maintaining the relative order of shadows in the pending list are not worth the increases in time and space required. Nearly all shadows that overlap lines are found to be at the head of the row and pending lists as it is. The few that are not are fairly easy to handle with simple loops and flags.

The code simplifications outlined above remain attractive, however. If another simple method could be found to guarantee that a child line never has parent lines on both sides of it, they may be achievable.

August 1994/An Efficient Flood Visit Algorithm/Table 1

Table 1 Percentage of time executing each function in Flood() using Egapix() point examination Function

               Test
Function       0     1   2   3   4   5   6   7   8   9
--------------------------------------------------------
visitshadow    98    98  96  93  66  66  78  78  84  85
makeshadow     --    --  1   2   14  14  7   7   5   4
doflood        --    --  --  1   5   4   3   3   2   2
makerow        --    --  --  1   2   1   1   1   2   3
newshadow      --    --  --  --  6   6   4   4   2   1
clipshadow     --    --  --  --  5   5   3   3   1   1
freeshadow     --    --  --  --  --  --  --  --  --  --
removeoverlap  --    --  --  --  --  --  --  --  --  --
_flood         --    --  --  --  --  --  --  --  --  --

Notes:
1. "--"indicates less than 1% of total time.
2. Percentages for test 9 averaged over 10 runs.
3. Tests made using a 386DX-40 processor with a 64K static RAM cache. 
   Source compiled by Turbo C v2.0 to small model byte-aligned 8088/86
   object code using default compiler options (size favored over speed).
August 1994/An Efficient Flood Visit Algorithm/Table 2

Table 2 Flood() shadow storage requirements

Terms of Service | Privacy Statement | Copyright © 2024 UBM Tech, All rights reserved.