blob: d485ce3ff053e04a5b7ee505019307ccd182cf7a [file] [log] [blame]
/*
* 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));
}