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