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