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