OLD | NEW |
1 /* | 1 /* |
2 * Copyright 2015 Google Inc. | 2 * Copyright 2015 Google Inc. |
3 * | 3 * |
4 * Use of this source code is governed by a BSD-style license that can be | 4 * Use of this source code is governed by a BSD-style license that can be |
5 * found in the LICENSE file. | 5 * found in the LICENSE file. |
6 */ | 6 */ |
7 #include "SkOpCoincidence.h" | 7 #include "SkOpCoincidence.h" |
8 #include "SkOpSegment.h" | 8 #include "SkOpSegment.h" |
9 #include "SkPathOpsTSect.h" | 9 #include "SkPathOpsTSect.h" |
10 | 10 |
(...skipping 47 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
58 const SkOpPtT* coinPtTStart, const SkOpPtT* coinPtTEnd, double* coinTs,
double* coinTe) { | 58 const SkOpPtT* coinPtTStart, const SkOpPtT* coinPtTEnd, double* coinTs,
double* coinTe) { |
59 double denom = overE->fT - overS->fT; | 59 double denom = overE->fT - overS->fT; |
60 double start = 0 < denom ? tStart : tEnd; | 60 double start = 0 < denom ? tStart : tEnd; |
61 double end = 0 < denom ? tEnd : tStart; | 61 double end = 0 < denom ? tEnd : tStart; |
62 double sRatio = (start - overS->fT) / denom; | 62 double sRatio = (start - overS->fT) / denom; |
63 double eRatio = (end - overS->fT) / denom; | 63 double eRatio = (end - overS->fT) / denom; |
64 *coinTs = coinPtTStart->fT + (coinPtTEnd->fT - coinPtTStart->fT) * sRatio; | 64 *coinTs = coinPtTStart->fT + (coinPtTEnd->fT - coinPtTStart->fT) * sRatio; |
65 *coinTe = coinPtTStart->fT + (coinPtTEnd->fT - coinPtTStart->fT) * eRatio; | 65 *coinTe = coinPtTStart->fT + (coinPtTEnd->fT - coinPtTStart->fT) * eRatio; |
66 } | 66 } |
67 | 67 |
| 68 void SkOpCoincidence::addExpanded(SkChunkAlloc* allocator |
| 69 PATH_OPS_DEBUG_VALIDATE_PARAMS(SkOpGlobalState* globalState)) { |
| 70 #if DEBUG_VALIDATE |
| 71 globalState->setPhase(SkOpGlobalState::kIntersecting); |
| 72 #endif |
| 73 // for each coincident pair, match the spans |
| 74 // if the spans don't match, add the mssing pt to the segment and loop it in
the opposite span |
| 75 SkCoincidentSpans* coin = this->fHead; |
| 76 SkASSERT(coin); |
| 77 do { |
| 78 SkOpPtT* startPtT = coin->fCoinPtTStart; |
| 79 SkOpPtT* oStartPtT = coin->fOppPtTStart; |
| 80 SkASSERT(startPtT->contains(oStartPtT)); |
| 81 SkASSERT(coin->fCoinPtTEnd->contains(coin->fOppPtTEnd)); |
| 82 SkOpSpanBase* start = startPtT->span(); |
| 83 SkOpSpanBase* oStart = oStartPtT->span(); |
| 84 const SkOpSpanBase* end = coin->fCoinPtTEnd->span(); |
| 85 const SkOpSpanBase* oEnd = coin->fOppPtTEnd->span(); |
| 86 SkOpSpanBase* test = start->upCast()->next(); |
| 87 SkOpSpanBase* oTest = coin->fFlipped ? oStart->prev() : oStart->upCast()
->next(); |
| 88 while (test != end || oTest != oEnd) { |
| 89 if (!test->ptT()->contains(oTest->ptT())) { |
| 90 // use t ranges to guess which one is missing |
| 91 double startRange = coin->fCoinPtTEnd->fT - startPtT->fT; |
| 92 double startPart = (test->t() - startPtT->fT) / startRange; |
| 93 double oStartRange = coin->fOppPtTEnd->fT - oStartPtT->fT; |
| 94 double oStartPart = (oTest->t() - oStartPtT->fT) / oStartRange; |
| 95 SkASSERT(startPart != oStartPart); |
| 96 SkOpPtT* newPt; |
| 97 if (startPart < oStartPart) { |
| 98 double newT = oStartPtT->fT + oStartRange * startPart; |
| 99 newPt = oStart->segment()->addT(newT, SkOpSegment::kAllowAli
as, allocator); |
| 100 newPt->fPt = test->pt(); |
| 101 test->ptT()->addOpp(newPt); |
| 102 } else { |
| 103 double newT = startPtT->fT + startRange * oStartPart; |
| 104 newPt = start->segment()->addT(newT, SkOpSegment::kAllowAlia
s, allocator); |
| 105 newPt->fPt = oTest->pt(); |
| 106 oTest->ptT()->addOpp(newPt); |
| 107 } |
| 108 // start over |
| 109 test = start; |
| 110 oTest = oStart; |
| 111 } |
| 112 if (test != end) { |
| 113 test = test->upCast()->next(); |
| 114 } |
| 115 if (oStart != oEnd) { |
| 116 oTest = coin->fFlipped ? oTest->prev() : oTest->upCast()->next()
; |
| 117 } |
| 118 } |
| 119 } while ((coin = coin->fNext)); |
| 120 #if DEBUG_VALIDATE |
| 121 globalState->setPhase(SkOpGlobalState::kWalking); |
| 122 #endif |
| 123 } |
| 124 |
| 125 void SkOpCoincidence::addIfMissing(const SkCoincidentSpans* outer, SkOpPtT* over
1s, |
| 126 SkOpPtT* over1e, SkChunkAlloc* allocator) { |
| 127 SkCoincidentSpans* check = this->fTop; |
| 128 do { |
| 129 if (check->fCoinPtTStart->span() == over1s->span() |
| 130 && check->fOppPtTStart->span() == outer->fOppPtTStart->span()) { |
| 131 SkASSERT(check->fCoinPtTEnd->span() == over1e->span() |
| 132 || !fDebugState->debugRunFail()); |
| 133 SkASSERT(check->fOppPtTEnd->span() == outer->fOppPtTEnd->span() |
| 134 || !fDebugState->debugRunFail()); |
| 135 return; |
| 136 } |
| 137 if (check->fCoinPtTStart->span() == outer->fCoinPtTStart->span() |
| 138 && check->fOppPtTStart->span() == over1s->span()) { |
| 139 SkASSERT(check->fCoinPtTEnd->span() == outer->fCoinPtTEnd->span() |
| 140 || !fDebugState->debugRunFail()); |
| 141 SkASSERT(check->fOppPtTEnd->span() == over1e->span() |
| 142 || !fDebugState->debugRunFail()); |
| 143 return; |
| 144 } |
| 145 } while ((check = check->fNext)); |
| 146 this->add(outer->fCoinPtTStart, outer->fCoinPtTEnd, over1s, over1e, allocato
r); |
| 147 #if 0 |
| 148 // FIXME: up to four flavors could be added -- do we need only one? |
| 149 #endif |
| 150 } |
| 151 |
68 bool SkOpCoincidence::addIfMissing(const SkOpPtT* over1s, const SkOpPtT* over1e, | 152 bool SkOpCoincidence::addIfMissing(const SkOpPtT* over1s, const SkOpPtT* over1e, |
69 const SkOpPtT* over2s, const SkOpPtT* over2e, double tStar
t, double tEnd, | 153 const SkOpPtT* over2s, const SkOpPtT* over2e, double tStar
t, double tEnd, |
70 SkOpPtT* coinPtTStart, const SkOpPtT* coinPtTEnd, | 154 SkOpPtT* coinPtTStart, const SkOpPtT* coinPtTEnd, |
71 SkOpPtT* oppPtTStart, const SkOpPtT* oppPtTEnd, SkChunkAlloc* allocator)
{ | 155 SkOpPtT* oppPtTStart, const SkOpPtT* oppPtTEnd, SkChunkAlloc* allocator)
{ |
72 double coinTs, coinTe, oppTs, oppTe; | 156 double coinTs, coinTe, oppTs, oppTe; |
73 t_range(over1s, over1e, tStart, tEnd, coinPtTStart, coinPtTEnd, &coinTs, &co
inTe); | 157 t_range(over1s, over1e, tStart, tEnd, coinPtTStart, coinPtTEnd, &coinTs, &co
inTe); |
74 t_range(over2s, over2e, tStart, tEnd, oppPtTStart, oppPtTEnd, &oppTs, &oppTe
); | 158 t_range(over2s, over2e, tStart, tEnd, oppPtTStart, oppPtTEnd, &oppTs, &oppTe
); |
75 SkOpSegment* coinSeg = coinPtTStart->segment(); | 159 SkOpSegment* coinSeg = coinPtTStart->segment(); |
76 SkOpSegment* oppSeg = oppPtTStart->segment(); | 160 SkOpSegment* oppSeg = oppPtTStart->segment(); |
77 SkASSERT(coinSeg != oppSeg); | 161 SkASSERT(coinSeg != oppSeg); |
78 SkCoincidentSpans* check = this->fHead; | 162 SkCoincidentSpans* check = this->fTop; |
79 do { | 163 do { |
80 const SkOpSegment* checkCoinSeg = check->fCoinPtTStart->segment(); | 164 const SkOpSegment* checkCoinSeg = check->fCoinPtTStart->segment(); |
81 if (checkCoinSeg != coinSeg && checkCoinSeg != oppSeg) { | 165 if (checkCoinSeg != coinSeg && checkCoinSeg != oppSeg) { |
82 continue; | 166 continue; |
83 } | 167 } |
84 const SkOpSegment* checkOppSeg = check->fOppPtTStart->segment(); | 168 const SkOpSegment* checkOppSeg = check->fOppPtTStart->segment(); |
85 if (checkOppSeg != coinSeg && checkOppSeg != oppSeg) { | 169 if (checkOppSeg != coinSeg && checkOppSeg != oppSeg) { |
86 continue; | 170 continue; |
87 } | 171 } |
88 int cTs = coinTs; | 172 int cTs = coinTs; |
(...skipping 28 matching lines...) Expand all Loading... |
117 } | 201 } |
118 SkOpPtT* os = oppSeg->addMissing(oppTs, coinSeg, allocator); | 202 SkOpPtT* os = oppSeg->addMissing(oppTs, coinSeg, allocator); |
119 SkOpPtT* oe = oppSeg->addMissing(oppTe, coinSeg, allocator); | 203 SkOpPtT* oe = oppSeg->addMissing(oppTe, coinSeg, allocator); |
120 SkASSERT(os != oe); | 204 SkASSERT(os != oe); |
121 cs->addOpp(os); | 205 cs->addOpp(os); |
122 ce->addOpp(oe); | 206 ce->addOpp(oe); |
123 this->add(cs, ce, os, oe, allocator); | 207 this->add(cs, ce, os, oe, allocator); |
124 return true; | 208 return true; |
125 } | 209 } |
126 | 210 |
| 211 /* detects overlaps of different coincident runs on same segment */ |
| 212 /* does not detect overlaps for pairs without any segments in common */ |
127 bool SkOpCoincidence::addMissing(SkChunkAlloc* allocator) { | 213 bool SkOpCoincidence::addMissing(SkChunkAlloc* allocator) { |
128 SkCoincidentSpans* outer = this->fHead; | 214 SkCoincidentSpans* outer = fHead; |
129 if (!outer) { | 215 if (!outer) { |
130 return true; | 216 return true; |
131 } | 217 } |
| 218 bool result; |
| 219 fTop = outer; |
| 220 fHead = NULL; |
132 do { | 221 do { |
| 222 // addifmissing can modify the list that this is walking |
| 223 // maybe save head so that walker can iterate over old data unperturbed |
| 224 // and addifmissing can add to head freely then add saved head in the end |
| 225 const SkOpSegment* outerCoin = outer->fCoinPtTStart->segment(); |
| 226 SkASSERT(outerCoin == outer->fCoinPtTEnd->segment()); |
| 227 const SkOpSegment* outerOpp = outer->fOppPtTStart->segment(); |
| 228 SkASSERT(outerOpp == outer->fOppPtTEnd->segment()); |
133 SkCoincidentSpans* inner = outer; | 229 SkCoincidentSpans* inner = outer; |
134 while ((inner = inner->fNext)) { | 230 while ((inner = inner->fNext)) { |
135 double overS, overE; | 231 double overS, overE; |
136 if (this->overlap(outer->fCoinPtTStart, outer->fCoinPtTEnd, | 232 const SkOpSegment* innerCoin = inner->fCoinPtTStart->segment(); |
| 233 SkASSERT(innerCoin == inner->fCoinPtTEnd->segment()); |
| 234 const SkOpSegment* innerOpp = inner->fOppPtTStart->segment(); |
| 235 SkASSERT(innerOpp == inner->fOppPtTEnd->segment()); |
| 236 if (outerCoin == innerCoin |
| 237 && this->overlap(outer->fCoinPtTStart, outer->fCoinPtTEnd, |
137 inner->fCoinPtTStart, inner->fCoinPtTEnd, &overS, &overE)) { | 238 inner->fCoinPtTStart, inner->fCoinPtTEnd, &overS, &overE)) { |
138 if (!this->addIfMissing(outer->fCoinPtTStart, outer->fCoinPtTEnd
, | 239 if (!this->addIfMissing(outer->fCoinPtTStart, outer->fCoinPtTEnd
, |
139 inner->fCoinPtTStart, inner->fCoinPtTEnd, overS, overE, | 240 inner->fCoinPtTStart, inner->fCoinPtTEnd, overS, overE, |
140 outer->fOppPtTStart, outer->fOppPtTEnd, | 241 outer->fOppPtTStart, outer->fOppPtTEnd, |
141 inner->fOppPtTStart, inner->fOppPtTEnd, allocator)) { | 242 inner->fOppPtTStart, inner->fOppPtTEnd, allocator)) { |
142 return false; | 243 result = false; |
| 244 goto returnResult; |
143 } | 245 } |
144 } else if (this->overlap(outer->fCoinPtTStart, outer->fCoinPtTEnd, | 246 } else if (outerCoin == innerOpp |
| 247 && this->overlap(outer->fCoinPtTStart, outer->fCoinPtTEnd, |
145 inner->fOppPtTStart, inner->fOppPtTEnd, &overS, &overE)) { | 248 inner->fOppPtTStart, inner->fOppPtTEnd, &overS, &overE)) { |
146 if (!this->addIfMissing(outer->fCoinPtTStart, outer->fCoinPtTEnd
, | 249 if (!this->addIfMissing(outer->fCoinPtTStart, outer->fCoinPtTEnd
, |
147 inner->fOppPtTStart, inner->fOppPtTEnd, overS, overE, | 250 inner->fOppPtTStart, inner->fOppPtTEnd, overS, overE, |
148 outer->fOppPtTStart, outer->fOppPtTEnd, | 251 outer->fOppPtTStart, outer->fOppPtTEnd, |
149 inner->fCoinPtTStart, inner->fCoinPtTEnd, allocator)) { | 252 inner->fCoinPtTStart, inner->fCoinPtTEnd, allocator)) { |
150 return false; | 253 result = false; |
| 254 goto returnResult; |
151 } | 255 } |
152 } else if (this->overlap(outer->fOppPtTStart, outer->fOppPtTEnd, | 256 } else if (outerOpp == innerCoin |
| 257 && this->overlap(outer->fOppPtTStart, outer->fOppPtTEnd, |
153 inner->fCoinPtTStart, inner->fCoinPtTEnd, &overS, &overE)) { | 258 inner->fCoinPtTStart, inner->fCoinPtTEnd, &overS, &overE)) { |
154 if (!this->addIfMissing(outer->fOppPtTStart, outer->fOppPtTEnd, | 259 if (!this->addIfMissing(outer->fOppPtTStart, outer->fOppPtTEnd, |
155 inner->fCoinPtTStart, inner->fCoinPtTEnd, overS, overE, | 260 inner->fCoinPtTStart, inner->fCoinPtTEnd, overS, overE, |
156 outer->fCoinPtTStart, outer->fCoinPtTEnd, | 261 outer->fCoinPtTStart, outer->fCoinPtTEnd, |
157 inner->fOppPtTStart, inner->fOppPtTEnd, allocator)) { | 262 inner->fOppPtTStart, inner->fOppPtTEnd, allocator)) { |
158 return false; | 263 result = false; |
| 264 goto returnResult; |
159 } | 265 } |
160 } else if (this->overlap(outer->fOppPtTStart, outer->fOppPtTEnd, | 266 } else if (outerOpp == innerOpp |
| 267 && this->overlap(outer->fOppPtTStart, outer->fOppPtTEnd, |
161 inner->fOppPtTStart, inner->fOppPtTEnd, &overS, &overE)) { | 268 inner->fOppPtTStart, inner->fOppPtTEnd, &overS, &overE)) { |
162 if (!this->addIfMissing(outer->fOppPtTStart, outer->fOppPtTEnd, | 269 if (!this->addIfMissing(outer->fOppPtTStart, outer->fOppPtTEnd, |
163 inner->fOppPtTStart, inner->fOppPtTEnd, overS, overE, | 270 inner->fOppPtTStart, inner->fOppPtTEnd, overS, overE, |
164 outer->fCoinPtTStart, outer->fCoinPtTEnd, | 271 outer->fCoinPtTStart, outer->fCoinPtTEnd, |
165 inner->fCoinPtTStart, inner->fCoinPtTEnd, allocator)) { | 272 inner->fCoinPtTStart, inner->fCoinPtTEnd, allocator)) { |
166 return false; | 273 result = false; |
| 274 goto returnResult; |
| 275 } |
| 276 } else if (outerCoin != innerCoin) { |
| 277 // check to see if outer span overlaps the inner span |
| 278 // look for inner segment in pt-t list |
| 279 // if present, and if t values are in coincident range |
| 280 // add two pairs of new coincidence |
| 281 SkOpPtT* testS = outer->fCoinPtTStart->contains(innerCoin); |
| 282 SkOpPtT* testE = outer->fCoinPtTEnd->contains(innerCoin); |
| 283 if (testS && testS->fT >= inner->fCoinPtTStart->fT |
| 284 && testE && testE->fT <= inner->fCoinPtTEnd->fT |
| 285 && this->testForCoincidence(outer, testS, testE)) { |
| 286 this->addIfMissing(outer, testS, testE, allocator); |
| 287 } else { |
| 288 testS = inner->fCoinPtTStart->contains(outerCoin); |
| 289 testE = inner->fCoinPtTEnd->contains(outerCoin); |
| 290 if (testS && testS->fT >= outer->fCoinPtTStart->fT |
| 291 && testE && testE->fT <= outer->fCoinPtTEnd->fT |
| 292 && this->testForCoincidence(inner, testS, testE)) { |
| 293 this->addIfMissing(inner, testS, testE, allocator); |
| 294 } |
167 } | 295 } |
168 } | 296 } |
169 } | 297 } |
| 298 } while ((outer = outer->fNext)); |
| 299 result = true; |
| 300 returnResult: |
| 301 SkCoincidentSpans** headPtr = &fHead; |
| 302 while (*headPtr) { |
| 303 SkCoincidentSpans** headNext = &(*headPtr)->fNext; |
| 304 if (*headNext) { |
| 305 break; |
| 306 } |
| 307 headPtr = headNext; |
| 308 } |
| 309 *headPtr = fTop; |
| 310 return result; |
| 311 } |
170 | 312 |
171 } while ((outer = outer->fNext)); | 313 void SkOpCoincidence::addOverlap(SkOpSegment* seg1, SkOpSegment* seg1o, SkOpSegm
ent* seg2, |
172 return true; | 314 SkOpSegment* seg2o, SkOpPtT* overS, SkOpPtT* overE, SkChunkAlloc* alloca
tor) { |
| 315 SkOpPtT* s1 = overS->find(seg1); |
| 316 SkOpPtT* e1 = overE->find(seg1); |
| 317 if (!s1->starter(e1)->span()->upCast()->windValue()) { |
| 318 s1 = overS->find(seg1o); |
| 319 e1 = overE->find(seg1o); |
| 320 if (!s1->starter(e1)->span()->upCast()->windValue()) { |
| 321 return; |
| 322 } |
| 323 } |
| 324 SkOpPtT* s2 = overS->find(seg2); |
| 325 SkOpPtT* e2 = overE->find(seg2); |
| 326 if (!s2->starter(e2)->span()->upCast()->windValue()) { |
| 327 s2 = overS->find(seg2o); |
| 328 e2 = overE->find(seg2o); |
| 329 if (!s2->starter(e2)->span()->upCast()->windValue()) { |
| 330 return; |
| 331 } |
| 332 } |
| 333 if (s1->segment() == s2->segment()) { |
| 334 return; |
| 335 } |
| 336 if (s1->fT > e1->fT) { |
| 337 SkTSwap(s1, e1); |
| 338 SkTSwap(s2, e2); |
| 339 } |
| 340 this->add(s1, e1, s2, e2, allocator); |
173 } | 341 } |
174 | 342 |
175 bool SkOpCoincidence::contains(SkOpPtT* coinPtTStart, SkOpPtT* coinPtTEnd, SkOpP
tT* oppPtTStart, | 343 bool SkOpCoincidence::contains(SkOpPtT* coinPtTStart, SkOpPtT* coinPtTEnd, SkOpP
tT* oppPtTStart, |
176 SkOpPtT* oppPtTEnd, bool flipped) { | 344 SkOpPtT* oppPtTEnd, bool flipped) { |
177 SkCoincidentSpans* coin = fHead; | 345 SkCoincidentSpans* coin = fHead; |
178 if (!coin) { | 346 if (!coin) { |
179 return false; | 347 return false; |
180 } | 348 } |
181 do { | 349 do { |
182 if (coin->fCoinPtTStart == coinPtTStart && coin->fCoinPtTEnd == coinPtT
End | 350 if (coin->fCoinPtTStart == coinPtTStart && coin->fCoinPtTEnd == coinPtT
End |
(...skipping 126 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
309 } else { | 477 } else { |
310 fHead = next; | 478 fHead = next; |
311 } | 479 } |
312 break; | 480 break; |
313 } | 481 } |
314 prev = coin; | 482 prev = coin; |
315 } while ((coin = next)); | 483 } while ((coin = next)); |
316 SkASSERT(coin); | 484 SkASSERT(coin); |
317 } | 485 } |
318 | 486 |
319 void SkOpCoincidence::expand() { | 487 bool SkOpCoincidence::expand() { |
320 SkCoincidentSpans* coin = fHead; | 488 SkCoincidentSpans* coin = fHead; |
321 if (!coin) { | 489 if (!coin) { |
322 return; | 490 return false; |
323 } | 491 } |
| 492 bool expanded = false; |
324 do { | 493 do { |
325 SkOpSpan* start = coin->fCoinPtTStart->span()->upCast(); | 494 SkOpSpan* start = coin->fCoinPtTStart->span()->upCast(); |
326 SkOpSpanBase* end = coin->fCoinPtTEnd->span(); | 495 SkOpSpanBase* end = coin->fCoinPtTEnd->span(); |
327 SkOpSegment* segment = coin->fCoinPtTStart->segment(); | 496 SkOpSegment* segment = coin->fCoinPtTStart->segment(); |
328 SkOpSegment* oppSegment = coin->fOppPtTStart->segment(); | 497 SkOpSegment* oppSegment = coin->fOppPtTStart->segment(); |
329 SkOpSpan* prev = start->prev(); | 498 SkOpSpan* prev = start->prev(); |
330 SkOpPtT* oppPtT; | 499 SkOpPtT* oppPtT; |
331 if (prev && (oppPtT = prev->contains(oppSegment))) { | 500 if (prev && (oppPtT = prev->contains(oppSegment))) { |
332 double midT = (prev->t() + start->t()) / 2; | 501 double midT = (prev->t() + start->t()) / 2; |
333 if (segment->isClose(midT, oppSegment)) { | 502 if (segment->isClose(midT, oppSegment)) { |
334 coin->fCoinPtTStart = prev->ptT(); | 503 coin->fCoinPtTStart = prev->ptT(); |
335 coin->fOppPtTStart = oppPtT; | 504 coin->fOppPtTStart = oppPtT; |
| 505 expanded = true; |
336 } | 506 } |
337 } | 507 } |
338 SkOpSpanBase* next = end->final() ? NULL : end->upCast()->next(); | 508 SkOpSpanBase* next = end->final() ? NULL : end->upCast()->next(); |
339 if (next && (oppPtT = next->contains(oppSegment))) { | 509 if (next && (oppPtT = next->contains(oppSegment))) { |
340 double midT = (end->t() + next->t()) / 2; | 510 double midT = (end->t() + next->t()) / 2; |
341 if (segment->isClose(midT, oppSegment)) { | 511 if (segment->isClose(midT, oppSegment)) { |
342 coin->fCoinPtTEnd = next->ptT(); | 512 coin->fCoinPtTEnd = next->ptT(); |
343 coin->fOppPtTEnd = oppPtT; | 513 coin->fOppPtTEnd = oppPtT; |
| 514 expanded = true; |
344 } | 515 } |
345 } | 516 } |
346 } while ((coin = coin->fNext)); | 517 } while ((coin = coin->fNext)); |
| 518 return expanded; |
347 } | 519 } |
| 520 |
| 521 void SkOpCoincidence::findOverlaps(SkOpCoincidence* overlaps, SkChunkAlloc* allo
cator) const { |
| 522 overlaps->fHead = overlaps->fTop = NULL; |
| 523 SkDEBUGCODE_(overlaps->debugSetGlobalState(fDebugState)); |
| 524 SkCoincidentSpans* outer = fHead; |
| 525 while (outer) { |
| 526 SkOpSegment* outerCoin = outer->fCoinPtTStart->segment(); |
| 527 SkOpSegment* outerOpp = outer->fOppPtTStart->segment(); |
| 528 SkCoincidentSpans* inner = outer; |
| 529 while ((inner = inner->fNext)) { |
| 530 SkOpSegment* innerCoin = inner->fCoinPtTStart->segment(); |
| 531 if (outerCoin == innerCoin) { |
| 532 continue; // both winners are the same segment, so there's no a
dditional overlap |
| 533 } |
| 534 SkOpSegment* innerOpp = inner->fOppPtTStart->segment(); |
| 535 SkOpPtT* overlapS, * overlapE; |
| 536 if ((outerOpp == innerCoin && SkOpPtT::Overlaps(outer->fOppPtTStart,
outer->fOppPtTEnd, |
| 537 inner->fCoinPtTStart, inner->fCoinPtTEnd, &overlapS, &overla
pE)) |
| 538 || (outerCoin == innerOpp && SkOpPtT::Overlaps(outer->fCoinP
tTStart, |
| 539 outer->fCoinPtTEnd, inner->fOppPtTStart, inner->fOppPtTEnd, |
| 540 &overlapS, &overlapE)) |
| 541 || (outerOpp == innerOpp && SkOpPtT::Overlaps(outer->fOppPtT
Start, |
| 542 outer->fOppPtTEnd, inner->fOppPtTStart, inner->fOppPtTEnd, |
| 543 &overlapS, &overlapE))) { |
| 544 overlaps->addOverlap(outerCoin, outerOpp, innerCoin, innerOpp, |
| 545 overlapS, overlapE, allocator); |
| 546 } |
| 547 } |
| 548 outer = outer->fNext; |
| 549 } |
| 550 } |
| 551 |
| 552 void SkOpCoincidence::fixAligned() { |
| 553 SkCoincidentSpans* coin = fHead; |
| 554 if (!coin) { |
| 555 return; |
| 556 } |
| 557 do { |
| 558 if (coin->fCoinPtTStart->deleted()) { |
| 559 coin->fCoinPtTStart = coin->fCoinPtTStart->doppelganger(); |
| 560 } |
| 561 if (coin->fCoinPtTEnd->deleted()) { |
| 562 coin->fCoinPtTEnd = coin->fCoinPtTEnd->doppelganger(); |
| 563 } |
| 564 if (coin->fOppPtTStart->deleted()) { |
| 565 coin->fOppPtTStart = coin->fOppPtTStart->doppelganger(); |
| 566 } |
| 567 if (coin->fOppPtTEnd->deleted()) { |
| 568 coin->fOppPtTEnd = coin->fOppPtTEnd->doppelganger(); |
| 569 } |
| 570 } while ((coin = coin->fNext)); |
| 571 } |
348 | 572 |
349 void SkOpCoincidence::fixUp(SkOpPtT* deleted, SkOpPtT* kept) { | 573 void SkOpCoincidence::fixUp(SkOpPtT* deleted, SkOpPtT* kept) { |
350 SkCoincidentSpans* coin = fHead; | 574 SkCoincidentSpans* coin = fHead; |
351 if (!coin) { | 575 if (!coin) { |
352 return; | 576 return; |
353 } | 577 } |
354 do { | 578 do { |
355 if (coin->fCoinPtTStart == deleted) { | 579 if (coin->fCoinPtTStart == deleted) { |
356 if (coin->fCoinPtTEnd->span() == kept->span()) { | 580 if (coin->fCoinPtTEnd->span() == kept->span()) { |
357 return this->detach(coin); | 581 this->detach(coin); |
| 582 continue; |
358 } | 583 } |
359 coin->fCoinPtTStart = kept; | 584 coin->fCoinPtTStart = kept; |
360 } | 585 } |
361 if (coin->fCoinPtTEnd == deleted) { | 586 if (coin->fCoinPtTEnd == deleted) { |
362 if (coin->fCoinPtTStart->span() == kept->span()) { | 587 if (coin->fCoinPtTStart->span() == kept->span()) { |
363 return this->detach(coin); | 588 this->detach(coin); |
| 589 continue; |
364 } | 590 } |
365 coin->fCoinPtTEnd = kept; | 591 coin->fCoinPtTEnd = kept; |
366 } | 592 } |
367 if (coin->fOppPtTStart == deleted) { | 593 if (coin->fOppPtTStart == deleted) { |
368 if (coin->fOppPtTEnd->span() == kept->span()) { | 594 if (coin->fOppPtTEnd->span() == kept->span()) { |
369 return this->detach(coin); | 595 this->detach(coin); |
| 596 continue; |
370 } | 597 } |
371 coin->fOppPtTStart = kept; | 598 coin->fOppPtTStart = kept; |
372 } | 599 } |
373 if (coin->fOppPtTEnd == deleted) { | 600 if (coin->fOppPtTEnd == deleted) { |
374 if (coin->fOppPtTStart->span() == kept->span()) { | 601 if (coin->fOppPtTStart->span() == kept->span()) { |
375 return this->detach(coin); | 602 this->detach(coin); |
| 603 continue; |
376 } | 604 } |
377 coin->fOppPtTEnd = kept; | 605 coin->fOppPtTEnd = kept; |
378 } | 606 } |
379 } while ((coin = coin->fNext)); | 607 } while ((coin = coin->fNext)); |
380 } | 608 } |
381 | 609 |
| 610 /* this sets up the coincidence links in the segments when the coincidence cross
es multiple spans */ |
382 void SkOpCoincidence::mark() { | 611 void SkOpCoincidence::mark() { |
383 SkCoincidentSpans* coin = fHead; | 612 SkCoincidentSpans* coin = fHead; |
384 if (!coin) { | 613 if (!coin) { |
385 return; | 614 return; |
386 } | 615 } |
387 do { | 616 do { |
388 SkOpSpanBase* end = coin->fCoinPtTEnd->span(); | 617 SkOpSpanBase* end = coin->fCoinPtTEnd->span(); |
389 SkOpSpanBase* oldEnd = end; | 618 SkOpSpanBase* oldEnd = end; |
390 SkOpSpan* start = coin->fCoinPtTStart->span()->starter(&end); | 619 SkOpSpan* start = coin->fCoinPtTStart->span()->starter(&end); |
391 SkOpSpanBase* oEnd = coin->fOppPtTEnd->span(); | 620 SkOpSpanBase* oEnd = coin->fOppPtTEnd->span(); |
392 SkOpSpanBase* oOldEnd = oEnd; | 621 SkOpSpanBase* oOldEnd = oEnd; |
393 SkOpSpanBase* oStart = coin->fOppPtTStart->span()->starter(&oEnd); | 622 SkOpSpanBase* oStart = coin->fOppPtTStart->span()->starter(&oEnd); |
394 bool flipped = (end == oldEnd) != (oEnd == oOldEnd); | 623 bool flipped = (end == oldEnd) != (oEnd == oOldEnd); |
395 if (flipped) { | 624 if (flipped) { |
396 SkTSwap(oStart, oEnd); | 625 SkTSwap(oStart, oEnd); |
397 } | 626 } |
398 SkOpSpanBase* next = start; | 627 SkOpSpanBase* next = start; |
399 SkOpSpanBase* oNext = oStart; | 628 SkOpSpanBase* oNext = oStart; |
400 // check to see if coincident span could be bigger | |
401 | |
402 do { | 629 do { |
403 next = next->upCast()->next(); | 630 next = next->upCast()->next(); |
404 oNext = flipped ? oNext->prev() : oNext->upCast()->next(); | 631 oNext = flipped ? oNext->prev() : oNext->upCast()->next(); |
405 if (next == end || oNext == oEnd) { | 632 if (next == end || oNext == oEnd) { |
406 break; | 633 break; |
407 } | 634 } |
408 if (!next->containsCoinEnd(oNext)) { | 635 if (!next->containsCoinEnd(oNext)) { |
409 next->insertCoinEnd(oNext); | 636 next->insertCoinEnd(oNext); |
410 } | 637 } |
411 SkOpSpan* nextSpan = next->upCast(); | 638 SkOpSpan* nextSpan = next->upCast(); |
412 SkOpSpan* oNextSpan = oNext->upCast(); | 639 SkOpSpan* oNextSpan = oNext->upCast(); |
413 if (!nextSpan->containsCoincidence(oNextSpan)) { | 640 if (!nextSpan->containsCoincidence(oNextSpan)) { |
414 nextSpan->insertCoincidence(oNextSpan); | 641 nextSpan->insertCoincidence(oNextSpan); |
415 } | 642 } |
416 } while (true); | 643 } while (true); |
417 } while ((coin = coin->fNext)); | 644 } while ((coin = coin->fNext)); |
418 } | 645 } |
419 | 646 |
420 bool SkOpCoincidence::overlap(const SkOpPtT* coin1s, const SkOpPtT* coin1e, | 647 bool SkOpCoincidence::overlap(const SkOpPtT* coin1s, const SkOpPtT* coin1e, |
421 const SkOpPtT* coin2s, const SkOpPtT* coin2e, double* overS, double* ove
rE) const { | 648 const SkOpPtT* coin2s, const SkOpPtT* coin2e, double* overS, double* ove
rE) const { |
422 if (coin1s->segment() != coin2s->segment()) { | 649 SkASSERT(coin1s->segment() == coin2s->segment()); |
423 return false; | |
424 } | |
425 *overS = SkTMax(SkTMin(coin1s->fT, coin1e->fT), SkTMin(coin2s->fT, coin2e->f
T)); | 650 *overS = SkTMax(SkTMin(coin1s->fT, coin1e->fT), SkTMin(coin2s->fT, coin2e->f
T)); |
426 *overE = SkTMin(SkTMax(coin1s->fT, coin1e->fT), SkTMax(coin2s->fT, coin2e->f
T)); | 651 *overE = SkTMin(SkTMax(coin1s->fT, coin1e->fT), SkTMax(coin2s->fT, coin2e->f
T)); |
427 return *overS < *overE; | 652 return *overS < *overE; |
428 } | 653 } |
| 654 |
| 655 bool SkOpCoincidence::testForCoincidence(const SkCoincidentSpans* outer, SkOpPtT
* testS, |
| 656 SkOpPtT* testE) const { |
| 657 return testS->segment()->testForCoincidence(testS, testE, testS->span(), |
| 658 testE->span(), outer->fCoinPtTStart->segment(), 120000); // FIXME:
replace with tuned |
| 659 } |
OLD | NEW |