michael@0: 
michael@0: /*
michael@0:  * Copyright 2011 Google Inc.
michael@0:  *
michael@0:  * Use of this source code is governed by a BSD-style license that can be
michael@0:  * found in the LICENSE file.
michael@0:  */
michael@0: #include "SkRegion.h"
michael@0: #include "SkChunkAlloc.h"
michael@0: #include "SkTDArray.h"
michael@0: #include "SkTemplates.h"
michael@0: 
michael@0: #if 0
michael@0: 
michael@0: struct VEdge {
michael@0:     VEdge*  fPrev;
michael@0:     VEdge*  fNext;
michael@0: 
michael@0:     SkRegion::RunType   fX;
michael@0:     SkRegion::RunType   fTop;
michael@0:     SkRegion::RunType   fBottom;
michael@0:     int                 fWinding;
michael@0: 
michael@0:     void removeFromList() {
michael@0:         fPrev->fNext = fNext;
michael@0:         fNext->fPrev = fPrev;
michael@0:     }
michael@0: 
michael@0:     void backwardsInsert() {
michael@0:         while (fPrev->fX > fX) {
michael@0:             VEdge* prev = fPrev;
michael@0:             VEdge* next = this;
michael@0: 
michael@0:             // remove prev from the list
michael@0:             prev->fPrev->fNext = next;
michael@0:             next->fPrev = prev->fPrev;
michael@0: 
michael@0:             // insert prev after next
michael@0:             prev->fNext = next->fNext;
michael@0:             next->fNext->fPrev = prev;
michael@0:             next->fNext = prev;
michael@0:             prev->fPrev = next;
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     static void SetFromRect(VEdge edges[], const SkIRect& r) {
michael@0:         edges[0].fX = r.fLeft;
michael@0:         edges[0].fTop = r.fTop;
michael@0:         edges[0].fBottom = r.fBottom;
michael@0:         edges[0].fWinding = -1;
michael@0: 
michael@0:         edges[1].fX = r.fRight;
michael@0:         edges[1].fTop = r.fTop;
michael@0:         edges[1].fBottom = r.fBottom;
michael@0:         edges[1].fWinding = 1;
michael@0:     }
michael@0: };
michael@0: 
michael@0: class Accumulator {
michael@0: public:
michael@0:     Accumulator(SkRegion::RunType top, int numRects);
michael@0:     ~Accumulator() {}
michael@0: 
michael@0:     SkRegion::RunType append(SkRegion::RunType top, const VEdge* edge);
michael@0: 
michael@0:     int count() const { return fTotalCount; }
michael@0:     void copyTo(SkRegion::RunType dst[]);
michael@0: 
michael@0: private:
michael@0:     struct Row {
michael@0:         SkRegion::RunType*  fPtr;
michael@0:         SkRegion::RunType   fBottom;
michael@0:         int                 fCount; // just [L R] count
michael@0:     };
michael@0:     SkChunkAlloc    fAlloc;
michael@0:     SkTDArray<Row>  fRows;
michael@0:     SkRegion::RunType fTop;
michael@0:     int             fTotalCount;
michael@0:     int             fRectCount;
michael@0: };
michael@0: 
michael@0: Accumulator::Accumulator(SkRegion::RunType top, int numRects)
michael@0:         : fAlloc((1 + numRects * 2 + 1) * sizeof(int32_t)) {
michael@0:     fRectCount = numRects;
michael@0:     fTop = top;
michael@0:     fTotalCount = 2; // Top + final sentinel
michael@0: }
michael@0: 
michael@0: //#define TRACE_ROW(code) code
michael@0: #define TRACE_ROW(code)
michael@0: 
michael@0: SkRegion::RunType Accumulator::append(SkRegion::RunType currY, const VEdge* edge) {
michael@0:     // worst-case size
michael@0:     size_t size = fRectCount * 2 * sizeof(SkRegion::RunType);
michael@0:     SkRegion::RunType* row = (SkRegion::RunType*)fAlloc.allocThrow(size);
michael@0:     SkRegion::RunType* rowHead = row;
michael@0: 
michael@0:     SkRegion::RunType nextY = SkRegion::kRunTypeSentinel;
michael@0:     int winding = edge->fWinding;
michael@0: 
michael@0:     // record the L R values for this row
michael@0: 
michael@0:     if (edge->fTop > currY) {
michael@0:         nextY = SkMin32(nextY, edge->fTop);
michael@0:         TRACE_ROW(SkDebugf("Y %d\n", currY);)
michael@0:     } else {
michael@0:         SkRegion::RunType currR;
michael@0:         *row++ = edge->fX;
michael@0:         TRACE_ROW(SkDebugf("Y %d [%d", currY, edge->fX);)
michael@0:         edge = edge->fNext;
michael@0:         for (;;) {
michael@0:             if (edge->fTop > currY) {
michael@0:                 nextY = SkMin32(nextY, edge->fTop);
michael@0:                 break;
michael@0:             }
michael@0: 
michael@0:             int prevWinding = winding;
michael@0:             winding += edge->fWinding;
michael@0:             if (0 == winding) { // we finished an interval
michael@0:                 currR = edge->fX;
michael@0:             } else if (0 == prevWinding && edge->fX > currR) {
michael@0:                 *row++ = currR;
michael@0:                 *row++ = edge->fX;
michael@0:                 TRACE_ROW(SkDebugf(" %d] [%d", currR, edge->fX);)
michael@0:             }
michael@0: 
michael@0:             nextY = SkMin32(nextY, edge->fBottom);
michael@0:             edge = edge->fNext;
michael@0:         }
michael@0:         SkASSERT(0 == winding);
michael@0:         *row++ = currR;
michael@0:         TRACE_ROW(SkDebugf(" %d]\n", currR);)
michael@0:     }
michael@0:     int rowCount = row - rowHead;
michael@0: 
michael@0:     // now see if we have already seen this row, or if its unique
michael@0: 
michael@0:     Row* r = fRows.count() ? &fRows[fRows.count() - 1] : NULL;
michael@0:     if (r && (r->fCount == rowCount) &&
michael@0:         !memcmp(r->fPtr, rowHead,
michael@0:                 rowCount * sizeof(SkRegion::RunType))) {
michael@0:             r->fBottom = nextY;    // update bottom
michael@0:             fAlloc.unalloc(rowHead);
michael@0:         } else {
michael@0:             Row* r = fRows.append();
michael@0:             r->fPtr = rowHead;
michael@0:             r->fBottom = nextY;
michael@0:             r->fCount = rowCount;
michael@0:             fTotalCount += 1 + rowCount + 1;
michael@0:         }
michael@0: 
michael@0:     return nextY;
michael@0: }
michael@0: 
michael@0: void Accumulator::copyTo(SkRegion::RunType dst[]) {
michael@0:     SkDEBUGCODE(SkRegion::RunType* startDst = dst;)
michael@0: 
michael@0:     *dst++ = fTop;
michael@0: 
michael@0:     const Row* curr = fRows.begin();
michael@0:     const Row* stop = fRows.end();
michael@0:     while (curr < stop) {
michael@0:         *dst++ = curr->fBottom;
michael@0:         memcpy(dst, curr->fPtr, curr->fCount * sizeof(SkRegion::RunType));
michael@0:         dst += curr->fCount;
michael@0:         *dst++ = SkRegion::kRunTypeSentinel;
michael@0:         curr += 1;
michael@0:     }
michael@0:     *dst++ = SkRegion::kRunTypeSentinel;
michael@0:     SkASSERT(dst - startDst == fTotalCount);
michael@0: }
michael@0: 
michael@0: ///////////////////////////////////////////////////////////////////////////////
michael@0: 
michael@0: template <typename T> int SkTCmp2Int(const T& a, const T& b) {
michael@0:     return (a < b) ? -1 : ((b < a) ? 1 : 0);
michael@0: }
michael@0: 
michael@0: static inline int SkCmp32(int32_t a, int32_t b) {
michael@0:     return (a < b) ? -1 : ((b < a) ? 1 : 0);
michael@0: }
michael@0: 
michael@0: static int compare_edgeptr(const void* p0, const void* p1) {
michael@0:     const VEdge* e0 = *static_cast<VEdge*const*>(p0);
michael@0:     const VEdge* e1 = *static_cast<VEdge*const*>(p1);
michael@0: 
michael@0:     SkRegion::RunType v0 = e0->fTop;
michael@0:     SkRegion::RunType v1 = e1->fTop;
michael@0: 
michael@0:     if (v0 == v1) {
michael@0:         v0 = e0->fX;
michael@0:         v1 = e1->fX;
michael@0:     }
michael@0:     return SkCmp32(v0, v1);
michael@0: }
michael@0: 
michael@0: // fillout edge[] from rects[], sorted. Return the head, and set the tail
michael@0: //
michael@0: static VEdge* sort_edges(VEdge** edgePtr, VEdge edge[], const SkIRect rects[],
michael@0:                          int rectCount, VEdge** edgeTail) {
michael@0:     int i;
michael@0:     VEdge** ptr = edgePtr;
michael@0:     for (int i = 0; i < rectCount; i++) {
michael@0:         if (!rects[i].isEmpty()) {
michael@0:             VEdge::SetFromRect(edge, rects[i]);
michael@0:             *ptr++ = edge++;
michael@0:             *ptr++ = edge++;
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     int edgeCount = ptr - edgePtr;
michael@0:     if (0 == edgeCount) {
michael@0:         // all the rects[] were empty
michael@0:         return NULL;
michael@0:     }
michael@0: 
michael@0:     qsort(edgePtr, edgeCount, sizeof(*edgePtr), compare_edgeptr);
michael@0:     for (i = 1; i < edgeCount; i++) {
michael@0:         edgePtr[i - 1]->fNext = edgePtr[i];
michael@0:         edgePtr[i]->fPrev = edgePtr[i - 1];
michael@0:     }
michael@0:     *edgeTail = edgePtr[edgeCount - 1];
michael@0:     return edgePtr[0];
michael@0: }
michael@0: 
michael@0: bool SkRegion::setRects(const SkIRect rects[], int rectCount) {
michael@0:     if (0 == rectCount) {
michael@0:         return this->setEmpty();
michael@0:     }
michael@0:     if (1 == rectCount) {
michael@0:         return this->setRect(rects[0]);
michael@0:     }
michael@0: 
michael@0:     int edgeCount = rectCount * 2;
michael@0:     SkAutoMalloc memory((sizeof(VEdge) + sizeof(VEdge*)) * edgeCount);
michael@0:     VEdge** edgePtr = (VEdge**)memory.get();
michael@0:     VEdge* tail, *head = (VEdge*)(edgePtr + edgeCount);
michael@0:     head = sort_edges(edgePtr, head, rects, rectCount, &tail);
michael@0:     // check if we have no edges
michael@0:     if (NULL == head) {
michael@0:         return this->setEmpty();
michael@0:     }
michael@0: 
michael@0:     // at this stage, we don't really care about edgeCount, or if rectCount is
michael@0:     // larger that it should be (since sort_edges might have skipped some
michael@0:     // empty rects[]). rectCount now is just used for worst-case allocations
michael@0: 
michael@0:     VEdge headEdge, tailEdge;
michael@0:     headEdge.fPrev = NULL;
michael@0:     headEdge.fNext = head;
michael@0:     headEdge.fTop = SK_MinS32;
michael@0:     headEdge.fX = SK_MinS32;
michael@0:     head->fPrev = &headEdge;
michael@0: 
michael@0:     tailEdge.fPrev = tail;
michael@0:     tailEdge.fNext = NULL;
michael@0:     tailEdge.fTop = SK_MaxS32;
michael@0:     tail->fNext = &tailEdge;
michael@0: 
michael@0:     int32_t currY = head->fTop;
michael@0:     Accumulator accum(currY, rectCount);
michael@0: 
michael@0:     while (head->fNext) {
michael@0:         VEdge* edge = head;
michael@0:         // accumulate the current
michael@0:         SkRegion::RunType nextY = accum.append(currY, edge);
michael@0:         // remove the old
michael@0:         while (edge->fTop <= currY) {
michael@0:             VEdge* next = edge->fNext;
michael@0:             if (edge->fBottom <= nextY) {
michael@0:                 edge->removeFromList();
michael@0:             }
michael@0:             edge = next;
michael@0:         }
michael@0:         // insert (sorted) the new
michael@0:         while (edge->fTop == nextY) {
michael@0:             VEdge* next = edge->fNext;
michael@0:             edge->backwardsInsert();
michael@0:             edge = next;
michael@0:         }
michael@0:         currY = nextY;
michael@0:         head = headEdge.fNext;
michael@0:     }
michael@0: 
michael@0:     SkAutoTArray<RunType> runs(accum.count());
michael@0:     accum.copyTo(runs.get());
michael@0:     return this->setRuns(runs.get(), accum.count());
michael@0: }
michael@0: 
michael@0: #endif