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