1 /*
2  * Copyright 2014 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 #ifndef GrRectanizer_skyline_DEFINED
9 #define GrRectanizer_skyline_DEFINED
10 
11 #include "GrRectanizer.h"
12 #include "SkTDArray.h"
13 
14 // Pack rectangles and track the current silhouette
15 // Based, in part, on Jukka Jylanki's work at http://clb.demon.fi
16 class GrRectanizerSkyline : public GrRectanizer {
17 public:
18     GrRectanizerSkyline(int w, int h) : INHERITED(w, h) {
19         this->reset();
20     }
21 
22     ~GrRectanizerSkyline() override { }
23 
24     void reset() override {
25         fAreaSoFar = 0;
26         fSkyline.reset();
27         SkylineSegment* seg = fSkyline.append(1);
28         seg->fX = 0;
29         seg->fY = 0;
30         seg->fWidth = this->width();
31     }
32 
33     bool addRect(int w, int h, SkIPoint16* loc) override;
34 
35     float percentFull() const override {
36         return fAreaSoFar / ((float)this->width() * this->height());
37     }
38 
39 private:
40     struct SkylineSegment {
41         int  fX;
42         int  fY;
43         int  fWidth;
44     };
45 
46     SkTDArray<SkylineSegment> fSkyline;
47 
48     int32_t fAreaSoFar;
49 
50     // Can a width x height rectangle fit in the free space represented by
51     // the skyline segments >= 'skylineIndex'? If so, return true and fill in
52     // 'y' with the y-location at which it fits (the x location is pulled from
53     // 'skylineIndex's segment.
54     bool rectangleFits(int skylineIndex, int width, int height, int* y) const;
55     // Update the skyline structure to include a width x height rect located
56     // at x,y.
57     void addSkylineLevel(int skylineIndex, int x, int y, int width, int height);
58 
59     typedef GrRectanizer INHERITED;
60 };
61 
62 #endif
63