1 /* 2 * Copyright 2005 The Android Open Source Project 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 #ifndef SkRegion_DEFINED 9 #define SkRegion_DEFINED 10 11 #include "include/core/SkRect.h" 12 #include "include/private/base/SkAPI.h" 13 #include "include/private/base/SkAssert.h" 14 #include "include/private/base/SkDebug.h" 15 #include "include/private/base/SkTypeTraits.h" 16 17 #include <cstddef> 18 #include <cstdint> 19 #include <type_traits> 20 21 class SkPath; 22 23 /** \class SkRegion 24 SkRegion describes the set of pixels used to clip SkCanvas. SkRegion is compact, 25 efficiently storing a single integer rectangle, or a run length encoded array 26 of rectangles. SkRegion may reduce the current SkCanvas clip, or may be drawn as 27 one or more integer rectangles. SkRegion iterator returns the scan lines or 28 rectangles contained by it, optionally intersecting a bounding rectangle. 29 */ 30 class SK_API SkRegion { 31 typedef int32_t RunType; 32 public: 33 34 /** Constructs an empty SkRegion. SkRegion is set to empty bounds 35 at (0, 0) with zero width and height. 36 37 @return empty SkRegion 38 39 example: https://fiddle.skia.org/c/@Region_empty_constructor 40 */ 41 SkRegion(); 42 43 /** Constructs a copy of an existing region. 44 Copy constructor makes two regions identical by value. Internally, region and 45 the returned result share pointer values. The underlying SkRect array is 46 copied when modified. 47 48 Creating a SkRegion copy is very efficient and never allocates memory. 49 SkRegion are always copied by value from the interface; the underlying shared 50 pointers are not exposed. 51 52 @param region SkRegion to copy by value 53 @return copy of SkRegion 54 55 example: https://fiddle.skia.org/c/@Region_copy_const_SkRegion 56 */ 57 SkRegion(const SkRegion& region); 58 59 /** Constructs a rectangular SkRegion matching the bounds of rect. 60 61 @param rect bounds of constructed SkRegion 62 @return rectangular SkRegion 63 64 example: https://fiddle.skia.org/c/@Region_copy_const_SkIRect 65 */ 66 explicit SkRegion(const SkIRect& rect); 67 68 /** Releases ownership of any shared data and deletes data if SkRegion is sole owner. 69 70 example: https://fiddle.skia.org/c/@Region_destructor 71 */ 72 ~SkRegion(); 73 74 /** Constructs a copy of an existing region. 75 Makes two regions identical by value. Internally, region and 76 the returned result share pointer values. The underlying SkRect array is 77 copied when modified. 78 79 Creating a SkRegion copy is very efficient and never allocates memory. 80 SkRegion are always copied by value from the interface; the underlying shared 81 pointers are not exposed. 82 83 @param region SkRegion to copy by value 84 @return SkRegion to copy by value 85 86 example: https://fiddle.skia.org/c/@Region_copy_operator 87 */ 88 SkRegion& operator=(const SkRegion& region); 89 90 /** Compares SkRegion and other; returns true if they enclose exactly 91 the same area. 92 93 @param other SkRegion to compare 94 @return true if SkRegion pair are equivalent 95 96 example: https://fiddle.skia.org/c/@Region_equal1_operator 97 */ 98 bool operator==(const SkRegion& other) const; 99 100 /** Compares SkRegion and other; returns true if they do not enclose the same area. 101 102 @param other SkRegion to compare 103 @return true if SkRegion pair are not equivalent 104 */ 105 bool operator!=(const SkRegion& other) const { 106 return !(*this == other); 107 } 108 109 /** Sets SkRegion to src, and returns true if src bounds is not empty. 110 This makes SkRegion and src identical by value. Internally, 111 SkRegion and src share pointer values. The underlying SkRect array is 112 copied when modified. 113 114 Creating a SkRegion copy is very efficient and never allocates memory. 115 SkRegion are always copied by value from the interface; the underlying shared 116 pointers are not exposed. 117 118 @param src SkRegion to copy 119 @return copy of src 120 */ set(const SkRegion & src)121 bool set(const SkRegion& src) { 122 *this = src; 123 return !this->isEmpty(); 124 } 125 126 /** Exchanges SkIRect array of SkRegion and other. swap() internally exchanges pointers, 127 so it is lightweight and does not allocate memory. 128 129 swap() usage has largely been replaced by operator=(const SkRegion& region). 130 SkPath do not copy their content on assignment until they are written to, 131 making assignment as efficient as swap(). 132 133 @param other operator=(const SkRegion& region) set 134 135 example: https://fiddle.skia.org/c/@Region_swap 136 */ 137 void swap(SkRegion& other); 138 139 /** Returns true if SkRegion is empty. 140 Empty SkRegion has bounds width or height less than or equal to zero. 141 SkRegion() constructs empty SkRegion; setEmpty() 142 and setRect() with dimensionless data make SkRegion empty. 143 144 @return true if bounds has no width or height 145 */ isEmpty()146 bool isEmpty() const { return fRunHead == emptyRunHeadPtr(); } 147 148 /** Returns true if SkRegion is one SkIRect with positive dimensions. 149 150 @return true if SkRegion contains one SkIRect 151 */ isRect()152 bool isRect() const { return fRunHead == kRectRunHeadPtr; } 153 154 /** Returns true if SkRegion is described by more than one rectangle. 155 156 @return true if SkRegion contains more than one SkIRect 157 */ isComplex()158 bool isComplex() const { return !this->isEmpty() && !this->isRect(); } 159 160 /** Returns minimum and maximum axes values of SkIRect array. 161 Returns (0, 0, 0, 0) if SkRegion is empty. 162 163 @return combined bounds of all SkIRect elements 164 */ getBounds()165 const SkIRect& getBounds() const { return fBounds; } 166 167 /** Returns a value that increases with the number of 168 elements in SkRegion. Returns zero if SkRegion is empty. 169 Returns one if SkRegion equals SkIRect; otherwise, returns 170 value greater than one indicating that SkRegion is complex. 171 172 Call to compare SkRegion for relative complexity. 173 174 @return relative complexity 175 176 example: https://fiddle.skia.org/c/@Region_computeRegionComplexity 177 */ 178 int computeRegionComplexity() const; 179 180 /** Appends outline of SkRegion to path. 181 Returns true if SkRegion is not empty; otherwise, returns false, and leaves path 182 unmodified. 183 184 @param path SkPath to append to 185 @return true if path changed 186 187 example: https://fiddle.skia.org/c/@Region_getBoundaryPath 188 */ 189 bool getBoundaryPath(SkPath* path) const; 190 191 /** Constructs an empty SkRegion. SkRegion is set to empty bounds 192 at (0, 0) with zero width and height. Always returns false. 193 194 @return false 195 196 example: https://fiddle.skia.org/c/@Region_setEmpty 197 */ 198 bool setEmpty(); 199 200 /** Constructs a rectangular SkRegion matching the bounds of rect. 201 If rect is empty, constructs empty and returns false. 202 203 @param rect bounds of constructed SkRegion 204 @return true if rect is not empty 205 206 example: https://fiddle.skia.org/c/@Region_setRect 207 */ 208 bool setRect(const SkIRect& rect); 209 210 /** Constructs SkRegion as the union of SkIRect in rects array. If count is 211 zero, constructs empty SkRegion. Returns false if constructed SkRegion is empty. 212 213 May be faster than repeated calls to op(). 214 215 @param rects array of SkIRect 216 @param count array size 217 @return true if constructed SkRegion is not empty 218 219 example: https://fiddle.skia.org/c/@Region_setRects 220 */ 221 bool setRects(const SkIRect rects[], int count); 222 223 /** Constructs a copy of an existing region. 224 Makes two regions identical by value. Internally, region and 225 the returned result share pointer values. The underlying SkRect array is 226 copied when modified. 227 228 Creating a SkRegion copy is very efficient and never allocates memory. 229 SkRegion are always copied by value from the interface; the underlying shared 230 pointers are not exposed. 231 232 @param region SkRegion to copy by value 233 @return SkRegion to copy by value 234 235 example: https://fiddle.skia.org/c/@Region_setRegion 236 */ 237 bool setRegion(const SkRegion& region); 238 239 /** Constructs SkRegion to match outline of path within clip. 240 Returns false if constructed SkRegion is empty. 241 242 Constructed SkRegion draws the same pixels as path through clip when 243 anti-aliasing is disabled. 244 245 @param path SkPath providing outline 246 @param clip SkRegion containing path 247 @return true if constructed SkRegion is not empty 248 249 example: https://fiddle.skia.org/c/@Region_setPath 250 */ 251 bool setPath(const SkPath& path, const SkRegion& clip); 252 253 /** Returns true if SkRegion intersects rect. 254 Returns false if either rect or SkRegion is empty, or do not intersect. 255 256 @param rect SkIRect to intersect 257 @return true if rect and SkRegion have area in common 258 259 example: https://fiddle.skia.org/c/@Region_intersects 260 */ 261 bool intersects(const SkIRect& rect) const; 262 263 /** Returns true if SkRegion intersects other. 264 Returns false if either other or SkRegion is empty, or do not intersect. 265 266 @param other SkRegion to intersect 267 @return true if other and SkRegion have area in common 268 269 example: https://fiddle.skia.org/c/@Region_intersects_2 270 */ 271 bool intersects(const SkRegion& other) const; 272 273 /** Returns true if SkIPoint (x, y) is inside SkRegion. 274 Returns false if SkRegion is empty. 275 276 @param x test SkIPoint x-coordinate 277 @param y test SkIPoint y-coordinate 278 @return true if (x, y) is inside SkRegion 279 280 example: https://fiddle.skia.org/c/@Region_contains 281 */ 282 bool contains(int32_t x, int32_t y) const; 283 284 /** Returns true if other is completely inside SkRegion. 285 Returns false if SkRegion or other is empty. 286 287 @param other SkIRect to contain 288 @return true if other is inside SkRegion 289 290 example: https://fiddle.skia.org/c/@Region_contains_2 291 */ 292 bool contains(const SkIRect& other) const; 293 294 /** Returns true if other is completely inside SkRegion. 295 Returns false if SkRegion or other is empty. 296 297 @param other SkRegion to contain 298 @return true if other is inside SkRegion 299 300 example: https://fiddle.skia.org/c/@Region_contains_3 301 */ 302 bool contains(const SkRegion& other) const; 303 304 /** Returns true if SkRegion is a single rectangle and contains r. 305 May return false even though SkRegion contains r. 306 307 @param r SkIRect to contain 308 @return true quickly if r points are equal or inside 309 */ quickContains(const SkIRect & r)310 bool quickContains(const SkIRect& r) const { 311 SkASSERT(this->isEmpty() == fBounds.isEmpty()); // valid region 312 313 return r.fLeft < r.fRight && r.fTop < r.fBottom && 314 fRunHead == kRectRunHeadPtr && // this->isRect() 315 /* fBounds.contains(left, top, right, bottom); */ 316 fBounds.fLeft <= r.fLeft && fBounds.fTop <= r.fTop && 317 fBounds.fRight >= r.fRight && fBounds.fBottom >= r.fBottom; 318 } 319 320 /** Returns true if SkRegion does not intersect rect. 321 Returns true if rect is empty or SkRegion is empty. 322 May return false even though SkRegion does not intersect rect. 323 324 @param rect SkIRect to intersect 325 @return true if rect does not intersect 326 */ quickReject(const SkIRect & rect)327 bool quickReject(const SkIRect& rect) const { 328 return this->isEmpty() || rect.isEmpty() || 329 !SkIRect::Intersects(fBounds, rect); 330 } 331 332 /** Returns true if SkRegion does not intersect rgn. 333 Returns true if rgn is empty or SkRegion is empty. 334 May return false even though SkRegion does not intersect rgn. 335 336 @param rgn SkRegion to intersect 337 @return true if rgn does not intersect 338 */ quickReject(const SkRegion & rgn)339 bool quickReject(const SkRegion& rgn) const { 340 return this->isEmpty() || rgn.isEmpty() || 341 !SkIRect::Intersects(fBounds, rgn.fBounds); 342 } 343 344 /** Offsets SkRegion by ivector (dx, dy). Has no effect if SkRegion is empty. 345 346 @param dx x-axis offset 347 @param dy y-axis offset 348 */ translate(int dx,int dy)349 void translate(int dx, int dy) { this->translate(dx, dy, this); } 350 351 /** Offsets SkRegion by ivector (dx, dy), writing result to dst. SkRegion may be passed 352 as dst parameter, translating SkRegion in place. Has no effect if dst is nullptr. 353 If SkRegion is empty, sets dst to empty. 354 355 @param dx x-axis offset 356 @param dy y-axis offset 357 @param dst translated result 358 359 example: https://fiddle.skia.org/c/@Region_translate_2 360 */ 361 void translate(int dx, int dy, SkRegion* dst) const; 362 363 /** \enum SkRegion::Op 364 The logical operations that can be performed when combining two SkRegion. 365 */ 366 enum Op { 367 kDifference_Op, //!< target minus operand 368 kIntersect_Op, //!< target intersected with operand 369 kUnion_Op, //!< target unioned with operand 370 kXOR_Op, //!< target exclusive or with operand 371 kReverseDifference_Op, //!< operand minus target 372 kReplace_Op, //!< replace target with operand 373 kLastOp = kReplace_Op, //!< last operator 374 }; 375 376 static const int kOpCnt = kLastOp + 1; 377 378 /** Replaces SkRegion with the result of SkRegion op rect. 379 Returns true if replaced SkRegion is not empty. 380 381 @param rect SkIRect operand 382 @return false if result is empty 383 */ op(const SkIRect & rect,Op op)384 bool op(const SkIRect& rect, Op op) { 385 if (this->isRect() && kIntersect_Op == op) { 386 if (!fBounds.intersect(rect)) { 387 return this->setEmpty(); 388 } 389 return true; 390 } 391 return this->op(*this, rect, op); 392 } 393 394 /** Replaces SkRegion with the result of SkRegion op rgn. 395 Returns true if replaced SkRegion is not empty. 396 397 @param rgn SkRegion operand 398 @return false if result is empty 399 */ op(const SkRegion & rgn,Op op)400 bool op(const SkRegion& rgn, Op op) { return this->op(*this, rgn, op); } 401 402 /** Replaces SkRegion with the result of rect op rgn. 403 Returns true if replaced SkRegion is not empty. 404 405 @param rect SkIRect operand 406 @param rgn SkRegion operand 407 @return false if result is empty 408 409 example: https://fiddle.skia.org/c/@Region_op_4 410 */ 411 bool op(const SkIRect& rect, const SkRegion& rgn, Op op); 412 413 /** Replaces SkRegion with the result of rgn op rect. 414 Returns true if replaced SkRegion is not empty. 415 416 @param rgn SkRegion operand 417 @param rect SkIRect operand 418 @return false if result is empty 419 420 example: https://fiddle.skia.org/c/@Region_op_5 421 */ 422 bool op(const SkRegion& rgn, const SkIRect& rect, Op op); 423 424 /** Replaces SkRegion with the result of rgna op rgnb. 425 Returns true if replaced SkRegion is not empty. 426 427 @param rgna SkRegion operand 428 @param rgnb SkRegion operand 429 @return false if result is empty 430 431 example: https://fiddle.skia.org/c/@Region_op_6 432 */ 433 bool op(const SkRegion& rgna, const SkRegion& rgnb, Op op); 434 435 #ifdef SK_BUILD_FOR_ANDROID_FRAMEWORK 436 /** Private. Android framework only. 437 438 @return string representation of SkRegion 439 */ 440 char* toString(); 441 #endif 442 443 /** \class SkRegion::Iterator 444 Returns sequence of rectangles, sorted along y-axis, then x-axis, that make 445 up SkRegion. 446 */ 447 class SK_API Iterator { 448 public: 449 450 /** Initializes SkRegion::Iterator with an empty SkRegion. done() on SkRegion::Iterator 451 returns true. 452 Call reset() to initialized SkRegion::Iterator at a later time. 453 454 @return empty SkRegion iterator 455 */ Iterator()456 Iterator() : fRgn(nullptr), fDone(true) {} 457 458 /** Sets SkRegion::Iterator to return elements of SkIRect array in region. 459 460 @param region SkRegion to iterate 461 @return SkRegion iterator 462 463 example: https://fiddle.skia.org/c/@Region_Iterator_copy_const_SkRegion 464 */ 465 Iterator(const SkRegion& region); 466 467 /** SkPoint SkRegion::Iterator to start of SkRegion. 468 Returns true if SkRegion was set; otherwise, returns false. 469 470 @return true if SkRegion was set 471 472 example: https://fiddle.skia.org/c/@Region_Iterator_rewind 473 */ 474 bool rewind(); 475 476 /** Resets iterator, using the new SkRegion. 477 478 @param region SkRegion to iterate 479 480 example: https://fiddle.skia.org/c/@Region_Iterator_reset 481 */ 482 void reset(const SkRegion& region); 483 484 /** Returns true if SkRegion::Iterator is pointing to final SkIRect in SkRegion. 485 486 @return true if data parsing is complete 487 */ done()488 bool done() const { return fDone; } 489 490 /** Advances SkRegion::Iterator to next SkIRect in SkRegion if it is not done. 491 492 example: https://fiddle.skia.org/c/@Region_Iterator_next 493 */ 494 void next(); 495 496 /** Returns SkIRect element in SkRegion. Does not return predictable results if SkRegion 497 is empty. 498 499 @return part of SkRegion as SkIRect 500 */ rect()501 const SkIRect& rect() const { return fRect; } 502 503 /** Returns SkRegion if set; otherwise, returns nullptr. 504 505 @return iterated SkRegion 506 */ rgn()507 const SkRegion* rgn() const { return fRgn; } 508 509 private: 510 const SkRegion* fRgn; 511 const SkRegion::RunType* fRuns; 512 SkIRect fRect = {0, 0, 0, 0}; 513 bool fDone; 514 }; 515 516 /** \class SkRegion::Cliperator 517 Returns the sequence of rectangles, sorted along y-axis, then x-axis, that make 518 up SkRegion intersected with the specified clip rectangle. 519 */ 520 class SK_API Cliperator { 521 public: 522 523 /** Sets SkRegion::Cliperator to return elements of SkIRect array in SkRegion within clip. 524 525 @param region SkRegion to iterate 526 @param clip bounds of iteration 527 @return SkRegion iterator 528 529 example: https://fiddle.skia.org/c/@Region_Cliperator_const_SkRegion_const_SkIRect 530 */ 531 Cliperator(const SkRegion& region, const SkIRect& clip); 532 533 /** Returns true if SkRegion::Cliperator is pointing to final SkIRect in SkRegion. 534 535 @return true if data parsing is complete 536 */ done()537 bool done() { return fDone; } 538 539 /** Advances iterator to next SkIRect in SkRegion contained by clip. 540 541 example: https://fiddle.skia.org/c/@Region_Cliperator_next 542 */ 543 void next(); 544 545 /** Returns SkIRect element in SkRegion, intersected with clip passed to 546 SkRegion::Cliperator constructor. Does not return predictable results if SkRegion 547 is empty. 548 549 @return part of SkRegion inside clip as SkIRect 550 */ rect()551 const SkIRect& rect() const { return fRect; } 552 553 private: 554 Iterator fIter; 555 SkIRect fClip; 556 SkIRect fRect = {0, 0, 0, 0}; 557 bool fDone; 558 }; 559 560 /** \class SkRegion::Spanerator 561 Returns the line segment ends within SkRegion that intersect a horizontal line. 562 */ 563 class Spanerator { 564 public: 565 566 /** Sets SkRegion::Spanerator to return line segments in SkRegion on scan line. 567 568 @param region SkRegion to iterate 569 @param y horizontal line to intersect 570 @param left bounds of iteration 571 @param right bounds of iteration 572 @return SkRegion iterator 573 574 example: https://fiddle.skia.org/c/@Region_Spanerator_const_SkRegion_int_int_int 575 */ 576 Spanerator(const SkRegion& region, int y, int left, int right); 577 578 /** Advances iterator to next span intersecting SkRegion within line segment provided 579 in constructor. Returns true if interval was found. 580 581 @param left pointer to span start; may be nullptr 582 @param right pointer to span end; may be nullptr 583 @return true if interval was found 584 585 example: https://fiddle.skia.org/c/@Region_Spanerator_next 586 */ 587 bool next(int* left, int* right); 588 589 private: 590 const SkRegion::RunType* fRuns; 591 int fLeft, fRight; 592 bool fDone; 593 }; 594 595 /** Writes SkRegion to buffer, and returns number of bytes written. 596 If buffer is nullptr, returns number number of bytes that would be written. 597 598 @param buffer storage for binary data 599 @return size of SkRegion 600 601 example: https://fiddle.skia.org/c/@Region_writeToMemory 602 */ 603 size_t writeToMemory(void* buffer) const; 604 605 /** Constructs SkRegion from buffer of size length. Returns bytes read. 606 Returned value will be multiple of four or zero if length was too small. 607 608 @param buffer storage for binary data 609 @param length size of buffer 610 @return bytes read 611 612 example: https://fiddle.skia.org/c/@Region_readFromMemory 613 */ 614 size_t readFromMemory(const void* buffer, size_t length); 615 616 using sk_is_trivially_relocatable = std::true_type; 617 618 private: 619 static constexpr int kOpCount = kReplace_Op + 1; 620 621 // T 622 // [B N L R S] 623 // S 624 static constexpr int kRectRegionRuns = 7; 625 626 struct RunHead; 627 emptyRunHeadPtr()628 static RunHead* emptyRunHeadPtr() { return (SkRegion::RunHead*) -1; } 629 static constexpr RunHead* kRectRunHeadPtr = nullptr; 630 631 // allocate space for count runs 632 void allocateRuns(int count); 633 void allocateRuns(int count, int ySpanCount, int intervalCount); 634 void allocateRuns(const RunHead& src); 635 636 SkDEBUGCODE(void dump() const;) 637 638 SkIRect fBounds; 639 RunHead* fRunHead; 640 641 static_assert(::sk_is_trivially_relocatable<decltype(fBounds)>::value); 642 static_assert(::sk_is_trivially_relocatable<decltype(fRunHead)>::value); 643 644 void freeRuns(); 645 646 /** 647 * Return the runs from this region, consing up fake runs if the region 648 * is empty or a rect. In those 2 cases, we use tmpStorage to hold the 649 * run data. 650 */ 651 const RunType* getRuns(RunType tmpStorage[], int* intervals) const; 652 653 // This is called with runs[] that do not yet have their interval-count 654 // field set on each scanline. That is computed as part of this call 655 // (inside ComputeRunBounds). 656 bool setRuns(RunType runs[], int count); 657 658 int count_runtype_values(int* itop, int* ibot) const; 659 660 bool isValid() const; 661 662 static void BuildRectRuns(const SkIRect& bounds, 663 RunType runs[kRectRegionRuns]); 664 665 // If the runs define a simple rect, return true and set bounds to that 666 // rect. If not, return false and ignore bounds. 667 static bool RunsAreARect(const SkRegion::RunType runs[], int count, 668 SkIRect* bounds); 669 670 /** 671 * If the last arg is null, just return if the result is non-empty, 672 * else store the result in the last arg. 673 */ 674 static bool Oper(const SkRegion&, const SkRegion&, SkRegion::Op, SkRegion*); 675 676 friend struct RunHead; 677 friend class Iterator; 678 friend class Spanerator; 679 friend class SkRegionPriv; 680 friend class SkRgnBuilder; 681 friend class SkFlatRegion; 682 }; 683 684 #endif 685