michael@0: 
michael@0: /*
michael@0:  * Copyright 2006 The Android Open Source Project
michael@0:  *
michael@0:  * Use of this source code is governed by a BSD-style license that can be
michael@0:  * found in the LICENSE file.
michael@0:  */
michael@0: 
michael@0: 
michael@0: #include "SkRegionPriv.h"
michael@0: #include "SkBlitter.h"
michael@0: #include "SkScan.h"
michael@0: #include "SkTDArray.h"
michael@0: #include "SkPath.h"
michael@0: 
michael@0: class SkRgnBuilder : public SkBlitter {
michael@0: public:
michael@0:     SkRgnBuilder();
michael@0:     virtual ~SkRgnBuilder();
michael@0: 
michael@0:     // returns true if it could allocate the working storage needed
michael@0:     bool init(int maxHeight, int maxTransitions, bool pathIsInverse);
michael@0: 
michael@0:     void done() {
michael@0:         if (fCurrScanline != NULL) {
michael@0:             fCurrScanline->fXCount = (SkRegion::RunType)((int)(fCurrXPtr - fCurrScanline->firstX()));
michael@0:             if (!this->collapsWithPrev()) { // flush the last line
michael@0:                 fCurrScanline = fCurrScanline->nextScanline();
michael@0:             }
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     int     computeRunCount() const;
michael@0:     void    copyToRect(SkIRect*) const;
michael@0:     void    copyToRgn(SkRegion::RunType runs[]) const;
michael@0: 
michael@0:     virtual void blitH(int x, int y, int width);
michael@0: 
michael@0: #ifdef SK_DEBUG
michael@0:     void dump() const {
michael@0:         SkDebugf("SkRgnBuilder: Top = %d\n", fTop);
michael@0:         const Scanline* line = (Scanline*)fStorage;
michael@0:         while (line < fCurrScanline) {
michael@0:             SkDebugf("SkRgnBuilder::Scanline: LastY=%d, fXCount=%d", line->fLastY, line->fXCount);
michael@0:             for (int i = 0; i < line->fXCount; i++) {
michael@0:                 SkDebugf(" %d", line->firstX()[i]);
michael@0:             }
michael@0:             SkDebugf("\n");
michael@0: 
michael@0:             line = line->nextScanline();
michael@0:         }
michael@0:     }
michael@0: #endif
michael@0: private:
michael@0:     /*
michael@0:      *  Scanline mimics a row in the region, nearly. A row in a region is:
michael@0:      *      [Bottom IntervalCount [L R]... Sentinel]
michael@0:      *  while a Scanline is
michael@0:      *      [LastY XCount [L R]... uninitialized]
michael@0:      *  The two are the same length (which is good), but we have to transmute
michael@0:      *  the scanline a little when we convert it to a region-row.
michael@0:      *
michael@0:      *  Potentially we could recode this to exactly match the row format, in
michael@0:      *  which case copyToRgn() could be a single memcpy. Not sure that is worth
michael@0:      *  the effort.
michael@0:      */
michael@0:     struct Scanline {
michael@0:         SkRegion::RunType fLastY;
michael@0:         SkRegion::RunType fXCount;
michael@0: 
michael@0:         SkRegion::RunType* firstX() const { return (SkRegion::RunType*)(this + 1); }
michael@0:         Scanline* nextScanline() const {
michael@0:             // add final +1 for the x-sentinel
michael@0:             return (Scanline*)((SkRegion::RunType*)(this + 1) + fXCount + 1);
michael@0:         }
michael@0:     };
michael@0:     SkRegion::RunType*  fStorage;
michael@0:     Scanline*           fCurrScanline;
michael@0:     Scanline*           fPrevScanline;
michael@0:     //  points at next avialable x[] in fCurrScanline
michael@0:     SkRegion::RunType*  fCurrXPtr;
michael@0:     SkRegion::RunType   fTop;           // first Y value
michael@0: 
michael@0:     int fStorageCount;
michael@0: 
michael@0:     bool collapsWithPrev() {
michael@0:         if (fPrevScanline != NULL &&
michael@0:             fPrevScanline->fLastY + 1 == fCurrScanline->fLastY &&
michael@0:             fPrevScanline->fXCount == fCurrScanline->fXCount &&
michael@0:             !memcmp(fPrevScanline->firstX(),
michael@0:                     fCurrScanline->firstX(),
michael@0:                     fCurrScanline->fXCount * sizeof(SkRegion::RunType)))
michael@0:         {
michael@0:             // update the height of fPrevScanline
michael@0:             fPrevScanline->fLastY = fCurrScanline->fLastY;
michael@0:             return true;
michael@0:         }
michael@0:         return false;
michael@0:     }
michael@0: };
michael@0: 
michael@0: SkRgnBuilder::SkRgnBuilder()
michael@0:     : fStorage(NULL) {
michael@0: }
michael@0: 
michael@0: SkRgnBuilder::~SkRgnBuilder() {
michael@0:     sk_free(fStorage);
michael@0: }
michael@0: 
michael@0: bool SkRgnBuilder::init(int maxHeight, int maxTransitions, bool pathIsInverse) {
michael@0:     if ((maxHeight | maxTransitions) < 0) {
michael@0:         return false;
michael@0:     }
michael@0: 
michael@0:     if (pathIsInverse) {
michael@0:         // allow for additional X transitions to "invert" each scanline
michael@0:         // [ L' ... normal transitions ... R' ]
michael@0:         //
michael@0:         maxTransitions += 2;
michael@0:     }
michael@0: 
michael@0:     // compute the count with +1 and +3 slop for the working buffer
michael@0:     int64_t count = sk_64_mul(maxHeight + 1, 3 + maxTransitions);
michael@0: 
michael@0:     if (pathIsInverse) {
michael@0:         // allow for two "empty" rows for the top and bottom
michael@0:         //      [ Y, 1, L, R, S] == 5 (*2 for top and bottom)
michael@0:         count += 10;
michael@0:     }
michael@0: 
michael@0:     if (count < 0 || !sk_64_isS32(count)) {
michael@0:         return false;
michael@0:     }
michael@0:     fStorageCount = sk_64_asS32(count);
michael@0: 
michael@0:     int64_t size = sk_64_mul(fStorageCount, sizeof(SkRegion::RunType));
michael@0:     if (size < 0 || !sk_64_isS32(size)) {
michael@0:         return false;
michael@0:     }
michael@0: 
michael@0:     fStorage = (SkRegion::RunType*)sk_malloc_flags(sk_64_asS32(size), 0);
michael@0:     if (NULL == fStorage) {
michael@0:         return false;
michael@0:     }
michael@0: 
michael@0:     fCurrScanline = NULL;    // signal empty collection
michael@0:     fPrevScanline = NULL;    // signal first scanline
michael@0:     return true;
michael@0: }
michael@0: 
michael@0: void SkRgnBuilder::blitH(int x, int y, int width) {
michael@0:     if (fCurrScanline == NULL) {  // first time
michael@0:         fTop = (SkRegion::RunType)(y);
michael@0:         fCurrScanline = (Scanline*)fStorage;
michael@0:         fCurrScanline->fLastY = (SkRegion::RunType)(y);
michael@0:         fCurrXPtr = fCurrScanline->firstX();
michael@0:     } else {
michael@0:         SkASSERT(y >= fCurrScanline->fLastY);
michael@0: 
michael@0:         if (y > fCurrScanline->fLastY) {
michael@0:             // if we get here, we're done with fCurrScanline
michael@0:             fCurrScanline->fXCount = (SkRegion::RunType)((int)(fCurrXPtr - fCurrScanline->firstX()));
michael@0: 
michael@0:             int prevLastY = fCurrScanline->fLastY;
michael@0:             if (!this->collapsWithPrev()) {
michael@0:                 fPrevScanline = fCurrScanline;
michael@0:                 fCurrScanline = fCurrScanline->nextScanline();
michael@0: 
michael@0:             }
michael@0:             if (y - 1 > prevLastY) {  // insert empty run
michael@0:                 fCurrScanline->fLastY = (SkRegion::RunType)(y - 1);
michael@0:                 fCurrScanline->fXCount = 0;
michael@0:                 fCurrScanline = fCurrScanline->nextScanline();
michael@0:             }
michael@0:             // setup for the new curr line
michael@0:             fCurrScanline->fLastY = (SkRegion::RunType)(y);
michael@0:             fCurrXPtr = fCurrScanline->firstX();
michael@0:         }
michael@0:     }
michael@0:     //  check if we should extend the current run, or add a new one
michael@0:     if (fCurrXPtr > fCurrScanline->firstX() && fCurrXPtr[-1] == x) {
michael@0:         fCurrXPtr[-1] = (SkRegion::RunType)(x + width);
michael@0:     } else {
michael@0:         fCurrXPtr[0] = (SkRegion::RunType)(x);
michael@0:         fCurrXPtr[1] = (SkRegion::RunType)(x + width);
michael@0:         fCurrXPtr += 2;
michael@0:     }
michael@0:     SkASSERT(fCurrXPtr - fStorage < fStorageCount);
michael@0: }
michael@0: 
michael@0: int SkRgnBuilder::computeRunCount() const {
michael@0:     if (fCurrScanline == NULL) {
michael@0:         return 0;
michael@0:     }
michael@0: 
michael@0:     const SkRegion::RunType*  line = fStorage;
michael@0:     const SkRegion::RunType*  stop = (const SkRegion::RunType*)fCurrScanline;
michael@0: 
michael@0:     return 2 + (int)(stop - line);
michael@0: }
michael@0: 
michael@0: void SkRgnBuilder::copyToRect(SkIRect* r) const {
michael@0:     SkASSERT(fCurrScanline != NULL);
michael@0:     // A rect's scanline is [bottom intervals left right sentinel] == 5
michael@0:     SkASSERT((const SkRegion::RunType*)fCurrScanline - fStorage == 5);
michael@0: 
michael@0:     const Scanline* line = (const Scanline*)fStorage;
michael@0:     SkASSERT(line->fXCount == 2);
michael@0: 
michael@0:     r->set(line->firstX()[0], fTop, line->firstX()[1], line->fLastY + 1);
michael@0: }
michael@0: 
michael@0: void SkRgnBuilder::copyToRgn(SkRegion::RunType runs[]) const {
michael@0:     SkASSERT(fCurrScanline != NULL);
michael@0:     SkASSERT((const SkRegion::RunType*)fCurrScanline - fStorage > 4);
michael@0: 
michael@0:     const Scanline* line = (const Scanline*)fStorage;
michael@0:     const Scanline* stop = fCurrScanline;
michael@0: 
michael@0:     *runs++ = fTop;
michael@0:     do {
michael@0:         *runs++ = (SkRegion::RunType)(line->fLastY + 1);
michael@0:         int count = line->fXCount;
michael@0:         *runs++ = count >> 1;   // intervalCount
michael@0:         if (count) {
michael@0:             memcpy(runs, line->firstX(), count * sizeof(SkRegion::RunType));
michael@0:             runs += count;
michael@0:         }
michael@0:         *runs++ = SkRegion::kRunTypeSentinel;
michael@0:         line = line->nextScanline();
michael@0:     } while (line < stop);
michael@0:     SkASSERT(line == stop);
michael@0:     *runs = SkRegion::kRunTypeSentinel;
michael@0: }
michael@0: 
michael@0: static unsigned verb_to_initial_last_index(unsigned verb) {
michael@0:     static const uint8_t gPathVerbToInitialLastIndex[] = {
michael@0:         0,  //  kMove_Verb
michael@0:         1,  //  kLine_Verb
michael@0:         2,  //  kQuad_Verb
michael@0:         2,  //  kConic_Verb
michael@0:         3,  //  kCubic_Verb
michael@0:         0,  //  kClose_Verb
michael@0:         0   //  kDone_Verb
michael@0:     };
michael@0:     SkASSERT((unsigned)verb < SK_ARRAY_COUNT(gPathVerbToInitialLastIndex));
michael@0:     return gPathVerbToInitialLastIndex[verb];
michael@0: }
michael@0: 
michael@0: static unsigned verb_to_max_edges(unsigned verb) {
michael@0:     static const uint8_t gPathVerbToMaxEdges[] = {
michael@0:         0,  //  kMove_Verb
michael@0:         1,  //  kLine_Verb
michael@0:         2,  //  kQuad_VerbB
michael@0:         2,  //  kConic_VerbB
michael@0:         3,  //  kCubic_Verb
michael@0:         0,  //  kClose_Verb
michael@0:         0   //  kDone_Verb
michael@0:     };
michael@0:     SkASSERT((unsigned)verb < SK_ARRAY_COUNT(gPathVerbToMaxEdges));
michael@0:     return gPathVerbToMaxEdges[verb];
michael@0: }
michael@0: 
michael@0: 
michael@0: static int count_path_runtype_values(const SkPath& path, int* itop, int* ibot) {
michael@0:     SkPath::Iter    iter(path, true);
michael@0:     SkPoint         pts[4];
michael@0:     SkPath::Verb    verb;
michael@0: 
michael@0:     int maxEdges = 0;
michael@0:     SkScalar    top = SkIntToScalar(SK_MaxS16);
michael@0:     SkScalar    bot = SkIntToScalar(SK_MinS16);
michael@0: 
michael@0:     while ((verb = iter.next(pts, false)) != SkPath::kDone_Verb) {
michael@0:         maxEdges += verb_to_max_edges(verb);
michael@0: 
michael@0:         int lastIndex = verb_to_initial_last_index(verb);
michael@0:         if (lastIndex > 0) {
michael@0:             for (int i = 1; i <= lastIndex; i++) {
michael@0:                 if (top > pts[i].fY) {
michael@0:                     top = pts[i].fY;
michael@0:                 } else if (bot < pts[i].fY) {
michael@0:                     bot = pts[i].fY;
michael@0:                 }
michael@0:             }
michael@0:         } else if (SkPath::kMove_Verb == verb) {
michael@0:             if (top > pts[0].fY) {
michael@0:                 top = pts[0].fY;
michael@0:             } else if (bot < pts[0].fY) {
michael@0:                 bot = pts[0].fY;
michael@0:             }
michael@0:         }
michael@0:     }
michael@0:     SkASSERT(top <= bot);
michael@0: 
michael@0:     *itop = SkScalarRoundToInt(top);
michael@0:     *ibot = SkScalarRoundToInt(bot);
michael@0:     return maxEdges;
michael@0: }
michael@0: 
michael@0: bool SkRegion::setPath(const SkPath& path, const SkRegion& clip) {
michael@0:     SkDEBUGCODE(this->validate();)
michael@0: 
michael@0:     if (clip.isEmpty()) {
michael@0:         return this->setEmpty();
michael@0:     }
michael@0: 
michael@0:     if (path.isEmpty()) {
michael@0:         if (path.isInverseFillType()) {
michael@0:             return this->set(clip);
michael@0:         } else {
michael@0:             return this->setEmpty();
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     //  compute worst-case rgn-size for the path
michael@0:     int pathTop, pathBot;
michael@0:     int pathTransitions = count_path_runtype_values(path, &pathTop, &pathBot);
michael@0:     int clipTop, clipBot;
michael@0:     int clipTransitions;
michael@0: 
michael@0:     clipTransitions = clip.count_runtype_values(&clipTop, &clipBot);
michael@0: 
michael@0:     int top = SkMax32(pathTop, clipTop);
michael@0:     int bot = SkMin32(pathBot, clipBot);
michael@0: 
michael@0:     if (top >= bot)
michael@0:         return this->setEmpty();
michael@0: 
michael@0:     SkRgnBuilder builder;
michael@0: 
michael@0:     if (!builder.init(bot - top,
michael@0:                       SkMax32(pathTransitions, clipTransitions),
michael@0:                       path.isInverseFillType())) {
michael@0:         // can't allocate working space, so return false
michael@0:         return this->setEmpty();
michael@0:     }
michael@0: 
michael@0:     SkScan::FillPath(path, clip, &builder);
michael@0:     builder.done();
michael@0: 
michael@0:     int count = builder.computeRunCount();
michael@0:     if (count == 0) {
michael@0:         return this->setEmpty();
michael@0:     } else if (count == kRectRegionRuns) {
michael@0:         builder.copyToRect(&fBounds);
michael@0:         this->setRect(fBounds);
michael@0:     } else {
michael@0:         SkRegion tmp;
michael@0: 
michael@0:         tmp.fRunHead = RunHead::Alloc(count);
michael@0:         builder.copyToRgn(tmp.fRunHead->writable_runs());
michael@0:         tmp.fRunHead->computeRunBounds(&tmp.fBounds);
michael@0:         this->swap(tmp);
michael@0:     }
michael@0:     SkDEBUGCODE(this->validate();)
michael@0:     return true;
michael@0: }
michael@0: 
michael@0: /////////////////////////////////////////////////////////////////////////////////////////////////
michael@0: /////////////////////////////////////////////////////////////////////////////////////////////////
michael@0: 
michael@0: struct Edge {
michael@0:     enum {
michael@0:         kY0Link = 0x01,
michael@0:         kY1Link = 0x02,
michael@0: 
michael@0:         kCompleteLink = (kY0Link | kY1Link)
michael@0:     };
michael@0: 
michael@0:     SkRegion::RunType fX;
michael@0:     SkRegion::RunType fY0, fY1;
michael@0:     uint8_t fFlags;
michael@0:     Edge*   fNext;
michael@0: 
michael@0:     void set(int x, int y0, int y1) {
michael@0:         SkASSERT(y0 != y1);
michael@0: 
michael@0:         fX = (SkRegion::RunType)(x);
michael@0:         fY0 = (SkRegion::RunType)(y0);
michael@0:         fY1 = (SkRegion::RunType)(y1);
michael@0:         fFlags = 0;
michael@0:         SkDEBUGCODE(fNext = NULL;)
michael@0:     }
michael@0: 
michael@0:     int top() const {
michael@0:         return SkFastMin32(fY0, fY1);
michael@0:     }
michael@0: };
michael@0: 
michael@0: static void find_link(Edge* base, Edge* stop) {
michael@0:     SkASSERT(base < stop);
michael@0: 
michael@0:     if (base->fFlags == Edge::kCompleteLink) {
michael@0:         SkASSERT(base->fNext);
michael@0:         return;
michael@0:     }
michael@0: 
michael@0:     SkASSERT(base + 1 < stop);
michael@0: 
michael@0:     int y0 = base->fY0;
michael@0:     int y1 = base->fY1;
michael@0: 
michael@0:     Edge* e = base;
michael@0:     if ((base->fFlags & Edge::kY0Link) == 0) {
michael@0:         for (;;) {
michael@0:             e += 1;
michael@0:             if ((e->fFlags & Edge::kY1Link) == 0 && y0 == e->fY1) {
michael@0:                 SkASSERT(NULL == e->fNext);
michael@0:                 e->fNext = base;
michael@0:                 e->fFlags = SkToU8(e->fFlags | Edge::kY1Link);
michael@0:                 break;
michael@0:             }
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     e = base;
michael@0:     if ((base->fFlags & Edge::kY1Link) == 0) {
michael@0:         for (;;) {
michael@0:             e += 1;
michael@0:             if ((e->fFlags & Edge::kY0Link) == 0 && y1 == e->fY0) {
michael@0:                 SkASSERT(NULL == base->fNext);
michael@0:                 base->fNext = e;
michael@0:                 e->fFlags = SkToU8(e->fFlags | Edge::kY0Link);
michael@0:                 break;
michael@0:             }
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     base->fFlags = Edge::kCompleteLink;
michael@0: }
michael@0: 
michael@0: static int extract_path(Edge* edge, Edge* stop, SkPath* path) {
michael@0:     while (0 == edge->fFlags) {
michael@0:         edge++; // skip over "used" edges
michael@0:     }
michael@0: 
michael@0:     SkASSERT(edge < stop);
michael@0: 
michael@0:     Edge* base = edge;
michael@0:     Edge* prev = edge;
michael@0:     edge = edge->fNext;
michael@0:     SkASSERT(edge != base);
michael@0: 
michael@0:     int count = 1;
michael@0:     path->moveTo(SkIntToScalar(prev->fX), SkIntToScalar(prev->fY0));
michael@0:     prev->fFlags = 0;
michael@0:     do {
michael@0:         if (prev->fX != edge->fX || prev->fY1 != edge->fY0) { // skip collinear
michael@0:             path->lineTo(SkIntToScalar(prev->fX), SkIntToScalar(prev->fY1));    // V
michael@0:             path->lineTo(SkIntToScalar(edge->fX), SkIntToScalar(edge->fY0));    // H
michael@0:         }
michael@0:         prev = edge;
michael@0:         edge = edge->fNext;
michael@0:         count += 1;
michael@0:         prev->fFlags = 0;
michael@0:     } while (edge != base);
michael@0:     path->lineTo(SkIntToScalar(prev->fX), SkIntToScalar(prev->fY1));    // V
michael@0:     path->close();
michael@0:     return count;
michael@0: }
michael@0: 
michael@0: #include "SkTSearch.h"
michael@0: 
michael@0: static int EdgeProc(const Edge* a, const Edge* b) {
michael@0:     return (a->fX == b->fX) ? a->top() - b->top() : a->fX - b->fX;
michael@0: }
michael@0: 
michael@0: bool SkRegion::getBoundaryPath(SkPath* path) const {
michael@0:     // path could safely be NULL if we're empty, but the caller shouldn't
michael@0:     // *know* that
michael@0:     SkASSERT(path);
michael@0: 
michael@0:     if (this->isEmpty()) {
michael@0:         return false;
michael@0:     }
michael@0: 
michael@0:     const SkIRect& bounds = this->getBounds();
michael@0: 
michael@0:     if (this->isRect()) {
michael@0:         SkRect  r;
michael@0:         r.set(bounds);      // this converts the ints to scalars
michael@0:         path->addRect(r);
michael@0:         return true;
michael@0:     }
michael@0: 
michael@0:     SkRegion::Iterator  iter(*this);
michael@0:     SkTDArray<Edge>     edges;
michael@0: 
michael@0:     for (const SkIRect& r = iter.rect(); !iter.done(); iter.next()) {
michael@0:         Edge* edge = edges.append(2);
michael@0:         edge[0].set(r.fLeft, r.fBottom, r.fTop);
michael@0:         edge[1].set(r.fRight, r.fTop, r.fBottom);
michael@0:     }
michael@0:     qsort(edges.begin(), edges.count(), sizeof(Edge), SkCastForQSort(EdgeProc));
michael@0: 
michael@0:     int count = edges.count();
michael@0:     Edge* start = edges.begin();
michael@0:     Edge* stop = start + count;
michael@0:     Edge* e;
michael@0: 
michael@0:     for (e = start; e != stop; e++) {
michael@0:         find_link(e, stop);
michael@0:     }
michael@0: 
michael@0: #ifdef SK_DEBUG
michael@0:     for (e = start; e != stop; e++) {
michael@0:         SkASSERT(e->fNext != NULL);
michael@0:         SkASSERT(e->fFlags == Edge::kCompleteLink);
michael@0:     }
michael@0: #endif
michael@0: 
michael@0:     path->incReserve(count << 1);
michael@0:     do {
michael@0:         SkASSERT(count > 1);
michael@0:         count -= extract_path(start, stop, path);
michael@0:     } while (count > 0);
michael@0: 
michael@0:     return true;
michael@0: }