reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame^] | 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 | |
| 47 | static inline void remove_edge(SkEdge* edge) |
| 48 | { |
| 49 | edge->fPrev->fNext = edge->fNext; |
| 50 | edge->fNext->fPrev = edge->fPrev; |
| 51 | } |
| 52 | |
| 53 | static 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 | |
| 68 | static 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 | |
| 87 | static 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 |
| 100 | static 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 | |
| 122 | typedef void (*PrePostProc)(SkBlitter* blitter, int y, bool isStartOfScanline); |
| 123 | #define PREPOST_START true |
| 124 | #define PREPOST_END false |
| 125 | |
| 126 | static 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 | // |
| 230 | class InverseBlitter : public SkBlitter { |
| 231 | public: |
| 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 | |
| 275 | private: |
| 276 | SkBlitter* fBlitter; |
| 277 | int fFirstX, fLastX, fPrevX; |
| 278 | }; |
| 279 | |
| 280 | static 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 | */ |
| 294 | static 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 | |
| 303 | static 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 | |
| 357 | extern "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 | |
| 375 | static 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 | /* 'quick' computation of the max sized needed to allocated for |
| 391 | our edgelist. |
| 392 | */ |
| 393 | static int worst_case_edge_count(const SkPath& path, size_t* storage) |
| 394 | { |
| 395 | size_t size = 0; |
| 396 | int edgeCount = 0; |
| 397 | |
| 398 | SkPath::Iter iter(path, true); |
| 399 | SkPath::Verb verb; |
| 400 | |
| 401 | while ((verb = iter.next(NULL)) != SkPath::kDone_Verb) |
| 402 | { |
| 403 | switch (verb) { |
| 404 | case SkPath::kLine_Verb: |
| 405 | edgeCount += 1; |
| 406 | size += sizeof(SkQuadraticEdge); // treat line like Quad (in case its > 512) |
| 407 | break; |
| 408 | case SkPath::kQuad_Verb: |
| 409 | edgeCount += 2; // might need 2 edges when we chop on Y extrema |
| 410 | size += 2 * sizeof(SkQuadraticEdge); |
| 411 | break; |
| 412 | case SkPath::kCubic_Verb: |
| 413 | edgeCount += 3; // might need 3 edges when we chop on Y extrema |
| 414 | size += 3 * sizeof(SkCubicEdge); |
| 415 | break; |
| 416 | default: |
| 417 | break; |
| 418 | } |
| 419 | } |
| 420 | |
| 421 | SkASSERT(storage); |
| 422 | *storage = size; |
| 423 | return edgeCount; |
| 424 | } |
| 425 | |
| 426 | /* Much faster than worst_case_edge_count, but over estimates even more |
| 427 | */ |
| 428 | static int cheap_worst_case_edge_count(const SkPath& path, size_t* storage) |
| 429 | { |
| 430 | int ptCount = path.getPoints(NULL, 0); |
| 431 | int edgeCount = ptCount; |
| 432 | *storage = edgeCount * sizeof(SkCubicEdge); |
| 433 | return edgeCount; |
| 434 | } |
| 435 | |
| 436 | // clipRect may be null, even though we always have a clip. This indicates that |
| 437 | // the path is contained in the clip, and so we can ignore it during the blit |
| 438 | // |
| 439 | // clipRect (if no null) has already been shifted up |
| 440 | // |
| 441 | void sk_fill_path(const SkPath& path, const SkIRect* clipRect, SkBlitter* blitter, |
| 442 | int stop_y, int shiftEdgesUp, const SkRegion& clipRgn) |
| 443 | { |
| 444 | SkASSERT(&path && blitter); |
| 445 | |
| 446 | size_t size; |
| 447 | int maxCount = cheap_worst_case_edge_count(path, &size); |
| 448 | |
| 449 | #ifdef SK_DEBUG |
| 450 | { |
| 451 | size_t size2; |
| 452 | int maxCount2 = worst_case_edge_count(path, &size2); |
| 453 | |
| 454 | SkASSERT(maxCount >= maxCount2 && size >= size2); |
| 455 | } |
| 456 | #endif |
| 457 | |
| 458 | SkAutoMalloc memory(maxCount * sizeof(SkEdge*) + size); |
| 459 | SkEdge** list = (SkEdge**)memory.get(); |
| 460 | SkEdge* edge = (SkEdge*)(list + maxCount); |
| 461 | int count = build_edges(edge, path, clipRect, list, shiftEdgesUp); |
| 462 | SkEdge headEdge, tailEdge, *last; |
| 463 | |
| 464 | SkASSERT(count <= maxCount); |
| 465 | if (count == 0) { |
| 466 | return; |
| 467 | } |
| 468 | SkASSERT(count > 1); |
| 469 | |
| 470 | // this returns the first and last edge after they're sorted into a dlink list |
| 471 | edge = sort_edges(list, count, &last); |
| 472 | |
| 473 | headEdge.fPrev = NULL; |
| 474 | headEdge.fNext = edge; |
| 475 | headEdge.fFirstY = kEDGE_HEAD_Y; |
| 476 | headEdge.fX = SK_MinS32; |
| 477 | edge->fPrev = &headEdge; |
| 478 | |
| 479 | tailEdge.fPrev = last; |
| 480 | tailEdge.fNext = NULL; |
| 481 | tailEdge.fFirstY = kEDGE_TAIL_Y; |
| 482 | last->fNext = &tailEdge; |
| 483 | |
| 484 | // now edge is the head of the sorted linklist |
| 485 | |
| 486 | stop_y <<= shiftEdgesUp; |
| 487 | if (clipRect && stop_y > clipRect->fBottom) { |
| 488 | stop_y = clipRect->fBottom; |
| 489 | } |
| 490 | |
| 491 | InverseBlitter ib; |
| 492 | PrePostProc proc = NULL; |
| 493 | |
| 494 | if (path.isInverseFillType()) { |
| 495 | ib.setBlitter(blitter, clipRgn.getBounds(), shiftEdgesUp); |
| 496 | blitter = &ib; |
| 497 | proc = PrePostInverseBlitterProc; |
| 498 | } |
| 499 | |
| 500 | walk_edges(&headEdge, path.getFillType(), blitter, stop_y, proc); |
| 501 | } |
| 502 | |
| 503 | void sk_blit_above_and_below(SkBlitter* blitter, const SkIRect& ir, |
| 504 | const SkRegion& clip) { |
| 505 | const SkIRect& cr = clip.getBounds(); |
| 506 | SkIRect tmp; |
| 507 | |
| 508 | tmp.fLeft = cr.fLeft; |
| 509 | tmp.fRight = cr.fRight; |
| 510 | |
| 511 | tmp.fTop = cr.fTop; |
| 512 | tmp.fBottom = ir.fTop; |
| 513 | if (!tmp.isEmpty()) { |
| 514 | blitter->blitRectRegion(tmp, clip); |
| 515 | } |
| 516 | |
| 517 | tmp.fTop = ir.fBottom; |
| 518 | tmp.fBottom = cr.fBottom; |
| 519 | if (!tmp.isEmpty()) { |
| 520 | blitter->blitRectRegion(tmp, clip); |
| 521 | } |
| 522 | } |
| 523 | |
| 524 | ///////////////////////////////////////////////////////////////////////////////////// |
| 525 | |
| 526 | SkScanClipper::SkScanClipper(SkBlitter* blitter, const SkRegion* clip, const SkIRect& ir) |
| 527 | { |
| 528 | fBlitter = NULL; // null means blit nothing |
| 529 | fClipRect = NULL; |
| 530 | |
| 531 | if (clip) |
| 532 | { |
| 533 | fClipRect = &clip->getBounds(); |
| 534 | if (!SkIRect::Intersects(*fClipRect, ir)) // completely clipped out |
| 535 | return; |
| 536 | |
| 537 | if (clip->isRect()) |
| 538 | { |
| 539 | if (fClipRect->contains(ir)) |
| 540 | fClipRect = NULL; |
| 541 | else |
| 542 | { |
| 543 | // only need a wrapper blitter if we're horizontally clipped |
| 544 | if (fClipRect->fLeft > ir.fLeft || fClipRect->fRight < ir.fRight) |
| 545 | { |
| 546 | fRectBlitter.init(blitter, *fClipRect); |
| 547 | blitter = &fRectBlitter; |
| 548 | } |
| 549 | } |
| 550 | } |
| 551 | else |
| 552 | { |
| 553 | fRgnBlitter.init(blitter, clip); |
| 554 | blitter = &fRgnBlitter; |
| 555 | } |
| 556 | } |
| 557 | fBlitter = blitter; |
| 558 | } |
| 559 | |
| 560 | /////////////////////////////////////////////////////////////////////////////// |
| 561 | |
| 562 | void SkScan::FillPath(const SkPath& path, const SkRegion& clip, |
| 563 | SkBlitter* blitter) { |
| 564 | if (clip.isEmpty()) { |
| 565 | return; |
| 566 | } |
| 567 | |
| 568 | SkRect r; |
| 569 | SkIRect ir; |
| 570 | |
| 571 | path.computeBounds(&r, SkPath::kFast_BoundsType); |
| 572 | r.round(&ir); |
| 573 | if (ir.isEmpty()) { |
| 574 | if (path.isInverseFillType()) { |
| 575 | blitter->blitRegion(clip); |
| 576 | } |
| 577 | return; |
| 578 | } |
| 579 | |
| 580 | SkScanClipper clipper(blitter, &clip, ir); |
| 581 | |
| 582 | blitter = clipper.getBlitter(); |
| 583 | if (blitter) { |
| 584 | if (path.isInverseFillType()) { |
| 585 | sk_blit_above_and_below(blitter, ir, clip); |
| 586 | } |
| 587 | sk_fill_path(path, clipper.getClipRect(), blitter, ir.fBottom, 0, clip); |
| 588 | } else { |
| 589 | // what does it mean to not have a blitter if path.isInverseFillType??? |
| 590 | } |
| 591 | } |
| 592 | |
| 593 | /////////////////////////////////////////////////////////////////////////////// |
| 594 | |
| 595 | static int build_tri_edges(SkEdge edge[], const SkPoint pts[], |
| 596 | const SkIRect* clipRect, SkEdge* list[]) { |
| 597 | SkEdge** start = list; |
| 598 | |
| 599 | if (edge->setLine(pts[0], pts[1], clipRect, 0)) { |
| 600 | *list++ = edge; |
| 601 | edge = (SkEdge*)((char*)edge + sizeof(SkEdge)); |
| 602 | } |
| 603 | if (edge->setLine(pts[1], pts[2], clipRect, 0)) { |
| 604 | *list++ = edge; |
| 605 | edge = (SkEdge*)((char*)edge + sizeof(SkEdge)); |
| 606 | } |
| 607 | if (edge->setLine(pts[2], pts[0], clipRect, 0)) { |
| 608 | *list++ = edge; |
| 609 | } |
| 610 | return (int)(list - start); |
| 611 | } |
| 612 | |
| 613 | |
| 614 | void sk_fill_triangle(const SkPoint pts[], const SkIRect* clipRect, |
| 615 | SkBlitter* blitter, const SkIRect& ir) { |
| 616 | SkASSERT(pts && blitter); |
| 617 | |
| 618 | SkEdge edgeStorage[3]; |
| 619 | SkEdge* list[3]; |
| 620 | |
| 621 | int count = build_tri_edges(edgeStorage, pts, clipRect, list); |
| 622 | if (count < 2) { |
| 623 | return; |
| 624 | } |
| 625 | |
| 626 | SkEdge headEdge, tailEdge, *last; |
| 627 | |
| 628 | // this returns the first and last edge after they're sorted into a dlink list |
| 629 | SkEdge* edge = sort_edges(list, count, &last); |
| 630 | |
| 631 | headEdge.fPrev = NULL; |
| 632 | headEdge.fNext = edge; |
| 633 | headEdge.fFirstY = kEDGE_HEAD_Y; |
| 634 | headEdge.fX = SK_MinS32; |
| 635 | edge->fPrev = &headEdge; |
| 636 | |
| 637 | tailEdge.fPrev = last; |
| 638 | tailEdge.fNext = NULL; |
| 639 | tailEdge.fFirstY = kEDGE_TAIL_Y; |
| 640 | last->fNext = &tailEdge; |
| 641 | |
| 642 | // now edge is the head of the sorted linklist |
| 643 | int stop_y = ir.fBottom; |
| 644 | if (clipRect && stop_y > clipRect->fBottom) { |
| 645 | stop_y = clipRect->fBottom; |
| 646 | } |
| 647 | walk_edges(&headEdge, SkPath::kEvenOdd_FillType, blitter, stop_y, NULL); |
| 648 | } |
| 649 | |
| 650 | void SkScan::FillTriangle(const SkPoint pts[], const SkRegion* clip, |
| 651 | SkBlitter* blitter) { |
| 652 | if (clip && clip->isEmpty()) { |
| 653 | return; |
| 654 | } |
| 655 | |
| 656 | SkRect r; |
| 657 | SkIRect ir; |
| 658 | r.set(pts, 3); |
| 659 | r.round(&ir); |
| 660 | if (ir.isEmpty()) { |
| 661 | return; |
| 662 | } |
| 663 | |
| 664 | SkScanClipper clipper(blitter, clip, ir); |
| 665 | |
| 666 | blitter = clipper.getBlitter(); |
| 667 | if (NULL != blitter) { |
| 668 | sk_fill_triangle(pts, clipper.getClipRect(), blitter, ir); |
| 669 | } |
| 670 | } |
| 671 | |