From 087d5aafb18b88dfc6c6a5dbf59160c8be914e62 Mon Sep 17 00:00:00 2001
From: "reed@google.com" <reed@google.com@2bbb7eff-a529-9590-31e7-b0007b416f81>
Date: Wed, 29 Feb 2012 20:59:24 +0000
Subject: [PATCH] fix edgecase in chopcubic where we computed duplicate tvalues

git-svn-id: http://skia.googlecode.com/svn/trunk@3285 2bbb7eff-a529-9590-31e7-b0007b416f81
---
 src/core/SkGeometry.cpp | 70 ++++++++++++++++++++++++++++++++++++++++++++++++-
 tests/GeometryTest.cpp  | 22 ++++++++++++++++
 2 files changed, 91 insertions(+), 1 deletion(-)

diff --git a/src/core/SkGeometry.cpp b/src/core/SkGeometry.cpp
index 5308d56..de86827 100644
--- a/src/core/SkGeometry.cpp
+++ b/src/core/SkGeometry.cpp
@@ -834,6 +834,65 @@ static SkScalar refine_cubic_root(const SkFP coeff[4], SkScalar root)
 }
 #endif
 
+/**
+ *  Given an array and count, remove all pair-wise duplicates from the array,
+ *  keeping the existing sorting, and return the new count
+ */
+static int collaps_duplicates(float array[], int count) {
+    int n = count;
+    for (int n = count; n > 1; --n) {
+        if (array[0] == array[1]) {
+            for (int i = 1; i < n; ++i) {
+                array[i - 1] = array[i];
+            }
+            count -= 1;
+        } else {
+            array += 1;
+        }
+    }
+    return count;
+}
+
+#ifdef SK_DEBUG
+
+#define TEST_COLLAPS_ENTRY(array)   array, SK_ARRAY_COUNT(array)
+
+static void test_collaps_duplicates() {
+    static bool gOnce;
+    if (gOnce) { return; }
+    gOnce = true;
+    const float src0[] = { 0 };
+    const float src1[] = { 0, 0 };
+    const float src2[] = { 0, 1 };
+    const float src3[] = { 0, 0, 0 };
+    const float src4[] = { 0, 0, 1 };
+    const float src5[] = { 0, 1, 1 };
+    const float src6[] = { 0, 1, 2 };
+    const struct {
+        const float* fData;
+        int fCount;
+        int fCollapsedCount;
+    } data[] = {
+        { TEST_COLLAPS_ENTRY(src0), 1 },
+        { TEST_COLLAPS_ENTRY(src1), 1 },
+        { TEST_COLLAPS_ENTRY(src2), 2 },
+        { TEST_COLLAPS_ENTRY(src3), 1 },
+        { TEST_COLLAPS_ENTRY(src4), 2 },
+        { TEST_COLLAPS_ENTRY(src5), 2 },
+        { TEST_COLLAPS_ENTRY(src6), 3 },
+    };
+    for (size_t i = 0; i < SK_ARRAY_COUNT(data); ++i) {
+        float dst[3];
+        memcpy(dst, data[i].fData, data[i].fCount * sizeof(dst[0]));
+        int count = collaps_duplicates(dst, data[i].fCount);
+        SkASSERT(data[i].fCollapsedCount == count);
+        for (int j = 1; j < count; ++j) {
+            SkASSERT(dst[j-1] < dst[j]);
+        }
+    }
+}
+#endif
+
 #if defined _WIN32 && _MSC_VER >= 1300  && defined SK_SCALAR_IS_FIXED // disable warning : unreachable code if building fixed point for windows desktop
 #pragma warning ( disable : 4702 )
 #endif
@@ -841,6 +900,9 @@ static SkScalar refine_cubic_root(const SkFP coeff[4], SkScalar root)
 /*  Solve coeff(t) == 0, returning the number of roots that
     lie withing 0 < t < 1.
     coeff[0]t^3 + coeff[1]t^2 + coeff[2]t + coeff[3]
+ 
+    Eliminates repeated roots (so that all tValues are distinct, and are always
+    in increasing order.
 */
 static int solve_cubic_polynomial(const SkFP coeff[4], SkScalar tValues[3])
 {
@@ -895,8 +957,14 @@ static int solve_cubic_polynomial(const SkFP coeff[4], SkScalar tValues[3])
         if (is_unit_interval(r))
             *roots++ = r;
 
+        SkDEBUGCODE(test_collaps_duplicates();)
+
         // now sort the roots
-        bubble_sort(tValues, (int)(roots - tValues));
+        int count = (int)(roots - tValues);
+        SkASSERT((unsigned)count <= 3);
+        bubble_sort(tValues, count);
+        count = collaps_duplicates(tValues, count);
+        roots = tValues + count;    // so we compute the proper count below
 #endif
     }
     else                // we have 1 real root
diff --git a/tests/GeometryTest.cpp b/tests/GeometryTest.cpp
index 6158a20..7cee730 100644
--- a/tests/GeometryTest.cpp
+++ b/tests/GeometryTest.cpp
@@ -12,6 +12,26 @@ static bool nearly_equal(const SkPoint& a, const SkPoint& b) {
     return SkScalarNearlyEqual(a.fX, b.fX) && SkScalarNearlyEqual(a.fY, b.fY);
 }
 
+static void testChopCubic(skiatest::Reporter* reporter) {
+    /*
+        Inspired by this test, which used to assert that the tValues had dups
+     
+        <path stroke="#202020" d="M0,0 C0,0 1,1 2190,5130 C2190,5070 2220,5010 2205,4980" />
+     */
+    const SkPoint src[] = {
+        { SkIntToScalar(2190), SkIntToScalar(5130) },
+        { SkIntToScalar(2190), SkIntToScalar(5070) },
+        { SkIntToScalar(2220), SkIntToScalar(5010) },
+        { SkIntToScalar(2205), SkIntToScalar(4980) },
+    };
+    SkPoint dst[13];
+    SkScalar tValues[3];
+    int count = SkChopCubicAtMaxCurvature(src, dst, tValues);
+    // if we successfully collaps duplicate t-values, we should only get 2 segments
+    REPORTER_ASSERT(reporter, 2 == count);
+}
+
+
 static void TestGeometry(skiatest::Reporter* reporter) {
     SkPoint pts[3], dst[5];
 
@@ -35,6 +55,8 @@ static void TestGeometry(skiatest::Reporter* reporter) {
     for (int i = 0; i < 4; ++i) {
         REPORTER_ASSERT(reporter, nearly_equal(cubic[i], dst[i]));
     }
+    
+    testChopCubic(reporter);
 }
 
 #include "TestClassDef.h"
-- 
2.7.4