diff -r 000000000000 -r 6474c204b198 gfx/skia/trunk/src/pathops/SkAddIntersections.cpp --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/gfx/skia/trunk/src/pathops/SkAddIntersections.cpp Wed Dec 31 06:09:35 2014 +0100 @@ -0,0 +1,450 @@ +/* + * 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(); + 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(SkTArray* contourList, int total) { + int contourCount = (*contourList).count(); + 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(); + } +}