diff options
Diffstat (limited to 'chromium/third_party/skia/experimental/Intersection/SkAntiEdge.cpp')
| -rw-r--r-- | chromium/third_party/skia/experimental/Intersection/SkAntiEdge.cpp | 1086 |
1 files changed, 1086 insertions, 0 deletions
diff --git a/chromium/third_party/skia/experimental/Intersection/SkAntiEdge.cpp b/chromium/third_party/skia/experimental/Intersection/SkAntiEdge.cpp new file mode 100644 index 00000000000..2cce960e52d --- /dev/null +++ b/chromium/third_party/skia/experimental/Intersection/SkAntiEdge.cpp @@ -0,0 +1,1086 @@ +/* + * 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(); +} |