add unittest for IntersectLine, used by hairlines

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

3 files changed, 53 insertions, 12 deletions

diff --git a/src/core/SkEdgeClipper.cpp b/src/core/SkEdgeClipper.cpp
index dc136a6b56..d41291d4b7 100644
--- a/src/core/SkEdgeClipper.cpp
+++ b/src/core/SkEdgeClipper.cpp
@@ -235,23 +235,31 @@ static bool chopMonoCubicAt(SkScalar c0, SkScalar c1, SkScalar c2, SkScalar c3,
  //   SkASSERT(c0 <= c1 && c1 <= c2 && c2 <= c3);
     SkASSERT(c0 < target && target < c3);
 
-    SkScalar D = c0;
+    SkScalar D = c0 - target;
     SkScalar A = c3 + 3*(c1 - c2) - c0;
     SkScalar B = 3*(c2 - c1 - c1 + c0);
     SkScalar C = 3*(c1 - c0);
 
+    const SkScalar TOLERANCE = SK_Scalar1 / 4096;
     SkScalar minT = 0;
     SkScalar maxT = SK_Scalar1;
-    for (int i = 0; i < 8; i++) {
-        SkScalar mid = SkScalarAve(minT, maxT);
-        SkScalar coord = eval_cubic_coeff(A, B, C, D, mid);
-        if (coord < target) {
+    SkScalar mid;
+    int i;
+    for (i = 0; i < 16; i++) {
+        mid = SkScalarAve(minT, maxT);
+        SkScalar delta = eval_cubic_coeff(A, B, C, D, mid);
+        if (delta < 0) {
             minT = mid;
+            delta = -delta;
         } else {
             maxT = mid;
         }
+        if (delta < TOLERANCE) {
+            break;
+        }
     }
-    *t = SkScalarAve(minT, maxT);
+    *t = mid;
+//    SkDebugf("-- evalCubicAt %d delta %g\n", i, eval_cubic_coeff(A, B, C, D, *t));
     return true;
 }
 
diff --git a/src/core/SkLineClipper.cpp b/src/core/SkLineClipper.cpp
index 58bf6033a7..057f546d77 100644
--- a/src/core/SkLineClipper.cpp
+++ b/src/core/SkLineClipper.cpp
@@ -24,21 +24,37 @@ static SkScalar sect_with_vertical(const SkPoint src[2], SkScalar X) {
 
 ///////////////////////////////////////////////////////////////////////////////
 
+static inline bool nestedLT(SkScalar a, SkScalar b, SkScalar dim) {
+    return a <= b && (a < b || dim > 0);
+}
+
+// returns true if outer contains inner, even if inner is empty.
+// note: outer.contains(inner) always returns false if inner is empty.
+static inline bool containsNoEmptyCheck(const SkRect& outer,
+                                        const SkRect& inner) {
+    return  outer.fLeft <= inner.fLeft && outer.fTop <= inner.fTop &&
+            outer.fRight >= inner.fRight && outer.fBottom >= inner.fBottom;
+}
+
 bool SkLineClipper::IntersectLine(const SkPoint src[2], const SkRect& clip,
                                   SkPoint dst[2]) {
     SkRect bounds;
     
     bounds.set(src, 2);
-    if (bounds.fLeft >= clip.fRight || clip.fLeft >= bounds.fRight ||
-        bounds.fTop >= clip.fBottom || clip.fTop >= bounds.fBottom) {
-        return false;
-    }
-    if (clip.contains(bounds)) {
+    if (containsNoEmptyCheck(clip, bounds)) {
         if (src != dst) {
             memcpy(dst, src, 2 * sizeof(SkPoint));
         }
         return true;
     }
+    // check for no overlap, and only permit coincident edges if the line
+    // and the edge are colinear
+    if (nestedLT(bounds.fRight, clip.fLeft, bounds.width()) ||
+        nestedLT(clip.fRight, bounds.fLeft, bounds.width()) ||
+        nestedLT(bounds.fBottom, clip.fTop, bounds.height()) ||
+        nestedLT(clip.fBottom, bounds.fTop, bounds.height())) {
+        return false;
+    }
 
     int index0, index1;
     
@@ -70,7 +86,9 @@ bool SkLineClipper::IntersectLine(const SkPoint src[2], const SkRect& clip,
     }
 
     // check for quick-reject in X again, now that we may have been chopped
-    if (tmp[index1].fX <= clip.fLeft || tmp[index0].fX >= clip.fRight) {
+    if ((tmp[index1].fX <= clip.fLeft || tmp[index0].fX >= clip.fRight) &&
+        tmp[index0].fX < tmp[index1].fX) {
+        // only reject if we have a non-zero width
         return false;
     }
 
@@ -80,6 +98,10 @@ bool SkLineClipper::IntersectLine(const SkPoint src[2], const SkRect& clip,
     if (tmp[index1].fX > clip.fRight) {
         tmp[index1].set(clip.fRight, sect_with_vertical(src, clip.fRight));
     }
+#ifdef SK_DEBUG
+    bounds.set(tmp, 2);
+    SkASSERT(containsNoEmptyCheck(clip, bounds));
+#endif
     memcpy(dst, tmp, sizeof(tmp));
     return true;
 }
diff --git a/src/core/SkScan_Antihair.cpp b/src/core/SkScan_Antihair.cpp
index 13cdc09e79..0003298b38 100644
--- a/src/core/SkScan_Antihair.cpp
+++ b/src/core/SkScan_Antihair.cpp
@@ -429,6 +429,17 @@ void SkScan::AntiHairLine(const SkPoint& pt0, const SkPoint& pt1,
     if (clip) {
         SkRect clipBounds;
         clipBounds.set(clip->getBounds());
+        /*  We perform integral clipping later on, but we do a scalar clip first
+            to ensure that our coordinates are expressible in fixed/integers.
+
+            antialiased hairlines can draw up to 1/2 of a pixel outside of
+            their bounds, so we need to outset the clip before calling the
+            clipper. To make the numerics safer, we outset by a whole pixel,
+            since the 1/2 pixel boundary is important to the antihair blitter,
+            we don't want to risk numerical fate by chopping on that edge.
+         */
+        clipBounds.inset(-SK_Scalar1, -SK_Scalar1);
+
         if (!SkLineClipper::IntersectLine(pts, clipBounds, pts)) {
             return;
         }