cumulative pathops patch

tests/PathOpsAngleTest.cpp

 /*
  * Copyright 2013 Google Inc.
  *
  * Use of this source code is governed by a BSD-style license that can be
  * found in the LICENSE file.
  */
 #include "PathOpsTestCommon.h"
 #include "SkIntersections.h"
+#include "SkOpContour.h"
 #include "SkOpSegment.h"
-#include "SkPathOpsTriangle.h"
 #include "SkRandom.h"
-#include "SkTArray.h"
 #include "SkTSort.h"
 #include "Test.h"
 
 static bool gDisableAngleTests = true;
 
 static float next(float f)
 {
     int fBits = SkFloatAs2sCompliment(f);
     ++fBits;
     float fNext = Sk2sComplimentAsFloat(fBits);
@@ skipping 161 matching lines @@
         double angle = diamond_angle(y, x);
         double rAngle = diamond_angle(ry, rx);
         double diff = fabs(angle - rAngle);
         SkDebugf("%s diamond xy=%1.9g rxy=%1.9g diff=%1.9g factor=%d\n", __FUNCTION__,
                 angle, rAngle, diff, (int) (diff / FLT_EPSILON));
     }
 }
 
 class PathOpsAngleTester {
 public:
-    static int After(const SkOpAngle& lh, const SkOpAngle& rh) {
+    static int After(SkOpAngle& lh, SkOpAngle& rh) {
         return lh.after(&rh);
     }
 
-    static int ConvexHullOverlaps(const SkOpAngle& lh, const SkOpAngle& rh) {
-        return lh.convexHullOverlaps(rh);
+    static int ConvexHullOverlaps(SkOpAngle& lh, SkOpAngle& rh) {
+        return lh.convexHullOverlaps(&rh);
     }
 
-    static int Orderable(const SkOpAngle& lh, const SkOpAngle& rh) {
-        return lh.orderable(rh);
+    static int Orderable(SkOpAngle& lh, SkOpAngle& rh) {
+        return lh.orderable(&rh);
     }
 
-    static int EndsIntersect(const SkOpAngle& lh, const SkOpAngle& rh) {
-        return lh.endsIntersect(rh);
+    static int EndsIntersect(SkOpAngle& lh, SkOpAngle& rh) {
+        return lh.endsIntersect(&rh);
     }
 
     static void SetNext(SkOpAngle& lh, SkOpAngle& rh) {
         lh.fNext = &rh;
     }
 };
 
 class PathOpsSegmentTester {
 public:
-    static void ConstructCubic(SkOpSegment* segment, SkPoint shortCubic[4]) {
-        segment->debugConstructCubic(shortCubic);
-    }
-
-    static void ConstructLine(SkOpSegment* segment, SkPoint shortLine[2]) {
-        segment->debugConstructLine(shortLine);
-    }
-
-    static void ConstructQuad(SkOpSegment* segment, SkPoint shortQuad[3]) {
-        segment->debugConstructQuad(shortQuad);
-    }
-
     static void DebugReset(SkOpSegment* segment) {
         segment->debugReset();
     }
 };
 
 struct CircleData {
     const SkDCubic fPts;
     const int fPtCount;
     SkPoint fShortPts[4];
 };
 
 static CircleData circleDataSet[] = {
     { {{{313.0155029296875, 207.90290832519531}, {320.05078125, 227.58743286132812}}}, 2, {} },
     { {{{313.0155029296875, 207.90290832519531}, {313.98246891063195, 219.33615203830394},
             {320.05078125, 227.58743286132812}}}, 3, {} },
 };
 
 static const int circleDataSetSize = (int) SK_ARRAY_COUNT(circleDataSet);
 
 DEF_TEST(PathOpsAngleCircle, reporter) {
-    SkOpSegment segment[2];
+    SkChunkAlloc allocator(4096);
+    SkOpContour contour;
+    SkOpGlobalState state(NULL  PATH_OPS_DEBUG_PARAMS(&contour));
+    contour.init(&state, false, false);
     for (int index = 0; index < circleDataSetSize; ++index) {
         CircleData& data = circleDataSet[index];
         for (int idx2 = 0; idx2 < data.fPtCount; ++idx2) {
             data.fShortPts[idx2] = data.fPts.fPts[idx2].asSkPoint();
         }
         switch (data.fPtCount) {
             case 2:
-                PathOpsSegmentTester::ConstructLine(&segment[index], data.fShortPts);
+                contour.addLine(data.fShortPts, &allocator);
                 break;
             case 3:
-                PathOpsSegmentTester::ConstructQuad(&segment[index], data.fShortPts);
+                contour.addQuad(data.fShortPts, &allocator);
                 break;
             case 4:
-                PathOpsSegmentTester::ConstructCubic(&segment[index], data.fShortPts);
+                contour.addCubic(data.fShortPts, &allocator);
                 break;
         }
     }
-    PathOpsAngleTester::Orderable(*segment[0].debugLastAngle(), *segment[1].debugLastAngle());
+    SkOpSegment* first = contour.first();
+    first->debugAddAngle(0, 1, &allocator);
+    SkOpSegment* next = first->next();
+    next->debugAddAngle(0, 1, &allocator);
+    PathOpsAngleTester::Orderable(*first->debugLastAngle(), *next->debugLastAngle());
 }
 
 struct IntersectData {
     const SkDCubic fPts;
     const int fPtCount;
     double fTStart;
     double fTEnd;
     SkPoint fShortPts[4];
 };
 
@@ skipping 94 matching lines @@
     { {{{447.967,894.438}, {448.007,894.424}, {448.014,894.422}}}, 3, 0, 1, {} }, // pathops_visualizer.htm:6538
     { {{{490.435,879.407}, {405.593,909.436}}}, 2, 0.500554405, 0.500000273, {} }, // pathops_visualizer.htm:6538
 }; //
 
 static IntersectData intersectDataSet16[] = { // pathops_visualizer.htm:7419
     { {{{1.000,4.000}, {4.000,5.000}, {3.000,2.000}, {6.000,3.000}}}, 4, 0.5, 0, {} }, // pathops_visualizer.htm:7377
     { {{{2.000,3.000}, {3.000,6.000}, {4.000,1.000}, {5.000,4.000}}}, 4, 0.5, 0.112701665, {} }, // pathops_visualizer.htm:7377
     { {{{5.000,4.000}, {2.000,3.000}}}, 2, 0.5, 0, {} }, // pathops_visualizer.htm:7377
 }; //
 
+// from skpi_gino_com_16
+static IntersectData intersectDataSet17[] = {
+    { /*seg=7*/ {{{270.974121f, 770.025879f}, {234.948273f, 734}, {184, 734}}}
+        , 3, 0.74590454, 0.547660352, {} },
+    { /*seg=8*/ {{{185, 734}, {252.93103f, 734}, {308, 789.06897f}, {308, 857}}}
+        , 4, 0.12052623, 0, {} },
+    { /*seg=7*/ {{{270.974121f, 770.025879f}, {234.948273f, 734}, {184, 734}}}
+        , 3, 0.74590454, 1, {} },
+};
+
+static IntersectData intersectDataSet18[] = {
+    { /*seg=7*/ {{{270.974121f, 770.025879f}, {234.948273f, 734}, {184, 734}}}
+        , 3, 0.74590454, 1, {} },
+    { /*seg=8*/ {{{185, 734}, {252.93103f, 734}, {308, 789.06897f}, {308, 857}}}
+        , 4, 0.12052623, 0.217351928, {} },
+    { /*seg=7*/ {{{270.974121f, 770.025879f}, {234.948273f, 734}, {184, 734}}}
+        , 3, 0.74590454, 0.547660352, {} },
+};
+
+static IntersectData intersectDataSet19[] = {
+    { /*seg=1*/ {{{0, 1}, {3, 5}, {2, 1}, {3, 1}}}
+        , 4, 0.135148995, 0.134791946, {} },
+    { /*seg=3*/ {{{1, 2}, {1, 2.15061641f}, {1, 2.21049166f}, {1.01366711f, 2.21379328f}}}
+        , 4, 0.956740456, 0.894913214, {} },
+    { /*seg=1*/ {{{0, 1}, {3, 5}, {2, 1}, {3, 1}}}
+        , 4, 0.135148995, 0.551812363, {} },
+};
+
 #define I(x) intersectDataSet##x
 
 static IntersectData* intersectDataSets[] = {
     I(1), I(2), I(3), I(4), I(5), I(6), I(7), I(8), I(9), I(10),
-    I(11), I(12), I(13), I(14), I(15), I(16),
+    I(11), I(12), I(13), I(14), I(15), I(16), I(17), I(18), I(19),
 };
 
 #undef I
 #define I(x) (int) SK_ARRAY_COUNT(intersectDataSet##x)
 
 static const int intersectDataSetSizes[] = {
     I(1), I(2), I(3), I(4), I(5), I(6), I(7), I(8), I(9), I(10),
-    I(11), I(12), I(13), I(14), I(15), I(16),
+    I(11), I(12), I(13), I(14), I(15), I(16), I(17), I(18), I(19),
 };
 
 #undef I
 
 static const int intersectDataSetsSize = (int) SK_ARRAY_COUNT(intersectDataSetSizes);
 
+struct FourPoints {
+    SkPoint pts[4];
+};
+
 DEF_TEST(PathOpsAngleAfter, reporter) {
+    SkChunkAlloc allocator(4096);
+    SkOpContour contour;
+    SkOpGlobalState state(NULL  PATH_OPS_DEBUG_PARAMS(&contour));
+    contour.init(&state, false, false);
     for (int index = intersectDataSetsSize - 1; index >= 0; --index) {
         IntersectData* dataArray = intersectDataSets[index];
         const int dataSize = intersectDataSetSizes[index];
-        SkOpSegment segment[3];
         for (int index2 = 0; index2 < dataSize - 2; ++index2) {
-            for (int temp = 0; temp < (int) SK_ARRAY_COUNT(segment); ++temp) {
-                PathOpsSegmentTester::DebugReset(&segment[temp]);
-            }
-            for (int index3 = 0; index3 < (int) SK_ARRAY_COUNT(segment); ++index3) {
+            allocator.reset();
+            contour.reset();
+            for (int index3 = 0; index3 < 3; ++index3) {
                 IntersectData& data = dataArray[index2 + index3];
-                SkPoint temp[4];
+                SkPoint* temp = (SkPoint*) SkOpTAllocator<FourPoints>::Allocate(&allocator);
                 for (int idx2 = 0; idx2 < data.fPtCount; ++idx2) {
                     temp[idx2] = data.fPts.fPts[idx2].asSkPoint();
                 }
                 switch (data.fPtCount) {
                     case 2: {
-                        SkDLine seg = SkDLine::SubDivide(temp, data.fTStart,
-                                data.fTStart < data.fTEnd ? 1 : 0);
-                        data.fShortPts[0] = seg[0].asSkPoint();
-                        data.fShortPts[1] = seg[1].asSkPoint();
-                        PathOpsSegmentTester::ConstructLine(&segment[index3], data.fShortPts);
+                        contour.addLine(temp, &allocator);
                         } break;
                     case 3: {
-                        SkDQuad seg = SkDQuad::SubDivide(temp, data.fTStart, data.fTEnd);
-                        data.fShortPts[0] = seg[0].asSkPoint();
-                        data.fShortPts[1] = seg[1].asSkPoint();
-                        data.fShortPts[2] = seg[2].asSkPoint();
-                        PathOpsSegmentTester::ConstructQuad(&segment[index3], data.fShortPts);
+                        contour.addQuad(temp, &allocator);
                         } break;
                     case 4: {
-                        SkDCubic seg = SkDCubic::SubDivide(temp, data.fTStart, data.fTEnd);
-                        data.fShortPts[0] = seg[0].asSkPoint();
-                        data.fShortPts[1] = seg[1].asSkPoint();
-                        data.fShortPts[2] = seg[2].asSkPoint();
-                        data.fShortPts[3] = seg[3].asSkPoint();
-                        PathOpsSegmentTester::ConstructCubic(&segment[index3], data.fShortPts);
+                        contour.addCubic(temp, &allocator);
                         } break;
                 }
             }
-            SkOpAngle& angle1 = *const_cast<SkOpAngle*>(segment[0].debugLastAngle());
-            SkOpAngle& angle2 = *const_cast<SkOpAngle*>(segment[1].debugLastAngle());
-            SkOpAngle& angle3 = *const_cast<SkOpAngle*>(segment[2].debugLastAngle());
+            SkOpSegment* seg1 = contour.first();
+            seg1->debugAddAngle(dataArray[index2 + 0].fTStart, dataArray[index2 + 0].fTEnd, &allocator);
+            SkOpSegment* seg2 = seg1->next();
+            seg2->debugAddAngle(dataArray[index2 + 1].fTStart, dataArray[index2 + 1].fTEnd, &allocator);
+            SkOpSegment* seg3 = seg2->next();
+            seg3->debugAddAngle(dataArray[index2 + 2].fTStart, dataArray[index2 + 2].fTEnd, &allocator);
+            SkOpAngle& angle1 = *seg1->debugLastAngle();
+            SkOpAngle& angle2 = *seg2->debugLastAngle();
+            SkOpAngle& angle3 = *seg3->debugLastAngle();
             PathOpsAngleTester::SetNext(angle1, angle3);
        // These data sets are seeded when the set itself fails, so likely the dataset does not
        // match the expected result. The tests above return 1 when first added, but
        // return 0 after the bug is fixed.
             SkDEBUGCODE(int result =) PathOpsAngleTester::After(angle2, angle1);
             SkASSERT(result == 0 || result == 1);
         }
     }
 }
 
-void SkOpSegment::debugConstruct() {
-    addStartSpan(1);
-    addEndSpan(1);
-    debugAddAngle(0, 1);
+void SkOpSegment::debugAddAngle(double startT, double endT, SkChunkAlloc* allocator) {
+    SkOpPtT* startPtT = startT == 0 ? fHead.ptT() : startT == 1 ? fTail.ptT()
+            : this->addT(startT, kNoAlias, allocator);
+    SkOpPtT* endPtT = endT == 0 ? fHead.ptT() : endT == 1 ? fTail.ptT()
+            : this->addT(endT, kNoAlias, allocator);
+    SkOpAngle* angle = SkOpTAllocator<SkOpAngle>::Allocate(allocator);
+    SkOpSpanBase* startSpan = &fHead;
+    while (startSpan->ptT() != startPtT) {
+        startSpan = startSpan->upCast()->next();
+    }
+    SkOpSpanBase* endSpan = &fHead;
+    while (endSpan->ptT() != endPtT) {
+        endSpan = endSpan->upCast()->next();
+    }
+    angle->set(startSpan, endSpan);
+    if (startT < endT) {
+        startSpan->upCast()->setToAngle(angle);
+        endSpan->setFromAngle(angle);
+    } else {
+        endSpan->upCast()->setToAngle(angle);
+        startSpan->setFromAngle(angle);
+    }
 }
-
-void SkOpSegment::debugAddAngle(int start, int end) {
-    SkASSERT(start != end);
-    SkOpAngle& angle = fAngles.push_back();
-    angle.set(this, start, end);
-}
-
-void SkOpSegment::debugConstructCubic(SkPoint shortQuad[4]) {
-    addCubic(shortQuad, false, false);
-    addT(NULL, shortQuad[0], 0);
-    addT(NULL, shortQuad[3], 1);
-    debugConstruct();
-}
-
-void SkOpSegment::debugConstructLine(SkPoint shortQuad[2]) {
-    addLine(shortQuad, false, false);
-    addT(NULL, shortQuad[0], 0);
-    addT(NULL, shortQuad[1], 1);
-    debugConstruct();
-}
-
-void SkOpSegment::debugConstructQuad(SkPoint shortQuad[3]) {
-    addQuad(shortQuad, false, false);
-    addT(NULL, shortQuad[0], 0);
-    addT(NULL, shortQuad[2], 1);
-    debugConstruct();
-}