Draw more accurate thick-stroked Beziers (disabled)

Draw thick-stroked Beziers by computing the outset quadratic, measuring the error, and subdividing until the error is within a predetermined limit.

To try this CL out, change src/core/SkStroke.h:18 to

  #define QUAD_STROKE_APPROXIMATION 1

or from the command line: CPPFLAGS="-D QUAD_STROKE_APPROXIMATION=1" ./gyp_skia

Here's what's in this CL:

bench/BezierBench.cpp : a microbench for examining where the time is going
gm/beziers.cpp        : random Beziers with various thicknesses
gm/smallarc.cpp       : a distillation of bug skia:2769
samplecode/SampleRotateCircles.cpp : controls added for error, limit, width
src/core/SkStroke.cpp : the new stroke implementation (disabled)
tests/StrokerTest.cpp : a stroke torture test that checks normal and extreme values

The new stroke algorithm has a tweakable parameter:

  stroker.setError(1);  (SkStrokeRec.cpp:112)

The stroke error is the allowable gap between the midpoint of the stroke quadratic and the center Bezier. As the projection from the quadratic approaches the endpoints, the error is decreased proportionally so that it is always inside the quadratic curve.

An overview of how this works:
- For a given T range of a Bezier, compute the perpendiculars and find the points outset and inset for some radius.
- Construct tangents for the quadratic stroke.
- If the tangent don't intersect between them (may happen with cubics), subdivide.
- If the quadratic stroke end points are close (again, may happen with cubics), draw a line between them.
- Compute the quadratic formed by the intersecting tangents.
- If the midpoint of the quadratic is close to the midpoint of the Bezier perpendicular, return the quadratic.
- If the end of the stroke at the Bezier midpoint doesn't intersect the quad's bounds, subdivide.
- Find where the Bezier midpoint ray intersects the quadratic.
- If the intersection is too close to the quad's endpoints, subdivide.
- If the error is large proportional to the intersection's distance to the quad's endpoints, subdivide.

BUG=skia:723,skia:2769

Review URL: https://codereview.chromium.org/558163005

11 files changed, 1740 insertions, 37 deletions

