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 | bca19f7 | 2015-05-13 08:23:48 -0700 | [diff] [blame] | 11 | bool SkOpCoincidence::extend(SkOpPtT* coinPtTStart, SkOpPtT* coinPtTEnd, SkOpPtT* oppPtTStart, |
| 12 | SkOpPtT* oppPtTEnd) { |
| 13 | // if there is an existing pair that overlaps the addition, extend it |
| 14 | SkCoincidentSpans* coinRec = fHead; |
| 15 | if (coinRec) { |
| 16 | do { |
| 17 | if (coinRec->fCoinPtTStart->segment() != coinPtTStart->segment()) { |
| 18 | continue; |
| 19 | } |
| 20 | if (coinRec->fOppPtTStart->segment() != oppPtTStart->segment()) { |
| 21 | continue; |
| 22 | } |
| 23 | if (coinRec->fCoinPtTStart->fT > coinPtTEnd->fT) { |
| 24 | continue; |
| 25 | } |
| 26 | if (coinRec->fCoinPtTEnd->fT < coinPtTStart->fT) { |
| 27 | continue; |
| 28 | } |
| 29 | if (coinRec->fCoinPtTStart->fT > coinPtTStart->fT) { |
| 30 | coinRec->fCoinPtTStart = coinPtTStart; |
| 31 | coinRec->fOppPtTStart = oppPtTStart; |
| 32 | } |
| 33 | if (coinRec->fCoinPtTEnd->fT < coinPtTEnd->fT) { |
| 34 | coinRec->fCoinPtTEnd = coinPtTEnd; |
| 35 | coinRec->fOppPtTEnd = oppPtTEnd; |
| 36 | } |
| 37 | return true; |
| 38 | } while ((coinRec = coinRec->fNext)); |
| 39 | } |
| 40 | return false; |
| 41 | } |
| 42 | |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 43 | void SkOpCoincidence::add(SkOpPtT* coinPtTStart, SkOpPtT* coinPtTEnd, SkOpPtT* oppPtTStart, |
| 44 | SkOpPtT* oppPtTEnd, SkChunkAlloc* allocator) { |
| 45 | SkASSERT(coinPtTStart->fT < coinPtTEnd->fT); |
| 46 | bool flipped = oppPtTStart->fT > oppPtTEnd->fT; |
| 47 | SkCoincidentSpans* coinRec = SkOpTAllocator<SkCoincidentSpans>::Allocate(allocator); |
| 48 | coinRec->fNext = this->fHead; |
| 49 | coinRec->fCoinPtTStart = coinPtTStart; |
| 50 | coinRec->fCoinPtTEnd = coinPtTEnd; |
| 51 | coinRec->fOppPtTStart = oppPtTStart; |
| 52 | coinRec->fOppPtTEnd = oppPtTEnd; |
| 53 | coinRec->fFlipped = flipped; |
caryclark | 26ad22a | 2015-10-16 09:03:38 -0700 | [diff] [blame] | 54 | SkDEBUGCODE(coinRec->fID = fDebugState->nextCoinID()); |
| 55 | |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 56 | this->fHead = coinRec; |
| 57 | } |
| 58 | |
caryclark | 1049f12 | 2015-04-20 08:31:59 -0700 | [diff] [blame] | 59 | static void t_range(const SkOpPtT* overS, const SkOpPtT* overE, double tStart, double tEnd, |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 60 | const SkOpPtT* coinPtTStart, const SkOpPtT* coinPtTEnd, double* coinTs, double* coinTe) { |
| 61 | double denom = overE->fT - overS->fT; |
| 62 | double start = 0 < denom ? tStart : tEnd; |
| 63 | double end = 0 < denom ? tEnd : tStart; |
| 64 | double sRatio = (start - overS->fT) / denom; |
| 65 | double eRatio = (end - overS->fT) / denom; |
| 66 | *coinTs = coinPtTStart->fT + (coinPtTEnd->fT - coinPtTStart->fT) * sRatio; |
| 67 | *coinTe = coinPtTStart->fT + (coinPtTEnd->fT - coinPtTStart->fT) * eRatio; |
| 68 | } |
| 69 | |
caryclark | 26ad22a | 2015-10-16 09:03:38 -0700 | [diff] [blame] | 70 | bool SkOpCoincidence::addExpanded(SkChunkAlloc* allocator |
caryclark | 27c8eb8 | 2015-07-06 11:38:33 -0700 | [diff] [blame] | 71 | PATH_OPS_DEBUG_VALIDATE_PARAMS(SkOpGlobalState* globalState)) { |
| 72 | #if DEBUG_VALIDATE |
| 73 | globalState->setPhase(SkOpGlobalState::kIntersecting); |
| 74 | #endif |
| 75 | // for each coincident pair, match the spans |
| 76 | // if the spans don't match, add the mssing pt to the segment and loop it in the opposite span |
| 77 | SkCoincidentSpans* coin = this->fHead; |
| 78 | SkASSERT(coin); |
| 79 | do { |
| 80 | SkOpPtT* startPtT = coin->fCoinPtTStart; |
| 81 | SkOpPtT* oStartPtT = coin->fOppPtTStart; |
| 82 | SkASSERT(startPtT->contains(oStartPtT)); |
| 83 | SkASSERT(coin->fCoinPtTEnd->contains(coin->fOppPtTEnd)); |
| 84 | SkOpSpanBase* start = startPtT->span(); |
| 85 | SkOpSpanBase* oStart = oStartPtT->span(); |
| 86 | const SkOpSpanBase* end = coin->fCoinPtTEnd->span(); |
| 87 | const SkOpSpanBase* oEnd = coin->fOppPtTEnd->span(); |
caryclark | 1c9ce61 | 2015-11-20 14:06:28 -0800 | [diff] [blame] | 88 | if (oEnd->deleted()) { |
| 89 | return false; |
| 90 | } |
caryclark | 27c8eb8 | 2015-07-06 11:38:33 -0700 | [diff] [blame] | 91 | SkOpSpanBase* test = start->upCast()->next(); |
| 92 | SkOpSpanBase* oTest = coin->fFlipped ? oStart->prev() : oStart->upCast()->next(); |
| 93 | while (test != end || oTest != oEnd) { |
| 94 | if (!test->ptT()->contains(oTest->ptT())) { |
| 95 | // use t ranges to guess which one is missing |
| 96 | double startRange = coin->fCoinPtTEnd->fT - startPtT->fT; |
caryclark | 952ebfe | 2015-11-02 07:32:58 -0800 | [diff] [blame] | 97 | if (!startRange) { |
| 98 | return false; |
| 99 | } |
caryclark | 27c8eb8 | 2015-07-06 11:38:33 -0700 | [diff] [blame] | 100 | double startPart = (test->t() - startPtT->fT) / startRange; |
| 101 | double oStartRange = coin->fOppPtTEnd->fT - oStartPtT->fT; |
caryclark | 952ebfe | 2015-11-02 07:32:58 -0800 | [diff] [blame] | 102 | if (!oStartRange) { |
| 103 | return false; |
| 104 | } |
caryclark | 27c8eb8 | 2015-07-06 11:38:33 -0700 | [diff] [blame] | 105 | double oStartPart = (oTest->t() - oStartPtT->fT) / oStartRange; |
caryclark | 26ad22a | 2015-10-16 09:03:38 -0700 | [diff] [blame] | 106 | if (startPart == oStartPart) { |
| 107 | return false; |
| 108 | } |
caryclark | 27c8eb8 | 2015-07-06 11:38:33 -0700 | [diff] [blame] | 109 | SkOpPtT* newPt; |
| 110 | if (startPart < oStartPart) { |
| 111 | double newT = oStartPtT->fT + oStartRange * startPart; |
| 112 | newPt = oStart->segment()->addT(newT, SkOpSegment::kAllowAlias, allocator); |
caryclark | a3375e4 | 2015-12-07 12:18:02 -0800 | [diff] [blame] | 113 | if (!newPt) { |
| 114 | return false; |
| 115 | } |
caryclark | 27c8eb8 | 2015-07-06 11:38:33 -0700 | [diff] [blame] | 116 | newPt->fPt = test->pt(); |
| 117 | test->ptT()->addOpp(newPt); |
| 118 | } else { |
| 119 | double newT = startPtT->fT + startRange * oStartPart; |
| 120 | newPt = start->segment()->addT(newT, SkOpSegment::kAllowAlias, allocator); |
caryclark | a3375e4 | 2015-12-07 12:18:02 -0800 | [diff] [blame] | 121 | if (!newPt) { |
| 122 | return false; |
| 123 | } |
caryclark | 27c8eb8 | 2015-07-06 11:38:33 -0700 | [diff] [blame] | 124 | newPt->fPt = oTest->pt(); |
| 125 | oTest->ptT()->addOpp(newPt); |
| 126 | } |
| 127 | // start over |
| 128 | test = start; |
| 129 | oTest = oStart; |
| 130 | } |
| 131 | if (test != end) { |
| 132 | test = test->upCast()->next(); |
| 133 | } |
caryclark | 26ad22a | 2015-10-16 09:03:38 -0700 | [diff] [blame] | 134 | if (oTest != oEnd) { |
caryclark | 27c8eb8 | 2015-07-06 11:38:33 -0700 | [diff] [blame] | 135 | oTest = coin->fFlipped ? oTest->prev() : oTest->upCast()->next(); |
| 136 | } |
| 137 | } |
| 138 | } while ((coin = coin->fNext)); |
| 139 | #if DEBUG_VALIDATE |
| 140 | globalState->setPhase(SkOpGlobalState::kWalking); |
| 141 | #endif |
caryclark | 26ad22a | 2015-10-16 09:03:38 -0700 | [diff] [blame] | 142 | return true; |
caryclark | 27c8eb8 | 2015-07-06 11:38:33 -0700 | [diff] [blame] | 143 | } |
| 144 | |
caryclark | 26ad22a | 2015-10-16 09:03:38 -0700 | [diff] [blame] | 145 | bool SkOpCoincidence::addIfMissing(const SkCoincidentSpans* outer, SkOpPtT* over1s, |
caryclark | 27c8eb8 | 2015-07-06 11:38:33 -0700 | [diff] [blame] | 146 | SkOpPtT* over1e, SkChunkAlloc* allocator) { |
| 147 | SkCoincidentSpans* check = this->fTop; |
| 148 | do { |
| 149 | if (check->fCoinPtTStart->span() == over1s->span() |
| 150 | && check->fOppPtTStart->span() == outer->fOppPtTStart->span()) { |
| 151 | SkASSERT(check->fCoinPtTEnd->span() == over1e->span() |
| 152 | || !fDebugState->debugRunFail()); |
| 153 | SkASSERT(check->fOppPtTEnd->span() == outer->fOppPtTEnd->span() |
| 154 | || !fDebugState->debugRunFail()); |
caryclark | 26ad22a | 2015-10-16 09:03:38 -0700 | [diff] [blame] | 155 | return false; |
caryclark | 27c8eb8 | 2015-07-06 11:38:33 -0700 | [diff] [blame] | 156 | } |
| 157 | if (check->fCoinPtTStart->span() == outer->fCoinPtTStart->span() |
| 158 | && check->fOppPtTStart->span() == over1s->span()) { |
| 159 | SkASSERT(check->fCoinPtTEnd->span() == outer->fCoinPtTEnd->span() |
| 160 | || !fDebugState->debugRunFail()); |
| 161 | SkASSERT(check->fOppPtTEnd->span() == over1e->span() |
| 162 | || !fDebugState->debugRunFail()); |
caryclark | 26ad22a | 2015-10-16 09:03:38 -0700 | [diff] [blame] | 163 | return false; |
caryclark | 27c8eb8 | 2015-07-06 11:38:33 -0700 | [diff] [blame] | 164 | } |
| 165 | } while ((check = check->fNext)); |
| 166 | this->add(outer->fCoinPtTStart, outer->fCoinPtTEnd, over1s, over1e, allocator); |
| 167 | #if 0 |
| 168 | // FIXME: up to four flavors could be added -- do we need only one? |
| 169 | #endif |
caryclark | 26ad22a | 2015-10-16 09:03:38 -0700 | [diff] [blame] | 170 | return true; |
caryclark | 27c8eb8 | 2015-07-06 11:38:33 -0700 | [diff] [blame] | 171 | } |
| 172 | |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 173 | bool SkOpCoincidence::addIfMissing(const SkOpPtT* over1s, const SkOpPtT* over1e, |
| 174 | const SkOpPtT* over2s, const SkOpPtT* over2e, double tStart, double tEnd, |
| 175 | SkOpPtT* coinPtTStart, const SkOpPtT* coinPtTEnd, |
| 176 | SkOpPtT* oppPtTStart, const SkOpPtT* oppPtTEnd, SkChunkAlloc* allocator) { |
| 177 | double coinTs, coinTe, oppTs, oppTe; |
caryclark | 1049f12 | 2015-04-20 08:31:59 -0700 | [diff] [blame] | 178 | t_range(over1s, over1e, tStart, tEnd, coinPtTStart, coinPtTEnd, &coinTs, &coinTe); |
| 179 | t_range(over2s, over2e, tStart, tEnd, oppPtTStart, oppPtTEnd, &oppTs, &oppTe); |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 180 | SkOpSegment* coinSeg = coinPtTStart->segment(); |
| 181 | SkOpSegment* oppSeg = oppPtTStart->segment(); |
| 182 | SkASSERT(coinSeg != oppSeg); |
caryclark | 27c8eb8 | 2015-07-06 11:38:33 -0700 | [diff] [blame] | 183 | SkCoincidentSpans* check = this->fTop; |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 184 | do { |
| 185 | const SkOpSegment* checkCoinSeg = check->fCoinPtTStart->segment(); |
| 186 | if (checkCoinSeg != coinSeg && checkCoinSeg != oppSeg) { |
| 187 | continue; |
| 188 | } |
| 189 | const SkOpSegment* checkOppSeg = check->fOppPtTStart->segment(); |
| 190 | if (checkOppSeg != coinSeg && checkOppSeg != oppSeg) { |
| 191 | continue; |
| 192 | } |
| 193 | int cTs = coinTs; |
| 194 | int cTe = coinTe; |
| 195 | int oTs = oppTs; |
| 196 | int oTe = oppTe; |
| 197 | if (checkCoinSeg != coinSeg) { |
| 198 | SkASSERT(checkOppSeg != oppSeg); |
| 199 | SkTSwap(cTs, oTs); |
| 200 | SkTSwap(cTe, oTe); |
| 201 | } |
| 202 | int tweenCount = (int) between(check->fCoinPtTStart->fT, cTs, check->fCoinPtTEnd->fT) |
| 203 | + (int) between(check->fCoinPtTStart->fT, cTe, check->fCoinPtTEnd->fT) |
| 204 | + (int) between(check->fOppPtTStart->fT, oTs, check->fOppPtTEnd->fT) |
| 205 | + (int) between(check->fOppPtTStart->fT, oTe, check->fOppPtTEnd->fT); |
| 206 | // SkASSERT(tweenCount == 0 || tweenCount == 4); |
| 207 | if (tweenCount) { |
caryclark | 26ad22a | 2015-10-16 09:03:38 -0700 | [diff] [blame] | 208 | return false; |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 209 | } |
| 210 | } while ((check = check->fNext)); |
| 211 | if ((over1s->fT < over1e->fT) != (over2s->fT < over2e->fT)) { |
| 212 | SkTSwap(oppTs, oppTe); |
| 213 | } |
| 214 | if (coinTs > coinTe) { |
| 215 | SkTSwap(coinTs, coinTe); |
| 216 | SkTSwap(oppTs, oppTe); |
| 217 | } |
| 218 | SkOpPtT* cs = coinSeg->addMissing(coinTs, oppSeg, allocator); |
| 219 | SkOpPtT* ce = coinSeg->addMissing(coinTe, oppSeg, allocator); |
caryclark | 26ad22a | 2015-10-16 09:03:38 -0700 | [diff] [blame] | 220 | SkASSERT(cs != ce); |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 221 | SkOpPtT* os = oppSeg->addMissing(oppTs, coinSeg, allocator); |
| 222 | SkOpPtT* oe = oppSeg->addMissing(oppTe, coinSeg, allocator); |
caryclark | ed0935a | 2015-10-22 07:23:52 -0700 | [diff] [blame] | 223 | // SkASSERT(os != oe); |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 224 | cs->addOpp(os); |
| 225 | ce->addOpp(oe); |
| 226 | this->add(cs, ce, os, oe, allocator); |
| 227 | return true; |
| 228 | } |
| 229 | |
caryclark | 27c8eb8 | 2015-07-06 11:38:33 -0700 | [diff] [blame] | 230 | /* detects overlaps of different coincident runs on same segment */ |
| 231 | /* does not detect overlaps for pairs without any segments in common */ |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 232 | bool SkOpCoincidence::addMissing(SkChunkAlloc* allocator) { |
caryclark | 27c8eb8 | 2015-07-06 11:38:33 -0700 | [diff] [blame] | 233 | SkCoincidentSpans* outer = fHead; |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 234 | if (!outer) { |
| 235 | return true; |
| 236 | } |
caryclark | 26ad22a | 2015-10-16 09:03:38 -0700 | [diff] [blame] | 237 | bool added = false; |
caryclark | 27c8eb8 | 2015-07-06 11:38:33 -0700 | [diff] [blame] | 238 | fTop = outer; |
halcanary | 96fcdcc | 2015-08-27 07:41:13 -0700 | [diff] [blame] | 239 | fHead = nullptr; |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 240 | do { |
caryclark | 27c8eb8 | 2015-07-06 11:38:33 -0700 | [diff] [blame] | 241 | // addifmissing can modify the list that this is walking |
caryclark | 26ad22a | 2015-10-16 09:03:38 -0700 | [diff] [blame] | 242 | // save head so that walker can iterate over old data unperturbed |
| 243 | // addifmissing adds to head freely then add saved head in the end |
caryclark | 27c8eb8 | 2015-07-06 11:38:33 -0700 | [diff] [blame] | 244 | const SkOpSegment* outerCoin = outer->fCoinPtTStart->segment(); |
| 245 | SkASSERT(outerCoin == outer->fCoinPtTEnd->segment()); |
| 246 | const SkOpSegment* outerOpp = outer->fOppPtTStart->segment(); |
| 247 | SkASSERT(outerOpp == outer->fOppPtTEnd->segment()); |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 248 | SkCoincidentSpans* inner = outer; |
| 249 | while ((inner = inner->fNext)) { |
| 250 | double overS, overE; |
caryclark | 27c8eb8 | 2015-07-06 11:38:33 -0700 | [diff] [blame] | 251 | const SkOpSegment* innerCoin = inner->fCoinPtTStart->segment(); |
| 252 | SkASSERT(innerCoin == inner->fCoinPtTEnd->segment()); |
| 253 | const SkOpSegment* innerOpp = inner->fOppPtTStart->segment(); |
| 254 | SkASSERT(innerOpp == inner->fOppPtTEnd->segment()); |
| 255 | if (outerCoin == innerCoin |
| 256 | && this->overlap(outer->fCoinPtTStart, outer->fCoinPtTEnd, |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 257 | inner->fCoinPtTStart, inner->fCoinPtTEnd, &overS, &overE)) { |
caryclark | 26ad22a | 2015-10-16 09:03:38 -0700 | [diff] [blame] | 258 | added |= this->addIfMissing(outer->fCoinPtTStart, outer->fCoinPtTEnd, |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 259 | inner->fCoinPtTStart, inner->fCoinPtTEnd, overS, overE, |
| 260 | outer->fOppPtTStart, outer->fOppPtTEnd, |
caryclark | 26ad22a | 2015-10-16 09:03:38 -0700 | [diff] [blame] | 261 | inner->fOppPtTStart, inner->fOppPtTEnd, allocator); |
caryclark | 27c8eb8 | 2015-07-06 11:38:33 -0700 | [diff] [blame] | 262 | } else if (outerCoin == innerOpp |
| 263 | && this->overlap(outer->fCoinPtTStart, outer->fCoinPtTEnd, |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 264 | inner->fOppPtTStart, inner->fOppPtTEnd, &overS, &overE)) { |
caryclark | 26ad22a | 2015-10-16 09:03:38 -0700 | [diff] [blame] | 265 | added |= this->addIfMissing(outer->fCoinPtTStart, outer->fCoinPtTEnd, |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 266 | inner->fOppPtTStart, inner->fOppPtTEnd, overS, overE, |
| 267 | outer->fOppPtTStart, outer->fOppPtTEnd, |
caryclark | 26ad22a | 2015-10-16 09:03:38 -0700 | [diff] [blame] | 268 | inner->fCoinPtTStart, inner->fCoinPtTEnd, allocator); |
caryclark | 27c8eb8 | 2015-07-06 11:38:33 -0700 | [diff] [blame] | 269 | } else if (outerOpp == innerCoin |
| 270 | && this->overlap(outer->fOppPtTStart, outer->fOppPtTEnd, |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 271 | inner->fCoinPtTStart, inner->fCoinPtTEnd, &overS, &overE)) { |
caryclark | 26ad22a | 2015-10-16 09:03:38 -0700 | [diff] [blame] | 272 | added |= this->addIfMissing(outer->fOppPtTStart, outer->fOppPtTEnd, |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 273 | inner->fCoinPtTStart, inner->fCoinPtTEnd, overS, overE, |
| 274 | outer->fCoinPtTStart, outer->fCoinPtTEnd, |
caryclark | 26ad22a | 2015-10-16 09:03:38 -0700 | [diff] [blame] | 275 | inner->fOppPtTStart, inner->fOppPtTEnd, allocator); |
caryclark | 27c8eb8 | 2015-07-06 11:38:33 -0700 | [diff] [blame] | 276 | } else if (outerOpp == innerOpp |
| 277 | && this->overlap(outer->fOppPtTStart, outer->fOppPtTEnd, |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 278 | inner->fOppPtTStart, inner->fOppPtTEnd, &overS, &overE)) { |
caryclark | 26ad22a | 2015-10-16 09:03:38 -0700 | [diff] [blame] | 279 | added |= this->addIfMissing(outer->fOppPtTStart, outer->fOppPtTEnd, |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 280 | inner->fOppPtTStart, inner->fOppPtTEnd, overS, overE, |
| 281 | outer->fCoinPtTStart, outer->fCoinPtTEnd, |
caryclark | 26ad22a | 2015-10-16 09:03:38 -0700 | [diff] [blame] | 282 | inner->fCoinPtTStart, inner->fCoinPtTEnd, allocator); |
caryclark | 27c8eb8 | 2015-07-06 11:38:33 -0700 | [diff] [blame] | 283 | } else if (outerCoin != innerCoin) { |
| 284 | // check to see if outer span overlaps the inner span |
| 285 | // look for inner segment in pt-t list |
| 286 | // if present, and if t values are in coincident range |
| 287 | // add two pairs of new coincidence |
| 288 | SkOpPtT* testS = outer->fCoinPtTStart->contains(innerCoin); |
| 289 | SkOpPtT* testE = outer->fCoinPtTEnd->contains(innerCoin); |
| 290 | if (testS && testS->fT >= inner->fCoinPtTStart->fT |
| 291 | && testE && testE->fT <= inner->fCoinPtTEnd->fT |
| 292 | && this->testForCoincidence(outer, testS, testE)) { |
caryclark | 26ad22a | 2015-10-16 09:03:38 -0700 | [diff] [blame] | 293 | added |= this->addIfMissing(outer, testS, testE, allocator); |
caryclark | 27c8eb8 | 2015-07-06 11:38:33 -0700 | [diff] [blame] | 294 | } else { |
| 295 | testS = inner->fCoinPtTStart->contains(outerCoin); |
| 296 | testE = inner->fCoinPtTEnd->contains(outerCoin); |
| 297 | if (testS && testS->fT >= outer->fCoinPtTStart->fT |
| 298 | && testE && testE->fT <= outer->fCoinPtTEnd->fT |
| 299 | && this->testForCoincidence(inner, testS, testE)) { |
caryclark | 26ad22a | 2015-10-16 09:03:38 -0700 | [diff] [blame] | 300 | added |= this->addIfMissing(inner, testS, testE, allocator); |
caryclark | 27c8eb8 | 2015-07-06 11:38:33 -0700 | [diff] [blame] | 301 | } |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 302 | } |
| 303 | } |
caryclark | 26ad22a | 2015-10-16 09:03:38 -0700 | [diff] [blame] | 304 | #if 0 && DEBUG_COINCIDENCE |
| 305 | SkString miss; |
| 306 | miss.printf("addMissing inner=%d outer=%d", inner->debugID(), outer->debugID()); |
| 307 | DEBUG_COINCIDENCE_HEALTH(fDebugState->contourHead(), miss.c_str()); |
| 308 | #endif |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 309 | } |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 310 | } while ((outer = outer->fNext)); |
caryclark | 27c8eb8 | 2015-07-06 11:38:33 -0700 | [diff] [blame] | 311 | SkCoincidentSpans** headPtr = &fHead; |
| 312 | while (*headPtr) { |
| 313 | SkCoincidentSpans** headNext = &(*headPtr)->fNext; |
| 314 | if (*headNext) { |
| 315 | break; |
| 316 | } |
| 317 | headPtr = headNext; |
| 318 | } |
| 319 | *headPtr = fTop; |
caryclark | 26ad22a | 2015-10-16 09:03:38 -0700 | [diff] [blame] | 320 | return added; |
caryclark | 27c8eb8 | 2015-07-06 11:38:33 -0700 | [diff] [blame] | 321 | } |
| 322 | |
| 323 | void SkOpCoincidence::addOverlap(SkOpSegment* seg1, SkOpSegment* seg1o, SkOpSegment* seg2, |
| 324 | SkOpSegment* seg2o, SkOpPtT* overS, SkOpPtT* overE, SkChunkAlloc* allocator) { |
| 325 | SkOpPtT* s1 = overS->find(seg1); |
| 326 | SkOpPtT* e1 = overE->find(seg1); |
| 327 | if (!s1->starter(e1)->span()->upCast()->windValue()) { |
| 328 | s1 = overS->find(seg1o); |
| 329 | e1 = overE->find(seg1o); |
| 330 | if (!s1->starter(e1)->span()->upCast()->windValue()) { |
| 331 | return; |
| 332 | } |
| 333 | } |
| 334 | SkOpPtT* s2 = overS->find(seg2); |
| 335 | SkOpPtT* e2 = overE->find(seg2); |
| 336 | if (!s2->starter(e2)->span()->upCast()->windValue()) { |
| 337 | s2 = overS->find(seg2o); |
| 338 | e2 = overE->find(seg2o); |
| 339 | if (!s2->starter(e2)->span()->upCast()->windValue()) { |
| 340 | return; |
| 341 | } |
| 342 | } |
| 343 | if (s1->segment() == s2->segment()) { |
| 344 | return; |
| 345 | } |
| 346 | if (s1->fT > e1->fT) { |
| 347 | SkTSwap(s1, e1); |
| 348 | SkTSwap(s2, e2); |
| 349 | } |
| 350 | this->add(s1, e1, s2, e2, allocator); |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 351 | } |
| 352 | |
caryclark | 26ad22a | 2015-10-16 09:03:38 -0700 | [diff] [blame] | 353 | bool SkOpCoincidence::contains(const SkOpPtT* coinPtTStart, const SkOpPtT* coinPtTEnd, |
| 354 | const SkOpPtT* oppPtTStart, const SkOpPtT* oppPtTEnd, bool flipped) const { |
| 355 | const SkCoincidentSpans* coin = fHead; |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 356 | if (!coin) { |
| 357 | return false; |
| 358 | } |
| 359 | do { |
| 360 | if (coin->fCoinPtTStart == coinPtTStart && coin->fCoinPtTEnd == coinPtTEnd |
| 361 | && coin->fOppPtTStart == oppPtTStart && coin->fOppPtTEnd == oppPtTEnd |
| 362 | && coin->fFlipped == flipped) { |
| 363 | return true; |
| 364 | } |
| 365 | } while ((coin = coin->fNext)); |
| 366 | return false; |
| 367 | } |
| 368 | |
| 369 | // walk span sets in parallel, moving winding from one to the other |
| 370 | bool SkOpCoincidence::apply() { |
| 371 | SkCoincidentSpans* coin = fHead; |
| 372 | if (!coin) { |
| 373 | return true; |
| 374 | } |
| 375 | do { |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 376 | SkOpSpan* start = coin->fCoinPtTStart->span()->upCast(); |
caryclark | 182b499 | 2015-05-14 05:45:54 -0700 | [diff] [blame] | 377 | if (start->deleted()) { |
| 378 | continue; |
| 379 | } |
| 380 | SkOpSpanBase* end = coin->fCoinPtTEnd->span(); |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 381 | SkASSERT(start == start->starter(end)); |
| 382 | bool flipped = coin->fFlipped; |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 383 | SkOpSpan* oStart = (flipped ? coin->fOppPtTEnd : coin->fOppPtTStart)->span()->upCast(); |
caryclark | 182b499 | 2015-05-14 05:45:54 -0700 | [diff] [blame] | 384 | if (oStart->deleted()) { |
| 385 | continue; |
| 386 | } |
| 387 | SkOpSpanBase* oEnd = (flipped ? coin->fOppPtTStart : coin->fOppPtTEnd)->span(); |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 388 | SkASSERT(oStart == oStart->starter(oEnd)); |
| 389 | SkOpSegment* segment = start->segment(); |
| 390 | SkOpSegment* oSegment = oStart->segment(); |
| 391 | bool operandSwap = segment->operand() != oSegment->operand(); |
| 392 | if (flipped) { |
caryclark | 364a007 | 2015-12-14 08:43:21 -0800 | [diff] [blame] | 393 | if (oEnd->deleted()) { |
| 394 | continue; |
| 395 | } |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 396 | do { |
| 397 | SkOpSpanBase* oNext = oStart->next(); |
| 398 | if (oNext == oEnd) { |
| 399 | break; |
| 400 | } |
| 401 | oStart = oNext->upCast(); |
| 402 | } while (true); |
| 403 | } |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 404 | do { |
| 405 | int windValue = start->windValue(); |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 406 | int oppValue = start->oppValue(); |
caryclark | 1049f12 | 2015-04-20 08:31:59 -0700 | [diff] [blame] | 407 | int oWindValue = oStart->windValue(); |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 408 | int oOppValue = oStart->oppValue(); |
| 409 | // winding values are added or subtracted depending on direction and wind type |
| 410 | // same or opposite values are summed depending on the operand value |
caryclark | 1049f12 | 2015-04-20 08:31:59 -0700 | [diff] [blame] | 411 | int windDiff = operandSwap ? oOppValue : oWindValue; |
| 412 | int oWindDiff = operandSwap ? oppValue : windValue; |
| 413 | if (!flipped) { |
| 414 | windDiff = -windDiff; |
| 415 | oWindDiff = -oWindDiff; |
| 416 | } |
| 417 | if (windValue && (windValue > windDiff || (windValue == windDiff |
| 418 | && oWindValue <= oWindDiff))) { |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 419 | if (operandSwap) { |
| 420 | SkTSwap(oWindValue, oOppValue); |
| 421 | } |
| 422 | if (flipped) { |
| 423 | windValue -= oWindValue; |
| 424 | oppValue -= oOppValue; |
| 425 | } else { |
| 426 | windValue += oWindValue; |
| 427 | oppValue += oOppValue; |
| 428 | } |
caryclark | 1049f12 | 2015-04-20 08:31:59 -0700 | [diff] [blame] | 429 | if (segment->isXor()) { |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 430 | windValue &= 1; |
| 431 | } |
caryclark | 1049f12 | 2015-04-20 08:31:59 -0700 | [diff] [blame] | 432 | if (segment->oppXor()) { |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 433 | oppValue &= 1; |
| 434 | } |
| 435 | oWindValue = oOppValue = 0; |
| 436 | } else { |
| 437 | if (operandSwap) { |
| 438 | SkTSwap(windValue, oppValue); |
| 439 | } |
| 440 | if (flipped) { |
| 441 | oWindValue -= windValue; |
| 442 | oOppValue -= oppValue; |
| 443 | } else { |
| 444 | oWindValue += windValue; |
| 445 | oOppValue += oppValue; |
| 446 | } |
caryclark | 1049f12 | 2015-04-20 08:31:59 -0700 | [diff] [blame] | 447 | if (oSegment->isXor()) { |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 448 | oWindValue &= 1; |
| 449 | } |
caryclark | 1049f12 | 2015-04-20 08:31:59 -0700 | [diff] [blame] | 450 | if (oSegment->oppXor()) { |
| 451 | oOppValue &= 1; |
| 452 | } |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 453 | windValue = oppValue = 0; |
| 454 | } |
| 455 | start->setWindValue(windValue); |
| 456 | start->setOppValue(oppValue); |
| 457 | oStart->setWindValue(oWindValue); |
| 458 | oStart->setOppValue(oOppValue); |
| 459 | if (!windValue && !oppValue) { |
| 460 | segment->markDone(start); |
| 461 | } |
| 462 | if (!oWindValue && !oOppValue) { |
| 463 | oSegment->markDone(oStart); |
| 464 | } |
| 465 | SkOpSpanBase* next = start->next(); |
| 466 | SkOpSpanBase* oNext = flipped ? oStart->prev() : oStart->next(); |
| 467 | if (next == end) { |
| 468 | break; |
| 469 | } |
caryclark | 26ad22a | 2015-10-16 09:03:38 -0700 | [diff] [blame] | 470 | if (!next->upCastable()) { |
| 471 | return false; |
| 472 | } |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 473 | start = next->upCast(); |
caryclark | 1049f12 | 2015-04-20 08:31:59 -0700 | [diff] [blame] | 474 | // if the opposite ran out too soon, just reuse the last span |
| 475 | if (!oNext || !oNext->upCastable()) { |
| 476 | oNext = oStart; |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 477 | } |
| 478 | oStart = oNext->upCast(); |
| 479 | } while (true); |
| 480 | } while ((coin = coin->fNext)); |
| 481 | return true; |
| 482 | } |
| 483 | |
mtklein | 18300a3 | 2016-03-16 13:53:35 -0700 | [diff] [blame] | 484 | void SkOpCoincidence::release(SkCoincidentSpans* remove) { |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 485 | SkCoincidentSpans* coin = fHead; |
halcanary | 96fcdcc | 2015-08-27 07:41:13 -0700 | [diff] [blame] | 486 | SkCoincidentSpans* prev = nullptr; |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 487 | SkCoincidentSpans* next; |
| 488 | do { |
| 489 | next = coin->fNext; |
| 490 | if (coin == remove) { |
| 491 | if (prev) { |
| 492 | prev->fNext = next; |
| 493 | } else { |
| 494 | fHead = next; |
| 495 | } |
| 496 | break; |
| 497 | } |
| 498 | prev = coin; |
| 499 | } while ((coin = next)); |
| 500 | SkASSERT(coin); |
| 501 | } |
| 502 | |
caryclark | 27c8eb8 | 2015-07-06 11:38:33 -0700 | [diff] [blame] | 503 | bool SkOpCoincidence::expand() { |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 504 | SkCoincidentSpans* coin = fHead; |
| 505 | if (!coin) { |
caryclark | 27c8eb8 | 2015-07-06 11:38:33 -0700 | [diff] [blame] | 506 | return false; |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 507 | } |
caryclark | 27c8eb8 | 2015-07-06 11:38:33 -0700 | [diff] [blame] | 508 | bool expanded = false; |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 509 | do { |
| 510 | SkOpSpan* start = coin->fCoinPtTStart->span()->upCast(); |
| 511 | SkOpSpanBase* end = coin->fCoinPtTEnd->span(); |
| 512 | SkOpSegment* segment = coin->fCoinPtTStart->segment(); |
| 513 | SkOpSegment* oppSegment = coin->fOppPtTStart->segment(); |
| 514 | SkOpSpan* prev = start->prev(); |
| 515 | SkOpPtT* oppPtT; |
| 516 | if (prev && (oppPtT = prev->contains(oppSegment))) { |
| 517 | double midT = (prev->t() + start->t()) / 2; |
| 518 | if (segment->isClose(midT, oppSegment)) { |
| 519 | coin->fCoinPtTStart = prev->ptT(); |
| 520 | coin->fOppPtTStart = oppPtT; |
caryclark | 27c8eb8 | 2015-07-06 11:38:33 -0700 | [diff] [blame] | 521 | expanded = true; |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 522 | } |
| 523 | } |
halcanary | 96fcdcc | 2015-08-27 07:41:13 -0700 | [diff] [blame] | 524 | SkOpSpanBase* next = end->final() ? nullptr : end->upCast()->next(); |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 525 | if (next && (oppPtT = next->contains(oppSegment))) { |
| 526 | double midT = (end->t() + next->t()) / 2; |
| 527 | if (segment->isClose(midT, oppSegment)) { |
| 528 | coin->fCoinPtTEnd = next->ptT(); |
| 529 | coin->fOppPtTEnd = oppPtT; |
caryclark | 27c8eb8 | 2015-07-06 11:38:33 -0700 | [diff] [blame] | 530 | expanded = true; |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 531 | } |
| 532 | } |
| 533 | } while ((coin = coin->fNext)); |
caryclark | 27c8eb8 | 2015-07-06 11:38:33 -0700 | [diff] [blame] | 534 | return expanded; |
| 535 | } |
| 536 | |
| 537 | void SkOpCoincidence::findOverlaps(SkOpCoincidence* overlaps, SkChunkAlloc* allocator) const { |
halcanary | 96fcdcc | 2015-08-27 07:41:13 -0700 | [diff] [blame] | 538 | overlaps->fHead = overlaps->fTop = nullptr; |
caryclark | 27c8eb8 | 2015-07-06 11:38:33 -0700 | [diff] [blame] | 539 | SkDEBUGCODE_(overlaps->debugSetGlobalState(fDebugState)); |
| 540 | SkCoincidentSpans* outer = fHead; |
| 541 | while (outer) { |
| 542 | SkOpSegment* outerCoin = outer->fCoinPtTStart->segment(); |
| 543 | SkOpSegment* outerOpp = outer->fOppPtTStart->segment(); |
| 544 | SkCoincidentSpans* inner = outer; |
| 545 | while ((inner = inner->fNext)) { |
| 546 | SkOpSegment* innerCoin = inner->fCoinPtTStart->segment(); |
| 547 | if (outerCoin == innerCoin) { |
| 548 | continue; // both winners are the same segment, so there's no additional overlap |
| 549 | } |
| 550 | SkOpSegment* innerOpp = inner->fOppPtTStart->segment(); |
| 551 | SkOpPtT* overlapS, * overlapE; |
| 552 | if ((outerOpp == innerCoin && SkOpPtT::Overlaps(outer->fOppPtTStart, outer->fOppPtTEnd, |
| 553 | inner->fCoinPtTStart, inner->fCoinPtTEnd, &overlapS, &overlapE)) |
| 554 | || (outerCoin == innerOpp && SkOpPtT::Overlaps(outer->fCoinPtTStart, |
| 555 | outer->fCoinPtTEnd, inner->fOppPtTStart, inner->fOppPtTEnd, |
| 556 | &overlapS, &overlapE)) |
| 557 | || (outerOpp == innerOpp && SkOpPtT::Overlaps(outer->fOppPtTStart, |
| 558 | outer->fOppPtTEnd, inner->fOppPtTStart, inner->fOppPtTEnd, |
| 559 | &overlapS, &overlapE))) { |
| 560 | overlaps->addOverlap(outerCoin, outerOpp, innerCoin, innerOpp, |
| 561 | overlapS, overlapE, allocator); |
| 562 | } |
| 563 | } |
| 564 | outer = outer->fNext; |
| 565 | } |
| 566 | } |
| 567 | |
| 568 | void SkOpCoincidence::fixAligned() { |
| 569 | SkCoincidentSpans* coin = fHead; |
| 570 | if (!coin) { |
| 571 | return; |
| 572 | } |
| 573 | do { |
| 574 | if (coin->fCoinPtTStart->deleted()) { |
| 575 | coin->fCoinPtTStart = coin->fCoinPtTStart->doppelganger(); |
| 576 | } |
| 577 | if (coin->fCoinPtTEnd->deleted()) { |
| 578 | coin->fCoinPtTEnd = coin->fCoinPtTEnd->doppelganger(); |
| 579 | } |
| 580 | if (coin->fOppPtTStart->deleted()) { |
| 581 | coin->fOppPtTStart = coin->fOppPtTStart->doppelganger(); |
| 582 | } |
| 583 | if (coin->fOppPtTEnd->deleted()) { |
| 584 | coin->fOppPtTEnd = coin->fOppPtTEnd->doppelganger(); |
| 585 | } |
| 586 | } while ((coin = coin->fNext)); |
caryclark | d434972 | 2015-07-23 12:40:22 -0700 | [diff] [blame] | 587 | coin = fHead; |
| 588 | SkCoincidentSpans** priorPtr = &fHead; |
| 589 | do { |
| 590 | if (coin->fCoinPtTStart->collapsed(coin->fCoinPtTEnd) |
| 591 | || coin->fOppPtTStart->collapsed(coin->fOppPtTEnd)) { |
| 592 | *priorPtr = coin->fNext; |
| 593 | continue; |
| 594 | } |
| 595 | priorPtr = &coin->fNext; |
| 596 | } while ((coin = coin->fNext)); |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 597 | } |
| 598 | |
| 599 | void SkOpCoincidence::fixUp(SkOpPtT* deleted, SkOpPtT* kept) { |
| 600 | SkCoincidentSpans* coin = fHead; |
| 601 | if (!coin) { |
| 602 | return; |
| 603 | } |
| 604 | do { |
| 605 | if (coin->fCoinPtTStart == deleted) { |
| 606 | if (coin->fCoinPtTEnd->span() == kept->span()) { |
mtklein | 18300a3 | 2016-03-16 13:53:35 -0700 | [diff] [blame] | 607 | this->release(coin); |
caryclark | 27c8eb8 | 2015-07-06 11:38:33 -0700 | [diff] [blame] | 608 | continue; |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 609 | } |
| 610 | coin->fCoinPtTStart = kept; |
| 611 | } |
| 612 | if (coin->fCoinPtTEnd == deleted) { |
| 613 | if (coin->fCoinPtTStart->span() == kept->span()) { |
mtklein | 18300a3 | 2016-03-16 13:53:35 -0700 | [diff] [blame] | 614 | this->release(coin); |
caryclark | 27c8eb8 | 2015-07-06 11:38:33 -0700 | [diff] [blame] | 615 | continue; |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 616 | } |
| 617 | coin->fCoinPtTEnd = kept; |
| 618 | } |
| 619 | if (coin->fOppPtTStart == deleted) { |
| 620 | if (coin->fOppPtTEnd->span() == kept->span()) { |
mtklein | 18300a3 | 2016-03-16 13:53:35 -0700 | [diff] [blame] | 621 | this->release(coin); |
caryclark | 27c8eb8 | 2015-07-06 11:38:33 -0700 | [diff] [blame] | 622 | continue; |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 623 | } |
| 624 | coin->fOppPtTStart = kept; |
| 625 | } |
| 626 | if (coin->fOppPtTEnd == deleted) { |
| 627 | if (coin->fOppPtTStart->span() == kept->span()) { |
mtklein | 18300a3 | 2016-03-16 13:53:35 -0700 | [diff] [blame] | 628 | this->release(coin); |
caryclark | 27c8eb8 | 2015-07-06 11:38:33 -0700 | [diff] [blame] | 629 | continue; |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 630 | } |
| 631 | coin->fOppPtTEnd = kept; |
| 632 | } |
| 633 | } while ((coin = coin->fNext)); |
| 634 | } |
| 635 | |
caryclark | 27c8eb8 | 2015-07-06 11:38:33 -0700 | [diff] [blame] | 636 | /* this sets up the coincidence links in the segments when the coincidence crosses multiple spans */ |
caryclark | 5c5cfe2 | 2016-04-05 07:28:48 -0700 | [diff] [blame] | 637 | bool SkOpCoincidence::mark() { |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 638 | SkCoincidentSpans* coin = fHead; |
| 639 | if (!coin) { |
caryclark | 5c5cfe2 | 2016-04-05 07:28:48 -0700 | [diff] [blame] | 640 | return true; |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 641 | } |
| 642 | do { |
| 643 | SkOpSpanBase* end = coin->fCoinPtTEnd->span(); |
caryclark | 5c5cfe2 | 2016-04-05 07:28:48 -0700 | [diff] [blame] | 644 | if (end->deleted()) { |
| 645 | return false; |
| 646 | } |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 647 | SkOpSpanBase* oldEnd = end; |
| 648 | SkOpSpan* start = coin->fCoinPtTStart->span()->starter(&end); |
| 649 | SkOpSpanBase* oEnd = coin->fOppPtTEnd->span(); |
caryclark | 5c5cfe2 | 2016-04-05 07:28:48 -0700 | [diff] [blame] | 650 | if (oEnd->deleted()) { |
| 651 | return false; |
| 652 | } |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 653 | SkOpSpanBase* oOldEnd = oEnd; |
| 654 | SkOpSpanBase* oStart = coin->fOppPtTStart->span()->starter(&oEnd); |
| 655 | bool flipped = (end == oldEnd) != (oEnd == oOldEnd); |
| 656 | if (flipped) { |
| 657 | SkTSwap(oStart, oEnd); |
| 658 | } |
| 659 | SkOpSpanBase* next = start; |
| 660 | SkOpSpanBase* oNext = oStart; |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 661 | do { |
| 662 | next = next->upCast()->next(); |
| 663 | oNext = flipped ? oNext->prev() : oNext->upCast()->next(); |
| 664 | if (next == end || oNext == oEnd) { |
| 665 | break; |
| 666 | } |
| 667 | if (!next->containsCoinEnd(oNext)) { |
| 668 | next->insertCoinEnd(oNext); |
| 669 | } |
| 670 | SkOpSpan* nextSpan = next->upCast(); |
| 671 | SkOpSpan* oNextSpan = oNext->upCast(); |
| 672 | if (!nextSpan->containsCoincidence(oNextSpan)) { |
| 673 | nextSpan->insertCoincidence(oNextSpan); |
| 674 | } |
| 675 | } while (true); |
| 676 | } while ((coin = coin->fNext)); |
caryclark | 5c5cfe2 | 2016-04-05 07:28:48 -0700 | [diff] [blame] | 677 | return true; |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 678 | } |
| 679 | |
| 680 | bool SkOpCoincidence::overlap(const SkOpPtT* coin1s, const SkOpPtT* coin1e, |
| 681 | const SkOpPtT* coin2s, const SkOpPtT* coin2e, double* overS, double* overE) const { |
caryclark | 27c8eb8 | 2015-07-06 11:38:33 -0700 | [diff] [blame] | 682 | SkASSERT(coin1s->segment() == coin2s->segment()); |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 683 | *overS = SkTMax(SkTMin(coin1s->fT, coin1e->fT), SkTMin(coin2s->fT, coin2e->fT)); |
| 684 | *overE = SkTMin(SkTMax(coin1s->fT, coin1e->fT), SkTMax(coin2s->fT, coin2e->fT)); |
| 685 | return *overS < *overE; |
| 686 | } |
caryclark | 27c8eb8 | 2015-07-06 11:38:33 -0700 | [diff] [blame] | 687 | |
caryclark | 26ad22a | 2015-10-16 09:03:38 -0700 | [diff] [blame] | 688 | bool SkOpCoincidence::testForCoincidence(const SkCoincidentSpans* outer, const SkOpPtT* testS, |
| 689 | const SkOpPtT* testE) const { |
caryclark | 27c8eb8 | 2015-07-06 11:38:33 -0700 | [diff] [blame] | 690 | return testS->segment()->testForCoincidence(testS, testE, testS->span(), |
| 691 | testE->span(), outer->fCoinPtTStart->segment(), 120000); // FIXME: replace with tuned |
| 692 | } |