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