diff --git a/bench/BezierBench.cpp b/bench/BezierBench.cpp
new file mode 100755
index 0000000000..ec83d958bb
--- /dev/null
+++ b/bench/BezierBench.cpp
@@ -0,0 +1,101 @@
+/*
+ * Copyright 2014 Google Inc.
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+
+#include "Benchmark.h"
+#include "SkCanvas.h"
+#include "SkPaint.h"
+#include "SkString.h"
+
+struct BezierRec {
+    SkCanvas*   fCanvas;
+    SkPaint     fPaint;
+    SkPath      fQuad;
+    SkPath      fCubic;
+};
+
+typedef const char* (*DrawProc)(const BezierRec*, int);
+
+static const char* draw_quad(const BezierRec* rec, int count) {
+    if (rec) {
+        SkCanvas* canvas = rec->fCanvas;
+        const SkPaint& paint = rec->fPaint;
+        const SkPath& path = rec->fQuad;
+        for (int i = 0; i < count; ++i) {
+            canvas->drawPath(path, paint);
+        }
+    }
+    return "quad";
+}
+
+static const char* draw_cubic(const BezierRec* rec, int count) {
+    if (rec) {
+        SkCanvas* canvas = rec->fCanvas;
+        const SkPaint& paint = rec->fPaint;
+        const SkPath& path = rec->fCubic;
+        for (int i = 0; i < count; ++i) {
+            canvas->drawPath(path, paint);
+        }
+    }
+    return "cubic";
+}
+
+class BezierBench : public Benchmark {
+    SkString fName;
+    SkPaint::Cap fCap;
+    SkPaint::Join fJoin;
+    BezierRec fRec;
+    DrawProc fProc;
+    SkScalar fWidth;
+public:
+    BezierBench(SkPaint::Cap c, SkPaint::Join j, SkScalar w, DrawProc proc) {
+        static const char* gCapName[] = {
+            "butt", "round", "square"
+        };
+        static const char* gJoinName[] = {
+            "miter", "round", "bevel"
+        };
+
+        fCap = c;
+        fJoin = j;
+        fProc = proc;
+        fWidth = SkIntToScalar(w);
+        fName.printf("draw_stroke_bezier_%s_%s_%s_%g", proc(NULL, 0), gCapName[c], gJoinName[j], w);
+
+        fRec.fQuad.moveTo(20, 20);
+        fRec.fQuad.quadTo(60, 20, 60, 60);
+        fRec.fQuad.quadTo(20, 60, 20, 100);
+        fRec.fCubic.moveTo(20, 20);
+        fRec.fCubic.cubicTo(40, 20, 60, 40, 60, 60);
+        fRec.fCubic.cubicTo(40, 60, 20, 80, 20, 100);
+    }
+
+protected:
+    virtual const char* onGetName() {
+        return fName.c_str();
+    }
+
+    virtual void onDraw(const int loops, SkCanvas* canvas) {
+        fRec.fCanvas = canvas;
+        this->setupPaint(&fRec.fPaint);
+        fRec.fPaint.setStyle(SkPaint::kStroke_Style);
+        fRec.fPaint.setStrokeCap(fCap);
+        fRec.fPaint.setStrokeJoin(fJoin);
+        fRec.fPaint.setStrokeWidth(fWidth);
+        fProc(&fRec, loops);
+    }
+
+private:
+    typedef Benchmark INHERITED;
+};
+
+DEF_BENCH( return new BezierBench(SkPaint::kButt_Cap, SkPaint::kRound_Join, 2, draw_quad); )
+DEF_BENCH( return new BezierBench(SkPaint::kSquare_Cap, SkPaint::kBevel_Join, 10, draw_quad); )
+DEF_BENCH( return new BezierBench(SkPaint::kRound_Cap, SkPaint::kMiter_Join, 50, draw_quad); )
+
+DEF_BENCH( return new BezierBench(SkPaint::kButt_Cap, SkPaint::kRound_Join, 2, draw_cubic); )
+DEF_BENCH( return new BezierBench(SkPaint::kSquare_Cap, SkPaint::kBevel_Join, 10, draw_cubic); )
+DEF_BENCH( return new BezierBench(SkPaint::kRound_Cap, SkPaint::kMiter_Join, 50, draw_cubic); )
diff --git a/gm/beziers.cpp b/gm/beziers.cpp
new file mode 100755
index 0000000000..ac212278cf
--- /dev/null
+++ b/gm/beziers.cpp
@@ -0,0 +1,87 @@
+/*
+ * Copyright 2014 Google Inc.
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+
+#include "gm.h"
+#include "SkRandom.h"
+
+#define W   400
+#define H   400
+#define N   10
+
+static const SkScalar SW = SkIntToScalar(W);
+static const SkScalar SH = SkIntToScalar(H);
+
+static void rnd_quad(SkPath* p, SkPaint* paint, SkLCGRandom& rand) {
+    p->moveTo(rand.nextRangeScalar(0,  W), rand.nextRangeScalar(0,  H));
+    for (int x = 0; x < 2; ++x) {
+        p->quadTo(rand.nextRangeScalar(W / 4,  W), rand.nextRangeScalar(0,  H),
+                rand.nextRangeScalar(0,  W), rand.nextRangeScalar(H / 4,  H));
+    }
+    paint->setColor(rand.nextU());
+    SkScalar width = rand.nextRangeScalar(1, 5);
+    width *= width;
+    paint->setStrokeWidth(width);
+    paint->setAlpha(0xFF);
+}
+
+static void rnd_cubic(SkPath* p, SkPaint* paint, SkLCGRandom& rand) {
+    p->moveTo(rand.nextRangeScalar(0,  W), rand.nextRangeScalar(0,  H));
+    for (int x = 0; x < 2; ++x) {
+        p->cubicTo(rand.nextRangeScalar(W / 4,  W), rand.nextRangeScalar(0,  H),
+                rand.nextRangeScalar(0,  W), rand.nextRangeScalar(H / 4,  H),
+                rand.nextRangeScalar(W / 4,  W), rand.nextRangeScalar(H / 4,  H));
+    }
+    paint->setColor(rand.nextU());
+    SkScalar width = rand.nextRangeScalar(1, 5);
+    width *= width;
+    paint->setStrokeWidth(width);
+    paint->setAlpha(0xFF);
+}
+
+class BeziersGM : public skiagm::GM {
+public:
+    BeziersGM() {}
+
+protected:
+    virtual uint32_t onGetFlags() const SK_OVERRIDE {
+        return kSkipTiled_Flag;
+    }
+
+    virtual SkString onShortName() {
+        return SkString("beziers");
+    }
+
+    virtual SkISize onISize() {
+        return SkISize::Make(W, H*2);
+    }
+
+    virtual void onDraw(SkCanvas* canvas) {
+        SkPaint paint;
+        paint.setStyle(SkPaint::kStroke_Style);
+        paint.setStrokeWidth(SkIntToScalar(9)/2);
+        paint.setAntiAlias(true);
+
+        SkLCGRandom rand;
+        for (int i = 0; i < N; i++) {
+            SkPath p;
+            rnd_quad(&p, &paint, rand);
+            canvas->drawPath(p, paint);
+        }
+        canvas->translate(0, SH);
+        for (int i = 0; i < N; i++) {
+            SkPath p;
+            rnd_cubic(&p, &paint, rand);
+            canvas->drawPath(p, paint);
+        }
+    }
+
+private:
+    typedef skiagm::GM INHERITED;
+};
+
+static skiagm::GM* F0(void*) { return new BeziersGM; }
+static skiagm::GMRegistry R0(F0);
diff --git a/gm/smallarc.cpp b/gm/smallarc.cpp
new file mode 100755
index 0000000000..c311460e54
--- /dev/null
+++ b/gm/smallarc.cpp
@@ -0,0 +1,54 @@
+/*
+ * Copyright 2014 Google Inc.
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+
+#include "gm.h"
+
+namespace skiagm {
+
+// this draws a small arc scaled up
+// see https://code.google.com/p/chromium/issues/detail?id=102411
+// and https://code.google.com/p/skia/issues/detail?id=2769
+class SmallArcGM : public GM {
+public:
+    SmallArcGM() {
+    }
+
+protected:
+
+    virtual SkString onShortName() SK_OVERRIDE {
+        return SkString("smallarc");
+    }
+
+    virtual SkISize onISize() SK_OVERRIDE {
+        return SkISize::Make(762, 762);
+    }
+
+    virtual void onDraw(SkCanvas* canvas) SK_OVERRIDE {
+        SkPaint p;
+        p.setColor(SK_ColorRED);
+        p.setAntiAlias(true);
+        p.setStyle(SkPaint::kStroke_Style);
+        p.setStrokeWidth(120);
+
+        SkPath path;
+        path.moveTo(75, 0);
+        path.cubicTo(33.5, 0, 0, 33.5, 0, 75);
+
+        canvas->translate(-400, -400);
+        canvas->scale(8, 8);
+        canvas->drawPath(path, p);
+    }
+
+private:
+    typedef GM INHERITED;
+};
+
+//////////////////////////////////////////////////////////////////////////////
+
+DEF_GM( return SkNEW(SmallArcGM); )
+
+}
diff --git a/gyp/bench.gypi b/gyp/bench.gypi
index c2c8ec90fb..b057e89186 100644
--- a/gyp/bench.gypi
+++ b/gyp/bench.gypi
@@ -24,6 +24,7 @@
 
     '../bench/AAClipBench.cpp',
     '../bench/AlternatingColorPatternBench.cpp',
+    '../bench/BezierBench.cpp',
     '../bench/BitmapBench.cpp',
     '../bench/BitmapRectBench.cpp',
     '../bench/BitmapScaleBench.cpp',
diff --git a/gyp/gmslides.gypi b/gyp/gmslides.gypi
index 58bf17742d..6cf4767fb3 100644
--- a/gyp/gmslides.gypi
+++ b/gyp/gmslides.gypi
@@ -20,6 +20,7 @@
         '../gm/arithmode.cpp',
         '../gm/astcbitmap.cpp',
         '../gm/beziereffects.cpp',
+        '../gm/beziers.cpp',
         '../gm/bigblurs.cpp',
         '../gm/bigmatrix.cpp',
         '../gm/bigtext.cpp',
@@ -163,6 +164,7 @@
         '../gm/shallowgradient.cpp',
         '../gm/simpleaaclip.cpp',
         '../gm/skbug1719.cpp',
+        '../gm/smallarc.cpp',
         '../gm/stringart.cpp',
         '../gm/spritebitmap.cpp',
         '../gm/srcmode.cpp',
diff --git a/gyp/tests.gypi b/gyp/tests.gypi
index db87f3f7a4..fc0d69d0bf 100644
--- a/gyp/tests.gypi
+++ b/gyp/tests.gypi
@@ -192,6 +192,7 @@
     '../tests/StreamTest.cpp',
     '../tests/StringTest.cpp',
     '../tests/StrokeTest.cpp',
+    '../tests/StrokerTest.cpp',
     '../tests/SurfaceTest.cpp',
     '../tests/TArrayTest.cpp',
     '../tests/THashCache.cpp',
diff --git a/samplecode/SampleRotateCircles.cpp b/samplecode/SampleRotateCircles.cpp
index f9b32ea417..06350ab5b4 100644
--- a/samplecode/SampleRotateCircles.cpp
+++ b/samplecode/SampleRotateCircles.cpp
@@ -11,6 +11,7 @@
 #include "SkRandom.h"
 #include "SkRRect.h"
 #include "SkColorPriv.h"
+#include "SkStrokerPriv.h"
 
 static void rotateAbout(SkCanvas* canvas, SkScalar degrees,
                         SkScalar cx, SkScalar cy) {
@@ -177,6 +178,12 @@ static int getOnCurvePoints(const SkPath& path, SkPoint storage[]) {
 
 #include "SkPathMeasure.h"
 
+struct StrokeTypeButton {
+    SkRect fBounds;
+    char fLabel;
+    bool fEnabled;
+};
+
 class TestStrokeView : public SampleView {
     enum {
         SKELETON_COLOR = 0xFF0000FF,
@@ -187,7 +194,19 @@ class TestStrokeView : public SampleView {
         kCount = 9
     };
     SkPoint fPts[kCount];
+    SkRect fErrorControl;
+    SkRect fWidthControl;
+    StrokeTypeButton fCubicButton;
+    StrokeTypeButton fQuadButton;
+    StrokeTypeButton fRRectButton;
     SkScalar fWidth, fDWidth;
+    bool fAnimate;
+#if QUAD_STROKE_APPROXIMATION && defined(SK_DEBUG)
+    #define kStrokerErrorMin 0.001f
+    #define kStrokerErrorMax 5
+#endif
+    #define kWidthMin 1
+    #define kWidthMax 100
 public:
     TestStrokeView() {
         this->setBGColor(SK_ColorLTGRAY);
@@ -206,6 +225,14 @@ public:
 
         fWidth = 50;
         fDWidth = 0.25f;
+
+        fCubicButton.fLabel = 'C';
+        fCubicButton.fEnabled = true;
+        fQuadButton.fLabel = 'Q';
+        fQuadButton.fEnabled = true;
+        fRRectButton.fLabel = 'R';
+        fRRectButton.fEnabled = true;
+        fAnimate = true;
     }
 
 protected:
@@ -217,12 +244,21 @@ protected:
         return this->INHERITED::onQuery(evt);
     }
 
+    virtual void onSizeChange() {
+        fErrorControl.setXYWH(this->width() - 100, 30, 30, 400);
+        fWidthControl.setXYWH(this->width() -  50, 30, 30, 400);
+        fCubicButton.fBounds.setXYWH(this->width() - 50, 450, 30, 30);
+        fQuadButton.fBounds.setXYWH(this->width() - 50, 500, 30, 30);
+        fRRectButton.fBounds.setXYWH(this->width() - 50, 550, 30, 30);
+        this->INHERITED::onSizeChange();
+    }
+
     void draw_points(SkCanvas* canvas, const SkPath& path, SkColor color,
                      bool show_lines) {
         SkPaint paint;
         paint.setColor(color);
         paint.setAlpha(0x80);
-
+        paint.setAntiAlias(true);
         int n = path.countPoints();
         SkAutoSTArray<32, SkPoint> pts(n);
         if (show_lines) {
@@ -280,45 +316,95 @@ protected:
         draw_points(canvas, fill, WIREFRAME_COLOR, false);
     }
 
+    void draw_button(SkCanvas* canvas, const StrokeTypeButton& button) {
+        SkPaint paint;
+        paint.setAntiAlias(true);
+        paint.setStyle(SkPaint::kStroke_Style);
+        paint.setColor(button.fEnabled ? 0xFF3F0000 : 0x6F3F0000);
+        canvas->drawRect(button.fBounds, paint);
+        paint.setTextSize(25.0f);
+        paint.setColor(button.fEnabled ? 0xFF3F0000 : 0x6F3F0000);
+        paint.setTextAlign(SkPaint::kCenter_Align);
+        paint.setStyle(SkPaint::kFill_Style);
+        canvas->drawText(&button.fLabel, 1, button.fBounds.centerX(), button.fBounds.fBottom - 5,
+                paint);
+    }
+
+    void draw_control(SkCanvas* canvas, const SkRect& bounds, SkScalar value,
+            SkScalar min, SkScalar max, const char* name) {
+        SkPaint paint;
+        paint.setAntiAlias(true);
+        paint.setStyle(SkPaint::kStroke_Style);
+        canvas->drawRect(bounds, paint);
+        SkScalar scale = max - min;
+        SkScalar yPos = bounds.fTop + (value - min) * bounds.height() / scale;
+        paint.setColor(0xFFFF0000);
+        canvas->drawLine(bounds.fLeft - 5, yPos, bounds.fRight + 5, yPos, paint);
+        SkString label;
+        label.printf("%0.3g", value);
+        paint.setColor(0xFF000000);
+        paint.setTextSize(11.0f);
+        paint.setStyle(SkPaint::kFill_Style);
+        canvas->drawText(label.c_str(), label.size(), bounds.fLeft + 5, yPos - 5, paint);
+        paint.setTextSize(13.0f);
+        canvas->drawText(name, strlen(name), bounds.fLeft, bounds.bottom() + 11, paint);
+    }
+
     virtual void onDrawContent(SkCanvas* canvas) {
         SkPath path;
         SkScalar width = fWidth;
 
-        path.moveTo(fPts[0]);
-        path.cubicTo(fPts[1], fPts[2], fPts[3]);
-        draw_stroke(canvas, path, width);
-
-        path.reset();
-        path.moveTo(fPts[4]);
-        path.quadTo(fPts[5], fPts[6]);
-        draw_stroke(canvas, path, width);
-
-        SkScalar rad = 32;
-        SkRect r;
-        r.set(&fPts[7], 2);
-        path.reset();
-        SkRRect rr;
-        rr.setRectXY(r, rad, rad);
-        path.addRRect(rr);
-        draw_stroke(canvas, path, width);
-
-        path.reset();
-        SkRRect rr2;
-        rr.inset(width/2, width/2, &rr2);
-        path.addRRect(rr2, SkPath::kCCW_Direction);
-        rr.inset(-width/2, -width/2, &rr2);
-        path.addRRect(rr2, SkPath::kCW_Direction);
-        SkPaint paint;
-        paint.setAntiAlias(true);
-        paint.setColor(0x40FF8844);
-        canvas->drawPath(path, paint);
+        if (fCubicButton.fEnabled) {
+            path.moveTo(fPts[0]);
+            path.cubicTo(fPts[1], fPts[2], fPts[3]);
+            draw_stroke(canvas, path, width);
+        }
 
-        fWidth += fDWidth;
-        if (fDWidth > 0 && fWidth > 100) {
-            fDWidth = -fDWidth;
-        } else if (fDWidth < 0 && fWidth < 10) {
-            fDWidth = -fDWidth;
+        if (fQuadButton.fEnabled) {
+            path.reset();
+            path.moveTo(fPts[4]);
+            path.quadTo(fPts[5], fPts[6]);
+            draw_stroke(canvas, path, width);
         }
+
+        if (fRRectButton.fEnabled) {
+            SkScalar rad = 32;
+            SkRect r;
+            r.set(&fPts[7], 2);
+            path.reset();
+            SkRRect rr;
+            rr.setRectXY(r, rad, rad);
+            path.addRRect(rr);
+            draw_stroke(canvas, path, width);
+
+            path.reset();
+            SkRRect rr2;
+            rr.inset(width/2, width/2, &rr2);
+            path.addRRect(rr2, SkPath::kCCW_Direction);
+            rr.inset(-width/2, -width/2, &rr2);
+            path.addRRect(rr2, SkPath::kCW_Direction);
+            SkPaint paint;
+            paint.setAntiAlias(true);
+            paint.setColor(0x40FF8844);
+            canvas->drawPath(path, paint);
+        }
+
+        if (fAnimate) {
+            fWidth += fDWidth;
+            if (fDWidth > 0 && fWidth > kWidthMax) {
+                fDWidth = -fDWidth;
+            } else if (fDWidth < 0 && fWidth < kWidthMin) {
+                fDWidth = -fDWidth;
+            }
+        }
+#if QUAD_STROKE_APPROXIMATION && defined(SK_DEBUG)
+        draw_control(canvas, fErrorControl, gDebugStrokerError, kStrokerErrorMin, kStrokerErrorMax,
+                "error");
+#endif
+        draw_control(canvas, fWidthControl, fWidth, kWidthMin, kWidthMax, "width");
+        draw_button(canvas, fQuadButton);
+        draw_button(canvas, fCubicButton);
+        draw_button(canvas, fRRectButton);
         this->inval(NULL);
     }
 
@@ -335,14 +421,53 @@ protected:
                 return new MyClick(this, (int)i);
             }
         }
+        const SkRect& rectPt = SkRect::MakeXYWH(x, y, 1, 1);
+#if QUAD_STROKE_APPROXIMATION && defined(SK_DEBUG)
+        if (fErrorControl.contains(rectPt)) {
+            return new MyClick(this, (int) SK_ARRAY_COUNT(fPts) + 1);
+        }
+#endif
+        if (fWidthControl.contains(rectPt)) {
+            return new MyClick(this, (int) SK_ARRAY_COUNT(fPts) + 3);
+        }
+        if (fCubicButton.fBounds.contains(rectPt)) {
+            fCubicButton.fEnabled ^= true;
+            return new MyClick(this, (int) SK_ARRAY_COUNT(fPts) + 4);
+        }
+        if (fQuadButton.fBounds.contains(rectPt)) {
+            fQuadButton.fEnabled ^= true;
+            return new MyClick(this, (int) SK_ARRAY_COUNT(fPts) + 5);
+        }
+        if (fRRectButton.fBounds.contains(rectPt)) {
+            fRRectButton.fEnabled ^= true;
+            return new MyClick(this, (int) SK_ARRAY_COUNT(fPts) + 6);
+        }
         return this->INHERITED::onFindClickHandler(x, y, modi);
     }
 
+    static SkScalar MapScreenYtoValue(int y, const SkRect& control, SkScalar min,
+            SkScalar max) {
+        return (SkIntToScalar(y) - control.fTop) / control.height() * (max - min) + min;
+    }
+
     virtual bool onClick(Click* click) {
         int index = ((MyClick*)click)->fIndex;
-        fPts[index].offset(SkIntToScalar(click->fICurr.fX - click->fIPrev.fX),
-                           SkIntToScalar(click->fICurr.fY - click->fIPrev.fY));
-        this->inval(NULL);
+        if (index < (int) SK_ARRAY_COUNT(fPts)) {
+            fPts[index].offset(SkIntToScalar(click->fICurr.fX - click->fIPrev.fX),
+                               SkIntToScalar(click->fICurr.fY - click->fIPrev.fY));
+            this->inval(NULL);
+        }
+#if QUAD_STROKE_APPROXIMATION && defined(SK_DEBUG)
+        else if (index == (int) SK_ARRAY_COUNT(fPts) + 1) {
+            gDebugStrokerError = MapScreenYtoValue(click->fICurr.fY, fErrorControl,
+                    kStrokerErrorMin, kStrokerErrorMax);
+            gDebugStrokerErrorSet = true;
+        }
+#endif
+        else if (index == (int) SK_ARRAY_COUNT(fPts) + 3) {
+            fWidth = MapScreenYtoValue(click->fICurr.fY, fWidthControl, kWidthMin, kWidthMax);
+            fAnimate = fWidth <= kWidthMin;
+        }
         return true;
     }
 
diff --git a/src/core/SkStroke.cpp b/src/core/SkStroke.cpp
index 1e4ae79a5e..a9cc6cd60a 100644
--- a/src/core/SkStroke.cpp
+++ b/src/core/SkStroke.cpp
@@ -9,6 +9,48 @@
 #include "SkGeometry.h"
 #include "SkPath.h"
 
+#if QUAD_STROKE_APPROXIMATION
+
+    enum {
+        kTangent_RecursiveLimit,
+        kCubic_RecursiveLimit,
+        kQuad_RecursiveLimit
+    };
+
+    // quads with extreme widths (e.g. (0,1) (1,6) (0,3) width=5e7) recurse to point of failure
+    // largest seen for normal cubics : 5, 26
+    // largest seen for normal quads : 11
+    static const int kRecursiveLimits[] = { 5*3, 26*3, 11*3 };  // 3x limits seen in practical tests
+
+    SK_COMPILE_ASSERT(SK_ARRAY_COUNT(kRecursiveLimits) == kQuad_RecursiveLimit + 1,
+            recursive_limits_mismatch);
+
+    #ifdef SK_DEBUG  // enables tweaking these values at runtime from SampleApp
+        bool gDebugStrokerErrorSet = false;
+        SkScalar gDebugStrokerError;
+
+        int gMaxRecursion[SK_ARRAY_COUNT(kRecursiveLimits)] = { 0 };
+    #endif
+    #ifndef DEBUG_QUAD_STROKER
+        #define DEBUG_QUAD_STROKER 0
+    #endif
+
+    #if DEBUG_QUAD_STROKER
+        /* Enable to show the decisions made in subdividing the curve -- helpful when the resulting
+           stroke has more than the optimal number of quadratics and lines */
+        #define STROKER_RESULT(resultType, depth, quadPts, format, ...) \
+                SkDebugf("[%d] %s " format "\n", depth, __FUNCTION__, __VA_ARGS__), \
+                SkDebugf("  " #resultType " t=(%g,%g)\n", quadPts->fStartT, quadPts->fEndT), \
+                resultType
+        #define STROKER_DEBUG_PARAMS(...) , __VA_ARGS__
+    #else
+        #define STROKER_RESULT(resultType, depth, quadPts, format, ...) \
+                resultType
+        #define STROKER_DEBUG_PARAMS(...)
+    #endif
+
+#endif
+
 #define kMaxQuadSubdivide   5
 #define kMaxCubicSubdivide  7
 
@@ -16,6 +58,7 @@ static inline bool degenerate_vector(const SkVector& v) {
     return !SkPoint::CanNormalize(v.fX, v.fY);
 }
 
+#if !QUAD_STROKE_APPROXIMATION
 static inline bool normals_too_curvy(const SkVector& norm0, SkVector& norm1) {
     /*  root2/2 is a 45-degree angle
         make this constant bigger for more subdivisions (but not >= 1)
@@ -43,6 +86,7 @@ static inline bool normals_too_pinchy(const SkVector& norm0, SkVector& norm1) {
     SkScalar dot = SkPoint::DotProduct(norm0, norm1);
     return dot <= kTooPinchyNormalDotProd;
 }
+#endif
 
 static bool set_normal_unitnormal(const SkPoint& before, const SkPoint& after,
                                   SkScalar radius,
@@ -67,12 +111,60 @@ static bool set_normal_unitnormal(const SkVector& vec,
 }
 
 ///////////////////////////////////////////////////////////////////////////////
+#if QUAD_STROKE_APPROXIMATION
+
+struct SkQuadConstruct {    // The state of the quad stroke under construction.
+    SkPoint fQuad[3];       // the stroked quad parallel to the original curve
+    SkPoint fTangentStart;  // a point tangent to fQuad[0]
+    SkPoint fTangentEnd;    // a point tangent to fQuad[2]
+    SkScalar fStartT;       // a segment of the original curve
+    SkScalar fMidT;         //              "
+    SkScalar fEndT;         //              "
+    bool fStartSet;         // state to share common points across structs
+    bool fEndSet;           //                     "
+
+    // return false if start and end are too close to have a unique middle
+    bool init(SkScalar start, SkScalar end) {
+        fStartT = start;
+        fMidT = (start + end) * SK_ScalarHalf;
+        fEndT = end;
+        fStartSet = fEndSet = false;
+        return fStartT < fMidT && fMidT < fEndT;
+    }
+
+    bool initWithStart(SkQuadConstruct* parent) {
+        if (!init(parent->fStartT, parent->fMidT)) {
+            return false;
+        }
+        fQuad[0] = parent->fQuad[0];
+        fTangentStart = parent->fTangentStart;
+        fStartSet = true;
+        return true;
+    }
+
+    bool initWithEnd(SkQuadConstruct* parent) {
+        if (!init(parent->fMidT, parent->fEndT)) {
+            return false;
+        }
+        fQuad[2] = parent->fQuad[2];
+        fTangentEnd = parent->fTangentEnd;
+        fEndSet = true;
+        return true;
+   }
+};
+#endif
 
 class SkPathStroker {
 public:
+#if QUAD_STROKE_APPROXIMATION
+    SkPathStroker(const SkPath& src,
+                  SkScalar radius, SkScalar miterLimit, SkScalar error, SkPaint::Cap cap,
+                  SkPaint::Join join);
+#else
     SkPathStroker(const SkPath& src,
                   SkScalar radius, SkScalar miterLimit, SkPaint::Cap cap,
                   SkPaint::Join join);
+#endif
 
     void moveTo(const SkPoint&);
     void lineTo(const SkPoint&);
@@ -87,6 +179,9 @@ public:
     }
 
 private:
+#if QUAD_STROKE_APPROXIMATION
+    SkScalar    fError;
+#endif
     SkScalar    fRadius;
     SkScalar    fInvMiterLimit;
 
@@ -102,6 +197,67 @@ private:
     SkPath  fInner, fOuter; // outer is our working answer, inner is temp
     SkPath  fExtra;         // added as extra complete contours
 
+#if QUAD_STROKE_APPROXIMATION
+    enum StrokeType {
+        kOuter_StrokeType = 1,      // use sign-opposite values later to flip perpendicular axis
+        kInner_StrokeType = -1
+    } fStrokeType;
+
+    enum ResultType {
+        kSplit_ResultType,          // the caller should split the quad stroke in two
+        kDegenerate_ResultType,     // the caller should add a line
+        kQuad_ResultType,           // the caller should (continue to try to) add a quad stroke
+        kNormalError_ResultType,    // the cubic's normal couldn't be computed -- abort
+    };
+
+    enum ReductionType {
+        kPoint_ReductionType,       // all curve points are practically identical
+        kLine_ReductionType,        // the control point is on the line between the ends
+        kQuad_ReductionType,        // the control point is outside the line between the ends
+        kDegenerate_ReductionType,  // the control point is on the line but outside the ends
+        kDegenerate2_ReductionType, // two control points are on the line but outside ends (cubic)
+        kDegenerate3_ReductionType, // three areas of max curvature found (for cubic)
+    };
+
+    enum IntersectRayType {
+        kCtrlPt_RayType,
+        kResultType_RayType,
+    };
+
+    int fRecursionDepth;            // track stack depth to abort if numerics run amok
+    bool fFoundTangents;            // do less work until tangents meet (cubic)
+
+    void addDegenerateLine(const SkQuadConstruct* );
+    ReductionType CheckCubicLinear(const SkPoint cubic[4], SkPoint reduction[3],
+                                   const SkPoint** tanPtPtr);
+    ReductionType CheckQuadLinear(const SkPoint quad[3], SkPoint* reduction);
+    ResultType compareQuadCubic(const SkPoint cubic[4], SkQuadConstruct* );
+    ResultType compareQuadQuad(const SkPoint quad[3], SkQuadConstruct* );
+    bool cubicMidOnLine(const SkPoint cubic[4], const SkQuadConstruct* ) const;
+    bool cubicPerpRay(const SkPoint cubic[4], SkScalar t, SkPoint* tPt, SkPoint* onPt,
+                      SkPoint* tangent) const;
+    bool cubicQuadEnds(const SkPoint cubic[4], SkQuadConstruct* );
+    bool cubicQuadMid(const SkPoint cubic[4], const SkQuadConstruct* , SkPoint* mid) const;
+    bool cubicStroke(const SkPoint cubic[4], SkQuadConstruct* );
+    void init(StrokeType strokeType, SkQuadConstruct* , SkScalar tStart, SkScalar tEnd);
+    ResultType intersectRay(SkQuadConstruct* , IntersectRayType  STROKER_DEBUG_PARAMS(int) ) const;
+    bool ptInQuadBounds(const SkPoint quad[3], const SkPoint& pt) const;
+    void quadPerpRay(const SkPoint quad[3], SkScalar t, SkPoint* tPt, SkPoint* onPt,
+                     SkPoint* tangent) const;
+    bool quadStroke(const SkPoint quad[3], SkQuadConstruct* );
+    void setCubicEndNormal(const SkPoint cubic[4],
+                           const SkVector& normalAB, const SkVector& unitNormalAB,
+                           SkVector* normalCD, SkVector* unitNormalCD);
+    void setQuadEndNormal(const SkPoint quad[3],
+                          const SkVector& normalAB, const SkVector& unitNormalAB,
+                          SkVector* normalBC, SkVector* unitNormalBC);
+    void setRayPts(const SkPoint& tPt, SkVector* dxy, SkPoint* onPt, SkPoint* tangent) const;
+    static bool SlightAngle(SkQuadConstruct* );
+    ResultType strokeCloseEnough(const SkPoint stroke[3], const SkPoint ray[2],
+                                 SkQuadConstruct*  STROKER_DEBUG_PARAMS(int depth) ) const;
+    ResultType tangentsMeet(const SkPoint cubic[4], SkQuadConstruct* );
+#endif
+
     void    finishContour(bool close, bool isLine);
     void    preJoinTo(const SkPoint&, SkVector* normal, SkVector* unitNormal,
                       bool isLine);
@@ -109,6 +265,7 @@ private:
                        const SkVector& unitNormal);
 
     void    line_to(const SkPoint& currPt, const SkVector& normal);
+#if !QUAD_STROKE_APPROXIMATION
     void    quad_to(const SkPoint pts[3],
                     const SkVector& normalAB, const SkVector& unitNormalAB,
                     SkVector* normalBC, SkVector* unitNormalBC,
@@ -117,6 +274,7 @@ private:
                     const SkVector& normalAB, const SkVector& unitNormalAB,
                     SkVector* normalCD, SkVector* unitNormalCD,
                     int subDivide);
+#endif
 };
 
 ///////////////////////////////////////////////////////////////////////////////
@@ -187,9 +345,15 @@ void SkPathStroker::finishContour(bool close, bool currIsLine) {
 
 ///////////////////////////////////////////////////////////////////////////////
 
+#if QUAD_STROKE_APPROXIMATION
+SkPathStroker::SkPathStroker(const SkPath& src,
+                             SkScalar radius, SkScalar miterLimit, SkScalar error,
+                             SkPaint::Cap cap, SkPaint::Join join)
+#else
 SkPathStroker::SkPathStroker(const SkPath& src,
                              SkScalar radius, SkScalar miterLimit,
                              SkPaint::Cap cap, SkPaint::Join join)
+#endif
         : fRadius(radius) {
 
     /*  This is only used when join is miter_join, but we initialize it here
@@ -217,6 +381,17 @@ SkPathStroker::SkPathStroker(const SkPath& src,
     // 1x for inner == 'wag' (worst contour length would be better guess)
     fOuter.incReserve(src.countPoints() * 3);
     fInner.incReserve(src.countPoints());
+#if QUAD_STROKE_APPROXIMATION
+#ifdef SK_DEBUG
+    if (!gDebugStrokerErrorSet) {
+        gDebugStrokerError = error;
+    }
+    fError = gDebugStrokerError;
+#else
+    fError = error;
+#endif
+    fRecursionDepth = 0;
+#endif
 }
 
 void SkPathStroker::moveTo(const SkPoint& pt) {
@@ -243,6 +418,7 @@ void SkPathStroker::lineTo(const SkPoint& currPt) {
     this->postJoinTo(currPt, normal, unitNormal);
 }
 
+#if !QUAD_STROKE_APPROXIMATION
 void SkPathStroker::quad_to(const SkPoint pts[3],
                       const SkVector& normalAB, const SkVector& unitNormalAB,
                       SkVector* normalBC, SkVector* unitNormalBC,
@@ -278,6 +454,203 @@ void SkPathStroker::quad_to(const SkPoint pts[3],
                         pts[2].fX - normalBC->fX, pts[2].fY - normalBC->fY);
     }
 }
+#endif
+
+#if QUAD_STROKE_APPROXIMATION
+void SkPathStroker::setQuadEndNormal(const SkPoint quad[3], const SkVector& normalAB,
+        const SkVector& unitNormalAB, SkVector* normalBC, SkVector* unitNormalBC) {
+    if (!set_normal_unitnormal(quad[1], quad[2], fRadius, normalBC, unitNormalBC)) {
+        *normalBC = normalAB;
+        *unitNormalBC = unitNormalAB;
+    }
+}
+
+void SkPathStroker::setCubicEndNormal(const SkPoint cubic[4], const SkVector& normalAB,
+        const SkVector& unitNormalAB, SkVector* normalCD, SkVector* unitNormalCD) {
+    SkVector    ab = cubic[1] - cubic[0];
+    SkVector    cd = cubic[3] - cubic[2];
+
+    bool    degenerateAB = degenerate_vector(ab);
+    bool    degenerateCD = degenerate_vector(cd);
+
+    if (degenerateAB && degenerateCD) {
+        goto DEGENERATE_NORMAL;
+    }
+
+    if (degenerateAB) {
+        ab = cubic[2] - cubic[0];
+        degenerateAB = degenerate_vector(ab);
+    }
+    if (degenerateCD) {
+        cd = cubic[3] - cubic[1];
+        degenerateCD = degenerate_vector(cd);
+    }
+    if (degenerateAB || degenerateCD) {
+DEGENERATE_NORMAL:
+        *normalCD = normalAB;
+        *unitNormalCD = unitNormalAB;
+        return;
+    }
+    SkAssertResult(set_normal_unitnormal(cd, fRadius, normalCD, unitNormalCD));
+}
+
+void SkPathStroker::init(StrokeType strokeType, SkQuadConstruct* quadPts, SkScalar tStart,
+        SkScalar tEnd) {
+    fStrokeType = strokeType;
+    fFoundTangents = false;
+    quadPts->init(tStart, tEnd);
+}
+
+// returns the distance squared from the point to the line
+static SkScalar pt_to_line(const SkPoint& pt, const SkPoint& lineStart, const SkPoint& lineEnd) {
+    SkVector dxy = lineEnd - lineStart;
+    if (degenerate_vector(dxy)) {
+        return pt.distanceToSqd(lineStart);
+    }
+    SkVector ab0 = pt - lineStart;
+    SkScalar numer = dxy.dot(ab0);
+    SkScalar denom = dxy.dot(dxy);
+    SkScalar t = numer / denom;
+    SkPoint hit;
+    hit.fX = lineStart.fX * (1 - t) + lineEnd.fX * t;
+    hit.fY = lineStart.fY * (1 - t) + lineEnd.fY * t;
+    return hit.distanceToSqd(pt);
+}
+
+/*  Given a cubic, determine if all four points are in a line.
+    Return true if the inner points is close to a line connecting the outermost points.
+
+    Find the outermost point by looking for the largest difference in X or Y.
+    Given the indices of the outermost points, and that outer_1 is greater than outer_2,
+    this table shows the index of the smaller of the remaining points:
+
+                      outer_2
+                  0    1    2    3
+      outer_1     ----------------
+         0     |  -    2    1    1
+         1     |  -    -    0    0
+         2     |  -    -    -    0
+         3     |  -    -    -    -
+
+    If outer_1 == 0 and outer_2 == 1, the smaller of the remaining indices (2 and 3) is 2.
+
+    This table can be collapsed to: (1 + (2 >> outer_2)) >> outer_1
+
+    Given three indices (outer_1 outer_2 mid_1) from 0..3, the remaining index is:
+
+               mid_2 == (outer_1 ^ outer_2 ^ mid_1)
+ */
+static bool cubic_in_line(const SkPoint cubic[4]) {
+    SkScalar ptMax = -1;
+    int outer1, outer2;
+    for (int index = 0; index < 3; ++index) {
+        for (int inner = index + 1; inner < 4; ++inner) {
+            SkVector testDiff = cubic[inner] - cubic[index];
+            SkScalar testMax = SkTMax(SkScalarAbs(testDiff.fX), SkScalarAbs(testDiff.fY));
+            if (ptMax < testMax) {
+                outer1 = index;
+                outer2 = inner;
+                ptMax = testMax;
+            }
+        }
+    }
+    SkASSERT(outer1 >= 0 && outer1 <= 2);
+    SkASSERT(outer2 >= 1 && outer2 <= 3);
+    SkASSERT(outer1 < outer2);
+    int mid1 = (1 + (2 >> outer2)) >> outer1;
+    SkASSERT(mid1 >= 0 && mid1 <= 2);
+    SkASSERT(outer1 != mid1 && outer2 != mid1);
+    int mid2 = outer1 ^ outer2 ^ mid1;
+    SkASSERT(mid2 >= 1 && mid2 <= 3);
+    SkASSERT(mid2 != outer1 && mid2 != outer2 && mid2 != mid1);
+    SkASSERT(((1 << outer1) | (1 << outer2) | (1 << mid1) | (1 << mid2)) == 0x0f);
+    SkScalar lineSlop = ptMax * ptMax * 0.00001f;  // this multiplier is pulled out of the air
+    return pt_to_line(cubic[mid1], cubic[outer1], cubic[outer2]) <= lineSlop
+            && pt_to_line(cubic[mid2], cubic[outer1], cubic[outer2]) <= lineSlop;
+}
+
+/* Given quad, see if all there points are in a line.
+   Return true if the inside point is close to a line connecting the outermost points.
+
+   Find the outermost point by looking for the largest difference in X or Y.
+   Since the XOR of the indices is 3  (0 ^ 1 ^ 2)
+   the missing index equals: outer_1 ^ outer_2 ^ 3
+ */
+static bool quad_in_line(const SkPoint quad[3]) {
+    SkScalar ptMax = -1;
+    int outer1, outer2;
+    for (int index = 0; index < 2; ++index) {
+        for (int inner = index + 1; inner < 3; ++inner) {
+            SkVector testDiff = quad[inner] - quad[index];
+            SkScalar testMax = SkTMax(SkScalarAbs(testDiff.fX), SkScalarAbs(testDiff.fY));
+            if (ptMax < testMax) {
+                outer1 = index;
+                outer2 = inner;
+                ptMax = testMax;
+            }
+        }
+    }
+    SkASSERT(outer1 >= 0 && outer1 <= 1);
+    SkASSERT(outer2 >= 1 && outer2 <= 2);
+    SkASSERT(outer1 < outer2);
+    int mid = outer1 ^ outer2 ^ 3;
+    SkScalar lineSlop =  ptMax * ptMax * 0.00001f;  // this multiplier is pulled out of the air
+    return pt_to_line(quad[mid], quad[outer1], quad[outer2]) <= lineSlop;
+}
+
+SkPathStroker::ReductionType SkPathStroker::CheckCubicLinear(const SkPoint cubic[4],
+        SkPoint reduction[3], const SkPoint** tangentPtPtr) {
+    bool degenerateAB = degenerate_vector(cubic[1] - cubic[0]);
+    bool degenerateBC = degenerate_vector(cubic[2] - cubic[1]);
+    bool degenerateCD = degenerate_vector(cubic[3] - cubic[2]);
+    if (degenerateAB & degenerateBC & degenerateCD) {
+        return kPoint_ReductionType;
+    }
+    if (degenerateAB + degenerateBC + degenerateCD == 2) {
+        return kLine_ReductionType;
+    }
+    if (!cubic_in_line(cubic)) {
+        *tangentPtPtr = degenerateAB ? &cubic[2] : &cubic[1];
+        return kQuad_ReductionType;
+    }
+    SkScalar tValues[3];
+    int count = SkFindCubicMaxCurvature(cubic, tValues);
+    if (count == 0) {
+        return kLine_ReductionType;
+    }
+    for (int index = 0; index < count; ++index) {
+        SkScalar t = tValues[index];
+        SkEvalCubicAt(cubic, t, &reduction[index], NULL, NULL);
+    }
+    SK_COMPILE_ASSERT(kQuad_ReductionType + 1 == kDegenerate_ReductionType, enum_out_of_whack);
+    SK_COMPILE_ASSERT(kQuad_ReductionType + 2 == kDegenerate2_ReductionType, enum_out_of_whack);
+    SK_COMPILE_ASSERT(kQuad_ReductionType + 3 == kDegenerate3_ReductionType, enum_out_of_whack);
+
+    return (ReductionType) (kQuad_ReductionType + count);
+}
+
+SkPathStroker::ReductionType SkPathStroker::CheckQuadLinear(const SkPoint quad[3],
+        SkPoint* reduction) {
+    bool degenerateAB = degenerate_vector(quad[1] - quad[0]);
+    bool degenerateBC = degenerate_vector(quad[2] - quad[1]);
+    if (degenerateAB & degenerateBC) {
+        return kPoint_ReductionType;
+    }
+    if (degenerateAB | degenerateBC) {
+        return kLine_ReductionType;
+    }
+    if (!quad_in_line(quad)) {
+        return kQuad_ReductionType;
+    }
+    SkScalar t = SkFindQuadMaxCurvature(quad);
+    if (0 == t) {
+        return kLine_ReductionType;
+    }
+    SkEvalQuadAt(quad, t, reduction, NULL);
+    return kDegenerate_ReductionType;
+}
+
+#else
 
 void SkPathStroker::cubic_to(const SkPoint pts[4],
                       const SkVector& normalAB, const SkVector& unitNormalAB,
@@ -362,8 +735,42 @@ DRAW_LINE:
                         pts[3].fX - normalCD->fX, pts[3].fY - normalCD->fY);
     }
 }
