Preserve convex control point polygon in cubic->quadratic approximation

GM test modified, will require rebaselining.

Review URL: http://codereview.appspot.com/6355088/





git-svn-id: http://skia.googlecode.com/svn/trunk@4518 2bbb7eff-a529-9590-31e7-b0007b416f81

5 files changed, 178 insertions, 49 deletions

diff --git a/gm/convexpaths.cpp b/gm/convexpaths.cpp
index ebe715d866..d1c6aeeff0 100644
--- a/gm/convexpaths.cpp
+++ b/gm/convexpaths.cpp
@@ -134,7 +134,6 @@ protected:
                                                   100 * SK_Scalar1),
                                  25 * SK_Scalar1,  130 * SK_Scalar1, false);
         */
-
         // cubics
         fPaths.push_back().cubicTo( 1 * SK_Scalar1,  1 * SK_Scalar1,
                                    10 * SK_Scalar1,  90 * SK_Scalar1,
@@ -143,6 +142,27 @@ protected:
                                     20 * SK_Scalar1, 100 * SK_Scalar1,
                                      0 * SK_Scalar1,   0 * SK_Scalar1);
 
+        // path that has a cubic with a repeated first control point and
+        // a repeated last control point.
+        fPaths.push_back().moveTo(SK_Scalar1 * 10, SK_Scalar1 * 10);
+        fPaths.back().cubicTo(10 * SK_Scalar1, 10 * SK_Scalar1,
+                              10 * SK_Scalar1, 0,
+                              20 * SK_Scalar1, 0);
+        fPaths.back().lineTo(40 * SK_Scalar1, 0);
+        fPaths.back().cubicTo(40 * SK_Scalar1, 0,
+                              50 * SK_Scalar1, 0,
+                              50 * SK_Scalar1, 10 * SK_Scalar1);
+
+        // path that has two cubics with repeated middle control points.
+        fPaths.push_back().moveTo(SK_Scalar1 * 10, SK_Scalar1 * 10);
+        fPaths.back().cubicTo(10 * SK_Scalar1, 0,
+                              10 * SK_Scalar1, 0,
+                              20 * SK_Scalar1, 0);
+        fPaths.back().lineTo(40 * SK_Scalar1, 0);
+        fPaths.back().cubicTo(50 * SK_Scalar1, 0,
+                              50 * SK_Scalar1, 0,
+                              50 * SK_Scalar1, 10 * SK_Scalar1);
+
         // triangle where one edge is a degenerate quad
         fPaths.push_back().moveTo(SkFloatToScalar(8.59375f), 45 * SK_Scalar1);
         fPaths.back().quadTo(SkFloatToScalar(16.9921875f),   45 * SK_Scalar1,
diff --git a/src/gpu/GrAAConvexPathRenderer.cpp b/src/gpu/GrAAConvexPathRenderer.cpp
index ae4a77337b..41ab2427e3 100644
--- a/src/gpu/GrAAConvexPathRenderer.cpp
+++ b/src/gpu/GrAAConvexPathRenderer.cpp
@@ -63,7 +63,7 @@ void center_of_mass(const SegmentArray& segments, SkPoint* c) {
         p0 = segments[0].endPt();
         SkPoint pi;
         SkPoint pj;
-        // the first and last interation of the below loop would compute
+        // the first and last iteration of the below loop would compute
         // zeros since the starting / ending point is (0,0). So instead we start
         // at i=1 and make the last iteration i=count-2.
         pj = segments[1].endPt() - p0;
@@ -200,24 +200,20 @@ void update_degenerate_test(DegenerateTestData* data, const GrPoint& pt) {
     }
 }
 
-inline SkPath::Direction get_direction(const SkPath& path, const GrMatrix& m) {
-    SkPath::Direction dir;
-    GR_DEBUGCODE(bool succeeded = )
-    path.cheapComputeDirection(&dir);
-    GrAssert(succeeded);
+inline bool get_direction(const SkPath& path, const GrMatrix& m, SkPath::Direction* dir) {
+    if (!path.cheapComputeDirection(dir)) {
+        return false;
+    }
     // check whether m reverses the orientation
     GrAssert(!m.hasPerspective());
-    GrScalar det2x2 =
-        GrMul(m.get(SkMatrix::kMScaleX), m.get(SkMatrix::kMScaleY)) -
-        GrMul(m.get(SkMatrix::kMSkewX), m.get(SkMatrix::kMSkewY));
+    GrScalar det2x2 = GrMul(m.get(SkMatrix::kMScaleX), m.get(SkMatrix::kMScaleY)) -
+                      GrMul(m.get(SkMatrix::kMSkewX), m.get(SkMatrix::kMSkewY));
     if (det2x2 < 0) {
-        GR_STATIC_ASSERT(0 == SkPath::kCW_Direction ||
-                         1 == SkPath::kCW_Direction);
-        GR_STATIC_ASSERT(0 == SkPath::kCCW_Direction ||
-                         1 == SkPath::kCCW_Direction);
-        dir = static_cast<SkPath::Direction>(dir ^ 0x1);
+        GR_STATIC_ASSERT(0 == SkPath::kCW_Direction || 1 == SkPath::kCW_Direction);
+        GR_STATIC_ASSERT(0 == SkPath::kCCW_Direction || 1 == SkPath::kCCW_Direction);
+        *dir = static_cast<SkPath::Direction>(*dir ^ 0x1);
     }
-    return dir;
+    return true;
 }
 
 bool get_segments(const SkPath& path,
@@ -235,6 +231,11 @@ bool get_segments(const SkPath& path,
     // line paths. We detect paths that are very close to a line (zero area) and
     // draw nothing.
     DegenerateTestData degenerateData;
+    SkPath::Direction dir;
+    // get_direction can fail for some degenerate paths.
+    if (!get_direction(path, m, &dir)) {
+        return false;
+    }
 
     for (;;) {
         GrPoint pts[4];
@@ -269,7 +270,7 @@ bool get_segments(const SkPath& path,
                 // unlike quads and lines, the pts[0] will also be read (in
                 // convertCubicToQuads).
                 SkSTArray<15, SkPoint, true> quads;
-                GrPathUtils::convertCubicToQuads(pts, SK_Scalar1, &quads);
+                GrPathUtils::convertCubicToQuads(pts, SK_Scalar1, true, dir, &quads);
                 int count = quads.count();
                 for (int q = 0; q < count; q += 3) {
                     segments->push_back();
@@ -283,7 +284,6 @@ bool get_segments(const SkPath& path,
                 if (degenerateData.isDegenerate()) {
                     return false;
                 } else {
-                    SkPath::Direction dir = get_direction(path, m);
                     compute_vectors(segments, fanPt, dir, vCount, iCount);
                     return true;
                 }
diff --git a/src/gpu/GrAAHairLinePathRenderer.cpp b/src/gpu/GrAAHairLinePathRenderer.cpp
index 8aed4b03db..1731db5fbb 100644
--- a/src/gpu/GrAAHairLinePathRenderer.cpp
+++ b/src/gpu/GrAAHairLinePathRenderer.cpp
@@ -255,7 +255,7 @@ int generate_lines_and_quads(const SkPath& path,
                         totalQuadCount += 1 << subdiv;
                     }
                 }
-            break;
+                break;
             case kCubic_PathCmd:
                 SkPoint::Offset(pts, 4, translate);
                 m.mapPoints(devPts, pts, 4);
@@ -264,15 +264,17 @@ int generate_lines_and_quads(const SkPath& path,
                 bounds.roundOut(&ibounds);
                 if (SkIRect::Intersects(clip, ibounds)) {
                     PREALLOC_PTARRAY(32) q;
+                    // we don't need a direction if we aren't constraining the subdivision
+                    static const SkPath::Direction kDummyDir = SkPath::kCCW_Direction;
                     // We convert cubics to quadratics (for now).
                     // In perspective have to do conversion in src space.
                     if (persp) {
                         SkScalar tolScale = 
                             GrPathUtils::scaleToleranceToSrc(SK_Scalar1, m,
                                                              path.getBounds());
-                        GrPathUtils::convertCubicToQuads(pts, tolScale, &q);
+                        GrPathUtils::convertCubicToQuads(pts, tolScale, false, kDummyDir, &q);
                     } else {
-                        GrPathUtils::convertCubicToQuads(devPts, SK_Scalar1, &q);
+                        GrPathUtils::convertCubicToQuads(devPts, SK_Scalar1, false, kDummyDir, &q);
                     }
                     for (int i = 0; i < q.count(); i += 3) {
                         SkPoint* qInDevSpace;
@@ -311,7 +313,7 @@ int generate_lines_and_quads(const SkPath& path,
                         }
                     }
                 }
-            break;
+                break;
             case kClose_PathCmd:
                 break;
             case kEnd_PathCmd:
diff --git a/src/gpu/GrPathUtils.cpp b/src/gpu/GrPathUtils.cpp
index 4e487fd076..53e5e13b4d 100644
--- a/src/gpu/GrPathUtils.cpp
+++ b/src/gpu/GrPathUtils.cpp
@@ -277,60 +277,156 @@ void GrPathUtils::QuadUVMatrix::set(const GrPoint qPts[3]) {
 }
 
 namespace {
+
+// a is the first control point of the cubic.
+// ab is the vector from a to the second control point.
+// dc is the vector from the fourth to the third control point.
+// d is the fourth control point.
+// p is the candidate quadratic control point.
+// this assumes that the cubic doesn't inflect and is simple
+bool is_point_within_cubic_tangents(const SkPoint& a,
+                                    const SkVector& ab,
+                                    const SkVector& dc,
+                                    const SkPoint& d,
+                                    SkPath::Direction dir,
+                                    const SkPoint p) {
+    SkVector ap = p - a;
+    SkScalar apXab = ap.cross(ab);
+    if (SkPath::kCW_Direction == dir) {
+        if (apXab > 0) {
+            return false;
+        }
+    } else {
+        GrAssert(SkPath::kCCW_Direction == dir);
+        if (apXab < 0) {
+            return false;
+        }
+    }
+
+    SkVector dp = p - d;
+    SkScalar dpXdc = dp.cross(dc);
+    if (SkPath::kCW_Direction == dir) {
+        if (dpXdc < 0) {
+            return false;
+        }
+    } else {
+        GrAssert(SkPath::kCCW_Direction == dir);
+        if (dpXdc > 0) {
+            return false;
+        }
+    }
+    return true;
+}
+
 void convert_noninflect_cubic_to_quads(const SkPoint p[4],
-                                       SkScalar tolScale,
+                                       SkScalar toleranceSqd,
+                                       bool constrainWithinTangents,
+                                       SkPath::Direction dir,
                                        SkTArray<SkPoint, true>* quads,
                                        int sublevel = 0) {
-    SkVector ab = p[1];
-    ab -= p[0];
-    SkVector dc = p[2];
-    dc -= p[3];
-
-    static const SkScalar gLengthScale = 3 * SK_Scalar1 / 2;
-    // base tolerance is 2 pixels in dev coords.
-    const SkScalar distanceSqdTol = SkScalarMul(tolScale, 1 * SK_Scalar1);
+    SkVector ab = p[1] - p[0];
+    SkVector dc = p[2] - p[3];
+
+    if (ab.isZero()) {
+        if (dc.isZero()) {
+            SkPoint* degQuad = quads->push_back_n(3);
+            degQuad[0] = p[0];
+            degQuad[1] = p[0];
+            degQuad[2] = p[3];
+            return;
+        }
+        ab = p[2] - p[0];
+    }
+    if (dc.isZero()) {
+        dc = p[1] - p[3];
+    }
+
+    static const SkScalar kLengthScale = 3 * SK_Scalar1 / 2;
     static const int kMaxSubdivs = 10;
 
-    ab.scale(gLengthScale);
-    dc.scale(gLengthScale);
+    ab.scale(kLengthScale);
+    dc.scale(kLengthScale);
 
+    // e0 and e1 are extrapolations along vectors ab and dc.
     SkVector c0 = p[0];
     c0 += ab;
     SkVector c1 = p[3];
     c1 += dc;
 
-    SkScalar dSqd = c0.distanceToSqd(c1);
-    if (sublevel > kMaxSubdivs || dSqd <= distanceSqdTol) {
+    SkScalar dSqd = sublevel > kMaxSubdivs ? toleranceSqd : c0.distanceToSqd(c1);
+    if (dSqd < toleranceSqd) {
         SkPoint cAvg = c0;
         cAvg += c1;
         cAvg.scale(SK_ScalarHalf);
 
-        SkPoint* pts = quads->push_back_n(3);
-        pts[0] = p[0];
-        pts[1] = cAvg;
-        pts[2] = p[3];
-
-        return;
-    } else {
-        SkPoint choppedPts[7];
-        SkChopCubicAtHalf(p, choppedPts);
-        convert_noninflect_cubic_to_quads(choppedPts + 0, tolScale, 
-                                          quads, sublevel + 1);
-        convert_noninflect_cubic_to_quads(choppedPts + 3, tolScale,
-                                          quads, sublevel + 1);
+        bool subdivide = false;
+
+        if (constrainWithinTangents &&
+            !is_point_within_cubic_tangents(p[0], ab, dc, p[3], dir, cAvg)) {
+            // choose a new cAvg that is the intersection of the two tangent
+            // lines.
+            ab.setOrthog(ab);
+            SkScalar z0 = -ab.dot(p[0]);
+            dc.setOrthog(dc);
+            SkScalar z1 = -dc.dot(p[3]);
+            cAvg.fX = SkScalarMul(ab.fY, z1) - SkScalarMul(z0, dc.fY);
+            cAvg.fY = SkScalarMul(z0, dc.fX) - SkScalarMul(ab.fX, z1);
+            SkScalar z = SkScalarMul(ab.fX, dc.fY) - SkScalarMul(ab.fY, dc.fX);
+            z = SkScalarInvert(z);
+            cAvg.fX *= z;
+            cAvg.fY *= z;
+            if (sublevel <= kMaxSubdivs) {
+                SkScalar d0Sqd = c0.distanceToSqd(cAvg);
+                SkScalar d1Sqd = c1.distanceToSqd(cAvg);
+                // We need to subdivide if d0 + d1 > tolerance but we have the
+                // sqd values. We know the distances and tolerance can't be
+                // negative.
+                // (d0 + d1)^2 > toleranceSqd
+                // d0Sqd + 2*d0*d1 + d1Sqd > toleranceSqd
+                SkScalar d0d1 = SkScalarSqrt(SkScalarMul(d0Sqd, d1Sqd));
+                subdivide = 2 * d0d1 + d0Sqd + d1Sqd > toleranceSqd;
+            }
+        }
+        if (!subdivide) {
+            SkPoint* pts = quads->push_back_n(3);
+            pts[0] = p[0];
+            pts[1] = cAvg;
+            pts[2] = p[3];
+            return;
+        }
     }
+    SkPoint choppedPts[7];
+    SkChopCubicAtHalf(p, choppedPts);
+    convert_noninflect_cubic_to_quads(choppedPts + 0,
+                                      toleranceSqd,
+                                      constrainWithinTangents,
+                                      dir,
+                                      quads,
+                                      sublevel + 1);
+    convert_noninflect_cubic_to_quads(choppedPts + 3,
+                                      toleranceSqd,
+                                      constrainWithinTangents,
+                                      dir,
+                                      quads,
+                                      sublevel + 1);
 }
 }
 
 void GrPathUtils::convertCubicToQuads(const GrPoint p[4],
                                       SkScalar tolScale,
+                                      bool constrainWithinTangents,
+                                      SkPath::Direction dir,
                                       SkTArray<SkPoint, true>* quads) {
     SkPoint chopped[10];
     int count = SkChopCubicAtInflections(p, chopped);
 
+    // base tolerance is 1 pixel.
+    static const SkScalar kTolerance = SK_Scalar1;
+    const SkScalar tolSqd = SkScalarSquare(SkScalarMul(tolScale, kTolerance));
+
     for (int i = 0; i < count; ++i) {
         SkPoint* cubic = chopped + 3*i;
-        convert_noninflect_cubic_to_quads(cubic, tolScale, quads);
+        convert_noninflect_cubic_to_quads(cubic, tolSqd, constrainWithinTangents, dir, quads);
     }
 
 }
diff --git a/src/gpu/GrPathUtils.h b/src/gpu/GrPathUtils.h
index a1d0eb630b..31b639864e 100644
--- a/src/gpu/GrPathUtils.h
+++ b/src/gpu/GrPathUtils.h
@@ -96,12 +96,23 @@ namespace GrPathUtils {
         float fM[6];
     };
 
+
     // Converts a cubic into a sequence of quads. If working in device space
     // use tolScale = 1, otherwise set based on stretchiness of the matrix. The
     // result is sets of 3 points in quads (TODO: share endpoints in returned
     // array)
+    // When we approximate a cubic {a,b,c,d} with a quadratic we may have to
+    // ensure that the new control point lies between the lines ab and cd. The
+    // convex path renderer requires this. It starts with a path where all the
+    // control points taken together form a convex polygon. It relies on this
+    // property and the quadratic approximation of cubics step cannot alter it.
+    // Setting constrainWithinTangents to true enforces this property. When this
+    // is true the cubic must be simple and dir must specify the orientation of
+    // the cubic. Otherwise, dir is ignored.
     void convertCubicToQuads(const GrPoint p[4],
                              SkScalar tolScale,
+                             bool constrainWithinTangents,
+                             SkPath::Direction dir,
                              SkTArray<SkPoint, true>* quads);
 };
 #endif