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