• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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 
16 class SkRgnBuilder : public SkBlitter {
17 public:
18     virtual ~SkRgnBuilder();
19 
20     // returns true if it could allocate the working storage needed
21     bool init(int maxHeight, int maxTransitions);
22 
done()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
dump() const39     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
53 private:
54     struct Scanline {
55         SkRegion::RunType fLastY;
56         SkRegion::RunType fXCount;
57 
firstXSkRgnBuilder::Scanline58         SkRegion::RunType* firstX() const { return (SkRegion::RunType*)(this + 1); }
nextScanlineSkRgnBuilder::Scanline59         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 
collapsWithPrev()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 
~SkRgnBuilder()88 SkRgnBuilder::~SkRgnBuilder() {
89     sk_free(fStorage);
90 }
91 
init(int maxHeight,int maxTransitions)92 bool 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 
blitH(int x,int y,int width)121 void 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 
computeRunCount() const161 int 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 
copyToRect(SkIRect * r) const172 void 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 
copyToRgn(SkRegion::RunType runs[]) const182 void 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 
count_path_runtype_values(const SkPath & path,int * itop,int * ibot)204 static 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 
setPath(const SkPath & path,const SkRegion & clip)258 bool 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 
318 struct 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 
setEdge331     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 
topEdge341     int top() const {
342         return SkFastMin32(fY0, fY1);
343     }
344 };
345 
find_link(Edge * base,Edge * stop)346 static 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 
extract_path(Edge * edge,Edge * stop,SkPath * path)388 static 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 
EdgeProc(const Edge * a,const Edge * b)420 static int EdgeProc(const Edge* a, const Edge* b) {
421     return (a->fX == b->fX) ? a->top() - b->top() : a->fX - b->fX;
422 }
423 
getBoundaryPath(SkPath * path) const424 bool 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