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