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