Construct round rects with perpendicular tangents.

The round rects are constructed as before out of quadratics,
but without fudging the control points. Instead, the mid on-
curve point is nudged slightly outward to prevent the
convexity test from failing.

The convexity test now includes an error term for sign
inequality after computing the cross product of the control
lines. When the control points are represented as vectors,
the number of bits of precision may be greatly reduced.

Account for this by passing the number of bits available
from the original control point values into the equality
check.

Making round rect construction lines perpendicular improves
the chances of success when path ops encounters clips.

No new tests are needed -- this change is exercised by the
convex Path unit tests and the gm tests arcofzorro and
hairlines.

R=robertphillips@google.com, reed@google.com

Author: caryclark@google.com

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

git-svn-id: http://skia.googlecode.com/svn/trunk/src@12085 2bbb7eff-a529-9590-31e7-b0007b416f81
diff --git a/core/SkGeometry.cpp b/core/SkGeometry.cpp
index 5d0707a..9b15f9f 100644
--- a/core/SkGeometry.cpp
+++ b/core/SkGeometry.cpp
@@ -1256,43 +1256,34 @@
     return false;
 }
 
-#ifdef SK_SCALAR_IS_FLOAT
-
-// Due to floating point issues (i.e., 1.0f - SK_ScalarRoot2Over2 !=
-// SK_ScalarRoot2Over2 - SK_ScalarTanPIOver8), the "correct" off curve
-// control points cause the quadratic circle approximation to be concave.
-// SK_OffEps is used to pull in the off-curve control points a bit
-// to make the quadratic approximation convex.
-// Pulling the off-curve controls points in is preferable to pushing some
-// of the on-curve points off.
-#define SK_OffEps 0.0001f
-#else
-#define SK_OffEps 0
-#endif
-
-
 static const SkPoint gQuadCirclePts[kSkBuildQuadArcStorage] = {
-    { SK_Scalar1,                      0                                  },
-    { SK_Scalar1 - SK_OffEps,          SK_ScalarTanPIOver8 - SK_OffEps    },
-    { SK_ScalarRoot2Over2,             SK_ScalarRoot2Over2                },
-    { SK_ScalarTanPIOver8 - SK_OffEps, SK_Scalar1 - SK_OffEps             },
+// The mid point of the quadratic arc approximation is half way between the two
+// control points. The float epsilon adjustment moves the on curve point out by
+// two bits, distributing the convex test error between the round rect approximation
+// and the convex cross product sign equality test.
+#define SK_MID_RRECT_OFFSET (SK_Scalar1 + SK_ScalarTanPIOver8 + FLT_EPSILON * 4) / 2
+    { SK_Scalar1,            0                      },
+    { SK_Scalar1,            SK_ScalarTanPIOver8    },
+    { SK_MID_RRECT_OFFSET,   SK_MID_RRECT_OFFSET    },
+    { SK_ScalarTanPIOver8,   SK_Scalar1             },
 
-    { 0,                               SK_Scalar1                         },
-    { -SK_ScalarTanPIOver8 + SK_OffEps,SK_Scalar1 - SK_OffEps             },
-    { -SK_ScalarRoot2Over2,            SK_ScalarRoot2Over2                },
-    { -SK_Scalar1 + SK_OffEps,         SK_ScalarTanPIOver8 - SK_OffEps    },
+    { 0,                     SK_Scalar1             },
+    { -SK_ScalarTanPIOver8,  SK_Scalar1             },
+    { -SK_MID_RRECT_OFFSET,  SK_MID_RRECT_OFFSET    },
+    { -SK_Scalar1,           SK_ScalarTanPIOver8    },
 
-    { -SK_Scalar1,                     0                                  },
-    { -SK_Scalar1 + SK_OffEps,         -SK_ScalarTanPIOver8 + SK_OffEps   },
-    { -SK_ScalarRoot2Over2,            -SK_ScalarRoot2Over2               },
-    { -SK_ScalarTanPIOver8 + SK_OffEps,-SK_Scalar1 + SK_OffEps            },
+    { -SK_Scalar1,           0                      },
+    { -SK_Scalar1,           -SK_ScalarTanPIOver8   },
+    { -SK_MID_RRECT_OFFSET,  -SK_MID_RRECT_OFFSET   },
+    { -SK_ScalarTanPIOver8,  -SK_Scalar1            },
 
-    { 0,                               -SK_Scalar1                        },
-    { SK_ScalarTanPIOver8 - SK_OffEps, -SK_Scalar1 + SK_OffEps            },
-    { SK_ScalarRoot2Over2,             -SK_ScalarRoot2Over2               },
-    { SK_Scalar1 - SK_OffEps,          -SK_ScalarTanPIOver8 + SK_OffEps   },
+    { 0,                     -SK_Scalar1            },
+    { SK_ScalarTanPIOver8,   -SK_Scalar1            },
+    { SK_MID_RRECT_OFFSET,   -SK_MID_RRECT_OFFSET   },
+    { SK_Scalar1,            -SK_ScalarTanPIOver8   },
 
-    { SK_Scalar1,                      0                                  }
+    { SK_Scalar1,            0                      }
+#undef SK_MID_RRECT_OFFSET
 };
 
 int SkBuildQuadArc(const SkVector& uStart, const SkVector& uStop,
diff --git a/core/SkPath.cpp b/core/SkPath.cpp
index 94dd651..60cfe03 100644
--- a/core/SkPath.cpp
+++ b/core/SkPath.cpp
@@ -1083,23 +1083,21 @@
     } else if (skip_vert) {
         ry = halfH;
     }
