submodule/skia/src/utils/SkShadowTessellator.cpp

   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
   9 #include "src/utils/SkShadowTessellator.h"
  10
  11 #include "include/core/SkColor.h"
  12 #include "include/core/SkMatrix.h"
  13 #include "include/core/SkPath.h"
  14 #include "include/core/SkPoint.h"
  15 #include "include/core/SkPoint3.h"
  16 #include "include/core/SkRect.h"
  17 #include "include/core/SkTypes.h"
  18 #include "include/core/SkVertices.h"
  19 #include "include/private/SkColorData.h"
  20 #include "include/private/SkFloatingPoint.h"
  21 #include "include/private/SkTDArray.h"
  22 #include "include/private/SkTemplates.h"
  23 #include "src/core/SkDrawShadowInfo.h"
  24 #include "src/core/SkGeometry.h"
  25 #include "src/core/SkPointPriv.h"
  26 #include "src/core/SkRectPriv.h"
  27 #include "src/utils/SkPolyUtils.h"
  28
  29 #include <algorithm>
  30
  31 #if SK_SUPPORT_GPU
  32 #include "src/gpu/ganesh/geometry/GrPathUtils.h"
  33 #endif
  34
  35
  36 /**
  37  * Base class
  38  */
  39 class SkBaseShadowTessellator {
  40 public:
  41     SkBaseShadowTessellator(const SkPoint3& zPlaneParams, const SkRect& bounds, bool transparent);
  42     virtual ~SkBaseShadowTessellator() {}
  43
  44     sk_sp<SkVertices> releaseVertices() {
  45         if (!fSucceeded) {
  46             return nullptr;
  47         }
  48         return SkVertices::MakeCopy(SkVertices::kTriangles_VertexMode, this->vertexCount(),
  49                                     fPositions.begin(), nullptr, fColors.begin(),
  50                                     this->indexCount(), fIndices.begin());
  51     }
  52
  53 protected:
  54     inline static constexpr auto kMinHeight = 0.1f;
  55     inline static constexpr auto kPenumbraColor = SK_ColorTRANSPARENT;
  56     inline static constexpr auto kUmbraColor = SK_ColorBLACK;
  57
  58     int vertexCount() const { return fPositions.count(); }
  59     int indexCount() const { return fIndices.count(); }
  60
  61     // initialization methods
  62     bool accumulateCentroid(const SkPoint& c, const SkPoint& n);
  63     bool checkConvexity(const SkPoint& p0, const SkPoint& p1, const SkPoint& p2);
  64     void finishPathPolygon();
  65
  66     // convex shadow methods
  67     bool computeConvexShadow(SkScalar inset, SkScalar outset, bool doClip);
  68     void computeClipVectorsAndTestCentroid();
  69     bool clipUmbraPoint(const SkPoint& umbraPoint, const SkPoint& centroid, SkPoint* clipPoint);
  70     void addEdge(const SkVector& nextPoint, const SkVector& nextNormal, SkColor umbraColor,
  71                  const SkTDArray<SkPoint>& umbraPolygon, bool lastEdge, bool doClip);
  72     bool addInnerPoint(const SkPoint& pathPoint, SkColor umbraColor,
  73                        const SkTDArray<SkPoint>& umbraPolygon, int* currUmbraIndex);
  74     int getClosestUmbraIndex(const SkPoint& point, const SkTDArray<SkPoint>& umbraPolygon);
  75
  76     // concave shadow methods
  77     bool computeConcaveShadow(SkScalar inset, SkScalar outset);
  78     void stitchConcaveRings(const SkTDArray<SkPoint>& umbraPolygon,
  79                             SkTDArray<int>* umbraIndices,
  80                             const SkTDArray<SkPoint>& penumbraPolygon,
  81                             SkTDArray<int>* penumbraIndices);
  82
  83     void handleLine(const SkPoint& p);
  84     void handleLine(const SkMatrix& m, SkPoint* p);
  85
  86     void handleQuad(const SkPoint pts[3]);
  87     void handleQuad(const SkMatrix& m, SkPoint pts[3]);
  88
  89     void handleCubic(const SkMatrix& m, SkPoint pts[4]);
  90
  91     void handleConic(const SkMatrix& m, SkPoint pts[3], SkScalar w);
  92
  93     bool addArc(const SkVector& nextNormal, SkScalar offset, bool finishArc);
  94
  95     void appendTriangle(uint16_t index0, uint16_t index1, uint16_t index2);
  96     void appendQuad(uint16_t index0, uint16_t index1, uint16_t index2, uint16_t index3);
  97
  98     SkScalar heightFunc(SkScalar x, SkScalar y) {
  99         return fZPlaneParams.fX*x + fZPlaneParams.fY*y + fZPlaneParams.fZ;
 100     }
 101
 102     SkPoint3            fZPlaneParams;
 103
 104     // temporary buffer
 105     SkTDArray<SkPoint>  fPointBuffer;
 106
 107     SkTDArray<SkPoint>  fPositions;
 108     SkTDArray<SkColor>  fColors;
 109     SkTDArray<uint16_t> fIndices;
 110
 111     SkTDArray<SkPoint>   fPathPolygon;
 112     SkTDArray<SkPoint>   fClipPolygon;
 113     SkTDArray<SkVector>  fClipVectors;
 114
 115     SkRect              fPathBounds;
 116     SkPoint             fCentroid;
 117     SkScalar            fArea;
 118     SkScalar            fLastArea;
 119     SkScalar            fLastCross;
 120
 121     int                 fFirstVertexIndex;
 122     SkVector            fFirstOutset;
 123     SkPoint             fFirstPoint;
 124
 125     bool                fSucceeded;
 126     bool                fTransparent;
 127     bool                fIsConvex;
 128     bool                fValidUmbra;
 129
 130     SkScalar            fDirection;
 131     int                 fPrevUmbraIndex;
 132     int                 fCurrUmbraIndex;
 133     int                 fCurrClipIndex;
 134     bool                fPrevUmbraOutside;
 135     bool                fFirstUmbraOutside;
 136     SkVector            fPrevOutset;
 137     SkPoint             fPrevPoint;
 138 };
 139
 140 static bool compute_normal(const SkPoint& p0, const SkPoint& p1, SkScalar dir,
 141                            SkVector* newNormal) {
 142     SkVector normal;
 143     // compute perpendicular
 144     normal.fX = p0.fY - p1.fY;
 145     normal.fY = p1.fX - p0.fX;
 146     normal *= dir;
 147     if (!normal.normalize()) {
 148         return false;
 149     }
 150     *newNormal = normal;
 151     return true;
 152 }
 153
 154 static bool duplicate_pt(const SkPoint& p0, const SkPoint& p1) {
 155     static constexpr SkScalar kClose = (SK_Scalar1 / 16);
 156     static constexpr SkScalar kCloseSqd = kClose * kClose;
 157
 158     SkScalar distSq = SkPointPriv::DistanceToSqd(p0, p1);
 159     return distSq < kCloseSqd;
 160 }
 161
 162 static SkScalar perp_dot(const SkPoint& p0, const SkPoint& p1, const SkPoint& p2) {
 163     SkVector v0 = p1 - p0;
 164     SkVector v1 = p2 - p1;
 165     return v0.cross(v1);
 166 }
 167
 168 SkBaseShadowTessellator::SkBaseShadowTessellator(const SkPoint3& zPlaneParams, const SkRect& bounds,
 169                                                  bool transparent)
 170         : fZPlaneParams(zPlaneParams)
 171         , fPathBounds(bounds)
 172         , fCentroid({0, 0})
 173         , fArea(0)
 174         , fLastArea(0)
 175         , fLastCross(0)
 176         , fFirstVertexIndex(-1)
 177         , fSucceeded(false)
 178         , fTransparent(transparent)
 179         , fIsConvex(true)
 180         , fValidUmbra(true)
 181         , fDirection(1)
 182         , fPrevUmbraIndex(-1)
 183         , fCurrUmbraIndex(0)
 184         , fCurrClipIndex(0)
 185         , fPrevUmbraOutside(false)
 186         , fFirstUmbraOutside(false) {
 187     // child classes will set reserve for positions, colors and indices
 188 }
 189
 190 bool SkBaseShadowTessellator::accumulateCentroid(const SkPoint& curr, const SkPoint& next) {
 191     if (duplicate_pt(curr, next)) {
 192         return false;
 193     }
 194
 195     SkASSERT(fPathPolygon.count() > 0);
 196     SkVector v0 = curr - fPathPolygon[0];
 197     SkVector v1 = next - fPathPolygon[0];
 198     SkScalar quadArea = v0.cross(v1);
 199     fCentroid.fX += (v0.fX + v1.fX) * quadArea;
 200     fCentroid.fY += (v0.fY + v1.fY) * quadArea;
 201     fArea += quadArea;
 202     // convexity check
 203     if (quadArea*fLastArea < 0) {
 204         fIsConvex = false;
 205     }
 206     if (0 != quadArea) {
 207         fLastArea = quadArea;
 208     }
 209
 210     return true;
 211 }
 212
 213 bool SkBaseShadowTessellator::checkConvexity(const SkPoint& p0,
 214                                              const SkPoint& p1,
 215                                              const SkPoint& p2) {
 216     SkScalar cross = perp_dot(p0, p1, p2);
 217     // skip collinear point
 218     if (SkScalarNearlyZero(cross)) {
 219         return false;
 220     }
 221
 222     // check for convexity
 223     if (fLastCross*cross < 0) {
 224         fIsConvex = false;
 225     }
 226     if (0 != cross) {
 227         fLastCross = cross;
 228     }
 229
 230     return true;
 231 }
 232
 233 void SkBaseShadowTessellator::finishPathPolygon() {
 234     if (fPathPolygon.count() > 1) {
 235         if (!this->accumulateCentroid(fPathPolygon[fPathPolygon.count() - 1], fPathPolygon[0])) {
 236             // remove coincident point
 237             fPathPolygon.pop();
 238         }
 239     }
 240
 241     if (fPathPolygon.count() > 2) {
 242         // do this before the final convexity check, so we use the correct fPathPolygon[0]
 243         fCentroid *= sk_ieee_float_divide(1, 3 * fArea);
 244         fCentroid += fPathPolygon[0];
 245         if (!checkConvexity(fPathPolygon[fPathPolygon.count() - 2],
 246                             fPathPolygon[fPathPolygon.count() - 1],
 247                             fPathPolygon[0])) {
 248             // remove collinear point
 249             fPathPolygon[0] = fPathPolygon[fPathPolygon.count() - 1];
 250             fPathPolygon.pop();
 251         }
 252     }
 253
 254     // if area is positive, winding is ccw
 255     fDirection = fArea > 0 ? -1 : 1;
 256 }
 257
 258 bool SkBaseShadowTessellator::computeConvexShadow(SkScalar inset, SkScalar outset, bool doClip) {
 259     if (doClip) {
 260         this->computeClipVectorsAndTestCentroid();
 261     }
 262
 263     // adjust inset distance and umbra color if necessary
 264     auto umbraColor = kUmbraColor;
 265     SkScalar minDistSq = SkPointPriv::DistanceToLineSegmentBetweenSqd(fCentroid,
 266                                                                       fPathPolygon[0],
 267                                                                       fPathPolygon[1]);
 268     SkRect bounds;
 269     bounds.setBounds(&fPathPolygon[0], fPathPolygon.count());
 270     for (int i = 1; i < fPathPolygon.count(); ++i) {
 271         int j = i + 1;
 272         if (i == fPathPolygon.count() - 1) {
 273             j = 0;
 274         }
 275         SkPoint currPoint = fPathPolygon[i];
 276         SkPoint nextPoint = fPathPolygon[j];
 277         SkScalar distSq = SkPointPriv::DistanceToLineSegmentBetweenSqd(fCentroid, currPoint,
 278                                                                        nextPoint);
 279         if (distSq < minDistSq) {
 280             minDistSq = distSq;
 281         }
 282     }
 283
 284     SkTDArray<SkPoint> insetPolygon;
 285     if (inset > SK_ScalarNearlyZero) {
 286         static constexpr auto kTolerance = 1.0e-2f;
 287         if (minDistSq < (inset + kTolerance)*(inset + kTolerance)) {
 288             // if the umbra would collapse, we back off a bit on inner blur and adjust the alpha
 289             auto newInset = SkScalarSqrt(minDistSq) - kTolerance;
 290             auto ratio = 128 * (newInset / inset + 1);
 291             SkASSERT(SkScalarIsFinite(ratio));
 292             // they aren't PMColors, but the interpolation algorithm is the same
 293             umbraColor = SkPMLerp(kUmbraColor, kPenumbraColor, (unsigned)ratio);
 294             inset = newInset;
 295         }
 296
 297         // generate inner ring
 298         if (!SkInsetConvexPolygon(&fPathPolygon[0], fPathPolygon.count(), inset,
 299                                   &insetPolygon)) {
 300             // not ideal, but in this case we'll inset using the centroid
 301             fValidUmbra = false;
 302         }
 303     }
 304     const SkTDArray<SkPoint>& umbraPolygon = (inset > SK_ScalarNearlyZero) ? insetPolygon
 305                                                                            : fPathPolygon;
 306
 307     // walk around the path polygon, generate outer ring and connect to inner ring
 308     if (fTransparent) {
 309         fPositions.push_back(fCentroid);
 310         fColors.push_back(umbraColor);
 311     }
 312     fCurrUmbraIndex = 0;
 313
 314     // initial setup
 315     // add first quad
 316     int polyCount = fPathPolygon.count();
 317     if (!compute_normal(fPathPolygon[polyCount - 1], fPathPolygon[0], fDirection, &fFirstOutset)) {
 318         // polygon should be sanitized by this point, so this is unrecoverable
 319         return false;
 320     }
 321
 322     fFirstOutset *= outset;
 323     fFirstPoint = fPathPolygon[polyCount - 1];
 324     fFirstVertexIndex = fPositions.count();
 325     fPrevOutset = fFirstOutset;
 326     fPrevPoint = fFirstPoint;
 327     fPrevUmbraIndex = -1;
 328
 329     this->addInnerPoint(fFirstPoint, umbraColor, umbraPolygon, &fPrevUmbraIndex);
 330
 331     if (!fTransparent && doClip) {
 332         SkPoint clipPoint;
 333         bool isOutside = this->clipUmbraPoint(fPositions[fFirstVertexIndex],
 334                                               fCentroid, &clipPoint);
 335         if (isOutside) {
 336             fPositions.push_back(clipPoint);
 337             fColors.push_back(umbraColor);
 338         }
 339         fPrevUmbraOutside = isOutside;
 340         fFirstUmbraOutside = isOutside;
 341     }
 342
 343     SkPoint newPoint = fFirstPoint + fFirstOutset;
 344     fPositions.push_back(newPoint);
 345     fColors.push_back(kPenumbraColor);
 346     this->addEdge(fPathPolygon[0], fFirstOutset, umbraColor, umbraPolygon, false, doClip);
 347
 348     for (int i = 1; i < polyCount; ++i) {
 349         SkVector normal;
 350         if (!compute_normal(fPrevPoint, fPathPolygon[i], fDirection, &normal)) {
 351             return false;
 352         }
 353         normal *= outset;
 354         this->addArc(normal, outset, true);
 355         this->addEdge(fPathPolygon[i], normal, umbraColor, umbraPolygon,
 356                       i == polyCount - 1, doClip);
 357     }
 358     SkASSERT(this->indexCount());
 359
 360     // final fan
 361     SkASSERT(fPositions.count() >= 3);
 362     if (this->addArc(fFirstOutset, outset, false)) {
 363         if (fFirstUmbraOutside) {
 364             this->appendTriangle(fFirstVertexIndex, fPositions.count() - 1,
 365                                  fFirstVertexIndex + 2);
 366         } else {
 367             this->appendTriangle(fFirstVertexIndex, fPositions.count() - 1,
 368                                  fFirstVertexIndex + 1);
 369         }
 370     } else {
 371         // no arc added, fix up by setting first penumbra point position to last one
 372         if (fFirstUmbraOutside) {
 373             fPositions[fFirstVertexIndex + 2] = fPositions[fPositions.count() - 1];
 374         } else {
 375             fPositions[fFirstVertexIndex + 1] = fPositions[fPositions.count() - 1];
 376         }
 377     }
 378
 379     return true;
 380 }
 381
 382 void SkBaseShadowTessellator::computeClipVectorsAndTestCentroid() {
 383     SkASSERT(fClipPolygon.count() >= 3);
 384     fCurrClipIndex = fClipPolygon.count() - 1;
 385
 386     // init clip vectors
 387     SkVector v0 = fClipPolygon[1] - fClipPolygon[0];
 388     SkVector v1 = fClipPolygon[2] - fClipPolygon[0];
 389     fClipVectors.push_back(v0);
 390
 391     // init centroid check
 392     bool hiddenCentroid = true;
 393     v1 = fCentroid - fClipPolygon[0];
 394     SkScalar initCross = v0.cross(v1);
 395
 396     for (int p = 1; p < fClipPolygon.count(); ++p) {
 397         // add to clip vectors
 398         v0 = fClipPolygon[(p + 1) % fClipPolygon.count()] - fClipPolygon[p];
 399         fClipVectors.push_back(v0);
 400         // Determine if transformed centroid is inside clipPolygon.
 401         v1 = fCentroid - fClipPolygon[p];
 402         if (initCross*v0.cross(v1) <= 0) {
 403             hiddenCentroid = false;
 404         }
 405     }
 406     SkASSERT(fClipVectors.count() == fClipPolygon.count());
 407
 408     fTransparent = fTransparent || !hiddenCentroid;
 409 }
 410
 411 void SkBaseShadowTessellator::addEdge(const SkPoint& nextPoint, const SkVector& nextNormal,
 412                                       SkColor umbraColor, const SkTDArray<SkPoint>& umbraPolygon,
 413                                       bool lastEdge, bool doClip) {
 414     // add next umbra point
 415     int currUmbraIndex;
 416     bool duplicate;
 417     if (lastEdge) {
 418         duplicate = false;
 419         currUmbraIndex = fFirstVertexIndex;
 420         fPrevPoint = nextPoint;
 421     } else {
 422         duplicate = this->addInnerPoint(nextPoint, umbraColor, umbraPolygon, &currUmbraIndex);
 423     }
 424     int prevPenumbraIndex = duplicate || (currUmbraIndex == fFirstVertexIndex)
 425         ? fPositions.count() - 1
 426         : fPositions.count() - 2;
 427     if (!duplicate) {
 428         // add to center fan if transparent or centroid showing
 429         if (fTransparent) {
 430             this->appendTriangle(0, fPrevUmbraIndex, currUmbraIndex);
 431             // otherwise add to clip ring
 432         } else if (doClip) {
 433             SkPoint clipPoint;
 434             bool isOutside = lastEdge ? fFirstUmbraOutside
 435                 : this->clipUmbraPoint(fPositions[currUmbraIndex], fCentroid,
 436                                        &clipPoint);
 437             if (isOutside) {
 438                 if (!lastEdge) {
 439                     fPositions.push_back(clipPoint);
 440                     fColors.push_back(umbraColor);
 441                 }
 442                 this->appendTriangle(fPrevUmbraIndex, currUmbraIndex, currUmbraIndex + 1);
 443                 if (fPrevUmbraOutside) {
 444                     // fill out quad
 445                     this->appendTriangle(fPrevUmbraIndex, currUmbraIndex + 1,
 446                                          fPrevUmbraIndex + 1);
 447                 }
 448             } else if (fPrevUmbraOutside) {
 449                 // add tri
 450                 this->appendTriangle(fPrevUmbraIndex, currUmbraIndex, fPrevUmbraIndex + 1);
 451             }
 452
 453             fPrevUmbraOutside = isOutside;
 454         }
 455     }
 456
 457     // add next penumbra point and quad
 458     SkPoint newPoint = nextPoint + nextNormal;
 459     fPositions.push_back(newPoint);
 460     fColors.push_back(kPenumbraColor);
 461
 462     if (!duplicate) {
 463         this->appendTriangle(fPrevUmbraIndex, prevPenumbraIndex, currUmbraIndex);
 464     }
 465     this->appendTriangle(prevPenumbraIndex, fPositions.count() - 1, currUmbraIndex);
 466
 467     fPrevUmbraIndex = currUmbraIndex;
 468     fPrevOutset = nextNormal;
 469 }
 470
 471 bool SkBaseShadowTessellator::clipUmbraPoint(const SkPoint& umbraPoint, const SkPoint& centroid,
 472                                              SkPoint* clipPoint) {
 473     SkVector segmentVector = centroid - umbraPoint;
 474
 475     int startClipPoint = fCurrClipIndex;
 476     do {
 477         SkVector dp = umbraPoint - fClipPolygon[fCurrClipIndex];
 478         SkScalar denom = fClipVectors[fCurrClipIndex].cross(segmentVector);
 479         SkScalar t_num = dp.cross(segmentVector);
 480         // if line segments are nearly parallel
 481         if (SkScalarNearlyZero(denom)) {
 482             // and collinear
 483             if (SkScalarNearlyZero(t_num)) {
 484                 return false;
 485             }
 486             // otherwise are separate, will try the next poly segment
 487             // else if crossing lies within poly segment
 488         } else if (t_num >= 0 && t_num <= denom) {
 489             SkScalar s_num = dp.cross(fClipVectors[fCurrClipIndex]);
 490             // if umbra point is inside the clip polygon
 491             if (s_num >= 0 && s_num <= denom) {
 492                 segmentVector *= s_num / denom;
 493                 *clipPoint = umbraPoint + segmentVector;
 494                 return true;
 495             }
 496         }
 497         fCurrClipIndex = (fCurrClipIndex + 1) % fClipPolygon.count();
 498     } while (fCurrClipIndex != startClipPoint);
 499
 500     return false;
 501 }
 502
 503 bool SkBaseShadowTessellator::addInnerPoint(const SkPoint& pathPoint, SkColor umbraColor,
 504                                             const SkTDArray<SkPoint>& umbraPolygon,
 505                                             int* currUmbraIndex) {
 506     SkPoint umbraPoint;
 507     if (!fValidUmbra) {
 508         SkVector v = fCentroid - pathPoint;
 509         v *= 0.95f;
 510         umbraPoint = pathPoint + v;
 511     } else {
 512         umbraPoint = umbraPolygon[this->getClosestUmbraIndex(pathPoint, umbraPolygon)];
 513     }
 514
 515     fPrevPoint = pathPoint;
 516
 517     // merge "close" points
 518     if (fPrevUmbraIndex == -1 ||
 519         !duplicate_pt(umbraPoint, fPositions[fPrevUmbraIndex])) {
 520         // if we've wrapped around, don't add a new point
 521         if (fPrevUmbraIndex >= 0 && duplicate_pt(umbraPoint, fPositions[fFirstVertexIndex])) {
 522             *currUmbraIndex = fFirstVertexIndex;
 523         } else {
 524             *currUmbraIndex = fPositions.count();
 525             fPositions.push_back(umbraPoint);
 526             fColors.push_back(umbraColor);
 527         }
 528         return false;
 529     } else {
 530         *currUmbraIndex = fPrevUmbraIndex;
 531         return true;
 532     }
 533 }
 534
 535 int SkBaseShadowTessellator::getClosestUmbraIndex(const SkPoint& p,
 536                                                   const SkTDArray<SkPoint>& umbraPolygon) {
 537     SkScalar minDistance = SkPointPriv::DistanceToSqd(p, umbraPolygon[fCurrUmbraIndex]);
 538     int index = fCurrUmbraIndex;
 539     int dir = 1;
 540     int next = (index + dir) % umbraPolygon.count();
 541
 542     // init travel direction
 543     SkScalar distance = SkPointPriv::DistanceToSqd(p, umbraPolygon[next]);
 544     if (distance < minDistance) {
 545         index = next;
 546         minDistance = distance;
 547     } else {
 548         dir = umbraPolygon.count() - 1;
 549     }
 550
 551     // iterate until we find a point that increases the distance
 552     next = (index + dir) % umbraPolygon.count();
 553     distance = SkPointPriv::DistanceToSqd(p, umbraPolygon[next]);
 554     while (distance < minDistance) {
 555         index = next;
 556         minDistance = distance;
 557         next = (index + dir) % umbraPolygon.count();
 558         distance = SkPointPriv::DistanceToSqd(p, umbraPolygon[next]);
 559     }
 560
 561     fCurrUmbraIndex = index;
 562     return index;
 563 }
 564
 565 bool SkBaseShadowTessellator::computeConcaveShadow(SkScalar inset, SkScalar outset) {
 566     if (!SkIsSimplePolygon(&fPathPolygon[0], fPathPolygon.count())) {
 567         return false;
 568     }
 569
 570     // shouldn't inset more than the half bounds of the polygon
 571     inset = std::min(inset, std::min(SkTAbs(SkRectPriv::HalfWidth(fPathBounds)),
 572                                      SkTAbs(SkRectPriv::HalfHeight(fPathBounds))));
 573     // generate inner ring
 574     SkTDArray<SkPoint> umbraPolygon;
 575     SkTDArray<int> umbraIndices;
 576     umbraIndices.setReserve(fPathPolygon.count());
 577     if (!SkOffsetSimplePolygon(&fPathPolygon[0], fPathPolygon.count(), fPathBounds, inset,
 578                                &umbraPolygon, &umbraIndices)) {
 579         // TODO: figure out how to handle this case
 580         return false;
 581     }
 582
 583     // generate outer ring
 584     SkTDArray<SkPoint> penumbraPolygon;
 585     SkTDArray<int> penumbraIndices;
 586     penumbraPolygon.setReserve(umbraPolygon.count());
 587     penumbraIndices.setReserve(umbraPolygon.count());
 588     if (!SkOffsetSimplePolygon(&fPathPolygon[0], fPathPolygon.count(), fPathBounds, -outset,
 589                                &penumbraPolygon, &penumbraIndices)) {
 590         // TODO: figure out how to handle this case
 591         return false;
 592     }
 593
 594     if (!umbraPolygon.count() || !penumbraPolygon.count()) {
 595         return false;
 596     }
 597
 598     // attach the rings together
 599     this->stitchConcaveRings(umbraPolygon, &umbraIndices, penumbraPolygon, &penumbraIndices);
 600
 601     return true;
 602 }
 603
 604 void SkBaseShadowTessellator::stitchConcaveRings(const SkTDArray<SkPoint>& umbraPolygon,
 605                                                  SkTDArray<int>* umbraIndices,
 606                                                  const SkTDArray<SkPoint>& penumbraPolygon,
 607                                                  SkTDArray<int>* penumbraIndices) {
 608     // TODO: only create and fill indexMap when fTransparent is true?
 609     SkAutoSTMalloc<64, uint16_t> indexMap(umbraPolygon.count());
 610
 611     // find minimum indices
 612     int minIndex = 0;
 613     int min = (*penumbraIndices)[0];
 614     for (int i = 1; i < (*penumbraIndices).count(); ++i) {
 615         if ((*penumbraIndices)[i] < min) {
 616             min = (*penumbraIndices)[i];
 617             minIndex = i;
 618         }
 619     }
 620     int currPenumbra = minIndex;
 621
 622     minIndex = 0;
 623     min = (*umbraIndices)[0];
 624     for (int i = 1; i < (*umbraIndices).count(); ++i) {
 625         if ((*umbraIndices)[i] < min) {
 626             min = (*umbraIndices)[i];
 627             minIndex = i;
 628         }
 629     }
 630     int currUmbra = minIndex;
 631
 632     // now find a case where the indices are equal (there should be at least one)
 633     int maxPenumbraIndex = fPathPolygon.count() - 1;
 634     int maxUmbraIndex = fPathPolygon.count() - 1;
 635     while ((*penumbraIndices)[currPenumbra] != (*umbraIndices)[currUmbra]) {
 636         if ((*penumbraIndices)[currPenumbra] < (*umbraIndices)[currUmbra]) {
 637             (*penumbraIndices)[currPenumbra] += fPathPolygon.count();
 638             maxPenumbraIndex = (*penumbraIndices)[currPenumbra];
 639             currPenumbra = (currPenumbra + 1) % penumbraPolygon.count();
 640         } else {
 641             (*umbraIndices)[currUmbra] += fPathPolygon.count();
 642             maxUmbraIndex = (*umbraIndices)[currUmbra];
 643             currUmbra = (currUmbra + 1) % umbraPolygon.count();
 644         }
 645     }
 646
 647     fPositions.push_back(penumbraPolygon[currPenumbra]);
 648     fColors.push_back(kPenumbraColor);
 649     int prevPenumbraIndex = 0;
 650     fPositions.push_back(umbraPolygon[currUmbra]);
 651     fColors.push_back(kUmbraColor);
 652     fPrevUmbraIndex = 1;
 653     indexMap[currUmbra] = 1;
 654
 655     int nextPenumbra = (currPenumbra + 1) % penumbraPolygon.count();
 656     int nextUmbra = (currUmbra + 1) % umbraPolygon.count();
 657     while ((*penumbraIndices)[nextPenumbra] <= maxPenumbraIndex ||
 658            (*umbraIndices)[nextUmbra] <= maxUmbraIndex) {
 659
 660         if ((*umbraIndices)[nextUmbra] == (*penumbraIndices)[nextPenumbra]) {
 661             // advance both one step
 662             fPositions.push_back(penumbraPolygon[nextPenumbra]);
 663             fColors.push_back(kPenumbraColor);
 664             int currPenumbraIndex = fPositions.count() - 1;
 665
 666             fPositions.push_back(umbraPolygon[nextUmbra]);
 667             fColors.push_back(kUmbraColor);
 668             int currUmbraIndex = fPositions.count() - 1;
 669             indexMap[nextUmbra] = currUmbraIndex;
 670
 671             this->appendQuad(prevPenumbraIndex, currPenumbraIndex,
 672                              fPrevUmbraIndex, currUmbraIndex);
 673
 674             prevPenumbraIndex = currPenumbraIndex;
 675             (*penumbraIndices)[currPenumbra] += fPathPolygon.count();
 676             currPenumbra = nextPenumbra;
 677             nextPenumbra = (currPenumbra + 1) % penumbraPolygon.count();
 678
 679             fPrevUmbraIndex = currUmbraIndex;
 680             (*umbraIndices)[currUmbra] += fPathPolygon.count();
 681             currUmbra = nextUmbra;
 682             nextUmbra = (currUmbra + 1) % umbraPolygon.count();
 683         }
 684
 685         while ((*penumbraIndices)[nextPenumbra] < (*umbraIndices)[nextUmbra] &&
 686                (*penumbraIndices)[nextPenumbra] <= maxPenumbraIndex) {
 687             // fill out penumbra arc
 688             fPositions.push_back(penumbraPolygon[nextPenumbra]);
 689             fColors.push_back(kPenumbraColor);
 690             int currPenumbraIndex = fPositions.count() - 1;
 691
 692             this->appendTriangle(prevPenumbraIndex, currPenumbraIndex, fPrevUmbraIndex);
 693
 694             prevPenumbraIndex = currPenumbraIndex;
 695             // this ensures the ordering when we wrap around
 696             (*penumbraIndices)[currPenumbra] += fPathPolygon.count();
 697             currPenumbra = nextPenumbra;
 698             nextPenumbra = (currPenumbra + 1) % penumbraPolygon.count();
 699         }
 700
 701         while ((*umbraIndices)[nextUmbra] < (*penumbraIndices)[nextPenumbra] &&
 702                (*umbraIndices)[nextUmbra] <= maxUmbraIndex) {
 703             // fill out umbra arc
 704             fPositions.push_back(umbraPolygon[nextUmbra]);
 705             fColors.push_back(kUmbraColor);
 706             int currUmbraIndex = fPositions.count() - 1;
 707             indexMap[nextUmbra] = currUmbraIndex;
 708
 709             this->appendTriangle(fPrevUmbraIndex, prevPenumbraIndex, currUmbraIndex);
 710
 711             fPrevUmbraIndex = currUmbraIndex;
 712             // this ensures the ordering when we wrap around
 713             (*umbraIndices)[currUmbra] += fPathPolygon.count();
 714             currUmbra = nextUmbra;
 715             nextUmbra = (currUmbra + 1) % umbraPolygon.count();
 716         }
 717     }
 718     // finish up by advancing both one step
 719     fPositions.push_back(penumbraPolygon[nextPenumbra]);
 720     fColors.push_back(kPenumbraColor);
 721     int currPenumbraIndex = fPositions.count() - 1;
 722
 723     fPositions.push_back(umbraPolygon[nextUmbra]);
 724     fColors.push_back(kUmbraColor);
 725     int currUmbraIndex = fPositions.count() - 1;
 726     indexMap[nextUmbra] = currUmbraIndex;
 727
 728     this->appendQuad(prevPenumbraIndex, currPenumbraIndex,
 729                      fPrevUmbraIndex, currUmbraIndex);
 730
 731     if (fTransparent) {
 732         SkTriangulateSimplePolygon(umbraPolygon.begin(), indexMap, umbraPolygon.count(),
 733                                    &fIndices);
 734     }
 735 }
 736
 737
 738 // tesselation tolerance values, in device space pixels
 739 #if SK_SUPPORT_GPU
 740 static constexpr SkScalar kQuadTolerance = 0.2f;
 741 static constexpr SkScalar kCubicTolerance = 0.2f;
 742 static constexpr SkScalar kQuadToleranceSqd = kQuadTolerance * kQuadTolerance;
 743 static constexpr SkScalar kCubicToleranceSqd = kCubicTolerance * kCubicTolerance;
 744 #endif
 745 static constexpr SkScalar kConicTolerance = 0.25f;
 746
 747 // clamps the point to the nearest 16th of a pixel
 748 static void sanitize_point(const SkPoint& in, SkPoint* out) {
 749     out->fX = SkScalarRoundToScalar(16.f*in.fX)*0.0625f;
 750     out->fY = SkScalarRoundToScalar(16.f*in.fY)*0.0625f;
 751 }
 752
 753 void SkBaseShadowTessellator::handleLine(const SkPoint& p) {
 754     SkPoint pSanitized;
 755     sanitize_point(p, &pSanitized);
 756
 757     if (fPathPolygon.count() > 0) {
 758         if (!this->accumulateCentroid(fPathPolygon[fPathPolygon.count() - 1], pSanitized)) {
 759             // skip coincident point
 760             return;
 761         }
 762     }
 763
 764     if (fPathPolygon.count() > 1) {
 765         if (!checkConvexity(fPathPolygon[fPathPolygon.count() - 2],
 766                             fPathPolygon[fPathPolygon.count() - 1],
 767                             pSanitized)) {
 768             // remove collinear point
 769             fPathPolygon.pop();
 770             // it's possible that the previous point is coincident with the new one now
 771             if (duplicate_pt(fPathPolygon[fPathPolygon.count() - 1], pSanitized)) {
 772                 fPathPolygon.pop();
 773             }
 774         }
 775     }
 776
 777     fPathPolygon.push_back(pSanitized);
 778 }
 779
 780 void SkBaseShadowTessellator::handleLine(const SkMatrix& m, SkPoint* p) {
 781     m.mapPoints(p, 1);
 782
 783     this->handleLine(*p);
 784 }
 785
 786 void SkBaseShadowTessellator::handleQuad(const SkPoint pts[3]) {
 787 #if SK_SUPPORT_GPU
 788     // check for degeneracy
 789     SkVector v0 = pts[1] - pts[0];
 790     SkVector v1 = pts[2] - pts[0];
 791     if (SkScalarNearlyZero(v0.cross(v1))) {
 792         return;
 793     }
 794     // TODO: Pull PathUtils out of Ganesh?
 795     int maxCount = GrPathUtils::quadraticPointCount(pts, kQuadTolerance);
 796     fPointBuffer.setCount(maxCount);
 797     SkPoint* target = fPointBuffer.begin();
 798     int count = GrPathUtils::generateQuadraticPoints(pts[0], pts[1], pts[2],
 799                                                      kQuadToleranceSqd, &target, maxCount);
 800     fPointBuffer.setCount(count);
 801     for (int i = 0; i < count; i++) {
 802         this->handleLine(fPointBuffer[i]);
 803     }
 804 #else
 805     // for now, just to draw something
 806     this->handleLine(pts[1]);
 807     this->handleLine(pts[2]);
 808 #endif
 809 }
 810
 811 void SkBaseShadowTessellator::handleQuad(const SkMatrix& m, SkPoint pts[3]) {
 812     m.mapPoints(pts, 3);
 813     this->handleQuad(pts);
 814 }
 815
 816 void SkBaseShadowTessellator::handleCubic(const SkMatrix& m, SkPoint pts[4]) {
 817     m.mapPoints(pts, 4);
 818 #if SK_SUPPORT_GPU
 819     // TODO: Pull PathUtils out of Ganesh?
 820     int maxCount = GrPathUtils::cubicPointCount(pts, kCubicTolerance);
 821     fPointBuffer.setCount(maxCount);
 822     SkPoint* target = fPointBuffer.begin();
 823     int count = GrPathUtils::generateCubicPoints(pts[0], pts[1], pts[2], pts[3],
 824                                                  kCubicToleranceSqd, &target, maxCount);
 825     fPointBuffer.setCount(count);
 826     for (int i = 0; i < count; i++) {
 827         this->handleLine(fPointBuffer[i]);
 828     }
 829 #else
 830     // for now, just to draw something
 831     this->handleLine(pts[1]);
 832     this->handleLine(pts[2]);
 833     this->handleLine(pts[3]);
 834 #endif
 835 }
 836
 837 void SkBaseShadowTessellator::handleConic(const SkMatrix& m, SkPoint pts[3], SkScalar w) {
 838     if (m.hasPerspective()) {
 839         w = SkConic::TransformW(pts, w, m);
 840     }
 841     m.mapPoints(pts, 3);
 842     SkAutoConicToQuads quadder;
 843     const SkPoint* quads = quadder.computeQuads(pts, w, kConicTolerance);
 844     SkPoint lastPoint = *(quads++);
 845     int count = quadder.countQuads();
 846     for (int i = 0; i < count; ++i) {
 847         SkPoint quadPts[3];
 848         quadPts[0] = lastPoint;
 849         quadPts[1] = quads[0];
 850         quadPts[2] = i == count - 1 ? pts[2] : quads[1];
 851         this->handleQuad(quadPts);
 852         lastPoint = quadPts[2];
 853         quads += 2;
 854     }
 855 }
 856
 857 bool SkBaseShadowTessellator::addArc(const SkVector& nextNormal, SkScalar offset, bool finishArc) {
 858     // fill in fan from previous quad
 859     SkScalar rotSin, rotCos;
 860     int numSteps;
 861     if (!SkComputeRadialSteps(fPrevOutset, nextNormal, offset, &rotSin, &rotCos, &numSteps)) {
 862         // recover as best we can
 863         numSteps = 0;
 864     }
 865     SkVector prevNormal = fPrevOutset;
 866     for (int i = 0; i < numSteps-1; ++i) {
 867         SkVector currNormal;
 868         currNormal.fX = prevNormal.fX*rotCos - prevNormal.fY*rotSin;
 869         currNormal.fY = prevNormal.fY*rotCos + prevNormal.fX*rotSin;
 870         fPositions.push_back(fPrevPoint + currNormal);
 871         fColors.push_back(kPenumbraColor);
 872         this->appendTriangle(fPrevUmbraIndex, fPositions.count() - 1, fPositions.count() - 2);
 873
 874         prevNormal = currNormal;
 875     }
 876     if (finishArc && numSteps) {
 877         fPositions.push_back(fPrevPoint + nextNormal);
 878         fColors.push_back(kPenumbraColor);
 879         this->appendTriangle(fPrevUmbraIndex, fPositions.count() - 1, fPositions.count() - 2);
 880     }
 881     fPrevOutset = nextNormal;
 882
 883     return (numSteps > 0);
 884 }
 885
 886 void SkBaseShadowTessellator::appendTriangle(uint16_t index0, uint16_t index1, uint16_t index2) {
 887     auto indices = fIndices.append(3);
 888
 889     indices[0] = index0;
 890     indices[1] = index1;
 891     indices[2] = index2;
 892 }
 893
 894 void SkBaseShadowTessellator::appendQuad(uint16_t index0, uint16_t index1,
 895                                          uint16_t index2, uint16_t index3) {
 896     auto indices = fIndices.append(6);
 897
 898     indices[0] = index0;
 899     indices[1] = index1;
 900     indices[2] = index2;
 901
 902     indices[3] = index2;
 903     indices[4] = index1;
 904     indices[5] = index3;
 905 }
 906
 907 //////////////////////////////////////////////////////////////////////////////////////////////////
 908
 909 class SkAmbientShadowTessellator : public SkBaseShadowTessellator {
 910 public:
 911     SkAmbientShadowTessellator(const SkPath& path, const SkMatrix& ctm,
 912                                const SkPoint3& zPlaneParams, bool transparent);
 913
 914 private:
 915     bool computePathPolygon(const SkPath& path, const SkMatrix& ctm);
 916
 917     using INHERITED = SkBaseShadowTessellator;
 918 };
 919
 920 SkAmbientShadowTessellator::SkAmbientShadowTessellator(const SkPath& path,
 921                                                        const SkMatrix& ctm,
 922                                                        const SkPoint3& zPlaneParams,
 923                                                        bool transparent)
 924         : INHERITED(zPlaneParams, path.getBounds(), transparent) {
 925     // Set base colors
 926     auto baseZ = heightFunc(fPathBounds.centerX(), fPathBounds.centerY());
 927     // umbraColor is the interior value, penumbraColor the exterior value.
 928     auto outset = SkDrawShadowMetrics::AmbientBlurRadius(baseZ);
 929     auto inset = outset * SkDrawShadowMetrics::AmbientRecipAlpha(baseZ) - outset;
 930
 931     if (!this->computePathPolygon(path, ctm)) {
 932         return;
 933     }
 934     if (fPathPolygon.count() < 3 || !SkScalarIsFinite(fArea)) {
 935         fSucceeded = true; // We don't want to try to blur these cases, so we will
 936                            // return an empty SkVertices instead.
 937         return;
 938     }
 939
 940     // Outer ring: 3*numPts
 941     // Middle ring: numPts
 942     fPositions.setReserve(4 * path.countPoints());
 943     fColors.setReserve(4 * path.countPoints());
 944     // Outer ring: 12*numPts
 945     // Middle ring: 0
 946     fIndices.setReserve(12 * path.countPoints());
 947
 948     if (fIsConvex) {
 949         fSucceeded = this->computeConvexShadow(inset, outset, false);
 950     } else {
 951         fSucceeded = this->computeConcaveShadow(inset, outset);
 952     }
 953 }
 954
 955 bool SkAmbientShadowTessellator::computePathPolygon(const SkPath& path, const SkMatrix& ctm) {
 956     fPathPolygon.setReserve(path.countPoints());
 957
 958     // walk around the path, tessellate and generate outer ring
 959     // if original path is transparent, will accumulate sum of points for centroid
 960     SkPath::Iter iter(path, true);
 961     SkPoint pts[4];
 962     SkPath::Verb verb;
 963     bool verbSeen = false;
 964     bool closeSeen = false;
 965     while ((verb = iter.next(pts)) != SkPath::kDone_Verb) {
 966         if (closeSeen) {
 967             return false;
 968         }
 969         switch (verb) {
 970             case SkPath::kLine_Verb:
 971                 this->handleLine(ctm, &pts[1]);
 972                 break;
 973             case SkPath::kQuad_Verb:
 974                 this->handleQuad(ctm, pts);
 975                 break;
 976             case SkPath::kCubic_Verb:
 977                 this->handleCubic(ctm, pts);
 978                 break;
 979             case SkPath::kConic_Verb:
 980                 this->handleConic(ctm, pts, iter.conicWeight());
 981                 break;
 982             case SkPath::kMove_Verb:
 983                 if (verbSeen) {
 984                     return false;
 985                 }
 986                 break;
 987             case SkPath::kClose_Verb:
 988             case SkPath::kDone_Verb:
 989                 closeSeen = true;
 990                 break;
 991         }
 992         verbSeen = true;
 993     }
 994
 995     this->finishPathPolygon();
 996     return true;
 997 }
 998
 999 ///////////////////////////////////////////////////////////////////////////////////////////////////
