src/third_party/skia/src/gpu/GrRectanizer_skyline.cpp

   1
   2 /*
   3  * Copyright 2013 Google Inc.
   4  *
   5  * Use of this source code is governed by a BSD-style license that can be
   6  * found in the LICENSE file.
   7  */
   8
   9 #include "GrRectanizer.h"
  10 #include "SkTDArray.h"
  11
  12 // Pack rectangles and track the current silhouette
  13 // Based in part on Jukka Jylänki's work at http://clb.demon.fi
  14
  15 class GrRectanizerSkyline : public GrRectanizer {
  16 public:
  17     GrRectanizerSkyline(int w, int h) : INHERITED(w, h) {
  18         this->reset();
  19     }
  20
  21     virtual ~GrRectanizerSkyline() {
  22     }
  23
  24     virtual void reset() SK_OVERRIDE {
  25         fAreaSoFar = 0;
  26         fSkyline.reset();
  27         SkylineSegment* seg = fSkyline.append(1);
  28         seg->fX = 0;
  29         seg->fY = 0;
  30         seg->fWidth = this->width();
  31     }
  32
  33     virtual bool addRect(int w, int h, GrIPoint16* loc) SK_OVERRIDE;
  34
  35     virtual float percentFull() const SK_OVERRIDE {
  36         return fAreaSoFar / ((float)this->width() * this->height());
  37     }
  38
  39     virtual int stripToPurge(int height) const SK_OVERRIDE { return -1; }
  40     virtual void purgeStripAtY(int yCoord) SK_OVERRIDE { }
  41
  42     ///////////////////////////////////////////////////////////////////////////
  43
  44     struct SkylineSegment {
  45         int  fX;
  46         int  fY;
  47         int  fWidth;
  48     };
  49
  50     SkTDArray<SkylineSegment> fSkyline;
  51
  52     int32_t fAreaSoFar;
  53
  54     bool rectangleFits(int skylineIndex, int width, int height, int* y) const;
  55     void addSkylineLevel(int skylineIndex, int x, int y, int width, int height);
  56
  57 private:
  58     typedef GrRectanizer INHERITED;
  59 };
  60
  61 bool GrRectanizerSkyline::addRect(int width, int height, GrIPoint16* loc) {
  62     if ((unsigned)width > (unsigned)this->width() ||
  63         (unsigned)height > (unsigned)this->height()) {
  64         return false;
  65     }
  66
  67     // find position for new rectangle
  68     int bestWidth = this->width() + 1;
  69     int bestX;
  70     int bestY = this->height() + 1;
  71     int bestIndex = -1;
  72     for (int i = 0; i < fSkyline.count(); ++i) {
  73         int y;
  74         if (this->rectangleFits(i, width, height, &y)) {
  75             // minimize y position first, then width of skyline
  76             if (y < bestY || (y == bestY && fSkyline[i].fWidth < bestWidth)) {
  77                 bestIndex = i;
  78                 bestWidth = fSkyline[i].fWidth;
  79                 bestX = fSkyline[i].fX;
  80                 bestY = y;
  81             }
  82         }
  83     }
  84
  85     // add rectangle to skyline
  86     if (-1 != bestIndex) {
  87         this->addSkylineLevel(bestIndex, bestX, bestY, width, height);
  88         loc->fX = bestX;
  89         loc->fY = bestY;
  90
  91         fAreaSoFar += width*height;
  92         return true;
  93     }
  94
  95     loc->fX = 0;
  96     loc->fY = 0;
  97     return false;
  98 }
  99
 100 bool GrRectanizerSkyline::rectangleFits(int skylineIndex, int width, int height, int* ypos) const {
 101     int x = fSkyline[skylineIndex].fX;
 102     if (x + width > this->width()) {
 103         return false;
 104     }
 105
 106     int widthLeft = width;
 107     int i = skylineIndex;
 108     int y = fSkyline[skylineIndex].fY;
 109     while (widthLeft > 0) {
 110         y = SkMax32(y, fSkyline[i].fY);
 111         if (y + height > this->height()) {
 112             return false;
 113         }
 114         widthLeft -= fSkyline[i].fWidth;
 115         ++i;
 116         SkASSERT(i < fSkyline.count() || widthLeft <= 0);
 117     }
 118
 119     *ypos = y;
 120     return true;
 121 }
 122
 123 void GrRectanizerSkyline::addSkylineLevel(int skylineIndex, int x, int y, int width, int height) {
 124     SkylineSegment newSegment;
 125     newSegment.fX = x;
 126     newSegment.fY = y + height;
 127     newSegment.fWidth = width;
 128     fSkyline.insert(skylineIndex, 1, &newSegment);
 129
 130     SkASSERT(newSegment.fX + newSegment.fWidth <= this->width());
 131     SkASSERT(newSegment.fY <= this->height());
 132
 133     // delete width of this skyline segment from following ones
 134     for (int i = skylineIndex+1; i < fSkyline.count(); ++i) {
 135         SkASSERT(fSkyline[i-1].fX <= fSkyline[i].fX);
 136
 137         if (fSkyline[i].fX < fSkyline[i-1].fX + fSkyline[i-1].fWidth) {
 138             int shrink = fSkyline[i-1].fX + fSkyline[i-1].fWidth - fSkyline[i].fX;
 139
 140             fSkyline[i].fX += shrink;
 141             fSkyline[i].fWidth -= shrink;
 142
 143             if (fSkyline[i].fWidth <= 0) {
 144                 fSkyline.remove(i);
 145                 --i;
 146             } else {
 147                 break;
 148             }
 149         } else {
 150             break;
 151         }
 152     }
 153
 154     // merge fSkylines
 155     for (int i = 0; i < fSkyline.count()-1; ++i) {
 156         if (fSkyline[i].fY == fSkyline[i+1].fY) {
 157             fSkyline[i].fWidth += fSkyline[i+1].fWidth;
 158             fSkyline.remove(i+1);
 159             --i;
 160         }
 161     }
 162 }
 163
 164 ///////////////////////////////////////////////////////////////////////////////
 165
 166 GrRectanizer* GrRectanizer::Factory(int width, int height) {
 167     return SkNEW_ARGS(GrRectanizerSkyline, (width, height));
 168 }