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