The Tor Browser / file comparison
comparison: gfx/skia/trunk/src/gpu/GrRectanizer_skyline.cpp
gfx/skia/trunk/src/gpu/GrRectanizer_skyline.cpp
- branch
- TOR_BUG_3246
- changeset 7
- 129ffea94266
equal
deleted
inserted
replaced
| -1:000000000000 | 0:558a38a202b2 |
|---|---|
| 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) : 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 | |
| 58 bool 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 | |
| 97 bool 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 | |
| 120 void 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 | |
| 163 GrRectanizer* GrRectanizer::Factory(int width, int height) { | |
| 164 return SkNEW_ARGS(GrRectanizerSkyline, (width, height)); | |
| 165 } |
