Add implementation of path ops

src/pathops/SkAddIntersections.cpp

+/*
+ * Copyright 2012 Google Inc.
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+#include "SkAddIntersections.h"
+#include "SkPathOpsBounds.h"
+
+#if DEBUG_ADD_INTERSECTING_TS
+
+static void debugShowLineIntersection(int pts, const SkIntersectionHelper& wt,
+                                      const SkIntersectionHelper& wn, const SkIntersections& i) {
+    SkASSERT(i.used() == pts);
+    if (!pts) {
+        SkDebugf("%s no intersect " LINE_DEBUG_STR " " LINE_DEBUG_STR "\n",
+                __FUNCTION__, LINE_DEBUG_DATA(wt.pts()), LINE_DEBUG_DATA(wn.pts()));
+        return;
+    }
+    SkDebugf("%s " T_DEBUG_STR(wtTs, 0) " " LINE_DEBUG_STR " " PT_DEBUG_STR, __FUNCTION__,
+            i[0][0], LINE_DEBUG_DATA(wt.pts()), PT_DEBUG_DATA(i, 0));
+    if (pts == 2) {
+        SkDebugf(" " T_DEBUG_STR(wtTs, 1) " " PT_DEBUG_STR, i[0][1], PT_DEBUG_DATA(i, 1));
+    }
+    SkDebugf(" wnTs[0]=%g " LINE_DEBUG_STR, i[1][0], LINE_DEBUG_DATA(wn.pts()));
+    if (pts == 2) {
+        SkDebugf(" " T_DEBUG_STR(wnTs, 1), i[1][1]);
+    }
+    SkDebugf("\n");
+}
+
+static void debugShowQuadLineIntersection(int pts, const SkIntersectionHelper& wt,
+                                          const SkIntersectionHelper& wn,
+                                          const SkIntersections& i) {
+    SkASSERT(i.used() == pts);
+    if (!pts) {
+        SkDebugf("%s no intersect " QUAD_DEBUG_STR " " LINE_DEBUG_STR "\n",
+                __FUNCTION__, QUAD_DEBUG_DATA(wt.pts()), LINE_DEBUG_DATA(wn.pts()));
+        return;
+    }
+    SkDebugf("%s " T_DEBUG_STR(wtTs, 0) " " QUAD_DEBUG_STR " " PT_DEBUG_STR, __FUNCTION__,
+            i[0][0], QUAD_DEBUG_DATA(wt.pts()), PT_DEBUG_DATA(i, 0));
+    for (int n = 1; n < pts; ++n) {
+        SkDebugf(" " TX_DEBUG_STR(wtTs) " " PT_DEBUG_STR, n, i[0][n], PT_DEBUG_DATA(i, n));
+    }
+    SkDebugf(" wnTs[0]=%g " LINE_DEBUG_STR, i[1][0], LINE_DEBUG_DATA(wn.pts()));
+    for (int n = 1; n < pts; ++n) {
+        SkDebugf(" " TX_DEBUG_STR(wnTs), n, i[1][n]);
+    }
+    SkDebugf("\n");
+}
+
+static void debugShowQuadIntersection(int pts, const SkIntersectionHelper& wt,
+        const SkIntersectionHelper& wn, const SkIntersections& i) {
+    SkASSERT(i.used() == pts);
+    if (!pts) {
+        SkDebugf("%s no intersect " QUAD_DEBUG_STR " " QUAD_DEBUG_STR "\n",
+                __FUNCTION__, QUAD_DEBUG_DATA(wt.pts()), QUAD_DEBUG_DATA(wn.pts()));
+        return;
+    }
+    SkDebugf("%s " T_DEBUG_STR(wtTs, 0) " " QUAD_DEBUG_STR " " PT_DEBUG_STR, __FUNCTION__,
+            i[0][0], QUAD_DEBUG_DATA(wt.pts()), PT_DEBUG_DATA(i, 0));
+    for (int n = 1; n < pts; ++n) {
+        SkDebugf(" " TX_DEBUG_STR(wtTs) " " PT_DEBUG_STR, n, i[0][n], PT_DEBUG_DATA(i, n));
+    }
+    SkDebugf(" wnTs[0]=%g " QUAD_DEBUG_STR, i[1][0], QUAD_DEBUG_DATA(wn.pts()));
+    for (int n = 1; n < pts; ++n) {
+        SkDebugf(" " TX_DEBUG_STR(wnTs), n, i[1][n]);
+    }
+    SkDebugf("\n");
+}
+
+static void debugShowCubicLineIntersection(int pts, const SkIntersectionHelper& wt,
+        const SkIntersectionHelper& wn, const SkIntersections& i) {
+    SkASSERT(i.used() == pts);
+    if (!pts) {
+        SkDebugf("%s no intersect " CUBIC_DEBUG_STR " " LINE_DEBUG_STR "\n",
+                __FUNCTION__, CUBIC_DEBUG_DATA(wt.pts()), LINE_DEBUG_DATA(wn.pts()));
+        return;
+    }
+    SkDebugf("%s " T_DEBUG_STR(wtTs, 0) " " CUBIC_DEBUG_STR " " PT_DEBUG_STR, __FUNCTION__,
+            i[0][0], CUBIC_DEBUG_DATA(wt.pts()), PT_DEBUG_DATA(i, 0));
+    for (int n = 1; n < pts; ++n) {
+        SkDebugf(" " TX_DEBUG_STR(wtTs) " " PT_DEBUG_STR, n, i[0][n], PT_DEBUG_DATA(i, n));
+    }
+    SkDebugf(" wnTs[0]=%g " LINE_DEBUG_STR, i[1][0], LINE_DEBUG_DATA(wn.pts()));
+    for (int n = 1; n < pts; ++n) {
+        SkDebugf(" " TX_DEBUG_STR(wnTs), n, i[1][n]);
+    }
+    SkDebugf("\n");
+}
+
+static void debugShowCubicQuadIntersection(int pts, const SkIntersectionHelper& wt,
+        const SkIntersectionHelper& wn, const SkIntersections& i) {
+    SkASSERT(i.used() == pts);
+    if (!pts) {
+        SkDebugf("%s no intersect " CUBIC_DEBUG_STR " " QUAD_DEBUG_STR "\n",
+                __FUNCTION__, CUBIC_DEBUG_DATA(wt.pts()), QUAD_DEBUG_DATA(wn.pts()));
+        return;
+    }
+    SkDebugf("%s " T_DEBUG_STR(wtTs, 0) " " CUBIC_DEBUG_STR " " PT_DEBUG_STR, __FUNCTION__,
+            i[0][0], CUBIC_DEBUG_DATA(wt.pts()), PT_DEBUG_DATA(i, 0));
+    for (int n = 1; n < pts; ++n) {
+        SkDebugf(" " TX_DEBUG_STR(wtTs) " " PT_DEBUG_STR, n, i[0][n], PT_DEBUG_DATA(i, n));
+    }
+    SkDebugf(" wnTs[0]=%g " QUAD_DEBUG_STR, i[1][0], QUAD_DEBUG_DATA(wn.pts()));
+    for (int n = 1; n < pts; ++n) {
+        SkDebugf(" " TX_DEBUG_STR(wnTs), n, i[1][n]);
+    }
+    SkDebugf("\n");
+}
+
+static void debugShowCubicIntersection(int pts, const SkIntersectionHelper& wt,
+        const SkIntersectionHelper& wn, const SkIntersections& i) {
+    SkASSERT(i.used() == pts);
+    if (!pts) {
+        SkDebugf("%s no intersect " CUBIC_DEBUG_STR " " CUBIC_DEBUG_STR "\n",
+                __FUNCTION__, CUBIC_DEBUG_DATA(wt.pts()), CUBIC_DEBUG_DATA(wn.pts()));
+        return;
+    }
+    SkDebugf("%s " T_DEBUG_STR(wtTs, 0) " " CUBIC_DEBUG_STR " " PT_DEBUG_STR, __FUNCTION__,
+            i[0][0], CUBIC_DEBUG_DATA(wt.pts()), PT_DEBUG_DATA(i, 0));
+    for (int n = 1; n < pts; ++n) {
+        SkDebugf(" " TX_DEBUG_STR(wtTs) " " PT_DEBUG_STR, n, i[0][n], PT_DEBUG_DATA(i, n));
+    }
+    SkDebugf(" wnTs[0]=%g " CUBIC_DEBUG_STR, i[1][0], CUBIC_DEBUG_DATA(wn.pts()));
+    for (int n = 1; n < pts; ++n) {
+        SkDebugf(" " TX_DEBUG_STR(wnTs), n, i[1][n]);
+    }
+    SkDebugf("\n");
+}
+
+static void debugShowCubicIntersection(int pts, const SkIntersectionHelper& wt, const SkIntersections& i) {
+    SkASSERT(i.used() == pts);
+    if (!pts) {
+        SkDebugf("%s no self intersect " CUBIC_DEBUG_STR "\n", __FUNCTION__,
+                CUBIC_DEBUG_DATA(wt.pts()));
+        return;
+    }
+    SkDebugf("%s " T_DEBUG_STR(wtTs, 0) " " CUBIC_DEBUG_STR " " PT_DEBUG_STR, __FUNCTION__,
+            i[0][0], CUBIC_DEBUG_DATA(wt.pts()), PT_DEBUG_DATA(i, 0));
+    SkDebugf(" " T_DEBUG_STR(wtTs, 1), i[1][0]);
+    SkDebugf("\n");
+}
+
+#else
+static void debugShowLineIntersection(int , const SkIntersectionHelper& , const SkIntersectionHelper& , const SkIntersections& ) {
+}
+
+static void debugShowQuadLineIntersection(int , const SkIntersectionHelper& , const SkIntersectionHelper& , const SkIntersections& ) {
+}
+
+static void debugShowQuadIntersection(int , const SkIntersectionHelper& , const SkIntersectionHelper& , const SkIntersections& ) {
+}
+
+static void debugShowCubicLineIntersection(int , const SkIntersectionHelper& , const SkIntersectionHelper& ,
+        const SkIntersections& ) {
+}
+
+static void debugShowCubicQuadIntersection(int , const SkIntersectionHelper& , const SkIntersectionHelper& ,
+        const SkIntersections& ) {
+}
+
+static void debugShowCubicIntersection(int , const SkIntersectionHelper& , const SkIntersectionHelper& , const SkIntersections& ) {
+}
+
+static void debugShowCubicIntersection(int , const SkIntersectionHelper& , const SkIntersections& ) {
+}
+#endif
+
+bool AddIntersectTs(SkOpContour* test, SkOpContour* next) {
+
+    if (test != next) {
+        if (test->bounds().fBottom < next->bounds().fTop) {
+            return false;
+        }
+        if (!SkPathOpsBounds::Intersects(test->bounds(), next->bounds())) {
+            return true;
+        }
+    }
+    SkIntersectionHelper wt;
+    wt.init(test);
+    bool foundCommonContour = test == next;
+    do {
+        SkIntersectionHelper wn;
+        wn.init(next);
+        if (test == next && !wn.startAfter(wt)) {
+            continue;
+        }
+        do {
+            if (!SkPathOpsBounds::Intersects(wt.bounds(), wn.bounds())) {
+                continue;
+            }
+            int pts;
+            SkIntersections ts;
+            bool swap = false;
+            switch (wt.segmentType()) {
+                case SkIntersectionHelper::kHorizontalLine_Segment:
+                    swap = true;
+                    switch (wn.segmentType()) {
+                        case SkIntersectionHelper::kHorizontalLine_Segment:
+                        case SkIntersectionHelper::kVerticalLine_Segment:
+                        case SkIntersectionHelper::kLine_Segment: {
+                            pts = ts.lineHorizontal(wn.pts(), wt.left(),
+                                    wt.right(), wt.y(), wt.xFlipped());
+                            debugShowLineIntersection(pts, wt, wn, ts);
+                            break;
+                        }
+                        case SkIntersectionHelper::kQuad_Segment: {
+                            pts = ts.quadHorizontal(wn.pts(), wt.left(),
+                                    wt.right(), wt.y(), wt.xFlipped());
+                            debugShowQuadLineIntersection(pts, wn, wt, ts);
+                            break;
+                        }
+                        case SkIntersectionHelper::kCubic_Segment: {
+                            pts = ts.cubicHorizontal(wn.pts(), wt.left(),
+                                    wt.right(), wt.y(), wt.xFlipped());
+                            debugShowCubicLineIntersection(pts, wn, wt, ts);
+                            break;
+                        }
+                        default:
+                            SkASSERT(0);
+                    }
+                    break;
+                case SkIntersectionHelper::kVerticalLine_Segment:
+                    swap = true;
+                    switch (wn.segmentType()) {
+                        case SkIntersectionHelper::kHorizontalLine_Segment:
+                        case SkIntersectionHelper::kVerticalLine_Segment:
+                        case SkIntersectionHelper::kLine_Segment: {
+                            pts = ts.lineVertical(wn.pts(), wt.top(),
+                                    wt.bottom(), wt.x(), wt.yFlipped());
+                            debugShowLineIntersection(pts, wt, wn, ts);
+                            break;
+                        }
+                        case SkIntersectionHelper::kQuad_Segment: {
+                            pts = ts.quadVertical(wn.pts(), wt.top(),
+                                    wt.bottom(), wt.x(), wt.yFlipped());
+                            debugShowQuadLineIntersection(pts, wn, wt, ts);
+                            break;
+                        }
+                        case SkIntersectionHelper::kCubic_Segment: {
+                            pts = ts.cubicVertical(wn.pts(), wt.top(),
+                                    wt.bottom(), wt.x(), wt.yFlipped());
+                            debugShowCubicLineIntersection(pts, wn, wt, ts);
+                            break;
+                        }
+                        default:
+                            SkASSERT(0);
+                    }
+                    break;
+                case SkIntersectionHelper::kLine_Segment:
+                    switch (wn.segmentType()) {
+                        case SkIntersectionHelper::kHorizontalLine_Segment:
+                            pts = ts.lineHorizontal(wt.pts(), wn.left(),
+                                    wn.right(), wn.y(), wn.xFlipped());
+                            debugShowLineIntersection(pts, wt, wn, ts);
+                            break;
+                        case SkIntersectionHelper::kVerticalLine_Segment:
+                            pts = ts.lineVertical(wt.pts(), wn.top(),
+                                    wn.bottom(), wn.x(), wn.yFlipped());
+                            debugShowLineIntersection(pts, wt, wn, ts);
+                            break;
+                        case SkIntersectionHelper::kLine_Segment: {
+                            pts = ts.lineLine(wt.pts(), wn.pts());
+                            debugShowLineIntersection(pts, wt, wn, ts);
+                            break;
+                        }
+                        case SkIntersectionHelper::kQuad_Segment: {
+                            swap = true;
+                            pts = ts.quadLine(wn.pts(), wt.pts());
+                            debugShowQuadLineIntersection(pts, wn, wt, ts);
+                            break;
+                        }
+                        case SkIntersectionHelper::kCubic_Segment: {
+                            swap = true;
+                            pts = ts.cubicLine(wn.pts(), wt.pts());
+                            debugShowCubicLineIntersection(pts, wn, wt,  ts);
+                            break;
+                        }
+                        default:
+                            SkASSERT(0);
+                    }
+                    break;
+                case SkIntersectionHelper::kQuad_Segment:
+                    switch (wn.segmentType()) {
+                        case SkIntersectionHelper::kHorizontalLine_Segment:
+                            pts = ts.quadHorizontal(wt.pts(), wn.left(),
+                                    wn.right(), wn.y(), wn.xFlipped());
+                            debugShowQuadLineIntersection(pts, wt, wn, ts);
+                            break;
+                        case SkIntersectionHelper::kVerticalLine_Segment:
+                            pts = ts.quadVertical(wt.pts(), wn.top(),
+                                    wn.bottom(), wn.x(), wn.yFlipped());
+                            debugShowQuadLineIntersection(pts, wt, wn, ts);
+                            break;
+                        case SkIntersectionHelper::kLine_Segment: {
+                            pts = ts.quadLine(wt.pts(), wn.pts());
+                            debugShowQuadLineIntersection(pts, wt, wn, ts);
+                            break;
+                        }
+                        case SkIntersectionHelper::kQuad_Segment: {
+                            pts = ts.quadQuad(wt.pts(), wn.pts());
+                            debugShowQuadIntersection(pts, wt, wn, ts);
+                            break;
+                        }
+                        case SkIntersectionHelper::kCubic_Segment: {
+                            swap = true;
+                            pts = ts.cubicQuad(wn.pts(), wt.pts());
+                            debugShowCubicQuadIntersection(pts, wn, wt, ts);
+                            break;
+                        }
+                        default:
+                            SkASSERT(0);
+                    }
+                    break;
+                case SkIntersectionHelper::kCubic_Segment:
+                    switch (wn.segmentType()) {
+                        case SkIntersectionHelper::kHorizontalLine_Segment:
+                            pts = ts.cubicHorizontal(wt.pts(), wn.left(),
+                                    wn.right(), wn.y(), wn.xFlipped());
+                            debugShowCubicLineIntersection(pts, wt, wn, ts);
+                            break;
+                        case SkIntersectionHelper::kVerticalLine_Segment:
+                            pts = ts.cubicVertical(wt.pts(), wn.top(),
+                                    wn.bottom(), wn.x(), wn.yFlipped());
+                            debugShowCubicLineIntersection(pts, wt, wn, ts);
+                            break;
+                        case SkIntersectionHelper::kLine_Segment: {
+                            pts = ts.cubicLine(wt.pts(), wn.pts());
+                            debugShowCubicLineIntersection(pts, wt, wn, ts);
+                            break;
+                        }
+                        case SkIntersectionHelper::kQuad_Segment: {
+                            pts = ts.cubicQuad(wt.pts(), wn.pts());
+                            debugShowCubicQuadIntersection(pts, wt, wn, ts);
+                            break;
+                        }
+                        case SkIntersectionHelper::kCubic_Segment: {
+                            pts = ts.cubicCubic(wt.pts(), wn.pts());
+                            debugShowCubicIntersection(pts, wt, wn, ts);
+                            break;
+                        }
+                        default:
+                            SkASSERT(0);
+                    }
+                    break;
+                default:
+                    SkASSERT(0);
+            }
+            if (!foundCommonContour && pts > 0) {
+                test->addCross(next);
+                next->addCross(test);
+                foundCommonContour = true;
+            }
+            // in addition to recording T values, record matching segment
+            if (pts == 2) {
+                if (wn.segmentType() <= SkIntersectionHelper::kLine_Segment
+                        && wt.segmentType() <= SkIntersectionHelper::kLine_Segment) {
+                    wt.addCoincident(wn, ts, swap);
+                    continue;
+                }
+                if (wn.segmentType() >= SkIntersectionHelper::kQuad_Segment
+                        && wt.segmentType() >= SkIntersectionHelper::kQuad_Segment
+                        && ts.isCoincident(0)) {
+                    SkASSERT(ts.coincidentUsed() == 2);
+                    wt.addCoincident(wn, ts, swap);
+                    continue;
+                }
+
+            }
+            for (int pt = 0; pt < pts; ++pt) {
+                SkASSERT(ts[0][pt] >= 0 && ts[0][pt] <= 1);
+                SkASSERT(ts[1][pt] >= 0 && ts[1][pt] <= 1);
+                SkPoint point = ts.pt(pt).asSkPoint();
+                int testTAt = wt.addT(wn, point, ts[swap][pt]);
+                int nextTAt = wn.addT(wt, point, ts[!swap][pt]);
+                wt.addOtherT(testTAt, ts[!swap][pt], nextTAt);
+                wn.addOtherT(nextTAt, ts[swap][pt], testTAt);
+            }
+        } while (wn.advance());
+    } while (wt.advance());
+    return true;
+}
+
+void AddSelfIntersectTs(SkOpContour* test) {
+    SkIntersectionHelper wt;
+    wt.init(test);
+    do {
+        if (wt.segmentType() != SkIntersectionHelper::kCubic_Segment) {
+            continue;
+        }
+        SkIntersections ts;
+        int pts = ts.cubic(wt.pts());
+        debugShowCubicIntersection(pts, wt, ts);
+        if (!pts) {
+            continue;
+        }
+        SkASSERT(pts == 1);
+        SkASSERT(ts[0][0] >= 0 && ts[0][0] <= 1);
+        SkASSERT(ts[1][0] >= 0 && ts[1][0] <= 1);
+        SkPoint point = ts.pt(0).asSkPoint();
+        int testTAt = wt.addSelfT(wt, point, ts[0][0]);
+        int nextTAt = wt.addT(wt, point, ts[1][0]);
+        wt.addOtherT(testTAt, ts[1][0], nextTAt);
+        wt.addOtherT(nextTAt, ts[0][0], testTAt);
+    } while (wt.advance());
+}
+
+// resolve any coincident pairs found while intersecting, and
+// see if coincidence is formed by clipping non-concident segments
+void CoincidenceCheck(SkTDArray<SkOpContour*>& contourList, int total) {
+    int contourCount = contourList.count();
+#if ONE_PASS_COINCIDENCE_CHECK
+    for (int cIndex = 0; cIndex < contourCount; ++cIndex) {
+        SkOpContour* contour = contourList[cIndex];
+        contour->resolveCoincidence(contourList);
+    }
+#else
+    for (int cIndex = 0; cIndex < contourCount; ++cIndex) {
+        SkOpContour* contour = contourList[cIndex];
+        contour->addCoincidentPoints();
+    }
+    for (int cIndex = 0; cIndex < contourCount; ++cIndex) {
+        SkOpContour* contour = contourList[cIndex];
+        contour->calcCoincidentWinding();
+    }
+#endif
+    for (int cIndex = 0; cIndex < contourCount; ++cIndex) {
+        SkOpContour* contour = contourList[cIndex];
+        contour->findTooCloseToCall();
+    }
+}