src/gpu/GrRectanizer_skyline.cpp

/*
 * 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) : INHERITED(w, h) {
        this->reset();
    }

    virtual ~GrRectanizerSkyline() {
    }

    virtual void reset() SK_OVERRIDE {
        fAreaSoFar = 0;
        fSkyline.reset();
        SkylineSegment* seg = fSkyline.append(1);
        seg->fX = 0;
        seg->fY = 0;
        seg->fWidth = this->width();
    }

    virtual bool addRect(int w, int h, GrIPoint16* loc) SK_OVERRIDE;

    virtual float percentFull() const SK_OVERRIDE {
        return fAreaSoFar / ((float)this->width() * this->height());
    }

    virtual int stripToPurge(int height) const SK_OVERRIDE { return -1; }
    virtual void purgeStripAtY(int yCoord) SK_OVERRIDE { }

    ///////////////////////////////////////////////////////////////////////////

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

private:
    typedef GrRectanizer INHERITED;
};

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));
}