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