flutter::DlRegion Class Reference

#include <dl_region.h>

Public Member Functions
	DlRegion ()=default
	Creates an empty region. More...
	DlRegion (const std::vector< SkIRect > &rects)
	DlRegion (const SkIRect &rect)
	Creates region covering area of a rectangle. More...
	DlRegion (const DlRegion &)=default
	DlRegion (DlRegion &&)=default
DlRegion &	operator= (const DlRegion &)=default
DlRegion &	operator= (DlRegion &&)=default
std::vector< SkIRect >	getRects (bool deband=true) const
const SkIRect &	bounds () const
bool	intersects (const SkIRect &rect) const
	Returns whether this region intersects with a rectangle. More...
bool	intersects (const DlRegion &region) const
	Returns whether this region intersects with another region. More...
bool	isEmpty () const
	Returns true if region is empty (contains no rectangles). More...
bool	isComplex () const
	Returns true if region is not empty and contains more than one rectangle. More...
bool	isSimple () const

Static Public Member Functions
static DlRegion	MakeUnion (const DlRegion &a, const DlRegion &b)
static DlRegion	MakeIntersection (const DlRegion &a, const DlRegion &b)

Detailed Description

Represents a region as a collection of non-overlapping rectangles. Implements a subset of SkRegion functionality optimized for quickly converting set of overlapping rectangles to non-overlapping rectangles.

Definition at line 18 of file dl_region.h.

Constructor & Destructor Documentation

DlRegion() [1/5]

flutter::DlRegion::DlRegion ( )

default

Creates an empty region.

DlRegion() [2/5]

flutter::DlRegion::DlRegion ( const std::vector< SkIRect > &  rects )

explicit

Creates region by bulk adding the rectangles. Matches SkRegion::op(rect, SkRegion::kUnion_Op) behavior.

Definition at line 97 of file dl_region.cc.

                                                  {
  setRects(rects);
}

DlRegion() [3/5]

flutter::DlRegion::DlRegion ( const SkIRect &  rect )

explicit

Creates region covering area of a rectangle.

Definition at line 101 of file dl_region.cc.

                                      : bounds_(rect) {
  Span span{rect.left(), rect.right()};
  lines_.push_back(makeLine(rect.top(), rect.bottom(), &span, &span + 1));
}

DlRegion() [4/5]

flutter::DlRegion::DlRegion ( const DlRegion &  )

default

DlRegion() [5/5]

flutter::DlRegion::DlRegion ( DlRegion &&  )

default

Member Function Documentation

bounds()

const SkIRect & flutter::DlRegion::bounds ( ) const

inline

Returns maximum and minimum axis values of rectangles in this region. If region is empty returns SKIRect::MakeEmpty().

Definition at line 53 of file dl_region.h.

{ return bounds_; }

getRects()

std::vector< SkIRect > flutter::DlRegion::getRects

(

bool

deband = true

)

const

Returns list of non-overlapping rectangles that cover current region. If |deband| is false, each span line will result in separate rectangles, closely matching SkRegion::Iterator behavior. If |deband| is true, matching rectangles from adjacent span lines will be merged into single rectangle.

