diff options
Diffstat (limited to 'src/pathops')
27 files changed, 624 insertions, 259 deletions
diff --git a/src/pathops/SkAddIntersections.cpp b/src/pathops/SkAddIntersections.cpp index 05079845fe..5fa80ec506 100644 --- a/src/pathops/SkAddIntersections.cpp +++ b/src/pathops/SkAddIntersections.cpp @@ -363,15 +363,20 @@ bool AddIntersectTs(SkOpContour* test, SkOpContour* next) { 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 + 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); - wt.addCoincident(wn, ts, swap); - continue; + if (wt.addCoincident(wn, ts, swap)) { + continue; + } + ts.cleanUpCoincidence(); // prefer (t == 0 or t == 1) + pts = 1; } } if (pts >= 2) { @@ -380,7 +385,11 @@ bool AddIntersectTs(SkOpContour* test, SkOpContour* next) { 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)) { - wt.addPartialCoincident(wn, ts, pt, swap); + 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; + } } } } diff --git a/src/pathops/SkDCubicIntersection.cpp b/src/pathops/SkDCubicIntersection.cpp index 63d434f2fa..ce2344841b 100644 --- a/src/pathops/SkDCubicIntersection.cpp +++ b/src/pathops/SkDCubicIntersection.cpp @@ -15,8 +15,8 @@ #include "SkTSort.h" #if ONE_OFF_DEBUG -static const double tLimits1[2][2] = {{0.388600450, 0.388600452}, {0.245852802, 0.245852804}}; -static const double tLimits2[2][2] = {{-0.865211397, -0.865215212}, {-0.865207696, -0.865208078}}; +static const double tLimits1[2][2] = {{0.3, 0.4}, {0.8, 0.9}}; +static const double tLimits2[2][2] = {{-0.8, -0.9}, {-0.8, -0.9}}; #endif #define DEBUG_QUAD_PART ONE_OFF_DEBUG && 1 @@ -124,7 +124,8 @@ static void intersect(const SkDCubic& cubic1, double t1s, double t1e, const SkDC SkDPoint p1 = cubic1.ptAtT(to1); SkDPoint p2 = cubic2.ptAtT(to2); if (p1.approximatelyEqual(p2)) { - SkASSERT(!locals.isCoincident(tIdx)); + // FIXME: local edge may be coincident -- experiment with not propagating coincidence to caller +// SkASSERT(!locals.isCoincident(tIdx)); if (&cubic1 != &cubic2 || !approximately_equal(to1, to2)) { if (i.swapped()) { // FIXME: insert should respect swap i.insert(to2, to1, p1); @@ -249,39 +250,70 @@ static void intersect(const SkDCubic& cubic1, double t1s, double t1e, const SkDC i.downDepth(); } + // if two ends intersect, check middle for coincidence +bool SkIntersections::cubicCheckCoincidence(const SkDCubic& c1, const SkDCubic& c2) { + if (fUsed < 2) { + return false; + } + int last = fUsed - 1; + double tRange1 = fT[0][last] - fT[0][0]; + double tRange2 = fT[1][last] - fT[1][0]; + for (int index = 1; index < 5; ++index) { + double testT1 = fT[0][0] + tRange1 * index / 5; + double testT2 = fT[1][0] + tRange2 * index / 5; + SkDPoint testPt1 = c1.ptAtT(testT1); + SkDPoint testPt2 = c2.ptAtT(testT2); + if (!testPt1.approximatelyEqual(testPt2)) { + return false; + } + } + if (fUsed > 2) { + fPt[1] = fPt[last]; + fT[0][1] = fT[0][last]; + fT[1][1] = fT[1][last]; + fUsed = 2; + } + fIsCoincident[0] = fIsCoincident[1] = 0x03; + return true; +} + #define LINE_FRACTION 0.1 // intersect the end of the cubic with the other. Try lines from the end to control and opposite // end to determine range of t on opposite cubic. -static void intersectEnd(const SkDCubic& cubic1, bool start, const SkDCubic& cubic2, - const SkDRect& bounds2, bool selfIntersect, SkIntersections& i) { - SkDLine line; +bool SkIntersections::cubicExactEnd(const SkDCubic& cubic1, bool start, const SkDCubic& cubic2) { int t1Index = start ? 0 : 3; - bool swap = i.swapped(); double testT = (double) !start; + bool swap = swapped(); // quad/quad at this point checks to see if exact matches have already been found // cubic/cubic can't reject so easily since cubics can intersect same point more than once - if (!selfIntersect) { - SkDLine tmpLine; - tmpLine[0] = tmpLine[1] = cubic2[t1Index]; - tmpLine[1].fX += cubic2[2 - start].fY - cubic2[t1Index].fY; - tmpLine[1].fY -= cubic2[2 - start].fX - cubic2[t1Index].fX; - SkIntersections impTs; - impTs.intersectRay(cubic1, tmpLine); - for (int index = 0; index < impTs.used(); ++index) { - SkDPoint realPt = impTs.pt(index); - if (!tmpLine[0].approximatelyEqualHalf(realPt)) { - continue; - } - if (swap) { - i.insert(testT, impTs[0][index], tmpLine[0]); - } else { - i.insert(impTs[0][index], testT, tmpLine[0]); - } - return; + SkDLine tmpLine; + tmpLine[0] = tmpLine[1] = cubic2[t1Index]; + tmpLine[1].fX += cubic2[2 - start].fY - cubic2[t1Index].fY; + tmpLine[1].fY -= cubic2[2 - start].fX - cubic2[t1Index].fX; + SkIntersections impTs; + impTs.intersectRay(cubic1, tmpLine); + for (int index = 0; index < impTs.used(); ++index) { + SkDPoint realPt = impTs.pt(index); + if (!tmpLine[0].approximatelyEqual(realPt)) { + continue; + } + if (swap) { + insert(testT, impTs[0][index], tmpLine[0]); + } else { + insert(impTs[0][index], testT, tmpLine[0]); } + return true; } - // don't bother if the two cubics are connnected + return false; +} + +void SkIntersections::cubicNearEnd(const SkDCubic& cubic1, bool start, const SkDCubic& cubic2, + const SkDRect& bounds2) { + SkDLine line; + int t1Index = start ? 0 : 3; + double testT = (double) !start; + // don't bother if the two cubics are connnected static const int kPointsInCubic = 4; // FIXME: move to DCubic, replace '4' with this static const int kMaxLineCubicIntersections = 3; SkSTArray<(kMaxLineCubicIntersections - 1) * kMaxLineCubicIntersections, double, true> tVals; @@ -310,10 +342,10 @@ static void intersectEnd(const SkDCubic& cubic1, bool start, const SkDCubic& cub continue; } if (local.pt(idx2).approximatelyEqual(line[0])) { - if (i.swapped()) { // FIXME: insert should respect swap - i.insert(foundT, testT, line[0]); + if (swapped()) { // FIXME: insert should respect swap + insert(foundT, testT, line[0]); } else { - i.insert(testT, foundT, line[0]); + insert(testT, foundT, line[0]); } } else { tVals.push_back(foundT); @@ -334,12 +366,12 @@ static void intersectEnd(const SkDCubic& cubic1, bool start, const SkDCubic& cub } double tMin2 = SkTMax(tVals[tIdx] - LINE_FRACTION, 0.0); double tMax2 = SkTMin(tVals[tLast] + LINE_FRACTION, 1.0); - int lastUsed = i.used(); - intersect(cubic1, tMin1, tMax1, cubic2, tMin2, tMax2, 1, i); - if (lastUsed == i.used()) { + int lastUsed = used(); + ::intersect(cubic1, tMin1, tMax1, cubic2, tMin2, tMax2, 1, *this); + if (lastUsed == used()) { tMin2 = SkTMax(tVals[tIdx] - (1.0 / SkDCubic::gPrecisionUnit), 0.0); tMax2 = SkTMin(tVals[tLast] + (1.0 / SkDCubic::gPrecisionUnit), 1.0); - intersect(cubic1, tMin1, tMax1, cubic2, tMin2, tMax2, 1, i); + ::intersect(cubic1, tMin1, tMax1, cubic2, tMin2, tMax2, 1, *this); } tIdx = tLast + 1; } while (tIdx < tVals.count()); @@ -404,15 +436,19 @@ tryNextHalfPlane: } int SkIntersections::intersect(const SkDCubic& c1, const SkDCubic& c2) { + if (fMax == 0) { + fMax = 9; + } bool selfIntersect = &c1 == &c2; if (selfIntersect) { - if (c1[0].approximatelyEqualHalf(c1[3])) { + if (c1[0].approximatelyEqual(c1[3])) { insert(0, 1, c1[0]); + return fUsed; } } else { for (int i1 = 0; i1 < 4; i1 += 3) { for (int i2 = 0; i2 < 4; i2 += 3) { - if (c1[i1].approximatelyEqualHalf(c2[i2])) { + if (c1[i1].approximatelyEqual(c2[i2])) { insert(i1 >> 1, i2 >> 1, c1[i1]); } } @@ -429,47 +465,47 @@ int SkIntersections::intersect(const SkDCubic& c1, const SkDCubic& c2) { } // quad/quad does linear test here -- cubic does not // cubics which are really lines should have been detected in reduce step earlier - SkDRect c1Bounds, c2Bounds; - // FIXME: pass in cached bounds from caller - c1Bounds.setBounds(c1); // OPTIMIZE use setRawBounds ? - c2Bounds.setBounds(c2); - intersectEnd(c1, false, c2, c2Bounds, selfIntersect, *this); - intersectEnd(c1, true, c2, c2Bounds, selfIntersect, *this); + int exactEndBits = 0; if (selfIntersect) { if (fUsed) { return fUsed; } } else { + exactEndBits |= cubicExactEnd(c1, false, c2) << 0; + exactEndBits |= cubicExactEnd(c1, true, c2) << 1; swap(); - intersectEnd(c2, false, c1, c1Bounds, false, *this); - intersectEnd(c2, true, c1, c1Bounds, false, *this); + exactEndBits |= cubicExactEnd(c2, false, c1) << 2; + exactEndBits |= cubicExactEnd(c2, true, c1) << 3; swap(); } - // if two ends intersect, check middle for coincidence - if (fUsed >= 2) { + if (cubicCheckCoincidence(c1, c2)) { SkASSERT(!selfIntersect); - int last = fUsed - 1; - double tRange1 = fT[0][last] - fT[0][0]; - double tRange2 = fT[1][last] - fT[1][0]; - for (int index = 1; index < 5; ++index) { - double testT1 = fT[0][0] + tRange1 * index / 5; - double testT2 = fT[1][0] + tRange2 * index / 5; - SkDPoint testPt1 = c1.ptAtT(testT1); - SkDPoint testPt2 = c2.ptAtT(testT2); - if (!testPt1.approximatelyEqual(testPt2)) { - goto skipCoincidence; - } + return fUsed; + } + // FIXME: pass in cached bounds from caller + SkDRect c1Bounds, c2Bounds; + c1Bounds.setBounds(c1); // OPTIMIZE use setRawBounds ? + c2Bounds.setBounds(c2); + if (!(exactEndBits & 1)) { + cubicNearEnd(c1, false, c2, c2Bounds); + } + if (!(exactEndBits & 2)) { + cubicNearEnd(c1, true, c2, c2Bounds); + } + if (!selfIntersect) { + swap(); + if (!(exactEndBits & 4)) { + cubicNearEnd(c2, false, c1, c1Bounds); } - if (fUsed > 2) { - fPt[1] = fPt[last]; - fT[0][1] = fT[0][last]; - fT[1][1] = fT[1][last]; - fUsed = 2; + if (!(exactEndBits & 8)) { + cubicNearEnd(c2, true, c1, c1Bounds); } - fIsCoincident[0] = fIsCoincident[1] = 0x03; + swap(); + } + if (cubicCheckCoincidence(c1, c2)) { + SkASSERT(!selfIntersect); return fUsed; } -skipCoincidence: ::intersect(c1, 0, 1, c2, 0, 1, 1, *this); // 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 @@ -501,9 +537,11 @@ skipCoincidence: } } if (match) { +#if DEBUG_CONCIDENT if (((match + 1) & match) != 0) { SkDebugf("%s coincident hole\n", __FUNCTION__); } +#endif // for now, assume that everything from start to finish is coincident if (fUsed > 2) { fPt[1] = fPt[last]; @@ -522,6 +560,7 @@ skipCoincidence: // OPTIMIZATION If this is a common use case, optimize by duplicating // the intersect 3 loop to avoid the promotion / demotion code int SkIntersections::intersect(const SkDCubic& cubic, const SkDQuad& quad) { + fMax = 6; SkDCubic up = quad.toCubic(); (void) intersect(cubic, up); return used(); @@ -535,6 +574,7 @@ describes a method to find the self intersection of a cubic by taking the gradie form dotted with the normal, and solving for the roots. My math foo is too poor to implement this.*/ int SkIntersections::intersect(const SkDCubic& c) { + fMax = 1; // check to see if x or y end points are the extrema. Are other quick rejects possible? if (c.endsAreExtremaInXOrY()) { return false; diff --git a/src/pathops/SkDCubicLineIntersection.cpp b/src/pathops/SkDCubicLineIntersection.cpp index 0abb75b394..e9997e45dd 100644 --- a/src/pathops/SkDCubicLineIntersection.cpp +++ b/src/pathops/SkDCubicLineIntersection.cpp @@ -86,6 +86,7 @@ public: , fLine(l) , fIntersections(i) , fAllowNear(true) { + i->setMax(3); } void allowNear(bool allow) { @@ -122,7 +123,24 @@ public: SkDebugf("%s pt=(%1.9g,%1.9g) cPt=(%1.9g,%1.9g)\n", __FUNCTION__, pt.fX, pt.fY, cPt.fX, cPt.fY); #endif + for (int inner = 0; inner < fIntersections->used(); ++inner) { + if (fIntersections->pt(inner) != pt) { + continue; + } + double existingCubicT = (*fIntersections)[0][inner]; + if (cubicT == existingCubicT) { + goto skipInsert; + } + // check if midway on cubic is also same point. If so, discard this + double cubicMidT = (existingCubicT + cubicT) / 2; + SkDPoint cubicMidPt = fCubic.ptAtT(cubicMidT); + if (cubicMidPt.approximatelyEqual(pt)) { + goto skipInsert; + } + } fIntersections->insert(cubicT, lineT, pt); + skipInsert: + ; } } return fIntersections->used(); diff --git a/src/pathops/SkDLineIntersection.cpp b/src/pathops/SkDLineIntersection.cpp index 4b818dcb97..fca0a04d1f 100644 --- a/src/pathops/SkDLineIntersection.cpp +++ b/src/pathops/SkDLineIntersection.cpp @@ -26,15 +26,44 @@ SkDPoint SkIntersections::Line(const SkDLine& a, const SkDLine& b) { return p; } -int SkIntersections::computePoints(const SkDLine& line, int used) { +void SkIntersections::cleanUpCoincidence() { + SkASSERT(fUsed == 2); + // both t values are good + bool startMatch = fT[0][0] == 0 && (fT[1][0] == 0 || fT[1][0] == 1); + bool endMatch = fT[0][1] == 1 && (fT[1][1] == 0 || fT[1][1] == 1); + if (startMatch || endMatch) { + removeOne(startMatch); + return; + } + // either t value is good + bool pStartMatch = fT[0][0] == 0 || fT[1][0] == 0 || fT[1][0] == 1; + bool pEndMatch = fT[0][1] == 1 || fT[1][1] == 0 || fT[1][1] == 1; + removeOne(pStartMatch || !pEndMatch); +} + +void SkIntersections::cleanUpParallelLines(bool parallel) { + while (fUsed > 2) { + removeOne(1); + } + if (fUsed == 2 && !parallel) { + bool startMatch = fT[0][0] == 0 || fT[1][0] == 0 || fT[1][0] == 1; + bool endMatch = fT[0][1] == 1 || fT[1][1] == 0 || fT[1][1] == 1; + if ((!startMatch && !endMatch) || approximately_equal(fT[0][0], fT[0][1])) { + SkASSERT(startMatch || endMatch); + removeOne(endMatch); + } + } +} + +void SkIntersections::computePoints(const SkDLine& line, int used) { fPt[0] = line.ptAtT(fT[0][0]); if ((fUsed = used) == 2) { fPt[1] = line.ptAtT(fT[0][1]); } - return fUsed; } int SkIntersections::intersectRay(const SkDLine& a, const SkDLine& b) { + fMax = 2; SkDVector aLen = a[1] - a[0]; SkDVector bLen = b[1] - b[0]; /* Slopes match when denom goes to zero: @@ -69,11 +98,13 @@ int SkIntersections::intersectRay(const SkDLine& a, const SkDLine& b) { fT[1][0] = fT[1][1] = 1; used = 2; } - return computePoints(a, used); + computePoints(a, used); + return fUsed; } // note that this only works if both lines are neither horizontal nor vertical int SkIntersections::intersect(const SkDLine& a, const SkDLine& b) { + fMax = 3; // note that we clean up so that there is no more than two in the end // see if end points intersect the opposite line double t; for (int iA = 0; iA < 2; ++iA) { @@ -103,8 +134,9 @@ int SkIntersections::intersect(const SkDLine& a, const SkDLine& b) { double ayBxLen = ayLen * bxLen; // detect parallel lines the same way here and in SkOpAngle operator < // so that non-parallel means they are also sortable - bool unparallel = NotAlmostEqualUlps(axByLen, ayBxLen); - if (unparallel) { + bool unparallel = fAllowNear ? NotAlmostEqualUlps(axByLen, ayBxLen) + : NotAlmostDequalUlps(axByLen, ayBxLen); + if (unparallel && fUsed == 0) { double ab0y = a[0].fY - b[0].fY; double ab0x = a[0].fX - b[0].fX; double numerA = ab0y * bxLen - byLen * ab0x; @@ -128,17 +160,8 @@ int SkIntersections::intersect(const SkDLine& a, const SkDLine& b) { } } } - while (fUsed > 2) { - removeOne(1); - } - if (fUsed == 2 && unparallel) { - bool startMatch = fT[0][0] == 0 || fT[1][0] == 0 || fT[1][0] == 1; - bool endMatch = fT[0][1] == 1 || fT[1][1] == 0 || fT[1][1] == 1; - if (!startMatch && !endMatch) { - SkASSERT(startMatch || endMatch); - removeOne(endMatch); - } - } + cleanUpParallelLines(!unparallel); + SkASSERT(fUsed <= 2); return fUsed; } @@ -162,6 +185,7 @@ static double horizontal_intercept(const SkDLine& line, double y) { } int SkIntersections::horizontal(const SkDLine& line, double y) { + fMax = 2; int horizontalType = horizontal_coincident(line, y); if (horizontalType == 1) { fT[0][0] = horizontal_intercept(line, y); @@ -174,6 +198,7 @@ int SkIntersections::horizontal(const SkDLine& line, double y) { int SkIntersections::horizontal(const SkDLine& line, double left, double right, double y, bool flipped) { + fMax = 2; // see if end points intersect the opposite line double t; const SkDPoint leftPt = { left, y }; @@ -203,26 +228,26 @@ int SkIntersections::horizontal(const SkDLine& line, double left, double right, fT[1][index] = 1 - fT[1][index]; } } - return computePoints(line, result); + computePoints(line, result); } } - if (!fAllowNear && result != 2) { - return fUsed; - } - if ((t = line.nearPoint(leftPt)) >= 0) { - insert(t, (double) flipped, leftPt); - } - if (left != right) { - const SkDPoint rightPt = { right, y }; - if ((t = line.nearPoint(rightPt)) >= 0) { - insert(t, (double) !flipped, rightPt); + if (fAllowNear || result == 2) { + if ((t = line.nearPoint(leftPt)) >= 0) { + insert(t, (double) flipped, leftPt); } - for (int index = 0; index < 2; ++index) { - if ((t = SkDLine::NearPointH(line[index], left, right, y)) >= 0) { - insert((double) index, flipped ? 1 - t : t, line[index]); + if (left != right) { + const SkDPoint rightPt = { right, y }; + if ((t = line.nearPoint(rightPt)) >= 0) { + insert(t, (double) !flipped, rightPt); + } + for (int index = 0; index < 2; ++index) { + if ((t = SkDLine::NearPointH(line[index], left, right, y)) >= 0) { + insert((double) index, flipped ? 1 - t : t, line[index]); + } } } } + cleanUpParallelLines(result == 2); return fUsed; } @@ -246,6 +271,7 @@ static double vertical_intercept(const SkDLine& line, double x) { } int SkIntersections::vertical(const SkDLine& line, double x) { + fMax = 2; int verticalType = vertical_coincident(line, x); if (verticalType == 1) { fT[0][0] = vertical_intercept(line, x); @@ -258,6 +284,7 @@ int SkIntersections::vertical(const SkDLine& line, double x) { int SkIntersections::vertical(const SkDLine& line, double top, double bottom, double x, bool flipped) { + fMax = 2; // see if end points intersect the opposite line double t; SkDPoint topPt = { x, top }; @@ -287,26 +314,26 @@ int SkIntersections::vertical(const SkDLine& line, double top, double bottom, fT[1][index] = 1 - fT[1][index]; } } - return computePoints(line, result); + computePoints(line, result); } } - if (!fAllowNear && result != 2) { - return fUsed; - } - if ((t = line.nearPoint(topPt)) >= 0) { - insert(t, (double) flipped, topPt); - } - if (top != bottom) { - SkDPoint bottomPt = { x, bottom }; - if ((t = line.nearPoint(bottomPt)) >= 0) { - insert(t, (double) !flipped, bottomPt); + if (fAllowNear || result == 2) { + if ((t = line.nearPoint(topPt)) >= 0) { + insert(t, (double) flipped, topPt); } - for (int index = 0; index < 2; ++index) { - if ((t = SkDLine::NearPointV(line[index], top, bottom, x)) >= 0) { - insert((double) index, flipped ? 1 - t : t, line[index]); + if (top != bottom) { + SkDPoint bottomPt = { x, bottom }; + if ((t = line.nearPoint(bottomPt)) >= 0) { + insert(t, (double) !flipped, bottomPt); + } + for (int index = 0; index < 2; ++index) { + if ((t = SkDLine::NearPointV(line[index], top, bottom, x)) >= 0) { + insert((double) index, flipped ? 1 - t : t, line[index]); + } } } } + cleanUpParallelLines(result == 2); return fUsed; } diff --git a/src/pathops/SkDQuadImplicit.cpp b/src/pathops/SkDQuadImplicit.cpp index 84ad452f8a..f0f66d1a10 100644 --- a/src/pathops/SkDQuadImplicit.cpp +++ b/src/pathops/SkDQuadImplicit.cpp @@ -103,7 +103,7 @@ bool SkDQuadImplicit::match(const SkDQuadImplicit& p2) const { if (first == index) { continue; } - if (!AlmostEqualUlps(fP[index] * p2.fP[first], fP[first] * p2.fP[index])) { + if (!AlmostDequalUlps(fP[index] * p2.fP[first], fP[first] * p2.fP[index])) { return false; } } diff --git a/src/pathops/SkDQuadIntersection.cpp b/src/pathops/SkDQuadIntersection.cpp index 5869d7db19..71ebf9abc0 100644 --- a/src/pathops/SkDQuadIntersection.cpp +++ b/src/pathops/SkDQuadIntersection.cpp @@ -139,7 +139,7 @@ static bool add_intercept(const SkDQuad& q1, const SkDQuad& q2, double tMin, dou return false; } SkDPoint pt2 = q1.ptAtT(rootTs[0][0]); - if (!pt2.approximatelyEqualHalf(mid)) { + if (!pt2.approximatelyEqual(mid)) { return false; } i->insertSwap(rootTs[0][0], tMid, pt2); @@ -249,31 +249,36 @@ static bool is_linear(const SkDQuad& q1, const SkDQuad& q2, SkIntersections* i) } // FIXME: if flat measure is sufficiently large, then probably the quartic solution failed -static void relaxed_is_linear(const SkDQuad& q1, const SkDQuad& q2, SkIntersections* i) { - double m1 = flat_measure(q1); - double m2 = flat_measure(q2); -#if DEBUG_FLAT_QUADS - double min = SkTMin(m1, m2); - if (min > 5) { - SkDebugf("%s maybe not flat enough.. %1.9g\n", __FUNCTION__, min); - } -#endif +// avoid imprecision incurred with chopAt +static void relaxed_is_linear(const SkDQuad* q1, double s1, double e1, const SkDQuad* q2, + double s2, double e2, SkIntersections* i) { + double m1 = flat_measure(*q1); + double m2 = flat_measure(*q2); i->reset(); - const SkDQuad& rounder = m2 < m1 ? q1 : q2; - const SkDQuad& flatter = m2 < m1 ? q2 : q1; + const SkDQuad* rounder, *flatter; + double sf, midf, ef, sr, er; + if (m2 < m1) { + rounder = q1; + sr = s1; + er = e1; + flatter = q2; + sf = s2; + midf = (s2 + e2) / 2; + ef = e2; + } else { + rounder = q2; + sr = s2; + er = e2; + flatter = q1; + sf = s1; + midf = (s1 + e1) / 2; + ef = e1; + } bool subDivide = false; - is_linear_inner(flatter, 0, 1, rounder, 0, 1, i, &subDivide); + is_linear_inner(*flatter, sf, ef, *rounder, sr, er, i, &subDivide); if (subDivide) { - SkDQuadPair pair = flatter.chopAt(0.5); - SkIntersections firstI, secondI; - relaxed_is_linear(pair.first(), rounder, &firstI); - for (int index = 0; index < firstI.used(); ++index) { - i->insert(firstI[0][index] * 0.5, firstI[1][index], firstI.pt(index)); - } - relaxed_is_linear(pair.second(), rounder, &secondI); - for (int index = 0; index < secondI.used(); ++index) { - i->insert(0.5 + secondI[0][index] * 0.5, secondI[1][index], secondI.pt(index)); - } + relaxed_is_linear(flatter, sf, midf, rounder, sr, er, i); + relaxed_is_linear(flatter, midf, ef, rounder, sr, er, i); } if (m2 < m1) { i->swapPts(); @@ -378,7 +383,7 @@ static void lookNearEnd(const SkDQuad& q1, const SkDQuad& q2, int testT, impTs.intersectRay(q1, tmpLine); for (int index = 0; index < impTs.used(); ++index) { SkDPoint realPt = impTs.pt(index); - if (!tmpLine[0].approximatelyEqualHalf(realPt)) { + if (!tmpLine[0].approximatelyEqual(realPt)) { continue; } if (swap) { @@ -390,6 +395,7 @@ static void lookNearEnd(const SkDQuad& q1, const SkDQuad& q2, int testT, } int SkIntersections::intersect(const SkDQuad& q1, const SkDQuad& q2) { + fMax = 4; // if the quads share an end point, check to see if they overlap for (int i1 = 0; i1 < 3; i1 += 2) { for (int i2 = 0; i2 < 3; i2 += 2) { @@ -401,7 +407,7 @@ int SkIntersections::intersect(const SkDQuad& q1, const SkDQuad& q2) { if (fAllowNear || true) { // FIXME ? cubic/cubic intersection fails without (cubicOp67u) for (int i1 = 0; i1 < 3; i1 += 2) { for (int i2 = 0; i2 < 3; i2 += 2) { - if (q1[i1] != q2[i2] && q1[i1].approximatelyEqualHalf(q2[i2])) { + if (q1[i1] != q2[i2] && q1[i1].approximatelyEqual(q2[i2])) { insertNear(i1 >> 1, i2 >> 1, q1[i1]); } } @@ -420,6 +426,7 @@ int SkIntersections::intersect(const SkDQuad& q1, const SkDQuad& q2) { return fUsed; } SkIntersections swapped; + swapped.setMax(fMax); if (is_linear(q2, q1, &swapped)) { swapped.swapPts(); set(swapped); @@ -484,7 +491,7 @@ int SkIntersections::intersect(const SkDQuad& q1, const SkDQuad& q2) { } if (r1Count == r2Count && r1Count <= 1) { if (r1Count == 1) { - if (pts1[0].approximatelyEqualHalf(pts2[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 @@ -506,7 +513,7 @@ int SkIntersections::intersect(const SkDQuad& q1, const SkDQuad& q2) { dist[index] = DBL_MAX; closest[index] = -1; for (int ndex2 = 0; ndex2 < r2Count; ++ndex2) { - if (!pts2[ndex2].approximatelyEqualHalf(pts1[index])) { + if (!pts2[ndex2].approximatelyEqual(pts1[index])) { continue; } double dx = pts2[ndex2].fX - pts1[index].fX; @@ -532,7 +539,7 @@ int SkIntersections::intersect(const SkDQuad& q1, const SkDQuad& q2) { } } if (r1Count && r2Count && !foundSomething) { - relaxed_is_linear(q1, q2, this); + relaxed_is_linear(&q1, 0, 1, &q2, 0, 1, this); return fUsed; } int used = 0; diff --git a/src/pathops/SkDQuadLineIntersection.cpp b/src/pathops/SkDQuadLineIntersection.cpp index b335c5a4b2..14d7d9cea0 100644 --- a/src/pathops/SkDQuadLineIntersection.cpp +++ b/src/pathops/SkDQuadLineIntersection.cpp @@ -99,6 +99,7 @@ public: , fLine(l) , fIntersections(i) , fAllowNear(true) { + i->setMax(2); } void allowNear(bool allow) { diff --git a/src/pathops/SkIntersectionHelper.h b/src/pathops/SkIntersectionHelper.h index af246b760e..1a4b1f0441 100644 --- a/src/pathops/SkIntersectionHelper.h +++ b/src/pathops/SkIntersectionHelper.h @@ -17,8 +17,8 @@ public: kCubic_Segment = SkPath::kCubic_Verb, }; - void addCoincident(SkIntersectionHelper& other, const SkIntersections& ts, bool swap) { - fContour->addCoincident(fIndex, other.fContour, other.fIndex, ts, swap); + bool addCoincident(SkIntersectionHelper& other, const SkIntersections& ts, bool swap) { + return fContour->addCoincident(fIndex, other.fContour, other.fIndex, ts, swap); } // FIXME: does it make sense to write otherIndex now if we're going to @@ -27,9 +27,10 @@ public: fContour->addOtherT(fIndex, index, otherT, otherIndex); } - void addPartialCoincident(SkIntersectionHelper& other, const SkIntersections& ts, int index, + bool addPartialCoincident(SkIntersectionHelper& other, const SkIntersections& ts, int index, bool swap) { - fContour->addPartialCoincident(fIndex, other.fContour, other.fIndex, ts, index, swap); + return fContour->addPartialCoincident(fIndex, other.fContour, other.fIndex, ts, index, + swap); } // Avoid collapsing t values that are close to the same since @@ -77,7 +78,7 @@ public: double mid = (t1 + t2) / 2; SkDPoint midPtByT = segment.dPtAtT(mid); SkDPoint midPtByAvg = SkDPoint::Mid(pt1, pt2); - return midPtByT.approximatelyEqualHalf(midPtByAvg); + return midPtByT.approximatelyEqual(midPtByAvg); } SkScalar left() const { diff --git a/src/pathops/SkIntersections.cpp b/src/pathops/SkIntersections.cpp index 3a5e24f0a7..608ffe3b6d 100644 --- a/src/pathops/SkIntersections.cpp +++ b/src/pathops/SkIntersections.cpp @@ -45,6 +45,7 @@ int SkIntersections::coincidentUsed() const { int SkIntersections::cubicRay(const SkPoint pts[4], const SkDLine& line) { SkDCubic cubic; cubic.set(pts); + fMax = 3; return intersectRay(cubic, line); } @@ -87,7 +88,12 @@ int SkIntersections::insert(double one, double two, const SkDPoint& pt) { break; } } - SkASSERT(fUsed < 9); + if (fUsed >= fMax) { + SkASSERT(0); // FIXME : this error, if it is to be handled at runtime in release, must + // be propagated all the way back down to the caller, and return failure. + fUsed = 0; + return 0; + } int remaining = fUsed - index; if (remaining > 0) { memmove(&fPt[index + 1], &fPt[index], sizeof(fPt[0]) * remaining); @@ -132,6 +138,7 @@ void SkIntersections::offset(int base, double start, double end) { int SkIntersections::quadRay(const SkPoint pts[3], const SkDLine& line) { SkDQuad quad; quad.set(pts); + fMax = 2; return intersectRay(quad, line); } diff --git a/src/pathops/SkIntersections.h b/src/pathops/SkIntersections.h index 389098d84e..f63a023ef0 100644 --- a/src/pathops/SkIntersections.h +++ b/src/pathops/SkIntersections.h @@ -25,6 +25,7 @@ public: sk_bzero(fIsCoincident, sizeof(fIsCoincident)); sk_bzero(&fIsNear, sizeof(fIsNear)); reset(); + fMax = 0; // require that the caller set the max } class TArray { @@ -43,6 +44,7 @@ public: memcpy(fIsCoincident, i.fIsCoincident, sizeof(fIsCoincident)); memcpy(&fIsNear, &i.fIsNear, sizeof(fIsNear)); fUsed = i.fUsed; + fMax = i.fMax; fSwap = i.fSwap; SkDEBUGCODE(fDepth = i.fDepth); } @@ -54,6 +56,7 @@ public: int cubic(const SkPoint a[4]) { SkDCubic cubic; cubic.set(a); + fMax = 1; // self intersect return intersect(cubic); } @@ -62,6 +65,7 @@ public: aCubic.set(a); SkDCubic bCubic; bCubic.set(b); + fMax = 9; return intersect(aCubic, bCubic); } @@ -69,12 +73,14 @@ public: bool flipped) { SkDCubic cubic; cubic.set(a); + fMax = 3; return horizontal(cubic, left, right, y, flipped); } int cubicVertical(const SkPoint a[4], SkScalar top, SkScalar bottom, SkScalar x, bool flipped) { SkDCubic cubic; cubic.set(a); + fMax = 3; return vertical(cubic, top, bottom, x, flipped); } @@ -83,6 +89,7 @@ public: cubic.set(a); SkDLine line; line.set(b); + fMax = 3; return intersect(cubic, line); } @@ -91,6 +98,7 @@ public: cubic.set(a); SkDQuad quad; quad.set(b); + fMax = 6; return intersect(cubic, quad); } @@ -119,12 +127,14 @@ public: bool flipped) { SkDLine line; line.set(a); + fMax = 2; return horizontal(line, left, right, y, flipped); } int lineVertical(const SkPoint a[2], SkScalar top, SkScalar bottom, SkScalar x, bool flipped) { SkDLine line; line.set(a); + fMax = 2; return vertical(line, top, bottom, x, flipped); } @@ -132,6 +142,7 @@ public: SkDLine aLine, bLine; aLine.set(a); bLine.set(b); + fMax = 2; return intersect(aLine, bLine); } @@ -143,12 +154,14 @@ public: bool flipped) { SkDQuad quad; quad.set(a); + fMax = 2; return horizontal(quad, left, right, y, flipped); } int quadVertical(const SkPoint a[3], SkScalar top, SkScalar bottom, SkScalar x, bool flipped) { SkDQuad quad; quad.set(a); + fMax = 2; return vertical(quad, top, bottom, x, flipped); } @@ -157,6 +170,7 @@ public: quad.set(a); SkDLine line; line.set(b); + fMax = 2; return intersect(quad, line); } @@ -165,18 +179,23 @@ public: aQuad.set(a); SkDQuad bQuad; bQuad.set(b); + fMax = 4; return intersect(aQuad, bQuad); } int quadRay(const SkPoint pts[3], const SkDLine& line); void removeOne(int index); - // leaves flip, swap alone + // leaves flip, swap, max alone void reset() { fAllowNear = true; fUsed = 0; } + void setMax(int max) { + fMax = max; + } + void swap() { fSwap ^= true; } @@ -200,6 +219,7 @@ public: } static double Axial(const SkDQuad& , const SkDPoint& , bool vertical); + void cleanUpCoincidence(); int coincidentUsed() const; int cubicRay(const SkPoint pts[4], const SkDLine& line); void flip(); @@ -246,7 +266,11 @@ public: } private: - int computePoints(const SkDLine& line, int used); + bool cubicCheckCoincidence(const SkDCubic& c1, const SkDCubic& c2); + bool cubicExactEnd(const SkDCubic& cubic1, bool start, const SkDCubic& cubic2); + void cubicNearEnd(const SkDCubic& cubic1, bool start, const SkDCubic& cubic2, const SkDRect& ); + void cleanUpParallelLines(bool parallel); + void computePoints(const SkDLine& line, int used); // used by addCoincident to remove ordinary intersections in range // void remove(double one, double two, const SkDPoint& startPt, const SkDPoint& endPt); @@ -255,6 +279,7 @@ private: uint16_t fIsCoincident[2]; // bit set for each curve's coincident T uint16_t fIsNear; // bit set for each T if 2nd curve's point is near but not equal to 1st unsigned char fUsed; + unsigned char fMax; bool fAllowNear; bool fSwap; #ifdef SK_DEBUG diff --git a/src/pathops/SkOpAngle.cpp b/src/pathops/SkOpAngle.cpp index c1e2eae831..5e1d9e745e 100644 --- a/src/pathops/SkOpAngle.cpp +++ b/src/pathops/SkOpAngle.cpp @@ -131,6 +131,9 @@ bool SkOpAngle::operator<(const SkOpAngle& rh) const { // this/lh: left-hand; r if (!SkDLine::NearRay(x, y, rx, ry) && x_ry != rx_y) { return COMPARE_RESULT("7 !fComputed && !rh.fComputed", x_ry < rx_y); } + if (fSide2 == 0 && rh.fSide2 == 0) { + return COMPARE_RESULT("7a !fComputed && !rh.fComputed", x_ry < rx_y); + } } else { // if the vector was a result of subdividing a curve, see if it is stable bool sloppy1 = x_ry < rx_y; @@ -142,8 +145,12 @@ bool SkOpAngle::operator<(const SkOpAngle& rh) const { // this/lh: left-hand; r } } } - if (fSide2 * rh.fSide2 == 0) { -// SkASSERT(fSide2 + rh.fSide2 != 0); // hitting this assert means coincidence was undetected + if (fSide2 * rh.fSide2 == 0) { // one is zero +#if DEBUG_ANGLE + if (fSide2 == rh.fSide2 && y_ry) { // both is zero; coincidence was undetected + SkDebugf("%s coincidence!\n", __FUNCTION__); + } +#endif return COMPARE_RESULT("9a fSide2 * rh.fSide2 == 0 ...", fSide2 < rh.fSide2); } // at this point, the initial tangent line is nearly coincident @@ -409,8 +416,15 @@ void SkOpAngle::setSpans() { #ifdef SK_DEBUG void SkOpAngle::dump() const { - SkDebugf("id=%d (%1.9g,%1.9g) start=%d (%1.9g) end=%d (%1.9g)\n", fSegment->debugID(), - fSegment->xAtT(fStart), fSegment->yAtT(fStart), fStart, fSegment->span(fStart).fT, - fEnd, fSegment->span(fEnd).fT); + const SkOpSpan& spanStart = fSegment->span(fStart); + const SkOpSpan& spanEnd = fSegment->span(fEnd); + const SkOpSpan& spanMin = fStart < fEnd ? spanStart : spanEnd; + SkDebugf("id=%d (%1.9g,%1.9g) start=%d (%1.9g) end=%d (%1.9g) sumWind=", + fSegment->debugID(), fSegment->xAtT(fStart), fSegment->yAtT(fStart), + fStart, spanStart.fT, fEnd, spanEnd.fT); + SkPathOpsDebug::WindingPrintf(spanMin.fWindSum); + SkDebugf(" oppWind="); + SkPathOpsDebug::WindingPrintf(spanMin.fOppSum), + SkDebugf(" done=%d\n", spanMin.fDone); } #endif diff --git a/src/pathops/SkOpContour.cpp b/src/pathops/SkOpContour.cpp index facba87f78..4aa12cd465 100644 --- a/src/pathops/SkOpContour.cpp +++ b/src/pathops/SkOpContour.cpp @@ -9,8 +9,17 @@ #include "SkPathWriter.h" #include "SkTSort.h" -void SkOpContour::addCoincident(int index, SkOpContour* other, int otherIndex, +bool SkOpContour::addCoincident(int index, SkOpContour* other, int otherIndex, const SkIntersections& ts, bool swap) { + SkPoint pt0 = ts.pt(0).asSkPoint(); + SkPoint pt1 = ts.pt(1).asSkPoint(); + if (pt0 == pt1) { + // FIXME: one could imagine a case where it would be incorrect to ignore this + // suppose two self-intersecting cubics overlap to be coincident -- + // this needs to check that by some measure the t values are far enough apart + // or needs to check to see if the self-intersection bit was set on the cubic segment + return false; + } SkCoincidence& coincidence = fCoincidences.push_back(); coincidence.fOther = other; coincidence.fSegments[0] = index; @@ -19,8 +28,9 @@ void SkOpContour::addCoincident(int index, SkOpContour* other, int otherIndex, coincidence.fTs[swap][1] = ts[0][1]; coincidence.fTs[!swap][0] = ts[1][0]; coincidence.fTs[!swap][1] = ts[1][1]; - coincidence.fPts[0] = ts.pt(0).asSkPoint(); - coincidence.fPts[1] = ts.pt(1).asSkPoint(); + coincidence.fPts[0] = pt0; + coincidence.fPts[1] = pt1; + return true; } SkOpSegment* SkOpContour::nonVerticalSegment(int* start, int* end) { @@ -57,8 +67,8 @@ void SkOpContour::addCoincidentPoints() { continue; } #if DEBUG_CONCIDENT - thisOne.debugShowTs(); - other.debugShowTs(); + thisOne.debugShowTs("-"); + other.debugShowTs("o"); #endif double startT = coincidence.fTs[0][0]; double endT = coincidence.fTs[0][1]; @@ -66,6 +76,15 @@ void SkOpContour::addCoincidentPoints() { if ((cancelers = startSwapped = startT > endT)) { SkTSwap(startT, endT); } + if (startT == endT) { // if one is very large the smaller may have collapsed to nothing + if (endT <= 1 - FLT_EPSILON) { + endT += FLT_EPSILON; + SkASSERT(endT <= 1); + } else { + startT -= FLT_EPSILON; + SkASSERT(startT >= 0); + } + } SkASSERT(!approximately_negative(endT - startT)); double oStartT = coincidence.fTs[1][0]; double oEndT = coincidence.fTs[1][1]; @@ -76,43 +95,57 @@ void SkOpContour::addCoincidentPoints() { SkASSERT(!approximately_negative(oEndT - oStartT)); if (cancelers) { // make sure startT and endT have t entries + const SkPoint& startPt = coincidence.fPts[startSwapped]; if (startT > 0 || oEndT < 1 - || thisOne.isMissing(startT) || other.isMissing(oEndT)) { - thisOne.addTPair(startT, &other, oEndT, true, coincidence.fPts[startSwapped]); + || thisOne.isMissing(startT, startPt) || other.isMissing(oEndT, startPt)) { + thisOne.addTPair(startT, &other, oEndT, true, startPt); } + const SkPoint& oStartPt = coincidence.fPts[oStartSwapped]; if (oStartT > 0 || endT < 1 - || thisOne.isMissing(endT) || other.isMissing(oStartT)) { - other.addTPair(oStartT, &thisOne, endT, true, coincidence.fPts[oStartSwapped]); + || thisOne.isMissing(endT, oStartPt) || other.isMissing(oStartT, oStartPt)) { + other.addTPair(oStartT, &thisOne, endT, true, oStartPt); } } else { + const SkPoint& startPt = coincidence.fPts[startSwapped]; if (startT > 0 || oStartT > 0 - || thisOne.isMissing(startT) || other.isMissing(oStartT)) { - thisOne.addTPair(startT, &other, oStartT, true, coincidence.fPts[startSwapped]); + || thisOne.isMissing(startT, startPt) || other.isMissing(oStartT, startPt)) { + thisOne.addTPair(startT, &other, oStartT, true, startPt); } + const SkPoint& oEndPt = coincidence.fPts[!oStartSwapped]; if (endT < 1 || oEndT < 1 - || thisOne.isMissing(endT) || other.isMissing(oEndT)) { - other.addTPair(oEndT, &thisOne, endT, true, coincidence.fPts[!oStartSwapped]); + || thisOne.isMissing(endT, oEndPt) || other.isMissing(oEndT, oEndPt)) { + other.addTPair(oEndT, &thisOne, endT, true, oEndPt); } } #if DEBUG_CONCIDENT - thisOne.debugShowTs(); - other.debugShowTs(); + thisOne.debugShowTs("+"); + other.debugShowTs("o"); #endif } } -void SkOpContour::addPartialCoincident(int index, SkOpContour* other, int otherIndex, +bool SkOpContour::addPartialCoincident(int index, SkOpContour* other, int otherIndex, const SkIntersections& ts, int ptIndex, bool swap) { + SkPoint pt0 = ts.pt(ptIndex).asSkPoint(); + SkPoint pt1 = ts.pt(ptIndex + 1).asSkPoint(); + if (SkDPoint::ApproximatelyEqual(pt0, pt1)) { + // FIXME: one could imagine a case where it would be incorrect to ignore this + // suppose two self-intersecting cubics overlap to form a partial coincidence -- + // although it isn't clear why the regular coincidence could wouldn't pick this up + // this is exceptional enough to ignore for now + return false; + } SkCoincidence& coincidence = fPartialCoincidences.push_back(); coincidence.fOther = other; coincidence.fSegments[0] = index; coincidence.fSegments[1] = otherIndex; - coincidence.fTs[swap][0] = ts[0][index]; - coincidence.fTs[swap][1] = ts[0][index + 1]; - coincidence.fTs[!swap][0] = ts[1][index]; - coincidence.fTs[!swap][1] = ts[1][index + 1]; - coincidence.fPts[0] = ts.pt(index).asSkPoint(); - coincidence.fPts[1] = ts.pt(index + 1).asSkPoint(); + coincidence.fTs[swap][0] = ts[0][ptIndex]; + coincidence.fTs[swap][1] = ts[0][ptIndex + 1]; + coincidence.fTs[!swap][0] = ts[1][ptIndex]; + coincidence.fTs[!swap][1] = ts[1][ptIndex + 1]; + coincidence.fPts[0] = pt0; + coincidence.fPts[1] = pt1; + return true; } void SkOpContour::calcCoincidentWinding() { @@ -162,6 +195,15 @@ void SkOpContour::calcCommonCoincidentWinding(const SkCoincidence& coincidence) SkTSwap<double>(startT, endT); SkTSwap<const SkPoint*>(startPt, endPt); } + if (startT == endT) { // if span is very large, the smaller may have collapsed to nothing + if (endT <= 1 - FLT_EPSILON) { + endT += FLT_EPSILON; + SkASSERT(endT <= 1); + } else { + startT -= FLT_EPSILON; + SkASSERT(startT >= 0); + } + } SkASSERT(!approximately_negative(endT - startT)); double oStartT = coincidence.fTs[1][0]; double oEndT = coincidence.fTs[1][1]; @@ -173,11 +215,11 @@ void SkOpContour::calcCommonCoincidentWinding(const SkCoincidence& coincidence) if (cancelers) { thisOne.addTCancel(*startPt, *endPt, &other); } else { - thisOne.addTCoincident(*startPt, *endPt, &other); + thisOne.addTCoincident(*startPt, *endPt, endT, &other); } #if DEBUG_CONCIDENT - thisOne.debugShowTs(); - other.debugShowTs(); + thisOne.debugShowTs("p"); + other.debugShowTs("o"); #endif } diff --git a/src/pathops/SkOpContour.h b/src/pathops/SkOpContour.h index a5635fe3d2..a4ec6d398f 100644 --- a/src/pathops/SkOpContour.h +++ b/src/pathops/SkOpContour.h @@ -36,7 +36,7 @@ public: : fBounds.fTop < rh.fBounds.fTop; } - void addCoincident(int index, SkOpContour* other, int otherIndex, + bool addCoincident(int index, SkOpContour* other, int otherIndex, const SkIntersections& ts, bool swap); void addCoincidentPoints(); @@ -63,7 +63,7 @@ public: fSegments[segIndex].addOtherT(tIndex, otherT, otherIndex); } - void addPartialCoincident(int index, SkOpContour* other, int otherIndex, + bool addPartialCoincident(int index, SkOpContour* other, int otherIndex, const SkIntersections& ts, int ptIndex, bool swap); int addQuad(const SkPoint pts[3]) { @@ -100,6 +100,9 @@ public: if (segment->verb() == SkPath::kLine_Verb) { continue; } + if (segment->done()) { + continue; // likely coincident, nothing to do + } segment->checkEnds(); } } diff --git a/src/pathops/SkOpSegment.cpp b/src/pathops/SkOpSegment.cpp index c0ef1f8e11..4d11eb39e8 100644 --- a/src/pathops/SkOpSegment.cpp +++ b/src/pathops/SkOpSegment.cpp @@ -417,6 +417,8 @@ int SkOpSegment::addT(SkOpSegment* other, const SkPoint& pt, double newT, bool i // binary search? int insertedAt = -1; size_t tCount = fTs.count(); + const SkPoint& firstPt = fPts[0]; + const SkPoint& lastPt = fPts[SkPathOpsVerbToPoints(fVerb)]; for (size_t index = 0; index < tCount; ++index) { // OPTIMIZATION: if there are three or more identical Ts, then // the fourth and following could be further insertion-sorted so @@ -424,10 +426,21 @@ int SkOpSegment::addT(SkOpSegment* other, const SkPoint& pt, double newT, bool i // This could later limit segment tests to the two adjacent // neighbors, although it doesn't help with determining which // circular direction to go in. - if (newT < fTs[index].fT) { + const SkOpSpan& span = fTs[index]; + if (newT < span.fT) { insertedAt = index; break; } + if (newT == span.fT) { + if (pt == span.fPt) { + insertedAt = index; + break; + } + if ((pt == firstPt && newT == 0) || (span.fPt == lastPt && newT == 1)) { + insertedAt = index; + break; + } + } } SkOpSpan* span; if (insertedAt >= 0) { @@ -502,6 +515,10 @@ int SkOpSegment::addT(SkOpSegment* other, const SkPoint& pt, double newT, bool i } double tEndInterval = span[more].fT - newT; if (precisely_negative(tEndInterval)) { + if ((span->fTiny = span[more].fTiny)) { + span->fDone = true; + ++fDoneSpans; + } break; } if (fVerb == SkPath::kCubic_Verb) { @@ -556,11 +573,16 @@ void SkOpSegment::addTCancel(const SkPoint& startPt, const SkPoint& endPt, SkOpS SkASSERT(index < fTs.count()); ++index; } + while (index > 0 && fTs[index].fT == fTs[index - 1].fT) { + --index; + } int oIndex = other->fTs.count(); while (startPt != other->fTs[--oIndex].fPt) { // look for startPt match SkASSERT(oIndex > 0); } - while (startPt == other->fTs[--oIndex].fPt) { // look for first point beyond match + double oStartT = other->fTs[oIndex].fT; + // look for first point beyond match + while (startPt == other->fTs[--oIndex].fPt || oStartT == other->fTs[oIndex].fT) { SkASSERT(oIndex > 0); } SkOpSpan* test = &fTs[index]; @@ -574,7 +596,9 @@ void SkOpSegment::addTCancel(const SkPoint& startPt, const SkPoint& endPt, SkOpS bool track = test->fWindValue || oTest->fWindValue; bool bigger = test->fWindValue >= oTest->fWindValue; const SkPoint& testPt = test->fPt; + double testT = test->fT; const SkPoint& oTestPt = oTest->fPt; + double oTestT = oTest->fT; do { if (decrement) { if (binary && bigger) { @@ -587,7 +611,7 @@ void SkOpSegment::addTCancel(const SkPoint& startPt, const SkPoint& endPt, SkOpS } SkASSERT(index < fTs.count() - 1); test = &fTs[++index]; - } while (testPt == test->fPt); + } while (testPt == test->fPt || testT == test->fT); SkDEBUGCODE(int originalWindValue = oTest->fWindValue); do { SkASSERT(oTest->fT < 1); @@ -605,9 +629,8 @@ void SkOpSegment::addTCancel(const SkPoint& startPt, const SkPoint& endPt, SkOpS break; } oTest = &other->fTs[--oIndex]; - } while (oTestPt == oTest->fPt); - SkASSERT(endPt != test->fPt || oTestPt == endPt); - } while (endPt != test->fPt); + } while (oTestPt == oTest->fPt || oTestT == oTest->fT); + } while (endPt != test->fPt && test->fT < 1); // FIXME: determine if canceled edges need outside ts added int outCount = outsidePts.count(); if (!done() && outCount) { @@ -645,7 +668,7 @@ void SkOpSegment::bumpCoincidentThis(const SkOpSpan& oTest, bool binary, int* in TrackOutside(outsideTs, oStartPt); } end = &fTs[++index]; - } while (end->fPt == test->fPt); + } while ((end->fPt == test->fPt || end->fT == test->fT) && end->fT < 1); *indexPtr = index; } @@ -685,10 +708,11 @@ void SkOpSegment::bumpCoincidentOther(const SkOpSpan& test, int* oIndexPtr, SkOpSpan* oEnd = oTest; const SkPoint& startPt = test.fPt; const SkPoint& oStartPt = oTest->fPt; - if (oStartPt == oEnd->fPt) { + double oStartT = oTest->fT; + if (oStartPt == oEnd->fPt || oStartT == oEnd->fT) { TrackOutside(oOutsidePts, startPt); } - while (oStartPt == oEnd->fPt) { + while (oStartPt == oEnd->fPt || oStartT == oEnd->fT) { zeroSpan(oEnd); oEnd = &fTs[++oIndex]; } @@ -704,7 +728,7 @@ void SkOpSegment::bumpCoincidentOther(const SkOpSpan& test, int* oIndexPtr, // set spans from start to end to increment the greater by one and decrement // the lesser -void SkOpSegment::addTCoincident(const SkPoint& startPt, const SkPoint& endPt, +void SkOpSegment::addTCoincident(const SkPoint& startPt, const SkPoint& endPt, double endT, SkOpSegment* other) { bool binary = fOperand != other->fOperand; int index = 0; @@ -712,15 +736,24 @@ void SkOpSegment::addTCoincident(const SkPoint& startPt, const SkPoint& endPt, SkASSERT(index < fTs.count()); ++index; } + double startT = fTs[index].fT; + while (index > 0 && fTs[index - 1].fT == startT) { + --index; + } int oIndex = 0; while (startPt != other->fTs[oIndex].fPt) { SkASSERT(oIndex < other->fTs.count()); ++oIndex; } + double oStartT = other->fTs[oIndex].fT; + while (oIndex > 0 && other->fTs[oIndex - 1].fT == oStartT) { + --oIndex; + } SkSTArray<kOutsideTrackedTCount, SkPoint, true> outsidePts; SkSTArray<kOutsideTrackedTCount, SkPoint, true> oOutsidePts; SkOpSpan* test = &fTs[index]; const SkPoint* testPt = &test->fPt; + double testT = test->fT; SkOpSpan* oTest = &other->fTs[oIndex]; const SkPoint* oTestPt = &oTest->fPt; SkASSERT(AlmostEqualUlps(*testPt, *oTestPt)); @@ -760,13 +793,31 @@ void SkOpSegment::addTCoincident(const SkPoint& startPt, const SkPoint& endPt, } test = &fTs[index]; testPt = &test->fPt; - if (endPt == *testPt) { + testT = test->fT; + if (endPt == *testPt || endT == testT) { break; } oTest = &other->fTs[oIndex]; oTestPt = &oTest->fPt; SkASSERT(AlmostEqualUlps(*testPt, *oTestPt)); } while (endPt != *oTestPt); + if (endPt != *testPt && endT != testT) { // in rare cases, one may have ended before the other + int lastWind = test[-1].fWindValue; + int lastOpp = test[-1].fOppValue; + bool zero = lastWind == 0 && lastOpp == 0; + do { + if (test->fWindValue || test->fOppValue) { + test->fWindValue = lastWind; + test->fOppValue = lastOpp; + if (zero) { + test->fDone = true; + ++fDoneSpans; + } + } + test = &fTs[++index]; + testPt = &test->fPt; + } while (endPt != *testPt); + } int outCount = outsidePts.count(); if (!done() && outCount) { addCoinOutsides(outsidePts[0], endPt, other); @@ -1325,7 +1376,7 @@ bool SkOpSegment::decrementSpan(SkOpSpan* span) { } bool SkOpSegment::bumpSpan(SkOpSpan* span, int windDelta, int oppDelta) { - SkASSERT(!span->fDone || span->fTiny); + SkASSERT(!span->fDone || span->fTiny || span->fSmall); span->fWindValue += windDelta; SkASSERT(span->fWindValue >= 0); span->fOppValue += oppDelta; @@ -1384,17 +1435,20 @@ void SkOpSegment::checkEnds() { } const SkOpSpan& peekSpan = other->fTs[peekIndex]; SkOpSegment* match = peekSpan.fOther; + if (match->done()) { + continue; // if the edge has already been eaten (likely coincidence), ignore it + } const double matchT = peekSpan.fOtherT; // see if any of the spans match the other spans for (int tIndex = tStart + 1; tIndex < tLast; ++tIndex) { const SkOpSpan& tSpan = fTs[tIndex]; if (tSpan.fOther == match) { if (tSpan.fOtherT == matchT) { - goto nextPeeker; + goto nextPeekIndex; } double midT = (tSpan.fOtherT + matchT) / 2; if (match->betweenPoints(midT, tSpan.fPt, peekSpan.fPt)) { - goto nextPeeker; + goto nextPeekIndex; } } } @@ -1414,18 +1468,22 @@ void SkOpSegment::checkEnds() { #endif // this segment is missing a entry that the other contains // remember so we can add the missing one and recompute the indices - MissingSpan& missing = missingSpans.push_back(); - SkDEBUGCODE(sk_bzero(&missing, sizeof(missing))); - missing.fCommand = MissingSpan::kAddMissing; - missing.fT = t; - missing.fOther = match; - missing.fOtherT = matchT; - missing.fPt = peekSpan.fPt; - } -nextPeeker: - ; + { + MissingSpan& missing = missingSpans.push_back(); + SkDEBUGCODE(sk_bzero(&missing, sizeof(missing))); + missing.fCommand = MissingSpan::kAddMissing; + missing.fT = t; + missing.fOther = match; + missing.fOtherT = matchT; + missing.fPt = peekSpan.fPt; + } + break; +nextPeekIndex: + ; + } } if (missingSpans.count() == 0) { + debugValidate(); return; } // if one end is near the other point, look for a coincident span @@ -1690,6 +1748,11 @@ SkOpSegment* SkOpSegment::findNextOp(SkTDArray<SkOpSpan*>* chase, int* nextStart SkSTArray<SkOpAngle::kStackBasedCount, SkOpAngle*, true> sorted; int calcWinding = computeSum(startIndex, end, SkOpAngle::kBinaryOpp, &angles, &sorted); bool sortable = calcWinding != SK_NaN32; + if (sortable && sorted.count() == 0) { + // if no edge has a computed winding sum, we can go no further + *unsortable = true; + return NULL; + } int angleCount = angles.count(); int firstIndex = findStartingEdge(sorted, startIndex, end); SkASSERT(!sortable || firstIndex >= 0); @@ -2204,14 +2267,17 @@ void SkOpSegment::initWinding(int start, int end, double tHit, int winding, SkSc } } (void) markAndChaseWinding(start, end, winding, oppWind); + // OPTIMIZATION: the reverse mark and chase could skip the first marking + (void) markAndChaseWinding(end, start, winding, oppWind); } // OPTIMIZE: successive calls could start were the last leaves off // or calls could specialize to walk forwards or backwards -bool SkOpSegment::isMissing(double startT) const { +bool SkOpSegment::isMissing(double startT, const SkPoint& pt) const { size_t tCount = fTs.count(); for (size_t index = 0; index < tCount; ++index) { - if (approximately_zero(startT - fTs[index].fT)) { + const SkOpSpan& span = fTs[index]; + if (approximately_zero(startT - span.fT) && pt == span.fPt) { return false; } } @@ -2352,9 +2418,10 @@ SkOpSpan* SkOpSegment::markAngle(int maxWinding, int sumWinding, bool activeAngl } #if DEBUG_WINDING if (last) { - SkDebugf("%s last id=%d windSum=%d small=%d\n", __FUNCTION__, - last->fOther->fTs[last->fOtherIndex].fOther->debugID(), last->fWindSum, - last->fSmall); + SkDebugf("%s last id=%d windSum=", __FUNCTION__, + last->fOther->fTs[last->fOtherIndex].fOther->debugID()); + SkPathOpsDebug::WindingPrintf(last->fWindSum); + SkDebugf(" small=%d\n", last->fSmall); } #endif return last; @@ -2377,9 +2444,10 @@ SkOpSpan* SkOpSegment::markAngle(int maxWinding, int sumWinding, int oppMaxWindi } #if DEBUG_WINDING if (last) { - SkDebugf("%s last id=%d windSum=%d small=%d\n", __FUNCTION__, - last->fOther->fTs[last->fOtherIndex].fOther->debugID(), last->fWindSum, - last->fSmall); + SkDebugf("%s last id=%d windSum=", __FUNCTION__, + last->fOther->fTs[last->fOtherIndex].fOther->debugID()); + SkPathOpsDebug::WindingPrintf(last->fWindSum); + SkDebugf(" small=%d\n", last->fSmall); } #endif return last; @@ -2491,7 +2559,7 @@ SkOpSpan* SkOpSegment::markOneWinding(const char* funName, int tIndex, int windi SkOpSpan* SkOpSegment::markOneWinding(const char* funName, int tIndex, int winding, int oppWinding) { SkOpSpan& span = fTs[tIndex]; - if (span.fDone) { + if (span.fDone && !span.fSmall) { return NULL; } #if DEBUG_MARK_DONE @@ -3134,6 +3202,9 @@ void SkOpSegment::zeroSpan(SkOpSpan* span) { SkASSERT(span->fWindValue > 0 || span->fOppValue != 0); span->fWindValue = 0; span->fOppValue = 0; + if (span->fTiny || span->fSmall) { + return; + } SkASSERT(!span->fDone); span->fDone = true; ++fDoneSpans; @@ -3162,8 +3233,8 @@ void SkOpSegment::debugAddTPair(double t, const SkOpSegment& other, double other #endif #if DEBUG_CONCIDENT -void SkOpSegment::debugShowTs() const { - SkDebugf("%s id=%d", __FUNCTION__, fID); +void SkOpSegment::debugShowTs(const char* prefix) const { + SkDebugf("%s %s id=%d", __FUNCTION__, prefix, fID); int lastWind = -1; int lastOpp = -1; double lastT = -1; diff --git a/src/pathops/SkOpSegment.h b/src/pathops/SkOpSegment.h index acb114dfc7..85531f5262 100644 --- a/src/pathops/SkOpSegment.h +++ b/src/pathops/SkOpSegment.h @@ -248,7 +248,8 @@ public: int addSelfT(SkOpSegment* other, const SkPoint& pt, double newT); int addT(SkOpSegment* other, const SkPoint& pt, double newT, bool isNear); void addTCancel(const SkPoint& startPt, const SkPoint& endPt, SkOpSegment* other); - void addTCoincident(const SkPoint& startPt, const SkPoint& endPt, SkOpSegment* other); + void addTCoincident(const SkPoint& startPt, const SkPoint& endPt, double endT, + SkOpSegment* other); void addTPair(double t, SkOpSegment* other, double otherT, bool borrowWind, const SkPoint& pt); bool betweenTs(int lesser, double testT, int greater) const; void checkEnds(); @@ -269,7 +270,7 @@ public: void initWinding(int start, int end); void initWinding(int start, int end, double tHit, int winding, SkScalar hitDx, int oppWind, SkScalar hitOppDx); - bool isMissing(double startT) const; + bool isMissing(double startT, const SkPoint& pt) const; bool isTiny(const SkOpAngle* angle) const; SkOpSpan* markAndChaseDoneBinary(int index, int endIndex); SkOpSpan* markAndChaseDoneUnary(int index, int endIndex); @@ -316,7 +317,7 @@ public: bool sortable); #endif #if DEBUG_CONCIDENT - void debugShowTs() const; + void debugShowTs(const char* prefix) const; #endif #if DEBUG_SHOW_WINDING int debugShowWindingValues(int slotCount, int ofInterest) const; diff --git a/src/pathops/SkPathOpsCommon.cpp b/src/pathops/SkPathOpsCommon.cpp index 7dd13a7fe8..4db60797ec 100644 --- a/src/pathops/SkPathOpsCommon.cpp +++ b/src/pathops/SkPathOpsCommon.cpp @@ -399,10 +399,6 @@ void MakeContourList(SkTArray<SkOpContour>& contours, SkTArray<SkOpContour*, tru SkTQSort<SkOpContour>(list.begin(), list.end() - 1); } -static bool approximatelyEqual(const SkPoint& a, const SkPoint& b) { - return AlmostEqualUlps(a.fX, b.fX) && AlmostEqualUlps(a.fY, b.fY); -} - class DistanceLessThan { public: DistanceLessThan(double* distances) : fDistances(distances) { } @@ -435,7 +431,7 @@ void Assemble(const SkPathWriter& path, SkPathWriter* simple) { const SkPoint& eEnd = eContour.end(); #if DEBUG_ASSEMBLE SkDebugf("%s contour", __FUNCTION__); - if (!approximatelyEqual(eStart, eEnd)) { + if (!SkDPoint::ApproximatelyEqual(eStart, eEnd)) { SkDebugf("[%d]", runs.count()); } else { SkDebugf(" "); @@ -443,7 +439,7 @@ void Assemble(const SkPathWriter& path, SkPathWriter* simple) { SkDebugf(" start=(%1.9g,%1.9g) end=(%1.9g,%1.9g)\n", eStart.fX, eStart.fY, eEnd.fX, eEnd.fY); #endif - if (approximatelyEqual(eStart, eEnd)) { + if (SkDPoint::ApproximatelyEqual(eStart, eEnd)) { eContour.toPath(simple); continue; } diff --git a/src/pathops/SkPathOpsCubic.cpp b/src/pathops/SkPathOpsCubic.cpp index 662219acf5..8e8ec47bf9 100644 --- a/src/pathops/SkPathOpsCubic.cpp +++ b/src/pathops/SkPathOpsCubic.cpp @@ -155,7 +155,7 @@ int SkDCubic::RootsReal(double A, double B, double C, double D, double s[3]) { if (approximately_zero(A + B + C + D)) { // 1 is one root int num = SkDQuad::RootsReal(A, A + B, -D, s); for (int i = 0; i < num; ++i) { - if (AlmostEqualUlps(s[i], 1)) { + if (AlmostDequalUlps(s[i], 1)) { return num; } } @@ -186,11 +186,11 @@ int SkDCubic::RootsReal(double A, double B, double C, double D, double s[3]) { *roots++ = r; r = neg2RootQ * cos((theta + 2 * PI) / 3) - adiv3; - if (!AlmostEqualUlps(s[0], r)) { + if (!AlmostDequalUlps(s[0], r)) { *roots++ = r; } r = neg2RootQ * cos((theta - 2 * PI) / 3) - adiv3; - if (!AlmostEqualUlps(s[0], r) && (roots - s == 1 || !AlmostEqualUlps(s[1], r))) { + if (!AlmostDequalUlps(s[0], r) && (roots - s == 1 || !AlmostDequalUlps(s[1], r))) { *roots++ = r; } } else { // we have 1 real root @@ -205,9 +205,9 @@ int SkDCubic::RootsReal(double A, double B, double C, double D, double s[3]) { } r = A - adiv3; *roots++ = r; - if (AlmostEqualUlps(R2, Q3)) { + if (AlmostDequalUlps(R2, Q3)) { r = -A / 2 - adiv3; - if (!AlmostEqualUlps(s[0], r)) { + if (!AlmostDequalUlps(s[0], r)) { *roots++ = r; } } diff --git a/src/pathops/SkPathOpsDebug.cpp b/src/pathops/SkPathOpsDebug.cpp index 0505965b46..e52e47beb2 100644 --- a/src/pathops/SkPathOpsDebug.cpp +++ b/src/pathops/SkPathOpsDebug.cpp @@ -89,6 +89,13 @@ void SkPathOpsDebug::DumpAngles(const SkTArray<SkOpAngle, true>& angles) { angles[index].dump(); } } + +void SkPathOpsDebug::DumpAngles(const SkTArray<SkOpAngle* , true>& angles) { + int count = angles.count(); + for (int index = 0; index < count; ++index) { + angles[index]->dump(); + } +} #endif // SK_DEBUG || !FORCE_RELEASE #ifdef SK_DEBUG @@ -132,4 +139,22 @@ void SkOpSpan::dump() const { } SkDebugf("\n"); } + +void Dump(const SkTArray<class SkOpAngle, true>& angles) { + SkPathOpsDebug::DumpAngles(angles); +} + +void Dump(const SkTArray<class SkOpAngle* , true>& angles) { + SkPathOpsDebug::DumpAngles(angles); +} + +void Dump(const SkTArray<class SkOpAngle, true>* angles) { + SkPathOpsDebug::DumpAngles(*angles); +} + +void Dump(const SkTArray<class SkOpAngle* , true>* angles) { + SkPathOpsDebug::DumpAngles(*angles); +} + #endif + diff --git a/src/pathops/SkPathOpsDebug.h b/src/pathops/SkPathOpsDebug.h index 912f2f5f50..4fabd4cb22 100644 --- a/src/pathops/SkPathOpsDebug.h +++ b/src/pathops/SkPathOpsDebug.h @@ -160,8 +160,15 @@ public: static void ShowPath(const SkPath& one, const SkPath& two, SkPathOp op, const char* name); #endif static void DumpAngles(const SkTArray<class SkOpAngle, true>& angles); + static void DumpAngles(const SkTArray<class SkOpAngle* , true>& angles); }; +// shorthand for calling from debugger +void Dump(const SkTArray<class SkOpAngle, true>& angles); +void Dump(const SkTArray<class SkOpAngle* , true>& angles); +void Dump(const SkTArray<class SkOpAngle, true>* angles); +void Dump(const SkTArray<class SkOpAngle* , true>* angles); + #endif // SK_DEBUG || !FORCE_RELEASE #endif diff --git a/src/pathops/SkPathOpsLine.cpp b/src/pathops/SkPathOpsLine.cpp index 1b548fcd30..1e74123abf 100644 --- a/src/pathops/SkPathOpsLine.cpp +++ b/src/pathops/SkPathOpsLine.cpp @@ -152,8 +152,6 @@ double SkDLine::NearPointH(const SkDPoint& xy, double left, double right, double if (!AlmostEqualUlps(largest, largest + dist)) { // is the dist within ULPS tolerance? return -1; } - t = SkPinT(t); - SkASSERT(between(0, t, 1)); return t; } @@ -189,8 +187,6 @@ double SkDLine::NearPointV(const SkDPoint& xy, double top, double bottom, double if (!AlmostEqualUlps(largest, largest + dist)) { // is the dist within ULPS tolerance? return -1; } - t = SkPinT(t); - SkASSERT(between(0, t, 1)); return t; } diff --git a/src/pathops/SkPathOpsOp.cpp b/src/pathops/SkPathOpsOp.cpp index e532fda3de..71ebef00b3 100644 --- a/src/pathops/SkPathOpsOp.cpp +++ b/src/pathops/SkPathOpsOp.cpp @@ -165,8 +165,8 @@ static bool bridgeOp(SkTArray<SkOpContour*, true>& contourList, const SkPathOp o #endif if (simple->isEmpty()) { simple->init(); - break; } + break; } SkASSERT(unsortable || !current->done()); int nextStart = index; diff --git a/src/pathops/SkPathOpsPoint.h b/src/pathops/SkPathOpsPoint.h index 51216b60ef..40688d8072 100644 --- a/src/pathops/SkPathOpsPoint.h +++ b/src/pathops/SkPathOpsPoint.h @@ -100,30 +100,40 @@ struct SkDPoint { // return approximately_equal(a.fY, fY) && approximately_equal(a.fX, fX); // because that will not take the magnitude of the values bool approximatelyEqual(const SkDPoint& a) const { - double denom = SkTMax(fabs(fX), SkTMax(fabs(fY), - SkTMax(fabs(a.fX), fabs(a.fY)))); - if (precisely_zero(denom)) { + if (approximately_equal(fX, a.fX) && approximately_equal(fY, a.fY)) { return true; } - double inv = 1 / denom; - return approximately_equal(fX * inv, a.fX * inv) - && approximately_equal(fY * inv, a.fY * inv); + 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 AlmostBequalUlps(largest, largest + dist); // is the dist within ULPS tolerance? } bool approximatelyEqual(const SkPoint& a) const { - return AlmostEqualUlps(SkDoubleToScalar(fX), a.fX) - && AlmostEqualUlps(SkDoubleToScalar(fY), a.fY); + SkDPoint dA; + dA.set(a); + return approximatelyEqual(dA); } - bool approximatelyEqualHalf(const SkDPoint& a) const { - double denom = SkTMax(fabs(fX), SkTMax(fabs(fY), - SkTMax(fabs(a.fX), fabs(a.fY)))); - if (denom == 0) { + static bool ApproximatelyEqual(const SkPoint& a, const SkPoint& b) { + if (approximately_equal(a.fX, b.fX) && approximately_equal(a.fY, b.fY)) { return true; } - double inv = 1 / denom; - return approximately_equal_half(fX * inv, a.fX * inv) - && approximately_equal_half(fY * inv, a.fY * inv); + if (!RoughlyEqualUlps(a.fX, b.fX) || !RoughlyEqualUlps(a.fY, b.fY)) { + return false; + } + SkDPoint dA, dB; + dA.set(a); + dB.set(b); + double dist = dA.distance(dB); // OPTIMIZATION: can we compare against distSq instead ? + float tiniest = SkTMin(SkTMin(SkTMin(a.fX, b.fX), a.fY), b.fY); + float largest = SkTMax(SkTMax(SkTMax(a.fX, b.fX), a.fY), b.fY); + largest = SkTMax(largest, -tiniest); + return AlmostBequalUlps((double) largest, largest + dist); // is dist within ULPS tolerance? } bool approximatelyZero() const { @@ -152,11 +162,18 @@ struct SkDPoint { return result; } - double moreRoughlyEqual(const SkDPoint& a) const { - return more_roughly_equal(a.fY, fY) && more_roughly_equal(a.fX, fX); + bool moreRoughlyEqual(const SkDPoint& a) const { + if (roughly_equal(fX, a.fX) && roughly_equal(fY, a.fY)) { + return true; + } + 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 RoughlyEqualUlps(largest, largest + dist); // is the dist within ULPS tolerance? } - double roughlyEqual(const SkDPoint& a) const { + bool roughlyEqual(const SkDPoint& a) const { return roughly_equal(a.fY, fY) && roughly_equal(a.fX, fX); } diff --git a/src/pathops/SkPathOpsQuad.cpp b/src/pathops/SkPathOpsQuad.cpp index 1bd7796d96..63e20388dd 100644 --- a/src/pathops/SkPathOpsQuad.cpp +++ b/src/pathops/SkPathOpsQuad.cpp @@ -122,7 +122,7 @@ int SkDQuad::RootsReal(const double A, const double B, const double C, double s[ } /* normal form: x^2 + px + q = 0 */ const double p2 = p * p; - if (!AlmostEqualUlps(p2, q) && p2 < q) { + if (!AlmostDequalUlps(p2, q) && p2 < q) { return 0; } double sqrt_D = 0; @@ -131,7 +131,7 @@ int SkDQuad::RootsReal(const double A, const double B, const double C, double s[ } s[0] = sqrt_D - p; s[1] = -sqrt_D - p; - return 1 + !AlmostEqualUlps(s[0], s[1]); + return 1 + !AlmostDequalUlps(s[0], s[1]); } bool SkDQuad::isLinear(int startIndex, int endIndex) const { diff --git a/src/pathops/SkPathOpsTypes.cpp b/src/pathops/SkPathOpsTypes.cpp index 2d7388b882..df73d11ce4 100644 --- a/src/pathops/SkPathOpsTypes.cpp +++ b/src/pathops/SkPathOpsTypes.cpp @@ -7,12 +7,30 @@ #include "SkFloatBits.h" #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; +} + // 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) { if (!SkScalarIsFinite(a) || !SkScalarIsFinite(b)) { return false; } + if (arguments_denormalized(a, b, epsilon)) { + return true; + } + int aBits = SkFloatAs2sCompliment(a); + int bBits = SkFloatAs2sCompliment(b); + // Find the difference in ULPs. + return aBits < bBits + epsilon && bBits < aBits + epsilon; +} + +static bool d_equal_ulps(float a, float b, int epsilon) { + if (!SkScalarIsFinite(a) || !SkScalarIsFinite(b)) { + return false; + } int aBits = SkFloatAs2sCompliment(a); int bBits = SkFloatAs2sCompliment(b); // Find the difference in ULPs. @@ -23,6 +41,19 @@ static bool not_equal_ulps(float a, float b, int epsilon) { if (!SkScalarIsFinite(a) || !SkScalarIsFinite(b)) { return false; } + if (arguments_denormalized(a, b, epsilon)) { + return false; + } + int aBits = SkFloatAs2sCompliment(a); + int bBits = SkFloatAs2sCompliment(b); + // Find the difference in ULPs. + return aBits >= bBits + epsilon || bBits >= aBits + epsilon; +} + +static bool d_not_equal_ulps(float a, float b, int epsilon) { + if (!SkScalarIsFinite(a) || !SkScalarIsFinite(b)) { + return false; + } int aBits = SkFloatAs2sCompliment(a); int bBits = SkFloatAs2sCompliment(b); // Find the difference in ULPs. @@ -33,6 +64,9 @@ static bool less_ulps(float a, float b, int epsilon) { if (!SkScalarIsFinite(a) || !SkScalarIsFinite(b)) { return false; } + if (arguments_denormalized(a, b, epsilon)) { + return a <= b - FLT_EPSILON * epsilon; + } int aBits = SkFloatAs2sCompliment(a); int bBits = SkFloatAs2sCompliment(b); // Find the difference in ULPs. @@ -43,6 +77,9 @@ static bool less_or_equal_ulps(float a, float b, int epsilon) { if (!SkScalarIsFinite(a) || !SkScalarIsFinite(b)) { return false; } + if (arguments_denormalized(a, b, epsilon)) { + return a < b + FLT_EPSILON * epsilon; + } int aBits = SkFloatAs2sCompliment(a); int bBits = SkFloatAs2sCompliment(b); // Find the difference in ULPs. @@ -55,6 +92,11 @@ bool AlmostBequalUlps(float a, float b) { return equal_ulps(a, b, UlpsEpsilon); } +bool AlmostDequalUlps(float a, float b) { + const int UlpsEpsilon = 16; + return d_equal_ulps(a, b, UlpsEpsilon); +} + bool AlmostEqualUlps(float a, float b) { const int UlpsEpsilon = 16; return equal_ulps(a, b, UlpsEpsilon); @@ -65,6 +107,11 @@ bool NotAlmostEqualUlps(float a, float b) { return not_equal_ulps(a, b, UlpsEpsilon); } +bool NotAlmostDequalUlps(float a, float b) { + const int UlpsEpsilon = 16; + return d_not_equal_ulps(a, b, UlpsEpsilon); +} + bool RoughlyEqualUlps(float a, float b) { const int UlpsEpsilon = 256; return equal_ulps(a, b, UlpsEpsilon); diff --git a/src/pathops/SkPathOpsTypes.h b/src/pathops/SkPathOpsTypes.h index bc39675d62..0ad10c2eba 100644 --- a/src/pathops/SkPathOpsTypes.h +++ b/src/pathops/SkPathOpsTypes.h @@ -28,11 +28,22 @@ inline bool AlmostEqualUlps(double a, double b) { return AlmostEqualUlps(SkDoubleToScalar(a), SkDoubleToScalar(b)); } +// Use Almost Dequal when comparing should not special case denormalized values. +bool AlmostDequalUlps(float a, float b); +inline bool AlmostDequalUlps(double a, double b) { + return AlmostDequalUlps(SkDoubleToScalar(a), SkDoubleToScalar(b)); +} + bool NotAlmostEqualUlps(float a, float b); inline bool NotAlmostEqualUlps(double a, double b) { return NotAlmostEqualUlps(SkDoubleToScalar(a), SkDoubleToScalar(b)); } +bool NotAlmostDequalUlps(float a, float b); +inline bool NotAlmostDequalUlps(double a, double b) { + return NotAlmostDequalUlps(SkDoubleToScalar(a), SkDoubleToScalar(b)); +} + // Use Almost Bequal when comparing coordinates in conjunction with between. bool AlmostBequalUlps(float a, float b); inline bool AlmostBequalUlps(double a, double b) { diff --git a/src/pathops/SkPathWriter.cpp b/src/pathops/SkPathWriter.cpp index 5559026119..46ec7b9131 100644 --- a/src/pathops/SkPathWriter.cpp +++ b/src/pathops/SkPathWriter.cpp @@ -90,7 +90,7 @@ void SkPathWriter::init() { } bool SkPathWriter::isClosed() const { - return !fEmpty && fFirstPt == fDefer[1]; + return !fEmpty && SkDPoint::ApproximatelyEqual(fFirstPt, fDefer[1]); } void SkPathWriter::lineTo() { diff --git a/src/pathops/SkQuarticRoot.cpp b/src/pathops/SkQuarticRoot.cpp index d3a6a781c7..dca96ded3a 100644 --- a/src/pathops/SkQuarticRoot.cpp +++ b/src/pathops/SkQuarticRoot.cpp @@ -152,7 +152,7 @@ int SkQuarticRootsReal(int firstCubicRoot, const double A, const double B, const // eliminate duplicates for (int i = 0; i < num - 1; ++i) { for (int j = i + 1; j < num; ) { - if (AlmostEqualUlps(s[i], s[j])) { + if (AlmostDequalUlps(s[i], s[j])) { if (j < --num) { s[j] = s[num]; } |