xref: /external/skia/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 (AlmostLessUlps(test->bounds().fBottom, next->bounds().fTop)) {
            return false;
        }
        // OPTIMIZATION: outset contour bounds a smidgen instead?
        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 = 0;
            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, wn, wt, 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, wn, wt, 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) {
                    if (wt.addCoincident(wn, ts, swap)) {
                        continue;
                    }
                    ts.cleanUpCoincidence();  // prefer (t == 0 or t == 1)
                    pts = 1;
                } else if (wn.segmentType() >= SkIntersectionHelper::kQuad_Segment
                        && wt.segmentType() >= SkIntersectionHelper::kQuad_Segment
                        && ts.isCoincident(0)) {
                    SkASSERT(ts.coincidentUsed() == 2);
                    if (wt.addCoincident(wn, ts, swap)) {
                        continue;
                    }
                    ts.cleanUpCoincidence();  // prefer (t == 0 or t == 1)
                    pts = 1;
                }
            }
            if (pts >= 2) {
                for (int pt = 0; pt < pts - 1; ++pt) {
                    const SkDPoint& point = ts.pt(pt);
                    const SkDPoint& next = ts.pt(pt + 1);
                    if (wt.isPartial(ts[swap][pt], ts[swap][pt + 1], point, next)
                            && wn.isPartial(ts[!swap][pt], ts[!swap][pt + 1], point, next)) {
                        if (!wt.addPartialCoincident(wn, ts, pt, swap)) {
                            // remove extra point if two map to same float values
                            ts.cleanUpCoincidence();  // prefer (t == 0 or t == 1)
                            pts = 1;
                        }
                    }
                }
            }
            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();
                wt.alignTPt(wn, swap, pt, &ts, &point);
                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(point, ts[0][0]);
        int nextTAt = wt.addSelfT(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(SkTArray<SkOpContour*, true>* contourList, int total) {
    int contourCount = (*contourList).count();
    for (int cIndex = 0; cIndex < contourCount; ++cIndex) {
        SkOpContour* contour = (*contourList)[cIndex];
        contour->resolveNearCoincidence();
    }
    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();
    }
    for (int cIndex = 0; cIndex < contourCount; ++cIndex) {
        SkOpContour* contour = (*contourList)[cIndex];
        contour->calcPartialCoincidentWinding();
    }
}