| /* |
| * Copyright 2011 Google Inc. |
| * |
| * Use of this source code is governed by a BSD-style license that can be |
| * found in the LICENSE file. |
| */ |
| #include "SkAntiEdge.h" |
| #include "SkPoint.h" |
| |
| /** Returns the signed fraction of a SkFixed |
| */ |
| static inline SkFixed SkFixedFraction(SkFixed x) |
| { |
| SkFixed mask = x >> 31 << 16; |
| return (x & 0xFFFF) | mask; |
| } |
| |
| void SkAntiEdge::pointOnLine(SkFixed x, SkFixed y) { |
| float x0 = SkFixedToFloat(x); |
| float y0 = SkFixedToFloat(y); |
| float x1 = SkFixedToFloat(fFirstX); |
| float y1 = SkFixedToFloat(fFirstY); |
| float x2 = SkFixedToFloat(fLastX); |
| float y2 = SkFixedToFloat(fLastY); |
| float numer = (x2 - x1) * (y1 - y0) - (x1 - x0) * (y2 - y1); |
| float denom = (x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1); |
| double dist = fabs(numer) / sqrt(denom); |
| SkAssertResult(dist < 0.01); |
| } |
| |
| void SkAntiEdge::pointInLine(SkFixed x, SkFixed y) { |
| if (y == SK_MaxS32) { |
| return; |
| } |
| pointOnLine(x, y); |
| SkAssertResult(y >= fFirstY && y <= fLastY); |
| } |
| |
| void SkAntiEdge::validate() { |
| pointOnLine(fWalkX, fY); |
| pointOnLine(fX, fWalkY); |
| } |
| |
| bool SkAntiEdge::setLine(const SkPoint& p0, const SkPoint& p1) { |
| fFirstY = SkScalarToFixed(p0.fY); |
| fLastY = SkScalarToFixed(p1.fY); |
| if (fFirstY == fLastY) { |
| return false; |
| } |
| fFirstX = SkScalarToFixed(p0.fX); |
| fLastX = SkScalarToFixed(p1.fX); |
| if (fFirstY > fLastY) { |
| SkTSwap(fFirstX, fLastX); |
| SkTSwap(fFirstY, fLastY); |
| fWinding = -1; |
| } else { |
| fWinding = 1; |
| } |
| SkFixed dx = fLastX - fFirstX; |
| fDXFlipped = dx < 0; |
| SkFixed dy = fLastY - fFirstY; |
| fDX = SkFixedDiv(dx, dy); |
| fDY = dx == 0 ? SK_MaxS32 : SkFixedDiv(dy, SkFixedAbs(dx)); |
| fLink = NULL; |
| fLinkSet = false; |
| return true; |
| } |
| |
| void SkAntiEdge::calcLine() { |
| SkFixed yStartFrac = SkFixedFraction(fFirstY); |
| if (fDXFlipped) { |
| SkFixed vert = SK_Fixed1 - yStartFrac; // distance from y start to x-axis |
| fX0 = fFirstX + SkFixedMul(fDX, vert); |
| SkFixed backupX = fFirstX + SkFixedMul(vert, fDX); // x cell to back up to |
| SkFixed cellX = SkIntToFixed(SkFixedFloor(backupX)); |
| SkFixed endX = SkIntToFixed(SkFixedFloor(fLastX)); |
| if (cellX < endX) { |
| cellX = endX; |
| } |
| SkFixed distX = fFirstX - cellX; // to y-axis |
| fY0 = fFirstY + SkFixedMul(fDY, distX); |
| SkFixed rowBottom = SkIntToFixed(SkFixedCeil(fFirstY + 1)); |
| if (fLastY > rowBottom) { |
| fPartialY = 0; |
| fX = fX0; |
| fY = rowBottom; |
| } else { |
| fPartialY = SkFixedFraction(fLastY); |
| fX = fLastX; |
| fY = fLastY; |
| } |
| } else { |
| fPartialY = yStartFrac; |
| fX0 = fFirstX - SkFixedMul(fDX, yStartFrac); |
| fY0 = fFirstY; |
| if (fDY != SK_MaxS32) { |
| SkFixed xStartFrac = SkFixedFraction(fFirstX); |
| fY0 -= SkFixedMul(fDY, xStartFrac); |
| } |
| fX = fFirstX; |
| fY = fFirstY; |
| } |
| fWalkX = fX; |
| fWalkY = fY; |
| fFinished = false; |
| } |
| |
| static SkFixed SkFixedAddPin(SkFixed a, SkFixed b) { |
| SkFixed result = a + b; |
| if (((a ^ ~b) & (a ^ result)) >= 0) { // one positive, one negative |
| return result; // or all three same sign |
| } |
| return a < 0 ? -SK_FixedMax : SK_FixedMax; |
| } |
| |
| // edge is increasing in x and y |
| uint16_t SkAntiEdge::advanceX(SkFixed left) { |
| validate(); |
| SkFixed x = SkFixedAddPin(fX0, fDX); |
| SkFixed wy = SkIntToFixed(SkFixedFloor(fWalkY + SK_Fixed1)); |
| pointOnLine(x, wy); |
| SkFixed partial = SK_Fixed1 - fPartialY; |
| SkFixed bottomPartial = wy - fLastY; |
| if (bottomPartial > 0) { |
| partial -= bottomPartial; |
| } |
| if (x > fLastX) { |
| x = fLastX; |
| wy = fLastY; |
| } |
| uint16_t coverage; |
| if (left >= x) { |
| fFinished = true; |
| coverage = partial - 1; // walker is to the right of edge |
| } else { |
| SkFixed y = SkFixedAddPin(fY0, fDY); |
| SkFixed wx = SkIntToFixed(SkFixedFloor(fWalkX + SK_Fixed1)); |
| if (fDY != SK_MaxS32) { |
| pointOnLine(wx, y); |
| } |
| if (y > fLastY) { |
| y = fLastY; |
| wx = fLastX; |
| } |
| bool topCorner = fWalkX <= fX; |
| bool bottomCorner = x <= wx; |
| bool halfPlane = !(topCorner ^ bottomCorner); |
| if (halfPlane) { |
| if (x - SkIntToFixed(SkFixedFloor(fX)) <= SK_Fixed1) { |
| coverage = ~((fX + x) >> 1); // avg of fx, fx+dx |
| fFinished = true; |
| if (x >= left + SK_Fixed1) { |
| fWalkX = wx; |
| fY = fY0 = y; |
| } |
| } else { |
| SkAssertResult(y - SkIntToFixed(SkFixedFloor(fY)) <= SK_Fixed1); |
| coverage = ((fY + y) >> 1); |
| fFinished = y == fLastY; |
| fWalkX = wx; |
| fY = fY0 = y; |
| } |
| coverage = coverage * partial >> 16; |
| } else if (topCorner) { |
| SkFixed xDiff = wx - fX; |
| SkAssertResult(xDiff >= 0); |
| SkAssertResult(xDiff <= SK_Fixed1); |
| SkFixed yDiff = y - fWalkY; |
| // This may be a very small negative number if error accumulates |
| // FIXME: for now, try setting it to zero in that case. |
| if (yDiff < 0) { |
| fX = fX0 = SkIntToFixed(SkFixedCeil(fX)); |
| yDiff = 0; |
| } |
| SkAssertResult(yDiff >= 0); |
| SkAssertResult(yDiff <= SK_Fixed1); |
| int xCoverage = xDiff >> 1; // throw away 1 bit so multiply |
| int yCoverage = yDiff >> 1; // stays in range |
| int triangle = xCoverage * yCoverage; // 30 bits |
| SkFixed bottomPartial = y - fLastY; |
| fFinished = bottomPartial >= 0; |
| if (fFinished) { |
| yCoverage = bottomPartial >> 1; |
| xCoverage = (wx - fLastX) >> 1; |
| triangle -= xCoverage * yCoverage; |
| } |
| coverage = triangle >> 15; |
| fWalkX = wx; |
| fY = fY0 = y; |
| } else { |
| SkAssertResult(bottomCorner); |
| SkFixed xDiff = x - fWalkX; |
| SkAssertResult(xDiff >= 0); |
| SkAssertResult(xDiff <= SK_Fixed1); |
| SkFixed yDiff = wy - fY; |
| SkAssertResult(yDiff >= 0); |
| SkAssertResult(yDiff <= SK_Fixed1); |
| int xCoverage = xDiff >> 1; // throw away 1 bit so multiply |
| int yCoverage = yDiff >> 1; // stays in range |
| int triangle = xCoverage * yCoverage >> 15; |
| coverage = partial - 1 - triangle; |
| fFinished = true; |
| } |
| } |
| validate(); |
| return coverage; |
| } |
| |
| // edge is increasing in x, but decreasing in y |
| uint16_t SkAntiEdge::advanceFlippedX(SkFixed left) { |
| validate(); |
| SkFixed x = SkFixedAddPin(fX0, -fDX); |
| SkFixed wy = SkIntToFixed(SkFixedFloor(fWalkY - 1)); |
| pointOnLine(x, wy); |
| SkFixed partial = fPartialY ? fPartialY : SK_Fixed1; |
| SkFixed topPartial = fFirstY - wy; |
| if (topPartial > 0) { |
| partial -= topPartial; |
| } |
| if (x > fFirstX) { |
| x = fFirstX; |
| wy = fFirstY; |
| } |
| uint16_t coverage; |
| if (left >= x) { |
| fFinished = true; |
| coverage = partial - 1; // walker is to the right of edge |
| } else { |
| SkFixed y = SkFixedAddPin(fY0, -fDY); |
| SkFixed wx = SkIntToFixed(SkFixedFloor(fWalkX + SK_Fixed1)); |
| pointOnLine(wx, y); |
| if (y < fFirstY) { |
| y = fFirstY; |
| wx = fFirstX; |
| } |
| bool bottomCorner = fWalkX <= fX; |
| bool topCorner = x <= wx; |
| bool halfPlane = !(topCorner ^ bottomCorner); |
| if (halfPlane) { |
| if (x - SkIntToFixed(SkFixedFloor(fX)) <= SK_Fixed1) { |
| coverage = ~((fX + x) >> 1); // avg of fx, fx+dx |
| fFinished = true; |
| } else { |
| SkAssertResult(y - SkIntToFixed(SkFixedFloor(fY)) <= SK_Fixed1); |
| coverage = ~((fY + y) >> 1); |
| fFinished = y == fY; |
| fWalkX = wx; |
| fY = fY0 = y; |
| } |
| coverage = coverage * partial >> 16; |
| } else if (bottomCorner) { |
| SkFixed xDiff = wx - fX; |
| SkAssertResult(xDiff >= 0); |
| SkAssertResult(xDiff <= SK_Fixed1); |
| SkFixed yDiff = fWalkY - y; |
| SkAssertResult(yDiff >= 0); |
| SkAssertResult(yDiff <= SK_Fixed1); |
| int xCoverage = xDiff >> 1; // throw away 1 bit so multiply |
| int yCoverage = yDiff >> 1; // stays in range |
| int triangle = xCoverage * yCoverage; // 30 bits |
| SkFixed bottomPartial = fFirstY - y; |
| fFinished = bottomPartial >= 0; |
| if (fFinished) { |
| yCoverage = bottomPartial >> 1; |
| xCoverage = (wx - fFirstX) >> 1; |
| triangle -= xCoverage * yCoverage; |
| } |
| coverage = triangle >> 15; |
| fWalkX = wx; |
| fY = fY0 = y; |
| } else { |
| SkAssertResult(topCorner); |
| SkFixed xDiff = x - fWalkX; |
| SkAssertResult(xDiff >= 0); |
| SkAssertResult(xDiff <= SK_Fixed1); |
| SkFixed yDiff = fY - wy; |
| SkAssertResult(yDiff >= 0); |
| SkAssertResult(yDiff <= SK_Fixed1); |
| int xCoverage = xDiff >> 1; // throw away 1 bit so multiply |
| int yCoverage = yDiff >> 1; // stays in range |
| int triangle = xCoverage * yCoverage >> 15; |
| coverage = partial - 1 - triangle; |
| fFinished = true; |
| } |
| } |
| validate(); |
| return coverage; |
| } |
| |
| void SkAntiEdge::advanceY(SkFixed top) { |
| validate(); |
| fX0 = SkFixedAddPin(fX0, fDX); |
| fPartialY = 0; |
| if (fDXFlipped) { |
| if (fX0 < fLastX) { |
| fWalkX = fX = fLastX; |
| } else { |
| fWalkX = fX = fX0; |
| } |
| SkFixed bottom = top + SK_Fixed1; |
| if (bottom > fLastY) { |
| bottom = fLastY; |
| } |
| SkFixed vert = bottom - fFirstY; // distance from y start to x-axis |
| SkFixed backupX = fFirstX + SkFixedMul(vert, fDX); // x cell to back up to |
| SkFixed distX = fFirstX - SkIntToFixed(SkFixedFloor(backupX)); // to y-axis |
| fY0 = fFirstY + SkFixedMul(fDY, distX); |
| |
| fY = top + SK_Fixed1; |
| if (fY > fLastY) { |
| fY = fLastY; |
| } |
| if (fLastY < top + SK_Fixed1) { |
| fPartialY = SkFixedFraction(fLastY); |
| } |
| } else { |
| if (fX0 > fLastX) { |
| fX0 = fLastX; |
| } |
| fX = fX0; |
| } |
| fWalkY = SkIntToFixed(SkFixedFloor(fWalkY + SK_Fixed1)); |
| if (fWalkY > fLastY) { |
| fWalkY = fLastY; |
| } |
| validate(); |
| fFinished = false; |
| } |
| |
| int SkAntiEdgeBuilder::build(const SkPoint pts[], int count) { |
| SkAntiEdge* edge = fEdges.append(); |
| for (int index = 0; index < count; ++index) { |
| if (edge->setLine(pts[index], pts[(index + 1) % count])) { |
| edge = fEdges.append(); |
| } |
| } |
| int result = fEdges.count(); |
| fEdges.setCount(--result); |
| if (result > 0) { |
| sk_bzero(&fHeadEdge, sizeof(fHeadEdge)); |
| sk_bzero(&fTailEdge, sizeof(fTailEdge)); |
| for (int index = 0; index < result; ++index) { |
| *fList.append() = &fEdges[index]; |
| } |
| } |
| return result; |
| } |
| |
| void SkAntiEdgeBuilder::calc() { |
| for (SkAntiEdge* active = fEdges.begin(); active != fEdges.end(); ++active) { |
| active->calcLine(); |
| } |
| // compute winding sum for edges |
| SkAntiEdge* first = fHeadEdge.fNext; |
| SkAntiEdge* active; |
| SkAntiEdge* listTop = first; |
| for (active = first; active != &fTailEdge; active = active->fNext) { |
| active->fWindingSum = active->fWinding; |
| while (listTop->fLastY < active->fFirstY) { |
| listTop = listTop->fNext; |
| } |
| for (SkAntiEdge* check = listTop; check->fFirstY <= active->fFirstY; check = check->fNext) { |
| if (check == active) { |
| continue; |
| } |
| if (check->fLastY <= active->fFirstY) { |
| continue; |
| } |
| if (check->fFirstX > active->fFirstX) { |
| continue; |
| } |
| if (check->fFirstX == active->fFirstX && check->fDX > active->fDX) { |
| continue; |
| } |
| active->fWindingSum += check->fWinding; |
| } |
| } |
| } |
| |
| extern "C" { |
| static int edge_compare(const void* a, const void* b) { |
| const SkAntiEdge* edgea = *(const SkAntiEdge**)a; |
| const SkAntiEdge* edgeb = *(const SkAntiEdge**)b; |
| |
| int valuea = edgea->fFirstY; |
| int valueb = edgeb->fFirstY; |
| |
| if (valuea == valueb) { |
| valuea = edgea->fFirstX; |
| valueb = edgeb->fFirstX; |
| } |
| |
| if (valuea == valueb) { |
| valuea = edgea->fDX; |
| valueb = edgeb->fDX; |
| } |
| |
| return valuea - valueb; |
| } |
| } |
| |
| void SkAntiEdgeBuilder::sort(SkTDArray<SkAntiEdge*>& listOfEdges) { |
| SkAntiEdge** list = listOfEdges.begin(); |
| int count = listOfEdges.count(); |
| qsort(list, count, sizeof(SkAntiEdge*), edge_compare); |
| |
| // link the edges in sorted order |
| for (int i = 1; i < count; i++) { |
| list[i - 1]->fNext = list[i]; |
| list[i]->fPrev = list[i - 1]; |
| } |
| } |
| |
| #define kEDGE_HEAD_XY SK_MinS32 |
| #define kEDGE_TAIL_XY SK_MaxS32 |
| |
| void SkAntiEdgeBuilder::sort() { |
| sort(fList); |
| SkAntiEdge* last = fList.end()[-1]; |
| fHeadEdge.fNext = fList[0]; |
| fHeadEdge.fFirstX = fHeadEdge.fFirstY = fHeadEdge.fWalkY = fHeadEdge.fLastY = kEDGE_HEAD_XY; |
| fList[0]->fPrev = &fHeadEdge; |
| |
| fTailEdge.fPrev = last; |
| fTailEdge.fFirstX = fTailEdge.fFirstY = fTailEdge.fWalkY = fTailEdge.fLastY = kEDGE_TAIL_XY; |
| last->fNext = &fTailEdge; |
| } |
| |
| static inline void remove_edge(SkAntiEdge* edge) { |
| edge->fPrev->fNext = edge->fNext; |
| edge->fNext->fPrev = edge->fPrev; |
| } |
| |
| static inline void swap_edges(SkAntiEdge* prev, SkAntiEdge* next) { |
| SkASSERT(prev->fNext == next && next->fPrev == prev); |
| |
| // remove prev from the list |
| prev->fPrev->fNext = next; |
| next->fPrev = prev->fPrev; |
| |
| // insert prev after next |
| prev->fNext = next->fNext; |
| next->fNext->fPrev = prev; |
| next->fNext = prev; |
| prev->fPrev = next; |
| } |
| |
| static void backward_insert_edge_based_on_x(SkAntiEdge* edge SkDECLAREPARAM(int, y)) { |
| SkFixed x = edge->fFirstX; |
| |
| for (;;) { |
| SkAntiEdge* prev = edge->fPrev; |
| |
| // add 1 to curr_y since we may have added new edges (built from curves) |
| // that start on the next scanline |
| SkASSERT(prev && SkFixedFloor(prev->fWalkY - prev->fDXFlipped) <= y + 1); |
| |
| if (prev->fFirstX <= x) { |
| break; |
| } |
| swap_edges(prev, edge); |
| } |
| } |
| |
| static void insert_new_edges(SkAntiEdge* newEdge, SkFixed curr_y) { |
| int y = SkFixedFloor(curr_y); |
| if (SkFixedFloor(newEdge->fWalkY - newEdge->fDXFlipped) < y) { |
| return; |
| } |
| while (SkFixedFloor(newEdge->fWalkY - newEdge->fDXFlipped) == y) { |
| SkAntiEdge* next = newEdge->fNext; |
| backward_insert_edge_based_on_x(newEdge SkPARAM(y)); |
| newEdge = next; |
| } |
| } |
| |
| static int find_active_edges(int y, SkAntiEdge** activeLeft, |
| SkAntiEdge** activeLast) { |
| SkAntiEdge* first = *activeLeft; |
| SkFixed bottom = first->fLastY; |
| SkAntiEdge* active = first->fNext; |
| first->fLinkSet = false; |
| SkFixed yLimit = SkIntToFixed(y + 1); // limiting pixel edge |
| for ( ; active->fWalkY != kEDGE_TAIL_XY; active = active->fNext) { |
| active->fLinkSet = false; |
| if (yLimit <= active->fWalkY - active->fDXFlipped) { |
| break; |
| } |
| if ((*activeLeft)->fWalkX > active->fWalkX) { |
| *activeLeft = active; |
| } |
| if (bottom > active->fLastY) { |
| bottom = active->fLastY; |
| } |
| } |
| *activeLast = active; |
| return SkFixedCeil(bottom); |
| } |
| |
| // All edges are oriented to increase in y. Link edges with common tops and |
| // bottoms so the links can share their winding sum. |
| void SkAntiEdgeBuilder::link() { |
| SkAntiEdge* tail = fEdges.end(); |
| // look for links forwards and backwards |
| SkAntiEdge* prev = fEdges.begin(); |
| SkAntiEdge* active; |
| for (active = prev + 1; active != tail; ++active) { |
| if (prev->fWinding == active->fWinding) { |
| if (prev->fLastX == active->fFirstX && prev->fLastY == active->fFirstY) { |
| prev->fLink = active; |
| active->fLinkSet = true; |
| } else if (active->fLastX == prev->fFirstX && active->fLastY == prev->fFirstY) { |
| active->fLink = prev; |
| prev->fLinkSet = true; |
| } |
| } |
| prev = active; |
| } |
| // look for stragglers |
| prev = fEdges.begin() - 1; |
| do { |
| do { |
| if (++prev == tail) { |
| return; |
| } |
| } while (prev->fLinkSet || NULL != prev->fLink); |
| for (active = prev + 1; active != tail; ++active) { |
| if (active->fLinkSet || NULL != active->fLink) { |
| continue; |
| } |
| if (prev->fWinding != active->fWinding) { |
| continue; |
| } |
| if (prev->fLastX == active->fFirstX && prev->fLastY == active->fFirstY) { |
| prev->fLink = active; |
| active->fLinkSet = true; |
| break; |
| } |
| if (active->fLastX == prev->fFirstX && active->fLastY == prev->fFirstY) { |
| active->fLink = prev; |
| prev->fLinkSet = true; |
| break; |
| } |
| } |
| } while (true); |
| } |
| |
| void SkAntiEdgeBuilder::split(SkAntiEdge* edge, SkFixed y) { |
| SkPoint upperPoint = {edge->fFirstX, edge->fFirstY}; |
| SkPoint midPoint = {edge->fFirstX + SkMulDiv(y - edge->fFirstY, |
| edge->fLastX - edge->fFirstX, edge->fLastY - edge->fFirstY), y}; |
| SkPoint lowerPoint = {edge->fLastX, edge->fLastY}; |
| int8_t winding = edge->fWinding; |
| edge->setLine(upperPoint, midPoint); |
| edge->fWinding = winding; |
| SkAntiEdge* lower = fEdges.append(); |
| lower->setLine(midPoint, lowerPoint); |
| lower->fWinding = winding; |
| insert_new_edges(lower, y); |
| } |
| |
| // An edge computes pixel coverage by considering the integral winding value |
| // to its left. If an edge is enclosed by fractional winding, split it. |
| // FIXME: This is also a good time to find crossing edges and split them, too. |
| void SkAntiEdgeBuilder::split() { |
| // create a new set of edges that describe the whole link |
| SkTDArray<SkAntiEdge> links; |
| SkAntiEdge* first = fHeadEdge.fNext; |
| SkAntiEdge* active; |
| for (active = first; active != &fTailEdge; active = active->fNext) { |
| if (active->fLinkSet || NULL == active->fLink) { |
| continue; |
| } |
| SkAntiEdge* link = links.append(); |
| link->fFirstX = active->fFirstX; |
| link->fFirstY = active->fFirstY; |
| SkAntiEdge* linkEnd; |
| SkAntiEdge* next = active; |
| do { |
| linkEnd = next; |
| next = next->fLink; |
| } while (NULL != next); |
| link->fLastX = linkEnd->fLastX; |
| link->fLastY = linkEnd->fLastY; |
| } |
| // create a list of all edges, links and singletons |
| SkTDArray<SkAntiEdge*> list; |
| for (active = links.begin(); active != links.end(); ++active) { |
| *list.append() = active; |
| } |
| for (active = first; active != &fTailEdge; active = active->fNext) { |
| if (!active->fLinkSet && NULL == active->fLink) { |
| SkAntiEdge* link = links.append(); |
| link->fFirstX = active->fFirstX; |
| link->fFirstY = active->fFirstY; |
| link->fLastX = active->fLastX; |
| link->fLastY = active->fLastY; |
| *list.append() = link; |
| } |
| } |
| SkAntiEdge tail; |
| tail.fFirstY = tail.fLastY = kEDGE_TAIL_XY; |
| *list.append() = &tail; |
| sort(list); |
| // walk the list, splitting edges partially occluded on the left |
| SkAntiEdge* listTop = list[0]; |
| for (active = first; active != &fTailEdge; active = active->fNext) { |
| while (listTop->fLastY < active->fFirstY) { |
| listTop = listTop->fNext; |
| } |
| for (SkAntiEdge* check = listTop; check->fFirstY < active->fLastY; check = check->fNext) { |
| if (check->fFirstX > active->fFirstX) { |
| continue; |
| } |
| if (check->fFirstX == active->fFirstX && check->fDX > active->fDX) { |
| continue; |
| } |
| if (check->fFirstY > active->fFirstY) { |
| split(active, check->fFirstY); |
| } |
| if (check->fLastY < active->fLastY) { |
| split(active, check->fLastY); |
| } |
| } |
| } |
| } |
| |
| static inline uint8_t coverage_to_8(int coverage) { |
| uint16_t x = coverage < 0 ? 0 : coverage > 0xFFFF ? 0xFFFF : coverage; |
| // for values 0x7FFF and smaller, add (0x7F - high byte) and trunc |
| // for values 0x8000 and larger, subtract (high byte - 0x80) and trunc |
| return (x + 0x7f + (x >> 15) - (x >> 8)) >> 8; |
| } |
| |
| void SkAntiEdgeBuilder::walk(uint8_t* result, int rowBytes, int height) { |
| SkAntiEdge* first = fHeadEdge.fNext; |
| SkFixed top = first->fWalkY - first->fDXFlipped; |
| int y = SkFixedFloor(top); |
| do { |
| SkAntiEdge* activeLeft = first; |
| SkAntiEdge* activeLast, * active; |
| int yLast = find_active_edges(y, &activeLeft, &activeLast); |
| while (y < yLast) { |
| SkAssertResult(y >= 0); |
| SkAssertResult(y < height); |
| SkFixed left = activeLeft->fWalkX; |
| int x = SkFixedFloor(left); |
| uint8_t* resultPtr = &result[y * rowBytes + x]; |
| bool finished; |
| do { |
| left = SkIntToFixed(x); |
| SkAssertResult(x >= 0); |
| // SkAssertResult(x < pixelCol); |
| if (x >= rowBytes) { // FIXME: cumulative error in fX += fDX |
| break; // fails to set fFinished early enough |
| } // see test 6 (dy<dx) |
| finished = true; |
| int coverage = 0; |
| for (active = first; active != activeLast; active = active->fNext) { |
| if (left + SK_Fixed1 <= active->fX) { |
| finished = false; |
| continue; // walker is to the left of edge |
| } |
| int cover = active->fDXFlipped ? |
| active->advanceFlippedX(left) : active->advanceX(left); |
| if (0 == active->fWindingSum) { |
| cover = -cover; |
| } |
| coverage += cover; |
| finished &= active->fFinished; |
| } |
| uint8_t old = *resultPtr; |
| uint8_t pix = coverage_to_8(coverage); |
| uint8_t blend = old > pix ? old : pix; |
| *resultPtr++ = blend; |
| ++x; |
| } while (!finished); |
| ++y; |
| top = SkIntToFixed(y); |
| SkFixed topLimit = top + SK_Fixed1; |
| SkFixed xSort = -SK_FixedMax; |
| for (active = first; active != activeLast; active = active->fNext) { |
| if (xSort > active->fX || topLimit > active->fLastY) { |
| yLast = y; // recompute bottom after all Ys are advanced |
| } |
| xSort = active->fX; |
| if (active->fWalkY < active->fLastY) { |
| active->advanceY(top); |
| } |
| } |
| for (active = first; active != activeLast; ) { |
| SkAntiEdge* next = active->fNext; |
| if (top >= active->fLastY) { |
| remove_edge(active); |
| } |
| active = next; |
| } |
| first = fHeadEdge.fNext; |
| } |
| SkAntiEdge* prev = activeLast->fPrev; |
| if (prev != &fHeadEdge) { |
| insert_new_edges(prev, top); |
| first = fHeadEdge.fNext; |
| } |
| } while (first->fWalkY < kEDGE_TAIL_XY); |
| } |
| |
| void SkAntiEdgeBuilder::process(const SkPoint* points, int ptCount, |
| uint8_t* result, int pixelCol, int pixelRow) { |
| if (ptCount < 3) { |
| return; |
| } |
| int count = build(points, ptCount); |
| if (count == 0) { |
| return; |
| } |
| SkAssertResult(count > 1); |
| link(); |
| sort(); |
| split(); |
| calc(); |
| walk(result, pixelCol, pixelRow); |
| } |
| |
| //////////////////////////////////////////////////////////////////////////////// |
| |
| int test3by3_test; |
| |
| // input is a rectangle |
| static void test_3_by_3() { |
| const int pixelRow = 3; |
| const int pixelCol = 3; |
| const int ptCount = 4; |
| const int pixelCount = pixelRow * pixelCol; |
| const SkPoint tests[][ptCount] = { |
| {{2.0f, 1.0f}, {1.0f, 1.0f}, {1.0f, 2.0f}, {2.0f, 2.0f}}, // 0: full rect |
| {{2.5f, 1.0f}, {1.5f, 1.0f}, {1.5f, 2.0f}, {2.5f, 2.0f}}, // 1: y edge |
| {{2.0f, 1.5f}, {1.0f, 1.5f}, {1.0f, 2.5f}, {2.0f, 2.5f}}, // 2: x edge |
| {{2.5f, 1.5f}, {1.5f, 1.5f}, {1.5f, 2.5f}, {2.5f, 2.5f}}, // 3: x/y edge |
| {{2.8f, 0.2f}, {0.2f, 0.2f}, {0.2f, 2.8f}, {2.8f, 2.8f}}, // 4: large |
| {{1.8f, 1.2f}, {1.2f, 1.2f}, {1.2f, 1.8f}, {1.8f, 1.8f}}, // 5: small |
| {{0.0f, 0.0f}, {0.0f, 1.0f}, {3.0f, 2.0f}, {3.0f, 1.0f}}, // 6: dy<dx |
| {{3.0f, 0.0f}, {0.0f, 1.0f}, {0.0f, 2.0f}, {3.0f, 1.0f}}, // 7: dy<-dx |
| {{1.0f, 0.0f}, {0.0f, 0.0f}, {1.0f, 3.0f}, {2.0f, 3.0f}}, // 8: dy>dx |
| {{2.0f, 0.0f}, {1.0f, 0.0f}, {0.0f, 3.0f}, {1.0f, 3.0f}}, // 9: dy>-dx |
| {{0.5f, 0.5f}, {0.5f, 1.5f}, {2.5f, 2.5f}, {2.5f, 1.5f}}, // 10: dy<dx 2 |
| {{2.5f, 0.5f}, {0.5f, 1.5f}, {0.5f, 2.5f}, {2.5f, 1.5f}}, // 11: dy<-dx 2 |
| {{0.0f, 0.0f}, {2.0f, 0.0f}, {2.0f, 2.0f}, {0.0f, 2.0f}}, // 12: 2x2 |
| {{0.0f, 0.0f}, {3.0f, 0.0f}, {3.0f, 3.0f}, {0.0f, 3.0f}}, // 13: 3x3 |
| {{1.75f, 0.25f}, {2.75f, 1.25f}, {1.25f, 2.75f}, {0.25f, 1.75f}}, // 14 |
| {{2.25f, 0.25f}, {2.75f, 0.75f}, {0.75f, 2.75f}, {0.25f, 2.25f}}, // 15 |
| {{0.25f, 0.75f}, {0.75f, 0.25f}, {2.75f, 2.25f}, {2.25f, 2.75f}}, // 16 |
| {{1.25f, 0.50f}, {1.75f, 0.25f}, {2.75f, 2.25f}, {2.25f, 2.50f}}, // 17 |
| {{1.00f, 0.75f}, {2.00f, 0.50f}, {2.00f, 1.50f}, {1.00f, 1.75f}}, // 18 |
| {{1.00f, 0.50f}, {2.00f, 0.75f}, {2.00f, 1.75f}, {1.00f, 1.50f}}, // 19 |
| {{1.00f, 0.75f}, {1.00f, 1.75f}, {2.00f, 1.50f}, {2.00f, 0.50f}}, // 20 |
| {{1.00f, 0.50f}, {1.00f, 1.50f}, {2.00f, 1.75f}, {2.00f, 0.75f}}, // 21 |
| }; |
| const uint8_t results[][pixelCount] = { |
| {0x00, 0x00, 0x00, // 0: 1 pixel rect |
| 0x00, 0xFF, 0x00, |
| 0x00, 0x00, 0x00}, |
| {0x00, 0x00, 0x00, // 1: y edge |
| 0x00, 0x7F, 0x80, |
| 0x00, 0x00, 0x00}, |
| {0x00, 0x00, 0x00, // 2: x edge |
| 0x00, 0x7F, 0x00, |
| 0x00, 0x7F, 0x00}, |
| {0x00, 0x00, 0x00, // 3: x/y edge |
| 0x00, 0x40, 0x40, |
| 0x00, 0x40, 0x40}, |
| {0xA3, 0xCC, 0xA3, // 4: large |
| 0xCC, 0xFF, 0xCC, |
| 0xA3, 0xCC, 0xA3}, |
| {0x00, 0x00, 0x00, // 5: small |
| 0x00, 0x5C, 0x00, |
| 0x00, 0x00, 0x00}, |
| {0xD5, 0x80, 0x2B, // 6: dy<dx |
| 0x2A, 0x7F, 0xD4, |
| 0x00, 0x00, 0x00}, |
| {0x2B, 0x80, 0xD5, // 7: dy<-dx |
| 0xD4, 0x7F, 0x2A, |
| 0x00, 0x00, 0x00}, |
| {0xD5, 0x2A, 0x00, // 8: dy>dx |
| 0x80, 0x7F, 0x00, |
| 0x2B, 0xD4, 0x00}, |
| {0x2A, 0xD5, 0x00, // 9: dy>-dx |
| 0x7F, 0x80, 0x00, |
| 0xD4, 0x2B, 0x00}, |
| {0x30, 0x10, 0x00, // 10: dy<dx 2 |
| 0x50, 0xDF, 0x50, |
| 0x00, 0x10, 0x30}, |
| {0x00, 0x10, 0x30, // 11: dy<-dx 2 |
| 0x50, 0xDF, 0x50, |
| 0x30, 0x10, 0x00}, |
| {0xFF, 0xFF, 0x00, // 12: 2x2 |
| 0xFF, 0xFF, 0x00, |
| 0x00, 0x00, 0x00}, |
| {0xFF, 0xFF, 0xFF, // 13: 3x3 |
| 0xFF, 0xFF, 0xFF, |
| 0xFF, 0xFF, 0xFF}, |
| {0x00, 0x70, 0x20, // 14 |
| 0x70, 0xFF, 0x70, |
| 0x20, 0x70, 0x00}, |
| {0x00, 0x20, 0x60, // 15 |
| 0x20, 0xBF, 0x20, |
| 0x60, 0x20, 0x00}, |
| {0x60, 0x20, 0x00, // 16 |
| 0x20, 0xBF, 0x20, |
| 0x00, 0x20, 0x60}, |
| {0x00, 0x60, 0x04, // 17 |
| 0x00, 0x40, 0x60, |
| 0x00, 0x00, 0x3C}, |
| {0x00, 0x60, 0x00, // 18 |
| 0x00, 0x9F, 0x00, |
| 0x00, 0x00, 0x00}, |
| {0x00, 0x60, 0x00, // 19 |
| 0x00, 0x9F, 0x00, |
| 0x00, 0x00, 0x00}, |
| {0x00, 0x60, 0x00, // 20 |
| 0x00, 0x9F, 0x00, |
| 0x00, 0x00, 0x00}, |
| {0x00, 0x60, 0x00, // 21 |
| 0x00, 0x9F, 0x00, |
| 0x00, 0x00, 0x00}, |
| }; |
| const int testCount = sizeof(tests) / sizeof(tests[0]); |
| SkAssertResult(testCount == sizeof(results) / sizeof(results[0])); |
| int testFirst = test3by3_test < 0 ? 0 : test3by3_test; |
| int testLast = test3by3_test < 0 ? testCount : test3by3_test + 1; |
| for (int testIndex = testFirst; testIndex < testLast; ++testIndex) { |
| uint8_t result[pixelRow][pixelCol]; |
| sk_bzero(result, sizeof(result)); |
| const SkPoint* rect = tests[testIndex]; |
| SkAntiEdgeBuilder builder; |
| builder.process(rect, ptCount, result[0], pixelCol, pixelRow); |
| SkAssertResult(memcmp(results[testIndex], result[0], pixelCount) == 0); |
| } |
| } |
| |
| // input has arbitrary number of points |
| static void test_arbitrary_3_by_3() { |
| const int pixelRow = 3; |
| const int pixelCol = 3; |
| const int pixelCount = pixelRow * pixelCol; |
| const SkPoint t1[] = { {1,1}, {2,1}, {2,1.5f}, {1,1.5f}, {1,2}, {2,2}, |
| {2,1.5f}, {1,1.5f}, {1,1} }; |
| const SkPoint* tests[] = { t1 }; |
| size_t testPts[] = { sizeof(t1) / sizeof(t1[0]) }; |
| const uint8_t results[][pixelCount] = { |
| {0x00, 0x00, 0x00, // 0: 1 pixel rect |
| 0x00, 0xFF, 0x00, |
| 0x00, 0x00, 0x00}, |
| }; |
| const int testCount = sizeof(tests) / sizeof(tests[0]); |
| SkAssertResult(testCount == sizeof(results) / sizeof(results[0])); |
| int testFirst = test3by3_test < 0 ? 0 : test3by3_test; |
| int testLast = test3by3_test < 0 ? testCount : test3by3_test + 1; |
| for (int testIndex = testFirst; testIndex < testLast; ++testIndex) { |
| uint8_t result[pixelRow][pixelCol]; |
| sk_bzero(result, sizeof(result)); |
| const SkPoint* pts = tests[testIndex]; |
| size_t ptCount = testPts[testIndex]; |
| SkAntiEdgeBuilder builder; |
| builder.process(pts, ptCount, result[0], pixelCol, pixelRow); |
| SkAssertResult(memcmp(results[testIndex], result[0], pixelCount) == 0); |
| } |
| } |
| |
| #include "SkRect.h" |
| #include "SkPath.h" |
| |
| int testsweep_test; |
| |
| static void create_sweep(uint8_t* result, int pixelRow, int pixelCol, SkScalar rectWidth) { |
| const int ptCount = 4; |
| SkRect refRect = {pixelCol / 2 - rectWidth / 2, 5, |
| pixelCol / 2 + rectWidth / 2, pixelRow / 2 - 5}; |
| SkPath refPath; |
| refPath.addRect(refRect); |
| SkScalar angleFirst = testsweep_test < 0 ? 0 : testsweep_test; |
| SkScalar angleLast = testsweep_test < 0 ? 360 : testsweep_test + 1; |
| for (SkScalar angle = angleFirst; angle < angleLast; angle += 12) { |
| SkPath rotPath; |
| SkMatrix matrix; |
| matrix.setRotate(angle, SkIntToScalar(pixelCol) / 2, |
| SkIntToScalar(pixelRow) / 2); |
| refPath.transform(matrix, &rotPath); |
| SkPoint rect[ptCount], temp[2]; |
| SkPath::Iter iter(rotPath, false); |
| int index = 0; |
| for (;;) { |
| SkPath::Verb verb = iter.next(temp); |
| if (verb == SkPath::kMove_Verb) { |
| continue; |
| } |
| if (verb == SkPath::kClose_Verb) { |
| break; |
| } |
| SkAssertResult(SkPath::kLine_Verb == verb); |
| rect[index++] = temp[0]; |
| } |
| SkAntiEdgeBuilder builder; |
| builder.process(rect, ptCount, result, pixelCol, pixelRow); |
| } |
| } |
| |
| static void create_horz(uint8_t* result, int pixelRow, int pixelCol) { |
| const int ptCount = 4; |
| for (SkScalar x = 0; x < 100; x += 5) { |
| SkPoint rect[ptCount]; |
| rect[0].fX = 0; rect[0].fY = x; |
| rect[1].fX = 100; rect[1].fY = x; |
| rect[2].fX = 100; rect[2].fY = x + x / 50; |
| rect[3].fX = 0; rect[3].fY = x + x / 50; |
| SkAntiEdgeBuilder builder; |
| builder.process(rect, ptCount, result, pixelCol, pixelRow); |
| } |
| } |
| |
| static void create_vert(uint8_t* result, int pixelRow, int pixelCol) { |
| const int ptCount = 4; |
| for (SkScalar x = 0; x < 100; x += 5) { |
| SkPoint rect[ptCount]; |
| rect[0].fY = 0; rect[0].fX = x; |
| rect[1].fY = 100; rect[1].fX = x; |
| rect[2].fY = 100; rect[2].fX = x + x / 50; |
| rect[3].fY = 0; rect[3].fX = x + x / 50; |
| SkAntiEdgeBuilder builder; |
| builder.process(rect, ptCount, result, pixelCol, pixelRow); |
| } |
| } |
| |
| static void create_angle(uint8_t* result, int pixelRow, int pixelCol, SkScalar angle) { |
| const int ptCount = 4; |
| SkRect refRect = {25, 25, 125, 125}; |
| SkPath refPath; |
| for (SkScalar x = 30; x < 125; x += 5) { |
| refRect.fTop = x; |
| refRect.fBottom = x + (x - 25) / 50; |
| refPath.addRect(refRect); |
| } |
| SkPath rotPath; |
| SkMatrix matrix; |
| matrix.setRotate(angle, 75, 75); |
| refPath.transform(matrix, &rotPath); |
| SkPath::Iter iter(rotPath, false); |
| for (SkScalar x = 30; x < 125; x += 5) { |
| SkPoint rect[ptCount], temp[2]; |
| int index = 0; |
| for (;;) { |
| SkPath::Verb verb = iter.next(temp); |
| if (verb == SkPath::kMove_Verb) { |
| continue; |
| } |
| if (verb == SkPath::kClose_Verb) { |
| break; |
| } |
| SkAssertResult(SkPath::kLine_Verb == verb); |
| rect[index++] = temp[0]; |
| } |
| // if ((x == 30 || x == 75) && angle == 12) continue; |
| SkAntiEdgeBuilder builder; |
| builder.process(rect, ptCount, result, pixelCol, pixelRow); |
| } |
| } |
| |
| static void test_sweep() { |
| const int pixelRow = 100; |
| const int pixelCol = 100; |
| uint8_t result[pixelRow][pixelCol]; |
| sk_bzero(result, sizeof(result)); |
| create_sweep(result[0], pixelRow, pixelCol, 1); |
| } |
| |
| static void test_horz() { |
| const int pixelRow = 100; |
| const int pixelCol = 100; |
| uint8_t result[pixelRow][pixelCol]; |
| sk_bzero(result, sizeof(result)); |
| create_horz(result[0], pixelRow, pixelCol); |
| } |
| |
| static void test_vert() { |
| const int pixelRow = 100; |
| const int pixelCol = 100; |
| uint8_t result[pixelRow][pixelCol]; |
| sk_bzero(result, sizeof(result)); |
| create_vert(result[0], pixelRow, pixelCol); |
| } |
| |
| static void test_angle(SkScalar angle) { |
| const int pixelRow = 150; |
| const int pixelCol = 150; |
| uint8_t result[pixelRow][pixelCol]; |
| sk_bzero(result, sizeof(result)); |
| create_angle(result[0], pixelRow, pixelCol, angle); |
| } |
| |
| #include "SkBitmap.h" |
| |
| void CreateSweep(SkBitmap* sweep, SkScalar rectWidth) { |
| const int pixelRow = 100; |
| const int pixelCol = 100; |
| sweep->setConfig(SkBitmap::kA8_Config, pixelCol, pixelRow); |
| sweep->allocPixels(); |
| sweep->eraseColor(SK_ColorTRANSPARENT); |
| sweep->lockPixels(); |
| void* pixels = sweep->getPixels(); |
| create_sweep((uint8_t*) pixels, pixelRow, pixelCol, rectWidth); |
| sweep->unlockPixels(); |
| } |
| |
| void CreateHorz(SkBitmap* sweep) { |
| const int pixelRow = 100; |
| const int pixelCol = 100; |
| sweep->setConfig(SkBitmap::kA8_Config, pixelCol, pixelRow); |
| sweep->allocPixels(); |
| sweep->eraseColor(SK_ColorTRANSPARENT); |
| sweep->lockPixels(); |
| void* pixels = sweep->getPixels(); |
| create_horz((uint8_t*) pixels, pixelRow, pixelCol); |
| sweep->unlockPixels(); |
| } |
| |
| void CreateVert(SkBitmap* sweep) { |
| const int pixelRow = 100; |
| const int pixelCol = 100; |
| sweep->setConfig(SkBitmap::kA8_Config, pixelCol, pixelRow); |
| sweep->allocPixels(); |
| sweep->eraseColor(SK_ColorTRANSPARENT); |
| sweep->lockPixels(); |
| void* pixels = sweep->getPixels(); |
| create_vert((uint8_t*) pixels, pixelRow, pixelCol); |
| sweep->unlockPixels(); |
| } |
| |
| void CreateAngle(SkBitmap* sweep, SkScalar angle) { |
| const int pixelRow = 150; |
| const int pixelCol = 150; |
| sweep->setConfig(SkBitmap::kA8_Config, pixelCol, pixelRow); |
| sweep->allocPixels(); |
| sweep->eraseColor(SK_ColorTRANSPARENT); |
| sweep->lockPixels(); |
| void* pixels = sweep->getPixels(); |
| create_angle((uint8_t*) pixels, pixelRow, pixelCol, angle); |
| sweep->unlockPixels(); |
| } |
| |
| #include "SkCanvas.h" |
| |
| static void testPng() { |
| SkBitmap device; |
| device.setConfig(SkBitmap::kARGB_8888_Config, 4, 4); |
| device.allocPixels(); |
| device.eraseColor(0xFFFFFFFF); |
| |
| SkCanvas canvas(device); |
| canvas.drawARGB(167, 0, 0, 0); |
| |
| device.lockPixels(); |
| unsigned char* pixels = (unsigned char*) device.getPixels(); |
| SkDebugf("%02x%02x%02x%02x", pixels[3], pixels[2], pixels[1], pixels[0]); |
| } |
| |
| void SkAntiEdge_Test() { |
| testPng(); |
| test_arbitrary_3_by_3(); |
| test_angle(12); |
| #if 0 |
| test3by3_test = 18; |
| #else |
| test3by3_test = -1; |
| #endif |
| #if 0 |
| testsweep_test = 7 * 12; |
| #else |
| testsweep_test = -1; |
| #endif |
| if (testsweep_test == -1) { |
| test_3_by_3(); |
| } |
| test_sweep(); |
| test_horz(); |
| test_vert(); |
| } |
