turn off debugging printfs
fix pathops issues 1417, 1418
be more rigorous about pulling intersections of lines to end points
rewrite cubic/line and quad/line intersections to share style
BUG=
Review URL: https://codereview.chromium.org/19543005
git-svn-id: http://skia.googlecode.com/svn/trunk@10270 2bbb7eff-a529-9590-31e7-b0007b416f81
diff --git a/src/pathops/SkDCubicIntersection.cpp b/src/pathops/SkDCubicIntersection.cpp
index 6e04970..19e7340 100644
--- a/src/pathops/SkDCubicIntersection.cpp
+++ b/src/pathops/SkDCubicIntersection.cpp
@@ -114,26 +114,16 @@
#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 @@
// for that.
}
}
- SkASSERT(coStart[0] == -1);
t2Start = t2;
}
t1Start = t1;
@@ -263,11 +252,34 @@
// 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 @@
}
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 @@
}
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 @@
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 @@
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 @@
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 dc80479..a891abe 100644
--- a/src/pathops/SkDCubicLineIntersection.cpp
+++ b/src/pathops/SkDCubicLineIntersection.cpp
@@ -76,250 +76,252 @@
class LineCubicIntersections {
public:
+ enum PinTPoint {
+ kPointUninitialized,
+ kPointInitialized
+ };
-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;
+ LineCubicIntersections(const SkDCubic& c, const SkDLine& l, SkIntersections* i)
+ : fCubic(c)
+ , fLine(l)
+ , fIntersections(i)
+ , fAllowNear(true) {
}
- 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);
+ void allowNear(bool allow) {
+ fAllowNear = allow;
+ }
+
+ // 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);
+ }
+
+ 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();
+ }
+
+ 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 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();
+ }
+
+ 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);
+ }
+
+ 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();
+ }
+
+ protected:
+
+ 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]);
}
}
- 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);
+ 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]);
}
}
- 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 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);
+ 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]);
}
}
- if (fAllowNear) {
- addNearVerticalEndPoints(top, bottom, axisIntercept);
- }
- if (flipped) {
- intersections.flip();
- }
- return intersections.used();
-}
-protected:
+ 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]);
+ }
+ // FIXME: see if line end is nearly on cubic
+ }
-void addExactEndPoints() {
- for (int cIndex = 0; cIndex < 4; cIndex += 3) {
- double lineT = line.exactPoint(cubic[cIndex]);
- 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 addNearEndPoints() {
- 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 = line.nearPoint(cubic[cIndex]);
- if (lineT < 0) {
- continue;
- }
- intersections.insert(cubicT, lineT, cubic[cIndex]);
+ // FIXME: see if line end is nearly on cubic
}
-}
-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;
+ 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;
}
- double cubicT = (double) (cIndex >> 1);
- intersections.insert(cubicT, lineT, cubic[cIndex]);
+ return (xy.fY - fLine[0].fY) / dy;
}
-}
-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;
+ bool pinTs(double* cubicT, double* lineT, SkDPoint* pt, PinTPoint ptSet) {
+ if (!approximately_one_or_less(*lineT)) {
+ return false;
}
- double lineT = SkDLine::NearPointH(cubic[cIndex], left, right, y);
- if (lineT < 0) {
- continue;
+ if (!approximately_zero_or_more(*lineT)) {
+ return false;
}
- intersections.insert(cubicT, lineT, cubic[cIndex]);
- }
- // 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;
+ 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);
}
- double cubicT = (double) (cIndex >> 1);
- intersections.insert(cubicT, lineT, cubic[cIndex]);
+ return true;
}
-}
-
-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;
- }
- 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
-}
-
-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;
- }
- 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;
- }
- 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 faa7c1d..46118429 100644
--- a/src/pathops/SkDLineIntersection.cpp
+++ b/src/pathops/SkDLineIntersection.cpp
@@ -27,9 +27,9 @@
}
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 @@
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 124c7da..e10fb3f 100644
--- a/src/pathops/SkDQuadIntersection.cpp
+++ b/src/pathops/SkDQuadIntersection.cpp
@@ -87,8 +87,8 @@
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 @@
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 @@
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 @@
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 @@
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 @@
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 @@
#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 @@
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 @@
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 @@
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
+ 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;
+ }
+ 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);
+ }
+ }
+ bool expectCoincident = copyI.fUsed >= 2 && innerEqual == 2;
+ if (expectCoincident) {
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]);
- }
- if ((t = SkIntersections::Axial(q2, q1[2], useVertical)) >= 0) {
- insertCoincident(1, t, q1[2]);
- }
- SkASSERT(coincidentUsed() <= 2);
+ 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 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 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 9df2dc2..58b3060 100644
--- a/src/pathops/SkDQuadLineIntersection.cpp
+++ b/src/pathops/SkDQuadLineIntersection.cpp
@@ -89,10 +89,15 @@
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 @@
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 @@
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 @@
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 @@
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 @@
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 @@
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 @@
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 @@
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 @@
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 fe23316..242c67b 100644
--- a/src/pathops/SkIntersections.cpp
+++ b/src/pathops/SkIntersections.cpp
@@ -54,108 +54,6 @@
}
}
-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 de3d44c..26a1d1a 100644
--- a/src/pathops/SkIntersections.h
+++ b/src/pathops/SkIntersections.h
@@ -208,8 +208,6 @@
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 5b20749..7e69bb8 100644
--- a/src/pathops/SkOpSegment.cpp
+++ b/src/pathops/SkOpSegment.cpp
@@ -1082,9 +1082,7 @@
// 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 @@
;
}
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 @@
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 @@
#if DEBUG_ACTIVE_SPANS || DEBUG_ACTIVE_SPANS_FIRST_ONLY
void SkOpSegment::debugShowActiveSpans() const {
+ debugValidate();
if (done()) {
return;
}
@@ -2763,8 +2771,6 @@
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 @@
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 7e5e644..bfaf4ed 100644
--- a/src/pathops/SkOpSegment.h
+++ b/src/pathops/SkOpSegment.h
@@ -130,6 +130,11 @@
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 @@
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 @@
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 9a92b00..28cf59c 100644
--- a/src/pathops/SkPathOpsCommon.cpp
+++ b/src/pathops/SkPathOpsCommon.cpp
@@ -17,7 +17,7 @@
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 60dca44..5fbfeba 100644
--- a/src/pathops/SkPathOpsCubic.cpp
+++ b/src/pathops/SkPathOpsCubic.cpp
@@ -304,7 +304,7 @@
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 @@
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 f07af80..1ba35be 100644
--- a/src/pathops/SkPathOpsCubic.h
+++ b/src/pathops/SkPathOpsCubic.h
@@ -53,6 +53,7 @@
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 @@
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 ca68a66..5d12cb8 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 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 05fe241..e4ef072 100644
--- a/src/pathops/SkPathOpsDebug.h
+++ b/src/pathops/SkPathOpsDebug.h
@@ -64,6 +64,7 @@
#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 @@
#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 47c0565..48c042a 100644
--- a/src/pathops/SkPathOpsLine.cpp
+++ b/src/pathops/SkPathOpsLine.cpp
@@ -41,8 +41,13 @@
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 @@
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 c5ac7fd..75f3bd1 100644
--- a/src/pathops/SkPathOpsLine.h
+++ b/src/pathops/SkPathOpsLine.h
@@ -33,8 +33,8 @@
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 636e385..7d9ff52 100644
--- a/src/pathops/SkPathOpsQuad.cpp
+++ b/src/pathops/SkPathOpsQuad.cpp
@@ -30,7 +30,7 @@
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 @@
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 @@
}
// 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 d06f344..c865051 100644
--- a/src/pathops/SkPathOpsQuad.h
+++ b/src/pathops/SkPathOpsQuad.h
@@ -42,6 +42,7 @@
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 @@
}
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 9d7f876..2ceed32 100644
--- a/src/pathops/SkPathOpsRect.cpp
+++ b/src/pathops/SkPathOpsRect.cpp
@@ -26,7 +26,7 @@
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 @@
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 a076d15..8135c57 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 @@
: 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 c988691..6158f13 100644
--- a/src/pathops/SkPathOpsTypes.h
+++ b/src/pathops/SkPathOpsTypes.h
@@ -23,19 +23,24 @@
};
// 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 4c362b6..f7507a0 100644
--- a/tests/PathOpsAngleTest.cpp
+++ b/tests/PathOpsAngleTest.cpp
@@ -257,8 +257,8 @@
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 @@
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 @@
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 c4915e9..a0f2846 100644
--- a/tests/PathOpsCubicIntersectionTest.cpp
+++ b/tests/PathOpsCubicIntersectionTest.cpp
@@ -52,9 +52,9 @@
}
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 @@
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 @@
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 @@
}
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 @@
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 @@
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 @@
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 @@
DEFINE_TESTCLASS_SHORT(PathOpsCubicIntersectionTest)
DEFINE_TESTCLASS_SHORT(PathOpsCubicIntersectionOneOffTest)
+
+DEFINE_TESTCLASS_SHORT(PathOpsCubicSelfOneOffTest)
diff --git a/tests/PathOpsCubicLineIntersectionTest.cpp b/tests/PathOpsCubicLineIntersectionTest.cpp
index 2f52b3b..866acb3 100644
--- a/tests/PathOpsCubicLineIntersectionTest.cpp
+++ b/tests/PathOpsCubicLineIntersectionTest.cpp
@@ -54,9 +54,9 @@
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 @@
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 42a5d33..76ecd01 100644
--- a/tests/PathOpsCubicQuadIntersectionTest.cpp
+++ b/tests/PathOpsCubicQuadIntersectionTest.cpp
@@ -52,9 +52,9 @@
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 feab21d..ea816c5 100644
--- a/tests/PathOpsDLineTest.cpp
+++ b/tests/PathOpsDLineTest.cpp
@@ -47,7 +47,7 @@
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 f2bef91..57b42ec 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 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 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 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 @@
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 @@
#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 c81f1dc..a85c435 100644
--- a/tests/PathOpsOpTest.cpp
+++ b/tests/PathOpsOpTest.cpp
@@ -1803,7 +1803,6 @@
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 @@
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 ee2e8de..2d72b41 100644
--- a/tests/PathOpsQuadIntersectionTest.cpp
+++ b/tests/PathOpsQuadIntersectionTest.cpp
@@ -37,9 +37,9 @@
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 @@
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 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 @@
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 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 @@
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 @@
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 @@
DEFINE_TESTCLASS_SHORT(PathOpsQuadIntersectionTest)
DEFINE_TESTCLASS_SHORT(PathOpsQuadIntersectionOneOffTest)
+
+DEFINE_TESTCLASS_SHORT(PathOpsQuadIntersectionCoincidenceOneOffTest)
diff --git a/tests/PathOpsQuadLineIntersectionTest.cpp b/tests/PathOpsQuadLineIntersectionTest.cpp
index 02c925c..555a90c 100644
--- a/tests/PathOpsQuadLineIntersectionTest.cpp
+++ b/tests/PathOpsQuadLineIntersectionTest.cpp
@@ -80,9 +80,9 @@
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 @@
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 7d1b133..63f9447 100644
--- a/tests/PathOpsQuadLineIntersectionThreadedTest.cpp
+++ b/tests/PathOpsQuadLineIntersectionThreadedTest.cpp
@@ -55,9 +55,9 @@
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 @@
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 5f61812..954435f 100644
--- a/tests/PathOpsSimplifyTest.cpp
+++ b/tests/PathOpsSimplifyTest.cpp
@@ -3828,7 +3828,7 @@
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 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 f9d33e1..146c42a 100644
--- a/tests/PathOpsSkpClipTest.cpp
+++ b/tests/PathOpsSkpClipTest.cpp
@@ -58,9 +58,8 @@
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 @@
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;