From 843f6500aaa01a7cbe6ee7d8e11b87ee38bb1d33 Mon Sep 17 00:00:00 2001 From: MrStevns Date: Sat, 2 Apr 2022 20:33:20 +0200 Subject: [PATCH 01/10] Optimize floodfill algorithm - Minimizes the amount of allocations required to fill by only allocating when the new size has been calculated - Calculate the new fill rect, and only expand to what's required. This should should give a substantial performance improvement to the expand algorithm --- core_lib/src/graphics/bitmap/bitmapbucket.cpp | 4 +- core_lib/src/graphics/bitmap/bitmapimage.cpp | 158 ++++++++++-------- core_lib/src/graphics/bitmap/bitmapimage.h | 11 +- core_lib/src/util/blitrect.cpp | 7 + core_lib/src/util/blitrect.h | 1 + 5 files changed, 109 insertions(+), 72 deletions(-) diff --git a/core_lib/src/graphics/bitmap/bitmapbucket.cpp b/core_lib/src/graphics/bitmap/bitmapbucket.cpp index 8495d6df32..bf8c4556b7 100644 --- a/core_lib/src/graphics/bitmap/bitmapbucket.cpp +++ b/core_lib/src/graphics/bitmap/bitmapbucket.cpp @@ -151,12 +151,14 @@ void BitmapBucket::paint(const QPointF updatedPoint, std::functionbounds(), Qt::transparent); + int expandValue = mProperties.bucketFillExpandEnabled ? mProperties.bucketFillExpand : 0; bool didFloodFill = BitmapImage::floodFill(&replaceImage, &referenceImage, cameraRect, point, fillColor, - tolerance); + tolerance, + expandValue); if (!didFloodFill) { return; diff --git a/core_lib/src/graphics/bitmap/bitmapimage.cpp b/core_lib/src/graphics/bitmap/bitmapimage.cpp index 0194aced27..0ffb2d13f0 100644 --- a/core_lib/src/graphics/bitmap/bitmapimage.cpp +++ b/core_lib/src/graphics/bitmap/bitmapimage.cpp @@ -23,6 +23,8 @@ GNU General Public License for more details. #include #include "util.h" +#include "blitrect.h" + BitmapImage::BitmapImage() { mImage.reset(new QImage); // create null image @@ -717,9 +719,8 @@ void BitmapImage::clear() QRgb BitmapImage::constScanLine(int x, int y) const { - QRgb result = qRgba(0, 0, 0, 0); - if (mBounds.contains(QPoint(x, y))) - { + QRgb result = QRgb(); + if (mBounds.contains(x, y)) { result = *(reinterpret_cast(mImage->constScanLine(y - mBounds.top())) + x - mBounds.left()); } return result; @@ -727,17 +728,11 @@ QRgb BitmapImage::constScanLine(int x, int y) const void BitmapImage::scanLine(int x, int y, QRgb color) { - extend(QPoint(x, y)); - if (mBounds.contains(QPoint(x, y))) - { - // Make sure color is premultiplied before calling - *(reinterpret_cast(image()->scanLine(y - mBounds.top())) + x - mBounds.left()) = - qRgba( - qRed(color), - qGreen(color), - qBlue(color), - qAlpha(color)); + if (!mBounds.contains(x, y)) { + return; } + // Make sure color is premultiplied before calling + *(reinterpret_cast(image()->scanLine(y - mBounds.top())) + x - mBounds.left()) = color; } void BitmapImage::clear(QRect rectangle) @@ -800,14 +795,15 @@ bool BitmapImage::compareColor(QRgb newColor, QRgb oldColor, int tolerance, QHas // Flood fill // ----- http://lodev.org/cgtutor/floodfill.html bool BitmapImage::floodFill(BitmapImage* replaceImage, - BitmapImage* targetImage, - QRect cameraRect, + const BitmapImage* targetImage, + const QRect& cameraRect, QPoint point, QRgb fillColor, - int tolerance) + int tolerance, + int expandValue) { // If the point we are supposed to fill is outside the image and camera bounds, do nothing - if(!cameraRect.united(targetImage->bounds()).contains(point)) + if(!cameraRect.united(targetImage->mBounds).contains(point)) { return false; } @@ -815,26 +811,54 @@ bool BitmapImage::floodFill(BitmapImage* replaceImage, // Square tolerance for use with compareColor tolerance = static_cast(qPow(tolerance, 2)); - QRgb oldColor = targetImage->pixel(point); + QRect newBounds; + QHash> points = floodFillPoints(targetImage, cameraRect, fillColor, point, tolerance, newBounds); + + QRect expandRect = QRect(newBounds.topLeft() - QPoint(expandValue, expandValue), newBounds.bottomRight() + QPoint(expandValue, expandValue)); + if (expandValue > 0) { + newBounds = expandRect; + } + + replaceImage->extend(newBounds); + QHashIterator> xCoords(points); + while (xCoords.hasNext()) { + xCoords.next(); + + QHashIterator yCoords(xCoords.value()); + while (yCoords.hasNext()) { + yCoords.next(); + replaceImage->scanLine(xCoords.key(), yCoords.key(), fillColor); + } + } + + return true; +} + +QHash> BitmapImage::floodFillPoints(const BitmapImage* targetImage, + const QRect& bounds, + const QRgb& fillColor, + QPoint point, + const int tolerance, + QRect& newBounds) +{ + QRgb oldColor = targetImage->constScanLine(point.x(), point.y()); oldColor = qRgba(qRed(oldColor), qGreen(oldColor), qBlue(oldColor), qAlpha(oldColor)); // Preparations QList queue; // queue all the pixels of the filled area (as they are found) QPoint tempPoint; - QRgb newPlacedColor = 0; QScopedPointer< QHash > cache(new QHash()); int xTemp = 0; bool spanLeft = false; bool spanRight = false; - // Extend to size of Camera - targetImage->extend(cameraRect); - queue.append(point); // Preparations END + QHash> floodfillPoints = QHash>(); + BlitRect blitBounds(targetImage->mBounds); while (!queue.empty()) { tempPoint = queue.takeFirst(); @@ -844,77 +868,59 @@ bool BitmapImage::floodFill(BitmapImage* replaceImage, xTemp = point.x(); - newPlacedColor = replaceImage->constScanLine(xTemp, point.y()); - while (xTemp >= targetImage->mBounds.left() && + while (xTemp >= bounds.left() && compareColor(targetImage->constScanLine(xTemp, point.y()), oldColor, tolerance, cache.data())) xTemp--; xTemp++; + int xCoord = xTemp; + int yCoord = point.y(); + QRgb newPlacedColor = floodfillPoints[xCoord][yCoord]; + spanLeft = spanRight = false; - while (xTemp <= targetImage->mBounds.right() && + while (xTemp <= bounds.right() && compareColor(targetImage->constScanLine(xTemp, point.y()), oldColor, tolerance, cache.data()) && newPlacedColor != fillColor) { + QPoint floodPoint = QPoint(xTemp, point.y()); + if (!blitBounds.contains(floodPoint)) { + blitBounds.extend(floodPoint); + } + xCoord = xTemp; + yCoord = point.y(); // Set pixel color - replaceImage->scanLine(xTemp, point.y(), fillColor); + floodfillPoints[xCoord][yCoord] = fillColor; - if (!spanLeft && (point.y() > targetImage->mBounds.top()) && + if (!spanLeft && (point.y() > bounds.top()) && compareColor(targetImage->constScanLine(xTemp, point.y() - 1), oldColor, tolerance, cache.data())) { queue.append(QPoint(xTemp, point.y() - 1)); spanLeft = true; } - else if (spanLeft && (point.y() > targetImage->mBounds.top()) && + else if (spanLeft && (point.y() > bounds.top()) && !compareColor(targetImage->constScanLine(xTemp, point.y() - 1), oldColor, tolerance, cache.data())) { spanLeft = false; } - if (!spanRight && point.y() < targetImage->mBounds.bottom() && + if (!spanRight && point.y() < bounds.bottom() && compareColor(targetImage->constScanLine(xTemp, point.y() + 1), oldColor, tolerance, cache.data())) { queue.append(QPoint(xTemp, point.y() + 1)); spanRight = true; - } - else if (spanRight && point.y() < targetImage->mBounds.bottom() && + else if (spanRight && point.y() < bounds.bottom() && !compareColor(targetImage->constScanLine(xTemp, point.y() + 1), oldColor, tolerance, cache.data())) { spanRight = false; } - Q_ASSERT(queue.count() < (targetImage->mBounds.width() * targetImage->mBounds.height())); + Q_ASSERT(queue.count() < (bounds.width() * bounds.height())); xTemp++; } } - return true; -} - -/** Fills the target image with a given color in a radius of the expansion value - * - * @param targetImage - * @param newColor - * @param expand - */ -void BitmapImage::expandFill(BitmapImage* targetImage, QRgb newColor, int expand) -{ - QList expandPoints; - - QRect expandRect = QRect(targetImage->topLeft() - QPoint(expand, expand), targetImage->bottomRight() + QPoint(expand, expand)); - targetImage->extend(expandRect); - - auto twoDVectorList = manhattanDistance(targetImage, newColor); - - for (int y = 0; y < expandRect.height(); y++) - { - for (int x = 0; x < expandRect.width(); x++) - { - if (twoDVectorList[y][x] <= expand && twoDVectorList[y][x] != 0) { - *(reinterpret_cast(targetImage->image()->scanLine(y)) + x) = newColor; - } - } - } + newBounds = blitBounds; + return floodfillPoints; } -/** Finds all pixels closest to the input color and returns the result as a 2D array - * matching the size of the image +/** Finds all pixels closest to the input color and applies the input color to the image * * An example: * @@ -928,18 +934,16 @@ void BitmapImage::expandFill(BitmapImage* targetImage, QRgb newColor, int expand * * @param bitmapImage: Image to search * @param searchColor: Color to find - * @return Return a 2D array of pixels closes to the inputColor */ -QVector> BitmapImage::manhattanDistance(BitmapImage* bitmapImage, QRgb& searchColor) { +void BitmapImage::expandFill(BitmapImage* targetImage, QRgb& searchColor, int expand) { - // Allocate with size of image size - QVector> manhattanPoints(bitmapImage->height(), QVector(bitmapImage->width())); + QVector> manhattanPoints(targetImage->mBounds.height(), QVector(targetImage->mBounds.width())); // traverse from top left to bottom right for (int y = 0; y < manhattanPoints.length(); y++) { for (int x = 0; x < manhattanPoints[y].length(); x++) { - const QRgb& colorAtPixel = *(reinterpret_cast(bitmapImage->image()->constScanLine(y)) + x); + const QRgb& colorAtPixel = *(reinterpret_cast(targetImage->image()->constScanLine(y)) + x); if (colorAtPixel == searchColor) { manhattanPoints[y][x] = 0; } else { @@ -949,11 +953,21 @@ QVector> BitmapImage::manhattanDistance(BitmapImage* bitmapImage, Q // the value will be the num of pixels away from y - 1 of the next position manhattanPoints[y][x] = qMin(manhattanPoints[y][x], manhattanPoints[y - 1][x] + 1); + + int distance = manhattanPoints[y][x]; + if (distance <= expand && distance != 0) { + *(reinterpret_cast(targetImage->image()->scanLine(y)) + x) = searchColor; + } } if (x > 0) { // the value will be the num of pixels away from x - 1 of the next position manhattanPoints[y][x] = qMin(manhattanPoints[y][x], manhattanPoints[y][x - 1] + 1); + + int distance = manhattanPoints[y][x]; + if (distance <= expand && distance != 0) { + *(reinterpret_cast(targetImage->image()->scanLine(y)) + x) = searchColor; + } } } } @@ -965,13 +979,21 @@ QVector> BitmapImage::manhattanDistance(BitmapImage* bitmapImage, Q if (y + 1 < manhattanPoints.length()) { manhattanPoints[y][x] = qMin(manhattanPoints[y][x], manhattanPoints[y + 1][x] + 1); + + int distance = manhattanPoints[y][x]; + if (distance <= expand && distance != 0) { + *(reinterpret_cast(targetImage->image()->scanLine(y)) + x) = searchColor; + } } if (x + 1 < manhattanPoints[y].length()) { manhattanPoints[y][x] = qMin(manhattanPoints[y][x], manhattanPoints[y][x + 1] + 1); + + int distance = manhattanPoints[y][x]; + if (distance <= expand && distance != 0) { + *(reinterpret_cast(targetImage->image()->scanLine(y)) + x) = searchColor; + } } } } - - return manhattanPoints; } diff --git a/core_lib/src/graphics/bitmap/bitmapimage.h b/core_lib/src/graphics/bitmap/bitmapimage.h index 94d799f994..2046c64b1d 100644 --- a/core_lib/src/graphics/bitmap/bitmapimage.h +++ b/core_lib/src/graphics/bitmap/bitmapimage.h @@ -75,9 +75,14 @@ class BitmapImage : public KeyFrame void clear(QRectF rectangle) { clear(rectangle.toRect()); } static inline bool compareColor(QRgb newColor, QRgb oldColor, int tolerance, QHash *cache); - static bool floodFill(BitmapImage* replaceImage, BitmapImage* targetImage, QRect cameraRect, QPoint point, QRgb fillColor, int tolerance); - static void expandFill(BitmapImage* targetImage, QRgb fillColor, int expand); - static QVector > manhattanDistance(BitmapImage* image, QRgb& searchColor); + static bool floodFill(BitmapImage* replaceImage, const BitmapImage* targetImage, const QRect& cameraRect, QPoint point, QRgb fillColor, int tolerance, int expandValue); + static QHash > floodFillPoints(const BitmapImage* targetImage, + const QRect& bounds, + const QRgb& fillColor, + QPoint point, + const int tolerance, + QRect& newBounds); + static void expandFill(BitmapImage* targetImage, QRgb& searchColor, int expand); void drawLine(QPointF P1, QPointF P2, QPen pen, QPainter::CompositionMode cm, bool antialiasing); void drawRect(QRectF rectangle, QPen pen, QBrush brush, QPainter::CompositionMode cm, bool antialiasing); diff --git a/core_lib/src/util/blitrect.cpp b/core_lib/src/util/blitrect.cpp index 534bdd114e..e578bda31f 100644 --- a/core_lib/src/util/blitrect.cpp +++ b/core_lib/src/util/blitrect.cpp @@ -21,6 +21,13 @@ BlitRect::BlitRect() { } +BlitRect::BlitRect(const QRect rect) +{ + setTopLeft(rect.topLeft()); + setBottomRight(rect.bottomRight()); + mInitialized = true; +} + BlitRect::BlitRect(const QPoint p) { extend(p); diff --git a/core_lib/src/util/blitrect.h b/core_lib/src/util/blitrect.h index 788e54f391..b0c10cfb35 100644 --- a/core_lib/src/util/blitrect.h +++ b/core_lib/src/util/blitrect.h @@ -26,6 +26,7 @@ class BlitRect : public QRect public: explicit BlitRect(); explicit BlitRect(const QPoint p); + explicit BlitRect(const QRect rect); void extend(const QPoint p); private: From 4d0e6a7bc9c95162b38afe684e58bbfcc41615bb Mon Sep 17 00:00:00 2001 From: MrStevns Date: Sun, 3 Apr 2022 16:30:58 +0200 Subject: [PATCH 02/10] Speedup pixel search - Create replaceImage after figuring out the size for the optimal size to search when calling expand - Replace hashmaps with ptr array. - Credits goes to scribblemaniac for the solution to traverse a ptr instead of using hashmaps. --- core_lib/src/graphics/bitmap/bitmapbucket.cpp | 22 +-- core_lib/src/graphics/bitmap/bitmapimage.cpp | 155 ++++++++++-------- core_lib/src/graphics/bitmap/bitmapimage.h | 7 +- 3 files changed, 100 insertions(+), 84 deletions(-) diff --git a/core_lib/src/graphics/bitmap/bitmapbucket.cpp b/core_lib/src/graphics/bitmap/bitmapbucket.cpp index bf8c4556b7..f9be8b3c5a 100644 --- a/core_lib/src/graphics/bitmap/bitmapbucket.cpp +++ b/core_lib/src/graphics/bitmap/bitmapbucket.cpp @@ -149,7 +149,7 @@ void BitmapBucket::paint(const QPointF updatedPoint, std::functionbounds(), Qt::transparent); + BitmapImage* replaceImage = nullptr; int expandValue = mProperties.bucketFillExpandEnabled ? mProperties.bucketFillExpand : 0; bool didFloodFill = BitmapImage::floodFill(&replaceImage, @@ -160,34 +160,29 @@ void BitmapBucket::paint(const QPointF updatedPoint, std::functionpaste(&replaceImage); + targetImage->paste(replaceImage); } else if (mProperties.fillMode == 2) { - targetImage->paste(&replaceImage, QPainter::CompositionMode_DestinationOver); + targetImage->paste(replaceImage, QPainter::CompositionMode_DestinationOver); } else { // fill mode replace - targetImage->paste(&replaceImage, QPainter::CompositionMode_DestinationOut); + targetImage->paste(replaceImage, QPainter::CompositionMode_DestinationOut); // Reduce the opacity of the fill to match the new color - BitmapImage properColor(replaceImage.bounds(), QColor::fromRgba(origColor)); - properColor.paste(&replaceImage, QPainter::CompositionMode_DestinationIn); + BitmapImage properColor(replaceImage->bounds(), QColor::fromRgba(origColor)); + properColor.paste(replaceImage, QPainter::CompositionMode_DestinationIn); // Write reduced-opacity fill image on top of target image targetImage->paste(&properColor); } @@ -196,6 +191,7 @@ void BitmapBucket::paint(const QPointF updatedPoint, std::functionmodification(); + delete replaceImage; state(BucketState::DidFillTarget, targetLayerIndex, currentFrameIndex); } diff --git a/core_lib/src/graphics/bitmap/bitmapimage.cpp b/core_lib/src/graphics/bitmap/bitmapimage.cpp index 0ffb2d13f0..e778ec0c2d 100644 --- a/core_lib/src/graphics/bitmap/bitmapimage.cpp +++ b/core_lib/src/graphics/bitmap/bitmapimage.cpp @@ -794,7 +794,7 @@ bool BitmapImage::compareColor(QRgb newColor, QRgb oldColor, int tolerance, QHas // Flood fill // ----- http://lodev.org/cgtutor/floodfill.html -bool BitmapImage::floodFill(BitmapImage* replaceImage, +bool BitmapImage::floodFill(BitmapImage** replaceImage, const BitmapImage* targetImage, const QRect& cameraRect, QPoint point, @@ -802,8 +802,10 @@ bool BitmapImage::floodFill(BitmapImage* replaceImage, int tolerance, int expandValue) { + QRect maxBounds = cameraRect.united(targetImage->mBounds); + // If the point we are supposed to fill is outside the image and camera bounds, do nothing - if(!cameraRect.united(targetImage->mBounds).contains(point)) + if(!maxBounds.contains(point)) { return false; } @@ -812,31 +814,40 @@ bool BitmapImage::floodFill(BitmapImage* replaceImage, tolerance = static_cast(qPow(tolerance, 2)); QRect newBounds; - QHash> points = floodFillPoints(targetImage, cameraRect, fillColor, point, tolerance, newBounds); + const bool *filledPixels = floodFillPoints(targetImage, maxBounds, point, tolerance, newBounds); QRect expandRect = QRect(newBounds.topLeft() - QPoint(expandValue, expandValue), newBounds.bottomRight() + QPoint(expandValue, expandValue)); if (expandValue > 0) { newBounds = expandRect; } - replaceImage->extend(newBounds); - QHashIterator> xCoords(points); - while (xCoords.hasNext()) { - xCoords.next(); + *replaceImage = new BitmapImage(newBounds, Qt::transparent); + + int imgWidth = maxBounds.width(), left = maxBounds.left(), top = maxBounds.top(); + int filledCount = 0; - QHashIterator yCoords(xCoords.value()); - while (yCoords.hasNext()) { - yCoords.next(); - replaceImage->scanLine(xCoords.key(), yCoords.key(), fillColor); + for (int i = 0; i < (maxBounds.height()*maxBounds.width()); i++) { + if (!filledPixels[i]) + { + continue; } + int x = i % imgWidth + left; + int y = i / imgWidth + top; + (*replaceImage)->scanLine(x, y, fillColor); + filledCount++; + } + + delete[] filledPixels; + + if (expandValue > 0) { + expandFill(*replaceImage, newBounds, fillColor, expandValue); } return true; } -QHash> BitmapImage::floodFillPoints(const BitmapImage* targetImage, +const bool* BitmapImage::floodFillPoints(const BitmapImage* targetImage, const QRect& bounds, - const QRgb& fillColor, QPoint point, const int tolerance, QRect& newBounds) @@ -857,8 +868,9 @@ QHash> BitmapImage::floodFillPoints(const BitmapImage* tar queue.append(point); // Preparations END - QHash> floodfillPoints = QHash>(); - BlitRect blitBounds(targetImage->mBounds); + bool *filledPixels = new bool[bounds.height()*bounds.width()]{}; + + BlitRect blitBounds(point); while (!queue.empty()) { tempPoint = queue.takeFirst(); @@ -868,28 +880,26 @@ QHash> BitmapImage::floodFillPoints(const BitmapImage* tar xTemp = point.x(); + int xCoord = xTemp - bounds.left(); + int yCoord = point.y() - bounds.top(); + if (filledPixels[yCoord*bounds.width()+xCoord]) continue; + while (xTemp >= bounds.left() && compareColor(targetImage->constScanLine(xTemp, point.y()), oldColor, tolerance, cache.data())) xTemp--; xTemp++; - int xCoord = xTemp; - int yCoord = point.y(); - QRgb newPlacedColor = floodfillPoints[xCoord][yCoord]; - spanLeft = spanRight = false; while (xTemp <= bounds.right() && - compareColor(targetImage->constScanLine(xTemp, point.y()), oldColor, tolerance, cache.data()) && - newPlacedColor != fillColor) + compareColor(targetImage->constScanLine(xTemp, point.y()), oldColor, tolerance, cache.data())) { QPoint floodPoint = QPoint(xTemp, point.y()); if (!blitBounds.contains(floodPoint)) { blitBounds.extend(floodPoint); } - xCoord = xTemp; - yCoord = point.y(); - // Set pixel color - floodfillPoints[xCoord][yCoord] = fillColor; + xCoord = xTemp - bounds.left(); + // This pixel is what we're going to fill later + filledPixels[yCoord*bounds.width()+xCoord] = true; if (!spanLeft && (point.y() > bounds.top()) && compareColor(targetImage->constScanLine(xTemp, point.y() - 1), oldColor, tolerance, cache.data())) { @@ -917,7 +927,7 @@ QHash> BitmapImage::floodFillPoints(const BitmapImage* tar } newBounds = blitBounds; - return floodfillPoints; + return filledPixels; } /** Finds all pixels closest to the input color and applies the input color to the image @@ -935,65 +945,76 @@ QHash> BitmapImage::floodFillPoints(const BitmapImage* tar * @param bitmapImage: Image to search * @param searchColor: Color to find */ -void BitmapImage::expandFill(BitmapImage* targetImage, QRgb& searchColor, int expand) { +void BitmapImage::expandFill(BitmapImage* targetImage, const QRect& maxBounds, const QRgb& searchColor, int expand) { + + int height = maxBounds.height(); + int width = maxBounds.width(); + int left = maxBounds.left(), top = maxBounds.top(); + + int* manhattanPoints = new int[maxBounds.height()*maxBounds.width()]{}; - QVector> manhattanPoints(targetImage->mBounds.height(), QVector(targetImage->mBounds.width())); + for (int i = 0; i < maxBounds.height()*maxBounds.width(); i++) { - // traverse from top left to bottom right - for (int y = 0; y < manhattanPoints.length(); y++) { - for (int x = 0; x < manhattanPoints[y].length(); x++) { + int x = i % width; + int y = i / width; + int posX = x + left; + int posY = y + top; - const QRgb& colorAtPixel = *(reinterpret_cast(targetImage->image()->constScanLine(y)) + x); - if (colorAtPixel == searchColor) { - manhattanPoints[y][x] = 0; - } else { - manhattanPoints[y][x] = manhattanPoints.length() + manhattanPoints[y].length(); + const QRgb& colorAtPixel = *(reinterpret_cast(targetImage->image()->constScanLine(y)) + x); + if (colorAtPixel == searchColor) { + manhattanPoints[y*width+x] = 0; + } else { + manhattanPoints[y*width+x] = height + width; - if (y > 0) { - // the value will be the num of pixels away from y - 1 of the next position - manhattanPoints[y][x] = qMin(manhattanPoints[y][x], - manhattanPoints[y - 1][x] + 1); + if (y > 0 && y < (height - 1)) { + // the value will be the num of pixels away from y - 1 of the next position + manhattanPoints[y*width+x] = qMin(manhattanPoints[y*width+x], + manhattanPoints[(y - 1) * width+x] + 1); - int distance = manhattanPoints[y][x]; - if (distance <= expand && distance != 0) { - *(reinterpret_cast(targetImage->image()->scanLine(y)) + x) = searchColor; - } + int distance = manhattanPoints[y*width+x]; + if (distance <= expand && distance != 0) { + targetImage->scanLine(posX, posY, searchColor); } - if (x > 0) { - // the value will be the num of pixels away from x - 1 of the next position - manhattanPoints[y][x] = qMin(manhattanPoints[y][x], - manhattanPoints[y][x - 1] + 1); - - int distance = manhattanPoints[y][x]; - if (distance <= expand && distance != 0) { - *(reinterpret_cast(targetImage->image()->scanLine(y)) + x) = searchColor; - } + } + if (x > 0 && x < (width - 1)) { + // the value will be the num of pixels away from x - 1 of the next position + manhattanPoints[y*width+x] = qMin(manhattanPoints[y*width+x], + manhattanPoints[y*width+(x - 1)] + 1); + + int distance = manhattanPoints[y*width+x]; + if (distance <= expand && distance != 0) { + targetImage->scanLine(posX, posY, searchColor); } } } } // traverse from bottom right to top left - for (int y = manhattanPoints.length() - 1; y >= 0; y--) { - for (int x = manhattanPoints[y].length() - 1; x >= 0; x--) { + for (int i = maxBounds.height()*maxBounds.width(); i > 0; i--) { - if (y + 1 < manhattanPoints.length()) { - manhattanPoints[y][x] = qMin(manhattanPoints[y][x], manhattanPoints[y + 1][x] + 1); + int x = i % width; + int y = i / width; + int posX = x + left; + int posY = y + top; - int distance = manhattanPoints[y][x]; - if (distance <= expand && distance != 0) { - *(reinterpret_cast(targetImage->image()->scanLine(y)) + x) = searchColor; - } + if (y + 1 < maxBounds.height()) { + manhattanPoints[y*width+x] = qMin(manhattanPoints[y*width+x], manhattanPoints[(y + 1)*width+x] + 1); + + int distance = manhattanPoints[y*width+x]; + if (distance <= expand && distance != 0) { + targetImage->scanLine(posX, posY, searchColor); } - if (x + 1 < manhattanPoints[y].length()) { - manhattanPoints[y][x] = qMin(manhattanPoints[y][x], manhattanPoints[y][x + 1] + 1); + } + if (x + 1 < maxBounds.width()) { + manhattanPoints[y*width+x] = qMin(manhattanPoints[y*width+x], manhattanPoints[y*width+(x + 1)] + 1); - int distance = manhattanPoints[y][x]; - if (distance <= expand && distance != 0) { - *(reinterpret_cast(targetImage->image()->scanLine(y)) + x) = searchColor; - } + int distance = manhattanPoints[y*width+x]; + if (distance <= expand && distance != 0) { + targetImage->scanLine(posX, posY, searchColor); } } } + + delete[] manhattanPoints; } diff --git a/core_lib/src/graphics/bitmap/bitmapimage.h b/core_lib/src/graphics/bitmap/bitmapimage.h index 2046c64b1d..795e26f689 100644 --- a/core_lib/src/graphics/bitmap/bitmapimage.h +++ b/core_lib/src/graphics/bitmap/bitmapimage.h @@ -75,14 +75,13 @@ class BitmapImage : public KeyFrame void clear(QRectF rectangle) { clear(rectangle.toRect()); } static inline bool compareColor(QRgb newColor, QRgb oldColor, int tolerance, QHash *cache); - static bool floodFill(BitmapImage* replaceImage, const BitmapImage* targetImage, const QRect& cameraRect, QPoint point, QRgb fillColor, int tolerance, int expandValue); - static QHash > floodFillPoints(const BitmapImage* targetImage, + static bool floodFill(BitmapImage** replaceImage, const BitmapImage* targetImage, const QRect& cameraRect, QPoint point, QRgb fillColor, int tolerance, int expandValue); + static const bool* floodFillPoints(const BitmapImage* targetImage, const QRect& bounds, - const QRgb& fillColor, QPoint point, const int tolerance, QRect& newBounds); - static void expandFill(BitmapImage* targetImage, QRgb& searchColor, int expand); + static void expandFill(BitmapImage* targetImage, const QRect& maxBounds, const QRgb& searchColor, int expand); void drawLine(QPointF P1, QPointF P2, QPen pen, QPainter::CompositionMode cm, bool antialiasing); void drawRect(QRectF rectangle, QPen pen, QBrush brush, QPainter::CompositionMode cm, bool antialiasing); From 49d1f068d0822b0e55c0564748e8f6c1a6ff6374 Mon Sep 17 00:00:00 2001 From: scribblemaniac Date: Sun, 3 Apr 2022 19:10:33 -0600 Subject: [PATCH 03/10] Use filledPixel array for expandFill --- core_lib/src/graphics/bitmap/bitmapimage.cpp | 163 ++++++++++--------- core_lib/src/graphics/bitmap/bitmapimage.h | 13 +- 2 files changed, 91 insertions(+), 85 deletions(-) diff --git a/core_lib/src/graphics/bitmap/bitmapimage.cpp b/core_lib/src/graphics/bitmap/bitmapimage.cpp index e778ec0c2d..8f42270766 100644 --- a/core_lib/src/graphics/bitmap/bitmapimage.cpp +++ b/core_lib/src/graphics/bitmap/bitmapimage.cpp @@ -802,31 +802,34 @@ bool BitmapImage::floodFill(BitmapImage** replaceImage, int tolerance, int expandValue) { - QRect maxBounds = cameraRect.united(targetImage->mBounds); + QRect fillBounds = cameraRect.united(targetImage->mBounds); // If the point we are supposed to fill is outside the image and camera bounds, do nothing - if(!maxBounds.contains(point)) + if(!fillBounds.contains(point)) { return false; } + QRect maxBounds = fillBounds.adjusted(-expandValue, -expandValue, expandValue, expandValue); + // Square tolerance for use with compareColor tolerance = static_cast(qPow(tolerance, 2)); QRect newBounds; - const bool *filledPixels = floodFillPoints(targetImage, maxBounds, point, tolerance, newBounds); + bool *filledPixels = floodFillPoints(targetImage, fillBounds, maxBounds, point, tolerance, newBounds); - QRect expandRect = QRect(newBounds.topLeft() - QPoint(expandValue, expandValue), newBounds.bottomRight() + QPoint(expandValue, expandValue)); - if (expandValue > 0) { - newBounds = expandRect; + if (expandValue > 0) + { + newBounds = newBounds.adjusted(-expandValue, -expandValue, expandValue, expandValue);; + expandFill(newBounds, maxBounds, filledPixels, expandValue); } *replaceImage = new BitmapImage(newBounds, Qt::transparent); int imgWidth = maxBounds.width(), left = maxBounds.left(), top = maxBounds.top(); - int filledCount = 0; - for (int i = 0; i < (maxBounds.height()*maxBounds.width()); i++) { + for (int i = 0; i < (maxBounds.height()*maxBounds.width()); i++) + { if (!filledPixels[i]) { continue; @@ -834,23 +837,19 @@ bool BitmapImage::floodFill(BitmapImage** replaceImage, int x = i % imgWidth + left; int y = i / imgWidth + top; (*replaceImage)->scanLine(x, y, fillColor); - filledCount++; } delete[] filledPixels; - if (expandValue > 0) { - expandFill(*replaceImage, newBounds, fillColor, expandValue); - } - return true; } -const bool* BitmapImage::floodFillPoints(const BitmapImage* targetImage, - const QRect& bounds, - QPoint point, - const int tolerance, - QRect& newBounds) +bool* BitmapImage::floodFillPoints(const BitmapImage* targetImage, + const QRect& searchBounds, + const QRect& maxBounds, + QPoint point, + const int tolerance, + QRect& newBounds) { QRgb oldColor = targetImage->constScanLine(point.x(), point.y()); oldColor = qRgba(qRed(oldColor), qGreen(oldColor), qBlue(oldColor), qAlpha(oldColor)); @@ -868,7 +867,7 @@ const bool* BitmapImage::floodFillPoints(const BitmapImage* targetImage, queue.append(point); // Preparations END - bool *filledPixels = new bool[bounds.height()*bounds.width()]{}; + bool *filledPixels = new bool[maxBounds.height()*maxBounds.width()]{}; BlitRect blitBounds(point); while (!queue.empty()) @@ -880,48 +879,47 @@ const bool* BitmapImage::floodFillPoints(const BitmapImage* targetImage, xTemp = point.x(); - int xCoord = xTemp - bounds.left(); - int yCoord = point.y() - bounds.top(); - if (filledPixels[yCoord*bounds.width()+xCoord]) continue; + int xCoord = xTemp - maxBounds.left(); + int yCoord = point.y() - maxBounds.top(); + if (filledPixels[yCoord*maxBounds.width()+xCoord]) continue; - while (xTemp >= bounds.left() && + while (xTemp >= searchBounds.left() && compareColor(targetImage->constScanLine(xTemp, point.y()), oldColor, tolerance, cache.data())) xTemp--; xTemp++; spanLeft = spanRight = false; - while (xTemp <= bounds.right() && + while (xTemp <= searchBounds.right() && compareColor(targetImage->constScanLine(xTemp, point.y()), oldColor, tolerance, cache.data())) { - QPoint floodPoint = QPoint(xTemp, point.y()); if (!blitBounds.contains(floodPoint)) { blitBounds.extend(floodPoint); } - xCoord = xTemp - bounds.left(); + xCoord = xTemp - maxBounds.left(); // This pixel is what we're going to fill later - filledPixels[yCoord*bounds.width()+xCoord] = true; + filledPixels[yCoord*maxBounds.width()+xCoord] = true; - if (!spanLeft && (point.y() > bounds.top()) && + if (!spanLeft && (point.y() > searchBounds.top()) && compareColor(targetImage->constScanLine(xTemp, point.y() - 1), oldColor, tolerance, cache.data())) { queue.append(QPoint(xTemp, point.y() - 1)); spanLeft = true; } - else if (spanLeft && (point.y() > bounds.top()) && + else if (spanLeft && (point.y() > searchBounds.top()) && !compareColor(targetImage->constScanLine(xTemp, point.y() - 1), oldColor, tolerance, cache.data())) { spanLeft = false; } - if (!spanRight && point.y() < bounds.bottom() && + if (!spanRight && point.y() < searchBounds.bottom() && compareColor(targetImage->constScanLine(xTemp, point.y() + 1), oldColor, tolerance, cache.data())) { queue.append(QPoint(xTemp, point.y() + 1)); spanRight = true; } - else if (spanRight && point.y() < bounds.bottom() && + else if (spanRight && point.y() < searchBounds.bottom() && !compareColor(targetImage->constScanLine(xTemp, point.y() + 1), oldColor, tolerance, cache.data())) { spanRight = false; } - Q_ASSERT(queue.count() < (bounds.width() * bounds.height())); + Q_ASSERT(queue.count() < (searchBounds.width() * searchBounds.height())); xTemp++; } } @@ -945,72 +943,79 @@ const bool* BitmapImage::floodFillPoints(const BitmapImage* targetImage, * @param bitmapImage: Image to search * @param searchColor: Color to find */ -void BitmapImage::expandFill(BitmapImage* targetImage, const QRect& maxBounds, const QRgb& searchColor, int expand) { - - int height = maxBounds.height(); - int width = maxBounds.width(); - int left = maxBounds.left(), top = maxBounds.top(); - - int* manhattanPoints = new int[maxBounds.height()*maxBounds.width()]{}; - - for (int i = 0; i < maxBounds.height()*maxBounds.width(); i++) { +void BitmapImage::expandFill(const QRect& searchBounds, const QRect& maxBounds, bool* filledPixels, int expand) +{ + const QRect& translatedSearchBounds = searchBounds.translated(-maxBounds.topLeft()); + const int searchWidth = searchBounds.width(); + const int searchHeight = searchBounds.height(); + const int maxWidth = maxBounds.width(); - int x = i % width; - int y = i / width; - int posX = x + left; - int posY = y + top; + int* manhattanPoints = new int[maxBounds.height()*maxBounds.width()]; + std::fill_n(manhattanPoints, maxBounds.height()*maxBounds.width(), searchWidth+searchHeight); - const QRgb& colorAtPixel = *(reinterpret_cast(targetImage->image()->constScanLine(y)) + x); - if (colorAtPixel == searchColor) { - manhattanPoints[y*width+x] = 0; - } else { - manhattanPoints[y*width+x] = height + width; + for (int y = translatedSearchBounds.top(); y <= translatedSearchBounds.bottom(); y++) + { + for (int x = translatedSearchBounds.left(); x <= translatedSearchBounds.right(); x++) + { + const int i = y*maxWidth+x; + if (filledPixels[i]) + { + manhattanPoints[i] = 0; + continue; + } - if (y > 0 && y < (height - 1)) { + if (y > translatedSearchBounds.top()) + { // the value will be the num of pixels away from y - 1 of the next position - manhattanPoints[y*width+x] = qMin(manhattanPoints[y*width+x], - manhattanPoints[(y - 1) * width+x] + 1); + const int distance = qMin(manhattanPoints[i], manhattanPoints[i-maxWidth] + 1); - int distance = manhattanPoints[y*width+x]; - if (distance <= expand && distance != 0) { - targetImage->scanLine(posX, posY, searchColor); + manhattanPoints[i] = distance; + if (distance <= expand) + { + filledPixels[i] = true; } } - if (x > 0 && x < (width - 1)) { + if (x > translatedSearchBounds.left()) + { // the value will be the num of pixels away from x - 1 of the next position - manhattanPoints[y*width+x] = qMin(manhattanPoints[y*width+x], - manhattanPoints[y*width+(x - 1)] + 1); + const int distance = qMin(manhattanPoints[i], manhattanPoints[i-1] + 1); - int distance = manhattanPoints[y*width+x]; - if (distance <= expand && distance != 0) { - targetImage->scanLine(posX, posY, searchColor); + manhattanPoints[i] = distance; + if (distance <= expand) + { + filledPixels[i] = true; } } } } // traverse from bottom right to top left - for (int i = maxBounds.height()*maxBounds.width(); i > 0; i--) { - - int x = i % width; - int y = i / width; - int posX = x + left; - int posY = y + top; + for (int y = translatedSearchBounds.bottom(); y >= translatedSearchBounds.top(); y--) + { + for (int x = translatedSearchBounds.right(); x >= translatedSearchBounds.left(); x--) + { + const int i = y*maxWidth+x; + if (filledPixels[i]) continue; - if (y + 1 < maxBounds.height()) { - manhattanPoints[y*width+x] = qMin(manhattanPoints[y*width+x], manhattanPoints[(y + 1)*width+x] + 1); + if (y + 1 < translatedSearchBounds.bottom()) + { + const int distance = qMin(manhattanPoints[i], manhattanPoints[i+maxWidth] + 1); - int distance = manhattanPoints[y*width+x]; - if (distance <= expand && distance != 0) { - targetImage->scanLine(posX, posY, searchColor); + manhattanPoints[i] = distance; + if (distance <= expand) + { + filledPixels[i] = true; + } } - } - if (x + 1 < maxBounds.width()) { - manhattanPoints[y*width+x] = qMin(manhattanPoints[y*width+x], manhattanPoints[y*width+(x + 1)] + 1); + if (x + 1 < translatedSearchBounds.right()) + { + const int distance = qMin(manhattanPoints[i], manhattanPoints[i+1] + 1); - int distance = manhattanPoints[y*width+x]; - if (distance <= expand && distance != 0) { - targetImage->scanLine(posX, posY, searchColor); + manhattanPoints[i] = distance; + if (distance <= expand) + { + filledPixels[i] = true; + } } } } diff --git a/core_lib/src/graphics/bitmap/bitmapimage.h b/core_lib/src/graphics/bitmap/bitmapimage.h index 795e26f689..77233455b5 100644 --- a/core_lib/src/graphics/bitmap/bitmapimage.h +++ b/core_lib/src/graphics/bitmap/bitmapimage.h @@ -76,12 +76,13 @@ class BitmapImage : public KeyFrame static inline bool compareColor(QRgb newColor, QRgb oldColor, int tolerance, QHash *cache); static bool floodFill(BitmapImage** replaceImage, const BitmapImage* targetImage, const QRect& cameraRect, QPoint point, QRgb fillColor, int tolerance, int expandValue); - static const bool* floodFillPoints(const BitmapImage* targetImage, - const QRect& bounds, - QPoint point, - const int tolerance, - QRect& newBounds); - static void expandFill(BitmapImage* targetImage, const QRect& maxBounds, const QRgb& searchColor, int expand); + static bool *floodFillPoints(const BitmapImage* targetImage, + const QRect &searchBounds, + const QRect& maxBounds, + QPoint point, + const int tolerance, + QRect& newBounds); + static void expandFill(const QRect &searchBounds, const QRect& maxBounds, bool *filledPixels, int expand); void drawLine(QPointF P1, QPointF P2, QPen pen, QPainter::CompositionMode cm, bool antialiasing); void drawRect(QRectF rectangle, QPen pen, QBrush brush, QPainter::CompositionMode cm, bool antialiasing); From 5c04f27cead1561683e63dec4cb6a105055d2075 Mon Sep 17 00:00:00 2001 From: MrStevns Date: Fri, 8 Apr 2022 17:46:19 +0200 Subject: [PATCH 04/10] Fix bugs where expand algorithm didn't fill properly --- core_lib/src/graphics/bitmap/bitmapbucket.cpp | 2 +- core_lib/src/graphics/bitmap/bitmapimage.cpp | 129 +++++++++--------- core_lib/src/graphics/bitmap/bitmapimage.h | 13 +- 3 files changed, 74 insertions(+), 70 deletions(-) diff --git a/core_lib/src/graphics/bitmap/bitmapbucket.cpp b/core_lib/src/graphics/bitmap/bitmapbucket.cpp index f9be8b3c5a..ba190af1ed 100644 --- a/core_lib/src/graphics/bitmap/bitmapbucket.cpp +++ b/core_lib/src/graphics/bitmap/bitmapbucket.cpp @@ -160,11 +160,11 @@ void BitmapBucket::paint(const QPointF updatedPoint, std::function 0) - { - newBounds = newBounds.adjusted(-expandValue, -expandValue, expandValue, expandValue);; - expandFill(newBounds, maxBounds, filledPixels, expandValue); + QRect expandRect = newBounds.adjusted(-expandValue, -expandValue, expandValue, expandValue); + + if (expandValue > 0) { + newBounds = expandRect; + } + + if (!maxBounds.contains(expandRect)) { + newBounds = maxBounds; } *replaceImage = new BitmapImage(newBounds, Qt::transparent); - int imgWidth = maxBounds.width(), left = maxBounds.left(), top = maxBounds.top(); + int maxWidth = maxBounds.width(), left = maxBounds.left(), top = maxBounds.top(); - for (int i = 0; i < (maxBounds.height()*maxBounds.width()); i++) + const QRect& translatedSearchBounds = newBounds.translated(-maxBounds.topLeft()); + if (expandValue > 0) { + expandFill(filledPixels, translatedSearchBounds, maxBounds, expandValue); + } + + for (int y = translatedSearchBounds.top(); y <= translatedSearchBounds.bottom(); y++) { - if (!filledPixels[i]) + for (int x = translatedSearchBounds.left(); x <= translatedSearchBounds.right(); x++) { - continue; + int index = y * maxWidth + x; + if (!filledPixels[index]) + { + continue; + } + (*replaceImage)->scanLine(x + left, y + top, fillColor); } - int x = i % imgWidth + left; - int y = i / imgWidth + top; - (*replaceImage)->scanLine(x, y, fillColor); } delete[] filledPixels; @@ -845,11 +856,11 @@ bool BitmapImage::floodFill(BitmapImage** replaceImage, } bool* BitmapImage::floodFillPoints(const BitmapImage* targetImage, - const QRect& searchBounds, - const QRect& maxBounds, - QPoint point, - const int tolerance, - QRect& newBounds) + const QRect& searchBounds, + const QRect& maxBounds, + QPoint point, + const int tolerance, + QRect& newBounds) { QRgb oldColor = targetImage->constScanLine(point.x(), point.y()); oldColor = qRgba(qRed(oldColor), qGreen(oldColor), qBlue(oldColor), qAlpha(oldColor)); @@ -891,6 +902,7 @@ bool* BitmapImage::floodFillPoints(const BitmapImage* targetImage, while (xTemp <= searchBounds.right() && compareColor(targetImage->constScanLine(xTemp, point.y()), oldColor, tolerance, cache.data())) { + QPoint floodPoint = QPoint(xTemp, point.y()); if (!blitBounds.contains(floodPoint)) { blitBounds.extend(floodPoint); @@ -919,7 +931,7 @@ bool* BitmapImage::floodFillPoints(const BitmapImage* targetImage, spanRight = false; } - Q_ASSERT(queue.count() < (searchBounds.width() * searchBounds.height())); + Q_ASSERT(queue.count() < (maxBounds.width() * maxBounds.height())); xTemp++; } } @@ -943,78 +955,71 @@ bool* BitmapImage::floodFillPoints(const BitmapImage* targetImage, * @param bitmapImage: Image to search * @param searchColor: Color to find */ -void BitmapImage::expandFill(const QRect& searchBounds, const QRect& maxBounds, bool* filledPixels, int expand) -{ - const QRect& translatedSearchBounds = searchBounds.translated(-maxBounds.topLeft()); - const int searchWidth = searchBounds.width(); - const int searchHeight = searchBounds.height(); +void BitmapImage::expandFill(bool* fillPixels, const QRect& searchBounds, const QRect& maxBounds, int expand) { + + const int maxHeight = maxBounds.height(); const int maxWidth = maxBounds.width(); - int* manhattanPoints = new int[maxBounds.height()*maxBounds.width()]; - std::fill_n(manhattanPoints, maxBounds.height()*maxBounds.width(), searchWidth+searchHeight); + int* manhattanPoints = new int[(maxBounds.height())*(maxBounds.width())]{}; - for (int y = translatedSearchBounds.top(); y <= translatedSearchBounds.bottom(); y++) + /// Fill points with max length, this is important because otherwise the filled pixels will include a border of the expanded area + std::fill_n(manhattanPoints, maxBounds.height()*maxBounds.width(), searchBounds.width()+searchBounds.height()); + + for (int y = searchBounds.top(); y <= searchBounds.bottom(); y++) { - for (int x = translatedSearchBounds.left(); x <= translatedSearchBounds.right(); x++) + for (int x = searchBounds.left(); x <= searchBounds.right(); x++) { - const int i = y*maxWidth+x; - if (filledPixels[i]) - { - manhattanPoints[i] = 0; + const int index = y*maxWidth+x; + + if (fillPixels[index]) { + manhattanPoints[index] = 0; continue; } - if (y > translatedSearchBounds.top()) - { + if (y > 0 && y < (maxHeight - 1)) { // the value will be the num of pixels away from y - 1 of the next position - const int distance = qMin(manhattanPoints[i], manhattanPoints[i-maxWidth] + 1); + manhattanPoints[index] = qMin(manhattanPoints[index], + manhattanPoints[(y - 1) * maxWidth+x] + 1); - manhattanPoints[i] = distance; - if (distance <= expand) - { - filledPixels[i] = true; + int distance = manhattanPoints[index]; + if (distance <= expand && distance != 0) { + fillPixels[index] = true; } } - if (x > translatedSearchBounds.left()) - { + if (x > 0 && x < (maxWidth - 1)) { // the value will be the num of pixels away from x - 1 of the next position - const int distance = qMin(manhattanPoints[i], manhattanPoints[i-1] + 1); + manhattanPoints[index] = qMin(manhattanPoints[index], + manhattanPoints[y*maxWidth+(x - 1)] + 1); - manhattanPoints[i] = distance; - if (distance <= expand) - { - filledPixels[i] = true; + int distance = manhattanPoints[index]; + if (distance <= expand && distance != 0) { + fillPixels[index] = true; } } } } // traverse from bottom right to top left - for (int y = translatedSearchBounds.bottom(); y >= translatedSearchBounds.top(); y--) + for (int y = searchBounds.bottom(); y >= searchBounds.top(); y--) { - for (int x = translatedSearchBounds.right(); x >= translatedSearchBounds.left(); x--) + for (int x = searchBounds.right(); x >= searchBounds.left(); x--) { - const int i = y*maxWidth+x; - if (filledPixels[i]) continue; + const int index = y*maxWidth+x; - if (y + 1 < translatedSearchBounds.bottom()) - { - const int distance = qMin(manhattanPoints[i], manhattanPoints[i+maxWidth] + 1); + if (y + 1 < maxBounds.height()) { + manhattanPoints[index] = qMin(manhattanPoints[index], manhattanPoints[(y + 1)*maxWidth+x] + 1); - manhattanPoints[i] = distance; - if (distance <= expand) - { - filledPixels[i] = true; + int distance = manhattanPoints[index]; + if (distance <= expand && distance != 0) { + fillPixels[index] = true; } } - if (x + 1 < translatedSearchBounds.right()) - { - const int distance = qMin(manhattanPoints[i], manhattanPoints[i+1] + 1); + if (x + 1 < maxBounds.width()) { + manhattanPoints[index] = qMin(manhattanPoints[index], manhattanPoints[y*maxWidth+(x + 1)] + 1); - manhattanPoints[i] = distance; - if (distance <= expand) - { - filledPixels[i] = true; + int distance = manhattanPoints[index]; + if (distance <= expand && distance != 0) { + fillPixels[index] = true; } } } diff --git a/core_lib/src/graphics/bitmap/bitmapimage.h b/core_lib/src/graphics/bitmap/bitmapimage.h index 77233455b5..220774c0a2 100644 --- a/core_lib/src/graphics/bitmap/bitmapimage.h +++ b/core_lib/src/graphics/bitmap/bitmapimage.h @@ -76,13 +76,12 @@ class BitmapImage : public KeyFrame static inline bool compareColor(QRgb newColor, QRgb oldColor, int tolerance, QHash *cache); static bool floodFill(BitmapImage** replaceImage, const BitmapImage* targetImage, const QRect& cameraRect, QPoint point, QRgb fillColor, int tolerance, int expandValue); - static bool *floodFillPoints(const BitmapImage* targetImage, - const QRect &searchBounds, - const QRect& maxBounds, - QPoint point, - const int tolerance, - QRect& newBounds); - static void expandFill(const QRect &searchBounds, const QRect& maxBounds, bool *filledPixels, int expand); + static bool* floodFillPoints(const BitmapImage* targetImage, + const QRect& searchBounds, const QRect& maxBounds, + QPoint point, + const int tolerance, + QRect& newBounds); + static void expandFill(bool* fillPixels, const QRect& searchBounds, const QRect& maxBounds, int expand); void drawLine(QPointF P1, QPointF P2, QPen pen, QPainter::CompositionMode cm, bool antialiasing); void drawRect(QRectF rectangle, QPen pen, QBrush brush, QPainter::CompositionMode cm, bool antialiasing); From 3bace61f4beee819b579e73b9c4a175aa3713187 Mon Sep 17 00:00:00 2001 From: MrStevns Date: Fri, 8 Apr 2022 18:29:13 +0200 Subject: [PATCH 05/10] Optimize floodfill search for contours This change will only affect when filling inside a contour, but that also means that even on a huge 5000x5000 canvas, filling inside a 200x200 contour will be much faster. --- core_lib/src/graphics/bitmap/bitmapimage.cpp | 56 ++++++++++++-------- core_lib/src/graphics/bitmap/bitmapimage.h | 4 +- 2 files changed, 36 insertions(+), 24 deletions(-) diff --git a/core_lib/src/graphics/bitmap/bitmapimage.cpp b/core_lib/src/graphics/bitmap/bitmapimage.cpp index b96c61476c..a35fc680b8 100644 --- a/core_lib/src/graphics/bitmap/bitmapimage.cpp +++ b/core_lib/src/graphics/bitmap/bitmapimage.cpp @@ -792,56 +792,58 @@ bool BitmapImage::compareColor(QRgb newColor, QRgb oldColor, int tolerance, QHas return isSimilar; } -// Flood fill -// ----- http://lodev.org/cgtutor/floodfill.html bool BitmapImage::floodFill(BitmapImage** replaceImage, const BitmapImage* targetImage, const QRect& cameraRect, - QPoint point, - QRgb fillColor, + const QPoint& point, + const QRgb& fillColor, int tolerance, - int expandValue) + const int expandValue) { - QRect fillBounds = cameraRect.united(targetImage->mBounds); + QRect fillBounds = targetImage->mBounds; + QRect maxBounds = cameraRect.united(fillBounds).adjusted(-expandValue, -expandValue, expandValue, expandValue); - // If the point we are supposed to fill is outside the image and camera bounds, do nothing - if(!fillBounds.contains(point)) + // If the point we are supposed to fill is outside the max bounds, do nothing + if(!maxBounds.contains(point)) { return false; } - QRect maxBounds = fillBounds.adjusted(-expandValue, -expandValue, expandValue, expandValue); - // Square tolerance for use with compareColor tolerance = static_cast(qPow(tolerance, 2)); QRect newBounds; bool *filledPixels = floodFillPoints(targetImage, fillBounds, maxBounds, point, tolerance, newBounds); - QRect expandRect = newBounds.adjusted(-expandValue, -expandValue, expandValue, expandValue); + const QRect& expandRect = newBounds.adjusted(-expandValue, -expandValue, expandValue, expandValue); + // The scanned bounds should take the expansion into account if (expandValue > 0) { newBounds = expandRect; } - if (!maxBounds.contains(expandRect)) { + // The new bounds was smaller than the max, so set the size to maxBounds + // This ensures that the expanded area is not doubled. + // because the initial maxBounds is already expanded + if (!maxBounds.contains(newBounds)) { newBounds = maxBounds; } *replaceImage = new BitmapImage(newBounds, Qt::transparent); - int maxWidth = maxBounds.width(), left = maxBounds.left(), top = maxBounds.top(); + const int maxWidth = maxBounds.width(), left = maxBounds.left(), top = maxBounds.top(); const QRect& translatedSearchBounds = newBounds.translated(-maxBounds.topLeft()); if (expandValue > 0) { expandFill(filledPixels, translatedSearchBounds, maxBounds, expandValue); } + // Fill all the found pixels for (int y = translatedSearchBounds.top(); y <= translatedSearchBounds.bottom(); y++) { for (int x = translatedSearchBounds.left(); x <= translatedSearchBounds.right(); x++) { - int index = y * maxWidth + x; + const int index = y * maxWidth + x; if (!filledPixels[index]) { continue; @@ -855,12 +857,14 @@ bool BitmapImage::floodFill(BitmapImage** replaceImage, return true; } +// Flood filling based on this scanline algorithm +// ----- http://lodev.org/cgtutor/floodfill.html bool* BitmapImage::floodFillPoints(const BitmapImage* targetImage, - const QRect& searchBounds, - const QRect& maxBounds, - QPoint point, - const int tolerance, - QRect& newBounds) + QRect searchBounds, + const QRect& maxBounds, + QPoint point, + const int tolerance, + QRect& newBounds) { QRgb oldColor = targetImage->constScanLine(point.x(), point.y()); oldColor = qRgba(qRed(oldColor), qGreen(oldColor), qBlue(oldColor), qAlpha(oldColor)); @@ -892,6 +896,12 @@ bool* BitmapImage::floodFillPoints(const BitmapImage* targetImage, int xCoord = xTemp - maxBounds.left(); int yCoord = point.y() - maxBounds.top(); + + // In case we fill outside the searchBounds, expand the search area to the max. + if (!searchBounds.contains(xCoord, yCoord)) { + searchBounds = maxBounds; + } + if (filledPixels[yCoord*maxBounds.width()+xCoord]) continue; while (xTemp >= searchBounds.left() && @@ -907,6 +917,7 @@ bool* BitmapImage::floodFillPoints(const BitmapImage* targetImage, if (!blitBounds.contains(floodPoint)) { blitBounds.extend(floodPoint); } + xCoord = xTemp - maxBounds.left(); // This pixel is what we're going to fill later filledPixels[yCoord*maxBounds.width()+xCoord] = true; @@ -959,11 +970,12 @@ void BitmapImage::expandFill(bool* fillPixels, const QRect& searchBounds, const const int maxHeight = maxBounds.height(); const int maxWidth = maxBounds.width(); + const int length = maxBounds.height() * maxBounds.width(); - int* manhattanPoints = new int[(maxBounds.height())*(maxBounds.width())]{}; + int* manhattanPoints = new int[length]{}; - /// Fill points with max length, this is important because otherwise the filled pixels will include a border of the expanded area - std::fill_n(manhattanPoints, maxBounds.height()*maxBounds.width(), searchBounds.width()+searchBounds.height()); + // Fill points with max length, this is important because otherwise the filled pixels will include a border of the expanded area + std::fill_n(manhattanPoints, length, searchBounds.width()+searchBounds.height()); for (int y = searchBounds.top(); y <= searchBounds.bottom(); y++) { diff --git a/core_lib/src/graphics/bitmap/bitmapimage.h b/core_lib/src/graphics/bitmap/bitmapimage.h index 220774c0a2..1461d7c7a1 100644 --- a/core_lib/src/graphics/bitmap/bitmapimage.h +++ b/core_lib/src/graphics/bitmap/bitmapimage.h @@ -75,9 +75,9 @@ class BitmapImage : public KeyFrame void clear(QRectF rectangle) { clear(rectangle.toRect()); } static inline bool compareColor(QRgb newColor, QRgb oldColor, int tolerance, QHash *cache); - static bool floodFill(BitmapImage** replaceImage, const BitmapImage* targetImage, const QRect& cameraRect, QPoint point, QRgb fillColor, int tolerance, int expandValue); + static bool floodFill(BitmapImage** replaceImage, const BitmapImage* targetImage, const QRect& cameraRect, const QPoint& point, const QRgb& fillColor, int tolerance, const int expandValue); static bool* floodFillPoints(const BitmapImage* targetImage, - const QRect& searchBounds, const QRect& maxBounds, + QRect searchBounds, const QRect& maxBounds, QPoint point, const int tolerance, QRect& newBounds); From a93b0cebaf5f30f9c9bb40de58eb7283b72f33a1 Mon Sep 17 00:00:00 2001 From: MrStevns Date: Fri, 8 Apr 2022 20:52:43 +0200 Subject: [PATCH 06/10] Simplify expand algorithm Taken from Scribblemaniac's branch. --- core_lib/src/graphics/bitmap/bitmapimage.cpp | 17 ++++++++--------- 1 file changed, 8 insertions(+), 9 deletions(-) diff --git a/core_lib/src/graphics/bitmap/bitmapimage.cpp b/core_lib/src/graphics/bitmap/bitmapimage.cpp index a35fc680b8..8eb00bbd62 100644 --- a/core_lib/src/graphics/bitmap/bitmapimage.cpp +++ b/core_lib/src/graphics/bitmap/bitmapimage.cpp @@ -968,7 +968,6 @@ bool* BitmapImage::floodFillPoints(const BitmapImage* targetImage, */ void BitmapImage::expandFill(bool* fillPixels, const QRect& searchBounds, const QRect& maxBounds, int expand) { - const int maxHeight = maxBounds.height(); const int maxWidth = maxBounds.width(); const int length = maxBounds.height() * maxBounds.width(); @@ -988,23 +987,23 @@ void BitmapImage::expandFill(bool* fillPixels, const QRect& searchBounds, const continue; } - if (y > 0 && y < (maxHeight - 1)) { + if (y > searchBounds.top()) { // the value will be the num of pixels away from y - 1 of the next position manhattanPoints[index] = qMin(manhattanPoints[index], manhattanPoints[(y - 1) * maxWidth+x] + 1); int distance = manhattanPoints[index]; - if (distance <= expand && distance != 0) { + if (distance <= expand) { fillPixels[index] = true; } } - if (x > 0 && x < (maxWidth - 1)) { + if (x > searchBounds.left()) { // the value will be the num of pixels away from x - 1 of the next position manhattanPoints[index] = qMin(manhattanPoints[index], manhattanPoints[y*maxWidth+(x - 1)] + 1); int distance = manhattanPoints[index]; - if (distance <= expand && distance != 0) { + if (distance <= expand) { fillPixels[index] = true; } } @@ -1018,19 +1017,19 @@ void BitmapImage::expandFill(bool* fillPixels, const QRect& searchBounds, const { const int index = y*maxWidth+x; - if (y + 1 < maxBounds.height()) { + if (y + 1 < searchBounds.bottom()) { manhattanPoints[index] = qMin(manhattanPoints[index], manhattanPoints[(y + 1)*maxWidth+x] + 1); int distance = manhattanPoints[index]; - if (distance <= expand && distance != 0) { + if (distance <= expand) { fillPixels[index] = true; } } - if (x + 1 < maxBounds.width()) { + if (x + 1 < searchBounds.right()) { manhattanPoints[index] = qMin(manhattanPoints[index], manhattanPoints[y*maxWidth+(x + 1)] + 1); int distance = manhattanPoints[index]; - if (distance <= expand && distance != 0) { + if (distance <= expand) { fillPixels[index] = true; } } From ab4b5c4670110878f444cccc4abdba3ade07e23d Mon Sep 17 00:00:00 2001 From: scribblemaniac Date: Sat, 2 Apr 2022 16:17:06 -0600 Subject: [PATCH 07/10] Use bit shift for compareColor ^2 operations This change is useless for release build as the compiler will optimize this, but for debug builds this results in a roughly 3x speed improvment. --- core_lib/src/graphics/bitmap/bitmapimage.cpp | 8 ++++---- 1 file changed, 4 insertions(+), 4 deletions(-) diff --git a/core_lib/src/graphics/bitmap/bitmapimage.cpp b/core_lib/src/graphics/bitmap/bitmapimage.cpp index 8eb00bbd62..3a3241f058 100644 --- a/core_lib/src/graphics/bitmap/bitmapimage.cpp +++ b/core_lib/src/graphics/bitmap/bitmapimage.cpp @@ -774,12 +774,12 @@ bool BitmapImage::compareColor(QRgb newColor, QRgb oldColor, int tolerance, QHas // Get Eulcidian distance between colors // Not an accurate representation of human perception, // but it's the best any image editing program ever does - int diffRed = static_cast(qPow(qRed(oldColor) - qRed(newColor), 2)); - int diffGreen = static_cast(qPow(qGreen(oldColor) - qGreen(newColor), 2)); - int diffBlue = static_cast(qPow(qBlue(oldColor) - qBlue(newColor), 2)); + int diffRed = abs(qRed(oldColor) - qRed(newColor)) << 2; + int diffGreen = abs(qGreen(oldColor) - qGreen(newColor)) << 2; + int diffBlue = abs(qBlue(oldColor) - qBlue(newColor)) << 2; // This may not be the best way to handle alpha since the other channels become less relevant as // the alpha is reduces (ex. QColor(0,0,0,0) is the same as QColor(255,255,255,0)) - int diffAlpha = static_cast(qPow(qAlpha(oldColor) - qAlpha(newColor), 2)); + int diffAlpha = abs(qAlpha(oldColor) - qAlpha(newColor)) << 2; bool isSimilar = (diffRed + diffGreen + diffBlue + diffAlpha) <= tolerance; From 8c0fabf2606285af529745e0d1c4d7d7fc58b5ce Mon Sep 17 00:00:00 2001 From: scribblemaniac Date: Tue, 12 Apr 2022 20:27:50 -0600 Subject: [PATCH 08/10] Optimize flood fill of when expanding the target image This treats everything outside the minimally bounded target image as a single region (which it is). compareColor only needs to be called once, and if it's true, then all of the transparent "border" region can be filled at once. Ideally this would be done with a rectangular fill with a mask when creating replaceImage, but unforunately that information needs to be present in filledPixels if expandFill is run. Thankfull this is pretty fast anyway. --- core_lib/src/graphics/bitmap/bitmapimage.cpp | 57 ++++++++++++++------ core_lib/src/graphics/bitmap/bitmapimage.h | 3 +- 2 files changed, 44 insertions(+), 16 deletions(-) diff --git a/core_lib/src/graphics/bitmap/bitmapimage.cpp b/core_lib/src/graphics/bitmap/bitmapimage.cpp index 3a3241f058..d72f6a5fd6 100644 --- a/core_lib/src/graphics/bitmap/bitmapimage.cpp +++ b/core_lib/src/graphics/bitmap/bitmapimage.cpp @@ -800,8 +800,10 @@ bool BitmapImage::floodFill(BitmapImage** replaceImage, int tolerance, const int expandValue) { - QRect fillBounds = targetImage->mBounds; + // Fill region must be 1 pixel larger than the target image to fill regions on the edge connected only by transparent pixels + QRect fillBounds = targetImage->mBounds.adjusted(-1, -1, 1, 1); QRect maxBounds = cameraRect.united(fillBounds).adjusted(-expandValue, -expandValue, expandValue, expandValue); + const int maxWidth = maxBounds.width(), left = maxBounds.left(), top = maxBounds.top(); // If the point we are supposed to fill is outside the max bounds, do nothing if(!maxBounds.contains(point)) @@ -813,31 +815,42 @@ bool BitmapImage::floodFill(BitmapImage** replaceImage, tolerance = static_cast(qPow(tolerance, 2)); QRect newBounds; - bool *filledPixels = floodFillPoints(targetImage, fillBounds, maxBounds, point, tolerance, newBounds); + bool shouldFillBorder = false; + bool *filledPixels = floodFillPoints(targetImage, fillBounds, maxBounds, point, tolerance, newBounds, shouldFillBorder); - const QRect& expandRect = newBounds.adjusted(-expandValue, -expandValue, expandValue, expandValue); + QRect translatedSearchBounds = newBounds.translated(-maxBounds.topLeft()); + + if (shouldFillBorder) + { + for (int y = 0; y < maxBounds.height(); y++) + { + for (int x = 0; x < maxBounds.width(); x++) + { + if(!translatedSearchBounds.contains(x, y)) + { + filledPixels[y*maxWidth+x] = true; + } + } + } + newBounds = maxBounds; + } // The scanned bounds should take the expansion into account + const QRect& expandRect = newBounds.adjusted(-expandValue, -expandValue, expandValue, expandValue); if (expandValue > 0) { newBounds = expandRect; } - - // The new bounds was smaller than the max, so set the size to maxBounds - // This ensures that the expanded area is not doubled. - // because the initial maxBounds is already expanded if (!maxBounds.contains(newBounds)) { newBounds = maxBounds; } + translatedSearchBounds = newBounds.translated(-maxBounds.topLeft()); - *replaceImage = new BitmapImage(newBounds, Qt::transparent); - - const int maxWidth = maxBounds.width(), left = maxBounds.left(), top = maxBounds.top(); - - const QRect& translatedSearchBounds = newBounds.translated(-maxBounds.topLeft()); if (expandValue > 0) { expandFill(filledPixels, translatedSearchBounds, maxBounds, expandValue); } + *replaceImage = new BitmapImage(newBounds, Qt::transparent); + // Fill all the found pixels for (int y = translatedSearchBounds.top(); y <= translatedSearchBounds.bottom(); y++) { @@ -864,10 +877,12 @@ bool* BitmapImage::floodFillPoints(const BitmapImage* targetImage, const QRect& maxBounds, QPoint point, const int tolerance, - QRect& newBounds) + QRect& newBounds, + bool& fillBorder) { QRgb oldColor = targetImage->constScanLine(point.x(), point.y()); oldColor = qRgba(qRed(oldColor), qGreen(oldColor), qBlue(oldColor), qAlpha(oldColor)); + QRect borderBounds = searchBounds.adjusted(1,1,-1,-1); // Preparations QList queue; // queue all the pixels of the filled area (as they are found) @@ -879,11 +894,20 @@ bool* BitmapImage::floodFillPoints(const BitmapImage* targetImage, bool spanLeft = false; bool spanRight = false; + if (!searchBounds.contains(point)) + { + // If point is outside the search area, move it anywhere in the 1px transparent border + point = searchBounds.topLeft(); + } + queue.append(point); // Preparations END bool *filledPixels = new bool[maxBounds.height()*maxBounds.width()]{}; + // True if the algorithm has attempted to fill a pixel outside the search bounds + bool checkOutside = false; + BlitRect blitBounds(point); while (!queue.empty()) { @@ -898,8 +922,8 @@ bool* BitmapImage::floodFillPoints(const BitmapImage* targetImage, int yCoord = point.y() - maxBounds.top(); // In case we fill outside the searchBounds, expand the search area to the max. - if (!searchBounds.contains(xCoord, yCoord)) { - searchBounds = maxBounds; + if (!borderBounds.contains(point)) { + checkOutside = true; } if (filledPixels[yCoord*maxBounds.width()+xCoord]) continue; @@ -947,7 +971,10 @@ bool* BitmapImage::floodFillPoints(const BitmapImage* targetImage, } } + fillBorder = checkOutside && compareColor(Qt::transparent, oldColor, tolerance, cache.data()); + newBounds = blitBounds; + return filledPixels; } diff --git a/core_lib/src/graphics/bitmap/bitmapimage.h b/core_lib/src/graphics/bitmap/bitmapimage.h index 1461d7c7a1..5c859fd75a 100644 --- a/core_lib/src/graphics/bitmap/bitmapimage.h +++ b/core_lib/src/graphics/bitmap/bitmapimage.h @@ -80,7 +80,8 @@ class BitmapImage : public KeyFrame QRect searchBounds, const QRect& maxBounds, QPoint point, const int tolerance, - QRect& newBounds); + QRect& newBounds, + bool &fillBorder); static void expandFill(bool* fillPixels, const QRect& searchBounds, const QRect& maxBounds, int expand); void drawLine(QPointF P1, QPointF P2, QPen pen, QPainter::CompositionMode cm, bool antialiasing); From f4b352c8092f3612e7a97caa376fd4e26f37214e Mon Sep 17 00:00:00 2001 From: MrStevns Date: Wed, 13 Apr 2022 12:32:56 +0200 Subject: [PATCH 09/10] Fix tests Issue 1. The maxBounds shouldn't use the fillBounds, because it has an extra pixel boundary, instead it should be based on the targetImage bounds. Issue 2. Qt::GlobalColors and QRgb are not interchangeable, one can't compare Qt::Transparent against 0. --- core_lib/src/graphics/bitmap/bitmapimage.cpp | 7 ++++--- 1 file changed, 4 insertions(+), 3 deletions(-) diff --git a/core_lib/src/graphics/bitmap/bitmapimage.cpp b/core_lib/src/graphics/bitmap/bitmapimage.cpp index d72f6a5fd6..39a2832c57 100644 --- a/core_lib/src/graphics/bitmap/bitmapimage.cpp +++ b/core_lib/src/graphics/bitmap/bitmapimage.cpp @@ -801,8 +801,9 @@ bool BitmapImage::floodFill(BitmapImage** replaceImage, const int expandValue) { // Fill region must be 1 pixel larger than the target image to fill regions on the edge connected only by transparent pixels - QRect fillBounds = targetImage->mBounds.adjusted(-1, -1, 1, 1); - QRect maxBounds = cameraRect.united(fillBounds).adjusted(-expandValue, -expandValue, expandValue, expandValue); + const QRect& imageBounds = targetImage->mBounds; + QRect fillBounds = imageBounds.adjusted(-1, -1, 1, 1); + QRect maxBounds = cameraRect.united(imageBounds).adjusted(-expandValue, -expandValue, expandValue, expandValue); const int maxWidth = maxBounds.width(), left = maxBounds.left(), top = maxBounds.top(); // If the point we are supposed to fill is outside the max bounds, do nothing @@ -971,7 +972,7 @@ bool* BitmapImage::floodFillPoints(const BitmapImage* targetImage, } } - fillBorder = checkOutside && compareColor(Qt::transparent, oldColor, tolerance, cache.data()); + fillBorder = checkOutside && compareColor(qRgba(0,0,0,0), oldColor, tolerance, cache.data()); newBounds = blitBounds; From bdbea969b03a11785225f8a74c29802ad006e97f Mon Sep 17 00:00:00 2001 From: scribblemaniac Date: Wed, 13 Apr 2022 15:26:46 -0600 Subject: [PATCH 10/10] Fix memory error if targetImage->mBounds > maxBounds --- core_lib/src/graphics/bitmap/bitmapimage.cpp | 8 ++++---- 1 file changed, 4 insertions(+), 4 deletions(-) diff --git a/core_lib/src/graphics/bitmap/bitmapimage.cpp b/core_lib/src/graphics/bitmap/bitmapimage.cpp index 39a2832c57..5c5a9749a5 100644 --- a/core_lib/src/graphics/bitmap/bitmapimage.cpp +++ b/core_lib/src/graphics/bitmap/bitmapimage.cpp @@ -801,9 +801,8 @@ bool BitmapImage::floodFill(BitmapImage** replaceImage, const int expandValue) { // Fill region must be 1 pixel larger than the target image to fill regions on the edge connected only by transparent pixels - const QRect& imageBounds = targetImage->mBounds; - QRect fillBounds = imageBounds.adjusted(-1, -1, 1, 1); - QRect maxBounds = cameraRect.united(imageBounds).adjusted(-expandValue, -expandValue, expandValue, expandValue); + const QRect& fillBounds = targetImage->mBounds; + QRect maxBounds = cameraRect.united(fillBounds).adjusted(-expandValue, -expandValue, expandValue, expandValue); const int maxWidth = maxBounds.width(), left = maxBounds.left(), top = maxBounds.top(); // If the point we are supposed to fill is outside the max bounds, do nothing @@ -883,7 +882,8 @@ bool* BitmapImage::floodFillPoints(const BitmapImage* targetImage, { QRgb oldColor = targetImage->constScanLine(point.x(), point.y()); oldColor = qRgba(qRed(oldColor), qGreen(oldColor), qBlue(oldColor), qAlpha(oldColor)); - QRect borderBounds = searchBounds.adjusted(1,1,-1,-1); + QRect borderBounds = searchBounds.intersected(maxBounds); + searchBounds = searchBounds.adjusted(-1, -1, 1, 1).intersected(maxBounds); // Preparations QList queue; // queue all the pixels of the filled area (as they are found)