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