rom/graphics/flood.c

   1 /*
   2     Copyright © 1995-2007, The AROS Development Team. All rights reserved.
   3     $Id$
   4
   5     Desc:
   6     Lang: english
   7 */
   8 #include <aros/debug.h>
   9
  10 #include <proto/graphics.h>
  11 #include <string.h>
  12 #include "graphics_intern.h"
  13
  14 #define USE_WRITEPIXEL
  15
  16 struct fillinfo
  17 {
  18     ULONG fillpen;
  19     BOOL (*isfillable)();
  20     struct RastPort *rp;
  21     UBYTE *rasptr;
  22     ULONG bpr;
  23     ULONG orig_apen;
  24     ULONG orig_bpen;
  25     ULONG rp_width;
  26     ULONG rp_height;
  27
  28     struct GfxBase *gfxbase;
  29 };
  30
  31 static VOID settmpraspixel(BYTE *rasptr, LONG x, LONG y,  ULONG bpr, UBYTE state);
  32 static BOOL gettmpraspixel(BYTE *rasptr, LONG x, LONG y,  ULONG bpr );
  33
  34 static BOOL filline(struct fillinfo *fi, LONG start_x, LONG start_y);
  35 static BOOL outline_isfillable(struct fillinfo *fi, LONG x, LONG y);
  36 static BOOL color_isfillable(struct fillinfo *fi, LONG x, LONG y);
  37
  38 #if DEBUG_FLOOD
  39 static int fail_count;
  40 static int pix_written;
  41 #endif
  42
  43 /*****************************************************************************
  44
  45     NAME */
  46 #include <clib/graphics_protos.h>
  47
  48         AROS_LH4(BOOL, Flood,
  49
  50 /*  SYNOPSIS */
  51         AROS_LHA(struct RastPort *, rp, A1),
  52         AROS_LHA(ULONG            , mode, D2),
  53         AROS_LHA(LONG             , x, D0),
  54         AROS_LHA(LONG             , y, D1),
  55
  56 /*  LOCATION */
  57         struct GfxBase *, GfxBase, 55, Graphics)
  58
  59 /*  FUNCTION
  60         Flood fill a RastPort.
  61
  62     INPUTS
  63         rp   - destination RastPort
  64         mode - 0: fill adjacent pixels which don't have color of OPen.
  65                1: fill adjacent pixels which have the same pen as of coordinate x,y.
  66         x,y  - coordinate to start filling.
  67
  68     RESULT
  69
  70     NOTES
  71         The RastPort must have a TmpRas raster whose size is as large as of
  72         that of the RastPort.
  73
  74     EXAMPLE
  75
  76     BUGS
  77
  78     SEE ALSO
  79
  80     INTERNALS
  81
  82     HISTORY
  83         27-11-96    digulla automatically created from
  84                             graphics_lib.fd and clib/graphics_protos.h
  85
  86 *****************************************************************************/
  87 {
  88     AROS_LIBFUNC_INIT
  89
  90     struct TmpRas *tmpras = rp->TmpRas;
  91     ULONG bpr, needed_size;
  92
  93     struct fillinfo fi;
  94
  95     BOOL success;
  96
  97     EnterFunc(bug("Flood(rp=%p, mode=%d, x=%d, y=%d)\n"
  98                 , rp, mode, x, y));
  99
 100 #if DEBUG_FLOOD
 101     fail_count = 0;
 102     pix_written = 0;
 103 #endif
 104
 105     /* Check for tmpras */
 106     if (NULL == tmpras)
 107         ReturnBool("Flood (No tmpras)",  FALSE);
 108
 109     if (NULL != rp->Layer)
 110     {
 111         fi.rp_width  = rp->Layer->Width;
 112         fi.rp_height = rp->Layer->Height;
 113     }
 114     else
 115     {
 116         fi.rp_width  = GetBitMapAttr(rp->BitMap, BMA_WIDTH);
 117         fi.rp_height = GetBitMapAttr(rp->BitMap, BMA_HEIGHT);
 118     }
 119
 120
 121     bpr = WIDTH_TO_BYTES( fi.rp_width );
 122     needed_size = bpr * fi.rp_height;
 123
 124     if (tmpras->Size < needed_size)
 125         ReturnBool("Flood (To small tmpras)",  FALSE);
 126
 127
 128     /* Clear the needed part of tmpras */
 129
 130 /*
 131
 132 !!! Maybe we should use BltClear() here, since
 133 !!! tmpras allways reside in CHIP RAM
 134      */
 135
 136     D(bug("Clearing tmpras\n"));
 137     memset(tmpras->RasPtr, 0,  needed_size);
 138
 139     if (mode == 0)
 140     {
 141         /* Outline mode */
 142         D(bug("Getting outline pen\n"));
 143         fi.fillpen = GetOutlinePen(rp);
 144         D(bug("Got pen\n"));
 145
 146         fi.isfillable = outline_isfillable;
 147     }
 148     else
 149     {
 150         /* Color mode */
 151         D(bug("Reading pixel\n"));
 152         fi.fillpen = ReadPixel(rp, x, y);
 153         D(bug("pixel read: %d\n", fi.fillpen));
 154         fi.isfillable = color_isfillable;
 155     }
 156
 157     fi.rasptr = tmpras->RasPtr;
 158     fi.rp = rp;
 159     fi.bpr = bpr;
 160
 161     fi.orig_apen = GetAPen(rp);
 162     fi.orig_bpen = GetBPen(rp);
 163
 164     fi.gfxbase = GfxBase;
 165
 166     D(bug("Calling filline\n"));
 167     success = filline(&fi, x, y);
 168
 169 #if DEBUG_FLOOD
 170     D(bug("fails: %d, pix written: %d\n", fail_count, pix_written));
 171 #endif
 172
 173     SetAPen(rp, fi.orig_apen);
 174
 175     ReturnBool("Flood",  success);
 176
 177     AROS_LIBFUNC_EXIT
 178 } /* Flood */
 179
 180
 181
 182
 183 static VOID settmpraspixel(BYTE *rasptr, LONG x, LONG y,  ULONG bpr, UBYTE state)
 184 {
 185     ULONG idx  = COORD_TO_BYTEIDX(x, y, bpr);
 186     UBYTE mask = XCOORD_TO_MASK( x );
 187
 188     if (state)
 189         rasptr[idx] |= mask;
 190     else
 191         rasptr[idx] &= ~mask;
 192
 193     return;
 194 }
 195
 196 static BOOL gettmpraspixel(BYTE *rasptr, LONG x, LONG y,  ULONG bpr )
 197 {
 198     ULONG idx  = COORD_TO_BYTEIDX(x, y, bpr);
 199     UBYTE mask = XCOORD_TO_MASK( x );
 200     BOOL state;
 201
 202 /* D(bug("gettmpraspixel (%d, %d, %d): idx=%d, mask=%d, rasptr[idx]=%d, state=%d\n"
 203                 ,x, y, bpr, idx, mask, rasptr[idx], rasptr[idx] & mask));
 204 */
 205     state = ((rasptr[idx] & mask) != 0);
 206
 207 /* D(bug("Returning %d\n", state));
 208 */
 209     return state;
 210 }
 211
 212
 213 #undef GfxBase
 214 #define GfxBase (fi->gfxbase)
 215
 216 static BOOL color_isfillable(struct fillinfo *fi, LONG x, LONG y)
 217 {
 218     BOOL fill;
 219
 220     if (x < 0 || y < 0 || x >= fi->rp_width || y >= fi->rp_height)
 221         return FALSE;
 222
 223     if (gettmpraspixel(fi->rasptr, x, y, fi->bpr))
 224     {
 225 /*      D(bug("Pixel checked twice at (%d, %d)\n", x, y)); */
 226         fill = FALSE;
 227 #if DEBUG_FLOOD
 228         fail_count ++;
 229 #endif
 230     }
 231     else
 232     {
 233         fill = (fi->fillpen == ReadPixel(fi->rp, x, y));
 234     }
 235
 236     return fill;
 237 }
 238
 239 static BOOL outline_isfillable(struct fillinfo *fi, LONG x, LONG y)
 240 {
 241     BOOL fill;
 242 /*    EnterFunc(bug("outline_isfillable(fi=%p, x=%d, y=%d)\n",
 243         fi, x, y));
 244 */
 245     if (x < 0 || y < 0 || x >= fi->rp_width || y >= fi->rp_height)
 246         return FALSE;
 247
 248     if (gettmpraspixel(fi->rasptr, x, y, fi->bpr))
 249     {
 250 /*      D(bug("Pixel checked twice at (%d, %d)\n", x, y)); */
 251         fill = FALSE;
 252 #if DEBUG_FLOOD
 253         fail_count ++;
 254 #endif
 255     }
 256     else
 257     {
 258         fill = (fi->fillpen != ReadPixel(fi->rp, x, y));
 259     }
 260
 261 /*    D(bug("fillpen: %d, pen: %d\n", fi->fillpen, ReadPixel(fi->rp, x, y)));
 262 */
 263
 264 /*    ReturnBool("outline_isfillable", fill);
 265 */
 266     return fill;
 267 }
 268
 269
 270
 271 static VOID putfillpixel(struct fillinfo *fi, LONG x, LONG y)
 272 {
 273
 274     /* TODO: Implement use of patterns */
 275
 276 #ifdef USE_WRITEPIXEL
 277     ULONG pixval, set_pixel = 0UL;
 278
 279     if (fi->rp->AreaPtrn)
 280     {
 281         set_pixel = pattern_pen(fi->rp
 282                 , x, y
 283                 , fi->orig_apen
 284                 , fi->orig_bpen
 285                 , &pixval
 286                 , GfxBase);
 287     }
 288     else
 289     {
 290         pixval = GetAPen(fi->rp);
 291         set_pixel = TRUE;
 292     }
 293
 294     if (set_pixel)
 295     {
 296         SetAPen(fi->rp, pixval);
 297         WritePixel(fi->rp, x, y);
 298     }
 299
 300 #endif
 301
 302     settmpraspixel(fi->rasptr, x, y, fi->bpr, 1);
 303
 304 #if DEBUG_FLOOD
 305     pix_written ++;
 306 #endif
 307     return;
 308 }
 309
 310 #define STACKSIZE 100
 311
 312 struct stack
 313 {
 314     ULONG current;
 315     struct scanline
 316     {
 317        LONG x, y;
 318     } items [STACKSIZE];
 319 };
 320
 321 static VOID init_stack(struct stack *s)
 322 {
 323     s->current = 0;
 324 }
 325
 326 static BOOL push(struct stack *s, LONG x, LONG y)
 327 {
 328    if (s->current == STACKSIZE)
 329         return FALSE;
 330
 331    s->items[s->current].x = x;
 332    s->items[s->current].y = y;
 333
 334
 335    s->current ++;
 336
 337    return TRUE;
 338
 339 }
 340 static BOOL pop(struct stack *s, LONG *xptr, LONG *yptr)
 341 {
 342     if (s->current == 0)
 343         return FALSE;
 344
 345     s->current --;
 346
 347
 348     *xptr = s->items[s->current].x;
 349     *yptr = s->items[s->current].y;
 350
 351
 352     return TRUE;
 353 }
 354
 355 static BOOL filline(struct fillinfo *fi, LONG start_x, LONG start_y)
 356 {
 357     LONG x;
 358
 359     LONG rightmost_above, rightmost_below;
 360     LONG leftmost_above, leftmost_below;
 361     struct stack stack;
 362
 363     EnterFunc(bug("filline(fi=%p, start_x=%d, start_y=%d)\n"
 364         ,fi, start_x, start_y));
 365
 366     init_stack(&stack);
 367
 368     for (;;) {
 369     /* Scan right */
 370
 371     rightmost_above = start_x;
 372     rightmost_below = start_x;
 373
 374     for (x = start_x + 1; ; x ++)
 375     {
 376
 377         if (fi->isfillable(fi, x, start_y))
 378         {
 379             putfillpixel(fi, x, start_y);
 380
 381             /* Check above */
 382             if (x > rightmost_above)
 383             {
 384                 if (fi->isfillable(fi, x, start_y - 1))
 385                 {
 386                     /* Find rightmost pixel */
 387
 388                     for (rightmost_above = x; ; rightmost_above ++)
 389                     {
 390                         if (!fi->isfillable(fi, rightmost_above + 1, start_y - 1))
 391                             break;
 392                     }
 393
 394                     /* Fill that line */
 395                     if (!push(&stack, rightmost_above, start_y - 1))
 396                         ReturnBool("filline (stack full)", FALSE);
 397 /*                  filline(fi, rightmost_above, start_y - 1);
 398 */              }
 399
 400             }
 401
 402             /* Check below */
 403
 404             if (x > rightmost_below)
 405             {
 406                 if (fi->isfillable(fi, x, start_y + 1))
 407                 {
 408                     /* Find rightmost pixel */
 409
 410                     for (rightmost_below = x; ; rightmost_below ++)
 411                     {
 412                         if (!fi->isfillable(fi, rightmost_below + 1, start_y + 1))
 413                             break;
 414                     }
 415
 416                     /* Fill that line */
 417                     if (!push(&stack, rightmost_below, start_y + 1))
 418                         ReturnBool("filline (stack full)", FALSE);
 419
 420 /*                  filline(fi, rightmost_below, start_y + 1);
 421 */              }
 422
 423             }
 424
 425         }
 426         else
 427             break;
 428
 429     } /* for (scan right)  */
 430
 431
 432     /* scan left */
 433
 434
 435     leftmost_above = start_x + 1;
 436     leftmost_below = start_x + 1;
 437
 438     for (x = start_x; ; x -- )
 439     {
 440
 441
 442         if (fi->isfillable(fi, x, start_y))
 443         {
 444             putfillpixel(fi, x, start_y);
 445
 446             /* Check above */
 447             if (x <= leftmost_above)
 448             {
 449                 if (fi->isfillable(fi, x, start_y - 1))
 450                 {
 451                     /* Find rightmost pixel */
 452
 453                     for (leftmost_above = x; ; leftmost_above --)
 454                     {
 455                         if (!fi->isfillable(fi, leftmost_above - 1, start_y - 1))
 456                             break;
 457                     }
 458
 459                     /* Fill that line */
 460                     if (!push(&stack, leftmost_above, start_y - 1))
 461                         ReturnBool("filline (stack full)", FALSE);
 462 /*                  filline(fi, leftmost_above, start_y - 1);
 463 */              }
 464
 465             }
 466
 467             /* Check below */
 468
 469             if (x < leftmost_below)
 470             {
 471                 if (fi->isfillable(fi, x, start_y + 1))
 472                 {
 473                     /* Find rightmost pixel */
 474
 475                     for (leftmost_below = x; ; leftmost_below --)
 476                     {
 477                         if (!fi->isfillable(fi, leftmost_below - 1, start_y + 1))
 478                             break;
 479                     }
 480
 481                     /* Fill that line */
 482                     if (!push(&stack, leftmost_below, start_y + 1))
 483                         ReturnBool("filline (stack full)", FALSE);
 484
 485 /*                  filline(fi, leftmost_below, start_y + 1);
 486 */              }
 487
 488             }
 489
 490         }
 491         else
 492             break;
 493
 494     } /* for (scan left)  */
 495
 496
 497     if (!pop(&stack, &start_x, &start_y))
 498         break;
 499 D(bug("\t\t\tpop(%d, %d)\n", start_x, start_y));
 500
 501   } /* forever */
 502
 503     ReturnBool("filline", TRUE);
 504
 505 }
 506
 507
 508 #undef GfxBase