-
 #ifdef SK_IGNORE_QUAD_RR_CORNERS_OPT
     SkScalar    sx = SkScalarMul(rx, CUBIC_ARC_FACTOR);
     SkScalar    sy = SkScalarMul(ry, CUBIC_ARC_FACTOR);
 
     this->incReserve(17);
 #else
-    // Please see SkBuildQuadArc for more information but, we need to pull
-    // the off-curve quadratic points in a little bit to make the round
-    // rects convex.
-    static const SkScalar kOffCurveEpsilon = 0.0001f;
+// The mid point of the quadratic arc approximation is half way between the two
+// control points. The float epsilon adjustment moves the on curve point out by
+// two bits, distributing the convex test error between the round rect approximation
+// and the convex cross product sign equality test.
+    SkScalar    midPtX = rx * (SK_Scalar1 + SK_ScalarTanPIOver8 + FLT_EPSILON * 4) / 2;
+    SkScalar    midPtY = ry * (SK_Scalar1 + SK_ScalarTanPIOver8 + FLT_EPSILON * 4) / 2;
 
-    SkScalar    midPtX = rx * SK_ScalarRoot2Over2;
-    SkScalar    midPtY = ry * SK_ScalarRoot2Over2;
-
-    SkScalar    offPtX = rx * SK_ScalarTanPIOver8 - kOffCurveEpsilon;
-    SkScalar    offPtY = ry * SK_ScalarTanPIOver8 - kOffCurveEpsilon;
+    SkScalar    offPtX = rx * SK_ScalarTanPIOver8;
+    SkScalar    offPtY = ry * SK_ScalarTanPIOver8;
 
     this->incReserve(21);
 #endif
@@ -1113,9 +1111,9 @@
                       rect.fLeft, rect.fTop + ry - sy,
                       rect.fLeft, rect.fTop + ry);          // top-left
 #else
