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/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");
}