diff options
author | 2010-07-13 18:35:14 +0000 | |
---|---|---|
committer | 2010-07-13 18:35:14 +0000 | |
commit | 097a3513535ad854c1b049c32c080ec875ab1411 (patch) | |
tree | bdc3288c64b8ccdf5a11574068cd0a656591b583 | |
parent | 930056ed27a2de58f315910e63db1ddca0bac63f (diff) |
add SkRegion::setRects(), and its unit tests
git-svn-id: http://skia.googlecode.com/svn/trunk@588 2bbb7eff-a529-9590-31e7-b0007b416f81
-rw-r--r-- | include/core/SkRect.h | 30 | ||||
-rw-r--r-- | include/core/SkRegion.h | 7 | ||||
-rw-r--r-- | src/core/SkRegion.cpp | 230 | ||||
-rw-r--r-- | tests/RegionTest.cpp | 63 | ||||
-rw-r--r-- | tests/tests_files.mk | 1 |
5 files changed, 330 insertions, 1 deletions
diff --git a/include/core/SkRect.h b/include/core/SkRect.h index fbd9f7f502..00e0aaf576 100644 --- a/include/core/SkRect.h +++ b/include/core/SkRect.h @@ -27,6 +27,36 @@ struct SkIRect { int32_t fLeft, fTop, fRight, fBottom; + static SkIRect MakeEmpty() { + SkIRect r; + r.setEmpty(); + return r; + } + + static SkIRect MakeWH(int32_t w, int32_t h) { + SkIRect r; + r.set(0, 0, w, h); + return r; + } + + static SkIRect MakeSize(const SkISize& size) { + SkIRect r; + r.set(0, 0, size.width(), size.height()); + return r; + } + + static SkIRect MakeLTRB(int32_t l, int32_t t, int32_t r, int32_t b) { + SkIRect rect; + rect.set(l, t, r, b); + return rect; + } + + static SkIRect MakeXYWH(int32_t x, int32_t y, int32_t w, int32_t h) { + SkIRect r; + r.set(x, y, x + w, y + h); + return r; + } + /** Return true if the rectangle's width or height are <= 0 */ bool isEmpty() const { return fLeft >= fRight || fTop >= fBottom; } diff --git a/include/core/SkRegion.h b/include/core/SkRegion.h index 8b15a893c8..103e2cc864 100644 --- a/include/core/SkRegion.h +++ b/include/core/SkRegion.h @@ -98,6 +98,13 @@ public: */ bool setRect(int32_t left, int32_t top, int32_t right, int32_t bottom); + /** Set this region to the union of an array of rects. This is generally + faster than calling region.op(rect, kUnion_Op) in a loop. If count is + 0, then this region is set to the empty region. + @return true if the resulting region is non-empty + */ + bool setRects(const SkIRect rects[], int count); + /** Set this region to the specified region, and return true if it is non-empty. */ bool setRegion(const SkRegion&); diff --git a/src/core/SkRegion.cpp b/src/core/SkRegion.cpp index a5a1555505..376f79c255 100644 --- a/src/core/SkRegion.cpp +++ b/src/core/SkRegion.cpp @@ -553,7 +553,235 @@ void SkRegion::translate(int dx, int dy, SkRegion* dst) const SkDEBUGCODE(this->validate();) } -///////////////////////////////////////////////////////////////////////////////////// +/////////////////////////////////////////////////////////////////////////////// + +#include "SkChunkAlloc.h" +#include "SkTDArray.h" +#include "SkTSearch.h" +#include "SkTemplates.h" + +template <typename T> int SkTCmp2Int(const T& a, const T& b) { + return (a < b) ? -1 : ((b < a) ? 1 : 0); +} + +struct VEdge { + int32_t fX; + int fDir; // 1, -1 +}; + +static VEdge* append_rect(VEdge* edge, const SkIRect& r) { + edge[0].fX = r.fLeft; + edge[0].fDir = -1; + edge[1].fX = r.fRight; + edge[1].fDir = 1; + return edge + 2; +} + +class Accumulator { +public: + Accumulator(SkRegion::RunType top, int numRects); + ~Accumulator() {} + + void append(int32_t bottom, const VEdge edge[], int count); + + int count() const { return fTotalCount; } + void copyTo(SkRegion::RunType dst[]); + +private: + struct Row { + SkRegion::RunType* fPtr; + SkRegion::RunType fBottom; + int fCount; // just [L R] count + }; + SkChunkAlloc fAlloc; + SkTDArray<Row> fRows; + SkRegion::RunType fTop; + int fTotalCount; +}; + +Accumulator::Accumulator(SkRegion::RunType top, int numRects) + : fAlloc((1 + numRects * 2 + 1) * sizeof(int32_t)) { + fTop = top; + fTotalCount = 2; // Top + final sentinel +} + +static int union_edges(SkRegion::RunType dst[], const VEdge edge[], int count) { + if (0 == count) { + return 0; + } + + SkRegion::RunType* startDst = dst; + const VEdge* stop = edge + count; + + SkRegion::RunType currR; + int dir = edge->fDir; + + *dst++ = edge->fX; // initial L + while (++edge < stop) { + int prevDir = dir; + dir += edge->fDir; + if (0 == dir) { // we finished an interval + currR = edge->fX; + } else if (0 == prevDir && edge->fX > currR) { + *dst++ = currR; + *dst++ = edge->fX; + } + } + SkASSERT(0 == dir); + *dst++ = currR; + SkDEBUGCODE(int resultCount = dst - startDst;) + SkASSERT(resultCount <= count && (resultCount & 1) == 0); + return dst - startDst; +} + +void Accumulator::append(int32_t bottom, const VEdge edge[], int count) { + SkASSERT((count & 1) == 0); + + size_t size = count * sizeof(SkRegion::RunType); + int32_t* row = (SkRegion::RunType*)fAlloc.allocThrow(size); + int rowCount = union_edges(row, edge, count); + + Row* r = fRows.count() ? &fRows[fRows.count() - 1] : NULL; + if (r && (r->fCount == rowCount) && + !memcmp(r->fPtr, row, + rowCount * sizeof(SkRegion::RunType))) { + r->fBottom = bottom; // update bottom + fAlloc.unalloc(row); + } else { + Row* r = fRows.append(); + r->fPtr = row; + r->fBottom = bottom; + r->fCount = rowCount; + fTotalCount += 1 + rowCount + 1; + } +} + +void Accumulator::copyTo(SkRegion::RunType dst[]) { + SkDEBUGCODE(SkRegion::RunType* startDst = dst;) + + *dst++ = fTop; + + const Row* curr = fRows.begin(); + const Row* stop = fRows.end(); + while (curr < stop) { + *dst++ = curr->fBottom; + memcpy(dst, curr->fPtr, curr->fCount * sizeof(SkRegion::RunType)); + dst += curr->fCount; + *dst++ = SkRegion::kRunTypeSentinel; + curr += 1; + } + *dst++ = SkRegion::kRunTypeSentinel; + SkASSERT(dst - startDst == fTotalCount); +} + +///////////// + +struct RNode { + RNode* fNext; + const SkIRect* fRect; +}; + +static int compare_rnode_top(const void* e0, const void* e1) { + const RNode* r0 = static_cast<const RNode*>(e0); + const RNode* r1 = static_cast<const RNode*>(e1); + return SkTCmp2Int<int32_t>(r0->fRect->fTop, r1->fRect->fTop); +} + +static int compare_vedge(const void* e0, const void* e1) { + const VEdge* v0 = static_cast<const VEdge*>(e0); + const VEdge* v1 = static_cast<const VEdge*>(e1); + return SkTCmp2Int<int32_t>(v0->fX, v1->fX); +} + +bool SkRegion::setRects(const SkIRect rects[], int count) { + if (0 == count) { + return this->setEmpty(); + } + if (1 == count) { + return this->setRect(rects[0]); + } + + int i; + SkIRect sentinelRect = SkIRect::MakeLTRB(kRunTypeSentinel, kRunTypeSentinel, + kRunTypeSentinel, kRunTypeSentinel); + + SkAutoTArray<RNode> nodeStorage(count + 1); + RNode* nodes = nodeStorage.get(); + for (i = 0; i < count; i++) { + if (!rects[i].isEmpty()) { + nodes->fRect = &rects[i]; + nodes += 1; + } + } + // recompute count, since we may have skipped empty rects + count = nodes - nodeStorage.get(); + nodes = nodeStorage.get(); + // we are now done with the original rects[] parameter + SkDEBUGCODE(rects = NULL;) + + SkQSort(nodes, count, sizeof(nodes[0]), compare_rnode_top); + for (i = 0; i < count; i++) { + nodes[i].fNext = &nodes[i + 1]; + } + nodes[count].fNext = NULL; + nodes[count].fRect = &sentinelRect; + + SkAutoTArray<VEdge> edgeStorage(count * 2); + + VEdge* edges = edgeStorage.get(); + RNode* nodeHead = nodeStorage.get(); + + int32_t currY = nodeHead->fRect->fTop; + Accumulator accum(currY, count); + + while (nodeHead->fNext) { + RNode* node = nodeHead; + + int32_t nextY = kRunTypeSentinel; + const SkIRect* r = node->fRect; + for (;;) { + if (r->fTop > currY) { + nextY = SkMin32(nextY, r->fTop); + break; + } + edges = append_rect(edges, *r); + nextY = SkMin32(nextY, r->fBottom); + node = node->fNext; + r = node->fRect; + } + int edgeCount = edges - edgeStorage.get(); + edges = edgeStorage.get(); + SkASSERT(edgeCount <= count * 2); + + SkQSort(edges, edgeCount, sizeof(edges[0]), compare_vedge); + accum.append(nextY, edges, edgeCount); + + RNode* prev = NULL; + node = nodeHead; + while (node->fRect->fTop <= currY) { + RNode* next = node->fNext; + if (node->fRect->fBottom <= nextY) { + // drop this rect from our linklist + SkASSERT(node->fRect->fBottom == nextY); + if (prev) { + prev->fNext = next; + } else { + nodeHead = next; + } + } else { + prev = node; + } + node = next; + } + currY = nextY; + } + + SkAutoTArray<RunType> runs(accum.count()); + accum.copyTo(runs.get()); + return this->setRuns(runs.get(), accum.count()); +} + +/////////////////////////////////////////////////////////////////////////////// #if defined _WIN32 && _MSC_VER >= 1300 // disable warning : local variable used without having been initialized #pragma warning ( push ) diff --git a/tests/RegionTest.cpp b/tests/RegionTest.cpp new file mode 100644 index 0000000000..ee34d8ba83 --- /dev/null +++ b/tests/RegionTest.cpp @@ -0,0 +1,63 @@ +#include "Test.h" +#include "SkRegion.h" +#include "SkRandom.h" + +static void rand_rect(SkIRect* rect, SkRandom& rand) { + int bits = 6; + int shift = 32 - bits; + rect->set(rand.nextU() >> shift, rand.nextU() >> shift, + rand.nextU() >> shift, rand.nextU() >> shift); + rect->sort(); +} + +static bool test_rects(const SkIRect rect[], int count) { + SkRegion rgn0, rgn1; + + for (int i = 0; i < count; i++) { + rgn0.op(rect[i], SkRegion::kUnion_Op); + } + rgn1.setRects(rect, count); + + if (rgn0 != rgn1) { + SkDebugf("\n"); + for (int i = 0; i < count; i++) { + SkDebugf(" { %d, %d, %d, %d },\n", + rect[i].fLeft, rect[i].fTop, + rect[i].fRight, rect[i].fBottom); + } + SkDebugf("\n"); + return false; + } + return true; +} + +static void TestRegion(skiatest::Reporter* reporter) { + const SkIRect r2[] = { + { 0, 0, 1, 1 }, + { 2, 2, 3, 3 }, + }; + REPORTER_ASSERT(reporter, test_rects(r2, SK_ARRAY_COUNT(r2))); + + const SkIRect rects[] = { + { 0, 0, 1, 2 }, + { 2, 1, 3, 3 }, + { 4, 0, 5, 1 }, + { 6, 0, 7, 4 }, + }; + REPORTER_ASSERT(reporter, test_rects(rects, SK_ARRAY_COUNT(rects))); + + SkRandom rand; + for (int i = 0; i < 1000; i++) { + SkRegion rgn0, rgn1; + + const int N = 8; + SkIRect rect[N]; + for (int j = 0; j < N; j++) { + rand_rect(&rect[j], rand); + } + REPORTER_ASSERT(reporter, test_rects(rect, N)); + } +} + +#include "TestClassDef.h" +DEFINE_TESTCLASS("Region", RegionTestClass, TestRegion) diff --git a/tests/tests_files.mk b/tests/tests_files.mk index 1850494b2f..98d703e360 100644 --- a/tests/tests_files.mk +++ b/tests/tests_files.mk @@ -12,6 +12,7 @@ SOURCE := \ PaintTest.cpp \ ParsePathTest.cpp \ PathTest.cpp \ + RegionTest.cpp \ ClipCubicTest.cpp \ SrcOverTest.cpp \ StreamTest.cpp \ |