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