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.h"
10#include "SkTDArray.h"
11
12// Pack rectangles and track the current silhouette
13// Based in part on Jukka Jylänki's work at http://clb.demon.fi
14
15class GrRectanizerSkyline : public GrRectanizer {
16public:
17    GrRectanizerSkyline(int w, int h) : GrRectanizer(w, h) {
18        reset();
19    }
20
21    virtual ~GrRectanizerSkyline() {
22    }
23
24    virtual void reset() {
25        fAreaSoFar = 0;
26        fSkyline.reset();
27        SkylineSegment* seg = fSkyline.append(1);
28        seg->fX = 0;
29        seg->fY = 0;
30        seg->fWidth = width();
31    }
32
33    virtual bool addRect(int w, int h, GrIPoint16* loc);
34
35    virtual float percentFull() const {
36        return fAreaSoFar / ((float)this->width() * this->height());
37    }
38
39    virtual int stripToPurge(int height) const { return -1; }
40    virtual void purgeStripAtY(int yCoord) { }
41
42    ///////////////////////////////////////////////////////////////////////////
43
44    struct SkylineSegment {
45        int  fX;
46        int  fY;
47        int  fWidth;
48    };
49
50    SkTDArray<SkylineSegment> fSkyline;
51
52    int32_t fAreaSoFar;
53
54    bool rectangleFits(int skylineIndex, int width, int height, int* y) const;
55    void addSkylineLevel(int skylineIndex, int x, int y, int width, int height);
56};
57
58bool GrRectanizerSkyline::addRect(int width, int height, GrIPoint16* loc) {
59    if ((unsigned)width > (unsigned)this->width() ||
60        (unsigned)height > (unsigned)this->height()) {
61        return false;
62    }
63
64    // find position for new rectangle
65    int bestWidth = this->width() + 1;
66    int bestX;
67    int bestY = this->height() + 1;
68    int bestIndex = -1;
69    for (int i = 0; i < fSkyline.count(); ++i) {
70        int y;
71        if (this->rectangleFits(i, width, height, &y)) {
72            // minimize y position first, then width of skyline
73            if (y < bestY || (y == bestY && fSkyline[i].fWidth < bestWidth)) {
74                bestIndex = i;
75                bestWidth = fSkyline[i].fWidth;
76                bestX = fSkyline[i].fX;
77                bestY = y;
78            }
79        }
80    }
81
82    // add rectangle to skyline
83    if (-1 != bestIndex) {
84        this->addSkylineLevel(bestIndex, bestX, bestY, width, height);
85        loc->fX = bestX;
86        loc->fY = bestY;
87
88        fAreaSoFar += width*height;
89        return true;
90    }
91
92    loc->fX = 0;
93    loc->fY = 0;
94    return false;
95}
96
97bool GrRectanizerSkyline::rectangleFits(int skylineIndex, int width, int height, int* ypos) const {
98    int x = fSkyline[skylineIndex].fX;
99    if (x + width > this->width()) {
100        return false;
101    }
102
103    int widthLeft = width;
104    int i = skylineIndex;
105    int y = fSkyline[skylineIndex].fY;
106    while (widthLeft > 0) {
107    y = SkMax32(y, fSkyline[i].fY);
108        if (y + height > this->height()) {
109            return false;
110        }
111    widthLeft -= fSkyline[i].fWidth;
112    ++i;
113    SkASSERT(i < fSkyline.count() || widthLeft <= 0);
114    }
115
116    *ypos = y;
117    return true;
118}
119
120void GrRectanizerSkyline::addSkylineLevel(int skylineIndex, int x, int y, int width, int height) {
121    SkylineSegment newSegment;
122    newSegment.fX = x;
123    newSegment.fY = y + height;
124    newSegment.fWidth = width;
125    fSkyline.insert(skylineIndex, 1, &newSegment);
126
127    SkASSERT(newSegment.fX + newSegment.fWidth <= this->width());
128    SkASSERT(newSegment.fY <= this->height());
129
130    // delete width of this skyline segment from following ones
131    for (int i = skylineIndex+1; i < fSkyline.count(); ++i) {
132        SkASSERT(fSkyline[i-1].fX <= fSkyline[i].fX);
133
134        if (fSkyline[i].fX < fSkyline[i-1].fX + fSkyline[i-1].fWidth) {
135            int shrink = fSkyline[i-1].fX + fSkyline[i-1].fWidth - fSkyline[i].fX;
136
137            fSkyline[i].fX += shrink;
138            fSkyline[i].fWidth -= shrink;
139
140            if (fSkyline[i].fWidth <= 0) {
141                fSkyline.remove(i);
142                --i;
143            }
144            else
145                break;
146        }
147        else
148            break;
149    }
150
151    // merge fSkylines
152    for (int i = 0; i < fSkyline.count()-1; ++i) {
153        if (fSkyline[i].fY == fSkyline[i+1].fY) {
154            fSkyline[i].fWidth += fSkyline[i+1].fWidth;
155            fSkyline.remove(i+1);
156            --i;
157        }
158    }
159}
160
161///////////////////////////////////////////////////////////////////////////////
162
163GrRectanizer* GrRectanizer::Factory(int width, int height) {
164    return SkNEW_ARGS(GrRectanizerSkyline, (width, height));
165}
166