Add Sample slide for Rectanizers

R=jvanverth@google.com, bsalomon@google.com

Author: robertphillips@google.com

Review URL: https://codereview.chromium.org/303263005

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) {