+#endif
 
 void SkPathStroker::quadTo(const SkPoint& pt1, const SkPoint& pt2) {
+#if QUAD_STROKE_APPROXIMATION
+    const SkPoint quad[3] = { fPrevPt, pt1, pt2 };
+    SkPoint reduction;
+    ReductionType reductionType = CheckQuadLinear(quad, &reduction);
+    if (kPoint_ReductionType == reductionType) {
+        return;
+    }
+    if (kLine_ReductionType == reductionType) {
+        this->lineTo(pt2);
+        return;
+    }
+    if (kDegenerate_ReductionType == reductionType) {
+        this->lineTo(reduction);
+        SkStrokerPriv::JoinProc saveJoiner = fJoiner;
+        fJoiner = SkStrokerPriv::JoinFactory(SkPaint::kRound_Join);
+        this->lineTo(pt2);
+        fJoiner = saveJoiner;
+        return;
+    }
+    SkASSERT(kQuad_ReductionType == reductionType);
+    SkVector normalAB, unitAB, normalBC, unitBC;
+    this->preJoinTo(pt1, &normalAB, &unitAB, false);
+    SkQuadConstruct quadPts;
+    this->init(kOuter_StrokeType, &quadPts, 0, 1);
+    if (!this->quadStroke(quad, &quadPts)) {
+        return;
+    }
+    this->init(kInner_StrokeType, &quadPts, 0, 1);
+    if (!this->quadStroke(quad, &quadPts)) {
+        return;
+    }
+    this->setQuadEndNormal(quad, normalAB, unitAB, &normalBC, &unitBC);
+#else
     bool    degenerateAB = SkPath::IsLineDegenerate(fPrevPt, pt1);
     bool    degenerateBC = SkPath::IsLineDegenerate(pt1, pt2);
 
@@ -414,12 +821,450 @@ void SkPathStroker::quadTo(const SkPoint& pt1, const SkPoint& pt2) {
                           kMaxQuadSubdivide);
         }
     }
