thick stroke Beziers

src/core/SkStroke.cpp

Index: src/core/SkStroke.cpp
diff --git a/src/core/SkStroke.cpp b/src/core/SkStroke.cpp
index 1e4ae79a5e0108725d2492a268bdeac122e053bb..a9cc6cd60ad9ec5d684927ee9c5bbecce96a0842 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;