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