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
12bool 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
51bool 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
74void 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
120GrRectanizer* GrRectanizer::Factory(int width, int height) {
121    return SkNEW_ARGS(GrRectanizerSkyline, (width, height));
122}
123