1 /* 2 * Copyright 2011 Google Inc. 3 * 4 * Use of this source code is governed by a BSD-style license that can be 5 * found in the LICENSE file. 6 */ 7 #include "SkAntiEdge.h" 8 #include "SkPoint.h" 9 10 /** Returns the signed fraction of a SkFixed 11 */ 12 static inline SkFixed SkFixedFraction(SkFixed x) 13 { 14 SkFixed mask = x >> 31 << 16; 15 return (x & 0xFFFF) | mask; 16 } 17 18 void SkAntiEdge::pointOnLine(SkFixed x, SkFixed y) { 19 float x0 = SkFixedToFloat(x); 20 float y0 = SkFixedToFloat(y); 21 float x1 = SkFixedToFloat(fFirstX); 22 float y1 = SkFixedToFloat(fFirstY); 23 float x2 = SkFixedToFloat(fLastX); 24 float y2 = SkFixedToFloat(fLastY); 25 float numer = (x2 - x1) * (y1 - y0) - (x1 - x0) * (y2 - y1); 26 float denom = (x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1); 27 double dist = fabs(numer) / sqrt(denom); 28 SkAssertResult(dist < 0.01); 29 } 30 31 void SkAntiEdge::pointInLine(SkFixed x, SkFixed y) { 32 if (y == SK_MaxS32) { 33 return; 34 } 35 pointOnLine(x, y); 36 SkAssertResult(y >= fFirstY && y <= fLastY); 37 } 38 39 void SkAntiEdge::validate() { 40 pointOnLine(fWalkX, fY); 41 pointOnLine(fX, fWalkY); 42 } 43 44 bool SkAntiEdge::setLine(const SkPoint& p0, const SkPoint& p1) { 45 fFirstY = SkScalarToFixed(p0.fY); 46 fLastY = SkScalarToFixed(p1.fY); 47 if (fFirstY == fLastY) { 48 return false; 49 } 50 fFirstX = SkScalarToFixed(p0.fX); 51 fLastX = SkScalarToFixed(p1.fX); 52 if (fFirstY > fLastY) { 53 SkTSwap(fFirstX, fLastX); 54 SkTSwap(fFirstY, fLastY); 55 fWinding = -1; 56 } else { 57 fWinding = 1; 58 } 59 SkFixed dx = fLastX - fFirstX; 60 fDXFlipped = dx < 0; 61 SkFixed dy = fLastY - fFirstY; 62 fDX = SkFixedDiv(dx, dy); 63 fDY = dx == 0 ? SK_MaxS32 : SkFixedDiv(dy, SkFixedAbs(dx)); 64 fLink = NULL; 65 fLinkSet = false; 66 return true; 67 } 68 69 void SkAntiEdge::calcLine() { 70 SkFixed yStartFrac = SkFixedFraction(fFirstY); 71 if (fDXFlipped) { 72 SkFixed vert = SK_Fixed1 - yStartFrac; // distance from y start to x-axis 73 fX0 = fFirstX + SkFixedMul(fDX, vert); 74 SkFixed backupX = fFirstX + SkFixedMul(vert, fDX); // x cell to back up to 75 SkFixed cellX = SkIntToFixed(SkFixedFloor(backupX)); 76 SkFixed endX = SkIntToFixed(SkFixedFloor(fLastX)); 77 if (cellX < endX) { 78 cellX = endX; 79 } 80 SkFixed distX = fFirstX - cellX; // to y-axis 81 fY0 = fFirstY + SkFixedMul(fDY, distX); 82 SkFixed rowBottom = SkIntToFixed(SkFixedCeil(fFirstY + 1)); 83 if (fLastY > rowBottom) { 84 fPartialY = 0; 85 fX = fX0; 86 fY = rowBottom; 87 } else { 88 fPartialY = SkFixedFraction(fLastY); 89 fX = fLastX; 90 fY = fLastY; 91 } 92 } else { 93 fPartialY = yStartFrac; 94 fX0 = fFirstX - SkFixedMul(fDX, yStartFrac); 95 fY0 = fFirstY; 96 if (fDY != SK_MaxS32) { 97 SkFixed xStartFrac = SkFixedFraction(fFirstX); 98 fY0 -= SkFixedMul(fDY, xStartFrac); 99 } 100 fX = fFirstX; 101 fY = fFirstY; 102 } 103 fWalkX = fX; 104 fWalkY = fY; 105 fFinished = false; 106 } 107 108 static SkFixed SkFixedAddPin(SkFixed a, SkFixed b) { 109 SkFixed result = a + b; 110 if (((a ^ ~b) & (a ^ result)) >= 0) { // one positive, one negative 111 return result; // or all three same sign 112 } 113 return a < 0 ? -SK_FixedMax : SK_FixedMax; 114 } 115 116 // edge is increasing in x and y 117 uint16_t SkAntiEdge::advanceX(SkFixed left) { 118 validate(); 119 SkFixed x = SkFixedAddPin(fX0, fDX); 120 SkFixed wy = SkIntToFixed(SkFixedFloor(fWalkY + SK_Fixed1)); 121 pointOnLine(x, wy); 122 SkFixed partial = SK_Fixed1 - fPartialY; 123 SkFixed bottomPartial = wy - fLastY; 124 if (bottomPartial > 0) { 125 partial -= bottomPartial; 126 } 127 if (x > fLastX) { 128 x = fLastX; 129 wy = fLastY; 130 } 131 uint16_t coverage; 132 if (left >= x) { 133 fFinished = true; 134 coverage = partial - 1; // walker is to the right of edge 135 } else { 136 SkFixed y = SkFixedAddPin(fY0, fDY); 137 SkFixed wx = SkIntToFixed(SkFixedFloor(fWalkX + SK_Fixed1)); 138 if (fDY != SK_MaxS32) { 139 pointOnLine(wx, y); 140 } 141 if (y > fLastY) { 142 y = fLastY; 143 wx = fLastX; 144 } 145 bool topCorner = fWalkX <= fX; 146 bool bottomCorner = x <= wx; 147 bool halfPlane = !(topCorner ^ bottomCorner); 148 if (halfPlane) { 149 if (x - SkIntToFixed(SkFixedFloor(fX)) <= SK_Fixed1) { 150 coverage = ~((fX + x) >> 1); // avg of fx, fx+dx 151 fFinished = true; 152 if (x >= left + SK_Fixed1) { 153 fWalkX = wx; 154 fY = fY0 = y; 155 } 156 } else { 157 SkAssertResult(y - SkIntToFixed(SkFixedFloor(fY)) <= SK_Fixed1); 158 coverage = ((fY + y) >> 1); 159 fFinished = y == fLastY; 160 fWalkX = wx; 161 fY = fY0 = y; 162 } 163 coverage = coverage * partial >> 16; 164 } else if (topCorner) { 165 SkFixed xDiff = wx - fX; 166 SkAssertResult(xDiff >= 0); 167 SkAssertResult(xDiff <= SK_Fixed1); 168 SkFixed yDiff = y - fWalkY; 169 // This may be a very small negative number if error accumulates 170 // FIXME: for now, try setting it to zero in that case. 171 if (yDiff < 0) { 172 fX = fX0 = SkIntToFixed(SkFixedCeil(fX)); 173 yDiff = 0; 174 } 175 SkAssertResult(yDiff >= 0); 176 SkAssertResult(yDiff <= SK_Fixed1); 177 int xCoverage = xDiff >> 1; // throw away 1 bit so multiply 178 int yCoverage = yDiff >> 1; // stays in range 179 int triangle = xCoverage * yCoverage; // 30 bits 180 SkFixed bottomPartial = y - fLastY; 181 fFinished = bottomPartial >= 0; 182 if (fFinished) { 183 yCoverage = bottomPartial >> 1; 184 xCoverage = (wx - fLastX) >> 1; 185 triangle -= xCoverage * yCoverage; 186 } 187 coverage = triangle >> 15; 188 fWalkX = wx; 189 fY = fY0 = y; 190 } else { 191 SkAssertResult(bottomCorner); 192 SkFixed xDiff = x - fWalkX; 193 SkAssertResult(xDiff >= 0); 194 SkAssertResult(xDiff <= SK_Fixed1); 195 SkFixed yDiff = wy - fY; 196 SkAssertResult(yDiff >= 0); 197 SkAssertResult(yDiff <= SK_Fixed1); 198 int xCoverage = xDiff >> 1; // throw away 1 bit so multiply 199 int yCoverage = yDiff >> 1; // stays in range 200 int triangle = xCoverage * yCoverage >> 15; 201 coverage = partial - 1 - triangle; 202 fFinished = true; 203 } 204 } 205 validate(); 206 return coverage; 207 } 208 209 // edge is increasing in x, but decreasing in y 210 uint16_t SkAntiEdge::advanceFlippedX(SkFixed left) { 211 validate(); 212 SkFixed x = SkFixedAddPin(fX0, -fDX); 213 SkFixed wy = SkIntToFixed(SkFixedFloor(fWalkY - 1)); 214 pointOnLine(x, wy); 215 SkFixed partial = fPartialY ? fPartialY : SK_Fixed1; 216 SkFixed topPartial = fFirstY - wy; 217 if (topPartial > 0) { 218 partial -= topPartial; 219 } 220 if (x > fFirstX) { 221 x = fFirstX; 222 wy = fFirstY; 223 } 224 uint16_t coverage; 225 if (left >= x) { 226 fFinished = true; 227 coverage = partial - 1; // walker is to the right of edge 228 } else { 229 SkFixed y = SkFixedAddPin(fY0, -fDY); 230 SkFixed wx = SkIntToFixed(SkFixedFloor(fWalkX + SK_Fixed1)); 231 pointOnLine(wx, y); 232 if (y < fFirstY) { 233 y = fFirstY; 234 wx = fFirstX; 235 } 236 bool bottomCorner = fWalkX <= fX; 237 bool topCorner = x <= wx; 238 bool halfPlane = !(topCorner ^ bottomCorner); 239 if (halfPlane) { 240 if (x - SkIntToFixed(SkFixedFloor(fX)) <= SK_Fixed1) { 241 coverage = ~((fX + x) >> 1); // avg of fx, fx+dx 242 fFinished = true; 243 } else { 244 SkAssertResult(y - SkIntToFixed(SkFixedFloor(fY)) <= SK_Fixed1); 245 coverage = ~((fY + y) >> 1); 246 fFinished = y == fY; 247 fWalkX = wx; 248 fY = fY0 = y; 249 } 250 coverage = coverage * partial >> 16; 251 } else if (bottomCorner) { 252 SkFixed xDiff = wx - fX; 253 SkAssertResult(xDiff >= 0); 254 SkAssertResult(xDiff <= SK_Fixed1); 255 SkFixed yDiff = fWalkY - y; 256 SkAssertResult(yDiff >= 0); 257 SkAssertResult(yDiff <= SK_Fixed1); 258 int xCoverage = xDiff >> 1; // throw away 1 bit so multiply 259 int yCoverage = yDiff >> 1; // stays in range 260 int triangle = xCoverage * yCoverage; // 30 bits 261 SkFixed bottomPartial = fFirstY - y; 262 fFinished = bottomPartial >= 0; 263 if (fFinished) { 264 yCoverage = bottomPartial >> 1; 265 xCoverage = (wx - fFirstX) >> 1; 266 triangle -= xCoverage * yCoverage; 267 } 268 coverage = triangle >> 15; 269 fWalkX = wx; 270 fY = fY0 = y; 271 } else { 272 SkAssertResult(topCorner); 273 SkFixed xDiff = x - fWalkX; 274 SkAssertResult(xDiff >= 0); 275 SkAssertResult(xDiff <= SK_Fixed1); 276 SkFixed yDiff = fY - wy; 277 SkAssertResult(yDiff >= 0); 278 SkAssertResult(yDiff <= SK_Fixed1); 279 int xCoverage = xDiff >> 1; // throw away 1 bit so multiply 280 int yCoverage = yDiff >> 1; // stays in range 281 int triangle = xCoverage * yCoverage >> 15; 282 coverage = partial - 1 - triangle; 283 fFinished = true; 284 } 285 } 286 validate(); 287 return coverage; 288 } 289 290 void SkAntiEdge::advanceY(SkFixed top) { 291 validate(); 292 fX0 = SkFixedAddPin(fX0, fDX); 293 fPartialY = 0; 294 if (fDXFlipped) { 295 if (fX0 < fLastX) { 296 fWalkX = fX = fLastX; 297 } else { 298 fWalkX = fX = fX0; 299 } 300 SkFixed bottom = top + SK_Fixed1; 301 if (bottom > fLastY) { 302 bottom = fLastY; 303 } 304 SkFixed vert = bottom - fFirstY; // distance from y start to x-axis 305 SkFixed backupX = fFirstX + SkFixedMul(vert, fDX); // x cell to back up to 306 SkFixed distX = fFirstX - SkIntToFixed(SkFixedFloor(backupX)); // to y-axis 307 fY0 = fFirstY + SkFixedMul(fDY, distX); 308 309 fY = top + SK_Fixed1; 310 if (fY > fLastY) { 311 fY = fLastY; 312 } 313 if (fLastY < top + SK_Fixed1) { 314 fPartialY = SkFixedFraction(fLastY); 315 } 316 } else { 317 if (fX0 > fLastX) { 318 fX0 = fLastX; 319 } 320 fX = fX0; 321 } 322 fWalkY = SkIntToFixed(SkFixedFloor(fWalkY + SK_Fixed1)); 323 if (fWalkY > fLastY) { 324 fWalkY = fLastY; 325 } 326 validate(); 327 fFinished = false; 328 } 329 330 int SkAntiEdgeBuilder::build(const SkPoint pts[], int count) { 331 SkAntiEdge* edge = fEdges.append(); 332 for (int index = 0; index < count; ++index) { 333 if (edge->setLine(pts[index], pts[(index + 1) % count])) { 334 edge = fEdges.append(); 335 } 336 } 337 int result = fEdges.count(); 338 fEdges.setCount(--result); 339 if (result > 0) { 340 sk_bzero(&fHeadEdge, sizeof(fHeadEdge)); 341 sk_bzero(&fTailEdge, sizeof(fTailEdge)); 342 for (int index = 0; index < result; ++index) { 343 *fList.append() = &fEdges[index]; 344 } 345 } 346 return result; 347 } 348 349 void SkAntiEdgeBuilder::calc() { 350 for (SkAntiEdge* active = fEdges.begin(); active != fEdges.end(); ++active) { 351 active->calcLine(); 352 } 353 // compute winding sum for edges 354 SkAntiEdge* first = fHeadEdge.fNext; 355 SkAntiEdge* active; 356 SkAntiEdge* listTop = first; 357 for (active = first; active != &fTailEdge; active = active->fNext) { 358 active->fWindingSum = active->fWinding; 359 while (listTop->fLastY < active->fFirstY) { 360 listTop = listTop->fNext; 361 } 362 for (SkAntiEdge* check = listTop; check->fFirstY <= active->fFirstY; check = check->fNext) { 363 if (check == active) { 364 continue; 365 } 366 if (check->fLastY <= active->fFirstY) { 367 continue; 368 } 369 if (check->fFirstX > active->fFirstX) { 370 continue; 371 } 372 if (check->fFirstX == active->fFirstX && check->fDX > active->fDX) { 373 continue; 374 } 375 active->fWindingSum += check->fWinding; 376 } 377 } 378 } 379 380 extern "C" { 381 static int edge_compare(const void* a, const void* b) { 382 const SkAntiEdge* edgea = *(const SkAntiEdge**)a; 383 const SkAntiEdge* edgeb = *(const SkAntiEdge**)b; 384 385 int valuea = edgea->fFirstY; 386 int valueb = edgeb->fFirstY; 387 388 if (valuea == valueb) { 389 valuea = edgea->fFirstX; 390 valueb = edgeb->fFirstX; 391 } 392 393 if (valuea == valueb) { 394 valuea = edgea->fDX; 395 valueb = edgeb->fDX; 396 } 397 398 return valuea - valueb; 399 } 400 } 401 402 void SkAntiEdgeBuilder::sort(SkTDArray<SkAntiEdge*>& listOfEdges) { 403 SkAntiEdge** list = listOfEdges.begin(); 404 int count = listOfEdges.count(); 405 qsort(list, count, sizeof(SkAntiEdge*), edge_compare); 406 407 // link the edges in sorted order 408 for (int i = 1; i < count; i++) { 409 list[i - 1]->fNext = list[i]; 410 list[i]->fPrev = list[i - 1]; 411 } 412 } 413 414 #define kEDGE_HEAD_XY SK_MinS32 415 #define kEDGE_TAIL_XY SK_MaxS32 416 417 void SkAntiEdgeBuilder::sort() { 418 sort(fList); 419 SkAntiEdge* last = fList.end()[-1]; 420 fHeadEdge.fNext = fList[0]; 421 fHeadEdge.fFirstX = fHeadEdge.fFirstY = fHeadEdge.fWalkY = fHeadEdge.fLastY = kEDGE_HEAD_XY; 422 fList[0]->fPrev = &fHeadEdge; 423 424 fTailEdge.fPrev = last; 425 fTailEdge.fFirstX = fTailEdge.fFirstY = fTailEdge.fWalkY = fTailEdge.fLastY = kEDGE_TAIL_XY; 426 last->fNext = &fTailEdge; 427 } 428 429 static inline void remove_edge(SkAntiEdge* edge) { 430 edge->fPrev->fNext = edge->fNext; 431 edge->fNext->fPrev = edge->fPrev; 432 } 433 434 static inline void swap_edges(SkAntiEdge* prev, SkAntiEdge* next) { 435 SkASSERT(prev->fNext == next && next->fPrev == prev); 436 437 // remove prev from the list 438 prev->fPrev->fNext = next; 439 next->fPrev = prev->fPrev; 440 441 // insert prev after next 442 prev->fNext = next->fNext; 443 next->fNext->fPrev = prev; 444 next->fNext = prev; 445 prev->fPrev = next; 446 } 447 448 static void backward_insert_edge_based_on_x(SkAntiEdge* edge SkDECLAREPARAM(int, y)) { 449 SkFixed x = edge->fFirstX; 450 451 for (;;) { 452 SkAntiEdge* prev = edge->fPrev; 453 454 // add 1 to curr_y since we may have added new edges (built from curves) 455 // that start on the next scanline 456 SkASSERT(prev && SkFixedFloor(prev->fWalkY - prev->fDXFlipped) <= y + 1); 457 458 if (prev->fFirstX <= x) { 459 break; 460 } 461 swap_edges(prev, edge); 462 } 463 } 464 465 static void insert_new_edges(SkAntiEdge* newEdge, SkFixed curr_y) { 466 int y = SkFixedFloor(curr_y); 467 if (SkFixedFloor(newEdge->fWalkY - newEdge->fDXFlipped) < y) { 468 return; 469 } 470 while (SkFixedFloor(newEdge->fWalkY - newEdge->fDXFlipped) == y) { 471 SkAntiEdge* next = newEdge->fNext; 472 backward_insert_edge_based_on_x(newEdge SkPARAM(y)); 473 newEdge = next; 474 } 475 } 476 477 static int find_active_edges(int y, SkAntiEdge** activeLeft, 478 SkAntiEdge** activeLast) { 479 SkAntiEdge* first = *activeLeft; 480 SkFixed bottom = first->fLastY; 481 SkAntiEdge* active = first->fNext; 482 first->fLinkSet = false; 483 SkFixed yLimit = SkIntToFixed(y + 1); // limiting pixel edge 484 for ( ; active->fWalkY != kEDGE_TAIL_XY; active = active->fNext) { 485 active->fLinkSet = false; 486 if (yLimit <= active->fWalkY - active->fDXFlipped) { 487 break; 488 } 489 if ((*activeLeft)->fWalkX > active->fWalkX) { 490 *activeLeft = active; 491 } 492 if (bottom > active->fLastY) { 493 bottom = active->fLastY; 494 } 495 } 496 *activeLast = active; 497 return SkFixedCeil(bottom); 498 } 499 500 // All edges are oriented to increase in y. Link edges with common tops and 501 // bottoms so the links can share their winding sum. 502 void SkAntiEdgeBuilder::link() { 503 SkAntiEdge* tail = fEdges.end(); 504 // look for links forwards and backwards 505 SkAntiEdge* prev = fEdges.begin(); 506 SkAntiEdge* active; 507 for (active = prev + 1; active != tail; ++active) { 508 if (prev->fWinding == active->fWinding) { 509 if (prev->fLastX == active->fFirstX && prev->fLastY == active->fFirstY) { 510 prev->fLink = active; 511 active->fLinkSet = true; 512 } else if (active->fLastX == prev->fFirstX && active->fLastY == prev->fFirstY) { 513 active->fLink = prev; 514 prev->fLinkSet = true; 515 } 516 } 517 prev = active; 518 } 519 // look for stragglers 520 prev = fEdges.begin() - 1; 521 do { 522 do { 523 if (++prev == tail) { 524 return; 525 } 526 } while (prev->fLinkSet || NULL != prev->fLink); 527 for (active = prev + 1; active != tail; ++active) { 528 if (active->fLinkSet || NULL != active->fLink) { 529 continue; 530 } 531 if (prev->fWinding != active->fWinding) { 532 continue; 533 } 534 if (prev->fLastX == active->fFirstX && prev->fLastY == active->fFirstY) { 535 prev->fLink = active; 536 active->fLinkSet = true; 537 break; 538 } 539 if (active->fLastX == prev->fFirstX && active->fLastY == prev->fFirstY) { 540 active->fLink = prev; 541 prev->fLinkSet = true; 542 break; 543 } 544 } 545 } while (true); 546 } 547 548 void SkAntiEdgeBuilder::split(SkAntiEdge* edge, SkFixed y) { 549 SkPoint upperPoint = {edge->fFirstX, edge->fFirstY}; 550 SkPoint midPoint = {edge->fFirstX + SkMulDiv(y - edge->fFirstY, 551 edge->fLastX - edge->fFirstX, edge->fLastY - edge->fFirstY), y}; 552 SkPoint lowerPoint = {edge->fLastX, edge->fLastY}; 553 int8_t winding = edge->fWinding; 554 edge->setLine(upperPoint, midPoint); 555 edge->fWinding = winding; 556 SkAntiEdge* lower = fEdges.append(); 557 lower->setLine(midPoint, lowerPoint); 558 lower->fWinding = winding; 559 insert_new_edges(lower, y); 560 } 561 562 // An edge computes pixel coverage by considering the integral winding value 563 // to its left. If an edge is enclosed by fractional winding, split it. 564 // FIXME: This is also a good time to find crossing edges and split them, too. 565 void SkAntiEdgeBuilder::split() { 566 // create a new set of edges that describe the whole link 567 SkTDArray<SkAntiEdge> links; 568 SkAntiEdge* first = fHeadEdge.fNext; 569 SkAntiEdge* active; 570 for (active = first; active != &fTailEdge; active = active->fNext) { 571 if (active->fLinkSet || NULL == active->fLink) { 572 continue; 573 } 574 SkAntiEdge* link = links.append(); 575 link->fFirstX = active->fFirstX; 576 link->fFirstY = active->fFirstY; 577 SkAntiEdge* linkEnd; 578 SkAntiEdge* next = active; 579 do { 580 linkEnd = next; 581 next = next->fLink; 582 } while (NULL != next); 583 link->fLastX = linkEnd->fLastX; 584 link->fLastY = linkEnd->fLastY; 585 } 586 // create a list of all edges, links and singletons 587 SkTDArray<SkAntiEdge*> list; 588 for (active = links.begin(); active != links.end(); ++active) { 589 *list.append() = active; 590 } 591 for (active = first; active != &fTailEdge; active = active->fNext) { 592 if (!active->fLinkSet && NULL == active->fLink) { 593 SkAntiEdge* link = links.append(); 594 link->fFirstX = active->fFirstX; 595 link->fFirstY = active->fFirstY; 596 link->fLastX = active->fLastX; 597 link->fLastY = active->fLastY; 598 *list.append() = link; 599 } 600 } 601 SkAntiEdge tail; 602 tail.fFirstY = tail.fLastY = kEDGE_TAIL_XY; 603 *list.append() = &tail; 604 sort(list); 605 // walk the list, splitting edges partially occluded on the left 606 SkAntiEdge* listTop = list[0]; 607 for (active = first; active != &fTailEdge; active = active->fNext) { 608 while (listTop->fLastY < active->fFirstY) { 609 listTop = listTop->fNext; 610 } 611 for (SkAntiEdge* check = listTop; check->fFirstY < active->fLastY; check = check->fNext) { 612 if (check->fFirstX > active->fFirstX) { 613 continue; 614 } 615 if (check->fFirstX == active->fFirstX && check->fDX > active->fDX) { 616 continue; 617 } 618 if (check->fFirstY > active->fFirstY) { 619 split(active, check->fFirstY); 620 } 621 if (check->fLastY < active->fLastY) { 622 split(active, check->fLastY); 623 } 624 } 625 } 626 } 627 628 static inline uint8_t coverage_to_8(int coverage) { 629 uint16_t x = coverage < 0 ? 0 : coverage > 0xFFFF ? 0xFFFF : coverage; 630 // for values 0x7FFF and smaller, add (0x7F - high byte) and trunc 631 // for values 0x8000 and larger, subtract (high byte - 0x80) and trunc 632 return (x + 0x7f + (x >> 15) - (x >> 8)) >> 8; 633 } 634 635 void SkAntiEdgeBuilder::walk(uint8_t* result, int rowBytes, int height) { 636 SkAntiEdge* first = fHeadEdge.fNext; 637 SkFixed top = first->fWalkY - first->fDXFlipped; 638 int y = SkFixedFloor(top); 639 do { 640 SkAntiEdge* activeLeft = first; 641 SkAntiEdge* activeLast, * active; 642 int yLast = find_active_edges(y, &activeLeft, &activeLast); 643 while (y < yLast) { 644 SkAssertResult(y >= 0); 645 SkAssertResult(y < height); 646 SkFixed left = activeLeft->fWalkX; 647 int x = SkFixedFloor(left); 648 uint8_t* resultPtr = &result[y * rowBytes + x]; 649 bool finished; 650 do { 651 left = SkIntToFixed(x); 652 SkAssertResult(x >= 0); 653 // SkAssertResult(x < pixelCol); 654 if (x >= rowBytes) { // FIXME: cumulative error in fX += fDX 655 break; // fails to set fFinished early enough 656 } // see test 6 (dy<dx) 657 finished = true; 658 int coverage = 0; 659 for (active = first; active != activeLast; active = active->fNext) { 660 if (left + SK_Fixed1 <= active->fX) { 661 finished = false; 662 continue; // walker is to the left of edge 663 } 664 int cover = active->fDXFlipped ? 665 active->advanceFlippedX(left) : active->advanceX(left); 666 if (0 == active->fWindingSum) { 667 cover = -cover; 668 } 669 coverage += cover; 670 finished &= active->fFinished; 671 } 672 uint8_t old = *resultPtr; 673 uint8_t pix = coverage_to_8(coverage); 674 uint8_t blend = old > pix ? old : pix; 675 *resultPtr++ = blend; 676 ++x; 677 } while (!finished); 678 ++y; 679 top = SkIntToFixed(y); 680 SkFixed topLimit = top + SK_Fixed1; 681 SkFixed xSort = -SK_FixedMax; 682 for (active = first; active != activeLast; active = active->fNext) { 683 if (xSort > active->fX || topLimit > active->fLastY) { 684 yLast = y; // recompute bottom after all Ys are advanced 685 } 686 xSort = active->fX; 687 if (active->fWalkY < active->fLastY) { 688 active->advanceY(top); 689 } 690 } 691 for (active = first; active != activeLast; ) { 692 SkAntiEdge* next = active->fNext; 693 if (top >= active->fLastY) { 694 remove_edge(active); 695 } 696 active = next; 697 } 698 first = fHeadEdge.fNext; 699 } 700 SkAntiEdge* prev = activeLast->fPrev; 701 if (prev != &fHeadEdge) { 702 insert_new_edges(prev, top); 703 first = fHeadEdge.fNext; 704 } 705 } while (first->fWalkY < kEDGE_TAIL_XY); 706 } 707 708 void SkAntiEdgeBuilder::process(const SkPoint* points, int ptCount, 709 uint8_t* result, int pixelCol, int pixelRow) { 710 if (ptCount < 3) { 711 return; 712 } 713 int count = build(points, ptCount); 714 if (count == 0) { 715 return; 716 } 717 SkAssertResult(count > 1); 718 link(); 719 sort(); 720 split(); 721 calc(); 722 walk(result, pixelCol, pixelRow); 723 } 724 725 //////////////////////////////////////////////////////////////////////////////// 726 727 int test3by3_test; 728 729 // input is a rectangle 730 static void test_3_by_3() { 731 const int pixelRow = 3; 732 const int pixelCol = 3; 733 const int ptCount = 4; 734 const int pixelCount = pixelRow * pixelCol; 735 const SkPoint tests[][ptCount] = { 736 {{2.0f, 1.0f}, {1.0f, 1.0f}, {1.0f, 2.0f}, {2.0f, 2.0f}}, // 0: full rect 737 {{2.5f, 1.0f}, {1.5f, 1.0f}, {1.5f, 2.0f}, {2.5f, 2.0f}}, // 1: y edge 738 {{2.0f, 1.5f}, {1.0f, 1.5f}, {1.0f, 2.5f}, {2.0f, 2.5f}}, // 2: x edge 739 {{2.5f, 1.5f}, {1.5f, 1.5f}, {1.5f, 2.5f}, {2.5f, 2.5f}}, // 3: x/y edge 740 {{2.8f, 0.2f}, {0.2f, 0.2f}, {0.2f, 2.8f}, {2.8f, 2.8f}}, // 4: large 741 {{1.8f, 1.2f}, {1.2f, 1.2f}, {1.2f, 1.8f}, {1.8f, 1.8f}}, // 5: small 742 {{0.0f, 0.0f}, {0.0f, 1.0f}, {3.0f, 2.0f}, {3.0f, 1.0f}}, // 6: dy<dx 743 {{3.0f, 0.0f}, {0.0f, 1.0f}, {0.0f, 2.0f}, {3.0f, 1.0f}}, // 7: dy<-dx 744 {{1.0f, 0.0f}, {0.0f, 0.0f}, {1.0f, 3.0f}, {2.0f, 3.0f}}, // 8: dy>dx 745 {{2.0f, 0.0f}, {1.0f, 0.0f}, {0.0f, 3.0f}, {1.0f, 3.0f}}, // 9: dy>-dx 746 {{0.5f, 0.5f}, {0.5f, 1.5f}, {2.5f, 2.5f}, {2.5f, 1.5f}}, // 10: dy<dx 2 747 {{2.5f, 0.5f}, {0.5f, 1.5f}, {0.5f, 2.5f}, {2.5f, 1.5f}}, // 11: dy<-dx 2 748 {{0.0f, 0.0f}, {2.0f, 0.0f}, {2.0f, 2.0f}, {0.0f, 2.0f}}, // 12: 2x2 749 {{0.0f, 0.0f}, {3.0f, 0.0f}, {3.0f, 3.0f}, {0.0f, 3.0f}}, // 13: 3x3 750 {{1.75f, 0.25f}, {2.75f, 1.25f}, {1.25f, 2.75f}, {0.25f, 1.75f}}, // 14 751 {{2.25f, 0.25f}, {2.75f, 0.75f}, {0.75f, 2.75f}, {0.25f, 2.25f}}, // 15 752 {{0.25f, 0.75f}, {0.75f, 0.25f}, {2.75f, 2.25f}, {2.25f, 2.75f}}, // 16 753 {{1.25f, 0.50f}, {1.75f, 0.25f}, {2.75f, 2.25f}, {2.25f, 2.50f}}, // 17 754 {{1.00f, 0.75f}, {2.00f, 0.50f}, {2.00f, 1.50f}, {1.00f, 1.75f}}, // 18 755 {{1.00f, 0.50f}, {2.00f, 0.75f}, {2.00f, 1.75f}, {1.00f, 1.50f}}, // 19 756 {{1.00f, 0.75f}, {1.00f, 1.75f}, {2.00f, 1.50f}, {2.00f, 0.50f}}, // 20 757 {{1.00f, 0.50f}, {1.00f, 1.50f}, {2.00f, 1.75f}, {2.00f, 0.75f}}, // 21 758 }; 759 const uint8_t results[][pixelCount] = { 760 {0x00, 0x00, 0x00, // 0: 1 pixel rect 761 0x00, 0xFF, 0x00, 762 0x00, 0x00, 0x00}, 763 {0x00, 0x00, 0x00, // 1: y edge 764 0x00, 0x7F, 0x80, 765 0x00, 0x00, 0x00}, 766 {0x00, 0x00, 0x00, // 2: x edge 767 0x00, 0x7F, 0x00, 768 0x00, 0x7F, 0x00}, 769 {0x00, 0x00, 0x00, // 3: x/y edge 770 0x00, 0x40, 0x40, 771 0x00, 0x40, 0x40}, 772 {0xA3, 0xCC, 0xA3, // 4: large 773 0xCC, 0xFF, 0xCC, 774 0xA3, 0xCC, 0xA3}, 775 {0x00, 0x00, 0x00, // 5: small 776 0x00, 0x5C, 0x00, 777 0x00, 0x00, 0x00}, 778 {0xD5, 0x80, 0x2B, // 6: dy<dx 779 0x2A, 0x7F, 0xD4, 780 0x00, 0x00, 0x00}, 781 {0x2B, 0x80, 0xD5, // 7: dy<-dx 782 0xD4, 0x7F, 0x2A, 783 0x00, 0x00, 0x00}, 784 {0xD5, 0x2A, 0x00, // 8: dy>dx 785 0x80, 0x7F, 0x00, 786 0x2B, 0xD4, 0x00}, 787 {0x2A, 0xD5, 0x00, // 9: dy>-dx 788 0x7F, 0x80, 0x00, 789 0xD4, 0x2B, 0x00}, 790 {0x30, 0x10, 0x00, // 10: dy<dx 2 791 0x50, 0xDF, 0x50, 792 0x00, 0x10, 0x30}, 793 {0x00, 0x10, 0x30, // 11: dy<-dx 2 794 0x50, 0xDF, 0x50, 795 0x30, 0x10, 0x00}, 796 {0xFF, 0xFF, 0x00, // 12: 2x2 797 0xFF, 0xFF, 0x00, 798 0x00, 0x00, 0x00}, 799 {0xFF, 0xFF, 0xFF, // 13: 3x3 800 0xFF, 0xFF, 0xFF, 801 0xFF, 0xFF, 0xFF}, 802 {0x00, 0x70, 0x20, // 14 803 0x70, 0xFF, 0x70, 804 0x20, 0x70, 0x00}, 805 {0x00, 0x20, 0x60, // 15 806 0x20, 0xBF, 0x20, 807 0x60, 0x20, 0x00}, 808 {0x60, 0x20, 0x00, // 16 809 0x20, 0xBF, 0x20, 810 0x00, 0x20, 0x60}, 811 {0x00, 0x60, 0x04, // 17 812 0x00, 0x40, 0x60, 813 0x00, 0x00, 0x3C}, 814 {0x00, 0x60, 0x00, // 18 815 0x00, 0x9F, 0x00, 816 0x00, 0x00, 0x00}, 817 {0x00, 0x60, 0x00, // 19 818 0x00, 0x9F, 0x00, 819 0x00, 0x00, 0x00}, 820 {0x00, 0x60, 0x00, // 20 821 0x00, 0x9F, 0x00, 822 0x00, 0x00, 0x00}, 823 {0x00, 0x60, 0x00, // 21 824 0x00, 0x9F, 0x00, 825 0x00, 0x00, 0x00}, 826 }; 827 const int testCount = sizeof(tests) / sizeof(tests[0]); 828 SkAssertResult(testCount == sizeof(results) / sizeof(results[0])); 829 int testFirst = test3by3_test < 0 ? 0 : test3by3_test; 830 int testLast = test3by3_test < 0 ? testCount : test3by3_test + 1; 831 for (int testIndex = testFirst; testIndex < testLast; ++testIndex) { 832 uint8_t result[pixelRow][pixelCol]; 833 sk_bzero(result, sizeof(result)); 834 const SkPoint* rect = tests[testIndex]; 835 SkAntiEdgeBuilder builder; 836 builder.process(rect, ptCount, result[0], pixelCol, pixelRow); 837 SkAssertResult(memcmp(results[testIndex], result[0], pixelCount) == 0); 838 } 839 } 840 841 // input has arbitrary number of points 842 static void test_arbitrary_3_by_3() { 843 const int pixelRow = 3; 844 const int pixelCol = 3; 845 const int pixelCount = pixelRow * pixelCol; 846 const SkPoint t1[] = { {1,1}, {2,1}, {2,1.5f}, {1,1.5f}, {1,2}, {2,2}, 847 {2,1.5f}, {1,1.5f}, {1,1} }; 848 const SkPoint* tests[] = { t1 }; 849 size_t testPts[] = { sizeof(t1) / sizeof(t1[0]) }; 850 const uint8_t results[][pixelCount] = { 851 {0x00, 0x00, 0x00, // 0: 1 pixel rect 852 0x00, 0xFF, 0x00, 853 0x00, 0x00, 0x00}, 854 }; 855 const int testCount = sizeof(tests) / sizeof(tests[0]); 856 SkAssertResult(testCount == sizeof(results) / sizeof(results[0])); 857 int testFirst = test3by3_test < 0 ? 0 : test3by3_test; 858 int testLast = test3by3_test < 0 ? testCount : test3by3_test + 1; 859 for (int testIndex = testFirst; testIndex < testLast; ++testIndex) { 860 uint8_t result[pixelRow][pixelCol]; 861 sk_bzero(result, sizeof(result)); 862 const SkPoint* pts = tests[testIndex]; 863 size_t ptCount = testPts[testIndex]; 864 SkAntiEdgeBuilder builder; 865 builder.process(pts, ptCount, result[0], pixelCol, pixelRow); 866 SkAssertResult(memcmp(results[testIndex], result[0], pixelCount) == 0); 867 } 868 } 869 870 #include "SkRect.h" 871 #include "SkPath.h" 872 873 int testsweep_test; 874 875 static void create_sweep(uint8_t* result, int pixelRow, int pixelCol, SkScalar rectWidth) { 876 const int ptCount = 4; 877 SkRect refRect = {pixelCol / 2 - rectWidth / 2, 5, 878 pixelCol / 2 + rectWidth / 2, pixelRow / 2 - 5}; 879 SkPath refPath; 880 refPath.addRect(refRect); 881 SkScalar angleFirst = testsweep_test < 0 ? 0 : testsweep_test; 882 SkScalar angleLast = testsweep_test < 0 ? 360 : testsweep_test + 1; 883 for (SkScalar angle = angleFirst; angle < angleLast; angle += 12) { 884 SkPath rotPath; 885 SkMatrix matrix; 886 matrix.setRotate(angle, SkIntToScalar(pixelCol) / 2, 887 SkIntToScalar(pixelRow) / 2); 888 refPath.transform(matrix, &rotPath); 889 SkPoint rect[ptCount], temp[2]; 890 SkPath::Iter iter(rotPath, false); 891 int index = 0; 892 for (;;) { 893 SkPath::Verb verb = iter.next(temp); 894 if (verb == SkPath::kMove_Verb) { 895 continue; 896 } 897 if (verb == SkPath::kClose_Verb) { 898 break; 899 } 900 SkAssertResult(SkPath::kLine_Verb == verb); 901 rect[index++] = temp[0]; 902 } 903 SkAntiEdgeBuilder builder; 904 builder.process(rect, ptCount, result, pixelCol, pixelRow); 905 } 906 } 907 908 static void create_horz(uint8_t* result, int pixelRow, int pixelCol) { 909 const int ptCount = 4; 910 for (SkScalar x = 0; x < 100; x += 5) { 911 SkPoint rect[ptCount]; 912 rect[0].fX = 0; rect[0].fY = x; 913 rect[1].fX = 100; rect[1].fY = x; 914 rect[2].fX = 100; rect[2].fY = x + x / 50; 915 rect[3].fX = 0; rect[3].fY = x + x / 50; 916 SkAntiEdgeBuilder builder; 917 builder.process(rect, ptCount, result, pixelCol, pixelRow); 918 } 919 } 920 921 static void create_vert(uint8_t* result, int pixelRow, int pixelCol) { 922 const int ptCount = 4; 923 for (SkScalar x = 0; x < 100; x += 5) { 924 SkPoint rect[ptCount]; 925 rect[0].fY = 0; rect[0].fX = x; 926 rect[1].fY = 100; rect[1].fX = x; 927 rect[2].fY = 100; rect[2].fX = x + x / 50; 928 rect[3].fY = 0; rect[3].fX = x + x / 50; 929 SkAntiEdgeBuilder builder; 930 builder.process(rect, ptCount, result, pixelCol, pixelRow); 931 } 932 } 933 934 static void create_angle(uint8_t* result, int pixelRow, int pixelCol, SkScalar angle) { 935 const int ptCount = 4; 936 SkRect refRect = {25, 25, 125, 125}; 937 SkPath refPath; 938 for (SkScalar x = 30; x < 125; x += 5) { 939 refRect.fTop = x; 940 refRect.fBottom = x + (x - 25) / 50; 941 refPath.addRect(refRect); 942 } 943 SkPath rotPath; 944 SkMatrix matrix; 945 matrix.setRotate(angle, 75, 75); 946 refPath.transform(matrix, &rotPath); 947 SkPath::Iter iter(rotPath, false); 948 for (SkScalar x = 30; x < 125; x += 5) { 949 SkPoint rect[ptCount], temp[2]; 950 int index = 0; 951 for (;;) { 952 SkPath::Verb verb = iter.next(temp); 953 if (verb == SkPath::kMove_Verb) { 954 continue; 955 } 956 if (verb == SkPath::kClose_Verb) { 957 break; 958 } 959 SkAssertResult(SkPath::kLine_Verb == verb); 960 rect[index++] = temp[0]; 961 } 962 // if ((x == 30 || x == 75) && angle == 12) continue; 963 SkAntiEdgeBuilder builder; 964 builder.process(rect, ptCount, result, pixelCol, pixelRow); 965 } 966 } 967 968 static void test_sweep() { 969 const int pixelRow = 100; 970 const int pixelCol = 100; 971 uint8_t result[pixelRow][pixelCol]; 972 sk_bzero(result, sizeof(result)); 973 create_sweep(result[0], pixelRow, pixelCol, 1); 974 } 975 976 static void test_horz() { 977 const int pixelRow = 100; 978 const int pixelCol = 100; 979 uint8_t result[pixelRow][pixelCol]; 980 sk_bzero(result, sizeof(result)); 981 create_horz(result[0], pixelRow, pixelCol); 982 } 983 984 static void test_vert() { 985 const int pixelRow = 100; 986 const int pixelCol = 100; 987 uint8_t result[pixelRow][pixelCol]; 988 sk_bzero(result, sizeof(result)); 989 create_vert(result[0], pixelRow, pixelCol); 990 } 991 992 static void test_angle(SkScalar angle) { 993 const int pixelRow = 150; 994 const int pixelCol = 150; 995 uint8_t result[pixelRow][pixelCol]; 996 sk_bzero(result, sizeof(result)); 997 create_angle(result[0], pixelRow, pixelCol, angle); 998 } 999 1000 #include "SkBitmap.h" 1001 1002 void CreateSweep(SkBitmap* sweep, SkScalar rectWidth) { 1003 const int pixelRow = 100; 1004 const int pixelCol = 100; 1005 sweep->setConfig(SkBitmap::kA8_Config, pixelCol, pixelRow); 1006 sweep->allocPixels(); 1007 sweep->eraseColor(SK_ColorTRANSPARENT); 1008 sweep->lockPixels(); 1009 void* pixels = sweep->getPixels(); 1010 create_sweep((uint8_t*) pixels, pixelRow, pixelCol, rectWidth); 1011 sweep->unlockPixels(); 1012 } 1013 1014 void CreateHorz(SkBitmap* sweep) { 1015 const int pixelRow = 100; 1016 const int pixelCol = 100; 1017 sweep->setConfig(SkBitmap::kA8_Config, pixelCol, pixelRow); 1018 sweep->allocPixels(); 1019 sweep->eraseColor(SK_ColorTRANSPARENT); 1020 sweep->lockPixels(); 1021 void* pixels = sweep->getPixels(); 1022 create_horz((uint8_t*) pixels, pixelRow, pixelCol); 1023 sweep->unlockPixels(); 1024 } 1025 1026 void CreateVert(SkBitmap* sweep) { 1027 const int pixelRow = 100; 1028 const int pixelCol = 100; 1029 sweep->setConfig(SkBitmap::kA8_Config, pixelCol, pixelRow); 1030 sweep->allocPixels(); 1031 sweep->eraseColor(SK_ColorTRANSPARENT); 1032 sweep->lockPixels(); 1033 void* pixels = sweep->getPixels(); 1034 create_vert((uint8_t*) pixels, pixelRow, pixelCol); 1035 sweep->unlockPixels(); 1036 } 1037 1038 void CreateAngle(SkBitmap* sweep, SkScalar angle) { 1039 const int pixelRow = 150; 1040 const int pixelCol = 150; 1041 sweep->setConfig(SkBitmap::kA8_Config, pixelCol, pixelRow); 1042 sweep->allocPixels(); 1043 sweep->eraseColor(SK_ColorTRANSPARENT); 1044 sweep->lockPixels(); 1045 void* pixels = sweep->getPixels(); 1046 create_angle((uint8_t*) pixels, pixelRow, pixelCol, angle); 1047 sweep->unlockPixels(); 1048 } 1049 1050 #include "SkCanvas.h" 1051 1052 static void testPng() { 1053 SkBitmap device; 1054 device.setConfig(SkBitmap::kARGB_8888_Config, 4, 4); 1055 device.allocPixels(); 1056 device.eraseColor(0xFFFFFFFF); 1057 1058 SkCanvas canvas(device); 1059 canvas.drawARGB(167, 0, 0, 0); 1060 1061 device.lockPixels(); 1062 unsigned char* pixels = (unsigned char*) device.getPixels(); 1063 SkDebugf("%02x%02x%02x%02x", pixels[3], pixels[2], pixels[1], pixels[0]); 1064 } 1065 1066 void SkAntiEdge_Test() { 1067 testPng(); 1068 test_arbitrary_3_by_3(); 1069 test_angle(12); 1070 #if 0 1071 test3by3_test = 18; 1072 #else 1073 test3by3_test = -1; 1074 #endif 1075 #if 0 1076 testsweep_test = 7 * 12; 1077 #else 1078 testsweep_test = -1; 1079 #endif 1080 if (testsweep_test == -1) { 1081 test_3_by_3(); 1082 } 1083 test_sweep(); 1084 test_horz(); 1085 test_vert(); 1086 } 1087
