1 /* 2 * Copyright 2017 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 "SkShadowTessellator.h" 9 #include "SkColorData.h" 10 #include "SkDrawShadowInfo.h" 11 #include "SkGeometry.h" 12 #include "SkInsetConvexPolygon.h" 13 #include "SkPath.h" 14 #include "SkPoint3.h" 15 #include "SkPointPriv.h" 16 #include "SkVertices.h" 17 18 #if SK_SUPPORT_GPU 19 #include "GrPathUtils.h" 20 #endif 21 22 23 /** 24 * Base class 25 */ 26 class SkBaseShadowTessellator { 27 public: 28 SkBaseShadowTessellator(const SkPoint3& zPlaneParams, bool transparent); 29 virtual ~SkBaseShadowTessellator() {} 30 31 sk_sp<SkVertices> releaseVertices() { 32 if (!fSucceeded) { 33 return nullptr; 34 } 35 return SkVertices::MakeCopy(SkVertices::kTriangles_VertexMode, this->vertexCount(), 36 fPositions.begin(), nullptr, fColors.begin(), 37 this->indexCount(), fIndices.begin()); 38 } 39 40 protected: 41 static constexpr auto kMinHeight = 0.1f; 42 43 int vertexCount() const { return fPositions.count(); } 44 int indexCount() const { return fIndices.count(); } 45 46 bool setZOffset(const SkRect& bounds, bool perspective); 47 48 virtual void handleLine(const SkPoint& p) = 0; 49 void handleLine(const SkMatrix& m, SkPoint* p); 50 51 void handleQuad(const SkPoint pts[3]); 52 void handleQuad(const SkMatrix& m, SkPoint pts[3]); 53 54 void handleCubic(const SkMatrix& m, SkPoint pts[4]); 55 56 void handleConic(const SkMatrix& m, SkPoint pts[3], SkScalar w); 57 58 bool setTransformedHeightFunc(const SkMatrix& ctm); 59 60 bool addArc(const SkVector& nextNormal, bool finishArc); 61 62 SkScalar heightFunc(SkScalar x, SkScalar y) { 63 return fZPlaneParams.fX*x + fZPlaneParams.fY*y + fZPlaneParams.fZ; 64 } 65 66 SkPoint3 fZPlaneParams; 67 std::function<SkScalar(const SkPoint&)> fTransformedHeightFunc; 68 SkScalar fZOffset; 69 // members for perspective height function 70 SkPoint3 fTransformedZParams; 71 SkScalar fPartialDeterminants[3]; 72 73 // first two points 74 SkTDArray<SkPoint> fInitPoints; 75 // temporary buffer 76 SkTDArray<SkPoint> fPointBuffer; 77 78 SkTDArray<SkPoint> fPositions; 79 SkTDArray<SkColor> fColors; 80 SkTDArray<uint16_t> fIndices; 81 82 int fFirstVertexIndex; 83 SkVector fFirstOutset; 84 SkPoint fFirstPoint; 85 86 bool fSucceeded; 87 bool fTransparent; 88 89 SkColor fUmbraColor; 90 SkColor fPenumbraColor; 91 92 SkScalar fRadius; 93 SkScalar fDirection; 94 int fPrevUmbraIndex; 95 SkVector fPrevOutset; 96 SkPoint fPrevPoint; 97 }; 98 99 static bool compute_normal(const SkPoint& p0, const SkPoint& p1, SkScalar dir, 100 SkVector* newNormal) { 101 SkVector normal; 102 // compute perpendicular 103 normal.fX = p0.fY - p1.fY; 104 normal.fY = p1.fX - p0.fX; 105 normal *= dir; 106 if (!normal.normalize()) { 107 return false; 108 } 109 *newNormal = normal; 110 return true; 111 } 112 113 static void compute_radial_steps(const SkVector& v1, const SkVector& v2, SkScalar r, 114 SkScalar* rotSin, SkScalar* rotCos, int* n) { 115 const SkScalar kRecipPixelsPerArcSegment = 0.125f; 116 117 SkScalar rCos = v1.dot(v2); 118 SkScalar rSin = v1.cross(v2); 119 SkScalar theta = SkScalarATan2(rSin, rCos); 120 121 int steps = SkScalarFloorToInt(r*theta*kRecipPixelsPerArcSegment); 122 123 SkScalar dTheta = theta / steps; 124 *rotSin = SkScalarSinCos(dTheta, rotCos); 125 *n = steps; 126 } 127 128 SkBaseShadowTessellator::SkBaseShadowTessellator(const SkPoint3& zPlaneParams, bool transparent) 129 : fZPlaneParams(zPlaneParams) 130 , fZOffset(0) 131 , fFirstVertexIndex(-1) 132 , fSucceeded(false) 133 , fTransparent(transparent) 134 , fDirection(1) 135 , fPrevUmbraIndex(-1) { 136 fInitPoints.setReserve(3); 137 138 // child classes will set reserve for positions, colors and indices 139 } 140 141 bool SkBaseShadowTessellator::setZOffset(const SkRect& bounds, bool perspective) { 142 SkScalar minZ = this->heightFunc(bounds.fLeft, bounds.fTop); 143 if (perspective) { 144 SkScalar z = this->heightFunc(bounds.fLeft, bounds.fBottom); 145 if (z < minZ) { 146 minZ = z; 147 } 148 z = this->heightFunc(bounds.fRight, bounds.fTop); 149 if (z < minZ) { 150 minZ = z; 151 } 152 z = this->heightFunc(bounds.fRight, bounds.fBottom); 153 if (z < minZ) { 154 minZ = z; 155 } 156 } 157 158 if (minZ < kMinHeight) { 159 fZOffset = -minZ + kMinHeight; 160 return true; 161 } 162 163 return false; 164 } 165 166 // tesselation tolerance values, in device space pixels 167 #if SK_SUPPORT_GPU 168 static const SkScalar kQuadTolerance = 0.2f; 169 static const SkScalar kCubicTolerance = 0.2f; 170 #endif 171 static const SkScalar kConicTolerance = 0.5f; 172 173 void SkBaseShadowTessellator::handleLine(const SkMatrix& m, SkPoint* p) { 174 m.mapPoints(p, 1); 175 this->handleLine(*p); 176 } 177 178 void SkBaseShadowTessellator::handleQuad(const SkPoint pts[3]) { 179 #if SK_SUPPORT_GPU 180 // TODO: Pull PathUtils out of Ganesh? 181 int maxCount = GrPathUtils::quadraticPointCount(pts, kQuadTolerance); 182 fPointBuffer.setReserve(maxCount); 183 SkPoint* target = fPointBuffer.begin(); 184 int count = GrPathUtils::generateQuadraticPoints(pts[0], pts[1], pts[2], 185 kQuadTolerance, &target, maxCount); 186 fPointBuffer.setCount(count); 187 for (int i = 0; i < count; i++) { 188 this->handleLine(fPointBuffer[i]); 189 } 190 #else 191 // for now, just to draw something 192 this->handleLine(pts[1]); 193 this->handleLine(pts[2]); 194 #endif 195 } 196 197 void SkBaseShadowTessellator::handleQuad(const SkMatrix& m, SkPoint pts[3]) { 198 m.mapPoints(pts, 3); 199 this->handleQuad(pts); 200 } 201 202 void SkBaseShadowTessellator::handleCubic(const SkMatrix& m, SkPoint pts[4]) { 203 m.mapPoints(pts, 4); 204 #if SK_SUPPORT_GPU 205 // TODO: Pull PathUtils out of Ganesh? 206 int maxCount = GrPathUtils::cubicPointCount(pts, kCubicTolerance); 207 fPointBuffer.setReserve(maxCount); 208 SkPoint* target = fPointBuffer.begin(); 209 int count = GrPathUtils::generateCubicPoints(pts[0], pts[1], pts[2], pts[3], 210 kCubicTolerance, &target, maxCount); 211 fPointBuffer.setCount(count); 212 for (int i = 0; i < count; i++) { 213 this->handleLine(fPointBuffer[i]); 214 } 215 #else 216 // for now, just to draw something 217 this->handleLine(pts[1]); 218 this->handleLine(pts[2]); 219 this->handleLine(pts[3]); 220 #endif 221 } 222 223 void SkBaseShadowTessellator::handleConic(const SkMatrix& m, SkPoint pts[3], SkScalar w) { 224 if (m.hasPerspective()) { 225 w = SkConic::TransformW(pts, w, m); 226 } 227 m.mapPoints(pts, 3); 228 SkAutoConicToQuads quadder; 229 const SkPoint* quads = quadder.computeQuads(pts, w, kConicTolerance); 230 SkPoint lastPoint = *(quads++); 231 int count = quadder.countQuads(); 232 for (int i = 0; i < count; ++i) { 233 SkPoint quadPts[3]; 234 quadPts[0] = lastPoint; 235 quadPts[1] = quads[0]; 236 quadPts[2] = i == count - 1 ? pts[2] : quads[1]; 237 this->handleQuad(quadPts); 238 lastPoint = quadPts[2]; 239 quads += 2; 240 } 241 } 242 243 bool SkBaseShadowTessellator::addArc(const SkVector& nextNormal, bool finishArc) { 244 // fill in fan from previous quad 245 SkScalar rotSin, rotCos; 246 int numSteps; 247 compute_radial_steps(fPrevOutset, nextNormal, fRadius, &rotSin, &rotCos, &numSteps); 248 SkVector prevNormal = fPrevOutset; 249 for (int i = 0; i < numSteps-1; ++i) { 250 SkVector currNormal; 251 currNormal.fX = prevNormal.fX*rotCos - prevNormal.fY*rotSin; 252 currNormal.fY = prevNormal.fY*rotCos + prevNormal.fX*rotSin; 253 *fPositions.push() = fPrevPoint + currNormal; 254 *fColors.push() = fPenumbraColor; 255 *fIndices.push() = fPrevUmbraIndex; 256 *fIndices.push() = fPositions.count() - 1; 257 *fIndices.push() = fPositions.count() - 2; 258 259 prevNormal = currNormal; 260 } 261 if (finishArc && numSteps) { 262 *fPositions.push() = fPrevPoint + nextNormal; 263 *fColors.push() = fPenumbraColor; 264 *fIndices.push() = fPrevUmbraIndex; 265 *fIndices.push() = fPositions.count() - 1; 266 *fIndices.push() = fPositions.count() - 2; 267 } 268 fPrevOutset = nextNormal; 269 270 return (numSteps > 0); 271 } 272 273 bool SkBaseShadowTessellator::setTransformedHeightFunc(const SkMatrix& ctm) { 274 if (SkScalarNearlyZero(fZPlaneParams.fX) && SkScalarNearlyZero(fZPlaneParams.fY)) { 275 fTransformedHeightFunc = [this](const SkPoint& p) { 276 return fZPlaneParams.fZ; 277 }; 278 } else { 279 SkMatrix ctmInverse; 280 if (!ctm.invert(&ctmInverse)) { 281 return false; 282 } 283 // multiply by transpose 284 fTransformedZParams = SkPoint3::Make( 285 ctmInverse[SkMatrix::kMScaleX] * fZPlaneParams.fX + 286 ctmInverse[SkMatrix::kMSkewY] * fZPlaneParams.fY + 287 ctmInverse[SkMatrix::kMPersp0] * fZPlaneParams.fZ, 288 289 ctmInverse[SkMatrix::kMSkewX] * fZPlaneParams.fX + 290 ctmInverse[SkMatrix::kMScaleY] * fZPlaneParams.fY + 291 ctmInverse[SkMatrix::kMPersp1] * fZPlaneParams.fZ, 292 293 ctmInverse[SkMatrix::kMTransX] * fZPlaneParams.fX + 294 ctmInverse[SkMatrix::kMTransY] * fZPlaneParams.fY + 295 ctmInverse[SkMatrix::kMPersp2] * fZPlaneParams.fZ 296 ); 297 298 if (ctm.hasPerspective()) { 299 // We use Cramer's rule to solve for the W value for a given post-divide X and Y, 300 // so pre-compute those values that are independent of X and Y. 301 // W is det(ctmInverse)/(PD[0]*X + PD[1]*Y + PD[2]) 302 fPartialDeterminants[0] = ctm[SkMatrix::kMSkewY] * ctm[SkMatrix::kMPersp1] - 303 ctm[SkMatrix::kMScaleY] * ctm[SkMatrix::kMPersp0]; 304 fPartialDeterminants[1] = ctm[SkMatrix::kMPersp0] * ctm[SkMatrix::kMSkewX] - 305 ctm[SkMatrix::kMPersp1] * ctm[SkMatrix::kMScaleX]; 306 fPartialDeterminants[2] = ctm[SkMatrix::kMScaleX] * ctm[SkMatrix::kMScaleY] - 307 ctm[SkMatrix::kMSkewX] * ctm[SkMatrix::kMSkewY]; 308 SkScalar ctmDeterminant = ctm[SkMatrix::kMTransX] * fPartialDeterminants[0] + 309 ctm[SkMatrix::kMTransY] * fPartialDeterminants[1] + 310 ctm[SkMatrix::kMPersp2] * fPartialDeterminants[2]; 311 312 // Pre-bake the numerator of Cramer's rule into the zParams to avoid another multiply. 313 // TODO: this may introduce numerical instability, but I haven't seen any issues yet. 314 fTransformedZParams.fX *= ctmDeterminant; 315 fTransformedZParams.fY *= ctmDeterminant; 316 fTransformedZParams.fZ *= ctmDeterminant; 317 318 fTransformedHeightFunc = [this](const SkPoint& p) { 319 SkScalar denom = p.fX * fPartialDeterminants[0] + 320 p.fY * fPartialDeterminants[1] + 321 fPartialDeterminants[2]; 322 SkScalar w = SkScalarFastInvert(denom); 323 return fZOffset + w*(fTransformedZParams.fX * p.fX + 324 fTransformedZParams.fY * p.fY + 325 fTransformedZParams.fZ); 326 }; 327 } else { 328 fTransformedHeightFunc = [this](const SkPoint& p) { 329 return fZOffset + fTransformedZParams.fX * p.fX + 330 fTransformedZParams.fY * p.fY + fTransformedZParams.fZ; 331 }; 332 } 333 } 334 335 return true; 336 } 337 338 339 ////////////////////////////////////////////////////////////////////////////////////////////////// 340 341 class SkAmbientShadowTessellator : public SkBaseShadowTessellator { 342 public: 343 SkAmbientShadowTessellator(const SkPath& path, const SkMatrix& ctm, 344 const SkPoint3& zPlaneParams, bool transparent); 345 346 private: 347 void handleLine(const SkPoint& p) override; 348 void addEdge(const SkVector& nextPoint, const SkVector& nextNormal); 349 350 static constexpr auto kMaxEdgeLenSqr = 20 * 20; 351 static constexpr auto kInsetFactor = -0.5f; 352 353 SkScalar offset(SkScalar z) { 354 return SkDrawShadowMetrics::AmbientBlurRadius(z); 355 } 356 SkColor umbraColor(SkScalar z) { 357 SkScalar umbraAlpha = SkScalarInvert(SkDrawShadowMetrics::AmbientRecipAlpha(z)); 358 return SkColorSetARGB(umbraAlpha * 255.9999f, 0, 0, 0); 359 } 360 361 int fCentroidCount; 362 bool fSplitFirstEdge; 363 bool fSplitPreviousEdge; 364 365 typedef SkBaseShadowTessellator INHERITED; 366 }; 367 368 SkAmbientShadowTessellator::SkAmbientShadowTessellator(const SkPath& path, 369 const SkMatrix& ctm, 370 const SkPoint3& zPlaneParams, 371 bool transparent) 372 : INHERITED(zPlaneParams, transparent) 373 , fSplitFirstEdge(false) 374 , fSplitPreviousEdge(false) { 375 // Set base colors 376 SkScalar umbraAlpha = SkScalarInvert(SkDrawShadowMetrics::AmbientRecipAlpha(heightFunc(0, 0))); 377 // umbraColor is the interior value, penumbraColor the exterior value. 378 // umbraAlpha is the factor that is linearly interpolated from outside to inside, and 379 // then "blurred" by the GrBlurredEdgeFP. It is then multiplied by fAmbientAlpha to get 380 // the final alpha. 381 fUmbraColor = SkColorSetARGB(umbraAlpha * 255.9999f, 0, 0, 0); 382 fPenumbraColor = SkColorSetARGB(0, 0, 0, 0); 383 384 // make sure we're not below the canvas plane 385 this->setZOffset(path.getBounds(), ctm.hasPerspective()); 386 387 this->setTransformedHeightFunc(ctm); 388 389 // Outer ring: 3*numPts 390 // Middle ring: numPts 391 fPositions.setReserve(4 * path.countPoints()); 392 fColors.setReserve(4 * path.countPoints()); 393 // Outer ring: 12*numPts 394 // Middle ring: 0 395 fIndices.setReserve(12 * path.countPoints()); 396 397 // walk around the path, tessellate and generate outer ring 398 // if original path is transparent, will accumulate sum of points for centroid 399 SkPath::Iter iter(path, true); 400 SkPoint pts[4]; 401 SkPath::Verb verb; 402 if (fTransparent) { 403 *fPositions.push() = SkPoint::Make(0, 0); 404 *fColors.push() = fUmbraColor; 405 fCentroidCount = 0; 406 } 407 while ((verb = iter.next(pts)) != SkPath::kDone_Verb) { 408 switch (verb) { 409 case SkPath::kLine_Verb: 410 this->INHERITED::handleLine(ctm, &pts[1]); 411 break; 412 case SkPath::kQuad_Verb: 413 this->handleQuad(ctm, pts); 414 break; 415 case SkPath::kCubic_Verb: 416 this->handleCubic(ctm, pts); 417 break; 418 case SkPath::kConic_Verb: 419 this->handleConic(ctm, pts, iter.conicWeight()); 420 break; 421 case SkPath::kMove_Verb: 422 case SkPath::kClose_Verb: 423 case SkPath::kDone_Verb: 424 break; 425 } 426 } 427 428 if (!this->indexCount()) { 429 return; 430 } 431 432 // Finish up 433 SkVector normal; 434 if (compute_normal(fPrevPoint, fFirstPoint, fDirection, &normal)) { 435 SkScalar z = fTransformedHeightFunc(fPrevPoint); 436 fRadius = this->offset(z); 437 SkVector scaledNormal(normal); 438 scaledNormal *= fRadius; 439 this->addArc(scaledNormal, true); 440 441 // fix-up the last and first umbra points 442 SkVector inset = normal; 443 // adding to an average, so multiply by an additional half 444 inset *= 0.5f*kInsetFactor; 445 fPositions[fPrevUmbraIndex] += inset; 446 fPositions[fFirstVertexIndex] += inset; 447 // we multiply by another half because now we're adding to an average of an average 448 inset *= 0.5f; 449 if (fSplitPreviousEdge) { 450 fPositions[fPrevUmbraIndex - 2] += inset; 451 } 452 if (fSplitFirstEdge) { 453 fPositions[fFirstVertexIndex + 2] += inset; 454 } 455 456 // set up for final edge 457 z = fTransformedHeightFunc(fFirstPoint); 458 normal *= this->offset(z); 459 460 // make sure we don't end up with a sharp alpha edge along the quad diagonal 461 if (fColors[fPrevUmbraIndex] != fColors[fFirstVertexIndex] && 462 SkPointPriv::DistanceToSqd(fFirstPoint, fPositions[fPrevUmbraIndex]) > kMaxEdgeLenSqr) { 463 SkPoint centerPoint = fPositions[fPrevUmbraIndex] + fPositions[fFirstVertexIndex]; 464 centerPoint *= 0.5f; 465 *fPositions.push() = centerPoint; 466 *fColors.push() = SkPMLerp(fColors[fFirstVertexIndex], fColors[fPrevUmbraIndex], 128); 467 centerPoint = fPositions[fPositions.count()-2] + fPositions[fFirstVertexIndex+1]; 468 centerPoint *= 0.5f; 469 *fPositions.push() = centerPoint; 470 *fColors.push() = fPenumbraColor; 471 472 if (fColors[fPrevUmbraIndex] > fColors[fPositions.count() - 2]) { 473 *fIndices.push() = fPrevUmbraIndex; 474 *fIndices.push() = fPositions.count() - 3; 475 *fIndices.push() = fPositions.count() - 2; 476 477 *fIndices.push() = fPositions.count() - 3; 478 *fIndices.push() = fPositions.count() - 1; 479 *fIndices.push() = fPositions.count() - 2; 480 } else { 481 *fIndices.push() = fPrevUmbraIndex; 482 *fIndices.push() = fPositions.count() - 2; 483 *fIndices.push() = fPositions.count() - 1; 484 485 *fIndices.push() = fPrevUmbraIndex; 486 *fIndices.push() = fPositions.count() - 1; 487 *fIndices.push() = fPositions.count() - 3; 488 } 489 490 // if transparent, add point to first one in array and add to center fan 491 if (fTransparent) { 492 fPositions[0] += centerPoint; 493 ++fCentroidCount; 494 495 *fIndices.push() = 0; 496 *fIndices.push() = fPrevUmbraIndex; 497 *fIndices.push() = fPositions.count() - 2; 498 } 499 500 fPrevUmbraIndex = fPositions.count() - 2; 501 } 502 503 // final edge 504 *fPositions.push() = fFirstPoint + normal; 505 *fColors.push() = fPenumbraColor; 506 507 if (fColors[fPrevUmbraIndex] > fColors[fFirstVertexIndex]) { 508 *fIndices.push() = fPrevUmbraIndex; 509 *fIndices.push() = fPositions.count() - 2; 510 *fIndices.push() = fFirstVertexIndex; 511 512 *fIndices.push() = fPositions.count() - 2; 513 *fIndices.push() = fPositions.count() - 1; 514 *fIndices.push() = fFirstVertexIndex; 515 } else { 516 *fIndices.push() = fPrevUmbraIndex; 517 *fIndices.push() = fPositions.count() - 2; 518 *fIndices.push() = fPositions.count() - 1; 519 520 *fIndices.push() = fPrevUmbraIndex; 521 *fIndices.push() = fPositions.count() - 1; 522 *fIndices.push() = fFirstVertexIndex; 523 } 524 fPrevOutset = normal; 525 } 526 527 // finalize centroid 528 if (fTransparent) { 529 fPositions[0] *= SkScalarFastInvert(fCentroidCount); 530 fColors[0] = this->umbraColor(fTransformedHeightFunc(fPositions[0])); 531 532 *fIndices.push() = 0; 533 *fIndices.push() = fPrevUmbraIndex; 534 *fIndices.push() = fFirstVertexIndex; 535 } 536 537 // final fan 538 if (fPositions.count() >= 3) { 539 fPrevUmbraIndex = fFirstVertexIndex; 540 fPrevPoint = fFirstPoint; 541 fRadius = this->offset(fTransformedHeightFunc(fPrevPoint)); 542 if (this->addArc(fFirstOutset, false)) { 543 *fIndices.push() = fFirstVertexIndex; 544 *fIndices.push() = fPositions.count() - 1; 545 *fIndices.push() = fFirstVertexIndex + 1; 546 } else { 547 // arc is too small, set the first penumbra point to be the same position 548 // as the last one 549 fPositions[fFirstVertexIndex + 1] = fPositions[fPositions.count() - 1]; 550 } 551 } 552 fSucceeded = true; 553 } 554 555 void SkAmbientShadowTessellator::handleLine(const SkPoint& p) { 556 if (fInitPoints.count() < 2) { 557 *fInitPoints.push() = p; 558 return; 559 } 560 561 if (fInitPoints.count() == 2) { 562 // determine if cw or ccw 563 SkVector v0 = fInitPoints[1] - fInitPoints[0]; 564 SkVector v1 = p - fInitPoints[0]; 565 SkScalar perpDot = v0.fX*v1.fY - v0.fY*v1.fX; 566 if (SkScalarNearlyZero(perpDot)) { 567 // nearly parallel, just treat as straight line and continue 568 fInitPoints[1] = p; 569 return; 570 } 571 572 // if perpDot > 0, winding is ccw 573 fDirection = (perpDot > 0) ? -1 : 1; 574 575 // add first quad 576 SkVector normal; 577 if (!compute_normal(fInitPoints[0], fInitPoints[1], fDirection, &normal)) { 578 // first two points are incident, make the third point the second and continue 579 fInitPoints[1] = p; 580 return; 581 } 582 583 fFirstPoint = fInitPoints[0]; 584 fFirstVertexIndex = fPositions.count(); 585 SkScalar z = fTransformedHeightFunc(fFirstPoint); 586 fFirstOutset = normal; 587 fFirstOutset *= this->offset(z); 588 589 fPrevOutset = fFirstOutset; 590 fPrevPoint = fFirstPoint; 591 fPrevUmbraIndex = fFirstVertexIndex; 592 593 *fPositions.push() = fFirstPoint; 594 *fColors.push() = this->umbraColor(z); 595 *fPositions.push() = fFirstPoint + fFirstOutset; 596 *fColors.push() = fPenumbraColor; 597 if (fTransparent) { 598 fPositions[0] += fFirstPoint; 599 fCentroidCount = 1; 600 } 601 602 // add the first quad 603 z = fTransformedHeightFunc(fInitPoints[1]); 604 fRadius = this->offset(z); 605 fUmbraColor = this->umbraColor(z); 606 this->addEdge(fInitPoints[1], normal); 607 608 // to ensure we skip this block next time 609 *fInitPoints.push() = p; 610 } 611 612 SkVector normal; 613 if (compute_normal(fPrevPoint, p, fDirection, &normal)) { 614 SkVector scaledNormal = normal; 615 scaledNormal *= fRadius; 616 this->addArc(scaledNormal, true); 617 SkScalar z = fTransformedHeightFunc(p); 618 fRadius = this->offset(z); 619 fUmbraColor = this->umbraColor(z); 620 this->addEdge(p, normal); 621 } 622 } 623 624 void SkAmbientShadowTessellator::addEdge(const SkPoint& nextPoint, const SkVector& nextNormal) { 625 // We compute the inset in two stages: first we inset by half the current normal, 626 // then on the next addEdge() we add half of the next normal to get an average of the two 627 SkVector insetNormal = nextNormal; 628 insetNormal *= 0.5f*kInsetFactor; 629 630 // Adding the other half of the average for the previous edge 631 fPositions[fPrevUmbraIndex] += insetNormal; 632 633 SkPoint umbraPoint = nextPoint + insetNormal; 634 SkVector outsetNormal = nextNormal; 635 outsetNormal *= fRadius; 636 SkPoint penumbraPoint = nextPoint + outsetNormal; 637 638 // For split edges, we're adding an average of two averages, so we multiply by another half 639 if (fSplitPreviousEdge) { 640 insetNormal *= 0.5f; 641 fPositions[fPrevUmbraIndex - 2] += insetNormal; 642 } 643 644 // Split the edge to make sure we don't end up with a sharp alpha edge along the quad diagonal 645 if (fColors[fPrevUmbraIndex] != fUmbraColor && 646 SkPointPriv::DistanceToSqd(nextPoint, fPositions[fPrevUmbraIndex]) > kMaxEdgeLenSqr) { 647 648 // This is lacking 1/4 of the next inset -- we'll add it the next time we call addEdge() 649 SkPoint centerPoint = fPositions[fPrevUmbraIndex] + umbraPoint; 650 centerPoint *= 0.5f; 651 *fPositions.push() = centerPoint; 652 *fColors.push() = SkPMLerp(fUmbraColor, fColors[fPrevUmbraIndex], 128); 653 centerPoint = fPositions[fPositions.count()-2] + penumbraPoint; 654 centerPoint *= 0.5f; 655 *fPositions.push() = centerPoint; 656 *fColors.push() = fPenumbraColor; 657 658 // set triangularization to get best interpolation of color 659 if (fColors[fPrevUmbraIndex] > fColors[fPositions.count() - 2]) { 660 *fIndices.push() = fPrevUmbraIndex; 661 *fIndices.push() = fPositions.count() - 3; 662 *fIndices.push() = fPositions.count() - 2; 663 664 *fIndices.push() = fPositions.count() - 3; 665 *fIndices.push() = fPositions.count() - 1; 666 *fIndices.push() = fPositions.count() - 2; 667 } else { 668 *fIndices.push() = fPrevUmbraIndex; 669 *fIndices.push() = fPositions.count() - 2; 670 *fIndices.push() = fPositions.count() - 1; 671 672 *fIndices.push() = fPrevUmbraIndex; 673 *fIndices.push() = fPositions.count() - 1; 674 *fIndices.push() = fPositions.count() - 3; 675 } 676 677 // if transparent, add point to first one in array and add to center fan 678 if (fTransparent) { 679 fPositions[0] += centerPoint; 680 ++fCentroidCount; 681 682 *fIndices.push() = 0; 683 *fIndices.push() = fPrevUmbraIndex; 684 *fIndices.push() = fPositions.count() - 2; 685 } 686 687 fSplitPreviousEdge = true; 688 if (fPrevUmbraIndex == fFirstVertexIndex) { 689 fSplitFirstEdge = true; 690 } 691 fPrevUmbraIndex = fPositions.count() - 2; 692 } else { 693 fSplitPreviousEdge = false; 694 } 695 696 // add next quad 697 *fPositions.push() = umbraPoint; 698 *fColors.push() = fUmbraColor; 699 *fPositions.push() = penumbraPoint; 700 *fColors.push() = fPenumbraColor; 701 702 // set triangularization to get best interpolation of color 703 if (fColors[fPrevUmbraIndex] > fColors[fPositions.count() - 2]) { 704 *fIndices.push() = fPrevUmbraIndex; 705 *fIndices.push() = fPositions.count() - 3; 706 *fIndices.push() = fPositions.count() - 2; 707 708 *fIndices.push() = fPositions.count() - 3; 709 *fIndices.push() = fPositions.count() - 1; 710 *fIndices.push() = fPositions.count() - 2; 711 } else { 712 *fIndices.push() = fPrevUmbraIndex; 713 *fIndices.push() = fPositions.count() - 2; 714 *fIndices.push() = fPositions.count() - 1; 715 716 *fIndices.push() = fPrevUmbraIndex; 717 *fIndices.push() = fPositions.count() - 1; 718 *fIndices.push() = fPositions.count() - 3; 719 } 720 721 // if transparent, add point to first one in array and add to center fan 722 if (fTransparent) { 723 fPositions[0] += nextPoint; 724 ++fCentroidCount; 725 726 *fIndices.push() = 0; 727 *fIndices.push() = fPrevUmbraIndex; 728 *fIndices.push() = fPositions.count() - 2; 729 } 730 731 fPrevUmbraIndex = fPositions.count() - 2; 732 fPrevPoint = nextPoint; 733 fPrevOutset = outsetNormal; 734 } 735 736 /////////////////////////////////////////////////////////////////////////////////////////////////// 737 738 class SkSpotShadowTessellator : public SkBaseShadowTessellator { 739 public: 740 SkSpotShadowTessellator(const SkPath& path, const SkMatrix& ctm, 741 const SkPoint3& zPlaneParams, const SkPoint3& lightPos, 742 SkScalar lightRadius, bool transparent); 743 744 private: 745 void computeClipAndPathPolygons(const SkPath& path, const SkMatrix& ctm, 746 const SkMatrix& shadowTransform); 747 void computeClipVectorsAndTestCentroid(); 748 bool clipUmbraPoint(const SkPoint& umbraPoint, const SkPoint& centroid, SkPoint* clipPoint); 749 int getClosestUmbraPoint(const SkPoint& point); 750 751 void handleLine(const SkPoint& p) override; 752 bool handlePolyPoint(const SkPoint& p); 753 754 void mapPoints(SkScalar scale, const SkVector& xlate, SkPoint* pts, int count); 755 bool addInnerPoint(const SkPoint& pathPoint); 756 void addEdge(const SkVector& nextPoint, const SkVector& nextNormal); 757 758 SkScalar offset(SkScalar z) { 759 float zRatio = SkTPin(z / (fLightZ - z), 0.0f, 0.95f); 760 return fLightRadius*zRatio; 761 } 762 763 SkScalar fLightZ; 764 SkScalar fLightRadius; 765 SkScalar fOffsetAdjust; 766 767 SkTDArray<SkPoint> fClipPolygon; 768 SkTDArray<SkVector> fClipVectors; 769 SkPoint fCentroid; 770 SkScalar fArea; 771 772 SkTDArray<SkPoint> fPathPolygon; 773 SkTDArray<SkPoint> fUmbraPolygon; 774 int fCurrClipPoint; 775 int fCurrUmbraPoint; 776 bool fPrevUmbraOutside; 777 bool fFirstUmbraOutside; 778 bool fValidUmbra; 779 780 typedef SkBaseShadowTessellator INHERITED; 781 }; 782 783 SkSpotShadowTessellator::SkSpotShadowTessellator(const SkPath& path, const SkMatrix& ctm, 784 const SkPoint3& zPlaneParams, 785 const SkPoint3& lightPos, SkScalar lightRadius, 786 bool transparent) 787 : INHERITED(zPlaneParams, transparent) 788 , fLightZ(lightPos.fZ) 789 , fLightRadius(lightRadius) 790 , fOffsetAdjust(0) 791 , fCurrClipPoint(0) 792 , fPrevUmbraOutside(false) 793 , fFirstUmbraOutside(false) 794 , fValidUmbra(true) { 795 796 // make sure we're not below the canvas plane 797 if (this->setZOffset(path.getBounds(), ctm.hasPerspective())) { 798 // Adjust light height and radius 799 fLightRadius *= (fLightZ + fZOffset) / fLightZ; 800 fLightZ += fZOffset; 801 } 802 803 // Set radius and colors 804 SkPoint center = SkPoint::Make(path.getBounds().centerX(), path.getBounds().centerY()); 805 SkScalar occluderHeight = this->heightFunc(center.fX, center.fY) + fZOffset; 806 fUmbraColor = SkColorSetARGB(255, 0, 0, 0); 807 fPenumbraColor = SkColorSetARGB(0, 0, 0, 0); 808 809 // Compute the blur radius, scale and translation for the spot shadow. 810 SkScalar radius; 811 SkMatrix shadowTransform; 812 if (!ctm.hasPerspective()) { 813 SkScalar scale; 814 SkVector translate; 815 SkDrawShadowMetrics::GetSpotParams(occluderHeight, lightPos.fX, lightPos.fY, fLightZ, 816 lightRadius, &radius, &scale, &translate); 817 shadowTransform.setScaleTranslate(scale, scale, translate.fX, translate.fY); 818 } else { 819 // For perspective, we have a scale, a z-shear, and another projective divide -- 820 // this varies at each point so we can't use an affine transform. 821 // We'll just apply this to each generated point in turn. 822 shadowTransform.reset(); 823 // Also can't cull the center (for now). 824 fTransparent = true; 825 radius = SkDrawShadowMetrics::SpotBlurRadius(occluderHeight, lightPos.fZ, lightRadius); 826 } 827 fRadius = radius; 828 SkMatrix fullTransform = SkMatrix::Concat(shadowTransform, ctm); 829 830 // Set up our reverse mapping 831 this->setTransformedHeightFunc(fullTransform); 832 833 // TODO: calculate these reserves better 834 // Penumbra ring: 3*numPts 835 // Umbra ring: numPts 836 // Inner ring: numPts 837 fPositions.setReserve(5 * path.countPoints()); 838 fColors.setReserve(5 * path.countPoints()); 839 // Penumbra ring: 12*numPts 840 // Umbra ring: 3*numPts 841 fIndices.setReserve(15 * path.countPoints()); 842 fClipPolygon.setReserve(path.countPoints()); 843 844 // compute rough clip bounds for umbra, plus offset polygon, plus centroid 845 this->computeClipAndPathPolygons(path, ctm, shadowTransform); 846 if (fClipPolygon.count() < 3 || fPathPolygon.count() < 3) { 847 return; 848 } 849 850 // check to see if umbra collapses 851 SkScalar minDistSq = SkPointPriv::DistanceToLineSegmentBetweenSqd(fCentroid, fPathPolygon[0], 852 fPathPolygon[1]); 853 SkRect bounds; 854 bounds.setBounds(&fPathPolygon[0], fPathPolygon.count()); 855 for (int i = 1; i < fPathPolygon.count(); ++i) { 856 int j = i + 1; 857 if (i == fPathPolygon.count() - 1) { 858 j = 0; 859 } 860 SkPoint currPoint = fPathPolygon[i]; 861 SkPoint nextPoint = fPathPolygon[j]; 862 SkScalar distSq = SkPointPriv::DistanceToLineSegmentBetweenSqd(fCentroid, currPoint, 863 nextPoint); 864 if (distSq < minDistSq) { 865 minDistSq = distSq; 866 } 867 } 868 static constexpr auto kTolerance = 1.0e-2f; 869 if (minDistSq < (radius + kTolerance)*(radius + kTolerance)) { 870 // if the umbra would collapse, we back off a bit on inner blur and adjust the alpha 871 SkScalar newRadius = SkScalarSqrt(minDistSq) - kTolerance; 872 fOffsetAdjust = newRadius - radius; 873 SkScalar ratio = 128 * (newRadius + radius) / radius; 874 // they aren't PMColors, but the interpolation algorithm is the same 875 fUmbraColor = SkPMLerp(fUmbraColor, fPenumbraColor, (unsigned)ratio); 876 radius = newRadius; 877 } 878 879 // compute vectors for clip tests 880 this->computeClipVectorsAndTestCentroid(); 881 882 // generate inner ring 883 if (!SkInsetConvexPolygon(&fPathPolygon[0], fPathPolygon.count(), radius, 884 &fUmbraPolygon)) { 885 // this shouldn't happen, but just in case we'll inset using the centroid 886 fValidUmbra = false; 887 } 888 889 // walk around the path polygon, generate outer ring and connect to inner ring 890 if (fTransparent) { 891 *fPositions.push() = fCentroid; 892 *fColors.push() = fUmbraColor; 893 } 894 fCurrUmbraPoint = 0; 895 for (int i = 0; i < fPathPolygon.count(); ++i) { 896 if (!this->handlePolyPoint(fPathPolygon[i])) { 897 return; 898 } 899 } 900 901 if (!this->indexCount()) { 902 return; 903 } 904 905 // finish up the final verts 906 SkVector normal; 907 if (compute_normal(fPrevPoint, fFirstPoint, fDirection, &normal)) { 908 normal *= fRadius; 909 this->addArc(normal, true); 910 911 // add to center fan 912 if (fTransparent) { 913 *fIndices.push() = 0; 914 *fIndices.push() = fPrevUmbraIndex; 915 *fIndices.push() = fFirstVertexIndex; 916 // or to clip ring 917 } else { 918 if (fFirstUmbraOutside) { 919 *fIndices.push() = fPrevUmbraIndex; 920 *fIndices.push() = fFirstVertexIndex; 921 *fIndices.push() = fFirstVertexIndex + 1; 922 if (fPrevUmbraOutside) { 923 // fill out quad 924 *fIndices.push() = fPrevUmbraIndex; 925 *fIndices.push() = fFirstVertexIndex + 1; 926 *fIndices.push() = fPrevUmbraIndex + 1; 927 } 928 } else if (fPrevUmbraOutside) { 929 // add tri 930 *fIndices.push() = fPrevUmbraIndex; 931 *fIndices.push() = fFirstVertexIndex; 932 *fIndices.push() = fPrevUmbraIndex + 1; 933 } 934 } 935 936 // add final edge 937 *fPositions.push() = fFirstPoint + normal; 938 *fColors.push() = fPenumbraColor; 939 940 *fIndices.push() = fPrevUmbraIndex; 941 *fIndices.push() = fPositions.count() - 2; 942 *fIndices.push() = fFirstVertexIndex; 943 944 *fIndices.push() = fPositions.count() - 2; 945 *fIndices.push() = fPositions.count() - 1; 946 *fIndices.push() = fFirstVertexIndex; 947 948 fPrevOutset = normal; 949 } 950 951 // final fan 952 if (fPositions.count() >= 3) { 953 fPrevUmbraIndex = fFirstVertexIndex; 954 fPrevPoint = fFirstPoint; 955 if (this->addArc(fFirstOutset, false)) { 956 *fIndices.push() = fFirstVertexIndex; 957 *fIndices.push() = fPositions.count() - 1; 958 if (fFirstUmbraOutside) { 959 *fIndices.push() = fFirstVertexIndex + 2; 960 } else { 961 *fIndices.push() = fFirstVertexIndex + 1; 962 } 963 } else { 964 // no arc added, fix up by setting first penumbra point position to last one 965 if (fFirstUmbraOutside) { 966 fPositions[fFirstVertexIndex + 2] = fPositions[fPositions.count() - 1]; 967 } else { 968 fPositions[fFirstVertexIndex + 1] = fPositions[fPositions.count() - 1]; 969 } 970 } 971 } 972 973 if (ctm.hasPerspective()) { 974 for (int i = 0; i < fPositions.count(); ++i) { 975 SkScalar pathZ = fTransformedHeightFunc(fPositions[i]); 976 SkScalar factor = SkScalarInvert(fLightZ - pathZ); 977 fPositions[i].fX = (fPositions[i].fX*fLightZ - lightPos.fX*pathZ)*factor; 978 fPositions[i].fY = (fPositions[i].fY*fLightZ - lightPos.fY*pathZ)*factor; 979 } 980 #ifdef DRAW_CENTROID 981 SkScalar pathZ = fTransformedHeightFunc(fCentroid); 982 SkScalar factor = SkScalarInvert(fLightZ - pathZ); 983 fCentroid.fX = (fCentroid.fX*fLightZ - lightPos.fX*pathZ)*factor; 984 fCentroid.fY = (fCentroid.fY*fLightZ - lightPos.fY*pathZ)*factor; 985 #endif 986 } 987 #ifdef DRAW_CENTROID 988 *fPositions.push() = fCentroid + SkVector::Make(-2, -2); 989 *fColors.push() = SkColorSetARGB(255, 0, 255, 255); 990 *fPositions.push() = fCentroid + SkVector::Make(2, -2); 991 *fColors.push() = SkColorSetARGB(255, 0, 255, 255); 992 *fPositions.push() = fCentroid + SkVector::Make(-2, 2); 993 *fColors.push() = SkColorSetARGB(255, 0, 255, 255); 994 *fPositions.push() = fCentroid + SkVector::Make(2, 2); 995 *fColors.push() = SkColorSetARGB(255, 0, 255, 255); 996 997 *fIndices.push() = fPositions.count() - 4; 998 *fIndices.push() = fPositions.count() - 2; 999 *fIndices.push() = fPositions.count() - 1; 1000 1001 *fIndices.push() = fPositions.count() - 4; 1002 *fIndices.push() = fPositions.count() - 1; 1003 *fIndices.push() = fPositions.count() - 3; 1004 #endif 1005 1006 fSucceeded = true; 1007 } 1008 1009 void SkSpotShadowTessellator::computeClipAndPathPolygons(const SkPath& path, const SkMatrix& ctm, 1010 const SkMatrix& shadowTransform) { 1011 1012 fPathPolygon.setReserve(path.countPoints()); 1013 1014 // Walk around the path and compute clip polygon and path polygon. 1015 // Will also accumulate sum of areas for centroid. 1016 // For Bezier curves, we compute additional interior points on curve. 1017 SkPath::Iter iter(path, true); 1018 SkPoint pts[4]; 1019 SkPath::Verb verb; 1020 1021 fClipPolygon.reset(); 1022 1023 // init centroid 1024 fCentroid = SkPoint::Make(0, 0); 1025 fArea = 0; 1026 1027 // coefficients to compute cubic Bezier at t = 5/16 1028 static constexpr SkScalar kA = 0.32495117187f; 1029 static constexpr SkScalar kB = 0.44311523437f; 1030 static constexpr SkScalar kC = 0.20141601562f; 1031 static constexpr SkScalar kD = 0.03051757812f; 1032 1033 SkPoint curvePoint; 1034 SkScalar w; 1035 while ((verb = iter.next(pts)) != SkPath::kDone_Verb) { 1036 switch (verb) { 1037 case SkPath::kLine_Verb: 1038 ctm.mapPoints(&pts[1], 1); 1039 *fClipPolygon.push() = pts[1]; 1040 this->INHERITED::handleLine(shadowTransform, &pts[1]); 1041 break; 1042 case SkPath::kQuad_Verb: 1043 ctm.mapPoints(pts, 3); 1044 // point at t = 1/2 1045 curvePoint.fX = 0.25f*pts[0].fX + 0.5f*pts[1].fX + 0.25f*pts[2].fX; 1046 curvePoint.fY = 0.25f*pts[0].fY + 0.5f*pts[1].fY + 0.25f*pts[2].fY; 1047 *fClipPolygon.push() = curvePoint; 1048 *fClipPolygon.push() = pts[2]; 1049 this->handleQuad(shadowTransform, pts); 1050 break; 1051 case SkPath::kConic_Verb: 1052 ctm.mapPoints(pts, 3); 1053 w = iter.conicWeight(); 1054 // point at t = 1/2 1055 curvePoint.fX = 0.25f*pts[0].fX + w*0.5f*pts[1].fX + 0.25f*pts[2].fX; 1056 curvePoint.fY = 0.25f*pts[0].fY + w*0.5f*pts[1].fY + 0.25f*pts[2].fY; 1057 curvePoint *= SkScalarInvert(0.5f + 0.5f*w); 1058 *fClipPolygon.push() = curvePoint; 1059 *fClipPolygon.push() = pts[2]; 1060 this->handleConic(shadowTransform, pts, w); 1061 break; 1062 case SkPath::kCubic_Verb: 1063 ctm.mapPoints(pts, 4); 1064 // point at t = 5/16 1065 curvePoint.fX = kA*pts[0].fX + kB*pts[1].fX + kC*pts[2].fX + kD*pts[3].fX; 1066 curvePoint.fY = kA*pts[0].fY + kB*pts[1].fY + kC*pts[2].fY + kD*pts[3].fY; 1067 *fClipPolygon.push() = curvePoint; 1068 // point at t = 11/16 1069 curvePoint.fX = kD*pts[0].fX + kC*pts[1].fX + kB*pts[2].fX + kA*pts[3].fX; 1070 curvePoint.fY = kD*pts[0].fY + kC*pts[1].fY + kB*pts[2].fY + kA*pts[3].fY; 1071 *fClipPolygon.push() = curvePoint; 1072 *fClipPolygon.push() = pts[3]; 1073 this->handleCubic(shadowTransform, pts); 1074 break; 1075 case SkPath::kMove_Verb: 1076 case SkPath::kClose_Verb: 1077 case SkPath::kDone_Verb: 1078 break; 1079 default: 1080 SkDEBUGFAIL("unknown verb"); 1081 } 1082 } 1083 1084 // finish centroid 1085 if (fPathPolygon.count() > 0) { 1086 SkPoint currPoint = fPathPolygon[fPathPolygon.count() - 1]; 1087 SkPoint nextPoint = fPathPolygon[0]; 1088 SkScalar quadArea = currPoint.cross(nextPoint); 1089 fCentroid.fX += (currPoint.fX + nextPoint.fX) * quadArea; 1090 fCentroid.fY += (currPoint.fY + nextPoint.fY) * quadArea; 1091 fArea += quadArea; 1092 fCentroid *= SK_Scalar1 / (3 * fArea); 1093 } 1094 1095 fCurrClipPoint = fClipPolygon.count() - 1; 1096 } 1097 1098 void SkSpotShadowTessellator::computeClipVectorsAndTestCentroid() { 1099 SkASSERT(fClipPolygon.count() >= 3); 1100 1101 // init clip vectors 1102 SkVector v0 = fClipPolygon[1] - fClipPolygon[0]; 1103 *fClipVectors.push() = v0; 1104 1105 // init centroid check 1106 bool hiddenCentroid = true; 1107 SkVector v1 = fCentroid - fClipPolygon[0]; 1108 SkScalar initCross = v0.cross(v1); 1109 1110 for (int p = 1; p < fClipPolygon.count(); ++p) { 1111 // add to clip vectors 1112 v0 = fClipPolygon[(p + 1) % fClipPolygon.count()] - fClipPolygon[p]; 1113 *fClipVectors.push() = v0; 1114 // Determine if transformed centroid is inside clipPolygon. 1115 v1 = fCentroid - fClipPolygon[p]; 1116 if (initCross*v0.cross(v1) <= 0) { 1117 hiddenCentroid = false; 1118 } 1119 } 1120 SkASSERT(fClipVectors.count() == fClipPolygon.count()); 1121 1122 fTransparent = fTransparent || !hiddenCentroid; 1123 } 1124 1125 bool SkSpotShadowTessellator::clipUmbraPoint(const SkPoint& umbraPoint, const SkPoint& centroid, 1126 SkPoint* clipPoint) { 1127 SkVector segmentVector = centroid - umbraPoint; 1128 1129 int startClipPoint = fCurrClipPoint; 1130 do { 1131 SkVector dp = umbraPoint - fClipPolygon[fCurrClipPoint]; 1132 SkScalar denom = fClipVectors[fCurrClipPoint].cross(segmentVector); 1133 SkScalar t_num = dp.cross(segmentVector); 1134 // if line segments are nearly parallel 1135 if (SkScalarNearlyZero(denom)) { 1136 // and collinear 1137 if (SkScalarNearlyZero(t_num)) { 1138 return false; 1139 } 1140 // otherwise are separate, will try the next poly segment 1141 // else if crossing lies within poly segment 1142 } else if (t_num >= 0 && t_num <= denom) { 1143 SkScalar s_num = dp.cross(fClipVectors[fCurrClipPoint]); 1144 // if umbra point is inside the clip polygon 1145 if (s_num >= 0 && s_num <= denom) { 1146 segmentVector *= s_num/denom; 1147 *clipPoint = umbraPoint + segmentVector; 1148 return true; 1149 } 1150 } 1151 fCurrClipPoint = (fCurrClipPoint + 1) % fClipPolygon.count(); 1152 } while (fCurrClipPoint != startClipPoint); 1153 1154 return false; 1155 } 1156 1157 int SkSpotShadowTessellator::getClosestUmbraPoint(const SkPoint& p) { 1158 SkScalar minDistance = SkPointPriv::DistanceToSqd(p, fUmbraPolygon[fCurrUmbraPoint]); 1159 int index = fCurrUmbraPoint; 1160 int dir = 1; 1161 int next = (index + dir) % fUmbraPolygon.count(); 1162 1163 // init travel direction 1164 SkScalar distance = SkPointPriv::DistanceToSqd(p, fUmbraPolygon[next]); 1165 if (distance < minDistance) { 1166 index = next; 1167 minDistance = distance; 1168 } else { 1169 dir = fUmbraPolygon.count()-1; 1170 } 1171 1172 // iterate until we find a point that increases the distance 1173 next = (index + dir) % fUmbraPolygon.count(); 1174 distance = SkPointPriv::DistanceToSqd(p, fUmbraPolygon[next]); 1175 while (distance < minDistance) { 1176 index = next; 1177 minDistance = distance; 1178 next = (index + dir) % fUmbraPolygon.count(); 1179 distance = SkPointPriv::DistanceToSqd(p, fUmbraPolygon[next]); 1180 } 1181 1182 fCurrUmbraPoint = index; 1183 return index; 1184 } 1185 1186 void SkSpotShadowTessellator::mapPoints(SkScalar scale, const SkVector& xlate, 1187 SkPoint* pts, int count) { 1188 // TODO: vectorize 1189 for (int i = 0; i < count; ++i) { 1190 pts[i] *= scale; 1191 pts[i] += xlate; 1192 } 1193 } 1194 1195 static bool duplicate_pt(const SkPoint& p0, const SkPoint& p1) { 1196 static constexpr SkScalar kClose = (SK_Scalar1 / 16); 1197 static constexpr SkScalar kCloseSqd = kClose*kClose; 1198 1199 SkScalar distSq = SkPointPriv::DistanceToSqd(p0, p1); 1200 return distSq < kCloseSqd; 1201 } 1202 1203 static SkScalar perp_dot(const SkPoint& p0, const SkPoint& p1, const SkPoint& p2) { 1204 SkVector v0 = p1 - p0; 1205 SkVector v1 = p2 - p0; 1206 return v0.cross(v1); 1207 } 1208 1209 static bool is_collinear(const SkPoint& p0, const SkPoint& p1, const SkPoint& p2) { 1210 return (SkScalarNearlyZero(perp_dot(p0, p1, p2))); 1211 } 1212 1213 void SkSpotShadowTessellator::handleLine(const SkPoint& p) { 1214 // remove coincident points and add to centroid 1215 if (fPathPolygon.count() > 0) { 1216 const SkPoint& lastPoint = fPathPolygon[fPathPolygon.count() - 1]; 1217 if (duplicate_pt(p, lastPoint)) { 1218 return; 1219 } 1220 SkScalar quadArea = lastPoint.cross(p); 1221 fCentroid.fX += (p.fX + lastPoint.fX) * quadArea; 1222 fCentroid.fY += (p.fY + lastPoint.fY) * quadArea; 1223 fArea += quadArea; 1224 } 1225 1226 // try to remove collinear points 1227 if (fPathPolygon.count() > 1 && is_collinear(fPathPolygon[fPathPolygon.count()-2], 1228 fPathPolygon[fPathPolygon.count()-1], 1229 p)) { 1230 fPathPolygon[fPathPolygon.count() - 1] = p; 1231 } else { 1232 *fPathPolygon.push() = p; 1233 } 1234 } 1235 1236 bool SkSpotShadowTessellator::handlePolyPoint(const SkPoint& p) { 1237 if (fInitPoints.count() < 2) { 1238 *fInitPoints.push() = p; 1239 return true; 1240 } 1241 1242 if (fInitPoints.count() == 2) { 1243 // determine if cw or ccw 1244 SkScalar perpDot = perp_dot(fInitPoints[0], fInitPoints[1], p); 1245 if (SkScalarNearlyZero(perpDot)) { 1246 // nearly parallel, just treat as straight line and continue 1247 fInitPoints[1] = p; 1248 return true; 1249 } 1250 1251 // if perpDot > 0, winding is ccw 1252 fDirection = (perpDot > 0) ? -1 : 1; 1253 1254 // add first quad 1255 if (!compute_normal(fInitPoints[0], fInitPoints[1], fDirection, &fFirstOutset)) { 1256 // first two points are incident, make the third point the second and continue 1257 fInitPoints[1] = p; 1258 return true; 1259 } 1260 1261 fFirstOutset *= fRadius; 1262 fFirstPoint = fInitPoints[0]; 1263 fFirstVertexIndex = fPositions.count(); 1264 fPrevOutset = fFirstOutset; 1265 fPrevPoint = fFirstPoint; 1266 fPrevUmbraIndex = -1; 1267 1268 this->addInnerPoint(fFirstPoint); 1269 fPrevUmbraIndex = fFirstVertexIndex; 1270 1271 if (!fTransparent) { 1272 SkPoint clipPoint; 1273 bool isOutside = this->clipUmbraPoint(fPositions[fFirstVertexIndex], 1274 fCentroid, &clipPoint); 1275 if (isOutside) { 1276 *fPositions.push() = clipPoint; 1277 *fColors.push() = fUmbraColor; 1278 } 1279 fPrevUmbraOutside = isOutside; 1280 fFirstUmbraOutside = isOutside; 1281 } 1282 1283 SkPoint newPoint = fFirstPoint + fFirstOutset; 1284 *fPositions.push() = newPoint; 1285 *fColors.push() = fPenumbraColor; 1286 this->addEdge(fInitPoints[1], fFirstOutset); 1287 1288 // to ensure we skip this block next time 1289 *fInitPoints.push() = p; 1290 } 1291 1292 // if concave, abort 1293 SkScalar perpDot = perp_dot(fInitPoints[1], fInitPoints[2], p); 1294 if (fDirection*perpDot > 0) { 1295 return false; 1296 } 1297 1298 SkVector normal; 1299 if (compute_normal(fPrevPoint, p, fDirection, &normal)) { 1300 normal *= fRadius; 1301 this->addArc(normal, true); 1302 this->addEdge(p, normal); 1303 fInitPoints[1] = fInitPoints[2]; 1304 fInitPoints[2] = p; 1305 } 1306 1307 return true; 1308 } 1309 1310 bool SkSpotShadowTessellator::addInnerPoint(const SkPoint& pathPoint) { 1311 SkPoint umbraPoint; 1312 if (!fValidUmbra) { 1313 SkVector v = fCentroid - pathPoint; 1314 v *= 0.95f; 1315 umbraPoint = pathPoint + v; 1316 } else { 1317 umbraPoint = fUmbraPolygon[this->getClosestUmbraPoint(pathPoint)]; 1318 } 1319 1320 fPrevPoint = pathPoint; 1321 1322 // merge "close" points 1323 if (fPrevUmbraIndex == -1 || 1324 !duplicate_pt(umbraPoint, fPositions[fPrevUmbraIndex])) { 1325 *fPositions.push() = umbraPoint; 1326 *fColors.push() = fUmbraColor; 1327 1328 return false; 1329 } else { 1330 return true; 1331 } 1332 } 1333 1334 void SkSpotShadowTessellator::addEdge(const SkPoint& nextPoint, const SkVector& nextNormal) { 1335 // add next umbra point 1336 bool duplicate = this->addInnerPoint(nextPoint); 1337 int prevPenumbraIndex = duplicate ? fPositions.count()-1 : fPositions.count()-2; 1338 int currUmbraIndex = duplicate ? fPrevUmbraIndex : fPositions.count()-1; 1339 1340 if (!duplicate) { 1341 // add to center fan if transparent or centroid showing 1342 if (fTransparent) { 1343 *fIndices.push() = 0; 1344 *fIndices.push() = fPrevUmbraIndex; 1345 *fIndices.push() = currUmbraIndex; 1346 // otherwise add to clip ring 1347 } else { 1348 SkPoint clipPoint; 1349 bool isOutside = this->clipUmbraPoint(fPositions[currUmbraIndex], fCentroid, 1350 &clipPoint); 1351 if (isOutside) { 1352 *fPositions.push() = clipPoint; 1353 *fColors.push() = fUmbraColor; 1354 1355 *fIndices.push() = fPrevUmbraIndex; 1356 *fIndices.push() = currUmbraIndex; 1357 *fIndices.push() = currUmbraIndex + 1; 1358 if (fPrevUmbraOutside) { 1359 // fill out quad 1360 *fIndices.push() = fPrevUmbraIndex; 1361 *fIndices.push() = currUmbraIndex + 1; 1362 *fIndices.push() = fPrevUmbraIndex + 1; 1363 } 1364 } else if (fPrevUmbraOutside) { 1365 // add tri 1366 *fIndices.push() = fPrevUmbraIndex; 1367 *fIndices.push() = currUmbraIndex; 1368 *fIndices.push() = fPrevUmbraIndex + 1; 1369 } 1370 fPrevUmbraOutside = isOutside; 1371 } 1372 } 1373 1374 // add next penumbra point and quad 1375 SkPoint newPoint = nextPoint + nextNormal; 1376 *fPositions.push() = newPoint; 1377 *fColors.push() = fPenumbraColor; 1378 1379 if (!duplicate) { 1380 *fIndices.push() = fPrevUmbraIndex; 1381 *fIndices.push() = prevPenumbraIndex; 1382 *fIndices.push() = currUmbraIndex; 1383 } 1384 1385 *fIndices.push() = prevPenumbraIndex; 1386 *fIndices.push() = fPositions.count() - 1; 1387 *fIndices.push() = currUmbraIndex; 1388 1389 fPrevUmbraIndex = currUmbraIndex; 1390 fPrevOutset = nextNormal; 1391 } 1392 1393 /////////////////////////////////////////////////////////////////////////////////////////////////// 1394 1395 sk_sp<SkVertices> SkShadowTessellator::MakeAmbient(const SkPath& path, const SkMatrix& ctm, 1396 const SkPoint3& zPlane, bool transparent) { 1397 SkAmbientShadowTessellator ambientTess(path, ctm, zPlane, transparent); 1398 return ambientTess.releaseVertices(); 1399 } 1400 1401 sk_sp<SkVertices> SkShadowTessellator::MakeSpot(const SkPath& path, const SkMatrix& ctm, 1402 const SkPoint3& zPlane, const SkPoint3& lightPos, 1403 SkScalar lightRadius, bool transparent) { 1404 SkSpotShadowTessellator spotTess(path, ctm, zPlane, lightPos, lightRadius, transparent); 1405 return spotTess.releaseVertices(); 1406 } 1407
