blob: 44ef8134fa4cc7514ac29054db174e41dc82b4bf [file] [log] [blame]
commit-bot@chromium.org09846a02013-10-02 17:37:59 +00001/*
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
commit-bot@chromium.orgad854bf2014-05-29 18:46:38 +00008#include "GrRectanizer_skyline.h"
Mike Reed1fda0242018-04-04 15:39:46 -04009#include "SkIPoint16.h"
commit-bot@chromium.org09846a02013-10-02 17:37:59 +000010
robertphillipsd5373412014-06-02 10:20:14 -070011bool GrRectanizerSkyline::addRect(int width, int height, SkIPoint16* loc) {
commit-bot@chromium.org09846a02013-10-02 17:37:59 +000012 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;
Kevin Lubick42846132018-01-05 10:11:11 -050019 int bestX = 0;
commit-bot@chromium.org09846a02013-10-02 17:37:59 +000020 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
50bool 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) {
commit-bot@chromium.org53e1e4d2014-04-01 16:25:11 +000060 y = SkMax32(y, fSkyline[i].fY);
commit-bot@chromium.org09846a02013-10-02 17:37:59 +000061 if (y + height > this->height()) {
62 return false;
63 }
commit-bot@chromium.org53e1e4d2014-04-01 16:25:11 +000064 widthLeft -= fSkyline[i].fWidth;
65 ++i;
66 SkASSERT(i < fSkyline.count() || widthLeft <= 0);
commit-bot@chromium.org09846a02013-10-02 17:37:59 +000067 }
68
69 *ypos = y;
70 return true;
71}
72
73void 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
robertphillips4cbf8e32014-06-09 07:59:25 -070083 // delete width of the new skyline segment from following ones
commit-bot@chromium.org09846a02013-10-02 17:37:59 +000084 for (int i = skylineIndex+1; i < fSkyline.count(); ++i) {
robertphillips4cbf8e32014-06-09 07:59:25 -070085 // The new segment subsumes all or part of fSkyline[i]
commit-bot@chromium.org09846a02013-10-02 17:37:59 +000086 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) {
robertphillips4cbf8e32014-06-09 07:59:25 -070095 // fully consumed
commit-bot@chromium.org09846a02013-10-02 17:37:59 +000096 fSkyline.remove(i);
97 --i;
commit-bot@chromium.org53e1e4d2014-04-01 16:25:11 +000098 } else {
robertphillips4cbf8e32014-06-09 07:59:25 -070099 // only partially consumed
commit-bot@chromium.org09846a02013-10-02 17:37:59 +0000100 break;
commit-bot@chromium.org53e1e4d2014-04-01 16:25:11 +0000101 }
102 } else {
commit-bot@chromium.org09846a02013-10-02 17:37:59 +0000103 break;
commit-bot@chromium.org53e1e4d2014-04-01 16:25:11 +0000104 }
commit-bot@chromium.org09846a02013-10-02 17:37:59 +0000105 }
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
119GrRectanizer* GrRectanizer::Factory(int width, int height) {
halcanary385fe4d2015-08-26 13:07:48 -0700120 return new GrRectanizerSkyline(width, height);
commit-bot@chromium.org09846a02013-10-02 17:37:59 +0000121}