diff options
33 files changed, 949 insertions, 795 deletions
diff --git a/src/pathops/SkDCubicIntersection.cpp b/src/pathops/SkDCubicIntersection.cpp index 6e049708ac..19e7340cdc 100644 --- a/src/pathops/SkDCubicIntersection.cpp +++ b/src/pathops/SkDCubicIntersection.cpp @@ -114,26 +114,16 @@ static void intersect(const SkDCubic& cubic1, double t1s, double t1e, const SkDC #endif SkIntersections locals; intersectWithOrder(s1.fQuad, o1, s2.fQuad, o2, locals); - double coStart[2] = { -1 }; - SkDPoint coPoint; int tCount = locals.used(); for (int tIdx = 0; tIdx < tCount; ++tIdx) { double to1 = t1Start + (t1 - t1Start) * locals[0][tIdx]; double to2 = t2Start + (t2 - t2Start) * locals[1][tIdx]; // if the computed t is not sufficiently precise, iterate - SkDPoint p1 = cubic1.xyAtT(to1); - SkDPoint p2 = cubic2.xyAtT(to2); + SkDPoint p1 = cubic1.ptAtT(to1); + SkDPoint p2 = cubic2.ptAtT(to2); if (p1.approximatelyEqual(p2)) { - if (locals.isCoincident(tIdx)) { - if (coStart[0] < 0) { - coStart[0] = to1; - coStart[1] = to2; - coPoint = p1; - } else { - i.insertCoincidentPair(coStart[0], to1, coStart[1], to2, coPoint, p1); - coStart[0] = -1; - } - } else if (&cubic1 != &cubic2 || !approximately_equal(to1, to2)) { + SkASSERT(!locals.isCoincident(tIdx)); + if (&cubic1 != &cubic2 || !approximately_equal(to1, to2)) { if (i.swapped()) { // FIXME: insert should respect swap i.insert(to2, to1, p1); } else { @@ -250,7 +240,6 @@ static void intersect(const SkDCubic& cubic1, double t1s, double t1e, const SkDC // for that. } } - SkASSERT(coStart[0] == -1); t2Start = t2; } t1Start = t1; @@ -263,11 +252,34 @@ static void intersect(const SkDCubic& cubic1, double t1s, double t1e, const SkDC // 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, SkIntersections& i) { + const SkDRect& bounds2, bool selfIntersect, SkIntersections& i) { SkDLine line; int t1Index = start ? 0 : 3; + bool swap = i.swapped(); + double testT = (double) !start; + // 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; + } + } // don't bother if the two cubics are connnected -#if 1 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; @@ -297,9 +309,9 @@ static void intersectEnd(const SkDCubic& cubic1, bool start, const SkDCubic& cub } if (local.pt(idx2).approximatelyEqual(line[0])) { if (i.swapped()) { // FIXME: insert should respect swap - i.insert(foundT, start ? 0 : 1, line[0]); + i.insert(foundT, testT, line[0]); } else { - i.insert(start ? 0 : 1, foundT, line[0]); + i.insert(testT, foundT, line[0]); } } else { tVals.push_back(foundT); @@ -329,57 +341,6 @@ static void intersectEnd(const SkDCubic& cubic1, bool start, const SkDCubic& cub } tIdx = tLast + 1; } while (tIdx < tVals.count()); -#else - const SkDPoint& endPt = cubic1[t1Index]; - if (!bounds2.contains(endPt)) { - return; - } - // this variant looks for intersections within an 'x' of the endpoint - double delta = SkTMax(bounds2.width(), bounds2.height()); - for (int index = 0; index < 2; ++index) { - if (index == 0) { - line[0].fY = line[1].fY = endPt.fY; - line[0].fX = endPt.fX - delta; - line[1].fX = endPt.fX + delta; - } else { - line[0].fX = line[1].fX = cubic1[t1Index].fX; - line[0].fY = endPt.fY - delta; - line[1].fY = endPt.fY + delta; - } - SkIntersections local; - local.intersectRay(cubic2, line); // OPTIMIZE: special for horizontal/vertical lines - int used = local.used(); - for (int index = 0; index < used; ++index) { - double foundT = local[0][index]; - if (approximately_less_than_zero(foundT) || approximately_greater_than_one(foundT)) { - continue; - } - if (!local.pt(index).approximatelyEqual(endPt)) { - continue; - } - if (i.swapped()) { // FIXME: insert should respect swap - i.insert(foundT, start ? 0 : 1, endPt); - } else { - i.insert(start ? 0 : 1, foundT, endPt); - } - return; - } - } -// the above doesn't catch when the end of the cubic missed the other cubic because the quad -// approximation moved too far away, so something like the below is still needed. The enabled -// code above tries to avoid this heavy lifting unless the convex hull intersected the cubic. - double tMin1 = start ? 0 : 1 - LINE_FRACTION; - double tMax1 = start ? LINE_FRACTION : 1; - double tMin2 = SkTMax(foundT - LINE_FRACTION, 0.0); - double tMax2 = SkTMin(foundT + LINE_FRACTION, 1.0); - int lastUsed = i.used(); - intersect(cubic1, tMin1, tMax1, cubic2, tMin2, tMax2, 1, i); - if (lastUsed == i.used()) { - tMin2 = SkTMax(foundT - (1.0 / SkDCubic::gPrecisionUnit), 0.0); - tMax2 = SkTMin(foundT + (1.0 / SkDCubic::gPrecisionUnit), 1.0); - intersect(cubic1, tMin1, tMax1, cubic2, tMin2, tMax2, 1, i); - } -#endif return; } @@ -389,7 +350,7 @@ static bool closeStart(const SkDCubic& cubic, int cubicIndex, SkIntersections& i if (i[cubicIndex][0] != 0 || i[cubicIndex][1] > CLOSE_ENOUGH) { return false; } - pt = cubic.xyAtT((i[cubicIndex][0] + i[cubicIndex][1]) / 2); + pt = cubic.ptAtT((i[cubicIndex][0] + i[cubicIndex][1]) / 2); return true; } @@ -398,29 +359,120 @@ static bool closeEnd(const SkDCubic& cubic, int cubicIndex, SkIntersections& i, if (i[cubicIndex][last] != 1 || i[cubicIndex][last - 1] < 1 - CLOSE_ENOUGH) { return false; } - pt = cubic.xyAtT((i[cubicIndex][last] + i[cubicIndex][last - 1]) / 2); + pt = cubic.ptAtT((i[cubicIndex][last] + i[cubicIndex][last - 1]) / 2); return true; } +static bool only_end_pts_in_common(const SkDCubic& c1, const SkDCubic& c2) { +// the idea here is to see at minimum do a quick reject by rotating all points +// to either side of the line formed by connecting the endpoints +// if the opposite curves points are on the line or on the other side, the +// curves at most intersect at the endpoints + for (int oddMan = 0; oddMan < 4; ++oddMan) { + const SkDPoint* endPt[3]; + for (int opp = 1; opp < 4; ++opp) { + int end = oddMan ^ opp; // choose a value not equal to oddMan + endPt[opp - 1] = &c1[end]; + } + for (int triTest = 0; triTest < 3; ++triTest) { + double origX = endPt[triTest]->fX; + double origY = endPt[triTest]->fY; + int oppTest = triTest + 1; + if (3 == oppTest) { + oppTest = 0; + } + double adj = endPt[oppTest]->fX - origX; + double opp = endPt[oppTest]->fY - origY; + double sign = (c1[oddMan].fY - origY) * adj - (c1[oddMan].fX - origX) * opp; + if (approximately_zero(sign)) { + goto tryNextHalfPlane; + } + for (int n = 0; n < 4; ++n) { + double test = (c2[n].fY - origY) * adj - (c2[n].fX - origX) * opp; + if (test * sign > 0 && !precisely_zero(test)) { + goto tryNextHalfPlane; + } + } + } + return true; +tryNextHalfPlane: + ; + } + return false; +} + int SkIntersections::intersect(const SkDCubic& c1, const SkDCubic& c2) { - ::intersect(c1, 0, 1, c2, 0, 1, 1, *this); - // FIXME: pass in cached bounds from caller + bool selfIntersect = &c1 == &c2; + if (selfIntersect) { + if (c1[0].approximatelyEqualHalf(c1[3])) { + insert(0, 1, c1[0]); + } + } else { + for (int i1 = 0; i1 < 4; i1 += 3) { + for (int i2 = 0; i2 < 4; i2 += 3) { + if (c1[i1].approximatelyEqualHalf(c2[i2])) { + insert(i1 >> 1, i2 >> 1, c1[i1]); + } + } + } + } + SkASSERT(fUsed < 4); + if (!selfIntersect) { + if (only_end_pts_in_common(c1, c2)) { + return fUsed; + } + if (only_end_pts_in_common(c2, c1)) { + return fUsed; + } + } + // 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, *this); - intersectEnd(c1, true, c2, c2Bounds, *this); - bool selfIntersect = &c1 == &c2; - if (!selfIntersect) { + intersectEnd(c1, false, c2, c2Bounds, selfIntersect, *this); + intersectEnd(c1, true, c2, c2Bounds, selfIntersect, *this); + if (selfIntersect) { + if (fUsed) { + return fUsed; + } + } else { swap(); - intersectEnd(c2, false, c1, c1Bounds, *this); - intersectEnd(c2, true, c1, c1Bounds, *this); + intersectEnd(c2, false, c1, c1Bounds, false, *this); + intersectEnd(c2, true, c1, c1Bounds, false, *this); swap(); } + // if two ends intersect, check middle for coincidence + if (fUsed >= 2) { + 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; + } + } + 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 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 // intersected at the end and close to it. Verify that the second point is valid. - if (fUsed <= 1 || coincidentUsed()) { + if (fUsed <= 1) { return fUsed; } SkDPoint pt[2]; @@ -440,8 +492,8 @@ int SkIntersections::intersect(const SkDCubic& c1, const SkDCubic& c2) { for (int index = 0; index < last; ++index) { double mid1 = (fT[0][index] + fT[0][index + 1]) / 2; double mid2 = (fT[1][index] + fT[1][index + 1]) / 2; - pt[0] = c1.xyAtT(mid1); - pt[1] = c2.xyAtT(mid2); + pt[0] = c1.ptAtT(mid1); + pt[1] = c2.ptAtT(mid2); if (pt[0].approximatelyEqual(pt[1])) { match |= 1 << index; } diff --git a/src/pathops/SkDCubicLineIntersection.cpp b/src/pathops/SkDCubicLineIntersection.cpp index dc80479f60..a891abec66 100644 --- a/src/pathops/SkDCubicLineIntersection.cpp +++ b/src/pathops/SkDCubicLineIntersection.cpp @@ -76,250 +76,252 @@ For horizontal lines: class LineCubicIntersections { public: + enum PinTPoint { + kPointUninitialized, + kPointInitialized + }; + + LineCubicIntersections(const SkDCubic& c, const SkDLine& l, SkIntersections* i) + : fCubic(c) + , fLine(l) + , fIntersections(i) + , fAllowNear(true) { + } -LineCubicIntersections(const SkDCubic& c, const SkDLine& l, SkIntersections& i) - : cubic(c) - , line(l) - , intersections(i) - , fAllowNear(true) { -} - -void allowNear(bool allow) { - fAllowNear = allow; -} - -// see parallel routine in line quadratic intersections -int intersectRay(double roots[3]) { - double adj = line[1].fX - line[0].fX; - double opp = line[1].fY - line[0].fY; - SkDCubic r; - for (int n = 0; n < 4; ++n) { - r[n].fX = (cubic[n].fY - line[0].fY) * adj - (cubic[n].fX - line[0].fX) * opp; + void allowNear(bool allow) { + fAllowNear = allow; } - double A, B, C, D; - SkDCubic::Coefficients(&r[0].fX, &A, &B, &C, &D); - return SkDCubic::RootsValidT(A, B, C, D, roots); -} -int intersect() { - addExactEndPoints(); - double rootVals[3]; - int roots = intersectRay(rootVals); - for (int index = 0; index < roots; ++index) { - double cubicT = rootVals[index]; - double lineT = findLineT(cubicT); - if (pinTs(&cubicT, &lineT)) { - SkDPoint pt = line.xyAtT(lineT); -#if ONE_OFF_DEBUG - SkDPoint cPt = cubic.xyAtT(cubicT); - SkDebugf("%s pt=(%1.9g,%1.9g) cPt=(%1.9g,%1.9g)\n", __FUNCTION__, pt.fX, pt.fY, - cPt.fX, cPt.fY); -#endif - intersections.insert(cubicT, lineT, pt); + // see parallel routine in line quadratic intersections + int intersectRay(double roots[3]) { + double adj = fLine[1].fX - fLine[0].fX; + double opp = fLine[1].fY - fLine[0].fY; + SkDCubic r; + for (int n = 0; n < 4; ++n) { + r[n].fX = (fCubic[n].fY - fLine[0].fY) * adj - (fCubic[n].fX - fLine[0].fX) * opp; } + double A, B, C, D; + SkDCubic::Coefficients(&r[0].fX, &A, &B, &C, &D); + return SkDCubic::RootsValidT(A, B, C, D, roots); } - if (fAllowNear) { - addNearEndPoints(); - } - return intersections.used(); -} -int horizontalIntersect(double axisIntercept, double roots[3]) { - double A, B, C, D; - SkDCubic::Coefficients(&cubic[0].fY, &A, &B, &C, &D); - D -= axisIntercept; - return SkDCubic::RootsValidT(A, B, C, D, roots); -} - -int horizontalIntersect(double axisIntercept, double left, double right, bool flipped) { - addExactHorizontalEndPoints(left, right, axisIntercept); - double rootVals[3]; - int roots = horizontalIntersect(axisIntercept, rootVals); - for (int index = 0; index < roots; ++index) { - double cubicT = rootVals[index]; - SkDPoint pt = cubic.xyAtT(cubicT); - double lineT = (pt.fX - left) / (right - left); - if (pinTs(&cubicT, &lineT)) { - intersections.insert(cubicT, lineT, pt); + int intersect() { + addExactEndPoints(); + double rootVals[3]; + int roots = intersectRay(rootVals); + for (int index = 0; index < roots; ++index) { + double cubicT = rootVals[index]; + double lineT = findLineT(cubicT); + SkDPoint pt; + if (pinTs(&cubicT, &lineT, &pt, kPointUninitialized)) { + #if ONE_OFF_DEBUG + SkDPoint cPt = fCubic.ptAtT(cubicT); + SkDebugf("%s pt=(%1.9g,%1.9g) cPt=(%1.9g,%1.9g)\n", __FUNCTION__, pt.fX, pt.fY, + cPt.fX, cPt.fY); + #endif + fIntersections->insert(cubicT, lineT, pt); + } } + if (fAllowNear) { + addNearEndPoints(); + } + return fIntersections->used(); } - if (fAllowNear) { - addNearHorizontalEndPoints(left, right, axisIntercept); - } - if (flipped) { - intersections.flip(); - } - return intersections.used(); -} -int verticalIntersect(double axisIntercept, double roots[3]) { - double A, B, C, D; - SkDCubic::Coefficients(&cubic[0].fX, &A, &B, &C, &D); - D -= axisIntercept; - return SkDCubic::RootsValidT(A, B, C, D, roots); -} + int horizontalIntersect(double axisIntercept, double roots[3]) { + double A, B, C, D; + SkDCubic::Coefficients(&fCubic[0].fY, &A, &B, &C, &D); + D -= axisIntercept; + return SkDCubic::RootsValidT(A, B, C, D, roots); + } -int verticalIntersect(double axisIntercept, double top, double bottom, bool flipped) { - addExactVerticalEndPoints(top, bottom, axisIntercept); - double rootVals[3]; - int roots = verticalIntersect(axisIntercept, rootVals); - for (int index = 0; index < roots; ++index) { - double cubicT = rootVals[index]; - SkDPoint pt = cubic.xyAtT(cubicT); - double lineT = (pt.fY - top) / (bottom - top); - if (pinTs(&cubicT, &lineT)) { - intersections.insert(cubicT, lineT, pt); + int horizontalIntersect(double axisIntercept, double left, double right, bool flipped) { + addExactHorizontalEndPoints(left, right, axisIntercept); + double rootVals[3]; + int roots = horizontalIntersect(axisIntercept, rootVals); + for (int index = 0; index < roots; ++index) { + double cubicT = rootVals[index]; + SkDPoint pt = fCubic.ptAtT(cubicT); + double lineT = (pt.fX - left) / (right - left); + if (pinTs(&cubicT, &lineT, &pt, kPointInitialized)) { + fIntersections->insert(cubicT, lineT, pt); + } + } + if (fAllowNear) { + addNearHorizontalEndPoints(left, right, axisIntercept); } + if (flipped) { + fIntersections->flip(); + } + return fIntersections->used(); } - if (fAllowNear) { - addNearVerticalEndPoints(top, bottom, axisIntercept); + + int verticalIntersect(double axisIntercept, double roots[3]) { + double A, B, C, D; + SkDCubic::Coefficients(&fCubic[0].fX, &A, &B, &C, &D); + D -= axisIntercept; + return SkDCubic::RootsValidT(A, B, C, D, roots); } - if (flipped) { - intersections.flip(); + + int verticalIntersect(double axisIntercept, double top, double bottom, bool flipped) { + addExactVerticalEndPoints(top, bottom, axisIntercept); + double rootVals[3]; + int roots = verticalIntersect(axisIntercept, rootVals); + for (int index = 0; index < roots; ++index) { + double cubicT = rootVals[index]; + SkDPoint pt = fCubic.ptAtT(cubicT); + double lineT = (pt.fY - top) / (bottom - top); + if (pinTs(&cubicT, &lineT, &pt, kPointInitialized)) { + fIntersections->insert(cubicT, lineT, pt); + } + } + if (fAllowNear) { + addNearVerticalEndPoints(top, bottom, axisIntercept); + } + if (flipped) { + fIntersections->flip(); + } + return fIntersections->used(); } - return intersections.used(); -} -protected: + protected: -void addExactEndPoints() { - for (int cIndex = 0; cIndex < 4; cIndex += 3) { - double lineT = line.exactPoint(cubic[cIndex]); - if (lineT < 0) { - continue; + void addExactEndPoints() { + for (int cIndex = 0; cIndex < 4; cIndex += 3) { + double lineT = fLine.exactPoint(fCubic[cIndex]); + if (lineT < 0) { + continue; + } + double cubicT = (double) (cIndex >> 1); + fIntersections->insert(cubicT, lineT, fCubic[cIndex]); } - double cubicT = (double) (cIndex >> 1); - intersections.insert(cubicT, lineT, cubic[cIndex]); } -} -void addNearEndPoints() { - for (int cIndex = 0; cIndex < 4; cIndex += 3) { - double cubicT = (double) (cIndex >> 1); - if (intersections.hasT(cubicT)) { - continue; + void addNearEndPoints() { + for (int cIndex = 0; cIndex < 4; cIndex += 3) { + double cubicT = (double) (cIndex >> 1); + if (fIntersections->hasT(cubicT)) { + continue; + } + double lineT = fLine.nearPoint(fCubic[cIndex]); + if (lineT < 0) { + continue; + } + fIntersections->insert(cubicT, lineT, fCubic[cIndex]); } - double lineT = line.nearPoint(cubic[cIndex]); - if (lineT < 0) { - continue; - } - intersections.insert(cubicT, lineT, cubic[cIndex]); } -} -void addExactHorizontalEndPoints(double left, double right, double y) { - for (int cIndex = 0; cIndex < 4; cIndex += 3) { - double lineT = SkDLine::ExactPointH(cubic[cIndex], left, right, y); - if (lineT < 0) { - continue; + void addExactHorizontalEndPoints(double left, double right, double y) { + for (int cIndex = 0; cIndex < 4; cIndex += 3) { + double lineT = SkDLine::ExactPointH(fCubic[cIndex], left, right, y); + if (lineT < 0) { + continue; + } + double cubicT = (double) (cIndex >> 1); + fIntersections->insert(cubicT, lineT, fCubic[cIndex]); } - double cubicT = (double) (cIndex >> 1); - intersections.insert(cubicT, lineT, cubic[cIndex]); } -} -void addNearHorizontalEndPoints(double left, double right, double y) { - for (int cIndex = 0; cIndex < 4; cIndex += 3) { - double cubicT = (double) (cIndex >> 1); - if (intersections.hasT(cubicT)) { - continue; + void addNearHorizontalEndPoints(double left, double right, double y) { + for (int cIndex = 0; cIndex < 4; cIndex += 3) { + double cubicT = (double) (cIndex >> 1); + if (fIntersections->hasT(cubicT)) { + continue; + } + double lineT = SkDLine::NearPointH(fCubic[cIndex], left, right, y); + if (lineT < 0) { + continue; + } + fIntersections->insert(cubicT, lineT, fCubic[cIndex]); } - double lineT = SkDLine::NearPointH(cubic[cIndex], left, right, y); - if (lineT < 0) { - continue; - } - intersections.insert(cubicT, lineT, cubic[cIndex]); + // FIXME: see if line end is nearly on cubic } - // FIXME: see if line end is nearly on cubic -} -void addExactVerticalEndPoints(double top, double bottom, double x) { - for (int cIndex = 0; cIndex < 4; cIndex += 3) { - double lineT = SkDLine::ExactPointV(cubic[cIndex], top, bottom, x); - if (lineT < 0) { - continue; + void addExactVerticalEndPoints(double top, double bottom, double x) { + for (int cIndex = 0; cIndex < 4; cIndex += 3) { + double lineT = SkDLine::ExactPointV(fCubic[cIndex], top, bottom, x); + if (lineT < 0) { + continue; + } + double cubicT = (double) (cIndex >> 1); + fIntersections->insert(cubicT, lineT, fCubic[cIndex]); } - double cubicT = (double) (cIndex >> 1); - intersections.insert(cubicT, lineT, cubic[cIndex]); } -} -void addNearVerticalEndPoints(double top, double bottom, double x) { - for (int cIndex = 0; cIndex < 4; cIndex += 3) { - double cubicT = (double) (cIndex >> 1); - if (intersections.hasT(cubicT)) { - continue; + void addNearVerticalEndPoints(double top, double bottom, double x) { + for (int cIndex = 0; cIndex < 4; cIndex += 3) { + double cubicT = (double) (cIndex >> 1); + if (fIntersections->hasT(cubicT)) { + continue; + } + double lineT = SkDLine::NearPointV(fCubic[cIndex], top, bottom, x); + if (lineT < 0) { + continue; + } + fIntersections->insert(cubicT, lineT, fCubic[cIndex]); } - double lineT = SkDLine::NearPointV(cubic[cIndex], top, bottom, x); - if (lineT < 0) { - continue; - } - intersections.insert(cubicT, lineT, cubic[cIndex]); + // FIXME: see if line end is nearly on cubic } - // FIXME: see if line end is nearly on cubic -} -double findLineT(double t) { - SkDPoint xy = cubic.xyAtT(t); - double dx = line[1].fX - line[0].fX; - double dy = line[1].fY - line[0].fY; - if (fabs(dx) > fabs(dy)) { - return (xy.fX - line[0].fX) / dx; + double findLineT(double t) { + SkDPoint xy = fCubic.ptAtT(t); + double dx = fLine[1].fX - fLine[0].fX; + double dy = fLine[1].fY - fLine[0].fY; + if (fabs(dx) > fabs(dy)) { + return (xy.fX - fLine[0].fX) / dx; + } + return (xy.fY - fLine[0].fY) / dy; } - return (xy.fY - line[0].fY) / dy; -} -static bool pinTs(double* cubicT, double* lineT) { - if (!approximately_one_or_less(*lineT)) { - return false; - } - if (!approximately_zero_or_more(*lineT)) { - return false; - } - if (precisely_less_than_zero(*cubicT)) { - *cubicT = 0; - } else if (precisely_greater_than_one(*cubicT)) { - *cubicT = 1; - } - if (precisely_less_than_zero(*lineT)) { - *lineT = 0; - } else if (precisely_greater_than_one(*lineT)) { - *lineT = 1; + bool pinTs(double* cubicT, double* lineT, SkDPoint* pt, PinTPoint ptSet) { + if (!approximately_one_or_less(*lineT)) { + return false; + } + if (!approximately_zero_or_more(*lineT)) { + return false; + } + double cT = *cubicT = SkPinT(*cubicT); + double lT = *lineT = SkPinT(*lineT); + if (lT == 0 || lT == 1 || (ptSet == kPointUninitialized && cT != 0 && cT != 1)) { + *pt = fLine.ptAtT(lT); + } else if (ptSet == kPointUninitialized) { + *pt = fCubic.ptAtT(cT); + } + return true; } - return true; -} private: - -const SkDCubic& cubic; -const SkDLine& line; -SkIntersections& intersections; -bool fAllowNear; + const SkDCubic& fCubic; + const SkDLine& fLine; + SkIntersections* fIntersections; + bool fAllowNear; }; int SkIntersections::horizontal(const SkDCubic& cubic, double left, double right, double y, bool flipped) { - LineCubicIntersections c(cubic, *(static_cast<SkDLine*>(0)), *this); + SkDLine line = {{{ left, y }, { right, y }}}; + LineCubicIntersections c(cubic, line, this); return c.horizontalIntersect(y, left, right, flipped); } int SkIntersections::vertical(const SkDCubic& cubic, double top, double bottom, double x, bool flipped) { - LineCubicIntersections c(cubic, *(static_cast<SkDLine*>(0)), *this); + SkDLine line = {{{ x, top }, { x, bottom }}}; + LineCubicIntersections c(cubic, line, this); return c.verticalIntersect(x, top, bottom, flipped); } int SkIntersections::intersect(const SkDCubic& cubic, const SkDLine& line) { - LineCubicIntersections c(cubic, line, *this); + LineCubicIntersections c(cubic, line, this); c.allowNear(fAllowNear); return c.intersect(); } int SkIntersections::intersectRay(const SkDCubic& cubic, const SkDLine& line) { - LineCubicIntersections c(cubic, line, *this); + LineCubicIntersections c(cubic, line, this); fUsed = c.intersectRay(fT[0]); for (int index = 0; index < fUsed; ++index) { - fPt[index] = cubic.xyAtT(fT[0][index]); + fPt[index] = cubic.ptAtT(fT[0][index]); } return fUsed; } diff --git a/src/pathops/SkDLineIntersection.cpp b/src/pathops/SkDLineIntersection.cpp index faa7c1d392..46118429cd 100644 --- a/src/pathops/SkDLineIntersection.cpp +++ b/src/pathops/SkDLineIntersection.cpp @@ -27,9 +27,9 @@ SkDPoint SkIntersections::Line(const SkDLine& a, const SkDLine& b) { } int SkIntersections::computePoints(const SkDLine& line, int used) { - fPt[0] = line.xyAtT(fT[0][0]); + fPt[0] = line.ptAtT(fT[0][0]); if ((fUsed = used) == 2) { - fPt[1] = line.xyAtT(fT[0][1]); + fPt[1] = line.ptAtT(fT[0][1]); } return fUsed; } @@ -102,19 +102,24 @@ int SkIntersections::intersect(const SkDLine& a, const SkDLine& b) { byLen * axLen == ayLen * bxLen byLen * axLen - ayLen * bxLen == 0 ( == denom ) */ - double denom = byLen * axLen - ayLen * bxLen; - if (0 != denom) { + double axByLen = axLen * byLen; + 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 parallel = AlmostEqualUlps(axByLen, ayBxLen); + if (!parallel) { double ab0y = a[0].fY - b[0].fY; double ab0x = a[0].fX - b[0].fX; double numerA = ab0y * bxLen - byLen * ab0x; double numerB = ab0y * axLen - ayLen * ab0x; + double denom = axByLen - ayBxLen; if (between(0, numerA, denom) && between(0, numerB, denom)) { fT[0][0] = numerA / denom; fT[1][0] = numerB / denom; - return computePoints(a, 1); + computePoints(a, 1); } } - if (fAllowNear || 0 == denom) { + if (fAllowNear || parallel) { for (int iA = 0; iA < 2; ++iA) { if ((t = b.nearPoint(a[iA])) >= 0) { insert(iA, t, a[iA]); diff --git a/src/pathops/SkDQuadIntersection.cpp b/src/pathops/SkDQuadIntersection.cpp index 124c7dab06..e10fb3f139 100644 --- a/src/pathops/SkDQuadIntersection.cpp +++ b/src/pathops/SkDQuadIntersection.cpp @@ -87,8 +87,8 @@ static bool only_end_pts_in_common(const SkDQuad& q1, const SkDQuad& q2) { for (int oddMan = 0; oddMan < 3; ++oddMan) { const SkDPoint* endPt[2]; for (int opp = 1; opp < 3; ++opp) { - int end = oddMan ^ opp; - if (end == 3) { + int end = oddMan ^ opp; // choose a value not equal to oddMan + if (3 == end) { // and correct so that largest value is 1 or 2 end = opp; } endPt[opp - 1] = &q1[end]; @@ -120,7 +120,7 @@ tryNextHalfPlane: static bool add_intercept(const SkDQuad& q1, const SkDQuad& q2, double tMin, double tMax, SkIntersections* i, bool* subDivide) { double tMid = (tMin + tMax) / 2; - SkDPoint mid = q2.xyAtT(tMid); + SkDPoint mid = q2.ptAtT(tMid); SkDLine line; line[0] = line[1] = mid; SkDVector dxdy = q2.dxdyAtT(tMid); @@ -138,7 +138,7 @@ static bool add_intercept(const SkDQuad& q1, const SkDQuad& q2, double tMin, dou if (roots == 2) { return false; } - SkDPoint pt2 = q1.xyAtT(rootTs[0][0]); + SkDPoint pt2 = q1.ptAtT(rootTs[0][0]); if (!pt2.approximatelyEqualHalf(mid)) { return false; } @@ -160,8 +160,8 @@ static bool is_linear_inner(const SkDQuad& q1, double t1s, double t1e, const SkD for (int idx2 = 0; idx2 < roots; ++idx2) { double t = rootTs[0][idx2]; #ifdef SK_DEBUG - SkDPoint qPt = q2.xyAtT(t); - SkDPoint lPt = testLines[index]->xyAtT(rootTs[1][idx2]); + SkDPoint qPt = q2.ptAtT(t); + SkDPoint lPt = testLines[index]->ptAtT(rootTs[1][idx2]); SkASSERT(qPt.approximatelyEqual(lPt)); #endif if (approximately_negative(t - t2s) || approximately_positive(t - t2e)) { @@ -183,12 +183,12 @@ static bool is_linear_inner(const SkDQuad& q1, double t1s, double t1e, const SkD tMin = tsFound[0]; tMax = tsFound[tsFound.count() - 1]; } - SkDPoint end = q2.xyAtT(t2s); + SkDPoint end = q2.ptAtT(t2s); bool startInTriangle = hull.pointInHull(end); if (startInTriangle) { tMin = t2s; } - end = q2.xyAtT(t2e); + end = q2.ptAtT(t2e); bool endInTriangle = hull.pointInHull(end); if (endInTriangle) { tMax = t2e; @@ -290,8 +290,8 @@ static bool binary_search(const SkDQuad& quad1, const SkDQuad& quad2, double* t1 SkDPoint t1[3], t2[3]; int calcMask = ~0; do { - if (calcMask & (1 << 1)) t1[1] = quad1.xyAtT(*t1Seed); - if (calcMask & (1 << 4)) t2[1] = quad2.xyAtT(*t2Seed); + if (calcMask & (1 << 1)) t1[1] = quad1.ptAtT(*t1Seed); + if (calcMask & (1 << 4)) t2[1] = quad2.ptAtT(*t2Seed); if (t1[1].approximatelyEqual(t2[1])) { *pt = t1[1]; #if ONE_OFF_DEBUG @@ -300,10 +300,10 @@ static bool binary_search(const SkDQuad& quad1, const SkDQuad& quad2, double* t1 #endif return true; } - if (calcMask & (1 << 0)) t1[0] = quad1.xyAtT(*t1Seed - tStep); - if (calcMask & (1 << 2)) t1[2] = quad1.xyAtT(*t1Seed + tStep); - if (calcMask & (1 << 3)) t2[0] = quad2.xyAtT(*t2Seed - tStep); - if (calcMask & (1 << 5)) t2[2] = quad2.xyAtT(*t2Seed + tStep); + if (calcMask & (1 << 0)) t1[0] = quad1.ptAtT(*t1Seed - tStep); + if (calcMask & (1 << 2)) t1[2] = quad1.ptAtT(*t1Seed + tStep); + if (calcMask & (1 << 3)) t2[0] = quad2.ptAtT(*t2Seed - tStep); + if (calcMask & (1 << 5)) t2[2] = quad2.ptAtT(*t2Seed + tStep); double dist[3][3]; // OPTIMIZE: using calcMask value permits skipping some distance calcuations // if prior loop's results are moved to correct slot for reuse @@ -361,6 +361,34 @@ static bool binary_search(const SkDQuad& quad1, const SkDQuad& quad2, double* t1 return false; } +static void lookNearEnd(const SkDQuad& q1, const SkDQuad& q2, int testT, + const SkIntersections& orig, bool swap, SkIntersections* i) { + if (orig.used() == 1 && orig[!swap][0] == testT) { + return; + } + if (orig.used() == 2 && orig[!swap][1] == testT) { + return; + } + SkDLine tmpLine; + int testTIndex = testT << 1; + tmpLine[0] = tmpLine[1] = q2[testTIndex]; + tmpLine[1].fX += q2[1].fY - q2[testTIndex].fY; + tmpLine[1].fY -= q2[1].fX - q2[testTIndex].fX; + SkIntersections impTs; + impTs.intersectRay(q1, 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]); + } + } +} + int SkIntersections::intersect(const SkDQuad& q1, const SkDQuad& q2) { // if the quads share an end point, check to see if they overlap @@ -379,6 +407,7 @@ int SkIntersections::intersect(const SkDQuad& q1, const SkDQuad& q2) { return fUsed; } // see if either quad is really a line + // FIXME: figure out why reduce step didn't find this earlier if (is_linear(q1, q2, this)) { return fUsed; } @@ -388,30 +417,42 @@ int SkIntersections::intersect(const SkDQuad& q1, const SkDQuad& q2) { set(swapped); return fUsed; } - SkDQuadImplicit i1(q1); - SkDQuadImplicit i2(q2); - if (i1.match(i2)) { - // FIXME: compute T values - // compute the intersections of the ends to find the coincident span - reset(); - bool useVertical = fabs(q1[0].fX - q1[2].fX) < fabs(q1[0].fY - q1[2].fY); - double t; - if ((t = SkIntersections::Axial(q1, q2[0], useVertical)) >= 0) { - insertCoincident(t, 0, q2[0]); - } - if ((t = SkIntersections::Axial(q1, q2[2], useVertical)) >= 0) { - insertCoincident(t, 1, q2[2]); - } - useVertical = fabs(q2[0].fX - q2[2].fX) < fabs(q2[0].fY - q2[2].fY); - if ((t = SkIntersections::Axial(q2, q1[0], useVertical)) >= 0) { - insertCoincident(0, t, q1[0]); + SkIntersections copyI(*this); + lookNearEnd(q1, q2, 0, *this, false, ©I); + lookNearEnd(q1, q2, 1, *this, false, ©I); + lookNearEnd(q2, q1, 0, *this, true, ©I); + lookNearEnd(q2, q1, 1, *this, true, ©I); + int innerEqual = 0; + if (copyI.fUsed >= 2) { + SkASSERT(copyI.fUsed <= 4); + double width = copyI[0][1] - copyI[0][0]; + int midEnd = 1; + for (int index = 2; index < copyI.fUsed; ++index) { + double testWidth = copyI[0][index] - copyI[0][index - 1]; + if (testWidth <= width) { + continue; + } + midEnd = index; } - if ((t = SkIntersections::Axial(q2, q1[2], useVertical)) >= 0) { - insertCoincident(1, t, q1[2]); + for (int index = 0; index < 2; ++index) { + double testT = (copyI[0][midEnd] * (index + 1) + + copyI[0][midEnd - 1] * (2 - index)) / 3; + SkDPoint testPt1 = q1.ptAtT(testT); + testT = (copyI[1][midEnd] * (index + 1) + copyI[1][midEnd - 1] * (2 - index)) / 3; + SkDPoint testPt2 = q2.ptAtT(testT); + innerEqual += testPt1.approximatelyEqual(testPt2); } - SkASSERT(coincidentUsed() <= 2); + } + bool expectCoincident = copyI.fUsed >= 2 && innerEqual == 2; + if (expectCoincident) { + reset(); + insertCoincident(copyI[0][0], copyI[1][0], copyI.fPt[0]); + int last = copyI.fUsed - 1; + insertCoincident(copyI[0][last], copyI[1][last], copyI.fPt[last]); return fUsed; } + SkDQuadImplicit i1(q1); + SkDQuadImplicit i2(q2); int index; bool flip1 = q1[2] == q2[0]; bool flip2 = q1[0] == q2[2]; @@ -423,7 +464,7 @@ int SkIntersections::intersect(const SkDQuad& q1, const SkDQuad& q2) { int r1Count = addValidRoots(roots1, rootCount, roots1Copy); SkDPoint pts1[4]; for (index = 0; index < r1Count; ++index) { - pts1[index] = q1.xyAtT(roots1Copy[index]); + pts1[index] = q1.ptAtT(roots1Copy[index]); } double roots2[4]; int rootCount2 = findRoots(i1, q2, roots2, useCubic, flip2, 0); @@ -431,7 +472,7 @@ int SkIntersections::intersect(const SkDQuad& q1, const SkDQuad& q2) { int r2Count = addValidRoots(roots2, rootCount2, roots2Copy); SkDPoint pts2[4]; for (index = 0; index < r2Count; ++index) { - pts2[index] = q2.xyAtT(roots2Copy[index]); + pts2[index] = q2.ptAtT(roots2Copy[index]); } if (r1Count == r2Count && r1Count <= 1) { if (r1Count == 1) { diff --git a/src/pathops/SkDQuadLineIntersection.cpp b/src/pathops/SkDQuadLineIntersection.cpp index 9df2dc248a..58b3060ab3 100644 --- a/src/pathops/SkDQuadLineIntersection.cpp +++ b/src/pathops/SkDQuadLineIntersection.cpp @@ -89,10 +89,15 @@ Thus, if the slope of the line tends towards vertical, we use: class LineQuadraticIntersections { public: + enum PinTPoint { + kPointUninitialized, + kPointInitialized + }; + LineQuadraticIntersections(const SkDQuad& q, const SkDLine& l, SkIntersections* i) - : quad(q) - , line(l) - , intersections(i) + : fQuad(q) + , fLine(l) + , fIntersections(i) , fAllowNear(true) { } @@ -116,11 +121,11 @@ public: for each of the three points (e.g. n = 0 to 2) quad[n].fY' = (quad[n].fY - line[0].fY) * A - (quad[n].fX - line[0].fX) * O */ - double adj = line[1].fX - line[0].fX; - double opp = line[1].fY - line[0].fY; + double adj = fLine[1].fX - fLine[0].fX; + double opp = fLine[1].fY - fLine[0].fY; double r[3]; for (int n = 0; n < 3; ++n) { - r[n] = (quad[n].fY - line[0].fY) * adj - (quad[n].fX - line[0].fX) * opp; + r[n] = (fQuad[n].fY - fLine[0].fY) * adj - (fQuad[n].fX - fLine[0].fX) * opp; } double A = r[2]; double B = r[1]; @@ -137,21 +142,21 @@ public: for (int index = 0; index < roots; ++index) { double quadT = rootVals[index]; double lineT = findLineT(quadT); - if (PinTs(&quadT, &lineT)) { - SkDPoint pt = line.xyAtT(lineT); - intersections->insert(quadT, lineT, pt); + SkDPoint pt; + if (pinTs(&quadT, &lineT, &pt, kPointUninitialized)) { + fIntersections->insert(quadT, lineT, pt); } } if (fAllowNear) { addNearEndPoints(); } - return intersections->used(); + return fIntersections->used(); } int horizontalIntersect(double axisIntercept, double roots[2]) { - double D = quad[2].fY; // f - double E = quad[1].fY; // e - double F = quad[0].fY; // d + double D = fQuad[2].fY; // f + double E = fQuad[1].fY; // e + double F = fQuad[0].fY; // d D += F - 2 * E; // D = d - 2*e + f E -= F; // E = -(d - e) F -= axisIntercept; @@ -164,25 +169,25 @@ public: int roots = horizontalIntersect(axisIntercept, rootVals); for (int index = 0; index < roots; ++index) { double quadT = rootVals[index]; - SkDPoint pt = quad.xyAtT(quadT); + SkDPoint pt = fQuad.ptAtT(quadT); double lineT = (pt.fX - left) / (right - left); - if (PinTs(&quadT, &lineT)) { - intersections->insert(quadT, lineT, pt); + if (pinTs(&quadT, &lineT, &pt, kPointInitialized)) { + fIntersections->insert(quadT, lineT, pt); } } if (fAllowNear) { addNearHorizontalEndPoints(left, right, axisIntercept); } if (flipped) { - intersections->flip(); + fIntersections->flip(); } - return intersections->used(); + return fIntersections->used(); } int verticalIntersect(double axisIntercept, double roots[2]) { - double D = quad[2].fX; // f - double E = quad[1].fX; // e - double F = quad[0].fX; // d + double D = fQuad[2].fX; // f + double E = fQuad[1].fX; // e + double F = fQuad[0].fX; // d D += F - 2 * E; // D = d - 2*e + f E -= F; // E = -(d - e) F -= axisIntercept; @@ -195,107 +200,107 @@ public: int roots = verticalIntersect(axisIntercept, rootVals); for (int index = 0; index < roots; ++index) { double quadT = rootVals[index]; - SkDPoint pt = quad.xyAtT(quadT); + SkDPoint pt = fQuad.ptAtT(quadT); double lineT = (pt.fY - top) / (bottom - top); - if (PinTs(&quadT, &lineT)) { - intersections->insert(quadT, lineT, pt); + if (pinTs(&quadT, &lineT, &pt, kPointInitialized)) { + fIntersections->insert(quadT, lineT, pt); } } if (fAllowNear) { addNearVerticalEndPoints(top, bottom, axisIntercept); } if (flipped) { - intersections->flip(); + fIntersections->flip(); } - return intersections->used(); + return fIntersections->used(); } protected: // add endpoints first to get zero and one t values exactly void addExactEndPoints() { for (int qIndex = 0; qIndex < 3; qIndex += 2) { - double lineT = line.exactPoint(quad[qIndex]); + double lineT = fLine.exactPoint(fQuad[qIndex]); if (lineT < 0) { continue; } double quadT = (double) (qIndex >> 1); - intersections->insert(quadT, lineT, quad[qIndex]); + fIntersections->insert(quadT, lineT, fQuad[qIndex]); } } void addNearEndPoints() { for (int qIndex = 0; qIndex < 3; qIndex += 2) { double quadT = (double) (qIndex >> 1); - if (intersections->hasT(quadT)) { + if (fIntersections->hasT(quadT)) { continue; } - double lineT = line.nearPoint(quad[qIndex]); + double lineT = fLine.nearPoint(fQuad[qIndex]); if (lineT < 0) { continue; } - intersections->insert(quadT, lineT, quad[qIndex]); + fIntersections->insert(quadT, lineT, fQuad[qIndex]); } // FIXME: see if line end is nearly on quad } void addExactHorizontalEndPoints(double left, double right, double y) { for (int qIndex = 0; qIndex < 3; qIndex += 2) { - double lineT = SkDLine::ExactPointH(quad[qIndex], left, right, y); + double lineT = SkDLine::ExactPointH(fQuad[qIndex], left, right, y); if (lineT < 0) { continue; } double quadT = (double) (qIndex >> 1); - intersections->insert(quadT, lineT, quad[qIndex]); + fIntersections->insert(quadT, lineT, fQuad[qIndex]); } } void addNearHorizontalEndPoints(double left, double right, double y) { for (int qIndex = 0; qIndex < 3; qIndex += 2) { double quadT = (double) (qIndex >> 1); - if (intersections->hasT(quadT)) { + if (fIntersections->hasT(quadT)) { continue; } - double lineT = SkDLine::NearPointH(quad[qIndex], left, right, y); + double lineT = SkDLine::NearPointH(fQuad[qIndex], left, right, y); if (lineT < 0) { continue; } - intersections->insert(quadT, lineT, quad[qIndex]); + fIntersections->insert(quadT, lineT, fQuad[qIndex]); } // FIXME: see if line end is nearly on quad } void addExactVerticalEndPoints(double top, double bottom, double x) { for (int qIndex = 0; qIndex < 3; qIndex += 2) { - double lineT = SkDLine::ExactPointV(quad[qIndex], top, bottom, x); + double lineT = SkDLine::ExactPointV(fQuad[qIndex], top, bottom, x); if (lineT < 0) { continue; } double quadT = (double) (qIndex >> 1); - intersections->insert(quadT, lineT, quad[qIndex]); + fIntersections->insert(quadT, lineT, fQuad[qIndex]); } } void addNearVerticalEndPoints(double top, double bottom, double x) { for (int qIndex = 0; qIndex < 3; qIndex += 2) { double quadT = (double) (qIndex >> 1); - if (intersections->hasT(quadT)) { + if (fIntersections->hasT(quadT)) { continue; } - double lineT = SkDLine::NearPointV(quad[qIndex], top, bottom, x); + double lineT = SkDLine::NearPointV(fQuad[qIndex], top, bottom, x); if (lineT < 0) { continue; } - intersections->insert(quadT, lineT, quad[qIndex]); + fIntersections->insert(quadT, lineT, fQuad[qIndex]); } // FIXME: see if line end is nearly on quad } double findLineT(double t) { - SkDPoint xy = quad.xyAtT(t); - double dx = line[1].fX - line[0].fX; - double dy = line[1].fY - line[0].fY; - double dxT = (xy.fX - line[0].fX) / dx; - double dyT = (xy.fY - line[0].fY) / dy; + SkDPoint xy = fQuad.ptAtT(t); + double dx = fLine[1].fX - fLine[0].fX; + double dy = fLine[1].fY - fLine[0].fY; + double dxT = (xy.fX - fLine[0].fX) / dx; + double dyT = (xy.fY - fLine[0].fY) / dy; if (!between(FLT_EPSILON, dxT, 1 - FLT_EPSILON) && between(0, dyT, 1)) { return dyT; } @@ -305,22 +310,27 @@ protected: return fabs(dx) > fabs(dy) ? dxT : dyT; } - static bool PinTs(double* quadT, double* lineT) { + bool pinTs(double* quadT, double* lineT, SkDPoint* pt, PinTPoint ptSet) { if (!approximately_one_or_less(*lineT)) { return false; } if (!approximately_zero_or_more(*lineT)) { return false; } - *quadT = SkPinT(*quadT); - *lineT = SkPinT(*lineT); + double qT = *quadT = SkPinT(*quadT); + double lT = *lineT = SkPinT(*lineT); + if (lT == 0 || lT == 1 || (ptSet == kPointUninitialized && qT != 0 && qT != 1)) { + *pt = fLine.ptAtT(lT); + } else if (ptSet == kPointUninitialized) { + *pt = fQuad.ptAtT(qT); + } return true; } private: - const SkDQuad& quad; - const SkDLine& line; - SkIntersections* intersections; + const SkDQuad& fQuad; + const SkDLine& fLine; + SkIntersections* fIntersections; bool fAllowNear; }; @@ -332,7 +342,7 @@ static double horizontalIntersect(const SkDQuad& quad, const SkDPoint& pt) { int roots = q.horizontalIntersect(pt.fY, rootVals); for (int index = 0; index < roots; ++index) { double t = rootVals[index]; - SkDPoint qPt = quad.xyAtT(t); + SkDPoint qPt = quad.ptAtT(t); if (AlmostEqualUlps(qPt.fX, pt.fX)) { return t; } @@ -347,7 +357,7 @@ static double verticalIntersect(const SkDQuad& quad, const SkDPoint& pt) { int roots = q.verticalIntersect(pt.fX, rootVals); for (int index = 0; index < roots; ++index) { double t = rootVals[index]; - SkDPoint qPt = quad.xyAtT(t); + SkDPoint qPt = quad.ptAtT(t); if (AlmostEqualUlps(qPt.fY, pt.fY)) { return t; } @@ -364,13 +374,15 @@ double SkIntersections::Axial(const SkDQuad& q1, const SkDPoint& p, bool vertica int SkIntersections::horizontal(const SkDQuad& quad, double left, double right, double y, bool flipped) { - LineQuadraticIntersections q(quad, *(static_cast<SkDLine*>(0)), this); + SkDLine line = {{{ left, y }, { right, y }}}; + LineQuadraticIntersections q(quad, line, this); return q.horizontalIntersect(y, left, right, flipped); } int SkIntersections::vertical(const SkDQuad& quad, double top, double bottom, double x, bool flipped) { - LineQuadraticIntersections q(quad, *(static_cast<SkDLine*>(0)), this); + SkDLine line = {{{ x, top }, { x, bottom }}}; + LineQuadraticIntersections q(quad, line, this); return q.verticalIntersect(x, top, bottom, flipped); } @@ -384,7 +396,7 @@ int SkIntersections::intersectRay(const SkDQuad& quad, const SkDLine& line) { LineQuadraticIntersections q(quad, line, this); fUsed = q.intersectRay(fT[0]); for (int index = 0; index < fUsed; ++index) { - fPt[index] = quad.xyAtT(fT[0][index]); + fPt[index] = quad.ptAtT(fT[0][index]); } return fUsed; } diff --git a/src/pathops/SkIntersections.cpp b/src/pathops/SkIntersections.cpp index fe23316683..242c67b926 100644 --- a/src/pathops/SkIntersections.cpp +++ b/src/pathops/SkIntersections.cpp @@ -54,108 +54,6 @@ void SkIntersections::flip() { } } -void SkIntersections::insertCoincidentPair(double s1, double e1, double s2, double e2, - const SkDPoint& startPt, const SkDPoint& endPt) { - SkASSERT(s1 < e1); - SkASSERT(s2 != e2); - if (coincidentUsed() != fUsed) { // if the curve is partially coincident, treat it as fully so - for (int index = fUsed - 1; index >= 0; --index) { - if (fIsCoincident[0] & (1 << index)) { - continue; - } - double nonCoinT = fT[0][index]; - if (!between(s1, nonCoinT, e1)) { - if (s1 > nonCoinT) { - s1 = nonCoinT; - } else { - e1 = nonCoinT; - } - } - nonCoinT = fT[1][index]; - if (!between(s2, nonCoinT, e2)) { - if ((s2 > nonCoinT) ^ (s2 > e2)) { - s2 = nonCoinT; - } else { - e2 = nonCoinT; - } - } - removeOne(index); - } - } - SkASSERT(coincidentUsed() == fUsed); - SkASSERT((coincidentUsed() & 1) != 1); - int i1 = 0; - int i2 = 0; - do { - while (i1 < fUsed && !(fIsCoincident[fSwap] & (1 << i1))) { - ++i1; - } - if (i1 == fUsed) { - break; - } - SkASSERT(i1 < fUsed); - int iEnd1 = i1 + 1; - while (!(fIsCoincident[fSwap] & (1 << iEnd1))) { - ++iEnd1; - } - SkASSERT(iEnd1 < fUsed); - double cs1 = fT[fSwap][i1]; - double ce1 = fT[fSwap][iEnd1]; - bool s1in = between(cs1, s1, ce1) || startPt.approximatelyEqual(fPt[i1]) - || startPt.approximatelyEqual(fPt[iEnd1]); - bool e1in = between(cs1, e1, ce1) || endPt.approximatelyEqual(fPt[i1]) - || endPt.approximatelyEqual(fPt[iEnd1]); - while (i2 < fUsed && !(fIsCoincident[fSwap ^ 1] & (1 << i2))) { - ++i2; - } - int iEnd2 = i2 + 1; - while (!(fIsCoincident[fSwap ^ 1] & (1 << iEnd2))) { - ++iEnd2; - } - SkASSERT(iEnd2 < fUsed); - double cs2 = fT[fSwap ^ 1][i2]; - double ce2 = fT[fSwap ^ 1][iEnd2]; - bool s2in = between(cs2, s2, ce2) || startPt.approximatelyEqual(fPt[i2]) - || startPt.approximatelyEqual(fPt[iEnd2]); - bool e2in = between(cs2, e2, ce2) || endPt.approximatelyEqual(fPt[i2]) - || endPt.approximatelyEqual(fPt[iEnd2]); - if ((s1in | e1in) & (s2in | e2in)) { - if (s1 < cs1) { - fT[fSwap][i1] = s1; - fPt[i1] = startPt; - } else if (e1 < cs1) { - fT[fSwap][i1] = e1; - fPt[i1] = endPt; - } - if (s1 > ce1) { - fT[fSwap][iEnd1] = s1; - fPt[iEnd1] = startPt; - } else if (e1 > ce1) { - fT[fSwap][iEnd1] = e1; - fPt[iEnd1] = endPt; - } - if (s2 > e2) { - SkTSwap(cs2, ce2); - SkTSwap(i2, iEnd2); - } - if (s2 < cs2) { - fT[fSwap ^ 1][i2] = s2; - } else if (e2 < cs2) { - fT[fSwap ^ 1][i2] = e2; - } - if (s2 > ce2) { - fT[fSwap ^ 1][iEnd2] = s2; - } else if (e2 > ce2) { - fT[fSwap ^ 1][iEnd2] = e2; - } - return; - } - } while (true); - SkASSERT(fUsed < 9); - insertCoincident(s1, s2, startPt); - insertCoincident(e1, e2, endPt); -} - int SkIntersections::insert(double one, double two, const SkDPoint& pt) { if (fIsCoincident[0] == 3 && between(fT[0][0], one, fT[0][1])) { // For now, don't allow a mix of coincident and non-coincident intersections diff --git a/src/pathops/SkIntersections.h b/src/pathops/SkIntersections.h index de3d44cd70..26a1d1a559 100644 --- a/src/pathops/SkIntersections.h +++ b/src/pathops/SkIntersections.h @@ -208,8 +208,6 @@ public: int insert(double one, double two, const SkDPoint& pt); // start if index == 0 : end if index == 1 void insertCoincident(double one, double two, const SkDPoint& pt); - void insertCoincidentPair(double s1, double e1, double s2, double e2, - const SkDPoint& startPt, const SkDPoint& endPt); int intersect(const SkDLine&, const SkDLine&); int intersect(const SkDQuad&, const SkDLine&); int intersect(const SkDQuad&, const SkDQuad&); diff --git a/src/pathops/SkOpSegment.cpp b/src/pathops/SkOpSegment.cpp index 5b20749957..7e69bb835b 100644 --- a/src/pathops/SkOpSegment.cpp +++ b/src/pathops/SkOpSegment.cpp @@ -1082,9 +1082,7 @@ bool SkOpSegment::bumpSpan(SkOpSpan* span, int windDelta, int oppDelta) { // look to see if the curve end intersects an intermediary that intersects the other void SkOpSegment::checkEnds() { -#if 1 - return; // FIXME: suspect we will need the code below to make intersections consistent -#else + debugValidate(); SkTDArray<SkOpSpan> missingSpans; int count = fTs.count(); for (int index = 0; index < count; ++index) { @@ -1150,14 +1148,20 @@ nextPeeker: ; } int missingCount = missingSpans.count(); + if (missingCount == 0) { + return; + } + debugValidate(); for (int index = 0; index < missingCount; ++index) { const SkOpSpan& missing = missingSpans[index]; addTPair(missing.fT, missing.fOther, missing.fOtherT, false, missing.fPt); } - if (missingCount > 0) { - fixOtherTIndex(); + fixOtherTIndex(); + for (int index = 0; index < missingCount; ++index) { + const SkOpSpan& missing = missingSpans[index]; + missing.fOther->fixOtherTIndex(); } -#endif + debugValidate(); } bool SkOpSegment::equalPoints(int greaterTIndex, int lesserTIndex) { @@ -1792,13 +1796,16 @@ void SkOpSegment::fixOtherTIndex() { double oT = iSpan.fOtherT; SkOpSegment* other = iSpan.fOther; int oCount = other->fTs.count(); + SkDEBUGCODE(iSpan.fOtherIndex = -1); for (int o = 0; o < oCount; ++o) { SkOpSpan& oSpan = other->fTs[o]; if (oT == oSpan.fT && this == oSpan.fOther && oSpan.fOtherT == iSpan.fT) { iSpan.fOtherIndex = o; + oSpan.fOtherIndex = i; break; } } + SkASSERT(iSpan.fOtherIndex >= 0); } } @@ -2755,6 +2762,7 @@ void SkOpSegment::debugShowTs() const { #if DEBUG_ACTIVE_SPANS || DEBUG_ACTIVE_SPANS_FIRST_ONLY void SkOpSegment::debugShowActiveSpans() const { + debugValidate(); if (done()) { return; } @@ -2763,8 +2771,6 @@ void SkOpSegment::debugShowActiveSpans() const { double lastT = -1; #endif for (int i = 0; i < fTs.count(); ++i) { - SkASSERT(&fTs[i] == &fTs[i].fOther->fTs[fTs[i].fOtherIndex].fOther-> - fTs[fTs[i].fOther->fTs[fTs[i].fOtherIndex].fOtherIndex]); if (fTs[i].fDone) { continue; } @@ -2995,3 +3001,27 @@ int SkOpSegment::debugShowWindingValues(int slotCount, int ofInterest) const { return sum; } #endif + +void SkOpSegment::debugValidate() const { +#if DEBUG_VALIDATE + int count = fTs.count(); + SkASSERT(count >= 2); + SkASSERT(fTs[0].fT == 0); + SkASSERT(fTs[count - 1].fT == 1); + int done = 0; + double t = -1; + for (int i = 0; i < count; ++i) { + const SkOpSpan& span = fTs[i]; + SkASSERT(t <= span.fT); + t = span.fT; + int otherIndex = span.fOtherIndex; + const SkOpSegment* other = span.fOther; + const SkOpSpan& otherSpan = other->fTs[otherIndex]; + SkASSERT(otherSpan.fPt == span.fPt); + SkASSERT(otherSpan.fOtherT == t); + SkASSERT(&fTs[i] == &otherSpan.fOther->fTs[otherSpan.fOtherIndex]); + done += span.fDone; + } + SkASSERT(done == fDoneSpans); +#endif +} diff --git a/src/pathops/SkOpSegment.h b/src/pathops/SkOpSegment.h index 7e5e644f1d..bfaf4ed9de 100644 --- a/src/pathops/SkOpSegment.h +++ b/src/pathops/SkOpSegment.h @@ -130,6 +130,11 @@ public: return fTs[index].fOther; } + // was used only by right angle winding finding + SkPoint ptAtT(double mid) const { + return (*CurvePointAtT[SkPathOpsVerbToPoints(fVerb)])(fPts, mid); + } + const SkPoint* pts() const { return fPts; } @@ -214,11 +219,6 @@ public: return span->fPt; } - // used only by right angle winding finding - SkPoint xyAtT(double mid) const { - return (*CurvePointAtT[SkPathOpsVerbToPoints(fVerb)])(fPts, mid); - } - const SkPoint& xyAtT(int index) const { return xyAtT(&fTs[index]); } @@ -394,6 +394,7 @@ private: return value < 0 ? '?' : value <= 9 ? '0' + value : '+'; } #endif + void debugValidate() const; const SkPoint* fPts; SkPathOpsBounds fBounds; diff --git a/src/pathops/SkPathOpsCommon.cpp b/src/pathops/SkPathOpsCommon.cpp index 9a92b00acd..28cf59cdd3 100644 --- a/src/pathops/SkPathOpsCommon.cpp +++ b/src/pathops/SkPathOpsCommon.cpp @@ -17,7 +17,7 @@ static int contourRangeCheckY(const SkTArray<SkOpContour*, true>& contourList, S const double mid = *midPtr; const SkOpSegment* current = *currentPtr; double tAtMid = current->tAtMid(index, endIndex, mid); - SkPoint basePt = current->xyAtT(tAtMid); + SkPoint basePt = current->ptAtT(tAtMid); int contourCount = contourList.count(); SkScalar bestY = SK_ScalarMin; SkOpSegment* bestSeg = NULL; diff --git a/src/pathops/SkPathOpsCubic.cpp b/src/pathops/SkPathOpsCubic.cpp index 60dca44a27..5fbfeba50d 100644 --- a/src/pathops/SkPathOpsCubic.cpp +++ b/src/pathops/SkPathOpsCubic.cpp @@ -304,7 +304,7 @@ SkDPoint SkDCubic::top(double startT, double endT) const { int roots = FindExtrema(sub[0].fY, sub[1].fY, sub[2].fY, sub[3].fY, extremeTs); for (int index = 0; index < roots; ++index) { double t = startT + (endT - startT) * extremeTs[index]; - SkDPoint mid = xyAtT(t); + SkDPoint mid = ptAtT(t); if (topPt.fY > mid.fY || (topPt.fY == mid.fY && topPt.fX > mid.fX)) { topPt = mid; } @@ -313,7 +313,13 @@ SkDPoint SkDCubic::top(double startT, double endT) const { return topPt; } -SkDPoint SkDCubic::xyAtT(double t) const { +SkDPoint SkDCubic::ptAtT(double t) const { + if (0 == t) { + return fPts[0]; + } + if (1 == t) { + return fPts[3]; + } double one_t = 1 - t; double one_t2 = one_t * one_t; double a = one_t2 * one_t; diff --git a/src/pathops/SkPathOpsCubic.h b/src/pathops/SkPathOpsCubic.h index f07af80dcd..1ba35be22b 100644 --- a/src/pathops/SkPathOpsCubic.h +++ b/src/pathops/SkPathOpsCubic.h @@ -53,6 +53,7 @@ struct SkDCubic { int findMaxCurvature(double tValues[]) const; bool isLinear(int startIndex, int endIndex) const; bool monotonicInY() const; + SkDPoint ptAtT(double t) const; static int RootsReal(double A, double B, double C, double D, double t[3]); static int RootsValidT(const double A, const double B, const double C, double D, double s[3]); bool serpentine() const; @@ -76,7 +77,6 @@ struct SkDCubic { SkDPoint top(double startT, double endT) const; void toQuadraticTs(double precision, SkTArray<double, true>* ts) const; SkDQuad toQuad() const; - SkDPoint xyAtT(double t) const; }; #endif diff --git a/src/pathops/SkPathOpsCurve.h b/src/pathops/SkPathOpsCurve.h index ca68a664e6..5d12cb811a 100644 --- a/src/pathops/SkPathOpsCurve.h +++ b/src/pathops/SkPathOpsCurve.h @@ -14,19 +14,19 @@ static SkDPoint dline_xy_at_t(const SkPoint a[2], double t) { SkDLine line; line.set(a); - return line.xyAtT(t); + return line.ptAtT(t); } static SkDPoint dquad_xy_at_t(const SkPoint a[3], double t) { SkDQuad quad; quad.set(a); - return quad.xyAtT(t); + return quad.ptAtT(t); } static SkDPoint dcubic_xy_at_t(const SkPoint a[4], double t) { SkDCubic cubic; cubic.set(a); - return cubic.xyAtT(t); + return cubic.ptAtT(t); } static SkDPoint (* const CurveDPointAtT[])(const SkPoint[], double ) = { @@ -123,7 +123,7 @@ static SkPoint (* const CurveTop[])(const SkPoint[], double , double ) = { static bool line_is_vertical(const SkPoint a[2], double startT, double endT) { SkDLine line; line.set(a); - SkDPoint dst[2] = { line.xyAtT(startT), line.xyAtT(endT) }; + SkDPoint dst[2] = { line.ptAtT(startT), line.ptAtT(endT) }; return AlmostEqualUlps(dst[0].fX, dst[1].fX); } diff --git a/src/pathops/SkPathOpsDebug.h b/src/pathops/SkPathOpsDebug.h index 05fe241e0f..e4ef072b9e 100644 --- a/src/pathops/SkPathOpsDebug.h +++ b/src/pathops/SkPathOpsDebug.h @@ -64,6 +64,7 @@ extern int gDebugMaxWindValue; #define DEBUG_SORT_SINGLE 0 #define DEBUG_SWAP_TOP 0 #define DEBUG_UNSORTABLE 0 +#define DEBUG_VALIDATE 0 #define DEBUG_WIND_BUMP 0 #define DEBUG_WINDING 0 #define DEBUG_WINDING_AT_T 0 @@ -93,6 +94,7 @@ extern int gDebugMaxWindValue; #define DEBUG_SORT_SINGLE 0 #define DEBUG_SWAP_TOP 1 #define DEBUG_UNSORTABLE 1 +#define DEBUG_VALIDATE 1 #define DEBUG_WIND_BUMP 0 #define DEBUG_WINDING 1 #define DEBUG_WINDING_AT_T 1 diff --git a/src/pathops/SkPathOpsLine.cpp b/src/pathops/SkPathOpsLine.cpp index 47c0565b69..48c042a7fa 100644 --- a/src/pathops/SkPathOpsLine.cpp +++ b/src/pathops/SkPathOpsLine.cpp @@ -41,8 +41,13 @@ double SkDLine::isLeft(const SkDPoint& pt) const { return p0.cross(p2); } -// OPTIMIZE: assert if t is 0 or 1 (caller shouldn't pass only 0/1) -SkDPoint SkDLine::xyAtT(double t) const { +SkDPoint SkDLine::ptAtT(double t) const { + if (0 == t) { + return fPts[0]; + } + if (1 == t) { + return fPts[1]; + } double one_t = 1 - t; SkDPoint result = { one_t * fPts[0].fX + t * fPts[1].fX, one_t * fPts[0].fY + t * fPts[1].fY }; return result; @@ -72,7 +77,7 @@ double SkDLine::nearPoint(const SkDPoint& xy) const { return -1; } double t = numer / denom; - SkDPoint realPt = xyAtT(t); + SkDPoint realPt = ptAtT(t); SkDVector distU = xy - realPt; double distSq = distU.fX * distU.fX + distU.fY * distU.fY; double dist = sqrt(distSq); // OPTIMIZATION: can we compare against distSq instead ? diff --git a/src/pathops/SkPathOpsLine.h b/src/pathops/SkPathOpsLine.h index c5ac7fdb09..75f3bd1058 100644 --- a/src/pathops/SkPathOpsLine.h +++ b/src/pathops/SkPathOpsLine.h @@ -33,8 +33,8 @@ struct SkDLine { double nearPoint(const SkDPoint& xy) const; static double NearPointH(const SkDPoint& xy, double left, double right, double y); static double NearPointV(const SkDPoint& xy, double top, double bottom, double x); + SkDPoint ptAtT(double t) const; SkDLine subDivide(double t1, double t2) const; - SkDPoint xyAtT(double t) const; private: SkDVector tangent() const { return fPts[0] - fPts[1]; } }; diff --git a/src/pathops/SkPathOpsQuad.cpp b/src/pathops/SkPathOpsQuad.cpp index 636e3854fd..7d9ff52aa2 100644 --- a/src/pathops/SkPathOpsQuad.cpp +++ b/src/pathops/SkPathOpsQuad.cpp @@ -30,7 +30,7 @@ double SkDQuad::nearestT(const SkDPoint& pt) const { double distMin = SkTMin(d0, d2); int bestIndex = -1; for (int index = 0; index < roots; ++index) { - SkDPoint onQuad = xyAtT(ts[index]); + SkDPoint onQuad = ptAtT(ts[index]); double dist = pt.distanceSquared(onQuad); if (distMin > dist) { distMin = dist; @@ -57,7 +57,7 @@ SkDPoint SkDQuad::top(double startT, double endT) const { double extremeT; if (FindExtrema(sub[0].fY, sub[1].fY, sub[2].fY, &extremeT)) { extremeT = startT + (endT - startT) * extremeT; - SkDPoint test = xyAtT(extremeT); + SkDPoint test = ptAtT(extremeT); if (topPt.fY > test.fY || (topPt.fY == test.fY && topPt.fX > test.fX)) { topPt = test; } @@ -165,7 +165,13 @@ SkDVector SkDQuad::dxdyAtT(double t) const { } // OPTIMIZE: assert if caller passes in t == 0 / t == 1 ? -SkDPoint SkDQuad::xyAtT(double t) const { +SkDPoint SkDQuad::ptAtT(double t) const { + if (0 == t) { + return fPts[0]; + } + if (1 == t) { + return fPts[2]; + } double one_t = 1 - t; double a = one_t * one_t; double b = 2 * one_t * t; diff --git a/src/pathops/SkPathOpsQuad.h b/src/pathops/SkPathOpsQuad.h index d06f3449bf..c8650515bb 100644 --- a/src/pathops/SkPathOpsQuad.h +++ b/src/pathops/SkPathOpsQuad.h @@ -42,6 +42,7 @@ struct SkDQuad { bool monotonicInY() const; double nearestT(const SkDPoint&) const; bool pointInHull(const SkDPoint&) const; + SkDPoint ptAtT(double t) const; static int RootsReal(double A, double B, double C, double t[2]); static int RootsValidT(const double A, const double B, const double C, double s[2]); static void SetABC(const double* quad, double* a, double* b, double* c); @@ -60,7 +61,6 @@ struct SkDQuad { } SkDCubic toCubic() const; SkDPoint top(double startT, double endT) const; - SkDPoint xyAtT(double t) const; private: // static double Tangent(const double* quadratic, double t); // uncalled }; diff --git a/src/pathops/SkPathOpsRect.cpp b/src/pathops/SkPathOpsRect.cpp index 9d7f876cac..2ceed32900 100644 --- a/src/pathops/SkPathOpsRect.cpp +++ b/src/pathops/SkPathOpsRect.cpp @@ -26,7 +26,7 @@ void SkDRect::setBounds(const SkDQuad& quad) { roots += SkDQuad::FindExtrema(quad[0].fY, quad[1].fY, quad[2].fY, &tValues[roots]); } for (int x = 0; x < roots; ++x) { - add(quad.xyAtT(tValues[x])); + add(quad.ptAtT(tValues[x])); } } @@ -53,7 +53,7 @@ void SkDRect::setBounds(const SkDCubic& c) { roots += SkDCubic::FindExtrema(c[0].fY, c[1].fY, c[2].fY, c[3].fY, &tValues[roots]); } for (int x = 0; x < roots; ++x) { - add(c.xyAtT(tValues[x])); + add(c.ptAtT(tValues[x])); } } diff --git a/src/pathops/SkPathOpsTypes.cpp b/src/pathops/SkPathOpsTypes.cpp index a076d155f2..8135c57025 100644 --- a/src/pathops/SkPathOpsTypes.cpp +++ b/src/pathops/SkPathOpsTypes.cpp @@ -11,40 +11,40 @@ // 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) { SkFloatIntUnion floatIntA, floatIntB; - floatIntA.fFloat = A; - floatIntB.fFloat = B; + floatIntA.fFloat = a; + floatIntB.fFloat = b; // Different signs means they do not match. if ((floatIntA.fSignBitInt < 0) != (floatIntB.fSignBitInt < 0)) { // Check for equality to make sure +0 == -0 - return A == B; + return a == b; } // Find the difference in ULPs. int ulpsDiff = abs(floatIntA.fSignBitInt - floatIntB.fSignBitInt); return ulpsDiff <= epsilon; } -static bool less_ulps(float A, float B, int epsilon) { +static bool less_ulps(float a, float b, int epsilon) { SkFloatIntUnion floatIntA, floatIntB; - floatIntA.fFloat = A; - floatIntB.fFloat = B; + floatIntA.fFloat = a; + floatIntB.fFloat = b; // Check different signs with float epsilon since we only care if they're both close to 0. if ((floatIntA.fSignBitInt < 0) != (floatIntB.fSignBitInt < 0)) { - return A <= B + FLT_EPSILON * epsilon; + return a <= b + FLT_EPSILON * epsilon; } // Find the difference in ULPs. return floatIntA.fSignBitInt <= floatIntB.fSignBitInt + epsilon; } -bool AlmostEqualUlps(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); } -bool RoughlyEqualUlps(float A, float B) { +bool RoughlyEqualUlps(float a, float b) { const int UlpsEpsilon = 256; - return equal_ulps(A, B, UlpsEpsilon); + return equal_ulps(a, b, UlpsEpsilon); } bool AlmostBetweenUlps(float a, float b, float c) { @@ -53,6 +53,19 @@ bool AlmostBetweenUlps(float a, float b, float c) { : less_ulps(b, a, UlpsEpsilon) && less_ulps(c, b, UlpsEpsilon); } +int UlpsDistance(float a, float b) { + SkFloatIntUnion floatIntA, floatIntB; + floatIntA.fFloat = a; + floatIntB.fFloat = b; + // Different signs means they do not match. + if ((floatIntA.fSignBitInt < 0) != (floatIntB.fSignBitInt < 0)) { + // Check for equality to make sure +0 == -0 + return a == b ? 0 : SK_MaxS32; + } + // Find the difference in ULPs. + return abs(floatIntA.fSignBitInt - floatIntB.fSignBitInt); +} + // cube root approximation using bit hack for 64-bit float // adapted from Kahan's cbrt static double cbrt_5d(double d) { diff --git a/src/pathops/SkPathOpsTypes.h b/src/pathops/SkPathOpsTypes.h index c988691e26..6158f13576 100644 --- a/src/pathops/SkPathOpsTypes.h +++ b/src/pathops/SkPathOpsTypes.h @@ -23,19 +23,24 @@ enum SkPathOpsMask { }; // Use Almost Equal when comparing coordinates. Use epsilon to compare T values. -bool AlmostEqualUlps(float A, float B); -inline bool AlmostEqualUlps(double A, double B) { - return AlmostEqualUlps(SkDoubleToScalar(A), SkDoubleToScalar(B)); +bool AlmostEqualUlps(float a, float b); +inline bool AlmostEqualUlps(double a, double b) { + return AlmostEqualUlps(SkDoubleToScalar(a), SkDoubleToScalar(b)); } -bool RoughlyEqualUlps(float A, float B); -inline bool RoughlyEqualUlps(double A, double B) { - return RoughlyEqualUlps(SkDoubleToScalar(A), SkDoubleToScalar(B)); +bool RoughlyEqualUlps(float a, float b); +inline bool RoughlyEqualUlps(double a, double b) { + return RoughlyEqualUlps(SkDoubleToScalar(a), SkDoubleToScalar(b)); } bool AlmostBetweenUlps(float a, float b, float c); -inline bool AlmostBetweenUlps(double A, double B, double C) { - return AlmostBetweenUlps(SkDoubleToScalar(A), SkDoubleToScalar(B), SkDoubleToScalar(C)); +inline bool AlmostBetweenUlps(double a, double b, double c) { + return AlmostBetweenUlps(SkDoubleToScalar(a), SkDoubleToScalar(b), SkDoubleToScalar(c)); +} + +int UlpsDistance(float a, float b); +inline int UlpsDistance(double a, double b) { + return UlpsDistance(SkDoubleToScalar(a), SkDoubleToScalar(b)); } // FLT_EPSILON == 1.19209290E-07 == 1 / (2 ^ 23) diff --git a/tests/PathOpsAngleTest.cpp b/tests/PathOpsAngleTest.cpp index 4c362b6276..f7507a0f97 100644 --- a/tests/PathOpsAngleTest.cpp +++ b/tests/PathOpsAngleTest.cpp @@ -257,8 +257,8 @@ static void setup(const SortSet* set, const size_t idx, if (useIntersectPt) { break; } - start = dLine.xyAtT(set[idx].tStart).asSkPoint(); - end = dLine.xyAtT(set[idx].tEnd).asSkPoint(); + start = dLine.ptAtT(set[idx].tStart).asSkPoint(); + end = dLine.ptAtT(set[idx].tEnd).asSkPoint(); } break; case 3: { SkASSERT(ValidPoints(data, 3)); @@ -269,8 +269,8 @@ static void setup(const SortSet* set, const size_t idx, if (useIntersectPt) { break; } - start = dQuad.xyAtT(set[idx].tStart).asSkPoint(); - end = dQuad.xyAtT(set[idx].tEnd).asSkPoint(); + start = dQuad.ptAtT(set[idx].tStart).asSkPoint(); + end = dQuad.ptAtT(set[idx].tEnd).asSkPoint(); } break; case 4: { SkASSERT(ValidPoints(data, 4)); @@ -281,8 +281,8 @@ static void setup(const SortSet* set, const size_t idx, if (useIntersectPt) { break; } - start = dCubic.xyAtT(set[idx].tStart).asSkPoint(); - end = dCubic.xyAtT(set[idx].tEnd).asSkPoint(); + start = dCubic.ptAtT(set[idx].tStart).asSkPoint(); + end = dCubic.ptAtT(set[idx].tEnd).asSkPoint(); } break; } double tStart = set[idx].tStart; diff --git a/tests/PathOpsCubicIntersectionTest.cpp b/tests/PathOpsCubicIntersectionTest.cpp index c4915e99c9..a0f2846984 100644 --- a/tests/PathOpsCubicIntersectionTest.cpp +++ b/tests/PathOpsCubicIntersectionTest.cpp @@ -52,9 +52,9 @@ static void standardTestCases(skiatest::Reporter* reporter) { } for (int pt = 0; pt < tIntersections.used(); ++pt) { double tt1 = tIntersections[0][pt]; - SkDPoint xy1 = cubic1.xyAtT(tt1); + SkDPoint xy1 = cubic1.ptAtT(tt1); double tt2 = tIntersections[1][pt]; - SkDPoint xy2 = cubic2.xyAtT(tt2); + SkDPoint xy2 = cubic2.ptAtT(tt2); if (!xy1.approximatelyEqual(xy2)) { SkDebugf("%s [%d,%d] x!= t1=%g (%g,%g) t2=%g (%g,%g)\n", __FUNCTION__, (int)index, pt, tt1, xy1.fX, xy1.fY, tt2, xy2.fX, xy2.fY); @@ -163,6 +163,19 @@ static const SkDCubic testSet[] = { const size_t testSetCount = SK_ARRAY_COUNT(testSet); static const SkDCubic newTestSet[] = { +{{{3, 4}, {1, 5}, {4, 3}, {6, 4}}},
+{{{3, 4}, {4, 6}, {4, 3}, {5, 1}}},
+ +{{{130.04275512695312, 11417.413085937500 },
+ {130.23312377929687, 11418.319335937500 },
+ {131.03707885742187, 11419.000000000000 },
+ {132.00000000000000, 11419.000000000000 }}},
+
+{{{132.00000000000000, 11419.000000000000 },
+ {130.89543151855469, 11419.000000000000 },
+ {130.00000000000000, 11418.104492187500 },
+ {130.00000000000000, 11417.000000000000 }}}, + {{{1.0516976506771041, 2.9684399028541346 }, {1.0604363140895228, 2.9633503074444141 }, {1.0692548215065762, 2.9580354426587459 }, @@ -305,9 +318,9 @@ static void oneOff(skiatest::Reporter* reporter, const SkDCubic& cubic1, const S SkDPoint xy1, xy2; for (int pt3 = 0; pt3 < intersections.used(); ++pt3) { tt1 = intersections[0][pt3]; - xy1 = cubic1.xyAtT(tt1); + xy1 = cubic1.ptAtT(tt1); tt2 = intersections[1][pt3]; - xy2 = cubic2.xyAtT(tt2); + xy2 = cubic2.ptAtT(tt2); const SkDPoint& iPt = intersections.pt(pt3); #if ONE_OFF_DEBUG SkDebugf("%s t1=%1.9g (%1.9g, %1.9g) (%1.9g, %1.9g) (%1.9g, %1.9g) t2=%1.9g\n", @@ -391,9 +404,9 @@ static void CubicIntersection_RandTest(skiatest::Reporter* reporter) { } for (int pt = 0; pt < intersections2.used(); ++pt) { double tt1 = intersections2[0][pt]; - SkDPoint xy1 = cubic1.xyAtT(tt1); + SkDPoint xy1 = cubic1.ptAtT(tt1); double tt2 = intersections2[1][pt]; - SkDPoint xy2 = cubic2.xyAtT(tt2); + SkDPoint xy2 = cubic2.ptAtT(tt2); REPORTER_ASSERT(reporter, xy1.approximatelyEqual(xy2)); } } @@ -406,12 +419,12 @@ static void intersectionFinder(int index0, int index1, double t1Seed, double t2S SkDPoint t1[3], t2[3]; bool toggle = true; do { - t1[0] = cubic1.xyAtT(t1Seed - t1Step); - t1[1] = cubic1.xyAtT(t1Seed); - t1[2] = cubic1.xyAtT(t1Seed + t1Step); - t2[0] = cubic2.xyAtT(t2Seed - t2Step); - t2[1] = cubic2.xyAtT(t2Seed); - t2[2] = cubic2.xyAtT(t2Seed + t2Step); + t1[0] = cubic1.ptAtT(t1Seed - t1Step); + t1[1] = cubic1.ptAtT(t1Seed); + t1[2] = cubic1.ptAtT(t1Seed + t1Step); + t2[0] = cubic2.ptAtT(t2Seed - t2Step); + t2[1] = cubic2.ptAtT(t2Seed); + t2[2] = cubic2.ptAtT(t2Seed + t2Step); double dist[3][3]; dist[1][1] = t1[1].distance(t2[1]); int best_i = 1, best_j = 1; @@ -452,38 +465,38 @@ static void intersectionFinder(int index0, int index1, double t1Seed, double t2S double t22 = t2Seed + t2Step * 2; SkDPoint test; while (!approximately_zero(t1Step)) { - test = cubic1.xyAtT(t10); + test = cubic1.ptAtT(t10); t10 += t1[1].approximatelyEqual(test) ? -t1Step : t1Step; t1Step /= 2; } t1Step = 0.1; while (!approximately_zero(t1Step)) { - test = cubic1.xyAtT(t12); + test = cubic1.ptAtT(t12); t12 -= t1[1].approximatelyEqual(test) ? -t1Step : t1Step; t1Step /= 2; } while (!approximately_zero(t2Step)) { - test = cubic2.xyAtT(t20); + test = cubic2.ptAtT(t20); t20 += t2[1].approximatelyEqual(test) ? -t2Step : t2Step; t2Step /= 2; } t2Step = 0.1; while (!approximately_zero(t2Step)) { - test = cubic2.xyAtT(t22); + test = cubic2.ptAtT(t22); t22 -= t2[1].approximatelyEqual(test) ? -t2Step : t2Step; t2Step /= 2; } #if ONE_OFF_DEBUG SkDebugf("%s t1=(%1.9g<%1.9g<%1.9g) t2=(%1.9g<%1.9g<%1.9g)\n", __FUNCTION__, t10, t1Seed, t12, t20, t2Seed, t22); - SkDPoint p10 = cubic1.xyAtT(t10); - SkDPoint p1Seed = cubic1.xyAtT(t1Seed); - SkDPoint p12 = cubic1.xyAtT(t12); + SkDPoint p10 = cubic1.ptAtT(t10); + SkDPoint p1Seed = cubic1.ptAtT(t1Seed); + SkDPoint p12 = cubic1.ptAtT(t12); SkDebugf("%s p1=(%1.9g,%1.9g)<(%1.9g,%1.9g)<(%1.9g,%1.9g)\n", __FUNCTION__, p10.fX, p10.fY, p1Seed.fX, p1Seed.fY, p12.fX, p12.fY); - SkDPoint p20 = cubic2.xyAtT(t20); - SkDPoint p2Seed = cubic2.xyAtT(t2Seed); - SkDPoint p22 = cubic2.xyAtT(t22); + SkDPoint p20 = cubic2.ptAtT(t20); + SkDPoint p2Seed = cubic2.ptAtT(t2Seed); + SkDPoint p22 = cubic2.ptAtT(t22); SkDebugf("%s p2=(%1.9g,%1.9g)<(%1.9g,%1.9g)<(%1.9g,%1.9g)\n", __FUNCTION__, p20.fX, p20.fY, p2Seed.fX, p2Seed.fY, p22.fX, p22.fY); #endif @@ -499,54 +512,65 @@ static void CubicIntersection_IntersectionFinder() { intersectionFinder(0, 1, 0.865213351, 0.865208087, t1Step, t2Step); } +static const SkDCubic selfSet[] = { + {{{2, 3}, {0, 4}, {3, 2}, {5, 3}}}, + {{{3, 6}, {2, 3}, {4, 0}, {3, 2}}}, + {{{0, 2}, {2, 3}, {5, 1}, {3, 2}}}, + {{{0, 2}, {3, 5}, {5, 0}, {4, 2}}}, + {{{3.34, 8.98}, {1.95, 10.27}, {3.76, 7.65}, {4.96, 10.64}}}, + {{{3.13, 2.74}, {1.08, 4.62}, {3.71, 0.94}, {2.01, 3.81}}}, + {{{6.71, 3.14}, {7.99, 2.75}, {8.27, 1.96}, {6.35, 3.57}}}, + {{{12.81, 7.27}, {7.22, 6.98}, {12.49, 8.97}, {11.42, 6.18}}}, +}; +size_t selfSetCount = SK_ARRAY_COUNT(selfSet); + +static void selfOneOff(skiatest::Reporter* reporter, int index) { + const SkDCubic& cubic = selfSet[index]; +#if ONE_OFF_DEBUG + int idx2; + double max[3]; + int ts = cubic.findMaxCurvature(max); + for (idx2 = 0; idx2 < ts; ++idx2) { + SkDebugf("%s max[%d]=%1.9g (%1.9g, %1.9g)\n", __FUNCTION__, idx2, + max[idx2], cubic.ptAtT(max[idx2]).fX, cubic.ptAtT(max[idx2]).fY); + } + SkTArray<double, true> ts1; + SkTArray<SkDQuad, true> quads1; + cubic.toQuadraticTs(cubic.calcPrecision(), &ts1); + for (idx2 = 0; idx2 < ts1.count(); ++idx2) { + SkDebugf("%s t[%d]=%1.9g\n", __FUNCTION__, idx2, ts1[idx2]); + } + CubicToQuads(cubic, cubic.calcPrecision(), quads1); + for (idx2 = 0; idx2 < quads1.count(); ++idx2) { + const SkDQuad& q = quads1[idx2]; + SkDebugf(" {{{%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}}},\n", + q[0].fX, q[0].fY, q[1].fX, q[1].fY, q[2].fX, q[2].fY); + } + SkDebugf("\n"); +#endif + SkIntersections i; + int result = i.intersect(cubic); + REPORTER_ASSERT(reporter, result == 1); + REPORTER_ASSERT(reporter, i.used() == 1); + REPORTER_ASSERT(reporter, !approximately_equal(i[0][0], i[1][0])); + SkDPoint pt1 = cubic.ptAtT(i[0][0]); + SkDPoint pt2 = cubic.ptAtT(i[1][0]); + REPORTER_ASSERT(reporter, pt1.approximatelyEqual(pt2)); +} + static void cubicIntersectionSelfTest(skiatest::Reporter* reporter) { - const SkDCubic selfSet[] = { - {{{0, 2}, {2, 3}, {5, 1}, {3, 2}}}, - {{{0, 2}, {3, 5}, {5, 0}, {4, 2}}}, - {{{3.34, 8.98}, {1.95, 10.27}, {3.76, 7.65}, {4.96, 10.64}}}, - {{{3.13, 2.74}, {1.08, 4.62}, {3.71, 0.94}, {2.01, 3.81}}}, - {{{6.71, 3.14}, {7.99, 2.75}, {8.27, 1.96}, {6.35, 3.57}}}, - {{{12.81, 7.27}, {7.22, 6.98}, {12.49, 8.97}, {11.42, 6.18}}}, - }; - size_t selfSetCount = SK_ARRAY_COUNT(selfSet); - size_t firstFail = 1; + size_t firstFail = 0; for (size_t index = firstFail; index < selfSetCount; ++index) { - const SkDCubic& cubic = selfSet[index]; - #if ONE_OFF_DEBUG - int idx2; - double max[3]; - int ts = cubic.findMaxCurvature(max); - for (idx2 = 0; idx2 < ts; ++idx2) { - SkDebugf("%s max[%d]=%1.9g (%1.9g, %1.9g)\n", __FUNCTION__, idx2, - max[idx2], cubic.xyAtT(max[idx2]).fX, cubic.xyAtT(max[idx2]).fY); - } - SkTArray<double, true> ts1; - SkTArray<SkDQuad, true> quads1; - cubic.toQuadraticTs(cubic.calcPrecision(), &ts1); - for (idx2 = 0; idx2 < ts1.count(); ++idx2) { - SkDebugf("%s t[%d]=%1.9g\n", __FUNCTION__, idx2, ts1[idx2]); - } - CubicToQuads(cubic, cubic.calcPrecision(), quads1); - for (idx2 = 0; idx2 < quads1.count(); ++idx2) { - const SkDQuad& q = quads1[idx2]; - SkDebugf(" {{{%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}}},\n", - q[0].fX, q[0].fY, q[1].fX, q[1].fY, q[2].fX, q[2].fY); - } - SkDebugf("\n"); - #endif - SkIntersections i; - int result = i.intersect(cubic); - REPORTER_ASSERT(reporter, result == 1); - REPORTER_ASSERT(reporter, i.used() == 1); - REPORTER_ASSERT(reporter, !approximately_equal(i[0][0], i[1][0])); - SkDPoint pt1 = cubic.xyAtT(i[0][0]); - SkDPoint pt2 = cubic.xyAtT(i[1][0]); - REPORTER_ASSERT(reporter, pt1.approximatelyEqual(pt2)); + selfOneOff(reporter, index); } } static void PathOpsCubicIntersectionOneOffTest(skiatest::Reporter* reporter) { - newOneOff(reporter, 6, 7); + newOneOff(reporter, 0, 1); +} + +static void PathOpsCubicSelfOneOffTest(skiatest::Reporter* reporter) { + selfOneOff(reporter, 0); } static void PathOpsCubicIntersectionTest(skiatest::Reporter* reporter) { @@ -561,3 +585,5 @@ static void PathOpsCubicIntersectionTest(skiatest::Reporter* reporter) { DEFINE_TESTCLASS_SHORT(PathOpsCubicIntersectionTest) DEFINE_TESTCLASS_SHORT(PathOpsCubicIntersectionOneOffTest) + +DEFINE_TESTCLASS_SHORT(PathOpsCubicSelfOneOffTest) diff --git a/tests/PathOpsCubicLineIntersectionTest.cpp b/tests/PathOpsCubicLineIntersectionTest.cpp index 2f52b3b1f2..866acb34fd 100644 --- a/tests/PathOpsCubicLineIntersectionTest.cpp +++ b/tests/PathOpsCubicLineIntersectionTest.cpp @@ -54,9 +54,9 @@ static void testOne(skiatest::Reporter* reporter, int iIndex) { int roots = i.intersect(cubic, line); for (int pt = 0; pt < roots; ++pt) { double tt1 = i[0][pt]; - SkDPoint xy1 = cubic.xyAtT(tt1); + SkDPoint xy1 = cubic.ptAtT(tt1); double tt2 = i[1][pt]; - SkDPoint xy2 = line.xyAtT(tt2); + SkDPoint xy2 = line.ptAtT(tt2); if (!xy1.approximatelyEqual(xy2)) { SkDebugf("%s [%d,%d] x!= t1=%g (%g,%g) t2=%g (%g,%g)\n", __FUNCTION__, iIndex, pt, tt1, xy1.fX, xy1.fY, tt2, xy2.fX, xy2.fY); @@ -84,15 +84,15 @@ static void PathOpsCubicLineIntersectionOneOffTest(skiatest::Reporter* reporter) SkASSERT(i.used() == 1); #if ONE_OFF_DEBUG double cubicT = i[0][0]; - SkDPoint prev = cubic.xyAtT(cubicT * 2 - 1); - SkDPoint sect = cubic.xyAtT(cubicT); + SkDPoint prev = cubic.ptAtT(cubicT * 2 - 1); + SkDPoint sect = cubic.ptAtT(cubicT); double left[3] = { line.isLeft(prev), line.isLeft(sect), line.isLeft(cubic[3]) }; SkDebugf("cubic=(%1.9g, %1.9g, %1.9g)\n", left[0], left[1], left[2]); SkDebugf("{{%1.9g,%1.9g}, {%1.9g,%1.9g}},\n", prev.fX, prev.fY, sect.fX, sect.fY); SkDebugf("{{%1.9g,%1.9g}, {%1.9g,%1.9g}},\n", sect.fX, sect.fY, cubic[3].fX, cubic[3].fY); - SkDPoint prevL = line.xyAtT(i[1][0] - 0.0000007); + SkDPoint prevL = line.ptAtT(i[1][0] - 0.0000007); SkDebugf("{{%1.9g,%1.9g}, {%1.9g,%1.9g}},\n", prevL.fX, prevL.fY, i.pt(0).fX, i.pt(0).fY); - SkDPoint nextL = line.xyAtT(i[1][0] + 0.0000007); + SkDPoint nextL = line.ptAtT(i[1][0] + 0.0000007); SkDebugf("{{%1.9g,%1.9g}, {%1.9g,%1.9g}},\n", i.pt(0).fX, i.pt(0).fY, nextL.fX, nextL.fY); SkDebugf("prevD=%1.9g dist=%1.9g nextD=%1.9g\n", prev.distance(nextL), sect.distance(i.pt(0)), cubic[3].distance(prevL)); diff --git a/tests/PathOpsCubicQuadIntersectionTest.cpp b/tests/PathOpsCubicQuadIntersectionTest.cpp index 42a5d33cb1..76ecd01a47 100644 --- a/tests/PathOpsCubicQuadIntersectionTest.cpp +++ b/tests/PathOpsCubicQuadIntersectionTest.cpp @@ -52,9 +52,9 @@ static void PathOpsCubicQuadIntersectionTest(skiatest::Reporter* reporter) { SkASSERT(roots == quadCubicTests[index].answerCount); for (int pt = 0; pt < roots; ++pt) { double tt1 = i[0][pt]; - SkDPoint xy1 = cubic.xyAtT(tt1); + SkDPoint xy1 = cubic.ptAtT(tt1); double tt2 = i[1][pt]; - SkDPoint xy2 = quad.xyAtT(tt2); + SkDPoint xy2 = quad.ptAtT(tt2); if (!xy1.approximatelyEqual(xy2)) { SkDebugf("%s [%d,%d] x!= t1=%g (%g,%g) t2=%g (%g,%g)\n", __FUNCTION__, iIndex, pt, tt1, xy1.fX, xy1.fY, tt2, xy2.fX, xy2.fY); diff --git a/tests/PathOpsDLineTest.cpp b/tests/PathOpsDLineTest.cpp index feab21d466..ea816c5b8f 100644 --- a/tests/PathOpsDLineTest.cpp +++ b/tests/PathOpsDLineTest.cpp @@ -47,7 +47,7 @@ static void PathOpsLineUtilitiesTest(skiatest::Reporter* reporter) { REPORTER_ASSERT(reporter, line[0] == line2[1] && line[1] == line2[0]); line2 = SkDLine::SubDivide(pts, 1, 0); REPORTER_ASSERT(reporter, line[0] == line2[1] && line[1] == line2[0]); - SkDPoint mid = line.xyAtT(.5); + SkDPoint mid = line.ptAtT(.5); REPORTER_ASSERT(reporter, approximately_equal((line[0].fX + line[1].fX) / 2, mid.fX)); REPORTER_ASSERT(reporter, approximately_equal((line[0].fY + line[1].fY) / 2, mid.fY)); } diff --git a/tests/PathOpsLineIntersectionTest.cpp b/tests/PathOpsLineIntersectionTest.cpp index f2bef912eb..57b42ec3c0 100644 --- a/tests/PathOpsLineIntersectionTest.cpp +++ b/tests/PathOpsLineIntersectionTest.cpp @@ -11,6 +11,8 @@ // FIXME: add tests for intersecting, non-intersecting, degenerate, coincident static const SkDLine tests[][2] = { + {{{{181.1764678955078125f, 120}, {186.3661956787109375f, 134.7042236328125f}}},
+ {{{175.8309783935546875f, 141.5211334228515625f}, {187.8782806396484375f, 133.7258148193359375f}}}}, #if 0 // FIXME: these fail because one line is too short and appears quasi-coincident {{{{158.000000, 926.000000}, {1108.00000, 926.000000}}}, {{{1108.00000, 926.000000}, {1108.00000, 925.999634}}}}, @@ -41,8 +43,11 @@ static const SkDLine noIntersect[][2] = { static const size_t noIntersect_count = SK_ARRAY_COUNT(noIntersect); static const SkDLine coincidentTests[][2] = { + {{{{186.3661956787109375f, 134.7042236328125f}, {187.8782806396484375f, 133.7258148193359375f}}},
+ {{{175.8309783935546875f, 141.5211334228515625f}, {187.8782806396484375f, 133.7258148193359375f}}}}, + {{{{235.681549, 531.000000}, {280.318420, 321.000000}}}, - {{{286.695129, 291.000000}, {229.304855, 561.000000}}}}, + {{{286.695129, 291.000000}, {229.304855, 561.000000}}}}, }; static const size_t coincidentTests_count = SK_ARRAY_COUNT(coincidentTests); @@ -50,11 +55,11 @@ static const size_t coincidentTests_count = SK_ARRAY_COUNT(coincidentTests); static void check_results(skiatest::Reporter* reporter, const SkDLine& line1, const SkDLine& line2, const SkIntersections& ts) { for (int i = 0; i < ts.used(); ++i) { - SkDPoint result1 = line1.xyAtT(ts[0][i]); - SkDPoint result2 = line2.xyAtT(ts[1][i]); + SkDPoint result1 = line1.ptAtT(ts[0][i]); + SkDPoint result2 = line2.ptAtT(ts[1][i]); if (!result1.approximatelyEqual(result2)) { REPORTER_ASSERT(reporter, ts.used() != 1); - result2 = line2.xyAtT(ts[1][i ^ 1]); + result2 = line2.ptAtT(ts[1][i ^ 1]); REPORTER_ASSERT(reporter, result1.approximatelyEqual(result2)); REPORTER_ASSERT(reporter, result1.approximatelyEqual(ts.pt(i).asSkPoint())); } @@ -146,7 +151,7 @@ static void PathOpsLineIntersectionTest(skiatest::Reporter* reporter) { } } -static void PathOpsLineIntersectionTestOne(skiatest::Reporter* reporter) { +static void PathOpsLineIntersectionOneOffTest(skiatest::Reporter* reporter) { int index = 0; SkASSERT(index < (int) tests_count); const SkDLine& line1 = tests[index][0]; @@ -154,7 +159,7 @@ static void PathOpsLineIntersectionTestOne(skiatest::Reporter* reporter) { testOne(reporter, line1, line2); } -static void PathOpsLineIntersectionTestOneCoincident(skiatest::Reporter* reporter) { +static void PathOpsLineIntersectionOneCoincidentTest(skiatest::Reporter* reporter) { int index = 0; SkASSERT(index < (int) coincidentTests_count); const SkDLine& line1 = coincidentTests[index][0]; @@ -165,6 +170,6 @@ static void PathOpsLineIntersectionTestOneCoincident(skiatest::Reporter* reporte #include "TestClassDef.h" DEFINE_TESTCLASS_SHORT(PathOpsLineIntersectionTest) -DEFINE_TESTCLASS_SHORT(PathOpsLineIntersectionTestOne) +DEFINE_TESTCLASS_SHORT(PathOpsLineIntersectionOneOffTest) -DEFINE_TESTCLASS_SHORT(PathOpsLineIntersectionTestOneCoincident) +DEFINE_TESTCLASS_SHORT(PathOpsLineIntersectionOneCoincidentTest) diff --git a/tests/PathOpsOpTest.cpp b/tests/PathOpsOpTest.cpp index c81f1dc025..a85c435f98 100644 --- a/tests/PathOpsOpTest.cpp +++ b/tests/PathOpsOpTest.cpp @@ -1803,7 +1803,6 @@ static void cubicOp85d(skiatest::Reporter* reporter) { testPathOp(reporter, path, pathB, kDifference_PathOp); } -#if 0 // FIXME // this fails because the pair of nearly coincident cubics intersect at the ends // but the line connected to one of the cubics at the same point does not intersect // the other @@ -1834,158 +1833,194 @@ static void skpkkiste_to98(skiatest::Reporter* reporter) { pathB.close(); testPathOp(reporter, path, pathB, kIntersect_PathOp); } -#endif -#if 0 // https://code.google.com/p/skia/issues/detail?id=1417 +#if 01 static void issue1417(skiatest::Reporter* reporter) { - SkPath path1; - path1.moveTo(122.589f, 82.2836f); - path1.quadTo(129.822f, 80, 138, 80); - path1.quadTo(147.157f, 80, 155.128f, 82.8628f); - path1.lineTo(161.176f, 100); - path1.lineTo(161.176f, 100); - path1.lineTo(115.294f, 100); - path1.lineTo(115.294f, 100); - path1.lineTo(122.589f, 82.2836f); - path1.lineTo(122.589f, 82.2836f); - path1.close(); - path1.moveTo(98.6819f, 140.344f); - path1.lineTo(115.294f, 100); - path1.lineTo(115.294f, 100); - path1.lineTo(97.9338f, 100); - path1.lineTo(97.9338f, 100); - path1.quadTo(88, 112.943f, 88, 130); - path1.quadTo(88, 131.545f, 88.0815f, 133.056f); - path1.lineTo(98.6819f, 140.344f); - path1.lineTo(98.6819f, 140.344f); - path1.close(); - path1.moveTo(136.97f, 166.667f); - path1.lineTo(98.6819f, 140.344f); - path1.lineTo(98.6819f, 140.344f); - path1.lineTo(93.4589f, 153.028f); - path1.lineTo(93.4589f, 153.028f); - path1.quadTo(96.9412f, 159.652f, 102.645f, 165.355f); - path1.quadTo(110.792f, 173.503f, 120.818f, 177.118f); - path1.lineTo(136.97f, 166.667f); - path1.lineTo(136.97f, 166.667f); - path1.close(); - path1.moveTo(175.831f, 141.521f); - path1.lineTo(136.97f, 166.667f); - path1.lineTo(136.97f, 166.667f); - path1.lineTo(153.157f, 177.796f); - path1.lineTo(153.157f, 177.796f); - path1.quadTo(164.392f, 174.318f, 173.355f, 165.355f); - path1.quadTo(177.806f, 160.905f, 180.904f, 155.894f); - path1.lineTo(175.831f, 141.521f); - path1.lineTo(175.831f, 141.521f); - path1.close(); - path1.moveTo(175.831f, 141.521f); - path1.lineTo(187.878f, 133.726f); - path1.lineTo(187.878f, 133.726f); - path1.quadTo(188, 131.888f, 188, 130); - path1.quadTo(188, 112.943f, 178.066f, 100); - path1.lineTo(161.176f, 100); - path1.lineTo(161.176f, 100); - path1.lineTo(175.831f, 141.521f); - path1.lineTo(175.831f, 141.521f); - path1.close(); - - SkPath path2; - path2.moveTo(174.118f, 100); - path2.lineTo(161.176f, 100); - path2.lineTo(161.176f, 100); - path2.lineTo(155.128f, 82.8628f); - path2.lineTo(155.128f, 82.8628f); - path2.quadTo(153.15f, 82.1523f, 151.098f, 81.6181f); - path2.lineTo(143.529f, 100); - path2.lineTo(143.529f, 100); - path2.lineTo(161.176f, 100); - path2.lineTo(161.176f, 100); - path2.lineTo(168.235f, 120); - path2.lineTo(168.235f, 120); - path2.lineTo(181.176f, 120); - path2.lineTo(181.176f, 120); - path2.lineTo(186.366f, 134.704f); - path2.lineTo(186.366f, 134.704f); - path2.lineTo(187.878f, 133.726f); - path2.lineTo(187.878f, 133.726f); - path2.quadTo(188, 131.888f, 188, 130); - path2.quadTo(188, 124.809f, 187.08f, 120); - path2.lineTo(181.176f, 120); - path2.lineTo(181.176f, 120); - path2.lineTo(174.118f, 100); - path2.lineTo(174.118f, 100); - path2.close(); - path2.moveTo(88.9198f, 120); - path2.lineTo(107.059f, 120); - path2.lineTo(107.059f, 120); - path2.lineTo(98.6819f, 140.344f); - path2.lineTo(98.6819f, 140.344f); - path2.lineTo(88.0815f, 133.056f); - path2.lineTo(88.0815f, 133.056f); - path2.quadTo(88, 131.545f, 88, 130); - path2.quadTo(88, 124.81f, 88.9198f, 120); - path2.close(); - path2.moveTo(96.6762f, 145.215f); - path2.lineTo(98.6819f, 140.344f); - path2.lineTo(98.6819f, 140.344f); - path2.lineTo(120.688f, 155.473f); - path2.lineTo(120.688f, 155.473f); - path2.lineTo(118.682f, 160.344f); - path2.lineTo(118.682f, 160.344f); - path2.lineTo(96.6762f, 145.215f); - path2.lineTo(96.6762f, 145.215f); - path2.close(); - path2.moveTo(113.232f, 173.579f); - path2.quadTo(116.88f, 175.698f, 120.818f, 177.118f); - path2.lineTo(132.286f, 169.697f); - path2.lineTo(132.286f, 169.697f); - path2.lineTo(118.682f, 160.344f); - path2.lineTo(118.682f, 160.344f); - path2.lineTo(113.232f, 173.579f); - path2.lineTo(113.232f, 173.579f); - path2.close(); + SkPath path1;
+ path1.moveTo(122.58908843994140625f, 82.2836456298828125f);
+ path1.quadTo(129.8215789794921875f, 80, 138, 80);
+ path1.quadTo(147.15692138671875f, 80, 155.1280364990234375f, 82.86279296875f);
+ path1.lineTo(161.1764678955078125f, 100);
+ path1.lineTo(161.1764678955078125f, 100);
+ path1.lineTo(115.29412078857421875f, 100);
+ path1.lineTo(115.29412078857421875f, 100);
+ path1.lineTo(122.58908843994140625f, 82.2836456298828125f);
+ path1.lineTo(122.58908843994140625f, 82.2836456298828125f);
+ path1.close();
+ path1.moveTo(98.68194580078125f, 140.343841552734375f);
+ path1.lineTo(115.29412078857421875f, 100);
+ path1.lineTo(115.29412078857421875f, 100);
+ path1.lineTo(97.9337615966796875f, 100);
+ path1.lineTo(97.9337615966796875f, 100);
+ path1.quadTo(88, 112.94264984130859375f, 88, 130);
+ path1.quadTo(88, 131.544830322265625f, 88.08148956298828125f, 133.0560302734375f);
+ path1.lineTo(98.68194580078125f, 140.343841552734375f);
+ path1.lineTo(98.68194580078125f, 140.343841552734375f);
+ path1.close();
+ path1.moveTo(136.969696044921875f, 166.6666717529296875f);
+ path1.lineTo(98.68194580078125f, 140.343841552734375f);
+ path1.lineTo(98.68194580078125f, 140.343841552734375f);
+ path1.lineTo(93.45894622802734375f, 153.02825927734375f);
+ path1.lineTo(93.45894622802734375f, 153.02825927734375f);
+ path1.quadTo(96.94116973876953125f, 159.65185546875f, 102.64466094970703125f, 165.3553466796875f);
+ path1.quadTo(110.7924652099609375f, 173.503143310546875f, 120.8179779052734375f, 177.1177825927734375f);
+ path1.lineTo(136.969696044921875f, 166.6666717529296875f);
+ path1.lineTo(136.969696044921875f, 166.6666717529296875f);
+ path1.close();
+ path1.moveTo(175.8309783935546875f, 141.5211334228515625f);
+ path1.lineTo(136.969696044921875f, 166.6666717529296875f);
+ path1.lineTo(136.969696044921875f, 166.6666717529296875f);
+ path1.lineTo(153.15728759765625f, 177.7956390380859375f);
+ path1.lineTo(153.15728759765625f, 177.7956390380859375f);
+ path1.quadTo(164.392425537109375f, 174.318267822265625f, 173.3553466796875f, 165.3553466796875f);
+ path1.quadTo(177.805816650390625f, 160.9048614501953125f, 180.90380859375f, 155.8941650390625f);
+ path1.lineTo(175.8309783935546875f, 141.5211334228515625f);
+ path1.lineTo(175.8309783935546875f, 141.5211334228515625f);
+ path1.close();
+ path1.moveTo(175.8309783935546875f, 141.5211334228515625f);
+ path1.lineTo(187.8782806396484375f, 133.7258148193359375f);
+ path1.lineTo(187.8782806396484375f, 133.7258148193359375f);
+ path1.quadTo(188, 131.8880615234375f, 188, 130);
+ path1.quadTo(188, 112.942657470703125f, 178.0662384033203125f, 100);
+ path1.lineTo(161.1764678955078125f, 100);
+ path1.lineTo(161.1764678955078125f, 100);
+ path1.lineTo(175.8309783935546875f, 141.5211334228515625f);
+ path1.lineTo(175.8309783935546875f, 141.5211334228515625f);
+ path1.close();
+
+ SkPath path2;
+ path2.moveTo(174.117645263671875f, 100);
+ path2.lineTo(161.1764678955078125f, 100);
+ path2.lineTo(161.1764678955078125f, 100);
+ path2.lineTo(155.1280364990234375f, 82.86279296875f);
+ path2.lineTo(155.1280364990234375f, 82.86279296875f);
+ path2.quadTo(153.14971923828125f, 82.15229034423828125f, 151.098419189453125f, 81.618133544921875f);
+ path2.lineTo(143.5294189453125f, 100);
+ path2.lineTo(143.5294189453125f, 100);
+ path2.lineTo(161.1764678955078125f, 100);
+ path2.lineTo(161.1764678955078125f, 100);
+ path2.lineTo(168.23529052734375f, 120);
+ path2.lineTo(168.23529052734375f, 120);
+ path2.lineTo(181.1764678955078125f, 120);
+ path2.lineTo(181.1764678955078125f, 120);
+ path2.lineTo(186.3661956787109375f, 134.7042236328125f);
+ path2.lineTo(186.3661956787109375f, 134.7042236328125f);
+ path2.lineTo(187.8782806396484375f, 133.7258148193359375f);
+ path2.lineTo(187.8782806396484375f, 133.7258148193359375f);
+ path2.quadTo(188, 131.8880615234375f, 188, 130);
+ path2.quadTo(188, 124.80947113037109375f, 187.080169677734375f, 120);
+ path2.lineTo(181.1764678955078125f, 120);
+ path2.lineTo(181.1764678955078125f, 120);
+ path2.lineTo(174.117645263671875f, 100);
+ path2.lineTo(174.117645263671875f, 100);
+ path2.close();
+ path2.moveTo(88.91983795166015625f, 120);
+ path2.lineTo(107.0588226318359375f, 120);
+ path2.lineTo(107.0588226318359375f, 120);
+ path2.lineTo(98.68194580078125f, 140.343841552734375f);
+ path2.lineTo(98.68194580078125f, 140.343841552734375f);
+ path2.lineTo(88.08148956298828125f, 133.0560302734375f);
+ path2.lineTo(88.08148956298828125f, 133.0560302734375f);
+ path2.quadTo(88, 131.544830322265625f, 88, 130);
+ path2.quadTo(88, 124.80951690673828125f, 88.91983795166015625f, 120);
+ path2.close();
+ path2.moveTo(96.67621612548828125f, 145.21490478515625f);
+ path2.lineTo(98.68194580078125f, 140.343841552734375f);
+ path2.lineTo(98.68194580078125f, 140.343841552734375f);
+ path2.lineTo(120.68767547607421875f, 155.4727783203125f);
+ path2.lineTo(120.68767547607421875f, 155.4727783203125f);
+ path2.lineTo(118.68194580078125f, 160.343841552734375f);
+ path2.lineTo(118.68194580078125f, 160.343841552734375f);
+ path2.lineTo(96.67621612548828125f, 145.21490478515625f);
+ path2.lineTo(96.67621612548828125f, 145.21490478515625f);
+ path2.close();
+ path2.moveTo(113.232177734375f, 173.5789947509765625f);
+ path2.quadTo(116.8802642822265625f, 175.69805908203125f, 120.8179779052734375f, 177.1177825927734375f);
+ path2.lineTo(132.2864990234375f, 169.6969757080078125f);
+ path2.lineTo(132.2864990234375f, 169.6969757080078125f);
+ path2.lineTo(118.68194580078125f, 160.343841552734375f);
+ path2.lineTo(118.68194580078125f, 160.343841552734375f);
+ path2.lineTo(113.232177734375f, 173.5789947509765625f);
+ path2.lineTo(113.232177734375f, 173.5789947509765625f);
+ path2.close();
testPathOp(reporter, path1, path2, kUnion_PathOp); } #endif -#if 0 // https://code.google.com/p/skia/issues/detail?id=1418 static void issue1418(skiatest::Reporter* reporter) { - SkPath path1; - path1.moveTo(0, 0); - path1.lineTo(1, 0); - path1.lineTo(1, 0); - path1.lineTo(1, 1); - path1.lineTo(1, 1); - path1.lineTo(0, 1); - path1.lineTo(0, 1); - path1.lineTo(0, 0); - path1.lineTo(0, 0); - path1.close(); - - SkPath path2; - path2.moveTo(0.646447f, -0.353553f); - path2.quadTo(0.792893f, -0.5f, 1, -0.5f); - path2.quadTo(1.20711f, -0.5f, 1.35355f, -0.353553f); - path2.quadTo(1.5f, -0.207107f, 1.5f, 0); - path2.quadTo(1.5f, 0.207107f, 1.35355f, 0.353553f); - path2.quadTo(1.20711f, 0.5f, 1, 0.5f); - path2.quadTo(0.792893f, 0.5f, 0.646447f, 0.353553f); - path2.quadTo(0.5f, 0.207107f, 0.5f, 0); - path2.quadTo(0.5f, -0.207107f, 0.646447f, -0.353553f); - path2.close(); - + SkPath path1;
+ path1.moveTo(0, 0);
+ path1.lineTo(1, 0);
+ path1.lineTo(1, 0);
+ path1.lineTo(1, 1);
+ path1.lineTo(1, 1);
+ path1.lineTo(0, 1);
+ path1.lineTo(0, 1);
+ path1.lineTo(0, 0);
+ path1.lineTo(0, 0);
+ path1.close();
+
+ SkPath path2;
+ path2.moveTo(0.64644664525985717773f, -0.35355341434478759766f);
+ path2.quadTo(0.79289329051971435547f, -0.50000005960464477539f, 1.0000001192092895508f, -0.50000005960464477539f);
+ path2.quadTo(1.2071068286895751953f, -0.50000005960464477539f, 1.3535535335540771484f, -0.35355341434478759766f);
+ path2.quadTo(1.5000001192092895508f, -0.20710679888725280762f, 1.5000001192092895508f, 0);
+ path2.quadTo(1.5000001192092895508f, 0.20710679888725280762f, 1.3535535335540771484f, 0.35355341434478759766f);
+ path2.quadTo(1.2071068286895751953f, 0.50000005960464477539f, 1.0000001192092895508f, 0.50000005960464477539f);
+ path2.quadTo(0.79289329051971435547f, 0.50000005960464477539f, 0.64644664525985717773f, 0.35355341434478759766f);
+ path2.quadTo(0.50000005960464477539f, 0.20710679888725280762f, 0.50000005960464477539f, 0);
+ path2.quadTo(0.50000005960464477539f, -0.20710679888725280762f, 0.64644664525985717773f, -0.35355341434478759766f); testPathOp(reporter, path1, path2, kIntersect_PathOp); } + +static void cubicOp85i(skiatest::Reporter* reporter) {
+ SkPath path, pathB;
+ path.setFillType(SkPath::kWinding_FillType);
+ path.moveTo(3, 4);
+ path.cubicTo(1, 5, 4, 3, 6, 4);
+ path.close();
+ pathB.setFillType(SkPath::kWinding_FillType);
+ pathB.moveTo(3, 4);
+ pathB.cubicTo(4, 6, 4, 3, 5, 1);
+ pathB.close();
+ testPathOp(reporter, path, pathB, kIntersect_PathOp);
+} + +#if 0 +static void skpkkiste_to716(skiatest::Reporter* reporter) {
+ SkPath path;
+ path.setFillType(SkPath::kEvenOdd_FillType);
+ path.moveTo(1173, 284);
+ path.cubicTo(1173, 285.125824f, 1173.37207f, 286.164734f, 1174, 287.000488f);
+ path.lineTo(1174, 123.999496f);
+ path.cubicTo(1173.37207f, 124.835243f, 1173, 125.874168f, 1173, 127);
+ path.lineTo(1173, 284);
+ path.close();
+ SkPath pathB;
+ pathB.setFillType(SkPath::kWinding_FillType);
+ pathB.moveTo(1340, 122);
+ pathB.cubicTo(1342.76147f, 122, 1345, 124.238579f, 1345, 127);
+ pathB.lineTo(1345, 284);
+ pathB.cubicTo(1345, 286.761414f, 1342.76147f, 289, 1340, 289);
+ pathB.lineTo(1178, 289);
+ pathB.cubicTo(1175.23853f, 289, 1173, 286.761414f, 1173, 284);
+ pathB.lineTo(1173, 127);
+ pathB.cubicTo(1173, 124.238579f, 1175.23853f, 122, 1178, 122);
+ pathB.lineTo(1340, 122);
+ pathB.close();
+ testPathOp(reporter, path, pathB, kIntersect_PathOp);
+}
#endif static void (*firstTest)(skiatest::Reporter* ) = 0; static struct TestDesc tests[] = { -// TEST(issue1418), -// TEST(issue1417), -// TEST(skpkkiste_to98), + // TEST(skpkkiste_to716), + TEST(cubicOp85i), + TEST(issue1417), + TEST(issue1418), + TEST(skpkkiste_to98), TEST(skpahrefs_com29), TEST(cubicOp85d), TEST(skpahrefs_com88), diff --git a/tests/PathOpsQuadIntersectionTest.cpp b/tests/PathOpsQuadIntersectionTest.cpp index ee2e8de8a1..2d72b41d2d 100644 --- a/tests/PathOpsQuadIntersectionTest.cpp +++ b/tests/PathOpsQuadIntersectionTest.cpp @@ -37,9 +37,9 @@ static void standardTestCases(skiatest::Reporter* reporter) { if (intersections.used() > 0) { for (int pt = 0; pt < intersections.used(); ++pt) { double tt1 = intersections[0][pt]; - SkDPoint xy1 = quad1.xyAtT(tt1); + SkDPoint xy1 = quad1.ptAtT(tt1); double tt2 = intersections[1][pt]; - SkDPoint xy2 = quad2.xyAtT(tt2); + SkDPoint xy2 = quad2.ptAtT(tt2); if (!xy1.approximatelyEqual(xy2)) { SkDebugf("%s [%d,%d] x!= t1=%g (%g,%g) t2=%g (%g,%g)\n", __FUNCTION__, static_cast<int>(index), pt, tt1, xy1.fX, xy1.fY, @@ -256,9 +256,9 @@ static void oneOffTest1(skiatest::Reporter* reporter, size_t outer, size_t inner intersections2.intersect(quad1, quad2); for (int pt = 0; pt < intersections2.used(); ++pt) { double tt1 = intersections2[0][pt]; - SkDPoint xy1 = quad1.xyAtT(tt1); + SkDPoint xy1 = quad1.ptAtT(tt1); double tt2 = intersections2[1][pt]; - SkDPoint xy2 = quad2.xyAtT(tt2); + SkDPoint xy2 = quad2.ptAtT(tt2); if (!xy1.approximatelyEqual(xy2)) { SkDebugf("%s [%d,%d] x!= t1=%g (%g,%g) t2=%g (%g,%g)\n", __FUNCTION__, static_cast<int>(outer), static_cast<int>(inner), @@ -285,6 +285,8 @@ static void oneOffTests(skiatest::Reporter* reporter) { } static const SkDQuad coincidentTestSet[] = { + {{{97.9337615966796875,100}, {88,112.94264984130859375}, {88,130}}}, + {{{88,130}, {88,124.80951690673828125}, {88.91983795166015625,120}}}, {{{369.850525, 145.675964}, {382.362915, 121.29287}, {406.211273, 121.29287}}}, {{{369.850525, 145.675964}, {382.362915, 121.29287}, {406.211273, 121.29287}}}, {{{8, 8}, {10, 10}, {8, -10}}}, @@ -293,25 +295,34 @@ static const SkDQuad coincidentTestSet[] = { const size_t coincidentTestSetCount = SK_ARRAY_COUNT(coincidentTestSet); +static void coincidentTestOne(skiatest::Reporter* reporter, int test1, int test2) { + const SkDQuad& quad1 = coincidentTestSet[test1]; + SkASSERT(ValidQuad(quad1)); + const SkDQuad& quad2 = coincidentTestSet[test2]; + SkASSERT(ValidQuad(quad2)); + SkIntersections intersections2; + intersections2.intersect(quad1, quad2); + REPORTER_ASSERT(reporter, intersections2.coincidentUsed() == 2); + REPORTER_ASSERT(reporter, intersections2.used() == 2); + for (int pt = 0; pt < intersections2.coincidentUsed(); ++pt) { + double tt1 = intersections2[0][pt]; + double tt2 = intersections2[1][pt]; + SkDPoint pt1 = quad1.ptAtT(tt1); + SkDPoint pt2 = quad2.ptAtT(tt2); + REPORTER_ASSERT(reporter, pt1.approximatelyEqual(pt2)); + } +} + static void coincidentTest(skiatest::Reporter* reporter) { for (size_t testIndex = 0; testIndex < coincidentTestSetCount - 1; testIndex += 2) { - const SkDQuad& quad1 = coincidentTestSet[testIndex]; - SkASSERT(ValidQuad(quad1)); - const SkDQuad& quad2 = coincidentTestSet[testIndex + 1]; - SkASSERT(ValidQuad(quad2)); - SkIntersections intersections2; - intersections2.intersect(quad1, quad2); - REPORTER_ASSERT(reporter, intersections2.coincidentUsed() == 2); - REPORTER_ASSERT(reporter, intersections2.used() == 2); - for (int pt = 0; pt < intersections2.coincidentUsed(); ++pt) { - double tt1 = intersections2[0][pt]; - double tt2 = intersections2[1][pt]; - REPORTER_ASSERT(reporter, approximately_equal(1, tt1) || approximately_zero(tt1)); - REPORTER_ASSERT(reporter, approximately_equal(1, tt2) || approximately_zero(tt2)); - } + coincidentTestOne(reporter, testIndex, testIndex + 1); } } +static void PathOpsQuadIntersectionCoincidenceOneOffTest(skiatest::Reporter* reporter) { + coincidentTestOne(reporter, 0, 1); +} + static int floatSign(double x) { return x < 0 ? -1 : x > 0 ? 1 : 0; } @@ -338,7 +349,7 @@ static const SkDQuad pointFinderTestSet[] = { static void pointFinder(const SkDQuad& q1, const SkDQuad& q2) { for (int index = 0; index < 3; ++index) { double t = q1.nearestT(q2[index]); - SkDPoint onQuad = q1.xyAtT(t); + SkDPoint onQuad = q1.ptAtT(t); SkDebugf("%s t=%1.9g (%1.9g,%1.9g) dist=%1.9g\n", __FUNCTION__, t, onQuad.fX, onQuad.fY, onQuad.distance(q2[index])); double left[3]; @@ -388,12 +399,12 @@ static void intersectionFinder(int test1, int test2) { SkDPoint t1[3], t2[3]; bool toggle = true; do { - t1[0] = quad1.xyAtT(t1Seed - t1Step); - t1[1] = quad1.xyAtT(t1Seed); - t1[2] = quad1.xyAtT(t1Seed + t1Step); - t2[0] = quad2.xyAtT(t2Seed - t2Step); - t2[1] = quad2.xyAtT(t2Seed); - t2[2] = quad2.xyAtT(t2Seed + t2Step); + t1[0] = quad1.ptAtT(t1Seed - t1Step); + t1[1] = quad1.ptAtT(t1Seed); + t1[2] = quad1.ptAtT(t1Seed + t1Step); + t2[0] = quad2.ptAtT(t2Seed - t2Step); + t2[1] = quad2.ptAtT(t2Seed); + t2[2] = quad2.ptAtT(t2Seed + t2Step); double dist[3][3]; dist[1][1] = t1[1].distance(t2[1]); int best_i = 1, best_j = 1; @@ -434,38 +445,38 @@ static void intersectionFinder(int test1, int test2) { double t22 = t2Seed + t2Step * 2; SkDPoint test; while (!approximately_zero(t1Step)) { - test = quad1.xyAtT(t10); + test = quad1.ptAtT(t10); t10 += t1[1].approximatelyEqual(test) ? -t1Step : t1Step; t1Step /= 2; } t1Step = 0.1; while (!approximately_zero(t1Step)) { - test = quad1.xyAtT(t12); + test = quad1.ptAtT(t12); t12 -= t1[1].approximatelyEqual(test) ? -t1Step : t1Step; t1Step /= 2; } while (!approximately_zero(t2Step)) { - test = quad2.xyAtT(t20); + test = quad2.ptAtT(t20); t20 += t2[1].approximatelyEqual(test) ? -t2Step : t2Step; t2Step /= 2; } t2Step = 0.1; while (!approximately_zero(t2Step)) { - test = quad2.xyAtT(t22); + test = quad2.ptAtT(t22); t22 -= t2[1].approximatelyEqual(test) ? -t2Step : t2Step; t2Step /= 2; } #if ONE_OFF_DEBUG SkDebugf("%s t1=(%1.9g<%1.9g<%1.9g) t2=(%1.9g<%1.9g<%1.9g)\n", __FUNCTION__, t10, t1Seed, t12, t20, t2Seed, t22); - SkDPoint p10 = quad1.xyAtT(t10); - SkDPoint p1Seed = quad1.xyAtT(t1Seed); - SkDPoint p12 = quad1.xyAtT(t12); + SkDPoint p10 = quad1.ptAtT(t10); + SkDPoint p1Seed = quad1.ptAtT(t1Seed); + SkDPoint p12 = quad1.ptAtT(t12); SkDebugf("%s p1=(%1.9g,%1.9g)<(%1.9g,%1.9g)<(%1.9g,%1.9g)\n", __FUNCTION__, p10.fX, p10.fY, p1Seed.fX, p1Seed.fY, p12.fX, p12.fY); - SkDPoint p20 = quad2.xyAtT(t20); - SkDPoint p2Seed = quad2.xyAtT(t2Seed); - SkDPoint p22 = quad2.xyAtT(t22); + SkDPoint p20 = quad2.ptAtT(t20); + SkDPoint p2Seed = quad2.ptAtT(t2Seed); + SkDPoint p22 = quad2.ptAtT(t22); SkDebugf("%s p2=(%1.9g,%1.9g)<(%1.9g,%1.9g)<(%1.9g,%1.9g)\n", __FUNCTION__, p20.fX, p20.fY, p2Seed.fX, p2Seed.fY, p22.fX, p22.fY); #endif @@ -488,3 +499,5 @@ static void PathOpsQuadIntersectionTest(skiatest::Reporter* reporter) { DEFINE_TESTCLASS_SHORT(PathOpsQuadIntersectionTest) DEFINE_TESTCLASS_SHORT(PathOpsQuadIntersectionOneOffTest) + +DEFINE_TESTCLASS_SHORT(PathOpsQuadIntersectionCoincidenceOneOffTest) diff --git a/tests/PathOpsQuadLineIntersectionTest.cpp b/tests/PathOpsQuadLineIntersectionTest.cpp index 02c925cad2..555a90ce70 100644 --- a/tests/PathOpsQuadLineIntersectionTest.cpp +++ b/tests/PathOpsQuadLineIntersectionTest.cpp @@ -80,9 +80,9 @@ static void testOneOffs(skiatest::Reporter* reporter) { int result = doIntersect(intersections, quad, line, flipped); for (int inner = 0; inner < result; ++inner) { double quadT = intersections[0][inner]; - SkDPoint quadXY = quad.xyAtT(quadT); + SkDPoint quadXY = quad.ptAtT(quadT); double lineT = intersections[1][inner]; - SkDPoint lineXY = line.xyAtT(lineT); + SkDPoint lineXY = line.ptAtT(lineT); REPORTER_ASSERT(reporter, quadXY.approximatelyEqual(lineXY)); } } @@ -120,10 +120,10 @@ static void PathOpsQuadLineIntersectionTest(skiatest::Reporter* reporter) { for (int pt = 0; pt < result; ++pt) { double tt1 = intersections[0][pt]; REPORTER_ASSERT(reporter, tt1 >= 0 && tt1 <= 1); - SkDPoint t1 = quad.xyAtT(tt1); + SkDPoint t1 = quad.ptAtT(tt1); double tt2 = intersections[1][pt]; REPORTER_ASSERT(reporter, tt2 >= 0 && tt2 <= 1); - SkDPoint t2 = line.xyAtT(tt2); + SkDPoint t2 = line.ptAtT(tt2); if (!t1.approximatelyEqual(t2)) { SkDebugf("%s [%d,%d] x!= t1=%1.9g (%1.9g,%1.9g) t2=%1.9g (%1.9g,%1.9g)\n", __FUNCTION__, iIndex, pt, tt1, t1.fX, t1.fY, tt2, t2.fX, t2.fY); diff --git a/tests/PathOpsQuadLineIntersectionThreadedTest.cpp b/tests/PathOpsQuadLineIntersectionThreadedTest.cpp index 7d1b133fac..63f9447edf 100644 --- a/tests/PathOpsQuadLineIntersectionThreadedTest.cpp +++ b/tests/PathOpsQuadLineIntersectionThreadedTest.cpp @@ -55,9 +55,9 @@ static void testLineIntersect(skiatest::Reporter* reporter, const SkDQuad& quad, bool found = false; for (int index = 0; index < result; ++index) { double quadT = intersections[0][index]; - SkDPoint quadXY = quad.xyAtT(quadT); + SkDPoint quadXY = quad.ptAtT(quadT); double lineT = intersections[1][index]; - SkDPoint lineXY = line.xyAtT(lineT); + SkDPoint lineXY = line.ptAtT(lineT); if (quadXY.approximatelyEqual(lineXY)) { found = true; } @@ -89,7 +89,7 @@ static void testQuadLineIntersectMain(PathOpsThreadState* data) return; } for (int tIndex = 0; tIndex <= 4; ++tIndex) { - SkDPoint xy = quad.xyAtT(tIndex / 4.0); + SkDPoint xy = quad.ptAtT(tIndex / 4.0); for (int h = -2; h <= 2; ++h) { for (int v = -2; v <= 2; ++v) { if (h == v && abs(h) != 1) { diff --git a/tests/PathOpsSimplifyTest.cpp b/tests/PathOpsSimplifyTest.cpp index 5f61812b1f..954435fc92 100644 --- a/tests/PathOpsSimplifyTest.cpp +++ b/tests/PathOpsSimplifyTest.cpp @@ -3828,7 +3828,7 @@ static void skphealth_com76(skiatest::Reporter* reporter) { testSimplify(reporter, path); } -static void (*firstTest)(skiatest::Reporter* ) = testLine24a; +static void (*firstTest)(skiatest::Reporter* ) = testQuad6; static TestDesc tests[] = { TEST(skphealth_com76), @@ -4194,7 +4194,7 @@ static const size_t subTestCount = SK_ARRAY_COUNT(subTests); static void (*firstSubTest)(skiatest::Reporter* ) = 0; static bool runSubTestsFirst = false; -static bool runReverse = true; +static bool runReverse = false; static void (*stopTest)(skiatest::Reporter* ) = 0; static void PathOpsSimplifyTest(skiatest::Reporter* reporter) { diff --git a/tests/PathOpsSkpClipTest.cpp b/tests/PathOpsSkpClipTest.cpp index f9d33e16f8..146c42ade7 100644 --- a/tests/PathOpsSkpClipTest.cpp +++ b/tests/PathOpsSkpClipTest.cpp @@ -58,9 +58,8 @@ static void testOne(const SkString& filename) { if (!stream.isValid()) { return; } - bool success; - SkPicture* pic = SkNEW_ARGS(SkPicture, (&stream, &success, &SkImageDecoder::DecodeMemory)); - if (!success) { + SkPicture* pic = SkPicture::CreateFromStream(&stream, &SkImageDecoder::DecodeMemory); + if (!pic) { SkDebugf("unable to decode %s\n", filename.c_str()); return; } @@ -68,7 +67,7 @@ static void testOne(const SkString& filename) { int height = pic->height(); SkBitmap bitmap; bitmap.setConfig(SkBitmap::kARGB_8888_Config, width, height); - success = bitmap.allocPixels(); + bool success = bitmap.allocPixels(); if (!success) { SkDebugf("unable to allocate bitmap for %s\n", filename.c_str()); return; |