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 "SkIPoint16.h"
10 
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 = 0;
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 
50 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 
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 
119 GrRectanizer* GrRectanizer::Factory(int width, int height) {
120     return new GrRectanizerSkyline(width, height);
121 }
122