impeller/typographer/rectangle_packer.cc

// Copyright 2013 The Flutter Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#include "impeller/typographer/rectangle_packer.h"

#include <algorithm>
#include <vector>

namespace impeller {

// Pack rectangles and track the current silhouette
// Based, in part, on Jukka Jylanki's work at http://clb.demon.fi
// and ported from Skia's implementation
// https://github.com/google/skia/blob/b5de4b8ae95c877a9ecfad5eab0765bc22550301/src/gpu/RectanizerSkyline.cpp
class SkylineRectanglePacker final : public RectanglePacker {
 public:
  SkylineRectanglePacker(int w, int h) : RectanglePacker(w, h) {
    this->reset();
  }

  ~SkylineRectanglePacker() final {}

  void reset() final {
    area_so_far_ = 0;
    skyline_.clear();
    skyline_.push_back(SkylineSegment{0, 0, this->width()});
  }

  bool addRect(int w, int h, IPoint16* loc) final;

  float percentFull() const final {
    return area_so_far_ / ((float)this->width() * this->height());
  }

 private:
  struct SkylineSegment {
    int x_;
    int y_;
    int width_;
  };

  std::vector<SkylineSegment> skyline_;

  int32_t area_so_far_;

  // Can a width x height rectangle fit in the free space represented by
  // the skyline segments >= 'skylineIndex'? If so, return true and fill in
  // 'y' with the y-location at which it fits (the x location is pulled from
  // 'skylineIndex's segment.
  bool rectangleFits(int skylineIndex, int width, int height, int* y) const;
  // Update the skyline structure to include a width x height rect located
  // at x,y.
  void addSkylineLevel(int skylineIndex, int x, int y, int width, int height);
};

bool SkylineRectanglePacker::addRect(int width, int height, IPoint16* loc) {
  if ((unsigned)width > (unsigned)this->width() ||
      (unsigned)height > (unsigned)this->height()) {
    return false;
  }

  // find position for new rectangle
  int bestWidth = this->width() + 1;
  int bestX = 0;
  int bestY = this->height() + 1;
  int bestIndex = -1;
  for (int i = 0; i < (int)skyline_.size(); ++i) {
    int y;
    if (this->rectangleFits(i, width, height, &y)) {
      // minimize y position first, then width of skyline
      if (y < bestY || (y == bestY && skyline_[i].width_ < bestWidth)) {
        bestIndex = i;
        bestWidth = skyline_[i].width_;
        bestX = skyline_[i].x_;
        bestY = y;
      }
    }
  }

  // add rectangle to skyline
  if (-1 != bestIndex) {
    this->addSkylineLevel(bestIndex, bestX, bestY, width, height);
    loc->x_ = bestX;
    loc->y_ = bestY;

    area_so_far_ += width * height;
    return true;
  }

  loc->x_ = 0;
  loc->y_ = 0;
  return false;
}

bool SkylineRectanglePacker::rectangleFits(int skylineIndex,
                                           int width,
                                           int height,
                                           int* ypos) const {
  int x = skyline_[skylineIndex].x_;
  if (x + width > this->width()) {
    return false;
  }

  int widthLeft = width;
  int i = skylineIndex;
  int y = skyline_[skylineIndex].y_;
  while (widthLeft > 0 && i < (int)skyline_.size()) {
    y = std::max(y, skyline_[i].y_);
    if (y + height > this->height()) {
      return false;
    }
    widthLeft -= skyline_[i].width_;
    ++i;
  }

  *ypos = y;
  return true;
}

void SkylineRectanglePacker::addSkylineLevel(int skylineIndex,
                                             int x,
                                             int y,
                                             int width,
                                             int height) {
  SkylineSegment newSegment;
  newSegment.x_ = x;
  newSegment.y_ = y + height;
  newSegment.width_ = width;
  skyline_.insert(std::next(skyline_.begin(), skylineIndex), newSegment);

  FML_DCHECK(newSegment.x_ + newSegment.width_ <= this->width());
  FML_DCHECK(newSegment.y_ <= this->height());

  // delete width of the new skyline segment from following ones
  for (int i = skylineIndex + 1; i < (int)skyline_.size(); ++i) {
    // The new segment subsumes all or part of skyline_[i]
    FML_DCHECK(skyline_[i - 1].x_ <= skyline_[i].x_);

    if (skyline_[i].x_ < skyline_[i - 1].x_ + skyline_[i - 1].width_) {
      int shrink = skyline_[i - 1].x_ + skyline_[i - 1].width_ - skyline_[i].x_;

      skyline_[i].x_ += shrink;
      skyline_[i].width_ -= shrink;

      if (skyline_[i].width_ <= 0) {
        // fully consumed, remove item at index i
        skyline_.erase(std::next(skyline_.begin(), i));
        --i;
      } else {
        // only partially consumed
        break;
      }
    } else {
      break;
    }
  }

  // merge skyline_s
  for (int i = 0; i < ((int)skyline_.size()) - 1; ++i) {
    if (skyline_[i].y_ == skyline_[i + 1].y_) {
      skyline_[i].width_ += skyline_[i + 1].width_;
      skyline_.erase(std::next(skyline_.begin(), i));
      --i;
    }
  }
}

RectanglePacker* RectanglePacker::Factory(int width, int height) {
  return new SkylineRectanglePacker(width, height);
}

}  // namespace impeller