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