perpendicular round rects; fuzzy convexity

src/core/SkPath.cpp

 
 /*
  * Copyright 2006 The Android Open Source Project
  *
  * Use of this source code is governed by a BSD-style license that can be
  * found in the LICENSE file.
  */
 
 
 #include "SkBuffer.h"
@@ skipping 1065 matching lines @@
     fDirection = this->hasOnlyMoveTos() ? dir : kUnknown_Direction;
 
     SkAutoPathBoundsUpdate apbu(this, rect);
     SkAutoDisableDirectionCheck(this);
 
     if (skip_hori) {
         rx = halfW;
     } 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
     this->moveTo(rect.fRight - rx, rect.fTop);                  // top-right
     if (dir == kCCW_Direction) {
         if (!skip_hori) {
             this->lineTo(rect.fLeft + rx, rect.fTop);           // top
         }
 #ifdef SK_IGNORE_QUAD_RR_CORNERS_OPT
         this->cubicTo(rect.fLeft + rx - sx, rect.fTop,
                       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) {
             this->lineTo(rect.fLeft, rect.fBottom - ry);        // left
         }
 #ifdef SK_IGNORE_QUAD_RR_CORNERS_OPT
         this->cubicTo(rect.fLeft, rect.fBottom - ry + sy,
                       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) {
             this->lineTo(rect.fRight - rx, rect.fBottom);       // bottom
         }
 #ifdef SK_IGNORE_QUAD_RR_CORNERS_OPT
         this->cubicTo(rect.fRight - rx + sx, rect.fBottom,
                       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) {
             this->lineTo(rect.fRight, rect.fTop + ry);          // right
         }
 #ifdef SK_IGNORE_QUAD_RR_CORNERS_OPT
         this->cubicTo(rect.fRight, rect.fTop + ry - sy,
                       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 {
 #ifdef SK_IGNORE_QUAD_RR_CORNERS_OPT
         this->cubicTo(rect.fRight - rx + sx, rect.fTop,
                       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) {
             this->lineTo(rect.fRight, rect.fBottom - ry);       // right
         }
 #ifdef SK_IGNORE_QUAD_RR_CORNERS_OPT
         this->cubicTo(rect.fRight, rect.fBottom - ry + sy,
                       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) {
             this->lineTo(rect.fLeft + rx, rect.fBottom);        // bottom
         }
 #ifdef SK_IGNORE_QUAD_RR_CORNERS_OPT
         this->cubicTo(rect.fLeft + rx - sx, rect.fBottom,
                       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) {
             this->lineTo(rect.fLeft, rect.fTop + ry);           // left
         }
 #ifdef SK_IGNORE_QUAD_RR_CORNERS_OPT
         this->cubicTo(rect.fLeft, rect.fTop + ry - sy,
                       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) {
             this->lineTo(rect.fRight - rx, rect.fTop);          // top
         }
     }
     this->close();
 }
 
 void SkPath::addOval(const SkRect& oval, Direction dir) {
@@ skipping 1038 matching lines @@
     SkASSERT(mask == fSegmentMask);
 #endif // SK_DEBUG_PATH
 }
 #endif // SK_DEBUG
 
 ///////////////////////////////////////////////////////////////////////////////
 
 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) {

[scroggo, 2013/11/01 16:04:10]

Is this deliberately different from SkScalarNearlyEqual in SkScalar.h?

Also, should this function go in SkScalar.h?

+    // 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
 struct Convexicator {
     Convexicator()
     : fPtCount(0)
     , fConvexity(SkPath::kConvex_Convexity)
     , fDirection(SkPath::kUnknown_Direction) {
         fSign = 0;
         // warnings
+        fLastPt.set(0, 0);
         fCurrPt.set(0, 0);
         fVec0.set(0, 0);
         fVec1.set(0, 0);
         fFirstVec.set(0, 0);
 
         fDx = fDy = 0;
         fSx = fSy = kValueNeverReturnedBySign;
     }
 
     SkPath::Convexity getConvexity() const { return fConvexity; }
 
     /** The direction returned is only valid if the path is determined convex */
     SkPath::Direction getDirection() const { return fDirection; }
 
     void addPt(const SkPoint& pt) {
         if (SkPath::kConcave_Convexity == fConvexity) {
             return;
         }
 
         if (0 == fPtCount) {
             fCurrPt = pt;
             ++fPtCount;
         } else {
             SkVector vec = pt - fCurrPt;
             if (vec.fX || vec.fY) {
+                fLastPt = fCurrPt;
                 fCurrPt = pt;
                 if (++fPtCount == 2) {
                     fFirstVec = fVec1 = vec;
                 } else {
                     SkASSERT(fPtCount > 2);
                     this->addVec(vec);
                 }
 
                 int sx = sign(vec.fX);
                 int sy = sign(vec.fY);
@@ skipping 13 matching lines @@
         if (fPtCount > 2) {
             this->addVec(fFirstVec);
         }
     }
 
 private:
     void addVec(const SkVector& vec) {
         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) {
                 fDirection = SkPath::kCW_Direction;
             } else if (-1 == sign) {
                 fDirection = SkPath::kCCW_Direction;
             }
         } else if (sign) {
             if (fSign != sign) {
                 fConvexity = SkPath::kConcave_Convexity;
                 fDirection = SkPath::kUnknown_Direction;
             }
         }
     }
 
+    SkPoint             fLastPt;
     SkPoint             fCurrPt;
     SkVector            fVec0, fVec1, fFirstVec;
     int                 fPtCount;   // non-degenerate points
     int                 fSign;
     SkPath::Convexity   fConvexity;
     SkPath::Direction   fDirection;
     int                 fDx, fDy, fSx, fSy;
 };
 
 SkPath::Convexity SkPath::internalGetConvexity() const {
@@ skipping 623 matching lines @@
     switch (this->getFillType()) {
         case SkPath::kEvenOdd_FillType:
         case SkPath::kInverseEvenOdd_FillType:
             w &= 1;
             break;
         default:
             break;
     }
     return SkToBool(w);
 }