| Flutter Impeller |

rectangle_packer.cc
Go to the documentation of this file.
1 // Copyright 2013 The Flutter Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4
5 #include "impeller/typographer/rectangle_packer.h"
6
7 #include <algorithm>
8 #include <vector>
9
10 namespace impeller {
11
12 // Pack rectangles and track the current silhouette
13 // Based, in part, on Jukka Jylanki's work at http://clb.demon.fi
14 // and ported from Skia's implementation
15 // https://github.com/google/skia/blob/b5de4b8ae95c877a9ecfad5eab0765bc22550301/src/gpu/RectanizerSkyline.cpp
16 class SkylineRectanglePacker final : public RectanglePacker {
17 public:
18 SkylineRectanglePacker(int w, int h) : RectanglePacker(w, h) {
19 this->reset();
20 }
21
22 ~SkylineRectanglePacker() final {}
23
24 void reset() final {
25 area_so_far_ = 0;
26 skyline_.clear();
27 skyline_.push_back(SkylineSegment{0, 0, this->width()});
28 }
29
30 bool addRect(int w, int h, IPoint16* loc) final;
31
32 float percentFull() const final {
33 return area_so_far_ / ((float)this->width() * this->height());
34 }
35
36 private:
37 struct SkylineSegment {
38 int x_;
39 int y_;
40 int width_;
41 };
42
43 std::vector<SkylineSegment> skyline_;
44
45 int32_t area_so_far_;
46
47 // Can a width x height rectangle fit in the free space represented by
48 // the skyline segments >= 'skylineIndex'? If so, return true and fill in
49 // 'y' with the y-location at which it fits (the x location is pulled from
50 // 'skylineIndex's segment.
51 bool rectangleFits(int skylineIndex, int width, int height, int* y) const;
52 // Update the skyline structure to include a width x height rect located
53 // at x,y.
54 void addSkylineLevel(int skylineIndex, int x, int y, int width, int height);
55 };
56
57 bool SkylineRectanglePacker::addRect(int width, int height, IPoint16* loc) {
58 if ((unsigned)width > (unsigned)this->width() ||
59 (unsigned)height > (unsigned)this->height()) {
60 return false;
61 }
62
63 // find position for new rectangle
64 int bestWidth = this->width() + 1;
65 int bestX = 0;
66 int bestY = this->height() + 1;
67 int bestIndex = -1;
68 for (int i = 0; i < (int)skyline_.size(); ++i) {
69 int y;
70 if (this->rectangleFits(i, width, height, &y)) {
71 // minimize y position first, then width of skyline
72 if (y < bestY || (y == bestY && skyline_[i].width_ < bestWidth)) {
73 bestIndex = i;
74 bestWidth = skyline_[i].width_;
75 bestX = skyline_[i].x_;
76 bestY = y;
77 }
78 }
79 }
80
81 // add rectangle to skyline
82 if (-1 != bestIndex) {
83 this->addSkylineLevel(bestIndex, bestX, bestY, width, height);
84 loc->x_ = bestX;
85 loc->y_ = bestY;
86
87 area_so_far_ += width * height;
88 return true;
89 }
90
91 loc->x_ = 0;
92 loc->y_ = 0;
93 return false;
94 }
95
96 bool SkylineRectanglePacker::rectangleFits(int skylineIndex,
97 int width,
98 int height,
99 int* ypos) const {
100 int x = skyline_[skylineIndex].x_;
101 if (x + width > this->width()) {
102 return false;
103 }
104
105 int widthLeft = width;
106 int i = skylineIndex;
107 int y = skyline_[skylineIndex].y_;
108 while (widthLeft > 0 && i < (int)skyline_.size()) {
109 y = std::max(y, skyline_[i].y_);
110 if (y + height > this->height()) {
111 return false;
112 }
113 widthLeft -= skyline_[i].width_;
114 ++i;
115 }
116
117 *ypos = y;
118 return true;
119 }
120
121 void SkylineRectanglePacker::addSkylineLevel(int skylineIndex,
122 int x,
123 int y,
124 int width,
125 int height) {
126 SkylineSegment newSegment;
127 newSegment.x_ = x;
128 newSegment.y_ = y + height;
129 newSegment.width_ = width;
130 skyline_.insert(std::next(skyline_.begin(), skylineIndex), newSegment);
131
132 FML_DCHECK(newSegment.x_ + newSegment.width_ <= this->width());
133 FML_DCHECK(newSegment.y_ <= this->height());
134
135 // delete width of the new skyline segment from following ones
136 for (int i = skylineIndex + 1; i < (int)skyline_.size(); ++i) {
137 // The new segment subsumes all or part of skyline_[i]
138 FML_DCHECK(skyline_[i - 1].x_ <= skyline_[i].x_);
139
140 if (skyline_[i].x_ < skyline_[i - 1].x_ + skyline_[i - 1].width_) {
141 int shrink = skyline_[i - 1].x_ + skyline_[i - 1].width_ - skyline_[i].x_;
142
143 skyline_[i].x_ += shrink;
144 skyline_[i].width_ -= shrink;
145
146 if (skyline_[i].width_ <= 0) {
147 // fully consumed, remove item at index i
148 skyline_.erase(std::next(skyline_.begin(), i));
149 --i;
150 } else {
151 // only partially consumed
152 break;
153 }
154 } else {
155 break;
156 }
157 }
158
159 // merge skyline_s
160 for (int i = 0; i < ((int)skyline_.size()) - 1; ++i) {
161 if (skyline_[i].y_ == skyline_[i + 1].y_) {
162 skyline_[i].width_ += skyline_[i + 1].width_;
163 skyline_.erase(std::next(skyline_.begin(), i));
164 --i;
165 }
166 }
167 }
168
169 std::unique_ptr<RectanglePacker> RectanglePacker::Factory(int width,
170 int height) {
171 return std::make_unique<SkylineRectanglePacker>(width, height);
172 }
173
174 } // namespace impeller
impeller::SkylineRectanglePacker::addRect
bool addRect(int w, int h, IPoint16 *loc) final
Attempt to add a rect without moving already placed rectangles.
Definition: rectangle_packer.cc:57
impeller::SkylineRectanglePacker::~SkylineRectanglePacker
~SkylineRectanglePacker() final
Definition: rectangle_packer.cc:22
impeller::RectanglePacker::width
int width() const
Definition: rectangle_packer.h:64
impeller::RectanglePacker::Factory
static std::unique_ptr< RectanglePacker > Factory(int width, int height)
Return an empty packer with area specified by width and height.
Definition: rectangle_packer.cc:169
impeller::SkylineRectanglePacker::reset
void reset() final
Empty out all previously added rectangles.
Definition: rectangle_packer.cc:24
impeller::RectanglePacker
Packs rectangles into a specified area without rotating them.
Definition: rectangle_packer.h:25
rectangle_packer.h
impeller::RectanglePacker::height
int height() const
Definition: rectangle_packer.h:65
impeller::IPoint16::x_
int16_t x_
Definition: rectangle_packer.h:18
impeller::SkylineRectanglePacker
Definition: rectangle_packer.cc:16
impeller::IPoint16::y_
int16_t y_
Definition: rectangle_packer.h:19
impeller::SkylineRectanglePacker::SkylineRectanglePacker
SkylineRectanglePacker(int w, int h)
Definition: rectangle_packer.cc:18
impeller::IPoint16
Definition: rectangle_packer.h:14
impeller
Definition: aiks_blur_unittests.cc:20
impeller::SkylineRectanglePacker::percentFull
float percentFull() const final
Returns how much area has been filled with rectangles.
Definition: rectangle_packer.cc:32