Add new skyline Rectanizer

src/gpu/GrRectanizer_skyline.cpp

Index: src/gpu/GrRectanizer_skyline.cpp
diff --git a/src/gpu/GrRectanizer_skyline.cpp b/src/gpu/GrRectanizer_skyline.cpp
new file mode 100755
index 0000000000000000000000000000000000000000..96de2d05fdf30017d63def63ef455296f3b57e7e
--- /dev/null
+++ b/src/gpu/GrRectanizer_skyline.cpp
@@ -0,0 +1,166 @@
+
+/*
+ * Copyright 2013 Google Inc.
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+
+#include "GrRectanizer.h"
+#include "SkTDArray.h"
+
+// Pack rectangles and track the current silhouette
+// Based in part on Jukka Jylänki's work at http://clb.demon.fi
+
+class GrRectanizerSkyline : public GrRectanizer {
+public:
+    GrRectanizerSkyline(int w, int h) : GrRectanizer(w, h) {
+        reset();
+    }
+
+    virtual ~GrRectanizerSkyline() {
+    }
+
+    virtual void reset() {
+        fAreaSoFar = 0;
+        fSkyline.reset();
+        SkylineSegment* seg = fSkyline.append(1);
+        seg->fX = 0;
+        seg->fY = 0;
+        seg->fWidth = width();
+    }
+
+    virtual bool addRect(int w, int h, GrIPoint16* loc);
+
+    virtual float percentFull() const {
+        return fAreaSoFar / ((float)this->width() * this->height());
+    }
+
+    virtual int stripToPurge(int height) const { return -1; }
+    virtual void purgeStripAtY(int yCoord) { }
+
+    ///////////////////////////////////////////////////////////////////////////
+
+    struct SkylineSegment {
+        int  fX;
+        int  fY;
+        int  fWidth;
+    };
+
+    SkTDArray<SkylineSegment> fSkyline;
+
+    int32_t fAreaSoFar;
+
+    bool rectangleFits(int skylineIndex, int width, int height, int* y) const;
+    void addSkylineLevel(int skylineIndex, int x, int y, int width, int height);
+};
+
+bool GrRectanizerSkyline::addRect(int width, int height, GrIPoint16* loc) {
+    if ((unsigned)width > (unsigned)this->width() ||
+        (unsigned)height > (unsigned)this->height()) {
+        return false;
+    }
+
+    // find position for new rectangle
+    int bestWidth = this->width() + 1;
+    int bestX;
+    int bestY = this->height() + 1;
+    int bestIndex = -1;
+    for (int i = 0; i < fSkyline.count(); ++i) {
+        int y;
+        if (this->rectangleFits(i, width, height, &y)) {
+            // minimize y position first, then width of skyline
+            if (y < bestY || (y == bestY && fSkyline[i].fWidth < bestWidth)) {
+                bestIndex = i;
+                bestWidth = fSkyline[i].fWidth;
+                bestX = fSkyline[i].fX;
+                bestY = y;
+            }
+        }
+    }
+
+    // add rectangle to skyline
+    if (-1 != bestIndex) {
+        this->addSkylineLevel(bestIndex, bestX, bestY, width, height);
+        loc->fX = bestX;
+        loc->fY = bestY;
+
+        fAreaSoFar += width*height;
+        return true;
+    }
+
+    loc->fX = 0;
+    loc->fY = 0;
+    return false;
+}
+
+bool GrRectanizerSkyline::rectangleFits(int skylineIndex, int width, int height, int* ypos) const {
+    int x = fSkyline[skylineIndex].fX;
+    if (x + width > this->width()) {
+        return false;
+    }
+
+    int widthLeft = width;
+    int i = skylineIndex;
+    int y = fSkyline[skylineIndex].fY;
+    while (widthLeft > 0) {
+	y = SkMax32(y, fSkyline[i].fY);
+        if (y + height > this->height()) {
+            return false;
+        }
+	widthLeft -= fSkyline[i].fWidth;
+	++i;
+	SkASSERT(i < fSkyline.count() || widthLeft <= 0);
+    }
+
+    *ypos = y;
+    return true;
+}
+
+void GrRectanizerSkyline::addSkylineLevel(int skylineIndex, int x, int y, int width, int height) {
+    SkylineSegment newSegment;
+    newSegment.fX = x;
+    newSegment.fY = y + height;
+    newSegment.fWidth = width;
+    fSkyline.insert(skylineIndex, 1, &newSegment);
+
+    SkASSERT(newSegment.fX + newSegment.fWidth <= this->width());
+    SkASSERT(newSegment.fY <= this->height());
+
+    // delete width of this skyline segment from following ones
+    for (int i = skylineIndex+1; i < fSkyline.count(); ++i) {
+        SkASSERT(fSkyline[i-1].fX <= fSkyline[i].fX);
+
+        if (fSkyline[i].fX < fSkyline[i-1].fX + fSkyline[i-1].fWidth) {
+            int shrink = fSkyline[i-1].fX + fSkyline[i-1].fWidth - fSkyline[i].fX;
+
+            fSkyline[i].fX += shrink;
+            fSkyline[i].fWidth -= shrink;
+
+            if (fSkyline[i].fWidth <= 0) {
+                fSkyline.remove(i);
+                --i;
+            }
+            else
+                break;
+        }
+        else
+            break;
+    }
+
+    // merge fSkylines
+    for (int i = 0; i < fSkyline.count()-1; ++i) {
+        if (fSkyline[i].fY == fSkyline[i+1].fY) {
+            fSkyline[i].fWidth += fSkyline[i+1].fWidth;
+            fSkyline.remove(i+1);
+            --i;
+        }
+    }
+}
+
+///////////////////////////////////////////////////////////////////////////////
+
+GrRectanizer* GrRectanizer::Factory(int width, int height) {
+    return SkNEW_ARGS(GrRectanizerSkyline, (width, height));
+}
+