kolourpaint/imagelib/kpFloodFill.cpp

   1
   2 /*
   3    Copyright (c) 2003-2007 Clarence Dang <dang@kde.org>
   4    All rights reserved.
   5
   6    Redistribution and use in source and binary forms, with or without
   7    modification, are permitted provided that the following conditions
   8    are met:
   9
  10    1. Redistributions of source code must retain the above copyright
  11       notice, this list of conditions and the following disclaimer.
  12    2. Redistributions in binary form must reproduce the above copyright
  13       notice, this list of conditions and the following disclaimer in the
  14       documentation and/or other materials provided with the distribution.
  15
  16    THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
  17    IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  18    OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
  19    IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
  20    INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  21    NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  22    DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  23    THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  24    (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  25    THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  26 */
  27
  28
  29 #define DEBUG_KP_FLOOD_FILL 0
  30
  31
  32 #include <kpFloodFill.h>
  33
  34 #include <QApplication>
  35 #include <QImage>
  36 #include <QLinkedList>
  37 #include <QList>
  38 #include <QPainter>
  39
  40 #include <kdebug.h>
  41
  42 #include <kpColor.h>
  43 #include <kpDefs.h>
  44 #include <kpImage.h>
  45 #include <kpPixmapFX.h>
  46 #include <kpTool.h>
  47
  48
  49 class kpFillLine
  50 {
  51 public:
  52     kpFillLine (int y = -1, int x1 = -1, int x2 = -1)
  53         : m_y (y), m_x1 (x1), m_x2 (x2)
  54     {
  55     }
  56
  57     static kpCommandSize::SizeType size ()
  58     {
  59         return sizeof (kpFillLine);
  60     }
  61
  62     int m_y, m_x1, m_x2;
  63 };
  64
  65 static kpCommandSize::SizeType FillLinesListSize (const QLinkedList <kpFillLine> &fillLines)
  66 {
  67     return (fillLines.size () * kpFillLine::size ());
  68 }
  69
  70
  71 struct kpFloodFillPrivate
  72 {
  73     //
  74     // Copy of whatever was passed to the constructor.
  75     //
  76
  77     kpImage *imagePtr;
  78     int x, y;
  79     kpColor color;
  80     int processedColorSimilarity;
  81
  82
  83     //
  84     // Set by Step 1.
  85     //
  86
  87     kpColor colorToChange;
  88
  89
  90     //
  91     // Set by Step 2.
  92     //
  93
  94     QImage readableImage;
  95
  96     QLinkedList <kpFillLine> fillLines;
  97     QList < QLinkedList <kpFillLine> > fillLinesCache;
  98
  99     QRect boundingRect;
 100
 101     bool prepared;
 102 };
 103
 104 kpFloodFill::kpFloodFill (kpImage *image, int x, int y,
 105                          const kpColor &color, int processedColorSimilarity)
 106     : d (new kpFloodFillPrivate ())
 107 {
 108     d->imagePtr = image;
 109     d->x = x, d->y = y;
 110     d->color = color, d->processedColorSimilarity = processedColorSimilarity;
 111
 112     d->prepared = false;
 113 }
 114
 115 kpFloodFill::~kpFloodFill ()
 116 {
 117     delete d;
 118 }
 119
 120
 121 // public
 122 kpColor kpFloodFill::color () const
 123 {
 124     return d->color;
 125 }
 126
 127 // public
 128 int kpFloodFill::processedColorSimilarity () const
 129 {
 130     return d->processedColorSimilarity;
 131 }
 132
 133
 134 // public
 135 kpCommandSize::SizeType kpFloodFill::size () const
 136 {
 137     kpCommandSize::SizeType fillLinesCacheSize = 0;
 138     foreach (const QLinkedList <kpFillLine> &linesList, d->fillLinesCache)
 139     {
 140         fillLinesCacheSize += ::FillLinesListSize (linesList);
 141     }
 142
 143     return ::FillLinesListSize (d->fillLines) +
 144            kpCommandSize::QImageSize (d->readableImage) +
 145            fillLinesCacheSize;
 146 }
 147
 148
 149 // public
 150 void kpFloodFill::prepareColorToChange ()
 151 {
 152     if (d->colorToChange.isValid ())
 153         return;
 154
 155 #if DEBUG_KP_FLOOD_FILL && 1
 156     kDebug () << "kpFloodFill::prepareColorToChange()";
 157 #endif
 158
 159     d->colorToChange = kpPixmapFX::getColorAtPixel (*d->imagePtr, QPoint (d->x, d->y));
 160
 161     if (d->colorToChange.isOpaque ())
 162     {
 163     #if DEBUG_KP_FLOOD_FILL && 1
 164         kDebug () << "\tcolorToChange: " << (int *) d->colorToChange.toQRgb ()
 165                   << endl;
 166     #endif
 167     }
 168     else
 169     {
 170     #if DEBUG_KP_FLOOD_FILL && 1
 171         kDebug () << "\tcolorToChange: transparent";
 172     #endif
 173     }
 174 }
 175
 176 // public
 177 kpColor kpFloodFill::colorToChange ()
 178 {
 179     prepareColorToChange ();
 180
 181     return d->colorToChange;
 182 }
 183
 184
 185 // Derived from the zSprite2 Graphics Engine
 186
 187
 188 // private
 189 kpColor kpFloodFill::pixelColor (int x, int y, bool *beenHere) const
 190 {
 191     if (beenHere)
 192         *beenHere = false;
 193
 194     Q_ASSERT (y >= 0 && y < (int) d->fillLinesCache.count ());
 195
 196     foreach (const kpFillLine &line, d->fillLinesCache [y])
 197     {
 198         if (x >= line.m_x1 && x <= line.m_x2)
 199         {
 200             if (beenHere)
 201                 *beenHere = true;
 202             return d->color;
 203         }
 204     }
 205
 206     return kpPixmapFX::getColorAtPixel (d->readableImage, QPoint (x, y));
 207 }
 208
 209 // private
 210 bool kpFloodFill::shouldGoTo (int x, int y) const
 211 {
 212     bool beenThere;
 213     const kpColor col = pixelColor (x, y, &beenThere);
 214
 215     return (!beenThere && col.isSimilarTo (d->colorToChange, d->processedColorSimilarity));
 216 }
 217
 218
 219 // private
 220 int kpFloodFill::findMinX (int y, int x) const
 221 {
 222     for (;;)
 223     {
 224         if (x < 0)
 225             return 0;
 226
 227         if (shouldGoTo (x, y))
 228             x--;
 229         else
 230             return x + 1;
 231     }
 232 }
 233
 234 // private
 235 int kpFloodFill::findMaxX (int y, int x) const
 236 {
 237     for (;;)
 238     {
 239         if (x > d->imagePtr->width () - 1)
 240             return d->imagePtr->width () - 1;
 241
 242         if (shouldGoTo (x, y))
 243             x++;
 244         else
 245             return x - 1;
 246     }
 247 }
 248
 249
 250 // private
 251 void kpFloodFill::addLine (int y, int x1, int x2)
 252 {
 253 #if DEBUG_KP_FLOOD_FILL && 0
 254     kDebug () << "kpFillCommand::fillAddLine ("
 255               << y << "," << x1 << "," << x2 << ")" << endl;
 256 #endif
 257
 258     d->fillLines.append (kpFillLine (y, x1, x2));
 259     d->fillLinesCache [y].append (
 260         kpFillLine (y/*OPT: can determine from array index*/, x1, x2));
 261     d->boundingRect = d->boundingRect.unite (QRect (QPoint (x1, y), QPoint (x2, y)));
 262 }
 263
 264 // private
 265 void kpFloodFill::findAndAddLines (const kpFillLine &fillLine, int dy)
 266 {
 267     // out of bounds?
 268     if (fillLine.m_y + dy < 0 || fillLine.m_y + dy >= d->imagePtr->height ())
 269         return;
 270
 271     for (int xnow = fillLine.m_x1; xnow <= fillLine.m_x2; xnow++)
 272     {
 273         // At current position, right colour?
 274         if (shouldGoTo (xnow, fillLine.m_y + dy))
 275         {
 276             // Find minimum and maximum x values
 277             int minxnow = findMinX (fillLine.m_y + dy, xnow);
 278             int maxxnow = findMaxX (fillLine.m_y + dy, xnow);
 279
 280             // Draw line
 281             addLine (fillLine.m_y + dy, minxnow, maxxnow);
 282
 283             // Move x pointer
 284             xnow = maxxnow;
 285         }
 286     }
 287 }
 288
 289
 290 // public
 291 void kpFloodFill::prepare ()
 292 {
 293     if (d->prepared)
 294         return;
 295
 296 #if DEBUG_KP_FLOOD_FILL && 1
 297     kDebug () << "kpFloodFill::prepare()";
 298 #endif
 299
 300     prepareColorToChange ();
 301
 302     d->boundingRect = QRect ();
 303
 304
 305 #if DEBUG_KP_FLOOD_FILL && 1
 306     kDebug () << "\tperforming NOP check";
 307 #endif
 308
 309     // get the color we need to replace
 310     if (d->processedColorSimilarity == 0 && d->color == d->colorToChange)
 311     {
 312         // need to do absolutely nothing (this is a significant optimization
 313         // for people who randomly click a lot over already-filled areas)
 314         d->prepared = true;  // sync with all "return true"'s
 315         return;
 316     }
 317
 318 #if DEBUG_KP_FLOOD_FILL && 1
 319     kDebug () << "\tconverting to image";
 320 #endif
 321
 322     // The only way to read pixels.  Sigh.
 323     d->readableImage = kpPixmapFX::convertToQImage (*d->imagePtr);
 324
 325 #if DEBUG_KP_FLOOD_FILL && 1
 326     kDebug () << "\tcreating fillLinesCache";
 327 #endif
 328
 329     // ready cache
 330     for (int i = 0; i < d->imagePtr->height (); i++)
 331          d->fillLinesCache.append (QLinkedList <kpFillLine> ());
 332
 333 #if DEBUG_KP_FLOOD_FILL && 1
 334     kDebug () << "\tcreating fill lines";
 335 #endif
 336
 337     // draw initial line
 338     addLine (d->y, findMinX (d->y, d->x), findMaxX (d->y, d->x));
 339
 340     for (QLinkedList <kpFillLine>::ConstIterator it = d->fillLines.begin ();
 341          it != d->fillLines.end ();
 342          it++)
 343     {
 344     #if DEBUG_KP_FLOOD_FILL && 0
 345         kDebug () << "Expanding from y=" << (*it).m_y
 346                    << " x1=" << (*it).m_x1
 347                    << " x2=" << (*it).m_x2
 348                    << endl;
 349     #endif
 350
 351         //
 352         // Make more lines above and below current line.
 353         //
 354         // WARNING: Adds to end of "fillLines" (the linked list we are iterating
 355         //          through).  Therefore, "fillLines" must remain a linked list
 356         //          - you cannot change it into a vector.  Also, do not use
 357         //          "foreach" for this loop as that makes a copy of the linked
 358         //          list at the start and won't see new lines.
 359         //
 360         findAndAddLines (*it, -1);
 361         findAndAddLines (*it, +1);
 362     }
 363
 364 #if DEBUG_KP_FLOOD_FILL && 1
 365     kDebug () << "\tfinalising memory usage";
 366 #endif
 367
 368     // finalize memory usage
 369     d->readableImage = QImage ();
 370     d->fillLinesCache.clear ();
 371
 372     d->prepared = true;  // sync with all "return true"'s
 373 }
 374
 375 // public
 376 QRect kpFloodFill::boundingRect ()
 377 {
 378     prepare ();
 379
 380     return d->boundingRect;
 381 }
 382
 383
 384 struct DrawLinesPackage
 385 {
 386     const QLinkedList <kpFillLine> *lines;
 387     kpColor color;
 388 };
 389
 390 static void DrawLinesHelper (QPainter *p,
 391         bool drawingOnRGBLayer,
 392         void *data)
 393 {
 394     const DrawLinesPackage *pack = static_cast <DrawLinesPackage *> (data);
 395
 396 #if DEBUG_KP_FLOOD_FILL
 397     kDebug () << "DrawLinesHelper() lines"
 398         << " color=" << (int *) pack->color.toQRgb ()
 399         << endl;
 400 #endif
 401
 402     p->setPen (kpPixmapFX::draw_ToQColor (pack->color, drawingOnRGBLayer));
 403
 404     foreach (const kpFillLine &l, *pack->lines)
 405     {
 406         const QPoint p1 (l.m_x1, l.m_y);
 407         const QPoint p2 (l.m_x2, l.m_y);
 408
 409         p->drawLine (p1, p2);
 410     }
 411 }
 412
 413 static void DrawLines (kpImage *image,
 414         const QLinkedList <kpFillLine> &lines,
 415         const kpColor &color)
 416 {
 417     DrawLinesPackage pack;
 418     pack.lines = &lines;
 419     pack.color = color;
 420
 421     kpPixmapFX::draw (image, &::DrawLinesHelper,
 422         color.isOpaque (), color.isTransparent (),
 423         &pack);
 424 }
 425
 426
 427 // public
 428 void kpFloodFill::fill ()
 429 {
 430     prepare ();
 431
 432
 433     QApplication::setOverrideCursor (Qt::WaitCursor);
 434     {
 435         ::DrawLines (d->imagePtr, d->fillLines, d->color);
 436     }
 437     QApplication::restoreOverrideCursor ();
 438 }