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