diff options
Diffstat (limited to 'src/pathops')
25 files changed, 472 insertions, 106 deletions
diff --git a/src/pathops/SkAddIntersections.cpp b/src/pathops/SkAddIntersections.cpp index 5fa80ec506..7d5fc0d4a6 100644 --- a/src/pathops/SkAddIntersections.cpp +++ b/src/pathops/SkAddIntersections.cpp @@ -383,8 +383,8 @@ bool AddIntersectTs(SkOpContour* test, SkOpContour* next) { for (int pt = 0; pt < pts - 1; ++pt) { const SkDPoint& point = ts.pt(pt); const SkDPoint& next = ts.pt(pt + 1); - if (wt.isNear(ts[swap][pt], ts[swap][pt + 1], point, next) - && wn.isNear(ts[!swap][pt], ts[!swap][pt + 1], point, next)) { + 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) diff --git a/src/pathops/SkDCubicIntersection.cpp b/src/pathops/SkDCubicIntersection.cpp index ce2344841b..27b16341a8 100644 --- a/src/pathops/SkDCubicIntersection.cpp +++ b/src/pathops/SkDCubicIntersection.cpp @@ -292,6 +292,7 @@ bool SkIntersections::cubicExactEnd(const SkDCubic& cubic1, bool start, const Sk tmpLine[1].fX += cubic2[2 - start].fY - cubic2[t1Index].fY; tmpLine[1].fY -= cubic2[2 - start].fX - cubic2[t1Index].fX; SkIntersections impTs; + impTs.allowNear(false); impTs.intersectRay(cubic1, tmpLine); for (int index = 0; index < impTs.used(); ++index) { SkDPoint realPt = impTs.pt(index); @@ -446,6 +447,7 @@ int SkIntersections::intersect(const SkDCubic& c1, const SkDCubic& c2) { return fUsed; } } else { + // OPTIMIZATION: set exact end bits here to avoid cubic exact end later for (int i1 = 0; i1 < 4; i1 += 3) { for (int i2 = 0; i2 < 4; i2 += 3) { if (c1[i1].approximatelyEqual(c2[i2])) { @@ -483,21 +485,22 @@ int SkIntersections::intersect(const SkDCubic& c1, const SkDCubic& c2) { return fUsed; } // FIXME: pass in cached bounds from caller - SkDRect c1Bounds, c2Bounds; - c1Bounds.setBounds(c1); // OPTIMIZE use setRawBounds ? + SkDRect c2Bounds; c2Bounds.setBounds(c2); - if (!(exactEndBits & 1)) { + if (!(exactEndBits & 4)) { cubicNearEnd(c1, false, c2, c2Bounds); } - if (!(exactEndBits & 2)) { + if (!(exactEndBits & 8)) { cubicNearEnd(c1, true, c2, c2Bounds); } if (!selfIntersect) { + SkDRect c1Bounds; + c1Bounds.setBounds(c1); // OPTIMIZE use setRawBounds ? swap(); - if (!(exactEndBits & 4)) { + if (!(exactEndBits & 1)) { cubicNearEnd(c2, false, c1, c1Bounds); } - if (!(exactEndBits & 8)) { + if (!(exactEndBits & 2)) { cubicNearEnd(c2, true, c1, c1Bounds); } swap(); @@ -506,7 +509,61 @@ int SkIntersections::intersect(const SkDCubic& c1, const SkDCubic& c2) { SkASSERT(!selfIntersect); return fUsed; } - ::intersect(c1, 0, 1, c2, 0, 1, 1, *this); + SkIntersections i; + i.fAllowNear = false; + i.fMax = 9; + ::intersect(c1, 0, 1, c2, 0, 1, 1, i); + int compCount = i.used(); + if (compCount) { + int exactCount = used(); + if (exactCount == 0) { + set(i); + } else { + // at least one is exact or near, and at least one was computed. Eliminate duplicates + for (int exIdx = 0; exIdx < exactCount; ++exIdx) { + for (int cpIdx = 0; cpIdx < compCount; ) { + if (fT[0][0] == i[0][0] && fT[1][0] == i[1][0]) { + i.removeOne(cpIdx); + --compCount; + continue; + } + double tAvg = (fT[0][exIdx] + i[0][cpIdx]) / 2; + SkDPoint pt = c1.ptAtT(tAvg); + if (!pt.approximatelyEqual(fPt[exIdx])) { + ++cpIdx; + continue; + } + tAvg = (fT[1][exIdx] + i[1][cpIdx]) / 2; + pt = c2.ptAtT(tAvg); + if (!pt.approximatelyEqual(fPt[exIdx])) { + ++cpIdx; + continue; + } + i.removeOne(cpIdx); + --compCount; + } + } + // if mid t evaluates to nearly the same point, skip the t + for (int cpIdx = 0; cpIdx < compCount - 1; ) { + double tAvg = (fT[0][cpIdx] + i[0][cpIdx + 1]) / 2; + SkDPoint pt = c1.ptAtT(tAvg); + if (!pt.approximatelyEqual(fPt[cpIdx])) { + ++cpIdx; + continue; + } + tAvg = (fT[1][cpIdx] + i[1][cpIdx + 1]) / 2; + pt = c2.ptAtT(tAvg); + if (!pt.approximatelyEqual(fPt[cpIdx])) { + ++cpIdx; + continue; + } + i.removeOne(cpIdx); + --compCount; + } + // in addition to adding below missing function, think about how to say + append(i); + } + } // If an end point and a second point very close to the end is returned, the second // point may have been detected because the approximate quads // intersected at the end and close to it. Verify that the second point is valid. diff --git a/src/pathops/SkDCubicLineIntersection.cpp b/src/pathops/SkDCubicLineIntersection.cpp index e9997e45dd..abbc4e32b2 100644 --- a/src/pathops/SkDCubicLineIntersection.cpp +++ b/src/pathops/SkDCubicLineIntersection.cpp @@ -215,6 +215,8 @@ public: } } + /* Note that this does not look for endpoints of the line that are near the cubic. + These points are found later when check ends looks for missing points */ void addNearEndPoints() { for (int cIndex = 0; cIndex < 4; cIndex += 3) { double cubicT = (double) (cIndex >> 1); diff --git a/src/pathops/SkDLineIntersection.cpp b/src/pathops/SkDLineIntersection.cpp index fca0a04d1f..33c8480cd5 100644 --- a/src/pathops/SkDLineIntersection.cpp +++ b/src/pathops/SkDLineIntersection.cpp @@ -181,7 +181,7 @@ static int horizontal_coincident(const SkDLine& line, double y) { } static double horizontal_intercept(const SkDLine& line, double y) { - return (y - line[0].fY) / (line[1].fY - line[0].fY); + return SkPinT((y - line[0].fY) / (line[1].fY - line[0].fY)); } int SkIntersections::horizontal(const SkDLine& line, double y) { @@ -267,7 +267,7 @@ static int vertical_coincident(const SkDLine& line, double x) { } static double vertical_intercept(const SkDLine& line, double x) { - return (x - line[0].fX) / (line[1].fX - line[0].fX); + return SkPinT((x - line[0].fX) / (line[1].fX - line[0].fX)); } int SkIntersections::vertical(const SkDLine& line, double x) { diff --git a/src/pathops/SkDQuadIntersection.cpp b/src/pathops/SkDQuadIntersection.cpp index 6e5f3e6012..48725089da 100644 --- a/src/pathops/SkDQuadIntersection.cpp +++ b/src/pathops/SkDQuadIntersection.cpp @@ -301,7 +301,7 @@ static bool binary_search(const SkDQuad& quad1, const SkDQuad& quad2, double* t1 *pt = t1[1]; #if ONE_OFF_DEBUG SkDebugf("%s t1=%1.9g t2=%1.9g (%1.9g,%1.9g) == (%1.9g,%1.9g)\n", __FUNCTION__, - t1Seed, t2Seed, t1[1].fX, t1[1].fY, t1[2].fX, t1[2].fY); + t1Seed, t2Seed, t1[1].fX, t1[1].fY, t2[1].fX, t2[1].fY); #endif return true; } @@ -490,15 +490,11 @@ int SkIntersections::intersect(const SkDQuad& q1, const SkDQuad& q2) { pts2[index] = q2.ptAtT(roots2Copy[index]); } if (r1Count == r2Count && r1Count <= 1) { - if (r1Count == 1) { + if (r1Count == 1 && used() == 0) { if (pts1[0].approximatelyEqual(pts2[0])) { insert(roots1Copy[0], roots2Copy[0], pts1[0]); } else if (pts1[0].moreRoughlyEqual(pts2[0])) { // experiment: try to find intersection by chasing t - rootCount = findRoots(i2, q1, roots1, useCubic, flip1, 0); - (void) addValidRoots(roots1, rootCount, roots1Copy); - rootCount2 = findRoots(i1, q2, roots2, useCubic, flip2, 0); - (void) addValidRoots(roots2, rootCount2, roots2Copy); if (binary_search(q1, q2, roots1Copy, roots2Copy, pts1)) { insert(roots1Copy[0], roots2Copy[0], pts1[0]); } diff --git a/src/pathops/SkDQuadLineIntersection.cpp b/src/pathops/SkDQuadLineIntersection.cpp index 14d7d9cea0..8fce7a089f 100644 --- a/src/pathops/SkDQuadLineIntersection.cpp +++ b/src/pathops/SkDQuadLineIntersection.cpp @@ -141,14 +141,18 @@ public: if (fAllowNear) { addNearEndPoints(); } - double rootVals[2]; - int roots = intersectRay(rootVals); - for (int index = 0; index < roots; ++index) { - double quadT = rootVals[index]; - double lineT = findLineT(quadT); - SkDPoint pt; - if (pinTs(&quadT, &lineT, &pt, kPointUninitialized)) { - fIntersections->insert(quadT, lineT, pt); + if (fIntersections->used() == 2) { + // FIXME : need sharable code that turns spans into coincident if middle point is on + } else { + double rootVals[2]; + int roots = intersectRay(rootVals); + for (int index = 0; index < roots; ++index) { + double quadT = rootVals[index]; + double lineT = findLineT(quadT); + SkDPoint pt; + if (pinTs(&quadT, &lineT, &pt, kPointUninitialized)) { + fIntersections->insert(quadT, lineT, pt); + } } } return fIntersections->used(); diff --git a/src/pathops/SkIntersectionHelper.h b/src/pathops/SkIntersectionHelper.h index 1a4b1f0441..f5eeaf8813 100644 --- a/src/pathops/SkIntersectionHelper.h +++ b/src/pathops/SkIntersectionHelper.h @@ -7,6 +7,10 @@ #include "SkOpContour.h" #include "SkPath.h" +#if SK_DEBUG +#include "SkPathOpsPoint.h" +#endif + class SkIntersectionHelper { public: enum SegmentType { @@ -81,6 +85,14 @@ public: return midPtByT.approximatelyEqual(midPtByAvg); } + bool isPartial(double t1, double t2, const SkDPoint& pt1, const SkDPoint& pt2) const { + const SkOpSegment& segment = fContour->segments()[fIndex]; + double mid = (t1 + t2) / 2; + SkDPoint midPtByT = segment.dPtAtT(mid); + SkDPoint midPtByAvg = SkDPoint::Mid(pt1, pt2); + return midPtByT.approximatelyPEqual(midPtByAvg); + } + SkScalar left() const { return bounds().fLeft; } @@ -137,6 +149,19 @@ public: return y() != pts()[0].fY; } +#ifdef SK_DEBUG + void dump() { + SkDPoint::dump(pts()[0]); + SkDPoint::dump(pts()[1]); + if (verb() >= SkPath::kQuad_Verb) { + SkDPoint::dump(pts()[2]); + } + if (verb() >= SkPath::kCubic_Verb) { + SkDPoint::dump(pts()[3]); + } + } +#endif + private: SkOpContour* fContour; int fIndex; diff --git a/src/pathops/SkIntersections.cpp b/src/pathops/SkIntersections.cpp index 608ffe3b6d..35846f6cc9 100644 --- a/src/pathops/SkIntersections.cpp +++ b/src/pathops/SkIntersections.cpp @@ -7,6 +7,12 @@ #include "SkIntersections.h" +void SkIntersections::append(const SkIntersections& i) { + for (int index = 0; index < i.fUsed; ++index) { + insert(i[0][index], i[1][index], i.pt(index)); + } +} + int (SkIntersections::*CurveVertical[])(const SkPoint[], SkScalar, SkScalar, SkScalar, bool) = { NULL, &SkIntersections::verticalLine, @@ -16,7 +22,7 @@ int (SkIntersections::*CurveVertical[])(const SkPoint[], SkScalar, SkScalar, SkS int (SkIntersections::*CurveRay[])(const SkPoint[], const SkDLine&) = { NULL, - NULL, + &SkIntersections::lineRay, &SkIntersections::quadRay, &SkIntersections::cubicRay }; @@ -126,6 +132,13 @@ void SkIntersections::insertCoincident(double one, double two, const SkDPoint& p fIsCoincident[1] |= bit; } +int SkIntersections::lineRay(const SkPoint pts[2], const SkDLine& line) { + SkDLine l; + l.set(pts); + fMax = 2; + return intersectRay(l, line); +} + void SkIntersections::offset(int base, double start, double end) { for (int index = base; index < fUsed; ++index) { double val = fT[fSwap][index]; diff --git a/src/pathops/SkIntersections.h b/src/pathops/SkIntersections.h index f63a023ef0..a3e8332650 100644 --- a/src/pathops/SkIntersections.h +++ b/src/pathops/SkIntersections.h @@ -183,9 +183,6 @@ public: return intersect(aQuad, bQuad); } - int quadRay(const SkPoint pts[3], const SkDLine& line); - void removeOne(int index); - // leaves flip, swap, max alone void reset() { fAllowNear = true; @@ -218,6 +215,7 @@ public: SkASSERT(++fDepth < 16); } + void append(const SkIntersections& ); static double Axial(const SkDQuad& , const SkDPoint& , bool vertical); void cleanUpCoincidence(); int coincidentUsed() const; @@ -246,8 +244,11 @@ public: int intersectRay(const SkDQuad&, const SkDLine&); int intersectRay(const SkDCubic&, const SkDLine&); static SkDPoint Line(const SkDLine&, const SkDLine&); + int lineRay(const SkPoint pts[2], const SkDLine& line); void offset(int base, double start, double end); void quickRemoveOne(int index, int replace); + int quadRay(const SkPoint pts[3], const SkDLine& line); + void removeOne(int index); static bool Test(const SkDLine& , const SkDLine&); int vertical(const SkDLine&, double x); int vertical(const SkDLine&, double top, double bottom, double x, bool flipped); diff --git a/src/pathops/SkOpAngle.cpp b/src/pathops/SkOpAngle.cpp index 5e1d9e745e..4144add6fb 100644 --- a/src/pathops/SkOpAngle.cpp +++ b/src/pathops/SkOpAngle.cpp @@ -207,7 +207,10 @@ bool SkOpAngle::operator<(const SkOpAngle& rh) const { // this/lh: left-hand; r return COMPARE_RESULT("roots == 0 || rroots == 0", this < &rh); } SkASSERT(fSide != 0 && rh.fSide != 0); - SkASSERT(fSide * rh.fSide > 0); // both are the same sign + if (fSide * rh.fSide < 0) { + fUnsortable = true; + return COMPARE_RESULT("14 fSide * rh.fSide < 0", this < &rh); + } SkDPoint lLoc; double best = SK_ScalarInfinity; #if DEBUG_SORT @@ -246,7 +249,7 @@ bool SkOpAngle::operator<(const SkOpAngle& rh) const { // this/lh: left-hand; r if (flip) { leftLessThanRight = !leftLessThanRight; } - return COMPARE_RESULT("14 leftLessThanRight", leftLessThanRight); + return COMPARE_RESULT("15 leftLessThanRight", leftLessThanRight); } bool SkOpAngle::isHorizontal() const { diff --git a/src/pathops/SkOpContour.cpp b/src/pathops/SkOpContour.cpp index 4aa12cd465..5feef79801 100644 --- a/src/pathops/SkOpContour.cpp +++ b/src/pathops/SkOpContour.cpp @@ -174,6 +174,63 @@ void SkOpContour::calcPartialCoincidentWinding() { } } +void SkOpContour::joinCoincidence(const SkTArray<SkCoincidence, true>& coincidences, bool partial) { + int count = coincidences.count(); +#if DEBUG_CONCIDENT + if (count > 0) { + SkDebugf("%s count=%d\n", __FUNCTION__, count); + } +#endif + // look for a lineup where the partial implies another adjoining coincidence + for (int index = 0; index < count; ++index) { + const SkCoincidence& coincidence = coincidences[index]; + int thisIndex = coincidence.fSegments[0]; + SkOpSegment& thisOne = fSegments[thisIndex]; + SkOpContour* otherContour = coincidence.fOther; + int otherIndex = coincidence.fSegments[1]; + SkOpSegment& other = otherContour->fSegments[otherIndex]; + double startT = coincidence.fTs[0][0]; + double endT = coincidence.fTs[0][1]; + if (startT == endT) { // this can happen in very large compares + continue; + } + double oStartT = coincidence.fTs[1][0]; + double oEndT = coincidence.fTs[1][1]; + if (oStartT == oEndT) { + continue; + } + bool swapStart = startT > endT; + bool swapOther = oStartT > oEndT; + if (swapStart) { + SkTSwap<double>(startT, endT); + SkTSwap<double>(oStartT, oEndT); + } + bool cancel = swapOther != swapStart; + int step = swapStart ? -1 : 1; + int oStep = swapOther ? -1 : 1; + double oMatchStart = cancel ? oEndT : oStartT; + if (partial ? startT != 0 || oMatchStart != 0 : (startT == 0) != (oMatchStart == 0)) { + bool added = false; + if (oMatchStart != 0) { + added = thisOne.joinCoincidence(false, &other, oMatchStart, oStep, cancel); + } + if (startT != 0 && !added) { + (void) other.joinCoincidence(cancel, &thisOne, startT, step, cancel); + } + } + double oMatchEnd = cancel ? oStartT : oEndT; + if (partial ? endT != 1 || oMatchEnd != 1 : (endT == 1) != (oMatchEnd == 1)) { + bool added = false; + if (oMatchEnd != 1) { + added = thisOne.joinCoincidence(true, &other, oMatchEnd, -oStep, cancel); + } + if (endT != 1 && !added) { + (void) other.joinCoincidence(!cancel, &thisOne, endT, -step, cancel); + } + } + } +} + void SkOpContour::calcCommonCoincidentWinding(const SkCoincidence& coincidence) { int thisIndex = coincidence.fSegments[0]; SkOpSegment& thisOne = fSegments[thisIndex]; diff --git a/src/pathops/SkOpContour.h b/src/pathops/SkOpContour.h index a4ec6d398f..6b412e5f53 100644 --- a/src/pathops/SkOpContour.h +++ b/src/pathops/SkOpContour.h @@ -152,6 +152,11 @@ public: } } + void joinCoincidence() { + joinCoincidence(fCoincidences, false); + joinCoincidence(fPartialCoincidences, true); + } + SkOpSegment* nonVerticalSegment(int* start, int* end); bool operand() const { @@ -239,7 +244,8 @@ public: #endif private: - void calcCommonCoincidentWinding(const SkCoincidence& coincidence); + void calcCommonCoincidentWinding(const SkCoincidence& ); + void joinCoincidence(const SkTArray<SkCoincidence, true>& , bool partial); void setBounds(); SkTArray<SkOpSegment> fSegments; diff --git a/src/pathops/SkOpEdgeBuilder.cpp b/src/pathops/SkOpEdgeBuilder.cpp index 676c34fb37..ae72e29385 100644 --- a/src/pathops/SkOpEdgeBuilder.cpp +++ b/src/pathops/SkOpEdgeBuilder.cpp @@ -42,16 +42,11 @@ bool SkOpEdgeBuilder::finish() { } void SkOpEdgeBuilder::closeContour(const SkPoint& curveEnd, const SkPoint& curveStart) { - if ((!AlmostEqualUlps(curveEnd.fX, curveStart.fX) - || !AlmostEqualUlps(curveEnd.fY, curveStart.fY))) { + if (!SkDPoint::ApproximatelyEqual(curveEnd, curveStart)) { fPathVerbs.push_back(SkPath::kLine_Verb); fPathPts.push_back_n(1, &curveStart); } else { - if (curveEnd.fX != curveStart.fX || curveEnd.fY != curveStart.fY) { - fPathPts[fPathPts.count() - 1] = curveStart; - } else { - fPathPts[fPathPts.count() - 1] = curveStart; - } + fPathPts[fPathPts.count() - 1] = curveStart; } fPathVerbs.push_back(SkPath::kClose_Verb); } @@ -82,9 +77,9 @@ int SkOpEdgeBuilder::preFetch() { lastCurve = false; continue; case SkPath::kLine_Verb: - if (AlmostEqualUlps(curve[0].fX, pts[1].fX) - && AlmostEqualUlps(curve[0].fY, pts[1].fY)) { - if (fPathVerbs.back() != SkPath::kLine_Verb) { + if (SkDPoint::ApproximatelyEqual(curve[0], pts[1])) { + uint8_t lastVerb = fPathVerbs.back(); + if (lastVerb != SkPath::kLine_Verb && lastVerb != SkPath::kMove_Verb) { fPathPts.back() = pts[1]; } continue; // skip degenerate points diff --git a/src/pathops/SkOpSegment.cpp b/src/pathops/SkOpSegment.cpp index 4d11eb39e8..6fe1fbb49d 100644 --- a/src/pathops/SkOpSegment.cpp +++ b/src/pathops/SkOpSegment.cpp @@ -1298,6 +1298,7 @@ int SkOpSegment::crossedSpanY(const SkPoint& basePt, SkScalar* bestY, double* hi SkIntersections intersections; // OPTIMIZE: use specialty function that intersects ray with curve, // returning t values only for curve (we don't care about t on ray) + intersections.allowNear(false); int pts = (intersections.*CurveVertical[SkPathOpsVerbToPoints(fVerb)]) (fPts, top, bottom, basePt.fX, false); if (pts == 0 || (current && pts == 1)) { @@ -1420,15 +1421,29 @@ void SkOpSegment::checkEnds() { } // t start/last describe the range of spans that match the t of this span double t = span.fT; - int tStart = index; - while (--tStart >= 0 && (t == fTs[tStart].fT || fTs[tStart].fTiny)) - ; - int tLast = index; - while (fTs[tLast].fTiny) { - ++tLast; + double tBottom = -1; + int tStart = -1; + int tLast = count; + bool lastSmall = false; + double afterT = t; + for (int inner = 0; inner < count; ++inner) { + double innerT = fTs[inner].fT; + if (innerT <= t && innerT > tBottom) { + if (innerT < t || !lastSmall) { + tStart = inner - 1; + } + tBottom = innerT; + } + if (innerT > afterT) { + if (t == afterT && lastSmall) { + afterT = innerT; + } else { + tLast = inner; + break; + } + } + lastSmall = innerT <= t ? fTs[inner].fSmall : false; } - while (++tLast < count && t == fTs[tLast].fT) - ; for (int peekIndex = peekStart; peekIndex <= peekLast; ++peekIndex) { if (peekIndex == span.fOtherIndex) { // skip the other span pointed to by this span continue; @@ -1696,6 +1711,70 @@ void SkOpSegment::checkTiny() { } } +bool SkOpSegment::findCoincidentMatch(const SkOpSpan* span, const SkOpSegment* other, int oStart, + int oEnd, int step, SkPoint* startPt, SkPoint* endPt, double* endT) const { + SkASSERT(span->fT == 0 || span->fT == 1); + SkASSERT(span->fOtherT == 0 || span->fOtherT == 1); + const SkOpSpan* otherSpan = &other->span(oEnd); + double refT = otherSpan->fT; + const SkPoint& refPt = otherSpan->fPt; + const SkOpSpan* lastSpan = &other->span(step > 0 ? other->count() - 1 : 0); + do { + const SkOpSegment* match = span->fOther; + if (match == otherSpan->fOther) { + // find start of respective spans and see if both have winding + int startIndex, endIndex; + if (span->fOtherT == 1) { + endIndex = span->fOtherIndex; + startIndex = match->nextExactSpan(endIndex, -1); + } else { + startIndex = span->fOtherIndex; + endIndex = match->nextExactSpan(startIndex, 1); + } + const SkOpSpan& startSpan = match->span(startIndex); + if (startSpan.fWindValue != 0) { + // draw ray from endSpan.fPt perpendicular to end tangent and measure distance + // to other segment. + const SkOpSpan& endSpan = match->span(endIndex); + SkDLine ray; + SkVector dxdy; + if (span->fOtherT == 1) { + ray.fPts[0].set(startSpan.fPt); + dxdy = match->dxdy(startIndex); + } else { + ray.fPts[0].set(endSpan.fPt); + dxdy = match->dxdy(endIndex); + } + ray.fPts[1].fX = ray.fPts[0].fX + dxdy.fY; + ray.fPts[1].fY = ray.fPts[0].fY - dxdy.fX; + SkIntersections i; + int roots = (i.*CurveRay[SkPathOpsVerbToPoints(other->verb())])(other->pts(), ray); + for (int index = 0; index < roots; ++index) { + if (ray.fPts[0].approximatelyEqual(i.pt(index))) { + double matchMidT = (match->span(startIndex).fT + + match->span(endIndex).fT) / 2; + SkPoint matchMidPt = match->ptAtT(matchMidT); + double otherMidT = (i[0][index] + other->span(oStart).fT) / 2; + SkPoint otherMidPt = other->ptAtT(otherMidT); + if (SkDPoint::ApproximatelyEqual(matchMidPt, otherMidPt)) { + *startPt = startSpan.fPt; + *endPt = endSpan.fPt; + *endT = endSpan.fT; + return true; + } + } + } + } + return false; + } + if (otherSpan == lastSpan) { + break; + } + otherSpan += step; + } while (otherSpan->fT == refT || otherSpan->fPt == refPt); + return false; +} + /* The M and S variable name parts stand for the operators. Mi stands for Minuend (see wiki subtraction, analogous to difference) @@ -2076,6 +2155,18 @@ int SkOpSegment::findStartingEdge(const SkTArray<SkOpAngle*, true>& sorted, int return firstIndex; } +int SkOpSegment::findT(double t, const SkOpSegment* match) const { + int count = this->count(); + for (int index = 0; index < count; ++index) { + const SkOpSpan& span = fTs[index]; + if (span.fT == t && span.fOther == match) { + return index; + } + } + SkASSERT(0); + return -1; +} + // FIXME: either: // a) mark spans with either end unsortable as done, or // b) rewrite findTop / findTopSegment / findTopContour to iterate further @@ -2299,6 +2390,76 @@ bool SkOpSegment::isSimple(int end) const { return false; } +bool SkOpSegment::isTiny(const SkOpAngle* angle) const { + int start = angle->start(); + int end = angle->end(); + const SkOpSpan& mSpan = fTs[SkMin32(start, end)]; + return mSpan.fTiny; +} + +bool SkOpSegment::isTiny(int index) const { + return fTs[index].fTiny; +} + +// look pair of active edges going away from coincident edge +// one of them should be the continuation of other +// if both are active, look to see if they both the connect to another coincident pair +// if one at least one is a line, then make the pair coincident +// if neither is a line, test for coincidence +bool SkOpSegment::joinCoincidence(bool end, SkOpSegment* other, double otherT, int step, + bool cancel) { + int otherTIndex = other->findT(otherT, this); + int next = other->nextExactSpan(otherTIndex, step); + int otherMin = SkTMin(otherTIndex, next); + int otherWind = other->span(otherMin).fWindValue; + if (otherWind == 0) { + return false; + } + SkASSERT(next >= 0); + if (end) { + int tIndex = count() - 1; + do { + SkOpSpan* test = &fTs[tIndex]; + SkASSERT(test->fT == 1); + if (test->fOther == other || test->fOtherT != 0) { + continue; + } + SkPoint startPt, endPt; + double endT; + if (findCoincidentMatch(test, other, otherTIndex, next, step, &startPt, &endPt, &endT)) { + SkOpSegment* match = test->fOther; + if (cancel) { + match->addTCancel(startPt, endPt, other); + } else { + match->addTCoincident(startPt, endPt, endT, other); + } + return true; + } + } while (fTs[--tIndex].fT == 1); + } else { + int tIndex = 0; + do { + SkOpSpan* test = &fTs[tIndex]; + SkASSERT(test->fT == 0); + if (test->fOther == other || test->fOtherT != 1) { + continue; + } + SkPoint startPt, endPt; + double endT; + if (findCoincidentMatch(test, other, otherTIndex, next, step, &startPt, &endPt, &endT)) { + SkOpSegment* match = test->fOther; + if (cancel) { + match->addTCancel(startPt, endPt, other); + } else { + match->addTCoincident(startPt, endPt, endT, other); + } + return true; + } + } while (fTs[++tIndex].fT == 0); + } + return false; +} + // this span is excluded by the winding rule -- chase the ends // as long as they are unambiguous to mark connections as done // and give them the same winding value @@ -3018,17 +3179,6 @@ void SkOpSegment::subDivideBounds(int start, int end, SkPathOpsBounds* bounds) c (bounds->*SetCurveBounds[SkPathOpsVerbToPoints(fVerb)])(edge); } -bool SkOpSegment::isTiny(const SkOpAngle* angle) const { - int start = angle->start(); - int end = angle->end(); - const SkOpSpan& mSpan = fTs[SkMin32(start, end)]; - return mSpan.fTiny; -} - -bool SkOpSegment::isTiny(int index) const { - return fTs[index].fTiny; -} - void SkOpSegment::TrackOutsidePair(SkTArray<SkPoint, true>* outsidePts, const SkPoint& endPt, const SkPoint& startPt) { int outCount = outsidePts->count(); @@ -3558,10 +3708,10 @@ void SkOpSegment::dumpPts() const { SkDebugf("{{"); int index = 0; do { - SkDPoint::DumpSkPoint(fPts[index]); + SkDPoint::dump(fPts[index]); SkDebugf(", "); } while (++index < last); - SkDPoint::DumpSkPoint(fPts[index]); + SkDPoint::dump(fPts[index]); SkDebugf("}}\n"); } diff --git a/src/pathops/SkOpSegment.h b/src/pathops/SkOpSegment.h index 85531f5262..d56ce8e206 100644 --- a/src/pathops/SkOpSegment.h +++ b/src/pathops/SkOpSegment.h @@ -259,12 +259,15 @@ public: SkTArray<SkOpAngle, true>* angles, SkTArray<SkOpAngle*, true>* sorted); int crossedSpanY(const SkPoint& basePt, SkScalar* bestY, double* hitT, bool* hitSomething, double mid, bool opp, bool current) const; + bool findCoincidentMatch(const SkOpSpan* span, const SkOpSegment* other, int oStart, int oEnd, + int step, SkPoint* startPt, SkPoint* endPt, double* endT) const; SkOpSegment* findNextOp(SkTDArray<SkOpSpan*>* chase, int* nextStart, int* nextEnd, bool* unsortable, SkPathOp op, const int xorMiMask, const int xorSuMask); SkOpSegment* findNextWinding(SkTDArray<SkOpSpan*>* chase, int* nextStart, int* nextEnd, bool* unsortable); SkOpSegment* findNextXor(int* nextStart, int* nextEnd, bool* unsortable); + int findT(double t, const SkOpSegment* ) const; SkOpSegment* findTop(int* tIndex, int* endIndex, bool* unsortable, bool onlySortable); void fixOtherTIndex(); void initWinding(int start, int end); @@ -272,6 +275,7 @@ public: SkScalar hitOppDx); bool isMissing(double startT, const SkPoint& pt) const; bool isTiny(const SkOpAngle* angle) const; + bool joinCoincidence(bool end, SkOpSegment* other, double otherT, int step, bool cancel); SkOpSpan* markAndChaseDoneBinary(int index, int endIndex); SkOpSpan* markAndChaseDoneUnary(int index, int endIndex); SkOpSpan* markAndChaseWinding(const SkOpAngle* angle, int winding, int oppWinding); diff --git a/src/pathops/SkPathOpsCommon.cpp b/src/pathops/SkPathOpsCommon.cpp index 4db60797ec..c48a7eef68 100644 --- a/src/pathops/SkPathOpsCommon.cpp +++ b/src/pathops/SkPathOpsCommon.cpp @@ -4,6 +4,7 @@ * Use of this source code is governed by a BSD-style license that can be * found in the LICENSE file. */ +#include "SkAddIntersections.h" #include "SkOpEdgeBuilder.h" #include "SkPathOpsCommon.h" #include "SkPathWriter.h" @@ -350,7 +351,7 @@ SkOpSegment* FindSortableTop(const SkTArray<SkOpContour*, true>& contourList, return current; } -void CheckEnds(SkTArray<SkOpContour*, true>* contourList) { +static void checkEnds(SkTArray<SkOpContour*, true>* contourList) { // it's hard to determine if the end of a cubic or conic nearly intersects another curve. // instead, look to see if the connecting curve intersected at that same end. int contourCount = (*contourList).count(); @@ -361,7 +362,7 @@ void CheckEnds(SkTArray<SkOpContour*, true>* contourList) { } // A tiny interval may indicate an undiscovered coincidence. Find and fix. -void CheckTiny(SkTArray<SkOpContour*, true>* contourList) { +static void checkTiny(SkTArray<SkOpContour*, true>* contourList) { int contourCount = (*contourList).count(); for (int cTest = 0; cTest < contourCount; ++cTest) { SkOpContour* contour = (*contourList)[cTest]; @@ -369,7 +370,7 @@ void CheckTiny(SkTArray<SkOpContour*, true>* contourList) { } } -void FixOtherTIndex(SkTArray<SkOpContour*, true>* contourList) { +static void fixOtherTIndex(SkTArray<SkOpContour*, true>* contourList) { int contourCount = (*contourList).count(); for (int cTest = 0; cTest < contourCount; ++cTest) { SkOpContour* contour = (*contourList)[cTest]; @@ -377,7 +378,15 @@ void FixOtherTIndex(SkTArray<SkOpContour*, true>* contourList) { } } -void SortSegments(SkTArray<SkOpContour*, true>* contourList) { +static void joinCoincidence(SkTArray<SkOpContour*, true>* contourList) { + int contourCount = (*contourList).count(); + for (int cTest = 0; cTest < contourCount; ++cTest) { + SkOpContour* contour = (*contourList)[cTest]; + contour->joinCoincidence(); + } +} + +static void sortSegments(SkTArray<SkOpContour*, true>* contourList) { int contourCount = (*contourList).count(); for (int cTest = 0; cTest < contourCount; ++cTest) { SkOpContour* contour = (*contourList)[cTest]; @@ -603,3 +612,21 @@ void Assemble(const SkPathWriter& path, SkPathWriter* simple) { } #endif } + +void HandleCoincidence(SkTArray<SkOpContour*, true>* contourList, int total) { +#if DEBUG_SHOW_WINDING + SkOpContour::debugShowWindingValues(contourList); +#endif + CoincidenceCheck(contourList, total); +#if DEBUG_SHOW_WINDING + SkOpContour::debugShowWindingValues(contourList); +#endif + fixOtherTIndex(contourList); + checkEnds(contourList); + checkTiny(contourList); + joinCoincidence(contourList); + sortSegments(contourList); +#if DEBUG_ACTIVE_SPANS || DEBUG_ACTIVE_SPANS_FIRST_ONLY + DebugShowActiveSpans(*contourList); +#endif +} diff --git a/src/pathops/SkPathOpsCommon.h b/src/pathops/SkPathOpsCommon.h index e1ae998b10..afc751d130 100644 --- a/src/pathops/SkPathOpsCommon.h +++ b/src/pathops/SkPathOpsCommon.h @@ -14,18 +14,15 @@ class SkPathWriter; void Assemble(const SkPathWriter& path, SkPathWriter* simple); -void CheckEnds(SkTArray<SkOpContour*, true>* contourList); -void CheckTiny(SkTArray<SkOpContour*, true>* contourList); // FIXME: find chase uses insert, so it can't be converted to SkTArray yet SkOpSegment* FindChase(SkTDArray<SkOpSpan*>& chase, int& tIndex, int& endIndex); SkOpSegment* FindSortableTop(const SkTArray<SkOpContour*, true>& , SkOpAngle::IncludeType , bool* firstContour, int* index, int* endIndex, SkPoint* topLeft, bool* unsortable, bool* done); SkOpSegment* FindUndone(SkTArray<SkOpContour*, true>& contourList, int* start, int* end); -void FixOtherTIndex(SkTArray<SkOpContour*, true>* contourList); void MakeContourList(SkTArray<SkOpContour>& contours, SkTArray<SkOpContour*, true>& list, bool evenOdd, bool oppEvenOdd); -void SortSegments(SkTArray<SkOpContour*, true>* contourList); +void HandleCoincidence(SkTArray<SkOpContour*, true>* , int ); #if DEBUG_ACTIVE_SPANS || DEBUG_ACTIVE_SPANS_FIRST_ONLY void DebugShowActiveSpans(SkTArray<SkOpContour*, true>& contourList); diff --git a/src/pathops/SkPathOpsDebug.cpp b/src/pathops/SkPathOpsDebug.cpp index 1b19fe5ce1..95e2204c33 100644 --- a/src/pathops/SkPathOpsDebug.cpp +++ b/src/pathops/SkPathOpsDebug.cpp @@ -103,7 +103,7 @@ void SkOpSpan::dump() const { SkDebugf("t="); DebugDumpDouble(fT); SkDebugf(" pt="); - SkDPoint::DumpSkPoint(fPt); + SkDPoint::dump(fPt); SkDebugf(" other.fID=%d", fOther->debugID()); SkDebugf(" [%d] otherT=", fOtherIndex); DebugDumpDouble(fOtherT); @@ -157,3 +157,8 @@ void Dump(const SkTArray<class SkOpAngle* , true>* angles) { } #endif + +#if !FORCE_RELEASE && 0 // enable when building without extended test +void SkPathOpsDebug::ShowPath(const SkPath& one, const SkPath& two, SkPathOp op, const char* name) { +} +#endif diff --git a/src/pathops/SkPathOpsOp.cpp b/src/pathops/SkPathOpsOp.cpp index 71ebef00b3..9d6cd51b45 100644 --- a/src/pathops/SkPathOpsOp.cpp +++ b/src/pathops/SkPathOpsOp.cpp @@ -304,20 +304,7 @@ bool Op(const SkPath& one, const SkPath& two, SkPathOp op, SkPath* result) { for (index = 0; index < contourList.count(); ++index) { total += contourList[index]->segments().count(); } -#if DEBUG_SHOW_WINDING - SkOpContour::debugShowWindingValues(contourList); -#endif - CoincidenceCheck(&contourList, total); -#if DEBUG_SHOW_WINDING - SkOpContour::debugShowWindingValues(contourList); -#endif - FixOtherTIndex(&contourList); - CheckEnds(&contourList); - CheckTiny(&contourList); - SortSegments(&contourList); -#if DEBUG_ACTIVE_SPANS || DEBUG_ACTIVE_SPANS_FIRST_ONLY - DebugShowActiveSpans(contourList); -#endif + HandleCoincidence(&contourList, total); // construct closed contours SkPathWriter wrapper(*result); bridgeOp(contourList, op, xorMask, xorOpMask, &wrapper); diff --git a/src/pathops/SkPathOpsPoint.h b/src/pathops/SkPathOpsPoint.h index 40688d8072..c3e0b40ab9 100644 --- a/src/pathops/SkPathOpsPoint.h +++ b/src/pathops/SkPathOpsPoint.h @@ -98,7 +98,7 @@ struct SkDPoint { // note: this can not be implemented with // return approximately_equal(a.fY, fY) && approximately_equal(a.fX, fX); - // because that will not take the magnitude of the values + // because that will not take the magnitude of the values into account bool approximatelyEqual(const SkDPoint& a) const { if (approximately_equal(fX, a.fX) && approximately_equal(fY, a.fY)) { return true; @@ -136,6 +136,20 @@ struct SkDPoint { return AlmostBequalUlps((double) largest, largest + dist); // is dist within ULPS tolerance? } + bool approximatelyPEqual(const SkDPoint& a) const { + if (approximately_equal(fX, a.fX) && approximately_equal(fY, a.fY)) { + return true; + } + if (!RoughlyEqualUlps(fX, a.fX) || !RoughlyEqualUlps(fY, a.fY)) { + return false; + } + double dist = distance(a); // OPTIMIZATION: can we compare against distSq instead ? + double tiniest = SkTMin(SkTMin(SkTMin(fX, a.fX), fY), a.fY); + double largest = SkTMax(SkTMax(SkTMax(fX, a.fX), fY), a.fY); + largest = SkTMax(largest, -tiniest); + return AlmostPequalUlps(largest, largest + dist); // is the dist within ULPS tolerance? + } + bool approximatelyZero() const { return approximately_zero(fX) && approximately_zero(fY); } @@ -186,7 +200,7 @@ struct SkDPoint { SkDebugf("}"); } - static void DumpSkPoint(const SkPoint& pt) { + static void dump(const SkPoint& pt) { SkDebugf("{"); DebugDumpFloat(pt.fX); SkDebugf(", "); diff --git a/src/pathops/SkPathOpsSimplify.cpp b/src/pathops/SkPathOpsSimplify.cpp index 76e3413089..548f83e660 100644 --- a/src/pathops/SkPathOpsSimplify.cpp +++ b/src/pathops/SkPathOpsSimplify.cpp @@ -182,15 +182,7 @@ bool Simplify(const SkPath& path, SkPath* result) { next = *nextPtr++; } while (AddIntersectTs(current, next) && nextPtr != listEnd); } while (currentPtr != listEnd); - // eat through coincident edges - CoincidenceCheck(&contourList, 0); - FixOtherTIndex(&contourList); - CheckEnds(&contourList); - CheckTiny(&contourList); - SortSegments(&contourList); -#if DEBUG_ACTIVE_SPANS || DEBUG_ACTIVE_SPANS_FIRST_ONLY - DebugShowActiveSpans(contourList); -#endif + HandleCoincidence(&contourList, 0); // construct closed contours SkPathWriter simple(*result); if (builder.xorMask() == kWinding_PathOpsMask ? bridgeWinding(contourList, &simple) diff --git a/src/pathops/SkPathOpsTriangle.cpp b/src/pathops/SkPathOpsTriangle.cpp index 49391667ac..003968ddba 100644 --- a/src/pathops/SkPathOpsTriangle.cpp +++ b/src/pathops/SkPathOpsTriangle.cpp @@ -8,6 +8,7 @@ #include "SkPathOpsTriangle.h" // http://www.blackpawn.com/texts/pointinpoly/default.html +// return true if pt is inside triangle; false if outside or on the line bool SkDTriangle::contains(const SkDPoint& pt) const { // Compute vectors SkDVector v0 = fPts[2] - fPts[0]; @@ -21,11 +22,30 @@ bool SkDTriangle::contains(const SkDPoint& pt) const { double dot11 = v1.dot(v1); double dot12 = v1.dot(v2); +// original code doesn't handle degenerate input; isn't symmetric with inclusion of corner pts; +// introduces necessary error with divide; doesn't short circuit on early answer +#if 0 // Compute barycentric coordinates double invDenom = 1 / (dot00 * dot11 - dot01 * dot01); double u = (dot11 * dot02 - dot01 * dot12) * invDenom; double v = (dot00 * dot12 - dot01 * dot02) * invDenom; // Check if point is in triangle - return (u >= 0) && (v >= 0) && (u + v < 1); + return (u >= 0) && (v >= 0) && (u + v <= 1); +#else + double w = dot00 * dot11 - dot01 * dot01; + if (w == 0) { + return false; + } + double wSign = w < 0 ? -1 : 1; + double u = (dot11 * dot02 - dot01 * dot12) * wSign; + if (u <= 0) { + return false; + } + double v = (dot00 * dot12 - dot01 * dot02) * wSign; + if (v <= 0) { + return false; + } + return u + v < w * wSign; +#endif } diff --git a/src/pathops/SkPathOpsTypes.cpp b/src/pathops/SkPathOpsTypes.cpp index df73d11ce4..dbed086fbd 100644 --- a/src/pathops/SkPathOpsTypes.cpp +++ b/src/pathops/SkPathOpsTypes.cpp @@ -8,17 +8,17 @@ #include "SkPathOpsTypes.h" static bool arguments_denormalized(float a, float b, int epsilon) { - float denomalizedCheck = FLT_EPSILON * epsilon / 2; - return fabsf(a) <= denomalizedCheck && fabsf(b) <= denomalizedCheck; + float denormalizedCheck = FLT_EPSILON * epsilon / 2; + return fabsf(a) <= denormalizedCheck && fabsf(b) <= denormalizedCheck; } // from http://randomascii.wordpress.com/2012/02/25/comparing-floating-point-numbers-2012-edition/ // FIXME: move to SkFloatBits.h -static bool equal_ulps(float a, float b, int epsilon) { +static bool equal_ulps(float a, float b, int epsilon, int depsilon) { if (!SkScalarIsFinite(a) || !SkScalarIsFinite(b)) { return false; } - if (arguments_denormalized(a, b, epsilon)) { + if (arguments_denormalized(a, b, depsilon)) { return true; } int aBits = SkFloatAs2sCompliment(a); @@ -89,7 +89,12 @@ static bool less_or_equal_ulps(float a, float b, int epsilon) { // equality using the same error term as between bool AlmostBequalUlps(float a, float b) { const int UlpsEpsilon = 2; - return equal_ulps(a, b, UlpsEpsilon); + return equal_ulps(a, b, UlpsEpsilon, UlpsEpsilon); +} + +bool AlmostPequalUlps(float a, float b) { + const int UlpsEpsilon = 8; + return equal_ulps(a, b, UlpsEpsilon, UlpsEpsilon); } bool AlmostDequalUlps(float a, float b) { @@ -99,7 +104,7 @@ bool AlmostDequalUlps(float a, float b) { bool AlmostEqualUlps(float a, float b) { const int UlpsEpsilon = 16; - return equal_ulps(a, b, UlpsEpsilon); + return equal_ulps(a, b, UlpsEpsilon, UlpsEpsilon); } bool NotAlmostEqualUlps(float a, float b) { @@ -114,7 +119,8 @@ bool NotAlmostDequalUlps(float a, float b) { bool RoughlyEqualUlps(float a, float b) { const int UlpsEpsilon = 256; - return equal_ulps(a, b, UlpsEpsilon); + const int DUlpsEpsilon = 1024; + return equal_ulps(a, b, UlpsEpsilon, DUlpsEpsilon); } bool AlmostBetweenUlps(float a, float b, float c) { diff --git a/src/pathops/SkPathOpsTypes.h b/src/pathops/SkPathOpsTypes.h index 0ad10c2eba..4fa86abd91 100644 --- a/src/pathops/SkPathOpsTypes.h +++ b/src/pathops/SkPathOpsTypes.h @@ -50,6 +50,11 @@ inline bool AlmostBequalUlps(double a, double b) { return AlmostBequalUlps(SkDoubleToScalar(a), SkDoubleToScalar(b)); } +bool AlmostPequalUlps(float a, float b); +inline bool AlmostPequalUlps(double a, double b) { + return AlmostPequalUlps(SkDoubleToScalar(a), SkDoubleToScalar(b)); +} + bool RoughlyEqualUlps(float a, float b); inline bool RoughlyEqualUlps(double a, double b) { return RoughlyEqualUlps(SkDoubleToScalar(a), SkDoubleToScalar(b)); diff --git a/src/pathops/SkQuarticRoot.cpp b/src/pathops/SkQuarticRoot.cpp index dca96ded3a..e5b486c76c 100644 --- a/src/pathops/SkQuarticRoot.cpp +++ b/src/pathops/SkQuarticRoot.cpp @@ -71,7 +71,7 @@ int SkReducedQuarticRoots(const double t4, const double t3, const double t2, con return num; } if (oneHint) { - SkASSERT(approximately_zero(t4 + t3 + t2 + t1 + t0)); // 1 is one root + SkASSERT(approximately_zero_double(t4 + t3 + t2 + t1 + t0)); // 1 is one root // note that -C == A + B + D + E int num = SkDCubic::RootsReal(t4, t4 + t3, -(t1 + t0), -t0, roots); for (int i = 0; i < num; ++i) { |