+#endif
 
     this->postJoinTo(pt2, normalBC, unitBC);
 }
 
+#if QUAD_STROKE_APPROXIMATION
+// Given a point on the curve and its derivative, scale the derivative by the radius, and
+// compute the perpendicular point and its tangent.
+void SkPathStroker::setRayPts(const SkPoint& tPt, SkVector* dxy, SkPoint* onPt,
+        SkPoint* tangent) const {
+    if (!dxy->setLength(fRadius)) {  // consider moving double logic into SkPoint::setLength
+        double xx = dxy->fX;
+        double yy = dxy->fY;
+        double dscale = fRadius / sqrt(xx * xx + yy * yy);
+        dxy->fX = SkDoubleToScalar(xx * dscale);
+        dxy->fY = SkDoubleToScalar(yy * dscale);
+    }
+    SkScalar axisFlip = SkIntToScalar(fStrokeType);  // go opposite ways for outer, inner
+    onPt->fX = tPt.fX + axisFlip * dxy->fY;
+    onPt->fY = tPt.fY - axisFlip * dxy->fX;
+    if (tangent) {
+        tangent->fX = onPt->fX + dxy->fX;
+        tangent->fY = onPt->fY + dxy->fY;
+    }
+}
+
+// Given a cubic and t, return the point on curve, its perpendicular, and the perpendicular tangent.
+// Returns false if the perpendicular could not be computed (because the derivative collapsed to 0)
+bool SkPathStroker::cubicPerpRay(const SkPoint cubic[4], SkScalar t, SkPoint* tPt, SkPoint* onPt,
+        SkPoint* tangent) const {
+    SkVector dxy;
+    SkEvalCubicAt(cubic, t, tPt, &dxy, NULL);
+    if (dxy.fX == 0 && dxy.fY == 0) {
+        if (SkScalarNearlyZero(t)) {
+            dxy = cubic[2] - cubic[0];
+        } else if (SkScalarNearlyZero(1 - t)) {
+            dxy = cubic[3] - cubic[1];
+        } else {
+            return false;
+        }
+        if (dxy.fX == 0 && dxy.fY == 0) {
+            dxy = cubic[3] - cubic[0];
+        }
+    }
+    setRayPts(*tPt, &dxy, onPt, tangent);
+    return true;
+}
+
+// Given a cubic and a t range, find the start and end if they haven't been found already.
+bool SkPathStroker::cubicQuadEnds(const SkPoint cubic[4], SkQuadConstruct* quadPts) {
+    if (!quadPts->fStartSet) {
+        SkPoint cubicStartPt;
+        if (!this->cubicPerpRay(cubic, quadPts->fStartT, &cubicStartPt, &quadPts->fQuad[0],
+                &quadPts->fTangentStart)) {
+            return false;
+        }
+        quadPts->fStartSet = true;
+    }
+    if (!quadPts->fEndSet) {
+        SkPoint cubicEndPt;
+        if (!this->cubicPerpRay(cubic, quadPts->fEndT, &cubicEndPt, &quadPts->fQuad[2],
+                &quadPts->fTangentEnd)) {
+            return false;
+        }
+        quadPts->fEndSet = true;
+    }
+    return true;
+}
+
+bool SkPathStroker::cubicQuadMid(const SkPoint cubic[4], const SkQuadConstruct* quadPts,
+        SkPoint* mid) const {
+    SkPoint cubicMidPt;
+    return this->cubicPerpRay(cubic, quadPts->fMidT, &cubicMidPt, mid, NULL);
+}
+
+// Given a quad and t, return the point on curve, its perpendicular, and the perpendicular tangent.
+void SkPathStroker::quadPerpRay(const SkPoint quad[3], SkScalar t, SkPoint* tPt, SkPoint* onPt,
+        SkPoint* tangent) const {
+    SkVector dxy;
+    SkEvalQuadAt(quad, t, tPt, &dxy);
+    if (dxy.fX == 0 && dxy.fY == 0) {
+        dxy = quad[2] - quad[0];
+    }
+    setRayPts(*tPt, &dxy, onPt, tangent);
+}
+
+// Find the intersection of the stroke tangents to construct a stroke quad.
+// Return whether the stroke is a degenerate (a line), a quad, or must be split.
+// Optionally compute the quad's control point.
+SkPathStroker::ResultType SkPathStroker::intersectRay(SkQuadConstruct* quadPts,
+        IntersectRayType intersectRayType  STROKER_DEBUG_PARAMS(int depth)) const {
+    const SkPoint& start = quadPts->fQuad[0];
+    const SkPoint& end = quadPts->fQuad[2];
+    SkVector aLen = quadPts->fTangentStart - start;
+    SkVector bLen = quadPts->fTangentEnd - end;
+    SkScalar denom = aLen.cross(bLen);
+    SkVector ab0 = start - end;
+    SkScalar numerA = bLen.cross(ab0);
+    SkScalar numerB = aLen.cross(ab0);
+    if (!SkScalarNearlyZero(denom)) {
+        // if the perpendicular distances from the quad points to the opposite tangent line
+        // are small, a straight line is good enough
+        SkScalar dist1 = pt_to_line(start, end, quadPts->fTangentEnd);
+        SkScalar dist2 = pt_to_line(end, start, quadPts->fTangentStart);
+        if (SkTMax(dist1, dist2) <= fError * fError) {
+            return STROKER_RESULT(kDegenerate_ResultType, depth, quadPts,
+                    "SkTMax(dist1=%g, dist2=%g) <= fError * fError", dist1, dist2);
+        }
+        if ((numerA >= 0) != (numerB >= 0)) {
+            if (kCtrlPt_RayType == intersectRayType) {
+                numerA /= denom;
+                SkPoint* ctrlPt = &quadPts->fQuad[1];
+                ctrlPt->fX = start.fX * (1 - numerA) + quadPts->fTangentStart.fX * numerA;
+                ctrlPt->fY = start.fY * (1 - numerA) + quadPts->fTangentStart.fY * numerA;
+            }
+            return STROKER_RESULT(kQuad_ResultType, depth, quadPts,
+                    "(numerA=%g >= 0) != (numerB=%g >= 0)", numerA, numerB);
+        }
+        return STROKER_RESULT(kSplit_ResultType, depth, quadPts,
+                "(numerA=%g >= 0) == (numerB=%g >= 0)", numerA, numerB);
+    } else { // if the lines are parallel, straight line is good enough
+        return STROKER_RESULT(kDegenerate_ResultType, depth, quadPts,
+                "SkScalarNearlyZero(denom=%g)", denom);
+    }
+}
+
+// Given a cubic and a t-range, determine if the stroke can be described by a quadratic.
+SkPathStroker::ResultType SkPathStroker::tangentsMeet(const SkPoint cubic[4],
+        SkQuadConstruct* quadPts) {
+    if (!this->cubicQuadEnds(cubic, quadPts)) {
+        return kNormalError_ResultType;
+    }
+    return intersectRay(quadPts, kResultType_RayType  STROKER_DEBUG_PARAMS(fRecursionDepth));
+}
+
+// Intersect the line with the quad and return the t values on the quad where the line crosses.
+static int intersect_quad_ray(const SkPoint line[2], const SkPoint quad[3], SkScalar roots[2]) {
+    SkVector vec = line[1] - line[0];
+    SkScalar r[3];
+    for (int n = 0; n < 3; ++n) {
+        r[n] = (quad[n].fY - line[0].fY) * vec.fX - (quad[n].fX - line[0].fX) * vec.fY;
+    }
+    SkScalar A = r[2];
+    SkScalar B = r[1];
+    SkScalar C = r[0];
+    A += C - 2 * B;  // A = a - 2*b + c
+    B -= C;  // B = -(b - c)
+    return SkFindUnitQuadRoots(A, 2 * B, C, roots);
+}
+
+// Return true if the point is close to the bounds of the quad. This is used as a quick reject.
+bool SkPathStroker::ptInQuadBounds(const SkPoint quad[3], const SkPoint& pt) const {
+    SkScalar xMin = SkTMin(SkTMin(quad[0].fX, quad[1].fX), quad[2].fX);
+    if (pt.fX + fError < xMin) {
+        return false;
+    }
+    SkScalar xMax = SkTMax(SkTMax(quad[0].fX, quad[1].fX), quad[2].fX);
+    if (pt.fX - fError > xMax) {
+        return false;
+    }
+    SkScalar yMin = SkTMin(SkTMin(quad[0].fY, quad[1].fY), quad[2].fY);
+    if (pt.fY + fError < yMin) {
+        return false;
+    }
+    SkScalar yMax = SkTMax(SkTMax(quad[0].fY, quad[1].fY), quad[2].fY);
+    if (pt.fY - fError > yMax) {
+        return false;
+    }
+    return true;
+}
+
+static bool points_within_dist(const SkPoint& nearPt, const SkPoint& farPt, SkScalar limit) {
+    return nearPt.distanceToSqd(farPt) <= limit * limit;
+}
+
+static bool sharp_angle(const SkPoint quad[3]) {
+    SkVector smaller = quad[1] - quad[0];
+    SkVector larger = quad[1] - quad[2];
+    SkScalar smallerLen = smaller.lengthSqd();
+    SkScalar largerLen = larger.lengthSqd();
+    if (smallerLen > largerLen) {
+        SkTSwap(smaller, larger);
+        largerLen = smallerLen;
+    }
+    if (!smaller.setLength(largerLen)) {
+        return false;
+    }
+    SkScalar dot = smaller.dot(larger);
+    return dot > 0;
+}
+
+SkPathStroker::ResultType SkPathStroker::strokeCloseEnough(const SkPoint stroke[3],
+        const SkPoint ray[2], SkQuadConstruct* quadPts  STROKER_DEBUG_PARAMS(int depth)) const {
+    SkPoint strokeMid;
+    SkEvalQuadAt(stroke, SK_ScalarHalf, &strokeMid);
+    // measure the distance from the curve to the quad-stroke midpoint, compare to radius
+    if (points_within_dist(ray[0], strokeMid, fError)) {  // if the difference is small
+        if (sharp_angle(quadPts->fQuad)) {
+            return STROKER_RESULT(kSplit_ResultType, depth, quadPts,
+                    "sharp_angle (1) =%g,%g, %g,%g, %g,%g",
+                    quadPts->fQuad[0].fX, quadPts->fQuad[0].fY,
+                    quadPts->fQuad[1].fX, quadPts->fQuad[1].fY,
+                    quadPts->fQuad[2].fX, quadPts->fQuad[2].fY);
+        }
+        return STROKER_RESULT(kQuad_ResultType, depth, quadPts,
+                "points_within_dist(ray[0]=%g,%g, strokeMid=%g,%g, fError)",
+                ray[0].fX, ray[0].fY, strokeMid.fX, strokeMid.fY);
+    }
+    // measure the distance to quad's bounds (quick reject)
+        // an alternative : look for point in triangle
+    if (!ptInQuadBounds(stroke, ray[0])) {  // if far, subdivide
+        return STROKER_RESULT(kSplit_ResultType, depth, quadPts,
+                "!pt_in_quad_bounds(stroke=(%g,%g %g,%g %g,%g), ray[0]=%g,%g)",
+                stroke[0].fX, stroke[0].fY, stroke[1].fX, stroke[1].fY, stroke[2].fX, stroke[2].fY,
+                ray[0].fX, ray[0].fY);
+    }
+    // measure the curve ray distance to the quad-stroke
+    SkScalar roots[2];
+    int rootCount = intersect_quad_ray(ray, stroke, roots);
+    if (rootCount != 1) {
+        return STROKER_RESULT(kSplit_ResultType, depth, quadPts,
+                "rootCount=%d != 1", rootCount);
+    }
+    SkPoint quadPt;
+    SkEvalQuadAt(stroke, roots[0], &quadPt);
+    SkScalar error = fError * (SK_Scalar1 - SkScalarAbs(roots[0] - 0.5f) * 2);
+    if (points_within_dist(ray[0], quadPt, error)) {  // if the difference is small, we're done
+        if (sharp_angle(quadPts->fQuad)) {
+            return STROKER_RESULT(kSplit_ResultType, depth, quadPts,
+                    "sharp_angle (2) =%g,%g, %g,%g, %g,%g",
+                    quadPts->fQuad[0].fX, quadPts->fQuad[0].fY,
+                    quadPts->fQuad[1].fX, quadPts->fQuad[1].fY,
+                    quadPts->fQuad[2].fX, quadPts->fQuad[2].fY);
+        }
+        return STROKER_RESULT(kQuad_ResultType, depth, quadPts,
+                "points_within_dist(ray[0]=%g,%g, quadPt=%g,%g, error=%g)",
+                ray[0].fX, ray[0].fY, quadPt.fX, quadPt.fY, error);
+    }
+    // otherwise, subdivide
+    return STROKER_RESULT(kSplit_ResultType, depth, quadPts, "%s", "fall through");
+}
+
+SkPathStroker::ResultType SkPathStroker::compareQuadCubic(const SkPoint cubic[4],
+        SkQuadConstruct* quadPts) {
+    // get the quadratic approximation of the stroke
+    if (!this->cubicQuadEnds(cubic, quadPts)) {
+        return kNormalError_ResultType;
+    }
+    ResultType resultType = intersectRay(quadPts, kCtrlPt_RayType
+            STROKER_DEBUG_PARAMS(fRecursionDepth) );
+    if (resultType != kQuad_ResultType) {
+        return resultType;
+    }
+    // project a ray from the curve to the stroke
+    SkPoint ray[2];  // point near midpoint on quad, midpoint on cubic
+    if (!this->cubicPerpRay(cubic, quadPts->fMidT, &ray[1], &ray[0], NULL)) {
+        return kNormalError_ResultType;
+    }
+    return strokeCloseEnough(quadPts->fQuad, ray, quadPts  STROKER_DEBUG_PARAMS(fRecursionDepth));
+}
+
+// if false is returned, caller splits quadratic approximation
+SkPathStroker::ResultType SkPathStroker::compareQuadQuad(const SkPoint quad[3],
+        SkQuadConstruct* quadPts) {
+    // get the quadratic approximation of the stroke
+    if (!quadPts->fStartSet) {
+        SkPoint quadStartPt;
+        this->quadPerpRay(quad, quadPts->fStartT, &quadStartPt, &quadPts->fQuad[0],
+                &quadPts->fTangentStart);
+        quadPts->fStartSet = true;
+    }
+    if (!quadPts->fEndSet) {
+        SkPoint quadEndPt;
+        this->quadPerpRay(quad, quadPts->fEndT, &quadEndPt, &quadPts->fQuad[2],
+                &quadPts->fTangentEnd);
+        quadPts->fEndSet = true;
+    }
+    ResultType resultType = intersectRay(quadPts, kCtrlPt_RayType
+            STROKER_DEBUG_PARAMS(fRecursionDepth));
+    if (resultType != kQuad_ResultType) {
+        return resultType;
+    }
+    // project a ray from the curve to the stroke
+    SkPoint ray[2];
+    this->quadPerpRay(quad, quadPts->fMidT, &ray[1], &ray[0], NULL);
+    return strokeCloseEnough(quadPts->fQuad, ray, quadPts  STROKER_DEBUG_PARAMS(fRecursionDepth));
+}
+
+void SkPathStroker::addDegenerateLine(const SkQuadConstruct* quadPts) {
+    const SkPoint* quad = quadPts->fQuad;
+    SkPath* path = fStrokeType == kOuter_StrokeType ? &fOuter : &fInner;
+    path->lineTo(quad[2].fX, quad[2].fY);
+}
+
+bool SkPathStroker::cubicMidOnLine(const SkPoint cubic[4], const SkQuadConstruct* quadPts) const {
+    SkPoint strokeMid;
+    if (!cubicQuadMid(cubic, quadPts, &strokeMid)) {
+        return false;
+    }
+    SkScalar dist = pt_to_line(strokeMid, quadPts->fQuad[0], quadPts->fQuad[2]);
+    return dist < fError * fError;
+}
+
+bool SkPathStroker::cubicStroke(const SkPoint cubic[4], SkQuadConstruct* quadPts) {
+    if (!fFoundTangents) {
+        ResultType resultType = this->tangentsMeet(cubic, quadPts);
+        if (kQuad_ResultType != resultType) {
+            if (kNormalError_ResultType == resultType) {
+                return false;
+            }
+            if ((kDegenerate_ResultType == resultType
+                    || points_within_dist(quadPts->fQuad[0], quadPts->fQuad[2], fError))
+                    && cubicMidOnLine(cubic, quadPts)) {
+                addDegenerateLine(quadPts);
+                return true;
+            }
+        } else {
+            fFoundTangents = true;
+        }
+    }
+    if (fFoundTangents) {
+        ResultType resultType = this->compareQuadCubic(cubic, quadPts);
+        if (kQuad_ResultType == resultType) {
+            SkPath* path = fStrokeType == kOuter_StrokeType ? &fOuter : &fInner;
+            const SkPoint* stroke = quadPts->fQuad;
+            path->quadTo(stroke[1].fX, stroke[1].fY, stroke[2].fX, stroke[2].fY);
+            return true;
+        }
+        if (kDegenerate_ResultType == resultType) {
+            addDegenerateLine(quadPts);
+            return true;
+        }
+        if (kNormalError_ResultType == resultType) {
+            return false;
+        }
+    }
+    if (!SkScalarIsFinite(quadPts->fQuad[2].fX) || !SkScalarIsFinite(quadPts->fQuad[2].fY)) {
+        return false;  // just abort if projected quad isn't representable
+    }
+    SkDEBUGCODE(gMaxRecursion[fFoundTangents] = SkTMax(gMaxRecursion[fFoundTangents],
+            fRecursionDepth + 1));
+    if (++fRecursionDepth > kRecursiveLimits[fFoundTangents]) {
+        return false;  // just abort if projected quad isn't representable
+    }
+    SkQuadConstruct half;
+    if (!half.initWithStart(quadPts)) {
+        addDegenerateLine(quadPts);
+        return true;
+    }
+    if (!this->cubicStroke(cubic, &half)) {
+        return false;
+    }
+    if (!half.initWithEnd(quadPts)) {
+        addDegenerateLine(quadPts);
+        return true;
+    }
+    if (!this->cubicStroke(cubic, &half)) {
+        return false;
+    }
+    --fRecursionDepth;
+    return true;
+}
+
+bool SkPathStroker::quadStroke(const SkPoint quad[3], SkQuadConstruct* quadPts) {
+    ResultType resultType = this->compareQuadQuad(quad, quadPts);
+    if (kQuad_ResultType == resultType) {
+        const SkPoint* stroke = quadPts->fQuad;
+        SkPath* path = fStrokeType == kOuter_StrokeType ? &fOuter : &fInner;
+        path->quadTo(stroke[1].fX, stroke[1].fY, stroke[2].fX, stroke[2].fY);
+        return true;
+    }
+    if (kDegenerate_ResultType == resultType) {
+        addDegenerateLine(quadPts);
+        return true;
+    }
+    SkDEBUGCODE(gMaxRecursion[kQuad_RecursiveLimit] = SkTMax(gMaxRecursion[kQuad_RecursiveLimit],
+            fRecursionDepth + 1));
+    if (++fRecursionDepth > kRecursiveLimits[kQuad_RecursiveLimit]) {
+        return false;  // just abort if projected quad isn't representable
+    }
+    SkQuadConstruct half;
+    (void) half.initWithStart(quadPts);
+    if (!this->quadStroke(quad, &half)) {
+        return false;
+    }
+    (void) half.initWithEnd(quadPts);
+    if (!this->quadStroke(quad, &half)) {
+        return false;
+    }
+    --fRecursionDepth;
+    return true;
+}
+
+#endif
+
 void SkPathStroker::cubicTo(const SkPoint& pt1, const SkPoint& pt2,
                             const SkPoint& pt3) {
+#if QUAD_STROKE_APPROXIMATION
+    const SkPoint cubic[4] = { fPrevPt, pt1, pt2, pt3 };
+    SkPoint reduction[3];
+    const SkPoint* tangentPt;
+    ReductionType reductionType = CheckCubicLinear(cubic, reduction, &tangentPt);
+    if (kPoint_ReductionType == reductionType) {
+        return;
+    }
+    if (kLine_ReductionType == reductionType) {
+        this->lineTo(pt3);
+        return;
+    }
+    if (kDegenerate_ReductionType <= reductionType && kDegenerate3_ReductionType >= reductionType) {
+        this->lineTo(reduction[0]);
+        SkStrokerPriv::JoinProc saveJoiner = fJoiner;
+        fJoiner = SkStrokerPriv::JoinFactory(SkPaint::kRound_Join);
+        if (kDegenerate2_ReductionType <= reductionType) {
+            this->lineTo(reduction[1]);
+        }
+        if (kDegenerate3_ReductionType == reductionType) {
+            this->lineTo(reduction[2]);
+        }
+        this->lineTo(pt3);
+        fJoiner = saveJoiner;
+        return;
+    }
+    SkASSERT(kQuad_ReductionType == reductionType);
+    SkVector normalAB, unitAB, normalCD, unitCD;
+    this->preJoinTo(*tangentPt, &normalAB, &unitAB, false);
+    SkScalar tValues[2];
+    int count = SkFindCubicInflections(cubic, tValues);
+    SkScalar lastT = 0;
+    for (int index = 0; index <= count; ++index) {
+        SkScalar nextT = index < count ? tValues[index] : 1;
+        SkQuadConstruct quadPts;
+        this->init(kOuter_StrokeType, &quadPts, lastT, nextT);
+        if (!this->cubicStroke(cubic, &quadPts)) {
+            return;
+        }
+        this->init(kInner_StrokeType, &quadPts, lastT, nextT);
+        if (!this->cubicStroke(cubic, &quadPts)) {
+            return;
+        }
+        lastT = nextT;
+    }
+    this->setCubicEndNormal(cubic, normalAB, unitAB, &normalCD, &unitCD);
+#else
     bool    degenerateAB = SkPath::IsLineDegenerate(fPrevPt, pt1);
     bool    degenerateBC = SkPath::IsLineDegenerate(pt1, pt2);
     bool    degenerateCD = SkPath::IsLineDegenerate(pt2, pt3);
@@ -465,6 +1310,7 @@ void SkPathStroker::cubicTo(const SkPoint& pt1, const SkPoint& pt2,
 
         }
     }
