caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 1 | /* |
| 2 | * Copyright 2012 Google Inc. |
| 3 | * |
| 4 | * Use of this source code is governed by a BSD-style license that can be |
| 5 | * found in the LICENSE file. |
| 6 | */ |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 7 | #include "SkOpCoincidence.h" |
caryclark | dac1d17 | 2014-06-17 05:15:38 -0700 | [diff] [blame] | 8 | #include "SkOpContour.h" |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 9 | #include "SkOpSegment.h" |
| 10 | #include "SkPathWriter.h" |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 11 | |
| 12 | /* |
| 13 | After computing raw intersections, post process all segments to: |
| 14 | - find small collections of points that can be collapsed to a single point |
| 15 | - find missing intersections to resolve differences caused by different algorithms |
| 16 | |
| 17 | Consider segments containing tiny or small intervals. Consider coincident segments |
| 18 | because coincidence finds intersections through distance measurement that non-coincident |
| 19 | intersection tests cannot. |
| 20 | */ |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 21 | |
| 22 | #define F (false) // discard the edge |
| 23 | #define T (true) // keep the edge |
| 24 | |
| 25 | static const bool gUnaryActiveEdge[2][2] = { |
| 26 | // from=0 from=1 |
| 27 | // to=0,1 to=0,1 |
| 28 | {F, T}, {T, F}, |
| 29 | }; |
| 30 | |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 31 | static const bool gActiveEdge[kXOR_SkPathOp + 1][2][2][2][2] = { |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 32 | // miFrom=0 miFrom=1 |
commit-bot@chromium.org | 4431e77 | 2014-04-14 17:08:59 +0000 | [diff] [blame] | 33 | // miTo=0 miTo=1 miTo=0 miTo=1 |
| 34 | // suFrom=0 1 suFrom=0 1 suFrom=0 1 suFrom=0 1 |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 35 | // suTo=0,1 suTo=0,1 suTo=0,1 suTo=0,1 suTo=0,1 suTo=0,1 suTo=0,1 suTo=0,1 |
| 36 | {{{{F, F}, {F, F}}, {{T, F}, {T, F}}}, {{{T, T}, {F, F}}, {{F, T}, {T, F}}}}, // mi - su |
| 37 | {{{{F, F}, {F, F}}, {{F, T}, {F, T}}}, {{{F, F}, {T, T}}, {{F, T}, {T, F}}}}, // mi & su |
| 38 | {{{{F, T}, {T, F}}, {{T, T}, {F, F}}}, {{{T, F}, {T, F}}, {{F, F}, {F, F}}}}, // mi | su |
| 39 | {{{{F, T}, {T, F}}, {{T, F}, {F, T}}}, {{{T, F}, {F, T}}, {{F, T}, {T, F}}}}, // mi ^ su |
| 40 | }; |
| 41 | |
| 42 | #undef F |
| 43 | #undef T |
| 44 | |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 45 | SkOpAngle* SkOpSegment::activeAngle(SkOpSpanBase* start, SkOpSpanBase** startPtr, |
caryclark | bca19f7 | 2015-05-13 08:23:48 -0700 | [diff] [blame] | 46 | SkOpSpanBase** endPtr, bool* done) { |
| 47 | if (SkOpAngle* result = activeAngleInner(start, startPtr, endPtr, done)) { |
commit-bot@chromium.org | 4431e77 | 2014-04-14 17:08:59 +0000 | [diff] [blame] | 48 | return result; |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 49 | } |
caryclark | bca19f7 | 2015-05-13 08:23:48 -0700 | [diff] [blame] | 50 | if (SkOpAngle* result = activeAngleOther(start, startPtr, endPtr, done)) { |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 51 | return result; |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 52 | } |
halcanary | 96fcdcc | 2015-08-27 07:41:13 -0700 | [diff] [blame] | 53 | return nullptr; |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 54 | } |
| 55 | |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 56 | SkOpAngle* SkOpSegment::activeAngleInner(SkOpSpanBase* start, SkOpSpanBase** startPtr, |
caryclark | bca19f7 | 2015-05-13 08:23:48 -0700 | [diff] [blame] | 57 | SkOpSpanBase** endPtr, bool* done) { |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 58 | SkOpSpan* upSpan = start->upCastable(); |
| 59 | if (upSpan) { |
| 60 | if (upSpan->windValue() || upSpan->oppValue()) { |
| 61 | SkOpSpanBase* next = upSpan->next(); |
| 62 | if (!*endPtr) { |
| 63 | *startPtr = start; |
| 64 | *endPtr = next; |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 65 | } |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 66 | if (!upSpan->done()) { |
| 67 | if (upSpan->windSum() != SK_MinS32) { |
| 68 | return spanToAngle(start, next); |
commit-bot@chromium.org | 4431e77 | 2014-04-14 17:08:59 +0000 | [diff] [blame] | 69 | } |
| 70 | *done = false; |
| 71 | } |
| 72 | } else { |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 73 | SkASSERT(upSpan->done()); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 74 | } |
| 75 | } |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 76 | SkOpSpan* downSpan = start->prev(); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 77 | // edge leading into junction |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 78 | if (downSpan) { |
| 79 | if (downSpan->windValue() || downSpan->oppValue()) { |
| 80 | if (!*endPtr) { |
| 81 | *startPtr = start; |
| 82 | *endPtr = downSpan; |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 83 | } |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 84 | if (!downSpan->done()) { |
| 85 | if (downSpan->windSum() != SK_MinS32) { |
| 86 | return spanToAngle(start, downSpan); |
commit-bot@chromium.org | 4431e77 | 2014-04-14 17:08:59 +0000 | [diff] [blame] | 87 | } |
| 88 | *done = false; |
| 89 | } |
| 90 | } else { |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 91 | SkASSERT(downSpan->done()); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 92 | } |
| 93 | } |
halcanary | 96fcdcc | 2015-08-27 07:41:13 -0700 | [diff] [blame] | 94 | return nullptr; |
commit-bot@chromium.org | 4431e77 | 2014-04-14 17:08:59 +0000 | [diff] [blame] | 95 | } |
| 96 | |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 97 | SkOpAngle* SkOpSegment::activeAngleOther(SkOpSpanBase* start, SkOpSpanBase** startPtr, |
caryclark | bca19f7 | 2015-05-13 08:23:48 -0700 | [diff] [blame] | 98 | SkOpSpanBase** endPtr, bool* done) { |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 99 | SkOpPtT* oPtT = start->ptT()->next(); |
| 100 | SkOpSegment* other = oPtT->segment(); |
| 101 | SkOpSpanBase* oSpan = oPtT->span(); |
caryclark | bca19f7 | 2015-05-13 08:23:48 -0700 | [diff] [blame] | 102 | return other->activeAngleInner(oSpan, startPtr, endPtr, done); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 103 | } |
| 104 | |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 105 | bool SkOpSegment::activeOp(SkOpSpanBase* start, SkOpSpanBase* end, int xorMiMask, int xorSuMask, |
| 106 | SkPathOp op) { |
| 107 | int sumMiWinding = this->updateWinding(end, start); |
| 108 | int sumSuWinding = this->updateOppWinding(end, start); |
caryclark | 65f5531 | 2014-11-13 06:58:52 -0800 | [diff] [blame] | 109 | #if DEBUG_LIMIT_WIND_SUM |
| 110 | SkASSERT(abs(sumMiWinding) <= DEBUG_LIMIT_WIND_SUM); |
| 111 | SkASSERT(abs(sumSuWinding) <= DEBUG_LIMIT_WIND_SUM); |
| 112 | #endif |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 113 | if (this->operand()) { |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 114 | SkTSwap<int>(sumMiWinding, sumSuWinding); |
| 115 | } |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 116 | return this->activeOp(xorMiMask, xorSuMask, start, end, op, &sumMiWinding, &sumSuWinding); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 117 | } |
| 118 | |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 119 | bool SkOpSegment::activeOp(int xorMiMask, int xorSuMask, SkOpSpanBase* start, SkOpSpanBase* end, |
| 120 | SkPathOp op, int* sumMiWinding, int* sumSuWinding) { |
commit-bot@chromium.org | 4431e77 | 2014-04-14 17:08:59 +0000 | [diff] [blame] | 121 | int maxWinding, sumWinding, oppMaxWinding, oppSumWinding; |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 122 | this->setUpWindings(start, end, sumMiWinding, sumSuWinding, |
commit-bot@chromium.org | 4431e77 | 2014-04-14 17:08:59 +0000 | [diff] [blame] | 123 | &maxWinding, &sumWinding, &oppMaxWinding, &oppSumWinding); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 124 | bool miFrom; |
| 125 | bool miTo; |
| 126 | bool suFrom; |
| 127 | bool suTo; |
| 128 | if (operand()) { |
commit-bot@chromium.org | 4431e77 | 2014-04-14 17:08:59 +0000 | [diff] [blame] | 129 | miFrom = (oppMaxWinding & xorMiMask) != 0; |
| 130 | miTo = (oppSumWinding & xorMiMask) != 0; |
| 131 | suFrom = (maxWinding & xorSuMask) != 0; |
| 132 | suTo = (sumWinding & xorSuMask) != 0; |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 133 | } else { |
commit-bot@chromium.org | 4431e77 | 2014-04-14 17:08:59 +0000 | [diff] [blame] | 134 | miFrom = (maxWinding & xorMiMask) != 0; |
| 135 | miTo = (sumWinding & xorMiMask) != 0; |
| 136 | suFrom = (oppMaxWinding & xorSuMask) != 0; |
| 137 | suTo = (oppSumWinding & xorSuMask) != 0; |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 138 | } |
| 139 | bool result = gActiveEdge[op][miFrom][miTo][suFrom][suTo]; |
| 140 | #if DEBUG_ACTIVE_OP |
caryclark | dac1d17 | 2014-06-17 05:15:38 -0700 | [diff] [blame] | 141 | SkDebugf("%s id=%d t=%1.9g tEnd=%1.9g op=%s miFrom=%d miTo=%d suFrom=%d suTo=%d result=%d\n", |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 142 | __FUNCTION__, debugID(), start->t(), end->t(), |
caryclark@google.com | 570863f | 2013-09-16 15:55:01 +0000 | [diff] [blame] | 143 | SkPathOpsDebug::kPathOpStr[op], miFrom, miTo, suFrom, suTo, result); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 144 | #endif |
| 145 | return result; |
| 146 | } |
| 147 | |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 148 | bool SkOpSegment::activeWinding(SkOpSpanBase* start, SkOpSpanBase* end) { |
| 149 | int sumWinding = updateWinding(end, start); |
| 150 | return activeWinding(start, end, &sumWinding); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 151 | } |
| 152 | |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 153 | bool SkOpSegment::activeWinding(SkOpSpanBase* start, SkOpSpanBase* end, int* sumWinding) { |
commit-bot@chromium.org | 4431e77 | 2014-04-14 17:08:59 +0000 | [diff] [blame] | 154 | int maxWinding; |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 155 | setUpWinding(start, end, &maxWinding, sumWinding); |
commit-bot@chromium.org | 4431e77 | 2014-04-14 17:08:59 +0000 | [diff] [blame] | 156 | bool from = maxWinding != 0; |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 157 | bool to = *sumWinding != 0; |
| 158 | bool result = gUnaryActiveEdge[from][to]; |
| 159 | return result; |
| 160 | } |
| 161 | |
caryclark | 27c8eb8 | 2015-07-06 11:38:33 -0700 | [diff] [blame] | 162 | void SkOpSegment::addAlignIntersection(SkOpPtT& endPtT, SkPoint& oldPt, |
| 163 | SkOpContourHead* contourList, SkChunkAlloc* allocator) { |
| 164 | const SkPoint& newPt = endPtT.fPt; |
| 165 | if (newPt == oldPt) { |
| 166 | return; |
| 167 | } |
| 168 | SkPoint line[2] = { newPt, oldPt }; |
| 169 | SkPathOpsBounds lineBounds; |
| 170 | lineBounds.setBounds(line, 2); |
| 171 | SkDLine aLine; |
| 172 | aLine.set(line); |
| 173 | SkOpContour* current = contourList; |
| 174 | do { |
| 175 | if (!SkPathOpsBounds::Intersects(current->bounds(), lineBounds)) { |
| 176 | continue; |
| 177 | } |
| 178 | SkOpSegment* segment = current->first(); |
| 179 | do { |
| 180 | if (!SkPathOpsBounds::Intersects(segment->bounds(), lineBounds)) { |
| 181 | continue; |
| 182 | } |
| 183 | if (newPt == segment->fPts[0]) { |
| 184 | continue; |
| 185 | } |
| 186 | if (newPt == segment->fPts[SkPathOpsVerbToPoints(segment->fVerb)]) { |
| 187 | continue; |
| 188 | } |
| 189 | if (oldPt == segment->fPts[0]) { |
| 190 | continue; |
| 191 | } |
| 192 | if (oldPt == segment->fPts[SkPathOpsVerbToPoints(segment->fVerb)]) { |
| 193 | continue; |
| 194 | } |
| 195 | if (endPtT.contains(segment)) { |
| 196 | continue; |
| 197 | } |
| 198 | SkIntersections i; |
| 199 | switch (segment->fVerb) { |
| 200 | case SkPath::kLine_Verb: { |
| 201 | SkDLine bLine; |
| 202 | bLine.set(segment->fPts); |
| 203 | i.intersect(bLine, aLine); |
| 204 | } break; |
| 205 | case SkPath::kQuad_Verb: { |
| 206 | SkDQuad bQuad; |
| 207 | bQuad.set(segment->fPts); |
| 208 | i.intersect(bQuad, aLine); |
| 209 | } break; |
| 210 | case SkPath::kConic_Verb: { |
| 211 | SkDConic bConic; |
| 212 | bConic.set(segment->fPts, segment->fWeight); |
| 213 | i.intersect(bConic, aLine); |
| 214 | } break; |
| 215 | case SkPath::kCubic_Verb: { |
| 216 | SkDCubic bCubic; |
| 217 | bCubic.set(segment->fPts); |
| 218 | i.intersect(bCubic, aLine); |
| 219 | } break; |
| 220 | default: |
| 221 | SkASSERT(0); |
| 222 | } |
| 223 | if (i.used()) { |
| 224 | SkASSERT(i.used() == 1); |
| 225 | SkASSERT(!zero_or_one(i[0][0])); |
| 226 | SkOpSpanBase* checkSpan = fHead.next(); |
| 227 | while (!checkSpan->final()) { |
| 228 | if (checkSpan->contains(segment)) { |
| 229 | goto nextSegment; |
| 230 | } |
| 231 | checkSpan = checkSpan->upCast()->next(); |
| 232 | } |
| 233 | SkOpPtT* ptT = segment->addT(i[0][0], SkOpSegment::kAllowAlias, allocator); |
| 234 | ptT->fPt = newPt; |
| 235 | endPtT.addOpp(ptT); |
| 236 | } |
| 237 | nextSegment: |
| 238 | ; |
| 239 | } while ((segment = segment->next())); |
| 240 | } while ((current = current->next())); |
| 241 | } |
| 242 | |
caryclark | ef784fb | 2015-10-30 12:03:06 -0700 | [diff] [blame] | 243 | bool SkOpSegment::addCurveTo(const SkOpSpanBase* start, const SkOpSpanBase* end, |
| 244 | SkPathWriter* path) const { |
| 245 | if (start->starter(end)->alreadyAdded()) { |
| 246 | return false; |
| 247 | } |
caryclark | 1049f12 | 2015-04-20 08:31:59 -0700 | [diff] [blame] | 248 | SkOpCurve edge; |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 249 | const SkPoint* ePtr; |
caryclark | 1049f12 | 2015-04-20 08:31:59 -0700 | [diff] [blame] | 250 | SkScalar eWeight; |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 251 | if ((start == &fHead && end == &fTail) || (start == &fTail && end == &fHead)) { |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 252 | ePtr = fPts; |
caryclark | 1049f12 | 2015-04-20 08:31:59 -0700 | [diff] [blame] | 253 | eWeight = fWeight; |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 254 | } else { |
| 255 | // OPTIMIZE? if not active, skip remainder and return xyAtT(end) |
caryclark | 1049f12 | 2015-04-20 08:31:59 -0700 | [diff] [blame] | 256 | subDivide(start, end, &edge); |
| 257 | ePtr = edge.fPts; |
| 258 | eWeight = edge.fWeight; |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 259 | } |
caryclark | ef784fb | 2015-10-30 12:03:06 -0700 | [diff] [blame] | 260 | bool reverse = ePtr == fPts && start != &fHead; |
| 261 | if (reverse) { |
| 262 | path->deferredMoveLine(ePtr[SkPathOpsVerbToPoints(fVerb)]); |
| 263 | switch (fVerb) { |
| 264 | case SkPath::kLine_Verb: |
| 265 | path->deferredLine(ePtr[0]); |
| 266 | break; |
| 267 | case SkPath::kQuad_Verb: |
| 268 | path->quadTo(ePtr[1], ePtr[0]); |
| 269 | break; |
| 270 | case SkPath::kConic_Verb: |
| 271 | path->conicTo(ePtr[1], ePtr[0], eWeight); |
| 272 | break; |
| 273 | case SkPath::kCubic_Verb: |
| 274 | path->cubicTo(ePtr[2], ePtr[1], ePtr[0]); |
| 275 | break; |
| 276 | default: |
| 277 | SkASSERT(0); |
| 278 | } |
| 279 | } else { |
| 280 | path->deferredMoveLine(ePtr[0]); |
| 281 | switch (fVerb) { |
| 282 | case SkPath::kLine_Verb: |
| 283 | path->deferredLine(ePtr[1]); |
| 284 | break; |
| 285 | case SkPath::kQuad_Verb: |
| 286 | path->quadTo(ePtr[1], ePtr[2]); |
| 287 | break; |
| 288 | case SkPath::kConic_Verb: |
| 289 | path->conicTo(ePtr[1], ePtr[2], eWeight); |
| 290 | break; |
| 291 | case SkPath::kCubic_Verb: |
| 292 | path->cubicTo(ePtr[1], ePtr[2], ePtr[3]); |
| 293 | break; |
| 294 | default: |
| 295 | SkASSERT(0); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 296 | } |
| 297 | } |
caryclark | ef784fb | 2015-10-30 12:03:06 -0700 | [diff] [blame] | 298 | return true; |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 299 | } |
| 300 | |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 301 | SkOpPtT* SkOpSegment::addMissing(double t, SkOpSegment* opp, SkChunkAlloc* allocator) { |
halcanary | 96fcdcc | 2015-08-27 07:41:13 -0700 | [diff] [blame] | 302 | SkOpSpanBase* existing = nullptr; |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 303 | SkOpSpanBase* test = &fHead; |
| 304 | double testT; |
commit-bot@chromium.org | 4431e77 | 2014-04-14 17:08:59 +0000 | [diff] [blame] | 305 | do { |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 306 | if ((testT = test->ptT()->fT) >= t) { |
| 307 | if (testT == t) { |
| 308 | existing = test; |
| 309 | } |
reed | 0dc4dd6 | 2015-03-24 13:55:33 -0700 | [diff] [blame] | 310 | break; |
| 311 | } |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 312 | } while ((test = test->upCast()->next())); |
| 313 | SkOpPtT* result; |
| 314 | if (existing && existing->contains(opp)) { |
| 315 | result = existing->ptT(); |
| 316 | } else { |
| 317 | result = this->addT(t, SkOpSegment::kNoAlias, allocator); |
| 318 | } |
| 319 | SkASSERT(result); |
| 320 | return result; |
commit-bot@chromium.org | 4431e77 | 2014-04-14 17:08:59 +0000 | [diff] [blame] | 321 | } |
| 322 | |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 323 | SkOpPtT* SkOpSegment::addT(double t, AllowAlias allowAlias, SkChunkAlloc* allocator) { |
reed | 0dc4dd6 | 2015-03-24 13:55:33 -0700 | [diff] [blame] | 324 | debugValidate(); |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 325 | SkPoint pt = this->ptAtT(t); |
| 326 | SkOpSpanBase* span = &fHead; |
| 327 | do { |
| 328 | SkOpPtT* result = span->ptT(); |
caryclark | 08bc848 | 2015-04-24 09:08:57 -0700 | [diff] [blame] | 329 | SkOpPtT* loop; |
| 330 | bool duplicatePt; |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 331 | if (t == result->fT) { |
caryclark | 08bc848 | 2015-04-24 09:08:57 -0700 | [diff] [blame] | 332 | goto bumpSpan; |
reed | 0dc4dd6 | 2015-03-24 13:55:33 -0700 | [diff] [blame] | 333 | } |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 334 | if (this->match(result, this, t, pt)) { |
| 335 | // see if any existing alias matches segment, pt, and t |
caryclark | 08bc848 | 2015-04-24 09:08:57 -0700 | [diff] [blame] | 336 | loop = result->next(); |
| 337 | duplicatePt = false; |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 338 | while (loop != result) { |
| 339 | bool ptMatch = loop->fPt == pt; |
| 340 | if (loop->segment() == this && loop->fT == t && ptMatch) { |
caryclark | 08bc848 | 2015-04-24 09:08:57 -0700 | [diff] [blame] | 341 | goto bumpSpan; |
reed | 0dc4dd6 | 2015-03-24 13:55:33 -0700 | [diff] [blame] | 342 | } |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 343 | duplicatePt |= ptMatch; |
| 344 | loop = loop->next(); |
reed | 0dc4dd6 | 2015-03-24 13:55:33 -0700 | [diff] [blame] | 345 | } |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 346 | if (kNoAlias == allowAlias) { |
caryclark | 08bc848 | 2015-04-24 09:08:57 -0700 | [diff] [blame] | 347 | bumpSpan: |
| 348 | span->bumpSpanAdds(); |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 349 | return result; |
| 350 | } |
| 351 | SkOpPtT* alias = SkOpTAllocator<SkOpPtT>::Allocate(allocator); |
| 352 | alias->init(result->span(), t, pt, duplicatePt); |
| 353 | result->insert(alias); |
| 354 | result->span()->unaligned(); |
| 355 | this->debugValidate(); |
| 356 | #if DEBUG_ADD_T |
| 357 | SkDebugf("%s alias t=%1.9g segID=%d spanID=%d\n", __FUNCTION__, t, |
| 358 | alias->segment()->debugID(), alias->span()->debugID()); |
| 359 | #endif |
caryclark | 08bc848 | 2015-04-24 09:08:57 -0700 | [diff] [blame] | 360 | span->bumpSpanAdds(); |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 361 | return alias; |
reed | 0dc4dd6 | 2015-03-24 13:55:33 -0700 | [diff] [blame] | 362 | } |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 363 | if (t < result->fT) { |
| 364 | SkOpSpan* prev = result->span()->prev(); |
caryclark | a3375e4 | 2015-12-07 12:18:02 -0800 | [diff] [blame] | 365 | if (!prev) { |
| 366 | return nullptr; |
| 367 | } |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 368 | SkOpSpan* span = insert(prev, allocator); |
| 369 | span->init(this, prev, t, pt); |
| 370 | this->debugValidate(); |
| 371 | #if DEBUG_ADD_T |
| 372 | SkDebugf("%s insert t=%1.9g segID=%d spanID=%d\n", __FUNCTION__, t, |
| 373 | span->segment()->debugID(), span->debugID()); |
| 374 | #endif |
caryclark | 08bc848 | 2015-04-24 09:08:57 -0700 | [diff] [blame] | 375 | span->bumpSpanAdds(); |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 376 | return span->ptT(); |
| 377 | } |
| 378 | SkASSERT(span != &fTail); |
| 379 | } while ((span = span->upCast()->next())); |
| 380 | SkASSERT(0); |
halcanary | 96fcdcc | 2015-08-27 07:41:13 -0700 | [diff] [blame] | 381 | return nullptr; |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 382 | } |
| 383 | |
| 384 | // choose a solitary t and pt value; remove aliases; align the opposite ends |
| 385 | void SkOpSegment::align() { |
| 386 | debugValidate(); |
| 387 | SkOpSpanBase* span = &fHead; |
| 388 | if (!span->aligned()) { |
| 389 | span->alignEnd(0, fPts[0]); |
| 390 | } |
| 391 | while ((span = span->upCast()->next())) { |
| 392 | if (span == &fTail) { |
| 393 | break; |
| 394 | } |
| 395 | span->align(); |
| 396 | } |
| 397 | if (!span->aligned()) { |
| 398 | span->alignEnd(1, fPts[SkPathOpsVerbToPoints(fVerb)]); |
reed | 0dc4dd6 | 2015-03-24 13:55:33 -0700 | [diff] [blame] | 399 | } |
caryclark | bca19f7 | 2015-05-13 08:23:48 -0700 | [diff] [blame] | 400 | if (this->collapsed()) { |
| 401 | SkOpSpan* span = &fHead; |
| 402 | do { |
| 403 | span->setWindValue(0); |
| 404 | span->setOppValue(0); |
| 405 | this->markDone(span); |
| 406 | } while ((span = span->next()->upCastable())); |
| 407 | } |
reed | 0dc4dd6 | 2015-03-24 13:55:33 -0700 | [diff] [blame] | 408 | debugValidate(); |
| 409 | } |
| 410 | |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 411 | void SkOpSegment::calcAngles(SkChunkAlloc* allocator) { |
| 412 | bool activePrior = !fHead.isCanceled(); |
| 413 | if (activePrior && !fHead.simple()) { |
| 414 | addStartSpan(allocator); |
reed | 0dc4dd6 | 2015-03-24 13:55:33 -0700 | [diff] [blame] | 415 | } |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 416 | SkOpSpan* prior = &fHead; |
| 417 | SkOpSpanBase* spanBase = fHead.next(); |
| 418 | while (spanBase != &fTail) { |
| 419 | if (activePrior) { |
| 420 | SkOpAngle* priorAngle = SkOpTAllocator<SkOpAngle>::Allocate(allocator); |
| 421 | priorAngle->set(spanBase, prior); |
| 422 | spanBase->setFromAngle(priorAngle); |
reed | 0dc4dd6 | 2015-03-24 13:55:33 -0700 | [diff] [blame] | 423 | } |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 424 | SkOpSpan* span = spanBase->upCast(); |
| 425 | bool active = !span->isCanceled(); |
| 426 | SkOpSpanBase* next = span->next(); |
| 427 | if (active) { |
| 428 | SkOpAngle* angle = SkOpTAllocator<SkOpAngle>::Allocate(allocator); |
| 429 | angle->set(span, next); |
| 430 | span->setToAngle(angle); |
reed | 0dc4dd6 | 2015-03-24 13:55:33 -0700 | [diff] [blame] | 431 | } |
reed | 0dc4dd6 | 2015-03-24 13:55:33 -0700 | [diff] [blame] | 432 | activePrior = active; |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 433 | prior = span; |
| 434 | spanBase = next; |
reed | 0dc4dd6 | 2015-03-24 13:55:33 -0700 | [diff] [blame] | 435 | } |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 436 | if (activePrior && !fTail.simple()) { |
| 437 | addEndSpan(allocator); |
reed | 0dc4dd6 | 2015-03-24 13:55:33 -0700 | [diff] [blame] | 438 | } |
reed | 0dc4dd6 | 2015-03-24 13:55:33 -0700 | [diff] [blame] | 439 | } |
| 440 | |
caryclark | bca19f7 | 2015-05-13 08:23:48 -0700 | [diff] [blame] | 441 | bool SkOpSegment::collapsed() const { |
| 442 | return fVerb == SkPath::kLine_Verb && fHead.pt() == fTail.pt(); |
| 443 | } |
| 444 | |
caryclark@google.com | 570863f | 2013-09-16 15:55:01 +0000 | [diff] [blame] | 445 | void SkOpSegment::ComputeOneSum(const SkOpAngle* baseAngle, SkOpAngle* nextAngle, |
| 446 | SkOpAngle::IncludeType includeType) { |
caryclark | 624637c | 2015-05-11 07:21:27 -0700 | [diff] [blame] | 447 | SkOpSegment* baseSegment = baseAngle->segment(); |
caryclark@google.com | 570863f | 2013-09-16 15:55:01 +0000 | [diff] [blame] | 448 | int sumMiWinding = baseSegment->updateWindingReverse(baseAngle); |
| 449 | int sumSuWinding; |
| 450 | bool binary = includeType >= SkOpAngle::kBinarySingle; |
| 451 | if (binary) { |
| 452 | sumSuWinding = baseSegment->updateOppWindingReverse(baseAngle); |
| 453 | if (baseSegment->operand()) { |
| 454 | SkTSwap<int>(sumMiWinding, sumSuWinding); |
| 455 | } |
| 456 | } |
| 457 | SkOpSegment* nextSegment = nextAngle->segment(); |
| 458 | int maxWinding, sumWinding; |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 459 | SkOpSpanBase* last; |
caryclark@google.com | 570863f | 2013-09-16 15:55:01 +0000 | [diff] [blame] | 460 | if (binary) { |
| 461 | int oppMaxWinding, oppSumWinding; |
| 462 | nextSegment->setUpWindings(nextAngle->start(), nextAngle->end(), &sumMiWinding, |
| 463 | &sumSuWinding, &maxWinding, &sumWinding, &oppMaxWinding, &oppSumWinding); |
| 464 | last = nextSegment->markAngle(maxWinding, sumWinding, oppMaxWinding, oppSumWinding, |
commit-bot@chromium.org | 866f4e3 | 2013-11-21 17:04:29 +0000 | [diff] [blame] | 465 | nextAngle); |
caryclark@google.com | 570863f | 2013-09-16 15:55:01 +0000 | [diff] [blame] | 466 | } else { |
| 467 | nextSegment->setUpWindings(nextAngle->start(), nextAngle->end(), &sumMiWinding, |
| 468 | &maxWinding, &sumWinding); |
commit-bot@chromium.org | 866f4e3 | 2013-11-21 17:04:29 +0000 | [diff] [blame] | 469 | last = nextSegment->markAngle(maxWinding, sumWinding, nextAngle); |
caryclark@google.com | 570863f | 2013-09-16 15:55:01 +0000 | [diff] [blame] | 470 | } |
| 471 | nextAngle->setLastMarked(last); |
| 472 | } |
| 473 | |
caryclark | 624637c | 2015-05-11 07:21:27 -0700 | [diff] [blame] | 474 | void SkOpSegment::ComputeOneSumReverse(SkOpAngle* baseAngle, SkOpAngle* nextAngle, |
caryclark@google.com | 570863f | 2013-09-16 15:55:01 +0000 | [diff] [blame] | 475 | SkOpAngle::IncludeType includeType) { |
caryclark | 624637c | 2015-05-11 07:21:27 -0700 | [diff] [blame] | 476 | SkOpSegment* baseSegment = baseAngle->segment(); |
caryclark@google.com | 570863f | 2013-09-16 15:55:01 +0000 | [diff] [blame] | 477 | int sumMiWinding = baseSegment->updateWinding(baseAngle); |
| 478 | int sumSuWinding; |
| 479 | bool binary = includeType >= SkOpAngle::kBinarySingle; |
| 480 | if (binary) { |
| 481 | sumSuWinding = baseSegment->updateOppWinding(baseAngle); |
| 482 | if (baseSegment->operand()) { |
| 483 | SkTSwap<int>(sumMiWinding, sumSuWinding); |
| 484 | } |
| 485 | } |
| 486 | SkOpSegment* nextSegment = nextAngle->segment(); |
| 487 | int maxWinding, sumWinding; |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 488 | SkOpSpanBase* last; |
caryclark@google.com | 570863f | 2013-09-16 15:55:01 +0000 | [diff] [blame] | 489 | if (binary) { |
| 490 | int oppMaxWinding, oppSumWinding; |
| 491 | nextSegment->setUpWindings(nextAngle->end(), nextAngle->start(), &sumMiWinding, |
| 492 | &sumSuWinding, &maxWinding, &sumWinding, &oppMaxWinding, &oppSumWinding); |
| 493 | last = nextSegment->markAngle(maxWinding, sumWinding, oppMaxWinding, oppSumWinding, |
commit-bot@chromium.org | 866f4e3 | 2013-11-21 17:04:29 +0000 | [diff] [blame] | 494 | nextAngle); |
caryclark@google.com | 570863f | 2013-09-16 15:55:01 +0000 | [diff] [blame] | 495 | } else { |
| 496 | nextSegment->setUpWindings(nextAngle->end(), nextAngle->start(), &sumMiWinding, |
| 497 | &maxWinding, &sumWinding); |
commit-bot@chromium.org | 866f4e3 | 2013-11-21 17:04:29 +0000 | [diff] [blame] | 498 | last = nextSegment->markAngle(maxWinding, sumWinding, nextAngle); |
caryclark@google.com | 570863f | 2013-09-16 15:55:01 +0000 | [diff] [blame] | 499 | } |
| 500 | nextAngle->setLastMarked(last); |
| 501 | } |
| 502 | |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 503 | // at this point, the span is already ordered, or unorderable |
| 504 | int SkOpSegment::computeSum(SkOpSpanBase* start, SkOpSpanBase* end, |
| 505 | SkOpAngle::IncludeType includeType) { |
| 506 | SkASSERT(includeType != SkOpAngle::kUnaryXor); |
| 507 | SkOpAngle* firstAngle = this->spanToAngle(end, start); |
halcanary | 96fcdcc | 2015-08-27 07:41:13 -0700 | [diff] [blame] | 508 | if (nullptr == firstAngle || nullptr == firstAngle->next()) { |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 509 | return SK_NaN32; |
| 510 | } |
| 511 | // if all angles have a computed winding, |
| 512 | // or if no adjacent angles are orderable, |
| 513 | // or if adjacent orderable angles have no computed winding, |
| 514 | // there's nothing to do |
| 515 | // if two orderable angles are adjacent, and both are next to orderable angles, |
| 516 | // and one has winding computed, transfer to the other |
halcanary | 96fcdcc | 2015-08-27 07:41:13 -0700 | [diff] [blame] | 517 | SkOpAngle* baseAngle = nullptr; |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 518 | bool tryReverse = false; |
| 519 | // look for counterclockwise transfers |
| 520 | SkOpAngle* angle = firstAngle->previous(); |
| 521 | SkOpAngle* next = angle->next(); |
| 522 | firstAngle = next; |
commit-bot@chromium.org | 8cb1daa | 2014-04-25 12:59:11 +0000 | [diff] [blame] | 523 | do { |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 524 | SkOpAngle* prior = angle; |
| 525 | angle = next; |
| 526 | next = angle->next(); |
| 527 | SkASSERT(prior->next() == angle); |
| 528 | SkASSERT(angle->next() == next); |
| 529 | if (prior->unorderable() || angle->unorderable() || next->unorderable()) { |
halcanary | 96fcdcc | 2015-08-27 07:41:13 -0700 | [diff] [blame] | 530 | baseAngle = nullptr; |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 531 | continue; |
commit-bot@chromium.org | 8cb1daa | 2014-04-25 12:59:11 +0000 | [diff] [blame] | 532 | } |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 533 | int testWinding = angle->starter()->windSum(); |
| 534 | if (SK_MinS32 != testWinding) { |
| 535 | baseAngle = angle; |
| 536 | tryReverse = true; |
| 537 | continue; |
reed | 0dc4dd6 | 2015-03-24 13:55:33 -0700 | [diff] [blame] | 538 | } |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 539 | if (baseAngle) { |
| 540 | ComputeOneSum(baseAngle, angle, includeType); |
halcanary | 96fcdcc | 2015-08-27 07:41:13 -0700 | [diff] [blame] | 541 | baseAngle = SK_MinS32 != angle->starter()->windSum() ? angle : nullptr; |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 542 | } |
| 543 | } while (next != firstAngle); |
| 544 | if (baseAngle && SK_MinS32 == firstAngle->starter()->windSum()) { |
| 545 | firstAngle = baseAngle; |
| 546 | tryReverse = true; |
| 547 | } |
| 548 | if (tryReverse) { |
halcanary | 96fcdcc | 2015-08-27 07:41:13 -0700 | [diff] [blame] | 549 | baseAngle = nullptr; |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 550 | SkOpAngle* prior = firstAngle; |
| 551 | do { |
| 552 | angle = prior; |
| 553 | prior = angle->previous(); |
| 554 | SkASSERT(prior->next() == angle); |
| 555 | next = angle->next(); |
| 556 | if (prior->unorderable() || angle->unorderable() || next->unorderable()) { |
halcanary | 96fcdcc | 2015-08-27 07:41:13 -0700 | [diff] [blame] | 557 | baseAngle = nullptr; |
reed | 0dc4dd6 | 2015-03-24 13:55:33 -0700 | [diff] [blame] | 558 | continue; |
| 559 | } |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 560 | int testWinding = angle->starter()->windSum(); |
| 561 | if (SK_MinS32 != testWinding) { |
| 562 | baseAngle = angle; |
| 563 | continue; |
reed | 0dc4dd6 | 2015-03-24 13:55:33 -0700 | [diff] [blame] | 564 | } |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 565 | if (baseAngle) { |
| 566 | ComputeOneSumReverse(baseAngle, angle, includeType); |
halcanary | 96fcdcc | 2015-08-27 07:41:13 -0700 | [diff] [blame] | 567 | baseAngle = SK_MinS32 != angle->starter()->windSum() ? angle : nullptr; |
reed | 0dc4dd6 | 2015-03-24 13:55:33 -0700 | [diff] [blame] | 568 | } |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 569 | } while (prior != firstAngle); |
reed | 0dc4dd6 | 2015-03-24 13:55:33 -0700 | [diff] [blame] | 570 | } |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 571 | return start->starter(end)->windSum(); |
reed | 0dc4dd6 | 2015-03-24 13:55:33 -0700 | [diff] [blame] | 572 | } |
| 573 | |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 574 | void SkOpSegment::detach(const SkOpSpan* span) { |
| 575 | if (span->done()) { |
caryclark | 08bc848 | 2015-04-24 09:08:57 -0700 | [diff] [blame] | 576 | --fDoneCount; |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 577 | } |
caryclark | 08bc848 | 2015-04-24 09:08:57 -0700 | [diff] [blame] | 578 | --fCount; |
| 579 | SkASSERT(fCount >= fDoneCount); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 580 | } |
| 581 | |
caryclark | 26ad22a | 2015-10-16 09:03:38 -0700 | [diff] [blame] | 582 | double SkOpSegment::distSq(double t, const SkOpAngle* oppAngle) const { |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 583 | SkDPoint testPt = this->dPtAtT(t); |
| 584 | SkDLine testPerp = {{ testPt, testPt }}; |
| 585 | SkDVector slope = this->dSlopeAtT(t); |
| 586 | testPerp[1].fX += slope.fY; |
| 587 | testPerp[1].fY -= slope.fX; |
| 588 | SkIntersections i; |
caryclark | 26ad22a | 2015-10-16 09:03:38 -0700 | [diff] [blame] | 589 | const SkOpSegment* oppSegment = oppAngle->segment(); |
caryclark | 1049f12 | 2015-04-20 08:31:59 -0700 | [diff] [blame] | 590 | (*CurveIntersectRay[oppSegment->verb()])(oppSegment->pts(), oppSegment->weight(), testPerp, &i); |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 591 | double closestDistSq = SK_ScalarInfinity; |
| 592 | for (int index = 0; index < i.used(); ++index) { |
| 593 | if (!between(oppAngle->start()->t(), i[0][index], oppAngle->end()->t())) { |
commit-bot@chromium.org | 4431e77 | 2014-04-14 17:08:59 +0000 | [diff] [blame] | 594 | continue; |
| 595 | } |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 596 | double testDistSq = testPt.distanceSquared(i.pt(index)); |
| 597 | if (closestDistSq > testDistSq) { |
| 598 | closestDistSq = testDistSq; |
commit-bot@chromium.org | 4431e77 | 2014-04-14 17:08:59 +0000 | [diff] [blame] | 599 | } |
| 600 | } |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 601 | return closestDistSq; |
commit-bot@chromium.org | 4431e77 | 2014-04-14 17:08:59 +0000 | [diff] [blame] | 602 | } |
| 603 | |
caryclark | d434972 | 2015-07-23 12:40:22 -0700 | [diff] [blame] | 604 | void SkOpSegment::findCollapsed() { |
| 605 | if (fHead.contains(&fTail)) { |
| 606 | markAllDone(); |
| 607 | // move start and end to the same point |
| 608 | fHead.alignEnd(0, fHead.pt()); |
| 609 | fTail.setAligned(); |
| 610 | } |
| 611 | } |
| 612 | |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 613 | /* |
| 614 | The M and S variable name parts stand for the operators. |
| 615 | Mi stands for Minuend (see wiki subtraction, analogous to difference) |
| 616 | Su stands for Subtrahend |
| 617 | The Opp variable name part designates that the value is for the Opposite operator. |
| 618 | Opposite values result from combining coincident spans. |
| 619 | */ |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 620 | SkOpSegment* SkOpSegment::findNextOp(SkTDArray<SkOpSpanBase*>* chase, SkOpSpanBase** nextStart, |
| 621 | SkOpSpanBase** nextEnd, bool* unsortable, SkPathOp op, int xorMiMask, int xorSuMask) { |
| 622 | SkOpSpanBase* start = *nextStart; |
| 623 | SkOpSpanBase* end = *nextEnd; |
| 624 | SkASSERT(start != end); |
| 625 | int step = start->step(end); |
| 626 | SkOpSegment* other = this->isSimple(nextStart, &step); // advances nextStart |
| 627 | if (other) { |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 628 | // mark the smaller of startIndex, endIndex done, and all adjacent |
| 629 | // spans with the same T value (but not 'other' spans) |
| 630 | #if DEBUG_WINDING |
| 631 | SkDebugf("%s simple\n", __FUNCTION__); |
| 632 | #endif |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 633 | SkOpSpan* startSpan = start->starter(end); |
| 634 | if (startSpan->done()) { |
halcanary | 96fcdcc | 2015-08-27 07:41:13 -0700 | [diff] [blame] | 635 | return nullptr; |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 636 | } |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 637 | markDone(startSpan); |
| 638 | *nextEnd = step > 0 ? (*nextStart)->upCast()->next() : (*nextStart)->prev(); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 639 | return other; |
| 640 | } |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 641 | SkOpSpanBase* endNear = step > 0 ? (*nextStart)->upCast()->next() : (*nextStart)->prev(); |
| 642 | SkASSERT(endNear == end); // is this ever not end? |
| 643 | SkASSERT(endNear); |
| 644 | SkASSERT(start != endNear); |
| 645 | SkASSERT((start->t() < endNear->t()) ^ (step < 0)); |
commit-bot@chromium.org | 4431e77 | 2014-04-14 17:08:59 +0000 | [diff] [blame] | 646 | // more than one viable candidate -- measure angles to find best |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 647 | int calcWinding = computeSum(start, endNear, SkOpAngle::kBinaryOpp); |
caryclark@google.com | 570863f | 2013-09-16 15:55:01 +0000 | [diff] [blame] | 648 | bool sortable = calcWinding != SK_NaN32; |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 649 | if (!sortable) { |
| 650 | *unsortable = true; |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 651 | markDone(start->starter(end)); |
halcanary | 96fcdcc | 2015-08-27 07:41:13 -0700 | [diff] [blame] | 652 | return nullptr; |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 653 | } |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 654 | SkOpAngle* angle = this->spanToAngle(end, start); |
commit-bot@chromium.org | 4431e77 | 2014-04-14 17:08:59 +0000 | [diff] [blame] | 655 | if (angle->unorderable()) { |
| 656 | *unsortable = true; |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 657 | markDone(start->starter(end)); |
halcanary | 96fcdcc | 2015-08-27 07:41:13 -0700 | [diff] [blame] | 658 | return nullptr; |
commit-bot@chromium.org | 4431e77 | 2014-04-14 17:08:59 +0000 | [diff] [blame] | 659 | } |
| 660 | #if DEBUG_SORT |
| 661 | SkDebugf("%s\n", __FUNCTION__); |
| 662 | angle->debugLoop(); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 663 | #endif |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 664 | int sumMiWinding = updateWinding(end, start); |
commit-bot@chromium.org | 8cb1daa | 2014-04-25 12:59:11 +0000 | [diff] [blame] | 665 | if (sumMiWinding == SK_MinS32) { |
| 666 | *unsortable = true; |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 667 | markDone(start->starter(end)); |
halcanary | 96fcdcc | 2015-08-27 07:41:13 -0700 | [diff] [blame] | 668 | return nullptr; |
commit-bot@chromium.org | 8cb1daa | 2014-04-25 12:59:11 +0000 | [diff] [blame] | 669 | } |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 670 | int sumSuWinding = updateOppWinding(end, start); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 671 | if (operand()) { |
| 672 | SkTSwap<int>(sumMiWinding, sumSuWinding); |
| 673 | } |
commit-bot@chromium.org | 4431e77 | 2014-04-14 17:08:59 +0000 | [diff] [blame] | 674 | SkOpAngle* nextAngle = angle->next(); |
halcanary | 96fcdcc | 2015-08-27 07:41:13 -0700 | [diff] [blame] | 675 | const SkOpAngle* foundAngle = nullptr; |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 676 | bool foundDone = false; |
| 677 | // iterate through the angle, and compute everyone's winding |
| 678 | SkOpSegment* nextSegment; |
| 679 | int activeCount = 0; |
| 680 | do { |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 681 | nextSegment = nextAngle->segment(); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 682 | bool activeAngle = nextSegment->activeOp(xorMiMask, xorSuMask, nextAngle->start(), |
commit-bot@chromium.org | 4431e77 | 2014-04-14 17:08:59 +0000 | [diff] [blame] | 683 | nextAngle->end(), op, &sumMiWinding, &sumSuWinding); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 684 | if (activeAngle) { |
| 685 | ++activeCount; |
| 686 | if (!foundAngle || (foundDone && activeCount & 1)) { |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 687 | foundAngle = nextAngle; |
caryclark@google.com | 570863f | 2013-09-16 15:55:01 +0000 | [diff] [blame] | 688 | foundDone = nextSegment->done(nextAngle); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 689 | } |
| 690 | } |
| 691 | if (nextSegment->done()) { |
| 692 | continue; |
| 693 | } |
reed | 0dc4dd6 | 2015-03-24 13:55:33 -0700 | [diff] [blame] | 694 | if (!activeAngle) { |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 695 | (void) nextSegment->markAndChaseDone(nextAngle->start(), nextAngle->end()); |
reed | 0dc4dd6 | 2015-03-24 13:55:33 -0700 | [diff] [blame] | 696 | } |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 697 | SkOpSpanBase* last = nextAngle->lastMarked(); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 698 | if (last) { |
commit-bot@chromium.org | 4431e77 | 2014-04-14 17:08:59 +0000 | [diff] [blame] | 699 | SkASSERT(!SkPathOpsDebug::ChaseContains(*chase, last)); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 700 | *chase->append() = last; |
| 701 | #if DEBUG_WINDING |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 702 | SkDebugf("%s chase.append segment=%d span=%d", __FUNCTION__, |
| 703 | last->segment()->debugID(), last->debugID()); |
| 704 | if (!last->final()) { |
| 705 | SkDebugf(" windSum=%d", last->upCast()->windSum()); |
| 706 | } |
| 707 | SkDebugf("\n"); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 708 | #endif |
| 709 | } |
commit-bot@chromium.org | 4431e77 | 2014-04-14 17:08:59 +0000 | [diff] [blame] | 710 | } while ((nextAngle = nextAngle->next()) != angle); |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 711 | start->segment()->markDone(start->starter(end)); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 712 | if (!foundAngle) { |
halcanary | 96fcdcc | 2015-08-27 07:41:13 -0700 | [diff] [blame] | 713 | return nullptr; |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 714 | } |
| 715 | *nextStart = foundAngle->start(); |
| 716 | *nextEnd = foundAngle->end(); |
| 717 | nextSegment = foundAngle->segment(); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 718 | #if DEBUG_WINDING |
| 719 | SkDebugf("%s from:[%d] to:[%d] start=%d end=%d\n", |
| 720 | __FUNCTION__, debugID(), nextSegment->debugID(), *nextStart, *nextEnd); |
| 721 | #endif |
| 722 | return nextSegment; |
| 723 | } |
| 724 | |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 725 | SkOpSegment* SkOpSegment::findNextWinding(SkTDArray<SkOpSpanBase*>* chase, |
| 726 | SkOpSpanBase** nextStart, SkOpSpanBase** nextEnd, bool* unsortable) { |
| 727 | SkOpSpanBase* start = *nextStart; |
| 728 | SkOpSpanBase* end = *nextEnd; |
| 729 | SkASSERT(start != end); |
| 730 | int step = start->step(end); |
| 731 | SkOpSegment* other = this->isSimple(nextStart, &step); // advances nextStart |
| 732 | if (other) { |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 733 | // mark the smaller of startIndex, endIndex done, and all adjacent |
| 734 | // spans with the same T value (but not 'other' spans) |
| 735 | #if DEBUG_WINDING |
| 736 | SkDebugf("%s simple\n", __FUNCTION__); |
| 737 | #endif |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 738 | SkOpSpan* startSpan = start->starter(end); |
| 739 | if (startSpan->done()) { |
halcanary | 96fcdcc | 2015-08-27 07:41:13 -0700 | [diff] [blame] | 740 | return nullptr; |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 741 | } |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 742 | markDone(startSpan); |
| 743 | *nextEnd = step > 0 ? (*nextStart)->upCast()->next() : (*nextStart)->prev(); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 744 | return other; |
| 745 | } |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 746 | SkOpSpanBase* endNear = step > 0 ? (*nextStart)->upCast()->next() : (*nextStart)->prev(); |
| 747 | SkASSERT(endNear == end); // is this ever not end? |
| 748 | SkASSERT(endNear); |
| 749 | SkASSERT(start != endNear); |
| 750 | SkASSERT((start->t() < endNear->t()) ^ (step < 0)); |
commit-bot@chromium.org | 4431e77 | 2014-04-14 17:08:59 +0000 | [diff] [blame] | 751 | // more than one viable candidate -- measure angles to find best |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 752 | int calcWinding = computeSum(start, endNear, SkOpAngle::kUnaryWinding); |
caryclark@google.com | 570863f | 2013-09-16 15:55:01 +0000 | [diff] [blame] | 753 | bool sortable = calcWinding != SK_NaN32; |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 754 | if (!sortable) { |
| 755 | *unsortable = true; |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 756 | markDone(start->starter(end)); |
halcanary | 96fcdcc | 2015-08-27 07:41:13 -0700 | [diff] [blame] | 757 | return nullptr; |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 758 | } |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 759 | SkOpAngle* angle = this->spanToAngle(end, start); |
| 760 | if (angle->unorderable()) { |
| 761 | *unsortable = true; |
| 762 | markDone(start->starter(end)); |
halcanary | 96fcdcc | 2015-08-27 07:41:13 -0700 | [diff] [blame] | 763 | return nullptr; |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 764 | } |
commit-bot@chromium.org | 4431e77 | 2014-04-14 17:08:59 +0000 | [diff] [blame] | 765 | #if DEBUG_SORT |
| 766 | SkDebugf("%s\n", __FUNCTION__); |
| 767 | angle->debugLoop(); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 768 | #endif |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 769 | int sumWinding = updateWinding(end, start); |
commit-bot@chromium.org | 4431e77 | 2014-04-14 17:08:59 +0000 | [diff] [blame] | 770 | SkOpAngle* nextAngle = angle->next(); |
halcanary | 96fcdcc | 2015-08-27 07:41:13 -0700 | [diff] [blame] | 771 | const SkOpAngle* foundAngle = nullptr; |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 772 | bool foundDone = false; |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 773 | // iterate through the angle, and compute everyone's winding |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 774 | SkOpSegment* nextSegment; |
| 775 | int activeCount = 0; |
| 776 | do { |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 777 | nextSegment = nextAngle->segment(); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 778 | bool activeAngle = nextSegment->activeWinding(nextAngle->start(), nextAngle->end(), |
commit-bot@chromium.org | 4431e77 | 2014-04-14 17:08:59 +0000 | [diff] [blame] | 779 | &sumWinding); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 780 | if (activeAngle) { |
| 781 | ++activeCount; |
| 782 | if (!foundAngle || (foundDone && activeCount & 1)) { |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 783 | foundAngle = nextAngle; |
| 784 | foundDone = nextSegment->done(nextAngle); |
| 785 | } |
| 786 | } |
| 787 | if (nextSegment->done()) { |
| 788 | continue; |
| 789 | } |
reed | 0dc4dd6 | 2015-03-24 13:55:33 -0700 | [diff] [blame] | 790 | if (!activeAngle) { |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 791 | (void) nextSegment->markAndChaseDone(nextAngle->start(), nextAngle->end()); |
reed | 0dc4dd6 | 2015-03-24 13:55:33 -0700 | [diff] [blame] | 792 | } |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 793 | SkOpSpanBase* last = nextAngle->lastMarked(); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 794 | if (last) { |
commit-bot@chromium.org | 4431e77 | 2014-04-14 17:08:59 +0000 | [diff] [blame] | 795 | SkASSERT(!SkPathOpsDebug::ChaseContains(*chase, last)); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 796 | *chase->append() = last; |
| 797 | #if DEBUG_WINDING |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 798 | SkDebugf("%s chase.append segment=%d span=%d", __FUNCTION__, |
| 799 | last->segment()->debugID(), last->debugID()); |
| 800 | if (!last->final()) { |
| 801 | SkDebugf(" windSum=%d", last->upCast()->windSum()); |
| 802 | } |
| 803 | SkDebugf("\n"); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 804 | #endif |
| 805 | } |
commit-bot@chromium.org | 4431e77 | 2014-04-14 17:08:59 +0000 | [diff] [blame] | 806 | } while ((nextAngle = nextAngle->next()) != angle); |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 807 | start->segment()->markDone(start->starter(end)); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 808 | if (!foundAngle) { |
halcanary | 96fcdcc | 2015-08-27 07:41:13 -0700 | [diff] [blame] | 809 | return nullptr; |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 810 | } |
| 811 | *nextStart = foundAngle->start(); |
| 812 | *nextEnd = foundAngle->end(); |
| 813 | nextSegment = foundAngle->segment(); |
| 814 | #if DEBUG_WINDING |
| 815 | SkDebugf("%s from:[%d] to:[%d] start=%d end=%d\n", |
| 816 | __FUNCTION__, debugID(), nextSegment->debugID(), *nextStart, *nextEnd); |
| 817 | #endif |
| 818 | return nextSegment; |
| 819 | } |
| 820 | |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 821 | SkOpSegment* SkOpSegment::findNextXor(SkOpSpanBase** nextStart, SkOpSpanBase** nextEnd, |
| 822 | bool* unsortable) { |
| 823 | SkOpSpanBase* start = *nextStart; |
| 824 | SkOpSpanBase* end = *nextEnd; |
| 825 | SkASSERT(start != end); |
| 826 | int step = start->step(end); |
| 827 | SkOpSegment* other = this->isSimple(nextStart, &step); // advances nextStart |
| 828 | if (other) { |
| 829 | // mark the smaller of startIndex, endIndex done, and all adjacent |
| 830 | // spans with the same T value (but not 'other' spans) |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 831 | #if DEBUG_WINDING |
| 832 | SkDebugf("%s simple\n", __FUNCTION__); |
| 833 | #endif |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 834 | SkOpSpan* startSpan = start->starter(end); |
| 835 | if (startSpan->done()) { |
halcanary | 96fcdcc | 2015-08-27 07:41:13 -0700 | [diff] [blame] | 836 | return nullptr; |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 837 | } |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 838 | markDone(startSpan); |
| 839 | *nextEnd = step > 0 ? (*nextStart)->upCast()->next() : (*nextStart)->prev(); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 840 | return other; |
| 841 | } |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 842 | SkDEBUGCODE(SkOpSpanBase* endNear = step > 0 ? (*nextStart)->upCast()->next() \ |
| 843 | : (*nextStart)->prev()); |
| 844 | SkASSERT(endNear == end); // is this ever not end? |
| 845 | SkASSERT(endNear); |
| 846 | SkASSERT(start != endNear); |
| 847 | SkASSERT((start->t() < endNear->t()) ^ (step < 0)); |
| 848 | SkOpAngle* angle = this->spanToAngle(end, start); |
caryclark | 27c8eb8 | 2015-07-06 11:38:33 -0700 | [diff] [blame] | 849 | if (!angle || angle->unorderable()) { |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 850 | *unsortable = true; |
| 851 | markDone(start->starter(end)); |
halcanary | 96fcdcc | 2015-08-27 07:41:13 -0700 | [diff] [blame] | 852 | return nullptr; |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 853 | } |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 854 | #if DEBUG_SORT |
commit-bot@chromium.org | 4431e77 | 2014-04-14 17:08:59 +0000 | [diff] [blame] | 855 | SkDebugf("%s\n", __FUNCTION__); |
| 856 | angle->debugLoop(); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 857 | #endif |
commit-bot@chromium.org | 4431e77 | 2014-04-14 17:08:59 +0000 | [diff] [blame] | 858 | SkOpAngle* nextAngle = angle->next(); |
halcanary | 96fcdcc | 2015-08-27 07:41:13 -0700 | [diff] [blame] | 859 | const SkOpAngle* foundAngle = nullptr; |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 860 | bool foundDone = false; |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 861 | // iterate through the angle, and compute everyone's winding |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 862 | SkOpSegment* nextSegment; |
| 863 | int activeCount = 0; |
| 864 | do { |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 865 | nextSegment = nextAngle->segment(); |
| 866 | ++activeCount; |
| 867 | if (!foundAngle || (foundDone && activeCount & 1)) { |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 868 | foundAngle = nextAngle; |
commit-bot@chromium.org | 4431e77 | 2014-04-14 17:08:59 +0000 | [diff] [blame] | 869 | if (!(foundDone = nextSegment->done(nextAngle))) { |
| 870 | break; |
| 871 | } |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 872 | } |
commit-bot@chromium.org | 4431e77 | 2014-04-14 17:08:59 +0000 | [diff] [blame] | 873 | nextAngle = nextAngle->next(); |
| 874 | } while (nextAngle != angle); |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 875 | start->segment()->markDone(start->starter(end)); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 876 | if (!foundAngle) { |
halcanary | 96fcdcc | 2015-08-27 07:41:13 -0700 | [diff] [blame] | 877 | return nullptr; |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 878 | } |
| 879 | *nextStart = foundAngle->start(); |
| 880 | *nextEnd = foundAngle->end(); |
| 881 | nextSegment = foundAngle->segment(); |
| 882 | #if DEBUG_WINDING |
| 883 | SkDebugf("%s from:[%d] to:[%d] start=%d end=%d\n", |
| 884 | __FUNCTION__, debugID(), nextSegment->debugID(), *nextStart, *nextEnd); |
| 885 | #endif |
| 886 | return nextSegment; |
| 887 | } |
| 888 | |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 889 | SkOpGlobalState* SkOpSegment::globalState() const { |
| 890 | return contour()->globalState(); |
commit-bot@chromium.org | 4431e77 | 2014-04-14 17:08:59 +0000 | [diff] [blame] | 891 | } |
| 892 | |
caryclark | 1049f12 | 2015-04-20 08:31:59 -0700 | [diff] [blame] | 893 | void SkOpSegment::init(SkPoint pts[], SkScalar weight, SkOpContour* contour, SkPath::Verb verb) { |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 894 | fContour = contour; |
halcanary | 96fcdcc | 2015-08-27 07:41:13 -0700 | [diff] [blame] | 895 | fNext = nullptr; |
caryclark | 27c8eb8 | 2015-07-06 11:38:33 -0700 | [diff] [blame] | 896 | fOriginal[0] = pts[0]; |
| 897 | fOriginal[1] = pts[SkPathOpsVerbToPoints(verb)]; |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 898 | fPts = pts; |
caryclark | 1049f12 | 2015-04-20 08:31:59 -0700 | [diff] [blame] | 899 | fWeight = weight; |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 900 | fVerb = verb; |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 901 | fCount = 0; |
| 902 | fDoneCount = 0; |
| 903 | fVisited = false; |
| 904 | SkOpSpan* zeroSpan = &fHead; |
halcanary | 96fcdcc | 2015-08-27 07:41:13 -0700 | [diff] [blame] | 905 | zeroSpan->init(this, nullptr, 0, fPts[0]); |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 906 | SkOpSpanBase* oneSpan = &fTail; |
| 907 | zeroSpan->setNext(oneSpan); |
| 908 | oneSpan->initBase(this, zeroSpan, 1, fPts[SkPathOpsVerbToPoints(fVerb)]); |
caryclark | 1049f12 | 2015-04-20 08:31:59 -0700 | [diff] [blame] | 909 | SkDEBUGCODE(fID = globalState()->nextSegmentID()); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 910 | } |
| 911 | |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 912 | bool SkOpSegment::isClose(double t, const SkOpSegment* opp) const { |
| 913 | SkDPoint cPt = this->dPtAtT(t); |
caryclark | 1049f12 | 2015-04-20 08:31:59 -0700 | [diff] [blame] | 914 | SkDVector dxdy = (*CurveDSlopeAtT[this->verb()])(this->pts(), this->weight(), t); |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 915 | SkDLine perp = {{ cPt, {cPt.fX + dxdy.fY, cPt.fY - dxdy.fX} }}; |
| 916 | SkIntersections i; |
caryclark | 1049f12 | 2015-04-20 08:31:59 -0700 | [diff] [blame] | 917 | (*CurveIntersectRay[opp->verb()])(opp->pts(), opp->weight(), perp, &i); |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 918 | int used = i.used(); |
| 919 | for (int index = 0; index < used; ++index) { |
| 920 | if (cPt.roughlyEqual(i.pt(index))) { |
reed | 0dc4dd6 | 2015-03-24 13:55:33 -0700 | [diff] [blame] | 921 | return true; |
| 922 | } |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 923 | } |
caryclark@google.com | a2bbc6e | 2013-11-01 17:36:03 +0000 | [diff] [blame] | 924 | return false; |
| 925 | } |
| 926 | |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 927 | bool SkOpSegment::isXor() const { |
| 928 | return fContour->isXor(); |
| 929 | } |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 930 | |
caryclark | 5b5ddd7 | 2015-05-18 05:12:56 -0700 | [diff] [blame] | 931 | void SkOpSegment::markAllDone() { |
| 932 | SkOpSpan* span = this->head(); |
| 933 | do { |
| 934 | this->markDone(span); |
| 935 | } while ((span = span->next()->upCastable())); |
| 936 | } |
| 937 | |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 938 | SkOpSpanBase* SkOpSegment::markAndChaseDone(SkOpSpanBase* start, SkOpSpanBase* end) { |
| 939 | int step = start->step(end); |
| 940 | SkOpSpan* minSpan = start->starter(end); |
| 941 | markDone(minSpan); |
halcanary | 96fcdcc | 2015-08-27 07:41:13 -0700 | [diff] [blame] | 942 | SkOpSpanBase* last = nullptr; |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 943 | SkOpSegment* other = this; |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 944 | while ((other = other->nextChase(&start, &step, &minSpan, &last))) { |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 945 | if (other->done()) { |
caryclark | dac1d17 | 2014-06-17 05:15:38 -0700 | [diff] [blame] | 946 | SkASSERT(!last); |
| 947 | break; |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 948 | } |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 949 | other->markDone(minSpan); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 950 | } |
| 951 | return last; |
| 952 | } |
| 953 | |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 954 | bool SkOpSegment::markAndChaseWinding(SkOpSpanBase* start, SkOpSpanBase* end, int winding, |
| 955 | SkOpSpanBase** lastPtr) { |
| 956 | SkOpSpan* spanStart = start->starter(end); |
| 957 | int step = start->step(end); |
| 958 | bool success = markWinding(spanStart, winding); |
halcanary | 96fcdcc | 2015-08-27 07:41:13 -0700 | [diff] [blame] | 959 | SkOpSpanBase* last = nullptr; |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 960 | SkOpSegment* other = this; |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 961 | while ((other = other->nextChase(&start, &step, &spanStart, &last))) { |
| 962 | if (spanStart->windSum() != SK_MinS32) { |
| 963 | SkASSERT(spanStart->windSum() == winding); |
caryclark | dac1d17 | 2014-06-17 05:15:38 -0700 | [diff] [blame] | 964 | SkASSERT(!last); |
| 965 | break; |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 966 | } |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 967 | (void) other->markWinding(spanStart, winding); |
commit-bot@chromium.org | 4431e77 | 2014-04-14 17:08:59 +0000 | [diff] [blame] | 968 | } |
caryclark | 65f5531 | 2014-11-13 06:58:52 -0800 | [diff] [blame] | 969 | if (lastPtr) { |
| 970 | *lastPtr = last; |
| 971 | } |
| 972 | return success; |
commit-bot@chromium.org | 4431e77 | 2014-04-14 17:08:59 +0000 | [diff] [blame] | 973 | } |
| 974 | |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 975 | bool SkOpSegment::markAndChaseWinding(SkOpSpanBase* start, SkOpSpanBase* end, |
| 976 | int winding, int oppWinding, SkOpSpanBase** lastPtr) { |
| 977 | SkOpSpan* spanStart = start->starter(end); |
| 978 | int step = start->step(end); |
| 979 | bool success = markWinding(spanStart, winding, oppWinding); |
halcanary | 96fcdcc | 2015-08-27 07:41:13 -0700 | [diff] [blame] | 980 | SkOpSpanBase* last = nullptr; |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 981 | SkOpSegment* other = this; |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 982 | while ((other = other->nextChase(&start, &step, &spanStart, &last))) { |
| 983 | if (spanStart->windSum() != SK_MinS32) { |
| 984 | if (this->operand() == other->operand()) { |
caryclark | 624637c | 2015-05-11 07:21:27 -0700 | [diff] [blame] | 985 | if (spanStart->windSum() != winding || spanStart->oppSum() != oppWinding) { |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 986 | this->globalState()->setWindingFailed(); |
| 987 | return false; |
caryclark | dac1d17 | 2014-06-17 05:15:38 -0700 | [diff] [blame] | 988 | } |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 989 | } else { |
| 990 | SkASSERT(spanStart->windSum() == oppWinding); |
| 991 | SkASSERT(spanStart->oppSum() == winding); |
caryclark | dac1d17 | 2014-06-17 05:15:38 -0700 | [diff] [blame] | 992 | } |
| 993 | SkASSERT(!last); |
caryclark | dac1d17 | 2014-06-17 05:15:38 -0700 | [diff] [blame] | 994 | break; |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 995 | } |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 996 | if (this->operand() == other->operand()) { |
| 997 | (void) other->markWinding(spanStart, winding, oppWinding); |
caryclark | dac1d17 | 2014-06-17 05:15:38 -0700 | [diff] [blame] | 998 | } else { |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 999 | (void) other->markWinding(spanStart, oppWinding, winding); |
caryclark | dac1d17 | 2014-06-17 05:15:38 -0700 | [diff] [blame] | 1000 | } |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 1001 | } |
caryclark | 65f5531 | 2014-11-13 06:58:52 -0800 | [diff] [blame] | 1002 | if (lastPtr) { |
| 1003 | *lastPtr = last; |
| 1004 | } |
| 1005 | return success; |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 1006 | } |
| 1007 | |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 1008 | SkOpSpanBase* SkOpSegment::markAngle(int maxWinding, int sumWinding, const SkOpAngle* angle) { |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 1009 | SkASSERT(angle->segment() == this); |
| 1010 | if (UseInnerWinding(maxWinding, sumWinding)) { |
| 1011 | maxWinding = sumWinding; |
| 1012 | } |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 1013 | SkOpSpanBase* last; |
| 1014 | (void) markAndChaseWinding(angle->start(), angle->end(), maxWinding, &last); |
caryclark@google.com | 570863f | 2013-09-16 15:55:01 +0000 | [diff] [blame] | 1015 | #if DEBUG_WINDING |
| 1016 | if (last) { |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 1017 | SkDebugf("%s last seg=%d span=%d", __FUNCTION__, |
| 1018 | last->segment()->debugID(), last->debugID()); |
| 1019 | if (!last->final()) { |
| 1020 | SkDebugf(" windSum="); |
| 1021 | SkPathOpsDebug::WindingPrintf(last->upCast()->windSum()); |
| 1022 | } |
| 1023 | SkDebugf("\n"); |
caryclark@google.com | 570863f | 2013-09-16 15:55:01 +0000 | [diff] [blame] | 1024 | } |
| 1025 | #endif |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 1026 | return last; |
| 1027 | } |
| 1028 | |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 1029 | SkOpSpanBase* SkOpSegment::markAngle(int maxWinding, int sumWinding, int oppMaxWinding, |
| 1030 | int oppSumWinding, const SkOpAngle* angle) { |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 1031 | SkASSERT(angle->segment() == this); |
| 1032 | if (UseInnerWinding(maxWinding, sumWinding)) { |
| 1033 | maxWinding = sumWinding; |
| 1034 | } |
| 1035 | if (oppMaxWinding != oppSumWinding && UseInnerWinding(oppMaxWinding, oppSumWinding)) { |
| 1036 | oppMaxWinding = oppSumWinding; |
| 1037 | } |
halcanary | 96fcdcc | 2015-08-27 07:41:13 -0700 | [diff] [blame] | 1038 | SkOpSpanBase* last = nullptr; |
caryclark | 65f5531 | 2014-11-13 06:58:52 -0800 | [diff] [blame] | 1039 | // caller doesn't require that this marks anything |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 1040 | (void) markAndChaseWinding(angle->start(), angle->end(), maxWinding, oppMaxWinding, &last); |
caryclark@google.com | 570863f | 2013-09-16 15:55:01 +0000 | [diff] [blame] | 1041 | #if DEBUG_WINDING |
| 1042 | if (last) { |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 1043 | SkDebugf("%s last segment=%d span=%d", __FUNCTION__, |
| 1044 | last->segment()->debugID(), last->debugID()); |
| 1045 | if (!last->final()) { |
| 1046 | SkDebugf(" windSum="); |
| 1047 | SkPathOpsDebug::WindingPrintf(last->upCast()->windSum()); |
| 1048 | } |
| 1049 | SkDebugf(" \n"); |
caryclark@google.com | 570863f | 2013-09-16 15:55:01 +0000 | [diff] [blame] | 1050 | } |
| 1051 | #endif |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 1052 | return last; |
| 1053 | } |
| 1054 | |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 1055 | void SkOpSegment::markDone(SkOpSpan* span) { |
| 1056 | SkASSERT(this == span->segment()); |
| 1057 | if (span->done()) { |
| 1058 | return; |
| 1059 | } |
| 1060 | #if DEBUG_MARK_DONE |
| 1061 | debugShowNewWinding(__FUNCTION__, span, span->windSum(), span->oppSum()); |
| 1062 | #endif |
| 1063 | span->setDone(true); |
| 1064 | ++fDoneCount; |
| 1065 | debugValidate(); |
| 1066 | } |
| 1067 | |
| 1068 | bool SkOpSegment::markWinding(SkOpSpan* span, int winding) { |
| 1069 | SkASSERT(this == span->segment()); |
reed | 0dc4dd6 | 2015-03-24 13:55:33 -0700 | [diff] [blame] | 1070 | SkASSERT(winding); |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 1071 | if (span->done()) { |
reed | 0dc4dd6 | 2015-03-24 13:55:33 -0700 | [diff] [blame] | 1072 | return false; |
| 1073 | } |
| 1074 | #if DEBUG_MARK_DONE |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 1075 | debugShowNewWinding(__FUNCTION__, span, winding); |
reed | 0dc4dd6 | 2015-03-24 13:55:33 -0700 | [diff] [blame] | 1076 | #endif |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 1077 | span->setWindSum(winding); |
| 1078 | debugValidate(); |
reed | 0dc4dd6 | 2015-03-24 13:55:33 -0700 | [diff] [blame] | 1079 | return true; |
| 1080 | } |
| 1081 | |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 1082 | bool SkOpSegment::markWinding(SkOpSpan* span, int winding, int oppWinding) { |
| 1083 | SkASSERT(this == span->segment()); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 1084 | SkASSERT(winding || oppWinding); |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 1085 | if (span->done()) { |
| 1086 | return false; |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 1087 | } |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 1088 | #if DEBUG_MARK_DONE |
| 1089 | debugShowNewWinding(__FUNCTION__, span, winding, oppWinding); |
| 1090 | #endif |
| 1091 | span->setWindSum(winding); |
| 1092 | span->setOppSum(oppWinding); |
commit-bot@chromium.org | 4431e77 | 2014-04-14 17:08:59 +0000 | [diff] [blame] | 1093 | debugValidate(); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 1094 | return true; |
| 1095 | } |
| 1096 | |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 1097 | bool SkOpSegment::match(const SkOpPtT* base, const SkOpSegment* testParent, double testT, |
| 1098 | const SkPoint& testPt) const { |
| 1099 | const SkOpSegment* baseParent = base->segment(); |
| 1100 | if (this == baseParent && this == testParent && precisely_equal(base->fT, testT)) { |
| 1101 | return true; |
| 1102 | } |
| 1103 | if (!SkDPoint::ApproximatelyEqual(testPt, base->fPt)) { |
| 1104 | return false; |
| 1105 | } |
caryclark | 08bc848 | 2015-04-24 09:08:57 -0700 | [diff] [blame] | 1106 | return !this->ptsDisjoint(base->fT, base->fPt, testT, testPt); |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 1107 | } |
| 1108 | |
| 1109 | static SkOpSegment* set_last(SkOpSpanBase** last, SkOpSpanBase* endSpan) { |
| 1110 | if (last) { |
| 1111 | *last = endSpan; |
caryclark | dac1d17 | 2014-06-17 05:15:38 -0700 | [diff] [blame] | 1112 | } |
halcanary | 96fcdcc | 2015-08-27 07:41:13 -0700 | [diff] [blame] | 1113 | return nullptr; |
caryclark | dac1d17 | 2014-06-17 05:15:38 -0700 | [diff] [blame] | 1114 | } |
| 1115 | |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 1116 | SkOpSegment* SkOpSegment::nextChase(SkOpSpanBase** startPtr, int* stepPtr, SkOpSpan** minPtr, |
| 1117 | SkOpSpanBase** last) const { |
| 1118 | SkOpSpanBase* origStart = *startPtr; |
caryclark | dac1d17 | 2014-06-17 05:15:38 -0700 | [diff] [blame] | 1119 | int step = *stepPtr; |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 1120 | SkOpSpanBase* endSpan = step > 0 ? origStart->upCast()->next() : origStart->prev(); |
| 1121 | SkASSERT(endSpan); |
| 1122 | SkOpAngle* angle = step > 0 ? endSpan->fromAngle() : endSpan->upCast()->toAngle(); |
| 1123 | SkOpSpanBase* foundSpan; |
| 1124 | SkOpSpanBase* otherEnd; |
caryclark | dac1d17 | 2014-06-17 05:15:38 -0700 | [diff] [blame] | 1125 | SkOpSegment* other; |
halcanary | 96fcdcc | 2015-08-27 07:41:13 -0700 | [diff] [blame] | 1126 | if (angle == nullptr) { |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 1127 | if (endSpan->t() != 0 && endSpan->t() != 1) { |
halcanary | 96fcdcc | 2015-08-27 07:41:13 -0700 | [diff] [blame] | 1128 | return nullptr; |
caryclark | dac1d17 | 2014-06-17 05:15:38 -0700 | [diff] [blame] | 1129 | } |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 1130 | SkOpPtT* otherPtT = endSpan->ptT()->next(); |
| 1131 | other = otherPtT->segment(); |
| 1132 | foundSpan = otherPtT->span(); |
| 1133 | otherEnd = step > 0 ? foundSpan->upCast()->next() : foundSpan->prev(); |
caryclark | dac1d17 | 2014-06-17 05:15:38 -0700 | [diff] [blame] | 1134 | } else { |
| 1135 | int loopCount = angle->loopCount(); |
| 1136 | if (loopCount > 2) { |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 1137 | return set_last(last, endSpan); |
caryclark | dac1d17 | 2014-06-17 05:15:38 -0700 | [diff] [blame] | 1138 | } |
| 1139 | const SkOpAngle* next = angle->next(); |
halcanary | 96fcdcc | 2015-08-27 07:41:13 -0700 | [diff] [blame] | 1140 | if (nullptr == next) { |
| 1141 | return nullptr; |
caryclark | 65b427c | 2014-09-18 10:32:57 -0700 | [diff] [blame] | 1142 | } |
caryclark | dac1d17 | 2014-06-17 05:15:38 -0700 | [diff] [blame] | 1143 | #if DEBUG_WINDING |
caryclark | 624637c | 2015-05-11 07:21:27 -0700 | [diff] [blame] | 1144 | if (angle->debugSign() != next->debugSign() && !angle->segment()->contour()->isXor() |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 1145 | && !next->segment()->contour()->isXor()) { |
caryclark | dac1d17 | 2014-06-17 05:15:38 -0700 | [diff] [blame] | 1146 | SkDebugf("%s mismatched signs\n", __FUNCTION__); |
reed | 0dc4dd6 | 2015-03-24 13:55:33 -0700 | [diff] [blame] | 1147 | } |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 1148 | #endif |
caryclark | dac1d17 | 2014-06-17 05:15:38 -0700 | [diff] [blame] | 1149 | other = next->segment(); |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 1150 | foundSpan = endSpan = next->start(); |
caryclark | dac1d17 | 2014-06-17 05:15:38 -0700 | [diff] [blame] | 1151 | otherEnd = next->end(); |
caryclark@google.com | 570863f | 2013-09-16 15:55:01 +0000 | [diff] [blame] | 1152 | } |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 1153 | int foundStep = foundSpan->step(otherEnd); |
caryclark | dac1d17 | 2014-06-17 05:15:38 -0700 | [diff] [blame] | 1154 | if (*stepPtr != foundStep) { |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 1155 | return set_last(last, endSpan); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 1156 | } |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 1157 | SkASSERT(*startPtr); |
| 1158 | if (!otherEnd) { |
halcanary | 96fcdcc | 2015-08-27 07:41:13 -0700 | [diff] [blame] | 1159 | return nullptr; |
caryclark | 65b427c | 2014-09-18 10:32:57 -0700 | [diff] [blame] | 1160 | } |
| 1161 | // SkASSERT(otherEnd >= 0); |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 1162 | SkOpSpan* origMin = step < 0 ? origStart->prev() : origStart->upCast(); |
| 1163 | SkOpSpan* foundMin = foundSpan->starter(otherEnd); |
| 1164 | if (foundMin->windValue() != origMin->windValue() |
| 1165 | || foundMin->oppValue() != origMin->oppValue()) { |
| 1166 | return set_last(last, endSpan); |
caryclark | dac1d17 | 2014-06-17 05:15:38 -0700 | [diff] [blame] | 1167 | } |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 1168 | *startPtr = foundSpan; |
caryclark | dac1d17 | 2014-06-17 05:15:38 -0700 | [diff] [blame] | 1169 | *stepPtr = foundStep; |
| 1170 | if (minPtr) { |
| 1171 | *minPtr = foundMin; |
caryclark@google.com | a5e5592 | 2013-05-07 18:51:31 +0000 | [diff] [blame] | 1172 | } |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 1173 | return other; |
| 1174 | } |
| 1175 | |
caryclark | bca19f7 | 2015-05-13 08:23:48 -0700 | [diff] [blame] | 1176 | static void clear_visited(SkOpSpanBase* span) { |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 1177 | // reset visited flag back to false |
| 1178 | do { |
| 1179 | SkOpPtT* ptT = span->ptT(), * stopPtT = ptT; |
| 1180 | while ((ptT = ptT->next()) != stopPtT) { |
| 1181 | SkOpSegment* opp = ptT->segment(); |
| 1182 | opp->resetVisited(); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 1183 | } |
caryclark | bca19f7 | 2015-05-13 08:23:48 -0700 | [diff] [blame] | 1184 | } while (!span->final() && (span = span->upCast()->next())); |
reed | 0dc4dd6 | 2015-03-24 13:55:33 -0700 | [diff] [blame] | 1185 | } |
| 1186 | |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 1187 | // look for pairs of undetected coincident curves |
| 1188 | // assumes that segments going in have visited flag clear |
| 1189 | // curve/curve intersection should now do a pretty good job of finding coincident runs so |
| 1190 | // this may be only be necessary for line/curve pairs -- so skip unless this is a line and the |
| 1191 | // the opp is not a line |
caryclark | 27c8eb8 | 2015-07-06 11:38:33 -0700 | [diff] [blame] | 1192 | bool SkOpSegment::missingCoincidence(SkOpCoincidence* coincidences, SkChunkAlloc* allocator) { |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 1193 | if (this->verb() != SkPath::kLine_Verb) { |
caryclark | 27c8eb8 | 2015-07-06 11:38:33 -0700 | [diff] [blame] | 1194 | return false; |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 1195 | } |
caryclark | bca19f7 | 2015-05-13 08:23:48 -0700 | [diff] [blame] | 1196 | if (this->done()) { |
caryclark | 27c8eb8 | 2015-07-06 11:38:33 -0700 | [diff] [blame] | 1197 | return false; |
caryclark | bca19f7 | 2015-05-13 08:23:48 -0700 | [diff] [blame] | 1198 | } |
halcanary | 96fcdcc | 2015-08-27 07:41:13 -0700 | [diff] [blame] | 1199 | SkOpSpan* prior = nullptr; |
caryclark | bca19f7 | 2015-05-13 08:23:48 -0700 | [diff] [blame] | 1200 | SkOpSpanBase* spanBase = &fHead; |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 1201 | do { |
caryclark | bca19f7 | 2015-05-13 08:23:48 -0700 | [diff] [blame] | 1202 | SkOpPtT* ptT = spanBase->ptT(), * spanStopPtT = ptT; |
| 1203 | SkASSERT(ptT->span() == spanBase); |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 1204 | while ((ptT = ptT->next()) != spanStopPtT) { |
caryclark | 182b499 | 2015-05-14 05:45:54 -0700 | [diff] [blame] | 1205 | if (ptT->deleted()) { |
| 1206 | continue; |
| 1207 | } |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 1208 | SkOpSegment* opp = ptT->span()->segment(); |
caryclark | 26ad22a | 2015-10-16 09:03:38 -0700 | [diff] [blame] | 1209 | // if (opp->verb() == SkPath::kLine_Verb) { |
| 1210 | // continue; |
| 1211 | // } |
caryclark | bca19f7 | 2015-05-13 08:23:48 -0700 | [diff] [blame] | 1212 | if (opp->done()) { |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 1213 | continue; |
reed | 0dc4dd6 | 2015-03-24 13:55:33 -0700 | [diff] [blame] | 1214 | } |
caryclark | bca19f7 | 2015-05-13 08:23:48 -0700 | [diff] [blame] | 1215 | // when opp is encounted the 1st time, continue; on 2nd encounter, look for coincidence |
| 1216 | if (!opp->visited()) { |
| 1217 | continue; |
| 1218 | } |
| 1219 | if (spanBase == &fHead) { |
| 1220 | continue; |
| 1221 | } |
| 1222 | SkOpSpan* span = spanBase->upCastable(); |
| 1223 | // FIXME?: this assumes that if the opposite segment is coincident then no more |
| 1224 | // coincidence needs to be detected. This may not be true. |
| 1225 | if (span && span->containsCoincidence(opp)) { |
| 1226 | continue; |
| 1227 | } |
caryclark | 26ad22a | 2015-10-16 09:03:38 -0700 | [diff] [blame] | 1228 | if (spanBase->segment() == opp) { |
| 1229 | continue; |
| 1230 | } |
caryclark | bca19f7 | 2015-05-13 08:23:48 -0700 | [diff] [blame] | 1231 | if (spanBase->containsCoinEnd(opp)) { |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 1232 | continue; |
| 1233 | } |
halcanary | 96fcdcc | 2015-08-27 07:41:13 -0700 | [diff] [blame] | 1234 | SkOpPtT* priorPtT = nullptr, * priorStopPtT; |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 1235 | // find prior span containing opp segment |
halcanary | 96fcdcc | 2015-08-27 07:41:13 -0700 | [diff] [blame] | 1236 | SkOpSegment* priorOpp = nullptr; |
caryclark | bca19f7 | 2015-05-13 08:23:48 -0700 | [diff] [blame] | 1237 | SkOpSpan* priorTest = spanBase->prev(); |
| 1238 | while (!priorOpp && priorTest) { |
| 1239 | priorStopPtT = priorPtT = priorTest->ptT(); |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 1240 | while ((priorPtT = priorPtT->next()) != priorStopPtT) { |
caryclark | 182b499 | 2015-05-14 05:45:54 -0700 | [diff] [blame] | 1241 | if (priorPtT->deleted()) { |
| 1242 | continue; |
| 1243 | } |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 1244 | SkOpSegment* segment = priorPtT->span()->segment(); |
| 1245 | if (segment == opp) { |
caryclark | bca19f7 | 2015-05-13 08:23:48 -0700 | [diff] [blame] | 1246 | prior = priorTest; |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 1247 | priorOpp = opp; |
| 1248 | break; |
| 1249 | } |
| 1250 | } |
caryclark | bca19f7 | 2015-05-13 08:23:48 -0700 | [diff] [blame] | 1251 | priorTest = priorTest->prev(); |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 1252 | } |
| 1253 | if (!priorOpp) { |
| 1254 | continue; |
| 1255 | } |
caryclark | 26ad22a | 2015-10-16 09:03:38 -0700 | [diff] [blame] | 1256 | if (priorPtT == ptT) { |
| 1257 | continue; |
| 1258 | } |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 1259 | SkOpPtT* oppStart = prior->ptT(); |
caryclark | bca19f7 | 2015-05-13 08:23:48 -0700 | [diff] [blame] | 1260 | SkOpPtT* oppEnd = spanBase->ptT(); |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 1261 | bool swapped = priorPtT->fT > ptT->fT; |
| 1262 | if (swapped) { |
| 1263 | SkTSwap(priorPtT, ptT); |
| 1264 | SkTSwap(oppStart, oppEnd); |
| 1265 | } |
| 1266 | bool flipped = oppStart->fT > oppEnd->fT; |
caryclark | 26ad22a | 2015-10-16 09:03:38 -0700 | [diff] [blame] | 1267 | bool coincident = false; |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 1268 | if (coincidences->contains(priorPtT, ptT, oppStart, oppEnd, flipped)) { |
| 1269 | goto swapBack; |
| 1270 | } |
caryclark | 26ad22a | 2015-10-16 09:03:38 -0700 | [diff] [blame] | 1271 | if (opp->verb() == SkPath::kLine_Verb) { |
| 1272 | coincident = (SkDPoint::ApproximatelyEqual(priorPtT->fPt, oppStart->fPt) || |
| 1273 | SkDPoint::ApproximatelyEqual(priorPtT->fPt, oppEnd->fPt)) && |
| 1274 | (SkDPoint::ApproximatelyEqual(ptT->fPt, oppStart->fPt) || |
| 1275 | SkDPoint::ApproximatelyEqual(ptT->fPt, oppEnd->fPt)); |
| 1276 | } |
| 1277 | if (!coincident) { |
| 1278 | coincident = testForCoincidence(priorPtT, ptT, prior, spanBase, opp, 5000); |
| 1279 | } |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 1280 | if (coincident) { |
| 1281 | // mark coincidence |
caryclark | 182b499 | 2015-05-14 05:45:54 -0700 | [diff] [blame] | 1282 | if (!coincidences->extend(priorPtT, ptT, oppStart, oppEnd) |
| 1283 | && !coincidences->extend(oppStart, oppEnd, priorPtT, ptT)) { |
caryclark | bca19f7 | 2015-05-13 08:23:48 -0700 | [diff] [blame] | 1284 | coincidences->add(priorPtT, ptT, oppStart, oppEnd, allocator); |
| 1285 | } |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 1286 | clear_visited(&fHead); |
caryclark | 27c8eb8 | 2015-07-06 11:38:33 -0700 | [diff] [blame] | 1287 | return true; |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 1288 | } |
| 1289 | swapBack: |
| 1290 | if (swapped) { |
| 1291 | SkTSwap(priorPtT, ptT); |
| 1292 | } |
reed | 0dc4dd6 | 2015-03-24 13:55:33 -0700 | [diff] [blame] | 1293 | } |
halcanary | 96fcdcc | 2015-08-27 07:41:13 -0700 | [diff] [blame] | 1294 | } while ((spanBase = spanBase->final() ? nullptr : spanBase->upCast()->next())); |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 1295 | clear_visited(&fHead); |
caryclark | 27c8eb8 | 2015-07-06 11:38:33 -0700 | [diff] [blame] | 1296 | return false; |
reed | 0dc4dd6 | 2015-03-24 13:55:33 -0700 | [diff] [blame] | 1297 | } |
| 1298 | |
caryclark | 08bc848 | 2015-04-24 09:08:57 -0700 | [diff] [blame] | 1299 | // if a span has more than one intersection, merge the other segments' span as needed |
caryclark | d78c088 | 2016-02-24 09:03:07 -0800 | [diff] [blame] | 1300 | bool SkOpSegment::moveMultiples() { |
caryclark | 08bc848 | 2015-04-24 09:08:57 -0700 | [diff] [blame] | 1301 | debugValidate(); |
| 1302 | SkOpSpanBase* test = &fHead; |
| 1303 | do { |
| 1304 | int addCount = test->spanAddsCount(); |
caryclark | d78c088 | 2016-02-24 09:03:07 -0800 | [diff] [blame] | 1305 | if (addCount < 1) { |
| 1306 | return false; |
| 1307 | } |
caryclark | 08bc848 | 2015-04-24 09:08:57 -0700 | [diff] [blame] | 1308 | if (addCount == 1) { |
| 1309 | continue; |
| 1310 | } |
| 1311 | SkOpPtT* startPtT = test->ptT(); |
| 1312 | SkOpPtT* testPtT = startPtT; |
| 1313 | do { // iterate through all spans associated with start |
| 1314 | SkOpSpanBase* oppSpan = testPtT->span(); |
| 1315 | if (oppSpan->spanAddsCount() == addCount) { |
| 1316 | continue; |
| 1317 | } |
| 1318 | if (oppSpan->deleted()) { |
| 1319 | continue; |
| 1320 | } |
| 1321 | SkOpSegment* oppSegment = oppSpan->segment(); |
| 1322 | if (oppSegment == this) { |
| 1323 | continue; |
| 1324 | } |
| 1325 | // find range of spans to consider merging |
| 1326 | SkOpSpanBase* oppPrev = oppSpan; |
| 1327 | SkOpSpanBase* oppFirst = oppSpan; |
| 1328 | while ((oppPrev = oppPrev->prev())) { |
| 1329 | if (!roughly_equal(oppPrev->t(), oppSpan->t())) { |
| 1330 | break; |
| 1331 | } |
| 1332 | if (oppPrev->spanAddsCount() == addCount) { |
| 1333 | continue; |
| 1334 | } |
| 1335 | if (oppPrev->deleted()) { |
| 1336 | continue; |
| 1337 | } |
| 1338 | oppFirst = oppPrev; |
| 1339 | } |
| 1340 | SkOpSpanBase* oppNext = oppSpan; |
| 1341 | SkOpSpanBase* oppLast = oppSpan; |
halcanary | 96fcdcc | 2015-08-27 07:41:13 -0700 | [diff] [blame] | 1342 | while ((oppNext = oppNext->final() ? nullptr : oppNext->upCast()->next())) { |
caryclark | 08bc848 | 2015-04-24 09:08:57 -0700 | [diff] [blame] | 1343 | if (!roughly_equal(oppNext->t(), oppSpan->t())) { |
| 1344 | break; |
| 1345 | } |
| 1346 | if (oppNext->spanAddsCount() == addCount) { |
| 1347 | continue; |
| 1348 | } |
| 1349 | if (oppNext->deleted()) { |
| 1350 | continue; |
| 1351 | } |
| 1352 | oppLast = oppNext; |
| 1353 | } |
| 1354 | if (oppFirst == oppLast) { |
| 1355 | continue; |
| 1356 | } |
| 1357 | SkOpSpanBase* oppTest = oppFirst; |
| 1358 | do { |
| 1359 | if (oppTest == oppSpan) { |
| 1360 | continue; |
| 1361 | } |
| 1362 | // check to see if the candidate meets specific criteria: |
| 1363 | // it contains spans of segments in test's loop but not including 'this' |
| 1364 | SkOpPtT* oppStartPtT = oppTest->ptT(); |
| 1365 | SkOpPtT* oppPtT = oppStartPtT; |
| 1366 | while ((oppPtT = oppPtT->next()) != oppStartPtT) { |
| 1367 | SkOpSegment* oppPtTSegment = oppPtT->segment(); |
| 1368 | if (oppPtTSegment == this) { |
| 1369 | goto tryNextSpan; |
| 1370 | } |
| 1371 | SkOpPtT* matchPtT = startPtT; |
| 1372 | do { |
| 1373 | if (matchPtT->segment() == oppPtTSegment) { |
| 1374 | goto foundMatch; |
| 1375 | } |
| 1376 | } while ((matchPtT = matchPtT->next()) != startPtT); |
| 1377 | goto tryNextSpan; |
| 1378 | foundMatch: // merge oppTest and oppSpan |
| 1379 | oppSegment->debugValidate(); |
| 1380 | if (oppTest == &oppSegment->fTail || oppTest == &oppSegment->fHead) { |
| 1381 | SkASSERT(oppSpan != &oppSegment->fHead); // don't expect collapse |
| 1382 | SkASSERT(oppSpan != &oppSegment->fTail); |
| 1383 | oppTest->merge(oppSpan->upCast()); |
| 1384 | } else { |
| 1385 | oppSpan->merge(oppTest->upCast()); |
| 1386 | } |
| 1387 | oppSegment->debugValidate(); |
| 1388 | goto checkNextSpan; |
| 1389 | } |
| 1390 | tryNextSpan: |
| 1391 | ; |
| 1392 | } while (oppTest != oppLast && (oppTest = oppTest->upCast()->next())); |
| 1393 | } while ((testPtT = testPtT->next()) != startPtT); |
| 1394 | checkNextSpan: |
| 1395 | ; |
halcanary | 96fcdcc | 2015-08-27 07:41:13 -0700 | [diff] [blame] | 1396 | } while ((test = test->final() ? nullptr : test->upCast()->next())); |
caryclark | 08bc848 | 2015-04-24 09:08:57 -0700 | [diff] [blame] | 1397 | debugValidate(); |
caryclark | d78c088 | 2016-02-24 09:03:07 -0800 | [diff] [blame] | 1398 | return true; |
caryclark | 08bc848 | 2015-04-24 09:08:57 -0700 | [diff] [blame] | 1399 | } |
| 1400 | |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 1401 | // Move nearby t values and pts so they all hang off the same span. Alignment happens later. |
caryclark | 08bc848 | 2015-04-24 09:08:57 -0700 | [diff] [blame] | 1402 | void SkOpSegment::moveNearby() { |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 1403 | debugValidate(); |
| 1404 | SkOpSpanBase* spanS = &fHead; |
| 1405 | do { |
| 1406 | SkOpSpanBase* test = spanS->upCast()->next(); |
| 1407 | SkOpSpanBase* next; |
| 1408 | if (spanS->contains(test)) { |
| 1409 | if (!test->final()) { |
| 1410 | test->upCast()->detach(spanS->ptT()); |
| 1411 | continue; |
| 1412 | } else if (spanS != &fHead) { |
| 1413 | spanS->upCast()->detach(test->ptT()); |
| 1414 | spanS = test; |
| 1415 | continue; |
| 1416 | } |
reed | 0dc4dd6 | 2015-03-24 13:55:33 -0700 | [diff] [blame] | 1417 | } |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 1418 | do { // iterate through all spans associated with start |
| 1419 | SkOpPtT* startBase = spanS->ptT(); |
halcanary | 96fcdcc | 2015-08-27 07:41:13 -0700 | [diff] [blame] | 1420 | next = test->final() ? nullptr : test->upCast()->next(); |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 1421 | do { |
| 1422 | SkOpPtT* testBase = test->ptT(); |
| 1423 | do { |
| 1424 | if (startBase == testBase) { |
| 1425 | goto checkNextSpan; |
| 1426 | } |
| 1427 | if (testBase->duplicate()) { |
| 1428 | continue; |
| 1429 | } |
| 1430 | if (this->match(startBase, testBase->segment(), testBase->fT, testBase->fPt)) { |
| 1431 | if (test == &this->fTail) { |
| 1432 | if (spanS == &fHead) { |
| 1433 | debugValidate(); |
caryclark | 08bc848 | 2015-04-24 09:08:57 -0700 | [diff] [blame] | 1434 | return; // if this span has collapsed, remove it from parent |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 1435 | } |
| 1436 | this->fTail.merge(spanS->upCast()); |
| 1437 | debugValidate(); |
caryclark | 08bc848 | 2015-04-24 09:08:57 -0700 | [diff] [blame] | 1438 | return; |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 1439 | } |
| 1440 | spanS->merge(test->upCast()); |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 1441 | goto checkNextSpan; |
| 1442 | } |
| 1443 | } while ((testBase = testBase->next()) != test->ptT()); |
| 1444 | } while ((startBase = startBase->next()) != spanS->ptT()); |
| 1445 | checkNextSpan: |
| 1446 | ; |
| 1447 | } while ((test = next)); |
| 1448 | spanS = spanS->upCast()->next(); |
| 1449 | } while (!spanS->final()); |
| 1450 | debugValidate(); |
reed | 0dc4dd6 | 2015-03-24 13:55:33 -0700 | [diff] [blame] | 1451 | } |
| 1452 | |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 1453 | bool SkOpSegment::operand() const { |
| 1454 | return fContour->operand(); |
| 1455 | } |
| 1456 | |
| 1457 | bool SkOpSegment::oppXor() const { |
| 1458 | return fContour->oppXor(); |
| 1459 | } |
| 1460 | |
| 1461 | bool SkOpSegment::ptsDisjoint(double t1, const SkPoint& pt1, double t2, const SkPoint& pt2) const { |
| 1462 | if (fVerb == SkPath::kLine_Verb) { |
| 1463 | return false; |
| 1464 | } |
| 1465 | // quads (and cubics) can loop back to nearly a line so that an opposite curve |
| 1466 | // hits in two places with very different t values. |
| 1467 | // OPTIMIZATION: curves could be preflighted so that, for example, something like |
| 1468 | // 'controls contained by ends' could avoid this check for common curves |
| 1469 | // 'ends are extremes in x or y' is cheaper to compute and real-world common |
| 1470 | // on the other hand, the below check is relatively inexpensive |
| 1471 | double midT = (t1 + t2) / 2; |
| 1472 | SkPoint midPt = this->ptAtT(midT); |
| 1473 | double seDistSq = SkTMax(pt1.distanceToSqd(pt2) * 2, FLT_EPSILON * 2); |
| 1474 | return midPt.distanceToSqd(pt1) > seDistSq || midPt.distanceToSqd(pt2) > seDistSq; |
| 1475 | } |
| 1476 | |
| 1477 | void SkOpSegment::setUpWindings(SkOpSpanBase* start, SkOpSpanBase* end, int* sumMiWinding, |
| 1478 | int* maxWinding, int* sumWinding) { |
| 1479 | int deltaSum = SpanSign(start, end); |
| 1480 | *maxWinding = *sumMiWinding; |
| 1481 | *sumWinding = *sumMiWinding -= deltaSum; |
bungeman | 60e0fee | 2015-08-26 05:15:46 -0700 | [diff] [blame] | 1482 | SkASSERT(!DEBUG_LIMIT_WIND_SUM || SkTAbs(*sumWinding) <= DEBUG_LIMIT_WIND_SUM); |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 1483 | } |
| 1484 | |
| 1485 | void SkOpSegment::setUpWindings(SkOpSpanBase* start, SkOpSpanBase* end, int* sumMiWinding, |
| 1486 | int* sumSuWinding, int* maxWinding, int* sumWinding, int* oppMaxWinding, |
| 1487 | int* oppSumWinding) { |
| 1488 | int deltaSum = SpanSign(start, end); |
| 1489 | int oppDeltaSum = OppSign(start, end); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 1490 | if (operand()) { |
| 1491 | *maxWinding = *sumSuWinding; |
| 1492 | *sumWinding = *sumSuWinding -= deltaSum; |
| 1493 | *oppMaxWinding = *sumMiWinding; |
| 1494 | *oppSumWinding = *sumMiWinding -= oppDeltaSum; |
| 1495 | } else { |
| 1496 | *maxWinding = *sumMiWinding; |
| 1497 | *sumWinding = *sumMiWinding -= deltaSum; |
| 1498 | *oppMaxWinding = *sumSuWinding; |
| 1499 | *oppSumWinding = *sumSuWinding -= oppDeltaSum; |
| 1500 | } |
bungeman | 60e0fee | 2015-08-26 05:15:46 -0700 | [diff] [blame] | 1501 | SkASSERT(!DEBUG_LIMIT_WIND_SUM || SkTAbs(*sumWinding) <= DEBUG_LIMIT_WIND_SUM); |
| 1502 | SkASSERT(!DEBUG_LIMIT_WIND_SUM || SkTAbs(*oppSumWinding) <= DEBUG_LIMIT_WIND_SUM); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 1503 | } |
| 1504 | |
commit-bot@chromium.org | 4431e77 | 2014-04-14 17:08:59 +0000 | [diff] [blame] | 1505 | void SkOpSegment::sortAngles() { |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 1506 | SkOpSpanBase* span = &this->fHead; |
commit-bot@chromium.org | 4431e77 | 2014-04-14 17:08:59 +0000 | [diff] [blame] | 1507 | do { |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 1508 | SkOpAngle* fromAngle = span->fromAngle(); |
halcanary | 96fcdcc | 2015-08-27 07:41:13 -0700 | [diff] [blame] | 1509 | SkOpAngle* toAngle = span->final() ? nullptr : span->upCast()->toAngle(); |
caryclark | dac1d17 | 2014-06-17 05:15:38 -0700 | [diff] [blame] | 1510 | if (!fromAngle && !toAngle) { |
commit-bot@chromium.org | 4431e77 | 2014-04-14 17:08:59 +0000 | [diff] [blame] | 1511 | continue; |
| 1512 | } |
caryclark@google.com | 570863f | 2013-09-16 15:55:01 +0000 | [diff] [blame] | 1513 | #if DEBUG_ANGLE |
commit-bot@chromium.org | 4431e77 | 2014-04-14 17:08:59 +0000 | [diff] [blame] | 1514 | bool wroteAfterHeader = false; |
caryclark@google.com | 570863f | 2013-09-16 15:55:01 +0000 | [diff] [blame] | 1515 | #endif |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 1516 | SkOpAngle* baseAngle = fromAngle; |
| 1517 | if (fromAngle && toAngle) { |
commit-bot@chromium.org | 4431e77 | 2014-04-14 17:08:59 +0000 | [diff] [blame] | 1518 | #if DEBUG_ANGLE |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 1519 | SkDebugf("%s [%d] tStart=%1.9g [%d]\n", __FUNCTION__, debugID(), span->t(), |
| 1520 | span->debugID()); |
| 1521 | wroteAfterHeader = true; |
commit-bot@chromium.org | 4431e77 | 2014-04-14 17:08:59 +0000 | [diff] [blame] | 1522 | #endif |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 1523 | fromAngle->insert(toAngle); |
| 1524 | } else if (!fromAngle) { |
| 1525 | baseAngle = toAngle; |
reed | 0dc4dd6 | 2015-03-24 13:55:33 -0700 | [diff] [blame] | 1526 | } |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 1527 | SkOpPtT* ptT = span->ptT(), * stopPtT = ptT; |
reed | 0dc4dd6 | 2015-03-24 13:55:33 -0700 | [diff] [blame] | 1528 | do { |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 1529 | SkOpSpanBase* oSpan = ptT->span(); |
| 1530 | if (oSpan == span) { |
| 1531 | continue; |
| 1532 | } |
| 1533 | SkOpAngle* oAngle = oSpan->fromAngle(); |
caryclark | dac1d17 | 2014-06-17 05:15:38 -0700 | [diff] [blame] | 1534 | if (oAngle) { |
commit-bot@chromium.org | 4431e77 | 2014-04-14 17:08:59 +0000 | [diff] [blame] | 1535 | #if DEBUG_ANGLE |
| 1536 | if (!wroteAfterHeader) { |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 1537 | SkDebugf("%s [%d] tStart=%1.9g [%d]\n", __FUNCTION__, debugID(), |
| 1538 | span->t(), span->debugID()); |
commit-bot@chromium.org | 4431e77 | 2014-04-14 17:08:59 +0000 | [diff] [blame] | 1539 | wroteAfterHeader = true; |
| 1540 | } |
| 1541 | #endif |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 1542 | if (!oAngle->loopContains(baseAngle)) { |
commit-bot@chromium.org | 8cb1daa | 2014-04-25 12:59:11 +0000 | [diff] [blame] | 1543 | baseAngle->insert(oAngle); |
| 1544 | } |
commit-bot@chromium.org | 4431e77 | 2014-04-14 17:08:59 +0000 | [diff] [blame] | 1545 | } |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 1546 | if (!oSpan->final()) { |
| 1547 | oAngle = oSpan->upCast()->toAngle(); |
| 1548 | if (oAngle) { |
commit-bot@chromium.org | 4431e77 | 2014-04-14 17:08:59 +0000 | [diff] [blame] | 1549 | #if DEBUG_ANGLE |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 1550 | if (!wroteAfterHeader) { |
| 1551 | SkDebugf("%s [%d] tStart=%1.9g [%d]\n", __FUNCTION__, debugID(), |
| 1552 | span->t(), span->debugID()); |
| 1553 | wroteAfterHeader = true; |
| 1554 | } |
commit-bot@chromium.org | 4431e77 | 2014-04-14 17:08:59 +0000 | [diff] [blame] | 1555 | #endif |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 1556 | if (!oAngle->loopContains(baseAngle)) { |
| 1557 | baseAngle->insert(oAngle); |
| 1558 | } |
commit-bot@chromium.org | 8cb1daa | 2014-04-25 12:59:11 +0000 | [diff] [blame] | 1559 | } |
commit-bot@chromium.org | 4431e77 | 2014-04-14 17:08:59 +0000 | [diff] [blame] | 1560 | } |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 1561 | } while ((ptT = ptT->next()) != stopPtT); |
| 1562 | if (baseAngle->loopCount() == 1) { |
halcanary | 96fcdcc | 2015-08-27 07:41:13 -0700 | [diff] [blame] | 1563 | span->setFromAngle(nullptr); |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 1564 | if (toAngle) { |
halcanary | 96fcdcc | 2015-08-27 07:41:13 -0700 | [diff] [blame] | 1565 | span->upCast()->setToAngle(nullptr); |
commit-bot@chromium.org | 4431e77 | 2014-04-14 17:08:59 +0000 | [diff] [blame] | 1566 | } |
halcanary | 96fcdcc | 2015-08-27 07:41:13 -0700 | [diff] [blame] | 1567 | baseAngle = nullptr; |
commit-bot@chromium.org | 4431e77 | 2014-04-14 17:08:59 +0000 | [diff] [blame] | 1568 | } |
| 1569 | #if DEBUG_SORT |
| 1570 | SkASSERT(!baseAngle || baseAngle->loopCount() > 1); |
| 1571 | #endif |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 1572 | } while (!span->final() && (span = span->upCast()->next())); |
caryclark@google.com | 570863f | 2013-09-16 15:55:01 +0000 | [diff] [blame] | 1573 | } |
| 1574 | |
caryclark@google.com | cffbcc3 | 2013-06-04 17:59:42 +0000 | [diff] [blame] | 1575 | // return true if midpoints were computed |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 1576 | bool SkOpSegment::subDivide(const SkOpSpanBase* start, const SkOpSpanBase* end, |
caryclark | 1049f12 | 2015-04-20 08:31:59 -0700 | [diff] [blame] | 1577 | SkOpCurve* edge) const { |
caryclark@google.com | cffbcc3 | 2013-06-04 17:59:42 +0000 | [diff] [blame] | 1578 | SkASSERT(start != end); |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 1579 | const SkOpPtT& startPtT = *start->ptT(); |
| 1580 | const SkOpPtT& endPtT = *end->ptT(); |
caryclark | 1049f12 | 2015-04-20 08:31:59 -0700 | [diff] [blame] | 1581 | SkDEBUGCODE(edge->fVerb = fVerb); |
| 1582 | edge->fPts[0] = startPtT.fPt; |
caryclark@google.com | cffbcc3 | 2013-06-04 17:59:42 +0000 | [diff] [blame] | 1583 | int points = SkPathOpsVerbToPoints(fVerb); |
caryclark | 1049f12 | 2015-04-20 08:31:59 -0700 | [diff] [blame] | 1584 | edge->fPts[points] = endPtT.fPt; |
| 1585 | edge->fWeight = 1; |
caryclark@google.com | cffbcc3 | 2013-06-04 17:59:42 +0000 | [diff] [blame] | 1586 | if (fVerb == SkPath::kLine_Verb) { |
| 1587 | return false; |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 1588 | } |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 1589 | double startT = startPtT.fT; |
| 1590 | double endT = endPtT.fT; |
caryclark@google.com | cffbcc3 | 2013-06-04 17:59:42 +0000 | [diff] [blame] | 1591 | if ((startT == 0 || endT == 0) && (startT == 1 || endT == 1)) { |
| 1592 | // don't compute midpoints if we already have them |
| 1593 | if (fVerb == SkPath::kQuad_Verb) { |
caryclark | 1049f12 | 2015-04-20 08:31:59 -0700 | [diff] [blame] | 1594 | edge->fPts[1] = fPts[1]; |
| 1595 | return false; |
| 1596 | } |
| 1597 | if (fVerb == SkPath::kConic_Verb) { |
| 1598 | edge->fPts[1] = fPts[1]; |
| 1599 | edge->fWeight = fWeight; |
caryclark@google.com | cffbcc3 | 2013-06-04 17:59:42 +0000 | [diff] [blame] | 1600 | return false; |
| 1601 | } |
| 1602 | SkASSERT(fVerb == SkPath::kCubic_Verb); |
| 1603 | if (start < end) { |
caryclark | 1049f12 | 2015-04-20 08:31:59 -0700 | [diff] [blame] | 1604 | edge->fPts[1] = fPts[1]; |
| 1605 | edge->fPts[2] = fPts[2]; |
caryclark@google.com | cffbcc3 | 2013-06-04 17:59:42 +0000 | [diff] [blame] | 1606 | return false; |
| 1607 | } |
caryclark | 1049f12 | 2015-04-20 08:31:59 -0700 | [diff] [blame] | 1608 | edge->fPts[1] = fPts[2]; |
| 1609 | edge->fPts[2] = fPts[1]; |
caryclark@google.com | cffbcc3 | 2013-06-04 17:59:42 +0000 | [diff] [blame] | 1610 | return false; |
| 1611 | } |
caryclark | 1049f12 | 2015-04-20 08:31:59 -0700 | [diff] [blame] | 1612 | const SkDPoint sub[2] = {{ edge->fPts[0].fX, edge->fPts[0].fY}, |
| 1613 | {edge->fPts[points].fX, edge->fPts[points].fY }}; |
caryclark@google.com | cffbcc3 | 2013-06-04 17:59:42 +0000 | [diff] [blame] | 1614 | if (fVerb == SkPath::kQuad_Verb) { |
caryclark | 1049f12 | 2015-04-20 08:31:59 -0700 | [diff] [blame] | 1615 | edge->fPts[1] = SkDQuad::SubDivide(fPts, sub[0], sub[1], startT, endT).asSkPoint(); |
| 1616 | } else if (fVerb == SkPath::kConic_Verb) { |
| 1617 | edge->fPts[1] = SkDConic::SubDivide(fPts, fWeight, sub[0], sub[1], |
| 1618 | startT, endT, &edge->fWeight).asSkPoint(); |
caryclark@google.com | cffbcc3 | 2013-06-04 17:59:42 +0000 | [diff] [blame] | 1619 | } else { |
| 1620 | SkASSERT(fVerb == SkPath::kCubic_Verb); |
| 1621 | SkDPoint ctrl[2]; |
| 1622 | SkDCubic::SubDivide(fPts, sub[0], sub[1], startT, endT, ctrl); |
caryclark | 1049f12 | 2015-04-20 08:31:59 -0700 | [diff] [blame] | 1623 | edge->fPts[1] = ctrl[0].asSkPoint(); |
| 1624 | edge->fPts[2] = ctrl[1].asSkPoint(); |
caryclark@google.com | cffbcc3 | 2013-06-04 17:59:42 +0000 | [diff] [blame] | 1625 | } |
| 1626 | return true; |
| 1627 | } |
| 1628 | |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 1629 | bool SkOpSegment::subDivide(const SkOpSpanBase* start, const SkOpSpanBase* end, |
caryclark | 1049f12 | 2015-04-20 08:31:59 -0700 | [diff] [blame] | 1630 | SkDCurve* edge) const { |
caryclark@google.com | cffbcc3 | 2013-06-04 17:59:42 +0000 | [diff] [blame] | 1631 | SkASSERT(start != end); |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 1632 | const SkOpPtT& startPtT = *start->ptT(); |
| 1633 | const SkOpPtT& endPtT = *end->ptT(); |
caryclark | 1049f12 | 2015-04-20 08:31:59 -0700 | [diff] [blame] | 1634 | SkDEBUGCODE(edge->fVerb = fVerb); |
| 1635 | edge->fCubic[0].set(startPtT.fPt); |
caryclark@google.com | cffbcc3 | 2013-06-04 17:59:42 +0000 | [diff] [blame] | 1636 | int points = SkPathOpsVerbToPoints(fVerb); |
caryclark | 1049f12 | 2015-04-20 08:31:59 -0700 | [diff] [blame] | 1637 | edge->fCubic[points].set(endPtT.fPt); |
caryclark@google.com | cffbcc3 | 2013-06-04 17:59:42 +0000 | [diff] [blame] | 1638 | if (fVerb == SkPath::kLine_Verb) { |
| 1639 | return false; |
| 1640 | } |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 1641 | double startT = startPtT.fT; |
| 1642 | double endT = endPtT.fT; |
caryclark@google.com | cffbcc3 | 2013-06-04 17:59:42 +0000 | [diff] [blame] | 1643 | if ((startT == 0 || endT == 0) && (startT == 1 || endT == 1)) { |
| 1644 | // don't compute midpoints if we already have them |
| 1645 | if (fVerb == SkPath::kQuad_Verb) { |
caryclark | 1049f12 | 2015-04-20 08:31:59 -0700 | [diff] [blame] | 1646 | edge->fLine[1].set(fPts[1]); |
| 1647 | return false; |
| 1648 | } |
| 1649 | if (fVerb == SkPath::kConic_Verb) { |
| 1650 | edge->fConic[1].set(fPts[1]); |
| 1651 | edge->fConic.fWeight = fWeight; |
caryclark@google.com | cffbcc3 | 2013-06-04 17:59:42 +0000 | [diff] [blame] | 1652 | return false; |
| 1653 | } |
| 1654 | SkASSERT(fVerb == SkPath::kCubic_Verb); |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 1655 | if (startT == 0) { |
caryclark | 1049f12 | 2015-04-20 08:31:59 -0700 | [diff] [blame] | 1656 | edge->fCubic[1].set(fPts[1]); |
| 1657 | edge->fCubic[2].set(fPts[2]); |
caryclark@google.com | cffbcc3 | 2013-06-04 17:59:42 +0000 | [diff] [blame] | 1658 | return false; |
| 1659 | } |
caryclark | 1049f12 | 2015-04-20 08:31:59 -0700 | [diff] [blame] | 1660 | edge->fCubic[1].set(fPts[2]); |
| 1661 | edge->fCubic[2].set(fPts[1]); |
caryclark@google.com | cffbcc3 | 2013-06-04 17:59:42 +0000 | [diff] [blame] | 1662 | return false; |
| 1663 | } |
| 1664 | if (fVerb == SkPath::kQuad_Verb) { |
caryclark | 1049f12 | 2015-04-20 08:31:59 -0700 | [diff] [blame] | 1665 | edge->fQuad[1] = SkDQuad::SubDivide(fPts, edge->fQuad[0], edge->fQuad[2], startT, endT); |
| 1666 | } else if (fVerb == SkPath::kConic_Verb) { |
| 1667 | edge->fConic[1] = SkDConic::SubDivide(fPts, fWeight, edge->fQuad[0], edge->fQuad[2], |
| 1668 | startT, endT, &edge->fConic.fWeight); |
caryclark@google.com | cffbcc3 | 2013-06-04 17:59:42 +0000 | [diff] [blame] | 1669 | } else { |
| 1670 | SkASSERT(fVerb == SkPath::kCubic_Verb); |
caryclark | 1049f12 | 2015-04-20 08:31:59 -0700 | [diff] [blame] | 1671 | SkDCubic::SubDivide(fPts, edge->fCubic[0], edge->fCubic[3], startT, endT, &edge->fCubic[1]); |
caryclark@google.com | cffbcc3 | 2013-06-04 17:59:42 +0000 | [diff] [blame] | 1672 | } |
| 1673 | return true; |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 1674 | } |
| 1675 | |
caryclark | 27c8eb8 | 2015-07-06 11:38:33 -0700 | [diff] [blame] | 1676 | bool SkOpSegment::testForCoincidence(const SkOpPtT* priorPtT, const SkOpPtT* ptT, |
| 1677 | const SkOpSpanBase* prior, const SkOpSpanBase* spanBase, const SkOpSegment* opp, |
| 1678 | SkScalar flatnessLimit) const { |
| 1679 | // average t, find mid pt |
| 1680 | double midT = (prior->t() + spanBase->t()) / 2; |
| 1681 | SkPoint midPt = this->ptAtT(midT); |
| 1682 | bool coincident = true; |
| 1683 | // if the mid pt is not near either end pt, project perpendicular through opp seg |
| 1684 | if (!SkDPoint::ApproximatelyEqual(priorPtT->fPt, midPt) |
| 1685 | && !SkDPoint::ApproximatelyEqual(ptT->fPt, midPt)) { |
| 1686 | coincident = false; |
| 1687 | SkIntersections i; |
| 1688 | SkVector dxdy = (*CurveSlopeAtT[fVerb])(this->pts(), this->weight(), midT); |
caryclark | b669300 | 2015-12-16 12:28:35 -0800 | [diff] [blame] | 1689 | SkDLine ray = {{{midPt.fX, midPt.fY}, |
| 1690 | {(double) midPt.fX + dxdy.fY, (double) midPt.fY - dxdy.fX}}}; |
caryclark | 27c8eb8 | 2015-07-06 11:38:33 -0700 | [diff] [blame] | 1691 | (*CurveIntersectRay[opp->verb()])(opp->pts(), opp->weight(), ray, &i); |
| 1692 | // measure distance and see if it's small enough to denote coincidence |
| 1693 | for (int index = 0; index < i.used(); ++index) { |
| 1694 | SkDPoint oppPt = i.pt(index); |
| 1695 | if (oppPt.approximatelyEqual(midPt)) { |
| 1696 | SkVector oppDxdy = (*CurveSlopeAtT[opp->verb()])(opp->pts(), |
| 1697 | opp->weight(), i[index][0]); |
| 1698 | oppDxdy.normalize(); |
| 1699 | dxdy.normalize(); |
| 1700 | SkScalar flatness = SkScalarAbs(dxdy.cross(oppDxdy) / FLT_EPSILON); |
| 1701 | coincident |= flatness < flatnessLimit; |
| 1702 | } |
| 1703 | } |
| 1704 | } |
| 1705 | return coincident; |
| 1706 | } |
| 1707 | |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 1708 | void SkOpSegment::undoneSpan(SkOpSpanBase** start, SkOpSpanBase** end) { |
| 1709 | SkOpSpan* span = this->head(); |
| 1710 | do { |
| 1711 | if (!span->done()) { |
reed | 0dc4dd6 | 2015-03-24 13:55:33 -0700 | [diff] [blame] | 1712 | break; |
| 1713 | } |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 1714 | } while ((span = span->next()->upCastable())); |
| 1715 | SkASSERT(span); |
| 1716 | *start = span; |
| 1717 | *end = span->next(); |
reed | 0dc4dd6 | 2015-03-24 13:55:33 -0700 | [diff] [blame] | 1718 | } |
| 1719 | |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 1720 | int SkOpSegment::updateOppWinding(const SkOpSpanBase* start, const SkOpSpanBase* end) const { |
| 1721 | const SkOpSpan* lesser = start->starter(end); |
| 1722 | int oppWinding = lesser->oppSum(); |
| 1723 | int oppSpanWinding = SkOpSegment::OppSign(start, end); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 1724 | if (oppSpanWinding && UseInnerWinding(oppWinding - oppSpanWinding, oppWinding) |
| 1725 | && oppWinding != SK_MaxS32) { |
| 1726 | oppWinding -= oppSpanWinding; |
| 1727 | } |
| 1728 | return oppWinding; |
| 1729 | } |
| 1730 | |
| 1731 | int SkOpSegment::updateOppWinding(const SkOpAngle* angle) const { |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 1732 | const SkOpSpanBase* startSpan = angle->start(); |
| 1733 | const SkOpSpanBase* endSpan = angle->end(); |
| 1734 | return updateOppWinding(endSpan, startSpan); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 1735 | } |
| 1736 | |
| 1737 | int SkOpSegment::updateOppWindingReverse(const SkOpAngle* angle) const { |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 1738 | const SkOpSpanBase* startSpan = angle->start(); |
| 1739 | const SkOpSpanBase* endSpan = angle->end(); |
| 1740 | return updateOppWinding(startSpan, endSpan); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 1741 | } |
| 1742 | |
caryclark | 624637c | 2015-05-11 07:21:27 -0700 | [diff] [blame] | 1743 | int SkOpSegment::updateWinding(SkOpSpanBase* start, SkOpSpanBase* end) { |
| 1744 | SkOpSpan* lesser = start->starter(end); |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 1745 | int winding = lesser->windSum(); |
commit-bot@chromium.org | 8cb1daa | 2014-04-25 12:59:11 +0000 | [diff] [blame] | 1746 | if (winding == SK_MinS32) { |
caryclark | bca19f7 | 2015-05-13 08:23:48 -0700 | [diff] [blame] | 1747 | winding = lesser->computeWindSum(); |
caryclark | 624637c | 2015-05-11 07:21:27 -0700 | [diff] [blame] | 1748 | } |
| 1749 | if (winding == SK_MinS32) { |
commit-bot@chromium.org | 8cb1daa | 2014-04-25 12:59:11 +0000 | [diff] [blame] | 1750 | return winding; |
| 1751 | } |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 1752 | int spanWinding = SkOpSegment::SpanSign(start, end); |
caryclark@google.com | 570863f | 2013-09-16 15:55:01 +0000 | [diff] [blame] | 1753 | if (winding && UseInnerWinding(winding - spanWinding, winding) |
| 1754 | && winding != SK_MaxS32) { |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 1755 | winding -= spanWinding; |
| 1756 | } |
| 1757 | return winding; |
| 1758 | } |
| 1759 | |
caryclark | 624637c | 2015-05-11 07:21:27 -0700 | [diff] [blame] | 1760 | int SkOpSegment::updateWinding(SkOpAngle* angle) { |
| 1761 | SkOpSpanBase* startSpan = angle->start(); |
| 1762 | SkOpSpanBase* endSpan = angle->end(); |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 1763 | return updateWinding(endSpan, startSpan); |
caryclark@google.com | 570863f | 2013-09-16 15:55:01 +0000 | [diff] [blame] | 1764 | } |
| 1765 | |
caryclark | 624637c | 2015-05-11 07:21:27 -0700 | [diff] [blame] | 1766 | int SkOpSegment::updateWindingReverse(const SkOpAngle* angle) { |
| 1767 | SkOpSpanBase* startSpan = angle->start(); |
| 1768 | SkOpSpanBase* endSpan = angle->end(); |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 1769 | return updateWinding(startSpan, endSpan); |
caryclark@google.com | 570863f | 2013-09-16 15:55:01 +0000 | [diff] [blame] | 1770 | } |
| 1771 | |
| 1772 | // OPTIMIZATION: does the following also work, and is it any faster? |
| 1773 | // return outerWinding * innerWinding > 0 |
| 1774 | // || ((outerWinding + innerWinding < 0) ^ ((outerWinding - innerWinding) < 0))) |
| 1775 | bool SkOpSegment::UseInnerWinding(int outerWinding, int innerWinding) { |
| 1776 | SkASSERT(outerWinding != SK_MaxS32); |
| 1777 | SkASSERT(innerWinding != SK_MaxS32); |
bungeman | 60e0fee | 2015-08-26 05:15:46 -0700 | [diff] [blame] | 1778 | int absOut = SkTAbs(outerWinding); |
| 1779 | int absIn = SkTAbs(innerWinding); |
caryclark@google.com | 570863f | 2013-09-16 15:55:01 +0000 | [diff] [blame] | 1780 | bool result = absOut == absIn ? outerWinding < 0 : absOut < absIn; |
| 1781 | return result; |
| 1782 | } |
| 1783 | |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 1784 | int SkOpSegment::windSum(const SkOpAngle* angle) const { |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 1785 | const SkOpSpan* minSpan = angle->start()->starter(angle->end()); |
| 1786 | return minSpan->windSum(); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 1787 | } |