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