caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 1 | /* |
| 2 | * Copyright 2014 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 | */ |
| 7 | #include "SkOpCoincidence.h" |
| 8 | #include "SkOpContour.h" |
| 9 | #include "SkOpSegment.h" |
| 10 | #include "SkPathWriter.h" |
| 11 | |
| 12 | bool SkOpPtT::alias() const { |
| 13 | return this->span()->ptT() != this; |
| 14 | } |
| 15 | |
caryclark | 30b9fdd | 2016-08-31 14:36:29 -0700 | [diff] [blame] | 16 | const SkOpPtT* SkOpPtT::active() const { |
| 17 | if (!fDeleted) { |
| 18 | return this; |
| 19 | } |
| 20 | const SkOpPtT* ptT = this; |
| 21 | const SkOpPtT* stopPtT = ptT; |
| 22 | while ((ptT = ptT->next()) != stopPtT) { |
| 23 | if (ptT->fSpan == fSpan && !ptT->fDeleted) { |
| 24 | return ptT; |
| 25 | } |
| 26 | } |
Cary Clark | 74b4290 | 2018-03-09 07:38:47 -0500 | [diff] [blame] | 27 | return nullptr; // should never return deleted; caller must abort |
caryclark | 30b9fdd | 2016-08-31 14:36:29 -0700 | [diff] [blame] | 28 | } |
| 29 | |
caryclark | 27c8eb8 | 2015-07-06 11:38:33 -0700 | [diff] [blame] | 30 | bool SkOpPtT::contains(const SkOpPtT* check) const { |
caryclark | e7bb5b2 | 2016-09-22 05:20:07 -0700 | [diff] [blame] | 31 | SkOPASSERT(this != check); |
caryclark | 27c8eb8 | 2015-07-06 11:38:33 -0700 | [diff] [blame] | 32 | const SkOpPtT* ptT = this; |
| 33 | const SkOpPtT* stopPtT = ptT; |
| 34 | while ((ptT = ptT->next()) != stopPtT) { |
| 35 | if (ptT == check) { |
| 36 | return true; |
| 37 | } |
| 38 | } |
| 39 | return false; |
| 40 | } |
| 41 | |
caryclark | 55888e4 | 2016-07-18 10:01:36 -0700 | [diff] [blame] | 42 | bool SkOpPtT::contains(const SkOpSegment* segment, const SkPoint& pt) const { |
| 43 | SkASSERT(this->segment() != segment); |
| 44 | const SkOpPtT* ptT = this; |
caryclark | 27c8eb8 | 2015-07-06 11:38:33 -0700 | [diff] [blame] | 45 | const SkOpPtT* stopPtT = ptT; |
| 46 | while ((ptT = ptT->next()) != stopPtT) { |
caryclark | 55888e4 | 2016-07-18 10:01:36 -0700 | [diff] [blame] | 47 | if (ptT->fPt == pt && ptT->segment() == segment) { |
| 48 | return true; |
| 49 | } |
| 50 | } |
| 51 | return false; |
| 52 | } |
| 53 | |
| 54 | bool SkOpPtT::contains(const SkOpSegment* segment, double t) const { |
| 55 | const SkOpPtT* ptT = this; |
| 56 | const SkOpPtT* stopPtT = ptT; |
| 57 | while ((ptT = ptT->next()) != stopPtT) { |
| 58 | if (ptT->fT == t && ptT->segment() == segment) { |
| 59 | return true; |
| 60 | } |
| 61 | } |
| 62 | return false; |
| 63 | } |
| 64 | |
| 65 | const SkOpPtT* SkOpPtT::contains(const SkOpSegment* check) const { |
| 66 | SkASSERT(this->segment() != check); |
| 67 | const SkOpPtT* ptT = this; |
| 68 | const SkOpPtT* stopPtT = ptT; |
| 69 | while ((ptT = ptT->next()) != stopPtT) { |
| 70 | if (ptT->segment() == check && !ptT->deleted()) { |
caryclark | 27c8eb8 | 2015-07-06 11:38:33 -0700 | [diff] [blame] | 71 | return ptT; |
| 72 | } |
| 73 | } |
halcanary | 96fcdcc | 2015-08-27 07:41:13 -0700 | [diff] [blame] | 74 | return nullptr; |
caryclark | 27c8eb8 | 2015-07-06 11:38:33 -0700 | [diff] [blame] | 75 | } |
| 76 | |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 77 | SkOpContour* SkOpPtT::contour() const { |
| 78 | return segment()->contour(); |
| 79 | } |
| 80 | |
caryclark | 55888e4 | 2016-07-18 10:01:36 -0700 | [diff] [blame] | 81 | const SkOpPtT* SkOpPtT::find(const SkOpSegment* segment) const { |
| 82 | const SkOpPtT* ptT = this; |
caryclark | 27c8eb8 | 2015-07-06 11:38:33 -0700 | [diff] [blame] | 83 | const SkOpPtT* stopPtT = ptT; |
| 84 | do { |
caryclark | 55888e4 | 2016-07-18 10:01:36 -0700 | [diff] [blame] | 85 | if (ptT->segment() == segment && !ptT->deleted()) { |
caryclark | 27c8eb8 | 2015-07-06 11:38:33 -0700 | [diff] [blame] | 86 | return ptT; |
| 87 | } |
| 88 | ptT = ptT->fNext; |
| 89 | } while (stopPtT != ptT); |
caryclark | 55888e4 | 2016-07-18 10:01:36 -0700 | [diff] [blame] | 90 | // SkASSERT(0); |
halcanary | 96fcdcc | 2015-08-27 07:41:13 -0700 | [diff] [blame] | 91 | return nullptr; |
caryclark | 27c8eb8 | 2015-07-06 11:38:33 -0700 | [diff] [blame] | 92 | } |
| 93 | |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 94 | SkOpGlobalState* SkOpPtT::globalState() const { |
caryclark | 55888e4 | 2016-07-18 10:01:36 -0700 | [diff] [blame] | 95 | return contour()->globalState(); |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 96 | } |
| 97 | |
| 98 | void SkOpPtT::init(SkOpSpanBase* span, double t, const SkPoint& pt, bool duplicate) { |
| 99 | fT = t; |
| 100 | fPt = pt; |
| 101 | fSpan = span; |
| 102 | fNext = this; |
| 103 | fDuplicatePt = duplicate; |
| 104 | fDeleted = false; |
caryclark | 55888e4 | 2016-07-18 10:01:36 -0700 | [diff] [blame] | 105 | fCoincident = false; |
caryclark | 1049f12 | 2015-04-20 08:31:59 -0700 | [diff] [blame] | 106 | SkDEBUGCODE(fID = span->globalState()->nextPtTID()); |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 107 | } |
| 108 | |
| 109 | bool SkOpPtT::onEnd() const { |
| 110 | const SkOpSpanBase* span = this->span(); |
| 111 | if (span->ptT() != this) { |
| 112 | return false; |
| 113 | } |
| 114 | const SkOpSegment* segment = this->segment(); |
| 115 | return span == segment->head() || span == segment->tail(); |
| 116 | } |
| 117 | |
caryclark | 55888e4 | 2016-07-18 10:01:36 -0700 | [diff] [blame] | 118 | bool SkOpPtT::ptAlreadySeen(const SkOpPtT* check) const { |
| 119 | while (this != check) { |
| 120 | if (this->fPt == check->fPt) { |
| 121 | return true; |
| 122 | } |
| 123 | check = check->fNext; |
| 124 | } |
| 125 | return false; |
| 126 | } |
| 127 | |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 128 | SkOpPtT* SkOpPtT::prev() { |
| 129 | SkOpPtT* result = this; |
| 130 | SkOpPtT* next = this; |
| 131 | while ((next = next->fNext) != this) { |
| 132 | result = next; |
| 133 | } |
| 134 | SkASSERT(result->fNext == this); |
| 135 | return result; |
| 136 | } |
| 137 | |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 138 | const SkOpSegment* SkOpPtT::segment() const { |
| 139 | return span()->segment(); |
| 140 | } |
| 141 | |
| 142 | SkOpSegment* SkOpPtT::segment() { |
| 143 | return span()->segment(); |
| 144 | } |
| 145 | |
caryclark | 55888e4 | 2016-07-18 10:01:36 -0700 | [diff] [blame] | 146 | void SkOpPtT::setDeleted() { |
| 147 | SkASSERT(this->span()->debugDeleted() || this->span()->ptT() != this); |
caryclark | 1597628 | 2016-07-21 05:48:43 -0700 | [diff] [blame] | 148 | SkOPASSERT(!fDeleted); |
caryclark | 55888e4 | 2016-07-18 10:01:36 -0700 | [diff] [blame] | 149 | fDeleted = true; |
| 150 | } |
| 151 | |
caryclark | 30b9fdd | 2016-08-31 14:36:29 -0700 | [diff] [blame] | 152 | void SkOpSpanBase::addOpp(SkOpSpanBase* opp) { |
caryclark | 29b2563 | 2016-08-25 11:27:17 -0700 | [diff] [blame] | 153 | SkOpPtT* oppPrev = this->ptT()->oppPrev(opp->ptT()); |
caryclark | 30b9fdd | 2016-08-31 14:36:29 -0700 | [diff] [blame] | 154 | if (!oppPrev) { |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 155 | return; |
| 156 | } |
caryclark | 30b9fdd | 2016-08-31 14:36:29 -0700 | [diff] [blame] | 157 | this->mergeMatches(opp); |
| 158 | this->ptT()->addOpp(opp->ptT(), oppPrev); |
| 159 | this->checkForCollapsedCoincidence(); |
caryclark | 55888e4 | 2016-07-18 10:01:36 -0700 | [diff] [blame] | 160 | } |
| 161 | |
Cary Clark | ba61029 | 2018-06-19 09:47:15 -0400 | [diff] [blame] | 162 | SkOpSpanBase::Collapsed SkOpSpanBase::collapsed(double s, double e) const { |
caryclark | 30b9fdd | 2016-08-31 14:36:29 -0700 | [diff] [blame] | 163 | const SkOpPtT* start = &fPtT; |
Cary Clark | ba61029 | 2018-06-19 09:47:15 -0400 | [diff] [blame] | 164 | const SkOpPtT* startNext = nullptr; |
caryclark | 30b9fdd | 2016-08-31 14:36:29 -0700 | [diff] [blame] | 165 | const SkOpPtT* walk = start; |
| 166 | double min = walk->fT; |
| 167 | double max = min; |
| 168 | const SkOpSegment* segment = this->segment(); |
Cary Clark | 4929a4a | 2018-10-17 14:12:41 -0400 | [diff] [blame^] | 169 | int safetyNet = 100000; |
caryclark | 30b9fdd | 2016-08-31 14:36:29 -0700 | [diff] [blame] | 170 | while ((walk = walk->next()) != start) { |
Cary Clark | 4929a4a | 2018-10-17 14:12:41 -0400 | [diff] [blame^] | 171 | if (!--safetyNet) { |
| 172 | return Collapsed::kError; |
| 173 | } |
Cary Clark | ba61029 | 2018-06-19 09:47:15 -0400 | [diff] [blame] | 174 | if (walk == startNext) { |
| 175 | return Collapsed::kError; |
| 176 | } |
caryclark | 30b9fdd | 2016-08-31 14:36:29 -0700 | [diff] [blame] | 177 | if (walk->segment() != segment) { |
| 178 | continue; |
| 179 | } |
| 180 | min = SkTMin(min, walk->fT); |
| 181 | max = SkTMax(max, walk->fT); |
| 182 | if (between(min, s, max) && between(min, e, max)) { |
Cary Clark | ba61029 | 2018-06-19 09:47:15 -0400 | [diff] [blame] | 183 | return Collapsed::kYes; |
caryclark | 30b9fdd | 2016-08-31 14:36:29 -0700 | [diff] [blame] | 184 | } |
Cary Clark | ba61029 | 2018-06-19 09:47:15 -0400 | [diff] [blame] | 185 | startNext = start->next(); |
caryclark | 30b9fdd | 2016-08-31 14:36:29 -0700 | [diff] [blame] | 186 | } |
Cary Clark | ba61029 | 2018-06-19 09:47:15 -0400 | [diff] [blame] | 187 | return Collapsed::kNo; |
caryclark | 30b9fdd | 2016-08-31 14:36:29 -0700 | [diff] [blame] | 188 | } |
| 189 | |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 190 | bool SkOpSpanBase::contains(const SkOpSpanBase* span) const { |
| 191 | const SkOpPtT* start = &fPtT; |
| 192 | const SkOpPtT* check = &span->fPtT; |
caryclark | ef4f32a | 2016-08-24 09:24:18 -0700 | [diff] [blame] | 193 | SkOPASSERT(start != check); |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 194 | const SkOpPtT* walk = start; |
| 195 | while ((walk = walk->next()) != start) { |
| 196 | if (walk == check) { |
| 197 | return true; |
| 198 | } |
| 199 | } |
| 200 | return false; |
| 201 | } |
| 202 | |
caryclark | 55888e4 | 2016-07-18 10:01:36 -0700 | [diff] [blame] | 203 | const SkOpPtT* SkOpSpanBase::contains(const SkOpSegment* segment) const { |
| 204 | const SkOpPtT* start = &fPtT; |
| 205 | const SkOpPtT* walk = start; |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 206 | while ((walk = walk->next()) != start) { |
caryclark | 55888e4 | 2016-07-18 10:01:36 -0700 | [diff] [blame] | 207 | if (walk->deleted()) { |
| 208 | continue; |
| 209 | } |
| 210 | if (walk->segment() == segment && walk->span()->ptT() == walk) { |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 211 | return walk; |
| 212 | } |
| 213 | } |
halcanary | 96fcdcc | 2015-08-27 07:41:13 -0700 | [diff] [blame] | 214 | return nullptr; |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 215 | } |
| 216 | |
| 217 | bool SkOpSpanBase::containsCoinEnd(const SkOpSegment* segment) const { |
| 218 | SkASSERT(this->segment() != segment); |
| 219 | const SkOpSpanBase* next = this; |
| 220 | while ((next = next->fCoinEnd) != this) { |
| 221 | if (next->segment() == segment) { |
| 222 | return true; |
| 223 | } |
| 224 | } |
| 225 | return false; |
| 226 | } |
| 227 | |
| 228 | SkOpContour* SkOpSpanBase::contour() const { |
| 229 | return segment()->contour(); |
| 230 | } |
| 231 | |
| 232 | SkOpGlobalState* SkOpSpanBase::globalState() const { |
caryclark | 55888e4 | 2016-07-18 10:01:36 -0700 | [diff] [blame] | 233 | return contour()->globalState(); |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 234 | } |
| 235 | |
| 236 | void SkOpSpanBase::initBase(SkOpSegment* segment, SkOpSpan* prev, double t, const SkPoint& pt) { |
| 237 | fSegment = segment; |
| 238 | fPtT.init(this, t, pt, false); |
| 239 | fCoinEnd = this; |
halcanary | 96fcdcc | 2015-08-27 07:41:13 -0700 | [diff] [blame] | 240 | fFromAngle = nullptr; |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 241 | fPrev = prev; |
caryclark | 08bc848 | 2015-04-24 09:08:57 -0700 | [diff] [blame] | 242 | fSpanAdds = 0; |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 243 | fAligned = true; |
| 244 | fChased = false; |
caryclark | 1049f12 | 2015-04-20 08:31:59 -0700 | [diff] [blame] | 245 | SkDEBUGCODE(fCount = 1); |
| 246 | SkDEBUGCODE(fID = globalState()->nextSpanID()); |
caryclark | 30b9fdd | 2016-08-31 14:36:29 -0700 | [diff] [blame] | 247 | SkDEBUGCODE(fDebugDeleted = false); |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 248 | } |
| 249 | |
| 250 | // this pair of spans share a common t value or point; merge them and eliminate duplicates |
| 251 | // this does not compute the best t or pt value; this merely moves all data into a single list |
| 252 | void SkOpSpanBase::merge(SkOpSpan* span) { |
| 253 | SkOpPtT* spanPtT = span->ptT(); |
| 254 | SkASSERT(this->t() != spanPtT->fT); |
| 255 | SkASSERT(!zero_or_one(spanPtT->fT)); |
mtklein | 18300a3 | 2016-03-16 13:53:35 -0700 | [diff] [blame] | 256 | span->release(this->ptT()); |
caryclark | 55888e4 | 2016-07-18 10:01:36 -0700 | [diff] [blame] | 257 | if (this->contains(span)) { |
caryclark | 30b9fdd | 2016-08-31 14:36:29 -0700 | [diff] [blame] | 258 | SkOPASSERT(0); // check to see if this ever happens -- should have been found earlier |
caryclark | 55888e4 | 2016-07-18 10:01:36 -0700 | [diff] [blame] | 259 | return; // merge is already in the ptT loop |
| 260 | } |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 261 | SkOpPtT* remainder = spanPtT->next(); |
caryclark | 55888e4 | 2016-07-18 10:01:36 -0700 | [diff] [blame] | 262 | this->ptT()->insert(spanPtT); |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 263 | while (remainder != spanPtT) { |
| 264 | SkOpPtT* next = remainder->next(); |
| 265 | SkOpPtT* compare = spanPtT->next(); |
| 266 | while (compare != spanPtT) { |
| 267 | SkOpPtT* nextC = compare->next(); |
| 268 | if (nextC->span() == remainder->span() && nextC->fT == remainder->fT) { |
| 269 | goto tryNextRemainder; |
| 270 | } |
| 271 | compare = nextC; |
| 272 | } |
| 273 | spanPtT->insert(remainder); |
| 274 | tryNextRemainder: |
| 275 | remainder = next; |
| 276 | } |
caryclark | 08bc848 | 2015-04-24 09:08:57 -0700 | [diff] [blame] | 277 | fSpanAdds += span->fSpanAdds; |
caryclark | 30b9fdd | 2016-08-31 14:36:29 -0700 | [diff] [blame] | 278 | } |
| 279 | |
caryclark | 55888e4 | 2016-07-18 10:01:36 -0700 | [diff] [blame] | 280 | // please keep in sync with debugCheckForCollapsedCoincidence() |
| 281 | void SkOpSpanBase::checkForCollapsedCoincidence() { |
| 282 | SkOpCoincidence* coins = this->globalState()->coincidence(); |
| 283 | if (coins->isEmpty()) { |
| 284 | return; |
| 285 | } |
| 286 | // the insert above may have put both ends of a coincident run in the same span |
| 287 | // for each coincident ptT in loop; see if its opposite in is also in the loop |
| 288 | // this implementation is the motivation for marking that a ptT is referenced by a coincident span |
| 289 | SkOpPtT* head = this->ptT(); |
| 290 | SkOpPtT* test = head; |
| 291 | do { |
| 292 | if (!test->coincident()) { |
| 293 | continue; |
| 294 | } |
| 295 | coins->markCollapsed(test); |
| 296 | } while ((test = test->next()) != head); |
caryclark | 30b9fdd | 2016-08-31 14:36:29 -0700 | [diff] [blame] | 297 | coins->releaseDeleted(); |
| 298 | } |
| 299 | |
| 300 | // please keep in sync with debugMergeMatches() |
| 301 | // Look to see if pt-t linked list contains same segment more than once |
| 302 | // if so, and if each pt-t is directly pointed to by spans in that segment, |
| 303 | // merge them |
| 304 | // keep the points, but remove spans so that the segment doesn't have 2 or more |
| 305 | // spans pointing to the same pt-t loop at different loop elements |
| 306 | void SkOpSpanBase::mergeMatches(SkOpSpanBase* opp) { |
| 307 | SkOpPtT* test = &fPtT; |
| 308 | SkOpPtT* testNext; |
| 309 | const SkOpPtT* stop = test; |
| 310 | do { |
| 311 | testNext = test->next(); |
| 312 | if (test->deleted()) { |
| 313 | continue; |
| 314 | } |
| 315 | SkOpSpanBase* testBase = test->span(); |
| 316 | SkASSERT(testBase->ptT() == test); |
| 317 | SkOpSegment* segment = test->segment(); |
| 318 | if (segment->done()) { |
| 319 | continue; |
| 320 | } |
| 321 | SkOpPtT* inner = opp->ptT(); |
| 322 | const SkOpPtT* innerStop = inner; |
| 323 | do { |
| 324 | if (inner->segment() != segment) { |
| 325 | continue; |
| 326 | } |
| 327 | if (inner->deleted()) { |
| 328 | continue; |
| 329 | } |
| 330 | SkOpSpanBase* innerBase = inner->span(); |
| 331 | SkASSERT(innerBase->ptT() == inner); |
Ben Wagner | 63fd760 | 2017-10-09 15:45:33 -0400 | [diff] [blame] | 332 | // when the intersection is first detected, the span base is marked if there are |
caryclark | 30b9fdd | 2016-08-31 14:36:29 -0700 | [diff] [blame] | 333 | // more than one point in the intersection. |
| 334 | if (!zero_or_one(inner->fT)) { |
| 335 | innerBase->upCast()->release(test); |
| 336 | } else { |
caryclark | b393a49 | 2016-09-07 08:21:09 -0700 | [diff] [blame] | 337 | SkOPASSERT(inner->fT != test->fT); |
caryclark | 30b9fdd | 2016-08-31 14:36:29 -0700 | [diff] [blame] | 338 | if (!zero_or_one(test->fT)) { |
| 339 | testBase->upCast()->release(inner); |
| 340 | } else { |
| 341 | segment->markAllDone(); // mark segment as collapsed |
| 342 | SkDEBUGCODE(testBase->debugSetDeleted()); |
| 343 | test->setDeleted(); |
| 344 | SkDEBUGCODE(innerBase->debugSetDeleted()); |
| 345 | inner->setDeleted(); |
| 346 | } |
| 347 | } |
| 348 | #ifdef SK_DEBUG // assert if another undeleted entry points to segment |
| 349 | const SkOpPtT* debugInner = inner; |
| 350 | while ((debugInner = debugInner->next()) != innerStop) { |
| 351 | if (debugInner->segment() != segment) { |
| 352 | continue; |
| 353 | } |
| 354 | if (debugInner->deleted()) { |
| 355 | continue; |
| 356 | } |
| 357 | SkOPASSERT(0); |
| 358 | } |
| 359 | #endif |
| 360 | break; |
| 361 | } while ((inner = inner->next()) != innerStop); |
| 362 | } while ((test = testNext) != stop); |
| 363 | this->checkForCollapsedCoincidence(); |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 364 | } |
| 365 | |
caryclark | bca19f7 | 2015-05-13 08:23:48 -0700 | [diff] [blame] | 366 | int SkOpSpan::computeWindSum() { |
| 367 | SkOpGlobalState* globals = this->globalState(); |
| 368 | SkOpContour* contourHead = globals->contourHead(); |
| 369 | int windTry = 0; |
| 370 | while (!this->sortableTop(contourHead) && ++windTry < SkOpGlobalState::kMaxWindingTries) { |
| 371 | ; |
| 372 | } |
| 373 | return this->windSum(); |
| 374 | } |
| 375 | |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 376 | bool SkOpSpan::containsCoincidence(const SkOpSegment* segment) const { |
| 377 | SkASSERT(this->segment() != segment); |
| 378 | const SkOpSpan* next = fCoincident; |
| 379 | do { |
| 380 | if (next->segment() == segment) { |
| 381 | return true; |
| 382 | } |
| 383 | } while ((next = next->fCoincident) != this); |
| 384 | return false; |
| 385 | } |
| 386 | |
caryclark | 55888e4 | 2016-07-18 10:01:36 -0700 | [diff] [blame] | 387 | void SkOpSpan::init(SkOpSegment* segment, SkOpSpan* prev, double t, const SkPoint& pt) { |
| 388 | SkASSERT(t != 1); |
| 389 | initBase(segment, prev, t, pt); |
| 390 | fCoincident = this; |
| 391 | fToAngle = nullptr; |
| 392 | fWindSum = fOppSum = SK_MinS32; |
| 393 | fWindValue = 1; |
| 394 | fOppValue = 0; |
| 395 | fTopTTry = 0; |
| 396 | fChased = fDone = false; |
| 397 | segment->bumpCount(); |
| 398 | fAlreadyAdded = false; |
| 399 | } |
| 400 | |
| 401 | // Please keep this in sync with debugInsertCoincidence() |
caryclark | 81a478c | 2016-09-09 09:37:57 -0700 | [diff] [blame] | 402 | bool SkOpSpan::insertCoincidence(const SkOpSegment* segment, bool flipped, bool ordered) { |
caryclark | 55888e4 | 2016-07-18 10:01:36 -0700 | [diff] [blame] | 403 | if (this->containsCoincidence(segment)) { |
| 404 | return true; |
| 405 | } |
| 406 | SkOpPtT* next = &fPtT; |
| 407 | while ((next = next->next()) != &fPtT) { |
| 408 | if (next->segment() == segment) { |
caryclark | 1493b97 | 2016-07-19 11:29:14 -0700 | [diff] [blame] | 409 | SkOpSpan* span; |
caryclark | 81a478c | 2016-09-09 09:37:57 -0700 | [diff] [blame] | 410 | SkOpSpanBase* base = next->span(); |
| 411 | if (!ordered) { |
caryclark | e6522ea | 2016-10-17 07:54:33 -0700 | [diff] [blame] | 412 | const SkOpPtT* spanEndPtT = fNext->contains(segment); |
| 413 | FAIL_IF(!spanEndPtT); |
| 414 | const SkOpSpanBase* spanEnd = spanEndPtT->span(); |
caryclark | 81a478c | 2016-09-09 09:37:57 -0700 | [diff] [blame] | 415 | const SkOpPtT* start = base->ptT()->starter(spanEnd->ptT()); |
caryclark | 45f04b8 | 2016-09-21 08:46:56 -0700 | [diff] [blame] | 416 | FAIL_IF(!start->span()->upCastable()); |
caryclark | 81a478c | 2016-09-09 09:37:57 -0700 | [diff] [blame] | 417 | span = const_cast<SkOpSpan*>(start->span()->upCast()); |
| 418 | } else if (flipped) { |
| 419 | span = base->prev(); |
| 420 | FAIL_IF(!span); |
caryclark | 1493b97 | 2016-07-19 11:29:14 -0700 | [diff] [blame] | 421 | } else { |
caryclark | 81a478c | 2016-09-09 09:37:57 -0700 | [diff] [blame] | 422 | FAIL_IF(!base->upCastable()); |
caryclark | 1493b97 | 2016-07-19 11:29:14 -0700 | [diff] [blame] | 423 | span = base->upCast(); |
caryclark | 55888e4 | 2016-07-18 10:01:36 -0700 | [diff] [blame] | 424 | } |
| 425 | this->insertCoincidence(span); |
| 426 | return true; |
| 427 | } |
| 428 | } |
| 429 | #if DEBUG_COINCIDENCE |
| 430 | SkASSERT(0); // FIXME? if we get here, the span is missing its opposite segment... |
| 431 | #endif |
| 432 | return true; |
| 433 | } |
| 434 | |
| 435 | void SkOpSpan::release(const SkOpPtT* kept) { |
caryclark | 30b9fdd | 2016-08-31 14:36:29 -0700 | [diff] [blame] | 436 | SkDEBUGCODE(fDebugDeleted = true); |
caryclark | b393a49 | 2016-09-07 08:21:09 -0700 | [diff] [blame] | 437 | SkOPASSERT(kept->span() != this); |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 438 | SkASSERT(!final()); |
| 439 | SkOpSpan* prev = this->prev(); |
| 440 | SkASSERT(prev); |
| 441 | SkOpSpanBase* next = this->next(); |
| 442 | SkASSERT(next); |
| 443 | prev->setNext(next); |
| 444 | next->setPrev(prev); |
mtklein | 18300a3 | 2016-03-16 13:53:35 -0700 | [diff] [blame] | 445 | this->segment()->release(this); |
caryclark | 218f21a | 2015-06-29 11:41:52 -0700 | [diff] [blame] | 446 | SkOpCoincidence* coincidence = this->globalState()->coincidence(); |
| 447 | if (coincidence) { |
| 448 | coincidence->fixUp(this->ptT(), kept); |
| 449 | } |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 450 | this->ptT()->setDeleted(); |
caryclark | 55888e4 | 2016-07-18 10:01:36 -0700 | [diff] [blame] | 451 | SkOpPtT* stopPtT = this->ptT(); |
| 452 | SkOpPtT* testPtT = stopPtT; |
| 453 | const SkOpSpanBase* keptSpan = kept->span(); |
| 454 | do { |
| 455 | if (this == testPtT->span()) { |
| 456 | testPtT->setSpan(keptSpan); |
| 457 | } |
| 458 | } while ((testPtT = testPtT->next()) != stopPtT); |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 459 | } |
| 460 | |
| 461 | void SkOpSpan::setOppSum(int oppSum) { |
| 462 | SkASSERT(!final()); |
| 463 | if (fOppSum != SK_MinS32 && fOppSum != oppSum) { |
| 464 | this->globalState()->setWindingFailed(); |
| 465 | return; |
| 466 | } |
bungeman | 60e0fee | 2015-08-26 05:15:46 -0700 | [diff] [blame] | 467 | SkASSERT(!DEBUG_LIMIT_WIND_SUM || SkTAbs(oppSum) <= DEBUG_LIMIT_WIND_SUM); |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 468 | fOppSum = oppSum; |
| 469 | } |
caryclark | 624637c | 2015-05-11 07:21:27 -0700 | [diff] [blame] | 470 | |
| 471 | void SkOpSpan::setWindSum(int windSum) { |
| 472 | SkASSERT(!final()); |
| 473 | if (fWindSum != SK_MinS32 && fWindSum != windSum) { |
| 474 | this->globalState()->setWindingFailed(); |
| 475 | return; |
| 476 | } |
bungeman | 60e0fee | 2015-08-26 05:15:46 -0700 | [diff] [blame] | 477 | SkASSERT(!DEBUG_LIMIT_WIND_SUM || SkTAbs(windSum) <= DEBUG_LIMIT_WIND_SUM); |
caryclark | 624637c | 2015-05-11 07:21:27 -0700 | [diff] [blame] | 478 | fWindSum = windSum; |
| 479 | } |