SkScan_Path.cpp revision fc25abdabff76f913fb9d4f373418c10a1eca92b
1/* libs/graphics/sgl/SkScan_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 "SkScanPriv.h" 19#include "SkBlitter.h" 20#include "SkEdge.h" 21#include "SkGeometry.h" 22#include "SkPath.h" 23#include "SkRegion.h" 24#include "SkTemplates.h" 25 26#define kEDGE_HEAD_Y SK_MinS32 27#define kEDGE_TAIL_Y SK_MaxS32 28 29#ifdef SK_DEBUG 30 static void validate_sort(const SkEdge* edge) 31 { 32 int y = kEDGE_HEAD_Y; 33 34 while (edge->fFirstY != SK_MaxS32) 35 { 36 edge->validate(); 37 SkASSERT(y <= edge->fFirstY); 38 39 y = edge->fFirstY; 40 edge = edge->fNext; 41 } 42 } 43#else 44 #define validate_sort(edge) 45#endif 46 47static inline void remove_edge(SkEdge* edge) 48{ 49 edge->fPrev->fNext = edge->fNext; 50 edge->fNext->fPrev = edge->fPrev; 51} 52 53static inline void swap_edges(SkEdge* prev, SkEdge* next) 54{ 55 SkASSERT(prev->fNext == next && next->fPrev == prev); 56 57 // remove prev from the list 58 prev->fPrev->fNext = next; 59 next->fPrev = prev->fPrev; 60 61 // insert prev after next 62 prev->fNext = next->fNext; 63 next->fNext->fPrev = prev; 64 next->fNext = prev; 65 prev->fPrev = next; 66} 67 68static void backward_insert_edge_based_on_x(SkEdge* edge SkDECLAREPARAM(int, curr_y)) 69{ 70 SkFixed x = edge->fX; 71 72 for (;;) 73 { 74 SkEdge* prev = edge->fPrev; 75 76 // add 1 to curr_y since we may have added new edges (built from curves) 77 // that start on the next scanline 78 SkASSERT(prev && prev->fFirstY <= curr_y + 1); 79 80 if (prev->fX <= x) 81 break; 82 83 swap_edges(prev, edge); 84 } 85} 86 87static void insert_new_edges(SkEdge* newEdge, int curr_y) 88{ 89 SkASSERT(newEdge->fFirstY >= curr_y); 90 91 while (newEdge->fFirstY == curr_y) 92 { 93 SkEdge* next = newEdge->fNext; 94 backward_insert_edge_based_on_x(newEdge SkPARAM(curr_y)); 95 newEdge = next; 96 } 97} 98 99#ifdef SK_DEBUG 100static void validate_edges_for_y(const SkEdge* edge, int curr_y) 101{ 102 while (edge->fFirstY <= curr_y) 103 { 104 SkASSERT(edge->fPrev && edge->fNext); 105 SkASSERT(edge->fPrev->fNext == edge); 106 SkASSERT(edge->fNext->fPrev == edge); 107 SkASSERT(edge->fFirstY <= edge->fLastY); 108 109 SkASSERT(edge->fPrev->fX <= edge->fX); 110 edge = edge->fNext; 111 } 112} 113#else 114 #define validate_edges_for_y(edge, curr_y) 115#endif 116 117#if defined _WIN32 && _MSC_VER >= 1300 // disable warning : local variable used without having been initialized 118#pragma warning ( push ) 119#pragma warning ( disable : 4701 ) 120#endif 121 122typedef void (*PrePostProc)(SkBlitter* blitter, int y, bool isStartOfScanline); 123#define PREPOST_START true 124#define PREPOST_END false 125 126static void walk_edges(SkEdge* prevHead, SkPath::FillType fillType, 127 SkBlitter* blitter, int stop_y, PrePostProc proc) 128{ 129 validate_sort(prevHead->fNext); 130 131 int curr_y = prevHead->fNext->fFirstY; 132 // returns 1 for evenodd, -1 for winding, regardless of inverse-ness 133 int windingMask = (fillType & 1) ? 1 : -1; 134 135 for (;;) 136 { 137 int w = 0; 138 int left SK_INIT_TO_AVOID_WARNING; 139 bool in_interval = false; 140 SkEdge* currE = prevHead->fNext; 141 SkFixed prevX = prevHead->fX; 142 143 validate_edges_for_y(currE, curr_y); 144 145 if (proc) { 146 proc(blitter, curr_y, PREPOST_START); // pre-proc 147 } 148 149 while (currE->fFirstY <= curr_y) 150 { 151 SkASSERT(currE->fLastY >= curr_y); 152 153 int x = (currE->fX + SK_Fixed1/2) >> 16; 154 w += currE->fWinding; 155 if ((w & windingMask) == 0) // we finished an interval 156 { 157 SkASSERT(in_interval); 158 int width = x - left; 159 SkASSERT(width >= 0); 160 if (width) 161 blitter->blitH(left, curr_y, width); 162 in_interval = false; 163 } 164 else if (!in_interval) 165 { 166 left = x; 167 in_interval = true; 168 } 169 170 SkEdge* next = currE->fNext; 171 SkFixed newX; 172 173 if (currE->fLastY == curr_y) // are we done with this edge? 174 { 175 if (currE->fCurveCount < 0) 176 { 177 if (((SkCubicEdge*)currE)->updateCubic()) 178 { 179 SkASSERT(currE->fFirstY == curr_y + 1); 180 181 newX = currE->fX; 182 goto NEXT_X; 183 } 184 } 185 else if (currE->fCurveCount > 0) 186 { 187 if (((SkQuadraticEdge*)currE)->updateQuadratic()) 188 { 189 newX = currE->fX; 190 goto NEXT_X; 191 } 192 } 193 remove_edge(currE); 194 } 195 else 196 { 197 SkASSERT(currE->fLastY > curr_y); 198 newX = currE->fX + currE->fDX; 199 currE->fX = newX; 200 NEXT_X: 201 if (newX < prevX) // ripple currE backwards until it is x-sorted 202 backward_insert_edge_based_on_x(currE SkPARAM(curr_y)); 203 else 204 prevX = newX; 205 } 206 currE = next; 207 SkASSERT(currE); 208 } 209 210 if (proc) { 211 proc(blitter, curr_y, PREPOST_END); // post-proc 212 } 213 214 curr_y += 1; 215 if (curr_y >= stop_y) 216 break; 217 218 // now currE points to the first edge with a Yint larger than curr_y 219 insert_new_edges(currE, curr_y); 220 } 221} 222 223/////////////////////////////////////////////////////////////////////////////// 224 225// this guy overrides blitH, and will call its proxy blitter with the inverse 226// of the spans it is given (clipped to the left/right of the cliprect) 227// 228// used to implement inverse filltypes on paths 229// 230class InverseBlitter : public SkBlitter { 231public: 232 void setBlitter(SkBlitter* blitter, const SkIRect& clip, int shift) { 233 fBlitter = blitter; 234 fFirstX = clip.fLeft << shift; 235 fLastX = clip.fRight << shift; 236 } 237 void prepost(int y, bool isStart) { 238 if (isStart) { 239 fPrevX = fFirstX; 240 } else { 241 int invWidth = fLastX - fPrevX; 242 if (invWidth > 0) { 243 fBlitter->blitH(fPrevX, y, invWidth); 244 } 245 } 246 } 247 248 // overrides 249 virtual void blitH(int x, int y, int width) { 250 int invWidth = x - fPrevX; 251 if (invWidth > 0) { 252 fBlitter->blitH(fPrevX, y, invWidth); 253 } 254 fPrevX = x + width; 255 } 256 257 // we do not expect to get called with these entrypoints 258 virtual void blitAntiH(int, int, const SkAlpha[], const int16_t runs[]) { 259 SkASSERT(!"blitAntiH unexpected"); 260 } 261 virtual void blitV(int x, int y, int height, SkAlpha alpha) { 262 SkASSERT(!"blitV unexpected"); 263 } 264 virtual void blitRect(int x, int y, int width, int height) { 265 SkASSERT(!"blitRect unexpected"); 266 } 267 virtual void blitMask(const SkMask&, const SkIRect& clip) { 268 SkASSERT(!"blitMask unexpected"); 269 } 270 virtual const SkBitmap* justAnOpaqueColor(uint32_t* value) { 271 SkASSERT(!"justAnOpaqueColor unexpected"); 272 return NULL; 273 } 274 275private: 276 SkBlitter* fBlitter; 277 int fFirstX, fLastX, fPrevX; 278}; 279 280static void PrePostInverseBlitterProc(SkBlitter* blitter, int y, bool isStart) { 281 ((InverseBlitter*)blitter)->prepost(y, isStart); 282} 283 284/////////////////////////////////////////////////////////////////////////////// 285 286#if defined _WIN32 && _MSC_VER >= 1300 287#pragma warning ( pop ) 288#endif 289 290/* Our line edge relies on the maximum span being <= 512, so that it can 291 use FDot6 and keep the dx,dy in 16bits (for much faster slope divide). 292 This function returns true if the specified line is too big. 293*/ 294static inline bool line_too_big(const SkPoint pts[2]) 295{ 296 SkScalar dx = pts[1].fX - pts[0].fX; 297 SkScalar dy = pts[1].fY - pts[0].fY; 298 299 return SkScalarAbs(dx) > SkIntToScalar(511) || 300 SkScalarAbs(dy) > SkIntToScalar(511); 301} 302 303static int build_edges(SkEdge edge[], const SkPath& path, 304 const SkIRect* clipRect, SkEdge* list[], int shiftUp) { 305 SkEdge** start = list; 306 SkPath::Iter iter(path, true); 307 SkPoint pts[4]; 308 SkPath::Verb verb; 309 310 while ((verb = iter.next(pts)) != SkPath::kDone_Verb) { 311 switch (verb) { 312 case SkPath::kLine_Verb: 313 if (edge->setLine(pts[0], pts[1], clipRect, shiftUp)) { 314 *list++ = edge; 315 edge = (SkEdge*)((char*)edge + sizeof(SkEdge)); 316 } 317 break; 318 case SkPath::kQuad_Verb: { 319 SkPoint tmp[5]; 320 SkPoint* p = tmp; 321 int count = SkChopQuadAtYExtrema(pts, tmp); 322 323 do { 324 if (((SkQuadraticEdge*)edge)->setQuadratic(p, clipRect, 325 shiftUp)) 326 { 327 *list++ = edge; 328 edge = (SkEdge*)((char*)edge + sizeof(SkQuadraticEdge)); 329 } 330 p += 2; 331 } while (--count >= 0); 332 break; 333 } 334 case SkPath::kCubic_Verb: { 335 SkPoint tmp[10]; 336 SkPoint* p = tmp; 337 int count = SkChopCubicAtYExtrema(pts, tmp); 338 SkASSERT(count >= 0 && count <= 2); 339 340 do { 341 if (((SkCubicEdge*)edge)->setCubic(p, clipRect, shiftUp)) 342 { 343 *list++ = edge; 344 edge = (SkEdge*)((char*)edge + sizeof(SkCubicEdge)); 345 } 346 p += 3; 347 } while (--count >= 0); 348 break; 349 } 350 default: 351 break; 352 } 353 } 354 return (int)(list - start); 355} 356 357extern "C" { 358 static int edge_compare(const void* a, const void* b) 359 { 360 const SkEdge* edgea = *(const SkEdge**)a; 361 const SkEdge* edgeb = *(const SkEdge**)b; 362 363 int valuea = edgea->fFirstY; 364 int valueb = edgeb->fFirstY; 365 366 if (valuea == valueb) 367 { 368 valuea = edgea->fX; 369 valueb = edgeb->fX; 370 } 371 return valuea - valueb; 372 } 373} 374 375static SkEdge* sort_edges(SkEdge* list[], int count, SkEdge** last) 376{ 377 qsort(list, count, sizeof(SkEdge*), edge_compare); 378 379 // now make the edges linked in sorted order 380 for (int i = 1; i < count; i++) 381 { 382 list[i - 1]->fNext = list[i]; 383 list[i]->fPrev = list[i - 1]; 384 } 385 386 *last = list[count - 1]; 387 return list[0]; 388} 389 390#ifdef SK_DEBUG 391/* 'quick' computation of the max sized needed to allocated for 392 our edgelist. 393*/ 394static int worst_case_edge_count(const SkPath& path, size_t* storage) 395{ 396 size_t size = 0; 397 int edgeCount = 0; 398 399 SkPath::Iter iter(path, true); 400 SkPath::Verb verb; 401 402 while ((verb = iter.next(NULL)) != SkPath::kDone_Verb) 403 { 404 switch (verb) { 405 case SkPath::kLine_Verb: 406 edgeCount += 1; 407 size += sizeof(SkQuadraticEdge); // treat line like Quad (in case its > 512) 408 break; 409 case SkPath::kQuad_Verb: 410 edgeCount += 2; // might need 2 edges when we chop on Y extrema 411 size += 2 * sizeof(SkQuadraticEdge); 412 break; 413 case SkPath::kCubic_Verb: 414 edgeCount += 3; // might need 3 edges when we chop on Y extrema 415 size += 3 * sizeof(SkCubicEdge); 416 break; 417 default: 418 break; 419 } 420 } 421 422 SkASSERT(storage); 423 *storage = size; 424 return edgeCount; 425} 426#endif 427 428/* Much faster than worst_case_edge_count, but over estimates even more 429*/ 430static int cheap_worst_case_edge_count(const SkPath& path, size_t* storage) 431{ 432 int ptCount = path.getPoints(NULL, 0); 433 int edgeCount = ptCount; 434 *storage = edgeCount * sizeof(SkCubicEdge); 435 return edgeCount; 436} 437 438// clipRect may be null, even though we always have a clip. This indicates that 439// the path is contained in the clip, and so we can ignore it during the blit 440// 441// clipRect (if no null) has already been shifted up 442// 443void sk_fill_path(const SkPath& path, const SkIRect* clipRect, SkBlitter* blitter, 444 int stop_y, int shiftEdgesUp, const SkRegion& clipRgn) 445{ 446 SkASSERT(&path && blitter); 447 448 size_t size; 449 int maxCount = cheap_worst_case_edge_count(path, &size); 450 451#ifdef SK_DEBUG 452 { 453 size_t size2; 454 int maxCount2 = worst_case_edge_count(path, &size2); 455 456 SkASSERT(maxCount >= maxCount2 && size >= size2); 457 } 458#endif 459 460 SkAutoMalloc memory(maxCount * sizeof(SkEdge*) + size); 461 SkEdge** list = (SkEdge**)memory.get(); 462 SkEdge* edge = (SkEdge*)(list + maxCount); 463 int count = build_edges(edge, path, clipRect, list, shiftEdgesUp); 464 SkEdge headEdge, tailEdge, *last; 465 466 SkASSERT(count <= maxCount); 467 if (count == 0) { 468 return; 469 } 470 SkASSERT(count > 1); 471 472 // this returns the first and last edge after they're sorted into a dlink list 473 edge = sort_edges(list, count, &last); 474 475 headEdge.fPrev = NULL; 476 headEdge.fNext = edge; 477 headEdge.fFirstY = kEDGE_HEAD_Y; 478 headEdge.fX = SK_MinS32; 479 edge->fPrev = &headEdge; 480 481 tailEdge.fPrev = last; 482 tailEdge.fNext = NULL; 483 tailEdge.fFirstY = kEDGE_TAIL_Y; 484 last->fNext = &tailEdge; 485 486 // now edge is the head of the sorted linklist 487 488 stop_y <<= shiftEdgesUp; 489 if (clipRect && stop_y > clipRect->fBottom) { 490 stop_y = clipRect->fBottom; 491 } 492 493 InverseBlitter ib; 494 PrePostProc proc = NULL; 495 496 if (path.isInverseFillType()) { 497 ib.setBlitter(blitter, clipRgn.getBounds(), shiftEdgesUp); 498 blitter = &ib; 499 proc = PrePostInverseBlitterProc; 500 } 501 502 walk_edges(&headEdge, path.getFillType(), blitter, stop_y, proc); 503} 504 505void sk_blit_above_and_below(SkBlitter* blitter, const SkIRect& ir, 506 const SkRegion& clip) { 507 const SkIRect& cr = clip.getBounds(); 508 SkIRect tmp; 509 510 tmp.fLeft = cr.fLeft; 511 tmp.fRight = cr.fRight; 512 513 tmp.fTop = cr.fTop; 514 tmp.fBottom = ir.fTop; 515 if (!tmp.isEmpty()) { 516 blitter->blitRectRegion(tmp, clip); 517 } 518 519 tmp.fTop = ir.fBottom; 520 tmp.fBottom = cr.fBottom; 521 if (!tmp.isEmpty()) { 522 blitter->blitRectRegion(tmp, clip); 523 } 524} 525 526///////////////////////////////////////////////////////////////////////////////////// 527 528SkScanClipper::SkScanClipper(SkBlitter* blitter, const SkRegion* clip, const SkIRect& ir) 529{ 530 fBlitter = NULL; // null means blit nothing 531 fClipRect = NULL; 532 533 if (clip) 534 { 535 fClipRect = &clip->getBounds(); 536 if (!SkIRect::Intersects(*fClipRect, ir)) // completely clipped out 537 return; 538 539 if (clip->isRect()) 540 { 541 if (fClipRect->contains(ir)) 542 fClipRect = NULL; 543 else 544 { 545 // only need a wrapper blitter if we're horizontally clipped 546 if (fClipRect->fLeft > ir.fLeft || fClipRect->fRight < ir.fRight) 547 { 548 fRectBlitter.init(blitter, *fClipRect); 549 blitter = &fRectBlitter; 550 } 551 } 552 } 553 else 554 { 555 fRgnBlitter.init(blitter, clip); 556 blitter = &fRgnBlitter; 557 } 558 } 559 fBlitter = blitter; 560} 561 562/////////////////////////////////////////////////////////////////////////////// 563 564void SkScan::FillPath(const SkPath& path, const SkRegion& clip, 565 SkBlitter* blitter) { 566 if (clip.isEmpty()) { 567 return; 568 } 569 570 SkRect r; 571 SkIRect ir; 572 573 path.computeBounds(&r, SkPath::kFast_BoundsType); 574 r.round(&ir); 575 if (ir.isEmpty()) { 576 if (path.isInverseFillType()) { 577 blitter->blitRegion(clip); 578 } 579 return; 580 } 581 582 SkScanClipper clipper(blitter, &clip, ir); 583 584 blitter = clipper.getBlitter(); 585 if (blitter) { 586 if (path.isInverseFillType()) { 587 sk_blit_above_and_below(blitter, ir, clip); 588 } 589 sk_fill_path(path, clipper.getClipRect(), blitter, ir.fBottom, 0, clip); 590 } else { 591 // what does it mean to not have a blitter if path.isInverseFillType??? 592 } 593} 594 595/////////////////////////////////////////////////////////////////////////////// 596 597static int build_tri_edges(SkEdge edge[], const SkPoint pts[], 598 const SkIRect* clipRect, SkEdge* list[]) { 599 SkEdge** start = list; 600 601 if (edge->setLine(pts[0], pts[1], clipRect, 0)) { 602 *list++ = edge; 603 edge = (SkEdge*)((char*)edge + sizeof(SkEdge)); 604 } 605 if (edge->setLine(pts[1], pts[2], clipRect, 0)) { 606 *list++ = edge; 607 edge = (SkEdge*)((char*)edge + sizeof(SkEdge)); 608 } 609 if (edge->setLine(pts[2], pts[0], clipRect, 0)) { 610 *list++ = edge; 611 } 612 return (int)(list - start); 613} 614 615 616void sk_fill_triangle(const SkPoint pts[], const SkIRect* clipRect, 617 SkBlitter* blitter, const SkIRect& ir) { 618 SkASSERT(pts && blitter); 619 620 SkEdge edgeStorage[3]; 621 SkEdge* list[3]; 622 623 int count = build_tri_edges(edgeStorage, pts, clipRect, list); 624 if (count < 2) { 625 return; 626 } 627 628 SkEdge headEdge, tailEdge, *last; 629 630 // this returns the first and last edge after they're sorted into a dlink list 631 SkEdge* edge = sort_edges(list, count, &last); 632 633 headEdge.fPrev = NULL; 634 headEdge.fNext = edge; 635 headEdge.fFirstY = kEDGE_HEAD_Y; 636 headEdge.fX = SK_MinS32; 637 edge->fPrev = &headEdge; 638 639 tailEdge.fPrev = last; 640 tailEdge.fNext = NULL; 641 tailEdge.fFirstY = kEDGE_TAIL_Y; 642 last->fNext = &tailEdge; 643 644 // now edge is the head of the sorted linklist 645 int stop_y = ir.fBottom; 646 if (clipRect && stop_y > clipRect->fBottom) { 647 stop_y = clipRect->fBottom; 648 } 649 walk_edges(&headEdge, SkPath::kEvenOdd_FillType, blitter, stop_y, NULL); 650} 651 652void SkScan::FillTriangle(const SkPoint pts[], const SkRegion* clip, 653 SkBlitter* blitter) { 654 if (clip && clip->isEmpty()) { 655 return; 656 } 657 658 SkRect r; 659 SkIRect ir; 660 r.set(pts, 3); 661 r.round(&ir); 662 if (ir.isEmpty()) { 663 return; 664 } 665 666 SkScanClipper clipper(blitter, clip, ir); 667 668 blitter = clipper.getBlitter(); 669 if (NULL != blitter) { 670 sk_fill_triangle(pts, clipper.getClipRect(), blitter, ir); 671 } 672} 673 674