File indexing completed on 2024-06-16 04:16:49

0001 /*
0002  * KDE. Krita Project.
0003  *
0004  * SPDX-FileCopyrightText: 2021 Deif Lou <ginoba@gmail.com>
0005  *
0006  * SPDX-License-Identifier: GPL-2.0-or-later
0007  */
0008 
0009 #include <algorithm>
0010 #include <limits>
0011 #include <cmath>
0012 
0013 #include "KisScreentoneScreentoneFunctions.h"
0014 #include "KisScreentoneGeneratorTemplate.h"
0015 
0016 KisScreentoneGeneratorTemplate::KisScreentoneGeneratorTemplate(const KisScreentoneGeneratorConfigurationSP config)
0017 {
0018     const int pattern = config->pattern();
0019     const int shape = config->shape();
0020     const int interpolation = config->interpolation();
0021 
0022     if (pattern == KisScreentonePatternType_Dots) {
0023         if (shape == KisScreentoneShapeType_RoundDots) {
0024             if (interpolation == KisScreentoneInterpolationType_Linear) {
0025                 KisScreentoneScreentoneFunctions::DotsRoundLinear screentoneFunction;
0026                 makeTemplate(config, screentoneFunction);
0027             } else if (interpolation == KisScreentoneInterpolationType_Sinusoidal) {
0028                 KisScreentoneScreentoneFunctions::DotsRoundSinusoidal screentoneFunction;
0029                 makeTemplate(config, screentoneFunction);
0030             }
0031         } else if (shape == KisScreentoneShapeType_EllipseDotsLegacy) {
0032             if (interpolation == KisScreentoneInterpolationType_Linear) {
0033                 KisScreentoneScreentoneFunctions::DotsEllipseLinear_Legacy screentoneFunction;
0034                 makeTemplate(config, screentoneFunction);
0035             } else if (interpolation == KisScreentoneInterpolationType_Sinusoidal) {
0036                 KisScreentoneScreentoneFunctions::DotsEllipseSinusoidal_Legacy screentoneFunction;
0037                 makeTemplate(config, screentoneFunction);
0038             }
0039         } else if (shape == KisScreentoneShapeType_EllipseDots) {
0040             if (interpolation == KisScreentoneInterpolationType_Linear) {
0041                 KisScreentoneScreentoneFunctions::DotsEllipseLinear screentoneFunction;
0042                 makeTemplate(config, screentoneFunction);
0043             } else if (interpolation == KisScreentoneInterpolationType_Sinusoidal) {
0044                 KisScreentoneScreentoneFunctions::DotsEllipseSinusoidal screentoneFunction;
0045                 makeTemplate(config, screentoneFunction);
0046             }
0047         } else if (shape == KisScreentoneShapeType_DiamondDots) {
0048             KisScreentoneScreentoneFunctions::DotsDiamond screentoneFunction;
0049             makeTemplate(config, screentoneFunction);
0050         } else if (shape == KisScreentoneShapeType_SquareDots) {
0051             KisScreentoneScreentoneFunctions::DotsSquare screentoneFunction;
0052             makeTemplate(config, screentoneFunction);
0053         }
0054     } else if (pattern == KisScreentonePatternType_Lines) {
0055         if (shape == KisScreentoneShapeType_StraightLines) {
0056             if (interpolation == KisScreentoneInterpolationType_Linear) {
0057                 KisScreentoneScreentoneFunctions::LinesStraightLinear screentoneFunction;
0058                 makeTemplate(config, screentoneFunction);
0059             } else if (interpolation == KisScreentoneInterpolationType_Sinusoidal) {
0060                 KisScreentoneScreentoneFunctions::LinesStraightSinusoidal screentoneFunction;
0061                 makeTemplate(config, screentoneFunction);
0062             }
0063         } else if (shape == KisScreentoneShapeType_SineWaveLines) {
0064             if (interpolation == KisScreentoneInterpolationType_Linear) {
0065                 KisScreentoneScreentoneFunctions::LinesSineWaveLinear screentoneFunction;
0066                 makeTemplate(config, screentoneFunction);
0067             } else if (interpolation == KisScreentoneInterpolationType_Sinusoidal) {
0068                 KisScreentoneScreentoneFunctions::LinesSineWaveSinusoidal screentoneFunction;
0069                 makeTemplate(config, screentoneFunction);
0070             }
0071         } else if (shape == KisScreentoneShapeType_TriangularWaveLines) {
0072             if (interpolation == KisScreentoneInterpolationType_Linear) {
0073                 KisScreentoneScreentoneFunctions::LinesTriangularWaveLinear screentoneFunction;
0074                 makeTemplate(config, screentoneFunction);
0075             } else if (interpolation == KisScreentoneInterpolationType_Sinusoidal) {
0076                 KisScreentoneScreentoneFunctions::LinesTriangularWaveSinusoidal screentoneFunction;
0077                 makeTemplate(config, screentoneFunction);
0078             }
0079         } else if (shape == KisScreentoneShapeType_SawtoothWaveLines) {
0080             if (interpolation == KisScreentoneInterpolationType_Linear) {
0081                 KisScreentoneScreentoneFunctions::LinesSawToothWaveLinear screentoneFunction;
0082                 makeTemplate(config, screentoneFunction);
0083             } else if (interpolation == KisScreentoneInterpolationType_Sinusoidal) {
0084                 KisScreentoneScreentoneFunctions::LinesSawToothWaveSinusoidal screentoneFunction;
0085                 makeTemplate(config, screentoneFunction);
0086             }
0087         } else if (shape == KisScreentoneShapeType_CurtainsLines) {
0088             if (interpolation == KisScreentoneInterpolationType_Linear) {
0089                 KisScreentoneScreentoneFunctions::LinesCurtainsLinear screentoneFunction;
0090                 makeTemplate(config, screentoneFunction);
0091             } else if (interpolation == KisScreentoneInterpolationType_Sinusoidal) {
0092                 KisScreentoneScreentoneFunctions::LinesCurtainsSinusoidal screentoneFunction;
0093                 makeTemplate(config, screentoneFunction);
0094             }
0095         }
0096     }
0097 }
0098 
0099 // The following utility classes are used to get the preferred order in which
0100 // the pixels of a cell should be "turn on" based on the distance to the center
0101 // of the shape (center of the dot, center of the line, etc.). For simplicity
0102 // they just use the screentone function "as is" except for the round/ellipse
0103 // dot sinusoidal, which use the linear counterpart (to get an ordering that
0104 // seems to grow radially)
0105 template <typename ScreentoneFunction>
0106 struct LightUpOrderingFunction : public ScreentoneFunction
0107 {};
0108 template <>
0109 struct LightUpOrderingFunction<KisScreentoneScreentoneFunctions::DotsRoundSinusoidal>
0110     : public KisScreentoneScreentoneFunctions::DotsRoundLinear
0111 {};
0112 template <>
0113 struct LightUpOrderingFunction<KisScreentoneScreentoneFunctions::DotsEllipseSinusoidal>
0114     : public KisScreentoneScreentoneFunctions::DotsEllipseLinear
0115 {};
0116 
0117 template <typename ScreentoneFunction>
0118 void KisScreentoneGeneratorTemplate::makeTemplate(const KisScreentoneGeneratorConfigurationSP config,
0119                                                   ScreentoneFunction screentoneFunction)
0120 {
0121     // NOTE: In the following, the word "screen" is used to mean the dot screen
0122     // of the screentone (the grid of dots/cells)
0123 
0124     // Get transformation parameters
0125     qreal sizeX, sizeY;
0126     const int alignX = config->alignToPixelGrid() ? config->alignToPixelGridX() : 1;
0127     const int alignY = config->alignToPixelGrid() ? config->alignToPixelGridY() : 1;
0128     if (config->sizeMode() == KisScreentoneSizeMode_PixelBased) {
0129         const bool constrainSize = config->constrainSize();
0130         sizeX = config->sizeX();
0131         // Ensure that the size y component is equal to the x component
0132         // if keepSizeSquare is true
0133         sizeY = constrainSize ? sizeX : config->sizeY();
0134     } else {
0135         const qreal resolution = config->resolution();
0136         const bool constrainFrequency = config->constrainFrequency();
0137         const qreal frequencyX = config->frequencyX();
0138         // Ensure that the frequency y component is equal to the x component
0139         // if constrainFrequency is true
0140         const qreal frequencyY = constrainFrequency ? frequencyX : config->frequencyY();
0141         sizeX = qMax(1.0, resolution / frequencyX);
0142         sizeY = qMax(1.0, resolution / frequencyY);
0143     }
0144     const qreal positionX = config->alignToPixelGrid() ? qRound(config->positionX()) : config->positionX();
0145     const qreal positionY = config->alignToPixelGrid() ? qRound(config->positionY()) : config->positionY();
0146     m_screenPosition = QPointF(positionX, positionY);
0147     const qreal shearX = config->shearX();
0148     const qreal shearY = config->shearY();
0149     const qreal rotation = config->rotation();
0150     // Construct image<->screen transforms
0151     m_imageToScreenTransform.shear(shearX, shearY);
0152     m_imageToScreenTransform.scale(qFuzzyIsNull(sizeX) ? 0.0 : 1.0 / sizeX, qFuzzyIsNull(sizeY) ? 0.0 : 1.0 / sizeY);
0153     m_imageToScreenTransform.rotate(rotation);
0154     m_imageToScreenTransform.translate(positionX, positionY);
0155     QTransform screenToImage;
0156     screenToImage.rotate(-rotation);
0157     screenToImage.scale(sizeX, sizeY);
0158     screenToImage.shear(-shearX, -shearY);
0159     // u1 is the unaligned vector that goes from the origin to the top-right
0160     // corner of the macrocell. v1 is the aligned version
0161     // u2 is the unaligned vector that goes from the origin to the bottom-left
0162     // corner of the macrocell. v2 is the aligned version.
0163     // At this point we assume the macrocell will have a minimum size given by
0164     // the alignment
0165     const QPointF u1 = screenToImage.map(QPointF(static_cast<qreal>(alignX), 0.0));
0166     const QPointF u2 = screenToImage.map(QPointF(0.0, static_cast<qreal>(alignY)));
0167     QPointF v1(qRound(u1.x()), qRound(u1.y()));
0168     QPointF v2(qRound(u2.x()), qRound(u2.y()));
0169     // If the following condition is met, that means that the screen is
0170     // transformed in such a way that the cell corners are colinear so we move
0171     // v1 or v2 to a neighbor position and give the cell some area
0172     if (qFuzzyCompare(v1.y() * v2.x(), v2.y() * v1.x()) &&
0173         !qFuzzyIsNull(v1.x() * v2.x() + v1.y() * v2.y())) {
0174         // Choose point to move based on distance from non aligned point to
0175         // aligned point
0176         const qreal dist1 = kisSquareDistance(u1, v1);
0177         const qreal dist2 = kisSquareDistance(u2, v2);
0178         const QPointF *p_u = dist1 > dist2 ? &u1 : &u2;
0179         QPointF *p_v = dist1 > dist2 ? &v1 : &v2;
0180         // Then we get the closest pixel aligned point to the current, colinear,
0181         // point
0182         QPair<int, qreal> dists[4]{
0183             {1, kisSquareDistance(*p_u, *p_v + QPointF(0.0, -1.0))},
0184             {2, kisSquareDistance(*p_u, *p_v + QPointF(1.0, 0.0))},
0185             {3, kisSquareDistance(*p_u, *p_v + QPointF(0.0, 1.0))},
0186             {4, kisSquareDistance(*p_u, *p_v + QPointF(-1.0, 0.0))}
0187         };
0188         std::sort(
0189             std::begin(dists), std::end(dists),
0190             [](const QPair<int, qreal> &a, const QPair<int, qreal> &b)
0191             {
0192                 return a.second < b.second;
0193             }
0194         );
0195         // Move the point
0196         if (dists[0].first == 1) {
0197             p_v->setY(p_v->y() - 1.0);
0198         } else if (dists[0].first == 2) {
0199             p_v->setX(p_v->x() + 1.0);
0200         } else if (dists[0].first == 3) {
0201             p_v->setY(p_v->y() + 1.0);
0202         } else {
0203             p_v->setX(p_v->x() - 1.0);
0204         }
0205     }
0206     qreal v1Length = std::sqrt(v1.x() * v1.x() + v1.y() * v1.y());
0207     qreal v2Length = std::sqrt(v2.x() * v2.x() + v2.y() * v2.y());
0208     // The macrocell will have a minimum size derived from the alignment but if
0209     // its size doesn't contain enough pixels to cover all the range of
0210     // intensities we expand it.
0211     QSize macrocellTiles(1, 1);
0212     while (macrocellTiles.width() * v1Length * macrocellTiles.height() * v2Length < 256) {
0213         if (macrocellTiles.width() * v1Length > macrocellTiles.height() * v2Length) {
0214             macrocellTiles.setHeight(macrocellTiles.height() + 1);
0215         } else {
0216             macrocellTiles.setWidth(macrocellTiles.width() + 1);
0217         }
0218     }
0219     // Get size in cells of the macrocell
0220     m_macrocellSize = QSize(alignX * macrocellTiles.width(), alignY * macrocellTiles.height());
0221     const QSizeF macrocellSizeF = m_macrocellSize;
0222     // Scale the top and left vectors and lengths to the final macrocell size
0223     v1 *= macrocellTiles.width();
0224     v2 *= macrocellTiles.height();
0225     v1Length *= macrocellTiles.width();
0226     v2Length *= macrocellTiles.height();
0227     // Compute other useful quantities
0228     const QPointF v3 = v1 + v2;
0229     const QPointF l1 = v1;
0230     const QPointF l2 = v2;
0231     const QPointF l3 = -v1;
0232     const QPointF l4 = -v2;
0233     const qreal v1MicrocellLength = v1Length / macrocellSizeF.width();
0234     const qreal v2MicrocellLength = v2Length / macrocellSizeF.height();
0235     m_v1 = v1;
0236     m_v2 = v2;
0237     // Construct template<->screen transforms
0238     const QPolygonF quad(
0239         {
0240             QPointF(0.0, 0.0),
0241             v1 / macrocellSizeF.width(),
0242             v1 / macrocellSizeF.width() + v2 / macrocellSizeF.height(),
0243             v2 / macrocellSizeF.height()
0244         }
0245     );
0246     QTransform::quadToSquare(quad, m_templateToScreenTransform);
0247     m_screenToTemplateTransform = m_templateToScreenTransform.inverted();
0248 
0249     // Construct the template
0250 
0251     // Compute template dimensions
0252     const QPoint topLeft(
0253         static_cast<int>(qMin(0.0, qMin(v1.x(), qMin(v2.x(), v1.x() + v2.x())))),
0254         static_cast<int>(qMin(0.0, qMin(v1.y(), qMin(v2.y(), v1.y() + v2.y()))))
0255     );
0256     const QPoint bottomRight(
0257         static_cast<int>(qMax(0.0, qMax(v1.x(), qMax(v2.x(), v1.x() + v2.x())))),
0258         static_cast<int>(qMax(0.0, qMax(v1.y(), qMax(v2.y(), v1.y() + v2.y()))))
0259     );
0260     // Add an 1 pixel border around the template, useful for bilinear interpolation
0261     m_templateSize = QSize(bottomRight.x() - topLeft.x() + 2, bottomRight.y() - topLeft.y() + 2);
0262     m_originOffset = -topLeft + QPoint(1, 1);
0263 
0264     m_templateData = QVector<qreal>(m_templateSize.width() * m_templateSize.height(), -1.0);
0265 
0266     // Convenience struct to store some info for a single pixel during the
0267     // construction of the template
0268     struct AuxiliaryPoint
0269     {
0270         // Pixel index with respect to the template image
0271         int templatePixelIndex;
0272         // An pseudo index that orders the pixel with respect to a cell from
0273         // top-left to bottom right
0274         qreal microcellPixelIndex;
0275         // Spot function value at the top-left corner of the pixel
0276         qreal valueAtCorner;
0277         // Spot function value at the center of the pixel
0278         qreal valueAtCenter;
0279         // Distance from the "center" of the shape to the top-left corner of the
0280         // pixel
0281         qreal distanceToCorner;
0282         // Distance from the "center" of the shape to the center of the pixel
0283         qreal distanceToCenter;
0284     };
0285     // Convenience struct to store some info for a single microcell during the
0286     // construction of the template
0287     struct AuxiliaryMicrocell
0288     {
0289         // The order in which this cell should light up pixels with respect to
0290         // the other cells
0291         int index;
0292         // List of points in this cell
0293         QVector<AuxiliaryPoint> auxiliaryPoints;
0294     };
0295 
0296     QVector<AuxiliaryMicrocell> auxiliaryMicrocells(m_macrocellSize.width() * m_macrocellSize.height());
0297 
0298     // Set the ordered index for each auxiliary microcell
0299     // Use makeCellOrderList to shuffle the microcell activation order so that
0300     // they follow bayer matrix like patters. This allows to grow the
0301     // microcells in a way that they don't visually cluster
0302     QVector<int> microcellIndices = makeCellOrderList(m_macrocellSize.width(), m_macrocellSize.height());
0303     for (int i = 0; i < auxiliaryMicrocells.size(); ++i) {
0304         auxiliaryMicrocells[i].index = microcellIndices[i];
0305     }
0306 
0307     // "Rasterize" the macrocell: get all the points of the template that lie
0308     // inside the macrocell and store them as auxiliary points that contain
0309     // some info useful for sorting later.
0310     // The template will have a representation of the complete transformed
0311     // macrocell, but also some other areas outside (parts of adjacent
0312     // macrocells) if, for example, the screen is rotated. To get later a value
0313     // from the template we only use the pixels inside the macrocell, but the
0314     // pixels outside are useful to perform bilinear interpolation
0315 
0316     // Get the horizontal and vertical points at cell corners
0317     QVector<QPointF> horizontalCellPositions;
0318     for (int i = -1; i <= m_macrocellSize.width() + 1; ++i) {
0319         horizontalCellPositions.append(v1 / static_cast<qreal>(m_macrocellSize.width()) * static_cast<qreal>(i));
0320     }
0321     QVector<QPointF> verticalCellPositions;
0322     for (int i = -1; i <= m_macrocellSize.height() + 1; ++i) {
0323         verticalCellPositions.append(v2 / static_cast<qreal>(m_macrocellSize.height()) * static_cast<qreal>(i));
0324     }
0325 
0326     int totalNumberOfAuxiliaryPoints = 0;
0327 
0328     // Convenience function that tells if a pixel should belong to the left or
0329     // to the right side of an edge. Used only when the point lies exactly in
0330     // the edge
0331     auto pointBelongsToLeftSideOfEdge = [](const QPointF &point, const QPointF &edgeStart, const QPointF &edgeDirection) -> bool
0332     {
0333         const qreal r = (point.x() - edgeStart.x()) * edgeDirection.y() - (point.y() - edgeStart.y()) * edgeDirection.x();
0334         return (r == 0.0) && ((edgeDirection.y() == 0.0 && edgeDirection.x() > 0.0) || (edgeDirection.y() > 0.0));
0335     };
0336 
0337     // This is used to get an estimate of how far a given point is from the
0338     // "center" of the shape (center of dot, center of line, etc.)
0339     LightUpOrderingFunction<ScreentoneFunction> lightUpOrderingFunction;
0340 
0341     // Visit all the pixels on the template and add an auxiliary point for each
0342     // one that falls inside the macrocell
0343     for (int i = 0; i < m_templateData.size(); ++i) {
0344         // Transform the pixel position from template to screen coordinates.
0345         // We transform both the point at the pixel corner (used for sampling
0346         // the screentone function) and the point at pixel center (used to
0347         // compute to which cell the pixel belongs)
0348         const int templateY = i / m_templateSize.width();
0349         const int templateX = i - m_templateSize.width() * templateY;
0350         const QPointF pixelCornerPoint(
0351             static_cast<qreal>(templateX - m_originOffset.x()),
0352             static_cast<qreal>(templateY - m_originOffset.y())
0353         );
0354         const QPointF pixelCenterPoint(pixelCornerPoint + QPointF(0.5, 0.5));
0355         const QPointF pixelCenterScreenPoint = m_templateToScreenTransform.map(pixelCenterPoint);
0356         const QPointF macrocellPos(pixelCenterScreenPoint.x() * v1MicrocellLength, pixelCenterScreenPoint.y() * v2MicrocellLength);
0357         // Initial estimate for the microcell position
0358         int microcellX = static_cast<int>(std::floor(macrocellPos.x() * static_cast<qreal>(m_macrocellSize.width()) / v1Length));
0359         int microcellY = static_cast<int>(std::floor(macrocellPos.y() * static_cast<qreal>(m_macrocellSize.height()) / v2Length));
0360         // Discard this pixel if it is clearly outside the macrocell
0361         if (microcellX < -1 || microcellX > m_macrocellSize.width() ||
0362             microcellY < -1 || microcellY > m_macrocellSize.height()) {
0363             continue;
0364         }
0365         // If the pixel center lies exactly in a border between cells we must
0366         // decide if it should belong to a neighbor cell. This is an usual
0367         // problem in rasterization. Here we treat the pixel as if it belonged
0368         const QPointF topLeftCorner(horizontalCellPositions[microcellX + 1] + verticalCellPositions[microcellY + 1]);
0369         const QPointF topRightCorner(horizontalCellPositions[microcellX + 1 + 1] + verticalCellPositions[microcellY + 1]);
0370         const QPointF bottomRightCorner(horizontalCellPositions[microcellX + 1 + 1] + verticalCellPositions[microcellY + 1 + 1]);
0371         const QPointF bottomLeftCorner(horizontalCellPositions[microcellX + 1] + verticalCellPositions[microcellY + 1 + 1]);
0372         if (pointBelongsToLeftSideOfEdge(pixelCenterPoint, topLeftCorner, l1)) {
0373             --microcellY;
0374         }
0375         if (pointBelongsToLeftSideOfEdge(pixelCenterPoint, topRightCorner, l2)) {
0376             ++microcellX;
0377         }
0378         if (pointBelongsToLeftSideOfEdge(pixelCenterPoint, bottomRightCorner, l3)) {
0379             ++microcellY;
0380         }
0381         if (pointBelongsToLeftSideOfEdge(pixelCenterPoint, bottomLeftCorner, l4)) {
0382             --microcellX;
0383         }
0384         // Discard the pixel since the modified microcell position is for a cell
0385         // that belongs to another macrocell
0386         if (microcellX < 0 || microcellX >= m_macrocellSize.width() ||
0387             microcellY < 0 || microcellY >= m_macrocellSize.height()) {
0388             continue;
0389         }
0390         // Add the pixel to the auxiliary points collection
0391         const int microcellIndex = microcellY * m_macrocellSize.width() + microcellX;
0392         const qreal microcellPixelIndexX = macrocellPos.x() - static_cast<qreal>(microcellX) * v1MicrocellLength;
0393         const qreal microcellPixelIndexY = macrocellPos.y() - static_cast<qreal>(microcellY) * v2MicrocellLength;
0394         const qreal microcellPixelIndex = microcellPixelIndexY * v1MicrocellLength + microcellPixelIndexX;
0395         const QPointF pixelCornerScreenPoint = m_templateToScreenTransform.map(pixelCornerPoint);
0396         auxiliaryMicrocells[microcellIndex].auxiliaryPoints.push_back(
0397             {
0398                 i,
0399                 microcellPixelIndex,
0400                 screentoneFunction(pixelCornerScreenPoint.x(), pixelCornerScreenPoint.y()),
0401                 screentoneFunction(pixelCenterScreenPoint.x(), pixelCenterScreenPoint.y()),
0402                 lightUpOrderingFunction(pixelCornerScreenPoint.x(), pixelCornerScreenPoint.y()),
0403                 lightUpOrderingFunction(pixelCenterScreenPoint.x(), pixelCenterScreenPoint.y()),
0404             }
0405         );
0406         ++totalNumberOfAuxiliaryPoints;
0407     }
0408 
0409     // Sort the auxiliary points of each auxiliary microcell with respect to
0410     // different criteria
0411     for (int i = 0; i < auxiliaryMicrocells.size(); ++i) {
0412         std::sort(auxiliaryMicrocells[i].auxiliaryPoints.begin(), auxiliaryMicrocells[i].auxiliaryPoints.end(),
0413             [](const AuxiliaryPoint &a, const AuxiliaryPoint &b) {
0414                 if (qFuzzyCompare(a.valueAtCorner, b.valueAtCorner)) {
0415                     if (qFuzzyCompare(a.valueAtCenter, b.valueAtCenter)) {
0416                         if (qFuzzyCompare(a.distanceToCenter, b.distanceToCenter)) {
0417                             if (qFuzzyCompare(a.distanceToCorner, b.distanceToCorner)) {
0418                                 return a.microcellPixelIndex < b.microcellPixelIndex;
0419                             }
0420                             return a.distanceToCorner < b.distanceToCorner;
0421                         }
0422                         return a.distanceToCenter < b.distanceToCenter;
0423                     }
0424                     return a.valueAtCenter < b.valueAtCenter;
0425                 }
0426                 return a.valueAtCorner < b.valueAtCorner;
0427             }
0428         );
0429     }
0430 
0431     // Sort the auxiliary microcells themselves
0432     std::sort(auxiliaryMicrocells.begin(), auxiliaryMicrocells.end(),
0433         [](const AuxiliaryMicrocell &a, const AuxiliaryMicrocell &b) {
0434             return a.index < b.index;
0435         }
0436     );
0437 
0438     // Fill the template pixels inside the macrocell with the sorted auxiliary
0439     // points
0440     {
0441         int macrocellPixelIndex = 0;
0442         QVector<int> microcellPixelIndices(auxiliaryMicrocells.size());
0443         while (macrocellPixelIndex < totalNumberOfAuxiliaryPoints) {
0444             for (int i = 0; i < auxiliaryMicrocells.size(); ++i) {
0445                 if (microcellPixelIndices[i] == auxiliaryMicrocells[i].auxiliaryPoints.size()) {
0446                     continue;
0447                 }
0448                 m_templateData[auxiliaryMicrocells[i].auxiliaryPoints[microcellPixelIndices[i]].templatePixelIndex] =
0449                     totalNumberOfAuxiliaryPoints - 1 == 0 ? 0 // to avoid UB from division by zero
0450                                                           : static_cast<qreal>(macrocellPixelIndex) / static_cast<qreal>(totalNumberOfAuxiliaryPoints - 1);
0451                 ++microcellPixelIndices[i];
0452                 ++macrocellPixelIndex;
0453             }
0454         }
0455     }
0456 
0457     // Fill the rest of the template pixels by copying the values from the
0458     // already set ones
0459     for (int i = 0; i < m_templateData.size(); ++i) {
0460         if (m_templateData[i] < 0.0) {
0461             int templateY = i / m_templateSize.width();
0462             int templateX = i - m_templateSize.width() * templateY;
0463             QPointF pixelCenterPoint(
0464                 static_cast<qreal>(templateX - m_originOffset.x()) + 0.5,
0465                 static_cast<qreal>(templateY - m_originOffset.y()) + 0.5
0466             );
0467             const QPointF pixelCenterScreenPoint = m_templateToScreenTransform.map(pixelCenterPoint);
0468             const qreal a = -std::floor(pixelCenterScreenPoint.x() / macrocellSizeF.width());
0469             const qreal b = -std::floor(pixelCenterScreenPoint.y() / macrocellSizeF.height());
0470             pixelCenterPoint += QPointF(a * v1.x() + b * v2.x(), a * v1.y() + b * v2.y());
0471 
0472             int x = static_cast<int>(std::floor(pixelCenterPoint.x())) + m_originOffset.x();
0473             int y = static_cast<int>(std::floor(pixelCenterPoint.y())) + m_originOffset.y();
0474             int macrocellPointIndex = y * m_templateSize.width() + x;
0475 
0476             // if for some reason the target reference pixel is not set, we try
0477             // find another one just by wrapping around the macrocell
0478             if (m_templateData[macrocellPointIndex] < 0.0) {
0479                 if (pointBelongsToLeftSideOfEdge(pixelCenterPoint, QPointF(0.0, 0.0), l1)) {
0480                     pixelCenterPoint += v2;
0481                 }
0482                 if (pointBelongsToLeftSideOfEdge(pixelCenterPoint, v1, l2)) {
0483                     pixelCenterPoint -= v1;
0484                 }
0485                 if (pointBelongsToLeftSideOfEdge(pixelCenterPoint, v3, l3)) {
0486                     pixelCenterPoint -= v2;
0487                 }
0488                 if (pointBelongsToLeftSideOfEdge(pixelCenterPoint, v2, l4)) {
0489                     pixelCenterPoint += v1;
0490                 }
0491                 templateX = static_cast<int>(std::floor(pixelCenterPoint.x())) + m_originOffset.x();
0492                 templateY = static_cast<int>(std::floor(pixelCenterPoint.y())) + m_originOffset.y();
0493                 macrocellPointIndex = templateY * m_templateSize.width() + templateX;
0494             }
0495 
0496             m_templateData[i] = m_templateData[macrocellPointIndex];
0497         }
0498     }
0499 }
0500 
0501 QVector<int> KisScreentoneGeneratorTemplate::makeCellOrderList(int macrocellColumns, int macrocellRows) const
0502 {
0503     if (macrocellColumns == 1 && macrocellRows == 1) {
0504         return {0};
0505     }
0506 
0507     struct Candidate
0508     {
0509         int availableCellIndex;
0510         int index;
0511         int distanceSquared;
0512         int averageDistance;
0513     };
0514 
0515     const int numberOfCells = macrocellColumns * macrocellRows;
0516     QVector<int> processedCells;
0517     QVector<int> availableCells;
0518 
0519     // Insert the cell with index 0 in the first position
0520     processedCells.push_back(0);
0521     for (int i = 1; i < numberOfCells; ++i) {
0522         availableCells.push_back(i);
0523     }
0524 
0525     while (availableCells.size() > 0) {
0526         QVector<Candidate> candidates;
0527         for (int i = 0; i < availableCells.size(); ++i) {
0528             const int availableCellY = availableCells[i] / macrocellColumns;
0529             const int availableCellX = availableCells[i] - availableCellY * macrocellColumns;
0530             int averageDistanceToProcessedCells = 0;
0531             int minimumDistanceToProcessedCells = std::numeric_limits<int>::max();
0532             for (int j = 0; j < processedCells.size(); ++j) {
0533                 const int processedCellY = processedCells[j] / macrocellColumns;
0534                 const int processedCellX = processedCells[j] - processedCellY * macrocellColumns;
0535 
0536                 int distanceToCurrentProcessedCell = std::numeric_limits<int>::max();
0537                 for (int y = -1; y < 2; ++y) {
0538                     for (int x = -1; x < 2; ++x) {
0539                         const int xx = processedCellX + macrocellColumns * x;
0540                         const int yy = processedCellY + macrocellRows * y;
0541                         const int deltaX = availableCellX - xx;
0542                         const int deltaY = availableCellY - yy;
0543                         const int distanceSquared = deltaX * deltaX + deltaY * deltaY;
0544                         if (distanceSquared < distanceToCurrentProcessedCell) {
0545                             distanceToCurrentProcessedCell = distanceSquared;
0546                         }
0547                     }
0548                 }
0549                 if (distanceToCurrentProcessedCell < minimumDistanceToProcessedCells) {
0550                     minimumDistanceToProcessedCells = distanceToCurrentProcessedCell;
0551                 }
0552                 averageDistanceToProcessedCells += distanceToCurrentProcessedCell;
0553             }
0554             candidates.push_back({i, availableCells[i], minimumDistanceToProcessedCells, averageDistanceToProcessedCells});
0555         }
0556 
0557         // Find the best candidate
0558         int bestCandidateIndex = 0;
0559         for (int i = 0; i < candidates.size(); ++i) {
0560             if (candidates[i].distanceSquared > candidates[bestCandidateIndex].distanceSquared ||
0561                 (candidates[i].distanceSquared == candidates[bestCandidateIndex].distanceSquared &&
0562                 candidates[i].averageDistance > candidates[bestCandidateIndex].averageDistance)) {
0563                 bestCandidateIndex = i;
0564             }
0565         }
0566         
0567         processedCells.push_back(candidates[bestCandidateIndex].index);
0568         availableCells.remove(candidates[bestCandidateIndex].availableCellIndex);
0569     }
0570 
0571     QVector<int> cellOrderList(numberOfCells);
0572     for (int i = 1; i < numberOfCells; ++i) {
0573         cellOrderList[processedCells[i]] = i;
0574     }
0575 
0576     return cellOrderList;
0577 }