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