+#endif
 
     this->postJoinTo(pt3, normalCD, unitCD);
 }
@@ -498,6 +1344,13 @@ SkStroke::SkStroke(const SkPaint& p, SkScalar width) {
     fDoFill     = SkToU8(p.getStyle() == SkPaint::kStrokeAndFill_Style);
 }
 
+#if QUAD_STROKE_APPROXIMATION
+void SkStroke::setError(SkScalar error) {
+    SkASSERT(error > 0);
+    fError = error;
+}
+#endif
+
 void SkStroke::setWidth(SkScalar width) {
     SkASSERT(width >= 0);
     fWidth = width;
@@ -575,8 +1428,13 @@ void SkStroke::strokePath(const SkPath& src, SkPath* dst) const {
     SkAutoConicToQuads converter;
     const SkScalar conicTol = SK_Scalar1 / 4;
 
+#if QUAD_STROKE_APPROXIMATION
+    SkPathStroker   stroker(src, radius, fMiterLimit, fError, this->getCap(),
+                            this->getJoin());
+#else
     SkPathStroker   stroker(src, radius, fMiterLimit, this->getCap(),
                             this->getJoin());
+#endif
     SkPath::Iter    iter(src, false);
     SkPath::Verb    lastSegment = SkPath::kMove_Verb;
 
diff --git a/src/core/SkStroke.h b/src/core/SkStroke.h
index a6a9f08331..cb329399a9 100644
--- a/src/core/SkStroke.h
+++ b/src/core/SkStroke.h
@@ -11,6 +11,19 @@
 #include "SkPath.h"
 #include "SkPoint.h"
 #include "SkPaint.h"
+#include "SkStrokerPriv.h"
+
+// set to 1 to use experimental outset stroking with quads
+#ifndef QUAD_STROKE_APPROXIMATION
+#define QUAD_STROKE_APPROXIMATION 0
+#endif
+
+#if QUAD_STROKE_APPROXIMATION && defined(SK_DEBUG)
+extern bool gDebugStrokerErrorSet;
+extern SkScalar gDebugStrokerError;
+
+extern int gMaxRecursion[];
+#endif
 
 /** \class SkStroke
     SkStroke is the utility class that constructs paths by stroking
@@ -30,6 +43,9 @@ public:
     SkPaint::Join   getJoin() const { return (SkPaint::Join)fJoin; }
     void        setJoin(SkPaint::Join);
 
+#if QUAD_STROKE_APPROXIMATION
+    void    setError(SkScalar);
+#endif
     void    setMiterLimit(SkScalar);
     void    setWidth(SkScalar);
 
@@ -46,6 +62,9 @@ public:
     ////////////////////////////////////////////////////////////////
 
 private:
+#if QUAD_STROKE_APPROXIMATION
+    SkScalar    fError;
+#endif
     SkScalar    fWidth, fMiterLimit;
     uint8_t     fCap, fJoin;
     SkBool8     fDoFill;
diff --git a/src/core/SkStrokeRec.cpp b/src/core/SkStrokeRec.cpp
index a4c73af2c5..22f0562fe2 100644
--- a/src/core/SkStrokeRec.cpp
+++ b/src/core/SkStrokeRec.cpp
@@ -108,6 +108,9 @@ bool SkStrokeRec::applyToPath(SkPath* dst, const SkPath& src) const {
     stroker.setMiterLimit(fMiterLimit);
     stroker.setWidth(fWidth);
     stroker.setDoFill(fStrokeAndFill);
+#if QUAD_STROKE_APPROXIMATION
+    stroker.setError(1);
+#endif
     stroker.strokePath(src, dst);
     return true;
 }
diff --git a/tests/StrokerTest.cpp b/tests/StrokerTest.cpp
new file mode 100755
index 0000000000..804e0a1d5f
--- /dev/null
+++ b/tests/StrokerTest.cpp
@@ -0,0 +1,452 @@
+#include "PathOpsCubicIntersectionTestData.h"
+#include "PathOpsQuadIntersectionTestData.h"
+#include "SkCommonFlags.h"
+#include "SkPaint.h"
+#include "SkPath.h"
+#include "SkRandom.h"
+#include "SkStrokerPriv.h"
+#include "SkTime.h"
+#include "Test.h"
+
+DEFINE_bool2(extendedTest, x, false, "run extended tests regardless of how long takes");
+
+#define MS_TEST_DURATION 10
+
+const SkScalar widths[] = {-FLT_MAX, -1, -0.1f, -FLT_EPSILON, 0, FLT_EPSILON,
+        0.0000001f, 0.000001f, 0.00001f, 0.0001f, 0.001f, 0.01f,
+        0.1f, 0.2f, 0.3f, 0.4f, 0.5f, 1, 1.1f, 2, 10, 10e2f, 10e3f, 10e4f, 10e5f, 10e6f, 10e7f,
+        10e8f, 10e9f, 10e10f, 10e20f,  FLT_MAX };
+size_t widths_count = SK_ARRAY_COUNT(widths);
+
+static void pathTest(const SkPath& path) {
+    SkPaint p;
+	SkPath fill;
+    p.setStyle(SkPaint::kStroke_Style);
+    for (size_t index = 0; index < widths_count; ++index) {
+        p.setStrokeWidth(widths[index]);
+        p.getFillPath(path, &fill);
+    }
+}
+
+static void cubicTest(const SkPoint c[4]) {
+	SkPath path;
+	path.moveTo(c[0].fX, c[0].fY);
+	path.cubicTo(c[1].fX, c[1].fY, c[2].fX, c[2].fY, c[3].fX, c[3].fY);
+	pathTest(path);
+}
+
+static void quadTest(const SkPoint c[3]) {
+	SkPath path;
+	path.moveTo(c[0].fX, c[0].fY);
+	path.quadTo(c[1].fX, c[1].fY, c[2].fX, c[2].fY);
+	pathTest(path);
+}
+
+static void cubicSetTest(const SkDCubic* dCubic, size_t count) {
+    SkMSec limit = SkTime::GetMSecs() + MS_TEST_DURATION;
+	for (size_t index = 0; index < count; ++index) {
+		const SkDCubic& d = dCubic[index];
+		SkPoint c[4] = { {(float) d[0].fX, (float) d[0].fY}, {(float) d[1].fX, (float) d[1].fY},
+                         {(float) d[2].fX, (float) d[2].fY}, {(float) d[3].fX, (float) d[3].fY} };
+	    cubicTest(c);
+        if (!FLAGS_extendedTest && SkTime::GetMSecs() > limit) {
+            return;
+        }
+	}
+}
+
+static void cubicPairSetTest(const SkDCubic dCubic[][2], size_t count) {
+    SkMSec limit = SkTime::GetMSecs() + MS_TEST_DURATION;
+	for (size_t index = 0; index < count; ++index) {
+		for (int pair = 0; pair < 2; ++pair) {
+			const SkDCubic& d = dCubic[index][pair];
+			SkPoint c[4] = { {(float) d[0].fX, (float) d[0].fY}, {(float) d[1].fX, (float) d[1].fY},
+                             {(float) d[2].fX, (float) d[2].fY}, {(float) d[3].fX, (float) d[3].fY} };
+			cubicTest(c);
+            if (!FLAGS_extendedTest && SkTime::GetMSecs() > limit) {
+                return;
+            }
+		}
+	}
+}
+
+static void quadSetTest(const SkDQuad* dQuad, size_t count) {
+    SkMSec limit = SkTime::GetMSecs() + MS_TEST_DURATION;
+	for (size_t index = 0; index < count; ++index) {
+		const SkDQuad& d = dQuad[index];
+		SkPoint c[3] = { {(float) d[0].fX, (float) d[0].fY}, {(float) d[1].fX, (float) d[1].fY},
+                         {(float) d[2].fX, (float) d[2].fY}  };
+	    quadTest(c);
+        if (!FLAGS_extendedTest && SkTime::GetMSecs() > limit) {
+            return;
+        }
+	}
+}
+
+static void quadPairSetTest(const SkDQuad dQuad[][2], size_t count) {
+    SkMSec limit = SkTime::GetMSecs() + MS_TEST_DURATION;
+	for (size_t index = 0; index < count; ++index) {
+		for (int pair = 0; pair < 2; ++pair) {
+			const SkDQuad& d = dQuad[index][pair];
+			SkPoint c[3] = { {(float) d[0].fX, (float) d[0].fY}, {(float) d[1].fX, (float) d[1].fY},
+                             {(float) d[2].fX, (float) d[2].fY}  };
+			quadTest(c);
+            if (!FLAGS_extendedTest && SkTime::GetMSecs() > limit) {
+                return;
+            }
+		}
+	}
+}
+
+DEF_TEST(QuadStrokerSet, reporter) {
+	quadSetTest(quadraticLines, quadraticLines_count);
+	quadSetTest(quadraticPoints, quadraticPoints_count);
+	quadSetTest(quadraticModEpsilonLines, quadraticModEpsilonLines_count);
+	quadPairSetTest(quadraticTests, quadraticTests_count);
+}
+
+DEF_TEST(CubicStrokerSet, reporter) {
+	cubicSetTest(pointDegenerates, pointDegenerates_count);
+	cubicSetTest(notPointDegenerates, notPointDegenerates_count);
+	cubicSetTest(lines, lines_count);
+	cubicSetTest(notLines, notLines_count);
+	cubicSetTest(modEpsilonLines, modEpsilonLines_count);
+	cubicSetTest(lessEpsilonLines, lessEpsilonLines_count);
+	cubicSetTest(negEpsilonLines, negEpsilonLines_count);
+	cubicPairSetTest(tests, tests_count);
+}
+
+static SkScalar unbounded(SkLCGRandom& r) {
+    uint32_t val = r.nextU();
+    return SkBits2Float(val);
+}
+
+static SkScalar unboundedPos(SkLCGRandom& r) {
+    uint32_t val = r.nextU() & 0x7fffffff;
+    return SkBits2Float(val);
+}
+
+DEF_TEST(QuadStrokerUnbounded, reporter) {
+    SkLCGRandom r;
+    SkPaint p;
+    p.setStyle(SkPaint::kStroke_Style);
+#if defined(SK_DEBUG) && QUAD_STROKE_APPROXIMATION
+    int best = 0;
+    sk_bzero(gMaxRecursion, sizeof(gMaxRecursion[0]) * 3);
+#endif
+    SkMSec limit = SkTime::GetMSecs() + MS_TEST_DURATION;
+    for (int i = 0; i < 1000000; ++i) {
+        SkPath path, fill;
+        path.moveTo(unbounded(r), unbounded(r));
+        path.quadTo(unbounded(r), unbounded(r), unbounded(r), unbounded(r));
+        p.setStrokeWidth(unboundedPos(r));
+        p.getFillPath(path, &fill);
+#if defined(SK_DEBUG) && QUAD_STROKE_APPROXIMATION
+        if (best < gMaxRecursion[2]) {
+            if (FLAGS_verbose) {
+                SkDebugf("\n%s quad=%d width=%1.9g\n", __FUNCTION__, gMaxRecursion[2],
+                        p.getStrokeWidth());
+                path.dumpHex();
+                SkDebugf("fill:\n");
+                fill.dumpHex();
+            }
+            best = gMaxRecursion[2];
+        }
+#endif
+        if (!FLAGS_extendedTest && SkTime::GetMSecs() > limit) {
+            return;
+        }
+    }
+#if defined(SK_DEBUG) && QUAD_STROKE_APPROXIMATION
+    if (FLAGS_verbose) {
+       SkDebugf("\n%s max quad=%d\n", __FUNCTION__, best);
+    }
+#endif
+}
+
+DEF_TEST(CubicStrokerUnbounded, reporter) {
+    SkLCGRandom r;
+    SkPaint p;
+    p.setStyle(SkPaint::kStroke_Style);
+#if defined(SK_DEBUG) && QUAD_STROKE_APPROXIMATION
+    int bestTan = 0;
+    int bestCubic = 0;
+    sk_bzero(gMaxRecursion, sizeof(gMaxRecursion[0]) * 3);
+#endif
+    SkMSec limit = SkTime::GetMSecs() + MS_TEST_DURATION;
+    for (int i = 0; i < 1000000; ++i) {
+        SkPath path, fill;
+        path.moveTo(unbounded(r), unbounded(r));
+        path.cubicTo(unbounded(r), unbounded(r), unbounded(r), unbounded(r),
+                unbounded(r), unbounded(r));
+        p.setStrokeWidth(unboundedPos(r));
+        p.getFillPath(path, &fill);
+    #if defined(SK_DEBUG) && QUAD_STROKE_APPROXIMATION
+        if (bestTan < gMaxRecursion[0] || bestCubic < gMaxRecursion[1]) {
+            if (FLAGS_verbose) {
+                SkDebugf("\n%s tan=%d cubic=%d width=%1.9g\n", __FUNCTION__, gMaxRecursion[0],
+                        gMaxRecursion[1], p.getStrokeWidth());
+                path.dumpHex();
+                SkDebugf("fill:\n");
+                fill.dumpHex();
+            }
+            bestTan = SkTMax(bestTan, gMaxRecursion[0]);
+            bestCubic = SkTMax(bestCubic, gMaxRecursion[1]);
+        }
+    #endif
+        if (!FLAGS_extendedTest && SkTime::GetMSecs() > limit) {
+            return;
+        }
+    }
+#if defined(SK_DEBUG) && QUAD_STROKE_APPROXIMATION
+    if (FLAGS_verbose) {
+        SkDebugf("\n%s max tan=%d cubic=%d\n", __FUNCTION__, bestTan, bestCubic);
+    }
+#endif
+}
+
+DEF_TEST(QuadStrokerConstrained, reporter) {
+    SkLCGRandom r;
+    SkPaint p;
+    p.setStyle(SkPaint::kStroke_Style);
+#if defined(SK_DEBUG) && QUAD_STROKE_APPROXIMATION
+    int best = 0;
+    sk_bzero(gMaxRecursion, sizeof(gMaxRecursion[0]) * 3);
+#endif
+    SkMSec limit = SkTime::GetMSecs() + MS_TEST_DURATION;
+    for (int i = 0; i < 1000000; ++i) {
+        SkPath path, fill;
+        SkPoint quad[3];
+        quad[0].fX = r.nextRangeF(0, 500);
+        quad[0].fY = r.nextRangeF(0, 500);
+        const SkScalar halfSquared = 0.5f * 0.5f;
+        do {
+            quad[1].fX = r.nextRangeF(0, 500);
+            quad[1].fY = r.nextRangeF(0, 500);
+        } while (quad[0].distanceToSqd(quad[1]) < halfSquared);
+        do {
+            quad[2].fX = r.nextRangeF(0, 500);
+            quad[2].fY = r.nextRangeF(0, 500);
+        } while (quad[0].distanceToSqd(quad[2]) < halfSquared
+                || quad[1].distanceToSqd(quad[2]) < halfSquared);
+        path.moveTo(quad[0].fX, quad[0].fY);
+        path.quadTo(quad[1].fX, quad[1].fY, quad[2].fX, quad[2].fY);
+        p.setStrokeWidth(r.nextRangeF(0, 500));
+        p.getFillPath(path, &fill);
+#if defined(SK_DEBUG) && QUAD_STROKE_APPROXIMATION
+        if (best < gMaxRecursion[2]) {
+            if (FLAGS_verbose) {
+                SkDebugf("\n%s quad=%d width=%1.9g\n", __FUNCTION__, gMaxRecursion[2],
+                        p.getStrokeWidth());
+                path.dumpHex();
+                SkDebugf("fill:\n");
+                fill.dumpHex();
+            }
+            best = gMaxRecursion[2];
+        }
+#endif
+        if (!FLAGS_extendedTest && SkTime::GetMSecs() > limit) {
+            return;
+        }
+    }
+#if defined(SK_DEBUG) && QUAD_STROKE_APPROXIMATION
+    if (FLAGS_verbose) {
+        SkDebugf("\n%s max quad=%d\n", __FUNCTION__, best);
+    }
+#endif
+}
+
+DEF_TEST(CubicStrokerConstrained, reporter) {
+    SkLCGRandom r;
+    SkPaint p;
+    p.setStyle(SkPaint::kStroke_Style);
+#if defined(SK_DEBUG) && QUAD_STROKE_APPROXIMATION
+    int bestTan = 0;
+    int bestCubic = 0;
+    sk_bzero(gMaxRecursion, sizeof(gMaxRecursion[0]) * 3);
+#endif
+    SkMSec limit = SkTime::GetMSecs() + MS_TEST_DURATION;
+    for (int i = 0; i < 1000000; ++i) {
+        SkPath path, fill;
+        SkPoint cubic[4];
+        cubic[0].fX = r.nextRangeF(0, 500);
+        cubic[0].fY = r.nextRangeF(0, 500);
+        const SkScalar halfSquared = 0.5f * 0.5f;
+        do {
+            cubic[1].fX = r.nextRangeF(0, 500);
+            cubic[1].fY = r.nextRangeF(0, 500);
+        } while (cubic[0].distanceToSqd(cubic[1]) < halfSquared);
+        do {
+            cubic[2].fX = r.nextRangeF(0, 500);
+            cubic[2].fY = r.nextRangeF(0, 500);
+        } while (  cubic[0].distanceToSqd(cubic[2]) < halfSquared
+                || cubic[1].distanceToSqd(cubic[2]) < halfSquared);
+        do {
+            cubic[3].fX = r.nextRangeF(0, 500);
+            cubic[3].fY = r.nextRangeF(0, 500);
+        } while (  cubic[0].distanceToSqd(cubic[3]) < halfSquared
+                || cubic[1].distanceToSqd(cubic[3]) < halfSquared
+                || cubic[2].distanceToSqd(cubic[3]) < halfSquared);
+        path.moveTo(cubic[0].fX, cubic[0].fY);
+        path.cubicTo(cubic[1].fX, cubic[1].fY, cubic[2].fX, cubic[2].fY, cubic[3].fX, cubic[3].fY);
+        p.setStrokeWidth(r.nextRangeF(0, 500));
+        p.getFillPath(path, &fill);
+#if defined(SK_DEBUG) && QUAD_STROKE_APPROXIMATION
+        if (bestTan < gMaxRecursion[0] || bestCubic < gMaxRecursion[1]) {
+            if (FLAGS_verbose) {
+                SkDebugf("\n%s tan=%d cubic=%d width=%1.9g\n", __FUNCTION__, gMaxRecursion[0],
+                        gMaxRecursion[1], p.getStrokeWidth());
+                path.dumpHex();
+                SkDebugf("fill:\n");
+                fill.dumpHex();
+            }
+            bestTan = SkTMax(bestTan, gMaxRecursion[0]);
+            bestCubic = SkTMax(bestCubic, gMaxRecursion[1]);
+        }
+#endif
+        if (!FLAGS_extendedTest && SkTime::GetMSecs() > limit) {
+            return;
+        }
+    }
+#if defined(SK_DEBUG) && QUAD_STROKE_APPROXIMATION
+    if (FLAGS_verbose) {
+        SkDebugf("\n%s max tan=%d cubic=%d\n", __FUNCTION__, bestTan, bestCubic);
+    }
+#endif
+}
+
+DEF_TEST(QuadStrokerRange, reporter) {
+    SkLCGRandom r;
+    SkPaint p;
+    p.setStyle(SkPaint::kStroke_Style);
+#if defined(SK_DEBUG) && QUAD_STROKE_APPROXIMATION
+    int best = 0;
+    sk_bzero(gMaxRecursion, sizeof(gMaxRecursion[0]) * 3);
+#endif
+    SkMSec limit = SkTime::GetMSecs() + MS_TEST_DURATION;
+    for (int i = 0; i < 1000000; ++i) {
+        SkPath path, fill;
+        SkPoint quad[3];
+        quad[0].fX = r.nextRangeF(0, 500);
+        quad[0].fY = r.nextRangeF(0, 500);
+        quad[1].fX = r.nextRangeF(0, 500);
+        quad[1].fY = r.nextRangeF(0, 500);
+        quad[2].fX = r.nextRangeF(0, 500);
+        quad[2].fY = r.nextRangeF(0, 500);
+        path.moveTo(quad[0].fX, quad[0].fY);
+        path.quadTo(quad[1].fX, quad[1].fY, quad[2].fX, quad[2].fY);
+        p.setStrokeWidth(r.nextRangeF(0, 500));
+        p.getFillPath(path, &fill);
+#if defined(SK_DEBUG) && QUAD_STROKE_APPROXIMATION
+        if (best < gMaxRecursion[2]) {
+            if (FLAGS_verbose) {
+                SkDebugf("\n%s quad=%d width=%1.9g\n", __FUNCTION__, gMaxRecursion[2],
+                        p.getStrokeWidth());
+                path.dumpHex();
+                SkDebugf("fill:\n");
+                fill.dumpHex();
+            }
+            best = gMaxRecursion[2];
+        }
+#endif
+        if (!FLAGS_extendedTest && SkTime::GetMSecs() > limit) {
+            return;
+        }
+    }
+#if defined(SK_DEBUG) && QUAD_STROKE_APPROXIMATION
+    if (FLAGS_verbose) {
+        SkDebugf("\n%s max quad=%d\n", __FUNCTION__, best);
+    }
+#endif
+}
+
+DEF_TEST(CubicStrokerRange, reporter) {
+    SkLCGRandom r;
+    SkPaint p;
+    p.setStyle(SkPaint::kStroke_Style);
+#if defined(SK_DEBUG) && QUAD_STROKE_APPROXIMATION
+    int best[2] = { 0 };
+    sk_bzero(gMaxRecursion, sizeof(gMaxRecursion[0]) * 3);
+#endif
+    SkMSec limit = SkTime::GetMSecs() + MS_TEST_DURATION;
+    for (int i = 0; i < 1000000; ++i) {
+        SkPath path, fill;
+        path.moveTo(r.nextRangeF(0, 500), r.nextRangeF(0, 500));
+        path.cubicTo(r.nextRangeF(0, 500), r.nextRangeF(0, 500), r.nextRangeF(0, 500),
+                r.nextRangeF(0, 500), r.nextRangeF(0, 500), r.nextRangeF(0, 500));
+        p.setStrokeWidth(r.nextRangeF(0, 100));
+        p.getFillPath(path, &fill);
+#if defined(SK_DEBUG) && QUAD_STROKE_APPROXIMATION
+        if (best[0] < gMaxRecursion[0] || best[1] < gMaxRecursion[1]) {
+            if (FLAGS_verbose) {
+                SkDebugf("\n%s tan=%d cubic=%d width=%1.9g\n", __FUNCTION__, gMaxRecursion[0],
+                        gMaxRecursion[1], p.getStrokeWidth());
+                path.dumpHex();
+                SkDebugf("fill:\n");
+                fill.dumpHex();
+            }
+            best[0] = SkTMax(best[0], gMaxRecursion[0]);
+            best[1] = SkTMax(best[1], gMaxRecursion[1]);
+        }
+#endif
+        if (!FLAGS_extendedTest && SkTime::GetMSecs() > limit) {
+            return;
+        }
+    }
+#if defined(SK_DEBUG) && QUAD_STROKE_APPROXIMATION
+    if (FLAGS_verbose) {
+        SkDebugf("\n%s max tan=%d cubic=%d\n", __FUNCTION__, best[0], best[1]);
+    }
+#endif
+}
+
+
+DEF_TEST(QuadStrokerOneOff, reporter) {
+#if defined(SK_DEBUG) && QUAD_STROKE_APPROXIMATION
+    sk_bzero(gMaxRecursion, sizeof(gMaxRecursion[0]) * 3);
+#endif
+    SkPaint p;
+    p.setStyle(SkPaint::kStroke_Style);
+    p.setStrokeWidth(SkDoubleToScalar(164.683548));
+
+    SkPath path, fill;
+path.moveTo(SkBits2Float(0x43c99223), SkBits2Float(0x42b7417e));
+path.quadTo(SkBits2Float(0x4285d839), SkBits2Float(0x43ed6645), SkBits2Float(0x43c941c8), SkBits2Float(0x42b3ace3));
+    p.getFillPath(path, &fill);
+    if (FLAGS_verbose) {
+        SkDebugf("\n%s path\n", __FUNCTION__);
+        path.dump();
+        SkDebugf("fill:\n");
+        fill.dump();
+    }
+#if defined(SK_DEBUG) && QUAD_STROKE_APPROXIMATION
+    if (FLAGS_verbose) {
+        SkDebugf("max quad=%d\n", gMaxRecursion[2]);
+    }
+#endif
+}
+
+DEF_TEST(CubicStrokerOneOff, reporter) {
+#if defined(SK_DEBUG) && QUAD_STROKE_APPROXIMATION
+    sk_bzero(gMaxRecursion, sizeof(gMaxRecursion[0]) * 3);
+#endif
+    SkPaint p;
+    p.setStyle(SkPaint::kStroke_Style);
+    p.setStrokeWidth(SkDoubleToScalar(42.835968));
+
+    SkPath path, fill;
+path.moveTo(SkBits2Float(0x433f5370), SkBits2Float(0x43d1f4b3));
+path.cubicTo(SkBits2Float(0x4331cb76), SkBits2Float(0x43ea3340), SkBits2Float(0x4388f498), SkBits2Float(0x42f7f08d), SkBits2Float(0x43f1cd32), SkBits2Float(0x42802ec1));
+    p.getFillPath(path, &fill);
+    if (FLAGS_verbose) {
+        SkDebugf("\n%s path\n", __FUNCTION__);
+        path.dump();
+        SkDebugf("fill:\n");
+        fill.dump();
+    }
+#if defined(SK_DEBUG) && QUAD_STROKE_APPROXIMATION
+    if (FLAGS_verbose) {
+        SkDebugf("max tan=%d cubic=%d\n", gMaxRecursion[0], gMaxRecursion[1]);
+    }
+#endif
+}