pathops work in progress
BUG=
Review URL: https://codereview.chromium.org/52653002
git-svn-id: http://skia.googlecode.com/svn/trunk@12089 2bbb7eff-a529-9590-31e7-b0007b416f81
diff --git a/src/pathops/SkAddIntersections.cpp b/src/pathops/SkAddIntersections.cpp
index 5fa80ec..7d5fc0d 100644
--- a/src/pathops/SkAddIntersections.cpp
+++ b/src/pathops/SkAddIntersections.cpp
@@ -383,8 +383,8 @@
for (int pt = 0; pt < pts - 1; ++pt) {
const SkDPoint& point = ts.pt(pt);
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)) {
+ if (wt.isPartial(ts[swap][pt], ts[swap][pt + 1], point, next)
+ && wn.isPartial(ts[!swap][pt], ts[!swap][pt + 1], point, next)) {
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)
diff --git a/src/pathops/SkDCubicIntersection.cpp b/src/pathops/SkDCubicIntersection.cpp
index ce23448..27b1634 100644
--- a/src/pathops/SkDCubicIntersection.cpp
+++ b/src/pathops/SkDCubicIntersection.cpp
@@ -292,6 +292,7 @@
tmpLine[1].fX += cubic2[2 - start].fY - cubic2[t1Index].fY;
tmpLine[1].fY -= cubic2[2 - start].fX - cubic2[t1Index].fX;
SkIntersections impTs;
+ impTs.allowNear(false);
impTs.intersectRay(cubic1, tmpLine);
for (int index = 0; index < impTs.used(); ++index) {
SkDPoint realPt = impTs.pt(index);
@@ -446,6 +447,7 @@
return fUsed;
}
} else {
+ // OPTIMIZATION: set exact end bits here to avoid cubic exact end later
for (int i1 = 0; i1 < 4; i1 += 3) {
for (int i2 = 0; i2 < 4; i2 += 3) {
if (c1[i1].approximatelyEqual(c2[i2])) {
@@ -483,21 +485,22 @@
return fUsed;
}
// FIXME: pass in cached bounds from caller
- SkDRect c1Bounds, c2Bounds;
- c1Bounds.setBounds(c1); // OPTIMIZE use setRawBounds ?
+ SkDRect c2Bounds;
c2Bounds.setBounds(c2);
- if (!(exactEndBits & 1)) {
+ if (!(exactEndBits & 4)) {
cubicNearEnd(c1, false, c2, c2Bounds);
}
- if (!(exactEndBits & 2)) {
+ if (!(exactEndBits & 8)) {
cubicNearEnd(c1, true, c2, c2Bounds);
}
if (!selfIntersect) {
+ SkDRect c1Bounds;
+ c1Bounds.setBounds(c1); // OPTIMIZE use setRawBounds ?
swap();
- if (!(exactEndBits & 4)) {
+ if (!(exactEndBits & 1)) {
cubicNearEnd(c2, false, c1, c1Bounds);
}
- if (!(exactEndBits & 8)) {
+ if (!(exactEndBits & 2)) {
cubicNearEnd(c2, true, c1, c1Bounds);
}
swap();
@@ -506,7 +509,61 @@
SkASSERT(!selfIntersect);
return fUsed;
}
- ::intersect(c1, 0, 1, c2, 0, 1, 1, *this);
+ SkIntersections i;
+ i.fAllowNear = false;
+ i.fMax = 9;
+ ::intersect(c1, 0, 1, c2, 0, 1, 1, i);
+ int compCount = i.used();
+ if (compCount) {
+ int exactCount = used();
+ if (exactCount == 0) {
+ set(i);
+ } else {
+ // at least one is exact or near, and at least one was computed. Eliminate duplicates
+ for (int exIdx = 0; exIdx < exactCount; ++exIdx) {
+ for (int cpIdx = 0; cpIdx < compCount; ) {
+ if (fT[0][0] == i[0][0] && fT[1][0] == i[1][0]) {
+ i.removeOne(cpIdx);
+ --compCount;
+ continue;
+ }
+ double tAvg = (fT[0][exIdx] + i[0][cpIdx]) / 2;
+ SkDPoint pt = c1.ptAtT(tAvg);
+ if (!pt.approximatelyEqual(fPt[exIdx])) {
+ ++cpIdx;
+ continue;
+ }
+ tAvg = (fT[1][exIdx] + i[1][cpIdx]) / 2;
+ pt = c2.ptAtT(tAvg);
+ if (!pt.approximatelyEqual(fPt[exIdx])) {
+ ++cpIdx;
+ continue;
+ }
+ i.removeOne(cpIdx);
+ --compCount;
+ }
+ }
+ // if mid t evaluates to nearly the same point, skip the t
+ for (int cpIdx = 0; cpIdx < compCount - 1; ) {
+ double tAvg = (fT[0][cpIdx] + i[0][cpIdx + 1]) / 2;
+ SkDPoint pt = c1.ptAtT(tAvg);
+ if (!pt.approximatelyEqual(fPt[cpIdx])) {
+ ++cpIdx;
+ continue;
+ }
+ tAvg = (fT[1][cpIdx] + i[1][cpIdx + 1]) / 2;
+ pt = c2.ptAtT(tAvg);
+ if (!pt.approximatelyEqual(fPt[cpIdx])) {
+ ++cpIdx;
+ continue;
+ }
+ i.removeOne(cpIdx);
+ --compCount;
+ }
+ // in addition to adding below missing function, think about how to say
+ append(i);
+ }
+ }
// If an end point and a second point very close to the end is returned, the second
// point may have been detected because the approximate quads
// intersected at the end and close to it. Verify that the second point is valid.
diff --git a/src/pathops/SkDCubicLineIntersection.cpp b/src/pathops/SkDCubicLineIntersection.cpp
index e9997e4..abbc4e3 100644
--- a/src/pathops/SkDCubicLineIntersection.cpp
+++ b/src/pathops/SkDCubicLineIntersection.cpp
@@ -215,6 +215,8 @@
}
}
+ /* Note that this does not look for endpoints of the line that are near the cubic.
+ These points are found later when check ends looks for missing points */
void addNearEndPoints() {
for (int cIndex = 0; cIndex < 4; cIndex += 3) {
double cubicT = (double) (cIndex >> 1);
diff --git a/src/pathops/SkDLineIntersection.cpp b/src/pathops/SkDLineIntersection.cpp
index fca0a04..33c8480 100644
--- a/src/pathops/SkDLineIntersection.cpp
+++ b/src/pathops/SkDLineIntersection.cpp
@@ -181,7 +181,7 @@
}
static double horizontal_intercept(const SkDLine& line, double y) {
- return (y - line[0].fY) / (line[1].fY - line[0].fY);
+ return SkPinT((y - line[0].fY) / (line[1].fY - line[0].fY));
}
int SkIntersections::horizontal(const SkDLine& line, double y) {
@@ -267,7 +267,7 @@
}
static double vertical_intercept(const SkDLine& line, double x) {
- return (x - line[0].fX) / (line[1].fX - line[0].fX);
+ return SkPinT((x - line[0].fX) / (line[1].fX - line[0].fX));
}
int SkIntersections::vertical(const SkDLine& line, double x) {
diff --git a/src/pathops/SkDQuadIntersection.cpp b/src/pathops/SkDQuadIntersection.cpp
index 6e5f3e6..4872508 100644
--- a/src/pathops/SkDQuadIntersection.cpp
+++ b/src/pathops/SkDQuadIntersection.cpp
@@ -301,7 +301,7 @@
*pt = t1[1];
#if ONE_OFF_DEBUG
SkDebugf("%s t1=%1.9g t2=%1.9g (%1.9g,%1.9g) == (%1.9g,%1.9g)\n", __FUNCTION__,
- t1Seed, t2Seed, t1[1].fX, t1[1].fY, t1[2].fX, t1[2].fY);
+ t1Seed, t2Seed, t1[1].fX, t1[1].fY, t2[1].fX, t2[1].fY);
#endif
return true;
}
@@ -490,15 +490,11 @@
pts2[index] = q2.ptAtT(roots2Copy[index]);
}
if (r1Count == r2Count && r1Count <= 1) {
- if (r1Count == 1) {
+ if (r1Count == 1 && used() == 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
- rootCount = findRoots(i2, q1, roots1, useCubic, flip1, 0);
- (void) addValidRoots(roots1, rootCount, roots1Copy);
- rootCount2 = findRoots(i1, q2, roots2, useCubic, flip2, 0);
- (void) addValidRoots(roots2, rootCount2, roots2Copy);
if (binary_search(q1, q2, roots1Copy, roots2Copy, pts1)) {
insert(roots1Copy[0], roots2Copy[0], pts1[0]);
}
diff --git a/src/pathops/SkDQuadLineIntersection.cpp b/src/pathops/SkDQuadLineIntersection.cpp
index 14d7d9c..8fce7a0 100644
--- a/src/pathops/SkDQuadLineIntersection.cpp
+++ b/src/pathops/SkDQuadLineIntersection.cpp
@@ -141,14 +141,18 @@
if (fAllowNear) {
addNearEndPoints();
}
- double rootVals[2];
- int roots = intersectRay(rootVals);
- for (int index = 0; index < roots; ++index) {
- double quadT = rootVals[index];
- double lineT = findLineT(quadT);
- SkDPoint pt;
- if (pinTs(&quadT, &lineT, &pt, kPointUninitialized)) {
- fIntersections->insert(quadT, lineT, pt);
+ if (fIntersections->used() == 2) {
+ // FIXME : need sharable code that turns spans into coincident if middle point is on
+ } else {
+ double rootVals[2];
+ int roots = intersectRay(rootVals);
+ for (int index = 0; index < roots; ++index) {
+ double quadT = rootVals[index];
+ double lineT = findLineT(quadT);
+ SkDPoint pt;
+ if (pinTs(&quadT, &lineT, &pt, kPointUninitialized)) {
+ fIntersections->insert(quadT, lineT, pt);
+ }
}
}
return fIntersections->used();
diff --git a/src/pathops/SkIntersectionHelper.h b/src/pathops/SkIntersectionHelper.h
index 1a4b1f0..f5eeaf8 100644
--- a/src/pathops/SkIntersectionHelper.h
+++ b/src/pathops/SkIntersectionHelper.h
@@ -7,6 +7,10 @@
#include "SkOpContour.h"
#include "SkPath.h"
+#if SK_DEBUG
+#include "SkPathOpsPoint.h"
+#endif
+
class SkIntersectionHelper {
public:
enum SegmentType {
@@ -81,6 +85,14 @@
return midPtByT.approximatelyEqual(midPtByAvg);
}
+ bool isPartial(double t1, double t2, const SkDPoint& pt1, const SkDPoint& pt2) const {
+ const SkOpSegment& segment = fContour->segments()[fIndex];
+ double mid = (t1 + t2) / 2;
+ SkDPoint midPtByT = segment.dPtAtT(mid);
+ SkDPoint midPtByAvg = SkDPoint::Mid(pt1, pt2);
+ return midPtByT.approximatelyPEqual(midPtByAvg);
+ }
+
SkScalar left() const {
return bounds().fLeft;
}
@@ -137,6 +149,19 @@
return y() != pts()[0].fY;
}
+#ifdef SK_DEBUG
+ void dump() {
+ SkDPoint::dump(pts()[0]);
+ SkDPoint::dump(pts()[1]);
+ if (verb() >= SkPath::kQuad_Verb) {
+ SkDPoint::dump(pts()[2]);
+ }
+ if (verb() >= SkPath::kCubic_Verb) {
+ SkDPoint::dump(pts()[3]);
+ }
+ }
+#endif
+
private:
SkOpContour* fContour;
int fIndex;
diff --git a/src/pathops/SkIntersections.cpp b/src/pathops/SkIntersections.cpp
index 608ffe3..35846f6 100644
--- a/src/pathops/SkIntersections.cpp
+++ b/src/pathops/SkIntersections.cpp
@@ -7,6 +7,12 @@
#include "SkIntersections.h"
+void SkIntersections::append(const SkIntersections& i) {
+ for (int index = 0; index < i.fUsed; ++index) {
+ insert(i[0][index], i[1][index], i.pt(index));
+ }
+}
+
int (SkIntersections::*CurveVertical[])(const SkPoint[], SkScalar, SkScalar, SkScalar, bool) = {
NULL,
&SkIntersections::verticalLine,
@@ -16,7 +22,7 @@
int (SkIntersections::*CurveRay[])(const SkPoint[], const SkDLine&) = {
NULL,
- NULL,
+ &SkIntersections::lineRay,
&SkIntersections::quadRay,
&SkIntersections::cubicRay
};
@@ -126,6 +132,13 @@
fIsCoincident[1] |= bit;
}
+int SkIntersections::lineRay(const SkPoint pts[2], const SkDLine& line) {
+ SkDLine l;
+ l.set(pts);
+ fMax = 2;
+ return intersectRay(l, line);
+}
+
void SkIntersections::offset(int base, double start, double end) {
for (int index = base; index < fUsed; ++index) {
double val = fT[fSwap][index];
diff --git a/src/pathops/SkIntersections.h b/src/pathops/SkIntersections.h
index f63a023..a3e8332 100644
--- a/src/pathops/SkIntersections.h
+++ b/src/pathops/SkIntersections.h
@@ -183,9 +183,6 @@
return intersect(aQuad, bQuad);
}
- int quadRay(const SkPoint pts[3], const SkDLine& line);
- void removeOne(int index);
-
// leaves flip, swap, max alone
void reset() {
fAllowNear = true;
@@ -218,6 +215,7 @@
SkASSERT(++fDepth < 16);
}
+ void append(const SkIntersections& );
static double Axial(const SkDQuad& , const SkDPoint& , bool vertical);
void cleanUpCoincidence();
int coincidentUsed() const;
@@ -246,8 +244,11 @@
int intersectRay(const SkDQuad&, const SkDLine&);
int intersectRay(const SkDCubic&, const SkDLine&);
static SkDPoint Line(const SkDLine&, const SkDLine&);
+ int lineRay(const SkPoint pts[2], const SkDLine& line);
void offset(int base, double start, double end);
void quickRemoveOne(int index, int replace);
+ int quadRay(const SkPoint pts[3], const SkDLine& line);
+ void removeOne(int index);
static bool Test(const SkDLine& , const SkDLine&);
int vertical(const SkDLine&, double x);
int vertical(const SkDLine&, double top, double bottom, double x, bool flipped);
diff --git a/src/pathops/SkOpAngle.cpp b/src/pathops/SkOpAngle.cpp
index 5e1d9e7..4144add 100644
--- a/src/pathops/SkOpAngle.cpp
+++ b/src/pathops/SkOpAngle.cpp
@@ -207,7 +207,10 @@
return COMPARE_RESULT("roots == 0 || rroots == 0", this < &rh);
}
SkASSERT(fSide != 0 && rh.fSide != 0);
- SkASSERT(fSide * rh.fSide > 0); // both are the same sign
+ if (fSide * rh.fSide < 0) {
+ fUnsortable = true;
+ return COMPARE_RESULT("14 fSide * rh.fSide < 0", this < &rh);
+ }
SkDPoint lLoc;
double best = SK_ScalarInfinity;
#if DEBUG_SORT
@@ -246,7 +249,7 @@
if (flip) {
leftLessThanRight = !leftLessThanRight;
}
- return COMPARE_RESULT("14 leftLessThanRight", leftLessThanRight);
+ return COMPARE_RESULT("15 leftLessThanRight", leftLessThanRight);
}
bool SkOpAngle::isHorizontal() const {
diff --git a/src/pathops/SkOpContour.cpp b/src/pathops/SkOpContour.cpp
index 4aa12cd..5feef79 100644
--- a/src/pathops/SkOpContour.cpp
+++ b/src/pathops/SkOpContour.cpp
@@ -174,6 +174,63 @@
}
}
+void SkOpContour::joinCoincidence(const SkTArray<SkCoincidence, true>& coincidences, bool partial) {
+ int count = coincidences.count();
+#if DEBUG_CONCIDENT
+ if (count > 0) {
+ SkDebugf("%s count=%d\n", __FUNCTION__, count);
+ }
+#endif
+ // look for a lineup where the partial implies another adjoining coincidence
+ for (int index = 0; index < count; ++index) {
+ const SkCoincidence& coincidence = coincidences[index];
+ int thisIndex = coincidence.fSegments[0];
+ SkOpSegment& thisOne = fSegments[thisIndex];
+ SkOpContour* otherContour = coincidence.fOther;
+ int otherIndex = coincidence.fSegments[1];
+ SkOpSegment& other = otherContour->fSegments[otherIndex];
+ double startT = coincidence.fTs[0][0];
+ double endT = coincidence.fTs[0][1];
+ if (startT == endT) { // this can happen in very large compares
+ continue;
+ }
+ double oStartT = coincidence.fTs[1][0];
+ double oEndT = coincidence.fTs[1][1];
+ if (oStartT == oEndT) {
+ continue;
+ }
+ bool swapStart = startT > endT;
+ bool swapOther = oStartT > oEndT;
+ if (swapStart) {
+ SkTSwap<double>(startT, endT);
+ SkTSwap<double>(oStartT, oEndT);
+ }
+ bool cancel = swapOther != swapStart;
+ int step = swapStart ? -1 : 1;
+ int oStep = swapOther ? -1 : 1;
+ double oMatchStart = cancel ? oEndT : oStartT;
+ if (partial ? startT != 0 || oMatchStart != 0 : (startT == 0) != (oMatchStart == 0)) {
+ bool added = false;
+ if (oMatchStart != 0) {
+ added = thisOne.joinCoincidence(false, &other, oMatchStart, oStep, cancel);
+ }
+ if (startT != 0 && !added) {
+ (void) other.joinCoincidence(cancel, &thisOne, startT, step, cancel);
+ }
+ }
+ double oMatchEnd = cancel ? oStartT : oEndT;
+ if (partial ? endT != 1 || oMatchEnd != 1 : (endT == 1) != (oMatchEnd == 1)) {
+ bool added = false;
+ if (oMatchEnd != 1) {
+ added = thisOne.joinCoincidence(true, &other, oMatchEnd, -oStep, cancel);
+ }
+ if (endT != 1 && !added) {
+ (void) other.joinCoincidence(!cancel, &thisOne, endT, -step, cancel);
+ }
+ }
+ }
+}
+
void SkOpContour::calcCommonCoincidentWinding(const SkCoincidence& coincidence) {
int thisIndex = coincidence.fSegments[0];
SkOpSegment& thisOne = fSegments[thisIndex];
diff --git a/src/pathops/SkOpContour.h b/src/pathops/SkOpContour.h
index a4ec6d3..6b412e5 100644
--- a/src/pathops/SkOpContour.h
+++ b/src/pathops/SkOpContour.h
@@ -152,6 +152,11 @@
}
}
+ void joinCoincidence() {
+ joinCoincidence(fCoincidences, false);
+ joinCoincidence(fPartialCoincidences, true);
+ }
+
SkOpSegment* nonVerticalSegment(int* start, int* end);
bool operand() const {
@@ -239,7 +244,8 @@
#endif
private:
- void calcCommonCoincidentWinding(const SkCoincidence& coincidence);
+ void calcCommonCoincidentWinding(const SkCoincidence& );
+ void joinCoincidence(const SkTArray<SkCoincidence, true>& , bool partial);
void setBounds();
SkTArray<SkOpSegment> fSegments;
diff --git a/src/pathops/SkOpEdgeBuilder.cpp b/src/pathops/SkOpEdgeBuilder.cpp
index 676c34f..ae72e29 100644
--- a/src/pathops/SkOpEdgeBuilder.cpp
+++ b/src/pathops/SkOpEdgeBuilder.cpp
@@ -42,16 +42,11 @@
}
void SkOpEdgeBuilder::closeContour(const SkPoint& curveEnd, const SkPoint& curveStart) {
- if ((!AlmostEqualUlps(curveEnd.fX, curveStart.fX)
- || !AlmostEqualUlps(curveEnd.fY, curveStart.fY))) {
+ if (!SkDPoint::ApproximatelyEqual(curveEnd, curveStart)) {
fPathVerbs.push_back(SkPath::kLine_Verb);
fPathPts.push_back_n(1, &curveStart);
} else {
- if (curveEnd.fX != curveStart.fX || curveEnd.fY != curveStart.fY) {
- fPathPts[fPathPts.count() - 1] = curveStart;
- } else {
- fPathPts[fPathPts.count() - 1] = curveStart;
- }
+ fPathPts[fPathPts.count() - 1] = curveStart;
}
fPathVerbs.push_back(SkPath::kClose_Verb);
}
@@ -82,9 +77,9 @@
lastCurve = false;
continue;
case SkPath::kLine_Verb:
- if (AlmostEqualUlps(curve[0].fX, pts[1].fX)
- && AlmostEqualUlps(curve[0].fY, pts[1].fY)) {
- if (fPathVerbs.back() != SkPath::kLine_Verb) {
+ if (SkDPoint::ApproximatelyEqual(curve[0], pts[1])) {
+ uint8_t lastVerb = fPathVerbs.back();
+ if (lastVerb != SkPath::kLine_Verb && lastVerb != SkPath::kMove_Verb) {
fPathPts.back() = pts[1];
}
continue; // skip degenerate points
diff --git a/src/pathops/SkOpSegment.cpp b/src/pathops/SkOpSegment.cpp
index 4d11eb3..6fe1fbb 100644
--- a/src/pathops/SkOpSegment.cpp
+++ b/src/pathops/SkOpSegment.cpp
@@ -1298,6 +1298,7 @@
SkIntersections intersections;
// OPTIMIZE: use specialty function that intersects ray with curve,
// returning t values only for curve (we don't care about t on ray)
+ intersections.allowNear(false);
int pts = (intersections.*CurveVertical[SkPathOpsVerbToPoints(fVerb)])
(fPts, top, bottom, basePt.fX, false);
if (pts == 0 || (current && pts == 1)) {
@@ -1420,15 +1421,29 @@
}
// t start/last describe the range of spans that match the t of this span
double t = span.fT;
- int tStart = index;
- while (--tStart >= 0 && (t == fTs[tStart].fT || fTs[tStart].fTiny))
- ;
- int tLast = index;
- while (fTs[tLast].fTiny) {
- ++tLast;
+ double tBottom = -1;
+ int tStart = -1;
+ int tLast = count;
+ bool lastSmall = false;
+ double afterT = t;
+ for (int inner = 0; inner < count; ++inner) {
+ double innerT = fTs[inner].fT;
+ if (innerT <= t && innerT > tBottom) {
+ if (innerT < t || !lastSmall) {
+ tStart = inner - 1;
+ }
+ tBottom = innerT;
+ }
+ if (innerT > afterT) {
+ if (t == afterT && lastSmall) {
+ afterT = innerT;
+ } else {
+ tLast = inner;
+ break;
+ }
+ }
+ lastSmall = innerT <= t ? fTs[inner].fSmall : false;
}
- while (++tLast < count && t == fTs[tLast].fT)
- ;
for (int peekIndex = peekStart; peekIndex <= peekLast; ++peekIndex) {
if (peekIndex == span.fOtherIndex) { // skip the other span pointed to by this span
continue;
@@ -1696,6 +1711,70 @@
}
}
+bool SkOpSegment::findCoincidentMatch(const SkOpSpan* span, const SkOpSegment* other, int oStart,
+ int oEnd, int step, SkPoint* startPt, SkPoint* endPt, double* endT) const {
+ SkASSERT(span->fT == 0 || span->fT == 1);
+ SkASSERT(span->fOtherT == 0 || span->fOtherT == 1);
+ const SkOpSpan* otherSpan = &other->span(oEnd);
+ double refT = otherSpan->fT;
+ const SkPoint& refPt = otherSpan->fPt;
+ const SkOpSpan* lastSpan = &other->span(step > 0 ? other->count() - 1 : 0);
+ do {
+ const SkOpSegment* match = span->fOther;
+ if (match == otherSpan->fOther) {
+ // find start of respective spans and see if both have winding
+ int startIndex, endIndex;
+ if (span->fOtherT == 1) {
+ endIndex = span->fOtherIndex;
+ startIndex = match->nextExactSpan(endIndex, -1);
+ } else {
+ startIndex = span->fOtherIndex;
+ endIndex = match->nextExactSpan(startIndex, 1);
+ }
+ const SkOpSpan& startSpan = match->span(startIndex);
+ if (startSpan.fWindValue != 0) {
+ // draw ray from endSpan.fPt perpendicular to end tangent and measure distance
+ // to other segment.
+ const SkOpSpan& endSpan = match->span(endIndex);
+ SkDLine ray;
+ SkVector dxdy;
+ if (span->fOtherT == 1) {
+ ray.fPts[0].set(startSpan.fPt);
+ dxdy = match->dxdy(startIndex);
+ } else {
+ ray.fPts[0].set(endSpan.fPt);
+ dxdy = match->dxdy(endIndex);
+ }
+ ray.fPts[1].fX = ray.fPts[0].fX + dxdy.fY;
+ ray.fPts[1].fY = ray.fPts[0].fY - dxdy.fX;
+ SkIntersections i;
+ int roots = (i.*CurveRay[SkPathOpsVerbToPoints(other->verb())])(other->pts(), ray);
+ for (int index = 0; index < roots; ++index) {
+ if (ray.fPts[0].approximatelyEqual(i.pt(index))) {
+ double matchMidT = (match->span(startIndex).fT
+ + match->span(endIndex).fT) / 2;
+ SkPoint matchMidPt = match->ptAtT(matchMidT);
+ double otherMidT = (i[0][index] + other->span(oStart).fT) / 2;
+ SkPoint otherMidPt = other->ptAtT(otherMidT);
+ if (SkDPoint::ApproximatelyEqual(matchMidPt, otherMidPt)) {
+ *startPt = startSpan.fPt;
+ *endPt = endSpan.fPt;
+ *endT = endSpan.fT;
+ return true;
+ }
+ }
+ }
+ }
+ return false;
+ }
+ if (otherSpan == lastSpan) {
+ break;
+ }
+ otherSpan += step;
+ } while (otherSpan->fT == refT || otherSpan->fPt == refPt);
+ return false;
+}
+
/*
The M and S variable name parts stand for the operators.
Mi stands for Minuend (see wiki subtraction, analogous to difference)
@@ -2076,6 +2155,18 @@
return firstIndex;
}
+int SkOpSegment::findT(double t, const SkOpSegment* match) const {
+ int count = this->count();
+ for (int index = 0; index < count; ++index) {
+ const SkOpSpan& span = fTs[index];
+ if (span.fT == t && span.fOther == match) {
+ return index;
+ }
+ }
+ SkASSERT(0);
+ return -1;
+}
+
// FIXME: either:
// a) mark spans with either end unsortable as done, or
// b) rewrite findTop / findTopSegment / findTopContour to iterate further
@@ -2299,6 +2390,76 @@
return false;
}
+bool SkOpSegment::isTiny(const SkOpAngle* angle) const {
+ int start = angle->start();
+ int end = angle->end();
+ const SkOpSpan& mSpan = fTs[SkMin32(start, end)];
+ return mSpan.fTiny;
+}
+
+bool SkOpSegment::isTiny(int index) const {
+ return fTs[index].fTiny;
+}
+
+// look pair of active edges going away from coincident edge
+// one of them should be the continuation of other
+// if both are active, look to see if they both the connect to another coincident pair
+// if one at least one is a line, then make the pair coincident
+// if neither is a line, test for coincidence
+bool SkOpSegment::joinCoincidence(bool end, SkOpSegment* other, double otherT, int step,
+ bool cancel) {
+ int otherTIndex = other->findT(otherT, this);
+ int next = other->nextExactSpan(otherTIndex, step);
+ int otherMin = SkTMin(otherTIndex, next);
+ int otherWind = other->span(otherMin).fWindValue;
+ if (otherWind == 0) {
+ return false;
+ }
+ SkASSERT(next >= 0);
+ if (end) {
+ int tIndex = count() - 1;
+ do {
+ SkOpSpan* test = &fTs[tIndex];
+ SkASSERT(test->fT == 1);
+ if (test->fOther == other || test->fOtherT != 0) {
+ continue;
+ }
+ SkPoint startPt, endPt;
+ double endT;
+ if (findCoincidentMatch(test, other, otherTIndex, next, step, &startPt, &endPt, &endT)) {
+ SkOpSegment* match = test->fOther;
+ if (cancel) {
+ match->addTCancel(startPt, endPt, other);
+ } else {
+ match->addTCoincident(startPt, endPt, endT, other);
+ }
+ return true;
+ }
+ } while (fTs[--tIndex].fT == 1);
+ } else {
+ int tIndex = 0;
+ do {
+ SkOpSpan* test = &fTs[tIndex];
+ SkASSERT(test->fT == 0);
+ if (test->fOther == other || test->fOtherT != 1) {
+ continue;
+ }
+ SkPoint startPt, endPt;
+ double endT;
+ if (findCoincidentMatch(test, other, otherTIndex, next, step, &startPt, &endPt, &endT)) {
+ SkOpSegment* match = test->fOther;
+ if (cancel) {
+ match->addTCancel(startPt, endPt, other);
+ } else {
+ match->addTCoincident(startPt, endPt, endT, other);
+ }
+ return true;
+ }
+ } while (fTs[++tIndex].fT == 0);
+ }
+ return false;
+}
+
// this span is excluded by the winding rule -- chase the ends
// as long as they are unambiguous to mark connections as done
// and give them the same winding value
@@ -3018,17 +3179,6 @@
(bounds->*SetCurveBounds[SkPathOpsVerbToPoints(fVerb)])(edge);
}
-bool SkOpSegment::isTiny(const SkOpAngle* angle) const {
- int start = angle->start();
- int end = angle->end();
- const SkOpSpan& mSpan = fTs[SkMin32(start, end)];
- return mSpan.fTiny;
-}
-
-bool SkOpSegment::isTiny(int index) const {
- return fTs[index].fTiny;
-}
-
void SkOpSegment::TrackOutsidePair(SkTArray<SkPoint, true>* outsidePts, const SkPoint& endPt,
const SkPoint& startPt) {
int outCount = outsidePts->count();
@@ -3558,10 +3708,10 @@
SkDebugf("{{");
int index = 0;
do {
- SkDPoint::DumpSkPoint(fPts[index]);
+ SkDPoint::dump(fPts[index]);
SkDebugf(", ");
} while (++index < last);
- SkDPoint::DumpSkPoint(fPts[index]);
+ SkDPoint::dump(fPts[index]);
SkDebugf("}}\n");
}
diff --git a/src/pathops/SkOpSegment.h b/src/pathops/SkOpSegment.h
index 85531f5..d56ce8e 100644
--- a/src/pathops/SkOpSegment.h
+++ b/src/pathops/SkOpSegment.h
@@ -259,12 +259,15 @@
SkTArray<SkOpAngle, true>* angles, SkTArray<SkOpAngle*, true>* sorted);
int crossedSpanY(const SkPoint& basePt, SkScalar* bestY, double* hitT, bool* hitSomething,
double mid, bool opp, bool current) const;
+ bool findCoincidentMatch(const SkOpSpan* span, const SkOpSegment* other, int oStart, int oEnd,
+ int step, SkPoint* startPt, SkPoint* endPt, double* endT) const;
SkOpSegment* findNextOp(SkTDArray<SkOpSpan*>* chase, int* nextStart, int* nextEnd,
bool* unsortable, SkPathOp op, const int xorMiMask,
const int xorSuMask);
SkOpSegment* findNextWinding(SkTDArray<SkOpSpan*>* chase, int* nextStart, int* nextEnd,
bool* unsortable);
SkOpSegment* findNextXor(int* nextStart, int* nextEnd, bool* unsortable);
+ int findT(double t, const SkOpSegment* ) const;
SkOpSegment* findTop(int* tIndex, int* endIndex, bool* unsortable, bool onlySortable);
void fixOtherTIndex();
void initWinding(int start, int end);
@@ -272,6 +275,7 @@
SkScalar hitOppDx);
bool isMissing(double startT, const SkPoint& pt) const;
bool isTiny(const SkOpAngle* angle) const;
+ bool joinCoincidence(bool end, SkOpSegment* other, double otherT, int step, bool cancel);
SkOpSpan* markAndChaseDoneBinary(int index, int endIndex);
SkOpSpan* markAndChaseDoneUnary(int index, int endIndex);
SkOpSpan* markAndChaseWinding(const SkOpAngle* angle, int winding, int oppWinding);
diff --git a/src/pathops/SkPathOpsCommon.cpp b/src/pathops/SkPathOpsCommon.cpp
index 4db6079..c48a7ee 100644
--- a/src/pathops/SkPathOpsCommon.cpp
+++ b/src/pathops/SkPathOpsCommon.cpp
@@ -4,6 +4,7 @@
* Use of this source code is governed by a BSD-style license that can be
* found in the LICENSE file.
*/
+#include "SkAddIntersections.h"
#include "SkOpEdgeBuilder.h"
#include "SkPathOpsCommon.h"
#include "SkPathWriter.h"
@@ -350,7 +351,7 @@
return current;
}
-void CheckEnds(SkTArray<SkOpContour*, true>* contourList) {
+static void checkEnds(SkTArray<SkOpContour*, true>* contourList) {
// it's hard to determine if the end of a cubic or conic nearly intersects another curve.
// instead, look to see if the connecting curve intersected at that same end.
int contourCount = (*contourList).count();
@@ -361,7 +362,7 @@
}
// A tiny interval may indicate an undiscovered coincidence. Find and fix.
-void CheckTiny(SkTArray<SkOpContour*, true>* contourList) {
+static void checkTiny(SkTArray<SkOpContour*, true>* contourList) {
int contourCount = (*contourList).count();
for (int cTest = 0; cTest < contourCount; ++cTest) {
SkOpContour* contour = (*contourList)[cTest];
@@ -369,7 +370,7 @@
}
}
-void FixOtherTIndex(SkTArray<SkOpContour*, true>* contourList) {
+static void fixOtherTIndex(SkTArray<SkOpContour*, true>* contourList) {
int contourCount = (*contourList).count();
for (int cTest = 0; cTest < contourCount; ++cTest) {
SkOpContour* contour = (*contourList)[cTest];
@@ -377,7 +378,15 @@
}
}
-void SortSegments(SkTArray<SkOpContour*, true>* contourList) {
+static void joinCoincidence(SkTArray<SkOpContour*, true>* contourList) {
+ int contourCount = (*contourList).count();
+ for (int cTest = 0; cTest < contourCount; ++cTest) {
+ SkOpContour* contour = (*contourList)[cTest];
+ contour->joinCoincidence();
+ }
+}
+
+static void sortSegments(SkTArray<SkOpContour*, true>* contourList) {
int contourCount = (*contourList).count();
for (int cTest = 0; cTest < contourCount; ++cTest) {
SkOpContour* contour = (*contourList)[cTest];
@@ -603,3 +612,21 @@
}
#endif
}
+
+void HandleCoincidence(SkTArray<SkOpContour*, true>* contourList, int total) {
+#if DEBUG_SHOW_WINDING
+ SkOpContour::debugShowWindingValues(contourList);
+#endif
+ CoincidenceCheck(contourList, total);
+#if DEBUG_SHOW_WINDING
+ SkOpContour::debugShowWindingValues(contourList);
+#endif
+ fixOtherTIndex(contourList);
+ checkEnds(contourList);
+ checkTiny(contourList);
+ joinCoincidence(contourList);
+ sortSegments(contourList);
+#if DEBUG_ACTIVE_SPANS || DEBUG_ACTIVE_SPANS_FIRST_ONLY
+ DebugShowActiveSpans(*contourList);
+#endif
+}
diff --git a/src/pathops/SkPathOpsCommon.h b/src/pathops/SkPathOpsCommon.h
index e1ae998..afc751d 100644
--- a/src/pathops/SkPathOpsCommon.h
+++ b/src/pathops/SkPathOpsCommon.h
@@ -14,18 +14,15 @@
class SkPathWriter;
void Assemble(const SkPathWriter& path, SkPathWriter* simple);
-void CheckEnds(SkTArray<SkOpContour*, true>* contourList);
-void CheckTiny(SkTArray<SkOpContour*, true>* contourList);
// FIXME: find chase uses insert, so it can't be converted to SkTArray yet
SkOpSegment* FindChase(SkTDArray<SkOpSpan*>& chase, int& tIndex, int& endIndex);
SkOpSegment* FindSortableTop(const SkTArray<SkOpContour*, true>& , SkOpAngle::IncludeType ,
bool* firstContour, int* index, int* endIndex, SkPoint* topLeft,
bool* unsortable, bool* done);
SkOpSegment* FindUndone(SkTArray<SkOpContour*, true>& contourList, int* start, int* end);
-void FixOtherTIndex(SkTArray<SkOpContour*, true>* contourList);
void MakeContourList(SkTArray<SkOpContour>& contours, SkTArray<SkOpContour*, true>& list,
bool evenOdd, bool oppEvenOdd);
-void SortSegments(SkTArray<SkOpContour*, true>* contourList);
+void HandleCoincidence(SkTArray<SkOpContour*, true>* , int );
#if DEBUG_ACTIVE_SPANS || DEBUG_ACTIVE_SPANS_FIRST_ONLY
void DebugShowActiveSpans(SkTArray<SkOpContour*, true>& contourList);
diff --git a/src/pathops/SkPathOpsDebug.cpp b/src/pathops/SkPathOpsDebug.cpp
index 1b19fe5..95e2204 100644
--- a/src/pathops/SkPathOpsDebug.cpp
+++ b/src/pathops/SkPathOpsDebug.cpp
@@ -103,7 +103,7 @@
SkDebugf("t=");
DebugDumpDouble(fT);
SkDebugf(" pt=");
- SkDPoint::DumpSkPoint(fPt);
+ SkDPoint::dump(fPt);
SkDebugf(" other.fID=%d", fOther->debugID());
SkDebugf(" [%d] otherT=", fOtherIndex);
DebugDumpDouble(fOtherT);
@@ -157,3 +157,8 @@
}
#endif
+
+#if !FORCE_RELEASE && 0 // enable when building without extended test
+void SkPathOpsDebug::ShowPath(const SkPath& one, const SkPath& two, SkPathOp op, const char* name) {
+}
+#endif
diff --git a/src/pathops/SkPathOpsOp.cpp b/src/pathops/SkPathOpsOp.cpp
index 71ebef0..9d6cd51 100644
--- a/src/pathops/SkPathOpsOp.cpp
+++ b/src/pathops/SkPathOpsOp.cpp
@@ -304,20 +304,7 @@
for (index = 0; index < contourList.count(); ++index) {
total += contourList[index]->segments().count();
}
-#if DEBUG_SHOW_WINDING
- SkOpContour::debugShowWindingValues(contourList);
-#endif
- CoincidenceCheck(&contourList, total);
-#if DEBUG_SHOW_WINDING
- SkOpContour::debugShowWindingValues(contourList);
-#endif
- FixOtherTIndex(&contourList);
- CheckEnds(&contourList);
- CheckTiny(&contourList);
- SortSegments(&contourList);
-#if DEBUG_ACTIVE_SPANS || DEBUG_ACTIVE_SPANS_FIRST_ONLY
- DebugShowActiveSpans(contourList);
-#endif
+ HandleCoincidence(&contourList, total);
// construct closed contours
SkPathWriter wrapper(*result);
bridgeOp(contourList, op, xorMask, xorOpMask, &wrapper);
diff --git a/src/pathops/SkPathOpsPoint.h b/src/pathops/SkPathOpsPoint.h
index 40688d8..c3e0b40 100644
--- a/src/pathops/SkPathOpsPoint.h
+++ b/src/pathops/SkPathOpsPoint.h
@@ -98,7 +98,7 @@
// note: this can not be implemented with
// return approximately_equal(a.fY, fY) && approximately_equal(a.fX, fX);
- // because that will not take the magnitude of the values
+ // because that will not take the magnitude of the values into account
bool approximatelyEqual(const SkDPoint& a) const {
if (approximately_equal(fX, a.fX) && approximately_equal(fY, a.fY)) {
return true;
@@ -136,6 +136,20 @@
return AlmostBequalUlps((double) largest, largest + dist); // is dist within ULPS tolerance?
}
+ bool approximatelyPEqual(const SkDPoint& a) const {
+ if (approximately_equal(fX, a.fX) && approximately_equal(fY, a.fY)) {
+ return true;
+ }
+ 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 AlmostPequalUlps(largest, largest + dist); // is the dist within ULPS tolerance?
+ }
+
bool approximatelyZero() const {
return approximately_zero(fX) && approximately_zero(fY);
}
@@ -186,7 +200,7 @@
SkDebugf("}");
}
- static void DumpSkPoint(const SkPoint& pt) {
+ static void dump(const SkPoint& pt) {
SkDebugf("{");
DebugDumpFloat(pt.fX);
SkDebugf(", ");
diff --git a/src/pathops/SkPathOpsSimplify.cpp b/src/pathops/SkPathOpsSimplify.cpp
index 76e3413..548f83e 100644
--- a/src/pathops/SkPathOpsSimplify.cpp
+++ b/src/pathops/SkPathOpsSimplify.cpp
@@ -182,15 +182,7 @@
next = *nextPtr++;
} while (AddIntersectTs(current, next) && nextPtr != listEnd);
} while (currentPtr != listEnd);
- // eat through coincident edges
- CoincidenceCheck(&contourList, 0);
- FixOtherTIndex(&contourList);
- CheckEnds(&contourList);
- CheckTiny(&contourList);
- SortSegments(&contourList);
-#if DEBUG_ACTIVE_SPANS || DEBUG_ACTIVE_SPANS_FIRST_ONLY
- DebugShowActiveSpans(contourList);
-#endif
+ HandleCoincidence(&contourList, 0);
// construct closed contours
SkPathWriter simple(*result);
if (builder.xorMask() == kWinding_PathOpsMask ? bridgeWinding(contourList, &simple)
diff --git a/src/pathops/SkPathOpsTriangle.cpp b/src/pathops/SkPathOpsTriangle.cpp
index 4939166..003968d 100644
--- a/src/pathops/SkPathOpsTriangle.cpp
+++ b/src/pathops/SkPathOpsTriangle.cpp
@@ -8,6 +8,7 @@
#include "SkPathOpsTriangle.h"
// http://www.blackpawn.com/texts/pointinpoly/default.html
+// return true if pt is inside triangle; false if outside or on the line
bool SkDTriangle::contains(const SkDPoint& pt) const {
// Compute vectors
SkDVector v0 = fPts[2] - fPts[0];
@@ -21,11 +22,30 @@
double dot11 = v1.dot(v1);
double dot12 = v1.dot(v2);
+// original code doesn't handle degenerate input; isn't symmetric with inclusion of corner pts;
+// introduces necessary error with divide; doesn't short circuit on early answer
+#if 0
// Compute barycentric coordinates
double invDenom = 1 / (dot00 * dot11 - dot01 * dot01);
double u = (dot11 * dot02 - dot01 * dot12) * invDenom;
double v = (dot00 * dot12 - dot01 * dot02) * invDenom;
// Check if point is in triangle
- return (u >= 0) && (v >= 0) && (u + v < 1);
+ return (u >= 0) && (v >= 0) && (u + v <= 1);
+#else
+ double w = dot00 * dot11 - dot01 * dot01;
+ if (w == 0) {
+ return false;
+ }
+ double wSign = w < 0 ? -1 : 1;
+ double u = (dot11 * dot02 - dot01 * dot12) * wSign;
+ if (u <= 0) {
+ return false;
+ }
+ double v = (dot00 * dot12 - dot01 * dot02) * wSign;
+ if (v <= 0) {
+ return false;
+ }
+ return u + v < w * wSign;
+#endif
}
diff --git a/src/pathops/SkPathOpsTypes.cpp b/src/pathops/SkPathOpsTypes.cpp
index df73d11..dbed086 100644
--- a/src/pathops/SkPathOpsTypes.cpp
+++ b/src/pathops/SkPathOpsTypes.cpp
@@ -8,17 +8,17 @@
#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;
+ float denormalizedCheck = FLT_EPSILON * epsilon / 2;
+ return fabsf(a) <= denormalizedCheck && fabsf(b) <= denormalizedCheck;
}
// from http://randomascii.wordpress.com/2012/02/25/comparing-floating-point-numbers-2012-edition/
// FIXME: move to SkFloatBits.h
-static bool equal_ulps(float a, float b, int epsilon) {
+static bool equal_ulps(float a, float b, int epsilon, int depsilon) {
if (!SkScalarIsFinite(a) || !SkScalarIsFinite(b)) {
return false;
}
- if (arguments_denormalized(a, b, epsilon)) {
+ if (arguments_denormalized(a, b, depsilon)) {
return true;
}
int aBits = SkFloatAs2sCompliment(a);
@@ -89,7 +89,12 @@
// equality using the same error term as between
bool AlmostBequalUlps(float a, float b) {
const int UlpsEpsilon = 2;
- return equal_ulps(a, b, UlpsEpsilon);
+ return equal_ulps(a, b, UlpsEpsilon, UlpsEpsilon);
+}
+
+bool AlmostPequalUlps(float a, float b) {
+ const int UlpsEpsilon = 8;
+ return equal_ulps(a, b, UlpsEpsilon, UlpsEpsilon);
}
bool AlmostDequalUlps(float a, float b) {
@@ -99,7 +104,7 @@
bool AlmostEqualUlps(float a, float b) {
const int UlpsEpsilon = 16;
- return equal_ulps(a, b, UlpsEpsilon);
+ return equal_ulps(a, b, UlpsEpsilon, UlpsEpsilon);
}
bool NotAlmostEqualUlps(float a, float b) {
@@ -114,7 +119,8 @@
bool RoughlyEqualUlps(float a, float b) {
const int UlpsEpsilon = 256;
- return equal_ulps(a, b, UlpsEpsilon);
+ const int DUlpsEpsilon = 1024;
+ return equal_ulps(a, b, UlpsEpsilon, DUlpsEpsilon);
}
bool AlmostBetweenUlps(float a, float b, float c) {
diff --git a/src/pathops/SkPathOpsTypes.h b/src/pathops/SkPathOpsTypes.h
index 0ad10c2..4fa86ab 100644
--- a/src/pathops/SkPathOpsTypes.h
+++ b/src/pathops/SkPathOpsTypes.h
@@ -50,6 +50,11 @@
return AlmostBequalUlps(SkDoubleToScalar(a), SkDoubleToScalar(b));
}
+bool AlmostPequalUlps(float a, float b);
+inline bool AlmostPequalUlps(double a, double b) {
+ return AlmostPequalUlps(SkDoubleToScalar(a), SkDoubleToScalar(b));
+}
+
bool RoughlyEqualUlps(float a, float b);
inline bool RoughlyEqualUlps(double a, double b) {
return RoughlyEqualUlps(SkDoubleToScalar(a), SkDoubleToScalar(b));
diff --git a/src/pathops/SkQuarticRoot.cpp b/src/pathops/SkQuarticRoot.cpp
index dca96de..e5b486c 100644
--- a/src/pathops/SkQuarticRoot.cpp
+++ b/src/pathops/SkQuarticRoot.cpp
@@ -71,7 +71,7 @@
return num;
}
if (oneHint) {
- SkASSERT(approximately_zero(t4 + t3 + t2 + t1 + t0)); // 1 is one root
+ SkASSERT(approximately_zero_double(t4 + t3 + t2 + t1 + t0)); // 1 is one root
// note that -C == A + B + D + E
int num = SkDCubic::RootsReal(t4, t4 + t3, -(t1 + t0), -t0, roots);
for (int i = 0; i < num; ++i) {