← Back to branch summary

~ubuntu-branches/ubuntu/karmic/gears/karmic

« back to all changes in this revision

Viewing changes to third_party/skia/src/core/SkRegion_path.cpp

  • Committer: Bazaar Package Importer
  • Author(s): Stefan Lesicnik
  • Date: 2009-04-30 19:15:25 UTC
  • Revision ID: james.westby@ubuntu.com-20090430191525-0790sb5wzg8ou0xb
Tags: upstream-0.5.21.0~svn3334+dfsg
Import upstream version 0.5.21.0~svn3334+dfsg

Show diffs side-by-side

added added

removed removed

Lines of Context:
third_party/skia/src/core/SkRegion_path.cpp
 
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
 
 
24
class SkRgnBuilder : public SkBlitter {
 
25
public:
 
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
 
61
private:
 
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
 
 
96
SkRgnBuilder::~SkRgnBuilder() {
 
97
    sk_free(fStorage);
 
98
}
 
99
 
 
100
bool 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
 
 
129
void 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
 
 
169
int 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
 
 
180
void 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
 
 
190
void 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
 
 
212
static 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
 
 
266
bool 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
 
 
326
struct 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
 
 
354
static 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
 
 
396
static 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
 
 
428
static int EdgeProc(const Edge* a, const Edge* b) {
 
429
    return (a->fX == b->fX) ? a->top() - b->top() : a->fX - b->fX;
 
430
}
 
431
 
 
432
bool 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