1 /* 2 * Copyright 2019 Google Inc. 3 * 4 * Use of this source code is governed by a BSD-style license that can be 5 * found in the LICENSE file. 6 */ 7 8 #include "Sample.h" 9 10 #include "GrQuad.h" 11 #include "ops/GrQuadPerEdgeAA.h" 12 13 #include "SkCanvas.h" 14 #include "SkDashPathEffect.h" 15 #include "SkPaint.h" 16 #include "SkPathOps.h" 17 18 // Draw a line through the two points, outset by a fixed length in screen space 19 static void draw_extended_line(SkCanvas* canvas, const SkPaint paint, 20 const SkPoint& p0, const SkPoint& p1) { 21 SkVector v = p1 - p0; 22 v.setLength(v.length() + 3.f); 23 canvas->drawLine(p1 - v, p0 + v, paint); 24 25 // Draw normal vector too 26 SkPaint normalPaint = paint; 27 normalPaint.setPathEffect(nullptr); 28 normalPaint.setStrokeWidth(paint.getStrokeWidth() / 4.f); 29 30 SkVector n = {v.fY, -v.fX}; 31 n.setLength(.25f); 32 SkPoint m = (p0 + p1) * 0.5f; 33 canvas->drawLine(m, m + n, normalPaint); 34 } 35 36 static void make_aa_line(const SkPoint& p0, const SkPoint& p1, bool aaOn, 37 bool outset, SkPoint line[2]) { 38 SkVector n = {0.f, 0.f}; 39 if (aaOn) { 40 SkVector v = p1 - p0; 41 n = outset ? SkVector::Make(v.fY, -v.fX) : SkVector::Make(-v.fY, v.fX); 42 n.setLength(0.5f); 43 } 44 45 line[0] = p0 + n; 46 line[1] = p1 + n; 47 } 48 49 // To the line through l0-l1, not capped at the end points of the segment 50 static SkScalar signed_distance(const SkPoint& p, const SkPoint& l0, const SkPoint& l1) { 51 SkVector v = l1 - l0; 52 v.normalize(); 53 SkVector n = {v.fY, -v.fX}; 54 SkScalar c = -n.dot(l0); 55 return n.dot(p) + c; 56 } 57 58 static SkScalar get_area_coverage(const bool edgeAA[4], const SkPoint corners[4], 59 const SkPoint& point) { 60 SkPath shape; 61 shape.addPoly(corners, 4, true); 62 SkPath pixel; 63 pixel.addRect(SkRect::MakeXYWH(point.fX - 0.5f, point.fY - 0.5f, 1.f, 1.f)); 64 65 SkPath intersection; 66 if (!Op(shape, pixel, kIntersect_SkPathOp, &intersection) || intersection.isEmpty()) { 67 return 0.f; 68 } 69 70 // Calculate area of the convex polygon 71 SkScalar area = 0.f; 72 for (int i = 0; i < intersection.countPoints(); ++i) { 73 SkPoint p0 = intersection.getPoint(i); 74 SkPoint p1 = intersection.getPoint((i + 1) % intersection.countPoints()); 75 SkScalar det = p0.fX * p1.fY - p1.fX * p0.fY; 76 area += det; 77 } 78 79 // Scale by 1/2, then take abs value (this area formula is signed based on point winding, but 80 // since it's convex, just make it positive). 81 area = SkScalarAbs(0.5f * area); 82 83 // Now account for the edge AA. If the pixel center is outside of a non-AA edge, turn of its 84 // coverage. If the pixel only intersects non-AA edges, then set coverage to 1. 85 bool needsNonAA = false; 86 SkScalar edgeD[4]; 87 for (int i = 0; i < 4; ++i) { 88 SkPoint e0 = corners[i]; 89 SkPoint e1 = corners[(i + 1) % 4]; 90 edgeD[i] = -signed_distance(point, e0, e1); 91 if (!edgeAA[i]) { 92 if (edgeD[i] < -1e-4f) { 93 return 0.f; // Outside of non-AA line 94 } 95 needsNonAA = true; 96 } 97 } 98 // Otherwise inside the shape, so check if any AA edge exerts influence over nonAA 99 if (needsNonAA) { 100 for (int i = 0; i < 4; i++) { 101 if (edgeAA[i] && edgeD[i] < 0.5f) { 102 needsNonAA = false; 103 break; 104 } 105 } 106 } 107 return needsNonAA ? 1.f : area; 108 } 109 110 // FIXME take into account max coverage properly, 111 static SkScalar get_edge_dist_coverage(const bool edgeAA[4], const SkPoint corners[4], 112 const SkPoint outsetLines[8], const SkPoint insetLines[8], 113 const SkPoint& point) { 114 bool flip = false; 115 // If the quad has been inverted, the original corners will not all be on the negative side of 116 // every outset line. When that happens, calculate coverage using the "inset" lines and flip 117 // the signed distance 118 for (int i = 0; i < 4; ++i) { 119 for (int j = 0; j < 4; ++j) { 120 SkScalar d = signed_distance(corners[i], outsetLines[j * 2], outsetLines[j * 2 + 1]); 121 if (d >= 0.f) { 122 flip = true; 123 break; 124 } 125 } 126 if (flip) { 127 break; 128 } 129 } 130 131 const SkPoint* lines = flip ? insetLines : outsetLines; 132 133 SkScalar minCoverage = 1.f; 134 for (int i = 0; i < 4; ++i) { 135 // Multiply by negative 1 so that outside points have negative distances 136 SkScalar d = (flip ? 1 : -1) * signed_distance(point, lines[i * 2], lines[i * 2 + 1]); 137 if (!edgeAA[i] && d >= -1e-4f) { 138 d = 1.f; 139 } 140 if (d < minCoverage) { 141 minCoverage = d; 142 if (minCoverage < 0.f) { 143 break; // Outside the shape 144 } 145 } 146 } 147 return minCoverage < 0.f ? 0.f : minCoverage; 148 } 149 150 static bool inside_triangle(const SkPoint& point, const SkPoint& t0, const SkPoint& t1, 151 const SkPoint& t2, SkScalar bary[3]) { 152 // Check sign of t0 to (t1,t2). If it is positive, that means the normals point into the 153 // triangle otherwise the normals point outside the triangle so update edge distances as 154 // necessary 155 bool flip = signed_distance(t0, t1, t2) < 0.f; 156 157 SkScalar d0 = (flip ? -1 : 1) * signed_distance(point, t0, t1); 158 SkScalar d1 = (flip ? -1 : 1) * signed_distance(point, t1, t2); 159 SkScalar d2 = (flip ? -1 : 1) * signed_distance(point, t2, t0); 160 // Be a little forgiving 161 if (d0 < -1e-4f || d1 < -1e-4f || d2 < -1e-4f) { 162 return false; 163 } 164 165 // Inside, so calculate barycentric coords from the sideline distances 166 SkScalar d01 = (t0 - t1).length(); 167 SkScalar d12 = (t1 - t2).length(); 168 SkScalar d20 = (t2 - t0).length(); 169 170 if (SkScalarNearlyZero(d12) || SkScalarNearlyZero(d20) || SkScalarNearlyZero(d01)) { 171 // Empty degenerate triangle 172 return false; 173 } 174 175 // Coordinates for a vertex use distances to the opposite edge 176 bary[0] = d1 * d12; 177 bary[1] = d2 * d20; 178 bary[2] = d0 * d01; 179 // And normalize 180 SkScalar sum = bary[0] + bary[1] + bary[2]; 181 bary[0] /= sum; 182 bary[1] /= sum; 183 bary[2] /= sum; 184 185 return true; 186 } 187 188 static SkScalar get_framed_coverage(const SkPoint outer[4], const SkScalar outerCoverages[4], 189 const SkPoint inner[4], const SkScalar innerCoverages[4], 190 const SkPoint& point) { 191 // Triangles are ordered clock wise. Indices >= 4 refer to inner[i - 4]. Otherwise its outer[i]. 192 static const int kFrameTris[] = { 193 0, 1, 4, 4, 1, 5, 194 1, 2, 5, 5, 2, 6, 195 2, 3, 6, 6, 3, 7, 196 3, 0, 7, 7, 0, 4, 197 4, 5, 7, 7, 5, 6 198 }; 199 static const int kNumTris = 10; 200 201 SkScalar bary[3]; 202 for (int i = 0; i < kNumTris; ++i) { 203 int i0 = kFrameTris[i * 3]; 204 int i1 = kFrameTris[i * 3 + 1]; 205 int i2 = kFrameTris[i * 3 + 2]; 206 207 SkPoint t0 = i0 >= 4 ? inner[i0 - 4] : outer[i0]; 208 SkPoint t1 = i1 >= 4 ? inner[i1 - 4] : outer[i1]; 209 SkPoint t2 = i2 >= 4 ? inner[i2 - 4] : outer[i2]; 210 if (inside_triangle(point, t0, t1, t2, bary)) { 211 // Calculate coverage by barycentric interpolation of coverages 212 SkScalar c0 = i0 >= 4 ? innerCoverages[i0 - 4] : outerCoverages[i0]; 213 SkScalar c1 = i1 >= 4 ? innerCoverages[i1 - 4] : outerCoverages[i1]; 214 SkScalar c2 = i2 >= 4 ? innerCoverages[i2 - 4] : outerCoverages[i2]; 215 216 return bary[0] * c0 + bary[1] * c1 + bary[2] * c2; 217 } 218 } 219 // Not inside any triangle 220 return 0.f; 221 } 222 223 static constexpr SkScalar kViewScale = 100.f; 224 static constexpr SkScalar kViewOffset = 200.f; 225 226 class DegenerateQuadSample : public Sample { 227 public: 228 DegenerateQuadSample(const SkRect& rect) 229 : fOuterRect(rect) 230 , fCoverageMode(CoverageMode::kArea) { 231 fOuterRect.toQuad(fCorners); 232 for (int i = 0; i < 4; ++i) { 233 fEdgeAA[i] = true; 234 } 235 } 236 237 void onDrawContent(SkCanvas* canvas) override { 238 static const SkScalar kDotParams[2] = {1.f / kViewScale, 12.f / kViewScale}; 239 sk_sp<SkPathEffect> dots = SkDashPathEffect::Make(kDotParams, 2, 0.f); 240 static const SkScalar kDashParams[2] = {8.f / kViewScale, 12.f / kViewScale}; 241 sk_sp<SkPathEffect> dashes = SkDashPathEffect::Make(kDashParams, 2, 0.f); 242 243 SkPaint circlePaint; 244 circlePaint.setAntiAlias(true); 245 246 SkPaint linePaint; 247 linePaint.setAntiAlias(true); 248 linePaint.setStyle(SkPaint::kStroke_Style); 249 linePaint.setStrokeWidth(4.f / kViewScale); 250 linePaint.setStrokeJoin(SkPaint::kRound_Join); 251 linePaint.setStrokeCap(SkPaint::kRound_Cap); 252 253 canvas->translate(kViewOffset, kViewOffset); 254 canvas->scale(kViewScale, kViewScale); 255 256 // Draw the outer rectangle as a dotted line 257 linePaint.setPathEffect(dots); 258 canvas->drawRect(fOuterRect, linePaint); 259 260 bool valid = this->isValid(); 261 262 if (valid) { 263 SkPoint outsets[8]; 264 SkPoint insets[8]; 265 // Calculate inset and outset lines for edge-distance visualization 266 for (int i = 0; i < 4; ++i) { 267 make_aa_line(fCorners[i], fCorners[(i + 1) % 4], fEdgeAA[i], true, outsets + i * 2); 268 make_aa_line(fCorners[i], fCorners[(i + 1) % 4], fEdgeAA[i], false, insets + i * 2); 269 } 270 271 // Calculate inner and outer meshes for GPU visualization 272 SkPoint gpuOutset[4]; 273 SkScalar gpuOutsetCoverage[4]; 274 SkPoint gpuInset[4]; 275 SkScalar gpuInsetCoverage[4]; 276 this->getTessellatedPoints(gpuInset, gpuInsetCoverage, gpuOutset, gpuOutsetCoverage); 277 278 // Visualize the coverage values across the clamping rectangle, but test pixels outside 279 // of the "outer" rect since some quad edges can be outset extra far. 280 SkPaint pixelPaint; 281 pixelPaint.setAntiAlias(true); 282 SkRect covRect = fOuterRect.makeOutset(2.f, 2.f); 283 for (SkScalar py = covRect.fTop; py < covRect.fBottom; py += 1.f) { 284 for (SkScalar px = covRect.fLeft; px < covRect.fRight; px += 1.f) { 285 // px and py are the top-left corner of the current pixel, so get center's 286 // coordinate 287 SkPoint pixelCenter = {px + 0.5f, py + 0.5f}; 288 SkScalar coverage; 289 if (fCoverageMode == CoverageMode::kArea) { 290 coverage = get_area_coverage(fEdgeAA, fCorners, pixelCenter); 291 } else if (fCoverageMode == CoverageMode::kEdgeDistance) { 292 coverage = get_edge_dist_coverage(fEdgeAA, fCorners, outsets, insets, 293 pixelCenter); 294 } else { 295 SkASSERT(fCoverageMode == CoverageMode::kGPUMesh); 296 coverage = get_framed_coverage(gpuOutset, gpuOutsetCoverage, 297 gpuInset, gpuInsetCoverage, pixelCenter); 298 } 299 300 SkRect pixelRect = SkRect::MakeXYWH(px, py, 1.f, 1.f); 301 pixelRect.inset(0.1f, 0.1f); 302 303 SkScalar a = 1.f - 0.5f * coverage; 304 pixelPaint.setColor4f({a, a, a, 1.f}, nullptr); 305 canvas->drawRect(pixelRect, pixelPaint); 306 307 pixelPaint.setColor(coverage > 0.f ? SK_ColorGREEN : SK_ColorRED); 308 pixelRect.inset(0.38f, 0.38f); 309 canvas->drawRect(pixelRect, pixelPaint); 310 } 311 } 312 313 linePaint.setPathEffect(dashes); 314 // Draw the inset/outset "infinite" lines 315 if (fCoverageMode == CoverageMode::kEdgeDistance) { 316 for (int i = 0; i < 4; ++i) { 317 if (fEdgeAA[i]) { 318 linePaint.setColor(SK_ColorBLUE); 319 draw_extended_line(canvas, linePaint, outsets[i * 2], outsets[i * 2 + 1]); 320 linePaint.setColor(SK_ColorGREEN); 321 draw_extended_line(canvas, linePaint, insets[i * 2], insets[i * 2 + 1]); 322 } else { 323 // Both outset and inset are the same line, so only draw one in cyan 324 linePaint.setColor(SK_ColorCYAN); 325 draw_extended_line(canvas, linePaint, outsets[i * 2], outsets[i * 2 + 1]); 326 } 327 } 328 } 329 330 linePaint.setPathEffect(nullptr); 331 // What is tessellated using GrQuadPerEdgeAA 332 if (fCoverageMode == CoverageMode::kGPUMesh) { 333 SkPath outsetPath; 334 outsetPath.addPoly(gpuOutset, 4, true); 335 linePaint.setColor(SK_ColorBLUE); 336 canvas->drawPath(outsetPath, linePaint); 337 338 SkPath insetPath; 339 insetPath.addPoly(gpuInset, 4, true); 340 linePaint.setColor(SK_ColorGREEN); 341 canvas->drawPath(insetPath, linePaint); 342 } 343 344 // Draw the edges of the true quad as a solid line 345 SkPath path; 346 path.addPoly(fCorners, 4, true); 347 linePaint.setColor(SK_ColorBLACK); 348 canvas->drawPath(path, linePaint); 349 } else { 350 // Draw the edges of the true quad as a solid *red* line 351 SkPath path; 352 path.addPoly(fCorners, 4, true); 353 linePaint.setColor(SK_ColorRED); 354 linePaint.setPathEffect(nullptr); 355 canvas->drawPath(path, linePaint); 356 } 357 358 // Draw the four clickable corners as circles 359 circlePaint.setColor(valid ? SK_ColorBLACK : SK_ColorRED); 360 for (int i = 0; i < 4; ++i) { 361 canvas->drawCircle(fCorners[i], 5.f / kViewScale, circlePaint); 362 } 363 } 364 365 Sample::Click* onFindClickHandler(SkScalar x, SkScalar y, 366 unsigned) override; 367 bool onClick(Sample::Click*) override; 368 bool onQuery(Sample::Event* evt) override; 369 370 private: 371 class Click; 372 373 enum class CoverageMode { 374 kArea, kEdgeDistance, kGPUMesh 375 }; 376 377 const SkRect fOuterRect; 378 SkPoint fCorners[4]; // TL, TR, BR, BL 379 bool fEdgeAA[4]; // T, R, B, L 380 CoverageMode fCoverageMode; 381 382 bool isValid() const { 383 SkPath path; 384 path.addPoly(fCorners, 4, true); 385 return path.isConvex(); 386 } 387 388 void getTessellatedPoints(SkPoint inset[4], SkScalar insetCoverage[4], SkPoint outset[4], 389 SkScalar outsetCoverage[4]) const { 390 // Fixed vertex spec for extracting the picture frame geometry 391 static const GrQuadPerEdgeAA::VertexSpec kSpec = 392 {GrQuadType::kStandard, GrQuadPerEdgeAA::ColorType::kNone, 393 GrQuadType::kRect, false, GrQuadPerEdgeAA::Domain::kNo, 394 GrAAType::kCoverage, false}; 395 static const GrPerspQuad kIgnored(SkRect::MakeEmpty()); 396 397 GrQuadAAFlags flags = GrQuadAAFlags::kNone; 398 flags |= fEdgeAA[0] ? GrQuadAAFlags::kTop : GrQuadAAFlags::kNone; 399 flags |= fEdgeAA[1] ? GrQuadAAFlags::kRight : GrQuadAAFlags::kNone; 400 flags |= fEdgeAA[2] ? GrQuadAAFlags::kBottom : GrQuadAAFlags::kNone; 401 flags |= fEdgeAA[3] ? GrQuadAAFlags::kLeft : GrQuadAAFlags::kNone; 402 403 GrPerspQuad quad = GrPerspQuad::MakeFromSkQuad(fCorners, SkMatrix::I()); 404 405 float vertices[24]; // 2 quads, with x, y, and coverage 406 GrQuadPerEdgeAA::Tessellate(vertices, kSpec, quad, {1.f, 1.f, 1.f, 1.f}, 407 GrPerspQuad(SkRect::MakeEmpty()), SkRect::MakeEmpty(), flags); 408 409 // The first quad in vertices is the inset, then the outset, but they 410 // are ordered TL, BL, TR, BR so un-interleave coverage and re-arrange 411 inset[0] = {vertices[0], vertices[1]}; // TL 412 insetCoverage[0] = vertices[2]; 413 inset[3] = {vertices[3], vertices[4]}; // BL 414 insetCoverage[3] = vertices[5]; 415 inset[1] = {vertices[6], vertices[7]}; // TR 416 insetCoverage[1] = vertices[8]; 417 inset[2] = {vertices[9], vertices[10]}; // BR 418 insetCoverage[2] = vertices[11]; 419 420 outset[0] = {vertices[12], vertices[13]}; // TL 421 outsetCoverage[0] = vertices[14]; 422 outset[3] = {vertices[15], vertices[16]}; // BL 423 outsetCoverage[3] = vertices[17]; 424 outset[1] = {vertices[18], vertices[19]}; // TR 425 outsetCoverage[1] = vertices[20]; 426 outset[2] = {vertices[21], vertices[22]}; // BR 427 outsetCoverage[2] = vertices[23]; 428 } 429 430 typedef Sample INHERITED; 431 }; 432 433 class DegenerateQuadSample::Click : public Sample::Click { 434 public: 435 Click(Sample* target, const SkRect& clamp, int index) 436 : Sample::Click(target) 437 , fOuterRect(clamp) 438 , fIndex(index) {} 439 440 void doClick(SkPoint points[4]) { 441 if (fIndex >= 0) { 442 this->drag(&points[fIndex]); 443 } else { 444 for (int i = 0; i < 4; ++i) { 445 this->drag(&points[i]); 446 } 447 } 448 } 449 450 private: 451 SkRect fOuterRect; 452 int fIndex; 453 454 void drag(SkPoint* point) { 455 SkIPoint delta = fICurr - fIPrev; 456 *point += SkPoint::Make(delta.x() / kViewScale, delta.y() / kViewScale); 457 point->fX = SkMinScalar(fOuterRect.fRight, SkMaxScalar(point->fX, fOuterRect.fLeft)); 458 point->fY = SkMinScalar(fOuterRect.fBottom, SkMaxScalar(point->fY, fOuterRect.fTop)); 459 } 460 }; 461 462 Sample::Click* DegenerateQuadSample::onFindClickHandler(SkScalar x, SkScalar y, unsigned) { 463 SkPoint inCTM = SkPoint::Make((x - kViewOffset) / kViewScale, (y - kViewOffset) / kViewScale); 464 for (int i = 0; i < 4; ++i) { 465 if ((fCorners[i] - inCTM).length() < 10.f / kViewScale) { 466 return new Click(this, fOuterRect, i); 467 } 468 } 469 return new Click(this, fOuterRect, -1); 470 } 471 472 bool DegenerateQuadSample::onClick(Sample::Click* click) { 473 Click* myClick = (Click*) click; 474 myClick->doClick(fCorners); 475 return true; 476 } 477 478 bool DegenerateQuadSample::onQuery(Sample::Event* event) { 479 if (Sample::TitleQ(*event)) { 480 Sample::TitleR(event, "DegenerateQuad"); 481 return true; 482 } 483 SkUnichar code; 484 if (Sample::CharQ(*event, &code)) { 485 switch(code) { 486 case '1': 487 fEdgeAA[0] = !fEdgeAA[0]; 488 return true; 489 case '2': 490 fEdgeAA[1] = !fEdgeAA[1]; 491 return true; 492 case '3': 493 fEdgeAA[2] = !fEdgeAA[2]; 494 return true; 495 case '4': 496 fEdgeAA[3] = !fEdgeAA[3]; 497 return true; 498 case 'q': 499 fCoverageMode = CoverageMode::kArea; 500 return true; 501 case 'w': 502 fCoverageMode = CoverageMode::kEdgeDistance; 503 return true; 504 case 'e': 505 fCoverageMode = CoverageMode::kGPUMesh; 506 return true; 507 } 508 } 509 return this->INHERITED::onQuery(event); 510 } 511 512 DEF_SAMPLE(return new DegenerateQuadSample(SkRect::MakeWH(4.f, 4.f));) 513