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