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 }