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