aboutsummaryrefslogtreecommitdiffhomepage
path: root/src/pathops
diff options
context:
space:
mode:
Diffstat (limited to 'src/pathops')
-rw-r--r--src/pathops/SkDCubicIntersection.cpp218
-rw-r--r--src/pathops/SkDCubicLineIntersection.cpp372
-rw-r--r--src/pathops/SkDLineIntersection.cpp17
-rw-r--r--src/pathops/SkDQuadIntersection.cpp113
-rw-r--r--src/pathops/SkDQuadLineIntersection.cpp126
-rw-r--r--src/pathops/SkIntersections.cpp102
-rw-r--r--src/pathops/SkIntersections.h2
-rw-r--r--src/pathops/SkOpSegment.cpp46
-rw-r--r--src/pathops/SkOpSegment.h11
-rw-r--r--src/pathops/SkPathOpsCommon.cpp2
-rw-r--r--src/pathops/SkPathOpsCubic.cpp10
-rw-r--r--src/pathops/SkPathOpsCubic.h2
-rw-r--r--src/pathops/SkPathOpsCurve.h8
-rw-r--r--src/pathops/SkPathOpsDebug.h2
-rw-r--r--src/pathops/SkPathOpsLine.cpp11
-rw-r--r--src/pathops/SkPathOpsLine.h2
-rw-r--r--src/pathops/SkPathOpsQuad.cpp12
-rw-r--r--src/pathops/SkPathOpsQuad.h2
-rw-r--r--src/pathops/SkPathOpsRect.cpp4
-rw-r--r--src/pathops/SkPathOpsTypes.cpp37
-rw-r--r--src/pathops/SkPathOpsTypes.h21
21 files changed, 598 insertions, 522 deletions
diff --git a/src/pathops/SkDCubicIntersection.cpp b/src/pathops/SkDCubicIntersection.cpp
index 6e049708ac..19e7340cdc 100644
--- a/src/pathops/SkDCubicIntersection.cpp
+++ b/src/pathops/SkDCubicIntersection.cpp
@@ -114,26 +114,16 @@ static void intersect(const SkDCubic& cubic1, double t1s, double t1e, const SkDC
#endif
SkIntersections locals;
intersectWithOrder(s1.fQuad, o1, s2.fQuad, o2, locals);
- double coStart[2] = { -1 };
- SkDPoint coPoint;
int tCount = locals.used();
for (int tIdx = 0; tIdx < tCount; ++tIdx) {
double to1 = t1Start + (t1 - t1Start) * locals[0][tIdx];
double to2 = t2Start + (t2 - t2Start) * locals[1][tIdx];
// if the computed t is not sufficiently precise, iterate
- SkDPoint p1 = cubic1.xyAtT(to1);
- SkDPoint p2 = cubic2.xyAtT(to2);
+ SkDPoint p1 = cubic1.ptAtT(to1);
+ SkDPoint p2 = cubic2.ptAtT(to2);
if (p1.approximatelyEqual(p2)) {
- if (locals.isCoincident(tIdx)) {
- if (coStart[0] < 0) {
- coStart[0] = to1;
- coStart[1] = to2;
- coPoint = p1;
- } else {
- i.insertCoincidentPair(coStart[0], to1, coStart[1], to2, coPoint, p1);
- coStart[0] = -1;
- }
- } else if (&cubic1 != &cubic2 || !approximately_equal(to1, to2)) {
+ SkASSERT(!locals.isCoincident(tIdx));
+ if (&cubic1 != &cubic2 || !approximately_equal(to1, to2)) {
if (i.swapped()) { // FIXME: insert should respect swap
i.insert(to2, to1, p1);
} else {
@@ -250,7 +240,6 @@ static void intersect(const SkDCubic& cubic1, double t1s, double t1e, const SkDC
// for that.
}
}
- SkASSERT(coStart[0] == -1);
t2Start = t2;
}
t1Start = t1;
@@ -263,11 +252,34 @@ static void intersect(const SkDCubic& cubic1, double t1s, double t1e, const SkDC
// intersect the end of the cubic with the other. Try lines from the end to control and opposite
// end to determine range of t on opposite cubic.
static void intersectEnd(const SkDCubic& cubic1, bool start, const SkDCubic& cubic2,
- const SkDRect& bounds2, SkIntersections& i) {
+ const SkDRect& bounds2, bool selfIntersect, SkIntersections& i) {
SkDLine line;
int t1Index = start ? 0 : 3;
+ bool swap = i.swapped();
+ double testT = (double) !start;
+ // quad/quad at this point checks to see if exact matches have already been found
+ // cubic/cubic can't reject so easily since cubics can intersect same point more than once
+ if (!selfIntersect) {
+ SkDLine tmpLine;
+ tmpLine[0] = tmpLine[1] = cubic2[t1Index];
+ tmpLine[1].fX += cubic2[2 - start].fY - cubic2[t1Index].fY;
+ tmpLine[1].fY -= cubic2[2 - start].fX - cubic2[t1Index].fX;
+ SkIntersections impTs;
+ impTs.intersectRay(cubic1, tmpLine);
+ for (int index = 0; index < impTs.used(); ++index) {
+ SkDPoint realPt = impTs.pt(index);
+ if (!tmpLine[0].approximatelyEqualHalf(realPt)) {
+ continue;
+ }
+ if (swap) {
+ i.insert(testT, impTs[0][index], tmpLine[0]);
+ } else {
+ i.insert(impTs[0][index], testT, tmpLine[0]);
+ }
+ return;
+ }
+ }
// don't bother if the two cubics are connnected
-#if 1
static const int kPointsInCubic = 4; // FIXME: move to DCubic, replace '4' with this
static const int kMaxLineCubicIntersections = 3;
SkSTArray<(kMaxLineCubicIntersections - 1) * kMaxLineCubicIntersections, double, true> tVals;
@@ -297,9 +309,9 @@ static void intersectEnd(const SkDCubic& cubic1, bool start, const SkDCubic& cub
}
if (local.pt(idx2).approximatelyEqual(line[0])) {
if (i.swapped()) { // FIXME: insert should respect swap
- i.insert(foundT, start ? 0 : 1, line[0]);
+ i.insert(foundT, testT, line[0]);
} else {
- i.insert(start ? 0 : 1, foundT, line[0]);
+ i.insert(testT, foundT, line[0]);
}
} else {
tVals.push_back(foundT);
@@ -329,57 +341,6 @@ static void intersectEnd(const SkDCubic& cubic1, bool start, const SkDCubic& cub
}
tIdx = tLast + 1;
} while (tIdx < tVals.count());
-#else
- const SkDPoint& endPt = cubic1[t1Index];
- if (!bounds2.contains(endPt)) {
- return;
- }
- // this variant looks for intersections within an 'x' of the endpoint
- double delta = SkTMax(bounds2.width(), bounds2.height());
- for (int index = 0; index < 2; ++index) {
- if (index == 0) {
- line[0].fY = line[1].fY = endPt.fY;
- line[0].fX = endPt.fX - delta;
- line[1].fX = endPt.fX + delta;
- } else {
- line[0].fX = line[1].fX = cubic1[t1Index].fX;
- line[0].fY = endPt.fY - delta;
- line[1].fY = endPt.fY + delta;
- }
- SkIntersections local;
- local.intersectRay(cubic2, line); // OPTIMIZE: special for horizontal/vertical lines
- int used = local.used();
- for (int index = 0; index < used; ++index) {
- double foundT = local[0][index];
- if (approximately_less_than_zero(foundT) || approximately_greater_than_one(foundT)) {
- continue;
- }
- if (!local.pt(index).approximatelyEqual(endPt)) {
- continue;
- }
- if (i.swapped()) { // FIXME: insert should respect swap
- i.insert(foundT, start ? 0 : 1, endPt);
- } else {
- i.insert(start ? 0 : 1, foundT, endPt);
- }
- return;
- }
- }
-// the above doesn't catch when the end of the cubic missed the other cubic because the quad
-// approximation moved too far away, so something like the below is still needed. The enabled
-// code above tries to avoid this heavy lifting unless the convex hull intersected the cubic.
- double tMin1 = start ? 0 : 1 - LINE_FRACTION;
- double tMax1 = start ? LINE_FRACTION : 1;
- double tMin2 = SkTMax(foundT - LINE_FRACTION, 0.0);
- double tMax2 = SkTMin(foundT + LINE_FRACTION, 1.0);
- int lastUsed = i.used();
- intersect(cubic1, tMin1, tMax1, cubic2, tMin2, tMax2, 1, i);
- if (lastUsed == i.used()) {
- tMin2 = SkTMax(foundT - (1.0 / SkDCubic::gPrecisionUnit), 0.0);
- tMax2 = SkTMin(foundT + (1.0 / SkDCubic::gPrecisionUnit), 1.0);
- intersect(cubic1, tMin1, tMax1, cubic2, tMin2, tMax2, 1, i);
- }
-#endif
return;
}
@@ -389,7 +350,7 @@ static bool closeStart(const SkDCubic& cubic, int cubicIndex, SkIntersections& i
if (i[cubicIndex][0] != 0 || i[cubicIndex][1] > CLOSE_ENOUGH) {
return false;
}
- pt = cubic.xyAtT((i[cubicIndex][0] + i[cubicIndex][1]) / 2);
+ pt = cubic.ptAtT((i[cubicIndex][0] + i[cubicIndex][1]) / 2);
return true;
}
@@ -398,29 +359,120 @@ static bool closeEnd(const SkDCubic& cubic, int cubicIndex, SkIntersections& i,
if (i[cubicIndex][last] != 1 || i[cubicIndex][last - 1] < 1 - CLOSE_ENOUGH) {
return false;
}
- pt = cubic.xyAtT((i[cubicIndex][last] + i[cubicIndex][last - 1]) / 2);
+ pt = cubic.ptAtT((i[cubicIndex][last] + i[cubicIndex][last - 1]) / 2);
return true;
}
+static bool only_end_pts_in_common(const SkDCubic& c1, const SkDCubic& c2) {
+// the idea here is to see at minimum do a quick reject by rotating all points
+// to either side of the line formed by connecting the endpoints
+// if the opposite curves points are on the line or on the other side, the
+// curves at most intersect at the endpoints
+ for (int oddMan = 0; oddMan < 4; ++oddMan) {
+ const SkDPoint* endPt[3];
+ for (int opp = 1; opp < 4; ++opp) {
+ int end = oddMan ^ opp; // choose a value not equal to oddMan
+ endPt[opp - 1] = &c1[end];
+ }
+ for (int triTest = 0; triTest < 3; ++triTest) {
+ double origX = endPt[triTest]->fX;
+ double origY = endPt[triTest]->fY;
+ int oppTest = triTest + 1;
+ if (3 == oppTest) {
+ oppTest = 0;
+ }
+ double adj = endPt[oppTest]->fX - origX;
+ double opp = endPt[oppTest]->fY - origY;
+ double sign = (c1[oddMan].fY - origY) * adj - (c1[oddMan].fX - origX) * opp;
+ if (approximately_zero(sign)) {
+ goto tryNextHalfPlane;
+ }
+ for (int n = 0; n < 4; ++n) {
+ double test = (c2[n].fY - origY) * adj - (c2[n].fX - origX) * opp;
+ if (test * sign > 0 && !precisely_zero(test)) {
+ goto tryNextHalfPlane;
+ }
+ }
+ }
+ return true;
+tryNextHalfPlane:
+ ;
+ }
+ return false;
+}
+
int SkIntersections::intersect(const SkDCubic& c1, const SkDCubic& c2) {
- ::intersect(c1, 0, 1, c2, 0, 1, 1, *this);
- // FIXME: pass in cached bounds from caller
+ bool selfIntersect = &c1 == &c2;
+ if (selfIntersect) {
+ if (c1[0].approximatelyEqualHalf(c1[3])) {
+ insert(0, 1, c1[0]);
+ }
+ } else {
+ for (int i1 = 0; i1 < 4; i1 += 3) {
+ for (int i2 = 0; i2 < 4; i2 += 3) {
+ if (c1[i1].approximatelyEqualHalf(c2[i2])) {
+ insert(i1 >> 1, i2 >> 1, c1[i1]);
+ }
+ }
+ }
+ }
+ SkASSERT(fUsed < 4);
+ if (!selfIntersect) {
+ if (only_end_pts_in_common(c1, c2)) {
+ return fUsed;
+ }
+ if (only_end_pts_in_common(c2, c1)) {
+ return fUsed;
+ }
+ }
+ // quad/quad does linear test here -- cubic does not
+ // cubics which are really lines should have been detected in reduce step earlier
SkDRect c1Bounds, c2Bounds;
+ // FIXME: pass in cached bounds from caller
c1Bounds.setBounds(c1); // OPTIMIZE use setRawBounds ?
c2Bounds.setBounds(c2);
- intersectEnd(c1, false, c2, c2Bounds, *this);
- intersectEnd(c1, true, c2, c2Bounds, *this);
- bool selfIntersect = &c1 == &c2;
- if (!selfIntersect) {
+ intersectEnd(c1, false, c2, c2Bounds, selfIntersect, *this);
+ intersectEnd(c1, true, c2, c2Bounds, selfIntersect, *this);
+ if (selfIntersect) {
+ if (fUsed) {
+ return fUsed;
+ }
+ } else {
swap();
- intersectEnd(c2, false, c1, c1Bounds, *this);
- intersectEnd(c2, true, c1, c1Bounds, *this);
+ intersectEnd(c2, false, c1, c1Bounds, false, *this);
+ intersectEnd(c2, true, c1, c1Bounds, false, *this);
swap();
}
+ // if two ends intersect, check middle for coincidence
+ if (fUsed >= 2) {
+ SkASSERT(!selfIntersect);
+ int last = fUsed - 1;
+ double tRange1 = fT[0][last] - fT[0][0];
+ double tRange2 = fT[1][last] - fT[1][0];
+ for (int index = 1; index < 5; ++index) {
+ double testT1 = fT[0][0] + tRange1 * index / 5;
+ double testT2 = fT[1][0] + tRange2 * index / 5;
+ SkDPoint testPt1 = c1.ptAtT(testT1);
+ SkDPoint testPt2 = c2.ptAtT(testT2);
+ if (!testPt1.approximatelyEqual(testPt2)) {
+ goto skipCoincidence;
+ }
+ }
+ if (fUsed > 2) {
+ fPt[1] = fPt[last];
+ fT[0][1] = fT[0][last];
+ fT[1][1] = fT[1][last];
+ fUsed = 2;
+ }
+ fIsCoincident[0] = fIsCoincident[1] = 0x03;
+ return fUsed;
+ }
+skipCoincidence:
+ ::intersect(c1, 0, 1, c2, 0, 1, 1, *this);
// If an end point and a second point very close to the end is returned, the second
// point may have been detected because the approximate quads
// intersected at the end and close to it. Verify that the second point is valid.
- if (fUsed <= 1 || coincidentUsed()) {
+ if (fUsed <= 1) {
return fUsed;
}
SkDPoint pt[2];
@@ -440,8 +492,8 @@ int SkIntersections::intersect(const SkDCubic& c1, const SkDCubic& c2) {
for (int index = 0; index < last; ++index) {
double mid1 = (fT[0][index] + fT[0][index + 1]) / 2;
double mid2 = (fT[1][index] + fT[1][index + 1]) / 2;
- pt[0] = c1.xyAtT(mid1);
- pt[1] = c2.xyAtT(mid2);
+ pt[0] = c1.ptAtT(mid1);
+ pt[1] = c2.ptAtT(mid2);
if (pt[0].approximatelyEqual(pt[1])) {
match |= 1 << index;
}
diff --git a/src/pathops/SkDCubicLineIntersection.cpp b/src/pathops/SkDCubicLineIntersection.cpp
index dc80479f60..a891abec66 100644
--- a/src/pathops/SkDCubicLineIntersection.cpp
+++ b/src/pathops/SkDCubicLineIntersection.cpp
@@ -76,250 +76,252 @@ For horizontal lines:
class LineCubicIntersections {
public:
+ enum PinTPoint {
+ kPointUninitialized,
+ kPointInitialized
+ };
+
+ LineCubicIntersections(const SkDCubic& c, const SkDLine& l, SkIntersections* i)
+ : fCubic(c)
+ , fLine(l)
+ , fIntersections(i)
+ , fAllowNear(true) {
+ }
-LineCubicIntersections(const SkDCubic& c, const SkDLine& l, SkIntersections& i)
- : cubic(c)
- , line(l)
- , intersections(i)
- , fAllowNear(true) {
-}
-
-void allowNear(bool allow) {
- fAllowNear = allow;
-}
-
-// see parallel routine in line quadratic intersections
-int intersectRay(double roots[3]) {
- double adj = line[1].fX - line[0].fX;
- double opp = line[1].fY - line[0].fY;
- SkDCubic r;
- for (int n = 0; n < 4; ++n) {
- r[n].fX = (cubic[n].fY - line[0].fY) * adj - (cubic[n].fX - line[0].fX) * opp;
+ void allowNear(bool allow) {
+ fAllowNear = allow;
}
- double A, B, C, D;
- SkDCubic::Coefficients(&r[0].fX, &A, &B, &C, &D);
- return SkDCubic::RootsValidT(A, B, C, D, roots);
-}
-int intersect() {
- addExactEndPoints();
- double rootVals[3];
- int roots = intersectRay(rootVals);
- for (int index = 0; index < roots; ++index) {
- double cubicT = rootVals[index];
- double lineT = findLineT(cubicT);
- if (pinTs(&cubicT, &lineT)) {
- SkDPoint pt = line.xyAtT(lineT);
-#if ONE_OFF_DEBUG
- SkDPoint cPt = cubic.xyAtT(cubicT);
- SkDebugf("%s pt=(%1.9g,%1.9g) cPt=(%1.9g,%1.9g)\n", __FUNCTION__, pt.fX, pt.fY,
- cPt.fX, cPt.fY);
-#endif
- intersections.insert(cubicT, lineT, pt);
+ // see parallel routine in line quadratic intersections
+ int intersectRay(double roots[3]) {
+ double adj = fLine[1].fX - fLine[0].fX;
+ double opp = fLine[1].fY - fLine[0].fY;
+ SkDCubic r;
+ for (int n = 0; n < 4; ++n) {
+ r[n].fX = (fCubic[n].fY - fLine[0].fY) * adj - (fCubic[n].fX - fLine[0].fX) * opp;
}
+ double A, B, C, D;
+ SkDCubic::Coefficients(&r[0].fX, &A, &B, &C, &D);
+ return SkDCubic::RootsValidT(A, B, C, D, roots);
}
- if (fAllowNear) {
- addNearEndPoints();
- }
- return intersections.used();
-}
-int horizontalIntersect(double axisIntercept, double roots[3]) {
- double A, B, C, D;
- SkDCubic::Coefficients(&cubic[0].fY, &A, &B, &C, &D);
- D -= axisIntercept;
- return SkDCubic::RootsValidT(A, B, C, D, roots);
-}
-
-int horizontalIntersect(double axisIntercept, double left, double right, bool flipped) {
- addExactHorizontalEndPoints(left, right, axisIntercept);
- double rootVals[3];
- int roots = horizontalIntersect(axisIntercept, rootVals);
- for (int index = 0; index < roots; ++index) {
- double cubicT = rootVals[index];
- SkDPoint pt = cubic.xyAtT(cubicT);
- double lineT = (pt.fX - left) / (right - left);
- if (pinTs(&cubicT, &lineT)) {
- intersections.insert(cubicT, lineT, pt);
+ int intersect() {
+ addExactEndPoints();
+ double rootVals[3];
+ int roots = intersectRay(rootVals);
+ for (int index = 0; index < roots; ++index) {
+ double cubicT = rootVals[index];
+ double lineT = findLineT(cubicT);
+ SkDPoint pt;
+ if (pinTs(&cubicT, &lineT, &pt, kPointUninitialized)) {
+ #if ONE_OFF_DEBUG
+ SkDPoint cPt = fCubic.ptAtT(cubicT);
+ SkDebugf("%s pt=(%1.9g,%1.9g) cPt=(%1.9g,%1.9g)\n", __FUNCTION__, pt.fX, pt.fY,
+ cPt.fX, cPt.fY);
+ #endif
+ fIntersections->insert(cubicT, lineT, pt);
+ }
}
+ if (fAllowNear) {
+ addNearEndPoints();
+ }
+ return fIntersections->used();
}
- if (fAllowNear) {
- addNearHorizontalEndPoints(left, right, axisIntercept);
- }
- if (flipped) {
- intersections.flip();
- }
- return intersections.used();
-}
-int verticalIntersect(double axisIntercept, double roots[3]) {
- double A, B, C, D;
- SkDCubic::Coefficients(&cubic[0].fX, &A, &B, &C, &D);
- D -= axisIntercept;
- return SkDCubic::RootsValidT(A, B, C, D, roots);
-}
+ int horizontalIntersect(double axisIntercept, double roots[3]) {
+ double A, B, C, D;
+ SkDCubic::Coefficients(&fCubic[0].fY, &A, &B, &C, &D);
+ D -= axisIntercept;
+ return SkDCubic::RootsValidT(A, B, C, D, roots);
+ }
-int verticalIntersect(double axisIntercept, double top, double bottom, bool flipped) {
- addExactVerticalEndPoints(top, bottom, axisIntercept);
- double rootVals[3];
- int roots = verticalIntersect(axisIntercept, rootVals);
- for (int index = 0; index < roots; ++index) {
- double cubicT = rootVals[index];
- SkDPoint pt = cubic.xyAtT(cubicT);
- double lineT = (pt.fY - top) / (bottom - top);
- if (pinTs(&cubicT, &lineT)) {
- intersections.insert(cubicT, lineT, pt);
+ int horizontalIntersect(double axisIntercept, double left, double right, bool flipped) {
+ addExactHorizontalEndPoints(left, right, axisIntercept);
+ double rootVals[3];
+ int roots = horizontalIntersect(axisIntercept, rootVals);
+ for (int index = 0; index < roots; ++index) {
+ double cubicT = rootVals[index];
+ SkDPoint pt = fCubic.ptAtT(cubicT);
+ double lineT = (pt.fX - left) / (right - left);
+ if (pinTs(&cubicT, &lineT, &pt, kPointInitialized)) {
+ fIntersections->insert(cubicT, lineT, pt);
+ }
+ }
+ if (fAllowNear) {
+ addNearHorizontalEndPoints(left, right, axisIntercept);
}
+ if (flipped) {
+ fIntersections->flip();
+ }
+ return fIntersections->used();
}
- if (fAllowNear) {
- addNearVerticalEndPoints(top, bottom, axisIntercept);
+
+ int verticalIntersect(double axisIntercept, double roots[3]) {
+ double A, B, C, D;
+ SkDCubic::Coefficients(&fCubic[0].fX, &A, &B, &C, &D);
+ D -= axisIntercept;
+ return SkDCubic::RootsValidT(A, B, C, D, roots);
}
- if (flipped) {
- intersections.flip();
+
+ int verticalIntersect(double axisIntercept, double top, double bottom, bool flipped) {
+ addExactVerticalEndPoints(top, bottom, axisIntercept);
+ double rootVals[3];
+ int roots = verticalIntersect(axisIntercept, rootVals);
+ for (int index = 0; index < roots; ++index) {
+ double cubicT = rootVals[index];
+ SkDPoint pt = fCubic.ptAtT(cubicT);
+ double lineT = (pt.fY - top) / (bottom - top);
+ if (pinTs(&cubicT, &lineT, &pt, kPointInitialized)) {
+ fIntersections->insert(cubicT, lineT, pt);
+ }
+ }
+ if (fAllowNear) {
+ addNearVerticalEndPoints(top, bottom, axisIntercept);
+ }
+ if (flipped) {
+ fIntersections->flip();
+ }
+ return fIntersections->used();
}
- return intersections.used();
-}
-protected:
+ protected:
-void addExactEndPoints() {
- for (int cIndex = 0; cIndex < 4; cIndex += 3) {
- double lineT = line.exactPoint(cubic[cIndex]);
- if (lineT < 0) {
- continue;
+ void addExactEndPoints() {
+ for (int cIndex = 0; cIndex < 4; cIndex += 3) {
+ double lineT = fLine.exactPoint(fCubic[cIndex]);
+ if (lineT < 0) {
+ continue;
+ }
+ double cubicT = (double) (cIndex >> 1);
+ fIntersections->insert(cubicT, lineT, fCubic[cIndex]);
}
- double cubicT = (double) (cIndex >> 1);
- intersections.insert(cubicT, lineT, cubic[cIndex]);
}
-}
-void addNearEndPoints() {
- for (int cIndex = 0; cIndex < 4; cIndex += 3) {
- double cubicT = (double) (cIndex >> 1);
- if (intersections.hasT(cubicT)) {
- continue;
+ void addNearEndPoints() {
+ for (int cIndex = 0; cIndex < 4; cIndex += 3) {
+ double cubicT = (double) (cIndex >> 1);
+ if (fIntersections->hasT(cubicT)) {
+ continue;
+ }
+ double lineT = fLine.nearPoint(fCubic[cIndex]);
+ if (lineT < 0) {
+ continue;
+ }
+ fIntersections->insert(cubicT, lineT, fCubic[cIndex]);
}
- double lineT = line.nearPoint(cubic[cIndex]);
- if (lineT < 0) {
- continue;
- }
- intersections.insert(cubicT, lineT, cubic[cIndex]);
}
-}
-void addExactHorizontalEndPoints(double left, double right, double y) {
- for (int cIndex = 0; cIndex < 4; cIndex += 3) {
- double lineT = SkDLine::ExactPointH(cubic[cIndex], left, right, y);
- if (lineT < 0) {
- continue;
+ void addExactHorizontalEndPoints(double left, double right, double y) {
+ for (int cIndex = 0; cIndex < 4; cIndex += 3) {
+ double lineT = SkDLine::ExactPointH(fCubic[cIndex], left, right, y);
+ if (lineT < 0) {
+ continue;
+ }
+ double cubicT = (double) (cIndex >> 1);
+ fIntersections->insert(cubicT, lineT, fCubic[cIndex]);
}
- double cubicT = (double) (cIndex >> 1);
- intersections.insert(cubicT, lineT, cubic[cIndex]);
}
-}
-void addNearHorizontalEndPoints(double left, double right, double y) {
- for (int cIndex = 0; cIndex < 4; cIndex += 3) {
- double cubicT = (double) (cIndex >> 1);
- if (intersections.hasT(cubicT)) {
- continue;
+ void addNearHorizontalEndPoints(double left, double right, double y) {
+ for (int cIndex = 0; cIndex < 4; cIndex += 3) {
+ double cubicT = (double) (cIndex >> 1);
+ if (fIntersections->hasT(cubicT)) {
+ continue;
+ }
+ double lineT = SkDLine::NearPointH(fCubic[cIndex], left, right, y);
+ if (lineT < 0) {
+ continue;
+ }
+ fIntersections->insert(cubicT, lineT, fCubic[cIndex]);
}
- double lineT = SkDLine::NearPointH(cubic[cIndex], left, right, y);
- if (lineT < 0) {
- continue;
- }
- intersections.insert(cubicT, lineT, cubic[cIndex]);
+ // FIXME: see if line end is nearly on cubic
}
- // FIXME: see if line end is nearly on cubic
-}
-void addExactVerticalEndPoints(double top, double bottom, double x) {
- for (int cIndex = 0; cIndex < 4; cIndex += 3) {
- double lineT = SkDLine::ExactPointV(cubic[cIndex], top, bottom, x);
- if (lineT < 0) {
- continue;
+ void addExactVerticalEndPoints(double top, double bottom, double x) {
+ for (int cIndex = 0; cIndex < 4; cIndex += 3) {
+ double lineT = SkDLine::ExactPointV(fCubic[cIndex], top, bottom, x);
+ if (lineT < 0) {
+ continue;
+ }
+ double cubicT = (double) (cIndex >> 1);
+ fIntersections->insert(cubicT, lineT, fCubic[cIndex]);
}
- double cubicT = (double) (cIndex >> 1);
- intersections.insert(cubicT, lineT, cubic[cIndex]);
}
-}
-void addNearVerticalEndPoints(double top, double bottom, double x) {
- for (int cIndex = 0; cIndex < 4; cIndex += 3) {
- double cubicT = (double) (cIndex >> 1);
- if (intersections.hasT(cubicT)) {
- continue;
+ void addNearVerticalEndPoints(double top, double bottom, double x) {
+ for (int cIndex = 0; cIndex < 4; cIndex += 3) {
+ double cubicT = (double) (cIndex >> 1);
+ if (fIntersections->hasT(cubicT)) {
+ continue;
+ }
+ double lineT = SkDLine::NearPointV(fCubic[cIndex], top, bottom, x);
+ if (lineT < 0) {
+ continue;
+ }
+ fIntersections->insert(cubicT, lineT, fCubic[cIndex]);
}
- double lineT = SkDLine::NearPointV(cubic[cIndex], top, bottom, x);
- if (lineT < 0) {
- continue;
- }
- intersections.insert(cubicT, lineT, cubic[cIndex]);
+ // FIXME: see if line end is nearly on cubic
}
- // FIXME: see if line end is nearly on cubic
-}
-double findLineT(double t) {
- SkDPoint xy = cubic.xyAtT(t);
- double dx = line[1].fX - line[0].fX;
- double dy = line[1].fY - line[0].fY;
- if (fabs(dx) > fabs(dy)) {
- return (xy.fX - line[0].fX) / dx;
+ double findLineT(double t) {
+ SkDPoint xy = fCubic.ptAtT(t);
+ double dx = fLine[1].fX - fLine[0].fX;
+ double dy = fLine[1].fY - fLine[0].fY;
+ if (fabs(dx) > fabs(dy)) {
+ return (xy.fX - fLine[0].fX) / dx;
+ }
+ return (xy.fY - fLine[0].fY) / dy;
}
- return (xy.fY - line[0].fY) / dy;
-}
-static bool pinTs(double* cubicT, double* lineT) {
- if (!approximately_one_or_less(*lineT)) {
- return false;
- }
- if (!approximately_zero_or_more(*lineT)) {
- return false;
- }
- if (precisely_less_than_zero(*cubicT)) {
- *cubicT = 0;
- } else if (precisely_greater_than_one(*cubicT)) {
- *cubicT = 1;
- }
- if (precisely_less_than_zero(*lineT)) {
- *lineT = 0;
- } else if (precisely_greater_than_one(*lineT)) {
- *lineT = 1;
+ bool pinTs(double* cubicT, double* lineT, SkDPoint* pt, PinTPoint ptSet) {
+ if (!approximately_one_or_less(*lineT)) {
+ return false;
+ }
+ if (!approximately_zero_or_more(*lineT)) {
+ return false;
+ }
+ double cT = *cubicT = SkPinT(*cubicT);
+ double lT = *lineT = SkPinT(*lineT);
+ if (lT == 0 || lT == 1 || (ptSet == kPointUninitialized && cT != 0 && cT != 1)) {
+ *pt = fLine.ptAtT(lT);
+ } else if (ptSet == kPointUninitialized) {
+ *pt = fCubic.ptAtT(cT);
+ }
+ return true;
}
- return true;
-}
private:
-
-const SkDCubic& cubic;
-const SkDLine& line;
-SkIntersections& intersections;
-bool fAllowNear;
+ const SkDCubic& fCubic;
+ const SkDLine& fLine;
+ SkIntersections* fIntersections;
+ bool fAllowNear;
};
int SkIntersections::horizontal(const SkDCubic& cubic, double left, double right, double y,
bool flipped) {
- LineCubicIntersections c(cubic, *(static_cast<SkDLine*>(0)), *this);
+ SkDLine line = {{{ left, y }, { right, y }}};
+ LineCubicIntersections c(cubic, line, this);
return c.horizontalIntersect(y, left, right, flipped);
}
int SkIntersections::vertical(const SkDCubic& cubic, double top, double bottom, double x,
bool flipped) {
- LineCubicIntersections c(cubic, *(static_cast<SkDLine*>(0)), *this);
+ SkDLine line = {{{ x, top }, { x, bottom }}};
+ LineCubicIntersections c(cubic, line, this);
return c.verticalIntersect(x, top, bottom, flipped);
}
int SkIntersections::intersect(const SkDCubic& cubic, const SkDLine& line) {
- LineCubicIntersections c(cubic, line, *this);
+ LineCubicIntersections c(cubic, line, this);
c.allowNear(fAllowNear);
return c.intersect();
}
int SkIntersections::intersectRay(const SkDCubic& cubic, const SkDLine& line) {
- LineCubicIntersections c(cubic, line, *this);
+ LineCubicIntersections c(cubic, line, this);
fUsed = c.intersectRay(fT[0]);
for (int index = 0; index < fUsed; ++index) {
- fPt[index] = cubic.xyAtT(fT[0][index]);
+ fPt[index] = cubic.ptAtT(fT[0][index]);
}
return fUsed;
}
diff --git a/src/pathops/SkDLineIntersection.cpp b/src/pathops/SkDLineIntersection.cpp
index faa7c1d392..46118429cd 100644
--- a/src/pathops/SkDLineIntersection.cpp
+++ b/src/pathops/SkDLineIntersection.cpp
@@ -27,9 +27,9 @@ SkDPoint SkIntersections::Line(const SkDLine& a, const SkDLine& b) {
}
int SkIntersections::computePoints(const SkDLine& line, int used) {
- fPt[0] = line.xyAtT(fT[0][0]);
+ fPt[0] = line.ptAtT(fT[0][0]);
if ((fUsed = used) == 2) {
- fPt[1] = line.xyAtT(fT[0][1]);
+ fPt[1] = line.ptAtT(fT[0][1]);
}
return fUsed;
}
@@ -102,19 +102,24 @@ int SkIntersections::intersect(const SkDLine& a, const SkDLine& b) {
byLen * axLen == ayLen * bxLen
byLen * axLen - ayLen * bxLen == 0 ( == denom )
*/
- double denom = byLen * axLen - ayLen * bxLen;
- if (0 != denom) {
+ double axByLen = axLen * byLen;
+ double ayBxLen = ayLen * bxLen;
+ // detect parallel lines the same way here and in SkOpAngle operator <
+ // so that non-parallel means they are also sortable
+ bool parallel = AlmostEqualUlps(axByLen, ayBxLen);
+ if (!parallel) {
double ab0y = a[0].fY - b[0].fY;
double ab0x = a[0].fX - b[0].fX;
double numerA = ab0y * bxLen - byLen * ab0x;
double numerB = ab0y * axLen - ayLen * ab0x;
+ double denom = axByLen - ayBxLen;
if (between(0, numerA, denom) && between(0, numerB, denom)) {
fT[0][0] = numerA / denom;
fT[1][0] = numerB / denom;
- return computePoints(a, 1);
+ computePoints(a, 1);
}
}
- if (fAllowNear || 0 == denom) {
+ if (fAllowNear || parallel) {
for (int iA = 0; iA < 2; ++iA) {
if ((t = b.nearPoint(a[iA])) >= 0) {
insert(iA, t, a[iA]);
diff --git a/src/pathops/SkDQuadIntersection.cpp b/src/pathops/SkDQuadIntersection.cpp
index 124c7dab06..e10fb3f139 100644
--- a/src/pathops/SkDQuadIntersection.cpp
+++ b/src/pathops/SkDQuadIntersection.cpp
@@ -87,8 +87,8 @@ static bool only_end_pts_in_common(const SkDQuad& q1, const SkDQuad& q2) {
for (int oddMan = 0; oddMan < 3; ++oddMan) {
const SkDPoint* endPt[2];
for (int opp = 1; opp < 3; ++opp) {
- int end = oddMan ^ opp;
- if (end == 3) {
+ int end = oddMan ^ opp; // choose a value not equal to oddMan
+ if (3 == end) { // and correct so that largest value is 1 or 2
end = opp;
}
endPt[opp - 1] = &q1[end];
@@ -120,7 +120,7 @@ tryNextHalfPlane:
static bool add_intercept(const SkDQuad& q1, const SkDQuad& q2, double tMin, double tMax,
SkIntersections* i, bool* subDivide) {
double tMid = (tMin + tMax) / 2;
- SkDPoint mid = q2.xyAtT(tMid);
+ SkDPoint mid = q2.ptAtT(tMid);
SkDLine line;
line[0] = line[1] = mid;
SkDVector dxdy = q2.dxdyAtT(tMid);
@@ -138,7 +138,7 @@ static bool add_intercept(const SkDQuad& q1, const SkDQuad& q2, double tMin, dou
if (roots == 2) {
return false;
}
- SkDPoint pt2 = q1.xyAtT(rootTs[0][0]);
+ SkDPoint pt2 = q1.ptAtT(rootTs[0][0]);
if (!pt2.approximatelyEqualHalf(mid)) {
return false;
}
@@ -160,8 +160,8 @@ static bool is_linear_inner(const SkDQuad& q1, double t1s, double t1e, const SkD
for (int idx2 = 0; idx2 < roots; ++idx2) {
double t = rootTs[0][idx2];
#ifdef SK_DEBUG
- SkDPoint qPt = q2.xyAtT(t);
- SkDPoint lPt = testLines[index]->xyAtT(rootTs[1][idx2]);
+ SkDPoint qPt = q2.ptAtT(t);
+ SkDPoint lPt = testLines[index]->ptAtT(rootTs[1][idx2]);
SkASSERT(qPt.approximatelyEqual(lPt));
#endif
if (approximately_negative(t - t2s) || approximately_positive(t - t2e)) {
@@ -183,12 +183,12 @@ static bool is_linear_inner(const SkDQuad& q1, double t1s, double t1e, const SkD
tMin = tsFound[0];
tMax = tsFound[tsFound.count() - 1];
}
- SkDPoint end = q2.xyAtT(t2s);
+ SkDPoint end = q2.ptAtT(t2s);
bool startInTriangle = hull.pointInHull(end);
if (startInTriangle) {
tMin = t2s;
}
- end = q2.xyAtT(t2e);
+ end = q2.ptAtT(t2e);
bool endInTriangle = hull.pointInHull(end);
if (endInTriangle) {
tMax = t2e;
@@ -290,8 +290,8 @@ static bool binary_search(const SkDQuad& quad1, const SkDQuad& quad2, double* t1
SkDPoint t1[3], t2[3];
int calcMask = ~0;
do {
- if (calcMask & (1 << 1)) t1[1] = quad1.xyAtT(*t1Seed);
- if (calcMask & (1 << 4)) t2[1] = quad2.xyAtT(*t2Seed);
+ if (calcMask & (1 << 1)) t1[1] = quad1.ptAtT(*t1Seed);
+ if (calcMask & (1 << 4)) t2[1] = quad2.ptAtT(*t2Seed);
if (t1[1].approximatelyEqual(t2[1])) {
*pt = t1[1];
#if ONE_OFF_DEBUG
@@ -300,10 +300,10 @@ static bool binary_search(const SkDQuad& quad1, const SkDQuad& quad2, double* t1
#endif
return true;
}
- if (calcMask & (1 << 0)) t1[0] = quad1.xyAtT(*t1Seed - tStep);
- if (calcMask & (1 << 2)) t1[2] = quad1.xyAtT(*t1Seed + tStep);
- if (calcMask & (1 << 3)) t2[0] = quad2.xyAtT(*t2Seed - tStep);
- if (calcMask & (1 << 5)) t2[2] = quad2.xyAtT(*t2Seed + tStep);
+ if (calcMask & (1 << 0)) t1[0] = quad1.ptAtT(*t1Seed - tStep);
+ if (calcMask & (1 << 2)) t1[2] = quad1.ptAtT(*t1Seed + tStep);
+ if (calcMask & (1 << 3)) t2[0] = quad2.ptAtT(*t2Seed - tStep);
+ if (calcMask & (1 << 5)) t2[2] = quad2.ptAtT(*t2Seed + tStep);
double dist[3][3];
// OPTIMIZE: using calcMask value permits skipping some distance calcuations
// if prior loop's results are moved to correct slot for reuse
@@ -361,6 +361,34 @@ static bool binary_search(const SkDQuad& quad1, const SkDQuad& quad2, double* t1
return false;
}
+static void lookNearEnd(const SkDQuad& q1, const SkDQuad& q2, int testT,
+ const SkIntersections& orig, bool swap, SkIntersections* i) {
+ if (orig.used() == 1 && orig[!swap][0] == testT) {
+ return;
+ }
+ if (orig.used() == 2 && orig[!swap][1] == testT) {
+ return;
+ }
+ SkDLine tmpLine;
+ int testTIndex = testT << 1;
+ tmpLine[0] = tmpLine[1] = q2[testTIndex];
+ tmpLine[1].fX += q2[1].fY - q2[testTIndex].fY;
+ tmpLine[1].fY -= q2[1].fX - q2[testTIndex].fX;
+ SkIntersections impTs;
+ impTs.intersectRay(q1, tmpLine);
+ for (int index = 0; index < impTs.used(); ++index) {
+ SkDPoint realPt = impTs.pt(index);
+ if (!tmpLine[0].approximatelyEqualHalf(realPt)) {
+ continue;
+ }
+ if (swap) {
+ i->insert(testT, impTs[0][index], tmpLine[0]);
+ } else {
+ i->insert(impTs[0][index], testT, tmpLine[0]);
+ }
+ }
+}
+
int SkIntersections::intersect(const SkDQuad& q1, const SkDQuad& q2) {
// if the quads share an end point, check to see if they overlap
@@ -379,6 +407,7 @@ int SkIntersections::intersect(const SkDQuad& q1, const SkDQuad& q2) {
return fUsed;
}
// see if either quad is really a line
+ // FIXME: figure out why reduce step didn't find this earlier
if (is_linear(q1, q2, this)) {
return fUsed;
}
@@ -388,30 +417,42 @@ int SkIntersections::intersect(const SkDQuad& q1, const SkDQuad& q2) {
set(swapped);
return fUsed;
}
- SkDQuadImplicit i1(q1);
- SkDQuadImplicit i2(q2);
- if (i1.match(i2)) {
- // FIXME: compute T values
- // compute the intersections of the ends to find the coincident span
- reset();
- bool useVertical = fabs(q1[0].fX - q1[2].fX) < fabs(q1[0].fY - q1[2].fY);
- double t;
- if ((t = SkIntersections::Axial(q1, q2[0], useVertical)) >= 0) {
- insertCoincident(t, 0, q2[0]);
- }
- if ((t = SkIntersections::Axial(q1, q2[2], useVertical)) >= 0) {
- insertCoincident(t, 1, q2[2]);
- }
- useVertical = fabs(q2[0].fX - q2[2].fX) < fabs(q2[0].fY - q2[2].fY);
- if ((t = SkIntersections::Axial(q2, q1[0], useVertical)) >= 0) {
- insertCoincident(0, t, q1[0]);
+ SkIntersections copyI(*this);
+ lookNearEnd(q1, q2, 0, *this, false, &copyI);
+ lookNearEnd(q1, q2, 1, *this, false, &copyI);
+ lookNearEnd(q2, q1, 0, *this, true, &copyI);
+ lookNearEnd(q2, q1, 1, *this, true, &copyI);
+ int innerEqual = 0;
+ if (copyI.fUsed >= 2) {
+ SkASSERT(copyI.fUsed <= 4);
+ double width = copyI[0][1] - copyI[0][0];
+ int midEnd = 1;
+ for (int index = 2; index < copyI.fUsed; ++index) {
+ double testWidth = copyI[0][index] - copyI[0][index - 1];
+ if (testWidth <= width) {
+ continue;
+ }
+ midEnd = index;
}
- if ((t = SkIntersections::Axial(q2, q1[2], useVertical)) >= 0) {
- insertCoincident(1, t, q1[2]);
+ for (int index = 0; index < 2; ++index) {
+ double testT = (copyI[0][midEnd] * (index + 1)
+ + copyI[0][midEnd - 1] * (2 - index)) / 3;
+ SkDPoint testPt1 = q1.ptAtT(testT);
+ testT = (copyI[1][midEnd] * (index + 1) + copyI[1][midEnd - 1] * (2 - index)) / 3;
+ SkDPoint testPt2 = q2.ptAtT(testT);
+ innerEqual += testPt1.approximatelyEqual(testPt2);
}
- SkASSERT(coincidentUsed() <= 2);
+ }
+ bool expectCoincident = copyI.fUsed >= 2 && innerEqual == 2;
+ if (expectCoincident) {
+ reset();
+ insertCoincident(copyI[0][0], copyI[1][0], copyI.fPt[0]);
+ int last = copyI.fUsed - 1;
+ insertCoincident(copyI[0][last], copyI[1][last], copyI.fPt[last]);
return fUsed;
}
+ SkDQuadImplicit i1(q1);
+ SkDQuadImplicit i2(q2);
int index;
bool flip1 = q1[2] == q2[0];
bool flip2 = q1[0] == q2[2];
@@ -423,7 +464,7 @@ int SkIntersections::intersect(const SkDQuad& q1, const SkDQuad& q2) {
int r1Count = addValidRoots(roots1, rootCount, roots1Copy);
SkDPoint pts1[4];
for (index = 0; index < r1Count; ++index) {
- pts1[index] = q1.xyAtT(roots1Copy[index]);
+ pts1[index] = q1.ptAtT(roots1Copy[index]);
}
double roots2[4];
int rootCount2 = findRoots(i1, q2, roots2, useCubic, flip2, 0);
@@ -431,7 +472,7 @@ int SkIntersections::intersect(const SkDQuad& q1, const SkDQuad& q2) {
int r2Count = addValidRoots(roots2, rootCount2, roots2Copy);
SkDPoint pts2[4];
for (index = 0; index < r2Count; ++index) {
- pts2[index] = q2.xyAtT(roots2Copy[index]);
+ pts2[index] = q2.ptAtT(roots2Copy[index]);
}
if (r1Count == r2Count && r1Count <= 1) {
if (r1Count == 1) {
diff --git a/src/pathops/SkDQuadLineIntersection.cpp b/src/pathops/SkDQuadLineIntersection.cpp
index 9df2dc248a..58b3060ab3 100644
--- a/src/pathops/SkDQuadLineIntersection.cpp
+++ b/src/pathops/SkDQuadLineIntersection.cpp
@@ -89,10 +89,15 @@ Thus, if the slope of the line tends towards vertical, we use:
class LineQuadraticIntersections {
public:
+ enum PinTPoint {
+ kPointUninitialized,
+ kPointInitialized
+ };
+
LineQuadraticIntersections(const SkDQuad& q, const SkDLine& l, SkIntersections* i)
- : quad(q)
- , line(l)
- , intersections(i)
+ : fQuad(q)
+ , fLine(l)
+ , fIntersections(i)
, fAllowNear(true) {
}
@@ -116,11 +121,11 @@ public:
for each of the three points (e.g. n = 0 to 2)
quad[n].fY' = (quad[n].fY - line[0].fY) * A - (quad[n].fX - line[0].fX) * O
*/
- double adj = line[1].fX - line[0].fX;
- double opp = line[1].fY - line[0].fY;
+ double adj = fLine[1].fX - fLine[0].fX;
+ double opp = fLine[1].fY - fLine[0].fY;
double r[3];
for (int n = 0; n < 3; ++n) {
- r[n] = (quad[n].fY - line[0].fY) * adj - (quad[n].fX - line[0].fX) * opp;
+ r[n] = (fQuad[n].fY - fLine[0].fY) * adj - (fQuad[n].fX - fLine[0].fX) * opp;
}
double A = r[2];
double B = r[1];
@@ -137,21 +142,21 @@ public:
for (int index = 0; index < roots; ++index) {
double quadT = rootVals[index];
double lineT = findLineT(quadT);
- if (PinTs(&quadT, &lineT)) {
- SkDPoint pt = line.xyAtT(lineT);
- intersections->insert(quadT, lineT, pt);
+ SkDPoint pt;
+ if (pinTs(&quadT, &lineT, &pt, kPointUninitialized)) {
+ fIntersections->insert(quadT, lineT, pt);
}
}
if (fAllowNear) {
addNearEndPoints();
}
- return intersections->used();
+ return fIntersections->used();
}
int horizontalIntersect(double axisIntercept, double roots[2]) {
- double D = quad[2].fY; // f
- double E = quad[1].fY; // e
- double F = quad[0].fY; // d
+ double D = fQuad[2].fY; // f
+ double E = fQuad[1].fY; // e
+ double F = fQuad[0].fY; // d
D += F - 2 * E; // D = d - 2*e + f
E -= F; // E = -(d - e)
F -= axisIntercept;
@@ -164,25 +169,25 @@ public:
int roots = horizontalIntersect(axisIntercept, rootVals);
for (int index = 0; index < roots; ++index) {
double quadT = rootVals[index];
- SkDPoint pt = quad.xyAtT(quadT);
+ SkDPoint pt = fQuad.ptAtT(quadT);
double lineT = (pt.fX - left) / (right - left);
- if (PinTs(&quadT, &lineT)) {
- intersections->insert(quadT, lineT, pt);
+ if (pinTs(&quadT, &lineT, &pt, kPointInitialized)) {
+ fIntersections->insert(quadT, lineT, pt);
}
}
if (fAllowNear) {
addNearHorizontalEndPoints(left, right, axisIntercept);
}
if (flipped) {
- intersections->flip();
+ fIntersections->flip();
}
- return intersections->used();
+ return fIntersections->used();
}
int verticalIntersect(double axisIntercept, double roots[2]) {
- double D = quad[2].fX; // f
- double E = quad[1].fX; // e
- double F = quad[0].fX; // d
+ double D = fQuad[2].fX; // f
+ double E = fQuad[1].fX; // e
+ double F = fQuad[0].fX; // d
D += F - 2 * E; // D = d - 2*e + f
E -= F; // E = -(d - e)
F -= axisIntercept;
@@ -195,107 +200,107 @@ public:
int roots = verticalIntersect(axisIntercept, rootVals);
for (int index = 0; index < roots; ++index) {
double quadT = rootVals[index];
- SkDPoint pt = quad.xyAtT(quadT);
+ SkDPoint pt = fQuad.ptAtT(quadT);
double lineT = (pt.fY - top) / (bottom - top);
- if (PinTs(&quadT, &lineT)) {
- intersections->insert(quadT, lineT, pt);
+ if (pinTs(&quadT, &lineT, &pt, kPointInitialized)) {
+ fIntersections->insert(quadT, lineT, pt);
}
}
if (fAllowNear) {
addNearVerticalEndPoints(top, bottom, axisIntercept);
}
if (flipped) {
- intersections->flip();
+ fIntersections->flip();
}
- return intersections->used();
+ return fIntersections->used();
}
protected:
// add endpoints first to get zero and one t values exactly
void addExactEndPoints() {
for (int qIndex = 0; qIndex < 3; qIndex += 2) {
- double lineT = line.exactPoint(quad[qIndex]);
+ double lineT = fLine.exactPoint(fQuad[qIndex]);
if (lineT < 0) {
continue;
}
double quadT = (double) (qIndex >> 1);
- intersections->insert(quadT, lineT, quad[qIndex]);
+ fIntersections->insert(quadT, lineT, fQuad[qIndex]);
}
}
void addNearEndPoints() {
for (int qIndex = 0; qIndex < 3; qIndex += 2) {
double quadT = (double) (qIndex >> 1);
- if (intersections->hasT(quadT)) {
+ if (fIntersections->hasT(quadT)) {
continue;
}
- double lineT = line.nearPoint(quad[qIndex]);
+ double lineT = fLine.nearPoint(fQuad[qIndex]);
if (lineT < 0) {
continue;
}
- intersections->insert(quadT, lineT, quad[qIndex]);
+ fIntersections->insert(quadT, lineT, fQuad[qIndex]);
}
// FIXME: see if line end is nearly on quad
}
void addExactHorizontalEndPoints(double left, double right, double y) {
for (int qIndex = 0; qIndex < 3; qIndex += 2) {
- double lineT = SkDLine::ExactPointH(quad[qIndex], left, right, y);
+ double lineT = SkDLine::ExactPointH(fQuad[qIndex], left, right, y);
if (lineT < 0) {
continue;
}
double quadT = (double) (qIndex >> 1);
- intersections->insert(quadT, lineT, quad[qIndex]);
+ fIntersections->insert(quadT, lineT, fQuad[qIndex]);
}
}
void addNearHorizontalEndPoints(double left, double right, double y) {
for (int qIndex = 0; qIndex < 3; qIndex += 2) {
double quadT = (double) (qIndex >> 1);
- if (intersections->hasT(quadT)) {
+ if (fIntersections->hasT(quadT)) {
continue;
}
- double lineT = SkDLine::NearPointH(quad[qIndex], left, right, y);
+ double lineT = SkDLine::NearPointH(fQuad[qIndex], left, right, y);
if (lineT < 0) {
continue;
}
- intersections->insert(quadT, lineT, quad[qIndex]);
+ fIntersections->insert(quadT, lineT, fQuad[qIndex]);
}
// FIXME: see if line end is nearly on quad
}
void addExactVerticalEndPoints(double top, double bottom, double x) {
for (int qIndex = 0; qIndex < 3; qIndex += 2) {
- double lineT = SkDLine::ExactPointV(quad[qIndex], top, bottom, x);
+ double lineT = SkDLine::ExactPointV(fQuad[qIndex], top, bottom, x);
if (lineT < 0) {
continue;
}
double quadT = (double) (qIndex >> 1);
- intersections->insert(quadT, lineT, quad[qIndex]);
+ fIntersections->insert(quadT, lineT, fQuad[qIndex]);
}
}
void addNearVerticalEndPoints(double top, double bottom, double x) {
for (int qIndex = 0; qIndex < 3; qIndex += 2) {
double quadT = (double) (qIndex >> 1);
- if (intersections->hasT(quadT)) {
+ if (fIntersections->hasT(quadT)) {
continue;
}
- double lineT = SkDLine::NearPointV(quad[qIndex], top, bottom, x);
+ double lineT = SkDLine::NearPointV(fQuad[qIndex], top, bottom, x);
if (lineT < 0) {
continue;
}
- intersections->insert(quadT, lineT, quad[qIndex]);
+ fIntersections->insert(quadT, lineT, fQuad[qIndex]);
}
// FIXME: see if line end is nearly on quad
}
double findLineT(double t) {
- SkDPoint xy = quad.xyAtT(t);
- double dx = line[1].fX - line[0].fX;
- double dy = line[1].fY - line[0].fY;
- double dxT = (xy.fX - line[0].fX) / dx;
- double dyT = (xy.fY - line[0].fY) / dy;
+ SkDPoint xy = fQuad.ptAtT(t);
+ double dx = fLine[1].fX - fLine[0].fX;
+ double dy = fLine[1].fY - fLine[0].fY;
+ double dxT = (xy.fX - fLine[0].fX) / dx;
+ double dyT = (xy.fY - fLine[0].fY) / dy;
if (!between(FLT_EPSILON, dxT, 1 - FLT_EPSILON) && between(0, dyT, 1)) {
return dyT;
}
@@ -305,22 +310,27 @@ protected:
return fabs(dx) > fabs(dy) ? dxT : dyT;
}
- static bool PinTs(double* quadT, double* lineT) {
+ bool pinTs(double* quadT, double* lineT, SkDPoint* pt, PinTPoint ptSet) {
if (!approximately_one_or_less(*lineT)) {
return false;
}
if (!approximately_zero_or_more(*lineT)) {
return false;
}
- *quadT = SkPinT(*quadT);
- *lineT = SkPinT(*lineT);
+ double qT = *quadT = SkPinT(*quadT);
+ double lT = *lineT = SkPinT(*lineT);
+ if (lT == 0 || lT == 1 || (ptSet == kPointUninitialized && qT != 0 && qT != 1)) {
+ *pt = fLine.ptAtT(lT);
+ } else if (ptSet == kPointUninitialized) {
+ *pt = fQuad.ptAtT(qT);
+ }
return true;
}
private:
- const SkDQuad& quad;
- const SkDLine& line;
- SkIntersections* intersections;
+ const SkDQuad& fQuad;
+ const SkDLine& fLine;
+ SkIntersections* fIntersections;
bool fAllowNear;
};
@@ -332,7 +342,7 @@ static double horizontalIntersect(const SkDQuad& quad, const SkDPoint& pt) {
int roots = q.horizontalIntersect(pt.fY, rootVals);
for (int index = 0; index < roots; ++index) {
double t = rootVals[index];
- SkDPoint qPt = quad.xyAtT(t);
+ SkDPoint qPt = quad.ptAtT(t);
if (AlmostEqualUlps(qPt.fX, pt.fX)) {
return t;
}
@@ -347,7 +357,7 @@ static double verticalIntersect(const SkDQuad& quad, const SkDPoint& pt) {
int roots = q.verticalIntersect(pt.fX, rootVals);
for (int index = 0; index < roots; ++index) {
double t = rootVals[index];
- SkDPoint qPt = quad.xyAtT(t);
+ SkDPoint qPt = quad.ptAtT(t);
if (AlmostEqualUlps(qPt.fY, pt.fY)) {
return t;
}
@@ -364,13 +374,15 @@ double SkIntersections::Axial(const SkDQuad& q1, const SkDPoint& p, bool vertica
int SkIntersections::horizontal(const SkDQuad& quad, double left, double right, double y,
bool flipped) {
- LineQuadraticIntersections q(quad, *(static_cast<SkDLine*>(0)), this);
+ SkDLine line = {{{ left, y }, { right, y }}};
+ LineQuadraticIntersections q(quad, line, this);
return q.horizontalIntersect(y, left, right, flipped);
}
int SkIntersections::vertical(const SkDQuad& quad, double top, double bottom, double x,
bool flipped) {
- LineQuadraticIntersections q(quad, *(static_cast<SkDLine*>(0)), this);
+ SkDLine line = {{{ x, top }, { x, bottom }}};
+ LineQuadraticIntersections q(quad, line, this);
return q.verticalIntersect(x, top, bottom, flipped);
}
@@ -384,7 +396,7 @@ int SkIntersections::intersectRay(const SkDQuad& quad, const SkDLine& line) {
LineQuadraticIntersections q(quad, line, this);
fUsed = q.intersectRay(fT[0]);
for (int index = 0; index < fUsed; ++index) {
- fPt[index] = quad.xyAtT(fT[0][index]);
+ fPt[index] = quad.ptAtT(fT[0][index]);
}
return fUsed;
}
diff --git a/src/pathops/SkIntersections.cpp b/src/pathops/SkIntersections.cpp
index fe23316683..242c67b926 100644
--- a/src/pathops/SkIntersections.cpp
+++ b/src/pathops/SkIntersections.cpp
@@ -54,108 +54,6 @@ void SkIntersections::flip() {
}
}
-void SkIntersections::insertCoincidentPair(double s1, double e1, double s2, double e2,
- const SkDPoint& startPt, const SkDPoint& endPt) {
- SkASSERT(s1 < e1);
- SkASSERT(s2 != e2);
- if (coincidentUsed() != fUsed) { // if the curve is partially coincident, treat it as fully so
- for (int index = fUsed - 1; index >= 0; --index) {
- if (fIsCoincident[0] & (1 << index)) {
- continue;
- }
- double nonCoinT = fT[0][index];
- if (!between(s1, nonCoinT, e1)) {
- if (s1 > nonCoinT) {
- s1 = nonCoinT;
- } else {
- e1 = nonCoinT;
- }
- }
- nonCoinT = fT[1][index];
- if (!between(s2, nonCoinT, e2)) {
- if ((s2 > nonCoinT) ^ (s2 > e2)) {
- s2 = nonCoinT;
- } else {
- e2 = nonCoinT;
- }
- }
- removeOne(index);
- }
- }
- SkASSERT(coincidentUsed() == fUsed);
- SkASSERT((coincidentUsed() & 1) != 1);
- int i1 = 0;
- int i2 = 0;
- do {
- while (i1 < fUsed && !(fIsCoincident[fSwap] & (1 << i1))) {
- ++i1;
- }
- if (i1 == fUsed) {
- break;
- }
- SkASSERT(i1 < fUsed);
- int iEnd1 = i1 + 1;
- while (!(fIsCoincident[fSwap] & (1 << iEnd1))) {
- ++iEnd1;
- }
- SkASSERT(iEnd1 < fUsed);
- double cs1 = fT[fSwap][i1];
- double ce1 = fT[fSwap][iEnd1];
- bool s1in = between(cs1, s1, ce1) || startPt.approximatelyEqual(fPt[i1])
- || startPt.approximatelyEqual(fPt[iEnd1]);
- bool e1in = between(cs1, e1, ce1) || endPt.approximatelyEqual(fPt[i1])
- || endPt.approximatelyEqual(fPt[iEnd1]);
- while (i2 < fUsed && !(fIsCoincident[fSwap ^ 1] & (1 << i2))) {
- ++i2;
- }
- int iEnd2 = i2 + 1;
- while (!(fIsCoincident[fSwap ^ 1] & (1 << iEnd2))) {
- ++iEnd2;
- }
- SkASSERT(iEnd2 < fUsed);
- double cs2 = fT[fSwap ^ 1][i2];
- double ce2 = fT[fSwap ^ 1][iEnd2];
- bool s2in = between(cs2, s2, ce2) || startPt.approximatelyEqual(fPt[i2])
- || startPt.approximatelyEqual(fPt[iEnd2]);
- bool e2in = between(cs2, e2, ce2) || endPt.approximatelyEqual(fPt[i2])
- || endPt.approximatelyEqual(fPt[iEnd2]);
- if ((s1in | e1in) & (s2in | e2in)) {
- if (s1 < cs1) {
- fT[fSwap][i1] = s1;
- fPt[i1] = startPt;
- } else if (e1 < cs1) {
- fT[fSwap][i1] = e1;
- fPt[i1] = endPt;
- }
- if (s1 > ce1) {
- fT[fSwap][iEnd1] = s1;
- fPt[iEnd1] = startPt;
- } else if (e1 > ce1) {
- fT[fSwap][iEnd1] = e1;
- fPt[iEnd1] = endPt;
- }
- if (s2 > e2) {
- SkTSwap(cs2, ce2);
- SkTSwap(i2, iEnd2);
- }
- if (s2 < cs2) {
- fT[fSwap ^ 1][i2] = s2;
- } else if (e2 < cs2) {
- fT[fSwap ^ 1][i2] = e2;
- }
- if (s2 > ce2) {
- fT[fSwap ^ 1][iEnd2] = s2;
- } else if (e2 > ce2) {
- fT[fSwap ^ 1][iEnd2] = e2;
- }
- return;
- }
- } while (true);
- SkASSERT(fUsed < 9);
- insertCoincident(s1, s2, startPt);
- insertCoincident(e1, e2, endPt);
-}
-
int SkIntersections::insert(double one, double two, const SkDPoint& pt) {
if (fIsCoincident[0] == 3 && between(fT[0][0], one, fT[0][1])) {
// For now, don't allow a mix of coincident and non-coincident intersections
diff --git a/src/pathops/SkIntersections.h b/src/pathops/SkIntersections.h
index de3d44cd70..26a1d1a559 100644
--- a/src/pathops/SkIntersections.h
+++ b/src/pathops/SkIntersections.h
@@ -208,8 +208,6 @@ public:
int insert(double one, double two, const SkDPoint& pt);
// start if index == 0 : end if index == 1
void insertCoincident(double one, double two, const SkDPoint& pt);
- void insertCoincidentPair(double s1, double e1, double s2, double e2,
- const SkDPoint& startPt, const SkDPoint& endPt);
int intersect(const SkDLine&, const SkDLine&);
int intersect(const SkDQuad&, const SkDLine&);
int intersect(const SkDQuad&, const SkDQuad&);
diff --git a/src/pathops/SkOpSegment.cpp b/src/pathops/SkOpSegment.cpp
index 5b20749957..7e69bb835b 100644
--- a/src/pathops/SkOpSegment.cpp
+++ b/src/pathops/SkOpSegment.cpp
@@ -1082,9 +1082,7 @@ bool SkOpSegment::bumpSpan(SkOpSpan* span, int windDelta, int oppDelta) {
// look to see if the curve end intersects an intermediary that intersects the other
void SkOpSegment::checkEnds() {
-#if 1
- return; // FIXME: suspect we will need the code below to make intersections consistent
-#else
+ debugValidate();
SkTDArray<SkOpSpan> missingSpans;
int count = fTs.count();
for (int index = 0; index < count; ++index) {
@@ -1150,14 +1148,20 @@ nextPeeker:
;
}
int missingCount = missingSpans.count();
+ if (missingCount == 0) {
+ return;
+ }
+ debugValidate();
for (int index = 0; index < missingCount; ++index) {
const SkOpSpan& missing = missingSpans[index];
addTPair(missing.fT, missing.fOther, missing.fOtherT, false, missing.fPt);
}
- if (missingCount > 0) {
- fixOtherTIndex();
+ fixOtherTIndex();
+ for (int index = 0; index < missingCount; ++index) {
+ const SkOpSpan& missing = missingSpans[index];
+ missing.fOther->fixOtherTIndex();
}
-#endif
+ debugValidate();
}
bool SkOpSegment::equalPoints(int greaterTIndex, int lesserTIndex) {
@@ -1792,13 +1796,16 @@ void SkOpSegment::fixOtherTIndex() {
double oT = iSpan.fOtherT;
SkOpSegment* other = iSpan.fOther;
int oCount = other->fTs.count();
+ SkDEBUGCODE(iSpan.fOtherIndex = -1);
for (int o = 0; o < oCount; ++o) {
SkOpSpan& oSpan = other->fTs[o];
if (oT == oSpan.fT && this == oSpan.fOther && oSpan.fOtherT == iSpan.fT) {
iSpan.fOtherIndex = o;
+ oSpan.fOtherIndex = i;
break;
}
}
+ SkASSERT(iSpan.fOtherIndex >= 0);
}
}
@@ -2755,6 +2762,7 @@ void SkOpSegment::debugShowTs() const {
#if DEBUG_ACTIVE_SPANS || DEBUG_ACTIVE_SPANS_FIRST_ONLY
void SkOpSegment::debugShowActiveSpans() const {
+ debugValidate();
if (done()) {
return;
}
@@ -2763,8 +2771,6 @@ void SkOpSegment::debugShowActiveSpans() const {
double lastT = -1;
#endif
for (int i = 0; i < fTs.count(); ++i) {
- SkASSERT(&fTs[i] == &fTs[i].fOther->fTs[fTs[i].fOtherIndex].fOther->
- fTs[fTs[i].fOther->fTs[fTs[i].fOtherIndex].fOtherIndex]);
if (fTs[i].fDone) {
continue;
}
@@ -2995,3 +3001,27 @@ int SkOpSegment::debugShowWindingValues(int slotCount, int ofInterest) const {
return sum;
}
#endif
+
+void SkOpSegment::debugValidate() const {
+#if DEBUG_VALIDATE
+ int count = fTs.count();
+ SkASSERT(count >= 2);
+ SkASSERT(fTs[0].fT == 0);
+ SkASSERT(fTs[count - 1].fT == 1);
+ int done = 0;
+ double t = -1;
+ for (int i = 0; i < count; ++i) {
+ const SkOpSpan& span = fTs[i];
+ SkASSERT(t <= span.fT);
+ t = span.fT;
+ int otherIndex = span.fOtherIndex;
+ const SkOpSegment* other = span.fOther;
+ const SkOpSpan& otherSpan = other->fTs[otherIndex];
+ SkASSERT(otherSpan.fPt == span.fPt);
+ SkASSERT(otherSpan.fOtherT == t);
+ SkASSERT(&fTs[i] == &otherSpan.fOther->fTs[otherSpan.fOtherIndex]);
+ done += span.fDone;
+ }
+ SkASSERT(done == fDoneSpans);
+#endif
+}
diff --git a/src/pathops/SkOpSegment.h b/src/pathops/SkOpSegment.h
index 7e5e644f1d..bfaf4ed9de 100644
--- a/src/pathops/SkOpSegment.h
+++ b/src/pathops/SkOpSegment.h
@@ -130,6 +130,11 @@ public:
return fTs[index].fOther;
}
+ // was used only by right angle winding finding
+ SkPoint ptAtT(double mid) const {
+ return (*CurvePointAtT[SkPathOpsVerbToPoints(fVerb)])(fPts, mid);
+ }
+
const SkPoint* pts() const {
return fPts;
}
@@ -214,11 +219,6 @@ public:
return span->fPt;
}
- // used only by right angle winding finding
- SkPoint xyAtT(double mid) const {
- return (*CurvePointAtT[SkPathOpsVerbToPoints(fVerb)])(fPts, mid);
- }
-
const SkPoint& xyAtT(int index) const {
return xyAtT(&fTs[index]);
}
@@ -394,6 +394,7 @@ private:
return value < 0 ? '?' : value <= 9 ? '0' + value : '+';
}
#endif
+ void debugValidate() const;
const SkPoint* fPts;
SkPathOpsBounds fBounds;
diff --git a/src/pathops/SkPathOpsCommon.cpp b/src/pathops/SkPathOpsCommon.cpp
index 9a92b00acd..28cf59cdd3 100644
--- a/src/pathops/SkPathOpsCommon.cpp
+++ b/src/pathops/SkPathOpsCommon.cpp
@@ -17,7 +17,7 @@ static int contourRangeCheckY(const SkTArray<SkOpContour*, true>& contourList, S
const double mid = *midPtr;
const SkOpSegment* current = *currentPtr;
double tAtMid = current->tAtMid(index, endIndex, mid);
- SkPoint basePt = current->xyAtT(tAtMid);
+ SkPoint basePt = current->ptAtT(tAtMid);
int contourCount = contourList.count();
SkScalar bestY = SK_ScalarMin;
SkOpSegment* bestSeg = NULL;
diff --git a/src/pathops/SkPathOpsCubic.cpp b/src/pathops/SkPathOpsCubic.cpp
index 60dca44a27..5fbfeba50d 100644
--- a/src/pathops/SkPathOpsCubic.cpp
+++ b/src/pathops/SkPathOpsCubic.cpp
@@ -304,7 +304,7 @@ SkDPoint SkDCubic::top(double startT, double endT) const {
int roots = FindExtrema(sub[0].fY, sub[1].fY, sub[2].fY, sub[3].fY, extremeTs);
for (int index = 0; index < roots; ++index) {
double t = startT + (endT - startT) * extremeTs[index];
- SkDPoint mid = xyAtT(t);
+ SkDPoint mid = ptAtT(t);
if (topPt.fY > mid.fY || (topPt.fY == mid.fY && topPt.fX > mid.fX)) {
topPt = mid;
}
@@ -313,7 +313,13 @@ SkDPoint SkDCubic::top(double startT, double endT) const {
return topPt;
}
-SkDPoint SkDCubic::xyAtT(double t) const {
+SkDPoint SkDCubic::ptAtT(double t) const {
+ if (0 == t) {
+ return fPts[0];
+ }
+ if (1 == t) {
+ return fPts[3];
+ }
double one_t = 1 - t;
double one_t2 = one_t * one_t;
double a = one_t2 * one_t;
diff --git a/src/pathops/SkPathOpsCubic.h b/src/pathops/SkPathOpsCubic.h
index f07af80dcd..1ba35be22b 100644
--- a/src/pathops/SkPathOpsCubic.h
+++ b/src/pathops/SkPathOpsCubic.h
@@ -53,6 +53,7 @@ struct SkDCubic {
int findMaxCurvature(double tValues[]) const;
bool isLinear(int startIndex, int endIndex) const;
bool monotonicInY() const;
+ SkDPoint ptAtT(double t) const;
static int RootsReal(double A, double B, double C, double D, double t[3]);
static int RootsValidT(const double A, const double B, const double C, double D, double s[3]);
bool serpentine() const;
@@ -76,7 +77,6 @@ struct SkDCubic {
SkDPoint top(double startT, double endT) const;
void toQuadraticTs(double precision, SkTArray<double, true>* ts) const;
SkDQuad toQuad() const;
- SkDPoint xyAtT(double t) const;
};
#endif
diff --git a/src/pathops/SkPathOpsCurve.h b/src/pathops/SkPathOpsCurve.h
index ca68a664e6..5d12cb811a 100644
--- a/src/pathops/SkPathOpsCurve.h
+++ b/src/pathops/SkPathOpsCurve.h
@@ -14,19 +14,19 @@
static SkDPoint dline_xy_at_t(const SkPoint a[2], double t) {
SkDLine line;
line.set(a);
- return line.xyAtT(t);
+ return line.ptAtT(t);
}
static SkDPoint dquad_xy_at_t(const SkPoint a[3], double t) {
SkDQuad quad;
quad.set(a);
- return quad.xyAtT(t);
+ return quad.ptAtT(t);
}
static SkDPoint dcubic_xy_at_t(const SkPoint a[4], double t) {
SkDCubic cubic;
cubic.set(a);
- return cubic.xyAtT(t);
+ return cubic.ptAtT(t);
}
static SkDPoint (* const CurveDPointAtT[])(const SkPoint[], double ) = {
@@ -123,7 +123,7 @@ static SkPoint (* const CurveTop[])(const SkPoint[], double , double ) = {
static bool line_is_vertical(const SkPoint a[2], double startT, double endT) {
SkDLine line;
line.set(a);
- SkDPoint dst[2] = { line.xyAtT(startT), line.xyAtT(endT) };
+ SkDPoint dst[2] = { line.ptAtT(startT), line.ptAtT(endT) };
return AlmostEqualUlps(dst[0].fX, dst[1].fX);
}
diff --git a/src/pathops/SkPathOpsDebug.h b/src/pathops/SkPathOpsDebug.h
index 05fe241e0f..e4ef072b9e 100644
--- a/src/pathops/SkPathOpsDebug.h
+++ b/src/pathops/SkPathOpsDebug.h
@@ -64,6 +64,7 @@ extern int gDebugMaxWindValue;
#define DEBUG_SORT_SINGLE 0
#define DEBUG_SWAP_TOP 0
#define DEBUG_UNSORTABLE 0
+#define DEBUG_VALIDATE 0
#define DEBUG_WIND_BUMP 0
#define DEBUG_WINDING 0
#define DEBUG_WINDING_AT_T 0
@@ -93,6 +94,7 @@ extern int gDebugMaxWindValue;
#define DEBUG_SORT_SINGLE 0
#define DEBUG_SWAP_TOP 1
#define DEBUG_UNSORTABLE 1
+#define DEBUG_VALIDATE 1
#define DEBUG_WIND_BUMP 0
#define DEBUG_WINDING 1
#define DEBUG_WINDING_AT_T 1
diff --git a/src/pathops/SkPathOpsLine.cpp b/src/pathops/SkPathOpsLine.cpp
index 47c0565b69..48c042a7fa 100644
--- a/src/pathops/SkPathOpsLine.cpp
+++ b/src/pathops/SkPathOpsLine.cpp
@@ -41,8 +41,13 @@ double SkDLine::isLeft(const SkDPoint& pt) const {
return p0.cross(p2);
}
-// OPTIMIZE: assert if t is 0 or 1 (caller shouldn't pass only 0/1)
-SkDPoint SkDLine::xyAtT(double t) const {
+SkDPoint SkDLine::ptAtT(double t) const {
+ if (0 == t) {
+ return fPts[0];
+ }
+ if (1 == t) {
+ return fPts[1];
+ }
double one_t = 1 - t;
SkDPoint result = { one_t * fPts[0].fX + t * fPts[1].fX, one_t * fPts[0].fY + t * fPts[1].fY };
return result;
@@ -72,7 +77,7 @@ double SkDLine::nearPoint(const SkDPoint& xy) const {
return -1;
}
double t = numer / denom;
- SkDPoint realPt = xyAtT(t);
+ SkDPoint realPt = ptAtT(t);
SkDVector distU = xy - realPt;
double distSq = distU.fX * distU.fX + distU.fY * distU.fY;
double dist = sqrt(distSq); // OPTIMIZATION: can we compare against distSq instead ?
diff --git a/src/pathops/SkPathOpsLine.h b/src/pathops/SkPathOpsLine.h
index c5ac7fdb09..75f3bd1058 100644
--- a/src/pathops/SkPathOpsLine.h
+++ b/src/pathops/SkPathOpsLine.h
@@ -33,8 +33,8 @@ struct SkDLine {
double nearPoint(const SkDPoint& xy) const;
static double NearPointH(const SkDPoint& xy, double left, double right, double y);
static double NearPointV(const SkDPoint& xy, double top, double bottom, double x);
+ SkDPoint ptAtT(double t) const;
SkDLine subDivide(double t1, double t2) const;
- SkDPoint xyAtT(double t) const;
private:
SkDVector tangent() const { return fPts[0] - fPts[1]; }
};
diff --git a/src/pathops/SkPathOpsQuad.cpp b/src/pathops/SkPathOpsQuad.cpp
index 636e3854fd..7d9ff52aa2 100644
--- a/src/pathops/SkPathOpsQuad.cpp
+++ b/src/pathops/SkPathOpsQuad.cpp
@@ -30,7 +30,7 @@ double SkDQuad::nearestT(const SkDPoint& pt) const {
double distMin = SkTMin(d0, d2);
int bestIndex = -1;
for (int index = 0; index < roots; ++index) {
- SkDPoint onQuad = xyAtT(ts[index]);
+ SkDPoint onQuad = ptAtT(ts[index]);
double dist = pt.distanceSquared(onQuad);
if (distMin > dist) {
distMin = dist;
@@ -57,7 +57,7 @@ SkDPoint SkDQuad::top(double startT, double endT) const {
double extremeT;
if (FindExtrema(sub[0].fY, sub[1].fY, sub[2].fY, &extremeT)) {
extremeT = startT + (endT - startT) * extremeT;
- SkDPoint test = xyAtT(extremeT);
+ SkDPoint test = ptAtT(extremeT);
if (topPt.fY > test.fY || (topPt.fY == test.fY && topPt.fX > test.fX)) {
topPt = test;
}
@@ -165,7 +165,13 @@ SkDVector SkDQuad::dxdyAtT(double t) const {
}
// OPTIMIZE: assert if caller passes in t == 0 / t == 1 ?
-SkDPoint SkDQuad::xyAtT(double t) const {
+SkDPoint SkDQuad::ptAtT(double t) const {
+ if (0 == t) {
+ return fPts[0];
+ }
+ if (1 == t) {
+ return fPts[2];
+ }
double one_t = 1 - t;
double a = one_t * one_t;
double b = 2 * one_t * t;
diff --git a/src/pathops/SkPathOpsQuad.h b/src/pathops/SkPathOpsQuad.h
index d06f3449bf..c8650515bb 100644
--- a/src/pathops/SkPathOpsQuad.h
+++ b/src/pathops/SkPathOpsQuad.h
@@ -42,6 +42,7 @@ struct SkDQuad {
bool monotonicInY() const;
double nearestT(const SkDPoint&) const;
bool pointInHull(const SkDPoint&) const;
+ SkDPoint ptAtT(double t) const;
static int RootsReal(double A, double B, double C, double t[2]);
static int RootsValidT(const double A, const double B, const double C, double s[2]);
static void SetABC(const double* quad, double* a, double* b, double* c);
@@ -60,7 +61,6 @@ struct SkDQuad {
}
SkDCubic toCubic() const;
SkDPoint top(double startT, double endT) const;
- SkDPoint xyAtT(double t) const;
private:
// static double Tangent(const double* quadratic, double t); // uncalled
};
diff --git a/src/pathops/SkPathOpsRect.cpp b/src/pathops/SkPathOpsRect.cpp
index 9d7f876cac..2ceed32900 100644
--- a/src/pathops/SkPathOpsRect.cpp
+++ b/src/pathops/SkPathOpsRect.cpp
@@ -26,7 +26,7 @@ void SkDRect::setBounds(const SkDQuad& quad) {
roots += SkDQuad::FindExtrema(quad[0].fY, quad[1].fY, quad[2].fY, &tValues[roots]);
}
for (int x = 0; x < roots; ++x) {
- add(quad.xyAtT(tValues[x]));
+ add(quad.ptAtT(tValues[x]));
}
}
@@ -53,7 +53,7 @@ void SkDRect::setBounds(const SkDCubic& c) {
roots += SkDCubic::FindExtrema(c[0].fY, c[1].fY, c[2].fY, c[3].fY, &tValues[roots]);
}
for (int x = 0; x < roots; ++x) {
- add(c.xyAtT(tValues[x]));
+ add(c.ptAtT(tValues[x]));
}
}
diff --git a/src/pathops/SkPathOpsTypes.cpp b/src/pathops/SkPathOpsTypes.cpp
index a076d155f2..8135c57025 100644
--- a/src/pathops/SkPathOpsTypes.cpp
+++ b/src/pathops/SkPathOpsTypes.cpp
@@ -11,40 +11,40 @@
// from http://randomascii.wordpress.com/2012/02/25/comparing-floating-point-numbers-2012-edition/
// FIXME: move to SkFloatBits.h
-static bool equal_ulps(float A, float B, int epsilon) {
+static bool equal_ulps(float a, float b, int epsilon) {
SkFloatIntUnion floatIntA, floatIntB;
- floatIntA.fFloat = A;
- floatIntB.fFloat = B;
+ floatIntA.fFloat = a;
+ floatIntB.fFloat = b;
// Different signs means they do not match.
if ((floatIntA.fSignBitInt < 0) != (floatIntB.fSignBitInt < 0)) {
// Check for equality to make sure +0 == -0
- return A == B;
+ return a == b;
}
// Find the difference in ULPs.
int ulpsDiff = abs(floatIntA.fSignBitInt - floatIntB.fSignBitInt);
return ulpsDiff <= epsilon;
}
-static bool less_ulps(float A, float B, int epsilon) {
+static bool less_ulps(float a, float b, int epsilon) {
SkFloatIntUnion floatIntA, floatIntB;
- floatIntA.fFloat = A;
- floatIntB.fFloat = B;
+ floatIntA.fFloat = a;
+ floatIntB.fFloat = b;
// Check different signs with float epsilon since we only care if they're both close to 0.
if ((floatIntA.fSignBitInt < 0) != (floatIntB.fSignBitInt < 0)) {
- return A <= B + FLT_EPSILON * epsilon;
+ return a <= b + FLT_EPSILON * epsilon;
}
// Find the difference in ULPs.
return floatIntA.fSignBitInt <= floatIntB.fSignBitInt + epsilon;
}
-bool AlmostEqualUlps(float A, float B) {
+bool AlmostEqualUlps(float a, float b) {
const int UlpsEpsilon = 16;
- return equal_ulps(A, B, UlpsEpsilon);
+ return equal_ulps(a, b, UlpsEpsilon);
}
-bool RoughlyEqualUlps(float A, float B) {
+bool RoughlyEqualUlps(float a, float b) {
const int UlpsEpsilon = 256;
- return equal_ulps(A, B, UlpsEpsilon);
+ return equal_ulps(a, b, UlpsEpsilon);
}
bool AlmostBetweenUlps(float a, float b, float c) {
@@ -53,6 +53,19 @@ bool AlmostBetweenUlps(float a, float b, float c) {
: less_ulps(b, a, UlpsEpsilon) && less_ulps(c, b, UlpsEpsilon);
}
+int UlpsDistance(float a, float b) {
+ SkFloatIntUnion floatIntA, floatIntB;
+ floatIntA.fFloat = a;
+ floatIntB.fFloat = b;
+ // Different signs means they do not match.
+ if ((floatIntA.fSignBitInt < 0) != (floatIntB.fSignBitInt < 0)) {
+ // Check for equality to make sure +0 == -0
+ return a == b ? 0 : SK_MaxS32;
+ }
+ // Find the difference in ULPs.
+ return abs(floatIntA.fSignBitInt - floatIntB.fSignBitInt);
+}
+
// cube root approximation using bit hack for 64-bit float
// adapted from Kahan's cbrt
static double cbrt_5d(double d) {
diff --git a/src/pathops/SkPathOpsTypes.h b/src/pathops/SkPathOpsTypes.h
index c988691e26..6158f13576 100644
--- a/src/pathops/SkPathOpsTypes.h
+++ b/src/pathops/SkPathOpsTypes.h
@@ -23,19 +23,24 @@ enum SkPathOpsMask {
};
// Use Almost Equal when comparing coordinates. Use epsilon to compare T values.
-bool AlmostEqualUlps(float A, float B);
-inline bool AlmostEqualUlps(double A, double B) {
- return AlmostEqualUlps(SkDoubleToScalar(A), SkDoubleToScalar(B));
+bool AlmostEqualUlps(float a, float b);
+inline bool AlmostEqualUlps(double a, double b) {
+ return AlmostEqualUlps(SkDoubleToScalar(a), SkDoubleToScalar(b));
}
-bool RoughlyEqualUlps(float A, float B);
-inline bool RoughlyEqualUlps(double A, double B) {
- return RoughlyEqualUlps(SkDoubleToScalar(A), SkDoubleToScalar(B));
+bool RoughlyEqualUlps(float a, float b);
+inline bool RoughlyEqualUlps(double a, double b) {
+ return RoughlyEqualUlps(SkDoubleToScalar(a), SkDoubleToScalar(b));
}
bool AlmostBetweenUlps(float a, float b, float c);
-inline bool AlmostBetweenUlps(double A, double B, double C) {
- return AlmostBetweenUlps(SkDoubleToScalar(A), SkDoubleToScalar(B), SkDoubleToScalar(C));
+inline bool AlmostBetweenUlps(double a, double b, double c) {
+ return AlmostBetweenUlps(SkDoubleToScalar(a), SkDoubleToScalar(b), SkDoubleToScalar(c));
+}
+
+int UlpsDistance(float a, float b);
+inline int UlpsDistance(double a, double b) {
+ return UlpsDistance(SkDoubleToScalar(a), SkDoubleToScalar(b));
}
// FLT_EPSILON == 1.19209290E-07 == 1 / (2 ^ 23)
generated by cgit v1.2.3 (git 2.39.1) at 2024-11-23 23:46:17 +0000