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