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