caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 1 | /* |
| 2 | * Copyright 2015 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 "SkOpSegment.h" |
| 9 | #include "SkPathOpsTSect.h" |
| 10 | |
caryclark | 55888e4 | 2016-07-18 10:01:36 -0700 | [diff] [blame] | 11 | #if DEBUG_COINCIDENCE |
| 12 | #define FAIL_IF(cond) SkASSERT(!(cond)) |
| 13 | #else |
| 14 | #define FAIL_IF(cond) do { if (cond) return false; } while (false) |
| 15 | #endif |
| 16 | |
| 17 | // returns true if coincident span's start and end are the same |
| 18 | bool SkCoincidentSpans::collapsed(const SkOpPtT* test) const { |
| 19 | return (fCoinPtTStart == test && fCoinPtTEnd->contains(test)) |
| 20 | || (fCoinPtTEnd == test && fCoinPtTStart->contains(test)) |
| 21 | || (fOppPtTStart == test && fOppPtTEnd->contains(test)) |
| 22 | || (fOppPtTEnd == test && fOppPtTStart->contains(test)); |
| 23 | } |
| 24 | |
| 25 | // sets the span's end to the ptT referenced by the previous-next |
| 26 | void SkCoincidentSpans::correctOneEnd( |
| 27 | const SkOpPtT* (SkCoincidentSpans::* getEnd)() const, |
| 28 | void (SkCoincidentSpans::*setEnd)(const SkOpPtT* ptT) ) { |
| 29 | const SkOpPtT* origPtT = (this->*getEnd)(); |
| 30 | const SkOpSpanBase* origSpan = origPtT->span(); |
| 31 | const SkOpSpan* prev = origSpan->prev(); |
| 32 | const SkOpPtT* testPtT = prev ? prev->next()->ptT() |
| 33 | : origSpan->upCast()->next()->prev()->ptT(); |
| 34 | if (origPtT != testPtT) { |
| 35 | (this->*setEnd)(testPtT); |
caryclark | bca19f7 | 2015-05-13 08:23:48 -0700 | [diff] [blame] | 36 | } |
caryclark | 55888e4 | 2016-07-18 10:01:36 -0700 | [diff] [blame] | 37 | } |
| 38 | |
| 39 | // FIXME: member pointers have fallen out of favor and can be replaced with |
| 40 | // an alternative approach. |
| 41 | // makes all span ends agree with the segment's spans that define them |
| 42 | void SkCoincidentSpans::correctEnds() { |
| 43 | this->correctOneEnd(&SkCoincidentSpans::coinPtTStart, &SkCoincidentSpans::setCoinPtTStart); |
| 44 | this->correctOneEnd(&SkCoincidentSpans::coinPtTEnd, &SkCoincidentSpans::setCoinPtTEnd); |
| 45 | this->correctOneEnd(&SkCoincidentSpans::oppPtTStart, &SkCoincidentSpans::setOppPtTStart); |
| 46 | this->correctOneEnd(&SkCoincidentSpans::oppPtTEnd, &SkCoincidentSpans::setOppPtTEnd); |
| 47 | } |
| 48 | |
| 49 | /* Please keep this in sync with debugExpand */ |
| 50 | // expand the range by checking adjacent spans for coincidence |
| 51 | bool SkCoincidentSpans::expand() { |
| 52 | bool expanded = false; |
| 53 | const SkOpSegment* segment = coinPtTStart()->segment(); |
| 54 | const SkOpSegment* oppSegment = oppPtTStart()->segment(); |
| 55 | do { |
| 56 | const SkOpSpan* start = coinPtTStart()->span()->upCast(); |
| 57 | const SkOpSpan* prev = start->prev(); |
| 58 | const SkOpPtT* oppPtT; |
| 59 | if (!prev || !(oppPtT = prev->contains(oppSegment))) { |
| 60 | break; |
| 61 | } |
| 62 | double midT = (prev->t() + start->t()) / 2; |
| 63 | if (!segment->isClose(midT, oppSegment)) { |
| 64 | break; |
| 65 | } |
| 66 | setStarts(prev->ptT(), oppPtT); |
| 67 | expanded = true; |
| 68 | } while (true); |
| 69 | do { |
| 70 | const SkOpSpanBase* end = coinPtTEnd()->span(); |
| 71 | SkOpSpanBase* next = end->final() ? nullptr : end->upCast()->next(); |
| 72 | const SkOpPtT* oppPtT; |
| 73 | if (!next || !(oppPtT = next->contains(oppSegment))) { |
| 74 | break; |
| 75 | } |
| 76 | double midT = (end->t() + next->t()) / 2; |
| 77 | if (!segment->isClose(midT, oppSegment)) { |
| 78 | break; |
| 79 | } |
| 80 | setEnds(next->ptT(), oppPtT); |
| 81 | expanded = true; |
| 82 | } while (true); |
| 83 | return expanded; |
| 84 | } |
| 85 | |
| 86 | // increase the range of this span |
| 87 | bool SkCoincidentSpans::extend(const SkOpPtT* coinPtTStart, const SkOpPtT* coinPtTEnd, |
| 88 | const SkOpPtT* oppPtTStart, const SkOpPtT* oppPtTEnd) { |
| 89 | bool result = false; |
| 90 | if (fCoinPtTStart->fT > coinPtTStart->fT || (this->flipped() |
| 91 | ? fOppPtTStart->fT < oppPtTStart->fT : fOppPtTStart->fT > oppPtTStart->fT)) { |
| 92 | this->setStarts(coinPtTStart, oppPtTStart); |
| 93 | result = true; |
| 94 | } |
| 95 | if (fCoinPtTEnd->fT < coinPtTEnd->fT || (this->flipped() |
| 96 | ? fOppPtTEnd->fT > oppPtTEnd->fT : fOppPtTEnd->fT < oppPtTEnd->fT)) { |
| 97 | this->setEnds(coinPtTEnd, oppPtTEnd); |
| 98 | result = true; |
| 99 | } |
| 100 | return result; |
| 101 | } |
| 102 | |
| 103 | // set the range of this span |
| 104 | void SkCoincidentSpans::set(SkCoincidentSpans* next, const SkOpPtT* coinPtTStart, |
| 105 | const SkOpPtT* coinPtTEnd, const SkOpPtT* oppPtTStart, const SkOpPtT* oppPtTEnd |
| 106 | SkDEBUGPARAMS(int id)) { |
| 107 | SkASSERT(SkOpCoincidence::Ordered(coinPtTStart, oppPtTStart)); |
| 108 | fNext = next; |
| 109 | this->setStarts(coinPtTStart, oppPtTStart); |
| 110 | this->setEnds(coinPtTEnd, oppPtTEnd); |
| 111 | SkDEBUGCODE(fID = id); |
| 112 | } |
| 113 | |
| 114 | // returns true if both points are inside this |
| 115 | bool SkCoincidentSpans::contains(const SkOpPtT* s, const SkOpPtT* e) const { |
| 116 | if (s->fT > e->fT) { |
| 117 | SkTSwap(s, e); |
| 118 | } |
| 119 | if (s->segment() == fCoinPtTStart->segment()) { |
| 120 | return fCoinPtTStart->fT <= s->fT && e->fT <= fCoinPtTEnd->fT; |
| 121 | } else { |
| 122 | SkASSERT(s->segment() == fOppPtTStart->segment()); |
| 123 | double oppTs = fOppPtTStart->fT; |
| 124 | double oppTe = fOppPtTEnd->fT; |
| 125 | if (oppTs > oppTe) { |
| 126 | SkTSwap(oppTs, oppTe); |
| 127 | } |
| 128 | return oppTs <= s->fT && e->fT <= oppTe; |
| 129 | } |
| 130 | } |
| 131 | |
| 132 | // returns the number of segment span's contained by this, or -1 if inconsistent |
| 133 | int SkCoincidentSpans::spanCount() const { |
| 134 | // most commonly, concidence are one span long; check for that first |
| 135 | const SkOpSpanBase* start = coinPtTStart()->span(); |
| 136 | const SkOpSpanBase* end = coinPtTEnd()->span(); |
| 137 | int coinIntervals = 0; |
| 138 | while (start != end) { |
| 139 | coinIntervals++; |
| 140 | start = start->upCast()->next(); |
| 141 | } |
| 142 | const SkOpSpanBase* oppStart = (flipped() ? oppPtTEnd() : oppPtTStart())->span(); |
| 143 | const SkOpSpanBase* oppEnd = (flipped() ? oppPtTStart() : oppPtTEnd())->span(); |
| 144 | int oppIntervals = 0; |
| 145 | while (oppStart != oppEnd) { |
| 146 | oppIntervals++; |
| 147 | oppStart = oppStart->upCast()->next(); |
| 148 | } |
| 149 | return coinIntervals == oppIntervals ? coinIntervals : -1; |
| 150 | } |
| 151 | |
| 152 | // returns true if the point is on a coincident edge, and if it is the start of that edge |
| 153 | bool SkOpCoincidence::edge(const SkOpPtT* test, bool* start) const { |
| 154 | SkCoincidentSpans* coinRec = fHead; |
| 155 | if (!coinRec) { |
| 156 | return false; |
| 157 | } |
| 158 | do { |
| 159 | if (coinRec->coinPtTStart() == test) { |
| 160 | *start = true; |
| 161 | return true; |
| 162 | } |
| 163 | if (coinRec->coinPtTEnd() == test) { |
| 164 | *start = false; |
| 165 | return true; |
| 166 | } |
| 167 | if (coinRec->oppPtTStart() == test) { |
| 168 | *start = !coinRec->flipped(); |
| 169 | return true; |
| 170 | } |
| 171 | if (coinRec->coinPtTEnd() == test) { |
| 172 | *start = coinRec->flipped(); |
| 173 | return true; |
| 174 | } |
| 175 | } while ((coinRec = coinRec->next())); |
caryclark | bca19f7 | 2015-05-13 08:23:48 -0700 | [diff] [blame] | 176 | return false; |
| 177 | } |
| 178 | |
caryclark | 55888e4 | 2016-07-18 10:01:36 -0700 | [diff] [blame] | 179 | // if there is an existing pair that overlaps the addition, extend it |
| 180 | bool SkOpCoincidence::extend(const SkOpPtT* coinPtTStart, const SkOpPtT* coinPtTEnd, |
| 181 | const SkOpPtT* oppPtTStart, const SkOpPtT* oppPtTEnd) { |
| 182 | SkCoincidentSpans* test = fHead; |
| 183 | if (!test) { |
| 184 | return false; |
| 185 | } |
| 186 | const SkOpSegment* coinSeg = coinPtTStart->segment(); |
| 187 | const SkOpSegment* oppSeg = oppPtTStart->segment(); |
| 188 | if (!Ordered(coinPtTStart, oppPtTStart)) { |
| 189 | SkTSwap(coinSeg, oppSeg); |
| 190 | SkTSwap(coinPtTStart, oppPtTStart); |
| 191 | SkTSwap(coinPtTEnd, oppPtTEnd); |
| 192 | if (coinPtTStart->fT > coinPtTEnd->fT) { |
| 193 | SkTSwap(coinPtTStart, coinPtTEnd); |
| 194 | SkTSwap(oppPtTStart, oppPtTEnd); |
| 195 | } |
| 196 | } |
| 197 | double oppMinT = SkTMin(oppPtTStart->fT, oppPtTEnd->fT); |
| 198 | SkDEBUGCODE(double oppMaxT = SkTMax(oppPtTStart->fT, oppPtTEnd->fT)); |
| 199 | do { |
| 200 | if (coinSeg != test->coinPtTStart()->segment()) { |
| 201 | continue; |
| 202 | } |
| 203 | if (oppSeg != test->oppPtTStart()->segment()) { |
| 204 | continue; |
| 205 | } |
| 206 | double oTestMinT = SkTMin(test->oppPtTStart()->fT, test->oppPtTEnd()->fT); |
| 207 | double oTestMaxT = SkTMax(test->oppPtTStart()->fT, test->oppPtTEnd()->fT); |
| 208 | // if debug check triggers, caller failed to check if extended already exists |
| 209 | SkASSERT(test->coinPtTStart()->fT > coinPtTStart->fT |
| 210 | || coinPtTEnd->fT > test->coinPtTEnd()->fT |
| 211 | || oTestMinT > oppMinT || oppMaxT > oTestMaxT); |
| 212 | if ((test->coinPtTStart()->fT <= coinPtTEnd->fT |
| 213 | && coinPtTStart->fT <= test->coinPtTEnd()->fT) |
| 214 | || (oTestMinT <= oTestMaxT && oppMinT <= oTestMaxT)) { |
| 215 | test->extend(coinPtTStart, coinPtTEnd, oppPtTStart, oppPtTEnd); |
| 216 | return true; |
| 217 | } |
| 218 | } while ((test = test->next())); |
| 219 | return false; |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 220 | } |
| 221 | |
caryclark | 55888e4 | 2016-07-18 10:01:36 -0700 | [diff] [blame] | 222 | // verifies that the coincidence hasn't already been added |
| 223 | static void DebugCheckAdd(const SkCoincidentSpans* check, const SkOpPtT* coinPtTStart, |
| 224 | const SkOpPtT* coinPtTEnd, const SkOpPtT* oppPtTStart, const SkOpPtT* oppPtTEnd) { |
| 225 | #if DEBUG_COINCIDENCE |
| 226 | while (check) { |
| 227 | SkASSERT(check->coinPtTStart() != coinPtTStart || check->coinPtTEnd() != coinPtTEnd |
| 228 | || check->oppPtTStart() != oppPtTStart || check->oppPtTEnd() != oppPtTEnd); |
| 229 | SkASSERT(check->coinPtTStart() != oppPtTStart || check->coinPtTEnd() != oppPtTEnd |
| 230 | || check->oppPtTStart() != coinPtTStart || check->oppPtTEnd() != coinPtTEnd); |
| 231 | check = check->next(); |
| 232 | } |
| 233 | #endif |
| 234 | } |
| 235 | |
| 236 | // adds a new coincident pair |
| 237 | void SkOpCoincidence::add(SkOpPtT* coinPtTStart, SkOpPtT* coinPtTEnd, SkOpPtT* oppPtTStart, |
| 238 | SkOpPtT* oppPtTEnd) { |
| 239 | // OPTIMIZE: caller should have already sorted |
| 240 | if (!Ordered(coinPtTStart, oppPtTStart)) { |
| 241 | if (oppPtTStart->fT < oppPtTEnd->fT) { |
| 242 | this->add(oppPtTStart, oppPtTEnd, coinPtTStart, coinPtTEnd); |
| 243 | } else { |
| 244 | this->add(oppPtTEnd, oppPtTStart, coinPtTEnd, coinPtTStart); |
| 245 | } |
| 246 | return; |
| 247 | } |
| 248 | SkASSERT(Ordered(coinPtTStart, oppPtTStart)); |
| 249 | // choose the ptT at the front of the list to track |
| 250 | coinPtTStart = coinPtTStart->span()->ptT(); |
| 251 | coinPtTEnd = coinPtTEnd->span()->ptT(); |
| 252 | oppPtTStart = oppPtTStart->span()->ptT(); |
| 253 | oppPtTEnd = oppPtTEnd->span()->ptT(); |
| 254 | SkASSERT(coinPtTStart->fT < coinPtTEnd->fT); |
| 255 | SkASSERT(oppPtTStart->fT != oppPtTEnd->fT); |
| 256 | SkASSERT(!coinPtTStart->deleted()); |
| 257 | SkASSERT(!coinPtTEnd->deleted()); |
| 258 | SkASSERT(!oppPtTStart->deleted()); |
| 259 | SkASSERT(!oppPtTEnd->deleted()); |
| 260 | DebugCheckAdd(fHead, coinPtTStart, coinPtTEnd, oppPtTStart, oppPtTEnd); |
| 261 | DebugCheckAdd(fTop, coinPtTStart, coinPtTEnd, oppPtTStart, oppPtTEnd); |
| 262 | SkCoincidentSpans* coinRec = SkOpTAllocator<SkCoincidentSpans>::Allocate( |
| 263 | this->globalState()->allocator()); |
| 264 | coinRec->init(); |
| 265 | coinRec->set(this->fHead, coinPtTStart, coinPtTEnd, oppPtTStart, oppPtTEnd |
| 266 | SkDEBUGPARAMS(fGlobalState->nextCoinID())); |
| 267 | fHead = coinRec; |
| 268 | } |
| 269 | |
| 270 | // description below |
caryclark | 1597628 | 2016-07-21 05:48:43 -0700 | [diff] [blame] | 271 | bool SkOpCoincidence::addEndMovedSpans(const SkOpSpan* base, const SkOpSpanBase* testSpan) { |
caryclark | 55888e4 | 2016-07-18 10:01:36 -0700 | [diff] [blame] | 272 | const SkOpPtT* testPtT = testSpan->ptT(); |
| 273 | const SkOpPtT* stopPtT = testPtT; |
| 274 | const SkOpSegment* baseSeg = base->segment(); |
| 275 | while ((testPtT = testPtT->next()) != stopPtT) { |
| 276 | const SkOpSegment* testSeg = testPtT->segment(); |
| 277 | if (testPtT->deleted()) { |
| 278 | continue; |
| 279 | } |
| 280 | if (testSeg == baseSeg) { |
| 281 | continue; |
| 282 | } |
| 283 | if (this->contains(baseSeg, testSeg, testPtT->fT)) { |
| 284 | continue; |
| 285 | } |
| 286 | // intersect perp with base->ptT() with testPtT->segment() |
| 287 | SkDVector dxdy = baseSeg->dSlopeAtT(base->t()); |
| 288 | const SkPoint& pt = base->pt(); |
| 289 | SkDLine ray = {{{pt.fX, pt.fY}, {pt.fX + dxdy.fY, pt.fY - dxdy.fX}}}; |
| 290 | SkIntersections i; |
| 291 | (*CurveIntersectRay[testSeg->verb()])(testSeg->pts(), testSeg->weight(), ray, &i); |
| 292 | for (int index = 0; index < i.used(); ++index) { |
| 293 | double t = i[0][index]; |
| 294 | if (!between(0, t, 1)) { |
| 295 | continue; |
| 296 | } |
| 297 | SkDPoint oppPt = i.pt(index); |
| 298 | if (!oppPt.approximatelyEqual(pt)) { |
| 299 | continue; |
| 300 | } |
| 301 | SkOpSegment* writableSeg = const_cast<SkOpSegment*>(testSeg); |
| 302 | SkOpPtT* oppStart = writableSeg->addT(t, SkOpSegment::kAllowAliasMatch, nullptr); |
| 303 | SkOpSpan* writableBase = const_cast<SkOpSpan*>(base); |
| 304 | oppStart->span()->addOppAndMerge(writableBase); |
| 305 | if (oppStart->deleted()) { |
| 306 | continue; |
| 307 | } |
| 308 | SkOpSegment* coinSeg = base->segment(); |
| 309 | SkOpSegment* oppSeg = oppStart->segment(); |
| 310 | double coinTs, coinTe, oppTs, oppTe; |
| 311 | if (coinSeg < oppSeg) { |
| 312 | coinTs = base->t(); |
| 313 | coinTe = testSpan->t(); |
| 314 | oppTs = oppStart->fT; |
| 315 | oppTe = testPtT->fT; |
| 316 | } else { |
| 317 | SkTSwap(coinSeg, oppSeg); |
| 318 | coinTs = oppStart->fT; |
| 319 | coinTe = testPtT->fT; |
| 320 | oppTs = base->t(); |
| 321 | oppTe = testSpan->t(); |
| 322 | } |
| 323 | if (coinTs > coinTe) { |
| 324 | SkTSwap(coinTs, coinTe); |
| 325 | SkTSwap(oppTs, oppTe); |
| 326 | } |
caryclark | 1597628 | 2016-07-21 05:48:43 -0700 | [diff] [blame] | 327 | if (!this->addOrOverlap(coinSeg, oppSeg, coinTs, coinTe, oppTs, oppTe)) { |
| 328 | return false; |
| 329 | } |
caryclark | 55888e4 | 2016-07-18 10:01:36 -0700 | [diff] [blame] | 330 | } |
| 331 | } |
caryclark | 1597628 | 2016-07-21 05:48:43 -0700 | [diff] [blame] | 332 | return true; |
caryclark | 55888e4 | 2016-07-18 10:01:36 -0700 | [diff] [blame] | 333 | } |
| 334 | |
| 335 | // description below |
| 336 | bool SkOpCoincidence::addEndMovedSpans(const SkOpPtT* ptT) { |
| 337 | const SkOpSpan* base = ptT->span()->upCast(); |
| 338 | const SkOpSpan* prev = base->prev(); |
| 339 | if (!prev) { |
| 340 | return false; |
| 341 | } |
| 342 | if (!prev->isCanceled()) { |
caryclark | 1597628 | 2016-07-21 05:48:43 -0700 | [diff] [blame] | 343 | if (!this->addEndMovedSpans(base, base->prev())) { |
| 344 | return false; |
| 345 | } |
caryclark | 55888e4 | 2016-07-18 10:01:36 -0700 | [diff] [blame] | 346 | } |
| 347 | if (!base->isCanceled()) { |
caryclark | 1597628 | 2016-07-21 05:48:43 -0700 | [diff] [blame] | 348 | if (!this->addEndMovedSpans(base, base->next())) { |
| 349 | return false; |
| 350 | } |
caryclark | 55888e4 | 2016-07-18 10:01:36 -0700 | [diff] [blame] | 351 | } |
| 352 | return true; |
| 353 | } |
| 354 | |
| 355 | /* If A is coincident with B and B includes an endpoint, and A's matching point |
| 356 | is not the endpoint (i.e., there's an implied line connecting B-end and A) |
| 357 | then assume that the same implied line may intersect another curve close to B. |
| 358 | Since we only care about coincidence that was undetected, look at the |
| 359 | ptT list on B-segment adjacent to the B-end/A ptT loop (not in the loop, but |
| 360 | next door) and see if the A matching point is close enough to form another |
| 361 | coincident pair. If so, check for a new coincident span between B-end/A ptT loop |
| 362 | and the adjacent ptT loop. |
| 363 | */ |
| 364 | bool SkOpCoincidence::addEndMovedSpans() { |
| 365 | SkCoincidentSpans* span = fHead; |
| 366 | if (!span) { |
| 367 | return true; |
| 368 | } |
| 369 | fTop = span; |
| 370 | fHead = nullptr; |
| 371 | do { |
| 372 | if (span->coinPtTStart()->fPt != span->oppPtTStart()->fPt) { |
| 373 | if (1 == span->coinPtTStart()->fT) { |
| 374 | return false; |
| 375 | } |
| 376 | bool onEnd = span->coinPtTStart()->fT == 0; |
| 377 | bool oOnEnd = zero_or_one(span->oppPtTStart()->fT); |
| 378 | if (onEnd) { |
| 379 | if (!oOnEnd) { // if both are on end, any nearby intersect was already found |
| 380 | if (!this->addEndMovedSpans(span->oppPtTStart())) { |
| 381 | return false; |
| 382 | } |
| 383 | } |
| 384 | } else if (oOnEnd) { |
| 385 | if (!this->addEndMovedSpans(span->coinPtTStart())) { |
| 386 | return false; |
| 387 | } |
| 388 | } |
| 389 | } |
| 390 | if (span->coinPtTEnd()->fPt != span->oppPtTEnd()->fPt) { |
| 391 | bool onEnd = span->coinPtTEnd()->fT == 1; |
| 392 | bool oOnEnd = zero_or_one(span->oppPtTEnd()->fT); |
| 393 | if (onEnd) { |
| 394 | if (!oOnEnd) { |
| 395 | if (!this->addEndMovedSpans(span->oppPtTEnd())) { |
| 396 | return false; |
| 397 | } |
| 398 | } |
| 399 | } else if (oOnEnd) { |
| 400 | if (!this->addEndMovedSpans(span->coinPtTEnd())) { |
| 401 | return false; |
| 402 | } |
| 403 | } |
| 404 | } |
| 405 | } while ((span = span->next())); |
| 406 | this->restoreHead(); |
| 407 | return true; |
| 408 | } |
| 409 | |
| 410 | /* Please keep this in sync with debugAddExpanded */ |
| 411 | // for each coincident pair, match the spans |
| 412 | // if the spans don't match, add the missing pt to the segment and loop it in the opposite span |
| 413 | bool SkOpCoincidence::addExpanded() { |
| 414 | SkCoincidentSpans* coin = this->fHead; |
| 415 | if (!coin) { |
| 416 | return true; |
| 417 | } |
| 418 | do { |
| 419 | const SkOpPtT* startPtT = coin->coinPtTStart(); |
| 420 | const SkOpPtT* oStartPtT = coin->oppPtTStart(); |
| 421 | SkASSERT(startPtT->contains(oStartPtT)); |
| 422 | SkASSERT(coin->coinPtTEnd()->contains(coin->oppPtTEnd())); |
| 423 | const SkOpSpanBase* start = startPtT->span(); |
| 424 | const SkOpSpanBase* oStart = oStartPtT->span(); |
| 425 | const SkOpSpanBase* end = coin->coinPtTEnd()->span(); |
| 426 | const SkOpSpanBase* oEnd = coin->oppPtTEnd()->span(); |
| 427 | FAIL_IF(oEnd->deleted()); |
caryclark | e25a4f6 | 2016-07-26 09:26:29 -0700 | [diff] [blame^] | 428 | FAIL_IF(!start->upCastable()); |
caryclark | 55888e4 | 2016-07-18 10:01:36 -0700 | [diff] [blame] | 429 | const SkOpSpanBase* test = start->upCast()->next(); |
| 430 | const SkOpSpanBase* oTest = coin->flipped() ? oStart->prev() : oStart->upCast()->next(); |
| 431 | if (!oTest) { |
| 432 | return false; |
| 433 | } |
| 434 | while (test != end || oTest != oEnd) { |
| 435 | if (!test->ptT()->contains(oStart->segment()) |
| 436 | || !oTest->ptT()->contains(start->segment())) { |
| 437 | // use t ranges to guess which one is missing |
| 438 | double startRange = coin->coinPtTEnd()->fT - startPtT->fT; |
| 439 | FAIL_IF(!startRange); |
| 440 | double startPart = (test->t() - startPtT->fT) / startRange; |
| 441 | double oStartRange = coin->oppPtTEnd()->fT - oStartPtT->fT; |
| 442 | FAIL_IF(!oStartRange); |
| 443 | double oStartPart = (oTest->t() - oStartPtT->fT) / oStartRange; |
| 444 | FAIL_IF(startPart == oStartPart); |
| 445 | bool startOver = false; |
| 446 | bool success = startPart < oStartPart |
| 447 | ? oStart->segment()->addExpanded( |
| 448 | oStartPtT->fT + oStartRange * startPart, test, &startOver) |
| 449 | : start->segment()->addExpanded( |
| 450 | startPtT->fT + startRange * oStartPart, oTest, &startOver); |
| 451 | if (!success) { |
caryclark | e25a4f6 | 2016-07-26 09:26:29 -0700 | [diff] [blame^] | 452 | SkOPASSERT(false); |
caryclark | 55888e4 | 2016-07-18 10:01:36 -0700 | [diff] [blame] | 453 | return false; |
| 454 | } |
| 455 | if (startOver) { |
| 456 | test = start; |
| 457 | oTest = oStart; |
| 458 | } |
| 459 | } |
| 460 | if (test != end) { |
| 461 | test = test->upCast()->next(); |
| 462 | } |
| 463 | if (oTest != oEnd) { |
| 464 | oTest = coin->flipped() ? oTest->prev() : oTest->upCast()->next(); |
| 465 | if (!oTest) { |
| 466 | return false; |
| 467 | } |
| 468 | } |
| 469 | } |
| 470 | } while ((coin = coin->next())); |
| 471 | return true; |
| 472 | } |
| 473 | |
| 474 | // checks to see if coincidence has already been found |
| 475 | bool SkOpCoincidence::alreadyAdded(const SkCoincidentSpans* check, const SkCoincidentSpans* outer, |
| 476 | const SkOpPtT* over1s, const SkOpPtT* over1e) const { |
| 477 | do { |
| 478 | if (check->oppPtTStart() == outer->coinPtTStart() && check->coinPtTStart() == over1s |
| 479 | && check->oppPtTEnd() == outer->coinPtTEnd() && check->coinPtTEnd() == over1e) { |
| 480 | return true; |
| 481 | } |
| 482 | if (check->coinPtTStart() == outer->coinPtTStart() && check->oppPtTStart() == over1s |
| 483 | && check->coinPtTEnd() == outer->coinPtTEnd() && check->oppPtTEnd() == over1e) { |
| 484 | return true; |
| 485 | } |
| 486 | if (check->startEquals(outer->oppPtTStart()->span(), over1s->span())) { |
| 487 | SkDEBUGCODE(check->debugStartCheck(outer->oppPtTEnd()->span(), over1e->span(), |
| 488 | fGlobalState)); |
| 489 | return true; |
| 490 | } |
| 491 | if (check->startEquals(over1s->span(), outer->coinPtTStart()->span())) { |
| 492 | SkDEBUGCODE(check->debugStartCheck(over1e->span(), outer->oppPtTEnd()->span(), |
| 493 | fGlobalState)); |
| 494 | return true; |
| 495 | } |
| 496 | } while ((check = check->next())); |
| 497 | return false; |
| 498 | } |
| 499 | |
| 500 | /* Please keep this in sync with debugAddIfMissing() */ |
| 501 | bool SkOpCoincidence::addIfMissing(const SkCoincidentSpans* outer, SkOpPtT* over1s, |
| 502 | SkOpPtT* over1e) { |
| 503 | SkASSERT(fTop); |
| 504 | if (this->alreadyAdded(fTop, outer, over1s, over1e)) { |
| 505 | return false; |
| 506 | } |
| 507 | if (fHead && this->alreadyAdded(fHead, outer, over1s, over1e)) { |
| 508 | return false; |
| 509 | } |
| 510 | this->add(outer->coinPtTStart(), outer->coinPtTEnd(), over1s, over1e); |
| 511 | this->debugValidate(); |
| 512 | return true; |
| 513 | } |
| 514 | |
| 515 | // given a t span, map the same range on the coincident span |
| 516 | void SkOpCoincidence::TRange(const SkOpPtT* overS, const SkOpPtT* overE, double tStart, |
| 517 | double tEnd, const SkOpPtT* coinPtTStart, const SkOpPtT* coinPtTEnd, double* coinTs, |
| 518 | double* coinTe) { |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 519 | double denom = overE->fT - overS->fT; |
| 520 | double start = 0 < denom ? tStart : tEnd; |
| 521 | double end = 0 < denom ? tEnd : tStart; |
| 522 | double sRatio = (start - overS->fT) / denom; |
| 523 | double eRatio = (end - overS->fT) / denom; |
| 524 | *coinTs = coinPtTStart->fT + (coinPtTEnd->fT - coinPtTStart->fT) * sRatio; |
| 525 | *coinTe = coinPtTStart->fT + (coinPtTEnd->fT - coinPtTStart->fT) * eRatio; |
| 526 | } |
| 527 | |
caryclark | 55888e4 | 2016-07-18 10:01:36 -0700 | [diff] [blame] | 528 | // return true if span overlaps existing and needs to adjust the coincident list |
| 529 | bool SkOpCoincidence::checkOverlap(SkCoincidentSpans* check, |
| 530 | const SkOpSegment* coinSeg, const SkOpSegment* oppSeg, |
| 531 | double coinTs, double coinTe, double oppTs, double oppTe, |
| 532 | SkTDArray<SkCoincidentSpans*>* overlaps) const { |
| 533 | if (!Ordered(coinSeg, oppSeg)) { |
| 534 | if (oppTs < oppTe) { |
| 535 | return this->checkOverlap(check, oppSeg, coinSeg, oppTs, oppTe, coinTs, coinTe, |
| 536 | overlaps); |
| 537 | } |
| 538 | return this->checkOverlap(check, oppSeg, coinSeg, oppTe, oppTs, coinTe, coinTs, overlaps); |
| 539 | } |
| 540 | bool swapOpp = oppTs > oppTe; |
| 541 | if (swapOpp) { |
| 542 | SkTSwap(oppTs, oppTe); |
| 543 | } |
caryclark | 27c8eb8 | 2015-07-06 11:38:33 -0700 | [diff] [blame] | 544 | do { |
caryclark | 55888e4 | 2016-07-18 10:01:36 -0700 | [diff] [blame] | 545 | if (check->coinPtTStart()->segment() != coinSeg) { |
| 546 | continue; |
caryclark | 1c9ce61 | 2015-11-20 14:06:28 -0800 | [diff] [blame] | 547 | } |
caryclark | 55888e4 | 2016-07-18 10:01:36 -0700 | [diff] [blame] | 548 | if (check->oppPtTStart()->segment() != oppSeg) { |
| 549 | continue; |
caryclark | dae6b97 | 2016-06-08 04:28:19 -0700 | [diff] [blame] | 550 | } |
caryclark | 55888e4 | 2016-07-18 10:01:36 -0700 | [diff] [blame] | 551 | double checkTs = check->coinPtTStart()->fT; |
| 552 | double checkTe = check->coinPtTEnd()->fT; |
| 553 | bool coinOutside = coinTe < checkTs || coinTs > checkTe; |
| 554 | double oCheckTs = check->oppPtTStart()->fT; |
| 555 | double oCheckTe = check->oppPtTEnd()->fT; |
| 556 | if (swapOpp) { |
| 557 | if (oCheckTs <= oCheckTe) { |
| 558 | return false; |
caryclark | 27c8eb8 | 2015-07-06 11:38:33 -0700 | [diff] [blame] | 559 | } |
caryclark | 55888e4 | 2016-07-18 10:01:36 -0700 | [diff] [blame] | 560 | SkTSwap(oCheckTs, oCheckTe); |
caryclark | 27c8eb8 | 2015-07-06 11:38:33 -0700 | [diff] [blame] | 561 | } |
caryclark | 55888e4 | 2016-07-18 10:01:36 -0700 | [diff] [blame] | 562 | bool oppOutside = oppTe < oCheckTs || oppTs > oCheckTe; |
| 563 | if (coinOutside && oppOutside) { |
| 564 | continue; |
| 565 | } |
| 566 | bool coinInside = coinTe <= checkTe && coinTs >= checkTs; |
| 567 | bool oppInside = oppTe <= oCheckTe && oppTs >= oCheckTs; |
| 568 | if (coinInside && oppInside) { |
| 569 | return false; // complete overlap, already included, do nothing |
| 570 | } |
| 571 | *overlaps->append() = check; // partial overlap, extend existing entry |
| 572 | } while ((check = check->next())); |
caryclark | 26ad22a | 2015-10-16 09:03:38 -0700 | [diff] [blame] | 573 | return true; |
caryclark | 27c8eb8 | 2015-07-06 11:38:33 -0700 | [diff] [blame] | 574 | } |
| 575 | |
caryclark | 55888e4 | 2016-07-18 10:01:36 -0700 | [diff] [blame] | 576 | /* Please keep this in sync with debugAddIfMissing() */ |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 577 | bool SkOpCoincidence::addIfMissing(const SkOpPtT* over1s, const SkOpPtT* over1e, |
caryclark | 55888e4 | 2016-07-18 10:01:36 -0700 | [diff] [blame] | 578 | const SkOpPtT* over2s, const SkOpPtT* over2e, double tStart, double tEnd, |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 579 | SkOpPtT* coinPtTStart, const SkOpPtT* coinPtTEnd, |
caryclark | 55888e4 | 2016-07-18 10:01:36 -0700 | [diff] [blame] | 580 | SkOpPtT* oppPtTStart, const SkOpPtT* oppPtTEnd) { |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 581 | double coinTs, coinTe, oppTs, oppTe; |
caryclark | 55888e4 | 2016-07-18 10:01:36 -0700 | [diff] [blame] | 582 | TRange(over1s, over1e, tStart, tEnd, coinPtTStart, coinPtTEnd, &coinTs, &coinTe); |
| 583 | TRange(over2s, over2e, tStart, tEnd, oppPtTStart, oppPtTEnd, &oppTs, &oppTe); |
| 584 | bool swap = coinTs > coinTe; |
| 585 | if (swap) { |
| 586 | SkTSwap(coinTs, coinTe); |
| 587 | } |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 588 | if ((over1s->fT < over1e->fT) != (over2s->fT < over2e->fT)) { |
| 589 | SkTSwap(oppTs, oppTe); |
| 590 | } |
caryclark | 55888e4 | 2016-07-18 10:01:36 -0700 | [diff] [blame] | 591 | if (swap) { |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 592 | SkTSwap(oppTs, oppTe); |
| 593 | } |
caryclark | 55888e4 | 2016-07-18 10:01:36 -0700 | [diff] [blame] | 594 | SkOpSegment* coinSeg = coinPtTStart->segment(); |
| 595 | SkOpSegment* oppSeg = oppPtTStart->segment(); |
| 596 | if (coinSeg == oppSeg) { |
| 597 | return false; |
| 598 | } |
| 599 | return this->addOrOverlap(coinSeg, oppSeg, coinTs, coinTe, oppTs, oppTe); |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 600 | } |
| 601 | |
caryclark | 55888e4 | 2016-07-18 10:01:36 -0700 | [diff] [blame] | 602 | /* Please keep this in sync with debugAddOrOverlap() */ |
| 603 | bool SkOpCoincidence::addOrOverlap(SkOpSegment* coinSeg, SkOpSegment* oppSeg, |
| 604 | double coinTs, double coinTe, double oppTs, double oppTe) { |
| 605 | SkTDArray<SkCoincidentSpans*> overlaps; |
| 606 | SkASSERT(fTop); |
| 607 | if (!this->checkOverlap(fTop, coinSeg, oppSeg, coinTs, coinTe, oppTs, oppTe, &overlaps)) { |
| 608 | return false; |
| 609 | } |
| 610 | if (fHead && !this->checkOverlap(fHead, coinSeg, oppSeg, coinTs, |
| 611 | coinTe, oppTs, oppTe, &overlaps)) { |
| 612 | return false; |
| 613 | } |
| 614 | SkCoincidentSpans* overlap = overlaps.count() ? overlaps[0] : nullptr; |
| 615 | for (int index = 1; index < overlaps.count(); ++index) { // combine overlaps before continuing |
| 616 | SkCoincidentSpans* test = overlaps[index]; |
| 617 | if (overlap->coinPtTStart()->fT > test->coinPtTStart()->fT) { |
| 618 | overlap->setCoinPtTStart(test->coinPtTStart()); |
| 619 | } |
| 620 | if (overlap->coinPtTEnd()->fT < test->coinPtTEnd()->fT) { |
| 621 | overlap->setCoinPtTEnd(test->coinPtTEnd()); |
| 622 | } |
| 623 | if (overlap->flipped() |
| 624 | ? overlap->oppPtTStart()->fT < test->oppPtTStart()->fT |
| 625 | : overlap->oppPtTStart()->fT > test->oppPtTStart()->fT) { |
| 626 | overlap->setOppPtTStart(test->oppPtTStart()); |
| 627 | } |
| 628 | if (overlap->flipped() |
| 629 | ? overlap->oppPtTEnd()->fT > test->oppPtTEnd()->fT |
| 630 | : overlap->oppPtTEnd()->fT < test->oppPtTEnd()->fT) { |
| 631 | overlap->setOppPtTEnd(test->oppPtTEnd()); |
| 632 | } |
| 633 | if (!fHead || !this->release(fHead, test)) { |
| 634 | SkAssertResult(this->release(fTop, test)); |
| 635 | } |
| 636 | } |
| 637 | const SkOpPtT* cs = coinSeg->existing(coinTs, oppSeg); |
| 638 | const SkOpPtT* ce = coinSeg->existing(coinTe, oppSeg); |
| 639 | if (overlap && cs && ce && overlap->contains(cs, ce)) { |
| 640 | return false; |
| 641 | } |
caryclark | 1597628 | 2016-07-21 05:48:43 -0700 | [diff] [blame] | 642 | if (cs == ce && cs) { |
| 643 | return false; |
| 644 | } |
caryclark | 55888e4 | 2016-07-18 10:01:36 -0700 | [diff] [blame] | 645 | const SkOpPtT* os = oppSeg->existing(oppTs, coinSeg); |
| 646 | const SkOpPtT* oe = oppSeg->existing(oppTe, coinSeg); |
| 647 | if (overlap && os && oe && overlap->contains(os, oe)) { |
| 648 | return false; |
| 649 | } |
| 650 | SkASSERT(!cs || !cs->deleted()); |
| 651 | SkASSERT(!os || !os->deleted()); |
| 652 | SkASSERT(!ce || !ce->deleted()); |
| 653 | SkASSERT(!oe || !oe->deleted()); |
| 654 | const SkOpPtT* csExisting = !cs ? coinSeg->existing(coinTs, nullptr) : nullptr; |
| 655 | const SkOpPtT* ceExisting = !ce ? coinSeg->existing(coinTe, nullptr) : nullptr; |
| 656 | if (csExisting && csExisting == ceExisting) { |
| 657 | return false; |
| 658 | } |
| 659 | if (csExisting && (csExisting == ce || csExisting->contains(ceExisting ? ceExisting : ce))) { |
| 660 | return false; |
| 661 | } |
| 662 | if (ceExisting && (ceExisting == cs || ceExisting->contains(csExisting ? csExisting : cs))) { |
| 663 | return false; |
| 664 | } |
| 665 | const SkOpPtT* osExisting = !os ? oppSeg->existing(oppTs, nullptr) : nullptr; |
| 666 | const SkOpPtT* oeExisting = !oe ? oppSeg->existing(oppTe, nullptr) : nullptr; |
| 667 | if (osExisting && osExisting == oeExisting) { |
| 668 | return false; |
| 669 | } |
| 670 | if (osExisting && (osExisting == oe || osExisting->contains(oeExisting ? oeExisting : oe))) { |
| 671 | return false; |
| 672 | } |
| 673 | if (oeExisting && (oeExisting == os || oeExisting->contains(osExisting ? osExisting : os))) { |
| 674 | return false; |
| 675 | } |
| 676 | // extra line in debug code |
| 677 | this->debugValidate(); |
| 678 | if (!cs || !os) { |
| 679 | SkOpPtT* csWritable = cs ? const_cast<SkOpPtT*>(cs) |
| 680 | : coinSeg->addT(coinTs, SkOpSegment::kNoAliasMatch, nullptr); |
| 681 | SkOpPtT* osWritable = os ? const_cast<SkOpPtT*>(os) |
| 682 | : oppSeg->addT(oppTs, SkOpSegment::kNoAliasMatch, nullptr); |
| 683 | csWritable->span()->addOppAndMerge(osWritable->span()); |
| 684 | cs = csWritable; |
| 685 | os = osWritable; |
| 686 | if ((ce && ce->deleted()) || (oe && oe->deleted())) { |
| 687 | return false; |
| 688 | } |
| 689 | } |
| 690 | if (!ce || !oe) { |
| 691 | SkOpPtT* ceWritable = ce ? const_cast<SkOpPtT*>(ce) |
| 692 | : coinSeg->addT(coinTe, SkOpSegment::kNoAliasMatch, nullptr); |
| 693 | SkOpPtT* oeWritable = oe ? const_cast<SkOpPtT*>(oe) |
| 694 | : oppSeg->addT(oppTe, SkOpSegment::kNoAliasMatch, nullptr); |
| 695 | ceWritable->span()->addOppAndMerge(oeWritable->span()); |
| 696 | ce = ceWritable; |
| 697 | oe = oeWritable; |
| 698 | } |
| 699 | this->debugValidate(); |
| 700 | if (cs->deleted() || os->deleted() || ce->deleted() || oe->deleted()) { |
| 701 | return false; |
| 702 | } |
| 703 | if (cs->contains(ce) || os->contains(oe)) { |
| 704 | return false; |
| 705 | } |
| 706 | bool result = true; |
| 707 | if (overlap) { |
| 708 | if (overlap->coinPtTStart()->segment() == coinSeg) { |
| 709 | result = overlap->extend(cs, ce, os, oe); |
| 710 | } else { |
| 711 | if (os->fT > oe->fT) { |
| 712 | SkTSwap(cs, ce); |
| 713 | SkTSwap(os, oe); |
| 714 | } |
| 715 | result = overlap->extend(os, oe, cs, ce); |
| 716 | } |
| 717 | #if DEBUG_COINCIDENCE_VERBOSE |
| 718 | if (result) { |
| 719 | overlaps[0]->debugShow(); |
| 720 | } |
| 721 | #endif |
| 722 | } else { |
| 723 | this->add(cs, ce, os, oe); |
| 724 | #if DEBUG_COINCIDENCE_VERBOSE |
| 725 | fHead->debugShow(); |
| 726 | #endif |
| 727 | } |
| 728 | this->debugValidate(); |
| 729 | return result; |
| 730 | } |
| 731 | |
| 732 | // Please keep this in sync with debugAddMissing() |
caryclark | 27c8eb8 | 2015-07-06 11:38:33 -0700 | [diff] [blame] | 733 | /* detects overlaps of different coincident runs on same segment */ |
| 734 | /* does not detect overlaps for pairs without any segments in common */ |
caryclark | 55888e4 | 2016-07-18 10:01:36 -0700 | [diff] [blame] | 735 | // returns true if caller should loop again |
| 736 | bool SkOpCoincidence::addMissing() { |
caryclark | 27c8eb8 | 2015-07-06 11:38:33 -0700 | [diff] [blame] | 737 | SkCoincidentSpans* outer = fHead; |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 738 | if (!outer) { |
caryclark | 55888e4 | 2016-07-18 10:01:36 -0700 | [diff] [blame] | 739 | return false; |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 740 | } |
caryclark | 26ad22a | 2015-10-16 09:03:38 -0700 | [diff] [blame] | 741 | bool added = false; |
caryclark | 27c8eb8 | 2015-07-06 11:38:33 -0700 | [diff] [blame] | 742 | fTop = outer; |
halcanary | 96fcdcc | 2015-08-27 07:41:13 -0700 | [diff] [blame] | 743 | fHead = nullptr; |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 744 | do { |
caryclark | 27c8eb8 | 2015-07-06 11:38:33 -0700 | [diff] [blame] | 745 | // addifmissing can modify the list that this is walking |
caryclark | 26ad22a | 2015-10-16 09:03:38 -0700 | [diff] [blame] | 746 | // save head so that walker can iterate over old data unperturbed |
| 747 | // addifmissing adds to head freely then add saved head in the end |
caryclark | 55888e4 | 2016-07-18 10:01:36 -0700 | [diff] [blame] | 748 | const SkOpSegment* outerCoin = outer->coinPtTStart()->segment(); |
| 749 | const SkOpSegment* outerOpp = outer->oppPtTStart()->segment(); |
| 750 | if (outerCoin->done() || outerOpp->done()) { |
| 751 | continue; |
| 752 | } |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 753 | SkCoincidentSpans* inner = outer; |
caryclark | 55888e4 | 2016-07-18 10:01:36 -0700 | [diff] [blame] | 754 | while ((inner = inner->next())) { |
| 755 | this->debugValidate(); |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 756 | double overS, overE; |
caryclark | 55888e4 | 2016-07-18 10:01:36 -0700 | [diff] [blame] | 757 | const SkOpSegment* innerCoin = inner->coinPtTStart()->segment(); |
| 758 | const SkOpSegment* innerOpp = inner->oppPtTStart()->segment(); |
| 759 | if (innerCoin->done() || innerOpp->done()) { |
| 760 | continue; |
| 761 | } |
| 762 | if (outerCoin == innerCoin) { |
| 763 | if (outerOpp != innerOpp |
| 764 | && this->overlap(outer->coinPtTStart(), outer->coinPtTEnd(), |
| 765 | inner->coinPtTStart(), inner->coinPtTEnd(), &overS, &overE)) { |
| 766 | added |= this->addIfMissing(outer->coinPtTStart(), outer->coinPtTEnd(), |
| 767 | inner->coinPtTStart(), inner->coinPtTEnd(), overS, overE, |
| 768 | outer->oppPtTStart(), outer->oppPtTEnd(), |
| 769 | inner->oppPtTStart(), inner->oppPtTEnd()); |
| 770 | } |
| 771 | } else if (outerCoin == innerOpp) { |
| 772 | if (outerOpp != innerCoin |
| 773 | && this->overlap(outer->coinPtTStart(), outer->coinPtTEnd(), |
| 774 | inner->oppPtTStart(), inner->oppPtTEnd(), &overS, &overE)) { |
| 775 | added |= this->addIfMissing(outer->coinPtTStart(), outer->coinPtTEnd(), |
| 776 | inner->oppPtTStart(), inner->oppPtTEnd(), overS, overE, |
| 777 | outer->oppPtTStart(), outer->oppPtTEnd(), |
| 778 | inner->coinPtTStart(), inner->coinPtTEnd()); |
| 779 | } |
| 780 | } else if (outerOpp == innerCoin) { |
| 781 | SkASSERT(outerCoin != innerOpp); |
| 782 | if (this->overlap(outer->oppPtTStart(), outer->oppPtTEnd(), |
| 783 | inner->coinPtTStart(), inner->coinPtTEnd(), &overS, &overE)) { |
| 784 | added |= this->addIfMissing(outer->oppPtTStart(), outer->oppPtTEnd(), |
| 785 | inner->coinPtTStart(), inner->coinPtTEnd(), overS, overE, |
| 786 | outer->coinPtTStart(), outer->coinPtTEnd(), |
| 787 | inner->oppPtTStart(), inner->oppPtTEnd()); |
| 788 | } |
| 789 | } else if (outerOpp == innerOpp) { |
| 790 | SkASSERT(outerCoin != innerCoin); |
| 791 | if (this->overlap(outer->oppPtTStart(), outer->oppPtTEnd(), |
| 792 | inner->oppPtTStart(), inner->oppPtTEnd(), &overS, &overE)) { |
| 793 | added |= this->addIfMissing(outer->oppPtTStart(), outer->oppPtTEnd(), |
| 794 | inner->oppPtTStart(), inner->oppPtTEnd(), overS, overE, |
| 795 | outer->coinPtTStart(), outer->coinPtTEnd(), |
| 796 | inner->coinPtTStart(), inner->coinPtTEnd()); |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 797 | } |
| 798 | } |
caryclark | 55888e4 | 2016-07-18 10:01:36 -0700 | [diff] [blame] | 799 | this->debugValidate(); |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 800 | } |
caryclark | 55888e4 | 2016-07-18 10:01:36 -0700 | [diff] [blame] | 801 | } while ((outer = outer->next())); |
| 802 | this->restoreHead(); |
caryclark | 26ad22a | 2015-10-16 09:03:38 -0700 | [diff] [blame] | 803 | return added; |
caryclark | 27c8eb8 | 2015-07-06 11:38:33 -0700 | [diff] [blame] | 804 | } |
| 805 | |
caryclark | 55888e4 | 2016-07-18 10:01:36 -0700 | [diff] [blame] | 806 | bool SkOpCoincidence::addOverlap(const SkOpSegment* seg1, const SkOpSegment* seg1o, |
| 807 | const SkOpSegment* seg2, const SkOpSegment* seg2o, |
| 808 | const SkOpPtT* overS, const SkOpPtT* overE) { |
| 809 | const SkOpPtT* s1, * e1, * s2, * e2; |
| 810 | if (!(s1 = overS->find(seg1))) { |
| 811 | return true; |
| 812 | } |
| 813 | if (!(e1 = overE->find(seg1))) { |
| 814 | return true; |
| 815 | } |
| 816 | if (s1 == e1) { |
| 817 | return true; |
| 818 | } |
caryclark | 3f0753d | 2016-06-28 09:23:57 -0700 | [diff] [blame] | 819 | if (approximately_equal_half(s1->fT, e1->fT)) { |
| 820 | return false; |
| 821 | } |
caryclark | 27c8eb8 | 2015-07-06 11:38:33 -0700 | [diff] [blame] | 822 | if (!s1->starter(e1)->span()->upCast()->windValue()) { |
caryclark | 55888e4 | 2016-07-18 10:01:36 -0700 | [diff] [blame] | 823 | if (!(s1 = overS->find(seg1o))) { |
| 824 | return true; |
| 825 | } |
| 826 | if (!(e1 = overE->find(seg1o))) { |
| 827 | return true; |
| 828 | } |
| 829 | if (s1 == e1) { |
| 830 | return true; |
| 831 | } |
caryclark | 27c8eb8 | 2015-07-06 11:38:33 -0700 | [diff] [blame] | 832 | if (!s1->starter(e1)->span()->upCast()->windValue()) { |
caryclark | 3f0753d | 2016-06-28 09:23:57 -0700 | [diff] [blame] | 833 | return true; |
caryclark | 27c8eb8 | 2015-07-06 11:38:33 -0700 | [diff] [blame] | 834 | } |
| 835 | } |
caryclark | 55888e4 | 2016-07-18 10:01:36 -0700 | [diff] [blame] | 836 | if (!(s2 = overS->find(seg2))) { |
| 837 | return true; |
| 838 | } |
| 839 | if (!(e2 = overE->find(seg2))) { |
| 840 | return true; |
| 841 | } |
| 842 | if (s2 == e2) { |
| 843 | return true; |
| 844 | } |
caryclark | 3f0753d | 2016-06-28 09:23:57 -0700 | [diff] [blame] | 845 | if (approximately_equal_half(s2->fT, e2->fT)) { |
| 846 | return false; |
| 847 | } |
caryclark | 27c8eb8 | 2015-07-06 11:38:33 -0700 | [diff] [blame] | 848 | if (!s2->starter(e2)->span()->upCast()->windValue()) { |
caryclark | 55888e4 | 2016-07-18 10:01:36 -0700 | [diff] [blame] | 849 | if (!(s2 = overS->find(seg2o))) { |
| 850 | return true; |
| 851 | } |
| 852 | if (!(e2 = overE->find(seg2o))) { |
| 853 | return true; |
| 854 | } |
| 855 | if (s2 == e2) { |
| 856 | return true; |
| 857 | } |
caryclark | 27c8eb8 | 2015-07-06 11:38:33 -0700 | [diff] [blame] | 858 | if (!s2->starter(e2)->span()->upCast()->windValue()) { |
caryclark | 3f0753d | 2016-06-28 09:23:57 -0700 | [diff] [blame] | 859 | return true; |
caryclark | 27c8eb8 | 2015-07-06 11:38:33 -0700 | [diff] [blame] | 860 | } |
| 861 | } |
| 862 | if (s1->segment() == s2->segment()) { |
caryclark | 3f0753d | 2016-06-28 09:23:57 -0700 | [diff] [blame] | 863 | return true; |
caryclark | 27c8eb8 | 2015-07-06 11:38:33 -0700 | [diff] [blame] | 864 | } |
| 865 | if (s1->fT > e1->fT) { |
| 866 | SkTSwap(s1, e1); |
| 867 | SkTSwap(s2, e2); |
| 868 | } |
caryclark | 55888e4 | 2016-07-18 10:01:36 -0700 | [diff] [blame] | 869 | this->add(s1, e1, s2, e2); |
caryclark | 3f0753d | 2016-06-28 09:23:57 -0700 | [diff] [blame] | 870 | return true; |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 871 | } |
| 872 | |
caryclark | 55888e4 | 2016-07-18 10:01:36 -0700 | [diff] [blame] | 873 | /* look for pairs of coincidence with no common segments |
| 874 | if there's no existing coincidence found that matches up the segments, and |
| 875 | if the pt-t list for one contains the other, create coincident pairs for what's left */ |
| 876 | bool SkOpCoincidence::addUncommon() { |
| 877 | SkCoincidentSpans* outer = fHead; |
| 878 | if (!outer) { |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 879 | return false; |
| 880 | } |
caryclark | 55888e4 | 2016-07-18 10:01:36 -0700 | [diff] [blame] | 881 | bool added = false; |
| 882 | fTop = outer; |
| 883 | fHead = nullptr; |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 884 | do { |
caryclark | 55888e4 | 2016-07-18 10:01:36 -0700 | [diff] [blame] | 885 | // addifmissing can modify the list that this is walking |
| 886 | // save head so that walker can iterate over old data unperturbed |
| 887 | // addifmissing adds to head freely then add saved head in the end |
| 888 | const SkOpSegment* outerCoin = outer->coinPtTStart()->segment(); |
| 889 | const SkOpSegment* outerOpp = outer->oppPtTStart()->segment(); |
| 890 | if (outerCoin->done() || outerOpp->done()) { |
| 891 | continue; |
| 892 | } |
| 893 | SkCoincidentSpans* inner = outer; |
| 894 | while ((inner = inner->next())) { |
| 895 | this->debugValidate(); |
| 896 | const SkOpSegment* innerCoin = inner->coinPtTStart()->segment(); |
| 897 | const SkOpSegment* innerOpp = inner->oppPtTStart()->segment(); |
| 898 | if (innerCoin->done() || innerOpp->done()) { |
| 899 | continue; |
| 900 | } |
| 901 | // check to see if outer span overlaps the inner span |
| 902 | // look for inner segment in pt-t list |
| 903 | // if present, and if t values are in coincident range |
| 904 | // add two pairs of new coincidence |
| 905 | const SkOpPtT* testS = outer->coinPtTStart()->contains(innerCoin); |
| 906 | const SkOpPtT* testE = outer->coinPtTEnd()->contains(innerCoin); |
| 907 | if (testS && testS->fT >= inner->coinPtTStart()->fT |
| 908 | && testE && testE->fT <= inner->coinPtTEnd()->fT |
| 909 | && this->testForCoincidence(outer, testS, testE)) { |
| 910 | added |= this->addIfMissing(outer, testS, testE); |
| 911 | } else { |
| 912 | testS = inner->coinPtTStart()->contains(outerCoin); |
| 913 | testE = inner->coinPtTEnd()->contains(outerCoin); |
| 914 | if (testS && testS->fT >= outer->coinPtTStart()->fT |
| 915 | && testE && testE->fT <= outer->coinPtTEnd()->fT |
| 916 | && this->testForCoincidence(inner, testS, testE)) { |
| 917 | added |= this->addIfMissing(inner, testS, testE); |
| 918 | } |
| 919 | } |
| 920 | } |
| 921 | } while ((outer = outer->next())); |
| 922 | this->restoreHead(); |
| 923 | return added; |
| 924 | } |
| 925 | |
| 926 | bool SkOpCoincidence::contains(const SkOpSegment* seg, const SkOpSegment* opp, double oppT) const { |
| 927 | if (this->contains(fHead, seg, opp, oppT)) { |
| 928 | return true; |
| 929 | } |
| 930 | if (this->contains(fTop, seg, opp, oppT)) { |
| 931 | return true; |
| 932 | } |
| 933 | return false; |
| 934 | } |
| 935 | |
| 936 | bool SkOpCoincidence::contains(const SkCoincidentSpans* coin, const SkOpSegment* seg, |
| 937 | const SkOpSegment* opp, double oppT) const { |
| 938 | if (!coin) { |
| 939 | return false; |
| 940 | } |
| 941 | do { |
| 942 | if (coin->coinPtTStart()->segment() == seg && coin->oppPtTStart()->segment() == opp |
| 943 | && between(coin->oppPtTStart()->fT, oppT, coin->oppPtTEnd()->fT)) { |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 944 | return true; |
| 945 | } |
caryclark | 55888e4 | 2016-07-18 10:01:36 -0700 | [diff] [blame] | 946 | if (coin->oppPtTStart()->segment() == seg && coin->coinPtTStart()->segment() == opp |
| 947 | && between(coin->coinPtTStart()->fT, oppT, coin->coinPtTEnd()->fT)) { |
| 948 | return true; |
| 949 | } |
| 950 | } while ((coin = coin->next())); |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 951 | return false; |
| 952 | } |
| 953 | |
caryclark | 55888e4 | 2016-07-18 10:01:36 -0700 | [diff] [blame] | 954 | bool SkOpCoincidence::contains(const SkOpPtT* coinPtTStart, const SkOpPtT* coinPtTEnd, |
| 955 | const SkOpPtT* oppPtTStart, const SkOpPtT* oppPtTEnd) const { |
| 956 | const SkCoincidentSpans* test = fHead; |
| 957 | if (!test) { |
| 958 | return false; |
| 959 | } |
| 960 | const SkOpSegment* coinSeg = coinPtTStart->segment(); |
| 961 | const SkOpSegment* oppSeg = oppPtTStart->segment(); |
| 962 | if (!Ordered(coinPtTStart, oppPtTStart)) { |
| 963 | SkTSwap(coinSeg, oppSeg); |
| 964 | SkTSwap(coinPtTStart, oppPtTStart); |
| 965 | SkTSwap(coinPtTEnd, oppPtTEnd); |
| 966 | if (coinPtTStart->fT > coinPtTEnd->fT) { |
| 967 | SkTSwap(coinPtTStart, coinPtTEnd); |
| 968 | SkTSwap(oppPtTStart, oppPtTEnd); |
| 969 | } |
| 970 | } |
| 971 | double oppMinT = SkTMin(oppPtTStart->fT, oppPtTEnd->fT); |
| 972 | double oppMaxT = SkTMax(oppPtTStart->fT, oppPtTEnd->fT); |
| 973 | do { |
| 974 | if (coinSeg != test->coinPtTStart()->segment()) { |
| 975 | continue; |
| 976 | } |
| 977 | if (coinPtTStart->fT < test->coinPtTStart()->fT) { |
| 978 | continue; |
| 979 | } |
| 980 | if (coinPtTEnd->fT > test->coinPtTEnd()->fT) { |
| 981 | continue; |
| 982 | } |
| 983 | if (oppSeg != test->oppPtTStart()->segment()) { |
| 984 | continue; |
| 985 | } |
| 986 | if (oppMinT < SkTMin(test->oppPtTStart()->fT, test->oppPtTEnd()->fT)) { |
| 987 | continue; |
| 988 | } |
| 989 | if (oppMaxT > SkTMax(test->oppPtTStart()->fT, test->oppPtTEnd()->fT)) { |
| 990 | continue; |
| 991 | } |
| 992 | return true; |
| 993 | } while ((test = test->next())); |
| 994 | return false; |
| 995 | } |
| 996 | |
| 997 | void SkOpCoincidence::correctEnds() { |
| 998 | SkCoincidentSpans* coin = fHead; |
| 999 | if (!coin) { |
| 1000 | return; |
| 1001 | } |
| 1002 | do { |
| 1003 | coin->correctEnds(); |
| 1004 | } while ((coin = coin->next())); |
| 1005 | } |
| 1006 | |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 1007 | // walk span sets in parallel, moving winding from one to the other |
| 1008 | bool SkOpCoincidence::apply() { |
| 1009 | SkCoincidentSpans* coin = fHead; |
| 1010 | if (!coin) { |
| 1011 | return true; |
| 1012 | } |
| 1013 | do { |
caryclark | 55888e4 | 2016-07-18 10:01:36 -0700 | [diff] [blame] | 1014 | SkOpSpan* start = coin->coinPtTStartWritable()->span()->upCast(); |
caryclark | 182b499 | 2015-05-14 05:45:54 -0700 | [diff] [blame] | 1015 | if (start->deleted()) { |
| 1016 | continue; |
| 1017 | } |
caryclark | 55888e4 | 2016-07-18 10:01:36 -0700 | [diff] [blame] | 1018 | const SkOpSpanBase* end = coin->coinPtTEnd()->span(); |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 1019 | SkASSERT(start == start->starter(end)); |
caryclark | 55888e4 | 2016-07-18 10:01:36 -0700 | [diff] [blame] | 1020 | bool flipped = coin->flipped(); |
| 1021 | SkOpSpan* oStart = (flipped ? coin->oppPtTEndWritable() |
| 1022 | : coin->oppPtTStartWritable())->span()->upCast(); |
caryclark | 182b499 | 2015-05-14 05:45:54 -0700 | [diff] [blame] | 1023 | if (oStart->deleted()) { |
| 1024 | continue; |
| 1025 | } |
caryclark | 55888e4 | 2016-07-18 10:01:36 -0700 | [diff] [blame] | 1026 | const SkOpSpanBase* oEnd = (flipped ? coin->oppPtTStart() : coin->oppPtTEnd())->span(); |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 1027 | SkASSERT(oStart == oStart->starter(oEnd)); |
| 1028 | SkOpSegment* segment = start->segment(); |
| 1029 | SkOpSegment* oSegment = oStart->segment(); |
| 1030 | bool operandSwap = segment->operand() != oSegment->operand(); |
| 1031 | if (flipped) { |
caryclark | 364a007 | 2015-12-14 08:43:21 -0800 | [diff] [blame] | 1032 | if (oEnd->deleted()) { |
| 1033 | continue; |
| 1034 | } |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 1035 | do { |
| 1036 | SkOpSpanBase* oNext = oStart->next(); |
| 1037 | if (oNext == oEnd) { |
| 1038 | break; |
| 1039 | } |
| 1040 | oStart = oNext->upCast(); |
| 1041 | } while (true); |
| 1042 | } |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 1043 | do { |
| 1044 | int windValue = start->windValue(); |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 1045 | int oppValue = start->oppValue(); |
caryclark | 1049f12 | 2015-04-20 08:31:59 -0700 | [diff] [blame] | 1046 | int oWindValue = oStart->windValue(); |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 1047 | int oOppValue = oStart->oppValue(); |
| 1048 | // winding values are added or subtracted depending on direction and wind type |
| 1049 | // same or opposite values are summed depending on the operand value |
caryclark | 1049f12 | 2015-04-20 08:31:59 -0700 | [diff] [blame] | 1050 | int windDiff = operandSwap ? oOppValue : oWindValue; |
| 1051 | int oWindDiff = operandSwap ? oppValue : windValue; |
| 1052 | if (!flipped) { |
| 1053 | windDiff = -windDiff; |
| 1054 | oWindDiff = -oWindDiff; |
| 1055 | } |
caryclark | 55888e4 | 2016-07-18 10:01:36 -0700 | [diff] [blame] | 1056 | bool addToStart = windValue && (windValue > windDiff || (windValue == windDiff |
| 1057 | && oWindValue <= oWindDiff)); |
| 1058 | if (addToStart ? start->done() : oStart->done()) { |
| 1059 | addToStart ^= true; |
| 1060 | } |
| 1061 | if (addToStart) { |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 1062 | if (operandSwap) { |
| 1063 | SkTSwap(oWindValue, oOppValue); |
| 1064 | } |
| 1065 | if (flipped) { |
| 1066 | windValue -= oWindValue; |
| 1067 | oppValue -= oOppValue; |
| 1068 | } else { |
| 1069 | windValue += oWindValue; |
| 1070 | oppValue += oOppValue; |
| 1071 | } |
caryclark | 1049f12 | 2015-04-20 08:31:59 -0700 | [diff] [blame] | 1072 | if (segment->isXor()) { |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 1073 | windValue &= 1; |
| 1074 | } |
caryclark | 1049f12 | 2015-04-20 08:31:59 -0700 | [diff] [blame] | 1075 | if (segment->oppXor()) { |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 1076 | oppValue &= 1; |
| 1077 | } |
| 1078 | oWindValue = oOppValue = 0; |
| 1079 | } else { |
| 1080 | if (operandSwap) { |
| 1081 | SkTSwap(windValue, oppValue); |
| 1082 | } |
| 1083 | if (flipped) { |
| 1084 | oWindValue -= windValue; |
| 1085 | oOppValue -= oppValue; |
| 1086 | } else { |
| 1087 | oWindValue += windValue; |
| 1088 | oOppValue += oppValue; |
| 1089 | } |
caryclark | 1049f12 | 2015-04-20 08:31:59 -0700 | [diff] [blame] | 1090 | if (oSegment->isXor()) { |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 1091 | oWindValue &= 1; |
| 1092 | } |
caryclark | 1049f12 | 2015-04-20 08:31:59 -0700 | [diff] [blame] | 1093 | if (oSegment->oppXor()) { |
| 1094 | oOppValue &= 1; |
| 1095 | } |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 1096 | windValue = oppValue = 0; |
| 1097 | } |
caryclark | 55888e4 | 2016-07-18 10:01:36 -0700 | [diff] [blame] | 1098 | #if DEBUG_COINCIDENCE |
| 1099 | SkDebugf("seg=%d span=%d windValue=%d oppValue=%d\n", segment->debugID(), |
| 1100 | start->debugID(), windValue, oppValue); |
| 1101 | SkDebugf("seg=%d span=%d windValue=%d oppValue=%d\n", oSegment->debugID(), |
| 1102 | oStart->debugID(), oWindValue, oOppValue); |
| 1103 | #endif |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 1104 | start->setWindValue(windValue); |
| 1105 | start->setOppValue(oppValue); |
| 1106 | oStart->setWindValue(oWindValue); |
| 1107 | oStart->setOppValue(oOppValue); |
| 1108 | if (!windValue && !oppValue) { |
| 1109 | segment->markDone(start); |
| 1110 | } |
| 1111 | if (!oWindValue && !oOppValue) { |
| 1112 | oSegment->markDone(oStart); |
| 1113 | } |
| 1114 | SkOpSpanBase* next = start->next(); |
| 1115 | SkOpSpanBase* oNext = flipped ? oStart->prev() : oStart->next(); |
| 1116 | if (next == end) { |
| 1117 | break; |
| 1118 | } |
caryclark | 26ad22a | 2015-10-16 09:03:38 -0700 | [diff] [blame] | 1119 | if (!next->upCastable()) { |
| 1120 | return false; |
| 1121 | } |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 1122 | start = next->upCast(); |
caryclark | 1049f12 | 2015-04-20 08:31:59 -0700 | [diff] [blame] | 1123 | // if the opposite ran out too soon, just reuse the last span |
| 1124 | if (!oNext || !oNext->upCastable()) { |
| 1125 | oNext = oStart; |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 1126 | } |
| 1127 | oStart = oNext->upCast(); |
| 1128 | } while (true); |
caryclark | 55888e4 | 2016-07-18 10:01:36 -0700 | [diff] [blame] | 1129 | } while ((coin = coin->next())); |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 1130 | return true; |
| 1131 | } |
| 1132 | |
caryclark | 55888e4 | 2016-07-18 10:01:36 -0700 | [diff] [blame] | 1133 | // Please keep this in sync with debugRelease() |
| 1134 | bool SkOpCoincidence::release(SkCoincidentSpans* coin, SkCoincidentSpans* remove) { |
| 1135 | SkCoincidentSpans* head = coin; |
halcanary | 96fcdcc | 2015-08-27 07:41:13 -0700 | [diff] [blame] | 1136 | SkCoincidentSpans* prev = nullptr; |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 1137 | SkCoincidentSpans* next; |
| 1138 | do { |
caryclark | 55888e4 | 2016-07-18 10:01:36 -0700 | [diff] [blame] | 1139 | next = coin->next(); |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 1140 | if (coin == remove) { |
| 1141 | if (prev) { |
caryclark | 55888e4 | 2016-07-18 10:01:36 -0700 | [diff] [blame] | 1142 | prev->setNext(next); |
| 1143 | } else if (head == fHead) { |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 1144 | fHead = next; |
caryclark | 55888e4 | 2016-07-18 10:01:36 -0700 | [diff] [blame] | 1145 | } else { |
| 1146 | fTop = next; |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 1147 | } |
| 1148 | break; |
| 1149 | } |
| 1150 | prev = coin; |
| 1151 | } while ((coin = next)); |
caryclark | 55888e4 | 2016-07-18 10:01:36 -0700 | [diff] [blame] | 1152 | return coin != nullptr; |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 1153 | } |
| 1154 | |
caryclark | 55888e4 | 2016-07-18 10:01:36 -0700 | [diff] [blame] | 1155 | // Please keep this in sync with debugReorder() |
| 1156 | // iterate through all coincident pairs, looking for ranges greater than 1 |
| 1157 | // if found, see if the opposite pair can match it -- which may require |
| 1158 | // reordering the ptT pairs |
| 1159 | bool SkOpCoincidence::reorder() { |
| 1160 | SkCoincidentSpans* coin = fHead; |
| 1161 | if (!coin) { |
| 1162 | return true; |
| 1163 | } |
| 1164 | do { |
| 1165 | // most commonly, concidence are one span long; check for that first |
| 1166 | int intervals = coin->spanCount(); |
| 1167 | if (intervals <= 0) { |
| 1168 | return false; |
| 1169 | } |
| 1170 | if (1 == intervals) { |
| 1171 | #if DEBUG_COINCIDENCE_VERBOSE |
| 1172 | SkASSERT(!coin->debugExpand(nullptr, nullptr)); |
| 1173 | #endif |
| 1174 | continue; |
| 1175 | } |
| 1176 | coin->expand(); // be all that you can be |
| 1177 | if (coin->spanCount() <= 0) { |
| 1178 | return false; |
| 1179 | } |
| 1180 | // check to see if every span in coin has a mate in opp |
| 1181 | const SkOpSpan* start = coin->coinPtTStart()->span()->upCast(); |
| 1182 | bool flipped = coin->flipped(); |
| 1183 | const SkOpSpanBase* oppStartBase = coin->oppPtTStart()->span(); |
| 1184 | const SkOpSpan* oppStart = flipped ? oppStartBase->prev() : oppStartBase->upCast(); |
| 1185 | SkDebugf("", start, oppStart); |
| 1186 | } while ((coin = coin->next())); |
| 1187 | return true; |
| 1188 | } |
| 1189 | |
| 1190 | void SkOpCoincidence::restoreHead() { |
| 1191 | SkCoincidentSpans** headPtr = &fHead; |
| 1192 | while (*headPtr) { |
| 1193 | headPtr = (*headPtr)->nextPtr(); |
| 1194 | } |
| 1195 | *headPtr = fTop; |
| 1196 | fTop = nullptr; |
| 1197 | // segments may have collapsed in the meantime; remove empty referenced segments |
| 1198 | headPtr = &fHead; |
| 1199 | while (*headPtr) { |
| 1200 | SkCoincidentSpans* test = *headPtr; |
| 1201 | if (test->coinPtTStart()->segment()->done() || test->oppPtTStart()->segment()->done()) { |
| 1202 | *headPtr = test->next(); |
| 1203 | continue; |
| 1204 | } |
| 1205 | headPtr = (*headPtr)->nextPtr(); |
| 1206 | } |
| 1207 | } |
| 1208 | |
| 1209 | // Please keep this in sync with debugExpand() |
caryclark | 27c8eb8 | 2015-07-06 11:38:33 -0700 | [diff] [blame] | 1210 | bool SkOpCoincidence::expand() { |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 1211 | SkCoincidentSpans* coin = fHead; |
| 1212 | if (!coin) { |
caryclark | 27c8eb8 | 2015-07-06 11:38:33 -0700 | [diff] [blame] | 1213 | return false; |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 1214 | } |
caryclark | 27c8eb8 | 2015-07-06 11:38:33 -0700 | [diff] [blame] | 1215 | bool expanded = false; |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 1216 | do { |
caryclark | 55888e4 | 2016-07-18 10:01:36 -0700 | [diff] [blame] | 1217 | if (coin->expand()) { |
| 1218 | // check to see if multiple spans expanded so they are now identical |
| 1219 | SkCoincidentSpans* test = fHead; |
| 1220 | do { |
| 1221 | if (coin == test) { |
| 1222 | continue; |
| 1223 | } |
| 1224 | if (coin->coinPtTStart() == test->coinPtTStart() |
| 1225 | && coin->oppPtTStart() == test->oppPtTStart()) { |
| 1226 | this->release(fHead, test); |
| 1227 | break; |
| 1228 | } |
| 1229 | } while ((test = test->next())); |
| 1230 | expanded = true; |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 1231 | } |
caryclark | 55888e4 | 2016-07-18 10:01:36 -0700 | [diff] [blame] | 1232 | } while ((coin = coin->next())); |
caryclark | 27c8eb8 | 2015-07-06 11:38:33 -0700 | [diff] [blame] | 1233 | return expanded; |
| 1234 | } |
| 1235 | |
caryclark | 55888e4 | 2016-07-18 10:01:36 -0700 | [diff] [blame] | 1236 | bool SkOpCoincidence::findOverlaps(SkOpCoincidence* overlaps) const { |
halcanary | 96fcdcc | 2015-08-27 07:41:13 -0700 | [diff] [blame] | 1237 | overlaps->fHead = overlaps->fTop = nullptr; |
caryclark | 27c8eb8 | 2015-07-06 11:38:33 -0700 | [diff] [blame] | 1238 | SkCoincidentSpans* outer = fHead; |
| 1239 | while (outer) { |
caryclark | 55888e4 | 2016-07-18 10:01:36 -0700 | [diff] [blame] | 1240 | const SkOpSegment* outerCoin = outer->coinPtTStart()->segment(); |
| 1241 | const SkOpSegment* outerOpp = outer->oppPtTStart()->segment(); |
caryclark | 27c8eb8 | 2015-07-06 11:38:33 -0700 | [diff] [blame] | 1242 | SkCoincidentSpans* inner = outer; |
caryclark | 55888e4 | 2016-07-18 10:01:36 -0700 | [diff] [blame] | 1243 | while ((inner = inner->next())) { |
| 1244 | const SkOpSegment* innerCoin = inner->coinPtTStart()->segment(); |
caryclark | 27c8eb8 | 2015-07-06 11:38:33 -0700 | [diff] [blame] | 1245 | if (outerCoin == innerCoin) { |
| 1246 | continue; // both winners are the same segment, so there's no additional overlap |
| 1247 | } |
caryclark | 55888e4 | 2016-07-18 10:01:36 -0700 | [diff] [blame] | 1248 | const SkOpSegment* innerOpp = inner->oppPtTStart()->segment(); |
| 1249 | const SkOpPtT* overlapS; |
| 1250 | const SkOpPtT* overlapE; |
| 1251 | if ((outerOpp == innerCoin && SkOpPtT::Overlaps(outer->oppPtTStart(), |
| 1252 | outer->oppPtTEnd(),inner->coinPtTStart(), inner->coinPtTEnd(), &overlapS, |
| 1253 | &overlapE)) |
| 1254 | || (outerCoin == innerOpp && SkOpPtT::Overlaps(outer->coinPtTStart(), |
| 1255 | outer->coinPtTEnd(), inner->oppPtTStart(), inner->oppPtTEnd(), |
caryclark | 27c8eb8 | 2015-07-06 11:38:33 -0700 | [diff] [blame] | 1256 | &overlapS, &overlapE)) |
caryclark | 55888e4 | 2016-07-18 10:01:36 -0700 | [diff] [blame] | 1257 | || (outerOpp == innerOpp && SkOpPtT::Overlaps(outer->oppPtTStart(), |
| 1258 | outer->oppPtTEnd(), inner->oppPtTStart(), inner->oppPtTEnd(), |
caryclark | 27c8eb8 | 2015-07-06 11:38:33 -0700 | [diff] [blame] | 1259 | &overlapS, &overlapE))) { |
caryclark | 3f0753d | 2016-06-28 09:23:57 -0700 | [diff] [blame] | 1260 | if (!overlaps->addOverlap(outerCoin, outerOpp, innerCoin, innerOpp, |
caryclark | 55888e4 | 2016-07-18 10:01:36 -0700 | [diff] [blame] | 1261 | overlapS, overlapE)) { |
caryclark | 3f0753d | 2016-06-28 09:23:57 -0700 | [diff] [blame] | 1262 | return false; |
| 1263 | } |
caryclark | 27c8eb8 | 2015-07-06 11:38:33 -0700 | [diff] [blame] | 1264 | } |
| 1265 | } |
caryclark | 55888e4 | 2016-07-18 10:01:36 -0700 | [diff] [blame] | 1266 | outer = outer->next(); |
caryclark | 27c8eb8 | 2015-07-06 11:38:33 -0700 | [diff] [blame] | 1267 | } |
caryclark | 3f0753d | 2016-06-28 09:23:57 -0700 | [diff] [blame] | 1268 | return true; |
caryclark | 27c8eb8 | 2015-07-06 11:38:33 -0700 | [diff] [blame] | 1269 | } |
| 1270 | |
caryclark | 55888e4 | 2016-07-18 10:01:36 -0700 | [diff] [blame] | 1271 | // Please keep this in sync with debugRemoveCollapsed() |
| 1272 | bool SkOpCoincidence::removeCollapsed() { |
caryclark | 27c8eb8 | 2015-07-06 11:38:33 -0700 | [diff] [blame] | 1273 | SkCoincidentSpans* coin = fHead; |
| 1274 | if (!coin) { |
caryclark | 3f0753d | 2016-06-28 09:23:57 -0700 | [diff] [blame] | 1275 | return true; |
caryclark | 27c8eb8 | 2015-07-06 11:38:33 -0700 | [diff] [blame] | 1276 | } |
caryclark | d434972 | 2015-07-23 12:40:22 -0700 | [diff] [blame] | 1277 | SkCoincidentSpans** priorPtr = &fHead; |
| 1278 | do { |
caryclark | 55888e4 | 2016-07-18 10:01:36 -0700 | [diff] [blame] | 1279 | if (coin->coinPtTStart() == coin->coinPtTEnd()) { |
caryclark | 3f0753d | 2016-06-28 09:23:57 -0700 | [diff] [blame] | 1280 | return false; |
| 1281 | } |
caryclark | 55888e4 | 2016-07-18 10:01:36 -0700 | [diff] [blame] | 1282 | if (coin->oppPtTStart() == coin->oppPtTEnd()) { |
caryclark | 3f0753d | 2016-06-28 09:23:57 -0700 | [diff] [blame] | 1283 | return false; |
| 1284 | } |
caryclark | 55888e4 | 2016-07-18 10:01:36 -0700 | [diff] [blame] | 1285 | if (coin->coinPtTStart()->collapsed(coin->coinPtTEnd())) { |
| 1286 | *priorPtr = coin->next(); |
caryclark | d434972 | 2015-07-23 12:40:22 -0700 | [diff] [blame] | 1287 | continue; |
| 1288 | } |
caryclark | 55888e4 | 2016-07-18 10:01:36 -0700 | [diff] [blame] | 1289 | if (coin->oppPtTStart()->collapsed(coin->oppPtTEnd())) { |
| 1290 | *priorPtr = coin->next(); |
| 1291 | continue; |
| 1292 | } |
| 1293 | priorPtr = coin->nextPtr(); |
| 1294 | } while ((coin = coin->next())); |
caryclark | 3f0753d | 2016-06-28 09:23:57 -0700 | [diff] [blame] | 1295 | return true; |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 1296 | } |
| 1297 | |
caryclark | 55888e4 | 2016-07-18 10:01:36 -0700 | [diff] [blame] | 1298 | void SkOpCoincidence::fixUp(SkOpPtT* deleted, const SkOpPtT* kept) { |
| 1299 | SkASSERT(deleted != kept); |
| 1300 | if (fHead) { |
| 1301 | this->fixUp(fHead, deleted, kept); |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 1302 | } |
caryclark | 55888e4 | 2016-07-18 10:01:36 -0700 | [diff] [blame] | 1303 | if (fTop) { |
| 1304 | this->fixUp(fTop, deleted, kept); |
| 1305 | } |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 1306 | } |
| 1307 | |
caryclark | 55888e4 | 2016-07-18 10:01:36 -0700 | [diff] [blame] | 1308 | void SkOpCoincidence::fixUp(SkCoincidentSpans* coin, SkOpPtT* deleted, const SkOpPtT* kept) { |
| 1309 | SkCoincidentSpans* head = coin; |
| 1310 | do { |
| 1311 | if (coin->coinPtTStart() == deleted) { |
| 1312 | if (coin->coinPtTEnd()->span() == kept->span()) { |
| 1313 | this->release(head, coin); |
| 1314 | continue; |
| 1315 | } |
| 1316 | coin->setCoinPtTStart(kept); |
| 1317 | } |
| 1318 | if (coin->coinPtTEnd() == deleted) { |
| 1319 | if (coin->coinPtTStart()->span() == kept->span()) { |
| 1320 | this->release(head, coin); |
| 1321 | continue; |
| 1322 | } |
| 1323 | coin->setCoinPtTEnd(kept); |
| 1324 | } |
| 1325 | if (coin->oppPtTStart() == deleted) { |
| 1326 | if (coin->oppPtTEnd()->span() == kept->span()) { |
| 1327 | this->release(head, coin); |
| 1328 | continue; |
| 1329 | } |
| 1330 | coin->setOppPtTStart(kept); |
| 1331 | } |
| 1332 | if (coin->oppPtTEnd() == deleted) { |
| 1333 | if (coin->oppPtTStart()->span() == kept->span()) { |
| 1334 | this->release(head, coin); |
| 1335 | continue; |
| 1336 | } |
| 1337 | coin->setOppPtTEnd(kept); |
| 1338 | } |
| 1339 | } while ((coin = coin->next())); |
| 1340 | } |
| 1341 | |
| 1342 | // Please keep this in sync with debugMark() |
caryclark | 27c8eb8 | 2015-07-06 11:38:33 -0700 | [diff] [blame] | 1343 | /* this sets up the coincidence links in the segments when the coincidence crosses multiple spans */ |
caryclark | 5c5cfe2 | 2016-04-05 07:28:48 -0700 | [diff] [blame] | 1344 | bool SkOpCoincidence::mark() { |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 1345 | SkCoincidentSpans* coin = fHead; |
| 1346 | if (!coin) { |
caryclark | 5c5cfe2 | 2016-04-05 07:28:48 -0700 | [diff] [blame] | 1347 | return true; |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 1348 | } |
| 1349 | do { |
caryclark | 55888e4 | 2016-07-18 10:01:36 -0700 | [diff] [blame] | 1350 | SkOpSpan* start = coin->coinPtTStartWritable()->span()->upCast(); |
| 1351 | SkASSERT(!start->deleted()); |
| 1352 | SkOpSpanBase* end = coin->coinPtTEndWritable()->span(); |
| 1353 | SkASSERT(!end->deleted()); |
| 1354 | SkOpSpanBase* oStart = coin->oppPtTStartWritable()->span(); |
| 1355 | SkASSERT(!oStart->deleted()); |
| 1356 | SkOpSpanBase* oEnd = coin->oppPtTEndWritable()->span(); |
| 1357 | SkASSERT(!oEnd->deleted()); |
| 1358 | bool flipped = coin->flipped(); |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 1359 | if (flipped) { |
| 1360 | SkTSwap(oStart, oEnd); |
| 1361 | } |
caryclark | 55888e4 | 2016-07-18 10:01:36 -0700 | [diff] [blame] | 1362 | /* coin and opp spans may not match up. Mark the ends, and then let the interior |
| 1363 | get marked as many times as the spans allow */ |
| 1364 | start->insertCoincidence(oStart->upCast()); |
| 1365 | end->insertCoinEnd(oEnd); |
| 1366 | const SkOpSegment* segment = start->segment(); |
| 1367 | const SkOpSegment* oSegment = oStart->segment(); |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 1368 | SkOpSpanBase* next = start; |
| 1369 | SkOpSpanBase* oNext = oStart; |
caryclark | 55888e4 | 2016-07-18 10:01:36 -0700 | [diff] [blame] | 1370 | while ((next = next->upCast()->next()) != end) { |
| 1371 | if (!next->upCast()->insertCoincidence(oSegment, flipped)) { |
| 1372 | return false; |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 1373 | } |
caryclark | 55888e4 | 2016-07-18 10:01:36 -0700 | [diff] [blame] | 1374 | } |
| 1375 | while ((oNext = oNext->upCast()->next()) != oEnd) { |
| 1376 | if (!oNext->upCast()->insertCoincidence(segment, flipped)) { |
| 1377 | return false; |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 1378 | } |
caryclark | 55888e4 | 2016-07-18 10:01:36 -0700 | [diff] [blame] | 1379 | } |
| 1380 | } while ((coin = coin->next())); |
caryclark | 5c5cfe2 | 2016-04-05 07:28:48 -0700 | [diff] [blame] | 1381 | return true; |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 1382 | } |
| 1383 | |
caryclark | 55888e4 | 2016-07-18 10:01:36 -0700 | [diff] [blame] | 1384 | // Please keep in sync with debugMarkCollapsed() |
| 1385 | void SkOpCoincidence::markCollapsed(SkCoincidentSpans* coin, SkOpPtT* test) { |
| 1386 | SkCoincidentSpans* head = coin; |
| 1387 | while (coin) { |
| 1388 | if (coin->collapsed(test)) { |
| 1389 | if (zero_or_one(coin->coinPtTStart()->fT) && zero_or_one(coin->coinPtTEnd()->fT)) { |
| 1390 | coin->coinPtTStartWritable()->segment()->markAllDone(); |
| 1391 | } |
| 1392 | if (zero_or_one(coin->oppPtTStart()->fT) && zero_or_one(coin->oppPtTEnd()->fT)) { |
| 1393 | coin->oppPtTStartWritable()->segment()->markAllDone(); |
| 1394 | } |
| 1395 | this->release(head, coin); |
| 1396 | } |
| 1397 | coin = coin->next(); |
| 1398 | } |
| 1399 | } |
| 1400 | |
| 1401 | // Please keep in sync with debugMarkCollapsed() |
| 1402 | void SkOpCoincidence::markCollapsed(SkOpPtT* test) { |
| 1403 | markCollapsed(fHead, test); |
| 1404 | markCollapsed(fTop, test); |
| 1405 | } |
| 1406 | |
| 1407 | bool SkOpCoincidence::Ordered(const SkOpSegment* coinSeg, const SkOpSegment* oppSeg) { |
| 1408 | if (coinSeg->verb() < oppSeg->verb()) { |
| 1409 | return true; |
| 1410 | } |
| 1411 | if (coinSeg->verb() > oppSeg->verb()) { |
| 1412 | return false; |
| 1413 | } |
| 1414 | int count = (SkPathOpsVerbToPoints(coinSeg->verb()) + 1) * 2; |
| 1415 | const SkScalar* cPt = &coinSeg->pts()[0].fX; |
| 1416 | const SkScalar* oPt = &oppSeg->pts()[0].fX; |
| 1417 | for (int index = 0; index < count; ++index) { |
| 1418 | if (*cPt < *oPt) { |
| 1419 | return true; |
| 1420 | } |
| 1421 | if (*cPt > *oPt) { |
| 1422 | return false; |
| 1423 | } |
| 1424 | ++cPt; |
| 1425 | ++oPt; |
| 1426 | } |
| 1427 | return true; |
| 1428 | } |
| 1429 | |
| 1430 | bool SkOpCoincidence::overlap(const SkOpPtT* coin1s, const SkOpPtT* coin1e, |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 1431 | const SkOpPtT* coin2s, const SkOpPtT* coin2e, double* overS, double* overE) const { |
caryclark | 27c8eb8 | 2015-07-06 11:38:33 -0700 | [diff] [blame] | 1432 | SkASSERT(coin1s->segment() == coin2s->segment()); |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 1433 | *overS = SkTMax(SkTMin(coin1s->fT, coin1e->fT), SkTMin(coin2s->fT, coin2e->fT)); |
| 1434 | *overE = SkTMin(SkTMax(coin1s->fT, coin1e->fT), SkTMax(coin2s->fT, coin2e->fT)); |
| 1435 | return *overS < *overE; |
| 1436 | } |
caryclark | 27c8eb8 | 2015-07-06 11:38:33 -0700 | [diff] [blame] | 1437 | |
caryclark | 55888e4 | 2016-07-18 10:01:36 -0700 | [diff] [blame] | 1438 | // Commented-out lines keep this in sync with debugRelease() |
| 1439 | void SkOpCoincidence::release(const SkOpSegment* deleted) { |
| 1440 | SkCoincidentSpans* coin = fHead; |
| 1441 | if (!coin) { |
| 1442 | return; |
| 1443 | } |
| 1444 | do { |
| 1445 | if (coin->coinPtTStart()->segment() == deleted |
| 1446 | || coin->coinPtTEnd()->segment() == deleted |
| 1447 | || coin->oppPtTStart()->segment() == deleted |
| 1448 | || coin->oppPtTEnd()->segment() == deleted) { |
| 1449 | this->release(fHead, coin); |
| 1450 | } |
| 1451 | } while ((coin = coin->next())); |
| 1452 | } |
| 1453 | |
caryclark | 26ad22a | 2015-10-16 09:03:38 -0700 | [diff] [blame] | 1454 | bool SkOpCoincidence::testForCoincidence(const SkCoincidentSpans* outer, const SkOpPtT* testS, |
| 1455 | const SkOpPtT* testE) const { |
caryclark | 27c8eb8 | 2015-07-06 11:38:33 -0700 | [diff] [blame] | 1456 | return testS->segment()->testForCoincidence(testS, testE, testS->span(), |
caryclark | 55888e4 | 2016-07-18 10:01:36 -0700 | [diff] [blame] | 1457 | testE->span(), outer->coinPtTStart()->segment()); |
caryclark | 27c8eb8 | 2015-07-06 11:38:33 -0700 | [diff] [blame] | 1458 | } |