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