File indexing completed on 2024-05-19 04:26:41
0001 /* 0002 * SPDX-FileCopyrightText: 2020 Dmitry Kazakov <dimula73@gmail.com> 0003 * 0004 * SPDX-License-Identifier: GPL-2.0-or-later 0005 */ 0006 0007 #include "KisBezierTransformMesh.h" 0008 0009 #include "kis_grid_interpolation_tools.h" 0010 #include <KisBezierPatchParamSpaceUtils.h> 0011 #include <KisSampleRectIterator.h> 0012 #include <KisBezierPatchParamToSourceSampler.h> 0013 #include "kis_debug.h" 0014 0015 KisBezierTransformMesh::patch_const_iterator 0016 KisBezierTransformMesh::hitTestPatchImpl(const QPointF &pt, QPointF *localPointResult) const 0017 { 0018 auto result = endPatches(); 0019 0020 const QRectF unitRect(0, 0, 1, 1); 0021 0022 for (auto it = beginPatches(); it != endPatches(); ++it) { 0023 Patch patch = *it; 0024 0025 if (patch.dstBoundingRect().contains(pt)) { 0026 const QPointF localPos = KisBezierUtils::calculateLocalPos(patch.points, pt); 0027 0028 if (unitRect.contains(localPos)) { 0029 0030 if (localPointResult) { 0031 *localPointResult = localPos; 0032 } 0033 0034 result = it; 0035 break; 0036 } 0037 } 0038 } 0039 0040 return result; 0041 } 0042 0043 KisBezierTransformMesh::PatchIndex KisBezierTransformMesh::hitTestPatch(const QPointF &pt, QPointF *localPointResult) const 0044 { 0045 return hitTestPatchImpl(pt, localPointResult).patchIndex(); 0046 } 0047 0048 QRect KisBezierTransformMesh::hitTestPatchInSourceSpace(const QRectF &rect) const 0049 { 0050 const QRectF searchRect = rect & m_originalRect; 0051 0052 if (searchRect.isEmpty()) return QRect(); 0053 0054 const QPointF proportionalTL = KisAlgebra2D::absoluteToRelative(searchRect.topLeft(), m_originalRect); 0055 const QPointF proportionalBR = KisAlgebra2D::absoluteToRelative(searchRect.bottomRight(), m_originalRect); 0056 0057 const auto topItY = prev(upper_bound(m_rows.begin(), prev(m_rows.end()), proportionalTL.y())); 0058 const int topRow = distance(m_rows.begin(), topItY); 0059 0060 const auto leftItX = prev(upper_bound(m_columns.begin(), prev(m_columns.end()), proportionalTL.x())); 0061 const int leftColumn = distance(m_columns.begin(), leftItX); 0062 0063 const auto bottomItY = prev(upper_bound(m_rows.begin(), prev(m_rows.end()), proportionalBR.y())); 0064 const int bottomRow = distance(m_rows.begin(), bottomItY); 0065 0066 const auto rightItX = prev(upper_bound(m_columns.begin(), prev(m_columns.end()), proportionalBR.x())); 0067 const int rightColumn = distance(m_columns.begin(), rightItX); 0068 0069 return QRect(leftColumn, topRow, 0070 rightColumn - leftColumn + 1, 0071 bottomRow - topRow + 1); 0072 } 0073 0074 void KisBezierTransformMesh::transformPatch(const KisBezierPatch &patch, const QPoint &srcQImageOffset, const QImage &srcImage, const QPoint &dstQImageOffset, QImage *dstImage) 0075 { 0076 QVector<QPointF> originalPointsLocal; 0077 QVector<QPointF> transformedPointsLocal; 0078 QSize gridSize; 0079 0080 patch.sampleRegularGrid(gridSize, originalPointsLocal, transformedPointsLocal, QPointF(8,8)); 0081 0082 const QRect dstBoundsI = patch.dstBoundingRect().toAlignedRect(); 0083 const QRect imageSize = QRect(dstQImageOffset, dstImage->size()); 0084 KIS_SAFE_ASSERT_RECOVER_NOOP(imageSize.contains(dstBoundsI)); 0085 0086 { 0087 GridIterationTools::QImagePolygonOp polygonOp(srcImage, *dstImage, srcQImageOffset, dstQImageOffset); 0088 0089 GridIterationTools::RegularGridIndexesOp indexesOp(gridSize); 0090 GridIterationTools::iterateThroughGrid 0091 <GridIterationTools::AlwaysCompletePolygonPolicy>(polygonOp, indexesOp, 0092 gridSize, 0093 originalPointsLocal, 0094 transformedPointsLocal); 0095 } 0096 } 0097 0098 void KisBezierTransformMesh::transformPatch(const KisBezierPatch &patch, KisPaintDeviceSP srcDevice, KisPaintDeviceSP dstDevice) 0099 { 0100 QVector<QPointF> originalPointsLocal; 0101 QVector<QPointF> transformedPointsLocal; 0102 QSize gridSize; 0103 0104 patch.sampleRegularGrid(gridSize, originalPointsLocal, transformedPointsLocal, QPointF(8,8)); 0105 0106 { 0107 GridIterationTools::PaintDevicePolygonOp polygonOp(srcDevice, dstDevice); 0108 0109 GridIterationTools::RegularGridIndexesOp indexesOp(gridSize); 0110 GridIterationTools::iterateThroughGrid 0111 <GridIterationTools::AlwaysCompletePolygonPolicy>(polygonOp, indexesOp, 0112 gridSize, 0113 originalPointsLocal, 0114 transformedPointsLocal); 0115 } 0116 } 0117 0118 void KisBezierTransformMesh::transformMesh(const QPoint &srcQImageOffset, const QImage &srcImage, const QPoint &dstQImageOffset, QImage *dstImage) const 0119 { 0120 for (auto it = beginPatches(); it != endPatches(); ++it) { 0121 transformPatch(*it, srcQImageOffset, srcImage, dstQImageOffset, dstImage); 0122 } 0123 } 0124 0125 void KisBezierTransformMesh::transformMesh(KisPaintDeviceSP srcDevice, KisPaintDeviceSP dstDevice) const 0126 { 0127 for (auto it = beginPatches(); it != endPatches(); ++it) { 0128 transformPatch(*it, srcDevice, dstDevice); 0129 } 0130 } 0131 0132 QRect KisBezierTransformMesh::approxNeedRect(const QRect &rc) const 0133 { 0134 QRect result; 0135 0136 const QRect sampleRect = rc & dstBoundingRect().toAlignedRect(); 0137 if (sampleRect.isEmpty()) return result; 0138 0139 const QRectF unitRect(0, 0, 1, 1); 0140 const int samplesLimit = sampleRect.width() * sampleRect.height() / 2; 0141 0142 QRectF stepRect; 0143 0144 { 0145 /** 0146 * First, try to approximate the bounding need rect by sampling 0147 * control points. That is the main property of bezier curves: 0148 * the resulting curve is **always** contained inside the control 0149 * polygon. 0150 * 0151 * TODO: sample the whole wrapping polygon in a more uniform way, 0152 * that is, sample the whole perimeter of the patch. 0153 */ 0154 0155 const QRectF dstRect = rc; 0156 0157 auto tryAddHandle = [&dstRect, &stepRect] (const KisBezierPatch &patch, KisBezierPatch::ControlPointType controlType) { 0158 0159 auto fetchLocalPoint = 0160 [] (const KisBezierPatch &patch, 0161 KisBezierPatch::ControlPointType c0, 0162 KisBezierPatch::ControlPointType c1, 0163 KisBezierPatch::ControlPointType c2, 0164 KisBezierPatch::ControlPointType c3) { 0165 0166 const qreal handleLength = kisDistance(patch.points[c0], patch.points[c1]); 0167 const qreal totalLength = handleLength + 0168 kisDistance(patch.points[c1], patch.points[c2]) + 0169 kisDistance(patch.points[c2], patch.points[c3]); 0170 0171 return KisAlgebra2D::lerp(patch.originalRect.topLeft(), patch.originalRect.topRight(), 0172 handleLength / totalLength); 0173 }; 0174 0175 if (dstRect.contains(patch.points[controlType])) { 0176 QPointF localPoint; 0177 0178 switch (controlType) { 0179 case KisBezierPatch::TL: 0180 localPoint = patch.originalRect.topLeft(); 0181 break; 0182 case KisBezierPatch::TL_HC: { 0183 localPoint = fetchLocalPoint(patch, 0184 KisBezierPatch::TL, 0185 KisBezierPatch::TL_HC, 0186 KisBezierPatch::TR_HC, 0187 KisBezierPatch::TR); 0188 break; 0189 } 0190 case KisBezierPatch::TL_VC: 0191 localPoint = fetchLocalPoint(patch, 0192 KisBezierPatch::TL, 0193 KisBezierPatch::TL_VC, 0194 KisBezierPatch::BL_VC, 0195 KisBezierPatch::BL); 0196 break; 0197 case KisBezierPatch::TR: 0198 localPoint = patch.originalRect.topRight(); 0199 break; 0200 case KisBezierPatch::TR_HC: 0201 localPoint = fetchLocalPoint(patch, 0202 KisBezierPatch::TR, 0203 KisBezierPatch::TR_HC, 0204 KisBezierPatch::TL_HC, 0205 KisBezierPatch::TL); 0206 break; 0207 case KisBezierPatch::TR_VC: 0208 localPoint = fetchLocalPoint(patch, 0209 KisBezierPatch::TR, 0210 KisBezierPatch::TR_VC, 0211 KisBezierPatch::BR_VC, 0212 KisBezierPatch::BR); 0213 0214 break; 0215 case KisBezierPatch::BL: 0216 localPoint = patch.originalRect.bottomLeft(); 0217 break; 0218 case KisBezierPatch::BL_HC: 0219 localPoint = fetchLocalPoint(patch, 0220 KisBezierPatch::BL, 0221 KisBezierPatch::BL_HC, 0222 KisBezierPatch::BR_HC, 0223 KisBezierPatch::BR); 0224 break; 0225 case KisBezierPatch::BL_VC: 0226 localPoint = fetchLocalPoint(patch, 0227 KisBezierPatch::BL, 0228 KisBezierPatch::BL_VC, 0229 KisBezierPatch::TL_VC, 0230 KisBezierPatch::TL); 0231 break; 0232 case KisBezierPatch::BR: 0233 localPoint = patch.originalRect.bottomRight(); 0234 break; 0235 case KisBezierPatch::BR_HC: 0236 localPoint = fetchLocalPoint(patch, 0237 KisBezierPatch::BR, 0238 KisBezierPatch::BR_HC, 0239 KisBezierPatch::BL_HC, 0240 KisBezierPatch::BL); 0241 break; 0242 case KisBezierPatch::BR_VC: 0243 localPoint = fetchLocalPoint(patch, 0244 KisBezierPatch::BR, 0245 KisBezierPatch::BR_VC, 0246 KisBezierPatch::TR_VC, 0247 KisBezierPatch::TR); 0248 0249 break; 0250 } 0251 0252 KisAlgebra2D::accumulateBounds(localPoint, &stepRect); 0253 } 0254 }; 0255 0256 for (auto it = beginPatches(); it != endPatches(); ++it) { 0257 tryAddHandle(*it, KisBezierPatch::TL); 0258 tryAddHandle(*it, KisBezierPatch::TL_HC); 0259 tryAddHandle(*it, KisBezierPatch::TL_VC); 0260 0261 tryAddHandle(*it, KisBezierPatch::TR); 0262 tryAddHandle(*it, KisBezierPatch::TR_HC); 0263 tryAddHandle(*it, KisBezierPatch::TR_VC); 0264 0265 tryAddHandle(*it, KisBezierPatch::BL); 0266 tryAddHandle(*it, KisBezierPatch::BL_HC); 0267 tryAddHandle(*it, KisBezierPatch::BL_VC); 0268 0269 tryAddHandle(*it, KisBezierPatch::BR); 0270 tryAddHandle(*it, KisBezierPatch::BR_HC); 0271 tryAddHandle(*it, KisBezierPatch::BR_VC); 0272 } 0273 } 0274 0275 KisSampleRectIterator dstRectSampler(sampleRect); 0276 KisBezierPatch patch = *beginPatches(); 0277 KisBezierPatchParamToSourceSampler patchSampler(patch); 0278 0279 /// the number of points that has actually been 0280 /// sampled from the destination rect 0281 int hitPoints = 0; 0282 0283 while (1) { 0284 for (int i = 0; i < 10; i++) { 0285 const QPointF dstPoint = *dstRectSampler++; 0286 0287 if (patch.dstBoundingRect().contains(dstPoint)) { 0288 const QPointF localPoint = patch.globalToLocal(dstPoint); 0289 if (unitRect.contains(localPoint)) { 0290 KisAlgebra2D::accumulateBounds(patchSampler.point(localPoint), &stepRect); 0291 hitPoints++; 0292 continue; 0293 } 0294 } 0295 0296 { 0297 QPointF localPoint; 0298 auto it = hitTestPatchImpl(dstPoint, &localPoint); 0299 if (it != endPatches()) { 0300 patch = *it; 0301 patchSampler = KisBezierPatchParamToSourceSampler(patch); 0302 0303 KisAlgebra2D::accumulateBounds(patchSampler.point(localPoint), &stepRect); 0304 hitPoints++; 0305 } 0306 } 0307 } 0308 0309 QRect alignedRect = stepRect.toAlignedRect(); 0310 0311 if (hitPoints > 20 && !alignedRect.isEmpty() && alignedRect == result) { 0312 break; 0313 } 0314 0315 result = alignedRect; 0316 0317 if (dstRectSampler.numSamples() > qMin(2000, samplesLimit)) { 0318 /** 0319 * We don't warn if the "found" rect is empty, that is a perfectly 0320 * valid case. 0321 */ 0322 if (!result.isEmpty()) { 0323 qWarning() << "KisBezierTransformMesh::approxNeedRect: the algorithm hasn't converged!" 0324 << ppVar(hitPoints) << ppVar(stepRect) << ppVar(alignedRect) << ppVar(result); 0325 } 0326 break; 0327 } 0328 } 0329 0330 return result; 0331 } 0332 0333 QRect KisBezierTransformMesh::approxChangeRect(const QRect &rc) const 0334 { 0335 QRect result; 0336 0337 const QRect affectedPatches = hitTestPatchInSourceSpace(rc); 0338 0339 for (int row = affectedPatches.top(); row <= affectedPatches.bottom(); row++) { 0340 for (int column = affectedPatches.left(); column <= affectedPatches.right(); column++) { 0341 const KisBezierPatch patch = *find(PatchIndex(column, row)); 0342 const QRectF srcRect = QRectF(rc) & patch.srcBoundingRect(); 0343 const QRectF paramRect = calcTightSrcRectRangeInParamSpace(patch, srcRect, 0.1); 0344 0345 KisSampleRectIterator paramRectSampler(paramRect); 0346 QRect patchResultRect; 0347 QRectF stepRect; 0348 0349 while (1) { 0350 for (int i = 0; i < 10; i++) { 0351 const QPointF sampledParamPoint = *paramRectSampler++; 0352 const QPointF globalPoint = patch.localToGlobal(sampledParamPoint); 0353 KisAlgebra2D::accumulateBounds(globalPoint, &stepRect); 0354 } 0355 0356 const QRect alignedRect = stepRect.toAlignedRect(); 0357 0358 if (!alignedRect.isEmpty() && alignedRect == patchResultRect) { 0359 break; 0360 } 0361 0362 patchResultRect = alignedRect; 0363 0364 if (paramRectSampler.numSamples() > 2000) { 0365 qWarning() << "KisBezierTransformMesh::approxChangeRect: the algorithm hasn't converged!" 0366 << ppVar(result) << ppVar(patchResultRect) << ppVar(stepRect); 0367 break; 0368 } 0369 } 0370 0371 result |= patchResultRect; 0372 } 0373 } 0374 0375 return result; 0376 } 0377 0378 0379 /** 0380 * Approximate the param-space rect that corresponds to \p srcSpaceRect in the source-space. 0381 * The resulting param-space rect will fully cover the source-space rect (and will be bigger). 0382 */ 0383 QRectF KisBezierTransformMesh::calcTightSrcRectRangeInParamSpace(const KisBezierPatch &patch, const QRectF &srcSpaceRect, qreal srcPrecision) 0384 { 0385 using KisBezierUtils::Range; 0386 using KisBezierUtils::calcTightSrcRectRangeInParamSpace1D; 0387 0388 KIS_ASSERT_RECOVER_NOOP(patch.srcBoundingRect().contains(srcSpaceRect)); 0389 0390 KisBezierPatchParamToSourceSampler sampler(patch); 0391 0392 auto xSampler = [sampler] (qreal xParam) -> Range { 0393 return sampler.xRange(xParam); 0394 }; 0395 0396 auto ySampler = [sampler] (qreal yParam) -> Range { 0397 return sampler.yRange(yParam); 0398 }; 0399 0400 Range externalRangeX; 0401 Range internalRangeX; 0402 0403 Range externalRangeY; 0404 Range internalRangeY; 0405 0406 std::tie(externalRangeX, internalRangeX) = 0407 calcTightSrcRectRangeInParamSpace1D({0.0, 1.0}, 0408 Range::fromRectX(patch.originalRect), 0409 Range::fromRectX(srcSpaceRect), 0410 xSampler, srcPrecision); 0411 0412 std::tie(externalRangeY, internalRangeY) = 0413 calcTightSrcRectRangeInParamSpace1D({0.0, 1.0}, 0414 Range::fromRectY(patch.originalRect), 0415 Range::fromRectY(srcSpaceRect), 0416 ySampler, srcPrecision); 0417 0418 return Range::makeRectF(externalRangeX, externalRangeY); 0419 } 0420 0421 #include <kis_dom_utils.h> 0422 0423 void KisBezierTransformMeshDetail::saveValue(QDomElement *parent, const QString &tag, const KisBezierTransformMesh &mesh) 0424 { 0425 QDomDocument doc = parent->ownerDocument(); 0426 QDomElement e = doc.createElement(tag); 0427 parent->appendChild(e); 0428 0429 e.setAttribute("type", "transform-mesh"); 0430 0431 KisDomUtils::saveValue(&e, "size", mesh.m_size); 0432 KisDomUtils::saveValue(&e, "srcRect", mesh.m_originalRect); 0433 KisDomUtils::saveValue(&e, "columns", mesh.m_columns); 0434 KisDomUtils::saveValue(&e, "rows", mesh.m_rows); 0435 KisDomUtils::saveValue(&e, "nodes", mesh.m_nodes); 0436 } 0437 0438 bool KisBezierTransformMeshDetail::loadValue(const QDomElement &e, KisBezierTransformMesh *mesh) 0439 { 0440 if (!KisDomUtils::Private::checkType(e, "transform-mesh")) return false; 0441 0442 mesh->m_columns.clear(); 0443 mesh->m_rows.clear(); 0444 mesh->m_nodes.clear(); 0445 0446 KisDomUtils::loadValue(e, "size", &mesh->m_size); 0447 KisDomUtils::loadValue(e, "srcRect", &mesh->m_originalRect); 0448 KisDomUtils::loadValue(e, "columns", &mesh->m_columns); 0449 KisDomUtils::loadValue(e, "rows", &mesh->m_rows); 0450 KisDomUtils::loadValue(e, "nodes", &mesh->m_nodes); 0451 0452 return true; 0453 }