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