1 2 /* 3 * Copyright 2011 Google Inc. 4 * 5 * Use of this source code is governed by a BSD-style license that can be 6 * found in the LICENSE file. 7 */ 8 #include "SkRegion.h" 9 #include "SkChunkAlloc.h" 10 #include "SkTDArray.h" 11 #include "SkTemplates.h" 12 13 #if 0 14 15 struct VEdge { 16 VEdge* fPrev; 17 VEdge* fNext; 18 19 SkRegion::RunType fX; 20 SkRegion::RunType fTop; 21 SkRegion::RunType fBottom; 22 int fWinding; 23 24 void removeFromList() { 25 fPrev->fNext = fNext; 26 fNext->fPrev = fPrev; 27 } 28 29 void backwardsInsert() { 30 while (fPrev->fX > fX) { 31 VEdge* prev = fPrev; 32 VEdge* next = this; 33 34 // remove prev from the list 35 prev->fPrev->fNext = next; 36 next->fPrev = prev->fPrev; 37 38 // insert prev after next 39 prev->fNext = next->fNext; 40 next->fNext->fPrev = prev; 41 next->fNext = prev; 42 prev->fPrev = next; 43 } 44 } 45 46 static void SetFromRect(VEdge edges[], const SkIRect& r) { 47 edges[0].fX = r.fLeft; 48 edges[0].fTop = r.fTop; 49 edges[0].fBottom = r.fBottom; 50 edges[0].fWinding = -1; 51 52 edges[1].fX = r.fRight; 53 edges[1].fTop = r.fTop; 54 edges[1].fBottom = r.fBottom; 55 edges[1].fWinding = 1; 56 } 57 }; 58 59 class Accumulator { 60 public: 61 Accumulator(SkRegion::RunType top, int numRects); 62 ~Accumulator() {} 63 64 SkRegion::RunType append(SkRegion::RunType top, const VEdge* edge); 65 66 int count() const { return fTotalCount; } 67 void copyTo(SkRegion::RunType dst[]); 68 69 private: 70 struct Row { 71 SkRegion::RunType* fPtr; 72 SkRegion::RunType fBottom; 73 int fCount; // just [L R] count 74 }; 75 SkChunkAlloc fAlloc; 76 SkTDArray<Row> fRows; 77 SkRegion::RunType fTop; 78 int fTotalCount; 79 int fRectCount; 80 }; 81 82 Accumulator::Accumulator(SkRegion::RunType top, int numRects) 83 : fAlloc((1 + numRects * 2 + 1) * sizeof(int32_t)) { 84 fRectCount = numRects; 85 fTop = top; 86 fTotalCount = 2; // Top + final sentinel 87 } 88 89 //#define TRACE_ROW(code) code 90 #define TRACE_ROW(code) 91 92 SkRegion::RunType Accumulator::append(SkRegion::RunType currY, const VEdge* edge) { 93 // worst-case size 94 size_t size = fRectCount * 2 * sizeof(SkRegion::RunType); 95 SkRegion::RunType* row = (SkRegion::RunType*)fAlloc.allocThrow(size); 96 SkRegion::RunType* rowHead = row; 97 98 SkRegion::RunType nextY = SkRegion::kRunTypeSentinel; 99 int winding = edge->fWinding; 100 101 // record the L R values for this row 102 103 if (edge->fTop > currY) { 104 nextY = SkMin32(nextY, edge->fTop); 105 TRACE_ROW(SkDebugf("Y %d\n", currY);) 106 } else { 107 SkRegion::RunType currR; 108 *row++ = edge->fX; 109 TRACE_ROW(SkDebugf("Y %d [%d", currY, edge->fX);) 110 edge = edge->fNext; 111 for (;;) { 112 if (edge->fTop > currY) { 113 nextY = SkMin32(nextY, edge->fTop); 114 break; 115 } 116 117 int prevWinding = winding; 118 winding += edge->fWinding; 119 if (0 == winding) { // we finished an interval 120 currR = edge->fX; 121 } else if (0 == prevWinding && edge->fX > currR) { 122 *row++ = currR; 123 *row++ = edge->fX; 124 TRACE_ROW(SkDebugf(" %d] [%d", currR, edge->fX);) 125 } 126 127 nextY = SkMin32(nextY, edge->fBottom); 128 edge = edge->fNext; 129 } 130 SkASSERT(0 == winding); 131 *row++ = currR; 132 TRACE_ROW(SkDebugf(" %d]\n", currR);) 133 } 134 int rowCount = row - rowHead; 135 136 // now see if we have already seen this row, or if its unique 137 138 Row* r = fRows.count() ? &fRows[fRows.count() - 1] : NULL; 139 if (r && (r->fCount == rowCount) && 140 !memcmp(r->fPtr, rowHead, 141 rowCount * sizeof(SkRegion::RunType))) { 142 r->fBottom = nextY; // update bottom 143 fAlloc.unalloc(rowHead); 144 } else { 145 Row* r = fRows.append(); 146 r->fPtr = rowHead; 147 r->fBottom = nextY; 148 r->fCount = rowCount; 149 fTotalCount += 1 + rowCount + 1; 150 } 151 152 return nextY; 153 } 154 155 void Accumulator::copyTo(SkRegion::RunType dst[]) { 156 SkDEBUGCODE(SkRegion::RunType* startDst = dst;) 157 158 *dst++ = fTop; 159 160 const Row* curr = fRows.begin(); 161 const Row* stop = fRows.end(); 162 while (curr < stop) { 163 *dst++ = curr->fBottom; 164 memcpy(dst, curr->fPtr, curr->fCount * sizeof(SkRegion::RunType)); 165 dst += curr->fCount; 166 *dst++ = SkRegion::kRunTypeSentinel; 167 curr += 1; 168 } 169 *dst++ = SkRegion::kRunTypeSentinel; 170 SkASSERT(dst - startDst == fTotalCount); 171 } 172 173 /////////////////////////////////////////////////////////////////////////////// 174 175 template <typename T> int SkTCmp2Int(const T& a, const T& b) { 176 return (a < b) ? -1 : ((b < a) ? 1 : 0); 177 } 178 179 static inline int SkCmp32(int32_t a, int32_t b) { 180 return (a < b) ? -1 : ((b < a) ? 1 : 0); 181 } 182 183 static int compare_edgeptr(const void* p0, const void* p1) { 184 const VEdge* e0 = *static_cast<VEdge*const*>(p0); 185 const VEdge* e1 = *static_cast<VEdge*const*>(p1); 186 187 SkRegion::RunType v0 = e0->fTop; 188 SkRegion::RunType v1 = e1->fTop; 189 190 if (v0 == v1) { 191 v0 = e0->fX; 192 v1 = e1->fX; 193 } 194 return SkCmp32(v0, v1); 195 } 196 197 // fillout edge[] from rects[], sorted. Return the head, and set the tail 198 // 199 static VEdge* sort_edges(VEdge** edgePtr, VEdge edge[], const SkIRect rects[], 200 int rectCount, VEdge** edgeTail) { 201 int i; 202 VEdge** ptr = edgePtr; 203 for (int i = 0; i < rectCount; i++) { 204 if (!rects[i].isEmpty()) { 205 VEdge::SetFromRect(edge, rects[i]); 206 *ptr++ = edge++; 207 *ptr++ = edge++; 208 } 209 } 210 211 int edgeCount = ptr - edgePtr; 212 if (0 == edgeCount) { 213 // all the rects[] were empty 214 return NULL; 215 } 216 217 qsort(edgePtr, edgeCount, sizeof(*edgePtr), compare_edgeptr); 218 for (i = 1; i < edgeCount; i++) { 219 edgePtr[i - 1]->fNext = edgePtr[i]; 220 edgePtr[i]->fPrev = edgePtr[i - 1]; 221 } 222 *edgeTail = edgePtr[edgeCount - 1]; 223 return edgePtr[0]; 224 } 225 226 bool SkRegion::setRects(const SkIRect rects[], int rectCount) { 227 if (0 == rectCount) { 228 return this->setEmpty(); 229 } 230 if (1 == rectCount) { 231 return this->setRect(rects[0]); 232 } 233 234 int edgeCount = rectCount * 2; 235 SkAutoMalloc memory((sizeof(VEdge) + sizeof(VEdge*)) * edgeCount); 236 VEdge** edgePtr = (VEdge**)memory.get(); 237 VEdge* tail, *head = (VEdge*)(edgePtr + edgeCount); 238 head = sort_edges(edgePtr, head, rects, rectCount, &tail); 239 // check if we have no edges 240 if (NULL == head) { 241 return this->setEmpty(); 242 } 243 244 // at this stage, we don't really care about edgeCount, or if rectCount is 245 // larger that it should be (since sort_edges might have skipped some 246 // empty rects[]). rectCount now is just used for worst-case allocations 247 248 VEdge headEdge, tailEdge; 249 headEdge.fPrev = NULL; 250 headEdge.fNext = head; 251 headEdge.fTop = SK_MinS32; 252 headEdge.fX = SK_MinS32; 253 head->fPrev = &headEdge; 254 255 tailEdge.fPrev = tail; 256 tailEdge.fNext = NULL; 257 tailEdge.fTop = SK_MaxS32; 258 tail->fNext = &tailEdge; 259 260 int32_t currY = head->fTop; 261 Accumulator accum(currY, rectCount); 262 263 while (head->fNext) { 264 VEdge* edge = head; 265 // accumulate the current 266 SkRegion::RunType nextY = accum.append(currY, edge); 267 // remove the old 268 while (edge->fTop <= currY) { 269 VEdge* next = edge->fNext; 270 if (edge->fBottom <= nextY) { 271 edge->removeFromList(); 272 } 273 edge = next; 274 } 275 // insert (sorted) the new 276 while (edge->fTop == nextY) { 277 VEdge* next = edge->fNext; 278 edge->backwardsInsert(); 279 edge = next; 280 } 281 currY = nextY; 282 head = headEdge.fNext; 283 } 284 285 SkAutoTArray<RunType> runs(accum.count()); 286 accum.copyTo(runs.get()); 287 return this->setRuns(runs.get(), accum.count()); 288 } 289 290 #endif 291