path ops work in progress
make more skps work
remove edit files
BUG=
Review URL: https://codereview.chromium.org/23542056
git-svn-id: http://skia.googlecode.com/svn/trunk@11570 2bbb7eff-a529-9590-31e7-b0007b416f81
diff --git a/src/pathops/SkAddIntersections.cpp b/src/pathops/SkAddIntersections.cpp
index 0507984..5fa80ec 100644
--- a/src/pathops/SkAddIntersections.cpp
+++ b/src/pathops/SkAddIntersections.cpp
@@ -363,15 +363,20 @@
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 @@
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 63d434f..ce23448 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 @@
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 @@
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 @@
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 @@
}
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 @@
}
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 @@
}
// 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;
- }
- }
- 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:
+ // 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 (!(exactEndBits & 8)) {
+ cubicNearEnd(c2, true, c1, c1Bounds);
+ }
+ swap();
+ }
+ if (cubicCheckCoincidence(c1, c2)) {
+ SkASSERT(!selfIntersect);
+ return fUsed;
+ }
::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 @@
}
}
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 @@
// 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 @@
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 0abb75b..e9997e4 100644
--- a/src/pathops/SkDCubicLineIntersection.cpp
+++ b/src/pathops/SkDCubicLineIntersection.cpp
@@ -86,6 +86,7 @@
, fLine(l)
, fIntersections(i)
, fAllowNear(true) {
+ i->setMax(3);
}
void allowNear(bool allow) {
@@ -122,7 +123,24 @@
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 4b818dc..fca0a04 100644
--- a/src/pathops/SkDLineIntersection.cpp
+++ b/src/pathops/SkDLineIntersection.cpp
@@ -26,15 +26,44 @@
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 @@
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 @@
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 @@
}
}
}
- 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 @@
}
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 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 @@
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 @@
}
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 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 @@
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 84ad452..f0f66d1 100644
--- a/src/pathops/SkDQuadImplicit.cpp
+++ b/src/pathops/SkDQuadImplicit.cpp
@@ -103,7 +103,7 @@
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 5869d7d..71ebf9a 100644
--- a/src/pathops/SkDQuadIntersection.cpp
+++ b/src/pathops/SkDQuadIntersection.cpp
@@ -139,7 +139,7 @@
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 @@
}
// 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 @@
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 @@
}
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 @@
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 @@
return fUsed;
}
SkIntersections swapped;
+ swapped.setMax(fMax);
if (is_linear(q2, q1, &swapped)) {
swapped.swapPts();
set(swapped);
@@ -484,7 +491,7 @@
}
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 @@
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 @@
}
}
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 b335c5a..14d7d9c 100644
--- a/src/pathops/SkDQuadLineIntersection.cpp
+++ b/src/pathops/SkDQuadLineIntersection.cpp
@@ -99,6 +99,7 @@
, 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 af246b7..1a4b1f0 100644
--- a/src/pathops/SkIntersectionHelper.h
+++ b/src/pathops/SkIntersectionHelper.h
@@ -17,8 +17,8 @@
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 @@
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 @@
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 3a5e24f..608ffe3 100644
--- a/src/pathops/SkIntersections.cpp
+++ b/src/pathops/SkIntersections.cpp
@@ -45,6 +45,7 @@
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 @@
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 @@
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 389098d..f63a023 100644
--- a/src/pathops/SkIntersections.h
+++ b/src/pathops/SkIntersections.h
@@ -25,6 +25,7 @@
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 @@
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 @@
int cubic(const SkPoint a[4]) {
SkDCubic cubic;
cubic.set(a);
+ fMax = 1; // self intersect
return intersect(cubic);
}
@@ -62,6 +65,7 @@
aCubic.set(a);
SkDCubic bCubic;
bCubic.set(b);
+ fMax = 9;
return intersect(aCubic, bCubic);
}
@@ -69,12 +73,14 @@
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 @@
cubic.set(a);
SkDLine line;
line.set(b);
+ fMax = 3;
return intersect(cubic, line);
}
@@ -91,6 +98,7 @@
cubic.set(a);
SkDQuad quad;
quad.set(b);
+ fMax = 6;
return intersect(cubic, quad);
}
@@ -119,12 +127,14 @@
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 @@
SkDLine aLine, bLine;
aLine.set(a);
bLine.set(b);
+ fMax = 2;
return intersect(aLine, bLine);
}
@@ -143,12 +154,14 @@
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 @@
quad.set(a);
SkDLine line;
line.set(b);
+ fMax = 2;
return intersect(quad, line);
}
@@ -165,18 +179,23 @@
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 @@
}
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 @@
}
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 @@
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 c1e2eae..5e1d9e7 100644
--- a/src/pathops/SkOpAngle.cpp
+++ b/src/pathops/SkOpAngle.cpp
@@ -131,6 +131,9 @@
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 @@
}
}
}
- 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 @@
#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 facba87..4aa12cd 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 @@
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 @@
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 @@
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 @@
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 @@
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 @@
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 a5635fe..a4ec6d3 100644
--- a/src/pathops/SkOpContour.h
+++ b/src/pathops/SkOpContour.h
@@ -36,7 +36,7 @@
: 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 @@
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 @@
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 c0ef1f8..4d11eb3 100644
--- a/src/pathops/SkOpSegment.cpp
+++ b/src/pathops/SkOpSegment.cpp
@@ -417,6 +417,8 @@
// 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 @@
// 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 @@
}
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 @@
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 @@
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 @@
}
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 @@
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 @@
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 @@
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 @@
// 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 @@
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 @@
}
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::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 @@
}
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 @@
#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;
+ {
+ 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:
+ ;
}
-nextPeeker:
- ;
}
if (missingSpans.count() == 0) {
+ debugValidate();
return;
}
// if one end is near the other point, look for a coincident span
@@ -1690,6 +1748,11 @@
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) 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 @@
}
#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 @@
}
#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 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 @@
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 @@
#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 acb114d..85531f5 100644
--- a/src/pathops/SkOpSegment.h
+++ b/src/pathops/SkOpSegment.h
@@ -248,7 +248,8 @@
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 @@
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 @@
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 7dd13a7..4db6079 100644
--- a/src/pathops/SkPathOpsCommon.cpp
+++ b/src/pathops/SkPathOpsCommon.cpp
@@ -399,10 +399,6 @@
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 @@
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 @@
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 662219a..8e8ec47 100644
--- a/src/pathops/SkPathOpsCubic.cpp
+++ b/src/pathops/SkPathOpsCubic.cpp
@@ -155,7 +155,7 @@
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 @@
*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 @@
}
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 0505965..e52e47b 100644
--- a/src/pathops/SkPathOpsDebug.cpp
+++ b/src/pathops/SkPathOpsDebug.cpp
@@ -89,6 +89,13 @@
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 @@
}
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 912f2f5..4fabd4c 100644
--- a/src/pathops/SkPathOpsDebug.h
+++ b/src/pathops/SkPathOpsDebug.h
@@ -160,8 +160,15 @@
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 1b548fc..1e74123 100644
--- a/src/pathops/SkPathOpsLine.cpp
+++ b/src/pathops/SkPathOpsLine.cpp
@@ -152,8 +152,6 @@
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 @@
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 e532fda..71ebef0 100644
--- a/src/pathops/SkPathOpsOp.cpp
+++ b/src/pathops/SkPathOpsOp.cpp
@@ -165,8 +165,8 @@
#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 51216b6..40688d8 100644
--- a/src/pathops/SkPathOpsPoint.h
+++ b/src/pathops/SkPathOpsPoint.h
@@ -100,30 +100,40 @@
// 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 @@
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 1bd7796..63e2038 100644
--- a/src/pathops/SkPathOpsQuad.cpp
+++ b/src/pathops/SkPathOpsQuad.cpp
@@ -122,7 +122,7 @@
}
/* 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 @@
}
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 2d7388b..df73d11 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 @@
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 @@
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 @@
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 @@
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 @@
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 bc39675..0ad10c2 100644
--- a/src/pathops/SkPathOpsTypes.h
+++ b/src/pathops/SkPathOpsTypes.h
@@ -28,11 +28,22 @@
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 5559026..46ec7b9 100644
--- a/src/pathops/SkPathWriter.cpp
+++ b/src/pathops/SkPathWriter.cpp
@@ -90,7 +90,7 @@
}
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 d3a6a78..dca96de 100644
--- a/src/pathops/SkQuarticRoot.cpp
+++ b/src/pathops/SkQuarticRoot.cpp
@@ -152,7 +152,7 @@
// 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];
}