src/third_party/skia/src/core/SkRegion_path.cpp

   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 }