Add geometric implementation for ambient shadows

BUG=skia:6119

Change-Id: I3140522f223c35fc059a33b593064897485dff7c
Reviewed-on: https://skia-review.googlesource.com/7273
Reviewed-by: Brian Salomon <bsalomon@google.com>
Commit-Queue: Jim Van Verth <jvanverth@google.com>

6 files changed, 505 insertions, 15 deletions

diff --git a/gn/effects.gni b/gn/effects.gni
index b3459e36d9..ea7dd725be 100644
--- a/gn/effects.gni
+++ b/gn/effects.gni
@@ -88,6 +88,8 @@ skia_effects_sources = [
   "$_src/effects/shadows/SkAmbientShadowMaskFilter.h",
   "$_src/effects/shadows/SkSpotShadowMaskFilter.cpp",
   "$_src/effects/shadows/SkSpotShadowMaskFilter.h",
+  "$_src/effects/shadows/SkShadowTessellator.cpp",
+  "$_src/effects/shadows/SkShadowTessellator.h",
 
   "$_include/effects/Sk1DPathEffect.h",
   "$_include/effects/Sk2DPathEffect.h",
diff --git a/samplecode/SampleAndroidShadows.cpp b/samplecode/SampleAndroidShadows.cpp
index d9e513b5c4..8f2859282b 100644
--- a/samplecode/SampleAndroidShadows.cpp
+++ b/samplecode/SampleAndroidShadows.cpp
@@ -25,6 +25,8 @@ class ShadowsView : public SampleView {
     SkPath    fRectPath;
     SkPath    fRRPath;
     SkPath    fCirclePath;
+    SkPath    fFunkyRRPath;
+    SkPath    fCubicPath;
     SkPoint3  fLightPos;
 
     bool      fShowAmbient;
@@ -46,6 +48,13 @@ protected:
         fCirclePath.addCircle(0, 0, 50);
         fRectPath.addRect(SkRect::MakeXYWH(-100, -50, 200, 100));
         fRRPath.addRRect(SkRRect::MakeRectXY(SkRect::MakeXYWH(-100, -50, 200, 100), 4, 4));
+        fFunkyRRPath.addRoundRect(SkRect::MakeXYWH(-50, -50, SK_Scalar1 * 100, SK_Scalar1 * 100),
+                                  40 * SK_Scalar1, 20 * SK_Scalar1,
+                                  SkPath::kCW_Direction);
+        fCubicPath.cubicTo(100 * SK_Scalar1, 50 * SK_Scalar1,
+                           20 * SK_Scalar1, 100 * SK_Scalar1,
+                           0 * SK_Scalar1, 0 * SK_Scalar1);
+
         fLightPos = SkPoint3::Make(-700, -700, 2800);
     }
 
@@ -431,20 +440,20 @@ protected:
         canvas->translate(200, 90);
         lightPos.fX += 200;
         lightPos.fY += 90;
-        this->drawShadowedPath(canvas, fRectPath, 2, paint, kAmbientAlpha,
+        this->drawShadowedPath(canvas, fRRPath, 2, paint, kAmbientAlpha,
                                lightPos, kLightWidth, kSpotAlpha);
 
         paint.setColor(SK_ColorRED);
         canvas->translate(250, 0);
         lightPos.fX += 250;
-        this->drawShadowedPath(canvas, fRRPath, 4, paint, kAmbientAlpha,
+        this->drawShadowedPath(canvas, fRectPath, 4, paint, kAmbientAlpha,
                                lightPos, kLightWidth, kSpotAlpha);
 
         paint.setColor(SK_ColorBLUE);
         canvas->translate(-250, 110);
         lightPos.fX -= 250;
         lightPos.fY += 110;
-        this->drawShadowedPath(canvas, fCirclePath, 8, paint, 0.0f,
+        this->drawShadowedPath(canvas, fCirclePath, 8, paint, 0,
                                lightPos, kLightWidth, 0.5f);
 
         paint.setColor(SK_ColorGREEN);
@@ -452,6 +461,19 @@ protected:
         lightPos.fX += 250;
         this->drawShadowedPath(canvas, fRRPath, 64, paint, kAmbientAlpha,
                                lightPos, kLightWidth, kSpotAlpha);
+
+        paint.setColor(SK_ColorYELLOW);
+        canvas->translate(-250, 110);
+        lightPos.fX -= 250;
+        lightPos.fY += 110;
+        this->drawShadowedPath(canvas, fFunkyRRPath, 8, paint, kAmbientAlpha,
+                               lightPos, kLightWidth, kSpotAlpha);
+
+        paint.setColor(SK_ColorCYAN);
+        canvas->translate(250, 0);
+        lightPos.fX += 250;
+        this->drawShadowedPath(canvas, fCubicPath, 16, paint, kAmbientAlpha,
+                               lightPos, kLightWidth, kSpotAlpha);
     }
 
 protected:
diff --git a/src/effects/SkGaussianEdgeShader.cpp b/src/effects/SkGaussianEdgeShader.cpp
index e1c30c8fbf..7405fd14d9 100644
--- a/src/effects/SkGaussianEdgeShader.cpp
+++ b/src/effects/SkGaussianEdgeShader.cpp
@@ -79,9 +79,10 @@ public:
 
             if (!args.fGpImplementsDistanceVector) {
                 fragBuilder->codeAppendf("// GP does not implement fsDistanceVector - "
-                                         " returning grey in GLSLGaussianEdgeFP\n");
-                fragBuilder->codeAppendf("vec4 color = %s;", args.fInputColor);
-                fragBuilder->codeAppendf("%s = vec4(0.0, 0.0, 0.0, color.r);", args.fOutputColor);
+                                         " using alpha as input to GLSLGaussianEdgeFP\n");
+                fragBuilder->codeAppendf("float factor = 1.0 - %s.a;", args.fInputColor);
+                fragBuilder->codeAppend("factor = exp(-factor * factor * 4.0) - 0.018;");
+                fragBuilder->codeAppendf("%s = vec4(0.0, 0.0, 0.0, factor);", args.fOutputColor);
             } else {
                 fragBuilder->codeAppendf("vec4 color = %s;", args.fInputColor);
                 fragBuilder->codeAppend("float radius = color.r*256.0*64.0 + color.g*64.0;");
diff --git a/src/effects/shadows/SkAmbientShadowMaskFilter.cpp b/src/effects/shadows/SkAmbientShadowMaskFilter.cpp
index 3dfd84eedc..e378c184b9 100755
--- a/src/effects/shadows/SkAmbientShadowMaskFilter.cpp
+++ b/src/effects/shadows/SkAmbientShadowMaskFilter.cpp
@@ -22,6 +22,7 @@
 #include "glsl/GrGLSLFragmentShaderBuilder.h"
 #include "glsl/GrGLSLProgramDataManager.h"
 #include "glsl/GrGLSLUniformHandler.h"
+#include "SkShadowTessellator.h"
 #include "SkStrokeRec.h"
 #endif
 
@@ -132,6 +133,56 @@ void SkAmbientShadowMaskFilterImpl::flatten(SkWriteBuffer& buffer) const {
 
 ///////////////////////////////////////////////////////////////////////////////////////////////////
 
+//
+// Shader for managing the shadow's edge. a in the input color represents the initial
+// edge color, which is transformed by a Gaussian function. b represents the blend factor,
+// which is multiplied by this transformed value.
+//
+class ShadowEdgeFP : public GrFragmentProcessor {
+public:
+    ShadowEdgeFP() {
+        this->initClassID<ShadowEdgeFP>();
+    }
+
+    class GLSLShadowEdgeFP : public GrGLSLFragmentProcessor {
+    public:
+        GLSLShadowEdgeFP() {}
+
+        void emitCode(EmitArgs& args) override {
+            GrGLSLFPFragmentBuilder* fragBuilder = args.fFragBuilder;
+
+            fragBuilder->codeAppendf("float factor = 1.0 - %s.a;", args.fInputColor);
+            fragBuilder->codeAppend("factor = exp(-factor * factor * 4.0) - 0.018;");
+            fragBuilder->codeAppendf("%s = vec4(0.0, 0.0, 0.0, %s.b*factor);", args.fOutputColor,
+                                     args.fInputColor);
+        }
+
+        static void GenKey(const GrProcessor&, const GrShaderCaps&, GrProcessorKeyBuilder*) {}
+
+    protected:
+        void onSetData(const GrGLSLProgramDataManager& pdman, const GrProcessor& proc) override {}
+    };
+
+    void onGetGLSLProcessorKey(const GrShaderCaps& caps, GrProcessorKeyBuilder* b) const override {
+        GLSLShadowEdgeFP::GenKey(*this, caps, b);
+    }
+
+    const char* name() const override { return "ShadowEdgeFP"; }
+
+    void onComputeInvariantOutput(GrInvariantOutput* inout) const override {
+        inout->mulByUnknownFourComponents();
+    }
+
+private:
+    GrGLSLFragmentProcessor* onCreateGLSLInstance() const override {
+        return new GLSLShadowEdgeFP();
+    }
+
+    bool onIsEqual(const GrFragmentProcessor& proc) const override { return true; }
+};
+
+///////////////////////////////////////////////////////////////////////////////////////////////////
+
 bool SkAmbientShadowMaskFilterImpl::canFilterMaskGPU(const SkRRect& devRRect,
                                                      const SkIRect& clipBounds,
                                                      const SkMatrix& ctm,
@@ -141,16 +192,29 @@ bool SkAmbientShadowMaskFilterImpl::canFilterMaskGPU(const SkRRect& devRRect,
     return true;
 }
 
+static const float kHeightFactor = 1.0f / 128.0f;
+static const float kGeomFactor = 64.0f;
+
 bool SkAmbientShadowMaskFilterImpl::directFilterMaskGPU(GrTextureProvider* texProvider,
-                                                        GrRenderTargetContext* drawContext,
+                                                        GrRenderTargetContext* rtContext,
                                                         GrPaint&& paint,
                                                         const GrClip& clip,
                                                         const SkMatrix& viewMatrix,
-                                                        const SkStrokeRec& strokeRec,
+                                                        const SkStrokeRec&,
                                                         const SkPath& path) const {
-    SkASSERT(drawContext);
+    SkASSERT(rtContext);
     // TODO: this will not handle local coordinates properly
 
+    if (fAmbientAlpha <= 0.0f) {
+        return true;
+    }
+
+    // only convex paths for now
+    if (!path.isConvex()) {
+        return false;
+    }
+
+#ifdef SUPPORT_FAST_PATH
     // if circle
     // TODO: switch to SkScalarNearlyEqual when either oval renderer is updated or we
     // have our own GeometryProc.
@@ -163,9 +227,28 @@ bool SkAmbientShadowMaskFilterImpl::directFilterMaskGPU(GrTextureProvider* texPr
         return this->directFilterRRectMaskGPU(nullptr, drawContext, std::move(paint), clip,
                                               SkMatrix::I(), strokeRec, rrect, rrect);
     }
+#endif
 
-    // TODO
-    return false;
+    SkScalar radius = fOccluderHeight * kHeightFactor * kGeomFactor;
+    SkScalar umbraAlpha = SkScalarInvert((1.0f+SkTMax(fOccluderHeight * kHeightFactor, 0.0f)));
+    // umbraColor is the interior value, penumbraColor the exterior value.
+    // umbraAlpha is the factor that is linearly interpolated from outside to inside, and
+    // then "blurred" by the ShadowEdgeFP. It is then multiplied by fAmbientAlpha to get
+    // the final alpha.
+    GrColor  umbraColor = GrColorPackRGBA(0, 0, fAmbientAlpha*255.9999f, umbraAlpha*255.9999f);
+    GrColor  penumbraColor = GrColorPackRGBA(0, 0, fAmbientAlpha*255.9999f, 0);
+
+    SkAmbientShadowTessellator tess(SkMatrix::I(), path, radius, umbraColor, penumbraColor,
+                                SkToBool(fFlags & SkShadowFlags::kTransparentOccluder_ShadowFlag));
+
+    sk_sp<ShadowEdgeFP> edgeFP(new ShadowEdgeFP);
+    paint.addColorFragmentProcessor(edgeFP);
+
+    rtContext->drawVertices(clip, std::move(paint), SkMatrix::I(), kTriangles_GrPrimitiveType,
+                            tess.vertexCount(), tess.positions(), nullptr,
+                            tess.colors(), tess.indices(), tess.indexCount());
+
+    return true;
 }
 
 bool SkAmbientShadowMaskFilterImpl::directFilterRRectMaskGPU(GrContext*,
@@ -176,6 +259,10 @@ bool SkAmbientShadowMaskFilterImpl::directFilterRRectMaskGPU(GrContext*,
                                                              const SkStrokeRec& strokeRec,
                                                              const SkRRect& rrect,
                                                              const SkRRect& devRRect) const {
+#ifndef SUPPORT_FAST_PATH
+    return false;
+#endif
+
     // It's likely the caller has already done these checks, but we have to be sure.
     // TODO: support analytic blurring of general rrect
 
@@ -207,9 +294,6 @@ bool SkAmbientShadowMaskFilterImpl::directFilterRRectMaskGPU(GrContext*,
     // TODO: take flags into account when generating shadow data
 
     if (fAmbientAlpha > 0.0f) {
-        static const float kHeightFactor = 1.0f / 128.0f;
-        static const float kGeomFactor = 64.0f;
-
         SkScalar srcSpaceAmbientRadius = fOccluderHeight * kHeightFactor * kGeomFactor;
         const float umbraAlpha = (1.0f + SkTMax(fOccluderHeight * kHeightFactor, 0.0f));
         const SkScalar ambientOffset = srcSpaceAmbientRadius * umbraAlpha;
@@ -252,7 +336,7 @@ sk_sp<GrTextureProxy> SkAmbientShadowMaskFilterImpl::filterMaskGPU(GrContext*,
     return nullptr;
 }
 
-#endif
+#endif // SK_SUPPORT_GPU
 
 #ifndef SK_IGNORE_TO_STRING
 void SkAmbientShadowMaskFilterImpl::toString(SkString* str) const {
diff --git a/src/effects/shadows/SkShadowTessellator.cpp b/src/effects/shadows/SkShadowTessellator.cpp
new file mode 100755
index 0000000000..4171b6ee73
--- /dev/null
+++ b/src/effects/shadows/SkShadowTessellator.cpp
@@ -0,0 +1,310 @@
+/*
+ * Copyright 2017 Google Inc.
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+
+#include "SkShadowTessellator.h"
+#include "SkGeometry.h"
+#include "GrPathUtils.h"
+
+static bool compute_normal(const SkPoint& p0, const SkPoint& p1, SkScalar radius, SkScalar dir,
+                           SkVector* newNormal) {
+    SkVector normal;
+    // compute perpendicular
+    normal.fX = p0.fY - p1.fY;
+    normal.fY = p1.fX - p0.fX;
+    if (!normal.normalize()) {
+        return false;
+    }
+    normal *= radius*dir;
+    *newNormal = normal;
+    return true;
+}
+
+static void compute_radial_steps(const SkVector& v1, const SkVector& v2, SkScalar r,
+                                 SkScalar* rotSin, SkScalar* rotCos, int* n) {
+    const SkScalar kRecipPixelsPerArcSegment = 0.25f;
+
+    SkScalar rCos = v1.dot(v2);
+    SkScalar rSin = v1.cross(v2);
+    SkScalar theta = SkScalarATan2(rSin, rCos);
+
+    SkScalar steps = r*theta*kRecipPixelsPerArcSegment;
+
+    SkScalar dTheta = theta / steps;
+    *rotSin = SkScalarSinCos(dTheta, rotCos);
+    *n = SkScalarFloorToInt(steps);
+}
+
+SkAmbientShadowTessellator::SkAmbientShadowTessellator(const SkMatrix& viewMatrix,
+                                                       const SkPath& path,
+                                                       SkScalar radius,
+                                                       GrColor umbraColor,
+                                                       GrColor penumbraColor,
+                                                       bool transparent)
+    : fRadius(radius)
+    , fUmbraColor(umbraColor)
+    , fPenumbraColor(penumbraColor)
+    , fTransparent(transparent)
+    , fPrevInnerIndex(-1) {
+
+    // Outer ring: 3*numPts
+    // Middle ring: numPts
+    fPositions.setReserve(4 * path.countPoints());
+    fColors.setReserve(4 * path.countPoints());
+    // Outer ring: 12*numPts
+    // Middle ring: 0
+    fIndices.setReserve(12 * path.countPoints());
+
+    fInitPoints.setReserve(3);
+
+    // walk around the path, tessellate and generate outer ring
+    // if original path is transparent, will accumulate sum of points for centroid
+    SkPath::Iter iter(path, true);
+    SkPoint pts[4];
+    SkPath::Verb verb;
+    if (fTransparent) {
+        *fPositions.push() = SkPoint::Make(0, 0);
+        *fColors.push() = umbraColor;
+        fCentroidCount = 0;
+    }
+    while ((verb = iter.next(pts)) != SkPath::kDone_Verb) {
+        switch (verb) {
+            case SkPath::kLine_Verb:
+                this->handleLine(viewMatrix, pts[1]);
+                break;
+            case SkPath::kQuad_Verb:
+                this->handleQuad(viewMatrix, pts);
+                break;
+            case SkPath::kCubic_Verb:
+                this->handleCubic(viewMatrix, pts);
+                break;
+            case SkPath::kConic_Verb:
+                this->handleConic(viewMatrix, pts, iter.conicWeight());
+                break;
+            case SkPath::kMove_Verb:
+            case SkPath::kClose_Verb:
+            case SkPath::kDone_Verb:
+                break;
+        }
+    }
+
+    SkVector normal;
+    if (compute_normal(fPositions[fPrevInnerIndex], fPositions[fFirstVertex], fRadius, fDirection,
+                       &normal)) {
+        this->addArc(normal);
+
+        // close out previous arc
+        *fPositions.push() = fPositions[fPrevInnerIndex] + normal;
+        *fColors.push() = fPenumbraColor;
+        *fIndices.push() = fPrevInnerIndex;
+        *fIndices.push() = fPositions.count() - 2;
+        *fIndices.push() = fPositions.count() - 1;
+
+        // add final edge
+        *fPositions.push() = fPositions[fFirstVertex] + normal;
+        *fColors.push() = fPenumbraColor;
+
+        *fIndices.push() = fPrevInnerIndex;
+        *fIndices.push() = fPositions.count() - 2;
+        *fIndices.push() = fFirstVertex;
+
+        *fIndices.push() = fPositions.count() - 2;
+        *fIndices.push() = fPositions.count() - 1;
+        *fIndices.push() = fFirstVertex;
+    }
+
+    // finalize centroid
+    if (fTransparent) {
+        fPositions[0] *= SkScalarFastInvert(fCentroidCount);
+
+        *fIndices.push() = 0;
+        *fIndices.push() = fPrevInnerIndex;
+        *fIndices.push() = fFirstVertex;
+    }
+
+    // final fan
+    if (fPositions.count() >= 3) {
+        fPrevInnerIndex = fFirstVertex;
+        fPrevNormal = normal;
+        this->addArc(fFirstNormal);
+
+        *fIndices.push() = fFirstVertex;
+        *fIndices.push() = fPositions.count() - 1;
+        *fIndices.push() = fFirstVertex + 1;
+    }
+}
+
+// tesselation tolerance values, in device space pixels
+static const SkScalar kQuadTolerance = 0.2f;
+static const SkScalar kCubicTolerance = 0.2f;
+static const SkScalar kConicTolerance = 0.5f;
+
+void SkAmbientShadowTessellator::handleLine(const SkPoint& p)  {
+    if (fInitPoints.count() < 2) {
+        *fInitPoints.push() = p;
+        return;
+    }
+
+    if (fInitPoints.count() == 2) {
+        // determine if cw or ccw
+        SkVector v0 = fInitPoints[1] - fInitPoints[0];
+        SkVector v1 = p - fInitPoints[0];
+        SkScalar perpDot = v0.fX*v1.fY - v0.fY*v1.fX;
+        if (SkScalarNearlyZero(perpDot)) {
+            // nearly parallel, just treat as straight line and continue
+            fInitPoints[1] = p;
+            return;
+        }
+
+        // if perpDot > 0, winding is ccw
+        fDirection = (perpDot > 0) ? -1 : 1;
+
+        // add first quad
+        if (!compute_normal(fInitPoints[0], fInitPoints[1], fRadius, fDirection,
+                            &fFirstNormal)) {
+            // first two points are incident, make the third point the second and continue
+            fInitPoints[1] = p;
+            return;
+        }
+
+        fFirstVertex = fPositions.count();
+        fPrevNormal = fFirstNormal;
+        fPrevInnerIndex = fFirstVertex;
+
+        *fPositions.push() = fInitPoints[0];
+        *fColors.push() = fUmbraColor;
+        *fPositions.push() = fInitPoints[0] + fFirstNormal;
+        *fColors.push() = fPenumbraColor;
+        if (fTransparent) {
+            fPositions[0] += fInitPoints[0];
+            fCentroidCount = 1;
+        }
+        this->addEdge(fInitPoints[1], fFirstNormal);
+
+        // to ensure we skip this block next time
+        *fInitPoints.push() = p;
+    }
+
+    SkVector normal;
+    if (compute_normal(fPositions[fPrevInnerIndex], p, fRadius, fDirection, &normal)) {
+        this->addArc(normal);
+        this->addEdge(p, normal);
+    }
+}
+
+void SkAmbientShadowTessellator::handleLine(const SkMatrix& m, SkPoint p)  {
+    m.mapPoints(&p, 1);
+    this->handleLine(p);
+}
+
+void SkAmbientShadowTessellator::handleQuad(const SkPoint pts[3]) {
+    int maxCount = GrPathUtils::quadraticPointCount(pts, kQuadTolerance);
+    fPointBuffer.setReserve(maxCount);
+    SkPoint* target = fPointBuffer.begin();
+    int count = GrPathUtils::generateQuadraticPoints(pts[0], pts[1], pts[2],
+                                                     kQuadTolerance, &target, maxCount);
+    fPointBuffer.setCount(count);
+    for (int i = 0; i < count; i++) {
+        this->handleLine(fPointBuffer[i]);
+    }
+}
+
+void SkAmbientShadowTessellator::handleQuad(const SkMatrix& m, SkPoint pts[3]) {
+    m.mapPoints(pts, 3);
+    this->handleQuad(pts);
+}
+
+void SkAmbientShadowTessellator::handleCubic(const SkMatrix& m, SkPoint pts[4]) {
+    m.mapPoints(pts, 4);
+    int maxCount = GrPathUtils::cubicPointCount(pts, kCubicTolerance);
+    fPointBuffer.setReserve(maxCount);
+    SkPoint* target = fPointBuffer.begin();
+    int count = GrPathUtils::generateCubicPoints(pts[0], pts[1], pts[2], pts[3],
+                                                 kCubicTolerance, &target, maxCount);
+    fPointBuffer.setCount(count);
+    for (int i = 0; i < count; i++) {
+        this->handleLine(fPointBuffer[i]);
+    }
+}
+
+void SkAmbientShadowTessellator::handleConic(const SkMatrix& m, SkPoint pts[3], SkScalar w) {
+    m.mapPoints(pts, 3);
+    SkAutoConicToQuads quadder;
+    const SkPoint* quads = quadder.computeQuads(pts, w, kConicTolerance);
+    SkPoint lastPoint = *(quads++);
+    int count = quadder.countQuads();
+    for (int i = 0; i < count; ++i) {
+        SkPoint quadPts[3];
+        quadPts[0] = lastPoint;
+        quadPts[1] = quads[0];
+        quadPts[2] = i == count - 1 ? pts[2] : quads[1];
+        this->handleQuad(quadPts);
+        lastPoint = quadPts[2];
+        quads += 2;
+    }
+}
+
+void SkAmbientShadowTessellator::addArc(const SkVector& nextNormal) {
+    // fill in fan from previous quad
+    SkScalar rotSin, rotCos;
+    int numSteps;
+    compute_radial_steps(fPrevNormal, nextNormal, fRadius, &rotSin, &rotCos, &numSteps);
+    SkVector prevNormal = fPrevNormal;
+    for (int i = 0; i < numSteps; ++i) {
+        SkVector nextNormal;
+        nextNormal.fX = prevNormal.fX*rotCos - prevNormal.fY*rotSin;
+        nextNormal.fY = prevNormal.fY*rotCos + prevNormal.fX*rotSin;
+        *fPositions.push() = fPositions[fPrevInnerIndex] + nextNormal;
+        *fColors.push() = fPenumbraColor;
+        *fIndices.push() = fPrevInnerIndex;
+        *fIndices.push() = fPositions.count() - 2;
+        *fIndices.push() = fPositions.count() - 1;
+
+        prevNormal = nextNormal;
+    }
+}
+
+
+void SkAmbientShadowTessellator::finishArcAndAddEdge(const SkPoint& nextPoint,
+                                                     const SkVector& nextNormal) {
+    // close out previous arc
+    *fPositions.push() = fPositions[fPrevInnerIndex] + nextNormal;
+    *fColors.push() = fPenumbraColor;
+    *fIndices.push() = fPrevInnerIndex;
+    *fIndices.push() = fPositions.count() - 2;
+    *fIndices.push() = fPositions.count() - 1;
+
+    this->addEdge(nextPoint, nextNormal);
+}
+
+void SkAmbientShadowTessellator::addEdge(const SkPoint& nextPoint, const SkVector& nextNormal) {
+    // add next quad
+    *fPositions.push() = nextPoint;
+    *fColors.push() = fUmbraColor;
+    *fPositions.push() = nextPoint + nextNormal;
+    *fColors.push() = fPenumbraColor;
+
+    *fIndices.push() = fPrevInnerIndex;
+    *fIndices.push() = fPositions.count() - 3;
+    *fIndices.push() = fPositions.count() - 2;
+
+    *fIndices.push() = fPositions.count() - 3;
+    *fIndices.push() = fPositions.count() - 1;
+    *fIndices.push() = fPositions.count() - 2;
+
+    // if transparent, add point to first one in array and add to center fan
+    if (fTransparent) {
+        fPositions[0] += nextPoint;
+        ++fCentroidCount;
+
+        *fIndices.push() = 0;
+        *fIndices.push() = fPrevInnerIndex;
+        *fIndices.push() = fPositions.count() - 2;
+    }
+
+    fPrevInnerIndex = fPositions.count() - 2;
+    fPrevNormal = nextNormal;
+}
diff --git a/src/effects/shadows/SkShadowTessellator.h b/src/effects/shadows/SkShadowTessellator.h
new file mode 100755
index 0000000000..76ff3b7c01
--- /dev/null
+++ b/src/effects/shadows/SkShadowTessellator.h
@@ -0,0 +1,71 @@
+/*
+ * Copyright 2017 Google Inc.
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+
+#ifndef SkShadowTessellator_DEFINED
+#define SkShadowTessellator_DEFINED
+
+#include "GrColor.h"
+#include "SkTDArray.h"
+#include "SkPoint.h"
+
+class SkMatrix;
+class SkPath;
+
+/**
+ * This class generates an ambient shadow for a path by walking the path, outsetting by the
+ * radius, and setting inner and outer colors to umbraColor and penumbraColor, respectively.
+ * If transparent is true, then the center of the ambient shadow will be filled in.
+ */
+class SkAmbientShadowTessellator {
+public:
+    SkAmbientShadowTessellator(const SkMatrix& viewMatrix, const SkPath& path, SkScalar radius,
+                               GrColor umbraColor, GrColor penumbraColor, bool transparent);
+
+    int      vertexCount() { return fPositions.count(); }
+    SkPoint* positions() { return fPositions.begin(); }
+    GrColor* colors() { return fColors.begin(); }
+    int      indexCount() { return fIndices.count(); }
+    uint16_t* indices() { return fIndices.begin(); }
+
+private:
+    void handleLine(const SkPoint& p);
+    void handleLine(const SkMatrix& m, SkPoint p);
+
+    void handleQuad(const SkPoint pts[3]);
+    void handleQuad(const SkMatrix& m, SkPoint pts[3]);
+
+    void handleCubic(const SkMatrix& m, SkPoint pts[4]);
+
+    void handleConic(const SkMatrix& m, SkPoint pts[3], SkScalar w);
+
+    void addArc(const SkVector& nextNormal);
+    void finishArcAndAddEdge(const SkVector& nextPoint, const SkVector& nextNormal);
+    void addEdge(const SkVector& nextPoint, const SkVector& nextNormal);
+
+    SkScalar            fRadius;
+    GrColor             fUmbraColor;
+    GrColor             fPenumbraColor;
+    bool                fTransparent;
+
+    SkTDArray<SkPoint>  fPositions;
+    SkTDArray<GrColor>  fColors;
+    SkTDArray<uint16_t> fIndices;
+
+    int                 fPrevInnerIndex;
+    SkVector            fPrevNormal;
+    int                 fFirstVertex;
+    SkVector            fFirstNormal;
+    SkScalar            fDirection;
+    int                 fCentroidCount;
+
+    // first three points
+    SkTDArray<SkPoint>  fInitPoints;
+    // temporary buffer
+    SkTDArray<SkPoint>  fPointBuffer;
+};
+
+#endif