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