2 * Copyright 2013 Google Inc.
4 * Use of this source code is governed by a BSD-style license that can be
5 * found in the LICENSE file.
8 #include "src/core/SkIPoint16.h"
9 #include "src/gpu/RectanizerSkyline.h"
15 bool RectanizerSkyline::addRect(int width, int height, SkIPoint16* loc) {
16 if ((unsigned)width > (unsigned)this->width() ||
17 (unsigned)height > (unsigned)this->height()) {
21 // find position for new rectangle
22 int bestWidth = this->width() + 1;
24 int bestY = this->height() + 1;
26 for (int i = 0; i < fSkyline.count(); ++i) {
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)) {
32 bestWidth = fSkyline[i].fWidth;
33 bestX = fSkyline[i].fX;
39 // add rectangle to skyline
40 if (-1 != bestIndex) {
41 this->addSkylineLevel(bestIndex, bestX, bestY, width, height);
45 fAreaSoFar += width*height;
54 bool RectanizerSkyline::rectangleFits(int skylineIndex, int width, int height, int* ypos) const {
55 int x = fSkyline[skylineIndex].fX;
56 if (x + width > this->width()) {
60 int widthLeft = width;
62 int y = fSkyline[skylineIndex].fY;
63 while (widthLeft > 0) {
64 y = std::max(y, fSkyline[i].fY);
65 if (y + height > this->height()) {
68 widthLeft -= fSkyline[i].fWidth;
70 SkASSERT(i < fSkyline.count() || widthLeft <= 0);
77 void RectanizerSkyline::addSkylineLevel(int skylineIndex, int x, int y, int width, int height) {
78 SkylineSegment newSegment;
80 newSegment.fY = y + height;
81 newSegment.fWidth = width;
82 fSkyline.insert(skylineIndex, 1, &newSegment);
84 SkASSERT(newSegment.fX + newSegment.fWidth <= this->width());
85 SkASSERT(newSegment.fY <= this->height());
87 // delete width of the new skyline segment from following ones
88 for (int i = skylineIndex+1; i < fSkyline.count(); ++i) {
89 // The new segment subsumes all or part of fSkyline[i]
90 SkASSERT(fSkyline[i-1].fX <= fSkyline[i].fX);
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;
95 fSkyline[i].fX += shrink;
96 fSkyline[i].fWidth -= shrink;
98 if (fSkyline[i].fWidth <= 0) {
103 // only partially consumed
112 for (int i = 0; i < fSkyline.count()-1; ++i) {
113 if (fSkyline[i].fY == fSkyline[i+1].fY) {
114 fSkyline[i].fWidth += fSkyline[i+1].fWidth;
115 fSkyline.remove(i+1);
121 ///////////////////////////////////////////////////////////////////////////////
123 Rectanizer* Rectanizer::Factory(int width, int height) {
124 return new RectanizerSkyline(width, height);
127 } // End of namespace skgpu