1 /*
2 * Copyright 2013 Google Inc.
3 *
4 * Use of this source code is governed by a BSD-style license that can be
5 * found in the LICENSE file.
6 */
7
8 #include "src/core/SkIPoint16.h"
9 #include "src/gpu/RectanizerSkyline.h"
10
11 #include <algorithm>
12
13 namespace skgpu {
14
addRect(int width,int height,SkIPoint16 * loc)15 bool RectanizerSkyline::addRect(int width, int height, SkIPoint16* loc) {
16 if ((unsigned)width > (unsigned)this->width() ||
17 (unsigned)height > (unsigned)this->height()) {
18 return false;
19 }
20
21 // find position for new rectangle
22 int bestWidth = this->width() + 1;
23 int bestX = 0;
24 int bestY = this->height() + 1;
25 int bestIndex = -1;
26 for (int i = 0; i < fSkyline.size(); ++i) {
27 int y;
28 if (this->rectangleFits(i, width, height, &y)) {
29 // minimize y position first, then width of skyline
30 if (y < bestY || (y == bestY && fSkyline[i].fWidth < bestWidth)) {
31 bestIndex = i;
32 bestWidth = fSkyline[i].fWidth;
33 bestX = fSkyline[i].fX;
34 bestY = y;
35 }
36 }
37 }
38
39 // add rectangle to skyline
40 if (-1 != bestIndex) {
41 this->addSkylineLevel(bestIndex, bestX, bestY, width, height);
42 loc->fX = bestX;
43 loc->fY = bestY;
44
45 fAreaSoFar += width*height;
46 return true;
47 }
48
49 loc->fX = 0;
50 loc->fY = 0;
51 return false;
52 }
53
rectangleFits(int skylineIndex,int width,int height,int * ypos) const54 bool RectanizerSkyline::rectangleFits(int skylineIndex, int width, int height, int* ypos) const {
55 int x = fSkyline[skylineIndex].fX;
56 if (x + width > this->width()) {
57 return false;
58 }
59
60 int widthLeft = width;
61 int i = skylineIndex;
62 int y = fSkyline[skylineIndex].fY;
63 while (widthLeft > 0) {
64 y = std::max(y, fSkyline[i].fY);
65 if (y + height > this->height()) {
66 return false;
67 }
68 widthLeft -= fSkyline[i].fWidth;
69 ++i;
70 SkASSERT(i < fSkyline.size() || widthLeft <= 0);
71 }
72
73 *ypos = y;
74 return true;
75 }
76
addSkylineLevel(int skylineIndex,int x,int y,int width,int height)77 void RectanizerSkyline::addSkylineLevel(int skylineIndex, int x, int y, int width, int height) {
78 SkylineSegment newSegment;
79 newSegment.fX = x;
80 newSegment.fY = y + height;
81 newSegment.fWidth = width;
82 fSkyline.insert(skylineIndex, 1, &newSegment);
83
84 SkASSERT(newSegment.fX + newSegment.fWidth <= this->width());
85 SkASSERT(newSegment.fY <= this->height());
86
87 // delete width of the new skyline segment from following ones
88 for (int i = skylineIndex+1; i < fSkyline.size(); ++i) {
89 // The new segment subsumes all or part of fSkyline[i]
90 SkASSERT(fSkyline[i-1].fX <= fSkyline[i].fX);
91
92 if (fSkyline[i].fX < fSkyline[i-1].fX + fSkyline[i-1].fWidth) {
93 int shrink = fSkyline[i-1].fX + fSkyline[i-1].fWidth - fSkyline[i].fX;
94
95 fSkyline[i].fX += shrink;
96 fSkyline[i].fWidth -= shrink;
97
98 if (fSkyline[i].fWidth <= 0) {
99 // fully consumed
100 fSkyline.remove(i);
101 --i;
102 } else {
103 // only partially consumed
104 break;
105 }
106 } else {
107 break;
108 }
109 }
110
111 // merge fSkylines
112 for (int i = 0; i < fSkyline.size()-1; ++i) {
113 if (fSkyline[i].fY == fSkyline[i+1].fY) {
114 fSkyline[i].fWidth += fSkyline[i+1].fWidth;
115 fSkyline.remove(i+1);
116 --i;
117 }
118 }
119 }
120
121 ///////////////////////////////////////////////////////////////////////////////
122
Factory(int width,int height)123 Rectanizer* Rectanizer::Factory(int width, int height) {
124 return new RectanizerSkyline(width, height);
125 }
126
127 } // End of namespace skgpu
128