summaryrefslogtreecommitdiff
path: root/core/SkRegion_rects.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'core/SkRegion_rects.cpp')
-rw-r--r--core/SkRegion_rects.cpp290
1 files changed, 290 insertions, 0 deletions
diff --git a/core/SkRegion_rects.cpp b/core/SkRegion_rects.cpp
new file mode 100644
index 00000000..4121080c
--- /dev/null
+++ b/core/SkRegion_rects.cpp
@@ -0,0 +1,290 @@
+
+/*
+ * 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
generated by cgit v1.2.3 (git 2.25.1) at 2024-05-11 05:11:23 +0000