1000
1001 class SkSpotShadowTessellator : public SkBaseShadowTessellator {
1002 public:
1003     SkSpotShadowTessellator(const SkPath& path, const SkMatrix& ctm,
1004                             const SkPoint3& zPlaneParams, const SkPoint3& lightPos,
1005                             SkScalar lightRadius, bool transparent, bool directional);
1006
1007 private:
1008     bool computeClipAndPathPolygons(const SkPath& path, const SkMatrix& ctm,
1009                                     const SkMatrix& shadowTransform);
1010     void addToClip(const SkVector& nextPoint);
1011
1012     using INHERITED = SkBaseShadowTessellator;
1013 };
1014
1015 SkSpotShadowTessellator::SkSpotShadowTessellator(const SkPath& path, const SkMatrix& ctm,
1016                                                  const SkPoint3& zPlaneParams,
1017                                                  const SkPoint3& lightPos, SkScalar lightRadius,
1018                                                  bool transparent, bool directional)
1019     : INHERITED(zPlaneParams, path.getBounds(), transparent) {
1020
1021     // Compute the blur radius, scale and translation for the spot shadow.
1022     SkMatrix shadowTransform;
1023     SkScalar outset;
1024     if (!SkDrawShadowMetrics::GetSpotShadowTransform(lightPos, lightRadius, ctm, zPlaneParams,
1025                                                      path.getBounds(), directional,
1026                                                      &shadowTransform, &outset)) {
1027         return;
1028     }
1029     SkScalar inset = outset;
1030
1031     // compute rough clip bounds for umbra, plus offset polygon, plus centroid
1032     if (!this->computeClipAndPathPolygons(path, ctm, shadowTransform)) {
1033         return;
1034     }
1035     if (fClipPolygon.count() < 3 || fPathPolygon.count() < 3 || !SkScalarIsFinite(fArea)) {
1036         fSucceeded = true; // We don't want to try to blur these cases, so we will
1037                            // return an empty SkVertices instead.
1038         return;
1039     }
1040
1041     // TODO: calculate these reserves better
1042     // Penumbra ring: 3*numPts
1043     // Umbra ring: numPts
1044     // Inner ring: numPts
1045     fPositions.setReserve(5 * path.countPoints());
1046     fColors.setReserve(5 * path.countPoints());
1047     // Penumbra ring: 12*numPts
1048     // Umbra ring: 3*numPts
1049     fIndices.setReserve(15 * path.countPoints());
1050
1051     if (fIsConvex) {
1052         fSucceeded = this->computeConvexShadow(inset, outset, true);
1053     } else {
1054         fSucceeded = this->computeConcaveShadow(inset, outset);
1055     }
1056
1057     if (!fSucceeded) {
1058         return;
1059     }
1060
1061     fSucceeded = true;
1062 }
1063
1064 bool SkSpotShadowTessellator::computeClipAndPathPolygons(const SkPath& path, const SkMatrix& ctm,
1065                                                          const SkMatrix& shadowTransform) {
1066
1067     fPathPolygon.setReserve(path.countPoints());
1068     fClipPolygon.setReserve(path.countPoints());
1069
1070     // Walk around the path and compute clip polygon and path polygon.
1071     // Will also accumulate sum of areas for centroid.
1072     // For Bezier curves, we compute additional interior points on curve.
1073     SkPath::Iter iter(path, true);
1074     SkPoint pts[4];
1075     SkPoint clipPts[4];
1076     SkPath::Verb verb;
1077
1078     // coefficients to compute cubic Bezier at t = 5/16
1079     static constexpr SkScalar kA = 0.32495117187f;
1080     static constexpr SkScalar kB = 0.44311523437f;
1081     static constexpr SkScalar kC = 0.20141601562f;
1082     static constexpr SkScalar kD = 0.03051757812f;
1083
1084     SkPoint curvePoint;
1085     SkScalar w;
1086     bool closeSeen = false;
1087     bool verbSeen = false;
1088     while ((verb = iter.next(pts)) != SkPath::kDone_Verb) {
1089         if (closeSeen) {
1090             return false;
1091         }
1092         switch (verb) {
1093             case SkPath::kLine_Verb:
1094                 ctm.mapPoints(clipPts, &pts[1], 1);
1095                 this->addToClip(clipPts[0]);
1096                 this->handleLine(shadowTransform, &pts[1]);
1097                 break;
1098             case SkPath::kQuad_Verb:
1099                 ctm.mapPoints(clipPts, pts, 3);
1100                 // point at t = 1/2
1101                 curvePoint.fX = 0.25f*clipPts[0].fX + 0.5f*clipPts[1].fX + 0.25f*clipPts[2].fX;
1102                 curvePoint.fY = 0.25f*clipPts[0].fY + 0.5f*clipPts[1].fY + 0.25f*clipPts[2].fY;
1103                 this->addToClip(curvePoint);
1104                 this->addToClip(clipPts[2]);
1105                 this->handleQuad(shadowTransform, pts);
1106                 break;
1107             case SkPath::kConic_Verb:
1108                 ctm.mapPoints(clipPts, pts, 3);
1109                 w = iter.conicWeight();
1110                 // point at t = 1/2
1111                 curvePoint.fX = 0.25f*clipPts[0].fX + w*0.5f*clipPts[1].fX + 0.25f*clipPts[2].fX;
1112                 curvePoint.fY = 0.25f*clipPts[0].fY + w*0.5f*clipPts[1].fY + 0.25f*clipPts[2].fY;
1113                 curvePoint *= SkScalarInvert(0.5f + 0.5f*w);
1114                 this->addToClip(curvePoint);
1115                 this->addToClip(clipPts[2]);
1116                 this->handleConic(shadowTransform, pts, w);
1117                 break;
1118             case SkPath::kCubic_Verb:
1119                 ctm.mapPoints(clipPts, pts, 4);
1120                 // point at t = 5/16
1121                 curvePoint.fX = kA*clipPts[0].fX + kB*clipPts[1].fX
1122                               + kC*clipPts[2].fX + kD*clipPts[3].fX;
1123                 curvePoint.fY = kA*clipPts[0].fY + kB*clipPts[1].fY
1124                               + kC*clipPts[2].fY + kD*clipPts[3].fY;
1125                 this->addToClip(curvePoint);
1126                 // point at t = 11/16
1127                 curvePoint.fX = kD*clipPts[0].fX + kC*clipPts[1].fX
1128                               + kB*clipPts[2].fX + kA*clipPts[3].fX;
1129                 curvePoint.fY = kD*clipPts[0].fY + kC*clipPts[1].fY
1130                               + kB*clipPts[2].fY + kA*clipPts[3].fY;
1131                 this->addToClip(curvePoint);
1132                 this->addToClip(clipPts[3]);
1133                 this->handleCubic(shadowTransform, pts);
1134                 break;
1135             case SkPath::kMove_Verb:
1136                 if (verbSeen) {
1137                     return false;
1138                 }
1139                 break;
1140             case SkPath::kClose_Verb:
1141             case SkPath::kDone_Verb:
1142                 closeSeen = true;
1143                 break;
1144             default:
1145                 SkDEBUGFAIL("unknown verb");
1146         }
1147         verbSeen = true;
1148     }
1149
1150     this->finishPathPolygon();
1151     return true;
1152 }
1153
1154 void SkSpotShadowTessellator::addToClip(const SkPoint& point) {
1155     if (fClipPolygon.isEmpty() || !duplicate_pt(point, fClipPolygon[fClipPolygon.count() - 1])) {
1156         fClipPolygon.push_back(point);
1157     }
1158 }
1159
1160 ///////////////////////////////////////////////////////////////////////////////////////////////////
1161
1162 sk_sp<SkVertices> SkShadowTessellator::MakeAmbient(const SkPath& path, const SkMatrix& ctm,
1163                                                    const SkPoint3& zPlane, bool transparent) {
1164     if (!ctm.mapRect(path.getBounds()).isFinite() || !zPlane.isFinite()) {
1165         return nullptr;
1166     }
1167     SkAmbientShadowTessellator ambientTess(path, ctm, zPlane, transparent);
1168     return ambientTess.releaseVertices();
1169 }
1170
1171 sk_sp<SkVertices> SkShadowTessellator::MakeSpot(const SkPath& path, const SkMatrix& ctm,
1172                                                 const SkPoint3& zPlane, const SkPoint3& lightPos,
1173                                                 SkScalar lightRadius,  bool transparent,
1174                                                 bool directional) {
1175     if (!ctm.mapRect(path.getBounds()).isFinite() || !zPlane.isFinite() ||
1176         !lightPos.isFinite() || !(lightPos.fZ >= SK_ScalarNearlyZero) ||
1177         !SkScalarIsFinite(lightRadius) || !(lightRadius >= SK_ScalarNearlyZero)) {
1178         return nullptr;
1179     }
1180     SkSpotShadowTessellator spotTess(path, ctm, zPlane, lightPos, lightRadius, transparent,
1181                                      directional);
1182     return spotTess.releaseVertices();
1183 }