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