2 * Copyright 2006 The Android Open Source Project
4 * Use of this source code is governed by a BSD-style license that can be
5 * found in the LICENSE file.
8 #include "SkRegionPriv.h"
11 #include "SkTDArray.h"
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.
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) {
25 class SkRgnBuilder : public SkBlitter {
28 virtual ~SkRgnBuilder();
30 // returns true if it could allocate the working storage needed
31 bool init(int maxHeight, int maxTransitions, bool pathIsInverse);
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();
42 int computeRunCount() const;
43 void copyToRect(SkIRect*) const;
44 void copyToRgn(SkRegion::RunType runs[]) const;
46 void blitH(int x, int y, int width) override;
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]);
59 line = line->nextScanline();
65 * Scanline mimics a row in the region, nearly. A row in a region is:
66 * [Bottom IntervalCount [L R]... Sentinel]
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.
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
77 SkRegion::RunType fLastY;
78 SkRegion::RunType fXCount;
80 SkRegion::RunType* firstX() const { return (SkRegion::RunType*)(this + 1); }
81 Scanline* nextScanline() const {
82 // add final +1 for the x-sentinel
83 return (Scanline*)((SkRegion::RunType*)(this + 1) + fXCount + 1);
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
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))
101 // update the height of fPrevScanline
102 fPrevScanline->fLastY = fCurrScanline->fLastY;
109 SkRgnBuilder::SkRgnBuilder()
113 SkRgnBuilder::~SkRgnBuilder() {
117 bool SkRgnBuilder::init(int maxHeight, int maxTransitions, bool pathIsInverse) {
118 if ((maxHeight | maxTransitions) < 0) {
123 // allow for additional X transitions to "invert" each scanline
124 // [ L' ... normal transitions ... R' ]
129 // compute the count with +1 and +3 slop for the working buffer
130 int64_t count = sk_64_mul(maxHeight + 1, 3 + maxTransitions);
133 // allow for two "empty" rows for the top and bottom
134 // [ Y, 1, L, R, S] == 5 (*2 for top and bottom)
138 if (count < 0 || !sk_64_isS32(count)) {
141 fStorageCount = sk_64_asS32(count);
143 int64_t size = sk_64_mul(fStorageCount, sizeof(SkRegion::RunType));
144 if (size < 0 || !sk_64_isS32(size)) {
148 fStorage = (SkRegion::RunType*)sk_malloc_flags(sk_64_asS32(size), 0);
149 if (NULL == fStorage) {
153 fCurrScanline = NULL; // signal empty collection
154 fPrevScanline = NULL; // signal first scanline
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();
165 SkASSERT(y >= fCurrScanline->fLastY);
167 if (y > fCurrScanline->fLastY) {
168 // if we get here, we're done with fCurrScanline
169 fCurrScanline->fXCount = (SkRegion::RunType)((int)(fCurrXPtr - fCurrScanline->firstX()));
171 int prevLastY = fCurrScanline->fLastY;
172 if (!this->collapsWithPrev()) {
173 fPrevScanline = fCurrScanline;
174 fCurrScanline = fCurrScanline->nextScanline();
177 if (y - 1 > prevLastY) { // insert empty run
178 fCurrScanline->fLastY = (SkRegion::RunType)(y - 1);
179 fCurrScanline->fXCount = 0;
180 fCurrScanline = fCurrScanline->nextScanline();
182 // setup for the new curr line
183 fCurrScanline->fLastY = (SkRegion::RunType)(y);
184 fCurrXPtr = fCurrScanline->firstX();
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);
191 fCurrXPtr[0] = (SkRegion::RunType)(x);
192 fCurrXPtr[1] = (SkRegion::RunType)(x + width);
195 SkASSERT(fCurrXPtr - fStorage < fStorageCount);
198 int SkRgnBuilder::computeRunCount() const {
199 if (fCurrScanline == NULL) {
203 const SkRegion::RunType* line = fStorage;
204 const SkRegion::RunType* stop = (const SkRegion::RunType*)fCurrScanline;
206 return 2 + (int)(stop - line);
209 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);
214 const Scanline* line = (const Scanline*)fStorage;
215 SkASSERT(line->fXCount == 2);
217 r->set(line->firstX()[0], fTop, line->firstX()[1], line->fLastY + 1);
220 void SkRgnBuilder::copyToRgn(SkRegion::RunType runs[]) const {
221 SkASSERT(fCurrScanline != NULL);
222 SkASSERT((const SkRegion::RunType*)fCurrScanline - fStorage > 4);
224 const Scanline* line = (const Scanline*)fStorage;
225 const Scanline* stop = fCurrScanline;
229 *runs++ = (SkRegion::RunType)(line->fLastY + 1);
230 int count = line->fXCount;
231 *runs++ = count >> 1; // intervalCount
233 memcpy(runs, line->firstX(), count * sizeof(SkRegion::RunType));
236 *runs++ = SkRegion::kRunTypeSentinel;
237 line = line->nextScanline();
238 } while (line < stop);
239 SkASSERT(line == stop);
240 *runs = SkRegion::kRunTypeSentinel;
243 static unsigned verb_to_initial_last_index(unsigned verb) {
244 static const uint8_t gPathVerbToInitialLastIndex[] = {
253 SkASSERT((unsigned)verb < SK_ARRAY_COUNT(gPathVerbToInitialLastIndex));
254 return gPathVerbToInitialLastIndex[verb];
257 static unsigned verb_to_max_edges(unsigned verb) {
258 static const uint8_t gPathVerbToMaxEdges[] = {
267 SkASSERT((unsigned)verb < SK_ARRAY_COUNT(gPathVerbToMaxEdges));
268 return gPathVerbToMaxEdges[verb];
271 // If returns 0, ignore itop and ibot
272 static int count_path_runtype_values(const SkPath& path, int* itop, int* ibot) {
273 SkPath::Iter iter(path, true);
278 SkScalar top = SkIntToScalar(SK_MaxS16);
279 SkScalar bot = SkIntToScalar(SK_MinS16);
281 while ((verb = iter.next(pts, false)) != SkPath::kDone_Verb) {
282 maxEdges += verb_to_max_edges(verb);
284 int lastIndex = verb_to_initial_last_index(verb);
286 for (int i = 1; i <= lastIndex; i++) {
287 if (top > pts[i].fY) {
289 } else if (bot < pts[i].fY) {
293 } else if (SkPath::kMove_Verb == verb) {
294 if (top > pts[0].fY) {
296 } else if (bot < pts[0].fY) {
302 return 0; // we have only moves+closes
305 SkASSERT(top <= bot);
306 *itop = SkScalarRoundToInt(top);
307 *ibot = SkScalarRoundToInt(bot);
311 static bool check_inverse_on_empty_return(SkRegion* dst, const SkPath& path, const SkRegion& clip) {
312 if (path.isInverseFillType()) {
313 return dst->set(clip);
315 return dst->setEmpty();
319 bool SkRegion::setPath(const SkPath& path, const SkRegion& clip) {
320 SkDEBUGCODE(this->validate();)
322 if (clip.isEmpty()) {
323 return this->setEmpty();
326 if (path.isEmpty()) {
327 return check_inverse_on_empty_return(this, path, clip);
330 // compute worst-case rgn-size for the path
331 int pathTop, pathBot;
332 int pathTransitions = count_path_runtype_values(path, &pathTop, &pathBot);
333 if (0 == pathTransitions) {
334 return check_inverse_on_empty_return(this, path, clip);
337 int clipTop, clipBot;
338 int clipTransitions = clip.count_runtype_values(&clipTop, &clipBot);
340 int top = SkMax32(pathTop, clipTop);
341 int bot = SkMin32(pathBot, clipBot);
343 return check_inverse_on_empty_return(this, path, clip);
346 SkRgnBuilder builder;
348 if (!builder.init(bot - top,
349 SkMax32(pathTransitions, clipTransitions),
350 path.isInverseFillType())) {
351 // can't allocate working space, so return false
352 return this->setEmpty();
355 SkScan::FillPath(path, clip, &builder);
358 int count = builder.computeRunCount();
360 return this->setEmpty();
361 } else if (count == kRectRegionRuns) {
362 builder.copyToRect(&fBounds);
363 this->setRect(fBounds);
367 tmp.fRunHead = RunHead::Alloc(count);
368 builder.copyToRgn(tmp.fRunHead->writable_runs());
369 tmp.fRunHead->computeRunBounds(&tmp.fBounds);
372 SkDEBUGCODE(this->validate();)
376 /////////////////////////////////////////////////////////////////////////////////////////////////
377 /////////////////////////////////////////////////////////////////////////////////////////////////
384 kCompleteLink = (kY0Link | kY1Link)
387 SkRegion::RunType fX;
388 SkRegion::RunType fY0, fY1;
392 void set(int x, int y0, int y1) {
395 fX = (SkRegion::RunType)(x);
396 fY0 = (SkRegion::RunType)(y0);
397 fY1 = (SkRegion::RunType)(y1);
399 SkDEBUGCODE(fNext = NULL;)
403 return SkFastMin32(fY0, fY1);
407 static void find_link(Edge* base, Edge* stop) {
408 SkASSERT(base < stop);
410 if (base->fFlags == Edge::kCompleteLink) {
411 SkASSERT(base->fNext);
415 SkASSERT(base + 1 < stop);
421 if ((base->fFlags & Edge::kY0Link) == 0) {
424 if ((e->fFlags & Edge::kY1Link) == 0 && y0 == e->fY1) {
425 SkASSERT(NULL == e->fNext);
427 e->fFlags = SkToU8(e->fFlags | Edge::kY1Link);
434 if ((base->fFlags & Edge::kY1Link) == 0) {
437 if ((e->fFlags & Edge::kY0Link) == 0 && y1 == e->fY0) {
438 SkASSERT(NULL == base->fNext);
440 e->fFlags = SkToU8(e->fFlags | Edge::kY0Link);
446 base->fFlags = Edge::kCompleteLink;
449 static int extract_path(Edge* edge, Edge* stop, SkPath* path) {
450 while (0 == edge->fFlags) {
451 edge++; // skip over "used" edges
454 SkASSERT(edge < stop);
459 SkASSERT(edge != base);
462 path->moveTo(SkIntToScalar(prev->fX), SkIntToScalar(prev->fY0));
465 if (prev->fX != edge->fX || prev->fY1 != edge->fY0) { // skip collinear
466 path->lineTo(SkIntToScalar(prev->fX), SkIntToScalar(prev->fY1)); // V
467 path->lineTo(SkIntToScalar(edge->fX), SkIntToScalar(edge->fY0)); // H
473 } while (edge != base);
474 path->lineTo(SkIntToScalar(prev->fX), SkIntToScalar(prev->fY1)); // V
479 #include "SkTSearch.h"
481 static int EdgeProc(const Edge* a, const Edge* b) {
482 return (a->fX == b->fX) ? a->top() - b->top() : a->fX - b->fX;
485 bool SkRegion::getBoundaryPath(SkPath* path) const {
486 // path could safely be NULL if we're empty, but the caller shouldn't
490 if (this->isEmpty()) {
494 const SkIRect& bounds = this->getBounds();
496 if (this->isRect()) {
498 r.set(bounds); // this converts the ints to scalars
503 SkRegion::Iterator iter(*this);
504 SkTDArray<Edge> edges;
506 for (const SkIRect& r = iter.rect(); !iter.done(); iter.next()) {
507 Edge* edge = edges.append(2);
508 edge[0].set(r.fLeft, r.fBottom, r.fTop);
509 edge[1].set(r.fRight, r.fTop, r.fBottom);
511 qsort(edges.begin(), edges.count(), sizeof(Edge), SkCastForQSort(EdgeProc));
513 int count = edges.count();
514 Edge* start = edges.begin();
515 Edge* stop = start + count;
518 for (e = start; e != stop; e++) {
523 for (e = start; e != stop; e++) {
524 SkASSERT(e->fNext != NULL);
525 SkASSERT(e->fFlags == Edge::kCompleteLink);
529 path->incReserve(count << 1);
532 count -= extract_path(start, stop, path);