• 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     SkRgnBuilder();
19     virtual ~SkRgnBuilder();
20 
21     // returns true if it could allocate the working storage needed
22     bool init(int maxHeight, int maxTransitions, bool pathIsInverse);
23 
done()24     void done() {
25         if (fCurrScanline != NULL) {
26             fCurrScanline->fXCount = (SkRegion::RunType)((int)(fCurrXPtr - fCurrScanline->firstX()));
27             if (!this->collapsWithPrev()) { // flush the last line
28                 fCurrScanline = fCurrScanline->nextScanline();
29             }
30         }
31     }
32 
33     int     computeRunCount() const;
34     void    copyToRect(SkIRect*) const;
35     void    copyToRgn(SkRegion::RunType runs[]) const;
36 
37     virtual void blitH(int x, int y, int width);
38 
39 #ifdef SK_DEBUG
dump() const40     void dump() const {
41         SkDebugf("SkRgnBuilder: Top = %d\n", fTop);
42         const Scanline* line = (Scanline*)fStorage;
43         while (line < fCurrScanline) {
44             SkDebugf("SkRgnBuilder::Scanline: LastY=%d, fXCount=%d", line->fLastY, line->fXCount);
45             for (int i = 0; i < line->fXCount; i++) {
46                 SkDebugf(" %d", line->firstX()[i]);
47             }
48             SkDebugf("\n");
49 
50             line = line->nextScanline();
51         }
52     }
53 #endif
54 private:
55     /*
56      *  Scanline mimics a row in the region, nearly. A row in a region is:
57      *      [Bottom IntervalCount [L R]... Sentinel]
58      *  while a Scanline is
59      *      [LastY XCount [L R]... uninitialized]
60      *  The two are the same length (which is good), but we have to transmute
61      *  the scanline a little when we convert it to a region-row.
62      *
63      *  Potentially we could recode this to exactly match the row format, in
64      *  which case copyToRgn() could be a single memcpy. Not sure that is worth
65      *  the effort.
66      */
67     struct Scanline {
68         SkRegion::RunType fLastY;
69         SkRegion::RunType fXCount;
70 
firstXSkRgnBuilder::Scanline71         SkRegion::RunType* firstX() const { return (SkRegion::RunType*)(this + 1); }
nextScanlineSkRgnBuilder::Scanline72         Scanline* nextScanline() const {
73             // add final +1 for the x-sentinel
74             return (Scanline*)((SkRegion::RunType*)(this + 1) + fXCount + 1);
75         }
76     };
77     SkRegion::RunType*  fStorage;
78     Scanline*           fCurrScanline;
79     Scanline*           fPrevScanline;
80     //  points at next avialable x[] in fCurrScanline
81     SkRegion::RunType*  fCurrXPtr;
82     SkRegion::RunType   fTop;           // first Y value
83 
84     int fStorageCount;
85 
collapsWithPrev()86     bool collapsWithPrev() {
87         if (fPrevScanline != NULL &&
88             fPrevScanline->fLastY + 1 == fCurrScanline->fLastY &&
89             fPrevScanline->fXCount == fCurrScanline->fXCount &&
90             !memcmp(fPrevScanline->firstX(),
91                     fCurrScanline->firstX(),
92                     fCurrScanline->fXCount * sizeof(SkRegion::RunType)))
93         {
94             // update the height of fPrevScanline
95             fPrevScanline->fLastY = fCurrScanline->fLastY;
96             return true;
97         }
98         return false;
99     }
100 };
101 
SkRgnBuilder()102 SkRgnBuilder::SkRgnBuilder()
103     : fStorage(NULL) {
104 }
105 
~SkRgnBuilder()106 SkRgnBuilder::~SkRgnBuilder() {
107     sk_free(fStorage);
108 }
109 
init(int maxHeight,int maxTransitions,bool pathIsInverse)110 bool SkRgnBuilder::init(int maxHeight, int maxTransitions, bool pathIsInverse) {
111     if ((maxHeight | maxTransitions) < 0) {
112         return false;
113     }
114 
115     Sk64 count, size;
116 
117     if (pathIsInverse) {
118         // allow for additional X transitions to "invert" each scanline
119         // [ L' ... normal transitions ... R' ]
120         //
121         maxTransitions += 2;
122     }
123 
124     // compute the count with +1 and +3 slop for the working buffer
125     count.setMul(maxHeight + 1, 3 + maxTransitions);
126 
127     if (pathIsInverse) {
128         // allow for two "empty" rows for the top and bottom
129         //      [ Y, 1, L, R, S] == 5 (*2 for top and bottom)
130         count.add(10);
131     }
132 
133     if (!count.is32() || count.isNeg()) {
134         return false;
135     }
136     fStorageCount = count.get32();
137 
138     size.setMul(fStorageCount, sizeof(SkRegion::RunType));
139     if (!size.is32() || size.isNeg()) {
140         return false;
141     }
142 
143     fStorage = (SkRegion::RunType*)sk_malloc_flags(size.get32(), 0);
144     if (NULL == fStorage) {
145         return false;
146     }
147 
148     fCurrScanline = NULL;    // signal empty collection
149     fPrevScanline = NULL;    // signal first scanline
150     return true;
151 }
152 
blitH(int x,int y,int width)153 void SkRgnBuilder::blitH(int x, int y, int width) {
154     if (fCurrScanline == NULL) {  // first time
155         fTop = (SkRegion::RunType)(y);
156         fCurrScanline = (Scanline*)fStorage;
157         fCurrScanline->fLastY = (SkRegion::RunType)(y);
158         fCurrXPtr = fCurrScanline->firstX();
159     } else {
160         SkASSERT(y >= fCurrScanline->fLastY);
161 
162         if (y > fCurrScanline->fLastY) {
163             // if we get here, we're done with fCurrScanline
164             fCurrScanline->fXCount = (SkRegion::RunType)((int)(fCurrXPtr - fCurrScanline->firstX()));
165 
166             int prevLastY = fCurrScanline->fLastY;
167             if (!this->collapsWithPrev()) {
168                 fPrevScanline = fCurrScanline;
169                 fCurrScanline = fCurrScanline->nextScanline();
170 
171             }
172             if (y - 1 > prevLastY) {  // insert empty run
173                 fCurrScanline->fLastY = (SkRegion::RunType)(y - 1);
174                 fCurrScanline->fXCount = 0;
175                 fCurrScanline = fCurrScanline->nextScanline();
176             }
177             // setup for the new curr line
178             fCurrScanline->fLastY = (SkRegion::RunType)(y);
179             fCurrXPtr = fCurrScanline->firstX();
180         }
181     }
182     //  check if we should extend the current run, or add a new one
183     if (fCurrXPtr > fCurrScanline->firstX() && fCurrXPtr[-1] == x) {
184         fCurrXPtr[-1] = (SkRegion::RunType)(x + width);
185     } else {
186         fCurrXPtr[0] = (SkRegion::RunType)(x);
187         fCurrXPtr[1] = (SkRegion::RunType)(x + width);
188         fCurrXPtr += 2;
189     }
190     SkASSERT(fCurrXPtr - fStorage < fStorageCount);
191 }
192 
computeRunCount() const193 int SkRgnBuilder::computeRunCount() const {
194     if (fCurrScanline == NULL) {
195         return 0;
196     }
197 
198     const SkRegion::RunType*  line = fStorage;
199     const SkRegion::RunType*  stop = (const SkRegion::RunType*)fCurrScanline;
200 
201     return 2 + (int)(stop - line);
202 }
203 
copyToRect(SkIRect * r) const204 void SkRgnBuilder::copyToRect(SkIRect* r) const {
205     SkASSERT(fCurrScanline != NULL);
206     // A rect's scanline is [bottom intervals left right sentinel] == 5
207     SkASSERT((const SkRegion::RunType*)fCurrScanline - fStorage == 5);
208 
209     const Scanline* line = (const Scanline*)fStorage;
210     SkASSERT(line->fXCount == 2);
211 
212     r->set(line->firstX()[0], fTop, line->firstX()[1], line->fLastY + 1);
213 }
214 
copyToRgn(SkRegion::RunType runs[]) const215 void SkRgnBuilder::copyToRgn(SkRegion::RunType runs[]) const {
216     SkASSERT(fCurrScanline != NULL);
217     SkASSERT((const SkRegion::RunType*)fCurrScanline - fStorage > 4);
218 
219     const Scanline* line = (const Scanline*)fStorage;
220     const Scanline* stop = fCurrScanline;
221 
222     *runs++ = fTop;
223     do {
224         *runs++ = (SkRegion::RunType)(line->fLastY + 1);
225         int count = line->fXCount;
226         *runs++ = count >> 1;   // intervalCount
227         if (count) {
228             memcpy(runs, line->firstX(), count * sizeof(SkRegion::RunType));
229             runs += count;
230         }
231         *runs++ = SkRegion::kRunTypeSentinel;
232         line = line->nextScanline();
233     } while (line < stop);
234     SkASSERT(line == stop);
235     *runs = SkRegion::kRunTypeSentinel;
236 }
237 
verb_to_initial_last_index(unsigned verb)238 static unsigned verb_to_initial_last_index(unsigned verb) {
239     static const uint8_t gPathVerbToInitialLastIndex[] = {
240         0,  //  kMove_Verb
241         1,  //  kLine_Verb
242         2,  //  kQuad_Verb
243         2,  //  kConic_Verb
244         3,  //  kCubic_Verb
245         0,  //  kClose_Verb
246         0   //  kDone_Verb
247     };
248     SkASSERT((unsigned)verb < SK_ARRAY_COUNT(gPathVerbToInitialLastIndex));
249     return gPathVerbToInitialLastIndex[verb];
250 }
251 
verb_to_max_edges(unsigned verb)252 static unsigned verb_to_max_edges(unsigned verb) {
253     static const uint8_t gPathVerbToMaxEdges[] = {
254         0,  //  kMove_Verb
255         1,  //  kLine_Verb
256         2,  //  kQuad_VerbB
257         2,  //  kConic_VerbB
258         3,  //  kCubic_Verb
259         0,  //  kClose_Verb
260         0   //  kDone_Verb
261     };
262     SkASSERT((unsigned)verb < SK_ARRAY_COUNT(gPathVerbToMaxEdges));
263     return gPathVerbToMaxEdges[verb];
264 }
265 
266 
count_path_runtype_values(const SkPath & path,int * itop,int * ibot)267 static int count_path_runtype_values(const SkPath& path, int* itop, int* ibot) {
268     SkPath::Iter    iter(path, true);
269     SkPoint         pts[4];
270     SkPath::Verb    verb;
271 
272     int maxEdges = 0;
273     SkScalar    top = SkIntToScalar(SK_MaxS16);
274     SkScalar    bot = SkIntToScalar(SK_MinS16);
275 
276     while ((verb = iter.next(pts, false)) != SkPath::kDone_Verb) {
277         maxEdges += verb_to_max_edges(verb);
278 
279         int lastIndex = verb_to_initial_last_index(verb);
280         if (lastIndex > 0) {
281             for (int i = 1; i <= lastIndex; i++) {
282                 if (top > pts[i].fY) {
283                     top = pts[i].fY;
284                 } else if (bot < pts[i].fY) {
285                     bot = pts[i].fY;
286                 }
287             }
288         } else if (SkPath::kMove_Verb == verb) {
289             if (top > pts[0].fY) {
290                 top = pts[0].fY;
291             } else if (bot < pts[0].fY) {
292                 bot = pts[0].fY;
293             }
294         }
295     }
296     SkASSERT(top <= bot);
297 
298     *itop = SkScalarRound(top);
299     *ibot = SkScalarRound(bot);
300     return maxEdges;
301 }
302 
setPath(const SkPath & path,const SkRegion & clip)303 bool SkRegion::setPath(const SkPath& path, const SkRegion& clip) {
304     SkDEBUGCODE(this->validate();)
305 
306     if (clip.isEmpty()) {
307         return this->setEmpty();
308     }
309 
310     if (path.isEmpty()) {
311         if (path.isInverseFillType()) {
312             return this->set(clip);
313         } else {
314             return this->setEmpty();
315         }
316     }
317 
318     //  compute worst-case rgn-size for the path
319     int pathTop, pathBot;
320     int pathTransitions = count_path_runtype_values(path, &pathTop, &pathBot);
321     int clipTop, clipBot;
322     int clipTransitions;
323 
324     clipTransitions = clip.count_runtype_values(&clipTop, &clipBot);
325 
326     int top = SkMax32(pathTop, clipTop);
327     int bot = SkMin32(pathBot, clipBot);
328 
329     if (top >= bot)
330         return this->setEmpty();
331 
332     SkRgnBuilder builder;
333 
334     if (!builder.init(bot - top,
335                       SkMax32(pathTransitions, clipTransitions),
336                       path.isInverseFillType())) {
337         // can't allocate working space, so return false
338         return this->setEmpty();
339     }
340 
341     SkScan::FillPath(path, clip, &builder);
342     builder.done();
343 
344     int count = builder.computeRunCount();
345     if (count == 0) {
346         return this->setEmpty();
347     } else if (count == kRectRegionRuns) {
348         builder.copyToRect(&fBounds);
349         this->setRect(fBounds);
350     } else {
351         SkRegion tmp;
352 
353         tmp.fRunHead = RunHead::Alloc(count);
354         builder.copyToRgn(tmp.fRunHead->writable_runs());
355         tmp.fRunHead->computeRunBounds(&tmp.fBounds);
356         this->swap(tmp);
357     }
358     SkDEBUGCODE(this->validate();)
359     return true;
360 }
361 
362 /////////////////////////////////////////////////////////////////////////////////////////////////
363 /////////////////////////////////////////////////////////////////////////////////////////////////
364 
365 struct Edge {
366     enum {
367         kY0Link = 0x01,
368         kY1Link = 0x02,
369 
370         kCompleteLink = (kY0Link | kY1Link)
371     };
372 
373     SkRegion::RunType fX;
374     SkRegion::RunType fY0, fY1;
375     uint8_t fFlags;
376     Edge*   fNext;
377 
setEdge378     void set(int x, int y0, int y1) {
379         SkASSERT(y0 != y1);
380 
381         fX = (SkRegion::RunType)(x);
382         fY0 = (SkRegion::RunType)(y0);
383         fY1 = (SkRegion::RunType)(y1);
384         fFlags = 0;
385         SkDEBUGCODE(fNext = NULL;)
386     }
387 
topEdge388     int top() const {
389         return SkFastMin32(fY0, fY1);
390     }
391 };
392 
find_link(Edge * base,Edge * stop)393 static void find_link(Edge* base, Edge* stop) {
394     SkASSERT(base < stop);
395 
396     if (base->fFlags == Edge::kCompleteLink) {
397         SkASSERT(base->fNext);
398         return;
399     }
400 
401     SkASSERT(base + 1 < stop);
402 
403     int y0 = base->fY0;
404     int y1 = base->fY1;
405 
406     Edge* e = base;
407     if ((base->fFlags & Edge::kY0Link) == 0) {
408         for (;;) {
409             e += 1;
410             if ((e->fFlags & Edge::kY1Link) == 0 && y0 == e->fY1) {
411                 SkASSERT(NULL == e->fNext);
412                 e->fNext = base;
413                 e->fFlags = SkToU8(e->fFlags | Edge::kY1Link);
414                 break;
415             }
416         }
417     }
418 
419     e = base;
420     if ((base->fFlags & Edge::kY1Link) == 0) {
421         for (;;) {
422             e += 1;
423             if ((e->fFlags & Edge::kY0Link) == 0 && y1 == e->fY0) {
424                 SkASSERT(NULL == base->fNext);
425                 base->fNext = e;
426                 e->fFlags = SkToU8(e->fFlags | Edge::kY0Link);
427                 break;
428             }
429         }
430     }
431 
432     base->fFlags = Edge::kCompleteLink;
433 }
434 
extract_path(Edge * edge,Edge * stop,SkPath * path)435 static int extract_path(Edge* edge, Edge* stop, SkPath* path) {
436     while (0 == edge->fFlags) {
437         edge++; // skip over "used" edges
438     }
439 
440     SkASSERT(edge < stop);
441 
442     Edge* base = edge;
443     Edge* prev = edge;
444     edge = edge->fNext;
445     SkASSERT(edge != base);
446 
447     int count = 1;
448     path->moveTo(SkIntToScalar(prev->fX), SkIntToScalar(prev->fY0));
449     prev->fFlags = 0;
450     do {
451         if (prev->fX != edge->fX || prev->fY1 != edge->fY0) { // skip collinear
452             path->lineTo(SkIntToScalar(prev->fX), SkIntToScalar(prev->fY1));    // V
453             path->lineTo(SkIntToScalar(edge->fX), SkIntToScalar(edge->fY0));    // H
454         }
455         prev = edge;
456         edge = edge->fNext;
457         count += 1;
458         prev->fFlags = 0;
459     } while (edge != base);
460     path->lineTo(SkIntToScalar(prev->fX), SkIntToScalar(prev->fY1));    // V
461     path->close();
462     return count;
463 }
464 
465 #include "SkTSearch.h"
466 
EdgeProc(const Edge * a,const Edge * b)467 static int EdgeProc(const Edge* a, const Edge* b) {
468     return (a->fX == b->fX) ? a->top() - b->top() : a->fX - b->fX;
469 }
470 
getBoundaryPath(SkPath * path) const471 bool SkRegion::getBoundaryPath(SkPath* path) const {
472     // path could safely be NULL if we're empty, but the caller shouldn't
473     // *know* that
474     SkASSERT(path);
475 
476     if (this->isEmpty()) {
477         return false;
478     }
479 
480     const SkIRect& bounds = this->getBounds();
481 
482     if (this->isRect()) {
483         SkRect  r;
484         r.set(bounds);      // this converts the ints to scalars
485         path->addRect(r);
486         return true;
487     }
488 
489     SkRegion::Iterator  iter(*this);
490     SkTDArray<Edge>     edges;
491 
492     for (const SkIRect& r = iter.rect(); !iter.done(); iter.next()) {
493         Edge* edge = edges.append(2);
494         edge[0].set(r.fLeft, r.fBottom, r.fTop);
495         edge[1].set(r.fRight, r.fTop, r.fBottom);
496     }
497     qsort(edges.begin(), edges.count(), sizeof(Edge), SkCastForQSort(EdgeProc));
498 
499     int count = edges.count();
500     Edge* start = edges.begin();
501     Edge* stop = start + count;
502     Edge* e;
503 
504     for (e = start; e != stop; e++) {
505         find_link(e, stop);
506     }
507 
508 #ifdef SK_DEBUG
509     for (e = start; e != stop; e++) {
510         SkASSERT(e->fNext != NULL);
511         SkASSERT(e->fFlags == Edge::kCompleteLink);
512     }
513 #endif
514 
515     path->incReserve(count << 1);
516     do {
517         SkASSERT(count > 1);
518         count -= extract_path(start, stop, path);
519     } while (count > 0);
520 
521     return true;
522 }
523