Home | History | Annotate | Download | only in core 
      1 /*
      2  * Copyright 2006 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 #include "SkRegionPriv.h"
      9 #include "SkBlitter.h"
     10 #include "SkScan.h"
     11 #include "SkTSort.h"
     12 #include "SkTDArray.h"
     13 #include "SkPath.h"
     14 
     15 // The rgnbuilder caller *seems* to pass short counts, possible often seens early failure, so
     16 // we may not want to promote this to a "std" routine just yet.
     17 static bool sk_memeq32(const int32_t* SK_RESTRICT a, const int32_t* SK_RESTRICT b, int count) {
     18     for (int i = 0; i < count; ++i) {
     19         if (a[i] != b[i]) {
     20             return false;
     21         }
     22     }
     23     return true;
     24 }
     25 
     26 class SkRgnBuilder : public SkBlitter {
     27 public:
     28     SkRgnBuilder();
     29     virtual ~SkRgnBuilder();
     30 
     31     // returns true if it could allocate the working storage needed
     32     bool init(int maxHeight, int maxTransitions, bool pathIsInverse);
     33 
     34     void done() {
     35         if (fCurrScanline != nullptr) {
     36             fCurrScanline->fXCount = (SkRegion::RunType)((int)(fCurrXPtr - fCurrScanline->firstX()));
     37             if (!this->collapsWithPrev()) { // flush the last line
     38                 fCurrScanline = fCurrScanline->nextScanline();
     39             }
     40         }
     41     }
     42 
     43     int     computeRunCount() const;
     44     void    copyToRect(SkIRect*) const;
     45     void    copyToRgn(SkRegion::RunType runs[]) const;
     46 
     47     void blitH(int x, int y, int width) override;
     48 
     49 #ifdef SK_DEBUG
     50     void dump() const {
     51         SkDebugf("SkRgnBuilder: Top = %d\n", fTop);
     52         const Scanline* line = (Scanline*)fStorage;
     53         while (line < fCurrScanline) {
     54             SkDebugf("SkRgnBuilder::Scanline: LastY=%d, fXCount=%d", line->fLastY, line->fXCount);
     55             for (int i = 0; i < line->fXCount; i++) {
     56                 SkDebugf(" %d", line->firstX()[i]);
     57             }
     58             SkDebugf("\n");
     59 
     60             line = line->nextScanline();
     61         }
     62     }
     63 #endif
     64 private:
     65     /*
     66      *  Scanline mimics a row in the region, nearly. A row in a region is:
     67      *      [Bottom IntervalCount [L R]... Sentinel]
     68      *  while a Scanline is
     69      *      [LastY XCount [L R]... uninitialized]
     70      *  The two are the same length (which is good), but we have to transmute
     71      *  the scanline a little when we convert it to a region-row.
     72      *
     73      *  Potentially we could recode this to exactly match the row format, in
     74      *  which case copyToRgn() could be a single memcpy. Not sure that is worth
     75      *  the effort.
     76      */
     77     struct Scanline {
     78         SkRegion::RunType fLastY;
     79         SkRegion::RunType fXCount;
     80 
     81         SkRegion::RunType* firstX() const { return (SkRegion::RunType*)(this + 1); }
     82         Scanline* nextScanline() const {
     83             // add final +1 for the x-sentinel
     84             return (Scanline*)((SkRegion::RunType*)(this + 1) + fXCount + 1);
     85         }
     86     };
     87     SkRegion::RunType*  fStorage;
     88     Scanline*           fCurrScanline;
     89     Scanline*           fPrevScanline;
     90     //  points at next avialable x[] in fCurrScanline
     91     SkRegion::RunType*  fCurrXPtr;
     92     SkRegion::RunType   fTop;           // first Y value
     93 
     94     int fStorageCount;
     95 
     96     bool collapsWithPrev() {
     97         if (fPrevScanline != nullptr &&
     98             fPrevScanline->fLastY + 1 == fCurrScanline->fLastY &&
     99             fPrevScanline->fXCount == fCurrScanline->fXCount &&
    100             sk_memeq32(fPrevScanline->firstX(), fCurrScanline->firstX(), fCurrScanline->fXCount))
    101         {
    102             // update the height of fPrevScanline
    103             fPrevScanline->fLastY = fCurrScanline->fLastY;
    104             return true;
    105         }
    106         return false;
    107     }
    108 };
    109 
    110 SkRgnBuilder::SkRgnBuilder()
    111     : fStorage(nullptr) {
    112 }
    113 
    114 SkRgnBuilder::~SkRgnBuilder() {
    115     sk_free(fStorage);
    116 }
    117 
    118 bool SkRgnBuilder::init(int maxHeight, int maxTransitions, bool pathIsInverse) {
    119     if ((maxHeight | maxTransitions) < 0) {
    120         return false;
    121     }
    122 
    123     if (pathIsInverse) {
    124         // allow for additional X transitions to "invert" each scanline
    125         // [ L' ... normal transitions ... R' ]
    126         //
    127         maxTransitions += 2;
    128     }
    129 
    130     // compute the count with +1 and +3 slop for the working buffer
    131     int64_t count = sk_64_mul(maxHeight + 1, 3 + maxTransitions);
    132 
    133     if (pathIsInverse) {
    134         // allow for two "empty" rows for the top and bottom
    135         //      [ Y, 1, L, R, S] == 5 (*2 for top and bottom)
    136         count += 10;
    137     }
    138 
    139     if (count < 0 || !sk_64_isS32(count)) {
    140         return false;
    141     }
    142     fStorageCount = sk_64_asS32(count);
    143 
    144     int64_t size = sk_64_mul(fStorageCount, sizeof(SkRegion::RunType));
    145     if (size < 0 || !sk_64_isS32(size)) {
    146         return false;
    147     }
    148 
    149     fStorage = (SkRegion::RunType*)sk_malloc_flags(sk_64_asS32(size), 0);
    150     if (nullptr == fStorage) {
    151         return false;
    152     }
    153 
    154     fCurrScanline = nullptr;    // signal empty collection
    155     fPrevScanline = nullptr;    // signal first scanline
    156     return true;
    157 }
    158 
    159 void SkRgnBuilder::blitH(int x, int y, int width) {
    160     if (fCurrScanline == nullptr) {  // first time
    161         fTop = (SkRegion::RunType)(y);
    162         fCurrScanline = (Scanline*)fStorage;
    163         fCurrScanline->fLastY = (SkRegion::RunType)(y);
    164         fCurrXPtr = fCurrScanline->firstX();
    165     } else {
    166         SkASSERT(y >= fCurrScanline->fLastY);
    167 
    168         if (y > fCurrScanline->fLastY) {
    169             // if we get here, we're done with fCurrScanline
    170             fCurrScanline->fXCount = (SkRegion::RunType)((int)(fCurrXPtr - fCurrScanline->firstX()));
    171 
    172             int prevLastY = fCurrScanline->fLastY;
    173             if (!this->collapsWithPrev()) {
    174                 fPrevScanline = fCurrScanline;
    175                 fCurrScanline = fCurrScanline->nextScanline();
    176 
    177             }
    178             if (y - 1 > prevLastY) {  // insert empty run
    179                 fCurrScanline->fLastY = (SkRegion::RunType)(y - 1);
    180                 fCurrScanline->fXCount = 0;
    181                 fCurrScanline = fCurrScanline->nextScanline();
    182             }
    183             // setup for the new curr line
    184             fCurrScanline->fLastY = (SkRegion::RunType)(y);
    185             fCurrXPtr = fCurrScanline->firstX();
    186         }
    187     }
    188     //  check if we should extend the current run, or add a new one
    189     if (fCurrXPtr > fCurrScanline->firstX() && fCurrXPtr[-1] == x) {
    190         fCurrXPtr[-1] = (SkRegion::RunType)(x + width);
    191     } else {
    192         fCurrXPtr[0] = (SkRegion::RunType)(x);
    193         fCurrXPtr[1] = (SkRegion::RunType)(x + width);
    194         fCurrXPtr += 2;
    195     }
    196     SkASSERT(fCurrXPtr - fStorage < fStorageCount);
    197 }
    198 
    199 int SkRgnBuilder::computeRunCount() const {
    200     if (fCurrScanline == nullptr) {
    201         return 0;
    202     }
    203 
    204     const SkRegion::RunType*  line = fStorage;
    205     const SkRegion::RunType*  stop = (const SkRegion::RunType*)fCurrScanline;
    206 
    207     return 2 + (int)(stop - line);
    208 }
    209 
    210 void SkRgnBuilder::copyToRect(SkIRect* r) const {
    211     SkASSERT(fCurrScanline != nullptr);
    212     // A rect's scanline is [bottom intervals left right sentinel] == 5
    213     SkASSERT((const SkRegion::RunType*)fCurrScanline - fStorage == 5);
    214 
    215     const Scanline* line = (const Scanline*)fStorage;
    216     SkASSERT(line->fXCount == 2);
    217 
    218     r->set(line->firstX()[0], fTop, line->firstX()[1], line->fLastY + 1);
    219 }
    220 
    221 void SkRgnBuilder::copyToRgn(SkRegion::RunType runs[]) const {
    222     SkASSERT(fCurrScanline != nullptr);
    223     SkASSERT((const SkRegion::RunType*)fCurrScanline - fStorage > 4);
    224 
    225     const Scanline* line = (const Scanline*)fStorage;
    226     const Scanline* stop = fCurrScanline;
    227 
    228     *runs++ = fTop;
    229     do {
    230         *runs++ = (SkRegion::RunType)(line->fLastY + 1);
    231         int count = line->fXCount;
    232         *runs++ = count >> 1;   // intervalCount
    233         if (count) {
    234             memcpy(runs, line->firstX(), count * sizeof(SkRegion::RunType));
    235             runs += count;
    236         }
    237         *runs++ = SkRegion::kRunTypeSentinel;
    238         line = line->nextScanline();
    239     } while (line < stop);
    240     SkASSERT(line == stop);
    241     *runs = SkRegion::kRunTypeSentinel;
    242 }
    243 
    244 static unsigned verb_to_initial_last_index(unsigned verb) {
    245     static const uint8_t gPathVerbToInitialLastIndex[] = {
    246         0,  //  kMove_Verb
    247         1,  //  kLine_Verb
    248         2,  //  kQuad_Verb
    249         2,  //  kConic_Verb
    250         3,  //  kCubic_Verb
    251         0,  //  kClose_Verb
    252         0   //  kDone_Verb
    253     };
    254     SkASSERT((unsigned)verb < SK_ARRAY_COUNT(gPathVerbToInitialLastIndex));
    255     return gPathVerbToInitialLastIndex[verb];
    256 }
    257 
    258 static unsigned verb_to_max_edges(unsigned verb) {
    259     static const uint8_t gPathVerbToMaxEdges[] = {
    260         0,  //  kMove_Verb
    261         1,  //  kLine_Verb
    262         2,  //  kQuad_VerbB
    263         2,  //  kConic_VerbB
    264         3,  //  kCubic_Verb
    265         0,  //  kClose_Verb
    266         0   //  kDone_Verb
    267     };
    268     SkASSERT((unsigned)verb < SK_ARRAY_COUNT(gPathVerbToMaxEdges));
    269     return gPathVerbToMaxEdges[verb];
    270 }
    271 
    272 // If returns 0, ignore itop and ibot
    273 static int count_path_runtype_values(const SkPath& path, int* itop, int* ibot) {
    274     SkPath::Iter    iter(path, true);
    275     SkPoint         pts[4];
    276     SkPath::Verb    verb;
    277 
    278     int maxEdges = 0;
    279     SkScalar    top = SkIntToScalar(SK_MaxS16);
    280     SkScalar    bot = SkIntToScalar(SK_MinS16);
    281 
    282     while ((verb = iter.next(pts, false)) != SkPath::kDone_Verb) {
    283         maxEdges += verb_to_max_edges(verb);
    284 
    285         int lastIndex = verb_to_initial_last_index(verb);
    286         if (lastIndex > 0) {
    287             for (int i = 1; i <= lastIndex; i++) {
    288                 if (top > pts[i].fY) {
    289                     top = pts[i].fY;
    290                 } else if (bot < pts[i].fY) {
    291                     bot = pts[i].fY;
    292                 }
    293             }
    294         } else if (SkPath::kMove_Verb == verb) {
    295             if (top > pts[0].fY) {
    296                 top = pts[0].fY;
    297             } else if (bot < pts[0].fY) {
    298                 bot = pts[0].fY;
    299             }
    300         }
    301     }
    302     if (0 == maxEdges) {
    303         return 0;   // we have only moves+closes
    304     }
    305 
    306     SkASSERT(top <= bot);
    307     *itop = SkScalarRoundToInt(top);
    308     *ibot = SkScalarRoundToInt(bot);
    309     return maxEdges;
    310 }
    311 
    312 static bool check_inverse_on_empty_return(SkRegion* dst, const SkPath& path, const SkRegion& clip) {
    313     if (path.isInverseFillType()) {
    314         return dst->set(clip);
    315     } else {
    316         return dst->setEmpty();
    317     }
    318 }
    319 
    320 bool SkRegion::setPath(const SkPath& path, const SkRegion& clip) {
    321     SkDEBUGCODE(this->validate();)
    322 
    323     if (clip.isEmpty()) {
    324         return this->setEmpty();
    325     }
    326 
    327     if (path.isEmpty()) {
    328         return check_inverse_on_empty_return(this, path, clip);
    329     }
    330 
    331     //  compute worst-case rgn-size for the path
    332     int pathTop, pathBot;
    333     int pathTransitions = count_path_runtype_values(path, &pathTop, &pathBot);
    334     if (0 == pathTransitions) {
    335         return check_inverse_on_empty_return(this, path, clip);
    336     }
    337 
    338     int clipTop, clipBot;
    339     int clipTransitions = clip.count_runtype_values(&clipTop, &clipBot);
    340 
    341     int top = SkMax32(pathTop, clipTop);
    342     int bot = SkMin32(pathBot, clipBot);
    343     if (top >= bot) {
    344         return check_inverse_on_empty_return(this, path, clip);
    345     }
    346 
    347     SkRgnBuilder builder;
    348 
    349     if (!builder.init(bot - top,
    350                       SkMax32(pathTransitions, clipTransitions),
    351                       path.isInverseFillType())) {
    352         // can't allocate working space, so return false
    353         return this->setEmpty();
    354     }
    355 
    356     SkScan::FillPath(path, clip, &builder);
    357     builder.done();
    358 
    359     int count = builder.computeRunCount();
    360     if (count == 0) {
    361         return this->setEmpty();
    362     } else if (count == kRectRegionRuns) {
    363         builder.copyToRect(&fBounds);
    364         this->setRect(fBounds);
    365     } else {
    366         SkRegion tmp;
    367 
    368         tmp.fRunHead = RunHead::Alloc(count);
    369         builder.copyToRgn(tmp.fRunHead->writable_runs());
    370         tmp.fRunHead->computeRunBounds(&tmp.fBounds);
    371         this->swap(tmp);
    372     }
    373     SkDEBUGCODE(this->validate();)
    374     return true;
    375 }
    376 
    377 /////////////////////////////////////////////////////////////////////////////////////////////////
    378 /////////////////////////////////////////////////////////////////////////////////////////////////
    379 
    380 struct Edge {
    381     enum {
    382         kY0Link = 0x01,
    383         kY1Link = 0x02,
    384 
    385         kCompleteLink = (kY0Link | kY1Link)
    386     };
    387 
    388     SkRegion::RunType fX;
    389     SkRegion::RunType fY0, fY1;
    390     uint8_t fFlags;
    391     Edge*   fNext;
    392 
    393     void set(int x, int y0, int y1) {
    394         SkASSERT(y0 != y1);
    395 
    396         fX = (SkRegion::RunType)(x);
    397         fY0 = (SkRegion::RunType)(y0);
    398         fY1 = (SkRegion::RunType)(y1);
    399         fFlags = 0;
    400         SkDEBUGCODE(fNext = nullptr;)
    401     }
    402 
    403     int top() const {
    404         return SkFastMin32(fY0, fY1);
    405     }
    406 };
    407 
    408 static void find_link(Edge* base, Edge* stop) {
    409     SkASSERT(base < stop);
    410 
    411     if (base->fFlags == Edge::kCompleteLink) {
    412         SkASSERT(base->fNext);
    413         return;
    414     }
    415 
    416     SkASSERT(base + 1 < stop);
    417 
    418     int y0 = base->fY0;
    419     int y1 = base->fY1;
    420 
    421     Edge* e = base;
    422     if ((base->fFlags & Edge::kY0Link) == 0) {
    423         for (;;) {
    424             e += 1;
    425             if ((e->fFlags & Edge::kY1Link) == 0 && y0 == e->fY1) {
    426                 SkASSERT(nullptr == e->fNext);
    427                 e->fNext = base;
    428                 e->fFlags = SkToU8(e->fFlags | Edge::kY1Link);
    429                 break;
    430             }
    431         }
    432     }
    433 
    434     e = base;
    435     if ((base->fFlags & Edge::kY1Link) == 0) {
    436         for (;;) {
    437             e += 1;
    438             if ((e->fFlags & Edge::kY0Link) == 0 && y1 == e->fY0) {
    439                 SkASSERT(nullptr == base->fNext);
    440                 base->fNext = e;
    441                 e->fFlags = SkToU8(e->fFlags | Edge::kY0Link);
    442                 break;
    443             }
    444         }
    445     }
    446 
    447     base->fFlags = Edge::kCompleteLink;
    448 }
    449 
    450 static int extract_path(Edge* edge, Edge* stop, SkPath* path) {
    451     while (0 == edge->fFlags) {
    452         edge++; // skip over "used" edges
    453     }
    454 
    455     SkASSERT(edge < stop);
    456 
    457     Edge* base = edge;
    458     Edge* prev = edge;
    459     edge = edge->fNext;
    460     SkASSERT(edge != base);
    461 
    462     int count = 1;
    463     path->moveTo(SkIntToScalar(prev->fX), SkIntToScalar(prev->fY0));
    464     prev->fFlags = 0;
    465     do {
    466         if (prev->fX != edge->fX || prev->fY1 != edge->fY0) { // skip collinear
    467             path->lineTo(SkIntToScalar(prev->fX), SkIntToScalar(prev->fY1));    // V
    468             path->lineTo(SkIntToScalar(edge->fX), SkIntToScalar(edge->fY0));    // H
    469         }
    470         prev = edge;
    471         edge = edge->fNext;
    472         count += 1;
    473         prev->fFlags = 0;
    474     } while (edge != base);
    475     path->lineTo(SkIntToScalar(prev->fX), SkIntToScalar(prev->fY1));    // V
    476     path->close();
    477     return count;
    478 }
    479 
    480 struct EdgeLT {
    481     bool operator()(const Edge& a, const Edge& b) const {
    482         return (a.fX == b.fX) ? a.top() < b.top() : a.fX < b.fX;
    483     }
    484 };
    485 
    486 bool SkRegion::getBoundaryPath(SkPath* path) const {
    487     // path could safely be nullptr if we're empty, but the caller shouldn't
    488     // *know* that
    489     SkASSERT(path);
    490 
    491     if (this->isEmpty()) {
    492         return false;
    493     }
    494 
    495     const SkIRect& bounds = this->getBounds();
    496 
    497     if (this->isRect()) {
    498         SkRect  r;
    499         r.set(bounds);      // this converts the ints to scalars
    500         path->addRect(r);
    501         return true;
    502     }
    503 
    504     SkRegion::Iterator  iter(*this);
    505     SkTDArray<Edge>     edges;
    506 
    507     for (const SkIRect& r = iter.rect(); !iter.done(); iter.next()) {
    508         Edge* edge = edges.append(2);
    509         edge[0].set(r.fLeft, r.fBottom, r.fTop);
    510         edge[1].set(r.fRight, r.fTop, r.fBottom);
    511     }
    512 
    513     int count = edges.count();
    514     Edge* start = edges.begin();
    515     Edge* stop = start + count;
    516     SkTQSort<Edge>(start, stop - 1, EdgeLT());
    517 
    518     Edge* e;
    519     for (e = start; e != stop; e++) {
    520         find_link(e, stop);
    521     }
    522 
    523 #ifdef SK_DEBUG
    524     for (e = start; e != stop; e++) {
    525         SkASSERT(e->fNext != nullptr);
    526         SkASSERT(e->fFlags == Edge::kCompleteLink);
    527     }
    528 #endif
    529 
    530     path->incReserve(count << 1);
    531     do {
    532         SkASSERT(count > 1);
    533         count -= extract_path(start, stop, path);
    534     } while (count > 0);
    535 
    536     return true;
    537 }
    538