140528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger#include "SkRegion.h" 240528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger#include "SkChunkAlloc.h" 340528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger#include "SkTDArray.h" 440528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger#include "SkTemplates.h" 540528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger 640528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger#if 0 740528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger 840528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenbergerstruct VEdge { 940528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger VEdge* fPrev; 1040528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger VEdge* fNext; 1140528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger 1240528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger SkRegion::RunType fX; 1340528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger SkRegion::RunType fTop; 1440528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger SkRegion::RunType fBottom; 1540528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger int fWinding; 1640528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger 1740528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger void removeFromList() { 1840528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger fPrev->fNext = fNext; 1940528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger fNext->fPrev = fPrev; 2040528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger } 2140528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger 2240528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger void backwardsInsert() { 2340528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger while (fPrev->fX > fX) { 2440528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger VEdge* prev = fPrev; 2540528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger VEdge* next = this; 2640528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger 2740528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger // remove prev from the list 2840528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger prev->fPrev->fNext = next; 2940528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger next->fPrev = prev->fPrev; 3040528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger 3140528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger // insert prev after next 3240528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger prev->fNext = next->fNext; 3340528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger next->fNext->fPrev = prev; 3440528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger next->fNext = prev; 3540528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger prev->fPrev = next; 3640528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger } 3740528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger } 3840528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger 3940528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger static void SetFromRect(VEdge edges[], const SkIRect& r) { 4040528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger edges[0].fX = r.fLeft; 4140528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger edges[0].fTop = r.fTop; 4240528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger edges[0].fBottom = r.fBottom; 4340528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger edges[0].fWinding = -1; 4440528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger 4540528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger edges[1].fX = r.fRight; 4640528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger edges[1].fTop = r.fTop; 4740528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger edges[1].fBottom = r.fBottom; 4840528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger edges[1].fWinding = 1; 4940528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger } 5040528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger}; 5140528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger 5240528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenbergerclass Accumulator { 5340528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenbergerpublic: 5440528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger Accumulator(SkRegion::RunType top, int numRects); 5540528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger ~Accumulator() {} 5640528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger 5740528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger SkRegion::RunType append(SkRegion::RunType top, const VEdge* edge); 5840528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger 5940528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger int count() const { return fTotalCount; } 6040528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger void copyTo(SkRegion::RunType dst[]); 6140528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger 6240528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenbergerprivate: 6340528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger struct Row { 6440528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger SkRegion::RunType* fPtr; 6540528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger SkRegion::RunType fBottom; 6640528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger int fCount; // just [L R] count 6740528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger }; 6840528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger SkChunkAlloc fAlloc; 6940528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger SkTDArray<Row> fRows; 7040528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger SkRegion::RunType fTop; 7140528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger int fTotalCount; 7240528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger int fRectCount; 7340528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger}; 7440528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger 7540528743dbb9ce7f39f093e0cdc47849ac8887cfDerek SollenbergerAccumulator::Accumulator(SkRegion::RunType top, int numRects) 7640528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger : fAlloc((1 + numRects * 2 + 1) * sizeof(int32_t)) { 7740528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger fRectCount = numRects; 7840528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger fTop = top; 7940528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger fTotalCount = 2; // Top + final sentinel 8040528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger} 8140528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger 8240528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger//#define TRACE_ROW(code) code 8340528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger#define TRACE_ROW(code) 8440528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger 8540528743dbb9ce7f39f093e0cdc47849ac8887cfDerek SollenbergerSkRegion::RunType Accumulator::append(SkRegion::RunType currY, const VEdge* edge) { 8640528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger // worst-case size 8740528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger size_t size = fRectCount * 2 * sizeof(SkRegion::RunType); 8840528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger SkRegion::RunType* row = (SkRegion::RunType*)fAlloc.allocThrow(size); 8940528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger SkRegion::RunType* rowHead = row; 9040528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger 9140528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger SkRegion::RunType nextY = SkRegion::kRunTypeSentinel; 9240528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger int winding = edge->fWinding; 9340528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger 9440528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger // record the L R values for this row 9540528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger 9640528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger if (edge->fTop > currY) { 9740528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger nextY = SkMin32(nextY, edge->fTop); 9840528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger TRACE_ROW(SkDebugf("Y %d\n", currY);) 9940528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger } else { 10040528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger SkRegion::RunType currR; 10140528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger *row++ = edge->fX; 10240528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger TRACE_ROW(SkDebugf("Y %d [%d", currY, edge->fX);) 10340528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger edge = edge->fNext; 10440528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger for (;;) { 10540528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger if (edge->fTop > currY) { 10640528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger nextY = SkMin32(nextY, edge->fTop); 10740528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger break; 10840528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger } 10940528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger 11040528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger int prevWinding = winding; 11140528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger winding += edge->fWinding; 11240528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger if (0 == winding) { // we finished an interval 11340528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger currR = edge->fX; 11440528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger } else if (0 == prevWinding && edge->fX > currR) { 11540528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger *row++ = currR; 11640528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger *row++ = edge->fX; 11740528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger TRACE_ROW(SkDebugf(" %d] [%d", currR, edge->fX);) 11840528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger } 11940528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger 12040528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger nextY = SkMin32(nextY, edge->fBottom); 12140528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger edge = edge->fNext; 12240528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger } 12340528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger SkASSERT(0 == winding); 12440528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger *row++ = currR; 12540528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger TRACE_ROW(SkDebugf(" %d]\n", currR);) 12640528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger } 12740528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger int rowCount = row - rowHead; 12840528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger 12940528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger // now see if we have already seen this row, or if its unique 13040528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger 13140528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger Row* r = fRows.count() ? &fRows[fRows.count() - 1] : NULL; 13240528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger if (r && (r->fCount == rowCount) && 13340528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger !memcmp(r->fPtr, rowHead, 13440528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger rowCount * sizeof(SkRegion::RunType))) { 13540528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger r->fBottom = nextY; // update bottom 13640528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger fAlloc.unalloc(rowHead); 13740528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger } else { 13840528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger Row* r = fRows.append(); 13940528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger r->fPtr = rowHead; 14040528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger r->fBottom = nextY; 14140528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger r->fCount = rowCount; 14240528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger fTotalCount += 1 + rowCount + 1; 14340528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger } 14440528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger 14540528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger return nextY; 14640528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger} 14740528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger 14840528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenbergervoid Accumulator::copyTo(SkRegion::RunType dst[]) { 14940528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger SkDEBUGCODE(SkRegion::RunType* startDst = dst;) 15040528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger 15140528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger *dst++ = fTop; 15240528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger 15340528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger const Row* curr = fRows.begin(); 15440528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger const Row* stop = fRows.end(); 15540528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger while (curr < stop) { 15640528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger *dst++ = curr->fBottom; 15740528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger memcpy(dst, curr->fPtr, curr->fCount * sizeof(SkRegion::RunType)); 15840528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger dst += curr->fCount; 15940528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger *dst++ = SkRegion::kRunTypeSentinel; 16040528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger curr += 1; 16140528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger } 16240528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger *dst++ = SkRegion::kRunTypeSentinel; 16340528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger SkASSERT(dst - startDst == fTotalCount); 16440528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger} 16540528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger 16640528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger/////////////////////////////////////////////////////////////////////////////// 16740528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger 16840528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenbergertemplate <typename T> int SkTCmp2Int(const T& a, const T& b) { 16940528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger return (a < b) ? -1 : ((b < a) ? 1 : 0); 17040528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger} 17140528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger 17240528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenbergerstatic inline int SkCmp32(int32_t a, int32_t b) { 17340528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger return (a < b) ? -1 : ((b < a) ? 1 : 0); 17440528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger} 17540528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger 17640528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenbergerstatic int compare_edgeptr(const void* p0, const void* p1) { 17740528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger const VEdge* e0 = *static_cast<VEdge*const*>(p0); 17840528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger const VEdge* e1 = *static_cast<VEdge*const*>(p1); 17940528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger 18040528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger SkRegion::RunType v0 = e0->fTop; 18140528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger SkRegion::RunType v1 = e1->fTop; 18240528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger 18340528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger if (v0 == v1) { 18440528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger v0 = e0->fX; 18540528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger v1 = e1->fX; 18640528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger } 18740528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger return SkCmp32(v0, v1); 18840528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger} 18940528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger 19040528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger// fillout edge[] from rects[], sorted. Return the head, and set the tail 19140528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger// 19240528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenbergerstatic VEdge* sort_edges(VEdge** edgePtr, VEdge edge[], const SkIRect rects[], 19340528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger int rectCount, VEdge** edgeTail) { 19440528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger int i; 19540528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger VEdge** ptr = edgePtr; 19640528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger for (int i = 0; i < rectCount; i++) { 19740528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger if (!rects[i].isEmpty()) { 19840528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger VEdge::SetFromRect(edge, rects[i]); 19940528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger *ptr++ = edge++; 20040528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger *ptr++ = edge++; 20140528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger } 20240528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger } 20340528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger 20440528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger int edgeCount = ptr - edgePtr; 20540528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger if (0 == edgeCount) { 20640528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger // all the rects[] were empty 20740528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger return NULL; 20840528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger } 20940528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger 21040528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger qsort(edgePtr, edgeCount, sizeof(*edgePtr), compare_edgeptr); 21140528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger for (i = 1; i < edgeCount; i++) { 21240528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger edgePtr[i - 1]->fNext = edgePtr[i]; 21340528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger edgePtr[i]->fPrev = edgePtr[i - 1]; 21440528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger } 21540528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger *edgeTail = edgePtr[edgeCount - 1]; 21640528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger return edgePtr[0]; 21740528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger} 21840528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger 21940528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenbergerbool SkRegion::setRects(const SkIRect rects[], int rectCount) { 22040528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger if (0 == rectCount) { 22140528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger return this->setEmpty(); 22240528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger } 22340528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger if (1 == rectCount) { 22440528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger return this->setRect(rects[0]); 22540528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger } 22640528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger 22740528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger int edgeCount = rectCount * 2; 22840528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger SkAutoMalloc memory((sizeof(VEdge) + sizeof(VEdge*)) * edgeCount); 22940528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger VEdge** edgePtr = (VEdge**)memory.get(); 23040528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger VEdge* tail, *head = (VEdge*)(edgePtr + edgeCount); 23140528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger head = sort_edges(edgePtr, head, rects, rectCount, &tail); 23240528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger // check if we have no edges 23340528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger if (NULL == head) { 23440528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger return this->setEmpty(); 23540528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger } 23640528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger 23740528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger // at this stage, we don't really care about edgeCount, or if rectCount is 23840528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger // larger that it should be (since sort_edges might have skipped some 23940528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger // empty rects[]). rectCount now is just used for worst-case allocations 24040528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger 24140528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger VEdge headEdge, tailEdge; 24240528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger headEdge.fPrev = NULL; 24340528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger headEdge.fNext = head; 24440528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger headEdge.fTop = SK_MinS32; 24540528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger headEdge.fX = SK_MinS32; 24640528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger head->fPrev = &headEdge; 24740528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger 24840528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger tailEdge.fPrev = tail; 24940528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger tailEdge.fNext = NULL; 25040528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger tailEdge.fTop = SK_MaxS32; 25140528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger tail->fNext = &tailEdge; 25240528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger 25340528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger int32_t currY = head->fTop; 25440528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger Accumulator accum(currY, rectCount); 25540528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger 25640528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger while (head->fNext) { 25740528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger VEdge* edge = head; 25840528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger // accumulate the current 25940528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger SkRegion::RunType nextY = accum.append(currY, edge); 26040528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger // remove the old 26140528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger while (edge->fTop <= currY) { 26240528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger VEdge* next = edge->fNext; 26340528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger if (edge->fBottom <= nextY) { 26440528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger edge->removeFromList(); 26540528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger } 26640528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger edge = next; 26740528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger } 26840528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger // insert (sorted) the new 26940528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger while (edge->fTop == nextY) { 27040528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger VEdge* next = edge->fNext; 27140528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger edge->backwardsInsert(); 27240528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger edge = next; 27340528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger } 27440528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger currY = nextY; 27540528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger head = headEdge.fNext; 27640528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger } 27740528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger 27840528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger SkAutoTArray<RunType> runs(accum.count()); 27940528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger accum.copyTo(runs.get()); 28040528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger return this->setRuns(runs.get(), accum.count()); 28140528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger} 28240528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger 28340528743dbb9ce7f39f093e0cdc47849ac8887cfDerek Sollenberger#endif 284