| OLD | NEW |
|---|
| (Empty) |
| 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 - fCurr
Scanline->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->fLast
Y, 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 - fCurr
Scanline->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)Edge
Proc); | |
| 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 | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 113827:
Remove the remainder of the skia source code from the Chromium repo.... (Closed)
Base URL: svn://chrome-svn/chrome/trunk/src/