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 
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
20  public:
21  SkylineRectanglePacker(int w, int h) : RectanglePacker(w, h) { Reset(); }
22 
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
Packs rectangles into a specified area without rotating them.
static std::shared_ptr< RectanglePacker > Factory(int width, int height)
Return an empty packer with area specified by width and height.
void Reset() final
Empty out all previously added rectangles.
bool AddRect(int w, int h, IPoint16 *loc) final
Attempt to add a rect without moving already placed rectangles.
Scalar PercentFull() const final
Returns how much area has been filled with rectangles.
int32_t x
float Scalar
Definition: scalar.h:19