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 15class GrRectanizerSkyline : public GrRectanizer { 16public: 17 GrRectanizerSkyline(int w, int h) : GrRectanizer(w, h) { 18 reset(); 19 } 20 21 virtual ~GrRectanizerSkyline() { 22 } 23 24 virtual void reset() { 25 fAreaSoFar = 0; 26 fSkyline.reset(); 27 SkylineSegment* seg = fSkyline.append(1); 28 seg->fX = 0; 29 seg->fY = 0; 30 seg->fWidth = width(); 31 } 32 33 virtual bool addRect(int w, int h, GrIPoint16* loc); 34 35 virtual float percentFull() const { 36 return fAreaSoFar / ((float)this->width() * this->height()); 37 } 38 39 virtual int stripToPurge(int height) const { return -1; } 40 virtual void purgeStripAtY(int yCoord) { } 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 58bool GrRectanizerSkyline::addRect(int width, int height, GrIPoint16* loc) { 59 if ((unsigned)width > (unsigned)this->width() || 60 (unsigned)height > (unsigned)this->height()) { 61 return false; 62 } 63 64 // find position for new rectangle 65 int bestWidth = this->width() + 1; 66 int bestX; 67 int bestY = this->height() + 1; 68 int bestIndex = -1; 69 for (int i = 0; i < fSkyline.count(); ++i) { 70 int y; 71 if (this->rectangleFits(i, width, height, &y)) { 72 // minimize y position first, then width of skyline 73 if (y < bestY || (y == bestY && fSkyline[i].fWidth < bestWidth)) { 74 bestIndex = i; 75 bestWidth = fSkyline[i].fWidth; 76 bestX = fSkyline[i].fX; 77 bestY = y; 78 } 79 } 80 } 81 82 // add rectangle to skyline 83 if (-1 != bestIndex) { 84 this->addSkylineLevel(bestIndex, bestX, bestY, width, height); 85 loc->fX = bestX; 86 loc->fY = bestY; 87 88 fAreaSoFar += width*height; 89 return true; 90 } 91 92 loc->fX = 0; 93 loc->fY = 0; 94 return false; 95} 96 97bool GrRectanizerSkyline::rectangleFits(int skylineIndex, int width, int height, int* ypos) const { 98 int x = fSkyline[skylineIndex].fX; 99 if (x + width > this->width()) { 100 return false; 101 } 102 103 int widthLeft = width; 104 int i = skylineIndex; 105 int y = fSkyline[skylineIndex].fY; 106 while (widthLeft > 0) { 107 y = SkMax32(y, fSkyline[i].fY); 108 if (y + height > this->height()) { 109 return false; 110 } 111 widthLeft -= fSkyline[i].fWidth; 112 ++i; 113 SkASSERT(i < fSkyline.count() || widthLeft <= 0); 114 } 115 116 *ypos = y; 117 return true; 118} 119 120void GrRectanizerSkyline::addSkylineLevel(int skylineIndex, int x, int y, int width, int height) { 121 SkylineSegment newSegment; 122 newSegment.fX = x; 123 newSegment.fY = y + height; 124 newSegment.fWidth = width; 125 fSkyline.insert(skylineIndex, 1, &newSegment); 126 127 SkASSERT(newSegment.fX + newSegment.fWidth <= this->width()); 128 SkASSERT(newSegment.fY <= this->height()); 129 130 // delete width of this skyline segment from following ones 131 for (int i = skylineIndex+1; i < fSkyline.count(); ++i) { 132 SkASSERT(fSkyline[i-1].fX <= fSkyline[i].fX); 133 134 if (fSkyline[i].fX < fSkyline[i-1].fX + fSkyline[i-1].fWidth) { 135 int shrink = fSkyline[i-1].fX + fSkyline[i-1].fWidth - fSkyline[i].fX; 136 137 fSkyline[i].fX += shrink; 138 fSkyline[i].fWidth -= shrink; 139 140 if (fSkyline[i].fWidth <= 0) { 141 fSkyline.remove(i); 142 --i; 143 } 144 else 145 break; 146 } 147 else 148 break; 149 } 150 151 // merge fSkylines 152 for (int i = 0; i < fSkyline.count()-1; ++i) { 153 if (fSkyline[i].fY == fSkyline[i+1].fY) { 154 fSkyline[i].fWidth += fSkyline[i+1].fWidth; 155 fSkyline.remove(i+1); 156 --i; 157 } 158 } 159} 160 161/////////////////////////////////////////////////////////////////////////////// 162 163GrRectanizer* GrRectanizer::Factory(int width, int height) { 164 return SkNEW_ARGS(GrRectanizerSkyline, (width, height)); 165} 166