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 "SkColorPriv.h" 10 #include "SkGeometry.h" 11 #include "SkInsetConvexPolygon.h" 12 #include "SkPath.h" 13 #include "SkVertices.h" 14 15 #if SK_SUPPORT_GPU 16 #include "GrPathUtils.h" 17 #endif 18 19 20 /** 21 * Base class 22 */ 23 class SkBaseShadowTessellator { 24 public: 25 SkBaseShadowTessellator(const SkPoint3& zPlaneParams, bool transparent); 26 virtual ~SkBaseShadowTessellator() {} 27 28 sk_sp<SkVertices> releaseVertices() { 29 if (!fSucceeded) { 30 return nullptr; 31 } 32 return SkVertices::MakeCopy(SkVertices::kTriangles_VertexMode, this->vertexCount(), 33 fPositions.begin(), nullptr, fColors.begin(), 34 this->indexCount(), fIndices.begin()); 35 } 36 37 protected: 38 static constexpr auto kMinHeight = 0.1f; 39 40 int vertexCount() const { return fPositions.count(); } 41 int indexCount() const { return fIndices.count(); } 42 43 bool setZOffset(const SkRect& bounds, bool perspective); 44 45 virtual void handleLine(const SkPoint& p) = 0; 46 void handleLine(const SkMatrix& m, SkPoint* p); 47 48 void handleQuad(const SkPoint pts[3]); 49 void handleQuad(const SkMatrix& m, SkPoint pts[3]); 50 51 void handleCubic(const SkMatrix& m, SkPoint pts[4]); 52 53 void handleConic(const SkMatrix& m, SkPoint pts[3], SkScalar w); 54 55 bool setTransformedHeightFunc(const SkMatrix& ctm); 56 57 bool addArc(const SkVector& nextNormal, bool finishArc); 58 59 SkScalar heightFunc(SkScalar x, SkScalar y) { 60 return fZPlaneParams.fX*x + fZPlaneParams.fY*y + fZPlaneParams.fZ; 61 } 62 63 SkPoint3 fZPlaneParams; 64 std::function<SkScalar(const SkPoint&)> fTransformedHeightFunc; 65 SkScalar fZOffset; 66 // members for perspective height function 67 SkPoint3 fTransformedZParams; 68 SkScalar fPartialDeterminants[3]; 69 70 // first two points 71 SkTDArray<SkPoint> fInitPoints; 72 // temporary buffer 73 SkTDArray<SkPoint> fPointBuffer; 74 75 SkTDArray<SkPoint> fPositions; 76 SkTDArray<SkColor> fColors; 77 SkTDArray<uint16_t> fIndices; 78 79 int fFirstVertexIndex; 80 SkVector fFirstOutset; 81 SkPoint fFirstPoint; 82 83 bool fSucceeded; 84 bool fTransparent; 85 86 SkColor fUmbraColor; 87 SkColor fPenumbraColor; 88 89 SkScalar fRadius; 90 SkScalar fDirection; 91 int fPrevUmbraIndex; 92 SkVector fPrevOutset; 93 SkPoint fPrevPoint; 94 }; 95 96 static bool compute_normal(const SkPoint& p0, const SkPoint& p1, SkScalar dir, 97 SkVector* newNormal) { 98 SkVector normal; 99 // compute perpendicular 100 normal.fX = p0.fY - p1.fY; 101 normal.fY = p1.fX - p0.fX; 102 normal *= dir; 103 if (!normal.normalize()) { 104 return false; 105 } 106 *newNormal = normal; 107 return true; 108 } 109 110 static void compute_radial_steps(const SkVector& v1, const SkVector& v2, SkScalar r, 111 SkScalar* rotSin, SkScalar* rotCos, int* n) { 112 const SkScalar kRecipPixelsPerArcSegment = 0.125f; 113 114 SkScalar rCos = v1.dot(v2); 115 SkScalar rSin = v1.cross(v2); 116 SkScalar theta = SkScalarATan2(rSin, rCos); 117 118 int steps = SkScalarFloorToInt(r*theta*kRecipPixelsPerArcSegment); 119 120 SkScalar dTheta = theta / steps; 121 *rotSin = SkScalarSinCos(dTheta, rotCos); 122 *n = steps; 123 } 124 125 SkBaseShadowTessellator::SkBaseShadowTessellator(const SkPoint3& zPlaneParams, bool transparent) 126 : fZPlaneParams(zPlaneParams) 127 , fZOffset(0) 128 , fFirstVertexIndex(-1) 129 , fSucceeded(false) 130 , fTransparent(transparent) 131 , fDirection(1) 132 , fPrevUmbraIndex(-1) { 133 fInitPoints.setReserve(3); 134 135 // child classes will set reserve for positions, colors and indices 136 } 137 138 bool SkBaseShadowTessellator::setZOffset(const SkRect& bounds, bool perspective) { 139 SkScalar minZ = this->heightFunc(bounds.fLeft, bounds.fTop); 140 if (perspective) { 141 SkScalar z = this->heightFunc(bounds.fLeft, bounds.fBottom); 142 if (z < minZ) { 143 minZ = z; 144 } 145 z = this->heightFunc(bounds.fRight, bounds.fTop); 146 if (z < minZ) { 147 minZ = z; 148 } 149 z = this->heightFunc(bounds.fRight, bounds.fBottom); 150 if (z < minZ) { 151 minZ = z; 152 } 153 } 154 155 if (minZ < kMinHeight) { 156 fZOffset = -minZ + kMinHeight; 157 return true; 158 } 159 160 return false; 161 } 162 163 // tesselation tolerance values, in device space pixels 164 #if SK_SUPPORT_GPU 165 static const SkScalar kQuadTolerance = 0.2f; 166 static const SkScalar kCubicTolerance = 0.2f; 167 #endif 168 static const SkScalar kConicTolerance = 0.5f; 169 170 void SkBaseShadowTessellator::handleLine(const SkMatrix& m, SkPoint* p) { 171 m.mapPoints(p, 1); 172 this->handleLine(*p); 173 } 174 175 void SkBaseShadowTessellator::handleQuad(const SkPoint pts[3]) { 176 #if SK_SUPPORT_GPU 177 // TODO: Pull PathUtils out of Ganesh? 178 int maxCount = GrPathUtils::quadraticPointCount(pts, kQuadTolerance); 179 fPointBuffer.setReserve(maxCount); 180 SkPoint* target = fPointBuffer.begin(); 181 int count = GrPathUtils::generateQuadraticPoints(pts[0], pts[1], pts[2], 182 kQuadTolerance, &target, maxCount); 183 fPointBuffer.setCount(count); 184 for (int i = 0; i < count; i++) { 185 this->handleLine(fPointBuffer[i]); 186 } 187 #else 188 // for now, just to draw something 189 this->handleLine(pts[1]); 190 this->handleLine(pts[2]); 191 #endif 192 } 193 194 void SkBaseShadowTessellator::handleQuad(const SkMatrix& m, SkPoint pts[3]) { 195 m.mapPoints(pts, 3); 196 this->handleQuad(pts); 197 } 198 199 void SkBaseShadowTessellator::handleCubic(const SkMatrix& m, SkPoint pts[4]) { 200 m.mapPoints(pts, 4); 201 #if SK_SUPPORT_GPU 202 // TODO: Pull PathUtils out of Ganesh? 203 int maxCount = GrPathUtils::cubicPointCount(pts, kCubicTolerance); 204 fPointBuffer.setReserve(maxCount); 205 SkPoint* target = fPointBuffer.begin(); 206 int count = GrPathUtils::generateCubicPoints(pts[0], pts[1], pts[2], pts[3], 207 kCubicTolerance, &target, maxCount); 208 fPointBuffer.setCount(count); 209 for (int i = 0; i < count; i++) { 210 this->handleLine(fPointBuffer[i]); 211 } 212 #else 213 // for now, just to draw something 214 this->handleLine(pts[1]); 215 this->handleLine(pts[2]); 216 this->handleLine(pts[3]); 217 #endif 218 } 219 220 void SkBaseShadowTessellator::handleConic(const SkMatrix& m, SkPoint pts[3], SkScalar w) { 221 if (m.hasPerspective()) { 222 w = SkConic::TransformW(pts, w, m); 223 } 224 m.mapPoints(pts, 3); 225 SkAutoConicToQuads quadder; 226 const SkPoint* quads = quadder.computeQuads(pts, w, kConicTolerance); 227 SkPoint lastPoint = *(quads++); 228 int count = quadder.countQuads(); 229 for (int i = 0; i < count; ++i) { 230 SkPoint quadPts[3]; 231 quadPts[0] = lastPoint; 232 quadPts[1] = quads[0]; 233 quadPts[2] = i == count - 1 ? pts[2] : quads[1]; 234 this->handleQuad(quadPts); 235 lastPoint = quadPts[2]; 236 quads += 2; 237 } 238 } 239 240 bool SkBaseShadowTessellator::addArc(const SkVector& nextNormal, bool finishArc) { 241 // fill in fan from previous quad 242 SkScalar rotSin, rotCos; 243 int numSteps; 244 compute_radial_steps(fPrevOutset, nextNormal, fRadius, &rotSin, &rotCos, &numSteps); 245 SkVector prevNormal = fPrevOutset; 246 for (int i = 0; i < numSteps-1; ++i) { 247 SkVector currNormal; 248 currNormal.fX = prevNormal.fX*rotCos - prevNormal.fY*rotSin; 249 currNormal.fY = prevNormal.fY*rotCos + prevNormal.fX*rotSin; 250 *fPositions.push() = fPrevPoint + currNormal; 251 *fColors.push() = fPenumbraColor; 252 *fIndices.push() = fPrevUmbraIndex; 253 *fIndices.push() = fPositions.count() - 1; 254 *fIndices.push() = fPositions.count() - 2; 255 256 prevNormal = currNormal; 257 } 258 if (finishArc && numSteps) { 259 *fPositions.push() = fPrevPoint + nextNormal; 260 *fColors.push() = fPenumbraColor; 261 *fIndices.push() = fPrevUmbraIndex; 262 *fIndices.push() = fPositions.count() - 1; 263 *fIndices.push() = fPositions.count() - 2; 264 } 265 fPrevOutset = nextNormal; 266 267 return (numSteps > 0); 268 } 269 270 bool SkBaseShadowTessellator::setTransformedHeightFunc(const SkMatrix& ctm) { 271 if (SkScalarNearlyZero(fZPlaneParams.fX) && SkScalarNearlyZero(fZPlaneParams.fY)) { 272 fTransformedHeightFunc = [this](const SkPoint& p) { 273 return fZPlaneParams.fZ; 274 }; 275 } else { 276 SkMatrix ctmInverse; 277 if (!ctm.invert(&ctmInverse)) { 278 return false; 279 } 280 // multiply by transpose 281 fTransformedZParams = SkPoint3::Make( 282 ctmInverse[SkMatrix::kMScaleX] * fZPlaneParams.fX + 283 ctmInverse[SkMatrix::kMSkewY] * fZPlaneParams.fY + 284 ctmInverse[SkMatrix::kMPersp0] * fZPlaneParams.fZ, 285 286 ctmInverse[SkMatrix::kMSkewX] * fZPlaneParams.fX + 287 ctmInverse[SkMatrix::kMScaleY] * fZPlaneParams.fY + 288 ctmInverse[SkMatrix::kMPersp1] * fZPlaneParams.fZ, 289 290 ctmInverse[SkMatrix::kMTransX] * fZPlaneParams.fX + 291 ctmInverse[SkMatrix::kMTransY] * fZPlaneParams.fY + 292 ctmInverse[SkMatrix::kMPersp2] * fZPlaneParams.fZ 293 ); 294 295 if (ctm.hasPerspective()) { 296 // We use Cramer's rule to solve for the W value for a given post-divide X and Y, 297 // so pre-compute those values that are independent of X and Y. 298 // W is det(ctmInverse)/(PD[0]*X + PD[1]*Y + PD[2]) 299 fPartialDeterminants[0] = ctm[SkMatrix::kMSkewY] * ctm[SkMatrix::kMPersp1] - 300 ctm[SkMatrix::kMScaleY] * ctm[SkMatrix::kMPersp0]; 301 fPartialDeterminants[1] = ctm[SkMatrix::kMPersp0] * ctm[SkMatrix::kMSkewX] - 302 ctm[SkMatrix::kMPersp1] * ctm[SkMatrix::kMScaleX]; 303 fPartialDeterminants[2] = ctm[SkMatrix::kMScaleX] * ctm[SkMatrix::kMScaleY] - 304 ctm[SkMatrix::kMSkewX] * ctm[SkMatrix::kMSkewY]; 305 SkScalar ctmDeterminant = ctm[SkMatrix::kMTransX] * fPartialDeterminants[0] + 306 ctm[SkMatrix::kMTransY] * fPartialDeterminants[1] + 307 ctm[SkMatrix::kMPersp2] * fPartialDeterminants[2]; 308 309 // Pre-bake the numerator of Cramer's rule into the zParams to avoid another multiply. 310 // TODO: this may introduce numerical instability, but I haven't seen any issues yet. 311 fTransformedZParams.fX *= ctmDeterminant; 312 fTransformedZParams.fY *= ctmDeterminant; 313 fTransformedZParams.fZ *= ctmDeterminant; 314 315 fTransformedHeightFunc = [this](const SkPoint& p) { 316 SkScalar denom = p.fX * fPartialDeterminants[0] + 317 p.fY * fPartialDeterminants[1] + 318 fPartialDeterminants[2]; 319 SkScalar w = SkScalarFastInvert(denom); 320 return fZOffset + w*(fTransformedZParams.fX * p.fX + 321 fTransformedZParams.fY * p.fY + 322 fTransformedZParams.fZ); 323 }; 324 } else { 325 fTransformedHeightFunc = [this](const SkPoint& p) { 326 return fZOffset + fTransformedZParams.fX * p.fX + 327 fTransformedZParams.fY * p.fY + fTransformedZParams.fZ; 328 }; 329 } 330 } 331 332 return true; 333 } 334 335 336 ////////////////////////////////////////////////////////////////////////////////////////////////// 337 338 class SkAmbientShadowTessellator : public SkBaseShadowTessellator { 339 public: 340 SkAmbientShadowTessellator(const SkPath& path, const SkMatrix& ctm, 341 const SkPoint3& zPlaneParams, bool transparent); 342 343 private: 344 void handleLine(const SkPoint& p) override; 345 void addEdge(const SkVector& nextPoint, const SkVector& nextNormal); 346 347 static constexpr auto kHeightFactor = 1.0f / 128.0f; 348 static constexpr auto kGeomFactor = 64.0f; 349 static constexpr auto kMaxEdgeLenSqr = 20 * 20; 350 static constexpr auto kInsetFactor = -0.5f; 351 352 SkScalar offset(SkScalar z) { 353 return z * kHeightFactor * kGeomFactor; 354 } 355 SkColor umbraColor(SkScalar z) { 356 SkScalar umbraAlpha = SkScalarInvert((1.0f + SkTMax(z*kHeightFactor, 0.0f))); 357 return SkColorSetARGB(umbraAlpha * 255.9999f, 0, 0, 0); 358 } 359 360 int fCentroidCount; 361 bool fSplitFirstEdge; 362 bool fSplitPreviousEdge; 363 364 typedef SkBaseShadowTessellator INHERITED; 365 }; 366 367 SkAmbientShadowTessellator::SkAmbientShadowTessellator(const SkPath& path, 368 const SkMatrix& ctm, 369 const SkPoint3& zPlaneParams, 370 bool transparent) 371 : INHERITED(zPlaneParams, transparent) 372 , fSplitFirstEdge(false) 373 , fSplitPreviousEdge(false) { 374 // Set base colors 375 SkScalar occluderHeight = heightFunc(0, 0); 376 SkScalar umbraAlpha = SkScalarInvert((1.0f + SkTMax(occluderHeight*kHeightFactor, 0.0f))); 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 fFirstPoint.distanceToSqd(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 nextPoint.distanceToSqd(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 float zRatio = SkTPin(occluderHeight / (fLightZ - occluderHeight), 0.0f, 0.95f); 807 SkScalar radius = lightRadius * zRatio; 808 fRadius = radius; 809 fUmbraColor = SkColorSetARGB(255, 0, 0, 0); 810 fPenumbraColor = SkColorSetARGB(0, 0, 0, 0); 811 812 // Compute the scale and translation for the spot shadow. 813 SkMatrix shadowTransform; 814 if (!ctm.hasPerspective()) { 815 SkScalar scale = fLightZ / (fLightZ - occluderHeight); 816 SkVector translate = SkVector::Make(-zRatio * lightPos.fX, -zRatio * lightPos.fY); 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 } 826 SkMatrix fullTransform = SkMatrix::Concat(shadowTransform, ctm); 827 828 // Set up our reverse mapping 829 this->setTransformedHeightFunc(fullTransform); 830 831 // TODO: calculate these reserves better 832 // Penumbra ring: 3*numPts 833 // Umbra ring: numPts 834 // Inner ring: numPts 835 fPositions.setReserve(5 * path.countPoints()); 836 fColors.setReserve(5 * path.countPoints()); 837 // Penumbra ring: 12*numPts 838 // Umbra ring: 3*numPts 839 fIndices.setReserve(15 * path.countPoints()); 840 fClipPolygon.setReserve(path.countPoints()); 841 842 // compute rough clip bounds for umbra, plus offset polygon, plus centroid 843 this->computeClipAndPathPolygons(path, ctm, shadowTransform); 844 if (fClipPolygon.count() < 3 || fPathPolygon.count() < 3) { 845 return; 846 } 847 848 // check to see if umbra collapses 849 SkScalar minDistSq = fCentroid.distanceToLineSegmentBetweenSqd(fPathPolygon[0], 850 fPathPolygon[1]); 851 SkRect bounds; 852 bounds.setBounds(&fPathPolygon[0], fPathPolygon.count()); 853 for (int i = 1; i < fPathPolygon.count(); ++i) { 854 int j = i + 1; 855 if (i == fPathPolygon.count() - 1) { 856 j = 0; 857 } 858 SkPoint currPoint = fPathPolygon[i]; 859 SkPoint nextPoint = fPathPolygon[j]; 860 SkScalar distSq = fCentroid.distanceToLineSegmentBetweenSqd(currPoint, nextPoint); 861 if (distSq < minDistSq) { 862 minDistSq = distSq; 863 } 864 } 865 static constexpr auto kTolerance = 1.0e-2f; 866 if (minDistSq < (radius + kTolerance)*(radius + kTolerance)) { 867 // if the umbra would collapse, we back off a bit on inner blur and adjust the alpha 868 SkScalar newRadius = SkScalarSqrt(minDistSq) - kTolerance; 869 fOffsetAdjust = newRadius - radius; 870 SkScalar ratio = 128 * (newRadius + radius) / radius; 871 // they aren't PMColors, but the interpolation algorithm is the same 872 fUmbraColor = SkPMLerp(fUmbraColor, fPenumbraColor, (unsigned)ratio); 873 radius = newRadius; 874 } 875 876 // compute vectors for clip tests 877 this->computeClipVectorsAndTestCentroid(); 878 879 // generate inner ring 880 if (!SkInsetConvexPolygon(&fPathPolygon[0], fPathPolygon.count(), radius, 881 &fUmbraPolygon)) { 882 // this shouldn't happen, but just in case we'll inset using the centroid 883 fValidUmbra = false; 884 } 885 886 // walk around the path polygon, generate outer ring and connect to inner ring 887 if (fTransparent) { 888 *fPositions.push() = fCentroid; 889 *fColors.push() = fUmbraColor; 890 } 891 fCurrUmbraPoint = 0; 892 for (int i = 0; i < fPathPolygon.count(); ++i) { 893 if (!this->handlePolyPoint(fPathPolygon[i])) { 894 return; 895 } 896 } 897 898 if (!this->indexCount()) { 899 return; 900 } 901 902 // finish up the final verts 903 SkVector normal; 904 if (compute_normal(fPrevPoint, fFirstPoint, fDirection, &normal)) { 905 normal *= fRadius; 906 this->addArc(normal, true); 907 908 // add to center fan 909 if (fTransparent) { 910 *fIndices.push() = 0; 911 *fIndices.push() = fPrevUmbraIndex; 912 *fIndices.push() = fFirstVertexIndex; 913 // or to clip ring 914 } else { 915 if (fFirstUmbraOutside) { 916 *fIndices.push() = fPrevUmbraIndex; 917 *fIndices.push() = fFirstVertexIndex; 918 *fIndices.push() = fFirstVertexIndex + 1; 919 if (fPrevUmbraOutside) { 920 // fill out quad 921 *fIndices.push() = fPrevUmbraIndex; 922 *fIndices.push() = fFirstVertexIndex + 1; 923 *fIndices.push() = fPrevUmbraIndex + 1; 924 } 925 } else if (fPrevUmbraOutside) { 926 // add tri 927 *fIndices.push() = fPrevUmbraIndex; 928 *fIndices.push() = fFirstVertexIndex; 929 *fIndices.push() = fPrevUmbraIndex + 1; 930 } 931 } 932 933 // add final edge 934 *fPositions.push() = fFirstPoint + normal; 935 *fColors.push() = fPenumbraColor; 936 937 *fIndices.push() = fPrevUmbraIndex; 938 *fIndices.push() = fPositions.count() - 2; 939 *fIndices.push() = fFirstVertexIndex; 940 941 *fIndices.push() = fPositions.count() - 2; 942 *fIndices.push() = fPositions.count() - 1; 943 *fIndices.push() = fFirstVertexIndex; 944 945 fPrevOutset = normal; 946 } 947 948 // final fan 949 if (fPositions.count() >= 3) { 950 fPrevUmbraIndex = fFirstVertexIndex; 951 fPrevPoint = fFirstPoint; 952 if (this->addArc(fFirstOutset, false)) { 953 *fIndices.push() = fFirstVertexIndex; 954 *fIndices.push() = fPositions.count() - 1; 955 if (fFirstUmbraOutside) { 956 *fIndices.push() = fFirstVertexIndex + 2; 957 } else { 958 *fIndices.push() = fFirstVertexIndex + 1; 959 } 960 } else { 961 // no arc added, fix up by setting first penumbra point position to last one 962 if (fFirstUmbraOutside) { 963 fPositions[fFirstVertexIndex + 2] = fPositions[fPositions.count() - 1]; 964 } else { 965 fPositions[fFirstVertexIndex + 1] = fPositions[fPositions.count() - 1]; 966 } 967 } 968 } 969 970 if (ctm.hasPerspective()) { 971 for (int i = 0; i < fPositions.count(); ++i) { 972 SkScalar pathZ = fTransformedHeightFunc(fPositions[i]); 973 SkScalar factor = SkScalarInvert(fLightZ - pathZ); 974 fPositions[i].fX = (fPositions[i].fX*fLightZ - lightPos.fX*pathZ)*factor; 975 fPositions[i].fY = (fPositions[i].fY*fLightZ - lightPos.fY*pathZ)*factor; 976 } 977 #ifdef DRAW_CENTROID 978 SkScalar pathZ = fTransformedHeightFunc(fCentroid); 979 SkScalar factor = SkScalarInvert(fLightZ - pathZ); 980 fCentroid.fX = (fCentroid.fX*fLightZ - lightPos.fX*pathZ)*factor; 981 fCentroid.fY = (fCentroid.fY*fLightZ - lightPos.fY*pathZ)*factor; 982 #endif 983 } 984 #ifdef DRAW_CENTROID 985 *fPositions.push() = fCentroid + SkVector::Make(-2, -2); 986 *fColors.push() = SkColorSetARGB(255, 0, 255, 255); 987 *fPositions.push() = fCentroid + SkVector::Make(2, -2); 988 *fColors.push() = SkColorSetARGB(255, 0, 255, 255); 989 *fPositions.push() = fCentroid + SkVector::Make(-2, 2); 990 *fColors.push() = SkColorSetARGB(255, 0, 255, 255); 991 *fPositions.push() = fCentroid + SkVector::Make(2, 2); 992 *fColors.push() = SkColorSetARGB(255, 0, 255, 255); 993 994 *fIndices.push() = fPositions.count() - 4; 995 *fIndices.push() = fPositions.count() - 2; 996 *fIndices.push() = fPositions.count() - 1; 997 998 *fIndices.push() = fPositions.count() - 4; 999 *fIndices.push() = fPositions.count() - 1; 1000 *fIndices.push() = fPositions.count() - 3; 1001 #endif 1002 1003 fSucceeded = true; 1004 } 1005 1006 void SkSpotShadowTessellator::computeClipAndPathPolygons(const SkPath& path, const SkMatrix& ctm, 1007 const SkMatrix& shadowTransform) { 1008 1009 fPathPolygon.setReserve(path.countPoints()); 1010 1011 // Walk around the path and compute clip polygon and path polygon. 1012 // Will also accumulate sum of areas for centroid. 1013 // For Bezier curves, we compute additional interior points on curve. 1014 SkPath::Iter iter(path, true); 1015 SkPoint pts[4]; 1016 SkPath::Verb verb; 1017 1018 fClipPolygon.reset(); 1019 1020 // init centroid 1021 fCentroid = SkPoint::Make(0, 0); 1022 fArea = 0; 1023 1024 // coefficients to compute cubic Bezier at t = 5/16 1025 static constexpr SkScalar kA = 0.32495117187f; 1026 static constexpr SkScalar kB = 0.44311523437f; 1027 static constexpr SkScalar kC = 0.20141601562f; 1028 static constexpr SkScalar kD = 0.03051757812f; 1029 1030 SkPoint curvePoint; 1031 SkScalar w; 1032 while ((verb = iter.next(pts)) != SkPath::kDone_Verb) { 1033 switch (verb) { 1034 case SkPath::kLine_Verb: 1035 ctm.mapPoints(&pts[1], 1); 1036 *fClipPolygon.push() = pts[1]; 1037 this->INHERITED::handleLine(shadowTransform, &pts[1]); 1038 break; 1039 case SkPath::kQuad_Verb: 1040 ctm.mapPoints(pts, 3); 1041 // point at t = 1/2 1042 curvePoint.fX = 0.25f*pts[0].fX + 0.5f*pts[1].fX + 0.25f*pts[2].fX; 1043 curvePoint.fY = 0.25f*pts[0].fY + 0.5f*pts[1].fY + 0.25f*pts[2].fY; 1044 *fClipPolygon.push() = curvePoint; 1045 *fClipPolygon.push() = pts[2]; 1046 this->handleQuad(shadowTransform, pts); 1047 break; 1048 case SkPath::kConic_Verb: 1049 ctm.mapPoints(pts, 3); 1050 w = iter.conicWeight(); 1051 // point at t = 1/2 1052 curvePoint.fX = 0.25f*pts[0].fX + w*0.5f*pts[1].fX + 0.25f*pts[2].fX; 1053 curvePoint.fY = 0.25f*pts[0].fY + w*0.5f*pts[1].fY + 0.25f*pts[2].fY; 1054 curvePoint *= SkScalarInvert(0.5f + 0.5f*w); 1055 *fClipPolygon.push() = curvePoint; 1056 *fClipPolygon.push() = pts[2]; 1057 this->handleConic(shadowTransform, pts, w); 1058 break; 1059 case SkPath::kCubic_Verb: 1060 ctm.mapPoints(pts, 4); 1061 // point at t = 5/16 1062 curvePoint.fX = kA*pts[0].fX + kB*pts[1].fX + kC*pts[2].fX + kD*pts[3].fX; 1063 curvePoint.fY = kA*pts[0].fY + kB*pts[1].fY + kC*pts[2].fY + kD*pts[3].fY; 1064 *fClipPolygon.push() = curvePoint; 1065 // point at t = 11/16 1066 curvePoint.fX = kD*pts[0].fX + kC*pts[1].fX + kB*pts[2].fX + kA*pts[3].fX; 1067 curvePoint.fY = kD*pts[0].fY + kC*pts[1].fY + kB*pts[2].fY + kA*pts[3].fY; 1068 *fClipPolygon.push() = curvePoint; 1069 *fClipPolygon.push() = pts[3]; 1070 this->handleCubic(shadowTransform, pts); 1071 break; 1072 case SkPath::kMove_Verb: 1073 case SkPath::kClose_Verb: 1074 case SkPath::kDone_Verb: 1075 break; 1076 default: 1077 SkDEBUGFAIL("unknown verb"); 1078 } 1079 } 1080 1081 // finish centroid 1082 if (fPathPolygon.count() > 0) { 1083 SkPoint currPoint = fPathPolygon[fPathPolygon.count() - 1]; 1084 SkPoint nextPoint = fPathPolygon[0]; 1085 SkScalar quadArea = currPoint.cross(nextPoint); 1086 fCentroid.fX += (currPoint.fX + nextPoint.fX) * quadArea; 1087 fCentroid.fY += (currPoint.fY + nextPoint.fY) * quadArea; 1088 fArea += quadArea; 1089 fCentroid *= SK_Scalar1 / (3 * fArea); 1090 } 1091 1092 fCurrClipPoint = fClipPolygon.count() - 1; 1093 } 1094 1095 void SkSpotShadowTessellator::computeClipVectorsAndTestCentroid() { 1096 SkASSERT(fClipPolygon.count() >= 3); 1097 1098 // init clip vectors 1099 SkVector v0 = fClipPolygon[1] - fClipPolygon[0]; 1100 *fClipVectors.push() = v0; 1101 1102 // init centroid check 1103 bool hiddenCentroid = true; 1104 SkVector v1 = fCentroid - fClipPolygon[0]; 1105 SkScalar initCross = v0.cross(v1); 1106 1107 for (int p = 1; p < fClipPolygon.count(); ++p) { 1108 // add to clip vectors 1109 v0 = fClipPolygon[(p + 1) % fClipPolygon.count()] - fClipPolygon[p]; 1110 *fClipVectors.push() = v0; 1111 // Determine if transformed centroid is inside clipPolygon. 1112 v1 = fCentroid - fClipPolygon[p]; 1113 if (initCross*v0.cross(v1) <= 0) { 1114 hiddenCentroid = false; 1115 } 1116 } 1117 SkASSERT(fClipVectors.count() == fClipPolygon.count()); 1118 1119 fTransparent = fTransparent || !hiddenCentroid; 1120 } 1121 1122 bool SkSpotShadowTessellator::clipUmbraPoint(const SkPoint& umbraPoint, const SkPoint& centroid, 1123 SkPoint* clipPoint) { 1124 SkVector segmentVector = centroid - umbraPoint; 1125 1126 int startClipPoint = fCurrClipPoint; 1127 do { 1128 SkVector dp = umbraPoint - fClipPolygon[fCurrClipPoint]; 1129 SkScalar denom = fClipVectors[fCurrClipPoint].cross(segmentVector); 1130 SkScalar t_num = dp.cross(segmentVector); 1131 // if line segments are nearly parallel 1132 if (SkScalarNearlyZero(denom)) { 1133 // and collinear 1134 if (SkScalarNearlyZero(t_num)) { 1135 return false; 1136 } 1137 // otherwise are separate, will try the next poly segment 1138 // else if crossing lies within poly segment 1139 } else if (t_num >= 0 && t_num <= denom) { 1140 SkScalar s_num = dp.cross(fClipVectors[fCurrClipPoint]); 1141 // if umbra point is inside the clip polygon 1142 if (s_num >= 0 && s_num <= denom) { 1143 segmentVector *= s_num/denom; 1144 *clipPoint = umbraPoint + segmentVector; 1145 return true; 1146 } 1147 } 1148 fCurrClipPoint = (fCurrClipPoint + 1) % fClipPolygon.count(); 1149 } while (fCurrClipPoint != startClipPoint); 1150 1151 return false; 1152 } 1153 1154 int SkSpotShadowTessellator::getClosestUmbraPoint(const SkPoint& p) { 1155 SkScalar minDistance = p.distanceToSqd(fUmbraPolygon[fCurrUmbraPoint]); 1156 int index = fCurrUmbraPoint; 1157 int dir = 1; 1158 int next = (index + dir) % fUmbraPolygon.count(); 1159 1160 // init travel direction 1161 SkScalar distance = p.distanceToSqd(fUmbraPolygon[next]); 1162 if (distance < minDistance) { 1163 index = next; 1164 minDistance = distance; 1165 } else { 1166 dir = fUmbraPolygon.count()-1; 1167 } 1168 1169 // iterate until we find a point that increases the distance 1170 next = (index + dir) % fUmbraPolygon.count(); 1171 distance = p.distanceToSqd(fUmbraPolygon[next]); 1172 while (distance < minDistance) { 1173 index = next; 1174 minDistance = distance; 1175 next = (index + dir) % fUmbraPolygon.count(); 1176 distance = p.distanceToSqd(fUmbraPolygon[next]); 1177 } 1178 1179 fCurrUmbraPoint = index; 1180 return index; 1181 } 1182 1183 void SkSpotShadowTessellator::mapPoints(SkScalar scale, const SkVector& xlate, 1184 SkPoint* pts, int count) { 1185 // TODO: vectorize 1186 for (int i = 0; i < count; ++i) { 1187 pts[i] *= scale; 1188 pts[i] += xlate; 1189 } 1190 } 1191 1192 static bool duplicate_pt(const SkPoint& p0, const SkPoint& p1) { 1193 static constexpr SkScalar kClose = (SK_Scalar1 / 16); 1194 static constexpr SkScalar kCloseSqd = kClose*kClose; 1195 1196 SkScalar distSq = p0.distanceToSqd(p1); 1197 return distSq < kCloseSqd; 1198 } 1199 1200 static SkScalar perp_dot(const SkPoint& p0, const SkPoint& p1, const SkPoint& p2) { 1201 SkVector v0 = p1 - p0; 1202 SkVector v1 = p2 - p0; 1203 return v0.cross(v1); 1204 } 1205 1206 static bool is_collinear(const SkPoint& p0, const SkPoint& p1, const SkPoint& p2) { 1207 return (SkScalarNearlyZero(perp_dot(p0, p1, p2))); 1208 } 1209 1210 void SkSpotShadowTessellator::handleLine(const SkPoint& p) { 1211 // remove coincident points and add to centroid 1212 if (fPathPolygon.count() > 0) { 1213 const SkPoint& lastPoint = fPathPolygon[fPathPolygon.count() - 1]; 1214 if (duplicate_pt(p, lastPoint)) { 1215 return; 1216 } 1217 SkScalar quadArea = lastPoint.cross(p); 1218 fCentroid.fX += (p.fX + lastPoint.fX) * quadArea; 1219 fCentroid.fY += (p.fY + lastPoint.fY) * quadArea; 1220 fArea += quadArea; 1221 } 1222 1223 // try to remove collinear points 1224 if (fPathPolygon.count() > 1 && is_collinear(fPathPolygon[fPathPolygon.count()-2], 1225 fPathPolygon[fPathPolygon.count()-1], 1226 p)) { 1227 fPathPolygon[fPathPolygon.count() - 1] = p; 1228 } else { 1229 *fPathPolygon.push() = p; 1230 } 1231 } 1232 1233 bool SkSpotShadowTessellator::handlePolyPoint(const SkPoint& p) { 1234 if (fInitPoints.count() < 2) { 1235 *fInitPoints.push() = p; 1236 return true; 1237 } 1238 1239 if (fInitPoints.count() == 2) { 1240 // determine if cw or ccw 1241 SkScalar perpDot = perp_dot(fInitPoints[0], fInitPoints[1], p); 1242 if (SkScalarNearlyZero(perpDot)) { 1243 // nearly parallel, just treat as straight line and continue 1244 fInitPoints[1] = p; 1245 return true; 1246 } 1247 1248 // if perpDot > 0, winding is ccw 1249 fDirection = (perpDot > 0) ? -1 : 1; 1250 1251 // add first quad 1252 if (!compute_normal(fInitPoints[0], fInitPoints[1], fDirection, &fFirstOutset)) { 1253 // first two points are incident, make the third point the second and continue 1254 fInitPoints[1] = p; 1255 return true; 1256 } 1257 1258 fFirstOutset *= fRadius; 1259 fFirstPoint = fInitPoints[0]; 1260 fFirstVertexIndex = fPositions.count(); 1261 fPrevOutset = fFirstOutset; 1262 fPrevPoint = fFirstPoint; 1263 fPrevUmbraIndex = -1; 1264 1265 this->addInnerPoint(fFirstPoint); 1266 fPrevUmbraIndex = fFirstVertexIndex; 1267 1268 if (!fTransparent) { 1269 SkPoint clipPoint; 1270 bool isOutside = this->clipUmbraPoint(fPositions[fFirstVertexIndex], 1271 fCentroid, &clipPoint); 1272 if (isOutside) { 1273 *fPositions.push() = clipPoint; 1274 *fColors.push() = fUmbraColor; 1275 } 1276 fPrevUmbraOutside = isOutside; 1277 fFirstUmbraOutside = isOutside; 1278 } 1279 1280 SkPoint newPoint = fFirstPoint + fFirstOutset; 1281 *fPositions.push() = newPoint; 1282 *fColors.push() = fPenumbraColor; 1283 this->addEdge(fInitPoints[1], fFirstOutset); 1284 1285 // to ensure we skip this block next time 1286 *fInitPoints.push() = p; 1287 } 1288 1289 // if concave, abort 1290 SkScalar perpDot = perp_dot(fInitPoints[1], fInitPoints[2], p); 1291 if (fDirection*perpDot > 0) { 1292 return false; 1293 } 1294 1295 SkVector normal; 1296 if (compute_normal(fPrevPoint, p, fDirection, &normal)) { 1297 normal *= fRadius; 1298 this->addArc(normal, true); 1299 this->addEdge(p, normal); 1300 fInitPoints[1] = fInitPoints[2]; 1301 fInitPoints[2] = p; 1302 } 1303 1304 return true; 1305 } 1306 1307 bool SkSpotShadowTessellator::addInnerPoint(const SkPoint& pathPoint) { 1308 SkPoint umbraPoint; 1309 if (!fValidUmbra) { 1310 SkVector v = fCentroid - pathPoint; 1311 v *= 0.95f; 1312 umbraPoint = pathPoint + v; 1313 } else { 1314 umbraPoint = fUmbraPolygon[this->getClosestUmbraPoint(pathPoint)]; 1315 } 1316 1317 fPrevPoint = pathPoint; 1318 1319 // merge "close" points 1320 if (fPrevUmbraIndex == -1 || 1321 !duplicate_pt(umbraPoint, fPositions[fPrevUmbraIndex])) { 1322 *fPositions.push() = umbraPoint; 1323 *fColors.push() = fUmbraColor; 1324 1325 return false; 1326 } else { 1327 return true; 1328 } 1329 } 1330 1331 void SkSpotShadowTessellator::addEdge(const SkPoint& nextPoint, const SkVector& nextNormal) { 1332 // add next umbra point 1333 bool duplicate = this->addInnerPoint(nextPoint); 1334 int prevPenumbraIndex = duplicate ? fPositions.count()-1 : fPositions.count()-2; 1335 int currUmbraIndex = duplicate ? fPrevUmbraIndex : fPositions.count()-1; 1336 1337 if (!duplicate) { 1338 // add to center fan if transparent or centroid showing 1339 if (fTransparent) { 1340 *fIndices.push() = 0; 1341 *fIndices.push() = fPrevUmbraIndex; 1342 *fIndices.push() = currUmbraIndex; 1343 // otherwise add to clip ring 1344 } else { 1345 SkPoint clipPoint; 1346 bool isOutside = this->clipUmbraPoint(fPositions[currUmbraIndex], fCentroid, 1347 &clipPoint); 1348 if (isOutside) { 1349 *fPositions.push() = clipPoint; 1350 *fColors.push() = fUmbraColor; 1351 1352 *fIndices.push() = fPrevUmbraIndex; 1353 *fIndices.push() = currUmbraIndex; 1354 *fIndices.push() = currUmbraIndex + 1; 1355 if (fPrevUmbraOutside) { 1356 // fill out quad 1357 *fIndices.push() = fPrevUmbraIndex; 1358 *fIndices.push() = currUmbraIndex + 1; 1359 *fIndices.push() = fPrevUmbraIndex + 1; 1360 } 1361 } else if (fPrevUmbraOutside) { 1362 // add tri 1363 *fIndices.push() = fPrevUmbraIndex; 1364 *fIndices.push() = currUmbraIndex; 1365 *fIndices.push() = fPrevUmbraIndex + 1; 1366 } 1367 fPrevUmbraOutside = isOutside; 1368 } 1369 } 1370 1371 // add next penumbra point and quad 1372 SkPoint newPoint = nextPoint + nextNormal; 1373 *fPositions.push() = newPoint; 1374 *fColors.push() = fPenumbraColor; 1375 1376 if (!duplicate) { 1377 *fIndices.push() = fPrevUmbraIndex; 1378 *fIndices.push() = prevPenumbraIndex; 1379 *fIndices.push() = currUmbraIndex; 1380 } 1381 1382 *fIndices.push() = prevPenumbraIndex; 1383 *fIndices.push() = fPositions.count() - 1; 1384 *fIndices.push() = currUmbraIndex; 1385 1386 fPrevUmbraIndex = currUmbraIndex; 1387 fPrevOutset = nextNormal; 1388 } 1389 1390 /////////////////////////////////////////////////////////////////////////////////////////////////// 1391 1392 sk_sp<SkVertices> SkShadowTessellator::MakeAmbient(const SkPath& path, const SkMatrix& ctm, 1393 const SkPoint3& zPlane, bool transparent) { 1394 SkAmbientShadowTessellator ambientTess(path, ctm, zPlane, transparent); 1395 return ambientTess.releaseVertices(); 1396 } 1397 1398 sk_sp<SkVertices> SkShadowTessellator::MakeSpot(const SkPath& path, const SkMatrix& ctm, 1399 const SkPoint3& zPlane, const SkPoint3& lightPos, 1400 SkScalar lightRadius, bool transparent) { 1401 SkSpotShadowTessellator spotTess(path, ctm, zPlane, lightPos, lightRadius, transparent); 1402 return spotTess.releaseVertices(); 1403 } 1404
