| /* |
| * 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 "include/core/SkMatrix.h" |
| #include "include/core/SkPath.h" |
| #include "include/core/SkPathBuilder.h" |
| #include "include/core/SkPoint.h" |
| #include "include/core/SkRect.h" |
| #include "include/core/SkString.h" |
| #include "include/private/SkTDArray.h" |
| #include "src/gpu/graphite/sparse_strips/Flatten.h" |
| #include "src/gpu/graphite/sparse_strips/MSAA_LUT.h" |
| #include "src/gpu/graphite/sparse_strips/MakeStrips.h" |
| #include "src/gpu/graphite/sparse_strips/Polyline.h" |
| #include "src/gpu/graphite/sparse_strips/Strip.h" |
| #include "src/gpu/graphite/sparse_strips/Tiler.h" |
| #include "tests/Test.h" |
| |
| #include <array> |
| #include <cmath> |
| #include <cstdint> |
| |
| namespace skgpu::graphite { |
| |
| namespace { |
| |
| // Simplified point-in-polygon verification using Even-Odd rule. |
| bool is_inside(SkPoint pt, const Polyline& polyline) { |
| bool inside = false; |
| for (auto it = polyline.begin(); it != polyline.end(); ++it) { |
| auto [line, idx] = *it; |
| if ((line.p0.fY > pt.fY) != (line.p1.fY > pt.fY)) { |
| float t = (pt.fY - line.p0.fY) / (line.p1.fY - line.p0.fY); |
| float xInt = line.p0.fX + t * (line.p1.fX - line.p0.fX); |
| if (pt.fX < xInt) { |
| inside = !inside; |
| } |
| } |
| } |
| return inside; |
| } |
| |
| bool is_near_line(SkPoint pt, const Polyline& polyline, float threshold) { |
| for (auto it = polyline.begin(); it != polyline.end(); ++it) { |
| auto [line, idx] = *it; |
| float l2 = (line.p0.fX - line.p1.fX) * (line.p0.fX - line.p1.fX) + |
| (line.p0.fY - line.p1.fY) * (line.p0.fY - line.p1.fY); |
| float dist = 0.0f; |
| if (l2 == 0.0f) { |
| float dx = pt.fX - line.p0.fX; |
| float dy = pt.fY - line.p0.fY; |
| dist = std::sqrt(dx * dx + dy * dy); |
| } else { |
| float t = std::max(0.0f, |
| std::min(1.0f, |
| ((pt.fX - line.p0.fX) * (line.p1.fX - line.p0.fX) + |
| (pt.fY - line.p0.fY) * (line.p1.fY - line.p0.fY)) / |
| l2)); |
| float projX = line.p0.fX + t * (line.p1.fX - line.p0.fX); |
| float projY = line.p0.fY + t * (line.p1.fY - line.p0.fY); |
| dist = std::sqrt((pt.fX - projX) * (pt.fX - projX) + |
| (pt.fY - projY) * (pt.fY - projY)); |
| } |
| if (dist <= threshold) return true; |
| } |
| return false; |
| } |
| |
| template <uint16_t kTileWidth, uint16_t kTileHeight> |
| void print_diagnostics(skiatest::Reporter* reporter, |
| const Polyline& polyline, |
| const Tiles<kTileWidth, kTileHeight>& tiler, |
| int failX, |
| int failY, |
| const SkTDArray<uint8_t>& actualMasks, |
| size_t tileStartIdx) { |
| SkString out("\n--- FAILURE DIAGNOSTICS ---\n"); |
| |
| out.append("Geometry Lines: {\n"); |
| for (auto it = polyline.begin(); it != polyline.end(); ++it) { |
| auto [l, idx] = *it; |
| out.appendf(" {{%f, %f}, {%f, %f}},\n", l.p0.fX, l.p0.fY, l.p1.fX, l.p1.fY); |
| } |
| out.append("}\n\n"); |
| |
| out.append("Tile Intersections:\n"); |
| for (const auto& tile : tiler.getTiles()) { |
| uint32_t mask = tile.intersectionMask(); |
| uint32_t lineIdx = tile.lineIdx(); |
| out.appendf(" Tile(%u,%u) Line %u Mask: %s\n", |
| tile.x, |
| tile.y, |
| lineIdx, |
| IntersectionBits::MaskToString(mask).c_str()); |
| } |
| |
| out.appendf("\nASCII Map Tile(%d,%d) [Left: Expected | Right: Actual]\n", |
| failX / kTileWidth, |
| failY / kTileHeight); |
| SkString border("+"); |
| for (int x = 0; x < kTileWidth; ++x) border.append("----------------+"); |
| |
| for (int y = 0; y < kTileHeight; ++y) { |
| out.appendf("%s %s\n", border.c_str(), border.c_str()); |
| for (int sy = 0; sy < 8; ++sy) { |
| for (int side = 0; side < 2; ++side) { // 0: Expected, 1: Actual |
| out.append("|"); |
| for (int x = 0; x < kTileWidth; ++x) { |
| for (int sx = 0; sx < 8; ++sx) { |
| SkPoint cp = {failX + x + (sx + 0.5f) / 8.0f, |
| failY + y + (sy + 0.5f) / 8.0f}; |
| bool onLine = is_near_line(cp, polyline, 0.6f / 8.0f); |
| bool active = false; |
| |
| if (side == 0) { |
| active = is_inside(cp, polyline); |
| } else { |
| int32_t bufIdx = tileStartIdx + (y * kTileWidth + x); |
| uint8_t mask = |
| (bufIdx < actualMasks.size()) ? actualMasks[bufIdx] : 0; |
| active = (mask & (1 << sy)); |
| } |
| |
| if (MSAA_LUT<uint8_t>::kPattern[sy] == sx) { |
| out.append(active ? (onLine ? "*#" : " #") |
| : (onLine ? "*o" : " o")); |
| } else { |
| out.append(onLine ? "**" : " "); |
| } |
| } |
| out.append("|"); |
| } |
| if (side == 0) out.append(" "); |
| } |
| out.append("\n"); |
| } |
| } |
| out.appendf("%s %s\n", border.c_str(), border.c_str()); |
| INFOF(reporter, "%s", out.c_str()); |
| } |
| |
| } // namespace |
| |
| template <uint16_t kTileWidth, uint16_t kTileHeight> class CoverageTestRunner { |
| public: |
| static constexpr float kTileWidthF = static_cast<float>(kTileWidth); |
| static constexpr float kTileHeightF = static_cast<float>(kTileHeight); |
| static constexpr uint32_t kViewportWidth = 400; |
| static constexpr uint32_t kViewportHeight = 400; |
| static constexpr float kViewportWidthF = static_cast<float>(kViewportWidth); |
| static constexpr float kViewportHeightF = static_cast<float>(kViewportHeight); |
| |
| using StripFunc = void (*)(const Tiles<kTileWidth, kTileHeight>&, |
| SkTDArray<Strip>* stripBuf, |
| SkTDArray<uint8_t>* alphaBuf, |
| bool isInverse, |
| const Polyline& polyline, |
| const SkTDArray<uint8_t>& msaaLut, |
| MsaaExactMaskObserver observer); |
| |
| static void RunScalarWinding(const Tiles<kTileWidth, kTileHeight>& tileContainer, |
| SkTDArray<Strip>* stripBuf, |
| SkTDArray<uint8_t>* alphaBuf, |
| bool isInverse, |
| const Polyline& polyline, |
| const SkTDArray<uint8_t>& maskLut, |
| MsaaExactMaskObserver observer) { |
| SkPathFillType fillType = |
| isInverse ? SkPathFillType::kInverseWinding : SkPathFillType::kWinding; |
| MakeStrips::MsaaScalar<kTileWidth, kTileHeight>( |
| tileContainer, stripBuf, alphaBuf, fillType, polyline, maskLut, observer); |
| } |
| |
| static void RunSimdWinding(const Tiles<kTileWidth, kTileHeight>& tileContainer, |
| SkTDArray<Strip>* stripBuf, |
| SkTDArray<uint8_t>* alphaBuf, |
| bool isInverse, |
| const Polyline& polyline, |
| const SkTDArray<uint8_t>& maskLut, |
| MsaaExactMaskObserver observer) { |
| SkPathFillType fillType = |
| isInverse ? SkPathFillType::kInverseWinding : SkPathFillType::kWinding; |
| MakeStrips::MsaaSimd<kTileWidth, kTileHeight>( |
| tileContainer, stripBuf, alphaBuf, fillType, polyline, maskLut, observer); |
| } |
| |
| CoverageTestRunner(StripFunc func, const char* implName) : fFunc(func), fImplName(implName) {} |
| |
| void runAll(skiatest::Reporter* reporter) { |
| const SkTDArray<uint8_t> lut = GenerateMSAALUT<uint8_t>(); |
| constexpr int kErrorLimit = 3; |
| std::array<uint32_t, kErrorLimit> minorErrorCount = {0, 0, 0}; |
| int totalTestsRun = 0; |
| |
| struct TestCase { |
| SkPath path; |
| const char* name; |
| }; |
| std::vector<TestCase> baseGeometries; |
| |
| auto addRect = [&](float w, float h, const char* name) { |
| baseGeometries.push_back( |
| {SkPathBuilder().addRect(SkRect::MakeWH(w, h)).detach(), name}); |
| }; |
| |
| addRect(kTileWidthF * 0.5f, kTileHeightF * 0.5f, "Rect(Small)"); |
| addRect(kTileWidthF, kTileHeightF, "Rect(ExactTile)"); |
| addRect(kTileWidthF * 2.5f, kTileHeightF * 1.5f, "Rect(MultiTile)"); |
| addRect(kTileWidthF * 4.0f, 0.2f, "Rect(HorizSliver)"); |
| addRect(0.2f, kTileHeightF * 4.0f, "Rect(VertSliver)"); |
| |
| baseGeometries.push_back( |
| {SkPathBuilder() |
| .addCircle(kTileWidthF * 1.5f, kTileHeightF * 1.5f, kTileWidthF * 1.2f) |
| .detach(), |
| "Circle"}); |
| |
| baseGeometries.push_back({ |
| SkPathBuilder().addOval(SkRect::MakeWH(kTileWidth * 4.0f, 0.5f)).detach(), |
| "ThinOval" |
| }); |
| |
| SkPathBuilder inset; |
| inset.addRect(SkRect::MakeWH(kTileWidthF * 3.0f, kTileHeightF * 3.0f), |
| SkPathDirection::kCW); |
| inset.addRect(SkRect::MakeXYWH(kTileWidthF, kTileHeightF, kTileWidthF, kTileHeightF), |
| SkPathDirection::kCCW); |
| baseGeometries.push_back({inset.detach(), "InsetRect"}); |
| |
| // Tile-relative alignments (dx, dy) |
| const SkPoint alignments[] = { |
| {0.0f, 0.0f}, // Top & Left aligned |
| {0.0f, kTileHeightF * 0.5f}, // Left aligned, offset top |
| {kTileWidthF * 0.5f, 0.0f}, // Top aligned, offset left |
| {kTileWidthF * 0.33f, kTileHeightF * 0.33f}, // Strictly inside |
| {kTileWidthF - 0.01f, kTileHeightF - 0.01f} // Right on a tile boundary edge |
| }; |
| |
| for (const TestCase& geom : baseGeometries) { |
| // Progressively rotate the geometry |
| for (int angleDeg = 0; angleDeg < 360; ++angleDeg) { |
| float angle = static_cast<float>(angleDeg); |
| |
| for (const SkPoint& alignment : alignments) { |
| SkMatrix rotMatrix; |
| rotMatrix.setRotate(angle); |
| SkRect rotatedBounds = geom.path.makeTransform(rotMatrix).getBounds(); |
| SkMatrix transMatrix; |
| transMatrix.setTranslate(alignment.fX - rotatedBounds.fLeft, |
| alignment.fY - rotatedBounds.fTop); |
| SkMatrix ctm = SkMatrix::Concat(transMatrix, rotMatrix); |
| SkPath deviceSpacePath = geom.path.makeTransform(ctm); |
| |
| SkString testName; |
| testName.printf("%s - %s Rot(%.1f) Align(%.2f,%.2f)", |
| fImplName, |
| geom.name, |
| angle, |
| alignment.fX, |
| alignment.fY); |
| |
| if (!this->runSingleTest(reporter, |
| deviceSpacePath, |
| testName.c_str(), |
| lut, |
| &minorErrorCount)) { |
| return; |
| } |
| totalTestsRun++; |
| } |
| } |
| } |
| |
| INFOF(reporter, |
| "[%s (%dx%d)] Coverage LUT Test Complete. Ran %d variants. " |
| "Minor Error Summary: 1-sample: %u, 2-sample: %u, 3-sample: %u\n", |
| fImplName, |
| kTileWidth, |
| kTileHeight, |
| totalTestsRun, |
| minorErrorCount[0], |
| minorErrorCount[1], |
| minorErrorCount[2]); |
| } |
| |
| private: |
| StripFunc fFunc; |
| const char* fImplName; |
| |
| bool runSingleTest(skiatest::Reporter* reporter, |
| const SkPath& path, |
| const char* name, |
| const SkTDArray<uint8_t>& lut, |
| std::array<uint32_t, 3>* minorErrorCount) { |
| Flatten flattener; |
| Polyline polyline; |
| flattener.processPaths<FlattenMode::kSimd>( |
| path, SkMatrix(), kViewportWidthF, kViewportHeightF, &polyline); |
| |
| Tiles<kTileWidth, kTileHeight> tiler; |
| tiler.makeTilesMSAA(polyline, kViewportWidth, kViewportHeight); |
| tiler.sortTiles(); |
| |
| SkTDArray<Strip> stripBuf; |
| SkTDArray<uint8_t> alphaBuf; |
| SkTDArray<uint8_t> exactMasks; |
| |
| auto observer = [&](uint8_t exactMask) { exactMasks.push_back(exactMask); }; |
| fFunc(tiler, &stripBuf, &alphaBuf, /*isInverse=*/false, polyline, lut, observer); |
| |
| if (stripBuf.empty()) { |
| bool bufferSizeMatch = alphaBuf.empty(); |
| REPORTER_ASSERT( |
| reporter, bufferSizeMatch, "[%s] No strips but alpha buffer has data.", name); |
| return bufferSizeMatch; |
| } |
| |
| int32_t alphaIdx = 0; |
| |
| for (int32_t i = 0; i < stripBuf.size() - 1; ++i) { |
| const Strip& curr = stripBuf[i]; |
| const Strip& next = stripBuf[i + 1]; |
| |
| uint32_t startIdx = curr.alphaIndex(); |
| uint32_t endIdx = next.alphaIndex(); |
| uint16_t spannedTiles = (endIdx - startIdx) / (kTileWidth * kTileHeight); |
| |
| uint16_t currX = curr.fX; |
| uint16_t currY = curr.fY; |
| |
| for (int32_t s = 0; s < spannedTiles; ++s) { |
| int32_t tileStartIdx = alphaIdx; |
| for (int32_t y = 0; y < kTileHeight; ++y) { |
| for (int32_t x = 0; x < kTileWidth; ++x) { |
| uint8_t expectedMask = 0; |
| int expectedSamples = 0; |
| for (int k = 0; k < 8; ++k) { |
| if (is_inside( |
| {currX + x + (MSAA_LUT<uint8_t>::kPattern[k] + 0.5f) / 8.0f, |
| currY + y + (k + 0.5f) / 8.0f}, |
| polyline)) { |
| expectedSamples++; |
| expectedMask |= (1 << k); |
| } |
| } |
| |
| uint8_t actualMask = |
| (alphaIdx < exactMasks.size()) ? exactMasks[alphaIdx] : 0; |
| uint8_t actualAlpha = (alphaIdx < alphaBuf.size()) ? alphaBuf[alphaIdx] : 0; |
| |
| int sampleDiff = 0; |
| int actualSamples = 0; |
| for (int k = 0; k < 8; ++k) { |
| if (actualMask & (1 << k)) actualSamples++; |
| if ((expectedMask & (1 << k)) != (actualMask & (1 << k))) sampleDiff++; |
| } |
| |
| uint8_t expectedAlphaFromMask = |
| static_cast<uint8_t>((actualSamples * 255 + 4) / 8); |
| if (actualAlpha != expectedAlphaFromMask) { |
| REPORTER_ASSERT( |
| reporter, |
| false, |
| "[%s] Alpha Reduction Mismatch at tile(%d,%d) pixel(%d,%d). " |
| "Observer tracked %d active bits (expected alpha %d), " |
| "but AlphaBuf output was %d.", |
| name, |
| currX / kTileWidth, |
| currY / kTileHeight, |
| x, |
| y, |
| actualSamples, |
| expectedAlphaFromMask, |
| actualAlpha); |
| return false; |
| } |
| |
| if (sampleDiff > 3) { |
| print_diagnostics(reporter, |
| polyline, |
| tiler, |
| currX, |
| currY, |
| exactMasks, |
| tileStartIdx); |
| REPORTER_ASSERT(reporter, |
| false, |
| "[%s] Fail at tile(%d,%d). Exp %d, Got %d (alpha %d)", |
| name, |
| currX / kTileWidth, |
| currY / kTileHeight, |
| expectedSamples, |
| actualSamples, |
| actualAlpha); |
| return false; |
| } else if (sampleDiff > 0) { |
| (*minorErrorCount)[sampleDiff - 1]++; |
| } |
| |
| alphaIdx++; |
| } |
| } |
| currX += kTileWidth; |
| } |
| } |
| |
| bool bufferSizeMatch = (alphaIdx == alphaBuf.size()); |
| REPORTER_ASSERT(reporter, |
| bufferSizeMatch, |
| "[%s] Checked %d alpha bytes but buffer size is %d", |
| name, |
| alphaIdx, |
| alphaBuf.size()); |
| return bufferSizeMatch; |
| } |
| }; |
| |
| DEF_TEST(SparseStrips_CoverageScalar_4x4, reporter) { |
| skgpu::graphite::CoverageTestRunner<4, 4> scalarRunner( |
| &skgpu::graphite::CoverageTestRunner<4, 4>::RunScalarWinding, "Scalar"); |
| scalarRunner.runAll(reporter); |
| } |
| |
| DEF_TEST(SparseStrips_CoverageSIMD_4x4, reporter) { |
| skgpu::graphite::CoverageTestRunner<4, 4> simdRunner( |
| &skgpu::graphite::CoverageTestRunner<4, 4>::RunSimdWinding, "SIMD"); |
| simdRunner.runAll(reporter); |
| } |
| |
| DEF_TEST(SparseStrips_CoverageSIMD_8x8, reporter) { |
| skgpu::graphite::CoverageTestRunner<8, 8> simdRunner( |
| &skgpu::graphite::CoverageTestRunner<8, 8>::RunSimdWinding, "SIMD"); |
| simdRunner.runAll(reporter); |
| } |
| |
| } // namespace skgpu::graphite |
