1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/gfx/skia/trunk/src/core/SkRegion_path.cpp Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,520 @@
1.4 +
1.5 +/*
1.6 + * Copyright 2006 The Android Open Source Project
1.7 + *
1.8 + * Use of this source code is governed by a BSD-style license that can be
1.9 + * found in the LICENSE file.
1.10 + */
1.11 +
1.12 +
1.13 +#include "SkRegionPriv.h"
1.14 +#include "SkBlitter.h"
1.15 +#include "SkScan.h"
1.16 +#include "SkTDArray.h"
1.17 +#include "SkPath.h"
1.18 +
1.19 +class SkRgnBuilder : public SkBlitter {
1.20 +public:
1.21 + SkRgnBuilder();
1.22 + virtual ~SkRgnBuilder();
1.23 +
1.24 + // returns true if it could allocate the working storage needed
1.25 + bool init(int maxHeight, int maxTransitions, bool pathIsInverse);
1.26 +
1.27 + void done() {
1.28 + if (fCurrScanline != NULL) {
1.29 + fCurrScanline->fXCount = (SkRegion::RunType)((int)(fCurrXPtr - fCurrScanline->firstX()));
1.30 + if (!this->collapsWithPrev()) { // flush the last line
1.31 + fCurrScanline = fCurrScanline->nextScanline();
1.32 + }
1.33 + }
1.34 + }
1.35 +
1.36 + int computeRunCount() const;
1.37 + void copyToRect(SkIRect*) const;
1.38 + void copyToRgn(SkRegion::RunType runs[]) const;
1.39 +
1.40 + virtual void blitH(int x, int y, int width);
1.41 +
1.42 +#ifdef SK_DEBUG
1.43 + void dump() const {
1.44 + SkDebugf("SkRgnBuilder: Top = %d\n", fTop);
1.45 + const Scanline* line = (Scanline*)fStorage;
1.46 + while (line < fCurrScanline) {
1.47 + SkDebugf("SkRgnBuilder::Scanline: LastY=%d, fXCount=%d", line->fLastY, line->fXCount);
1.48 + for (int i = 0; i < line->fXCount; i++) {
1.49 + SkDebugf(" %d", line->firstX()[i]);
1.50 + }
1.51 + SkDebugf("\n");
1.52 +
1.53 + line = line->nextScanline();
1.54 + }
1.55 + }
1.56 +#endif
1.57 +private:
1.58 + /*
1.59 + * Scanline mimics a row in the region, nearly. A row in a region is:
1.60 + * [Bottom IntervalCount [L R]... Sentinel]
1.61 + * while a Scanline is
1.62 + * [LastY XCount [L R]... uninitialized]
1.63 + * The two are the same length (which is good), but we have to transmute
1.64 + * the scanline a little when we convert it to a region-row.
1.65 + *
1.66 + * Potentially we could recode this to exactly match the row format, in
1.67 + * which case copyToRgn() could be a single memcpy. Not sure that is worth
1.68 + * the effort.
1.69 + */
1.70 + struct Scanline {
1.71 + SkRegion::RunType fLastY;
1.72 + SkRegion::RunType fXCount;
1.73 +
1.74 + SkRegion::RunType* firstX() const { return (SkRegion::RunType*)(this + 1); }
1.75 + Scanline* nextScanline() const {
1.76 + // add final +1 for the x-sentinel
1.77 + return (Scanline*)((SkRegion::RunType*)(this + 1) + fXCount + 1);
1.78 + }
1.79 + };
1.80 + SkRegion::RunType* fStorage;
1.81 + Scanline* fCurrScanline;
1.82 + Scanline* fPrevScanline;
1.83 + // points at next avialable x[] in fCurrScanline
1.84 + SkRegion::RunType* fCurrXPtr;
1.85 + SkRegion::RunType fTop; // first Y value
1.86 +
1.87 + int fStorageCount;
1.88 +
1.89 + bool collapsWithPrev() {
1.90 + if (fPrevScanline != NULL &&
1.91 + fPrevScanline->fLastY + 1 == fCurrScanline->fLastY &&
1.92 + fPrevScanline->fXCount == fCurrScanline->fXCount &&
1.93 + !memcmp(fPrevScanline->firstX(),
1.94 + fCurrScanline->firstX(),
1.95 + fCurrScanline->fXCount * sizeof(SkRegion::RunType)))
1.96 + {
1.97 + // update the height of fPrevScanline
1.98 + fPrevScanline->fLastY = fCurrScanline->fLastY;
1.99 + return true;
1.100 + }
1.101 + return false;
1.102 + }
1.103 +};
1.104 +
1.105 +SkRgnBuilder::SkRgnBuilder()
1.106 + : fStorage(NULL) {
1.107 +}
1.108 +
1.109 +SkRgnBuilder::~SkRgnBuilder() {
1.110 + sk_free(fStorage);
1.111 +}
1.112 +
1.113 +bool SkRgnBuilder::init(int maxHeight, int maxTransitions, bool pathIsInverse) {
1.114 + if ((maxHeight | maxTransitions) < 0) {
1.115 + return false;
1.116 + }
1.117 +
1.118 + if (pathIsInverse) {
1.119 + // allow for additional X transitions to "invert" each scanline
1.120 + // [ L' ... normal transitions ... R' ]
1.121 + //
1.122 + maxTransitions += 2;
1.123 + }
1.124 +
1.125 + // compute the count with +1 and +3 slop for the working buffer
1.126 + int64_t count = sk_64_mul(maxHeight + 1, 3 + maxTransitions);
1.127 +
1.128 + if (pathIsInverse) {
1.129 + // allow for two "empty" rows for the top and bottom
1.130 + // [ Y, 1, L, R, S] == 5 (*2 for top and bottom)
1.131 + count += 10;
1.132 + }
1.133 +
1.134 + if (count < 0 || !sk_64_isS32(count)) {
1.135 + return false;
1.136 + }
1.137 + fStorageCount = sk_64_asS32(count);
1.138 +
1.139 + int64_t size = sk_64_mul(fStorageCount, sizeof(SkRegion::RunType));
1.140 + if (size < 0 || !sk_64_isS32(size)) {
1.141 + return false;
1.142 + }
1.143 +
1.144 + fStorage = (SkRegion::RunType*)sk_malloc_flags(sk_64_asS32(size), 0);
1.145 + if (NULL == fStorage) {
1.146 + return false;
1.147 + }
1.148 +
1.149 + fCurrScanline = NULL; // signal empty collection
1.150 + fPrevScanline = NULL; // signal first scanline
1.151 + return true;
1.152 +}
1.153 +
1.154 +void SkRgnBuilder::blitH(int x, int y, int width) {
1.155 + if (fCurrScanline == NULL) { // first time
1.156 + fTop = (SkRegion::RunType)(y);
1.157 + fCurrScanline = (Scanline*)fStorage;
1.158 + fCurrScanline->fLastY = (SkRegion::RunType)(y);
1.159 + fCurrXPtr = fCurrScanline->firstX();
1.160 + } else {
1.161 + SkASSERT(y >= fCurrScanline->fLastY);
1.162 +
1.163 + if (y > fCurrScanline->fLastY) {
1.164 + // if we get here, we're done with fCurrScanline
1.165 + fCurrScanline->fXCount = (SkRegion::RunType)((int)(fCurrXPtr - fCurrScanline->firstX()));
1.166 +
1.167 + int prevLastY = fCurrScanline->fLastY;
1.168 + if (!this->collapsWithPrev()) {
1.169 + fPrevScanline = fCurrScanline;
1.170 + fCurrScanline = fCurrScanline->nextScanline();
1.171 +
1.172 + }
1.173 + if (y - 1 > prevLastY) { // insert empty run
1.174 + fCurrScanline->fLastY = (SkRegion::RunType)(y - 1);
1.175 + fCurrScanline->fXCount = 0;
1.176 + fCurrScanline = fCurrScanline->nextScanline();
1.177 + }
1.178 + // setup for the new curr line
1.179 + fCurrScanline->fLastY = (SkRegion::RunType)(y);
1.180 + fCurrXPtr = fCurrScanline->firstX();
1.181 + }
1.182 + }
1.183 + // check if we should extend the current run, or add a new one
1.184 + if (fCurrXPtr > fCurrScanline->firstX() && fCurrXPtr[-1] == x) {
1.185 + fCurrXPtr[-1] = (SkRegion::RunType)(x + width);
1.186 + } else {
1.187 + fCurrXPtr[0] = (SkRegion::RunType)(x);
1.188 + fCurrXPtr[1] = (SkRegion::RunType)(x + width);
1.189 + fCurrXPtr += 2;
1.190 + }
1.191 + SkASSERT(fCurrXPtr - fStorage < fStorageCount);
1.192 +}
1.193 +
1.194 +int SkRgnBuilder::computeRunCount() const {
1.195 + if (fCurrScanline == NULL) {
1.196 + return 0;
1.197 + }
1.198 +
1.199 + const SkRegion::RunType* line = fStorage;
1.200 + const SkRegion::RunType* stop = (const SkRegion::RunType*)fCurrScanline;
1.201 +
1.202 + return 2 + (int)(stop - line);
1.203 +}
1.204 +
1.205 +void SkRgnBuilder::copyToRect(SkIRect* r) const {
1.206 + SkASSERT(fCurrScanline != NULL);
1.207 + // A rect's scanline is [bottom intervals left right sentinel] == 5
1.208 + SkASSERT((const SkRegion::RunType*)fCurrScanline - fStorage == 5);
1.209 +
1.210 + const Scanline* line = (const Scanline*)fStorage;
1.211 + SkASSERT(line->fXCount == 2);
1.212 +
1.213 + r->set(line->firstX()[0], fTop, line->firstX()[1], line->fLastY + 1);
1.214 +}
1.215 +
1.216 +void SkRgnBuilder::copyToRgn(SkRegion::RunType runs[]) const {
1.217 + SkASSERT(fCurrScanline != NULL);
1.218 + SkASSERT((const SkRegion::RunType*)fCurrScanline - fStorage > 4);
1.219 +
1.220 + const Scanline* line = (const Scanline*)fStorage;
1.221 + const Scanline* stop = fCurrScanline;
1.222 +
1.223 + *runs++ = fTop;
1.224 + do {
1.225 + *runs++ = (SkRegion::RunType)(line->fLastY + 1);
1.226 + int count = line->fXCount;
1.227 + *runs++ = count >> 1; // intervalCount
1.228 + if (count) {
1.229 + memcpy(runs, line->firstX(), count * sizeof(SkRegion::RunType));
1.230 + runs += count;
1.231 + }
1.232 + *runs++ = SkRegion::kRunTypeSentinel;
1.233 + line = line->nextScanline();
1.234 + } while (line < stop);
1.235 + SkASSERT(line == stop);
1.236 + *runs = SkRegion::kRunTypeSentinel;
1.237 +}
1.238 +
1.239 +static unsigned verb_to_initial_last_index(unsigned verb) {
1.240 + static const uint8_t gPathVerbToInitialLastIndex[] = {
1.241 + 0, // kMove_Verb
1.242 + 1, // kLine_Verb
1.243 + 2, // kQuad_Verb
1.244 + 2, // kConic_Verb
1.245 + 3, // kCubic_Verb
1.246 + 0, // kClose_Verb
1.247 + 0 // kDone_Verb
1.248 + };
1.249 + SkASSERT((unsigned)verb < SK_ARRAY_COUNT(gPathVerbToInitialLastIndex));
1.250 + return gPathVerbToInitialLastIndex[verb];
1.251 +}
1.252 +
1.253 +static unsigned verb_to_max_edges(unsigned verb) {
1.254 + static const uint8_t gPathVerbToMaxEdges[] = {
1.255 + 0, // kMove_Verb
1.256 + 1, // kLine_Verb
1.257 + 2, // kQuad_VerbB
1.258 + 2, // kConic_VerbB
1.259 + 3, // kCubic_Verb
1.260 + 0, // kClose_Verb
1.261 + 0 // kDone_Verb
1.262 + };
1.263 + SkASSERT((unsigned)verb < SK_ARRAY_COUNT(gPathVerbToMaxEdges));
1.264 + return gPathVerbToMaxEdges[verb];
1.265 +}
1.266 +
1.267 +
1.268 +static int count_path_runtype_values(const SkPath& path, int* itop, int* ibot) {
1.269 + SkPath::Iter iter(path, true);
1.270 + SkPoint pts[4];
1.271 + SkPath::Verb verb;
1.272 +
1.273 + int maxEdges = 0;
1.274 + SkScalar top = SkIntToScalar(SK_MaxS16);
1.275 + SkScalar bot = SkIntToScalar(SK_MinS16);
1.276 +
1.277 + while ((verb = iter.next(pts, false)) != SkPath::kDone_Verb) {
1.278 + maxEdges += verb_to_max_edges(verb);
1.279 +
1.280 + int lastIndex = verb_to_initial_last_index(verb);
1.281 + if (lastIndex > 0) {
1.282 + for (int i = 1; i <= lastIndex; i++) {
1.283 + if (top > pts[i].fY) {
1.284 + top = pts[i].fY;
1.285 + } else if (bot < pts[i].fY) {
1.286 + bot = pts[i].fY;
1.287 + }
1.288 + }
1.289 + } else if (SkPath::kMove_Verb == verb) {
1.290 + if (top > pts[0].fY) {
1.291 + top = pts[0].fY;
1.292 + } else if (bot < pts[0].fY) {
1.293 + bot = pts[0].fY;
1.294 + }
1.295 + }
1.296 + }
1.297 + SkASSERT(top <= bot);
1.298 +
1.299 + *itop = SkScalarRoundToInt(top);
1.300 + *ibot = SkScalarRoundToInt(bot);
1.301 + return maxEdges;
1.302 +}
1.303 +
1.304 +bool SkRegion::setPath(const SkPath& path, const SkRegion& clip) {
1.305 + SkDEBUGCODE(this->validate();)
1.306 +
1.307 + if (clip.isEmpty()) {
1.308 + return this->setEmpty();
1.309 + }
1.310 +
1.311 + if (path.isEmpty()) {
1.312 + if (path.isInverseFillType()) {
1.313 + return this->set(clip);
1.314 + } else {
1.315 + return this->setEmpty();
1.316 + }
1.317 + }
1.318 +
1.319 + // compute worst-case rgn-size for the path
1.320 + int pathTop, pathBot;
1.321 + int pathTransitions = count_path_runtype_values(path, &pathTop, &pathBot);
1.322 + int clipTop, clipBot;
1.323 + int clipTransitions;
1.324 +
1.325 + clipTransitions = clip.count_runtype_values(&clipTop, &clipBot);
1.326 +
1.327 + int top = SkMax32(pathTop, clipTop);
1.328 + int bot = SkMin32(pathBot, clipBot);
1.329 +
1.330 + if (top >= bot)
1.331 + return this->setEmpty();
1.332 +
1.333 + SkRgnBuilder builder;
1.334 +
1.335 + if (!builder.init(bot - top,
1.336 + SkMax32(pathTransitions, clipTransitions),
1.337 + path.isInverseFillType())) {
1.338 + // can't allocate working space, so return false
1.339 + return this->setEmpty();
1.340 + }
1.341 +
1.342 + SkScan::FillPath(path, clip, &builder);
1.343 + builder.done();
1.344 +
1.345 + int count = builder.computeRunCount();
1.346 + if (count == 0) {
1.347 + return this->setEmpty();
1.348 + } else if (count == kRectRegionRuns) {
1.349 + builder.copyToRect(&fBounds);
1.350 + this->setRect(fBounds);
1.351 + } else {
1.352 + SkRegion tmp;
1.353 +
1.354 + tmp.fRunHead = RunHead::Alloc(count);
1.355 + builder.copyToRgn(tmp.fRunHead->writable_runs());
1.356 + tmp.fRunHead->computeRunBounds(&tmp.fBounds);
1.357 + this->swap(tmp);
1.358 + }
1.359 + SkDEBUGCODE(this->validate();)
1.360 + return true;
1.361 +}
1.362 +
1.363 +/////////////////////////////////////////////////////////////////////////////////////////////////
1.364 +/////////////////////////////////////////////////////////////////////////////////////////////////
1.365 +
1.366 +struct Edge {
1.367 + enum {
1.368 + kY0Link = 0x01,
1.369 + kY1Link = 0x02,
1.370 +
1.371 + kCompleteLink = (kY0Link | kY1Link)
1.372 + };
1.373 +
1.374 + SkRegion::RunType fX;
1.375 + SkRegion::RunType fY0, fY1;
1.376 + uint8_t fFlags;
1.377 + Edge* fNext;
1.378 +
1.379 + void set(int x, int y0, int y1) {
1.380 + SkASSERT(y0 != y1);
1.381 +
1.382 + fX = (SkRegion::RunType)(x);
1.383 + fY0 = (SkRegion::RunType)(y0);
1.384 + fY1 = (SkRegion::RunType)(y1);
1.385 + fFlags = 0;
1.386 + SkDEBUGCODE(fNext = NULL;)
1.387 + }
1.388 +
1.389 + int top() const {
1.390 + return SkFastMin32(fY0, fY1);
1.391 + }
1.392 +};
1.393 +
1.394 +static void find_link(Edge* base, Edge* stop) {
1.395 + SkASSERT(base < stop);
1.396 +
1.397 + if (base->fFlags == Edge::kCompleteLink) {
1.398 + SkASSERT(base->fNext);
1.399 + return;
1.400 + }
1.401 +
1.402 + SkASSERT(base + 1 < stop);
1.403 +
1.404 + int y0 = base->fY0;
1.405 + int y1 = base->fY1;
1.406 +
1.407 + Edge* e = base;
1.408 + if ((base->fFlags & Edge::kY0Link) == 0) {
1.409 + for (;;) {
1.410 + e += 1;
1.411 + if ((e->fFlags & Edge::kY1Link) == 0 && y0 == e->fY1) {
1.412 + SkASSERT(NULL == e->fNext);
1.413 + e->fNext = base;
1.414 + e->fFlags = SkToU8(e->fFlags | Edge::kY1Link);
1.415 + break;
1.416 + }
1.417 + }
1.418 + }
1.419 +
1.420 + e = base;
1.421 + if ((base->fFlags & Edge::kY1Link) == 0) {
1.422 + for (;;) {
1.423 + e += 1;
1.424 + if ((e->fFlags & Edge::kY0Link) == 0 && y1 == e->fY0) {
1.425 + SkASSERT(NULL == base->fNext);
1.426 + base->fNext = e;
1.427 + e->fFlags = SkToU8(e->fFlags | Edge::kY0Link);
1.428 + break;
1.429 + }
1.430 + }
1.431 + }
1.432 +
1.433 + base->fFlags = Edge::kCompleteLink;
1.434 +}
1.435 +
1.436 +static int extract_path(Edge* edge, Edge* stop, SkPath* path) {
1.437 + while (0 == edge->fFlags) {
1.438 + edge++; // skip over "used" edges
1.439 + }
1.440 +
1.441 + SkASSERT(edge < stop);
1.442 +
1.443 + Edge* base = edge;
1.444 + Edge* prev = edge;
1.445 + edge = edge->fNext;
1.446 + SkASSERT(edge != base);
1.447 +
1.448 + int count = 1;
1.449 + path->moveTo(SkIntToScalar(prev->fX), SkIntToScalar(prev->fY0));
1.450 + prev->fFlags = 0;
1.451 + do {
1.452 + if (prev->fX != edge->fX || prev->fY1 != edge->fY0) { // skip collinear
1.453 + path->lineTo(SkIntToScalar(prev->fX), SkIntToScalar(prev->fY1)); // V
1.454 + path->lineTo(SkIntToScalar(edge->fX), SkIntToScalar(edge->fY0)); // H
1.455 + }
1.456 + prev = edge;
1.457 + edge = edge->fNext;
1.458 + count += 1;
1.459 + prev->fFlags = 0;
1.460 + } while (edge != base);
1.461 + path->lineTo(SkIntToScalar(prev->fX), SkIntToScalar(prev->fY1)); // V
1.462 + path->close();
1.463 + return count;
1.464 +}
1.465 +
1.466 +#include "SkTSearch.h"
1.467 +
1.468 +static int EdgeProc(const Edge* a, const Edge* b) {
1.469 + return (a->fX == b->fX) ? a->top() - b->top() : a->fX - b->fX;
1.470 +}
1.471 +
1.472 +bool SkRegion::getBoundaryPath(SkPath* path) const {
1.473 + // path could safely be NULL if we're empty, but the caller shouldn't
1.474 + // *know* that
1.475 + SkASSERT(path);
1.476 +
1.477 + if (this->isEmpty()) {
1.478 + return false;
1.479 + }
1.480 +
1.481 + const SkIRect& bounds = this->getBounds();
1.482 +
1.483 + if (this->isRect()) {
1.484 + SkRect r;
1.485 + r.set(bounds); // this converts the ints to scalars
1.486 + path->addRect(r);
1.487 + return true;
1.488 + }
1.489 +
1.490 + SkRegion::Iterator iter(*this);
1.491 + SkTDArray<Edge> edges;
1.492 +
1.493 + for (const SkIRect& r = iter.rect(); !iter.done(); iter.next()) {
1.494 + Edge* edge = edges.append(2);
1.495 + edge[0].set(r.fLeft, r.fBottom, r.fTop);
1.496 + edge[1].set(r.fRight, r.fTop, r.fBottom);
1.497 + }
1.498 + qsort(edges.begin(), edges.count(), sizeof(Edge), SkCastForQSort(EdgeProc));
1.499 +
1.500 + int count = edges.count();
1.501 + Edge* start = edges.begin();
1.502 + Edge* stop = start + count;
1.503 + Edge* e;
1.504 +
1.505 + for (e = start; e != stop; e++) {
1.506 + find_link(e, stop);
1.507 + }
1.508 +
1.509 +#ifdef SK_DEBUG
1.510 + for (e = start; e != stop; e++) {
1.511 + SkASSERT(e->fNext != NULL);
1.512 + SkASSERT(e->fFlags == Edge::kCompleteLink);
1.513 + }
1.514 +#endif
1.515 +
1.516 + path->incReserve(count << 1);
1.517 + do {
1.518 + SkASSERT(count > 1);
1.519 + count -= extract_path(start, stop, path);
1.520 + } while (count > 0);
1.521 +
1.522 + return true;
1.523 +}
