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