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