| OLD | NEW |
|---|
| (Empty) |
| 1 /* | |
| 2 * Copyright 2014 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 "SkOpContour.h" | |
| 9 #include "SkOpSegment.h" | |
| 10 #include "SkPathWriter.h" | |
| 11 | |
| 12 bool SkOpPtT::alias() const { | |
| 13 return this->span()->ptT() != this; | |
| 14 } | |
| 15 | |
| 16 SkOpContour* SkOpPtT::contour() const { | |
| 17 return segment()->contour(); | |
| 18 } | |
| 19 | |
| 20 SkOpGlobalState* SkOpPtT::globalState() const { | |
| 21 return PATH_OPS_DEBUG_RELEASE(contour()->globalState(), NULL); | |
| 22 } | |
| 23 | |
| 24 void SkOpPtT::init(SkOpSpanBase* span, double t, const SkPoint& pt, bool duplica
te) { | |
| 25 fT = t; | |
| 26 fPt = pt; | |
| 27 fSpan = span; | |
| 28 fNext = this; | |
| 29 fDuplicatePt = duplicate; | |
| 30 fDeleted = false; | |
| 31 PATH_OPS_DEBUG_CODE(fID = ++span->globalState()->fPtTID); | |
| 32 } | |
| 33 | |
| 34 bool SkOpPtT::onEnd() const { | |
| 35 const SkOpSpanBase* span = this->span(); | |
| 36 if (span->ptT() != this) { | |
| 37 return false; | |
| 38 } | |
| 39 const SkOpSegment* segment = this->segment(); | |
| 40 return span == segment->head() || span == segment->tail(); | |
| 41 } | |
| 42 | |
| 43 SkOpPtT* SkOpPtT::remove() { | |
| 44 SkOpPtT* prev = this; | |
| 45 do { | |
| 46 SkOpPtT* next = prev->fNext; | |
| 47 if (next == this) { | |
| 48 prev->removeNext(this); | |
| 49 fDeleted = true; | |
| 50 return prev; | |
| 51 } | |
| 52 prev = next; | |
| 53 } while (prev != this); | |
| 54 SkASSERT(0); | |
| 55 return NULL; | |
| 56 } | |
| 57 | |
| 58 void SkOpPtT::removeNext(SkOpPtT* kept) { | |
| 59 SkASSERT(this->fNext); | |
| 60 SkOpPtT* next = this->fNext; | |
| 61 this->fNext = next->fNext; | |
| 62 SkOpSpanBase* span = next->span(); | |
| 63 next->setDeleted(); | |
| 64 if (span->ptT() == next) { | |
| 65 span->upCast()->detach(kept); | |
| 66 } | |
| 67 } | |
| 68 | |
| 69 const SkOpSegment* SkOpPtT::segment() const { | |
| 70 return span()->segment(); | |
| 71 } | |
| 72 | |
| 73 SkOpSegment* SkOpPtT::segment() { | |
| 74 return span()->segment(); | |
| 75 } | |
| 76 | |
| 77 // find the starting or ending span with an existing loop of angles | |
| 78 // OPTIMIZE? remove the spans pointing to windValue==0 here or earlier? | |
| 79 // FIXME? assert that only one other span has a valid windValue or oppValue | |
| 80 void SkOpSpanBase::addSimpleAngle(bool checkFrom, SkChunkAlloc* allocator) { | |
| 81 SkOpAngle* angle; | |
| 82 if (checkFrom) { | |
| 83 SkASSERT(this->final()); | |
| 84 if (this->fromAngle()) { | |
| 85 SkASSERT(this->fromAngle()->loopCount() == 2); | |
| 86 return; | |
| 87 } | |
| 88 angle = this->segment()->addEndSpan(allocator); | |
| 89 } else { | |
| 90 SkASSERT(this->t() == 0); | |
| 91 SkOpSpan* span = this->upCast(); | |
| 92 if (span->toAngle()) { | |
| 93 SkASSERT(span->toAngle()->loopCount() == 2); | |
| 94 SkASSERT(!span->fromAngle()); | |
| 95 span->setFromAngle(span->toAngle()->next()); | |
| 96 return; | |
| 97 } | |
| 98 angle = this->segment()->addStartSpan(allocator); | |
| 99 } | |
| 100 SkOpPtT* ptT = this->ptT(); | |
| 101 SkOpSpanBase* oSpanBase; | |
| 102 SkOpSpan* oSpan; | |
| 103 SkOpSegment* other; | |
| 104 do { | |
| 105 ptT = ptT->next(); | |
| 106 oSpanBase = ptT->span(); | |
| 107 oSpan = oSpanBase->upCastable(); | |
| 108 other = oSpanBase->segment(); | |
| 109 if (oSpan && oSpan->windValue()) { | |
| 110 break; | |
| 111 } | |
| 112 if (oSpanBase->t() == 0) { | |
| 113 continue; | |
| 114 } | |
| 115 SkOpSpan* oFromSpan = oSpanBase->prev(); | |
| 116 SkASSERT(oFromSpan->t() < 1); | |
| 117 if (oFromSpan->windValue()) { | |
| 118 break; | |
| 119 } | |
| 120 } while (ptT != this->ptT()); | |
| 121 SkOpAngle* oAngle; | |
| 122 if (checkFrom) { | |
| 123 oAngle = other->addStartSpan(allocator); | |
| 124 SkASSERT(oSpan && !oSpan->final()); | |
| 125 SkASSERT(oAngle == oSpan->toAngle()); | |
| 126 } else { | |
| 127 oAngle = other->addEndSpan(allocator); | |
| 128 SkASSERT(oAngle == oSpanBase->fromAngle()); | |
| 129 } | |
| 130 angle->insert(oAngle); | |
| 131 } | |
| 132 | |
| 133 void SkOpSpanBase::align() { | |
| 134 if (this->fAligned) { | |
| 135 return; | |
| 136 } | |
| 137 SkASSERT(!zero_or_one(this->fPtT.fT)); | |
| 138 SkASSERT(this->fPtT.next()); | |
| 139 // if a linked pt/t pair has a t of zero or one, use it as the base for alig
nment | |
| 140 SkOpPtT* ptT = &this->fPtT, * stopPtT = ptT; | |
| 141 while ((ptT = ptT->next()) != stopPtT) { | |
| 142 if (zero_or_one(ptT->fT)) { | |
| 143 SkOpSegment* segment = ptT->segment(); | |
| 144 SkASSERT(this->segment() != segment); | |
| 145 SkASSERT(segment->head()->ptT() == ptT || segment->tail()->ptT() ==
ptT); | |
| 146 if (ptT->fT) { | |
| 147 segment->tail()->alignEnd(1, segment->lastPt()); | |
| 148 } else { | |
| 149 segment->head()->alignEnd(0, segment->pts()[0]); | |
| 150 } | |
| 151 return; | |
| 152 } | |
| 153 } | |
| 154 alignInner(); | |
| 155 this->fAligned = true; | |
| 156 } | |
| 157 | |
| 158 | |
| 159 // FIXME: delete spans that collapse | |
| 160 // delete segments that collapse | |
| 161 // delete contours that collapse | |
| 162 void SkOpSpanBase::alignEnd(double t, const SkPoint& pt) { | |
| 163 SkASSERT(zero_or_one(t)); | |
| 164 SkOpSegment* segment = this->segment(); | |
| 165 SkASSERT(t ? segment->lastPt() == pt : segment->pts()[0] == pt); | |
| 166 alignInner(); | |
| 167 *segment->writablePt(!!t) = pt; | |
| 168 SkOpPtT* ptT = &this->fPtT; | |
| 169 SkASSERT(t == ptT->fT); | |
| 170 SkASSERT(pt == ptT->fPt); | |
| 171 SkOpPtT* test = ptT, * stopPtT = ptT; | |
| 172 while ((test = test->next()) != stopPtT) { | |
| 173 SkOpSegment* other = test->segment(); | |
| 174 if (other == this->segment()) { | |
| 175 continue; | |
| 176 } | |
| 177 if (!zero_or_one(test->fT)) { | |
| 178 continue; | |
| 179 } | |
| 180 *other->writablePt(!!test->fT) = pt; | |
| 181 } | |
| 182 this->fAligned = true; | |
| 183 } | |
| 184 | |
| 185 void SkOpSpanBase::alignInner() { | |
| 186 // force the spans to share points and t values | |
| 187 SkOpPtT* ptT = &this->fPtT, * stopPtT = ptT; | |
| 188 const SkPoint& pt = ptT->fPt; | |
| 189 do { | |
| 190 ptT->fPt = pt; | |
| 191 const SkOpSpanBase* span = ptT->span(); | |
| 192 SkOpPtT* test = ptT; | |
| 193 do { | |
| 194 SkOpPtT* prev = test; | |
| 195 if ((test = test->next()) == stopPtT) { | |
| 196 break; | |
| 197 } | |
| 198 if (span == test->span() && !span->segment()->ptsDisjoint(*ptT, *tes
t)) { | |
| 199 // omit aliases that alignment makes redundant | |
| 200 if ((!ptT->alias() || test->alias()) && (ptT->onEnd() || !test->
onEnd())) { | |
| 201 SkASSERT(test->alias()); | |
| 202 prev->removeNext(ptT); | |
| 203 test = prev; | |
| 204 } else { | |
| 205 SkASSERT(ptT->alias()); | |
| 206 stopPtT = ptT = ptT->remove(); | |
| 207 break; | |
| 208 } | |
| 209 } | |
| 210 } while (true); | |
| 211 } while ((ptT = ptT->next()) != stopPtT); | |
| 212 } | |
| 213 | |
| 214 bool SkOpSpanBase::contains(const SkOpSpanBase* span) const { | |
| 215 const SkOpPtT* start = &fPtT; | |
| 216 const SkOpPtT* check = &span->fPtT; | |
| 217 SkASSERT(start != check); | |
| 218 const SkOpPtT* walk = start; | |
| 219 while ((walk = walk->next()) != start) { | |
| 220 if (walk == check) { | |
| 221 return true; | |
| 222 } | |
| 223 } | |
| 224 return false; | |
| 225 } | |
| 226 | |
| 227 bool SkOpSpanBase::containsCoinEnd(const SkOpSegment* segment) const { | |
| 228 SkASSERT(this->segment() != segment); | |
| 229 const SkOpSpanBase* next = this; | |
| 230 while ((next = next->fCoinEnd) != this) { | |
| 231 if (next->segment() == segment) { | |
| 232 return true; | |
| 233 } | |
| 234 } | |
| 235 return false; | |
| 236 } | |
| 237 | |
| 238 SkOpContour* SkOpSpanBase::contour() const { | |
| 239 return segment()->contour(); | |
| 240 } | |
| 241 | |
| 242 SkOpGlobalState* SkOpSpanBase::globalState() const { | |
| 243 return PATH_OPS_DEBUG_RELEASE(contour()->globalState(), NULL); | |
| 244 } | |
| 245 | |
| 246 void SkOpSpanBase::initBase(SkOpSegment* segment, SkOpSpan* prev, double t, cons
t SkPoint& pt) { | |
| 247 fSegment = segment; | |
| 248 fPtT.init(this, t, pt, false); | |
| 249 fCoinEnd = this; | |
| 250 fFromAngle = NULL; | |
| 251 fPrev = prev; | |
| 252 fAligned = true; | |
| 253 fChased = false; | |
| 254 PATH_OPS_DEBUG_CODE(fCount = 1); | |
| 255 PATH_OPS_DEBUG_CODE(fID = ++globalState()->fSpanID); | |
| 256 } | |
| 257 | |
| 258 // this pair of spans share a common t value or point; merge them and eliminate
duplicates | |
| 259 // this does not compute the best t or pt value; this merely moves all data into
a single list | |
| 260 void SkOpSpanBase::merge(SkOpSpan* span) { | |
| 261 SkOpPtT* spanPtT = span->ptT(); | |
| 262 SkASSERT(this->t() != spanPtT->fT); | |
| 263 SkASSERT(!zero_or_one(spanPtT->fT)); | |
| 264 span->detach(this->ptT()); | |
| 265 SkOpPtT* remainder = spanPtT->next(); | |
| 266 ptT()->insert(spanPtT); | |
| 267 while (remainder != spanPtT) { | |
| 268 SkOpPtT* next = remainder->next(); | |
| 269 SkOpPtT* compare = spanPtT->next(); | |
| 270 while (compare != spanPtT) { | |
| 271 SkOpPtT* nextC = compare->next(); | |
| 272 if (nextC->span() == remainder->span() && nextC->fT == remainder->fT
) { | |
| 273 goto tryNextRemainder; | |
| 274 } | |
| 275 compare = nextC; | |
| 276 } | |
| 277 spanPtT->insert(remainder); | |
| 278 tryNextRemainder: | |
| 279 remainder = next; | |
| 280 } | |
| 281 } | |
| 282 | |
| 283 void SkOpSpanBase::mergeBaseAttributes(SkOpSpanBase* span) { | |
| 284 SkASSERT(!span->fChased); | |
| 285 SkASSERT(!span->fFromAngle); | |
| 286 if (this->upCastable() && span->upCastable()) { | |
| 287 this->upCast()->mergeAttributes(span->upCast()); | |
| 288 } | |
| 289 } | |
| 290 | |
| 291 void SkOpSpan::applyCoincidence(SkOpSpan* opp) { | |
| 292 SkASSERT(!final()); | |
| 293 SkASSERT(0); // incomplete | |
| 294 } | |
| 295 | |
| 296 bool SkOpSpan::containsCoincidence(const SkOpSegment* segment) const { | |
| 297 SkASSERT(this->segment() != segment); | |
| 298 const SkOpSpan* next = this; | |
| 299 while ((next = next->fCoincident) != this) { | |
| 300 if (next->segment() == segment) { | |
| 301 return true; | |
| 302 } | |
| 303 } | |
| 304 return false; | |
| 305 } | |
| 306 | |
| 307 void SkOpSpan::detach(SkOpPtT* kept) { | |
| 308 SkASSERT(!final()); | |
| 309 SkOpSpan* prev = this->prev(); | |
| 310 SkASSERT(prev); | |
| 311 SkOpSpanBase* next = this->next(); | |
| 312 SkASSERT(next); | |
| 313 prev->setNext(next); | |
| 314 next->setPrev(prev); | |
| 315 this->segment()->detach(this); | |
| 316 if (this->coincident()) { | |
| 317 this->globalState()->fCoincidence->fixUp(this->ptT(), kept); | |
| 318 } | |
| 319 this->ptT()->setDeleted(); | |
| 320 } | |
| 321 | |
| 322 void SkOpSpan::init(SkOpSegment* segment, SkOpSpan* prev, double t, const SkPoin
t& pt) { | |
| 323 SkASSERT(t != 1); | |
| 324 initBase(segment, prev, t, pt); | |
| 325 fCoincident = this; | |
| 326 fToAngle = NULL; | |
| 327 fWindSum = fOppSum = SK_MinS32; | |
| 328 fWindValue = 1; | |
| 329 fOppValue = 0; | |
| 330 fChased = fDone = false; | |
| 331 segment->bumpCount(); | |
| 332 } | |
| 333 | |
| 334 void SkOpSpan::mergeAttributes(SkOpSpan* span) { | |
| 335 SkASSERT(!span->fToAngle); | |
| 336 if (span->fCoincident) { | |
| 337 this->insertCoincidence(span); | |
| 338 } | |
| 339 } | |
| 340 | |
| 341 void SkOpCoincidence::add(SkOpPtT* coinPtTStart, SkOpPtT* coinPtTEnd, SkOpPtT* o
ppPtTStart, | |
| 342 SkOpPtT* oppPtTEnd, bool flipped, SkChunkAlloc* allocator) { | |
| 343 SkCoincidentSpans* coinRec = SkOpTAllocator<SkCoincidentSpans>::Allocate(all
ocator); | |
| 344 SkOpSpanBase* coinEnd = coinPtTEnd->span(); | |
| 345 SkOpSpanBase* oppEnd = oppPtTEnd->span(); | |
| 346 SkOpSpan* coinStart = coinPtTStart->span()->upCast(); | |
| 347 SkASSERT(coinStart == coinStart->starter(coinEnd)); | |
| 348 SkOpSpan* oppStart = (flipped ? oppPtTEnd : oppPtTStart)->span()->upCast(); | |
| 349 SkASSERT(oppStart == oppStart->starter(oppEnd)); | |
| 350 coinStart->insertCoincidence(oppStart); | |
| 351 coinEnd->insertCoinEnd(oppEnd); | |
| 352 coinRec->fNext = this->fHead; | |
| 353 coinRec->fCoinPtTStart = coinPtTStart; | |
| 354 coinRec->fCoinPtTEnd = coinPtTEnd; | |
| 355 coinRec->fOppPtTStart = oppPtTStart; | |
| 356 coinRec->fOppPtTEnd = oppPtTEnd; | |
| 357 coinRec->fFlipped = flipped; | |
| 358 this->fHead = coinRec; | |
| 359 } | |
| 360 | |
| 361 bool SkOpCoincidence::contains(SkOpPtT* coinPtTStart, SkOpPtT* coinPtTEnd, SkOpP
tT* oppPtTStart, | |
| 362 SkOpPtT* oppPtTEnd, bool flipped) { | |
| 363 SkCoincidentSpans* coin = fHead; | |
| 364 if (!coin) { | |
| 365 return false; | |
| 366 } | |
| 367 do { | |
| 368 if (coin->fCoinPtTStart == coinPtTStart && coin->fCoinPtTEnd == coinPtT
End | |
| 369 && coin->fOppPtTStart == oppPtTStart && coin->fOppPtTEnd == oppP
tTEnd | |
| 370 && coin->fFlipped == flipped) { | |
| 371 return true; | |
| 372 } | |
| 373 } while ((coin = coin->fNext)); | |
| 374 return false; | |
| 375 } | |
| 376 | |
| 377 // walk span sets in parallel, moving winding from one to the other | |
| 378 void SkOpCoincidence::apply() { | |
| 379 SkCoincidentSpans* coin = fHead; | |
| 380 if (!coin) { | |
| 381 return; | |
| 382 } | |
| 383 do { | |
| 384 SkOpSpanBase* end = coin->fCoinPtTEnd->span(); | |
| 385 SkOpSpan* start = coin->fCoinPtTStart->span()->upCast(); | |
| 386 SkASSERT(start == start->starter(end)); | |
| 387 bool flipped = coin->fFlipped; | |
| 388 SkOpSpanBase* oEnd = (flipped ? coin->fOppPtTStart : coin->fOppPtTEnd)->
span(); | |
| 389 SkOpSpan* oStart = (flipped ? coin->fOppPtTEnd : coin->fOppPtTStart)->sp
an()->upCast(); | |
| 390 SkASSERT(oStart == oStart->starter(oEnd)); | |
| 391 SkOpSegment* segment = start->segment(); | |
| 392 SkOpSegment* oSegment = oStart->segment(); | |
| 393 bool operandSwap = segment->operand() != oSegment->operand(); | |
| 394 if (flipped) { | |
| 395 do { | |
| 396 SkOpSpanBase* oNext = oStart->next(); | |
| 397 if (oNext == oEnd) { | |
| 398 break; | |
| 399 } | |
| 400 oStart = oNext->upCast(); | |
| 401 } while (true); | |
| 402 } | |
| 403 bool isXor = segment->isXor(); | |
| 404 bool oppXor = oSegment->isXor(); | |
| 405 do { | |
| 406 int windValue = start->windValue(); | |
| 407 int oWindValue = oStart->windValue(); | |
| 408 int oppValue = start->oppValue(); | |
| 409 int oOppValue = oStart->oppValue(); | |
| 410 // winding values are added or subtracted depending on direction and
wind type | |
| 411 // same or opposite values are summed depending on the operand value | |
| 412 if (windValue >= oWindValue) { | |
| 413 if (operandSwap) { | |
| 414 SkTSwap(oWindValue, oOppValue); | |
| 415 } | |
| 416 if (flipped) { | |
| 417 windValue -= oWindValue; | |
| 418 oppValue -= oOppValue; | |
| 419 } else { | |
| 420 windValue += oWindValue; | |
| 421 oppValue += oOppValue; | |
| 422 } | |
| 423 if (isXor) { | |
| 424 windValue &= 1; | |
| 425 } | |
| 426 if (oppXor) { | |
| 427 oppValue &= 1; | |
| 428 } | |
| 429 oWindValue = oOppValue = 0; | |
| 430 } else { | |
| 431 if (operandSwap) { | |
| 432 SkTSwap(windValue, oppValue); | |
| 433 } | |
| 434 if (flipped) { | |
| 435 oWindValue -= windValue; | |
| 436 oOppValue -= oppValue; | |
| 437 } else { | |
| 438 oWindValue += windValue; | |
| 439 oOppValue += oppValue; | |
| 440 } | |
| 441 if (isXor) { | |
| 442 oOppValue &= 1; | |
| 443 } | |
| 444 if (oppXor) { | |
| 445 oWindValue &= 1; | |
| 446 } | |
| 447 windValue = oppValue = 0; | |
| 448 } | |
| 449 start->setWindValue(windValue); | |
| 450 start->setOppValue(oppValue); | |
| 451 oStart->setWindValue(oWindValue); | |
| 452 oStart->setOppValue(oOppValue); | |
| 453 if (!windValue && !oppValue) { | |
| 454 segment->markDone(start); | |
| 455 } | |
| 456 if (!oWindValue && !oOppValue) { | |
| 457 oSegment->markDone(oStart); | |
| 458 } | |
| 459 SkOpSpanBase* next = start->next(); | |
| 460 SkOpSpanBase* oNext = flipped ? oStart->prev() : oStart->next(); | |
| 461 if (next == end) { | |
| 462 break; | |
| 463 } | |
| 464 start = next->upCast(); | |
| 465 oStart = oNext->upCast(); | |
| 466 } while (true); | |
| 467 } while ((coin = coin->fNext)); | |
| 468 } | |
| 469 | |
| 470 void SkOpCoincidence::mark() { | |
| 471 SkCoincidentSpans* coin = fHead; | |
| 472 if (!coin) { | |
| 473 return; | |
| 474 } | |
| 475 do { | |
| 476 SkOpSpanBase* end = coin->fCoinPtTEnd->span(); | |
| 477 SkOpSpanBase* oldEnd = end; | |
| 478 SkOpSpan* start = coin->fCoinPtTStart->span()->starter(&end); | |
| 479 SkOpSpanBase* oEnd = coin->fOppPtTEnd->span(); | |
| 480 SkOpSpanBase* oOldEnd = oEnd; | |
| 481 SkOpSpanBase* oStart = coin->fOppPtTStart->span()->starter(&oEnd); | |
| 482 bool flipped = (end == oldEnd) != (oEnd == oOldEnd); | |
| 483 if (flipped) { | |
| 484 SkTSwap(oStart, oEnd); | |
| 485 } | |
| 486 SkOpSpanBase* next = start; | |
| 487 SkOpSpanBase* oNext = oStart; | |
| 488 do { | |
| 489 next = next->upCast()->next(); | |
| 490 oNext = flipped ? oNext->prev() : oNext->upCast()->next(); | |
| 491 if (next == end) { | |
| 492 SkASSERT(oNext == oEnd); | |
| 493 break; | |
| 494 } | |
| 495 if (!next->containsCoinEnd(oNext)) { | |
| 496 next->insertCoinEnd(oNext); | |
| 497 } | |
| 498 SkOpSpan* nextSpan = next->upCast(); | |
| 499 SkOpSpan* oNextSpan = oNext->upCast(); | |
| 500 if (!nextSpan->containsCoincidence(oNextSpan)) { | |
| 501 nextSpan->insertCoincidence(oNextSpan); | |
| 502 } | |
| 503 } while (true); | |
| 504 } while ((coin = coin->fNext)); | |
| 505 } | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 1299773002:
Remove a couple zombie pathops files. (Closed)
Base URL: https://skia.googlesource.com/skia.git@master