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 12bool SkOpPtT::alias() const { 13 return this->span()->ptT() != this; 14} 15 16SkOpContour* SkOpPtT::contour() const { 17 return segment()->contour(); 18} 19 20SkOpGlobalState* SkOpPtT::globalState() const { 21 return PATH_OPS_DEBUG_RELEASE(contour()->globalState(), NULL); 22} 23 24void SkOpPtT::init(SkOpSpanBase* span, double t, const SkPoint& pt, bool duplicate) { 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 34bool 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 43SkOpPtT* 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 58void 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 69const SkOpSegment* SkOpPtT::segment() const { 70 return span()->segment(); 71} 72 73SkOpSegment* 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 80void 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 133void 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 alignment 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 162void 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 185void 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, *test)) { 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 214bool 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 227bool 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 238SkOpContour* SkOpSpanBase::contour() const { 239 return segment()->contour(); 240} 241 242SkOpGlobalState* SkOpSpanBase::globalState() const { 243 return PATH_OPS_DEBUG_RELEASE(contour()->globalState(), NULL); 244} 245 246void SkOpSpanBase::initBase(SkOpSegment* segment, SkOpSpan* prev, double t, const 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 260void 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); 278tryNextRemainder: 279 remainder = next; 280 } 281} 282 283void 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 291void SkOpSpan::applyCoincidence(SkOpSpan* opp) { 292 SkASSERT(!final()); 293 SkASSERT(0); // incomplete 294} 295 296bool 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 307void 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 322void SkOpSpan::init(SkOpSegment* segment, SkOpSpan* prev, double t, const SkPoint& 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 334void SkOpSpan::mergeAttributes(SkOpSpan* span) { 335 SkASSERT(!span->fToAngle); 336 if (span->fCoincident) { 337 this->insertCoincidence(span); 338 } 339} 340 341void SkOpCoincidence::add(SkOpPtT* coinPtTStart, SkOpPtT* coinPtTEnd, SkOpPtT* oppPtTStart, 342 SkOpPtT* oppPtTEnd, bool flipped, SkChunkAlloc* allocator) { 343 SkCoincidentSpans* coinRec = SkOpTAllocator<SkCoincidentSpans>::Allocate(allocator); 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 361bool SkOpCoincidence::contains(SkOpPtT* coinPtTStart, SkOpPtT* coinPtTEnd, SkOpPtT* 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 == coinPtTEnd 369 && coin->fOppPtTStart == oppPtTStart && coin->fOppPtTEnd == oppPtTEnd 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 378void 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)->span()->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 470void 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} 506