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