diff options
-rw-r--r-- | gyp/SampleApp.gyp | 1 | ||||
-rw-r--r-- | include/gpu/GrPoint.h | 14 | ||||
-rw-r--r-- | samplecode/SampleRectanizer.cpp | 198 | ||||
-rw-r--r-- | src/gpu/GrRectanizer.h | 2 | ||||
-rw-r--r-- | src/gpu/GrRectanizer_pow2.cpp | 8 | ||||
-rw-r--r-- | src/gpu/GrRectanizer_pow2.h | 14 | ||||
-rw-r--r-- | src/gpu/GrRectanizer_skyline.h | 12 |
7 files changed, 229 insertions, 20 deletions
diff --git a/gyp/SampleApp.gyp b/gyp/SampleApp.gyp index 90a51aba10..e0579ac596 100644 --- a/gyp/SampleApp.gyp +++ b/gyp/SampleApp.gyp @@ -90,6 +90,7 @@ '../samplecode/SamplePictFile.cpp', '../samplecode/SamplePoints.cpp', '../samplecode/SamplePolyToPoly.cpp', + '../samplecode/SampleRectanizer.cpp', '../samplecode/SampleRegion.cpp', '../samplecode/SampleRepeatTile.cpp', '../samplecode/SampleRotateCircles.cpp', diff --git a/include/gpu/GrPoint.h b/include/gpu/GrPoint.h index 7be5736f56..16738f5243 100644 --- a/include/gpu/GrPoint.h +++ b/include/gpu/GrPoint.h @@ -15,14 +15,18 @@ #include "SkScalar.h" #include "SkPoint.h" -#if 0 -#define GrPoint SkPoint -#define GrVec SkVector -#endif - struct GrIPoint16 { int16_t fX, fY; + static GrIPoint16 Make(intptr_t x, intptr_t y) { + GrIPoint16 pt; + pt.set(x, y); + return pt; + } + + int16_t x() const { return fX; } + int16_t y() const { return fY; } + void set(intptr_t x, intptr_t y) { fX = SkToS16(x); fY = SkToS16(y); diff --git a/samplecode/SampleRectanizer.cpp b/samplecode/SampleRectanizer.cpp new file mode 100644 index 0000000000..fcb1cdb18e --- /dev/null +++ b/samplecode/SampleRectanizer.cpp @@ -0,0 +1,198 @@ +/* + * Copyright 2014 Google Inc. + * + * Use of this source code is governed by a BSD-style license that can be + * found in the LICENSE file. + */ + +#include "gm.h" +#include "SampleCode.h" +#include "SkRandom.h" +#include "SkUtils.h" +#if SK_SUPPORT_GPU +#include "GrRectanizer_pow2.h" +#include "GrRectanizer_skyline.h" + + +// This slide visualizes the various GrRectanizer-derived classes behavior +// for various input sets +// 'j' will cycle through the various rectanizers +// Pow2 -> GrRectanizerPow2 +// Skyline -> GrRectanizerSkyline +// 'h' will cycle through the various rect sets +// Rand -> random rects from 2-256 +// Pow2Rand -> random power of 2 sized rects from 2-256 +// SmallPow2 -> 128x128 rects +class RectanizerView : public SampleView { +public: + RectanizerView() + : fCurRandRect(0) { + for (int i = 0; i < 3; ++i) { + fRects[i].setReserve(kNumRandRects); + } + fRectLocations.setReserve(kNumRandRects); + + SkRandom random; + for (int i = 0; i < kNumRandRects; ++i) { + *fRects[0].append() = SkISize::Make(random.nextRangeU(kMinRectSize, kMaxRectSize), + random.nextRangeU(kMinRectSize, kMaxRectSize)); + *fRects[1].append() = SkISize::Make( + GrNextPow2(random.nextRangeU(kMinRectSize, kMaxRectSize)), + GrNextPow2(random.nextRangeU(kMinRectSize, kMaxRectSize))); + *fRects[2].append() = SkISize::Make(128, 128); + *fRectLocations.append() = GrIPoint16::Make(0, 0); + } + + fCurRects = &fRects[0]; + + fRectanizers[0] = new GrRectanizerPow2(kWidth, kHeight); + fRectanizers[1] = new GrRectanizerSkyline(kWidth, kHeight); + fCurRectanizer = fRectanizers[0]; + } + +protected: + virtual bool onQuery(SkEvent* evt) SK_OVERRIDE { + if (SampleCode::TitleQ(*evt)) { + SampleCode::TitleR(evt, "Rectanizer"); + return true; + } + SkUnichar uni; + if (SampleCode::CharQ(*evt, &uni)) { + char utf8[kMaxBytesInUTF8Sequence]; + size_t size = SkUTF8_FromUnichar(uni, utf8); + // Only consider events for single char keys + if (1 == size) { + switch (utf8[0]) { + case kCycleRectanizerKey: + this->cycleRectanizer(); + return true; + case kCycleRectsKey: + this->cycleRects(); + return true; + default: + break; + } + } + } + return this->INHERITED::onQuery(evt); + } + + virtual void onDrawContent(SkCanvas* canvas) SK_OVERRIDE { + if (fCurRandRect < kNumRandRects) { + if (fCurRectanizer->addRect((*fCurRects)[fCurRandRect].fWidth, + (*fCurRects)[fCurRandRect].fHeight, + &fRectLocations[fCurRandRect])) { + ++fCurRandRect; + } + } + + SkPaint blackBigFont; + blackBigFont.setTextSize(20); + SkPaint blackStroke; + blackStroke.setStyle(SkPaint::kStroke_Style); + SkPaint redFill; + redFill.setColor(SK_ColorRED); + + SkRect r = SkRect::MakeWH(SkIntToScalar(kWidth), SkIntToScalar(kHeight)); + + canvas->clear(SK_ColorWHITE); + canvas->drawRect(r, blackStroke); + + long totArea = 0; + for (int i = 0; i < fCurRandRect; ++i) { + r = SkRect::MakeXYWH(SkIntToScalar(fRectLocations[i].fX), + SkIntToScalar(fRectLocations[i].fY), + SkIntToScalar((*fCurRects)[i].fWidth), + SkIntToScalar((*fCurRects)[i].fHeight)); + canvas->drawRect(r, redFill); + canvas->drawRect(r, blackStroke); + totArea += (*fCurRects)[i].fWidth * (*fCurRects)[i].fHeight; + } + + SkString str; + + str.printf("%s-%s: tot Area: %ld %%full: %.2f (%.2f) numTextures: %d/%d", + this->getRectanizerName(), + this->getRectsName(), + totArea, + 100.0f * fCurRectanizer->percentFull(), + 100.0f * totArea / ((float)kWidth*kHeight), + fCurRandRect, + kNumRandRects); + canvas->drawText(str.c_str(), str.size(), 50, kHeight + 50, blackBigFont); + + str.printf("Press \'j\' to toggle rectanizer"); + canvas->drawText(str.c_str(), str.size(), 50, kHeight + 100, blackBigFont); + + str.printf("Press \'h\' to toggle rects"); + canvas->drawText(str.c_str(), str.size(), 50, kHeight + 150, blackBigFont); + + this->inval(NULL); + } + +private: + static const int kWidth = 1024; + static const int kHeight = 1024; + static const int kNumRandRects = 200; + static const char kCycleRectanizerKey = 'j'; + static const char kCycleRectsKey = 'h'; + static const int kMinRectSize = 2; + static const int kMaxRectSize = 256; + + int fCurRandRect; + SkTDArray<SkISize> fRects[3]; + SkTDArray<SkISize>* fCurRects; + SkTDArray<GrIPoint16> fRectLocations; + GrRectanizer* fRectanizers[2]; + GrRectanizer* fCurRectanizer; + + const char* getRectanizerName() const { + if (fCurRectanizer == fRectanizers[0]) { + return "Pow2"; + } else { + return "Skyline"; + } + } + + void cycleRectanizer() { + if (fCurRectanizer == fRectanizers[0]) { + fCurRectanizer = fRectanizers[1]; + } else { + fCurRectanizer = fRectanizers[0]; + } + + fCurRectanizer->reset(); + fCurRandRect = 0; + } + + const char* getRectsName() const { + if (fCurRects == &fRects[0]) { + return "Rand"; + } else if (fCurRects == &fRects[1]) { + return "Pow2Rand"; + } else { + return "SmallPow2"; + } + } + + void cycleRects() { + if (fCurRects == &fRects[0]) { + fCurRects = &fRects[1]; + } else if (fCurRects == &fRects[1]) { + fCurRects = &fRects[2]; + } else { + fCurRects = &fRects[0]; + } + + fCurRectanizer->reset(); + fCurRandRect = 0; + } + + typedef SampleView INHERITED; +}; + +////////////////////////////////////////////////////////////////////////////// +static SkView* MyFactory() { return new RectanizerView; } +static SkViewRegister reg(MyFactory); + +#endif diff --git a/src/gpu/GrRectanizer.h b/src/gpu/GrRectanizer.h index 2c290e9153..0f9d8fdfb6 100644 --- a/src/gpu/GrRectanizer.h +++ b/src/gpu/GrRectanizer.h @@ -24,6 +24,8 @@ public: int width() const { return fWidth; } int height() const { return fHeight; } + // Attempt to add a rect. Return true on success; false on failure. If + // successful the position in the atlas is returned in 'loc'. virtual bool addRect(int width, int height, GrIPoint16* loc) = 0; virtual float percentFull() const = 0; diff --git a/src/gpu/GrRectanizer_pow2.cpp b/src/gpu/GrRectanizer_pow2.cpp index d92e80c2d5..5da7e04528 100644 --- a/src/gpu/GrRectanizer_pow2.cpp +++ b/src/gpu/GrRectanizer_pow2.cpp @@ -7,7 +7,6 @@ */ #include "GrRectanizer_pow2.h" -#include "GrTBSearch.h" bool GrRectanizerPow2::addRect(int width, int height, GrIPoint16* loc) { if ((unsigned)width > (unsigned)this->width() || @@ -15,13 +14,8 @@ bool GrRectanizerPow2::addRect(int width, int height, GrIPoint16* loc) { return false; } - int32_t area = width * height; + int32_t area = width * height; // computed here since height will be modified - /* - We use bsearch, but there may be more than one row with the same height, - so we actually search for height-1, which can only be a pow2 itself if - height == 2. Thus we set a minimum height. - */ height = GrNextPow2(height); if (height < kMIN_HEIGHT_POW2) { height = kMIN_HEIGHT_POW2; diff --git a/src/gpu/GrRectanizer_pow2.h b/src/gpu/GrRectanizer_pow2.h index c2e45655f1..e9d9d02b0a 100644 --- a/src/gpu/GrRectanizer_pow2.h +++ b/src/gpu/GrRectanizer_pow2.h @@ -10,6 +10,11 @@ #include "GrRectanizer.h" +// This Rectanizer quantizes the incoming rects to powers of 2. Each power +// of two can have, at most, one active row/shelf. Once a row/shelf for +// a particular power of two gets full its fRows entry is recycled to point +// to a new row. +// The skyline algorithm almost always provides a better packing. class GrRectanizerPow2 : public GrRectanizer { public: GrRectanizerPow2(int w, int h) : INHERITED(w, h) { @@ -32,9 +37,12 @@ public: private: static const int kMIN_HEIGHT_POW2 = 2; + static const int kMaxExponent = 16; struct Row { GrIPoint16 fLoc; + // fRowHeight is actually known by this struct's position in fRows + // but it is used to signal if there exists an open row of this height int fRowHeight; bool canAddWidth(int width, int containerWidth) const { @@ -42,14 +50,16 @@ private: } }; - Row fRows[16]; + Row fRows[kMaxExponent]; // 0-th entry will be unused int fNextStripY; int32_t fAreaSoFar; static int HeightToRowIndex(int height) { SkASSERT(height >= kMIN_HEIGHT_POW2); - return 32 - SkCLZ(height - 1); + int index = 32 - SkCLZ(height - 1); + SkASSERT(index < kMaxExponent); + return index; } bool canAddStrip(int height) const { diff --git a/src/gpu/GrRectanizer_skyline.h b/src/gpu/GrRectanizer_skyline.h index d2dfe577f1..01c433db15 100644 --- a/src/gpu/GrRectanizer_skyline.h +++ b/src/gpu/GrRectanizer_skyline.h @@ -1,9 +1,9 @@ /* -* Copyright 2014 Google Inc. -* -* Use of this source code is governed by a BSD-style license that can be -* found in the LICENSE file. -*/ + * Copyright 2014 Google Inc. + * + * Use of this source code is governed by a BSD-style license that can be + * found in the LICENSE file. + */ #ifndef GrRectanizer_skyline_DEFINED #define GrRectanizer_skyline_DEFINED @@ -12,7 +12,7 @@ #include "SkTDArray.h" // Pack rectangles and track the current silhouette -// Based in part on Jukka Jylänki's work at http://clb.demon.fi +// Based, in part, on Jukka Jylanki's work at http://clb.demon.fi class GrRectanizerSkyline : public GrRectanizer { public: GrRectanizerSkyline(int w, int h) : INHERITED(w, h) { |