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