| |
| /* |
| * 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 "SkRegion.h" |
| #include "SkChunkAlloc.h" |
| #include "SkTDArray.h" |
| #include "SkTemplates.h" |
| |
| #if 0 |
| |
| struct VEdge { |
| VEdge* fPrev; |
| VEdge* fNext; |
| |
| SkRegion::RunType fX; |
| SkRegion::RunType fTop; |
| SkRegion::RunType fBottom; |
| int fWinding; |
| |
| void removeFromList() { |
| fPrev->fNext = fNext; |
| fNext->fPrev = fPrev; |
| } |
| |
| void backwardsInsert() { |
| while (fPrev->fX > fX) { |
| VEdge* prev = fPrev; |
| VEdge* next = this; |
| |
| // 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 SetFromRect(VEdge edges[], const SkIRect& r) { |
| edges[0].fX = r.fLeft; |
| edges[0].fTop = r.fTop; |
| edges[0].fBottom = r.fBottom; |
| edges[0].fWinding = -1; |
| |
| edges[1].fX = r.fRight; |
| edges[1].fTop = r.fTop; |
| edges[1].fBottom = r.fBottom; |
| edges[1].fWinding = 1; |
| } |
| }; |
| |
| class Accumulator { |
| public: |
| Accumulator(SkRegion::RunType top, int numRects); |
| ~Accumulator() {} |
| |
| SkRegion::RunType append(SkRegion::RunType top, const VEdge* edge); |
| |
| 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; |
| int fRectCount; |
| }; |
| |
| Accumulator::Accumulator(SkRegion::RunType top, int numRects) |
| : fAlloc((1 + numRects * 2 + 1) * sizeof(int32_t)) { |
| fRectCount = numRects; |
| fTop = top; |
| fTotalCount = 2; // Top + final sentinel |
| } |
| |
| //#define TRACE_ROW(code) code |
| #define TRACE_ROW(code) |
| |
| SkRegion::RunType Accumulator::append(SkRegion::RunType currY, const VEdge* edge) { |
| // worst-case size |
| size_t size = fRectCount * 2 * sizeof(SkRegion::RunType); |
| SkRegion::RunType* row = (SkRegion::RunType*)fAlloc.allocThrow(size); |
| SkRegion::RunType* rowHead = row; |
| |
| SkRegion::RunType nextY = SkRegion::kRunTypeSentinel; |
| int winding = edge->fWinding; |
| |
| // record the L R values for this row |
| |
| if (edge->fTop > currY) { |
| nextY = SkMin32(nextY, edge->fTop); |
| TRACE_ROW(SkDebugf("Y %d\n", currY);) |
| } else { |
| SkRegion::RunType currR; |
| *row++ = edge->fX; |
| TRACE_ROW(SkDebugf("Y %d [%d", currY, edge->fX);) |
| edge = edge->fNext; |
| for (;;) { |
| if (edge->fTop > currY) { |
| nextY = SkMin32(nextY, edge->fTop); |
| break; |
| } |
| |
| int prevWinding = winding; |
| winding += edge->fWinding; |
| if (0 == winding) { // we finished an interval |
| currR = edge->fX; |
| } else if (0 == prevWinding && edge->fX > currR) { |
| *row++ = currR; |
| *row++ = edge->fX; |
| TRACE_ROW(SkDebugf(" %d] [%d", currR, edge->fX);) |
| } |
| |
| nextY = SkMin32(nextY, edge->fBottom); |
| edge = edge->fNext; |
| } |
| SkASSERT(0 == winding); |
| *row++ = currR; |
| TRACE_ROW(SkDebugf(" %d]\n", currR);) |
| } |
| int rowCount = row - rowHead; |
| |
| // now see if we have already seen this row, or if its unique |
| |
| Row* r = fRows.count() ? &fRows[fRows.count() - 1] : NULL; |
| if (r && (r->fCount == rowCount) && |
| !memcmp(r->fPtr, rowHead, |
| rowCount * sizeof(SkRegion::RunType))) { |
| r->fBottom = nextY; // update bottom |
| fAlloc.unalloc(rowHead); |
| } else { |
| Row* r = fRows.append(); |
| r->fPtr = rowHead; |
| r->fBottom = nextY; |
| r->fCount = rowCount; |
| fTotalCount += 1 + rowCount + 1; |
| } |
| |
| return nextY; |
| } |
| |
| 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); |
| } |
| |
| /////////////////////////////////////////////////////////////////////////////// |
| |
| template <typename T> int SkTCmp2Int(const T& a, const T& b) { |
| return (a < b) ? -1 : ((b < a) ? 1 : 0); |
| } |
| |
| static inline int SkCmp32(int32_t a, int32_t b) { |
| return (a < b) ? -1 : ((b < a) ? 1 : 0); |
| } |
| |
| static int compare_edgeptr(const void* p0, const void* p1) { |
| const VEdge* e0 = *static_cast<VEdge*const*>(p0); |
| const VEdge* e1 = *static_cast<VEdge*const*>(p1); |
| |
| SkRegion::RunType v0 = e0->fTop; |
| SkRegion::RunType v1 = e1->fTop; |
| |
| if (v0 == v1) { |
| v0 = e0->fX; |
| v1 = e1->fX; |
| } |
| return SkCmp32(v0, v1); |
| } |
| |
| // fillout edge[] from rects[], sorted. Return the head, and set the tail |
| // |
| static VEdge* sort_edges(VEdge** edgePtr, VEdge edge[], const SkIRect rects[], |
| int rectCount, VEdge** edgeTail) { |
| int i; |
| VEdge** ptr = edgePtr; |
| for (int i = 0; i < rectCount; i++) { |
| if (!rects[i].isEmpty()) { |
| VEdge::SetFromRect(edge, rects[i]); |
| *ptr++ = edge++; |
| *ptr++ = edge++; |
| } |
| } |
| |
| int edgeCount = ptr - edgePtr; |
| if (0 == edgeCount) { |
| // all the rects[] were empty |
| return NULL; |
| } |
| |
| qsort(edgePtr, edgeCount, sizeof(*edgePtr), compare_edgeptr); |
| for (i = 1; i < edgeCount; i++) { |
| edgePtr[i - 1]->fNext = edgePtr[i]; |
| edgePtr[i]->fPrev = edgePtr[i - 1]; |
| } |
| *edgeTail = edgePtr[edgeCount - 1]; |
| return edgePtr[0]; |
| } |
| |
| bool SkRegion::setRects(const SkIRect rects[], int rectCount) { |
| if (0 == rectCount) { |
| return this->setEmpty(); |
| } |
| if (1 == rectCount) { |
| return this->setRect(rects[0]); |
| } |
| |
| int edgeCount = rectCount * 2; |
| SkAutoMalloc memory((sizeof(VEdge) + sizeof(VEdge*)) * edgeCount); |
| VEdge** edgePtr = (VEdge**)memory.get(); |
| VEdge* tail, *head = (VEdge*)(edgePtr + edgeCount); |
| head = sort_edges(edgePtr, head, rects, rectCount, &tail); |
| // check if we have no edges |
| if (NULL == head) { |
| return this->setEmpty(); |
| } |
| |
| // at this stage, we don't really care about edgeCount, or if rectCount is |
| // larger that it should be (since sort_edges might have skipped some |
| // empty rects[]). rectCount now is just used for worst-case allocations |
| |
| VEdge headEdge, tailEdge; |
| headEdge.fPrev = NULL; |
| headEdge.fNext = head; |
| headEdge.fTop = SK_MinS32; |
| headEdge.fX = SK_MinS32; |
| head->fPrev = &headEdge; |
| |
| tailEdge.fPrev = tail; |
| tailEdge.fNext = NULL; |
| tailEdge.fTop = SK_MaxS32; |
| tail->fNext = &tailEdge; |
| |
| int32_t currY = head->fTop; |
| Accumulator accum(currY, rectCount); |
| |
| while (head->fNext) { |
| VEdge* edge = head; |
| // accumulate the current |
| SkRegion::RunType nextY = accum.append(currY, edge); |
| // remove the old |
| while (edge->fTop <= currY) { |
| VEdge* next = edge->fNext; |
| if (edge->fBottom <= nextY) { |
| edge->removeFromList(); |
| } |
| edge = next; |
| } |
| // insert (sorted) the new |
| while (edge->fTop == nextY) { |
| VEdge* next = edge->fNext; |
| edge->backwardsInsert(); |
| edge = next; |
| } |
| currY = nextY; |
| head = headEdge.fNext; |
| } |
| |
| SkAutoTArray<RunType> runs(accum.count()); |
| accum.copyTo(runs.get()); |
| return this->setRuns(runs.get(), accum.count()); |
| } |
| |
| #endif |
