File indexing completed on 2024-05-05 04:21:07
0001 0002 /* 0003 Copyright (c) 2003-2007 Clarence Dang <dang@kde.org> 0004 All rights reserved. 0005 0006 Redistribution and use in source and binary forms, with or without 0007 modification, are permitted provided that the following conditions 0008 are met: 0009 0010 1. Redistributions of source code must retain the above copyright 0011 notice, this list of conditions and the following disclaimer. 0012 2. Redistributions in binary form must reproduce the above copyright 0013 notice, this list of conditions and the following disclaimer in the 0014 documentation and/or other materials provided with the distribution. 0015 0016 THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 0017 IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 0018 OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 0019 IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 0020 INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 0021 NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 0022 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 0023 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 0024 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 0025 THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 0026 */ 0027 0028 0029 #define DEBUG_KP_FLOOD_FILL 0 0030 0031 0032 #include "kpFloodFill.h" 0033 0034 #include <QApplication> 0035 #include <QImage> 0036 #include <QList> 0037 #include <QPainter> 0038 0039 #include "kpLogCategories.h" 0040 0041 #include "kpColor.h" 0042 #include "kpDefs.h" 0043 #include "pixmapfx/kpPixmapFX.h" 0044 #include "tools/kpTool.h" 0045 0046 //--------------------------------------------------------------------- 0047 0048 class kpFillLine 0049 { 0050 public: 0051 explicit kpFillLine (int y = -1, int x1 = -1, int x2 = -1) 0052 : m_y (y), m_x1 (x1), m_x2 (x2) 0053 { 0054 } 0055 0056 static kpCommandSize::SizeType size () 0057 { 0058 return sizeof (kpFillLine); 0059 } 0060 0061 int m_y, m_x1, m_x2; 0062 }; 0063 0064 //--------------------------------------------------------------------- 0065 0066 static kpCommandSize::SizeType FillLinesListSize (const QList <kpFillLine> &fillLines) 0067 { 0068 return (fillLines.size () * kpFillLine::size ()); 0069 } 0070 0071 //--------------------------------------------------------------------- 0072 0073 struct kpFloodFillPrivate 0074 { 0075 // 0076 // Copy of whatever was passed to the constructor. 0077 // 0078 0079 kpImage *imagePtr = nullptr; 0080 int x = 0, y = 0; 0081 kpColor color; 0082 int processedColorSimilarity = 0; 0083 0084 0085 // 0086 // Set by Step 1. 0087 // 0088 0089 kpColor colorToChange; 0090 0091 0092 // 0093 // Set by Step 2. 0094 // 0095 0096 QList <kpFillLine> fillLines; 0097 QList < QList <kpFillLine> > fillLinesCache; 0098 0099 QRect boundingRect; 0100 0101 bool prepared = false; 0102 }; 0103 0104 //--------------------------------------------------------------------- 0105 0106 kpFloodFill::kpFloodFill (kpImage *image, int x, int y, 0107 const kpColor &color, int processedColorSimilarity) 0108 : d (new kpFloodFillPrivate ()) 0109 { 0110 d->imagePtr = image; 0111 d->x = x; 0112 d->y = y; 0113 d->color = color; 0114 d->processedColorSimilarity = processedColorSimilarity; 0115 0116 d->prepared = false; 0117 } 0118 0119 //--------------------------------------------------------------------- 0120 0121 kpFloodFill::~kpFloodFill () 0122 { 0123 delete d; 0124 } 0125 0126 //--------------------------------------------------------------------- 0127 0128 // public 0129 kpColor kpFloodFill::color () const 0130 { 0131 return d->color; 0132 } 0133 0134 //--------------------------------------------------------------------- 0135 0136 // public 0137 int kpFloodFill::processedColorSimilarity () const 0138 { 0139 return d->processedColorSimilarity; 0140 } 0141 0142 //--------------------------------------------------------------------- 0143 0144 // public 0145 kpCommandSize::SizeType kpFloodFill::size () const 0146 { 0147 kpCommandSize::SizeType fillLinesCacheSize = 0; 0148 for (const auto &linesList : d->fillLinesCache) 0149 { 0150 fillLinesCacheSize += ::FillLinesListSize (linesList); 0151 } 0152 0153 return ::FillLinesListSize(d->fillLines) + 0154 kpCommandSize::QImageSize(d->imagePtr) + 0155 fillLinesCacheSize; 0156 } 0157 0158 //--------------------------------------------------------------------- 0159 0160 // public 0161 void kpFloodFill::prepareColorToChange () 0162 { 0163 if (d->colorToChange.isValid ()) { 0164 return; 0165 } 0166 0167 #if DEBUG_KP_FLOOD_FILL && 1 0168 qCDebug(kpLogImagelib) << "kpFloodFill::prepareColorToChange()"; 0169 #endif 0170 0171 d->colorToChange = kpPixmapFX::getColorAtPixel (*d->imagePtr, QPoint (d->x, d->y)); 0172 } 0173 0174 //--------------------------------------------------------------------- 0175 0176 // public 0177 kpColor kpFloodFill::colorToChange () 0178 { 0179 prepareColorToChange (); 0180 0181 return d->colorToChange; 0182 } 0183 0184 //--------------------------------------------------------------------- 0185 0186 // Derived from the zSprite2 Graphics Engine 0187 0188 // private 0189 kpColor kpFloodFill::pixelColor (int x, int y, bool *beenHere) const 0190 { 0191 if (beenHere) { 0192 *beenHere = false; 0193 } 0194 0195 Q_ASSERT (y >= 0 && y < static_cast<int> (d->fillLinesCache.count ())); 0196 0197 for (const auto &line : d->fillLinesCache [y]) 0198 { 0199 if (x >= line.m_x1 && x <= line.m_x2) 0200 { 0201 if (beenHere) { 0202 *beenHere = true; 0203 } 0204 return d->color; 0205 } 0206 } 0207 0208 return kpPixmapFX::getColorAtPixel (*(d->imagePtr), QPoint (x, y)); 0209 } 0210 0211 //--------------------------------------------------------------------- 0212 0213 // private 0214 bool kpFloodFill::shouldGoTo (int x, int y) const 0215 { 0216 bool beenThere; 0217 const kpColor col = pixelColor (x, y, &beenThere); 0218 0219 return (!beenThere && col.isSimilarTo (d->colorToChange, d->processedColorSimilarity)); 0220 } 0221 0222 //--------------------------------------------------------------------- 0223 0224 // private 0225 int kpFloodFill::findMinX (int y, int x) const 0226 { 0227 for (;;) 0228 { 0229 if (x < 0) { 0230 return 0; 0231 } 0232 0233 if (shouldGoTo (x, y)) { 0234 x--; 0235 } 0236 else { 0237 return x + 1; 0238 } 0239 } 0240 } 0241 0242 //--------------------------------------------------------------------- 0243 0244 // private 0245 int kpFloodFill::findMaxX (int y, int x) const 0246 { 0247 for (;;) 0248 { 0249 if (x > d->imagePtr->width () - 1) { 0250 return d->imagePtr->width () - 1; 0251 } 0252 0253 if (shouldGoTo (x, y)) { 0254 x++; 0255 } 0256 else { 0257 return x - 1; 0258 } 0259 } 0260 } 0261 0262 //--------------------------------------------------------------------- 0263 0264 // private 0265 void kpFloodFill::addLine (int y, int x1, int x2) 0266 { 0267 #if DEBUG_KP_FLOOD_FILL && 0 0268 qCDebug(kpLogImagelib) << "kpFillCommand::fillAddLine (" 0269 << y << "," << x1 << "," << x2 << ")" << endl; 0270 #endif 0271 0272 d->fillLines.append (kpFillLine (y, x1, x2)); 0273 d->fillLinesCache [y].append ( 0274 kpFillLine (y/*OPT: can determine from array index*/, x1, x2)); 0275 d->boundingRect = d->boundingRect.united (QRect (QPoint (x1, y), QPoint (x2, y))); 0276 } 0277 0278 //--------------------------------------------------------------------- 0279 0280 // private 0281 void kpFloodFill::findAndAddLines (const kpFillLine &fillLine, int dy) 0282 { 0283 // out of bounds? 0284 if (fillLine.m_y + dy < 0 || fillLine.m_y + dy >= d->imagePtr->height ()) { 0285 return; 0286 } 0287 0288 for (int xnow = fillLine.m_x1; xnow <= fillLine.m_x2; xnow++) 0289 { 0290 // At current position, right colour? 0291 if (shouldGoTo (xnow, fillLine.m_y + dy)) 0292 { 0293 // Find minimum and maximum x values 0294 int minxnow = findMinX (fillLine.m_y + dy, xnow); 0295 int maxxnow = findMaxX (fillLine.m_y + dy, xnow); 0296 0297 // Draw line 0298 addLine (fillLine.m_y + dy, minxnow, maxxnow); 0299 0300 // Move x pointer 0301 xnow = maxxnow; 0302 } 0303 } 0304 } 0305 0306 //--------------------------------------------------------------------- 0307 0308 // public 0309 void kpFloodFill::prepare () 0310 { 0311 if (d->prepared) { 0312 return; 0313 } 0314 0315 #if DEBUG_KP_FLOOD_FILL && 1 0316 qCDebug(kpLogImagelib) << "kpFloodFill::prepare()"; 0317 #endif 0318 0319 prepareColorToChange (); 0320 0321 d->boundingRect = QRect (); 0322 0323 0324 #if DEBUG_KP_FLOOD_FILL && 1 0325 qCDebug(kpLogImagelib) << "\tperforming NOP check"; 0326 #endif 0327 0328 // get the color we need to replace 0329 if (d->processedColorSimilarity == 0 && d->color == d->colorToChange) 0330 { 0331 // need to do absolutely nothing (this is a significant optimization 0332 // for people who randomly click a lot over already-filled areas) 0333 d->prepared = true; // sync with all "return true"'s 0334 return; 0335 } 0336 0337 #if DEBUG_KP_FLOOD_FILL && 1 0338 qCDebug(kpLogImagelib) << "\tcreating fillLinesCache"; 0339 #endif 0340 0341 // ready cache 0342 for (int i = 0; i < d->imagePtr->height (); i++) { 0343 d->fillLinesCache.append (QList <kpFillLine> ()); 0344 } 0345 0346 #if DEBUG_KP_FLOOD_FILL && 1 0347 qCDebug(kpLogImagelib) << "\tcreating fill lines"; 0348 #endif 0349 0350 // draw initial line 0351 addLine (d->y, findMinX (d->y, d->x), findMaxX (d->y, d->x)); 0352 0353 for (int i = 0; i < d->fillLines.count(); i++) 0354 { 0355 kpFillLine &fl = d->fillLines[i]; 0356 0357 #if DEBUG_KP_FLOOD_FILL && 0 0358 qCDebug(kpLogImagelib) << "Expanding from y=" << fl.m_y 0359 << " x1=" << fl.m_x1 0360 << " x2=" << fl.m_x2 0361 << endl; 0362 #endif 0363 0364 // 0365 // Make more lines above and below current line. 0366 // 0367 // WARNING: Adds to end of "fillLines" (the list we are iterating through). 0368 findAndAddLines(fl, -1); 0369 findAndAddLines(fl, +1); 0370 } 0371 0372 #if DEBUG_KP_FLOOD_FILL && 1 0373 qCDebug(kpLogImagelib) << "\tfinalising memory usage"; 0374 #endif 0375 0376 // finalize memory usage 0377 d->fillLinesCache.clear (); 0378 0379 d->prepared = true; // sync with all "return true"'s 0380 } 0381 0382 //--------------------------------------------------------------------- 0383 0384 // public 0385 QRect kpFloodFill::boundingRect () 0386 { 0387 prepare (); 0388 0389 return d->boundingRect; 0390 } 0391 0392 //--------------------------------------------------------------------- 0393 // public 0394 void kpFloodFill::fill() 0395 { 0396 prepare(); 0397 0398 QApplication::setOverrideCursor(Qt::WaitCursor); 0399 0400 QPainter painter(d->imagePtr); 0401 0402 // by definition, flood fill with a fully transparent color erases the pixels 0403 // and sets them to be fully transparent 0404 if ( d->color.isTransparent() ) { 0405 painter.setCompositionMode(QPainter::CompositionMode_Clear); 0406 } 0407 0408 painter.setPen(d->color.toQColor()); 0409 0410 for (const auto &l : d->fillLines) 0411 { 0412 if ( l.m_x1 == l.m_x2 ) { 0413 painter.drawPoint(l.m_x1, l.m_y); 0414 } 0415 else { 0416 painter.drawLine(l.m_x1, l.m_y, l.m_x2, l.m_y); 0417 } 0418 } 0419 0420 QApplication::restoreOverrideCursor(); 0421 } 0422 0423 //---------------------------------------------------------------------