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