1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/gfx/skia/trunk/src/pathops/SkOpSegment.cpp Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,3328 @@
1.4 +/*
1.5 + * Copyright 2012 Google Inc.
1.6 + *
1.7 + * Use of this source code is governed by a BSD-style license that can be
1.8 + * found in the LICENSE file.
1.9 + */
1.10 +#include "SkIntersections.h"
1.11 +#include "SkOpSegment.h"
1.12 +#include "SkPathWriter.h"
1.13 +#include "SkTSort.h"
1.14 +
1.15 +#define F (false) // discard the edge
1.16 +#define T (true) // keep the edge
1.17 +
1.18 +static const bool gUnaryActiveEdge[2][2] = {
1.19 +// from=0 from=1
1.20 +// to=0,1 to=0,1
1.21 + {F, T}, {T, F},
1.22 +};
1.23 +
1.24 +static const bool gActiveEdge[kXOR_PathOp + 1][2][2][2][2] = {
1.25 +// miFrom=0 miFrom=1
1.26 +// miTo=0 miTo=1 miTo=0 miTo=1
1.27 +// suFrom=0 1 suFrom=0 1 suFrom=0 1 suFrom=0 1
1.28 +// suTo=0,1 suTo=0,1 suTo=0,1 suTo=0,1 suTo=0,1 suTo=0,1 suTo=0,1 suTo=0,1
1.29 + {{{{F, F}, {F, F}}, {{T, F}, {T, F}}}, {{{T, T}, {F, F}}, {{F, T}, {T, F}}}}, // mi - su
1.30 + {{{{F, F}, {F, F}}, {{F, T}, {F, T}}}, {{{F, F}, {T, T}}, {{F, T}, {T, F}}}}, // mi & su
1.31 + {{{{F, T}, {T, F}}, {{T, T}, {F, F}}}, {{{T, F}, {T, F}}, {{F, F}, {F, F}}}}, // mi | su
1.32 + {{{{F, T}, {T, F}}, {{T, F}, {F, T}}}, {{{T, F}, {F, T}}, {{F, T}, {T, F}}}}, // mi ^ su
1.33 +};
1.34 +
1.35 +#undef F
1.36 +#undef T
1.37 +
1.38 +enum {
1.39 + kOutsideTrackedTCount = 16, // FIXME: determine what this should be
1.40 + kMissingSpanCount = 4, // FIXME: determine what this should be
1.41 +};
1.42 +
1.43 +// note that this follows the same logic flow as build angles
1.44 +bool SkOpSegment::activeAngle(int index, int* done, SkTArray<SkOpAngle, true>* angles) {
1.45 + if (activeAngleInner(index, done, angles)) {
1.46 + return true;
1.47 + }
1.48 + double referenceT = fTs[index].fT;
1.49 + int lesser = index;
1.50 + while (--lesser >= 0
1.51 + && (precisely_negative(referenceT - fTs[lesser].fT) || fTs[lesser].fTiny)) {
1.52 + if (activeAngleOther(lesser, done, angles)) {
1.53 + return true;
1.54 + }
1.55 + }
1.56 + do {
1.57 + if (activeAngleOther(index, done, angles)) {
1.58 + return true;
1.59 + }
1.60 + if (++index == fTs.count()) {
1.61 + break;
1.62 + }
1.63 + if (fTs[index - 1].fTiny) {
1.64 + referenceT = fTs[index].fT;
1.65 + continue;
1.66 + }
1.67 + } while (precisely_negative(fTs[index].fT - referenceT));
1.68 + return false;
1.69 +}
1.70 +
1.71 +bool SkOpSegment::activeAngleOther(int index, int* done, SkTArray<SkOpAngle, true>* angles) {
1.72 + SkOpSpan* span = &fTs[index];
1.73 + SkOpSegment* other = span->fOther;
1.74 + int oIndex = span->fOtherIndex;
1.75 + return other->activeAngleInner(oIndex, done, angles);
1.76 +}
1.77 +
1.78 +bool SkOpSegment::activeAngleInner(int index, int* done, SkTArray<SkOpAngle, true>* angles) {
1.79 + int next = nextExactSpan(index, 1);
1.80 + if (next > 0) {
1.81 + SkOpSpan& upSpan = fTs[index];
1.82 + if (upSpan.fWindValue || upSpan.fOppValue) {
1.83 + addAngle(angles, index, next);
1.84 + if (upSpan.fDone || upSpan.fUnsortableEnd) {
1.85 + (*done)++;
1.86 + } else if (upSpan.fWindSum != SK_MinS32) {
1.87 + return true;
1.88 + }
1.89 + } else if (!upSpan.fDone) {
1.90 + upSpan.fDone = true;
1.91 + fDoneSpans++;
1.92 + }
1.93 + }
1.94 + int prev = nextExactSpan(index, -1);
1.95 + // edge leading into junction
1.96 + if (prev >= 0) {
1.97 + SkOpSpan& downSpan = fTs[prev];
1.98 + if (downSpan.fWindValue || downSpan.fOppValue) {
1.99 + addAngle(angles, index, prev);
1.100 + if (downSpan.fDone) {
1.101 + (*done)++;
1.102 + } else if (downSpan.fWindSum != SK_MinS32) {
1.103 + return true;
1.104 + }
1.105 + } else if (!downSpan.fDone) {
1.106 + downSpan.fDone = true;
1.107 + fDoneSpans++;
1.108 + }
1.109 + }
1.110 + return false;
1.111 +}
1.112 +
1.113 +SkPoint SkOpSegment::activeLeftTop(bool onlySortable, int* firstT) const {
1.114 + SkASSERT(!done());
1.115 + SkPoint topPt = {SK_ScalarMax, SK_ScalarMax};
1.116 + int count = fTs.count();
1.117 + // see if either end is not done since we want smaller Y of the pair
1.118 + bool lastDone = true;
1.119 + bool lastUnsortable = false;
1.120 + double lastT = -1;
1.121 + for (int index = 0; index < count; ++index) {
1.122 + const SkOpSpan& span = fTs[index];
1.123 + if (onlySortable && (span.fUnsortableStart || lastUnsortable)) {
1.124 + goto next;
1.125 + }
1.126 + if (span.fDone && lastDone) {
1.127 + goto next;
1.128 + }
1.129 + if (approximately_negative(span.fT - lastT)) {
1.130 + goto next;
1.131 + }
1.132 + {
1.133 + const SkPoint& xy = xyAtT(&span);
1.134 + if (topPt.fY > xy.fY || (topPt.fY == xy.fY && topPt.fX > xy.fX)) {
1.135 + topPt = xy;
1.136 + if (firstT) {
1.137 + *firstT = index;
1.138 + }
1.139 + }
1.140 + if (fVerb != SkPath::kLine_Verb && !lastDone) {
1.141 + SkPoint curveTop = (*CurveTop[SkPathOpsVerbToPoints(fVerb)])(fPts, lastT, span.fT);
1.142 + if (topPt.fY > curveTop.fY || (topPt.fY == curveTop.fY
1.143 + && topPt.fX > curveTop.fX)) {
1.144 + topPt = curveTop;
1.145 + if (firstT) {
1.146 + *firstT = index;
1.147 + }
1.148 + }
1.149 + }
1.150 + lastT = span.fT;
1.151 + }
1.152 +next:
1.153 + lastDone = span.fDone;
1.154 + lastUnsortable = span.fUnsortableEnd;
1.155 + }
1.156 + return topPt;
1.157 +}
1.158 +
1.159 +bool SkOpSegment::activeOp(int index, int endIndex, int xorMiMask, int xorSuMask, SkPathOp op) {
1.160 + int sumMiWinding = updateWinding(endIndex, index);
1.161 + int sumSuWinding = updateOppWinding(endIndex, index);
1.162 + if (fOperand) {
1.163 + SkTSwap<int>(sumMiWinding, sumSuWinding);
1.164 + }
1.165 + int maxWinding, sumWinding, oppMaxWinding, oppSumWinding;
1.166 + return activeOp(xorMiMask, xorSuMask, index, endIndex, op, &sumMiWinding, &sumSuWinding,
1.167 + &maxWinding, &sumWinding, &oppMaxWinding, &oppSumWinding);
1.168 +}
1.169 +
1.170 +bool SkOpSegment::activeOp(int xorMiMask, int xorSuMask, int index, int endIndex, SkPathOp op,
1.171 + int* sumMiWinding, int* sumSuWinding,
1.172 + int* maxWinding, int* sumWinding, int* oppMaxWinding, int* oppSumWinding) {
1.173 + setUpWindings(index, endIndex, sumMiWinding, sumSuWinding,
1.174 + maxWinding, sumWinding, oppMaxWinding, oppSumWinding);
1.175 + bool miFrom;
1.176 + bool miTo;
1.177 + bool suFrom;
1.178 + bool suTo;
1.179 + if (operand()) {
1.180 + miFrom = (*oppMaxWinding & xorMiMask) != 0;
1.181 + miTo = (*oppSumWinding & xorMiMask) != 0;
1.182 + suFrom = (*maxWinding & xorSuMask) != 0;
1.183 + suTo = (*sumWinding & xorSuMask) != 0;
1.184 + } else {
1.185 + miFrom = (*maxWinding & xorMiMask) != 0;
1.186 + miTo = (*sumWinding & xorMiMask) != 0;
1.187 + suFrom = (*oppMaxWinding & xorSuMask) != 0;
1.188 + suTo = (*oppSumWinding & xorSuMask) != 0;
1.189 + }
1.190 + bool result = gActiveEdge[op][miFrom][miTo][suFrom][suTo];
1.191 +#if DEBUG_ACTIVE_OP
1.192 + SkDebugf("%s op=%s miFrom=%d miTo=%d suFrom=%d suTo=%d result=%d\n", __FUNCTION__,
1.193 + SkPathOpsDebug::kPathOpStr[op], miFrom, miTo, suFrom, suTo, result);
1.194 +#endif
1.195 + return result;
1.196 +}
1.197 +
1.198 +bool SkOpSegment::activeWinding(int index, int endIndex) {
1.199 + int sumWinding = updateWinding(endIndex, index);
1.200 + int maxWinding;
1.201 + return activeWinding(index, endIndex, &maxWinding, &sumWinding);
1.202 +}
1.203 +
1.204 +bool SkOpSegment::activeWinding(int index, int endIndex, int* maxWinding, int* sumWinding) {
1.205 + setUpWinding(index, endIndex, maxWinding, sumWinding);
1.206 + bool from = *maxWinding != 0;
1.207 + bool to = *sumWinding != 0;
1.208 + bool result = gUnaryActiveEdge[from][to];
1.209 + return result;
1.210 +}
1.211 +
1.212 +void SkOpSegment::addAngle(SkTArray<SkOpAngle, true>* anglesPtr, int start, int end) const {
1.213 + SkASSERT(start != end);
1.214 + SkOpAngle& angle = anglesPtr->push_back();
1.215 + angle.set(this, start, end);
1.216 +}
1.217 +
1.218 +void SkOpSegment::addCancelOutsides(const SkPoint& startPt, const SkPoint& endPt,
1.219 + SkOpSegment* other) {
1.220 + int tIndex = -1;
1.221 + int tCount = fTs.count();
1.222 + int oIndex = -1;
1.223 + int oCount = other->fTs.count();
1.224 + do {
1.225 + ++tIndex;
1.226 + } while (startPt != fTs[tIndex].fPt && tIndex < tCount);
1.227 + int tIndexStart = tIndex;
1.228 + do {
1.229 + ++oIndex;
1.230 + } while (endPt != other->fTs[oIndex].fPt && oIndex < oCount);
1.231 + int oIndexStart = oIndex;
1.232 + const SkPoint* nextPt;
1.233 + do {
1.234 + nextPt = &fTs[++tIndex].fPt;
1.235 + SkASSERT(fTs[tIndex].fT < 1 || startPt != *nextPt);
1.236 + } while (startPt == *nextPt);
1.237 + double nextT = fTs[tIndex].fT;
1.238 + const SkPoint* oNextPt;
1.239 + do {
1.240 + oNextPt = &other->fTs[++oIndex].fPt;
1.241 + SkASSERT(other->fTs[oIndex].fT < 1 || endPt != *oNextPt);
1.242 + } while (endPt == *oNextPt);
1.243 + double oNextT = other->fTs[oIndex].fT;
1.244 + // at this point, spans before and after are at:
1.245 + // fTs[tIndexStart - 1], fTs[tIndexStart], fTs[tIndex]
1.246 + // if tIndexStart == 0, no prior span
1.247 + // if nextT == 1, no following span
1.248 +
1.249 + // advance the span with zero winding
1.250 + // if the following span exists (not past the end, non-zero winding)
1.251 + // connect the two edges
1.252 + if (!fTs[tIndexStart].fWindValue) {
1.253 + if (tIndexStart > 0 && fTs[tIndexStart - 1].fWindValue) {
1.254 +#if DEBUG_CONCIDENT
1.255 + SkDebugf("%s 1 this=%d other=%d t [%d] %1.9g (%1.9g,%1.9g)\n",
1.256 + __FUNCTION__, fID, other->fID, tIndexStart - 1,
1.257 + fTs[tIndexStart].fT, xyAtT(tIndexStart).fX,
1.258 + xyAtT(tIndexStart).fY);
1.259 +#endif
1.260 + addTPair(fTs[tIndexStart].fT, other, other->fTs[oIndex].fT, false,
1.261 + fTs[tIndexStart].fPt);
1.262 + }
1.263 + if (nextT < 1 && fTs[tIndex].fWindValue) {
1.264 +#if DEBUG_CONCIDENT
1.265 + SkDebugf("%s 2 this=%d other=%d t [%d] %1.9g (%1.9g,%1.9g)\n",
1.266 + __FUNCTION__, fID, other->fID, tIndex,
1.267 + fTs[tIndex].fT, xyAtT(tIndex).fX,
1.268 + xyAtT(tIndex).fY);
1.269 +#endif
1.270 + addTPair(fTs[tIndex].fT, other, other->fTs[oIndexStart].fT, false, fTs[tIndex].fPt);
1.271 + }
1.272 + } else {
1.273 + SkASSERT(!other->fTs[oIndexStart].fWindValue);
1.274 + if (oIndexStart > 0 && other->fTs[oIndexStart - 1].fWindValue) {
1.275 +#if DEBUG_CONCIDENT
1.276 + SkDebugf("%s 3 this=%d other=%d t [%d] %1.9g (%1.9g,%1.9g)\n",
1.277 + __FUNCTION__, fID, other->fID, oIndexStart - 1,
1.278 + other->fTs[oIndexStart].fT, other->xyAtT(oIndexStart).fX,
1.279 + other->xyAtT(oIndexStart).fY);
1.280 + other->debugAddTPair(other->fTs[oIndexStart].fT, *this, fTs[tIndex].fT);
1.281 +#endif
1.282 + }
1.283 + if (oNextT < 1 && other->fTs[oIndex].fWindValue) {
1.284 +#if DEBUG_CONCIDENT
1.285 + SkDebugf("%s 4 this=%d other=%d t [%d] %1.9g (%1.9g,%1.9g)\n",
1.286 + __FUNCTION__, fID, other->fID, oIndex,
1.287 + other->fTs[oIndex].fT, other->xyAtT(oIndex).fX,
1.288 + other->xyAtT(oIndex).fY);
1.289 + other->debugAddTPair(other->fTs[oIndex].fT, *this, fTs[tIndexStart].fT);
1.290 +#endif
1.291 + }
1.292 + }
1.293 +}
1.294 +
1.295 +void SkOpSegment::addCoinOutsides(const SkPoint& startPt, const SkPoint& endPt,
1.296 + SkOpSegment* other) {
1.297 + // walk this to startPt
1.298 + // walk other to startPt
1.299 + // if either is > 0, add a pointer to the other, copying adjacent winding
1.300 + int tIndex = -1;
1.301 + int oIndex = -1;
1.302 + do {
1.303 + ++tIndex;
1.304 + } while (startPt != fTs[tIndex].fPt);
1.305 + do {
1.306 + ++oIndex;
1.307 + } while (startPt != other->fTs[oIndex].fPt);
1.308 + if (tIndex > 0 || oIndex > 0 || fOperand != other->fOperand) {
1.309 + addTPair(fTs[tIndex].fT, other, other->fTs[oIndex].fT, false, startPt);
1.310 + }
1.311 + SkPoint nextPt = startPt;
1.312 + do {
1.313 + const SkPoint* workPt;
1.314 + do {
1.315 + workPt = &fTs[++tIndex].fPt;
1.316 + } while (nextPt == *workPt);
1.317 + do {
1.318 + workPt = &other->fTs[++oIndex].fPt;
1.319 + } while (nextPt == *workPt);
1.320 + nextPt = *workPt;
1.321 + double tStart = fTs[tIndex].fT;
1.322 + double oStart = other->fTs[oIndex].fT;
1.323 + if (tStart == 1 && oStart == 1 && fOperand == other->fOperand) {
1.324 + break;
1.325 + }
1.326 + addTPair(tStart, other, oStart, false, nextPt);
1.327 + } while (endPt != nextPt);
1.328 +}
1.329 +
1.330 +void SkOpSegment::addCubic(const SkPoint pts[4], bool operand, bool evenOdd) {
1.331 + init(pts, SkPath::kCubic_Verb, operand, evenOdd);
1.332 + fBounds.setCubicBounds(pts);
1.333 +}
1.334 +
1.335 +void SkOpSegment::addCurveTo(int start, int end, SkPathWriter* path, bool active) const {
1.336 + SkPoint edge[4];
1.337 + const SkPoint* ePtr;
1.338 + int lastT = fTs.count() - 1;
1.339 + if (lastT < 0 || (start == 0 && end == lastT) || (start == lastT && end == 0)) {
1.340 + ePtr = fPts;
1.341 + } else {
1.342 + // OPTIMIZE? if not active, skip remainder and return xyAtT(end)
1.343 + subDivide(start, end, edge);
1.344 + ePtr = edge;
1.345 + }
1.346 + if (active) {
1.347 + bool reverse = ePtr == fPts && start != 0;
1.348 + if (reverse) {
1.349 + path->deferredMoveLine(ePtr[SkPathOpsVerbToPoints(fVerb)]);
1.350 + switch (fVerb) {
1.351 + case SkPath::kLine_Verb:
1.352 + path->deferredLine(ePtr[0]);
1.353 + break;
1.354 + case SkPath::kQuad_Verb:
1.355 + path->quadTo(ePtr[1], ePtr[0]);
1.356 + break;
1.357 + case SkPath::kCubic_Verb:
1.358 + path->cubicTo(ePtr[2], ePtr[1], ePtr[0]);
1.359 + break;
1.360 + default:
1.361 + SkASSERT(0);
1.362 + }
1.363 + // return ePtr[0];
1.364 + } else {
1.365 + path->deferredMoveLine(ePtr[0]);
1.366 + switch (fVerb) {
1.367 + case SkPath::kLine_Verb:
1.368 + path->deferredLine(ePtr[1]);
1.369 + break;
1.370 + case SkPath::kQuad_Verb:
1.371 + path->quadTo(ePtr[1], ePtr[2]);
1.372 + break;
1.373 + case SkPath::kCubic_Verb:
1.374 + path->cubicTo(ePtr[1], ePtr[2], ePtr[3]);
1.375 + break;
1.376 + default:
1.377 + SkASSERT(0);
1.378 + }
1.379 + }
1.380 + }
1.381 + // return ePtr[SkPathOpsVerbToPoints(fVerb)];
1.382 +}
1.383 +
1.384 +void SkOpSegment::addLine(const SkPoint pts[2], bool operand, bool evenOdd) {
1.385 + init(pts, SkPath::kLine_Verb, operand, evenOdd);
1.386 + fBounds.set(pts, 2);
1.387 +}
1.388 +
1.389 +// add 2 to edge or out of range values to get T extremes
1.390 +void SkOpSegment::addOtherT(int index, double otherT, int otherIndex) {
1.391 + SkOpSpan& span = fTs[index];
1.392 + if (precisely_zero(otherT)) {
1.393 + otherT = 0;
1.394 + } else if (precisely_equal(otherT, 1)) {
1.395 + otherT = 1;
1.396 + }
1.397 + span.fOtherT = otherT;
1.398 + span.fOtherIndex = otherIndex;
1.399 +}
1.400 +
1.401 +void SkOpSegment::addQuad(const SkPoint pts[3], bool operand, bool evenOdd) {
1.402 + init(pts, SkPath::kQuad_Verb, operand, evenOdd);
1.403 + fBounds.setQuadBounds(pts);
1.404 +}
1.405 +
1.406 + // Defer all coincident edge processing until
1.407 + // after normal intersections have been computed
1.408 +
1.409 +// no need to be tricky; insert in normal T order
1.410 +// resolve overlapping ts when considering coincidence later
1.411 +
1.412 + // add non-coincident intersection. Resulting edges are sorted in T.
1.413 +int SkOpSegment::addT(SkOpSegment* other, const SkPoint& pt, double newT) {
1.414 + if (precisely_zero(newT)) {
1.415 + newT = 0;
1.416 + } else if (precisely_equal(newT, 1)) {
1.417 + newT = 1;
1.418 + }
1.419 + // FIXME: in the pathological case where there is a ton of intercepts,
1.420 + // binary search?
1.421 + int insertedAt = -1;
1.422 + size_t tCount = fTs.count();
1.423 + const SkPoint& firstPt = fPts[0];
1.424 + const SkPoint& lastPt = fPts[SkPathOpsVerbToPoints(fVerb)];
1.425 + for (size_t index = 0; index < tCount; ++index) {
1.426 + // OPTIMIZATION: if there are three or more identical Ts, then
1.427 + // the fourth and following could be further insertion-sorted so
1.428 + // that all the edges are clockwise or counterclockwise.
1.429 + // This could later limit segment tests to the two adjacent
1.430 + // neighbors, although it doesn't help with determining which
1.431 + // circular direction to go in.
1.432 + const SkOpSpan& span = fTs[index];
1.433 + if (newT < span.fT) {
1.434 + insertedAt = index;
1.435 + break;
1.436 + }
1.437 + if (newT == span.fT) {
1.438 + if (pt == span.fPt) {
1.439 + insertedAt = index;
1.440 + break;
1.441 + }
1.442 + if ((pt == firstPt && newT == 0) || (span.fPt == lastPt && newT == 1)) {
1.443 + insertedAt = index;
1.444 + break;
1.445 + }
1.446 + }
1.447 + }
1.448 + SkOpSpan* span;
1.449 + if (insertedAt >= 0) {
1.450 + span = fTs.insert(insertedAt);
1.451 + } else {
1.452 + insertedAt = tCount;
1.453 + span = fTs.append();
1.454 + }
1.455 + span->fT = newT;
1.456 + span->fOther = other;
1.457 + span->fPt = pt;
1.458 +#if 0
1.459 + // cubics, for instance, may not be exact enough to satisfy this check (e.g., cubicOp69d)
1.460 + SkASSERT(approximately_equal(xyAtT(newT).fX, pt.fX)
1.461 + && approximately_equal(xyAtT(newT).fY, pt.fY));
1.462 +#endif
1.463 + span->fWindSum = SK_MinS32;
1.464 + span->fOppSum = SK_MinS32;
1.465 + span->fWindValue = 1;
1.466 + span->fOppValue = 0;
1.467 + span->fSmall = false;
1.468 + span->fTiny = false;
1.469 + span->fLoop = false;
1.470 + if ((span->fDone = newT == 1)) {
1.471 + ++fDoneSpans;
1.472 + }
1.473 + span->fUnsortableStart = false;
1.474 + span->fUnsortableEnd = false;
1.475 + int less = -1;
1.476 + while (&span[less + 1] - fTs.begin() > 0 && AlmostEqualUlps(span[less].fPt, span->fPt)) {
1.477 + if (span[less].fDone) {
1.478 + break;
1.479 + }
1.480 + double tInterval = newT - span[less].fT;
1.481 + if (precisely_negative(tInterval)) {
1.482 + break;
1.483 + }
1.484 + if (fVerb == SkPath::kCubic_Verb) {
1.485 + double tMid = newT - tInterval / 2;
1.486 + SkDPoint midPt = dcubic_xy_at_t(fPts, tMid);
1.487 + if (!midPt.approximatelyEqual(xyAtT(span))) {
1.488 + break;
1.489 + }
1.490 + }
1.491 + span[less].fSmall = true;
1.492 + bool tiny = span[less].fPt == span->fPt;
1.493 + span[less].fTiny = tiny;
1.494 + span[less].fDone = true;
1.495 + if (approximately_negative(newT - span[less].fT) && tiny) {
1.496 + if (approximately_greater_than_one(newT)) {
1.497 + SkASSERT(&span[less] - fTs.begin() < fTs.count());
1.498 + span[less].fUnsortableStart = true;
1.499 + if (&span[less - 1] - fTs.begin() >= 0) {
1.500 + span[less - 1].fUnsortableEnd = true;
1.501 + }
1.502 + }
1.503 + if (approximately_less_than_zero(span[less].fT)) {
1.504 + SkASSERT(&span[less + 1] - fTs.begin() < fTs.count());
1.505 + SkASSERT(&span[less] - fTs.begin() >= 0);
1.506 + span[less + 1].fUnsortableStart = true;
1.507 + span[less].fUnsortableEnd = true;
1.508 + }
1.509 + }
1.510 + ++fDoneSpans;
1.511 + --less;
1.512 + }
1.513 + int more = 1;
1.514 + while (fTs.end() - &span[more - 1] > 1 && AlmostEqualUlps(span[more].fPt, span->fPt)) {
1.515 + if (span[more - 1].fDone) {
1.516 + break;
1.517 + }
1.518 + double tEndInterval = span[more].fT - newT;
1.519 + if (precisely_negative(tEndInterval)) {
1.520 + if ((span->fTiny = span[more].fTiny)) {
1.521 + span->fDone = true;
1.522 + ++fDoneSpans;
1.523 + }
1.524 + break;
1.525 + }
1.526 + if (fVerb == SkPath::kCubic_Verb) {
1.527 + double tMid = newT - tEndInterval / 2;
1.528 + SkDPoint midEndPt = dcubic_xy_at_t(fPts, tMid);
1.529 + if (!midEndPt.approximatelyEqual(xyAtT(span))) {
1.530 + break;
1.531 + }
1.532 + }
1.533 + span[more - 1].fSmall = true;
1.534 + bool tiny = span[more].fPt == span->fPt;
1.535 + span[more - 1].fTiny = tiny;
1.536 + span[more - 1].fDone = true;
1.537 + if (approximately_negative(span[more].fT - newT) && tiny) {
1.538 + if (approximately_greater_than_one(span[more].fT)) {
1.539 + span[more + 1].fUnsortableStart = true;
1.540 + span[more].fUnsortableEnd = true;
1.541 + }
1.542 + if (approximately_less_than_zero(newT)) {
1.543 + span[more].fUnsortableStart = true;
1.544 + span[more - 1].fUnsortableEnd = true;
1.545 + }
1.546 + }
1.547 + ++fDoneSpans;
1.548 + ++more;
1.549 + }
1.550 + return insertedAt;
1.551 +}
1.552 +
1.553 +// set spans from start to end to decrement by one
1.554 +// note this walks other backwards
1.555 +// FIXME: there's probably an edge case that can be constructed where
1.556 +// two span in one segment are separated by float epsilon on one span but
1.557 +// not the other, if one segment is very small. For this
1.558 +// case the counts asserted below may or may not be enough to separate the
1.559 +// spans. Even if the counts work out, what if the spans aren't correctly
1.560 +// sorted? It feels better in such a case to match the span's other span
1.561 +// pointer since both coincident segments must contain the same spans.
1.562 +// FIXME? It seems that decrementing by one will fail for complex paths that
1.563 +// have three or more coincident edges. Shouldn't this subtract the difference
1.564 +// between the winding values?
1.565 +/* |--> |-->
1.566 +this 0>>>>1>>>>2>>>>3>>>4 0>>>>1>>>>2>>>>3>>>4 0>>>>1>>>>2>>>>3>>>4
1.567 +other 2<<<<1<<<<0 2<<<<1<<<<0 2<<<<1<<<<0
1.568 + ^ ^ <--| <--|
1.569 + startPt endPt test/oTest first pos test/oTest final pos
1.570 +*/
1.571 +void SkOpSegment::addTCancel(const SkPoint& startPt, const SkPoint& endPt, SkOpSegment* other) {
1.572 + bool binary = fOperand != other->fOperand;
1.573 + int index = 0;
1.574 + while (startPt != fTs[index].fPt) {
1.575 + SkASSERT(index < fTs.count());
1.576 + ++index;
1.577 + }
1.578 + while (index > 0 && fTs[index].fT == fTs[index - 1].fT) {
1.579 + --index;
1.580 + }
1.581 + int oIndex = other->fTs.count();
1.582 + while (startPt != other->fTs[--oIndex].fPt) { // look for startPt match
1.583 + SkASSERT(oIndex > 0);
1.584 + }
1.585 + double oStartT = other->fTs[oIndex].fT;
1.586 + // look for first point beyond match
1.587 + while (startPt == other->fTs[--oIndex].fPt || oStartT == other->fTs[oIndex].fT) {
1.588 + SkASSERT(oIndex > 0);
1.589 + }
1.590 + SkOpSpan* test = &fTs[index];
1.591 + SkOpSpan* oTest = &other->fTs[oIndex];
1.592 + SkSTArray<kOutsideTrackedTCount, SkPoint, true> outsidePts;
1.593 + SkSTArray<kOutsideTrackedTCount, SkPoint, true> oOutsidePts;
1.594 + do {
1.595 + SkASSERT(test->fT < 1);
1.596 + SkASSERT(oTest->fT < 1);
1.597 + bool decrement = test->fWindValue && oTest->fWindValue;
1.598 + bool track = test->fWindValue || oTest->fWindValue;
1.599 + bool bigger = test->fWindValue >= oTest->fWindValue;
1.600 + const SkPoint& testPt = test->fPt;
1.601 + double testT = test->fT;
1.602 + const SkPoint& oTestPt = oTest->fPt;
1.603 + double oTestT = oTest->fT;
1.604 + do {
1.605 + if (decrement) {
1.606 + if (binary && bigger) {
1.607 + test->fOppValue--;
1.608 + } else {
1.609 + decrementSpan(test);
1.610 + }
1.611 + } else if (track) {
1.612 + TrackOutsidePair(&outsidePts, testPt, oTestPt);
1.613 + }
1.614 + SkASSERT(index < fTs.count() - 1);
1.615 + test = &fTs[++index];
1.616 + } while (testPt == test->fPt || testT == test->fT);
1.617 + SkDEBUGCODE(int originalWindValue = oTest->fWindValue);
1.618 + do {
1.619 + SkASSERT(oTest->fT < 1);
1.620 + SkASSERT(originalWindValue == oTest->fWindValue);
1.621 + if (decrement) {
1.622 + if (binary && !bigger) {
1.623 + oTest->fOppValue--;
1.624 + } else {
1.625 + other->decrementSpan(oTest);
1.626 + }
1.627 + } else if (track) {
1.628 + TrackOutsidePair(&oOutsidePts, oTestPt, testPt);
1.629 + }
1.630 + if (!oIndex) {
1.631 + break;
1.632 + }
1.633 + oTest = &other->fTs[--oIndex];
1.634 + } while (oTestPt == oTest->fPt || oTestT == oTest->fT);
1.635 + } while (endPt != test->fPt && test->fT < 1);
1.636 + // FIXME: determine if canceled edges need outside ts added
1.637 + int outCount = outsidePts.count();
1.638 + if (!done() && outCount) {
1.639 + addCancelOutsides(outsidePts[0], outsidePts[1], other);
1.640 + if (outCount > 2) {
1.641 + addCancelOutsides(outsidePts[outCount - 2], outsidePts[outCount - 1], other);
1.642 + }
1.643 + }
1.644 + if (!other->done() && oOutsidePts.count()) {
1.645 + other->addCancelOutsides(oOutsidePts[0], oOutsidePts[1], this);
1.646 + }
1.647 +}
1.648 +
1.649 +int SkOpSegment::addSelfT(SkOpSegment* other, const SkPoint& pt, double newT) {
1.650 + // if the tail nearly intersects itself but not quite, the caller records this separately
1.651 + int result = addT(other, pt, newT);
1.652 + SkOpSpan* span = &fTs[result];
1.653 + span->fLoop = true;
1.654 + return result;
1.655 +}
1.656 +
1.657 +void SkOpSegment::bumpCoincidentThis(const SkOpSpan& oTest, bool binary, int* indexPtr,
1.658 + SkTArray<SkPoint, true>* outsideTs) {
1.659 + int index = *indexPtr;
1.660 + int oWindValue = oTest.fWindValue;
1.661 + int oOppValue = oTest.fOppValue;
1.662 + if (binary) {
1.663 + SkTSwap<int>(oWindValue, oOppValue);
1.664 + }
1.665 + SkOpSpan* const test = &fTs[index];
1.666 + SkOpSpan* end = test;
1.667 + const SkPoint& oStartPt = oTest.fPt;
1.668 + do {
1.669 + if (bumpSpan(end, oWindValue, oOppValue)) {
1.670 + TrackOutside(outsideTs, oStartPt);
1.671 + }
1.672 + end = &fTs[++index];
1.673 + } while ((end->fPt == test->fPt || end->fT == test->fT) && end->fT < 1);
1.674 + *indexPtr = index;
1.675 +}
1.676 +
1.677 +// because of the order in which coincidences are resolved, this and other
1.678 +// may not have the same intermediate points. Compute the corresponding
1.679 +// intermediate T values (using this as the master, other as the follower)
1.680 +// and walk other conditionally -- hoping that it catches up in the end
1.681 +void SkOpSegment::bumpCoincidentOther(const SkOpSpan& test, int* oIndexPtr,
1.682 + SkTArray<SkPoint, true>* oOutsidePts) {
1.683 + int oIndex = *oIndexPtr;
1.684 + SkOpSpan* const oTest = &fTs[oIndex];
1.685 + SkOpSpan* oEnd = oTest;
1.686 + const SkPoint& startPt = test.fPt;
1.687 + const SkPoint& oStartPt = oTest->fPt;
1.688 + double oStartT = oTest->fT;
1.689 + if (oStartPt == oEnd->fPt || oStartT == oEnd->fT) {
1.690 + TrackOutside(oOutsidePts, startPt);
1.691 + }
1.692 + while (oStartPt == oEnd->fPt || oStartT == oEnd->fT) {
1.693 + zeroSpan(oEnd);
1.694 + oEnd = &fTs[++oIndex];
1.695 + }
1.696 + *oIndexPtr = oIndex;
1.697 +}
1.698 +
1.699 +// FIXME: need to test this case:
1.700 +// contourA has two segments that are coincident
1.701 +// contourB has two segments that are coincident in the same place
1.702 +// each ends up with +2/0 pairs for winding count
1.703 +// since logic below doesn't transfer count (only increments/decrements) can this be
1.704 +// resolved to +4/0 ?
1.705 +
1.706 +// set spans from start to end to increment the greater by one and decrement
1.707 +// the lesser
1.708 +void SkOpSegment::addTCoincident(const SkPoint& startPt, const SkPoint& endPt, double endT,
1.709 + SkOpSegment* other) {
1.710 + bool binary = fOperand != other->fOperand;
1.711 + int index = 0;
1.712 + while (startPt != fTs[index].fPt) {
1.713 + SkASSERT(index < fTs.count());
1.714 + ++index;
1.715 + }
1.716 + double startT = fTs[index].fT;
1.717 + while (index > 0 && fTs[index - 1].fT == startT) {
1.718 + --index;
1.719 + }
1.720 + int oIndex = 0;
1.721 + while (startPt != other->fTs[oIndex].fPt) {
1.722 + SkASSERT(oIndex < other->fTs.count());
1.723 + ++oIndex;
1.724 + }
1.725 + double oStartT = other->fTs[oIndex].fT;
1.726 + while (oIndex > 0 && other->fTs[oIndex - 1].fT == oStartT) {
1.727 + --oIndex;
1.728 + }
1.729 + SkSTArray<kOutsideTrackedTCount, SkPoint, true> outsidePts;
1.730 + SkSTArray<kOutsideTrackedTCount, SkPoint, true> oOutsidePts;
1.731 + SkOpSpan* test = &fTs[index];
1.732 + const SkPoint* testPt = &test->fPt;
1.733 + double testT = test->fT;
1.734 + SkOpSpan* oTest = &other->fTs[oIndex];
1.735 + const SkPoint* oTestPt = &oTest->fPt;
1.736 + SkASSERT(AlmostEqualUlps(*testPt, *oTestPt));
1.737 + do {
1.738 + SkASSERT(test->fT < 1);
1.739 + SkASSERT(oTest->fT < 1);
1.740 +#if 0
1.741 + if (test->fDone || oTest->fDone) {
1.742 +#else // consolidate the winding count even if done
1.743 + if ((test->fWindValue == 0 && test->fOppValue == 0)
1.744 + || (oTest->fWindValue == 0 && oTest->fOppValue == 0)) {
1.745 +#endif
1.746 + SkDEBUGCODE(int firstWind = test->fWindValue);
1.747 + SkDEBUGCODE(int firstOpp = test->fOppValue);
1.748 + do {
1.749 + SkASSERT(firstWind == fTs[index].fWindValue);
1.750 + SkASSERT(firstOpp == fTs[index].fOppValue);
1.751 + ++index;
1.752 + SkASSERT(index < fTs.count());
1.753 + } while (*testPt == fTs[index].fPt);
1.754 + SkDEBUGCODE(firstWind = oTest->fWindValue);
1.755 + SkDEBUGCODE(firstOpp = oTest->fOppValue);
1.756 + do {
1.757 + SkASSERT(firstWind == other->fTs[oIndex].fWindValue);
1.758 + SkASSERT(firstOpp == other->fTs[oIndex].fOppValue);
1.759 + ++oIndex;
1.760 + SkASSERT(oIndex < other->fTs.count());
1.761 + } while (*oTestPt == other->fTs[oIndex].fPt);
1.762 + } else {
1.763 + if (!binary || test->fWindValue + oTest->fOppValue >= 0) {
1.764 + bumpCoincidentThis(*oTest, binary, &index, &outsidePts);
1.765 + other->bumpCoincidentOther(*test, &oIndex, &oOutsidePts);
1.766 + } else {
1.767 + other->bumpCoincidentThis(*test, binary, &oIndex, &oOutsidePts);
1.768 + bumpCoincidentOther(*oTest, &index, &outsidePts);
1.769 + }
1.770 + }
1.771 + test = &fTs[index];
1.772 + testPt = &test->fPt;
1.773 + testT = test->fT;
1.774 + if (endPt == *testPt || endT == testT) {
1.775 + break;
1.776 + }
1.777 + oTest = &other->fTs[oIndex];
1.778 + oTestPt = &oTest->fPt;
1.779 + SkASSERT(AlmostEqualUlps(*testPt, *oTestPt));
1.780 + } while (endPt != *oTestPt);
1.781 + if (endPt != *testPt && endT != testT) { // in rare cases, one may have ended before the other
1.782 + int lastWind = test[-1].fWindValue;
1.783 + int lastOpp = test[-1].fOppValue;
1.784 + bool zero = lastWind == 0 && lastOpp == 0;
1.785 + do {
1.786 + if (test->fWindValue || test->fOppValue) {
1.787 + test->fWindValue = lastWind;
1.788 + test->fOppValue = lastOpp;
1.789 + if (zero) {
1.790 + test->fDone = true;
1.791 + ++fDoneSpans;
1.792 + }
1.793 + }
1.794 + test = &fTs[++index];
1.795 + testPt = &test->fPt;
1.796 + } while (endPt != *testPt);
1.797 + }
1.798 + int outCount = outsidePts.count();
1.799 + if (!done() && outCount) {
1.800 + addCoinOutsides(outsidePts[0], endPt, other);
1.801 + }
1.802 + if (!other->done() && oOutsidePts.count()) {
1.803 + other->addCoinOutsides(oOutsidePts[0], endPt, this);
1.804 + }
1.805 +}
1.806 +
1.807 +// FIXME: this doesn't prevent the same span from being added twice
1.808 +// fix in caller, SkASSERT here?
1.809 +void SkOpSegment::addTPair(double t, SkOpSegment* other, double otherT, bool borrowWind,
1.810 + const SkPoint& pt) {
1.811 + int tCount = fTs.count();
1.812 + for (int tIndex = 0; tIndex < tCount; ++tIndex) {
1.813 + const SkOpSpan& span = fTs[tIndex];
1.814 + if (!approximately_negative(span.fT - t)) {
1.815 + break;
1.816 + }
1.817 + if (approximately_negative(span.fT - t) && span.fOther == other
1.818 + && approximately_equal(span.fOtherT, otherT)) {
1.819 +#if DEBUG_ADD_T_PAIR
1.820 + SkDebugf("%s addTPair duplicate this=%d %1.9g other=%d %1.9g\n",
1.821 + __FUNCTION__, fID, t, other->fID, otherT);
1.822 +#endif
1.823 + return;
1.824 + }
1.825 + }
1.826 +#if DEBUG_ADD_T_PAIR
1.827 + SkDebugf("%s addTPair this=%d %1.9g other=%d %1.9g\n",
1.828 + __FUNCTION__, fID, t, other->fID, otherT);
1.829 +#endif
1.830 + int insertedAt = addT(other, pt, t);
1.831 + int otherInsertedAt = other->addT(this, pt, otherT);
1.832 + addOtherT(insertedAt, otherT, otherInsertedAt);
1.833 + other->addOtherT(otherInsertedAt, t, insertedAt);
1.834 + matchWindingValue(insertedAt, t, borrowWind);
1.835 + other->matchWindingValue(otherInsertedAt, otherT, borrowWind);
1.836 +}
1.837 +
1.838 +void SkOpSegment::addTwoAngles(int start, int end, SkTArray<SkOpAngle, true>* angles) const {
1.839 + // add edge leading into junction
1.840 + int min = SkMin32(end, start);
1.841 + if (fTs[min].fWindValue > 0 || fTs[min].fOppValue != 0) {
1.842 + addAngle(angles, end, start);
1.843 + }
1.844 + // add edge leading away from junction
1.845 + int step = SkSign32(end - start);
1.846 + int tIndex = nextExactSpan(end, step);
1.847 + min = SkMin32(end, tIndex);
1.848 + if (tIndex >= 0 && (fTs[min].fWindValue > 0 || fTs[min].fOppValue != 0)) {
1.849 + addAngle(angles, end, tIndex);
1.850 + }
1.851 +}
1.852 +
1.853 +bool SkOpSegment::betweenPoints(double midT, const SkPoint& pt1, const SkPoint& pt2) const {
1.854 + const SkPoint midPt = ptAtT(midT);
1.855 + SkPathOpsBounds bounds;
1.856 + bounds.set(pt1.fX, pt1.fY, pt2.fX, pt2.fY);
1.857 + bounds.sort();
1.858 + return bounds.almostContains(midPt);
1.859 +}
1.860 +
1.861 +bool SkOpSegment::betweenTs(int lesser, double testT, int greater) const {
1.862 + if (lesser > greater) {
1.863 + SkTSwap<int>(lesser, greater);
1.864 + }
1.865 + return approximately_between(fTs[lesser].fT, testT, fTs[greater].fT);
1.866 +}
1.867 +
1.868 +// note that this follows the same logic flow as active angle
1.869 +bool SkOpSegment::buildAngles(int index, SkTArray<SkOpAngle, true>* angles, bool allowOpp) const {
1.870 + double referenceT = fTs[index].fT;
1.871 + const SkPoint& referencePt = fTs[index].fPt;
1.872 + int lesser = index;
1.873 + while (--lesser >= 0 && (allowOpp || fTs[lesser].fOther->fOperand == fOperand)
1.874 + && (precisely_negative(referenceT - fTs[lesser].fT) || fTs[lesser].fTiny)) {
1.875 + buildAnglesInner(lesser, angles);
1.876 + }
1.877 + do {
1.878 + buildAnglesInner(index, angles);
1.879 + if (++index == fTs.count()) {
1.880 + break;
1.881 + }
1.882 + if (!allowOpp && fTs[index].fOther->fOperand != fOperand) {
1.883 + break;
1.884 + }
1.885 + if (fTs[index - 1].fTiny) {
1.886 + referenceT = fTs[index].fT;
1.887 + continue;
1.888 + }
1.889 + if (!precisely_negative(fTs[index].fT - referenceT) && fTs[index].fPt == referencePt) {
1.890 + // FIXME
1.891 + // testQuad8 generates the wrong output unless false is returned here. Other tests will
1.892 + // take this path although they aren't required to. This means that many go much slower
1.893 + // because of this sort fail.
1.894 + // SkDebugf("!!!\n");
1.895 + return false;
1.896 + }
1.897 + } while (precisely_negative(fTs[index].fT - referenceT));
1.898 + return true;
1.899 +}
1.900 +
1.901 +void SkOpSegment::buildAnglesInner(int index, SkTArray<SkOpAngle, true>* angles) const {
1.902 + const SkOpSpan* span = &fTs[index];
1.903 + SkOpSegment* other = span->fOther;
1.904 +// if there is only one live crossing, and no coincidence, continue
1.905 +// in the same direction
1.906 +// if there is coincidence, the only choice may be to reverse direction
1.907 + // find edge on either side of intersection
1.908 + int oIndex = span->fOtherIndex;
1.909 + // if done == -1, prior span has already been processed
1.910 + int step = 1;
1.911 + int next = other->nextExactSpan(oIndex, step);
1.912 + if (next < 0) {
1.913 + step = -step;
1.914 + next = other->nextExactSpan(oIndex, step);
1.915 + }
1.916 + // add candidate into and away from junction
1.917 + other->addTwoAngles(next, oIndex, angles);
1.918 +}
1.919 +
1.920 +int SkOpSegment::computeSum(int startIndex, int endIndex, SkOpAngle::IncludeType includeType,
1.921 + SkTArray<SkOpAngle, true>* angles, SkTArray<SkOpAngle*, true>* sorted) {
1.922 + addTwoAngles(startIndex, endIndex, angles);
1.923 + if (!buildAngles(endIndex, angles, includeType == SkOpAngle::kBinaryOpp)) {
1.924 + return SK_NaN32;
1.925 + }
1.926 + int angleCount = angles->count();
1.927 + // abort early before sorting if an unsortable (not an unorderable) angle is found
1.928 + if (includeType != SkOpAngle::kUnaryXor) {
1.929 + int firstIndex = -1;
1.930 + while (++firstIndex < angleCount) {
1.931 + const SkOpAngle& angle = (*angles)[firstIndex];
1.932 + if (angle.segment()->windSum(&angle) != SK_MinS32) {
1.933 + break;
1.934 + }
1.935 + }
1.936 + if (firstIndex == angleCount) {
1.937 + return SK_MinS32;
1.938 + }
1.939 + }
1.940 + bool sortable = SortAngles2(*angles, sorted);
1.941 +#if DEBUG_SORT_RAW
1.942 + if (sorted->count() > 0) {
1.943 + (*sorted)[0]->segment()->debugShowSort(__FUNCTION__, *sorted, 0, 0, 0, sortable);
1.944 + }
1.945 +#endif
1.946 + if (!sortable) {
1.947 + return SK_NaN32;
1.948 + }
1.949 + if (includeType == SkOpAngle::kUnaryXor) {
1.950 + return SK_MinS32;
1.951 + }
1.952 + // if all angles have a computed winding,
1.953 + // or if no adjacent angles are orderable,
1.954 + // or if adjacent orderable angles have no computed winding,
1.955 + // there's nothing to do
1.956 + // if two orderable angles are adjacent, and one has winding computed, transfer to the other
1.957 + const SkOpAngle* baseAngle = NULL;
1.958 + int last = angleCount;
1.959 + int finalInitialOrderable = -1;
1.960 + bool tryReverse = false;
1.961 + // look for counterclockwise transfers
1.962 + do {
1.963 + int index = 0;
1.964 + do {
1.965 + SkOpAngle* testAngle = (*sorted)[index];
1.966 + int testWinding = testAngle->segment()->windSum(testAngle);
1.967 + if (SK_MinS32 != testWinding && !testAngle->unorderable()) {
1.968 + baseAngle = testAngle;
1.969 + continue;
1.970 + }
1.971 + if (testAngle->unorderable()) {
1.972 + baseAngle = NULL;
1.973 + tryReverse = true;
1.974 + continue;
1.975 + }
1.976 + if (baseAngle) {
1.977 + ComputeOneSum(baseAngle, testAngle, includeType);
1.978 + baseAngle = SK_MinS32 != testAngle->segment()->windSum(testAngle) ? testAngle
1.979 + : NULL;
1.980 + tryReverse |= !baseAngle;
1.981 + continue;
1.982 + }
1.983 + if (finalInitialOrderable + 1 == index) {
1.984 + finalInitialOrderable = index;
1.985 + }
1.986 + } while (++index != last);
1.987 + if (finalInitialOrderable < 0) {
1.988 + break;
1.989 + }
1.990 + last = finalInitialOrderable + 1;
1.991 + finalInitialOrderable = -2; // make this always negative the second time through
1.992 + } while (baseAngle);
1.993 + if (tryReverse) {
1.994 + baseAngle = NULL;
1.995 + last = 0;
1.996 + finalInitialOrderable = angleCount;
1.997 + do {
1.998 + int index = angleCount;
1.999 + while (--index >= last) {
1.1000 + SkOpAngle* testAngle = (*sorted)[index];
1.1001 + int testWinding = testAngle->segment()->windSum(testAngle);
1.1002 + if (SK_MinS32 != testWinding) {
1.1003 + baseAngle = testAngle;
1.1004 + continue;
1.1005 + }
1.1006 + if (testAngle->unorderable()) {
1.1007 + baseAngle = NULL;
1.1008 + continue;
1.1009 + }
1.1010 + if (baseAngle) {
1.1011 + ComputeOneSumReverse(baseAngle, testAngle, includeType);
1.1012 + baseAngle = SK_MinS32 != testAngle->segment()->windSum(testAngle) ? testAngle
1.1013 + : NULL;
1.1014 + continue;
1.1015 + }
1.1016 + if (finalInitialOrderable - 1 == index) {
1.1017 + finalInitialOrderable = index;
1.1018 + }
1.1019 + }
1.1020 + if (finalInitialOrderable >= angleCount) {
1.1021 + break;
1.1022 + }
1.1023 + last = finalInitialOrderable;
1.1024 + finalInitialOrderable = angleCount + 1; // make this inactive 2nd time through
1.1025 + } while (baseAngle);
1.1026 + }
1.1027 + int minIndex = SkMin32(startIndex, endIndex);
1.1028 + return windSum(minIndex);
1.1029 +}
1.1030 +
1.1031 +void SkOpSegment::ComputeOneSum(const SkOpAngle* baseAngle, SkOpAngle* nextAngle,
1.1032 + SkOpAngle::IncludeType includeType) {
1.1033 + const SkOpSegment* baseSegment = baseAngle->segment();
1.1034 + int sumMiWinding = baseSegment->updateWindingReverse(baseAngle);
1.1035 + int sumSuWinding;
1.1036 + bool binary = includeType >= SkOpAngle::kBinarySingle;
1.1037 + if (binary) {
1.1038 + sumSuWinding = baseSegment->updateOppWindingReverse(baseAngle);
1.1039 + if (baseSegment->operand()) {
1.1040 + SkTSwap<int>(sumMiWinding, sumSuWinding);
1.1041 + }
1.1042 + }
1.1043 + SkOpSegment* nextSegment = nextAngle->segment();
1.1044 + int maxWinding, sumWinding;
1.1045 + SkOpSpan* last;
1.1046 + if (binary) {
1.1047 + int oppMaxWinding, oppSumWinding;
1.1048 + nextSegment->setUpWindings(nextAngle->start(), nextAngle->end(), &sumMiWinding,
1.1049 + &sumSuWinding, &maxWinding, &sumWinding, &oppMaxWinding, &oppSumWinding);
1.1050 + last = nextSegment->markAngle(maxWinding, sumWinding, oppMaxWinding, oppSumWinding,
1.1051 + nextAngle);
1.1052 + } else {
1.1053 + nextSegment->setUpWindings(nextAngle->start(), nextAngle->end(), &sumMiWinding,
1.1054 + &maxWinding, &sumWinding);
1.1055 + last = nextSegment->markAngle(maxWinding, sumWinding, nextAngle);
1.1056 + }
1.1057 + nextAngle->setLastMarked(last);
1.1058 +}
1.1059 +
1.1060 +void SkOpSegment::ComputeOneSumReverse(const SkOpAngle* baseAngle, SkOpAngle* nextAngle,
1.1061 + SkOpAngle::IncludeType includeType) {
1.1062 + const SkOpSegment* baseSegment = baseAngle->segment();
1.1063 + int sumMiWinding = baseSegment->updateWinding(baseAngle);
1.1064 + int sumSuWinding;
1.1065 + bool binary = includeType >= SkOpAngle::kBinarySingle;
1.1066 + if (binary) {
1.1067 + sumSuWinding = baseSegment->updateOppWinding(baseAngle);
1.1068 + if (baseSegment->operand()) {
1.1069 + SkTSwap<int>(sumMiWinding, sumSuWinding);
1.1070 + }
1.1071 + }
1.1072 + SkOpSegment* nextSegment = nextAngle->segment();
1.1073 + int maxWinding, sumWinding;
1.1074 + SkOpSpan* last;
1.1075 + if (binary) {
1.1076 + int oppMaxWinding, oppSumWinding;
1.1077 + nextSegment->setUpWindings(nextAngle->end(), nextAngle->start(), &sumMiWinding,
1.1078 + &sumSuWinding, &maxWinding, &sumWinding, &oppMaxWinding, &oppSumWinding);
1.1079 + last = nextSegment->markAngle(maxWinding, sumWinding, oppMaxWinding, oppSumWinding,
1.1080 + nextAngle);
1.1081 + } else {
1.1082 + nextSegment->setUpWindings(nextAngle->end(), nextAngle->start(), &sumMiWinding,
1.1083 + &maxWinding, &sumWinding);
1.1084 + last = nextSegment->markAngle(maxWinding, sumWinding, nextAngle);
1.1085 + }
1.1086 + nextAngle->setLastMarked(last);
1.1087 +}
1.1088 +
1.1089 +int SkOpSegment::crossedSpanY(const SkPoint& basePt, SkScalar* bestY, double* hitT,
1.1090 + bool* hitSomething, double mid, bool opp, bool current) const {
1.1091 + SkScalar bottom = fBounds.fBottom;
1.1092 + int bestTIndex = -1;
1.1093 + if (bottom <= *bestY) {
1.1094 + return bestTIndex;
1.1095 + }
1.1096 + SkScalar top = fBounds.fTop;
1.1097 + if (top >= basePt.fY) {
1.1098 + return bestTIndex;
1.1099 + }
1.1100 + if (fBounds.fLeft > basePt.fX) {
1.1101 + return bestTIndex;
1.1102 + }
1.1103 + if (fBounds.fRight < basePt.fX) {
1.1104 + return bestTIndex;
1.1105 + }
1.1106 + if (fBounds.fLeft == fBounds.fRight) {
1.1107 + // if vertical, and directly above test point, wait for another one
1.1108 + return AlmostEqualUlps(basePt.fX, fBounds.fLeft) ? SK_MinS32 : bestTIndex;
1.1109 + }
1.1110 + // intersect ray starting at basePt with edge
1.1111 + SkIntersections intersections;
1.1112 + // OPTIMIZE: use specialty function that intersects ray with curve,
1.1113 + // returning t values only for curve (we don't care about t on ray)
1.1114 + intersections.allowNear(false);
1.1115 + int pts = (intersections.*CurveVertical[SkPathOpsVerbToPoints(fVerb)])
1.1116 + (fPts, top, bottom, basePt.fX, false);
1.1117 + if (pts == 0 || (current && pts == 1)) {
1.1118 + return bestTIndex;
1.1119 + }
1.1120 + if (current) {
1.1121 + SkASSERT(pts > 1);
1.1122 + int closestIdx = 0;
1.1123 + double closest = fabs(intersections[0][0] - mid);
1.1124 + for (int idx = 1; idx < pts; ++idx) {
1.1125 + double test = fabs(intersections[0][idx] - mid);
1.1126 + if (closest > test) {
1.1127 + closestIdx = idx;
1.1128 + closest = test;
1.1129 + }
1.1130 + }
1.1131 + intersections.quickRemoveOne(closestIdx, --pts);
1.1132 + }
1.1133 + double bestT = -1;
1.1134 + for (int index = 0; index < pts; ++index) {
1.1135 + double foundT = intersections[0][index];
1.1136 + if (approximately_less_than_zero(foundT)
1.1137 + || approximately_greater_than_one(foundT)) {
1.1138 + continue;
1.1139 + }
1.1140 + SkScalar testY = (*CurvePointAtT[SkPathOpsVerbToPoints(fVerb)])(fPts, foundT).fY;
1.1141 + if (approximately_negative(testY - *bestY)
1.1142 + || approximately_negative(basePt.fY - testY)) {
1.1143 + continue;
1.1144 + }
1.1145 + if (pts > 1 && fVerb == SkPath::kLine_Verb) {
1.1146 + return SK_MinS32; // if the intersection is edge on, wait for another one
1.1147 + }
1.1148 + if (fVerb > SkPath::kLine_Verb) {
1.1149 + SkScalar dx = (*CurveSlopeAtT[SkPathOpsVerbToPoints(fVerb)])(fPts, foundT).fX;
1.1150 + if (approximately_zero(dx)) {
1.1151 + return SK_MinS32; // hit vertical, wait for another one
1.1152 + }
1.1153 + }
1.1154 + *bestY = testY;
1.1155 + bestT = foundT;
1.1156 + }
1.1157 + if (bestT < 0) {
1.1158 + return bestTIndex;
1.1159 + }
1.1160 + SkASSERT(bestT >= 0);
1.1161 + SkASSERT(bestT <= 1);
1.1162 + int start;
1.1163 + int end = 0;
1.1164 + do {
1.1165 + start = end;
1.1166 + end = nextSpan(start, 1);
1.1167 + } while (fTs[end].fT < bestT);
1.1168 + // FIXME: see next candidate for a better pattern to find the next start/end pair
1.1169 + while (start + 1 < end && fTs[start].fDone) {
1.1170 + ++start;
1.1171 + }
1.1172 + if (!isCanceled(start)) {
1.1173 + *hitT = bestT;
1.1174 + bestTIndex = start;
1.1175 + *hitSomething = true;
1.1176 + }
1.1177 + return bestTIndex;
1.1178 +}
1.1179 +
1.1180 +bool SkOpSegment::decrementSpan(SkOpSpan* span) {
1.1181 + SkASSERT(span->fWindValue > 0);
1.1182 + if (--(span->fWindValue) == 0) {
1.1183 + if (!span->fOppValue && !span->fDone) {
1.1184 + span->fDone = true;
1.1185 + ++fDoneSpans;
1.1186 + return true;
1.1187 + }
1.1188 + }
1.1189 + return false;
1.1190 +}
1.1191 +
1.1192 +bool SkOpSegment::bumpSpan(SkOpSpan* span, int windDelta, int oppDelta) {
1.1193 + SkASSERT(!span->fDone || span->fTiny || span->fSmall);
1.1194 + span->fWindValue += windDelta;
1.1195 + SkASSERT(span->fWindValue >= 0);
1.1196 + span->fOppValue += oppDelta;
1.1197 + SkASSERT(span->fOppValue >= 0);
1.1198 + if (fXor) {
1.1199 + span->fWindValue &= 1;
1.1200 + }
1.1201 + if (fOppXor) {
1.1202 + span->fOppValue &= 1;
1.1203 + }
1.1204 + if (!span->fWindValue && !span->fOppValue) {
1.1205 + span->fDone = true;
1.1206 + ++fDoneSpans;
1.1207 + return true;
1.1208 + }
1.1209 + return false;
1.1210 +}
1.1211 +
1.1212 +// look to see if the curve end intersects an intermediary that intersects the other
1.1213 +void SkOpSegment::checkEnds() {
1.1214 + debugValidate();
1.1215 + SkSTArray<kMissingSpanCount, MissingSpan, true> missingSpans;
1.1216 + int count = fTs.count();
1.1217 + for (int index = 0; index < count; ++index) {
1.1218 + const SkOpSpan& span = fTs[index];
1.1219 + double otherT = span.fOtherT;
1.1220 + if (otherT != 0 && otherT != 1) { // only check ends
1.1221 + continue;
1.1222 + }
1.1223 + const SkOpSegment* other = span.fOther;
1.1224 + // peek start/last describe the range of spans that match the other t of this span
1.1225 + int peekStart = span.fOtherIndex;
1.1226 + while (--peekStart >= 0 && other->fTs[peekStart].fT == otherT)
1.1227 + ;
1.1228 + int otherCount = other->fTs.count();
1.1229 + int peekLast = span.fOtherIndex;
1.1230 + while (++peekLast < otherCount && other->fTs[peekLast].fT == otherT)
1.1231 + ;
1.1232 + if (++peekStart == --peekLast) { // if there isn't a range, there's nothing to do
1.1233 + continue;
1.1234 + }
1.1235 + // t start/last describe the range of spans that match the t of this span
1.1236 + double t = span.fT;
1.1237 + double tBottom = -1;
1.1238 + int tStart = -1;
1.1239 + int tLast = count;
1.1240 + bool lastSmall = false;
1.1241 + double afterT = t;
1.1242 + for (int inner = 0; inner < count; ++inner) {
1.1243 + double innerT = fTs[inner].fT;
1.1244 + if (innerT <= t && innerT > tBottom) {
1.1245 + if (innerT < t || !lastSmall) {
1.1246 + tStart = inner - 1;
1.1247 + }
1.1248 + tBottom = innerT;
1.1249 + }
1.1250 + if (innerT > afterT) {
1.1251 + if (t == afterT && lastSmall) {
1.1252 + afterT = innerT;
1.1253 + } else {
1.1254 + tLast = inner;
1.1255 + break;
1.1256 + }
1.1257 + }
1.1258 + lastSmall = innerT <= t ? fTs[inner].fSmall : false;
1.1259 + }
1.1260 + for (int peekIndex = peekStart; peekIndex <= peekLast; ++peekIndex) {
1.1261 + if (peekIndex == span.fOtherIndex) { // skip the other span pointed to by this span
1.1262 + continue;
1.1263 + }
1.1264 + const SkOpSpan& peekSpan = other->fTs[peekIndex];
1.1265 + SkOpSegment* match = peekSpan.fOther;
1.1266 + if (match->done()) {
1.1267 + continue; // if the edge has already been eaten (likely coincidence), ignore it
1.1268 + }
1.1269 + const double matchT = peekSpan.fOtherT;
1.1270 + // see if any of the spans match the other spans
1.1271 + for (int tIndex = tStart + 1; tIndex < tLast; ++tIndex) {
1.1272 + const SkOpSpan& tSpan = fTs[tIndex];
1.1273 + if (tSpan.fOther == match) {
1.1274 + if (tSpan.fOtherT == matchT) {
1.1275 + goto nextPeekIndex;
1.1276 + }
1.1277 + double midT = (tSpan.fOtherT + matchT) / 2;
1.1278 + if (match->betweenPoints(midT, tSpan.fPt, peekSpan.fPt)) {
1.1279 + goto nextPeekIndex;
1.1280 + }
1.1281 + }
1.1282 + }
1.1283 + if (missingSpans.count() > 0) {
1.1284 + const MissingSpan& lastMissing = missingSpans.back();
1.1285 + if (lastMissing.fT == t
1.1286 + && lastMissing.fOther == match
1.1287 + && lastMissing.fOtherT == matchT) {
1.1288 + SkASSERT(lastMissing.fPt == peekSpan.fPt);
1.1289 + continue;
1.1290 + }
1.1291 + }
1.1292 +#if DEBUG_CHECK_ENDS
1.1293 + SkDebugf("%s id=%d missing t=%1.9g other=%d otherT=%1.9g pt=(%1.9g,%1.9g)\n",
1.1294 + __FUNCTION__, fID, t, match->fID, matchT, peekSpan.fPt.fX, peekSpan.fPt.fY);
1.1295 +#endif
1.1296 + // this segment is missing a entry that the other contains
1.1297 + // remember so we can add the missing one and recompute the indices
1.1298 + {
1.1299 + MissingSpan& missing = missingSpans.push_back();
1.1300 + SkDEBUGCODE(sk_bzero(&missing, sizeof(missing)));
1.1301 + missing.fT = t;
1.1302 + missing.fOther = match;
1.1303 + missing.fOtherT = matchT;
1.1304 + missing.fPt = peekSpan.fPt;
1.1305 + }
1.1306 + break;
1.1307 +nextPeekIndex:
1.1308 + ;
1.1309 + }
1.1310 + }
1.1311 + if (missingSpans.count() == 0) {
1.1312 + debugValidate();
1.1313 + return;
1.1314 + }
1.1315 + debugValidate();
1.1316 + int missingCount = missingSpans.count();
1.1317 + for (int index = 0; index < missingCount; ++index) {
1.1318 + MissingSpan& missing = missingSpans[index];
1.1319 + addTPair(missing.fT, missing.fOther, missing.fOtherT, false, missing.fPt);
1.1320 + }
1.1321 + fixOtherTIndex();
1.1322 + // OPTIMIZATION: this may fix indices more than once. Build an array of unique segments to
1.1323 + // avoid this
1.1324 + for (int index = 0; index < missingCount; ++index) {
1.1325 + missingSpans[index].fOther->fixOtherTIndex();
1.1326 + }
1.1327 + debugValidate();
1.1328 +}
1.1329 +
1.1330 +bool SkOpSegment::checkSmall(int index) const {
1.1331 + if (fTs[index].fSmall) {
1.1332 + return true;
1.1333 + }
1.1334 + double tBase = fTs[index].fT;
1.1335 + while (index > 0 && precisely_negative(tBase - fTs[--index].fT))
1.1336 + ;
1.1337 + return fTs[index].fSmall;
1.1338 +}
1.1339 +
1.1340 +// if pair of spans on either side of tiny have the same end point and mid point, mark
1.1341 +// them as parallel
1.1342 +// OPTIMIZATION : mark the segment to note that some span is tiny
1.1343 +void SkOpSegment::checkTiny() {
1.1344 + SkSTArray<kMissingSpanCount, MissingSpan, true> missingSpans;
1.1345 + SkOpSpan* thisSpan = fTs.begin() - 1;
1.1346 + const SkOpSpan* endSpan = fTs.end() - 1; // last can't be tiny
1.1347 + while (++thisSpan < endSpan) {
1.1348 + if (!thisSpan->fTiny) {
1.1349 + continue;
1.1350 + }
1.1351 + SkOpSpan* nextSpan = thisSpan + 1;
1.1352 + double thisT = thisSpan->fT;
1.1353 + double nextT = nextSpan->fT;
1.1354 + if (thisT == nextT) {
1.1355 + continue;
1.1356 + }
1.1357 + SkASSERT(thisT < nextT);
1.1358 + SkASSERT(thisSpan->fPt == nextSpan->fPt);
1.1359 + SkOpSegment* thisOther = thisSpan->fOther;
1.1360 + SkOpSegment* nextOther = nextSpan->fOther;
1.1361 + int oIndex = thisSpan->fOtherIndex;
1.1362 + for (int oStep = -1; oStep <= 1; oStep += 2) {
1.1363 + int oEnd = thisOther->nextExactSpan(oIndex, oStep);
1.1364 + if (oEnd < 0) {
1.1365 + continue;
1.1366 + }
1.1367 + const SkOpSpan& oSpan = thisOther->span(oEnd);
1.1368 + int nIndex = nextSpan->fOtherIndex;
1.1369 + for (int nStep = -1; nStep <= 1; nStep += 2) {
1.1370 + int nEnd = nextOther->nextExactSpan(nIndex, nStep);
1.1371 + if (nEnd < 0) {
1.1372 + continue;
1.1373 + }
1.1374 + const SkOpSpan& nSpan = nextOther->span(nEnd);
1.1375 + if (oSpan.fPt != nSpan.fPt) {
1.1376 + continue;
1.1377 + }
1.1378 + double oMidT = (thisSpan->fOtherT + oSpan.fT) / 2;
1.1379 + const SkPoint& oPt = thisOther->ptAtT(oMidT);
1.1380 + double nMidT = (nextSpan->fOtherT + nSpan.fT) / 2;
1.1381 + const SkPoint& nPt = nextOther->ptAtT(nMidT);
1.1382 + if (!AlmostEqualUlps(oPt, nPt)) {
1.1383 + continue;
1.1384 + }
1.1385 +#if DEBUG_CHECK_TINY
1.1386 + SkDebugf("%s [%d] add coincidence [%d] [%d]\n", __FUNCTION__, fID,
1.1387 + thisOther->fID, nextOther->fID);
1.1388 +#endif
1.1389 + // this segment is missing a entry that the other contains
1.1390 + // remember so we can add the missing one and recompute the indices
1.1391 + MissingSpan& missing = missingSpans.push_back();
1.1392 + SkDEBUGCODE(sk_bzero(&missing, sizeof(missing)));
1.1393 + missing.fSegment = thisOther;
1.1394 + missing.fT = thisSpan->fOtherT;
1.1395 + missing.fOther = nextOther;
1.1396 + missing.fOtherT = nextSpan->fOtherT;
1.1397 + missing.fPt = thisSpan->fPt;
1.1398 + }
1.1399 + }
1.1400 + }
1.1401 + int missingCount = missingSpans.count();
1.1402 + if (!missingCount) {
1.1403 + return;
1.1404 + }
1.1405 + for (int index = 0; index < missingCount; ++index) {
1.1406 + MissingSpan& missing = missingSpans[index];
1.1407 + missing.fSegment->addTPair(missing.fT, missing.fOther, missing.fOtherT, false, missing.fPt);
1.1408 + }
1.1409 + for (int index = 0; index < missingCount; ++index) {
1.1410 + MissingSpan& missing = missingSpans[index];
1.1411 + missing.fSegment->fixOtherTIndex();
1.1412 + missing.fOther->fixOtherTIndex();
1.1413 + }
1.1414 +}
1.1415 +
1.1416 +bool SkOpSegment::findCoincidentMatch(const SkOpSpan* span, const SkOpSegment* other, int oStart,
1.1417 + int oEnd, int step, SkPoint* startPt, SkPoint* endPt, double* endT) const {
1.1418 + SkASSERT(span->fT == 0 || span->fT == 1);
1.1419 + SkASSERT(span->fOtherT == 0 || span->fOtherT == 1);
1.1420 + const SkOpSpan* otherSpan = &other->span(oEnd);
1.1421 + double refT = otherSpan->fT;
1.1422 + const SkPoint& refPt = otherSpan->fPt;
1.1423 + const SkOpSpan* lastSpan = &other->span(step > 0 ? other->count() - 1 : 0);
1.1424 + do {
1.1425 + const SkOpSegment* match = span->fOther;
1.1426 + if (match == otherSpan->fOther) {
1.1427 + // find start of respective spans and see if both have winding
1.1428 + int startIndex, endIndex;
1.1429 + if (span->fOtherT == 1) {
1.1430 + endIndex = span->fOtherIndex;
1.1431 + startIndex = match->nextExactSpan(endIndex, -1);
1.1432 + } else {
1.1433 + startIndex = span->fOtherIndex;
1.1434 + endIndex = match->nextExactSpan(startIndex, 1);
1.1435 + }
1.1436 + const SkOpSpan& startSpan = match->span(startIndex);
1.1437 + if (startSpan.fWindValue != 0) {
1.1438 + // draw ray from endSpan.fPt perpendicular to end tangent and measure distance
1.1439 + // to other segment.
1.1440 + const SkOpSpan& endSpan = match->span(endIndex);
1.1441 + SkDLine ray;
1.1442 + SkVector dxdy;
1.1443 + if (span->fOtherT == 1) {
1.1444 + ray.fPts[0].set(startSpan.fPt);
1.1445 + dxdy = match->dxdy(startIndex);
1.1446 + } else {
1.1447 + ray.fPts[0].set(endSpan.fPt);
1.1448 + dxdy = match->dxdy(endIndex);
1.1449 + }
1.1450 + ray.fPts[1].fX = ray.fPts[0].fX + dxdy.fY;
1.1451 + ray.fPts[1].fY = ray.fPts[0].fY - dxdy.fX;
1.1452 + SkIntersections i;
1.1453 + int roots = (i.*CurveRay[SkPathOpsVerbToPoints(other->verb())])(other->pts(), ray);
1.1454 + for (int index = 0; index < roots; ++index) {
1.1455 + if (ray.fPts[0].approximatelyEqual(i.pt(index))) {
1.1456 + double matchMidT = (match->span(startIndex).fT
1.1457 + + match->span(endIndex).fT) / 2;
1.1458 + SkPoint matchMidPt = match->ptAtT(matchMidT);
1.1459 + double otherMidT = (i[0][index] + other->span(oStart).fT) / 2;
1.1460 + SkPoint otherMidPt = other->ptAtT(otherMidT);
1.1461 + if (SkDPoint::ApproximatelyEqual(matchMidPt, otherMidPt)) {
1.1462 + *startPt = startSpan.fPt;
1.1463 + *endPt = endSpan.fPt;
1.1464 + *endT = endSpan.fT;
1.1465 + return true;
1.1466 + }
1.1467 + }
1.1468 + }
1.1469 + }
1.1470 + return false;
1.1471 + }
1.1472 + if (otherSpan == lastSpan) {
1.1473 + break;
1.1474 + }
1.1475 + otherSpan += step;
1.1476 + } while (otherSpan->fT == refT || otherSpan->fPt == refPt);
1.1477 + return false;
1.1478 +}
1.1479 +
1.1480 +/*
1.1481 + The M and S variable name parts stand for the operators.
1.1482 + Mi stands for Minuend (see wiki subtraction, analogous to difference)
1.1483 + Su stands for Subtrahend
1.1484 + The Opp variable name part designates that the value is for the Opposite operator.
1.1485 + Opposite values result from combining coincident spans.
1.1486 + */
1.1487 +SkOpSegment* SkOpSegment::findNextOp(SkTDArray<SkOpSpan*>* chase, int* nextStart, int* nextEnd,
1.1488 + bool* unsortable, SkPathOp op, const int xorMiMask,
1.1489 + const int xorSuMask) {
1.1490 + const int startIndex = *nextStart;
1.1491 + const int endIndex = *nextEnd;
1.1492 + SkASSERT(startIndex != endIndex);
1.1493 + SkDEBUGCODE(const int count = fTs.count());
1.1494 + SkASSERT(startIndex < endIndex ? startIndex < count - 1 : startIndex > 0);
1.1495 + const int step = SkSign32(endIndex - startIndex);
1.1496 + const int end = nextExactSpan(startIndex, step);
1.1497 + SkASSERT(end >= 0);
1.1498 + SkOpSpan* endSpan = &fTs[end];
1.1499 + SkOpSegment* other;
1.1500 + if (isSimple(end)) {
1.1501 + // mark the smaller of startIndex, endIndex done, and all adjacent
1.1502 + // spans with the same T value (but not 'other' spans)
1.1503 +#if DEBUG_WINDING
1.1504 + SkDebugf("%s simple\n", __FUNCTION__);
1.1505 +#endif
1.1506 + int min = SkMin32(startIndex, endIndex);
1.1507 + if (fTs[min].fDone) {
1.1508 + return NULL;
1.1509 + }
1.1510 + markDoneBinary(min);
1.1511 + other = endSpan->fOther;
1.1512 + *nextStart = endSpan->fOtherIndex;
1.1513 + double startT = other->fTs[*nextStart].fT;
1.1514 + *nextEnd = *nextStart;
1.1515 + do {
1.1516 + *nextEnd += step;
1.1517 + } while (precisely_zero(startT - other->fTs[*nextEnd].fT));
1.1518 + SkASSERT(step < 0 ? *nextEnd >= 0 : *nextEnd < other->fTs.count());
1.1519 + if (other->isTiny(SkMin32(*nextStart, *nextEnd))) {
1.1520 + *unsortable = true;
1.1521 + return NULL;
1.1522 + }
1.1523 + return other;
1.1524 + }
1.1525 + // more than one viable candidate -- measure angles to find best
1.1526 + SkSTArray<SkOpAngle::kStackBasedCount, SkOpAngle, true> angles;
1.1527 + SkASSERT(startIndex - endIndex != 0);
1.1528 + SkASSERT((startIndex - endIndex < 0) ^ (step < 0));
1.1529 + SkSTArray<SkOpAngle::kStackBasedCount, SkOpAngle*, true> sorted;
1.1530 + int calcWinding = computeSum(startIndex, end, SkOpAngle::kBinaryOpp, &angles, &sorted);
1.1531 + bool sortable = calcWinding != SK_NaN32;
1.1532 + if (sortable && sorted.count() == 0) {
1.1533 + // if no edge has a computed winding sum, we can go no further
1.1534 + *unsortable = true;
1.1535 + return NULL;
1.1536 + }
1.1537 + int angleCount = angles.count();
1.1538 + int firstIndex = findStartingEdge(sorted, startIndex, end);
1.1539 + SkASSERT(!sortable || firstIndex >= 0);
1.1540 +#if DEBUG_SORT
1.1541 + debugShowSort(__FUNCTION__, sorted, firstIndex, sortable);
1.1542 +#endif
1.1543 + if (!sortable) {
1.1544 + *unsortable = true;
1.1545 + return NULL;
1.1546 + }
1.1547 + SkASSERT(sorted[firstIndex]->segment() == this);
1.1548 +#if DEBUG_WINDING
1.1549 + SkDebugf("%s firstIndex=[%d] sign=%d\n", __FUNCTION__, firstIndex,
1.1550 + sorted[firstIndex]->sign());
1.1551 +#endif
1.1552 + int sumMiWinding = updateWinding(endIndex, startIndex);
1.1553 + int sumSuWinding = updateOppWinding(endIndex, startIndex);
1.1554 + if (operand()) {
1.1555 + SkTSwap<int>(sumMiWinding, sumSuWinding);
1.1556 + }
1.1557 + int nextIndex = firstIndex + 1;
1.1558 + int lastIndex = firstIndex != 0 ? firstIndex : angleCount;
1.1559 + const SkOpAngle* foundAngle = NULL;
1.1560 + bool foundDone = false;
1.1561 + // iterate through the angle, and compute everyone's winding
1.1562 + SkOpSegment* nextSegment;
1.1563 + int activeCount = 0;
1.1564 + do {
1.1565 + SkASSERT(nextIndex != firstIndex);
1.1566 + if (nextIndex == angleCount) {
1.1567 + nextIndex = 0;
1.1568 + }
1.1569 + const SkOpAngle* nextAngle = sorted[nextIndex];
1.1570 + nextSegment = nextAngle->segment();
1.1571 + int maxWinding, sumWinding, oppMaxWinding, oppSumWinding;
1.1572 + bool activeAngle = nextSegment->activeOp(xorMiMask, xorSuMask, nextAngle->start(),
1.1573 + nextAngle->end(), op, &sumMiWinding, &sumSuWinding,
1.1574 + &maxWinding, &sumWinding, &oppMaxWinding, &oppSumWinding);
1.1575 + if (activeAngle) {
1.1576 + ++activeCount;
1.1577 + if (!foundAngle || (foundDone && activeCount & 1)) {
1.1578 + if (nextSegment->isTiny(nextAngle)) {
1.1579 + *unsortable = true;
1.1580 + return NULL;
1.1581 + }
1.1582 + foundAngle = nextAngle;
1.1583 + foundDone = nextSegment->done(nextAngle);
1.1584 + }
1.1585 + }
1.1586 + if (nextSegment->done()) {
1.1587 + continue;
1.1588 + }
1.1589 + if (nextSegment->isTiny(nextAngle)) {
1.1590 + continue;
1.1591 + }
1.1592 + if (!activeAngle) {
1.1593 + nextSegment->markAndChaseDoneBinary(nextAngle->start(), nextAngle->end());
1.1594 + }
1.1595 + SkOpSpan* last = nextAngle->lastMarked();
1.1596 + if (last) {
1.1597 + *chase->append() = last;
1.1598 +#if DEBUG_WINDING
1.1599 + SkDebugf("%s chase.append id=%d windSum=%d small=%d\n", __FUNCTION__,
1.1600 + last->fOther->fTs[last->fOtherIndex].fOther->debugID(), last->fWindSum,
1.1601 + last->fSmall);
1.1602 +#endif
1.1603 + }
1.1604 + } while (++nextIndex != lastIndex);
1.1605 + markDoneBinary(SkMin32(startIndex, endIndex));
1.1606 + if (!foundAngle) {
1.1607 + return NULL;
1.1608 + }
1.1609 + *nextStart = foundAngle->start();
1.1610 + *nextEnd = foundAngle->end();
1.1611 + nextSegment = foundAngle->segment();
1.1612 +#if DEBUG_WINDING
1.1613 + SkDebugf("%s from:[%d] to:[%d] start=%d end=%d\n",
1.1614 + __FUNCTION__, debugID(), nextSegment->debugID(), *nextStart, *nextEnd);
1.1615 + #endif
1.1616 + return nextSegment;
1.1617 +}
1.1618 +
1.1619 +SkOpSegment* SkOpSegment::findNextWinding(SkTDArray<SkOpSpan*>* chase, int* nextStart,
1.1620 + int* nextEnd, bool* unsortable) {
1.1621 + const int startIndex = *nextStart;
1.1622 + const int endIndex = *nextEnd;
1.1623 + SkASSERT(startIndex != endIndex);
1.1624 + SkDEBUGCODE(const int count = fTs.count());
1.1625 + SkASSERT(startIndex < endIndex ? startIndex < count - 1 : startIndex > 0);
1.1626 + const int step = SkSign32(endIndex - startIndex);
1.1627 + const int end = nextExactSpan(startIndex, step);
1.1628 + SkASSERT(end >= 0);
1.1629 + SkOpSpan* endSpan = &fTs[end];
1.1630 + SkOpSegment* other;
1.1631 + if (isSimple(end)) {
1.1632 + // mark the smaller of startIndex, endIndex done, and all adjacent
1.1633 + // spans with the same T value (but not 'other' spans)
1.1634 +#if DEBUG_WINDING
1.1635 + SkDebugf("%s simple\n", __FUNCTION__);
1.1636 +#endif
1.1637 + int min = SkMin32(startIndex, endIndex);
1.1638 + if (fTs[min].fDone) {
1.1639 + return NULL;
1.1640 + }
1.1641 + markDoneUnary(min);
1.1642 + other = endSpan->fOther;
1.1643 + *nextStart = endSpan->fOtherIndex;
1.1644 + double startT = other->fTs[*nextStart].fT;
1.1645 + *nextEnd = *nextStart;
1.1646 + do {
1.1647 + *nextEnd += step;
1.1648 + } while (precisely_zero(startT - other->fTs[*nextEnd].fT));
1.1649 + SkASSERT(step < 0 ? *nextEnd >= 0 : *nextEnd < other->fTs.count());
1.1650 + if (other->isTiny(SkMin32(*nextStart, *nextEnd))) {
1.1651 + *unsortable = true;
1.1652 + return NULL;
1.1653 + }
1.1654 + return other;
1.1655 + }
1.1656 + // more than one viable candidate -- measure angles to find best
1.1657 + SkSTArray<SkOpAngle::kStackBasedCount, SkOpAngle, true> angles;
1.1658 + SkASSERT(startIndex - endIndex != 0);
1.1659 + SkASSERT((startIndex - endIndex < 0) ^ (step < 0));
1.1660 + SkSTArray<SkOpAngle::kStackBasedCount, SkOpAngle*, true> sorted;
1.1661 + int calcWinding = computeSum(startIndex, end, SkOpAngle::kUnaryWinding, &angles, &sorted);
1.1662 + bool sortable = calcWinding != SK_NaN32;
1.1663 + int angleCount = angles.count();
1.1664 + int firstIndex = findStartingEdge(sorted, startIndex, end);
1.1665 + SkASSERT(!sortable || firstIndex >= 0);
1.1666 +#if DEBUG_SORT
1.1667 + debugShowSort(__FUNCTION__, sorted, firstIndex, sortable);
1.1668 +#endif
1.1669 + if (!sortable) {
1.1670 + *unsortable = true;
1.1671 + return NULL;
1.1672 + }
1.1673 + SkASSERT(sorted[firstIndex]->segment() == this);
1.1674 +#if DEBUG_WINDING
1.1675 + SkDebugf("%s firstIndex=[%d] sign=%d\n", __FUNCTION__, firstIndex,
1.1676 + sorted[firstIndex]->sign());
1.1677 +#endif
1.1678 + int sumWinding = updateWinding(endIndex, startIndex);
1.1679 + int nextIndex = firstIndex + 1;
1.1680 + int lastIndex = firstIndex != 0 ? firstIndex : angleCount;
1.1681 + const SkOpAngle* foundAngle = NULL;
1.1682 + bool foundDone = false;
1.1683 + // iterate through the angle, and compute everyone's winding
1.1684 + SkOpSegment* nextSegment;
1.1685 + int activeCount = 0;
1.1686 + do {
1.1687 + SkASSERT(nextIndex != firstIndex);
1.1688 + if (nextIndex == angleCount) {
1.1689 + nextIndex = 0;
1.1690 + }
1.1691 + const SkOpAngle* nextAngle = sorted[nextIndex];
1.1692 + nextSegment = nextAngle->segment();
1.1693 + int maxWinding;
1.1694 + bool activeAngle = nextSegment->activeWinding(nextAngle->start(), nextAngle->end(),
1.1695 + &maxWinding, &sumWinding);
1.1696 + if (activeAngle) {
1.1697 + ++activeCount;
1.1698 + if (!foundAngle || (foundDone && activeCount & 1)) {
1.1699 + if (nextSegment->isTiny(nextAngle)) {
1.1700 + *unsortable = true;
1.1701 + return NULL;
1.1702 + }
1.1703 + foundAngle = nextAngle;
1.1704 + foundDone = nextSegment->done(nextAngle);
1.1705 + }
1.1706 + }
1.1707 + if (nextSegment->done()) {
1.1708 + continue;
1.1709 + }
1.1710 + if (nextSegment->isTiny(nextAngle)) {
1.1711 + continue;
1.1712 + }
1.1713 + if (!activeAngle) {
1.1714 + nextSegment->markAndChaseDoneUnary(nextAngle->start(), nextAngle->end());
1.1715 + }
1.1716 + SkOpSpan* last = nextAngle->lastMarked();
1.1717 + if (last) {
1.1718 + *chase->append() = last;
1.1719 +#if DEBUG_WINDING
1.1720 + SkDebugf("%s chase.append id=%d windSum=%d small=%d\n", __FUNCTION__,
1.1721 + last->fOther->fTs[last->fOtherIndex].fOther->debugID(), last->fWindSum,
1.1722 + last->fSmall);
1.1723 +#endif
1.1724 + }
1.1725 + } while (++nextIndex != lastIndex);
1.1726 + markDoneUnary(SkMin32(startIndex, endIndex));
1.1727 + if (!foundAngle) {
1.1728 + return NULL;
1.1729 + }
1.1730 + *nextStart = foundAngle->start();
1.1731 + *nextEnd = foundAngle->end();
1.1732 + nextSegment = foundAngle->segment();
1.1733 +#if DEBUG_WINDING
1.1734 + SkDebugf("%s from:[%d] to:[%d] start=%d end=%d\n",
1.1735 + __FUNCTION__, debugID(), nextSegment->debugID(), *nextStart, *nextEnd);
1.1736 + #endif
1.1737 + return nextSegment;
1.1738 +}
1.1739 +
1.1740 +SkOpSegment* SkOpSegment::findNextXor(int* nextStart, int* nextEnd, bool* unsortable) {
1.1741 + const int startIndex = *nextStart;
1.1742 + const int endIndex = *nextEnd;
1.1743 + SkASSERT(startIndex != endIndex);
1.1744 + SkDEBUGCODE(int count = fTs.count());
1.1745 + SkASSERT(startIndex < endIndex ? startIndex < count - 1 : startIndex > 0);
1.1746 + int step = SkSign32(endIndex - startIndex);
1.1747 + int end = nextExactSpan(startIndex, step);
1.1748 + SkASSERT(end >= 0);
1.1749 + SkOpSpan* endSpan = &fTs[end];
1.1750 + SkOpSegment* other;
1.1751 + if (isSimple(end)) {
1.1752 +#if DEBUG_WINDING
1.1753 + SkDebugf("%s simple\n", __FUNCTION__);
1.1754 +#endif
1.1755 + int min = SkMin32(startIndex, endIndex);
1.1756 + if (fTs[min].fDone) {
1.1757 + return NULL;
1.1758 + }
1.1759 + markDone(min, 1);
1.1760 + other = endSpan->fOther;
1.1761 + *nextStart = endSpan->fOtherIndex;
1.1762 + double startT = other->fTs[*nextStart].fT;
1.1763 + // FIXME: I don't know why the logic here is difference from the winding case
1.1764 + SkDEBUGCODE(bool firstLoop = true;)
1.1765 + if ((approximately_less_than_zero(startT) && step < 0)
1.1766 + || (approximately_greater_than_one(startT) && step > 0)) {
1.1767 + step = -step;
1.1768 + SkDEBUGCODE(firstLoop = false;)
1.1769 + }
1.1770 + do {
1.1771 + *nextEnd = *nextStart;
1.1772 + do {
1.1773 + *nextEnd += step;
1.1774 + } while (precisely_zero(startT - other->fTs[*nextEnd].fT));
1.1775 + if (other->fTs[SkMin32(*nextStart, *nextEnd)].fWindValue) {
1.1776 + break;
1.1777 + }
1.1778 + SkASSERT(firstLoop);
1.1779 + SkDEBUGCODE(firstLoop = false;)
1.1780 + step = -step;
1.1781 + } while (true);
1.1782 + SkASSERT(step < 0 ? *nextEnd >= 0 : *nextEnd < other->fTs.count());
1.1783 + return other;
1.1784 + }
1.1785 + SkSTArray<SkOpAngle::kStackBasedCount, SkOpAngle, true> angles;
1.1786 + SkASSERT(startIndex - endIndex != 0);
1.1787 + SkASSERT((startIndex - endIndex < 0) ^ (step < 0));
1.1788 + SkSTArray<SkOpAngle::kStackBasedCount, SkOpAngle*, true> sorted;
1.1789 + int calcWinding = computeSum(startIndex, end, SkOpAngle::kUnaryXor, &angles, &sorted);
1.1790 + bool sortable = calcWinding != SK_NaN32;
1.1791 + int angleCount = angles.count();
1.1792 + int firstIndex = findStartingEdge(sorted, startIndex, end);
1.1793 + SkASSERT(!sortable || firstIndex >= 0);
1.1794 +#if DEBUG_SORT
1.1795 + debugShowSort(__FUNCTION__, sorted, firstIndex, 0, 0, sortable);
1.1796 +#endif
1.1797 + if (!sortable) {
1.1798 + *unsortable = true;
1.1799 + return NULL;
1.1800 + }
1.1801 + SkASSERT(sorted[firstIndex]->segment() == this);
1.1802 +#if DEBUG_WINDING
1.1803 + SkDebugf("%s firstIndex=[%d] sign=%d\n", __FUNCTION__, firstIndex,
1.1804 + sorted[firstIndex]->sign());
1.1805 +#endif
1.1806 + int nextIndex = firstIndex + 1;
1.1807 + int lastIndex = firstIndex != 0 ? firstIndex : angleCount;
1.1808 + const SkOpAngle* foundAngle = NULL;
1.1809 + bool foundDone = false;
1.1810 + SkOpSegment* nextSegment;
1.1811 + int activeCount = 0;
1.1812 + do {
1.1813 + SkASSERT(nextIndex != firstIndex);
1.1814 + if (nextIndex == angleCount) {
1.1815 + nextIndex = 0;
1.1816 + }
1.1817 + const SkOpAngle* nextAngle = sorted[nextIndex];
1.1818 + nextSegment = nextAngle->segment();
1.1819 + ++activeCount;
1.1820 + if (!foundAngle || (foundDone && activeCount & 1)) {
1.1821 + if (nextSegment->isTiny(nextAngle)) {
1.1822 + *unsortable = true;
1.1823 + return NULL;
1.1824 + }
1.1825 + foundAngle = nextAngle;
1.1826 + foundDone = nextSegment->done(nextAngle);
1.1827 + }
1.1828 + if (nextSegment->done()) {
1.1829 + continue;
1.1830 + }
1.1831 + } while (++nextIndex != lastIndex);
1.1832 + markDone(SkMin32(startIndex, endIndex), 1);
1.1833 + if (!foundAngle) {
1.1834 + return NULL;
1.1835 + }
1.1836 + *nextStart = foundAngle->start();
1.1837 + *nextEnd = foundAngle->end();
1.1838 + nextSegment = foundAngle->segment();
1.1839 +#if DEBUG_WINDING
1.1840 + SkDebugf("%s from:[%d] to:[%d] start=%d end=%d\n",
1.1841 + __FUNCTION__, debugID(), nextSegment->debugID(), *nextStart, *nextEnd);
1.1842 + #endif
1.1843 + return nextSegment;
1.1844 +}
1.1845 +
1.1846 +int SkOpSegment::findStartingEdge(const SkTArray<SkOpAngle*, true>& sorted, int start, int end) {
1.1847 + int angleCount = sorted.count();
1.1848 + int firstIndex = -1;
1.1849 + for (int angleIndex = 0; angleIndex < angleCount; ++angleIndex) {
1.1850 + const SkOpAngle* angle = sorted[angleIndex];
1.1851 + if (angle->segment() == this && angle->start() == end &&
1.1852 + angle->end() == start) {
1.1853 + firstIndex = angleIndex;
1.1854 + break;
1.1855 + }
1.1856 + }
1.1857 + return firstIndex;
1.1858 +}
1.1859 +
1.1860 +int SkOpSegment::findT(double t, const SkOpSegment* match) const {
1.1861 + int count = this->count();
1.1862 + for (int index = 0; index < count; ++index) {
1.1863 + const SkOpSpan& span = fTs[index];
1.1864 + if (span.fT == t && span.fOther == match) {
1.1865 + return index;
1.1866 + }
1.1867 + }
1.1868 + SkASSERT(0);
1.1869 + return -1;
1.1870 +}
1.1871 +
1.1872 +// FIXME: either:
1.1873 +// a) mark spans with either end unsortable as done, or
1.1874 +// b) rewrite findTop / findTopSegment / findTopContour to iterate further
1.1875 +// when encountering an unsortable span
1.1876 +
1.1877 +// OPTIMIZATION : for a pair of lines, can we compute points at T (cached)
1.1878 +// and use more concise logic like the old edge walker code?
1.1879 +// FIXME: this needs to deal with coincident edges
1.1880 +SkOpSegment* SkOpSegment::findTop(int* tIndexPtr, int* endIndexPtr, bool* unsortable,
1.1881 + bool onlySortable) {
1.1882 + // iterate through T intersections and return topmost
1.1883 + // topmost tangent from y-min to first pt is closer to horizontal
1.1884 + SkASSERT(!done());
1.1885 + int firstT = -1;
1.1886 + /* SkPoint topPt = */ activeLeftTop(onlySortable, &firstT);
1.1887 + if (firstT < 0) {
1.1888 + *unsortable = true;
1.1889 + firstT = 0;
1.1890 + while (fTs[firstT].fDone) {
1.1891 + SkASSERT(firstT < fTs.count());
1.1892 + ++firstT;
1.1893 + }
1.1894 + *tIndexPtr = firstT;
1.1895 + *endIndexPtr = nextExactSpan(firstT, 1);
1.1896 + return this;
1.1897 + }
1.1898 + // sort the edges to find the leftmost
1.1899 + int step = 1;
1.1900 + int end = nextSpan(firstT, step);
1.1901 + if (end == -1) {
1.1902 + step = -1;
1.1903 + end = nextSpan(firstT, step);
1.1904 + SkASSERT(end != -1);
1.1905 + }
1.1906 + // if the topmost T is not on end, or is three-way or more, find left
1.1907 + // look for left-ness from tLeft to firstT (matching y of other)
1.1908 + SkSTArray<SkOpAngle::kStackBasedCount, SkOpAngle, true> angles;
1.1909 + SkASSERT(firstT - end != 0);
1.1910 + addTwoAngles(end, firstT, &angles);
1.1911 + if (!buildAngles(firstT, &angles, true) && onlySortable) {
1.1912 +// *unsortable = true;
1.1913 +// return NULL;
1.1914 + }
1.1915 + SkSTArray<SkOpAngle::kStackBasedCount, SkOpAngle*, true> sorted;
1.1916 + bool sortable = SortAngles(angles, &sorted, SkOpSegment::kMayBeUnordered_SortAngleKind);
1.1917 + if (onlySortable && !sortable) {
1.1918 + *unsortable = true;
1.1919 + return NULL;
1.1920 + }
1.1921 + int first = SK_MaxS32;
1.1922 + SkScalar top = SK_ScalarMax;
1.1923 + int count = sorted.count();
1.1924 + for (int index = 0; index < count; ++index) {
1.1925 + const SkOpAngle* angle = sorted[index];
1.1926 + if (onlySortable && angle->unorderable()) {
1.1927 + continue;
1.1928 + }
1.1929 + SkOpSegment* next = angle->segment();
1.1930 + SkPathOpsBounds bounds;
1.1931 + next->subDivideBounds(angle->end(), angle->start(), &bounds);
1.1932 + if (approximately_greater(top, bounds.fTop)) {
1.1933 + top = bounds.fTop;
1.1934 + first = index;
1.1935 + }
1.1936 + }
1.1937 + SkASSERT(first < SK_MaxS32);
1.1938 +#if DEBUG_SORT // || DEBUG_SWAP_TOP
1.1939 + sorted[first]->segment()->debugShowSort(__FUNCTION__, sorted, first, 0, 0, sortable);
1.1940 +#endif
1.1941 + // skip edges that have already been processed
1.1942 + firstT = first - 1;
1.1943 + SkOpSegment* leftSegment;
1.1944 + do {
1.1945 + if (++firstT == count) {
1.1946 + firstT = 0;
1.1947 + }
1.1948 + const SkOpAngle* angle = sorted[firstT];
1.1949 + SkASSERT(!onlySortable || !angle->unsortable());
1.1950 + leftSegment = angle->segment();
1.1951 + *tIndexPtr = angle->end();
1.1952 + *endIndexPtr = angle->start();
1.1953 + } while (leftSegment->fTs[SkMin32(*tIndexPtr, *endIndexPtr)].fDone);
1.1954 + if (leftSegment->verb() >= SkPath::kQuad_Verb) {
1.1955 + const int tIndex = *tIndexPtr;
1.1956 + const int endIndex = *endIndexPtr;
1.1957 + if (!leftSegment->clockwise(tIndex, endIndex)) {
1.1958 + bool swap = !leftSegment->monotonicInY(tIndex, endIndex)
1.1959 + && !leftSegment->serpentine(tIndex, endIndex);
1.1960 + #if DEBUG_SWAP_TOP
1.1961 + SkDebugf("%s swap=%d serpentine=%d containedByEnds=%d monotonic=%d\n", __FUNCTION__,
1.1962 + swap,
1.1963 + leftSegment->serpentine(tIndex, endIndex),
1.1964 + leftSegment->controlsContainedByEnds(tIndex, endIndex),
1.1965 + leftSegment->monotonicInY(tIndex, endIndex));
1.1966 + #endif
1.1967 + if (swap) {
1.1968 + // FIXME: I doubt it makes sense to (necessarily) swap if the edge was not the first
1.1969 + // sorted but merely the first not already processed (i.e., not done)
1.1970 + SkTSwap(*tIndexPtr, *endIndexPtr);
1.1971 + }
1.1972 + }
1.1973 + }
1.1974 + SkASSERT(!leftSegment->fTs[SkMin32(*tIndexPtr, *endIndexPtr)].fTiny);
1.1975 + return leftSegment;
1.1976 +}
1.1977 +
1.1978 +// FIXME: not crazy about this
1.1979 +// when the intersections are performed, the other index is into an
1.1980 +// incomplete array. As the array grows, the indices become incorrect
1.1981 +// while the following fixes the indices up again, it isn't smart about
1.1982 +// skipping segments whose indices are already correct
1.1983 +// assuming we leave the code that wrote the index in the first place
1.1984 +// FIXME: if called after remove, this needs to correct tiny
1.1985 +void SkOpSegment::fixOtherTIndex() {
1.1986 + int iCount = fTs.count();
1.1987 + for (int i = 0; i < iCount; ++i) {
1.1988 + SkOpSpan& iSpan = fTs[i];
1.1989 + double oT = iSpan.fOtherT;
1.1990 + SkOpSegment* other = iSpan.fOther;
1.1991 + int oCount = other->fTs.count();
1.1992 + SkDEBUGCODE(iSpan.fOtherIndex = -1);
1.1993 + for (int o = 0; o < oCount; ++o) {
1.1994 + SkOpSpan& oSpan = other->fTs[o];
1.1995 + if (oT == oSpan.fT && this == oSpan.fOther && oSpan.fOtherT == iSpan.fT) {
1.1996 + iSpan.fOtherIndex = o;
1.1997 + oSpan.fOtherIndex = i;
1.1998 + break;
1.1999 + }
1.2000 + }
1.2001 + SkASSERT(iSpan.fOtherIndex >= 0);
1.2002 + }
1.2003 +}
1.2004 +
1.2005 +void SkOpSegment::init(const SkPoint pts[], SkPath::Verb verb, bool operand, bool evenOdd) {
1.2006 + fDoneSpans = 0;
1.2007 + fOperand = operand;
1.2008 + fXor = evenOdd;
1.2009 + fPts = pts;
1.2010 + fVerb = verb;
1.2011 +}
1.2012 +
1.2013 +void SkOpSegment::initWinding(int start, int end) {
1.2014 + int local = spanSign(start, end);
1.2015 + int oppLocal = oppSign(start, end);
1.2016 + (void) markAndChaseWinding(start, end, local, oppLocal);
1.2017 + // OPTIMIZATION: the reverse mark and chase could skip the first marking
1.2018 + (void) markAndChaseWinding(end, start, local, oppLocal);
1.2019 +}
1.2020 +
1.2021 +/*
1.2022 +when we start with a vertical intersect, we try to use the dx to determine if the edge is to
1.2023 +the left or the right of vertical. This determines if we need to add the span's
1.2024 +sign or not. However, this isn't enough.
1.2025 +If the supplied sign (winding) is zero, then we didn't hit another vertical span, so dx is needed.
1.2026 +If there was a winding, then it may or may not need adjusting. If the span the winding was borrowed
1.2027 +from has the same x direction as this span, the winding should change. If the dx is opposite, then
1.2028 +the same winding is shared by both.
1.2029 +*/
1.2030 +void SkOpSegment::initWinding(int start, int end, double tHit, int winding, SkScalar hitDx,
1.2031 + int oppWind, SkScalar hitOppDx) {
1.2032 + SkASSERT(hitDx || !winding);
1.2033 + SkScalar dx = (*CurveSlopeAtT[SkPathOpsVerbToPoints(fVerb)])(fPts, tHit).fX;
1.2034 + SkASSERT(dx);
1.2035 + int windVal = windValue(SkMin32(start, end));
1.2036 +#if DEBUG_WINDING_AT_T
1.2037 + SkDebugf("%s oldWinding=%d hitDx=%c dx=%c windVal=%d", __FUNCTION__, winding,
1.2038 + hitDx ? hitDx > 0 ? '+' : '-' : '0', dx > 0 ? '+' : '-', windVal);
1.2039 +#endif
1.2040 + if (!winding) {
1.2041 + winding = dx < 0 ? windVal : -windVal;
1.2042 + } else if (winding * dx < 0) {
1.2043 + int sideWind = winding + (dx < 0 ? windVal : -windVal);
1.2044 + if (abs(winding) < abs(sideWind)) {
1.2045 + winding = sideWind;
1.2046 + }
1.2047 + }
1.2048 +#if DEBUG_WINDING_AT_T
1.2049 + SkDebugf(" winding=%d\n", winding);
1.2050 +#endif
1.2051 + SkDEBUGCODE(int oppLocal = oppSign(start, end));
1.2052 + SkASSERT(hitOppDx || !oppWind || !oppLocal);
1.2053 + int oppWindVal = oppValue(SkMin32(start, end));
1.2054 + if (!oppWind) {
1.2055 + oppWind = dx < 0 ? oppWindVal : -oppWindVal;
1.2056 + } else if (hitOppDx * dx >= 0) {
1.2057 + int oppSideWind = oppWind + (dx < 0 ? oppWindVal : -oppWindVal);
1.2058 + if (abs(oppWind) < abs(oppSideWind)) {
1.2059 + oppWind = oppSideWind;
1.2060 + }
1.2061 + }
1.2062 + (void) markAndChaseWinding(start, end, winding, oppWind);
1.2063 + // OPTIMIZATION: the reverse mark and chase could skip the first marking
1.2064 + (void) markAndChaseWinding(end, start, winding, oppWind);
1.2065 +}
1.2066 +
1.2067 +// OPTIMIZE: successive calls could start were the last leaves off
1.2068 +// or calls could specialize to walk forwards or backwards
1.2069 +bool SkOpSegment::isMissing(double startT, const SkPoint& pt) const {
1.2070 + size_t tCount = fTs.count();
1.2071 + for (size_t index = 0; index < tCount; ++index) {
1.2072 + const SkOpSpan& span = fTs[index];
1.2073 + if (approximately_zero(startT - span.fT) && pt == span.fPt) {
1.2074 + return false;
1.2075 + }
1.2076 + }
1.2077 + return true;
1.2078 +}
1.2079 +
1.2080 +bool SkOpSegment::isSimple(int end) const {
1.2081 + int count = fTs.count();
1.2082 + if (count == 2) {
1.2083 + return true;
1.2084 + }
1.2085 + double t = fTs[end].fT;
1.2086 + if (approximately_less_than_zero(t)) {
1.2087 + return !approximately_less_than_zero(fTs[1].fT);
1.2088 + }
1.2089 + if (approximately_greater_than_one(t)) {
1.2090 + return !approximately_greater_than_one(fTs[count - 2].fT);
1.2091 + }
1.2092 + return false;
1.2093 +}
1.2094 +
1.2095 +bool SkOpSegment::isTiny(const SkOpAngle* angle) const {
1.2096 + int start = angle->start();
1.2097 + int end = angle->end();
1.2098 + const SkOpSpan& mSpan = fTs[SkMin32(start, end)];
1.2099 + return mSpan.fTiny;
1.2100 +}
1.2101 +
1.2102 +bool SkOpSegment::isTiny(int index) const {
1.2103 + return fTs[index].fTiny;
1.2104 +}
1.2105 +
1.2106 +// look pair of active edges going away from coincident edge
1.2107 +// one of them should be the continuation of other
1.2108 +// if both are active, look to see if they both the connect to another coincident pair
1.2109 +// if one at least one is a line, then make the pair coincident
1.2110 +// if neither is a line, test for coincidence
1.2111 +bool SkOpSegment::joinCoincidence(SkOpSegment* other, double otherT, int step,
1.2112 + bool cancel) {
1.2113 + int otherTIndex = other->findT(otherT, this);
1.2114 + int next = other->nextExactSpan(otherTIndex, step);
1.2115 + int otherMin = SkTMin(otherTIndex, next);
1.2116 + int otherWind = other->span(otherMin).fWindValue;
1.2117 + if (otherWind == 0) {
1.2118 + return false;
1.2119 + }
1.2120 + SkASSERT(next >= 0);
1.2121 + int tIndex = 0;
1.2122 + do {
1.2123 + SkOpSpan* test = &fTs[tIndex];
1.2124 + SkASSERT(test->fT == 0);
1.2125 + if (test->fOther == other || test->fOtherT != 1) {
1.2126 + continue;
1.2127 + }
1.2128 + SkPoint startPt, endPt;
1.2129 + double endT;
1.2130 + if (findCoincidentMatch(test, other, otherTIndex, next, step, &startPt, &endPt, &endT)) {
1.2131 + SkOpSegment* match = test->fOther;
1.2132 + if (cancel) {
1.2133 + match->addTCancel(startPt, endPt, other);
1.2134 + } else {
1.2135 + match->addTCoincident(startPt, endPt, endT, other);
1.2136 + }
1.2137 + return true;
1.2138 + }
1.2139 + } while (fTs[++tIndex].fT == 0);
1.2140 + return false;
1.2141 +}
1.2142 +
1.2143 +// this span is excluded by the winding rule -- chase the ends
1.2144 +// as long as they are unambiguous to mark connections as done
1.2145 +// and give them the same winding value
1.2146 +
1.2147 +SkOpSpan* SkOpSegment::markAndChaseDoneBinary(int index, int endIndex) {
1.2148 + int step = SkSign32(endIndex - index);
1.2149 + int min = SkMin32(index, endIndex);
1.2150 + markDoneBinary(min);
1.2151 + SkOpSpan* last;
1.2152 + SkOpSegment* other = this;
1.2153 + while ((other = other->nextChase(&index, step, &min, &last))) {
1.2154 + if (other->done()) {
1.2155 + return NULL;
1.2156 + }
1.2157 + other->markDoneBinary(min);
1.2158 + }
1.2159 + return last;
1.2160 +}
1.2161 +
1.2162 +SkOpSpan* SkOpSegment::markAndChaseDoneUnary(int index, int endIndex) {
1.2163 + int step = SkSign32(endIndex - index);
1.2164 + int min = SkMin32(index, endIndex);
1.2165 + markDoneUnary(min);
1.2166 + SkOpSpan* last;
1.2167 + SkOpSegment* other = this;
1.2168 + while ((other = other->nextChase(&index, step, &min, &last))) {
1.2169 + if (other->done()) {
1.2170 + return NULL;
1.2171 + }
1.2172 + other->markDoneUnary(min);
1.2173 + }
1.2174 + return last;
1.2175 +}
1.2176 +
1.2177 +SkOpSpan* SkOpSegment::markAndChaseWinding(const SkOpAngle* angle, const int winding) {
1.2178 + int index = angle->start();
1.2179 + int endIndex = angle->end();
1.2180 + int step = SkSign32(endIndex - index);
1.2181 + int min = SkMin32(index, endIndex);
1.2182 + markWinding(min, winding);
1.2183 + SkOpSpan* last;
1.2184 + SkOpSegment* other = this;
1.2185 + while ((other = other->nextChase(&index, step, &min, &last))) {
1.2186 + if (other->fTs[min].fWindSum != SK_MinS32) {
1.2187 + SkASSERT(other->fTs[min].fWindSum == winding);
1.2188 + return NULL;
1.2189 + }
1.2190 + other->markWinding(min, winding);
1.2191 + }
1.2192 + return last;
1.2193 +}
1.2194 +
1.2195 +SkOpSpan* SkOpSegment::markAndChaseWinding(int index, int endIndex, int winding, int oppWinding) {
1.2196 + int min = SkMin32(index, endIndex);
1.2197 + int step = SkSign32(endIndex - index);
1.2198 + markWinding(min, winding, oppWinding);
1.2199 + SkOpSpan* last;
1.2200 + SkOpSegment* other = this;
1.2201 + while ((other = other->nextChase(&index, step, &min, &last))) {
1.2202 + if (other->fTs[min].fWindSum != SK_MinS32) {
1.2203 + SkASSERT(other->fTs[min].fWindSum == winding || other->fTs[min].fLoop);
1.2204 + return NULL;
1.2205 + }
1.2206 + other->markWinding(min, winding, oppWinding);
1.2207 + }
1.2208 + return last;
1.2209 +}
1.2210 +
1.2211 +SkOpSpan* SkOpSegment::markAndChaseWinding(const SkOpAngle* angle, int winding, int oppWinding) {
1.2212 + int start = angle->start();
1.2213 + int end = angle->end();
1.2214 + return markAndChaseWinding(start, end, winding, oppWinding);
1.2215 +}
1.2216 +
1.2217 +SkOpSpan* SkOpSegment::markAngle(int maxWinding, int sumWinding, const SkOpAngle* angle) {
1.2218 + SkASSERT(angle->segment() == this);
1.2219 + if (UseInnerWinding(maxWinding, sumWinding)) {
1.2220 + maxWinding = sumWinding;
1.2221 + }
1.2222 + SkOpSpan* last = markAndChaseWinding(angle, maxWinding);
1.2223 +#if DEBUG_WINDING
1.2224 + if (last) {
1.2225 + SkDebugf("%s last id=%d windSum=", __FUNCTION__,
1.2226 + last->fOther->fTs[last->fOtherIndex].fOther->debugID());
1.2227 + SkPathOpsDebug::WindingPrintf(last->fWindSum);
1.2228 + SkDebugf(" small=%d\n", last->fSmall);
1.2229 + }
1.2230 +#endif
1.2231 + return last;
1.2232 +}
1.2233 +
1.2234 +SkOpSpan* SkOpSegment::markAngle(int maxWinding, int sumWinding, int oppMaxWinding,
1.2235 + int oppSumWinding, const SkOpAngle* angle) {
1.2236 + SkASSERT(angle->segment() == this);
1.2237 + if (UseInnerWinding(maxWinding, sumWinding)) {
1.2238 + maxWinding = sumWinding;
1.2239 + }
1.2240 + if (oppMaxWinding != oppSumWinding && UseInnerWinding(oppMaxWinding, oppSumWinding)) {
1.2241 + oppMaxWinding = oppSumWinding;
1.2242 + }
1.2243 + SkOpSpan* last = markAndChaseWinding(angle, maxWinding, oppMaxWinding);
1.2244 +#if DEBUG_WINDING
1.2245 + if (last) {
1.2246 + SkDebugf("%s last id=%d windSum=", __FUNCTION__,
1.2247 + last->fOther->fTs[last->fOtherIndex].fOther->debugID());
1.2248 + SkPathOpsDebug::WindingPrintf(last->fWindSum);
1.2249 + SkDebugf(" small=%d\n", last->fSmall);
1.2250 + }
1.2251 +#endif
1.2252 + return last;
1.2253 +}
1.2254 +
1.2255 +// FIXME: this should also mark spans with equal (x,y)
1.2256 +// This may be called when the segment is already marked done. While this
1.2257 +// wastes time, it shouldn't do any more than spin through the T spans.
1.2258 +// OPTIMIZATION: abort on first done found (assuming that this code is
1.2259 +// always called to mark segments done).
1.2260 +void SkOpSegment::markDone(int index, int winding) {
1.2261 + // SkASSERT(!done());
1.2262 + SkASSERT(winding);
1.2263 + double referenceT = fTs[index].fT;
1.2264 + int lesser = index;
1.2265 + while (--lesser >= 0 && precisely_negative(referenceT - fTs[lesser].fT)) {
1.2266 + markOneDone(__FUNCTION__, lesser, winding);
1.2267 + }
1.2268 + do {
1.2269 + markOneDone(__FUNCTION__, index, winding);
1.2270 + } while (++index < fTs.count() && precisely_negative(fTs[index].fT - referenceT));
1.2271 +}
1.2272 +
1.2273 +void SkOpSegment::markDoneBinary(int index) {
1.2274 + double referenceT = fTs[index].fT;
1.2275 + int lesser = index;
1.2276 + while (--lesser >= 0 && precisely_negative(referenceT - fTs[lesser].fT)) {
1.2277 + markOneDoneBinary(__FUNCTION__, lesser);
1.2278 + }
1.2279 + do {
1.2280 + markOneDoneBinary(__FUNCTION__, index);
1.2281 + } while (++index < fTs.count() && precisely_negative(fTs[index].fT - referenceT));
1.2282 +}
1.2283 +
1.2284 +void SkOpSegment::markDoneUnary(int index) {
1.2285 + double referenceT = fTs[index].fT;
1.2286 + int lesser = index;
1.2287 + while (--lesser >= 0 && precisely_negative(referenceT - fTs[lesser].fT)) {
1.2288 + markOneDoneUnary(__FUNCTION__, lesser);
1.2289 + }
1.2290 + do {
1.2291 + markOneDoneUnary(__FUNCTION__, index);
1.2292 + } while (++index < fTs.count() && precisely_negative(fTs[index].fT - referenceT));
1.2293 +}
1.2294 +
1.2295 +void SkOpSegment::markOneDone(const char* funName, int tIndex, int winding) {
1.2296 + SkOpSpan* span = markOneWinding(funName, tIndex, winding);
1.2297 + if (!span) {
1.2298 + return;
1.2299 + }
1.2300 + span->fDone = true;
1.2301 + fDoneSpans++;
1.2302 +}
1.2303 +
1.2304 +void SkOpSegment::markOneDoneBinary(const char* funName, int tIndex) {
1.2305 + SkOpSpan* span = verifyOneWinding(funName, tIndex);
1.2306 + if (!span) {
1.2307 + return;
1.2308 + }
1.2309 + span->fDone = true;
1.2310 + fDoneSpans++;
1.2311 +}
1.2312 +
1.2313 +void SkOpSegment::markOneDoneUnary(const char* funName, int tIndex) {
1.2314 + SkOpSpan* span = verifyOneWindingU(funName, tIndex);
1.2315 + if (!span) {
1.2316 + return;
1.2317 + }
1.2318 + span->fDone = true;
1.2319 + fDoneSpans++;
1.2320 +}
1.2321 +
1.2322 +SkOpSpan* SkOpSegment::markOneWinding(const char* funName, int tIndex, int winding) {
1.2323 + SkOpSpan& span = fTs[tIndex];
1.2324 + if (span.fDone) {
1.2325 + return NULL;
1.2326 + }
1.2327 +#if DEBUG_MARK_DONE
1.2328 + debugShowNewWinding(funName, span, winding);
1.2329 +#endif
1.2330 + SkASSERT(span.fWindSum == SK_MinS32 || span.fWindSum == winding);
1.2331 + SkASSERT(abs(winding) <= SkPathOpsDebug::gMaxWindSum);
1.2332 + span.fWindSum = winding;
1.2333 + return &span;
1.2334 +}
1.2335 +
1.2336 +SkOpSpan* SkOpSegment::markOneWinding(const char* funName, int tIndex, int winding,
1.2337 + int oppWinding) {
1.2338 + SkOpSpan& span = fTs[tIndex];
1.2339 + if (span.fDone && !span.fSmall) {
1.2340 + return NULL;
1.2341 + }
1.2342 +#if DEBUG_MARK_DONE
1.2343 + debugShowNewWinding(funName, span, winding, oppWinding);
1.2344 +#endif
1.2345 + SkASSERT(span.fWindSum == SK_MinS32 || span.fWindSum == winding);
1.2346 + SkASSERT(abs(winding) <= SkPathOpsDebug::gMaxWindSum);
1.2347 + span.fWindSum = winding;
1.2348 + SkASSERT(span.fOppSum == SK_MinS32 || span.fOppSum == oppWinding);
1.2349 + SkASSERT(abs(oppWinding) <= SkPathOpsDebug::gMaxWindSum);
1.2350 + span.fOppSum = oppWinding;
1.2351 + return &span;
1.2352 +}
1.2353 +
1.2354 +// from http://stackoverflow.com/questions/1165647/how-to-determine-if-a-list-of-polygon-points-are-in-clockwise-order
1.2355 +bool SkOpSegment::clockwise(int tStart, int tEnd) const {
1.2356 + SkASSERT(fVerb != SkPath::kLine_Verb);
1.2357 + SkPoint edge[4];
1.2358 + subDivide(tStart, tEnd, edge);
1.2359 + int points = SkPathOpsVerbToPoints(fVerb);
1.2360 + double sum = (edge[0].fX - edge[points].fX) * (edge[0].fY + edge[points].fY);
1.2361 + if (fVerb == SkPath::kCubic_Verb) {
1.2362 + SkScalar lesser = SkTMin<SkScalar>(edge[0].fY, edge[3].fY);
1.2363 + if (edge[1].fY < lesser && edge[2].fY < lesser) {
1.2364 + SkDLine tangent1 = {{ {edge[0].fX, edge[0].fY}, {edge[1].fX, edge[1].fY} }};
1.2365 + SkDLine tangent2 = {{ {edge[2].fX, edge[2].fY}, {edge[3].fX, edge[3].fY} }};
1.2366 + if (SkIntersections::Test(tangent1, tangent2)) {
1.2367 + SkPoint topPt = cubic_top(fPts, fTs[tStart].fT, fTs[tEnd].fT);
1.2368 + sum += (topPt.fX - edge[0].fX) * (topPt.fY + edge[0].fY);
1.2369 + sum += (edge[3].fX - topPt.fX) * (edge[3].fY + topPt.fY);
1.2370 + return sum <= 0;
1.2371 + }
1.2372 + }
1.2373 + }
1.2374 + for (int idx = 0; idx < points; ++idx){
1.2375 + sum += (edge[idx + 1].fX - edge[idx].fX) * (edge[idx + 1].fY + edge[idx].fY);
1.2376 + }
1.2377 + return sum <= 0;
1.2378 +}
1.2379 +
1.2380 +bool SkOpSegment::monotonicInY(int tStart, int tEnd) const {
1.2381 + if (fVerb == SkPath::kLine_Verb) {
1.2382 + return false;
1.2383 + }
1.2384 + if (fVerb == SkPath::kQuad_Verb) {
1.2385 + SkDQuad dst = SkDQuad::SubDivide(fPts, fTs[tStart].fT, fTs[tEnd].fT);
1.2386 + return dst.monotonicInY();
1.2387 + }
1.2388 + SkASSERT(fVerb == SkPath::kCubic_Verb);
1.2389 + SkDCubic dst = SkDCubic::SubDivide(fPts, fTs[tStart].fT, fTs[tEnd].fT);
1.2390 + return dst.monotonicInY();
1.2391 +}
1.2392 +
1.2393 +bool SkOpSegment::serpentine(int tStart, int tEnd) const {
1.2394 + if (fVerb != SkPath::kCubic_Verb) {
1.2395 + return false;
1.2396 + }
1.2397 + SkDCubic dst = SkDCubic::SubDivide(fPts, fTs[tStart].fT, fTs[tEnd].fT);
1.2398 + return dst.serpentine();
1.2399 +}
1.2400 +
1.2401 +SkOpSpan* SkOpSegment::verifyOneWinding(const char* funName, int tIndex) {
1.2402 + SkOpSpan& span = fTs[tIndex];
1.2403 + if (span.fDone) {
1.2404 + return NULL;
1.2405 + }
1.2406 +#if DEBUG_MARK_DONE
1.2407 + debugShowNewWinding(funName, span, span.fWindSum, span.fOppSum);
1.2408 +#endif
1.2409 +// If the prior angle in the sort is unorderable, the winding sum may not be computable.
1.2410 +// To enable the assert, the 'prior is unorderable' state could be
1.2411 +// piped down to this test, but not sure it's worth it.
1.2412 +// (Once the sort order is stored in the span, this test may be feasible.)
1.2413 +// SkASSERT(span.fWindSum != SK_MinS32);
1.2414 +// SkASSERT(span.fOppSum != SK_MinS32);
1.2415 + return &span;
1.2416 +}
1.2417 +
1.2418 +SkOpSpan* SkOpSegment::verifyOneWindingU(const char* funName, int tIndex) {
1.2419 + SkOpSpan& span = fTs[tIndex];
1.2420 + if (span.fDone) {
1.2421 + return NULL;
1.2422 + }
1.2423 +#if DEBUG_MARK_DONE
1.2424 + debugShowNewWinding(funName, span, span.fWindSum);
1.2425 +#endif
1.2426 +// If the prior angle in the sort is unorderable, the winding sum may not be computable.
1.2427 +// To enable the assert, the 'prior is unorderable' state could be
1.2428 +// piped down to this test, but not sure it's worth it.
1.2429 +// (Once the sort order is stored in the span, this test may be feasible.)
1.2430 +// SkASSERT(span.fWindSum != SK_MinS32);
1.2431 + return &span;
1.2432 +}
1.2433 +
1.2434 +// note that just because a span has one end that is unsortable, that's
1.2435 +// not enough to mark it done. The other end may be sortable, allowing the
1.2436 +// span to be added.
1.2437 +// FIXME: if abs(start - end) > 1, mark intermediates as unsortable on both ends
1.2438 +void SkOpSegment::markUnsortable(int start, int end) {
1.2439 + SkOpSpan* span = &fTs[start];
1.2440 + if (start < end) {
1.2441 +#if DEBUG_UNSORTABLE
1.2442 + debugShowNewWinding(__FUNCTION__, *span, 0);
1.2443 +#endif
1.2444 + span->fUnsortableStart = true;
1.2445 + } else {
1.2446 + --span;
1.2447 +#if DEBUG_UNSORTABLE
1.2448 + debugShowNewWinding(__FUNCTION__, *span, 0);
1.2449 +#endif
1.2450 + span->fUnsortableEnd = true;
1.2451 + }
1.2452 + if (!span->fUnsortableStart || !span->fUnsortableEnd || span->fDone) {
1.2453 + return;
1.2454 + }
1.2455 + span->fDone = true;
1.2456 + fDoneSpans++;
1.2457 +}
1.2458 +
1.2459 +void SkOpSegment::markWinding(int index, int winding) {
1.2460 +// SkASSERT(!done());
1.2461 + SkASSERT(winding);
1.2462 + double referenceT = fTs[index].fT;
1.2463 + int lesser = index;
1.2464 + while (--lesser >= 0 && precisely_negative(referenceT - fTs[lesser].fT)) {
1.2465 + markOneWinding(__FUNCTION__, lesser, winding);
1.2466 + }
1.2467 + do {
1.2468 + markOneWinding(__FUNCTION__, index, winding);
1.2469 + } while (++index < fTs.count() && precisely_negative(fTs[index].fT - referenceT));
1.2470 +}
1.2471 +
1.2472 +void SkOpSegment::markWinding(int index, int winding, int oppWinding) {
1.2473 +// SkASSERT(!done());
1.2474 + SkASSERT(winding || oppWinding);
1.2475 + double referenceT = fTs[index].fT;
1.2476 + int lesser = index;
1.2477 + while (--lesser >= 0 && precisely_negative(referenceT - fTs[lesser].fT)) {
1.2478 + markOneWinding(__FUNCTION__, lesser, winding, oppWinding);
1.2479 + }
1.2480 + do {
1.2481 + markOneWinding(__FUNCTION__, index, winding, oppWinding);
1.2482 + } while (++index < fTs.count() && precisely_negative(fTs[index].fT - referenceT));
1.2483 +}
1.2484 +
1.2485 +void SkOpSegment::matchWindingValue(int tIndex, double t, bool borrowWind) {
1.2486 + int nextDoorWind = SK_MaxS32;
1.2487 + int nextOppWind = SK_MaxS32;
1.2488 + if (tIndex > 0) {
1.2489 + const SkOpSpan& below = fTs[tIndex - 1];
1.2490 + if (approximately_negative(t - below.fT)) {
1.2491 + nextDoorWind = below.fWindValue;
1.2492 + nextOppWind = below.fOppValue;
1.2493 + }
1.2494 + }
1.2495 + if (nextDoorWind == SK_MaxS32 && tIndex + 1 < fTs.count()) {
1.2496 + const SkOpSpan& above = fTs[tIndex + 1];
1.2497 + if (approximately_negative(above.fT - t)) {
1.2498 + nextDoorWind = above.fWindValue;
1.2499 + nextOppWind = above.fOppValue;
1.2500 + }
1.2501 + }
1.2502 + if (nextDoorWind == SK_MaxS32 && borrowWind && tIndex > 0 && t < 1) {
1.2503 + const SkOpSpan& below = fTs[tIndex - 1];
1.2504 + nextDoorWind = below.fWindValue;
1.2505 + nextOppWind = below.fOppValue;
1.2506 + }
1.2507 + if (nextDoorWind != SK_MaxS32) {
1.2508 + SkOpSpan& newSpan = fTs[tIndex];
1.2509 + newSpan.fWindValue = nextDoorWind;
1.2510 + newSpan.fOppValue = nextOppWind;
1.2511 + if (!nextDoorWind && !nextOppWind && !newSpan.fDone) {
1.2512 + newSpan.fDone = true;
1.2513 + ++fDoneSpans;
1.2514 + }
1.2515 + }
1.2516 +}
1.2517 +
1.2518 +// return span if when chasing, two or more radiating spans are not done
1.2519 +// OPTIMIZATION: ? multiple spans is detected when there is only one valid
1.2520 +// candidate and the remaining spans have windValue == 0 (canceled by
1.2521 +// coincidence). The coincident edges could either be removed altogether,
1.2522 +// or this code could be more complicated in detecting this case. Worth it?
1.2523 +bool SkOpSegment::multipleSpans(int end) const {
1.2524 + return end > 0 && end < fTs.count() - 1;
1.2525 +}
1.2526 +
1.2527 +bool SkOpSegment::nextCandidate(int* start, int* end) const {
1.2528 + while (fTs[*end].fDone) {
1.2529 + if (fTs[*end].fT == 1) {
1.2530 + return false;
1.2531 + }
1.2532 + ++(*end);
1.2533 + }
1.2534 + *start = *end;
1.2535 + *end = nextExactSpan(*start, 1);
1.2536 + return true;
1.2537 +}
1.2538 +
1.2539 +SkOpSegment* SkOpSegment::nextChase(int* index, const int step, int* min, SkOpSpan** last) {
1.2540 + int end = nextExactSpan(*index, step);
1.2541 + SkASSERT(end >= 0);
1.2542 + if (fTs[end].fSmall) {
1.2543 + *last = NULL;
1.2544 + return NULL;
1.2545 + }
1.2546 + if (multipleSpans(end)) {
1.2547 + *last = &fTs[end];
1.2548 + return NULL;
1.2549 + }
1.2550 + const SkOpSpan& endSpan = fTs[end];
1.2551 + SkOpSegment* other = endSpan.fOther;
1.2552 + *index = endSpan.fOtherIndex;
1.2553 + SkASSERT(*index >= 0);
1.2554 + int otherEnd = other->nextExactSpan(*index, step);
1.2555 + SkASSERT(otherEnd >= 0);
1.2556 + *min = SkMin32(*index, otherEnd);
1.2557 + if (other->fTs[*min].fSmall) {
1.2558 + *last = NULL;
1.2559 + return NULL;
1.2560 + }
1.2561 + return other;
1.2562 +}
1.2563 +
1.2564 +// This has callers for two different situations: one establishes the end
1.2565 +// of the current span, and one establishes the beginning of the next span
1.2566 +// (thus the name). When this is looking for the end of the current span,
1.2567 +// coincidence is found when the beginning Ts contain -step and the end
1.2568 +// contains step. When it is looking for the beginning of the next, the
1.2569 +// first Ts found can be ignored and the last Ts should contain -step.
1.2570 +// OPTIMIZATION: probably should split into two functions
1.2571 +int SkOpSegment::nextSpan(int from, int step) const {
1.2572 + const SkOpSpan& fromSpan = fTs[from];
1.2573 + int count = fTs.count();
1.2574 + int to = from;
1.2575 + while (step > 0 ? ++to < count : --to >= 0) {
1.2576 + const SkOpSpan& span = fTs[to];
1.2577 + if (approximately_zero(span.fT - fromSpan.fT)) {
1.2578 + continue;
1.2579 + }
1.2580 + return to;
1.2581 + }
1.2582 + return -1;
1.2583 +}
1.2584 +
1.2585 +// FIXME
1.2586 +// this returns at any difference in T, vs. a preset minimum. It may be
1.2587 +// that all callers to nextSpan should use this instead.
1.2588 +int SkOpSegment::nextExactSpan(int from, int step) const {
1.2589 + int to = from;
1.2590 + if (step < 0) {
1.2591 + const SkOpSpan& fromSpan = fTs[from];
1.2592 + while (--to >= 0) {
1.2593 + const SkOpSpan& span = fTs[to];
1.2594 + if (precisely_negative(fromSpan.fT - span.fT) || span.fTiny) {
1.2595 + continue;
1.2596 + }
1.2597 + return to;
1.2598 + }
1.2599 + } else {
1.2600 + while (fTs[from].fTiny) {
1.2601 + from++;
1.2602 + }
1.2603 + const SkOpSpan& fromSpan = fTs[from];
1.2604 + int count = fTs.count();
1.2605 + while (++to < count) {
1.2606 + const SkOpSpan& span = fTs[to];
1.2607 + if (precisely_negative(span.fT - fromSpan.fT)) {
1.2608 + continue;
1.2609 + }
1.2610 + return to;
1.2611 + }
1.2612 + }
1.2613 + return -1;
1.2614 +}
1.2615 +
1.2616 +void SkOpSegment::setUpWindings(int index, int endIndex, int* sumMiWinding, int* sumSuWinding,
1.2617 + int* maxWinding, int* sumWinding, int* oppMaxWinding, int* oppSumWinding) {
1.2618 + int deltaSum = spanSign(index, endIndex);
1.2619 + int oppDeltaSum = oppSign(index, endIndex);
1.2620 + if (operand()) {
1.2621 + *maxWinding = *sumSuWinding;
1.2622 + *sumWinding = *sumSuWinding -= deltaSum;
1.2623 + *oppMaxWinding = *sumMiWinding;
1.2624 + *oppSumWinding = *sumMiWinding -= oppDeltaSum;
1.2625 + } else {
1.2626 + *maxWinding = *sumMiWinding;
1.2627 + *sumWinding = *sumMiWinding -= deltaSum;
1.2628 + *oppMaxWinding = *sumSuWinding;
1.2629 + *oppSumWinding = *sumSuWinding -= oppDeltaSum;
1.2630 + }
1.2631 + SkASSERT(abs(*sumWinding) <= SkPathOpsDebug::gMaxWindSum);
1.2632 + SkASSERT(abs(*oppSumWinding) <= SkPathOpsDebug::gMaxWindSum);
1.2633 +}
1.2634 +
1.2635 +void SkOpSegment::setUpWindings(int index, int endIndex, int* sumMiWinding,
1.2636 + int* maxWinding, int* sumWinding) {
1.2637 + int deltaSum = spanSign(index, endIndex);
1.2638 + *maxWinding = *sumMiWinding;
1.2639 + *sumWinding = *sumMiWinding -= deltaSum;
1.2640 + SkASSERT(abs(*sumWinding) <= SkPathOpsDebug::gMaxWindSum);
1.2641 +}
1.2642 +
1.2643 +// This marks all spans unsortable so that this info is available for early
1.2644 +// exclusion in find top and others. This could be optimized to only mark
1.2645 +// adjacent spans that unsortable. However, this makes it difficult to later
1.2646 +// determine starting points for edge detection in find top and the like.
1.2647 +bool SkOpSegment::SortAngles(const SkTArray<SkOpAngle, true>& angles,
1.2648 + SkTArray<SkOpAngle*, true>* angleList,
1.2649 + SortAngleKind orderKind) {
1.2650 + bool sortable = true;
1.2651 + int angleCount = angles.count();
1.2652 + int angleIndex;
1.2653 + for (angleIndex = 0; angleIndex < angleCount; ++angleIndex) {
1.2654 + const SkOpAngle& angle = angles[angleIndex];
1.2655 + angleList->push_back(const_cast<SkOpAngle*>(&angle));
1.2656 +#if DEBUG_ANGLE
1.2657 + (*(angleList->end() - 1))->setID(angleIndex);
1.2658 +#endif
1.2659 + sortable &= !(angle.unsortable() || (orderKind == kMustBeOrdered_SortAngleKind
1.2660 + && angle.unorderable()));
1.2661 + }
1.2662 + if (sortable) {
1.2663 + SkTQSort<SkOpAngle>(angleList->begin(), angleList->end() - 1);
1.2664 + for (angleIndex = 0; angleIndex < angleCount; ++angleIndex) {
1.2665 + if (angles[angleIndex].unsortable() || (orderKind == kMustBeOrdered_SortAngleKind
1.2666 + && angles[angleIndex].unorderable())) {
1.2667 + sortable = false;
1.2668 + break;
1.2669 + }
1.2670 + }
1.2671 + }
1.2672 + if (!sortable) {
1.2673 + for (angleIndex = 0; angleIndex < angleCount; ++angleIndex) {
1.2674 + const SkOpAngle& angle = angles[angleIndex];
1.2675 + angle.segment()->markUnsortable(angle.start(), angle.end());
1.2676 + }
1.2677 + }
1.2678 + return sortable;
1.2679 +}
1.2680 +
1.2681 +// set segments to unsortable if angle is unsortable, but do not set all angles
1.2682 +// note that for a simple 4 way crossing, two of the edges may be orderable even though
1.2683 +// two edges are too short to be orderable.
1.2684 +// perhaps some classes of unsortable angles should make all shared angles unsortable, but
1.2685 +// simple lines that have tiny crossings are always sortable on the large ends
1.2686 +// OPTIMIZATION: check earlier when angles are added to input if any are unsortable
1.2687 +// may make sense then to mark all segments in angle sweep as unsortableStart/unsortableEnd
1.2688 +// solely for the purpose of short-circuiting future angle building around this center
1.2689 +bool SkOpSegment::SortAngles2(const SkTArray<SkOpAngle, true>& angles,
1.2690 + SkTArray<SkOpAngle*, true>* angleList) {
1.2691 + int angleCount = angles.count();
1.2692 + int angleIndex;
1.2693 + for (angleIndex = 0; angleIndex < angleCount; ++angleIndex) {
1.2694 + const SkOpAngle& angle = angles[angleIndex];
1.2695 + if (angle.unsortable()) {
1.2696 + return false;
1.2697 + }
1.2698 + angleList->push_back(const_cast<SkOpAngle*>(&angle));
1.2699 +#if DEBUG_ANGLE
1.2700 + (*(angleList->end() - 1))->setID(angleIndex);
1.2701 +#endif
1.2702 + }
1.2703 + SkTQSort<SkOpAngle>(angleList->begin(), angleList->end() - 1);
1.2704 + // at this point angles are sorted but individually may not be orderable
1.2705 + // this means that only adjcent orderable segments may transfer winding
1.2706 + return true;
1.2707 +}
1.2708 +
1.2709 +// return true if midpoints were computed
1.2710 +bool SkOpSegment::subDivide(int start, int end, SkPoint edge[4]) const {
1.2711 + SkASSERT(start != end);
1.2712 + edge[0] = fTs[start].fPt;
1.2713 + int points = SkPathOpsVerbToPoints(fVerb);
1.2714 + edge[points] = fTs[end].fPt;
1.2715 + if (fVerb == SkPath::kLine_Verb) {
1.2716 + return false;
1.2717 + }
1.2718 + double startT = fTs[start].fT;
1.2719 + double endT = fTs[end].fT;
1.2720 + if ((startT == 0 || endT == 0) && (startT == 1 || endT == 1)) {
1.2721 + // don't compute midpoints if we already have them
1.2722 + if (fVerb == SkPath::kQuad_Verb) {
1.2723 + edge[1] = fPts[1];
1.2724 + return false;
1.2725 + }
1.2726 + SkASSERT(fVerb == SkPath::kCubic_Verb);
1.2727 + if (start < end) {
1.2728 + edge[1] = fPts[1];
1.2729 + edge[2] = fPts[2];
1.2730 + return false;
1.2731 + }
1.2732 + edge[1] = fPts[2];
1.2733 + edge[2] = fPts[1];
1.2734 + return false;
1.2735 + }
1.2736 + const SkDPoint sub[2] = {{ edge[0].fX, edge[0].fY}, {edge[points].fX, edge[points].fY }};
1.2737 + if (fVerb == SkPath::kQuad_Verb) {
1.2738 + edge[1] = SkDQuad::SubDivide(fPts, sub[0], sub[1], startT, endT).asSkPoint();
1.2739 + } else {
1.2740 + SkASSERT(fVerb == SkPath::kCubic_Verb);
1.2741 + SkDPoint ctrl[2];
1.2742 + SkDCubic::SubDivide(fPts, sub[0], sub[1], startT, endT, ctrl);
1.2743 + edge[1] = ctrl[0].asSkPoint();
1.2744 + edge[2] = ctrl[1].asSkPoint();
1.2745 + }
1.2746 + return true;
1.2747 +}
1.2748 +
1.2749 +// return true if midpoints were computed
1.2750 +bool SkOpSegment::subDivide(int start, int end, SkDCubic* result) const {
1.2751 + SkASSERT(start != end);
1.2752 + (*result)[0].set(fTs[start].fPt);
1.2753 + int points = SkPathOpsVerbToPoints(fVerb);
1.2754 + (*result)[points].set(fTs[end].fPt);
1.2755 + if (fVerb == SkPath::kLine_Verb) {
1.2756 + return false;
1.2757 + }
1.2758 + double startT = fTs[start].fT;
1.2759 + double endT = fTs[end].fT;
1.2760 + if ((startT == 0 || endT == 0) && (startT == 1 || endT == 1)) {
1.2761 + // don't compute midpoints if we already have them
1.2762 + if (fVerb == SkPath::kQuad_Verb) {
1.2763 + (*result)[1].set(fPts[1]);
1.2764 + return false;
1.2765 + }
1.2766 + SkASSERT(fVerb == SkPath::kCubic_Verb);
1.2767 + if (start < end) {
1.2768 + (*result)[1].set(fPts[1]);
1.2769 + (*result)[2].set(fPts[2]);
1.2770 + return false;
1.2771 + }
1.2772 + (*result)[1].set(fPts[2]);
1.2773 + (*result)[2].set(fPts[1]);
1.2774 + return false;
1.2775 + }
1.2776 + if (fVerb == SkPath::kQuad_Verb) {
1.2777 + (*result)[1] = SkDQuad::SubDivide(fPts, (*result)[0], (*result)[2], startT, endT);
1.2778 + } else {
1.2779 + SkASSERT(fVerb == SkPath::kCubic_Verb);
1.2780 + SkDCubic::SubDivide(fPts, (*result)[0], (*result)[3], startT, endT, &(*result)[1]);
1.2781 + }
1.2782 + return true;
1.2783 +}
1.2784 +
1.2785 +void SkOpSegment::subDivideBounds(int start, int end, SkPathOpsBounds* bounds) const {
1.2786 + SkPoint edge[4];
1.2787 + subDivide(start, end, edge);
1.2788 + (bounds->*SetCurveBounds[SkPathOpsVerbToPoints(fVerb)])(edge);
1.2789 +}
1.2790 +
1.2791 +void SkOpSegment::TrackOutsidePair(SkTArray<SkPoint, true>* outsidePts, const SkPoint& endPt,
1.2792 + const SkPoint& startPt) {
1.2793 + int outCount = outsidePts->count();
1.2794 + if (outCount == 0 || endPt != (*outsidePts)[outCount - 2]) {
1.2795 + outsidePts->push_back(endPt);
1.2796 + outsidePts->push_back(startPt);
1.2797 + }
1.2798 +}
1.2799 +
1.2800 +void SkOpSegment::TrackOutside(SkTArray<SkPoint, true>* outsidePts, const SkPoint& startPt) {
1.2801 + int outCount = outsidePts->count();
1.2802 + if (outCount == 0 || startPt != (*outsidePts)[outCount - 1]) {
1.2803 + outsidePts->push_back(startPt);
1.2804 + }
1.2805 +}
1.2806 +
1.2807 +void SkOpSegment::undoneSpan(int* start, int* end) {
1.2808 + size_t tCount = fTs.count();
1.2809 + size_t index;
1.2810 + for (index = 0; index < tCount; ++index) {
1.2811 + if (!fTs[index].fDone) {
1.2812 + break;
1.2813 + }
1.2814 + }
1.2815 + SkASSERT(index < tCount - 1);
1.2816 + *start = index;
1.2817 + double startT = fTs[index].fT;
1.2818 + while (approximately_negative(fTs[++index].fT - startT))
1.2819 + SkASSERT(index < tCount);
1.2820 + SkASSERT(index < tCount);
1.2821 + *end = index;
1.2822 +}
1.2823 +
1.2824 +int SkOpSegment::updateOppWinding(int index, int endIndex) const {
1.2825 + int lesser = SkMin32(index, endIndex);
1.2826 + int oppWinding = oppSum(lesser);
1.2827 + int oppSpanWinding = oppSign(index, endIndex);
1.2828 + if (oppSpanWinding && UseInnerWinding(oppWinding - oppSpanWinding, oppWinding)
1.2829 + && oppWinding != SK_MaxS32) {
1.2830 + oppWinding -= oppSpanWinding;
1.2831 + }
1.2832 + return oppWinding;
1.2833 +}
1.2834 +
1.2835 +int SkOpSegment::updateOppWinding(const SkOpAngle* angle) const {
1.2836 + int startIndex = angle->start();
1.2837 + int endIndex = angle->end();
1.2838 + return updateOppWinding(endIndex, startIndex);
1.2839 +}
1.2840 +
1.2841 +int SkOpSegment::updateOppWindingReverse(const SkOpAngle* angle) const {
1.2842 + int startIndex = angle->start();
1.2843 + int endIndex = angle->end();
1.2844 + return updateOppWinding(startIndex, endIndex);
1.2845 +}
1.2846 +
1.2847 +int SkOpSegment::updateWinding(int index, int endIndex) const {
1.2848 + int lesser = SkMin32(index, endIndex);
1.2849 + int winding = windSum(lesser);
1.2850 + int spanWinding = spanSign(index, endIndex);
1.2851 + if (winding && UseInnerWinding(winding - spanWinding, winding)
1.2852 + && winding != SK_MaxS32) {
1.2853 + winding -= spanWinding;
1.2854 + }
1.2855 + return winding;
1.2856 +}
1.2857 +
1.2858 +int SkOpSegment::updateWinding(const SkOpAngle* angle) const {
1.2859 + int startIndex = angle->start();
1.2860 + int endIndex = angle->end();
1.2861 + return updateWinding(endIndex, startIndex);
1.2862 +}
1.2863 +
1.2864 +int SkOpSegment::updateWindingReverse(int index, int endIndex) const {
1.2865 + int lesser = SkMin32(index, endIndex);
1.2866 + int winding = windSum(lesser);
1.2867 + int spanWinding = spanSign(endIndex, index);
1.2868 + if (winding && UseInnerWindingReverse(winding - spanWinding, winding)
1.2869 + && winding != SK_MaxS32) {
1.2870 + winding -= spanWinding;
1.2871 + }
1.2872 + return winding;
1.2873 +}
1.2874 +
1.2875 +int SkOpSegment::updateWindingReverse(const SkOpAngle* angle) const {
1.2876 + int startIndex = angle->start();
1.2877 + int endIndex = angle->end();
1.2878 + return updateWindingReverse(endIndex, startIndex);
1.2879 +}
1.2880 +
1.2881 +// OPTIMIZATION: does the following also work, and is it any faster?
1.2882 +// return outerWinding * innerWinding > 0
1.2883 +// || ((outerWinding + innerWinding < 0) ^ ((outerWinding - innerWinding) < 0)))
1.2884 +bool SkOpSegment::UseInnerWinding(int outerWinding, int innerWinding) {
1.2885 + SkASSERT(outerWinding != SK_MaxS32);
1.2886 + SkASSERT(innerWinding != SK_MaxS32);
1.2887 + int absOut = abs(outerWinding);
1.2888 + int absIn = abs(innerWinding);
1.2889 + bool result = absOut == absIn ? outerWinding < 0 : absOut < absIn;
1.2890 + return result;
1.2891 +}
1.2892 +
1.2893 +bool SkOpSegment::UseInnerWindingReverse(int outerWinding, int innerWinding) {
1.2894 + SkASSERT(outerWinding != SK_MaxS32);
1.2895 + SkASSERT(innerWinding != SK_MaxS32);
1.2896 + int absOut = abs(outerWinding);
1.2897 + int absIn = abs(innerWinding);
1.2898 + bool result = absOut == absIn ? true : absOut < absIn;
1.2899 + return result;
1.2900 +}
1.2901 +
1.2902 +int SkOpSegment::windingAtT(double tHit, int tIndex, bool crossOpp, SkScalar* dx) const {
1.2903 + if (approximately_zero(tHit - t(tIndex))) { // if we hit the end of a span, disregard
1.2904 + return SK_MinS32;
1.2905 + }
1.2906 + int winding = crossOpp ? oppSum(tIndex) : windSum(tIndex);
1.2907 + SkASSERT(winding != SK_MinS32);
1.2908 + int windVal = crossOpp ? oppValue(tIndex) : windValue(tIndex);
1.2909 +#if DEBUG_WINDING_AT_T
1.2910 + SkDebugf("%s oldWinding=%d windValue=%d", __FUNCTION__, winding, windVal);
1.2911 +#endif
1.2912 + // see if a + change in T results in a +/- change in X (compute x'(T))
1.2913 + *dx = (*CurveSlopeAtT[SkPathOpsVerbToPoints(fVerb)])(fPts, tHit).fX;
1.2914 + if (fVerb > SkPath::kLine_Verb && approximately_zero(*dx)) {
1.2915 + *dx = fPts[2].fX - fPts[1].fX - *dx;
1.2916 + }
1.2917 + if (*dx == 0) {
1.2918 +#if DEBUG_WINDING_AT_T
1.2919 + SkDebugf(" dx=0 winding=SK_MinS32\n");
1.2920 +#endif
1.2921 + return SK_MinS32;
1.2922 + }
1.2923 + if (windVal < 0) { // reverse sign if opp contour traveled in reverse
1.2924 + *dx = -*dx;
1.2925 + }
1.2926 + if (winding * *dx > 0) { // if same signs, result is negative
1.2927 + winding += *dx > 0 ? -windVal : windVal;
1.2928 + }
1.2929 +#if DEBUG_WINDING_AT_T
1.2930 + SkDebugf(" dx=%c winding=%d\n", *dx > 0 ? '+' : '-', winding);
1.2931 +#endif
1.2932 + return winding;
1.2933 +}
1.2934 +
1.2935 +int SkOpSegment::windSum(const SkOpAngle* angle) const {
1.2936 + int start = angle->start();
1.2937 + int end = angle->end();
1.2938 + int index = SkMin32(start, end);
1.2939 + return windSum(index);
1.2940 +}
1.2941 +
1.2942 +void SkOpSegment::zeroSpan(SkOpSpan* span) {
1.2943 + SkASSERT(span->fWindValue > 0 || span->fOppValue != 0);
1.2944 + span->fWindValue = 0;
1.2945 + span->fOppValue = 0;
1.2946 + if (span->fTiny || span->fSmall) {
1.2947 + return;
1.2948 + }
1.2949 + SkASSERT(!span->fDone);
1.2950 + span->fDone = true;
1.2951 + ++fDoneSpans;
1.2952 +}
1.2953 +
1.2954 +#if DEBUG_SWAP_TOP
1.2955 +bool SkOpSegment::controlsContainedByEnds(int tStart, int tEnd) const {
1.2956 + if (fVerb != SkPath::kCubic_Verb) {
1.2957 + return false;
1.2958 + }
1.2959 + SkDCubic dst = SkDCubic::SubDivide(fPts, fTs[tStart].fT, fTs[tEnd].fT);
1.2960 + return dst.controlsContainedByEnds();
1.2961 +}
1.2962 +#endif
1.2963 +
1.2964 +#if DEBUG_CONCIDENT
1.2965 +// SkASSERT if pair has not already been added
1.2966 +void SkOpSegment::debugAddTPair(double t, const SkOpSegment& other, double otherT) const {
1.2967 + for (int i = 0; i < fTs.count(); ++i) {
1.2968 + if (fTs[i].fT == t && fTs[i].fOther == &other && fTs[i].fOtherT == otherT) {
1.2969 + return;
1.2970 + }
1.2971 + }
1.2972 + SkASSERT(0);
1.2973 +}
1.2974 +#endif
1.2975 +
1.2976 +#if DEBUG_CONCIDENT
1.2977 +void SkOpSegment::debugShowTs(const char* prefix) const {
1.2978 + SkDebugf("%s %s id=%d", __FUNCTION__, prefix, fID);
1.2979 + int lastWind = -1;
1.2980 + int lastOpp = -1;
1.2981 + double lastT = -1;
1.2982 + int i;
1.2983 + for (i = 0; i < fTs.count(); ++i) {
1.2984 + bool change = lastT != fTs[i].fT || lastWind != fTs[i].fWindValue
1.2985 + || lastOpp != fTs[i].fOppValue;
1.2986 + if (change && lastWind >= 0) {
1.2987 + SkDebugf(" t=%1.3g %1.9g,%1.9g w=%d o=%d]",
1.2988 + lastT, xyAtT(i - 1).fX, xyAtT(i - 1).fY, lastWind, lastOpp);
1.2989 + }
1.2990 + if (change) {
1.2991 + SkDebugf(" [o=%d", fTs[i].fOther->fID);
1.2992 + lastWind = fTs[i].fWindValue;
1.2993 + lastOpp = fTs[i].fOppValue;
1.2994 + lastT = fTs[i].fT;
1.2995 + } else {
1.2996 + SkDebugf(",%d", fTs[i].fOther->fID);
1.2997 + }
1.2998 + }
1.2999 + if (i <= 0) {
1.3000 + return;
1.3001 + }
1.3002 + SkDebugf(" t=%1.3g %1.9g,%1.9g w=%d o=%d]",
1.3003 + lastT, xyAtT(i - 1).fX, xyAtT(i - 1).fY, lastWind, lastOpp);
1.3004 + if (fOperand) {
1.3005 + SkDebugf(" operand");
1.3006 + }
1.3007 + if (done()) {
1.3008 + SkDebugf(" done");
1.3009 + }
1.3010 + SkDebugf("\n");
1.3011 +}
1.3012 +#endif
1.3013 +
1.3014 +#if DEBUG_ACTIVE_SPANS || DEBUG_ACTIVE_SPANS_FIRST_ONLY
1.3015 +void SkOpSegment::debugShowActiveSpans() const {
1.3016 + debugValidate();
1.3017 + if (done()) {
1.3018 + return;
1.3019 + }
1.3020 +#if DEBUG_ACTIVE_SPANS_SHORT_FORM
1.3021 + int lastId = -1;
1.3022 + double lastT = -1;
1.3023 +#endif
1.3024 + for (int i = 0; i < fTs.count(); ++i) {
1.3025 + if (fTs[i].fDone) {
1.3026 + continue;
1.3027 + }
1.3028 + SkASSERT(i < fTs.count() - 1);
1.3029 +#if DEBUG_ACTIVE_SPANS_SHORT_FORM
1.3030 + if (lastId == fID && lastT == fTs[i].fT) {
1.3031 + continue;
1.3032 + }
1.3033 + lastId = fID;
1.3034 + lastT = fTs[i].fT;
1.3035 +#endif
1.3036 + SkDebugf("%s id=%d", __FUNCTION__, fID);
1.3037 + SkDebugf(" (%1.9g,%1.9g", fPts[0].fX, fPts[0].fY);
1.3038 + for (int vIndex = 1; vIndex <= SkPathOpsVerbToPoints(fVerb); ++vIndex) {
1.3039 + SkDebugf(" %1.9g,%1.9g", fPts[vIndex].fX, fPts[vIndex].fY);
1.3040 + }
1.3041 + const SkOpSpan* span = &fTs[i];
1.3042 + SkDebugf(") t=%1.9g (%1.9g,%1.9g)", span->fT, xAtT(span), yAtT(span));
1.3043 + int iEnd = i + 1;
1.3044 + while (fTs[iEnd].fT < 1 && approximately_equal(fTs[i].fT, fTs[iEnd].fT)) {
1.3045 + ++iEnd;
1.3046 + }
1.3047 + SkDebugf(" tEnd=%1.9g", fTs[iEnd].fT);
1.3048 + const SkOpSegment* other = fTs[i].fOther;
1.3049 + SkDebugf(" other=%d otherT=%1.9g otherIndex=%d windSum=",
1.3050 + other->fID, fTs[i].fOtherT, fTs[i].fOtherIndex);
1.3051 + if (fTs[i].fWindSum == SK_MinS32) {
1.3052 + SkDebugf("?");
1.3053 + } else {
1.3054 + SkDebugf("%d", fTs[i].fWindSum);
1.3055 + }
1.3056 + SkDebugf(" windValue=%d oppValue=%d\n", fTs[i].fWindValue, fTs[i].fOppValue);
1.3057 + }
1.3058 +}
1.3059 +#endif
1.3060 +
1.3061 +
1.3062 +#if DEBUG_MARK_DONE || DEBUG_UNSORTABLE
1.3063 +void SkOpSegment::debugShowNewWinding(const char* fun, const SkOpSpan& span, int winding) {
1.3064 + const SkPoint& pt = xyAtT(&span);
1.3065 + SkDebugf("%s id=%d", fun, fID);
1.3066 + SkDebugf(" (%1.9g,%1.9g", fPts[0].fX, fPts[0].fY);
1.3067 + for (int vIndex = 1; vIndex <= SkPathOpsVerbToPoints(fVerb); ++vIndex) {
1.3068 + SkDebugf(" %1.9g,%1.9g", fPts[vIndex].fX, fPts[vIndex].fY);
1.3069 + }
1.3070 + SkASSERT(&span == &span.fOther->fTs[span.fOtherIndex].fOther->
1.3071 + fTs[span.fOther->fTs[span.fOtherIndex].fOtherIndex]);
1.3072 + SkDebugf(") t=%1.9g [%d] (%1.9g,%1.9g) tEnd=%1.9g newWindSum=%d windSum=",
1.3073 + span.fT, span.fOther->fTs[span.fOtherIndex].fOtherIndex, pt.fX, pt.fY,
1.3074 + (&span)[1].fT, winding);
1.3075 + if (span.fWindSum == SK_MinS32) {
1.3076 + SkDebugf("?");
1.3077 + } else {
1.3078 + SkDebugf("%d", span.fWindSum);
1.3079 + }
1.3080 + SkDebugf(" windValue=%d\n", span.fWindValue);
1.3081 +}
1.3082 +
1.3083 +void SkOpSegment::debugShowNewWinding(const char* fun, const SkOpSpan& span, int winding,
1.3084 + int oppWinding) {
1.3085 + const SkPoint& pt = xyAtT(&span);
1.3086 + SkDebugf("%s id=%d", fun, fID);
1.3087 + SkDebugf(" (%1.9g,%1.9g", fPts[0].fX, fPts[0].fY);
1.3088 + for (int vIndex = 1; vIndex <= SkPathOpsVerbToPoints(fVerb); ++vIndex) {
1.3089 + SkDebugf(" %1.9g,%1.9g", fPts[vIndex].fX, fPts[vIndex].fY);
1.3090 + }
1.3091 + SkASSERT(&span == &span.fOther->fTs[span.fOtherIndex].fOther->
1.3092 + fTs[span.fOther->fTs[span.fOtherIndex].fOtherIndex]);
1.3093 + SkDebugf(") t=%1.9g [%d] (%1.9g,%1.9g) tEnd=%1.9g newWindSum=%d newOppSum=%d oppSum=",
1.3094 + span.fT, span.fOther->fTs[span.fOtherIndex].fOtherIndex, pt.fX, pt.fY,
1.3095 + (&span)[1].fT, winding, oppWinding);
1.3096 + if (span.fOppSum == SK_MinS32) {
1.3097 + SkDebugf("?");
1.3098 + } else {
1.3099 + SkDebugf("%d", span.fOppSum);
1.3100 + }
1.3101 + SkDebugf(" windSum=");
1.3102 + if (span.fWindSum == SK_MinS32) {
1.3103 + SkDebugf("?");
1.3104 + } else {
1.3105 + SkDebugf("%d", span.fWindSum);
1.3106 + }
1.3107 + SkDebugf(" windValue=%d\n", span.fWindValue);
1.3108 +}
1.3109 +#endif
1.3110 +
1.3111 +#if DEBUG_SORT || DEBUG_SWAP_TOP
1.3112 +void SkOpSegment::debugShowSort(const char* fun, const SkTArray<SkOpAngle*, true>& angles,
1.3113 + int first, const int contourWinding,
1.3114 + const int oppContourWinding, bool sortable) const {
1.3115 + if (--SkPathOpsDebug::gSortCount < 0) {
1.3116 + return;
1.3117 + }
1.3118 + if (!sortable) {
1.3119 + if (angles.count() == 0) {
1.3120 + return;
1.3121 + }
1.3122 + if (first < 0) {
1.3123 + first = 0;
1.3124 + }
1.3125 + }
1.3126 + SkASSERT(angles[first]->segment() == this);
1.3127 + SkASSERT(!sortable || angles.count() > 1);
1.3128 + int lastSum = contourWinding;
1.3129 + int oppLastSum = oppContourWinding;
1.3130 + const SkOpAngle* firstAngle = angles[first];
1.3131 + int windSum = lastSum - spanSign(firstAngle);
1.3132 + int oppoSign = oppSign(firstAngle);
1.3133 + int oppWindSum = oppLastSum - oppoSign;
1.3134 + #define WIND_AS_STRING(x) char x##Str[12]; \
1.3135 + if (!SkPathOpsDebug::ValidWind(x)) strcpy(x##Str, "?"); \
1.3136 + else SK_SNPRINTF(x##Str, sizeof(x##Str), "%d", x)
1.3137 + WIND_AS_STRING(contourWinding);
1.3138 + WIND_AS_STRING(oppContourWinding);
1.3139 + SkDebugf("%s %s contourWinding=%s oppContourWinding=%s sign=%d\n", fun, __FUNCTION__,
1.3140 + contourWindingStr, oppContourWindingStr, spanSign(angles[first]));
1.3141 + int index = first;
1.3142 + bool firstTime = true;
1.3143 + do {
1.3144 + const SkOpAngle& angle = *angles[index];
1.3145 + const SkOpSegment& segment = *angle.segment();
1.3146 + int start = angle.start();
1.3147 + int end = angle.end();
1.3148 + const SkOpSpan& sSpan = segment.fTs[start];
1.3149 + const SkOpSpan& eSpan = segment.fTs[end];
1.3150 + const SkOpSpan& mSpan = segment.fTs[SkMin32(start, end)];
1.3151 + bool opp = segment.fOperand ^ fOperand;
1.3152 + if (!firstTime) {
1.3153 + oppoSign = segment.oppSign(&angle);
1.3154 + if (opp) {
1.3155 + oppLastSum = oppWindSum;
1.3156 + oppWindSum -= segment.spanSign(&angle);
1.3157 + if (oppoSign) {
1.3158 + lastSum = windSum;
1.3159 + windSum -= oppoSign;
1.3160 + }
1.3161 + } else {
1.3162 + lastSum = windSum;
1.3163 + windSum -= segment.spanSign(&angle);
1.3164 + if (oppoSign) {
1.3165 + oppLastSum = oppWindSum;
1.3166 + oppWindSum -= oppoSign;
1.3167 + }
1.3168 + }
1.3169 + }
1.3170 + SkDebugf("%s [%d] %s", __FUNCTION__, index,
1.3171 + angle.unsortable() ? "*** UNSORTABLE *** " : "");
1.3172 + #if DEBUG_SORT_COMPACT
1.3173 + SkDebugf("id=%d %s start=%d (%1.9g,%1.9g) end=%d (%1.9g,%1.9g)",
1.3174 + segment.fID, kLVerbStr[SkPathOpsVerbToPoints(segment.fVerb)],
1.3175 + start, segment.xAtT(&sSpan), segment.yAtT(&sSpan), end,
1.3176 + segment.xAtT(&eSpan), segment.yAtT(&eSpan));
1.3177 + #else
1.3178 + switch (segment.fVerb) {
1.3179 + case SkPath::kLine_Verb:
1.3180 + SkDebugf(LINE_DEBUG_STR, LINE_DEBUG_DATA(segment.fPts));
1.3181 + break;
1.3182 + case SkPath::kQuad_Verb:
1.3183 + SkDebugf(QUAD_DEBUG_STR, QUAD_DEBUG_DATA(segment.fPts));
1.3184 + break;
1.3185 + case SkPath::kCubic_Verb:
1.3186 + SkDebugf(CUBIC_DEBUG_STR, CUBIC_DEBUG_DATA(segment.fPts));
1.3187 + break;
1.3188 + default:
1.3189 + SkASSERT(0);
1.3190 + }
1.3191 + SkDebugf(" tStart=%1.9g tEnd=%1.9g", sSpan.fT, eSpan.fT);
1.3192 + #endif
1.3193 + SkDebugf(" sign=%d windValue=%d windSum=", angle.sign(), mSpan.fWindValue);
1.3194 + SkPathOpsDebug::WindingPrintf(mSpan.fWindSum);
1.3195 + int last, wind;
1.3196 + if (opp) {
1.3197 + last = oppLastSum;
1.3198 + wind = oppWindSum;
1.3199 + } else {
1.3200 + last = lastSum;
1.3201 + wind = windSum;
1.3202 + }
1.3203 + bool useInner = SkPathOpsDebug::ValidWind(last) && SkPathOpsDebug::ValidWind(wind)
1.3204 + && UseInnerWinding(last, wind);
1.3205 + WIND_AS_STRING(last);
1.3206 + WIND_AS_STRING(wind);
1.3207 + WIND_AS_STRING(lastSum);
1.3208 + WIND_AS_STRING(oppLastSum);
1.3209 + WIND_AS_STRING(windSum);
1.3210 + WIND_AS_STRING(oppWindSum);
1.3211 + #undef WIND_AS_STRING
1.3212 + if (!oppoSign) {
1.3213 + SkDebugf(" %s->%s (max=%s)", lastStr, windStr, useInner ? windStr : lastStr);
1.3214 + } else {
1.3215 + SkDebugf(" %s->%s (%s->%s)", lastStr, windStr, opp ? lastSumStr : oppLastSumStr,
1.3216 + opp ? windSumStr : oppWindSumStr);
1.3217 + }
1.3218 + SkDebugf(" done=%d unord=%d small=%d tiny=%d opp=%d\n",
1.3219 + mSpan.fDone, angle.unorderable(), mSpan.fSmall, mSpan.fTiny, opp);
1.3220 + ++index;
1.3221 + if (index == angles.count()) {
1.3222 + index = 0;
1.3223 + }
1.3224 + if (firstTime) {
1.3225 + firstTime = false;
1.3226 + }
1.3227 + } while (index != first);
1.3228 +}
1.3229 +
1.3230 +void SkOpSegment::debugShowSort(const char* fun, const SkTArray<SkOpAngle*, true>& angles,
1.3231 + int first, bool sortable) {
1.3232 + if (!sortable) {
1.3233 + if (angles.count() == 0) {
1.3234 + return;
1.3235 + }
1.3236 + if (first < 0) {
1.3237 + first = 0;
1.3238 + }
1.3239 + }
1.3240 + const SkOpAngle* firstAngle = angles[first];
1.3241 + const SkOpSegment* segment = firstAngle->segment();
1.3242 + int winding = segment->updateWinding(firstAngle);
1.3243 + int oppWinding = segment->updateOppWinding(firstAngle);
1.3244 + debugShowSort(fun, angles, first, winding, oppWinding, sortable);
1.3245 +}
1.3246 +
1.3247 +#endif
1.3248 +
1.3249 +#if DEBUG_SHOW_WINDING
1.3250 +int SkOpSegment::debugShowWindingValues(int slotCount, int ofInterest) const {
1.3251 + if (!(1 << fID & ofInterest)) {
1.3252 + return 0;
1.3253 + }
1.3254 + int sum = 0;
1.3255 + SkTArray<char, true> slots(slotCount * 2);
1.3256 + memset(slots.begin(), ' ', slotCount * 2);
1.3257 + for (int i = 0; i < fTs.count(); ++i) {
1.3258 + // if (!(1 << fTs[i].fOther->fID & ofInterest)) {
1.3259 + // continue;
1.3260 + // }
1.3261 + sum += fTs[i].fWindValue;
1.3262 + slots[fTs[i].fOther->fID - 1] = as_digit(fTs[i].fWindValue);
1.3263 + sum += fTs[i].fOppValue;
1.3264 + slots[slotCount + fTs[i].fOther->fID - 1] = as_digit(fTs[i].fOppValue);
1.3265 + }
1.3266 + SkDebugf("%s id=%2d %.*s | %.*s\n", __FUNCTION__, fID, slotCount, slots.begin(), slotCount,
1.3267 + slots.begin() + slotCount);
1.3268 + return sum;
1.3269 +}
1.3270 +#endif
1.3271 +
1.3272 +void SkOpSegment::debugValidate() const {
1.3273 +#if DEBUG_VALIDATE
1.3274 + int count = fTs.count();
1.3275 + SkASSERT(count >= 2);
1.3276 + SkASSERT(fTs[0].fT == 0);
1.3277 + SkASSERT(fTs[count - 1].fT == 1);
1.3278 + int done = 0;
1.3279 + double t = -1;
1.3280 + for (int i = 0; i < count; ++i) {
1.3281 + const SkOpSpan& span = fTs[i];
1.3282 + SkASSERT(t <= span.fT);
1.3283 + t = span.fT;
1.3284 + int otherIndex = span.fOtherIndex;
1.3285 + const SkOpSegment* other = span.fOther;
1.3286 + const SkOpSpan& otherSpan = other->fTs[otherIndex];
1.3287 + SkASSERT(otherSpan.fPt == span.fPt);
1.3288 + SkASSERT(otherSpan.fOtherT == t);
1.3289 + SkASSERT(&fTs[i] == &otherSpan.fOther->fTs[otherSpan.fOtherIndex]);
1.3290 + done += span.fDone;
1.3291 + }
1.3292 + SkASSERT(done == fDoneSpans);
1.3293 +#endif
1.3294 +}
1.3295 +
1.3296 +#ifdef SK_DEBUG
1.3297 +void SkOpSegment::dumpPts() const {
1.3298 + int last = SkPathOpsVerbToPoints(fVerb);
1.3299 + SkDebugf("{{");
1.3300 + int index = 0;
1.3301 + do {
1.3302 + SkDPoint::dump(fPts[index]);
1.3303 + SkDebugf(", ");
1.3304 + } while (++index < last);
1.3305 + SkDPoint::dump(fPts[index]);
1.3306 + SkDebugf("}}\n");
1.3307 +}
1.3308 +
1.3309 +void SkOpSegment::dumpDPts() const {
1.3310 + int count = SkPathOpsVerbToPoints(fVerb);
1.3311 + SkDebugf("{{");
1.3312 + int index = 0;
1.3313 + do {
1.3314 + SkDPoint dPt = {fPts[index].fX, fPts[index].fY};
1.3315 + dPt.dump();
1.3316 + if (index != count) {
1.3317 + SkDebugf(", ");
1.3318 + }
1.3319 + } while (++index <= count);
1.3320 + SkDebugf("}}\n");
1.3321 +}
1.3322 +
1.3323 +void SkOpSegment::dumpSpans() const {
1.3324 + int count = this->count();
1.3325 + for (int index = 0; index < count; ++index) {
1.3326 + const SkOpSpan& span = this->span(index);
1.3327 + SkDebugf("[%d] ", index);
1.3328 + span.dump();
1.3329 + }
1.3330 +}
1.3331 +#endif