Definition at line 563 of file dl_region.cc.

                                                       {
  std::vector<SkIRect> rects;
  if (isEmpty()) {
    return rects;
  } else if (isSimple()) {
    rects.push_back(bounds_);
    return rects;
  }
 
  size_t rect_count = 0;
  size_t previous_span_end = 0;
  for (const auto& line : lines_) {
    rect_count += span_buffer_.getChunkSize(line.chunk_handle);
  }
  rects.reserve(rect_count);
 
  for (const auto& line : lines_) {
    const Span *span_begin, *span_end;
    span_buffer_.getSpans(line.chunk_handle, span_begin, span_end);
    for (const auto* span = span_begin; span < span_end; ++span) {
      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;
}

intersects() [1/2]

bool flutter::DlRegion::intersects

(

const DlRegion &

region

)

const

Returns whether this region intersects with another region.

Definition at line 705 of file dl_region.cc.

                                                      {
  if (isEmpty() || region.isEmpty()) {
    return false;
  }
 
  auto our_complex = isComplex();
  auto their_complex = region.isComplex();
  auto bounds_intersect = SkIRect::Intersects(bounds_, region.bounds_);
 
  if (!our_complex && !their_complex) {
    return bounds_intersect;
  }
 
  if (!bounds_intersect) {
    return false;
  }
 
  if (!our_complex) {
    return region.intersects(bounds_);
  }
 
  if (!their_complex) {
    return intersects(region.bounds_);
  }
 
  std::vector<SpanLine>::const_iterator ours, theirs;
  getIntersectionIterators(lines_, region.lines_, ours, theirs);
  auto ours_end = lines_.end();
  auto theirs_end = region.lines_.end();
 
  while (ours != ours_end && theirs != theirs_end) {
    if (ours->bottom <= theirs->top) {
      ++ours;
    } else if (theirs->bottom <= ours->top) {
      ++theirs;
    } else {
      FML_DCHECK(ours->top < theirs->bottom && theirs->top < ours->bottom);
      const Span *ours_begin, *ours_end;
      span_buffer_.getSpans(ours->chunk_handle, ours_begin, ours_end);
      const Span *theirs_begin, *theirs_end;
      region.span_buffer_.getSpans(theirs->chunk_handle, theirs_begin,
                                   theirs_end);
      if (spansIntersect(ours_begin, ours_end, theirs_begin, theirs_end)) {
        return true;
      }
      if (ours->bottom < theirs->bottom) {
        ++ours;
      } else {
        ++theirs;
      }
    }
  }
  return false;
}

intersects() [2/2]

bool flutter::DlRegion::intersects

(

const SkIRect &

rect

)

const

Returns whether this region intersects with a rectangle.

Definition at line 617 of file dl_region.cc.

                                                   {
  if (isEmpty()) {
    return false;
  }
 
  auto bounds_intersect = SkIRect::Intersects(bounds_, rect);
 
  if (isSimple()) {
    return bounds_intersect;
  }
 
  if (!bounds_intersect) {
    return false;
  }
 
  auto it = lines_.begin();
  auto end = lines_.end();
  if (lines_.size() > kBinarySearchThreshold &&
      it[kBinarySearchThreshold].bottom <= rect.fTop) {
    it = std::lower_bound(
        lines_.begin() + kBinarySearchThreshold + 1, lines_.end(), rect.fTop,
        [](const SpanLine& line, int32_t top) { return line.bottom <= top; });
  } else {
    while (it != end && it->bottom <= rect.fTop) {
      ++it;
      continue;
    }
  }
  while (it != end && it->top < rect.fBottom) {
    FML_DCHECK(rect.fTop < it->bottom && it->top < rect.fBottom);
    const Span *begin, *end;
    span_buffer_.getSpans(it->chunk_handle, begin, end);
    while (begin != end && begin->left < rect.fRight) {
      if (begin->right > rect.fLeft) {
        return true;
      }
      ++begin;
    }
    ++it;
  }
 
  return false;
}

isComplex()

bool flutter::DlRegion::isComplex

(

)

const

Returns true if region is not empty and contains more than one rectangle.

Definition at line 611 of file dl_region.cc.

                               {
  return lines_.size() > 1 ||
         (lines_.size() == 1 &&
          span_buffer_.getChunkSize(lines_.front().chunk_handle) > 1);
}

isEmpty()

bool flutter::DlRegion::isEmpty ( ) const

inline

Returns true if region is empty (contains no rectangles).

Definition at line 62 of file dl_region.h.

{ return lines_.empty(); }

isSimple()

bool flutter::DlRegion::isSimple ( ) const

inline

Returns true if region can be represented by single rectangle or is empty.

Definition at line 69 of file dl_region.h.

{ return !isComplex(); }

MakeIntersection()

DlRegion flutter::DlRegion::MakeIntersection ( const DlRegion &  a, const DlRegion &  b  )

static

Creates intersection region of region a and b. Matches SkRegion a; a.op(b, SkRegion::kIntersect_Op) behavior.

Definition at line 497 of file dl_region.cc.

                                                                        {
  if (!SkIRect::Intersects(a.bounds_, b.bounds_)) {
    return DlRegion();
  } else if (a.isSimple() && b.isSimple()) {
    SkIRect r(a.bounds_);
    auto res = r.intersect(b.bounds_);
    (void)res;  // Suppress unused variable warning in release builds.
    FML_DCHECK(res);
    return DlRegion(r);
  } else if (a.isSimple() && a.bounds_.contains(b.bounds_)) {
    return b;
  } else if (b.isSimple() && b.bounds_.contains(a.bounds_)) {
    return a;
  }
 
  DlRegion res;
  res.span_buffer_.reserve(
      std::max(a.span_buffer_.capacity(), b.span_buffer_.capacity()));
 
  auto& lines = res.lines_;
  lines.reserve(std::min(a.lines_.size(), b.lines_.size()));
 
  std::vector<SpanLine>::const_iterator a_it, b_it;
  getIntersectionIterators(a.lines_, b.lines_, a_it, b_it);
 
  auto a_end = a.lines_.end();
  auto b_end = b.lines_.end();
 
  auto& a_buffer = a.span_buffer_;
  auto& b_buffer = b.span_buffer_;
 
  std::vector<Span> tmp;
 
  int32_t cur_top = std::numeric_limits<int32_t>::min();
 
  while (a_it != a_end && b_it != b_end) {
    auto a_top = std::max(cur_top, a_it->top);
    auto b_top = std::max(cur_top, b_it->top);
    if (a_it->bottom <= b_top) {
      ++a_it;
    } else if (b_it->bottom <= a_top) {
      ++b_it;
    } else {
      auto top = std::max(a_top, b_top);
      auto bottom = std::min(a_it->bottom, b_it->bottom);
      FML_DCHECK(top < bottom);
      auto size = intersectLineSpans(tmp, a_buffer, a_it->chunk_handle,
                                     b_buffer, b_it->chunk_handle);
      if (size > 0) {
        res.appendLine(top, bottom, tmp.data(), tmp.data() + size);
        res.bounds_.join(SkIRect::MakeLTRB(
            tmp.data()->left, top, (tmp.data() + size - 1)->right, bottom));
      }
      cur_top = bottom;
      if (cur_top == a_it->bottom) {
        ++a_it;
      }
      if (cur_top == b_it->bottom) {
        ++b_it;
      }
    }
  }
  FML_DCHECK(a_it == a_end || b_it == b_end);
  return res;
}

MakeUnion()

DlRegion flutter::DlRegion::MakeUnion ( const DlRegion &  a, const DlRegion &  b  )

static

Creates union region of region a and b. Matches SkRegion a; a.op(b, SkRegion::kUnion_Op) behavior.

Definition at line 405 of file dl_region.cc.

                                                                 {
  if (a.isEmpty()) {
    return b;
  } else if (b.isEmpty()) {
    return a;
  } else if (a.isSimple() && a.bounds_.contains(b.bounds_)) {
    return a;
  } else if (b.isSimple() && b.bounds_.contains(a.bounds_)) {
    return b;
  }
 
  DlRegion res;
  res.bounds_ = a.bounds_;
  res.bounds_.join(b.bounds_);
  res.span_buffer_.reserve(a.span_buffer_.capacity() +
                           b.span_buffer_.capacity());
 
  auto& lines = res.lines_;
  lines.reserve(a.lines_.size() + b.lines_.size());
 
  auto a_it = a.lines_.begin();
  auto b_it = b.lines_.begin();
  auto a_end = a.lines_.end();
  auto b_end = b.lines_.end();
 
  FML_DCHECK(a_it != a_end && b_it != b_end);
 
  auto& a_buffer = a.span_buffer_;
  auto& b_buffer = b.span_buffer_;
 
  std::vector<Span> tmp;
 
  int32_t cur_top = std::numeric_limits<int32_t>::min();
 
  while (a_it != a_end && b_it != b_end) {
    auto a_top = std::max(cur_top, a_it->top);
    auto b_top = std::max(cur_top, b_it->top);
    if (a_it->bottom <= b_top) {
      res.appendLine(a_top, a_it->bottom, a_buffer, a_it->chunk_handle);
      ++a_it;
    } else if (b_it->bottom <= a_top) {
      res.appendLine(b_top, b_it->bottom, b_buffer, b_it->chunk_handle);
      ++b_it;
    } else {
      if (a_top < b_top) {
        res.appendLine(a_top, b_top, a_buffer, a_it->chunk_handle);
        cur_top = b_top;
        if (cur_top == a_it->bottom) {
          ++a_it;
        }
      } else if (b_top < a_top) {
        res.appendLine(b_top, a_top, b_buffer, b_it->chunk_handle);
        cur_top = a_top;
        if (cur_top == b_it->bottom) {
          ++b_it;
        }
      } else {
        auto new_bottom = std::min(a_it->bottom, b_it->bottom);
        FML_DCHECK(a_top == b_top);
        FML_DCHECK(new_bottom > a_top);
        FML_DCHECK(new_bottom > b_top);
        auto size = unionLineSpans(tmp, a_buffer, a_it->chunk_handle, b_buffer,
                                   b_it->chunk_handle);
        res.appendLine(a_top, new_bottom, tmp.data(), tmp.data() + size);
        cur_top = new_bottom;
        if (cur_top == a_it->bottom) {
          ++a_it;
        }
        if (cur_top == b_it->bottom) {
          ++b_it;
        }
      }
    }
  }
 
  FML_DCHECK(a_it == a_end || b_it == b_end);
 
  while (a_it != a_end) {
    auto a_top = std::max(cur_top, a_it->top);
    res.appendLine(a_top, a_it->bottom, a_buffer, a_it->chunk_handle);
    ++a_it;
  }
 
  while (b_it != b_end) {
    auto b_top = std::max(cur_top, b_it->top);
    res.appendLine(b_top, b_it->bottom, b_buffer, b_it->chunk_handle);
    ++b_it;
  }
 
  return res;
}

operator=() [1/2]

DlRegion & flutter::DlRegion::operator= ( const DlRegion &  )

default

operator=() [2/2]

DlRegion & flutter::DlRegion::operator= ( DlRegion &&  )

default

---

The documentation for this class was generated from the following files:

• display_list/geometry/dl_region.h
• display_list/geometry/dl_region.cc