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     virtual void blitH(int x, int y, int width);
     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 
    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     SkASSERT(top <= bot);
    302 
    303     *itop = SkScalarRoundToInt(top);
    304     *ibot = SkScalarRoundToInt(bot);
    305     return maxEdges;
    306 }
    307 
    308 bool SkRegion::setPath(const SkPath& path, const SkRegion& clip) {
    309     SkDEBUGCODE(this->validate();)
    310 
    311     if (clip.isEmpty()) {
    312         return this->setEmpty();
    313     }
    314 
    315     if (path.isEmpty()) {
    316         if (path.isInverseFillType()) {
    317             return this->set(clip);
    318         } else {
    319             return this->setEmpty();
    320         }
    321     }
    322 
    323     //  compute worst-case rgn-size for the path
    324     int pathTop, pathBot;
    325     int pathTransitions = count_path_runtype_values(path, &pathTop, &pathBot);
    326     int clipTop, clipBot;
    327     int clipTransitions;
    328 
    329     clipTransitions = clip.count_runtype_values(&clipTop, &clipBot);
    330 
    331     int top = SkMax32(pathTop, clipTop);
    332     int bot = SkMin32(pathBot, clipBot);
    333 
    334     if (top >= bot)
    335         return this->setEmpty();
    336 
    337     SkRgnBuilder builder;
    338 
    339     if (!builder.init(bot - top,
    340                       SkMax32(pathTransitions, clipTransitions),
    341                       path.isInverseFillType())) {
    342         // can't allocate working space, so return false
    343         return this->setEmpty();
    344     }
    345 
    346     SkScan::FillPath(path, clip, &builder);
    347     builder.done();
    348 
    349     int count = builder.computeRunCount();
    350     if (count == 0) {
    351         return this->setEmpty();
    352     } else if (count == kRectRegionRuns) {
    353         builder.copyToRect(&fBounds);
    354         this->setRect(fBounds);
    355     } else {
    356         SkRegion tmp;
    357 
    358         tmp.fRunHead = RunHead::Alloc(count);
    359         builder.copyToRgn(tmp.fRunHead->writable_runs());
    360         tmp.fRunHead->computeRunBounds(&tmp.fBounds);
    361         this->swap(tmp);
    362     }
    363     SkDEBUGCODE(this->validate();)
    364     return true;
    365 }
    366 
    367 /////////////////////////////////////////////////////////////////////////////////////////////////
    368 /////////////////////////////////////////////////////////////////////////////////////////////////
    369 
    370 struct Edge {
    371     enum {
    372         kY0Link = 0x01,
    373         kY1Link = 0x02,
    374 
    375         kCompleteLink = (kY0Link | kY1Link)
    376     };
    377 
    378     SkRegion::RunType fX;
    379     SkRegion::RunType fY0, fY1;
    380     uint8_t fFlags;
    381     Edge*   fNext;
    382 
    383     void set(int x, int y0, int y1) {
    384         SkASSERT(y0 != y1);
    385 
    386         fX = (SkRegion::RunType)(x);
    387         fY0 = (SkRegion::RunType)(y0);
    388         fY1 = (SkRegion::RunType)(y1);
    389         fFlags = 0;
    390         SkDEBUGCODE(fNext = NULL;)
    391     }
    392 
    393     int top() const {
    394         return SkFastMin32(fY0, fY1);
    395     }
    396 };
    397 
    398 static void find_link(Edge* base, Edge* stop) {
    399     SkASSERT(base < stop);
    400 
    401     if (base->fFlags == Edge::kCompleteLink) {
    402         SkASSERT(base->fNext);
    403         return;
    404     }
    405 
    406     SkASSERT(base + 1 < stop);
    407 
    408     int y0 = base->fY0;
    409     int y1 = base->fY1;
    410 
    411     Edge* e = base;
    412     if ((base->fFlags & Edge::kY0Link) == 0) {
    413         for (;;) {
    414             e += 1;
    415             if ((e->fFlags & Edge::kY1Link) == 0 && y0 == e->fY1) {
    416                 SkASSERT(NULL == e->fNext);
    417                 e->fNext = base;
    418                 e->fFlags = SkToU8(e->fFlags | Edge::kY1Link);
    419                 break;
    420             }
    421         }
    422     }
    423 
    424     e = base;
    425     if ((base->fFlags & Edge::kY1Link) == 0) {
    426         for (;;) {
    427             e += 1;
    428             if ((e->fFlags & Edge::kY0Link) == 0 && y1 == e->fY0) {
    429                 SkASSERT(NULL == base->fNext);
    430                 base->fNext = e;
    431                 e->fFlags = SkToU8(e->fFlags | Edge::kY0Link);
    432                 break;
    433             }
    434         }
    435     }
    436 
    437     base->fFlags = Edge::kCompleteLink;
    438 }
    439 
    440 static int extract_path(Edge* edge, Edge* stop, SkPath* path) {
    441     while (0 == edge->fFlags) {
    442         edge++; // skip over "used" edges
    443     }
    444 
    445     SkASSERT(edge < stop);
    446 
    447     Edge* base = edge;
    448     Edge* prev = edge;
    449     edge = edge->fNext;
    450     SkASSERT(edge != base);
    451 
    452     int count = 1;
    453     path->moveTo(SkIntToScalar(prev->fX), SkIntToScalar(prev->fY0));
    454     prev->fFlags = 0;
    455     do {
    456         if (prev->fX != edge->fX || prev->fY1 != edge->fY0) { // skip collinear
    457             path->lineTo(SkIntToScalar(prev->fX), SkIntToScalar(prev->fY1));    // V
    458             path->lineTo(SkIntToScalar(edge->fX), SkIntToScalar(edge->fY0));    // H
    459         }
    460         prev = edge;
    461         edge = edge->fNext;
    462         count += 1;
    463         prev->fFlags = 0;
    464     } while (edge != base);
    465     path->lineTo(SkIntToScalar(prev->fX), SkIntToScalar(prev->fY1));    // V
    466     path->close();
    467     return count;
    468 }
    469 
    470 #include "SkTSearch.h"
    471 
    472 static int EdgeProc(const Edge* a, const Edge* b) {
    473     return (a->fX == b->fX) ? a->top() - b->top() : a->fX - b->fX;
    474 }
    475 
    476 bool SkRegion::getBoundaryPath(SkPath* path) const {
    477     // path could safely be NULL if we're empty, but the caller shouldn't
    478     // *know* that
    479     SkASSERT(path);
    480 
    481     if (this->isEmpty()) {
    482         return false;
    483     }
    484 
    485     const SkIRect& bounds = this->getBounds();
    486 
    487     if (this->isRect()) {
    488         SkRect  r;
    489         r.set(bounds);      // this converts the ints to scalars
    490         path->addRect(r);
    491         return true;
    492     }
    493 
    494     SkRegion::Iterator  iter(*this);
    495     SkTDArray<Edge>     edges;
    496 
    497     for (const SkIRect& r = iter.rect(); !iter.done(); iter.next()) {
    498         Edge* edge = edges.append(2);
    499         edge[0].set(r.fLeft, r.fBottom, r.fTop);
    500         edge[1].set(r.fRight, r.fTop, r.fBottom);
    501     }
    502     qsort(edges.begin(), edges.count(), sizeof(Edge), SkCastForQSort(EdgeProc));
    503 
    504     int count = edges.count();
    505     Edge* start = edges.begin();
    506     Edge* stop = start + count;
    507     Edge* e;
    508 
    509     for (e = start; e != stop; e++) {
    510         find_link(e, stop);
    511     }
    512 
    513 #ifdef SK_DEBUG
    514     for (e = start; e != stop; e++) {
    515         SkASSERT(e->fNext != NULL);
    516         SkASSERT(e->fFlags == Edge::kCompleteLink);
    517     }
    518 #endif
    519 
    520     path->incReserve(count << 1);
    521     do {
    522         SkASSERT(count > 1);
    523         count -= extract_path(start, stop, path);
    524     } while (count > 0);
    525 
    526     return true;
    527 }
    528