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