diff options
Diffstat (limited to 'src/core/SkRegion.cpp')
| -rw-r--r-- | src/core/SkRegion.cpp | 226 |
1 files changed, 6 insertions, 220 deletions
diff --git a/src/core/SkRegion.cpp b/src/core/SkRegion.cpp index 376f79c255..ce4252394c 100644 --- a/src/core/SkRegion.cpp +++ b/src/core/SkRegion.cpp @@ -555,230 +555,16 @@ void SkRegion::translate(int dx, int dy, SkRegion* dst) const /////////////////////////////////////////////////////////////////////////////// -#include "SkChunkAlloc.h" -#include "SkTDArray.h" -#include "SkTSearch.h" -#include "SkTemplates.h" - -template <typename T> int SkTCmp2Int(const T& a, const T& b) { - return (a < b) ? -1 : ((b < a) ? 1 : 0); -} - -struct VEdge { - int32_t fX; - int fDir; // 1, -1 -}; - -static VEdge* append_rect(VEdge* edge, const SkIRect& r) { - edge[0].fX = r.fLeft; - edge[0].fDir = -1; - edge[1].fX = r.fRight; - edge[1].fDir = 1; - return edge + 2; -} - -class Accumulator { -public: - Accumulator(SkRegion::RunType top, int numRects); - ~Accumulator() {} - - void append(int32_t bottom, const VEdge edge[], int count); - - int count() const { return fTotalCount; } - void copyTo(SkRegion::RunType dst[]); - -private: - struct Row { - SkRegion::RunType* fPtr; - SkRegion::RunType fBottom; - int fCount; // just [L R] count - }; - SkChunkAlloc fAlloc; - SkTDArray<Row> fRows; - SkRegion::RunType fTop; - int fTotalCount; -}; - -Accumulator::Accumulator(SkRegion::RunType top, int numRects) - : fAlloc((1 + numRects * 2 + 1) * sizeof(int32_t)) { - fTop = top; - fTotalCount = 2; // Top + final sentinel -} - -static int union_edges(SkRegion::RunType dst[], const VEdge edge[], int count) { - if (0 == count) { - return 0; - } - - SkRegion::RunType* startDst = dst; - const VEdge* stop = edge + count; - - SkRegion::RunType currR; - int dir = edge->fDir; - - *dst++ = edge->fX; // initial L - while (++edge < stop) { - int prevDir = dir; - dir += edge->fDir; - if (0 == dir) { // we finished an interval - currR = edge->fX; - } else if (0 == prevDir && edge->fX > currR) { - *dst++ = currR; - *dst++ = edge->fX; - } - } - SkASSERT(0 == dir); - *dst++ = currR; - SkDEBUGCODE(int resultCount = dst - startDst;) - SkASSERT(resultCount <= count && (resultCount & 1) == 0); - return dst - startDst; -} - -void Accumulator::append(int32_t bottom, const VEdge edge[], int count) { - SkASSERT((count & 1) == 0); - - size_t size = count * sizeof(SkRegion::RunType); - int32_t* row = (SkRegion::RunType*)fAlloc.allocThrow(size); - int rowCount = union_edges(row, edge, count); - - Row* r = fRows.count() ? &fRows[fRows.count() - 1] : NULL; - if (r && (r->fCount == rowCount) && - !memcmp(r->fPtr, row, - rowCount * sizeof(SkRegion::RunType))) { - r->fBottom = bottom; // update bottom - fAlloc.unalloc(row); - } else { - Row* r = fRows.append(); - r->fPtr = row; - r->fBottom = bottom; - r->fCount = rowCount; - fTotalCount += 1 + rowCount + 1; - } -} - -void Accumulator::copyTo(SkRegion::RunType dst[]) { - SkDEBUGCODE(SkRegion::RunType* startDst = dst;) - - *dst++ = fTop; - - const Row* curr = fRows.begin(); - const Row* stop = fRows.end(); - while (curr < stop) { - *dst++ = curr->fBottom; - memcpy(dst, curr->fPtr, curr->fCount * sizeof(SkRegion::RunType)); - dst += curr->fCount; - *dst++ = SkRegion::kRunTypeSentinel; - curr += 1; - } - *dst++ = SkRegion::kRunTypeSentinel; - SkASSERT(dst - startDst == fTotalCount); -} - -///////////// - -struct RNode { - RNode* fNext; - const SkIRect* fRect; -}; - -static int compare_rnode_top(const void* e0, const void* e1) { - const RNode* r0 = static_cast<const RNode*>(e0); - const RNode* r1 = static_cast<const RNode*>(e1); - return SkTCmp2Int<int32_t>(r0->fRect->fTop, r1->fRect->fTop); -} - -static int compare_vedge(const void* e0, const void* e1) { - const VEdge* v0 = static_cast<const VEdge*>(e0); - const VEdge* v1 = static_cast<const VEdge*>(e1); - return SkTCmp2Int<int32_t>(v0->fX, v1->fX); -} - bool SkRegion::setRects(const SkIRect rects[], int count) { if (0 == count) { - return this->setEmpty(); - } - if (1 == count) { - return this->setRect(rects[0]); - } - - int i; - SkIRect sentinelRect = SkIRect::MakeLTRB(kRunTypeSentinel, kRunTypeSentinel, - kRunTypeSentinel, kRunTypeSentinel); - - SkAutoTArray<RNode> nodeStorage(count + 1); - RNode* nodes = nodeStorage.get(); - for (i = 0; i < count; i++) { - if (!rects[i].isEmpty()) { - nodes->fRect = &rects[i]; - nodes += 1; - } - } - // recompute count, since we may have skipped empty rects - count = nodes - nodeStorage.get(); - nodes = nodeStorage.get(); - // we are now done with the original rects[] parameter - SkDEBUGCODE(rects = NULL;) - - SkQSort(nodes, count, sizeof(nodes[0]), compare_rnode_top); - for (i = 0; i < count; i++) { - nodes[i].fNext = &nodes[i + 1]; - } - nodes[count].fNext = NULL; - nodes[count].fRect = &sentinelRect; - - SkAutoTArray<VEdge> edgeStorage(count * 2); - - VEdge* edges = edgeStorage.get(); - RNode* nodeHead = nodeStorage.get(); - - int32_t currY = nodeHead->fRect->fTop; - Accumulator accum(currY, count); - - while (nodeHead->fNext) { - RNode* node = nodeHead; - - int32_t nextY = kRunTypeSentinel; - const SkIRect* r = node->fRect; - for (;;) { - if (r->fTop > currY) { - nextY = SkMin32(nextY, r->fTop); - break; - } - edges = append_rect(edges, *r); - nextY = SkMin32(nextY, r->fBottom); - node = node->fNext; - r = node->fRect; - } - int edgeCount = edges - edgeStorage.get(); - edges = edgeStorage.get(); - SkASSERT(edgeCount <= count * 2); - - SkQSort(edges, edgeCount, sizeof(edges[0]), compare_vedge); - accum.append(nextY, edges, edgeCount); - - RNode* prev = NULL; - node = nodeHead; - while (node->fRect->fTop <= currY) { - RNode* next = node->fNext; - if (node->fRect->fBottom <= nextY) { - // drop this rect from our linklist - SkASSERT(node->fRect->fBottom == nextY); - if (prev) { - prev->fNext = next; - } else { - nodeHead = next; - } - } else { - prev = node; - } - node = next; + this->setEmpty(); + } else { + this->setRect(rects[0]); + for (int i = 1; i < count; i++) { + this->op(rects[i], kUnion_Op); } - currY = nextY; } - - SkAutoTArray<RunType> runs(accum.count()); - accum.copyTo(runs.get()); - return this->setRuns(runs.get(), accum.count()); + return !this->isEmpty(); } /////////////////////////////////////////////////////////////////////////////// |