-        this->quadTo(rect.fLeft + rx - offPtX, rect.fTop + kOffCurveEpsilon,
+        this->quadTo(rect.fLeft + rx - offPtX, rect.fTop,
                      rect.fLeft + rx - midPtX, rect.fTop + ry - midPtY);
-        this->quadTo(rect.fLeft + kOffCurveEpsilon, rect.fTop + ry - offPtY,
+        this->quadTo(rect.fLeft, rect.fTop + ry - offPtY,
                      rect.fLeft, rect.fTop + ry);
 #endif
         if (!skip_vert) {
@@ -1126,9 +1124,9 @@
                       rect.fLeft + rx - sx, rect.fBottom,
                       rect.fLeft + rx, rect.fBottom);       // bot-left
 #else
-        this->quadTo(rect.fLeft + kOffCurveEpsilon, rect.fBottom - ry + offPtY,
+        this->quadTo(rect.fLeft, rect.fBottom - ry + offPtY,
                      rect.fLeft + rx - midPtX, rect.fBottom - ry + midPtY);
-        this->quadTo(rect.fLeft + rx - offPtX, rect.fBottom - kOffCurveEpsilon,
+        this->quadTo(rect.fLeft + rx - offPtX, rect.fBottom,
                      rect.fLeft + rx, rect.fBottom);
 #endif
         if (!skip_hori) {
@@ -1139,9 +1137,9 @@
                       rect.fRight, rect.fBottom - ry + sy,
                       rect.fRight, rect.fBottom - ry);      // bot-right
 #else
-        this->quadTo(rect.fRight - rx + offPtX, rect.fBottom - kOffCurveEpsilon,
+        this->quadTo(rect.fRight - rx + offPtX, rect.fBottom,
                      rect.fRight - rx + midPtX, rect.fBottom - ry + midPtY);
-        this->quadTo(rect.fRight - kOffCurveEpsilon, rect.fBottom - ry + offPtY,
+        this->quadTo(rect.fRight, rect.fBottom - ry + offPtY,
                      rect.fRight, rect.fBottom - ry);
 #endif
         if (!skip_vert) {
@@ -1152,9 +1150,9 @@
                       rect.fRight - rx + sx, rect.fTop,
                       rect.fRight - rx, rect.fTop);         // top-right
 #else
-        this->quadTo(rect.fRight - kOffCurveEpsilon, rect.fTop + ry - offPtY,
+        this->quadTo(rect.fRight, rect.fTop + ry - offPtY,
                      rect.fRight - rx + midPtX, rect.fTop + ry - midPtY);
-        this->quadTo(rect.fRight - rx + offPtX, rect.fTop + kOffCurveEpsilon,
+        this->quadTo(rect.fRight - rx + offPtX, rect.fTop,
                      rect.fRight - rx, rect.fTop);
 #endif
     } else {
@@ -1163,9 +1161,9 @@
                       rect.fRight, rect.fTop + ry - sy,
                       rect.fRight, rect.fTop + ry);         // top-right
 #else
-        this->quadTo(rect.fRight - rx + offPtX, rect.fTop + kOffCurveEpsilon,
+        this->quadTo(rect.fRight - rx + offPtX, rect.fTop,
                      rect.fRight - rx + midPtX, rect.fTop + ry - midPtY);
-        this->quadTo(rect.fRight - kOffCurveEpsilon, rect.fTop + ry - offPtY,
+        this->quadTo(rect.fRight, rect.fTop + ry - offPtY,
                      rect.fRight, rect.fTop + ry);
 #endif
         if (!skip_vert) {
@@ -1176,9 +1174,9 @@
                       rect.fRight - rx + sx, rect.fBottom,
                       rect.fRight - rx, rect.fBottom);      // bot-right
 #else
-        this->quadTo(rect.fRight - kOffCurveEpsilon, rect.fBottom - ry + offPtY,
+        this->quadTo(rect.fRight, rect.fBottom - ry + offPtY,
                      rect.fRight - rx + midPtX, rect.fBottom - ry + midPtY);
-        this->quadTo(rect.fRight - rx + offPtX, rect.fBottom - kOffCurveEpsilon,
+        this->quadTo(rect.fRight - rx + offPtX, rect.fBottom,
                      rect.fRight - rx, rect.fBottom);
 #endif
         if (!skip_hori) {
@@ -1189,9 +1187,9 @@
                       rect.fLeft, rect.fBottom - ry + sy,
                       rect.fLeft, rect.fBottom - ry);       // bot-left
 #else
-        this->quadTo(rect.fLeft + rx - offPtX, rect.fBottom - kOffCurveEpsilon,
+        this->quadTo(rect.fLeft + rx - offPtX, rect.fBottom,
                      rect.fLeft + rx - midPtX, rect.fBottom - ry + midPtY);
-        this->quadTo(rect.fLeft + kOffCurveEpsilon, rect.fBottom - ry + offPtY,
+        this->quadTo(rect.fLeft, rect.fBottom - ry + offPtY,
                      rect.fLeft, rect.fBottom - ry);
 #endif
         if (!skip_vert) {
@@ -1202,9 +1200,9 @@
                       rect.fLeft + rx - sx, rect.fTop,
                       rect.fLeft + rx, rect.fTop);          // top-left
 #else
-        this->quadTo(rect.fLeft + kOffCurveEpsilon, rect.fTop + ry - offPtY,
+        this->quadTo(rect.fLeft, rect.fTop + ry - offPtY,
                      rect.fLeft + rx - midPtX, rect.fTop + ry - midPtY);
-        this->quadTo(rect.fLeft + rx - offPtX, rect.fTop + kOffCurveEpsilon,
+        this->quadTo(rect.fLeft + rx - offPtX, rect.fTop,
                      rect.fLeft + rx, rect.fTop);
 #endif
         if (!skip_hori) {
@@ -2263,8 +2261,20 @@
 static int sign(SkScalar x) { return x < 0; }
 #define kValueNeverReturnedBySign   2
 
-static int CrossProductSign(const SkVector& a, const SkVector& b) {
-    return SkScalarSignAsInt(SkPoint::CrossProduct(a, b));
+static bool AlmostEqual(SkScalar compA, SkScalar compB) {
+    // The error epsilon was empirically derived; worse case round rects
+    // with a mid point outset by 2x float epsilon in tests had an error
+    // of 12.
+    const int epsilon = 16;
+    if (!SkScalarIsFinite(compA) || !SkScalarIsFinite(compB)) {
+        return false;
+    }
+    if (sk_float_abs(compA) <= FLT_EPSILON && sk_float_abs(compB) <= FLT_EPSILON) {
+        return true;
+    }
+    int aBits = SkFloatAs2sCompliment(compA);
+    int bBits = SkFloatAs2sCompliment(compB);
+    return aBits < bBits + epsilon && bBits < aBits + epsilon;
 }
 
 // only valid for a single contour
@@ -2275,6 +2285,7 @@
     , fDirection(SkPath::kUnknown_Direction) {
         fSign = 0;
         // warnings
+        fLastPt.set(0, 0);
         fCurrPt.set(0, 0);
         fVec0.set(0, 0);
         fVec1.set(0, 0);
@@ -2300,6 +2311,7 @@
         } else {
             SkVector vec = pt - fCurrPt;
             if (vec.fX || vec.fY) {
+                fLastPt = fCurrPt;
                 fCurrPt = pt;
                 if (++fPtCount == 2) {
                     fFirstVec = fVec1 = vec;
@@ -2333,7 +2345,11 @@
         SkASSERT(vec.fX || vec.fY);
         fVec0 = fVec1;
         fVec1 = vec;
-        int sign = CrossProductSign(fVec0, fVec1);
+        SkScalar cross = SkPoint::CrossProduct(fVec0, fVec1);
+        SkScalar smallest = SkTMin(fCurrPt.fX, SkTMin(fCurrPt.fY, SkTMin(fLastPt.fX, fLastPt.fY)));
+        SkScalar largest = SkTMax(fCurrPt.fX, SkTMax(fCurrPt.fY, SkTMax(fLastPt.fX, fLastPt.fY)));
+        largest = SkTMax(largest, -smallest);
+        int sign = AlmostEqual(largest, largest + cross) ? 0 : SkScalarSignAsInt(cross);
         if (0 == fSign) {
             fSign = sign;
             if (1 == sign) {
@@ -2349,6 +2365,7 @@
         }
     }
 
+    SkPoint             fLastPt;
     SkPoint             fCurrPt;
     SkVector            fVec0, fVec1, fFirstVec;
     int                 fPtCount;   // non-degenerate points