1 /* libs/graphics/sgl/SkRegion_path.cpp
2 **
3 ** Copyright 2006, The Android Open Source Project
4 **
5 ** Licensed under the Apache License, Version 2.0 (the "License");
6 ** you may not use this file except in compliance with the License.
7 ** You may obtain a copy of the License at
8 **
9 ** http://www.apache.org/licenses/LICENSE-2.0
10 **
11 ** Unless required by applicable law or agreed to in writing, software
12 ** distributed under the License is distributed on an "AS IS" BASIS,
13 ** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 ** See the License for the specific language governing permissions and
15 ** limitations under the License.
16 */
17
18 #include "SkRegionPriv.h"
19 #include "SkBlitter.h"
20 #include "SkScan.h"
21 #include "SkTDArray.h"
22 #include "SkPath.h"
23
24 class SkRgnBuilder : public SkBlitter {
25 public:
26 virtual ~SkRgnBuilder();
27
28 // returns true if it could allocate the working storage needed
29 bool init(int maxHeight, int maxTransitions);
30
done()31 void done() {
32 if (fCurrScanline != NULL) {
33 fCurrScanline->fXCount = (SkRegion::RunType)((int)(fCurrXPtr - fCurrScanline->firstX()));
34 if (!this->collapsWithPrev()) { // flush the last line
35 fCurrScanline = fCurrScanline->nextScanline();
36 }
37 }
38 }
39
40 int computeRunCount() const;
41 void copyToRect(SkIRect*) const;
42 void copyToRgn(SkRegion::RunType runs[]) const;
43
44 virtual void blitH(int x, int y, int width);
45
46 #ifdef SK_DEBUG
dump() const47 void dump() const {
48 SkDebugf("SkRgnBuilder: Top = %d\n", fTop);
49 const Scanline* line = (Scanline*)fStorage;
50 while (line < fCurrScanline) {
51 SkDebugf("SkRgnBuilder::Scanline: LastY=%d, fXCount=%d", line->fLastY, line->fXCount);
52 for (int i = 0; i < line->fXCount; i++) {
53 SkDebugf(" %d", line->firstX()[i]);
54 }
55 SkDebugf("\n");
56
57 line = line->nextScanline();
58 }
59 }
60 #endif
61 private:
62 struct Scanline {
63 SkRegion::RunType fLastY;
64 SkRegion::RunType fXCount;
65
firstXSkRgnBuilder::Scanline66 SkRegion::RunType* firstX() const { return (SkRegion::RunType*)(this + 1); }
nextScanlineSkRgnBuilder::Scanline67 Scanline* nextScanline() const {
68 return (Scanline*)((SkRegion::RunType*)(this + 1) + fXCount);
69 }
70 };
71 SkRegion::RunType* fStorage;
72 Scanline* fCurrScanline;
73 Scanline* fPrevScanline;
74 // points at next avialable x[] in fCurrScanline
75 SkRegion::RunType* fCurrXPtr;
76 SkRegion::RunType fTop; // first Y value
77
78 int fStorageCount;
79
collapsWithPrev()80 bool collapsWithPrev() {
81 if (fPrevScanline != NULL &&
82 fPrevScanline->fLastY + 1 == fCurrScanline->fLastY &&
83 fPrevScanline->fXCount == fCurrScanline->fXCount &&
84 !memcmp(fPrevScanline->firstX(),
85 fCurrScanline->firstX(),
86 fCurrScanline->fXCount * sizeof(SkRegion::RunType)))
87 {
88 // update the height of fPrevScanline
89 fPrevScanline->fLastY = fCurrScanline->fLastY;
90 return true;
91 }
92 return false;
93 }
94 };
95
~SkRgnBuilder()96 SkRgnBuilder::~SkRgnBuilder() {
97 sk_free(fStorage);
98 }
99
init(int maxHeight,int maxTransitions)100 bool SkRgnBuilder::init(int maxHeight, int maxTransitions) {
101 if ((maxHeight | maxTransitions) < 0) {
102 return false;
103 }
104
105 Sk64 count, size;
106
107 // compute the count with +1 and +3 slop for the working buffer
108 count.setMul(maxHeight + 1, 3 + maxTransitions);
109 if (!count.is32() || count.isNeg()) {
110 return false;
111 }
112 fStorageCount = count.get32();
113
114 size.setMul(fStorageCount, sizeof(SkRegion::RunType));
115 if (!size.is32() || size.isNeg()) {
116 return false;
117 }
118
119 fStorage = (SkRegion::RunType*)sk_malloc_flags(size.get32(), 0);
120 if (NULL == fStorage) {
121 return false;
122 }
123
124 fCurrScanline = NULL; // signal empty collection
125 fPrevScanline = NULL; // signal first scanline
126 return true;
127 }
128
blitH(int x,int y,int width)129 void SkRgnBuilder::blitH(int x, int y, int width) {
130 if (fCurrScanline == NULL) { // first time
131 fTop = (SkRegion::RunType)(y);
132 fCurrScanline = (Scanline*)fStorage;
133 fCurrScanline->fLastY = (SkRegion::RunType)(y);
134 fCurrXPtr = fCurrScanline->firstX();
135 } else {
136 SkASSERT(y >= fCurrScanline->fLastY);
137
138 if (y > fCurrScanline->fLastY) {
139 // if we get here, we're done with fCurrScanline
140 fCurrScanline->fXCount = (SkRegion::RunType)((int)(fCurrXPtr - fCurrScanline->firstX()));
141
142 int prevLastY = fCurrScanline->fLastY;
143 if (!this->collapsWithPrev()) {
144 fPrevScanline = fCurrScanline;
145 fCurrScanline = fCurrScanline->nextScanline();
146
147 }
148 if (y - 1 > prevLastY) { // insert empty run
149 fCurrScanline->fLastY = (SkRegion::RunType)(y - 1);
150 fCurrScanline->fXCount = 0;
151 fCurrScanline = fCurrScanline->nextScanline();
152 }
153 // setup for the new curr line
154 fCurrScanline->fLastY = (SkRegion::RunType)(y);
155 fCurrXPtr = fCurrScanline->firstX();
156 }
157 }
158 // check if we should extend the current run, or add a new one
159 if (fCurrXPtr > fCurrScanline->firstX() && fCurrXPtr[-1] == x) {
160 fCurrXPtr[-1] = (SkRegion::RunType)(x + width);
161 } else {
162 fCurrXPtr[0] = (SkRegion::RunType)(x);
163 fCurrXPtr[1] = (SkRegion::RunType)(x + width);
164 fCurrXPtr += 2;
165 }
166 SkASSERT(fCurrXPtr - fStorage < fStorageCount);
167 }
168
computeRunCount() const169 int SkRgnBuilder::computeRunCount() const {
170 if (fCurrScanline == NULL) {
171 return 0;
172 }
173
174 const SkRegion::RunType* line = fStorage;
175 const SkRegion::RunType* stop = (const SkRegion::RunType*)fCurrScanline;
176
177 return 2 + (int)(stop - line);
178 }
179
copyToRect(SkIRect * r) const180 void SkRgnBuilder::copyToRect(SkIRect* r) const {
181 SkASSERT(fCurrScanline != NULL);
182 SkASSERT((const SkRegion::RunType*)fCurrScanline - fStorage == 4);
183
184 const Scanline* line = (const Scanline*)fStorage;
185 SkASSERT(line->fXCount == 2);
186
187 r->set(line->firstX()[0], fTop, line->firstX()[1], line->fLastY + 1);
188 }
189
copyToRgn(SkRegion::RunType runs[]) const190 void SkRgnBuilder::copyToRgn(SkRegion::RunType runs[]) const {
191 SkASSERT(fCurrScanline != NULL);
192 SkASSERT((const SkRegion::RunType*)fCurrScanline - fStorage > 4);
193
194 const Scanline* line = (const Scanline*)fStorage;
195 const Scanline* stop = fCurrScanline;
196
197 *runs++ = fTop;
198 do {
199 *runs++ = (SkRegion::RunType)(line->fLastY + 1);
200 int count = line->fXCount;
201 if (count) {
202 memcpy(runs, line->firstX(), count * sizeof(SkRegion::RunType));
203 runs += count;
204 }
205 *runs++ = SkRegion::kRunTypeSentinel;
206 line = line->nextScanline();
207 } while (line < stop);
208 SkASSERT(line == stop);
209 *runs = SkRegion::kRunTypeSentinel;
210 }
211
count_path_runtype_values(const SkPath & path,int * itop,int * ibot)212 static int count_path_runtype_values(const SkPath& path, int* itop, int* ibot) {
213 static const uint8_t gPathVerbToInitialLastIndex[] = {
214 0, // kMove_Verb
215 1, // kLine_Verb
216 2, // kQuad_Verb
217 3, // kCubic_Verb
218 0, // kClose_Verb
219 0 // kDone_Verb
220 };
221
222 static const uint8_t gPathVerbToMaxEdges[] = {
223 0, // kMove_Verb
224 1, // kLine_Verb
225 2, // kQuad_VerbB
226 3, // kCubic_Verb
227 0, // kClose_Verb
228 0 // kDone_Verb
229 };
230
231 SkPath::Iter iter(path, true);
232 SkPoint pts[4];
233 SkPath::Verb verb;
234
235 int maxEdges = 0;
236 SkScalar top = SkIntToScalar(SK_MaxS16);
237 SkScalar bot = SkIntToScalar(SK_MinS16);
238
239 while ((verb = iter.next(pts)) != SkPath::kDone_Verb) {
240 maxEdges += gPathVerbToMaxEdges[verb];
241
242 int lastIndex = gPathVerbToInitialLastIndex[verb];
243 if (lastIndex > 0) {
244 for (int i = 1; i <= lastIndex; i++) {
245 if (top > pts[i].fY) {
246 top = pts[i].fY;
247 } else if (bot < pts[i].fY) {
248 bot = pts[i].fY;
249 }
250 }
251 } else if (SkPath::kMove_Verb == verb) {
252 if (top > pts[0].fY) {
253 top = pts[0].fY;
254 } else if (bot < pts[0].fY) {
255 bot = pts[0].fY;
256 }
257 }
258 }
259 SkASSERT(top <= bot);
260
261 *itop = SkScalarRound(top);
262 *ibot = SkScalarRound(bot);
263 return maxEdges;
264 }
265
setPath(const SkPath & path,const SkRegion & clip)266 bool SkRegion::setPath(const SkPath& path, const SkRegion& clip) {
267 SkDEBUGCODE(this->validate();)
268
269 if (clip.isEmpty()) {
270 return this->setEmpty();
271 }
272
273 if (path.isEmpty()) {
274 if (path.isInverseFillType()) {
275 return this->set(clip);
276 } else {
277 return this->setEmpty();
278 }
279 }
280
281 // compute worst-case rgn-size for the path
282 int pathTop, pathBot;
283 int pathTransitions = count_path_runtype_values(path, &pathTop, &pathBot);
284 int clipTop, clipBot;
285 int clipTransitions;
286
287 clipTransitions = clip.count_runtype_values(&clipTop, &clipBot);
288
289 int top = SkMax32(pathTop, clipTop);
290 int bot = SkMin32(pathBot, clipBot);
291
292 if (top >= bot)
293 return this->setEmpty();
294
295 SkRgnBuilder builder;
296
297 if (!builder.init(bot - top, SkMax32(pathTransitions, clipTransitions))) {
298 // can't allocate working space, so return false
299 return this->setEmpty();
300 }
301
302 SkScan::FillPath(path, clip, &builder);
303 builder.done();
304
305 int count = builder.computeRunCount();
306 if (count == 0) {
307 return this->setEmpty();
308 } else if (count == kRectRegionRuns) {
309 builder.copyToRect(&fBounds);
310 this->setRect(fBounds);
311 } else {
312 SkRegion tmp;
313
314 tmp.fRunHead = RunHead::Alloc(count);
315 builder.copyToRgn(tmp.fRunHead->writable_runs());
316 ComputeRunBounds(tmp.fRunHead->readonly_runs(), count, &tmp.fBounds);
317 this->swap(tmp);
318 }
319 SkDEBUGCODE(this->validate();)
320 return true;
321 }
322
323 /////////////////////////////////////////////////////////////////////////////////////////////////
324 /////////////////////////////////////////////////////////////////////////////////////////////////
325
326 struct Edge {
327 enum {
328 kY0Link = 0x01,
329 kY1Link = 0x02,
330
331 kCompleteLink = (kY0Link | kY1Link)
332 };
333
334 SkRegion::RunType fX;
335 SkRegion::RunType fY0, fY1;
336 uint8_t fFlags;
337 Edge* fNext;
338
setEdge339 void set(int x, int y0, int y1) {
340 SkASSERT(y0 != y1);
341
342 fX = (SkRegion::RunType)(x);
343 fY0 = (SkRegion::RunType)(y0);
344 fY1 = (SkRegion::RunType)(y1);
345 fFlags = 0;
346 SkDEBUGCODE(fNext = NULL;)
347 }
348
topEdge349 int top() const {
350 return SkFastMin32(fY0, fY1);
351 }
352 };
353
find_link(Edge * base,Edge * stop)354 static void find_link(Edge* base, Edge* stop) {
355 SkASSERT(base < stop);
356
357 if (base->fFlags == Edge::kCompleteLink) {
358 SkASSERT(base->fNext);
359 return;
360 }
361
362 SkASSERT(base + 1 < stop);
363
364 int y0 = base->fY0;
365 int y1 = base->fY1;
366
367 Edge* e = base;
368 if ((base->fFlags & Edge::kY0Link) == 0) {
369 for (;;) {
370 e += 1;
371 if ((e->fFlags & Edge::kY1Link) == 0 && y0 == e->fY1) {
372 SkASSERT(NULL == e->fNext);
373 e->fNext = base;
374 e->fFlags = SkToU8(e->fFlags | Edge::kY1Link);
375 break;
376 }
377 }
378 }
379
380 e = base;
381 if ((base->fFlags & Edge::kY1Link) == 0) {
382 for (;;) {
383 e += 1;
384 if ((e->fFlags & Edge::kY0Link) == 0 && y1 == e->fY0) {
385 SkASSERT(NULL == base->fNext);
386 base->fNext = e;
387 e->fFlags = SkToU8(e->fFlags | Edge::kY0Link);
388 break;
389 }
390 }
391 }
392
393 base->fFlags = Edge::kCompleteLink;
394 }
395
extract_path(Edge * edge,Edge * stop,SkPath * path)396 static int extract_path(Edge* edge, Edge* stop, SkPath* path) {
397 while (0 == edge->fFlags) {
398 edge++; // skip over "used" edges
399 }
400
401 SkASSERT(edge < stop);
402
403 Edge* base = edge;
404 Edge* prev = edge;
405 edge = edge->fNext;
406 SkASSERT(edge != base);
407
408 int count = 1;
409 path->moveTo(SkIntToScalar(prev->fX), SkIntToScalar(prev->fY0));
410 prev->fFlags = 0;
411 do {
412 if (prev->fX != edge->fX || prev->fY1 != edge->fY0) { // skip collinear
413 path->lineTo(SkIntToScalar(prev->fX), SkIntToScalar(prev->fY1)); // V
414 path->lineTo(SkIntToScalar(edge->fX), SkIntToScalar(edge->fY0)); // H
415 }
416 prev = edge;
417 edge = edge->fNext;
418 count += 1;
419 prev->fFlags = 0;
420 } while (edge != base);
421 path->lineTo(SkIntToScalar(prev->fX), SkIntToScalar(prev->fY1)); // V
422 path->close();
423 return count;
424 }
425
426 #include "SkTSearch.h"
427
EdgeProc(const Edge * a,const Edge * b)428 static int EdgeProc(const Edge* a, const Edge* b) {
429 return (a->fX == b->fX) ? a->top() - b->top() : a->fX - b->fX;
430 }
431
getBoundaryPath(SkPath * path) const432 bool SkRegion::getBoundaryPath(SkPath* path) const {
433 if (this->isEmpty()) {
434 return false;
435 }
436
437 const SkIRect& bounds = this->getBounds();
438
439 if (this->isRect()) {
440 SkRect r;
441 r.set(bounds); // this converts the ints to scalars
442 path->addRect(r);
443 return true;
444 }
445
446 SkRegion::Iterator iter(*this);
447 SkTDArray<Edge> edges;
448
449 for (const SkIRect& r = iter.rect(); !iter.done(); iter.next()) {
450 Edge* edge = edges.append(2);
451 edge[0].set(r.fLeft, r.fBottom, r.fTop);
452 edge[1].set(r.fRight, r.fTop, r.fBottom);
453 }
454 SkQSort(edges.begin(), edges.count(), sizeof(Edge), (SkQSortCompareProc)EdgeProc);
455
456 int count = edges.count();
457 Edge* start = edges.begin();
458 Edge* stop = start + count;
459 Edge* e;
460
461 for (e = start; e != stop; e++) {
462 find_link(e, stop);
463 }
464
465 #ifdef SK_DEBUG
466 for (e = start; e != stop; e++) {
467 SkASSERT(e->fNext != NULL);
468 SkASSERT(e->fFlags == Edge::kCompleteLink);
469 }
470 #endif
471
472 path->incReserve(count << 1);
473 do {
474 SkASSERT(count > 1);
475 count -= extract_path(start, stop, path);
476 } while (count > 0);
477
478 return true;
479 }
480
481