1 /* 2 * Copyright 2011 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 8 #include "SkAtomics.h" 9 #include "SkCanvas.h" 10 #include "SkClipStack.h" 11 #include "SkPath.h" 12 #include "SkPathOps.h" 13 #include "SkClipOpPriv.h" 14 15 #include <new> 16 17 18 // 0-2 are reserved for invalid, empty & wide-open 19 static const int32_t kFirstUnreservedGenID = 3; 20 int32_t SkClipStack::gGenID = kFirstUnreservedGenID; 21 22 SkClipStack::Element::Element(const Element& that) { 23 switch (that.getType()) { 24 case kEmpty_Type: 25 fRRect.setEmpty(); 26 fPath.reset(); 27 break; 28 case kRect_Type: // Rect uses rrect 29 case kRRect_Type: 30 fPath.reset(); 31 fRRect = that.fRRect; 32 break; 33 case kPath_Type: 34 fPath.set(that.getPath()); 35 break; 36 } 37 38 fSaveCount = that.fSaveCount; 39 fOp = that.fOp; 40 fType = that.fType; 41 fDoAA = that.fDoAA; 42 fFiniteBoundType = that.fFiniteBoundType; 43 fFiniteBound = that.fFiniteBound; 44 fIsIntersectionOfRects = that.fIsIntersectionOfRects; 45 fGenID = that.fGenID; 46 } 47 48 bool SkClipStack::Element::operator== (const Element& element) const { 49 if (this == &element) { 50 return true; 51 } 52 if (fOp != element.fOp || 53 fType != element.fType || 54 fDoAA != element.fDoAA || 55 fSaveCount != element.fSaveCount) { 56 return false; 57 } 58 switch (fType) { 59 case kPath_Type: 60 return this->getPath() == element.getPath(); 61 case kRRect_Type: 62 return fRRect == element.fRRect; 63 case kRect_Type: 64 return this->getRect() == element.getRect(); 65 case kEmpty_Type: 66 return true; 67 default: 68 SkDEBUGFAIL("Unexpected type."); 69 return false; 70 } 71 } 72 73 void SkClipStack::Element::invertShapeFillType() { 74 switch (fType) { 75 case kRect_Type: 76 fPath.init(); 77 fPath.get()->addRect(this->getRect()); 78 fPath.get()->setFillType(SkPath::kInverseEvenOdd_FillType); 79 fType = kPath_Type; 80 break; 81 case kRRect_Type: 82 fPath.init(); 83 fPath.get()->addRRect(fRRect); 84 fPath.get()->setFillType(SkPath::kInverseEvenOdd_FillType); 85 fType = kPath_Type; 86 break; 87 case kPath_Type: 88 fPath.get()->toggleInverseFillType(); 89 break; 90 case kEmpty_Type: 91 // Should this set to an empty, inverse filled path? 92 break; 93 } 94 } 95 96 void SkClipStack::Element::initPath(int saveCount, const SkPath& path, SkClipOp op, 97 bool doAA) { 98 if (!path.isInverseFillType()) { 99 SkRect r; 100 if (path.isRect(&r)) { 101 this->initRect(saveCount, r, op, doAA); 102 return; 103 } 104 SkRect ovalRect; 105 if (path.isOval(&ovalRect)) { 106 SkRRect rrect; 107 rrect.setOval(ovalRect); 108 this->initRRect(saveCount, rrect, op, doAA); 109 return; 110 } 111 } 112 fPath.set(path); 113 fPath.get()->setIsVolatile(true); 114 fType = kPath_Type; 115 this->initCommon(saveCount, op, doAA); 116 } 117 118 void SkClipStack::Element::asPath(SkPath* path) const { 119 switch (fType) { 120 case kEmpty_Type: 121 path->reset(); 122 path->setIsVolatile(true); 123 break; 124 case kRect_Type: 125 path->reset(); 126 path->addRect(this->getRect()); 127 path->setIsVolatile(true); 128 break; 129 case kRRect_Type: 130 path->reset(); 131 path->addRRect(fRRect); 132 path->setIsVolatile(true); 133 break; 134 case kPath_Type: 135 *path = *fPath.get(); 136 break; 137 } 138 path->setIsVolatile(true); 139 } 140 141 void SkClipStack::Element::setEmpty() { 142 fType = kEmpty_Type; 143 fFiniteBound.setEmpty(); 144 fFiniteBoundType = kNormal_BoundsType; 145 fIsIntersectionOfRects = false; 146 fRRect.setEmpty(); 147 fPath.reset(); 148 fGenID = kEmptyGenID; 149 SkDEBUGCODE(this->checkEmpty();) 150 } 151 152 void SkClipStack::Element::checkEmpty() const { 153 SkASSERT(fFiniteBound.isEmpty()); 154 SkASSERT(kNormal_BoundsType == fFiniteBoundType); 155 SkASSERT(!fIsIntersectionOfRects); 156 SkASSERT(kEmptyGenID == fGenID); 157 SkASSERT(fRRect.isEmpty()); 158 SkASSERT(!fPath.isValid()); 159 } 160 161 bool SkClipStack::Element::canBeIntersectedInPlace(int saveCount, SkClipOp op) const { 162 if (kEmpty_Type == fType && 163 (kDifference_SkClipOp == op || kIntersect_SkClipOp == op)) { 164 return true; 165 } 166 // Only clips within the same save/restore frame (as captured by 167 // the save count) can be merged 168 return fSaveCount == saveCount && 169 kIntersect_SkClipOp == op && 170 (kIntersect_SkClipOp == fOp || kReplace_SkClipOp == fOp); 171 } 172 173 bool SkClipStack::Element::rectRectIntersectAllowed(const SkRect& newR, bool newAA) const { 174 SkASSERT(kRect_Type == fType); 175 176 if (fDoAA == newAA) { 177 // if the AA setting is the same there is no issue 178 return true; 179 } 180 181 if (!SkRect::Intersects(this->getRect(), newR)) { 182 // The calling code will correctly set the result to the empty clip 183 return true; 184 } 185 186 if (this->getRect().contains(newR)) { 187 // if the new rect carves out a portion of the old one there is no 188 // issue 189 return true; 190 } 191 192 // So either the two overlap in some complex manner or newR contains oldR. 193 // In the first, case the edges will require different AA. In the second, 194 // the AA setting that would be carried forward is incorrect (e.g., oldR 195 // is AA while newR is BW but since newR contains oldR, oldR will be 196 // drawn BW) since the new AA setting will predominate. 197 return false; 198 } 199 200 // a mirror of combineBoundsRevDiff 201 void SkClipStack::Element::combineBoundsDiff(FillCombo combination, const SkRect& prevFinite) { 202 switch (combination) { 203 case kInvPrev_InvCur_FillCombo: 204 // In this case the only pixels that can remain set 205 // are inside the current clip rect since the extensions 206 // to infinity of both clips cancel out and whatever 207 // is outside of the current clip is removed 208 fFiniteBoundType = kNormal_BoundsType; 209 break; 210 case kInvPrev_Cur_FillCombo: 211 // In this case the current op is finite so the only pixels 212 // that aren't set are whatever isn't set in the previous 213 // clip and whatever this clip carves out 214 fFiniteBound.join(prevFinite); 215 fFiniteBoundType = kInsideOut_BoundsType; 216 break; 217 case kPrev_InvCur_FillCombo: 218 // In this case everything outside of this clip's bound 219 // is erased, so the only pixels that can remain set 220 // occur w/in the intersection of the two finite bounds 221 if (!fFiniteBound.intersect(prevFinite)) { 222 fFiniteBound.setEmpty(); 223 fGenID = kEmptyGenID; 224 } 225 fFiniteBoundType = kNormal_BoundsType; 226 break; 227 case kPrev_Cur_FillCombo: 228 // The most conservative result bound is that of the 229 // prior clip. This could be wildly incorrect if the 230 // second clip either exactly matches the first clip 231 // (which should yield the empty set) or reduces the 232 // size of the prior bound (e.g., if the second clip 233 // exactly matched the bottom half of the prior clip). 234 // We ignore these two possibilities. 235 fFiniteBound = prevFinite; 236 break; 237 default: 238 SkDEBUGFAIL("SkClipStack::Element::combineBoundsDiff Invalid fill combination"); 239 break; 240 } 241 } 242 243 void SkClipStack::Element::combineBoundsXOR(int combination, const SkRect& prevFinite) { 244 245 switch (combination) { 246 case kInvPrev_Cur_FillCombo: // fall through 247 case kPrev_InvCur_FillCombo: 248 // With only one of the clips inverted the result will always 249 // extend to infinity. The only pixels that may be un-writeable 250 // lie within the union of the two finite bounds 251 fFiniteBound.join(prevFinite); 252 fFiniteBoundType = kInsideOut_BoundsType; 253 break; 254 case kInvPrev_InvCur_FillCombo: 255 // The only pixels that can survive are within the 256 // union of the two bounding boxes since the extensions 257 // to infinity of both clips cancel out 258 // fall through! 259 case kPrev_Cur_FillCombo: 260 // The most conservative bound for xor is the 261 // union of the two bounds. If the two clips exactly overlapped 262 // the xor could yield the empty set. Similarly the xor 263 // could reduce the size of the original clip's bound (e.g., 264 // if the second clip exactly matched the bottom half of the 265 // first clip). We ignore these two cases. 266 fFiniteBound.join(prevFinite); 267 fFiniteBoundType = kNormal_BoundsType; 268 break; 269 default: 270 SkDEBUGFAIL("SkClipStack::Element::combineBoundsXOR Invalid fill combination"); 271 break; 272 } 273 } 274 275 // a mirror of combineBoundsIntersection 276 void SkClipStack::Element::combineBoundsUnion(int combination, const SkRect& prevFinite) { 277 278 switch (combination) { 279 case kInvPrev_InvCur_FillCombo: 280 if (!fFiniteBound.intersect(prevFinite)) { 281 fFiniteBound.setEmpty(); 282 fGenID = kWideOpenGenID; 283 } 284 fFiniteBoundType = kInsideOut_BoundsType; 285 break; 286 case kInvPrev_Cur_FillCombo: 287 // The only pixels that won't be drawable are inside 288 // the prior clip's finite bound 289 fFiniteBound = prevFinite; 290 fFiniteBoundType = kInsideOut_BoundsType; 291 break; 292 case kPrev_InvCur_FillCombo: 293 // The only pixels that won't be drawable are inside 294 // this clip's finite bound 295 break; 296 case kPrev_Cur_FillCombo: 297 fFiniteBound.join(prevFinite); 298 break; 299 default: 300 SkDEBUGFAIL("SkClipStack::Element::combineBoundsUnion Invalid fill combination"); 301 break; 302 } 303 } 304 305 // a mirror of combineBoundsUnion 306 void SkClipStack::Element::combineBoundsIntersection(int combination, const SkRect& prevFinite) { 307 308 switch (combination) { 309 case kInvPrev_InvCur_FillCombo: 310 // The only pixels that aren't writable in this case 311 // occur in the union of the two finite bounds 312 fFiniteBound.join(prevFinite); 313 fFiniteBoundType = kInsideOut_BoundsType; 314 break; 315 case kInvPrev_Cur_FillCombo: 316 // In this case the only pixels that will remain writeable 317 // are within the current clip 318 break; 319 case kPrev_InvCur_FillCombo: 320 // In this case the only pixels that will remain writeable 321 // are with the previous clip 322 fFiniteBound = prevFinite; 323 fFiniteBoundType = kNormal_BoundsType; 324 break; 325 case kPrev_Cur_FillCombo: 326 if (!fFiniteBound.intersect(prevFinite)) { 327 this->setEmpty(); 328 } 329 break; 330 default: 331 SkDEBUGFAIL("SkClipStack::Element::combineBoundsIntersection Invalid fill combination"); 332 break; 333 } 334 } 335 336 // a mirror of combineBoundsDiff 337 void SkClipStack::Element::combineBoundsRevDiff(int combination, const SkRect& prevFinite) { 338 339 switch (combination) { 340 case kInvPrev_InvCur_FillCombo: 341 // The only pixels that can survive are in the 342 // previous bound since the extensions to infinity in 343 // both clips cancel out 344 fFiniteBound = prevFinite; 345 fFiniteBoundType = kNormal_BoundsType; 346 break; 347 case kInvPrev_Cur_FillCombo: 348 if (!fFiniteBound.intersect(prevFinite)) { 349 this->setEmpty(); 350 } else { 351 fFiniteBoundType = kNormal_BoundsType; 352 } 353 break; 354 case kPrev_InvCur_FillCombo: 355 fFiniteBound.join(prevFinite); 356 fFiniteBoundType = kInsideOut_BoundsType; 357 break; 358 case kPrev_Cur_FillCombo: 359 // Fall through - as with the kDifference_Op case, the 360 // most conservative result bound is the bound of the 361 // current clip. The prior clip could reduce the size of this 362 // bound (as in the kDifference_Op case) but we are ignoring 363 // those cases. 364 break; 365 default: 366 SkDEBUGFAIL("SkClipStack::Element::combineBoundsRevDiff Invalid fill combination"); 367 break; 368 } 369 } 370 371 void SkClipStack::Element::updateBoundAndGenID(const Element* prior) { 372 // We set this first here but we may overwrite it later if we determine that the clip is 373 // either wide-open or empty. 374 fGenID = GetNextGenID(); 375 376 // First, optimistically update the current Element's bound information 377 // with the current clip's bound 378 fIsIntersectionOfRects = false; 379 switch (fType) { 380 case kRect_Type: 381 fFiniteBound = this->getRect(); 382 fFiniteBoundType = kNormal_BoundsType; 383 384 if (kReplace_SkClipOp == fOp || 385 (kIntersect_SkClipOp == fOp && nullptr == prior) || 386 (kIntersect_SkClipOp == fOp && prior->fIsIntersectionOfRects && 387 prior->rectRectIntersectAllowed(this->getRect(), fDoAA))) { 388 fIsIntersectionOfRects = true; 389 } 390 break; 391 case kRRect_Type: 392 fFiniteBound = fRRect.getBounds(); 393 fFiniteBoundType = kNormal_BoundsType; 394 break; 395 case kPath_Type: 396 fFiniteBound = fPath.get()->getBounds(); 397 398 if (fPath.get()->isInverseFillType()) { 399 fFiniteBoundType = kInsideOut_BoundsType; 400 } else { 401 fFiniteBoundType = kNormal_BoundsType; 402 } 403 break; 404 case kEmpty_Type: 405 SkDEBUGFAIL("We shouldn't get here with an empty element."); 406 break; 407 } 408 409 if (!fDoAA) { 410 fFiniteBound.set(SkScalarFloorToScalar(fFiniteBound.fLeft+0.45f), 411 SkScalarRoundToScalar(fFiniteBound.fTop), 412 SkScalarRoundToScalar(fFiniteBound.fRight), 413 SkScalarRoundToScalar(fFiniteBound.fBottom)); 414 } 415 416 // Now determine the previous Element's bound information taking into 417 // account that there may be no previous clip 418 SkRect prevFinite; 419 SkClipStack::BoundsType prevType; 420 421 if (nullptr == prior) { 422 // no prior clip means the entire plane is writable 423 prevFinite.setEmpty(); // there are no pixels that cannot be drawn to 424 prevType = kInsideOut_BoundsType; 425 } else { 426 prevFinite = prior->fFiniteBound; 427 prevType = prior->fFiniteBoundType; 428 } 429 430 FillCombo combination = kPrev_Cur_FillCombo; 431 if (kInsideOut_BoundsType == fFiniteBoundType) { 432 combination = (FillCombo) (combination | 0x01); 433 } 434 if (kInsideOut_BoundsType == prevType) { 435 combination = (FillCombo) (combination | 0x02); 436 } 437 438 SkASSERT(kInvPrev_InvCur_FillCombo == combination || 439 kInvPrev_Cur_FillCombo == combination || 440 kPrev_InvCur_FillCombo == combination || 441 kPrev_Cur_FillCombo == combination); 442 443 // Now integrate with clip with the prior clips 444 switch (fOp) { 445 case kDifference_SkClipOp: 446 this->combineBoundsDiff(combination, prevFinite); 447 break; 448 case kXOR_SkClipOp: 449 this->combineBoundsXOR(combination, prevFinite); 450 break; 451 case kUnion_SkClipOp: 452 this->combineBoundsUnion(combination, prevFinite); 453 break; 454 case kIntersect_SkClipOp: 455 this->combineBoundsIntersection(combination, prevFinite); 456 break; 457 case kReverseDifference_SkClipOp: 458 this->combineBoundsRevDiff(combination, prevFinite); 459 break; 460 case kReplace_SkClipOp: 461 // Replace just ignores everything prior 462 // The current clip's bound information is already filled in 463 // so nothing to do 464 break; 465 default: 466 SkDebugf("SkClipOp error\n"); 467 SkASSERT(0); 468 break; 469 } 470 } 471 472 // This constant determines how many Element's are allocated together as a block in 473 // the deque. As such it needs to balance allocating too much memory vs. 474 // incurring allocation/deallocation thrashing. It should roughly correspond to 475 // the deepest save/restore stack we expect to see. 476 static const int kDefaultElementAllocCnt = 8; 477 478 SkClipStack::SkClipStack() 479 : fDeque(sizeof(Element), kDefaultElementAllocCnt) 480 , fSaveCount(0) { 481 } 482 483 SkClipStack::SkClipStack(void* storage, size_t size) 484 : fDeque(sizeof(Element), storage, size, kDefaultElementAllocCnt) 485 , fSaveCount(0) { 486 } 487 488 SkClipStack::SkClipStack(const SkClipStack& b) 489 : fDeque(sizeof(Element), kDefaultElementAllocCnt) { 490 *this = b; 491 } 492 493 SkClipStack::~SkClipStack() { 494 reset(); 495 } 496 497 SkClipStack& SkClipStack::operator=(const SkClipStack& b) { 498 if (this == &b) { 499 return *this; 500 } 501 reset(); 502 503 fSaveCount = b.fSaveCount; 504 SkDeque::F2BIter recIter(b.fDeque); 505 for (const Element* element = (const Element*)recIter.next(); 506 element != nullptr; 507 element = (const Element*)recIter.next()) { 508 new (fDeque.push_back()) Element(*element); 509 } 510 511 return *this; 512 } 513 514 bool SkClipStack::operator==(const SkClipStack& b) const { 515 if (this->getTopmostGenID() == b.getTopmostGenID()) { 516 return true; 517 } 518 if (fSaveCount != b.fSaveCount || 519 fDeque.count() != b.fDeque.count()) { 520 return false; 521 } 522 SkDeque::F2BIter myIter(fDeque); 523 SkDeque::F2BIter bIter(b.fDeque); 524 const Element* myElement = (const Element*)myIter.next(); 525 const Element* bElement = (const Element*)bIter.next(); 526 527 while (myElement != nullptr && bElement != nullptr) { 528 if (*myElement != *bElement) { 529 return false; 530 } 531 myElement = (const Element*)myIter.next(); 532 bElement = (const Element*)bIter.next(); 533 } 534 return myElement == nullptr && bElement == nullptr; 535 } 536 537 void SkClipStack::reset() { 538 // We used a placement new for each object in fDeque, so we're responsible 539 // for calling the destructor on each of them as well. 540 while (!fDeque.empty()) { 541 Element* element = (Element*)fDeque.back(); 542 element->~Element(); 543 fDeque.pop_back(); 544 } 545 546 fSaveCount = 0; 547 } 548 549 void SkClipStack::save() { 550 fSaveCount += 1; 551 } 552 553 void SkClipStack::restore() { 554 fSaveCount -= 1; 555 restoreTo(fSaveCount); 556 } 557 558 void SkClipStack::restoreTo(int saveCount) { 559 while (!fDeque.empty()) { 560 Element* element = (Element*)fDeque.back(); 561 if (element->fSaveCount <= saveCount) { 562 break; 563 } 564 element->~Element(); 565 fDeque.pop_back(); 566 } 567 } 568 569 SkRect SkClipStack::bounds(const SkIRect& deviceBounds) const { 570 // TODO: optimize this. 571 SkRect r; 572 SkClipStack::BoundsType bounds; 573 this->getBounds(&r, &bounds); 574 if (bounds == SkClipStack::kInsideOut_BoundsType) { 575 return SkRect::Make(deviceBounds); 576 } 577 return r.intersect(SkRect::Make(deviceBounds)) ? r : SkRect::MakeEmpty(); 578 } 579 580 // TODO: optimize this. 581 bool SkClipStack::isEmpty(const SkIRect& r) const { return this->bounds(r).isEmpty(); } 582 583 void SkClipStack::getBounds(SkRect* canvFiniteBound, 584 BoundsType* boundType, 585 bool* isIntersectionOfRects) const { 586 SkASSERT(canvFiniteBound && boundType); 587 588 Element* element = (Element*)fDeque.back(); 589 590 if (nullptr == element) { 591 // the clip is wide open - the infinite plane w/ no pixels un-writeable 592 canvFiniteBound->setEmpty(); 593 *boundType = kInsideOut_BoundsType; 594 if (isIntersectionOfRects) { 595 *isIntersectionOfRects = false; 596 } 597 return; 598 } 599 600 *canvFiniteBound = element->fFiniteBound; 601 *boundType = element->fFiniteBoundType; 602 if (isIntersectionOfRects) { 603 *isIntersectionOfRects = element->fIsIntersectionOfRects; 604 } 605 } 606 607 bool SkClipStack::internalQuickContains(const SkRect& rect) const { 608 609 Iter iter(*this, Iter::kTop_IterStart); 610 const Element* element = iter.prev(); 611 while (element != nullptr) { 612 if (kIntersect_SkClipOp != element->getOp() && kReplace_SkClipOp != element->getOp()) 613 return false; 614 if (element->isInverseFilled()) { 615 // Part of 'rect' could be trimmed off by the inverse-filled clip element 616 if (SkRect::Intersects(element->getBounds(), rect)) { 617 return false; 618 } 619 } else { 620 if (!element->contains(rect)) { 621 return false; 622 } 623 } 624 if (kReplace_SkClipOp == element->getOp()) { 625 break; 626 } 627 element = iter.prev(); 628 } 629 return true; 630 } 631 632 bool SkClipStack::internalQuickContains(const SkRRect& rrect) const { 633 634 Iter iter(*this, Iter::kTop_IterStart); 635 const Element* element = iter.prev(); 636 while (element != nullptr) { 637 if (kIntersect_SkClipOp != element->getOp() && kReplace_SkClipOp != element->getOp()) 638 return false; 639 if (element->isInverseFilled()) { 640 // Part of 'rrect' could be trimmed off by the inverse-filled clip element 641 if (SkRect::Intersects(element->getBounds(), rrect.getBounds())) { 642 return false; 643 } 644 } else { 645 if (!element->contains(rrect)) { 646 return false; 647 } 648 } 649 if (kReplace_SkClipOp == element->getOp()) { 650 break; 651 } 652 element = iter.prev(); 653 } 654 return true; 655 } 656 657 bool SkClipStack::asPath(SkPath *path) const { 658 bool isAA = false; 659 660 path->reset(); 661 path->setFillType(SkPath::kInverseEvenOdd_FillType); 662 663 SkClipStack::Iter iter(*this, SkClipStack::Iter::kBottom_IterStart); 664 while (const SkClipStack::Element* element = iter.next()) { 665 SkPath operand; 666 if (element->getType() != SkClipStack::Element::kEmpty_Type) { 667 element->asPath(&operand); 668 } 669 670 SkClipOp elementOp = element->getOp(); 671 if (elementOp == kReplace_SkClipOp) { 672 *path = operand; 673 } else { 674 Op(*path, operand, (SkPathOp)elementOp, path); 675 } 676 677 // if the prev and curr clips disagree about aa -vs- not, favor the aa request. 678 // perhaps we need an API change to avoid this sort of mixed-signals about 679 // clipping. 680 isAA = (isAA || element->isAA()); 681 } 682 683 return isAA; 684 } 685 686 void SkClipStack::pushElement(const Element& element) { 687 // Use reverse iterator instead of back because Rect path may need previous 688 SkDeque::Iter iter(fDeque, SkDeque::Iter::kBack_IterStart); 689 Element* prior = (Element*) iter.prev(); 690 691 if (prior) { 692 if (prior->canBeIntersectedInPlace(fSaveCount, element.getOp())) { 693 switch (prior->fType) { 694 case Element::kEmpty_Type: 695 SkDEBUGCODE(prior->checkEmpty();) 696 return; 697 case Element::kRect_Type: 698 if (Element::kRect_Type == element.getType()) { 699 if (prior->rectRectIntersectAllowed(element.getRect(), element.isAA())) { 700 SkRect isectRect; 701 if (!isectRect.intersect(prior->getRect(), element.getRect())) { 702 prior->setEmpty(); 703 return; 704 } 705 706 prior->fRRect.setRect(isectRect); 707 prior->fDoAA = element.isAA(); 708 Element* priorPrior = (Element*) iter.prev(); 709 prior->updateBoundAndGenID(priorPrior); 710 return; 711 } 712 break; 713 } 714 // fallthrough 715 default: 716 if (!SkRect::Intersects(prior->getBounds(), element.getBounds())) { 717 prior->setEmpty(); 718 return; 719 } 720 break; 721 } 722 } else if (kReplace_SkClipOp == element.getOp()) { 723 this->restoreTo(fSaveCount - 1); 724 prior = (Element*) fDeque.back(); 725 } 726 } 727 Element* newElement = new (fDeque.push_back()) Element(element); 728 newElement->updateBoundAndGenID(prior); 729 } 730 731 void SkClipStack::clipRRect(const SkRRect& rrect, const SkMatrix& matrix, SkClipOp op, 732 bool doAA) { 733 SkRRect transformedRRect; 734 if (rrect.transform(matrix, &transformedRRect)) { 735 Element element(fSaveCount, transformedRRect, op, doAA); 736 this->pushElement(element); 737 if (this->hasClipRestriction(op)) { 738 Element element(fSaveCount, fClipRestrictionRect, kIntersect_SkClipOp, false); 739 this->pushElement(element); 740 } 741 return; 742 } 743 SkPath path; 744 path.addRRect(rrect); 745 path.setIsVolatile(true); 746 this->clipPath(path, matrix, op, doAA); 747 } 748 749 void SkClipStack::clipRect(const SkRect& rect, const SkMatrix& matrix, SkClipOp op, 750 bool doAA) { 751 if (matrix.rectStaysRect()) { 752 SkRect devRect; 753 matrix.mapRect(&devRect, rect); 754 if (this->hasClipRestriction(op)) { 755 if (!devRect.intersect(fClipRestrictionRect)) { 756 devRect.setEmpty(); 757 } 758 } 759 Element element(fSaveCount, devRect, op, doAA); 760 this->pushElement(element); 761 return; 762 } 763 SkPath path; 764 path.addRect(rect); 765 path.setIsVolatile(true); 766 this->clipPath(path, matrix, op, doAA); 767 } 768 769 void SkClipStack::clipPath(const SkPath& path, const SkMatrix& matrix, SkClipOp op, 770 bool doAA) { 771 SkPath devPath; 772 path.transform(matrix, &devPath); 773 Element element(fSaveCount, devPath, op, doAA); 774 this->pushElement(element); 775 if (this->hasClipRestriction(op)) { 776 Element element(fSaveCount, fClipRestrictionRect, kIntersect_SkClipOp, false); 777 this->pushElement(element); 778 } 779 } 780 781 void SkClipStack::clipEmpty() { 782 Element* element = (Element*) fDeque.back(); 783 784 if (element && element->canBeIntersectedInPlace(fSaveCount, kIntersect_SkClipOp)) { 785 element->setEmpty(); 786 } 787 new (fDeque.push_back()) Element(fSaveCount); 788 789 ((Element*)fDeque.back())->fGenID = kEmptyGenID; 790 } 791 792 /////////////////////////////////////////////////////////////////////////////// 793 794 SkClipStack::Iter::Iter() : fStack(nullptr) { 795 } 796 797 SkClipStack::Iter::Iter(const SkClipStack& stack, IterStart startLoc) 798 : fStack(&stack) { 799 this->reset(stack, startLoc); 800 } 801 802 const SkClipStack::Element* SkClipStack::Iter::next() { 803 return (const SkClipStack::Element*)fIter.next(); 804 } 805 806 const SkClipStack::Element* SkClipStack::Iter::prev() { 807 return (const SkClipStack::Element*)fIter.prev(); 808 } 809 810 const SkClipStack::Element* SkClipStack::Iter::skipToTopmost(SkClipOp op) { 811 812 if (nullptr == fStack) { 813 return nullptr; 814 } 815 816 fIter.reset(fStack->fDeque, SkDeque::Iter::kBack_IterStart); 817 818 const SkClipStack::Element* element = nullptr; 819 820 for (element = (const SkClipStack::Element*) fIter.prev(); 821 element; 822 element = (const SkClipStack::Element*) fIter.prev()) { 823 824 if (op == element->fOp) { 825 // The Deque's iterator is actually one pace ahead of the 826 // returned value. So while "element" is the element we want to 827 // return, the iterator is actually pointing at (and will 828 // return on the next "next" or "prev" call) the element 829 // in front of it in the deque. Bump the iterator forward a 830 // step so we get the expected result. 831 if (nullptr == fIter.next()) { 832 // The reverse iterator has run off the front of the deque 833 // (i.e., the "op" clip is the first clip) and can't 834 // recover. Reset the iterator to start at the front. 835 fIter.reset(fStack->fDeque, SkDeque::Iter::kFront_IterStart); 836 } 837 break; 838 } 839 } 840 841 if (nullptr == element) { 842 // There were no "op" clips 843 fIter.reset(fStack->fDeque, SkDeque::Iter::kFront_IterStart); 844 } 845 846 return this->next(); 847 } 848 849 void SkClipStack::Iter::reset(const SkClipStack& stack, IterStart startLoc) { 850 fStack = &stack; 851 fIter.reset(stack.fDeque, static_cast<SkDeque::Iter::IterStart>(startLoc)); 852 } 853 854 // helper method 855 void SkClipStack::getConservativeBounds(int offsetX, 856 int offsetY, 857 int maxWidth, 858 int maxHeight, 859 SkRect* devBounds, 860 bool* isIntersectionOfRects) const { 861 SkASSERT(devBounds); 862 863 devBounds->setLTRB(0, 0, 864 SkIntToScalar(maxWidth), SkIntToScalar(maxHeight)); 865 866 SkRect temp; 867 SkClipStack::BoundsType boundType; 868 869 // temp starts off in canvas space here 870 this->getBounds(&temp, &boundType, isIntersectionOfRects); 871 if (SkClipStack::kInsideOut_BoundsType == boundType) { 872 return; 873 } 874 875 // but is converted to device space here 876 temp.offset(SkIntToScalar(offsetX), SkIntToScalar(offsetY)); 877 878 if (!devBounds->intersect(temp)) { 879 devBounds->setEmpty(); 880 } 881 } 882 883 bool SkClipStack::isRRect(const SkRect& bounds, SkRRect* rrect, bool* aa) const { 884 // We limit to 5 elements. This means the back element will be bounds checked at most 4 times if 885 // it is an rrect. 886 int cnt = fDeque.count(); 887 if (!cnt || cnt > 5) { 888 return false; 889 } 890 const Element* back = static_cast<const Element*>(fDeque.back()); 891 if (back->getType() != SkClipStack::Element::kRect_Type && 892 back->getType() != SkClipStack::Element::kRRect_Type) { 893 return false; 894 } 895 if (back->getOp() == kReplace_SkClipOp) { 896 *rrect = back->asRRect(); 897 *aa = back->isAA(); 898 return true; 899 } 900 901 if (back->getOp() == kIntersect_SkClipOp) { 902 SkRect backBounds; 903 if (!backBounds.intersect(bounds, back->asRRect().rect())) { 904 return false; 905 } 906 if (cnt > 1) { 907 SkDeque::Iter iter(fDeque, SkDeque::Iter::kBack_IterStart); 908 SkAssertResult(static_cast<const Element*>(iter.prev()) == back); 909 while (const Element* prior = (const Element*)iter.prev()) { 910 if ((prior->getOp() != kIntersect_SkClipOp && 911 prior->getOp() != kReplace_SkClipOp) || 912 !prior->contains(backBounds)) { 913 return false; 914 } 915 if (prior->getOp() == kReplace_SkClipOp) { 916 break; 917 } 918 } 919 } 920 *rrect = back->asRRect(); 921 *aa = back->isAA(); 922 return true; 923 } 924 return false; 925 } 926 927 uint32_t SkClipStack::GetNextGenID() { 928 uint32_t id; 929 do { 930 id = static_cast<uint32_t>(sk_atomic_inc(&gGenID)); 931 } while (id < kFirstUnreservedGenID); 932 return id; 933 } 934 935 uint32_t SkClipStack::getTopmostGenID() const { 936 if (fDeque.empty()) { 937 return kWideOpenGenID; 938 } 939 940 const Element* back = static_cast<const Element*>(fDeque.back()); 941 if (kInsideOut_BoundsType == back->fFiniteBoundType && back->fFiniteBound.isEmpty()) { 942 return kWideOpenGenID; 943 } 944 945 return back->getGenID(); 946 } 947 948 #ifdef SK_DEBUG 949 void SkClipStack::Element::dump() const { 950 static const char* kTypeStrings[] = { 951 "empty", 952 "rect", 953 "rrect", 954 "path" 955 }; 956 static_assert(0 == kEmpty_Type, "type_str"); 957 static_assert(1 == kRect_Type, "type_str"); 958 static_assert(2 == kRRect_Type, "type_str"); 959 static_assert(3 == kPath_Type, "type_str"); 960 static_assert(SK_ARRAY_COUNT(kTypeStrings) == kTypeCnt, "type_str"); 961 962 static const char* kOpStrings[] = { 963 "difference", 964 "intersect", 965 "union", 966 "xor", 967 "reverse-difference", 968 "replace", 969 }; 970 static_assert(0 == static_cast<int>(kDifference_SkClipOp), "op_str"); 971 static_assert(1 == static_cast<int>(kIntersect_SkClipOp), "op_str"); 972 static_assert(2 == static_cast<int>(kUnion_SkClipOp), "op_str"); 973 static_assert(3 == static_cast<int>(kXOR_SkClipOp), "op_str"); 974 static_assert(4 == static_cast<int>(kReverseDifference_SkClipOp), "op_str"); 975 static_assert(5 == static_cast<int>(kReplace_SkClipOp), "op_str"); 976 static_assert(SK_ARRAY_COUNT(kOpStrings) == SkRegion::kOpCnt, "op_str"); 977 978 SkDebugf("Type: %s, Op: %s, AA: %s, Save Count: %d\n", kTypeStrings[fType], 979 kOpStrings[static_cast<int>(fOp)], (fDoAA ? "yes" : "no"), fSaveCount); 980 switch (fType) { 981 case kEmpty_Type: 982 SkDebugf("\n"); 983 break; 984 case kRect_Type: 985 this->getRect().dump(); 986 SkDebugf("\n"); 987 break; 988 case kRRect_Type: 989 this->getRRect().dump(); 990 SkDebugf("\n"); 991 break; 992 case kPath_Type: 993 this->getPath().dump(nullptr, true, false); 994 break; 995 } 996 } 997 998 void SkClipStack::dump() const { 999 B2TIter iter(*this); 1000 const Element* e; 1001 while ((e = iter.next())) { 1002 e->dump(); 1003 SkDebugf("\n"); 1004 } 1005 } 1006 #endif 1007