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