| /* |
| * Copyright 2026 Google LLC |
| * |
| * Use of this source code is governed by a BSD-style license that can be |
| * found in the LICENSE file. |
| */ |
| |
| #include "tests/graphite/sparse_strips/OracleValidator.h" |
| |
| #include "include/core/SkPath.h" |
| #include "include/core/SkPoint.h" |
| #include "include/core/SkRect.h" |
| #include "include/core/SkString.h" |
| #include "include/private/SkTDArray.h" |
| #include "src/core/SkVx.h" |
| #include "src/gpu/graphite/sparse_strips/Flatten.h" |
| #include "src/gpu/graphite/sparse_strips/MSAA_LUT.h" |
| #include "src/gpu/graphite/sparse_strips/Polyline.h" |
| #include "src/gpu/graphite/sparse_strips/Tiler.h" |
| #include "tests/Test.h" |
| #include "tests/graphite/sparse_strips/CoverageTestUtils.h" |
| #include "tests/graphite/sparse_strips/Oracle.h" |
| |
| #include <algorithm> |
| #include <cmath> |
| #include <cstdint> |
| #include <vector> |
| |
| namespace skgpu::graphite { |
| |
| template <uint16_t kTileWidth, uint16_t kTileHeight> |
| OracleValidator<kTileWidth, kTileHeight>::OracleValidator( |
| const SkPath& path, const WideTiles& wides, const EndCaps& ends, |
| const SkTDArray<skvx::int8>& exactWindings, const Polyline* polyline, |
| const Tiles<kTileWidth, kTileHeight>* tiler, const char* testName, Strictness strictness) |
| : fPath(path) |
| , fWides(wides) |
| , fEnds(ends) |
| , fExactWindings(exactWindings) |
| , fPolyline(polyline) |
| , fTiler(tiler) |
| , fTestName(testName) |
| , fStrictness(strictness) |
| , fToleranceSq(static_cast<float>(Flatten::kQuadTolerance2)) |
| , fOracle(path) { |
| this->buildTileLineMap(); |
| } |
| |
| template <uint16_t kTileWidth, uint16_t kTileHeight> |
| skvx::int8 OracleValidator<kTileWidth, kTileHeight>::GetOracleWinding( |
| int px, const std::vector<ScanlineOracle8x::RowWindingInterval>& intervals) { |
| return ScanlineOracle8x::GetOracleWinding(px, intervals); |
| } |
| |
| template <uint16_t kTileWidth, uint16_t kTileHeight> |
| bool OracleValidator<kTileWidth, kTileHeight>::validate(skiatest::Reporter* reporter, |
| uint16_t viewportWidth, |
| uint16_t viewportHeight, |
| uint32_t* maxSampleDiffOut) const { |
| if (!this->validateStreamInvariants(reporter, viewportWidth, viewportHeight)) { |
| return false; |
| } |
| |
| bool allPass = true; |
| const auto& caps = fEnds.caps(); |
| const auto& wides = fWides.tiles(); |
| |
| int capIdx = 0; |
| int wideIdx = 0; |
| |
| // Walk row by row through all tile rows present in caps or wides |
| while (capIdx < caps.size() || wideIdx < wides.size()) { |
| uint16_t rowY = UINT16_MAX; |
| if (capIdx < caps.size()) { |
| rowY = std::min(rowY, caps[capIdx].fY); |
| } |
| if (wideIdx < wides.size()) { |
| rowY = std::min(rowY, wides[wideIdx].fY); |
| } |
| |
| int rowCapStart = capIdx; |
| while (capIdx < caps.size() && caps[capIdx].fY == rowY) { |
| capIdx++; |
| } |
| int rowCapEnd = capIdx; |
| |
| int rowWideStart = wideIdx; |
| while (wideIdx < wides.size() && wides[wideIdx].fY == rowY) { |
| wideIdx++; |
| } |
| int rowWideEnd = wideIdx; |
| |
| auto isGapFilled = [&](uint16_t startX, uint16_t endX) -> bool { |
| for (int w = rowWideStart; w < rowWideEnd; ++w) { |
| if (wides[w].fX == startX && wides[w].fX + wides[w].fWidth == endX) { |
| return true; |
| } |
| } |
| return false; |
| }; |
| |
| // Process each pixel row within this tile row [rowY, rowY + kTileHeight) |
| for (uint16_t py = rowY; py < rowY + kTileHeight && py < viewportHeight; ++py) { |
| std::vector<ScanlineOracle8x::RowWindingInterval> oracleIntervals = |
| fOracle.buildRowIntervals(py); |
| |
| int prevEndTileX = 0; |
| |
| for (int c = rowCapStart; c < rowCapEnd; ++c) { |
| const auto& cap = caps[c]; |
| uint16_t alphaStartTileX = cap.fX; |
| uint16_t alphaEndTileX = cap.fX + cap.fWidth; |
| uint16_t spannedTiles = cap.fWidth / kTileWidth; |
| |
| // A. Validate gap preceding this cap [prevEndTileX, alphaStartTileX) |
| if (alphaStartTileX > prevEndTileX) { |
| bool filled = isGapFilled(prevEndTileX, alphaStartTileX); |
| allPass &= this->validateGapSpan(reporter, |
| prevEndTileX, |
| alphaStartTileX, |
| py, |
| oracleIntervals, |
| filled); |
| } |
| |
| // B. Validate boundary column left of the first tile in this cap run |
| if (alphaStartTileX > 0) { |
| uint16_t leftColX = alphaStartTileX - 1; |
| bool leftFill = false; |
| for (int w = rowWideStart; w < rowWideEnd; ++w) { |
| if (wides[w].fX + wides[w].fWidth == alphaStartTileX) { |
| leftFill = true; |
| break; |
| } |
| } |
| allPass &= this->validateBoundaryColumn( |
| reporter, leftColX, py, oracleIntervals, leftFill); |
| } |
| |
| // C. Validate inside the alpha tiles span |
| allPass &= this->validateAlphaTileSpan(reporter, |
| cap.fX, |
| cap.fY, |
| cap.fAlphaIndex, |
| spannedTiles, |
| py, |
| oracleIntervals, |
| maxSampleDiffOut); |
| |
| // D. Validate boundary column right of the last tile in this cap run |
| if (alphaEndTileX < viewportWidth) { |
| uint16_t rightColX = alphaEndTileX; |
| bool rightFill = false; |
| for (int w = rowWideStart; w < rowWideEnd; ++w) { |
| if (wides[w].fX == alphaEndTileX) { |
| rightFill = true; |
| break; |
| } |
| } |
| allPass &= this->validateBoundaryColumn( |
| reporter, rightColX, py, oracleIntervals, rightFill); |
| } |
| |
| prevEndTileX = alphaEndTileX; |
| } |
| |
| // E. Validate trailing gap to viewport edge [prevEndTileX, viewportWidth) |
| if (prevEndTileX < viewportWidth) { |
| bool filled = isGapFilled(prevEndTileX, viewportWidth); |
| allPass &= this->validateGapSpan(reporter, |
| prevEndTileX, |
| viewportWidth, |
| py, |
| oracleIntervals, |
| filled); |
| } |
| } |
| } |
| |
| return allPass; |
| } |
| |
| template <uint16_t kTileWidth, uint16_t kTileHeight> |
| bool OracleValidator<kTileWidth, kTileHeight>::validateStreamInvariants( |
| skiatest::Reporter* reporter, uint16_t viewportWidth, uint16_t viewportHeight) const { |
| const auto& caps = fEnds.caps(); |
| const auto& wides = fWides.tiles(); |
| |
| if (caps.empty() && wides.empty()) { |
| return true; |
| } |
| |
| // Validate EndCaps invariants |
| uint16_t lastCapY = 0; |
| uint16_t lastCapEndX = 0; |
| bool hasLastCap = false; |
| for (int i = 0; i < caps.size(); ++i) { |
| const auto& cap = caps[i]; |
| if (cap.fX % kTileWidth != 0) { |
| ERRORF(reporter, "[%s] Cap[%d] fX (%u) not aligned to kTileWidth (%u)", |
| fTestName, i, cap.fX, kTileWidth); |
| return false; |
| } |
| if (cap.fY % kTileHeight != 0) { |
| ERRORF(reporter, "[%s] Cap[%d] fY (%u) not aligned to kTileHeight (%u)", |
| fTestName, i, cap.fY, kTileHeight); |
| return false; |
| } |
| if (cap.fWidth % kTileWidth != 0 || cap.fWidth == 0) { |
| ERRORF(reporter, "[%s] Cap[%d] fWidth (%u) not valid multiple of kTileWidth (%u)", |
| fTestName, i, cap.fWidth, kTileWidth); |
| return false; |
| } |
| if (cap.fAlphaIndex % (kTileWidth * kTileHeight) != 0) { |
| ERRORF(reporter, "[%s] Cap[%d] fAlphaIndex (%d) not multiple of tile size (%d)", |
| fTestName, i, cap.fAlphaIndex, static_cast<int>(kTileWidth * kTileHeight)); |
| return false; |
| } |
| if (hasLastCap) { |
| if (cap.fY < lastCapY) { |
| ERRORF(reporter, "[%s] Cap[%d] fY (%u) < previous row fY (%u)", |
| fTestName, i, cap.fY, lastCapY); |
| return false; |
| } |
| if (cap.fY == lastCapY && cap.fX < lastCapEndX) { |
| ERRORF(reporter, "[%s] Cap[%d] fX (%u) overlaps with previous cap endX (%u)", |
| fTestName, i, cap.fX, lastCapEndX); |
| return false; |
| } |
| } |
| lastCapY = cap.fY; |
| lastCapEndX = cap.fX + cap.fWidth; |
| hasLastCap = true; |
| } |
| |
| // Validate WideTiles invariants |
| uint16_t lastWideY = 0; |
| uint16_t lastWideEndX = 0; |
| bool hasLastWide = false; |
| for (int i = 0; i < wides.size(); ++i) { |
| const auto& wide = wides[i]; |
| if (wide.fX % kTileWidth != 0) { |
| ERRORF(reporter, "[%s] Wide[%d] fX (%u) not aligned to kTileWidth (%u)", |
| fTestName, i, wide.fX, kTileWidth); |
| return false; |
| } |
| if (wide.fY % kTileHeight != 0) { |
| ERRORF(reporter, "[%s] Wide[%d] fY (%u) not aligned to kTileHeight (%u)", |
| fTestName, i, wide.fY, kTileHeight); |
| return false; |
| } |
| if (wide.fWidth % kTileWidth != 0 || wide.fWidth == 0) { |
| ERRORF(reporter, "[%s] Wide[%d] fWidth (%u) not valid multiple of kTileWidth (%u)", |
| fTestName, i, wide.fWidth, kTileWidth); |
| return false; |
| } |
| if (hasLastWide) { |
| if (wide.fY < lastWideY) { |
| ERRORF(reporter, "[%s] Wide[%d] fY (%u) < previous row fY (%u)", |
| fTestName, i, wide.fY, lastWideY); |
| return false; |
| } |
| if (wide.fY == lastWideY && wide.fX < lastWideEndX) { |
| ERRORF(reporter, "[%s] Wide[%d] fX (%u) overlaps with previous wide endX (%u)", |
| fTestName, i, wide.fX, lastWideEndX); |
| return false; |
| } |
| } |
| lastWideY = wide.fY; |
| lastWideEndX = wide.fX + wide.fWidth; |
| hasLastWide = true; |
| } |
| |
| return true; |
| } |
| |
| template <uint16_t kTileWidth, uint16_t kTileHeight> |
| bool OracleValidator<kTileWidth, kTileHeight>::validateBoundaryColumn( |
| skiatest::Reporter* reporter, |
| uint16_t px, |
| uint16_t py, |
| const std::vector<ScanlineOracle8x::RowWindingInterval>& oracleIntervals, |
| bool expectedFill) const { |
| skvx::int8 w = GetOracleWinding(px, oracleIntervals); |
| int activeCount = 0; |
| uint16_t tileX = px / kTileWidth; |
| uint16_t tileY = py / kTileHeight; |
| |
| for (int k = 0; k < 8; ++k) { |
| bool covered = (w[k] != 0); |
| if (fStrictness == Strictness::kNonStrict && covered != expectedFill) { |
| float subX = (static_cast<float>(kMsaaPattern<uint8_t>[k]) + 0.5f) / 8.0f; |
| float subY = (static_cast<float>(k) + 0.5f) / 8.0f; |
| SkPoint subPt = SkPoint::Make(px + subX, py + subY); |
| if (this->isWithinTolerance(subPt, tileX, tileY)) { |
| covered = expectedFill; |
| } |
| } |
| if (covered) activeCount++; |
| } |
| |
| // Allow 1-sample tolerance on boundary columns for curved paths due to flattening chord error |
| bool matches = expectedFill ? (activeCount >= 7) : (activeCount <= 1); |
| if (!matches) { |
| ERRORF(reporter, |
| "[%s] Boundary Column Winding Mismatch at (px=%u, py=%u): Expected %s, " |
| "but Oracle has winding [%d,%d,%d,%d,%d,%d,%d,%d] (%d non-zero)", |
| fTestName, |
| px, |
| py, |
| expectedFill ? "Solid Fill" : "Empty Space", |
| w[0], w[1], w[2], w[3], w[4], w[5], w[6], w[7], |
| activeCount); |
| return false; |
| } |
| return true; |
| } |
| |
| template <uint16_t kTileWidth, uint16_t kTileHeight> |
| bool OracleValidator<kTileWidth, kTileHeight>::validateGapSpan( |
| skiatest::Reporter* reporter, |
| int startPx, |
| int endPx, |
| uint16_t py, |
| const std::vector<ScanlineOracle8x::RowWindingInterval>& oracleIntervals, |
| bool expectedFill) const { |
| bool allPass = true; |
| uint16_t tileY = py / kTileHeight; |
| for (int px = startPx; px < endPx; ++px) { |
| skvx::int8 w = GetOracleWinding(px, oracleIntervals); |
| int activeCount = 0; |
| uint16_t tileX = px / kTileWidth; |
| for (int k = 0; k < 8; ++k) { |
| bool covered = (w[k] != 0); |
| if (fStrictness == Strictness::kNonStrict && covered != expectedFill) { |
| float subX = (static_cast<float>(kMsaaPattern<uint8_t>[k]) + 0.5f) / 8.0f; |
| float subY = (static_cast<float>(k) + 0.5f) / 8.0f; |
| SkPoint subPt = SkPoint::Make(px + subX, py + subY); |
| if (this->isWithinTolerance(subPt, tileX, tileY)) { |
| covered = expectedFill; |
| } |
| } |
| if (covered) activeCount++; |
| } |
| |
| // Allow 1-sample tolerance on gap edges for curved paths due to flattening chord error |
| bool matches = expectedFill ? (activeCount >= 7) : (activeCount <= 1); |
| if (!matches) { |
| ERRORF(reporter, |
| "[%s] Gap Span Winding Mismatch at (px=%d, py=%u): Expected %s, " |
| "but Oracle has winding [%d,%d,%d,%d,%d,%d,%d,%d] (%d non-zero)", |
| fTestName, |
| px, |
| py, |
| expectedFill ? "Solid Fill" : "Empty Space", |
| w[0], w[1], w[2], w[3], w[4], w[5], w[6], w[7], |
| activeCount); |
| allPass = false; |
| break; |
| } |
| } |
| return allPass; |
| } |
| |
| template <uint16_t kTileWidth, uint16_t kTileHeight> |
| bool OracleValidator<kTileWidth, kTileHeight>::validateAlphaTileSpan( |
| skiatest::Reporter* reporter, |
| uint16_t startTileX, |
| uint16_t rowY, |
| uint32_t startAlphaIdx, |
| uint16_t spannedTiles, |
| uint16_t py, |
| const std::vector<ScanlineOracle8x::RowWindingInterval>& oracleIntervals, |
| uint32_t* maxSampleDiffOut) const { |
| uint16_t localY = py - rowY; |
| uint16_t tileY = rowY / kTileHeight; |
| bool allPass = true; |
| |
| for (uint16_t t = 0; t < spannedTiles; ++t) { |
| uint16_t tileStartX = startTileX + t * kTileWidth; |
| uint16_t tileX = tileStartX / kTileWidth; |
| uint32_t tileStartAlphaIdx = startAlphaIdx + t * (kTileWidth * kTileHeight); |
| |
| for (uint16_t localX = 0; localX < kTileWidth; ++localX) { |
| uint16_t px = tileStartX + localX; |
| uint32_t alphaIdx = tileStartAlphaIdx + localY * kTileWidth + localX; |
| |
| if (alphaIdx >= static_cast<uint32_t>(fExactWindings.size())) { |
| ERRORF(reporter, |
| "[%s] Alpha index %u out of bounds (exactWindings size %d) at tile(%d,%d) " |
| "pixel(%d,%d)", |
| fTestName, |
| alphaIdx, |
| fExactWindings.size(), |
| static_cast<int>(tileX), |
| static_cast<int>(tileY), |
| static_cast<int>(localX), |
| static_cast<int>(localY)); |
| return false; |
| } |
| |
| skvx::int8 actualWinding = fExactWindings[alphaIdx]; |
| skvx::int8 oracleWinding = GetOracleWinding(px, oracleIntervals); |
| |
| int sampleDiff = 0; |
| for (int k = 0; k < 8; ++k) { |
| if (actualWinding[k] != oracleWinding[k]) { |
| bool isError = true; |
| if (fStrictness == Strictness::kNonStrict) { |
| float subX = (static_cast<float>(kMsaaPattern<uint8_t>[k]) + 0.5f) / 8.0f; |
| float subY = (static_cast<float>(k) + 0.5f) / 8.0f; |
| SkPoint subPt = SkPoint::Make(px + subX, py + subY); |
| if (this->isWithinTolerance(subPt, tileX, tileY)) { |
| isError = false; |
| } |
| } |
| if (isError) { |
| sampleDiff++; |
| } |
| } |
| } |
| |
| if (maxSampleDiffOut) { |
| *maxSampleDiffOut = std::max(*maxSampleDiffOut, static_cast<uint32_t>(sampleDiff)); |
| } |
| |
| if (sampleDiff > 4) { |
| CoverageTestUtils::PrintWindingDiagnostics<kTileWidth, kTileHeight>( |
| reporter, |
| fTestName, |
| tileStartX, |
| rowY, |
| px, |
| py, |
| actualWinding, |
| oracleWinding, |
| fPolyline, |
| fTiler, |
| fExactWindings, |
| tileStartAlphaIdx, |
| &fOracle); |
| ERRORF(reporter, |
| "[%s] Direct Winding Mismatch at tile(%d,%d) pixel(%d,%d) (px=%u, py=%u): " |
| "Diff %d samples. Actual Winding [%d,%d,%d,%d,%d,%d,%d,%d], Oracle Winding " |
| "[%d,%d,%d,%d,%d,%d,%d,%d]", |
| fTestName, |
| static_cast<int>(tileX), |
| static_cast<int>(tileY), |
| static_cast<int>(localX), |
| static_cast<int>(localY), |
| px, |
| py, |
| sampleDiff, |
| actualWinding[0], actualWinding[1], actualWinding[2], actualWinding[3], |
| actualWinding[4], actualWinding[5], actualWinding[6], actualWinding[7], |
| oracleWinding[0], oracleWinding[1], oracleWinding[2], oracleWinding[3], |
| oracleWinding[4], oracleWinding[5], oracleWinding[6], oracleWinding[7]); |
| allPass = false; |
| } |
| } |
| } |
| return allPass; |
| } |
| |
| template <uint16_t kTileWidth, uint16_t kTileHeight> |
| float OracleValidator<kTileWidth, kTileHeight>::DistanceSqToSegment(SkPoint p, |
| SkPoint a, |
| SkPoint b) { |
| float dx = b.fX - a.fX; |
| float dy = b.fY - a.fY; |
| float lenSq = dx * dx + dy * dy; |
| if (lenSq == 0.0f) { |
| float px = p.fX - a.fX; |
| float py = p.fY - a.fY; |
| return px * px + py * py; |
| } |
| float t = ((p.fX - a.fX) * dx + (p.fY - a.fY) * dy) / lenSq; |
| t = std::max(0.0f, std::min(1.0f, t)); |
| float projX = a.fX + t * dx; |
| float projY = a.fY + t * dy; |
| float distSqX = p.fX - projX; |
| float distSqY = p.fY - projY; |
| return distSqX * distSqX + distSqY * distSqY; |
| } |
| |
| template <uint16_t kTileWidth, uint16_t kTileHeight> |
| void OracleValidator<kTileWidth, kTileHeight>::buildTileLineMap() { |
| if (!fTiler || !fPolyline) { |
| return; |
| } |
| for (const auto& tile : fTiler->getTiles()) { |
| uint32_t lineIdx = tile.fPackedLineIdxIntersectionMask >> IntersectionBits::INT_MASK_SHIFT; |
| if (lineIdx + 1 < static_cast<uint32_t>(fPolyline->points().size())) { |
| Line line = fPolyline->getLine(lineIdx); |
| uint32_t tileKey = (static_cast<uint32_t>(tile.y) << 16) | tile.x; |
| auto& lines = fTileLineMap[tileKey]; |
| bool exists = false; |
| for (const auto& existing : lines) { |
| if (existing.p0 == line.p0 && existing.p1 == line.p1) { |
| exists = true; |
| break; |
| } |
| } |
| if (!exists) { |
| lines.push_back(line); |
| } |
| } |
| } |
| } |
| |
| template <uint16_t kTileWidth, uint16_t kTileHeight> |
| bool OracleValidator<kTileWidth, kTileHeight>::isWithinTolerance(SkPoint subPt, |
| uint16_t tileX, |
| uint16_t tileY) const { |
| for (int dy = -1; dy <= 1; ++dy) { |
| int ny = static_cast<int>(tileY) + dy; |
| if (ny < 0) { |
| continue; |
| } |
| for (int dx = -1; dx <= 1; ++dx) { |
| int nx = static_cast<int>(tileX) + dx; |
| if (nx < 0) { |
| continue; |
| } |
| uint32_t key = (static_cast<uint32_t>(ny) << 16) | static_cast<uint32_t>(nx); |
| auto it = fTileLineMap.find(key); |
| if (it != fTileLineMap.end()) { |
| for (const auto& line : it->second) { |
| if (DistanceSqToSegment(subPt, line.p0, line.p1) <= fToleranceSq) { |
| return true; |
| } |
| } |
| } |
| } |
| } |
| return false; |
| } |
| |
| // Explicit template instantiations for supported tile sizes |
| template class OracleValidator<4, 4>; |
| template class OracleValidator<8, 8>; |
| |
| } // namespace skgpu::graphite |
