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