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