1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/gfx/skia/trunk/src/core/SkRegion_rects.cpp Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,290 @@
1.4 +
1.5 +/*
1.6 + * Copyright 2011 Google Inc.
1.7 + *
1.8 + * Use of this source code is governed by a BSD-style license that can be
1.9 + * found in the LICENSE file.
1.10 + */
1.11 +#include "SkRegion.h"
1.12 +#include "SkChunkAlloc.h"
1.13 +#include "SkTDArray.h"
1.14 +#include "SkTemplates.h"
1.15 +
1.16 +#if 0
1.17 +
1.18 +struct VEdge {
1.19 + VEdge* fPrev;
1.20 + VEdge* fNext;
1.21 +
1.22 + SkRegion::RunType fX;
1.23 + SkRegion::RunType fTop;
1.24 + SkRegion::RunType fBottom;
1.25 + int fWinding;
1.26 +
1.27 + void removeFromList() {
1.28 + fPrev->fNext = fNext;
1.29 + fNext->fPrev = fPrev;
1.30 + }
1.31 +
1.32 + void backwardsInsert() {
1.33 + while (fPrev->fX > fX) {
1.34 + VEdge* prev = fPrev;
1.35 + VEdge* next = this;
1.36 +
1.37 + // remove prev from the list
1.38 + prev->fPrev->fNext = next;
1.39 + next->fPrev = prev->fPrev;
1.40 +
1.41 + // insert prev after next
1.42 + prev->fNext = next->fNext;
1.43 + next->fNext->fPrev = prev;
1.44 + next->fNext = prev;
1.45 + prev->fPrev = next;
1.46 + }
1.47 + }
1.48 +
1.49 + static void SetFromRect(VEdge edges[], const SkIRect& r) {
1.50 + edges[0].fX = r.fLeft;
1.51 + edges[0].fTop = r.fTop;
1.52 + edges[0].fBottom = r.fBottom;
1.53 + edges[0].fWinding = -1;
1.54 +
1.55 + edges[1].fX = r.fRight;
1.56 + edges[1].fTop = r.fTop;
1.57 + edges[1].fBottom = r.fBottom;
1.58 + edges[1].fWinding = 1;
1.59 + }
1.60 +};
1.61 +
1.62 +class Accumulator {
1.63 +public:
1.64 + Accumulator(SkRegion::RunType top, int numRects);
1.65 + ~Accumulator() {}
1.66 +
1.67 + SkRegion::RunType append(SkRegion::RunType top, const VEdge* edge);
1.68 +
1.69 + int count() const { return fTotalCount; }
1.70 + void copyTo(SkRegion::RunType dst[]);
1.71 +
1.72 +private:
1.73 + struct Row {
1.74 + SkRegion::RunType* fPtr;
1.75 + SkRegion::RunType fBottom;
1.76 + int fCount; // just [L R] count
1.77 + };
1.78 + SkChunkAlloc fAlloc;
1.79 + SkTDArray<Row> fRows;
1.80 + SkRegion::RunType fTop;
1.81 + int fTotalCount;
1.82 + int fRectCount;
1.83 +};
1.84 +
1.85 +Accumulator::Accumulator(SkRegion::RunType top, int numRects)
1.86 + : fAlloc((1 + numRects * 2 + 1) * sizeof(int32_t)) {
1.87 + fRectCount = numRects;
1.88 + fTop = top;
1.89 + fTotalCount = 2; // Top + final sentinel
1.90 +}
1.91 +
1.92 +//#define TRACE_ROW(code) code
1.93 +#define TRACE_ROW(code)
1.94 +
1.95 +SkRegion::RunType Accumulator::append(SkRegion::RunType currY, const VEdge* edge) {
1.96 + // worst-case size
1.97 + size_t size = fRectCount * 2 * sizeof(SkRegion::RunType);
1.98 + SkRegion::RunType* row = (SkRegion::RunType*)fAlloc.allocThrow(size);
1.99 + SkRegion::RunType* rowHead = row;
1.100 +
1.101 + SkRegion::RunType nextY = SkRegion::kRunTypeSentinel;
1.102 + int winding = edge->fWinding;
1.103 +
1.104 + // record the L R values for this row
1.105 +
1.106 + if (edge->fTop > currY) {
1.107 + nextY = SkMin32(nextY, edge->fTop);
1.108 + TRACE_ROW(SkDebugf("Y %d\n", currY);)
1.109 + } else {
1.110 + SkRegion::RunType currR;
1.111 + *row++ = edge->fX;
1.112 + TRACE_ROW(SkDebugf("Y %d [%d", currY, edge->fX);)
1.113 + edge = edge->fNext;
1.114 + for (;;) {
1.115 + if (edge->fTop > currY) {
1.116 + nextY = SkMin32(nextY, edge->fTop);
1.117 + break;
1.118 + }
1.119 +
1.120 + int prevWinding = winding;
1.121 + winding += edge->fWinding;
1.122 + if (0 == winding) { // we finished an interval
1.123 + currR = edge->fX;
1.124 + } else if (0 == prevWinding && edge->fX > currR) {
1.125 + *row++ = currR;
1.126 + *row++ = edge->fX;
1.127 + TRACE_ROW(SkDebugf(" %d] [%d", currR, edge->fX);)
1.128 + }
1.129 +
1.130 + nextY = SkMin32(nextY, edge->fBottom);
1.131 + edge = edge->fNext;
1.132 + }
1.133 + SkASSERT(0 == winding);
1.134 + *row++ = currR;
1.135 + TRACE_ROW(SkDebugf(" %d]\n", currR);)
1.136 + }
1.137 + int rowCount = row - rowHead;
1.138 +
1.139 + // now see if we have already seen this row, or if its unique
1.140 +
1.141 + Row* r = fRows.count() ? &fRows[fRows.count() - 1] : NULL;
1.142 + if (r && (r->fCount == rowCount) &&
1.143 + !memcmp(r->fPtr, rowHead,
1.144 + rowCount * sizeof(SkRegion::RunType))) {
1.145 + r->fBottom = nextY; // update bottom
1.146 + fAlloc.unalloc(rowHead);
1.147 + } else {
1.148 + Row* r = fRows.append();
1.149 + r->fPtr = rowHead;
1.150 + r->fBottom = nextY;
1.151 + r->fCount = rowCount;
1.152 + fTotalCount += 1 + rowCount + 1;
1.153 + }
1.154 +
1.155 + return nextY;
1.156 +}
1.157 +
1.158 +void Accumulator::copyTo(SkRegion::RunType dst[]) {
1.159 + SkDEBUGCODE(SkRegion::RunType* startDst = dst;)
1.160 +
1.161 + *dst++ = fTop;
1.162 +
1.163 + const Row* curr = fRows.begin();
1.164 + const Row* stop = fRows.end();
1.165 + while (curr < stop) {
1.166 + *dst++ = curr->fBottom;
1.167 + memcpy(dst, curr->fPtr, curr->fCount * sizeof(SkRegion::RunType));
1.168 + dst += curr->fCount;
1.169 + *dst++ = SkRegion::kRunTypeSentinel;
1.170 + curr += 1;
1.171 + }
1.172 + *dst++ = SkRegion::kRunTypeSentinel;
1.173 + SkASSERT(dst - startDst == fTotalCount);
1.174 +}
1.175 +
1.176 +///////////////////////////////////////////////////////////////////////////////
1.177 +
1.178 +template <typename T> int SkTCmp2Int(const T& a, const T& b) {
1.179 + return (a < b) ? -1 : ((b < a) ? 1 : 0);
1.180 +}
1.181 +
1.182 +static inline int SkCmp32(int32_t a, int32_t b) {
1.183 + return (a < b) ? -1 : ((b < a) ? 1 : 0);
1.184 +}
1.185 +
1.186 +static int compare_edgeptr(const void* p0, const void* p1) {
1.187 + const VEdge* e0 = *static_cast<VEdge*const*>(p0);
1.188 + const VEdge* e1 = *static_cast<VEdge*const*>(p1);
1.189 +
1.190 + SkRegion::RunType v0 = e0->fTop;
1.191 + SkRegion::RunType v1 = e1->fTop;
1.192 +
1.193 + if (v0 == v1) {
1.194 + v0 = e0->fX;
1.195 + v1 = e1->fX;
1.196 + }
1.197 + return SkCmp32(v0, v1);
1.198 +}
1.199 +
1.200 +// fillout edge[] from rects[], sorted. Return the head, and set the tail
1.201 +//
1.202 +static VEdge* sort_edges(VEdge** edgePtr, VEdge edge[], const SkIRect rects[],
1.203 + int rectCount, VEdge** edgeTail) {
1.204 + int i;
1.205 + VEdge** ptr = edgePtr;
1.206 + for (int i = 0; i < rectCount; i++) {
1.207 + if (!rects[i].isEmpty()) {
1.208 + VEdge::SetFromRect(edge, rects[i]);
1.209 + *ptr++ = edge++;
1.210 + *ptr++ = edge++;
1.211 + }
1.212 + }
1.213 +
1.214 + int edgeCount = ptr - edgePtr;
1.215 + if (0 == edgeCount) {
1.216 + // all the rects[] were empty
1.217 + return NULL;
1.218 + }
1.219 +
1.220 + qsort(edgePtr, edgeCount, sizeof(*edgePtr), compare_edgeptr);
1.221 + for (i = 1; i < edgeCount; i++) {
1.222 + edgePtr[i - 1]->fNext = edgePtr[i];
1.223 + edgePtr[i]->fPrev = edgePtr[i - 1];
1.224 + }
1.225 + *edgeTail = edgePtr[edgeCount - 1];
1.226 + return edgePtr[0];
1.227 +}
1.228 +
1.229 +bool SkRegion::setRects(const SkIRect rects[], int rectCount) {
1.230 + if (0 == rectCount) {
1.231 + return this->setEmpty();
1.232 + }
1.233 + if (1 == rectCount) {
1.234 + return this->setRect(rects[0]);
1.235 + }
1.236 +
1.237 + int edgeCount = rectCount * 2;
1.238 + SkAutoMalloc memory((sizeof(VEdge) + sizeof(VEdge*)) * edgeCount);
1.239 + VEdge** edgePtr = (VEdge**)memory.get();
1.240 + VEdge* tail, *head = (VEdge*)(edgePtr + edgeCount);
1.241 + head = sort_edges(edgePtr, head, rects, rectCount, &tail);
1.242 + // check if we have no edges
1.243 + if (NULL == head) {
1.244 + return this->setEmpty();
1.245 + }
1.246 +
1.247 + // at this stage, we don't really care about edgeCount, or if rectCount is
1.248 + // larger that it should be (since sort_edges might have skipped some
1.249 + // empty rects[]). rectCount now is just used for worst-case allocations
1.250 +
1.251 + VEdge headEdge, tailEdge;
1.252 + headEdge.fPrev = NULL;
1.253 + headEdge.fNext = head;
1.254 + headEdge.fTop = SK_MinS32;
1.255 + headEdge.fX = SK_MinS32;
1.256 + head->fPrev = &headEdge;
1.257 +
1.258 + tailEdge.fPrev = tail;
1.259 + tailEdge.fNext = NULL;
1.260 + tailEdge.fTop = SK_MaxS32;
1.261 + tail->fNext = &tailEdge;
1.262 +
1.263 + int32_t currY = head->fTop;
1.264 + Accumulator accum(currY, rectCount);
1.265 +
1.266 + while (head->fNext) {
1.267 + VEdge* edge = head;
1.268 + // accumulate the current
1.269 + SkRegion::RunType nextY = accum.append(currY, edge);
1.270 + // remove the old
1.271 + while (edge->fTop <= currY) {
1.272 + VEdge* next = edge->fNext;
1.273 + if (edge->fBottom <= nextY) {
1.274 + edge->removeFromList();
1.275 + }
1.276 + edge = next;
1.277 + }
1.278 + // insert (sorted) the new
1.279 + while (edge->fTop == nextY) {
1.280 + VEdge* next = edge->fNext;
1.281 + edge->backwardsInsert();
1.282 + edge = next;
1.283 + }
1.284 + currY = nextY;
1.285 + head = headEdge.fNext;
1.286 + }
1.287 +
1.288 + SkAutoTArray<RunType> runs(accum.count());
1.289 + accum.copyTo(runs.get());
1.290 + return this->setRuns(runs.get(), accum.count());
1.291 +}
1.292 +
1.293 +#endif
