dl_region2.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 "flutter/display_list/geometry/dl_region2.h"

#include "flutter/fml/logging.h"

namespace flutter {

#undef DLREGION2_DO_STATS

DlRegion2::DlRegion2(const std::vector<SkIRect>& rects) {
  addRects(std::move(rects));
}

std::vector<SkIRect> DlRegion2::getRects(bool deband) const {
  std::vector<SkIRect> rects;
  size_t previous_span_end = 0;
  for (const auto& line : lines_) {
    for (const Span& span : line.spans) {
      SkIRect rect{span.left, line.top, span.right, line.bottom};
      if (deband) {
        auto iter = rects.begin() + previous_span_end;
        // If there is rectangle previously in rects on which this one is a
        // vertical continuation, remove the previous rectangle and expand
        // this one vertically to cover the area.
        while (iter != rects.begin()) {
          --iter;
          if (iter->bottom() < rect.top()) {
            // Went all the way to previous span line.
            break;
          } else if (iter->left() == rect.left() &&
                     iter->right() == rect.right()) {
            FML_DCHECK(iter->bottom() == rect.top());
            rect.fTop = iter->fTop;
            rects.erase(iter);
            --previous_span_end;
            break;
          }
        }
      }
      rects.push_back(rect);
    }
    previous_span_end = rects.size();
  }
  return rects;
}

bool DlRegion2::spansEqual(const SpanVec& spans1, const SpanVec& spans2) {
  size_t size = spans1.size();
  if (spans2.size() != size) {
    return false;
  }
  return 0 == memcmp(spans1.data(), spans2.data(),
                     size * sizeof(DlRegion2::Span));
}

void DlRegion2::addRects(const std::vector<SkIRect>& unsorted_rects) {
  size_t count = unsorted_rects.size();
  std::vector<const SkIRect*> rects(count);
  for (size_t i = 0; i < count; i++) {
    rects[i] = &unsorted_rects[i];
  }
  std::sort(rects.begin(), rects.end(), [](const SkIRect* a, const SkIRect* b) {
    if (a->top() < b->top()) {
      return true;
    }
    if (a->top() > b->top()) {
      return false;
    }
    return a->left() < b->left();
  });

  size_t active_end = 0;
  size_t next_rect = 0;
  int32_t cur_y = std::numeric_limits<int32_t>::min();
  SpanVec working_spans;

#ifdef DLREGION2_DO_STATS
  size_t active_rect_count = 0;
  size_t span_count = 0;
  int pass_count = 0;
  int line_count = 0;
#endif

  while (next_rect < count || active_end > 0) {
    // First prune passed rects out of the active list
    size_t preserve_end = 0;
    for (size_t i = 0; i < active_end; i++) {
      const SkIRect* r = rects[i];
      if (r->bottom() > cur_y) {
        rects[preserve_end++] = r;
      }
    }
    active_end = preserve_end;

    // If we have no active rects any more, jump to the top of the
    // next available input rect.
    if (active_end == 0) {
      if (next_rect >= count) {
        // No active rects and no more rects to bring in. We are done.
        break;
      }
      cur_y = rects[next_rect]->top();
    }

    // Next, insert any new rects we've reached into the active list
    while (next_rect < count) {
      const SkIRect* r = rects[next_rect];
      if (r->isEmpty()) {
        continue;
      }
      if (r->top() > cur_y) {
        break;
      }
      // We now know that we will be inserting this rect into active list
      next_rect++;
      size_t insert_at = active_end++;
      while (insert_at > 0) {
        const SkIRect* ir = rects[insert_at - 1];
        if (ir->left() <= r->left()) {
          break;
        }
        rects[insert_at--] = ir;
      }
      rects[insert_at] = r;
    }

    // We either preserved some rects in the active list or added more from
    // the remaining input rects, or we would have exited the loop above.
    FML_DCHECK(active_end != 0);
    working_spans.clear();
    FML_DCHECK(working_spans.empty());

#ifdef DLREGION2_DO_STATS
    active_rect_count += active_end;
    pass_count++;
#endif

    // [start_x, end_x) always represents a valid span to be inserted
    // [cur_y, end_y) is the intersecting range over which all spans are valid
    int32_t start_x = rects[0]->left();
    int32_t end_x = rects[0]->right();
    int32_t end_y = rects[0]->bottom();
    for (size_t i = 1; i < active_end; i++) {
      const SkIRect* r = rects[i];
      if (r->left() > end_x) {
        working_spans.emplace_back(start_x, end_x);
        start_x = r->left();
        end_x = r->right();
      } else if (end_x < r->right()) {
        end_x = r->right();
      }
      if (end_y > r->bottom()) {
        end_y = r->bottom();
      }
    }
    working_spans.emplace_back(start_x, end_x);

    // end_y must not pass by the top of the next input rect
    if (next_rect < count && end_y > rects[next_rect]->top()) {
      end_y = rects[next_rect]->top();
    }

    // If all of the rules above work out, we should never collapse the
    // current range of Y coordinates to empty
    FML_DCHECK(end_y > cur_y);

    if (!lines_.empty() &&
        lines_.back().bottom == cur_y &&
        spansEqual(lines_.back().spans, working_spans)) {
      lines_.back().bottom = end_y;
    } else {
#ifdef DLREGION2_DO_STATS
      span_count += working_spans.size();
      line_count++;
#endif
      lines_.emplace_back(cur_y, end_y, working_spans);
    }
    cur_y = end_y;
  }

#ifdef DLREGION2_DO_STATS
  double span_avg = ((double) span_count) / line_count;
  double active_avg = ((double) active_rect_count) / pass_count;
  FML_LOG(ERROR) << lines_.size() << " lines for "
                 << count << " input rects, avg "
                 << span_avg << " spans per line and avg "
                 << active_avg << " active rects per loop";
#endif
}

#undef DLREGION2_DO_STATS

}  // namespace flutter