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