Line data Source code
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 "SkTSort.h"
12 : #include "SkTDArray.h"
13 : #include "SkPath.h"
14 :
15 : // The rgnbuilder caller *seems* to pass short counts, possible often seens early failure, so
16 : // we may not want to promote this to a "std" routine just yet.
17 0 : static bool sk_memeq32(const int32_t* SK_RESTRICT a, const int32_t* SK_RESTRICT b, int count) {
18 0 : for (int i = 0; i < count; ++i) {
19 0 : if (a[i] != b[i]) {
20 0 : return false;
21 : }
22 : }
23 0 : return true;
24 : }
25 :
26 : class SkRgnBuilder : public SkBlitter {
27 : public:
28 : SkRgnBuilder();
29 : ~SkRgnBuilder() override;
30 :
31 : // returns true if it could allocate the working storage needed
32 : bool init(int maxHeight, int maxTransitions, bool pathIsInverse);
33 :
34 0 : void done() {
35 0 : if (fCurrScanline != nullptr) {
36 0 : fCurrScanline->fXCount = (SkRegion::RunType)((int)(fCurrXPtr - fCurrScanline->firstX()));
37 0 : if (!this->collapsWithPrev()) { // flush the last line
38 0 : fCurrScanline = fCurrScanline->nextScanline();
39 : }
40 : }
41 0 : }
42 :
43 : int computeRunCount() const;
44 : void copyToRect(SkIRect*) const;
45 : void copyToRgn(SkRegion::RunType runs[]) const;
46 :
47 : void blitH(int x, int y, int width) override;
48 0 : void blitAntiH(int x, int y, const SkAlpha antialias[], const int16_t runs[]) override {
49 0 : SkDEBUGFAIL("blitAntiH not implemented");
50 0 : }
51 :
52 : #ifdef SK_DEBUG
53 : void dump() const {
54 : SkDebugf("SkRgnBuilder: Top = %d\n", fTop);
55 : const Scanline* line = (Scanline*)fStorage;
56 : while (line < fCurrScanline) {
57 : SkDebugf("SkRgnBuilder::Scanline: LastY=%d, fXCount=%d", line->fLastY, line->fXCount);
58 : for (int i = 0; i < line->fXCount; i++) {
59 : SkDebugf(" %d", line->firstX()[i]);
60 : }
61 : SkDebugf("\n");
62 :
63 : line = line->nextScanline();
64 : }
65 : }
66 : #endif
67 : private:
68 : /*
69 : * Scanline mimics a row in the region, nearly. A row in a region is:
70 : * [Bottom IntervalCount [L R]... Sentinel]
71 : * while a Scanline is
72 : * [LastY XCount [L R]... uninitialized]
73 : * The two are the same length (which is good), but we have to transmute
74 : * the scanline a little when we convert it to a region-row.
75 : *
76 : * Potentially we could recode this to exactly match the row format, in
77 : * which case copyToRgn() could be a single memcpy. Not sure that is worth
78 : * the effort.
79 : */
80 : struct Scanline {
81 : SkRegion::RunType fLastY;
82 : SkRegion::RunType fXCount;
83 :
84 0 : SkRegion::RunType* firstX() const { return (SkRegion::RunType*)(this + 1); }
85 0 : Scanline* nextScanline() const {
86 : // add final +1 for the x-sentinel
87 0 : return (Scanline*)((SkRegion::RunType*)(this + 1) + fXCount + 1);
88 : }
89 : };
90 : SkRegion::RunType* fStorage;
91 : Scanline* fCurrScanline;
92 : Scanline* fPrevScanline;
93 : // points at next avialable x[] in fCurrScanline
94 : SkRegion::RunType* fCurrXPtr;
95 : SkRegion::RunType fTop; // first Y value
96 :
97 : int fStorageCount;
98 :
99 0 : bool collapsWithPrev() {
100 0 : if (fPrevScanline != nullptr &&
101 0 : fPrevScanline->fLastY + 1 == fCurrScanline->fLastY &&
102 0 : fPrevScanline->fXCount == fCurrScanline->fXCount &&
103 0 : sk_memeq32(fPrevScanline->firstX(), fCurrScanline->firstX(), fCurrScanline->fXCount))
104 : {
105 : // update the height of fPrevScanline
106 0 : fPrevScanline->fLastY = fCurrScanline->fLastY;
107 0 : return true;
108 : }
109 0 : return false;
110 : }
111 : };
112 :
113 0 : SkRgnBuilder::SkRgnBuilder()
114 0 : : fStorage(nullptr) {
115 0 : }
116 :
117 0 : SkRgnBuilder::~SkRgnBuilder() {
118 0 : sk_free(fStorage);
119 0 : }
120 :
121 0 : bool SkRgnBuilder::init(int maxHeight, int maxTransitions, bool pathIsInverse) {
122 0 : if ((maxHeight | maxTransitions) < 0) {
123 0 : return false;
124 : }
125 :
126 0 : if (pathIsInverse) {
127 : // allow for additional X transitions to "invert" each scanline
128 : // [ L' ... normal transitions ... R' ]
129 : //
130 0 : maxTransitions += 2;
131 : }
132 :
133 : // compute the count with +1 and +3 slop for the working buffer
134 0 : int64_t count = sk_64_mul(maxHeight + 1, 3 + maxTransitions);
135 :
136 0 : if (pathIsInverse) {
137 : // allow for two "empty" rows for the top and bottom
138 : // [ Y, 1, L, R, S] == 5 (*2 for top and bottom)
139 0 : count += 10;
140 : }
141 :
142 0 : if (count < 0 || !sk_64_isS32(count)) {
143 0 : return false;
144 : }
145 0 : fStorageCount = sk_64_asS32(count);
146 :
147 0 : int64_t size = sk_64_mul(fStorageCount, sizeof(SkRegion::RunType));
148 0 : if (size < 0 || !sk_64_isS32(size)) {
149 0 : return false;
150 : }
151 :
152 0 : fStorage = (SkRegion::RunType*)sk_malloc_flags(sk_64_asS32(size), 0);
153 0 : if (nullptr == fStorage) {
154 0 : return false;
155 : }
156 :
157 0 : fCurrScanline = nullptr; // signal empty collection
158 0 : fPrevScanline = nullptr; // signal first scanline
159 0 : return true;
160 : }
161 :
162 0 : void SkRgnBuilder::blitH(int x, int y, int width) {
163 0 : if (fCurrScanline == nullptr) { // first time
164 0 : fTop = (SkRegion::RunType)(y);
165 0 : fCurrScanline = (Scanline*)fStorage;
166 0 : fCurrScanline->fLastY = (SkRegion::RunType)(y);
167 0 : fCurrXPtr = fCurrScanline->firstX();
168 : } else {
169 0 : SkASSERT(y >= fCurrScanline->fLastY);
170 :
171 0 : if (y > fCurrScanline->fLastY) {
172 : // if we get here, we're done with fCurrScanline
173 0 : fCurrScanline->fXCount = (SkRegion::RunType)((int)(fCurrXPtr - fCurrScanline->firstX()));
174 :
175 0 : int prevLastY = fCurrScanline->fLastY;
176 0 : if (!this->collapsWithPrev()) {
177 0 : fPrevScanline = fCurrScanline;
178 0 : fCurrScanline = fCurrScanline->nextScanline();
179 :
180 : }
181 0 : if (y - 1 > prevLastY) { // insert empty run
182 0 : fCurrScanline->fLastY = (SkRegion::RunType)(y - 1);
183 0 : fCurrScanline->fXCount = 0;
184 0 : fCurrScanline = fCurrScanline->nextScanline();
185 : }
186 : // setup for the new curr line
187 0 : fCurrScanline->fLastY = (SkRegion::RunType)(y);
188 0 : fCurrXPtr = fCurrScanline->firstX();
189 : }
190 : }
191 : // check if we should extend the current run, or add a new one
192 0 : if (fCurrXPtr > fCurrScanline->firstX() && fCurrXPtr[-1] == x) {
193 0 : fCurrXPtr[-1] = (SkRegion::RunType)(x + width);
194 : } else {
195 0 : fCurrXPtr[0] = (SkRegion::RunType)(x);
196 0 : fCurrXPtr[1] = (SkRegion::RunType)(x + width);
197 0 : fCurrXPtr += 2;
198 : }
199 0 : SkASSERT(fCurrXPtr - fStorage < fStorageCount);
200 0 : }
201 :
202 0 : int SkRgnBuilder::computeRunCount() const {
203 0 : if (fCurrScanline == nullptr) {
204 0 : return 0;
205 : }
206 :
207 0 : const SkRegion::RunType* line = fStorage;
208 0 : const SkRegion::RunType* stop = (const SkRegion::RunType*)fCurrScanline;
209 :
210 0 : return 2 + (int)(stop - line);
211 : }
212 :
213 0 : void SkRgnBuilder::copyToRect(SkIRect* r) const {
214 0 : SkASSERT(fCurrScanline != nullptr);
215 : // A rect's scanline is [bottom intervals left right sentinel] == 5
216 0 : SkASSERT((const SkRegion::RunType*)fCurrScanline - fStorage == 5);
217 :
218 0 : const Scanline* line = (const Scanline*)fStorage;
219 0 : SkASSERT(line->fXCount == 2);
220 :
221 0 : r->set(line->firstX()[0], fTop, line->firstX()[1], line->fLastY + 1);
222 0 : }
223 :
224 0 : void SkRgnBuilder::copyToRgn(SkRegion::RunType runs[]) const {
225 0 : SkASSERT(fCurrScanline != nullptr);
226 0 : SkASSERT((const SkRegion::RunType*)fCurrScanline - fStorage > 4);
227 :
228 0 : const Scanline* line = (const Scanline*)fStorage;
229 0 : const Scanline* stop = fCurrScanline;
230 :
231 0 : *runs++ = fTop;
232 0 : do {
233 0 : *runs++ = (SkRegion::RunType)(line->fLastY + 1);
234 0 : int count = line->fXCount;
235 0 : *runs++ = count >> 1; // intervalCount
236 0 : if (count) {
237 0 : memcpy(runs, line->firstX(), count * sizeof(SkRegion::RunType));
238 0 : runs += count;
239 : }
240 0 : *runs++ = SkRegion::kRunTypeSentinel;
241 0 : line = line->nextScanline();
242 0 : } while (line < stop);
243 0 : SkASSERT(line == stop);
244 0 : *runs = SkRegion::kRunTypeSentinel;
245 0 : }
246 :
247 0 : static unsigned verb_to_initial_last_index(unsigned verb) {
248 : static const uint8_t gPathVerbToInitialLastIndex[] = {
249 : 0, // kMove_Verb
250 : 1, // kLine_Verb
251 : 2, // kQuad_Verb
252 : 2, // kConic_Verb
253 : 3, // kCubic_Verb
254 : 0, // kClose_Verb
255 : 0 // kDone_Verb
256 : };
257 0 : SkASSERT((unsigned)verb < SK_ARRAY_COUNT(gPathVerbToInitialLastIndex));
258 0 : return gPathVerbToInitialLastIndex[verb];
259 : }
260 :
261 0 : static unsigned verb_to_max_edges(unsigned verb) {
262 : static const uint8_t gPathVerbToMaxEdges[] = {
263 : 0, // kMove_Verb
264 : 1, // kLine_Verb
265 : 2, // kQuad_VerbB
266 : 2, // kConic_VerbB
267 : 3, // kCubic_Verb
268 : 0, // kClose_Verb
269 : 0 // kDone_Verb
270 : };
271 0 : SkASSERT((unsigned)verb < SK_ARRAY_COUNT(gPathVerbToMaxEdges));
272 0 : return gPathVerbToMaxEdges[verb];
273 : }
274 :
275 : // If returns 0, ignore itop and ibot
276 0 : static int count_path_runtype_values(const SkPath& path, int* itop, int* ibot) {
277 0 : SkPath::Iter iter(path, true);
278 : SkPoint pts[4];
279 : SkPath::Verb verb;
280 :
281 0 : int maxEdges = 0;
282 0 : SkScalar top = SkIntToScalar(SK_MaxS16);
283 0 : SkScalar bot = SkIntToScalar(SK_MinS16);
284 :
285 0 : while ((verb = iter.next(pts, false)) != SkPath::kDone_Verb) {
286 0 : maxEdges += verb_to_max_edges(verb);
287 :
288 0 : int lastIndex = verb_to_initial_last_index(verb);
289 0 : if (lastIndex > 0) {
290 0 : for (int i = 1; i <= lastIndex; i++) {
291 0 : if (top > pts[i].fY) {
292 0 : top = pts[i].fY;
293 0 : } else if (bot < pts[i].fY) {
294 0 : bot = pts[i].fY;
295 : }
296 : }
297 0 : } else if (SkPath::kMove_Verb == verb) {
298 0 : if (top > pts[0].fY) {
299 0 : top = pts[0].fY;
300 0 : } else if (bot < pts[0].fY) {
301 0 : bot = pts[0].fY;
302 : }
303 : }
304 : }
305 0 : if (0 == maxEdges) {
306 0 : return 0; // we have only moves+closes
307 : }
308 :
309 0 : SkASSERT(top <= bot);
310 0 : *itop = SkScalarRoundToInt(top);
311 0 : *ibot = SkScalarRoundToInt(bot);
312 0 : return maxEdges;
313 : }
314 :
315 0 : static bool check_inverse_on_empty_return(SkRegion* dst, const SkPath& path, const SkRegion& clip) {
316 0 : if (path.isInverseFillType()) {
317 0 : return dst->set(clip);
318 : } else {
319 0 : return dst->setEmpty();
320 : }
321 : }
322 :
323 0 : bool SkRegion::setPath(const SkPath& path, const SkRegion& clip) {
324 0 : SkDEBUGCODE(this->validate();)
325 :
326 0 : if (clip.isEmpty()) {
327 0 : return this->setEmpty();
328 : }
329 :
330 0 : if (path.isEmpty()) {
331 0 : return check_inverse_on_empty_return(this, path, clip);
332 : }
333 :
334 : // compute worst-case rgn-size for the path
335 : int pathTop, pathBot;
336 0 : int pathTransitions = count_path_runtype_values(path, &pathTop, &pathBot);
337 0 : if (0 == pathTransitions) {
338 0 : return check_inverse_on_empty_return(this, path, clip);
339 : }
340 :
341 : int clipTop, clipBot;
342 0 : int clipTransitions = clip.count_runtype_values(&clipTop, &clipBot);
343 :
344 0 : int top = SkMax32(pathTop, clipTop);
345 0 : int bot = SkMin32(pathBot, clipBot);
346 0 : if (top >= bot) {
347 0 : return check_inverse_on_empty_return(this, path, clip);
348 : }
349 :
350 0 : SkRgnBuilder builder;
351 :
352 0 : if (!builder.init(bot - top,
353 : SkMax32(pathTransitions, clipTransitions),
354 0 : path.isInverseFillType())) {
355 : // can't allocate working space, so return false
356 0 : return this->setEmpty();
357 : }
358 :
359 0 : SkScan::FillPath(path, clip, &builder);
360 0 : builder.done();
361 :
362 0 : int count = builder.computeRunCount();
363 0 : if (count == 0) {
364 0 : return this->setEmpty();
365 0 : } else if (count == kRectRegionRuns) {
366 0 : builder.copyToRect(&fBounds);
367 0 : this->setRect(fBounds);
368 : } else {
369 0 : SkRegion tmp;
370 :
371 0 : tmp.fRunHead = RunHead::Alloc(count);
372 0 : builder.copyToRgn(tmp.fRunHead->writable_runs());
373 0 : tmp.fRunHead->computeRunBounds(&tmp.fBounds);
374 0 : this->swap(tmp);
375 : }
376 0 : SkDEBUGCODE(this->validate();)
377 0 : return true;
378 : }
379 :
380 : /////////////////////////////////////////////////////////////////////////////////////////////////
381 : /////////////////////////////////////////////////////////////////////////////////////////////////
382 :
383 : struct Edge {
384 : enum {
385 : kY0Link = 0x01,
386 : kY1Link = 0x02,
387 :
388 : kCompleteLink = (kY0Link | kY1Link)
389 : };
390 :
391 : SkRegion::RunType fX;
392 : SkRegion::RunType fY0, fY1;
393 : uint8_t fFlags;
394 : Edge* fNext;
395 :
396 0 : void set(int x, int y0, int y1) {
397 0 : SkASSERT(y0 != y1);
398 :
399 0 : fX = (SkRegion::RunType)(x);
400 0 : fY0 = (SkRegion::RunType)(y0);
401 0 : fY1 = (SkRegion::RunType)(y1);
402 0 : fFlags = 0;
403 0 : SkDEBUGCODE(fNext = nullptr;)
404 0 : }
405 :
406 0 : int top() const {
407 0 : return SkFastMin32(fY0, fY1);
408 : }
409 : };
410 :
411 0 : static void find_link(Edge* base, Edge* stop) {
412 0 : SkASSERT(base < stop);
413 :
414 0 : if (base->fFlags == Edge::kCompleteLink) {
415 0 : SkASSERT(base->fNext);
416 0 : return;
417 : }
418 :
419 0 : SkASSERT(base + 1 < stop);
420 :
421 0 : int y0 = base->fY0;
422 0 : int y1 = base->fY1;
423 :
424 0 : Edge* e = base;
425 0 : if ((base->fFlags & Edge::kY0Link) == 0) {
426 : for (;;) {
427 0 : e += 1;
428 0 : if ((e->fFlags & Edge::kY1Link) == 0 && y0 == e->fY1) {
429 0 : SkASSERT(nullptr == e->fNext);
430 0 : e->fNext = base;
431 0 : e->fFlags = SkToU8(e->fFlags | Edge::kY1Link);
432 0 : break;
433 : }
434 : }
435 : }
436 :
437 0 : e = base;
438 0 : if ((base->fFlags & Edge::kY1Link) == 0) {
439 : for (;;) {
440 0 : e += 1;
441 0 : if ((e->fFlags & Edge::kY0Link) == 0 && y1 == e->fY0) {
442 0 : SkASSERT(nullptr == base->fNext);
443 0 : base->fNext = e;
444 0 : e->fFlags = SkToU8(e->fFlags | Edge::kY0Link);
445 0 : break;
446 : }
447 : }
448 : }
449 :
450 0 : base->fFlags = Edge::kCompleteLink;
451 : }
452 :
453 0 : static int extract_path(Edge* edge, Edge* stop, SkPath* path) {
454 0 : while (0 == edge->fFlags) {
455 0 : edge++; // skip over "used" edges
456 : }
457 :
458 0 : SkASSERT(edge < stop);
459 :
460 0 : Edge* base = edge;
461 0 : Edge* prev = edge;
462 0 : edge = edge->fNext;
463 0 : SkASSERT(edge != base);
464 :
465 0 : int count = 1;
466 0 : path->moveTo(SkIntToScalar(prev->fX), SkIntToScalar(prev->fY0));
467 0 : prev->fFlags = 0;
468 0 : do {
469 0 : if (prev->fX != edge->fX || prev->fY1 != edge->fY0) { // skip collinear
470 0 : path->lineTo(SkIntToScalar(prev->fX), SkIntToScalar(prev->fY1)); // V
471 0 : path->lineTo(SkIntToScalar(edge->fX), SkIntToScalar(edge->fY0)); // H
472 : }
473 0 : prev = edge;
474 0 : edge = edge->fNext;
475 0 : count += 1;
476 0 : prev->fFlags = 0;
477 0 : } while (edge != base);
478 0 : path->lineTo(SkIntToScalar(prev->fX), SkIntToScalar(prev->fY1)); // V
479 0 : path->close();
480 0 : return count;
481 : }
482 :
483 : struct EdgeLT {
484 0 : bool operator()(const Edge& a, const Edge& b) const {
485 0 : return (a.fX == b.fX) ? a.top() < b.top() : a.fX < b.fX;
486 : }
487 : };
488 :
489 0 : bool SkRegion::getBoundaryPath(SkPath* path) const {
490 : // path could safely be nullptr if we're empty, but the caller shouldn't
491 : // *know* that
492 0 : SkASSERT(path);
493 :
494 0 : if (this->isEmpty()) {
495 0 : return false;
496 : }
497 :
498 0 : const SkIRect& bounds = this->getBounds();
499 :
500 0 : if (this->isRect()) {
501 : SkRect r;
502 0 : r.set(bounds); // this converts the ints to scalars
503 0 : path->addRect(r);
504 0 : return true;
505 : }
506 :
507 0 : SkRegion::Iterator iter(*this);
508 0 : SkTDArray<Edge> edges;
509 :
510 0 : for (const SkIRect& r = iter.rect(); !iter.done(); iter.next()) {
511 0 : Edge* edge = edges.append(2);
512 0 : edge[0].set(r.fLeft, r.fBottom, r.fTop);
513 0 : edge[1].set(r.fRight, r.fTop, r.fBottom);
514 : }
515 :
516 0 : int count = edges.count();
517 0 : Edge* start = edges.begin();
518 0 : Edge* stop = start + count;
519 0 : SkTQSort<Edge>(start, stop - 1, EdgeLT());
520 :
521 : Edge* e;
522 0 : for (e = start; e != stop; e++) {
523 0 : find_link(e, stop);
524 : }
525 :
526 : #ifdef SK_DEBUG
527 0 : for (e = start; e != stop; e++) {
528 0 : SkASSERT(e->fNext != nullptr);
529 0 : SkASSERT(e->fFlags == Edge::kCompleteLink);
530 : }
531 : #endif
532 :
533 0 : path->incReserve(count << 1);
534 0 : do {
535 0 : SkASSERT(count > 1);
536 0 : count -= extract_path(start, stop, path);
537 0 : } while (count > 0);
538 :
539 0 : return true;
540 : }
|
