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